Sign in to follow this  

Trying to understand triangle to triangle collision

This topic is 3105 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 am trying to learn triangle to triangle collision and there is several things I do not understand. I am been continually pointed to this source code http://jgt.akpeters.com/papers/Moller97/tritri.html. While it is decently documented, I have run into a few issues. 1) First of all, what is "float N[3]"? Is it normals? If so, for what triangle? Also, if it is normals why only pass in the normals for one triangle? 2) Am I correct to assume that V0, V1 and V2 are the vertices for the first triangle? Also that U0, U1 and U2 are the verticies for the second triangle? 3) POINT_IN_TRI just looks like a complete mess. Could anyone explain what the variavles a, b, c, d0, d2 and d2 really mean? 4) In EDGE_AGAINST_TRI_EDGES, what is Ax and Ay doing? 5) Finally, what in the world is EDGE_EDGE_TEST doing? I just have no idea ....

Share this post


Link to post
Share on other sites
Wow, what a MESSY piece of code that is! Frankly, I don't have the patience to reverse engineer exactly the logic of how variables are moved around in there. I don't think this is a good reference. It may be robust. It may be fast and based on good theory, but it is ugly.

So, I'll try to answer some things:

Yes, you are correct about V[*] and U[*].

In coplanar_tri_tri, N[3] appears to be the normal of some plane in which the coplanar test will be done. It's confusing. If you look at the code, N appears to only be used to compute i0 and i1, which aren't even used in the code as written. The i0 and i1 ared used down in the macros EDGE_AGAINST_TRI_EDGES and POINT_IN_TRI. This is an ugly, ugly trick. You can't see from the macro signature that they implicitly expect variables to be defined. This code would be a hell of a lot cleaner if he just passed i0 and i1 into the macros rather than have them hidden. You could not use that macro anywhere that didn't have an i0 and i1 defined. So, the N is some representative plane's normal. It doesn't at all have to either triangle's normal. I suspect that elsewhere in the code he may compute an average normal, e.g., the average of normals for two triangles, and passes that in as N. This is used to (down in EDGE_AGAINST* and POINT_IN* macros) project the triangles onto a cardinal plane, either the xy, yz, or zx plane, to make the test a 2D problem instead of a 3D problem. You could, actually, just give it any normal at all. But that would be problematic. Finding an average normal between two triangles is a basically appropriate thing to do, since it has the best chance of picking a good cardinal plane to project into.

The reason for picking a cardinal plane is that the project is super easy...just use those indices i0 and i1 (whatever they are computed to be) to pick off the appropriate coordinates of the input triangles. You could project everything into the absolute plane of one of the triangles, or onto the true average plane, but that would be more expensive. The cardinal plane projection is FAST.

I don't think you would be using coplanar_tri_tri directly, so not sure you really need to know all that.

POINT_IN_TRI is basically determining whether the point lies to the same side of all edges. The point will be inside if it is on the left (when you sit a the start vertex of an edge and look towards the end vertex) of ALL edges or if it is on the right of all edges. If it is on the left of some edges and right of some edges, it cannot be inside. (a,b) is for a given edge, a vector perpendicular to the edge and pointing outside the triangle if you place it at the start vertex for the edge. c is an offset used to translate V0 into a local coordinate system with the origin at the start of the edge. The d's are the perpendicular distance from V0 to the given edge, with a positive value indicating the point lies on the right side of the edge and a negative value indicating the point lies on the left side of the edge. If all d's are positive or all d's are negative, then the point is inside the triangle.

In EDGE_AGAINST_TRI_EDGES, this is another DIRTY TRICK. The Ax and Ay variables are used inside the EDGE_EDGE_TEST macro. He should have passed those variable in as parameters. This is obfuscated code. Ugly.

As for EDGE_EDGE_TEST, the Graphics Gems III reference may be better, but the idea is it is merely checking to see if a given edge of the first triangle intersects an edge of the other triangle. It does this by looking at two cross products. (f and d are cross products results. This is a 2D problem, complements of the magical canonical plane projections using variables i0 and i1, and the 2D cross product result is a scalar not a vector.) One cross product is based on the two edge vectors, and the other is based on crossing a vector that joins the start vertices of the two edges with the vector of one of the other triangle edges. The edge of triangle V is represented by (Ax, Ay), which was calculated outside the macro and not passed in (ugly code!). (Bx, By) is the U0, U1 edge vector. And (Cx, Cy) is the vector from U0 to V0. The two edges intersect depending on the relationship of the cross products. If you draw this out on paper and look at various scenarios of edges that do or do not intersect, it may help to clarify this algorithm. You need to have a fairly good understanding of vector algebra and cross products to follow it.

Hope that helps!

Share this post


Link to post
Share on other sites
I looked at that code a long time ago when Tomas mentioned it was faster than mine (which was based on SAT). His algorithm is basic algebra. Why it was "published" is beyond me, but now everyone references it as the definitive reference. The algorithm is as follows for triangles A and B, and the steps are executed in the order shown.

1. If triangle A does not intersect plane of triangle B, no intersection.

2. If triangle B does not intersect plane of triangle A, no intersection.

3. Planes of triangle A and triangle B must intersect. Compute the line of intersection L.

4. Compute interval IA that is the intersection of L and triangle A.

5. Compute interval IB that is the intersection of L and triangle B.

6. If IA and IB do not overlap. no intersection of triangles.

7. If IA and IB overlap, you have the point or segment of intersection of the triangles.

Share this post


Link to post
Share on other sites
Quote:
Original post by grhodes_at_work
Wow, what a MESSY piece of code that is! Frankly, I don't have the patience to reverse engineer exactly the logic of how variables are moved around in there. I don't think this is a good reference. It may be robust. It may be fast and based on good theory, but it is ugly.


What do you think a good reference would be?

Quote:
Original post by grhodes_at_workIn EDGE_AGAINST_TRI_EDGES, this is another DIRTY TRICK. The Ax and Ay variables are used inside the EDGE_EDGE_TEST macro. He should have passed those variable in as parameters. This is obfuscated code. Ugly.


While I definitely agree with that, what is the purpose of Ax and Ay though?

It seems as if the coplanar_tri_tri function is not something I would be using for plenty of reasons. I took a look at NoDivTriTriIsect and that makes about zero sense also.

Share this post


Link to post
Share on other sites
I don't have a great reference to suggest. Dave's approach based on the separating axis theorem (SAT) may be a more intuitive representative implementation. Christer Ericsson talks briefly about a few techniques in his book, Real-time Collision Detection, and in fact gives a plain English description of Moller's algorithm. It's a great book and recommended if you are able to buy books. I'm not sure how robust Moller's method is, though, if you were to continue using it.

Share this post


Link to post
Share on other sites
Quote:
Original post by simotix
What do you think a good reference would be?


The article that accompanies the code is a good reference. My objection is not to the article, it is to having a "journal" publication for something that is easily derived from basic principles.

Quote:

It seems as if the coplanar_tri_tri function is not something I would be using for plenty of reasons. I took a look at NoDivTriTriIsect and that makes about zero sense also.


I failed to mention in my Step 3 that the planes could be coincident, in which case the triangles are coplanar. You still need to handle this case in a general triangle-triangle collision routine.

Regarding NoDivTriTriIsect, I recall mentioning to Tomas that he could speed up his implementation slightly by deferring a division until it was actually needed.

Share this post


Link to post
Share on other sites

This topic is 3105 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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this