# SAT Trouble

## Recommended Posts

mrbig    100
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 on other sites
jyk    2094
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 on other sites
mrbig    100
Ok.
Here's a screenshot of the problem (screenshots from the program itselt, I just added some text):

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[i];      // 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[i];      // 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[i] < temp)   {    temp = depth[i];    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 on other sites
oliii    2196
<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 on other sites
jyk    2094
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 on other sites
mrbig    100
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 on other sites
Mattman    336
I got a 1300 on my SAT's.

##### Share on other sites
oliii    2196
d'oh!

btw, that SAT code is deprecated. but anyway, should work for basic shapes.

[Edited by - oliii on October 23, 2005 5:10:56 PM]

##### Share on other sites
mrbig    100
What SAT code is deprecated? Mine? What's wrong with it? :?

##### Share on other sites
oliii    2196
Quote:
 Original post by mrbigWhat 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 on other sites
mrbig    100
The piece of code you posted above looks like the old SAT code you used because it is taken from the old SAT code you used. xD
Everything else was written by me, though.
It would be very nice of you to tell me what could be improved. :D

##### Share on other sites
oliii    2196
First off, it would be nice to split the code into function blocks.

void body_interval_on_axis(vec_t axis, body_t a, float& min, float max){   min = vec_dot_product(axis, a.edge[0].world);   max = min;      for(j = 1; j < a.edge_num; j++)    {     temp = vec_dot_product(axis, a.edge[j].world);          if(temp < min) { min = temp; }      if(temp > max) { max = temp; }    }}bool interval_overlap(float min0, float max0, float min1, float max1, float& depth){   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 = d0;   else    depth = d1;    return TRUE;}bool body_intersection_test_on_axis(vec_t axis, body_t a, body_t b, float& depth){    float mina, maxa;    float minb, maxb;    body_interval_on_axis(axis, a, mina, maxa);    body_interval_on_axis(axis, b, minb, maxb);    return interval_overlap(mina, maxa, minb, maxb, depth);}bool body_intersection_push_vector(body_t a, body_t b, vec_t &push, float depth[]){ int i, j, total_edge_num = a.edge_num + b.edge_num; vec_t offset; temp = depth[0]; j = 0;  for(i = 1; i < total_edge_num; i++)  if(depth[i] < temp)   {    temp = depth[i];    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[j]  * b.normal[k].x;   push.y = depth[j]  * b.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;}bool body_intersection_test(body_t a, body_t b, vec_t &push){ int i, k, total_edge_num = a.edge_num + b.edge_num; vec_t axis; float depth[total_edge_num];  if(a.validity != 1 || b.validity != 1)  return 2;  k = 0;  // Project A and B on the axes of A: for(i = 0; i < a.edge_num; i++)  {   axis = a.normal[i];   if (!body_intersection_test_on_axis(axis, a, b, depth[k]))       return FALSE;   k++;  }   // Project A and B on the axes of B: for(i = 0; i < b.edge_num; i++)  {   axis = b.normal[i];   if (!body_intersection_test_on_axis(axis, a, b, depth[k]))       return FALSE;   k++;  }   return body_intersection_push_vector(a, b, push, depth);}

in the function interval_overlap() the signs of d1 and d2 can be used directly, thus avoiding the problems I pointed out in my previous post.

bool interval_overlap(float min0, float max0, float min1, float max1, float& depth){   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 = -d0; // sign!   else    depth = d1;    return TRUE;}bool body_intersection_push_vector(body_t a, body_t b, vec_t &push, float depth[]){ int i, j, total_edge_num = a.edge_num + b.edge_num; temp = depth[0]; j = 0;  for(i = 1; i < total_edge_num; i++)  if(fabs(depth[i]) < fabs(temp)) // depth values aren't always positive!   {    temp = depth[i];    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[j] * b.normal[k].x;   push.y = depth[j] * b.normal[k].y;  }   // It actually made it through all the tests, the bodies must be intersecting. return TRUE;}

pushing it further, you don't have to use depth values, you can use push vectors for each axis, and compare their length sqaured at the end.

void body_interval_on_axis(vec_t axis, body_t a, float& min, float max){   min = vec_dot_product(axis, a.edge[0].world);   max = min;      for(j = 1; j < a.edge_num; j++)    {     temp = vec_dot_product(axis, a.edge[j].world);          if(temp < min) { min = temp; }      if(temp > max) { max = temp; }    }}bool interval_overlap(float min0, float max0, float min1, float max1, float& depth){   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 = -d0;   else    depth = d1;    return TRUE;}bool body_intersection_test_on_axis(vec_t axis, body_t a, body_t b, vec_t& axis_push){    float depth;    float mina, maxa;    float minb, maxb;    body_interval_on_axis(axis, a, mina, maxa);    body_interval_on_axis(axis, b, minb, maxb);    if (!interval_overlap(mina, maxa, minb, maxb, depth))        return FALSE;    vec_mul(axis_push, axis, depth);    return TRUE;}bool body_intersection_push_vector(body_t a, body_t b, vec_t &push, vec_t axis_push[]){ int i, j, total_edge_num = a.edge_num + b.edge_num; float push_length_squared; push = axis_push[0]; push_length_squared = vec_dot(push, push); for(i = 1; i < total_edge_num; i++) {  float axis_push_length_squared;  axis_push_length_squared = vec_dot(axis_push[i], axis_push[i]);  if(axis_push_length_squared < push_length_squared)  {     push = axis_push[i];     push_length_squared = vec_dot(push, push);   }   // It actually made it through all the tests, the bodies must be intersecting. return TRUE;}bool body_intersection_test(body_t a, body_t b, vec_t &push){ int i, k, total_edge_num = a.edge_num + b.edge_num; vec_t axis; vec_t axis_push[total_edge_num];  if(a.validity != 1 || b.validity != 1)  return 2;  k = 0;  // Project A and B on the axes of A: for(i = 0; i < a.edge_num; i++)  {   axis = a.normal[i];   if (!body_intersection_test_on_axis(axis, a, b, axis_push[k]))       return FALSE;   k++;  }   // Project A and B on the axes of B: for(i = 0; i < b.edge_num; i++)  {   axis = b.normal[i];   if (!body_intersection_test_on_axis(axis, a, b, axis_push[k]))       return FALSE;   k++;  }   return body_intersection_push_vector(a, b, push, axis_push);}

there is no need to keep normals of polygon edges. You can use polygon edges directly, unormalised (moot point). Although if you do that, you have to remember that depth values are all scaled by the corresponding axis length.

You can also track the push vector as you go along.

void body_interval_on_axis(vec_t axis, body_t a, float& min, float max){   min = vec_dot_product(axis, a.edge[0].world);   max = min;      for(j = 1; j < a.edge_num; j++)    {     temp = vec_dot_product(axis, a.edge[j].world);          if(temp < min) { min = temp; }      if(temp > max) { max = temp; }    }}bool interval_overlap(float min0, float max0, float min1, float max1, float& depth){   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 = -d0;   else    depth = d1;    return TRUE;}bool body_intersection_test_update_push(vec_t axis, float depth, vec_t& push, float& push_length_squared){    vec_t axis_push;    float axis_push_length_squared;    float axis_length_squared;    axis_length_squared = vec_dot(axis, axis);    vec_mul(axis_push, axis, depth / axis_length_squared);    axis_push_length_squared = vec_dot(axis_push, axis_push);    if (axis_push_length_squared < push_length_squared || push_length_squared < 0.0f)    {        push_length_squared = axis_push_length_squared;        push = axis_push;    }       return TRUE;}bool body_intersection_test_on_axis(vec_t axis, body_t a, body_t b, vec_t& push, float& push_length_squared){    float depth;    float mina, maxa;    float minb, maxb;    body_interval_on_axis(axis, a, mina, maxa);    body_interval_on_axis(axis, b, minb, maxb);    if (!interval_overlap(mina, maxa, minb, maxb, depth))        return FALSE;     return body_intersection_test_update_push(axis, depth, push, push_length_squared);}bool body_intersection_test(body_t a, body_t b, vec_t &push){ int i, ip1; vec_t edge; vec_t axis; float push_length_squared = -1.0f; // initiaise to impossible value  if(a.validity != 1 || b.validity != 1)  return 2;  // Project A and B on the axes of A: i = a.edge_num-1; for(ip1 = 0; ip1 < a.edge_num; i = ip1, ip1++)  {   vec_sub(edge, a.edge[ip1], a.edge[i]);   axis = vec_t(-edge.y, edge.x);   if (!body_intersection_test_on_axis(axis, a, b, push, push_length_squared))       return FALSE;  }   i = b.edge_num-1; for(ip1 = 0; ip1 < b.edge_num; i = ip1, ip1++)  {   vec_sub(edge, b.edge[ip1], b.edge[i]);   axis = vec_t(-edge.y, edge.x);   if (!body_intersection_test_on_axis(axis, a, b, push, push_length_squared))       return FALSE;  }  return TRUE;}

##### Share on other sites
mrbig    100
"in the function interval_overlap() the signs of d1 and d2 can be used directly"
So no need to do the dot product to check the direction of the MTD?
Ok, i'll fix that.

"you don't have to use depth values, you can use push vectors for each axis, and compare their length sqaured at the end."
So no need to calculate and save all those depth values?
Sounds pretty good but I don't really get it...

"there is no need to keep normals of polygon edges. You can use polygon edges directly, unormalised (moot point). Although if you do that, you have to remember that depth values are all scaled by the corresponding axis length."

But if i'll do so, i'll have to take square roots in every MTD and rebound calculation, right?
In that case, I rather waste a few bytes on the normals and rotate them along with the object using precalculated sines and cosines.
After all, 3D computer games store thousands of them for the model illumination and it works fine.

##### Share on other sites
oliii    2196
Quote:
 Original post by mrbig"in the function interval_overlap() the signs of d1 and d2 can be used directly"So no need to do the dot product to check the direction of the MTD?Ok, i'll fix that.

but when doing comparisons of numbers to get the smallest, remember to use fabs().

Quote:
 Original post by mrbig"you don't have to use depth values, you can use push vectors for each axis, and compare their length sqaured at the end."So no need to calculate and save all those depth values?Sounds pretty good but I don't really get it...

The depth you get for each separation axis, really is a way to tell by how much the intervals overlap, and by how much you should push an object so the intervals along that axis stop overlapping. In the end, it is equivalent to pushing the objects by (axis * depth), for a given separation axis.

so, instead of storing depth values for each axis, you store (depth * axis) as a vector. And when you try to find the smallest of the push vectors, you take the one which as the smallest length squared (which is a simple dot product).

Why do that? Well, it would have prevented you having your particular bug in the first place. Secondly, it has to do with improving the algo and avoiding allocating a cache to store the vectors. OK, not big deal, but that's the way I'd improve things, since you asked. This becomes particularly handy when moving to swept tests, then you'd have to cache more data, and it gets messy. First, the algo has to be simple and working. Then after that, if you need full optimisations, you can think of doing that caching and comparisons at the end. If the algo works and it's nice and tidy first, it's a lot easier to debug (by for example, comparing values between optimised and non-optimised).

Quote:
 Original post by mrbig"there is no need to keep normals of polygon edges. You can use polygon edges directly, unormalised (moot point). Although if you do that, you have to remember that depth values are all scaled by the corresponding axis length."But if i'll do so, i'll have to take square roots in every MTD and rebound calculation, right?In that case, I rather waste a few bytes on the normals and rotate them along with the object using precalculated sines and cosines.After all, 3D computer games store thousands of them for the model illumination and it works fine.

you dont compare lengths, but squared lengths, which is just a dot product (where the length is a square root of a dot product). Again, it's not necessary, but it is neater in my opinion, and don't require precalculations and preconceptions for objects (the less the better in my experience, if you can avoid them). It's nice to know the algorithm can work efficiently that way too (so it can be extended to 3D for example).

##### Share on other sites
mrbig    100
I'm not trying to argue with you, really, but I just don't get it...
You said:

"instead of storing depth values for each axis, you store (depth * axis) as a vector. And when you try to find the smallest of the push vectors, you take the one which as the smallest length squared (which is a simple dot product). "

So instead of doing two subtractions for every axis, saving the result in a float array with [total_edge_num] elements and comparing them, I can calculate depth * axis for every axis, store it in a vector array with [total_edge_num] elements, (which is 2x bigger 'cause vec_t consists of two floats) and than compare their squared lenghts, which is another dot product per axis.

Am I missing something?
I hope i'm not starting to be annoying...
I could just copy-paste all that optimized code you wrote there, but that's not my style. I don't like using something I don't understand.

[OFF TOPIC]

Hey, take a look!
Somebody rated me one point up!
Wow, I must have been very helpful... [rolleyes]

##### Share on other sites
oliii    2196
It's not a problem with the code, or efficiency, it's the way I work. OK, the code here is not as efficient, but, if you get curious about expanding the algo further, caching would make it harder to explain, because there will be so many other things to track, and it will turn into a mess.

Quote:
 "So instead of doing two subtractions for every axis, saving the result in a float array with [total_edge_num] elements and comparing them, I can calculate depth * axis for every axis, store it in a vector array with [total_edge_num] elements, (which is 2x bigger 'cause vec_t consists of two floats) and than compare their squared lenghts, which is another dot product per axis."

first of, the memory requirement here is irrelevant. It's all allocated in the stack, and freed after the algo exits. This part of the program is only a step towards freeing you from having to cache stuff in the first place. Instead, you do just-in-time calculations. That also frees you from allocating stuff at run time, either on the heap (very bad), of on the stack (not so bad).

Again, I do not want to use normals, because of the preprocessing and extra dependencies involved in that case (i.e. a need to keep normals for edges, extra data, extra things to worry about). I prefer low level stuff, which works with the minimum amount of inputs (just a loop of vertices). That forces you to use extra dot products, but the cost is negligeable. The most costly thing on processors aren't ops, but jumps and dereferencing / cache misses.

Anyway, I don't care so much about efficiency when presenting stuff. Of course it's gonna be slower than caching data at the end of the algo, but that kind of methodology is more about optimisations than linked to the algorithm, and I'm not interested in optimisations. I want to present a complete thing, which may be slower, but that you can shape into something fast in your own time (like add normals to edges, add large caches, dont do just-in-time, but process the data only when a collision occurs, ect...). There are better pre-processing to be done anyway (like becuase edges are sometimes parallel to each other, you don't need to test all edges).

Don't worry about it then, ignore the posts if it confuses you. I should have never written the code with cached values in the first place anyway.

As long as you understand the process (minimise the MTD using just-in-time calculations, compare squared lengths, no cache), that's enough, even if you thing it's irrelevant and useless, then if you decide to jump into time-based algos ansd read that stuff, you'll see where this is going.

##### Share on other sites
mrbig    100
Ok.
Just one more thing:
Can you please post an example code for me on how to find the contact point of two polygons?
I know you already wrote about it in your tutorial, but if you're not too busy, can you please rewrite it in a way it would fit the rest of my SAT code?

I would figure it out myself, but i've wasted so much time figuring out collision detection and response, and I got so many other things to add to my engine and I could really use some more help.

Thanks for all your help. :)

##### Share on other sites
oliii    2196
findint contact points is separate from the SAT.

You basically take the MTD vector (Push vector) as your collision normal, and find the support features (edge or vertex, for 2D polygons) along that normal on both polys.

depending on edge-edge, point-edge pairs, you just work out the intersection point quite easily.

                      \  p0   /             ^      +---------*-----------+     |      |       \ | /         |     |  PUSH      |        \|/          |     |      |         *           |     |      |       p1            |

          |                         |          | p0              q0      |        +------+-----------------+       |    \     |                 /       |          \    | p1             / q1     |      \   +---------------/-+-------+       \                 /             \               /             \             /

finding the pairs (p0, p1) and (q0, q1) is easy, and it's just careful coding.

[Edited by - oliii on October 26, 2005 7:16:35 PM]