0

I implemented SAT to check for collisions of 2 rotated rectangles. Everything works fine, but I noticed that as the objects move, the collision check loses precision.

I set the speed of the squares by (v * 5) * dt. I determined 5 is one meter in my simulation.

At some point, a collision is detected at that position of the objects:

enter image description here

Can you advise me on how to keep the high precision of collision checking? Somewhere I found information that multisampling can help. Can you explain to me what it is, how does it solve the precision loss problem and how to implement it?

I wrote my solution in fpc (pascal / lazarus) but it probably doesn't matter. Below is the code:

Creating rectangle corners:

rectangle[0].x := position.x-15;
rectangle[0].y := position.y-35;
rectangle[1].x := position.x+15;
rectangle[1].y := position.y-35;
rectangle[2].x := position.x+15;
rectangle[2].y := position.y+26;
rectangle[3].x := position.x-15;
rectangle[3].y := position.y+26;

Rotate rectangle:

for i:= 0 to 3 do
begin
tempX := rectangle[i].x - position.x;
tempY := rectangle[i].y - position.y;

// now apply rotation
rotatedX := tempX * cos(DegToRad(ang)) - tempY * sin(DegToRad(ang));
rotatedY := tempX * sin(DegToRad(ang)) + tempY * cos(DegToRad(ang));

tempRectangle[i].x := position.x + rotatedX;
tempRetangle[i].y := position.y + rotatedY;

end;

rotatedRectangle:=tempRectangle;

And collision checking. This is solution from this post: How to check intersection between 2 rotated rectangles? ported to pascal:

Types

TRectangle = array[0..3] of TMyPoint;

TMyPoint = record
x:real;
y:real;
end;

Collision checking:

res:=true; 

for i := 0 to 1 do //2 cars
begin

    // for each polygon, look at each edge of the polygon, and determine if it separates
    // the two shapes
polygon := polygons[i];

    for i1 := 0 to Length(polygon)-1 do
    begin

        // grab 2 vertices to create an edge
        i2 := (i1 + 1) mod 4;
        p11 := polygon[i1];
        p22 := polygon[i2];

        // find the line perpendicular to this edge
        normal.x := p22.y - p11.y;
        normal.y := p11.x - p22.x;

        minA.assigned := false;
        maxA.assigned := false;
        // for each vertex in the first shape, project it onto the line perpendicular to the edge
        // and keep track of the min and max of these values
        for j := 0 to 3 do 
        begin
            projected := normal.x * rectangleA[j].x + normal.y * rectanglA[j].y;
            if ((minA.assigned = false) or (projected < minA.value)) then
                begin
                     minA.value := projected;
                     minA.assigned:=true;;
                end;
            if ((maxA.assigned = false) or (projected > maxA.value)) then
                begin
                     maxA.value := projected;
                     maxA.assigned := true;
                end;
        end;

        // for each vertex in the second shape, project it onto the line perpendicular to the edge
        // and keep track of the min and max of these values
        minB.assigned:=false;
        maxB.assigned:=false;
        for j := 0 to 3 do  
        begin
            projected := normal.x * rectanglB[j].x + normal.y * rectanglB[j].y;
            if ((minB.assigned = false) or (projected < minB.value)) then
                begin
                     minB.value := projected;
                     minB.assigned :=true;
                end;
            if ((maxB.assigned=false) or (projected > maxB.value)) then
                begin
                     maxB.value := projected;
                     maxB.assigned:=true;
                end;
        end;

        // if there is no overlap between the projects, the edge we are looking at separates the two
        // polygons, and we know there is no overlap
        if ((maxA.value < minB.value) or (maxB.value < minA.value)) then
            begin
                              res := false;

            end;
    end;
    end;

   result := res;
Mlody87
  • 425
  • 1
  • 7
  • 19
  • It doesn't seem to be about precision. Did you check, if your polygons (vertices) are specified in either clockwise or counterclockwise order? – divanov42 Apr 22 '21 at 09:41
  • I'll check it out, good lead, thanks – Mlody87 Apr 22 '21 at 09:49
  • @divanov42 It looks like everything is ok with this – Mlody87 Apr 22 '21 at 10:28
  • Is this "res := false;" equivalent to this "return false"? In the question you referenced, the code returns from the function immediately, when the condition is met, in yours however it seems like it keeps going, and the returned result is whatever res is equal to in the last iteration of the loop. – divanov42 Apr 22 '21 at 10:54
  • Before first loop I set res:=true;. I forgot to copy this to topic. Anyway I check this one more time. – Mlody87 Apr 22 '21 at 11:03
  • @divanov42 I think it cant be problem because I set result true only at start. So even when loop keeps going once result set false it will set to the end. – Mlody87 Apr 22 '21 at 11:38
  • Is going away from SAT an option? I am fairly certain, that the problem is in implementation, and not precision - in the image your reactangles are far enough - precision problems will surface only if these two would be almost indistinguishable. Can't you just find if two unrotated rects intersect? Btw. SAT algorithm is only needed if you need to work w. arbitrary convex polygons, in your case task can be greatly simplified. If you choose to go w. SAT, then probably you should review the code from here: https://www.codeproject.com/Articles/15573/2D-Polygon-Collision-Detection. – divanov42 Apr 22 '21 at 12:12
  • @divanov42 I don't insist on the SAT. But will checking unrotated rectangles work, for example, when turning? Thank you, I'll check this link – Mlody87 Apr 22 '21 at 12:19
  • 1
    If you take two rectangles then simultaneously rotate them about the same point, the distance between them wouldn't change. For pretty much the same reason rotated rectangles will still be rectangles, with the same side lengths. – divanov42 Apr 22 '21 at 12:30
  • I rotate each rectangle around its own center, but maybe this is just fine. I will check, thanks – Mlody87 Apr 22 '21 at 12:32
  • I found also this: http://www.jeffreythompson.org/collision-detection/poly-poly.php I'll try to implement this and check if this is better. – Mlody87 Apr 22 '21 at 12:37
  • @divanov42 You were right, I probably had a bug in the implementation. I rewrote to pascal the code from the link above and it works much better :) Check collisions correctly :) Thanks for your help :) – Mlody87 Apr 22 '21 at 14:22
  • 1
    Glad I could help) Good luck with your project) – divanov42 Apr 23 '21 at 05:44

0 Answers0