Jump to content
  • Advertisement
Sign in to follow this  
mrbig

SAT Trouble

This topic is 4621 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello. I'm working on a 2D polygon-based physics engine and have implemented SAT (the Separating Axis Theorem) for collision detection. After hours of debugging (eventually I found out that I forgot to check the direction of the vector that pushes the objects apart), I finally made it work. However, my collision detection function still has one bug in it: Assuming there are two objects, a triangle and a rectangle. The rectangle is dynamic and the triangle is static. If I push the rectangle on an edge of the triangle, it just jumps a few meters away with an incorrect direction. Has anyone encountered such a problem? Can anyone help me solve it? If my description wasn't clear, tell me and i'll post a link to the .exe or the code.

Share this post


Link to post
Share on other sites
Advertisement
Quote:
Assuming there are two objects, a triangle and a rectangle.
The rectangle is dynamic and the triangle is static.
If I push the rectangle on an edge of the triangle, it just jumps a few meters away with an incorrect direction.
The first step is probably to clarify the problem a little. I take it you're doing a static SAT test and using the intersection information to push the rectangle away from the triangle, which remains stationary. The 'few meters' part doesn't convey much information since we have no context for it. I gather though that the result is noticably incorrect.
Quote:
If my description wasn't clear, tell me and i'll post a link to the .exe or the code.
I would both provide some more information about the problem, and post or link to the relevant code. It'd probably be easier to look at the code if you just posted the relevant functions here. From there, it's likely that someone will be able to spot the problem or at least point you in the right direction.

Share this post


Link to post
Share on other sites
Ok.
Here's a screenshot of the problem (screenshots from the program itselt, I just added some text):

What the heck?

There is no elasticity.
Objects are supposed to stop when they hit and get pusehd apart form eachother by the MTD.
In this case, the triangle is static so only the rectanlge gets pushed.
As you can see, in this picture, the rectangle hits the edge of the triangle and gets pushed wrongly.

Here's the code.
Looks really long 'cause I didn't divide it into subfunctions, but everything there is pretty obvious:



bool body_intersection_test(body_t a, body_t b, vec_t &push)
{
float min0, max0, min1, max1, temp, d0, d1;
int i, j , k, total_edge_num = a.edge_num + b.edge_num;
vec_t axis, offset;
float depth[total_edge_num];

if(a.validity != 1 || b.validity != 1)
return 2;

// Project A and B on the axes of A:

k = 0;

for(i = 0; i < a.edge_num; i++)
{
axis = a.normal;

// Project A:

min0 = vec_dot_product(axis, a.edge[0].world);
max0 = min0;

for(j = 1; j < a.edge_num; j++)
{
temp = vec_dot_product(axis, a.edge[j].world);

if(temp < min0) { min0 = temp; }
if(temp > max0) { max0 = temp; }
}

// Project B:

min1 = vec_dot_product(axis, b.edge[0].world);
max1 = min1;

for(j = 1; j < b.edge_num; j++)
{
temp = vec_dot_product(axis, b.edge[j].world);

if(temp < min1) { min1 = temp; }
if(temp > max1) { max1 = temp; }
}

if(min0 > max1 || min1 > max0)
return FALSE; // Found a separating axis. Bodies can't intersecting.

d0 = max0 - min1;
d1 = max1 - min0;

if(d0 < d1)
depth[k] = d0;
else
depth[k] = d1;

k++;
}

// Project A and B on the axes of B:

for(i = 0; i < b.edge_num; i++)
{
axis = b.normal;

// Project A:

min0 = vec_dot_product(axis, a.edge[0].world);
max0 = min0;

for(j = 1; j < a.edge_num; j++)
{
temp = vec_dot_product(axis, a.edge[j].world);

if(temp < min0) { min0 = temp; }
if(temp > max0) { max0 = temp; }
}

// Project B:

min1 = vec_dot_product(axis, b.edge[0].world);
max1 = min1;

for(j = 1; j < b.edge_num; j++)
{
temp = vec_dot_product(axis, b.edge[j].world);

if(temp < min1) { min1 = temp; }
if(temp > max1) { max1 = temp; }
}

if(min0 > max1 || min1 > max0)
return FALSE; // Found a separating axis. Bodies can't be intersecting.

d0 = max0 - min1;
d1 = max1 - min0;

if(d0 < d1)
depth[k] = d0;
else
depth[k] = d1;

k++;
}

// Find the axis with the minimal penetration depth:

temp = depth[0];
j = 0;

for(i = 1; i < total_edge_num; i++)
if(depth < temp)
{
temp = depth;
j = i;
}

if(j < a.edge_num)
{
push.x = depth[j] * a.normal[j].x;
push.y = depth[j] * a.normal[j].y;
}

else
{
k = j - a.edge_num;
push.x = depth[k] * a.normal[k].x;
push.y = depth[k] * a.normal[k].y;
}

vec_set(offset, a.pos.x - b.pos.x, a.pos.y - b.pos.y);

// Check if the push vector is pointing in the right direction:

if(vec_dot_product(offset, push) >= 0.0)
vec_scale(push, -1.0, -1.0);

// It actually made it through all the tests, the bodies must be intersecting.
return TRUE;
}


Share this post


Link to post
Share on other sites
<code>
k = j - a.edge_num;
push.x = depth[k] * a.normal[k].x;
push.y = depth[k] * a.normal[k].y;
</code>
that's wrong.

should be

<code>
k = j - a.edge_num;
push.x = depth[j] * a.normal[k].x;
push.y = depth[j] * a.normal[k].y;
</code>

Share this post


Link to post
Share on other sites
And one more change:
k = j - a.edge_num;
push.x = depth[j] * b.normal[k].x;
push.y = depth[j] * b.normal[k].y;

Share this post


Link to post
Share on other sites
Thanks alot, Oliii and Jyk!
Both of you were correct and now it works perfectly!
By the way, Oliii, it was your tutorial that helped me see my first mistake about the MTD direction. If it wasn't for you, I would be spending hours to find that mistake.
Since you're both very helpful, I'll give you both a good rating. :D

Share this post


Link to post
Share on other sites
Quote:
Original post by mrbig
What SAT code is deprecated? Mine? What's wrong with it? :?


It's not wrong. It looks like the old SAT code I used, but there has been some improvements.

for example,


if(vec_dot_product(offset, push) &gt;= 0.0)
vec_scale(push, -1.0, -1.0);



is unnecessary, and potentially dangerous in some situations (very long thin objects). But it's just for the sake of arguments. I also included time-based movement.

If it works for you, then that's cool.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!