SAT Trouble
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.
Quote:Assuming there are two objects, a triangle and a rectangle.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.
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.
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.
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:
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; // 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;}
<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>
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>
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;
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
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
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]
btw, that SAT code is deprecated. but anyway, should work for basic shapes.
[Edited by - oliii on October 23, 2005 5:10:56 PM]
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) >= 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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement