• Advertisement
Sign in to follow this  

2D Triangle-Triangle Collision Detection

This topic is 4402 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

I have implemented working triangle against triangle collision detection in 2D. I am using the method of separation axis, as I plan to implement 2D rigid body dynamics. The problem, however, is that currently I am using 36 dot products (+world space transformations) which certainly sounds a lot. Especially for 2D. This is the way I am doing it: 1. project all vertices of triangle a and b to a's edge normals. 2. check for overlap 3. if there is no collision, project all vertices of a and b to b's edge normals. 4. check for overlap How expensive should it be? Are there better alternatives than this? I've tested it with multiple sets of triangles and it certainly seems to work. If I only test for one of the triangles there are places where one of the triangles gets "shadowed" by the other triangle and my system reports collision even if there's none. Ideas / Criticism appreciated.

Share this post


Link to post
Share on other sites
Advertisement
There is probably very little you can do to the algorithm itself, so the best way to increase performace would be to avoid performing the algorithm at all. You can do things like keep bounding circles around each triangle and first test if the circles intercept before even considering the triangles themselves. I would also imagine that you have larger bounding areas around whole objects as well.

In any case, though, I'd wager that your 36 dot product figure is only realized during the worst possible case - both your tests completely fail, or the second triangle collides during the very last test. This worst case cenario should almost never happen if you use bounding circles.

But overall, I wouldn't worry too much about it right now - if it works, great - you've got the hardest part done. Now move on to other things, and if the performance becomes unnacceptable, do something about it then.

Hope that helps. Good luck.

Share this post


Link to post
Share on other sites
I am already using bounding circle radius test for each "model". I think the algorithm is mathematically valid right now (although I am not doing "true" projections, merely dot products).

However, on principle it'd be nice to gain some feedback wether this kind of implementation is valid. 36 tests is abosulte maximum, because I only test the other triangle if one of the primary tests fails. So its either none, 18 or 36 dot products.

My game is very simple, so I doubt speed will be an issue on modern computers,but I have no idea if this solution is particularly elegant. This, too, I would like to know just "because".

Share this post


Link to post
Share on other sites
Quote:
Original post by el capitan
Are there better alternatives than this? I've tested it with multiple sets of triangles and it certainly seems to work. If I only test for one of the triangles there are places where one of the triangles gets "shadowed" by the other triangle and my system reports collision even if there's none.
I'm not sure what this means exactly, but it does sound like a bug in your implementation.

The above poster pretty much covered everything else; he's right that appropriate broad-phase culling is probably a more important optimization than tweaking the separating axis test.

If for some reason you really want to squeeze every last bit of performance out of the SAT, you can exploit the fact that a polygon 'knows' its projection onto the normals of its own faces. That projection never changes, but is simply offset by the position of the polygon (to take advantage of this, your triangles would have to be stored in local space). This would cut it down to 24 dot products, I think.

Share this post


Link to post
Share on other sites
Quote:
Original post by el capitan
I am already using bounding circle radius test for each "model". I think the algorithm is mathematically valid right now (although I am not doing "true" projections, merely dot products).

However, on principle it'd be nice to gain some feedback wether this kind of implementation is valid. 36 tests is abosulte maximum, because I only test the other triangle if one of the primary tests fails. So its either none, 18 or 36 dot products.

My game is very simple, so I doubt speed will be an issue on modern computers,but I have no idea if this solution is particularly elegant. This, too, I would like to know just "because".
Assuming your implementation is correct, the method you're using is perfectly appropriate, and probably will be plenty fast even without further optimizations.

Share this post


Link to post
Share on other sites
Quote:
Original post by SageofAges
Try line-line intersection test for the lines of one poly to another.
For most intersection problems (including the OP's), line-line intersection is not the preferred method. What the OP is already doing is better.

Share this post


Link to post
Share on other sites
Doing line-line intersection can be faster than your current method as long as you do it correctly. Since you don't actually care about the exact point of intersection you can use the following method to check if two lines intersect:

Here P1, P2, P3, and P4 are the end points of the lines
line1 = P1-P2
line2 = P3-P4
if P1 and P2 are on opposite sides of line2 and P3 and P4 are on opposite sides of line1 then the two lines intersect. To find which side of a line a point is on you can take the dot product of (checking P1 with line2 as an example):
(P1 - P3) dot N2 (where N2 is the edge normal of line2)
- note: P3 can be any point that is on line2
If the result is positive the point is on the side of the line where the edge normal points, if it is negative it is on the other side.

There are two cases where the triangles intersect:
1) Two of the edges intersect
2) All of the vertices of one triangle are inside the other

You need to do a dot product for each vertex in one triange with each edge in the other. This is 2 * 3 * 3 = 18 dot products total. This method is also nice because you can detect early whether or not there is a collision. As soon as you have two edges that intersect you know the triangles intersect. Also if all 3 vertices are on the "outside" of one of the lines of the other triangle then clearly the two triangles do not intersect. If one of the vertices is on the inside of all three edges of the other triangle (ie. the vertex is inside the other triangle) then they do intersect. If you're careful about when you actually do the dot products you can have anywhere from 3 to 18 dot products in an intersection test.

Share this post


Link to post
Share on other sites
Quote:
Original post by thooot
Doing line-line intersection can be faster than your current method as long as you do it correctly. Since you don't actually care about the exact point of intersection you can use the following method to check if two lines intersect:

Here P1, P2, P3, and P4 are the end points of the lines
line1 = P1-P2
line2 = P3-P4
if P1 and P2 are on opposite sides of line2 and P3 and P4 are on opposite sides of line1 then the two lines intersect. To find which side of a line a point is on you can take the dot product of (checking P1 with line2 as an example):
(P1 - P3) dot N2 (where N2 is the edge normal of line2)
- note: P3 can be any point that is on line2
If the result is positive the point is on the side of the line where the edge normal points, if it is negative it is on the other side.

There are two cases where the triangles intersect:
1) Two of the edges intersect
2) All of the vertices of one triangle are inside the other

You need to do a dot product for each vertex in one triange with each edge in the other. This is 2 * 3 * 3 = 18 dot products total. This method is also nice because you can detect early whether or not there is a collision. As soon as you have two edges that intersect you know the triangles intersect. Also if all 3 vertices are on the "outside" of one of the lines of the other triangle then clearly the two triangles do not intersect. If one of the vertices is on the inside of all three edges of the other triangle (ie. the vertex is inside the other triangle) then they do intersect. If you're careful about when you actually do the dot products you can have anywhere from 3 to 18 dot products in an intersection test.
By 'line intersection' I was actually referring more to the specific algorithm linked to in SageofAges post.

Anyway, the method you describe above is actually more 'separating axis' than 'line intersection', IMO. Keep in mind that the OP mentioned this is for a rigid body simulator, in which case he'll probably eventually need contact info (time of intersection, penetration vector, contact points and normals, or what have you). I can't say this for sure, but I think by the time you incorporated all this into the 'line intersection' method, it would basically become equivalent to the standard SAT algorithm.

Share this post


Link to post
Share on other sites
Quote:
Original post by thooot
stuff about lines


In my opinion that might actually end up being slower, since it doesn't make much difference whether you project edges or vertices. In fact that will most likely retain the same problem where small triangle can get shadowed by much bigger triangle (it can be solved, by checking collision for both triangles) as all of its vertices end up inside the bigger triangle within the projection.


http://img238.imageshack.us/my.php?image=problem8xx.gif

I have no idea how long that imageshack link will work. Either way that should demonstrate why there is a need for tests from both sides.

Share this post


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

  • Advertisement