Re: Triangle-Triangle Intersection Tests

[Steve Baker <sjbaker1@airmail.net>]

Miguel A. Osorio wrote:

>     I just recently finished coding my version of the algorithm for
> triangle-triangle intersection presented in the ERIT package (I got the
> algorithm outline in the book "Real-Time Rendering" from Moller and
> Haines, 2nd ed.). I believe it's working properly, but I'm not sure of
> it's efficiency.
The trick with these tests is not doing them!

You need to apply 'early-out' testing wherever possible.  Test bounding
spheres or bounding boxes first - only if those intersect should you
even consider testing triangles against each other.  You should be able
to avoid even transforming the triangle's vertices in most cases.

Every triangle-triangle test that I've ever seen has been considerably
expensive - but you can usually avoid doing all but a handful of them
each frame.

If the nature of your application is that there IS a need for a lot of
actual tests, you can still do quite a lot to help. There are decisions
you can make in implementing code within the triangle-triangle
intersector that greatly influence performance if you know things like
"90% ofmy tests result in no intersection"...or..."90% of my tests DO result
in an intersection".  Your algorithm needs to be sensitive to which of
those is most likely.

For example, it is common to compute the plane equation of one triangle
and substitute in each of the vertices of your other triangle to get
their (signed) distance from the plane - if all three vertex distances
have the same sign - then you know there is no intersection - and you
can punt the remainder of the test.  If you expect 90% of the tests
to fail to produce an intersection, it's worth doing that - but if
you expect 90% of tests to result in valid intersections (perhaps
because your previous bounding box test is so efficient) then you maybe
don't want to waste time doing that test.

So, if I were you, I'd look at the things you can do to avoid calling
the ERIT test at all - and if despite that, you still do too many
tests - then use your existing code to gather statistics about the
most likely results of the test and optimise for that case.

You should also consider whether you really NEED the results to the
precision that a triangle-triangle test would produce?   Would a
simple bounding box test be enough?

---------------------------- Steve Baker -------------------------
HomeEmail: <sjbaker1@airmail.net>    WorkEmail: <sjbaker@link.com>
HomePage : http://www.sjbaker.org
Projects : http://plib.sf.net    http://tuxaqfh.sf.net
           http://tuxkart.sf.net http://prettypoly.sf.net