3
\$\begingroup\$

I'm done implementing Moller's tri-tri intersection routine. It gives you the location of where each triangle edge intersects the line of intersection between the 2 triangle planes:

enter image description here

Really you get the point location in the form of t values along the (really big) purple ray shown above. So you can tell if the triangle intersects if the t values are overlapping..?

That's what the paper says. But I can show you scenarios where the t values are overlapping, but the triangles don't intersect:

enter image description here

So I can't seem to figure out which edge value to discard.

The original paper is here: http://fileadmin.cs.lth.se/cs/Personal/Tomas_Akenine-Moller/pubs/tritri.pdf

\$\endgroup\$
1
  • \$\begingroup\$ Can you explain more about what we see in the pictures and can you tell something about your implementation and the general idea of the algorithm? With the information we have now all I can say 'you probably did something wrong'. \$\endgroup\$
    – Roy T.
    Aug 7, 2013 at 18:10

1 Answer 1

3
\$\begingroup\$

It's not very clearly explained in the paper, but you can tell which two out of the three edges to look at by seeing which vertices are on which side of the other triangle's plane.

For instance, if triangle 1's vertices are A, B, C, and A and B are on one side of triangle 2's plane and C is on the other side of triangle 2's plane, then AC and BC are the edges that cross the plane, and those two are the edges to look at to get the t-interval for triangle 1. Swap the triangles and repeat the logic to get the t-interval for triangle 2.

You should always get one vertex on one side of the other triangle's plane and two on the other side, since if all three were on the same side of the plane then the triangles don't intersect and this would have been detected earlier in the algorithm.

BTW, there's Moller's sample code for this algorithm on the web (the link in the original paper is dead, but I found this one by following a link from the Real-Time Rendering intersection test table). The relevant part looks like the NEWCOMPUTE_INTERVALS macro.

\$\endgroup\$
1
  • \$\begingroup\$ Sweet! I fixed up Hullinator, now working! \$\endgroup\$
    – bobobobo
    Aug 8, 2013 at 1:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .