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:
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;