[Algorithms] fast triangle-segment test *with precomputation*

[Charles B. <cb...@cb...>]

Ok, so the Moller+Haines triangle-segment test is about
as good as it gets without any precomputation.  The
question is, how fast can you get with arbitrary
precomputation?  For example, I can precompute the
plane of the triangle, and the three perpendicular
planes which go through the edges.  Then the intersections
are all rays that hit the plane of the triangle and
whose intersection point is inside the three planes.
(BTW I don't care about computing the barycentric
coordinates).

Oh, BTW I also don't have the ray normal, so the 'd' used
in Moller+Haines requires a sqrt() for me to find, so
that's quite bad.  I think I could probably get the sqrt
out of there and push the length-squared of the ray through
the math to help it a bit.

The application here is when I have one triangle and I'm
about to do thousands of segment-triangle intersection tests
(actually, lots of bbox-triangle tests, but that requires
a segment-triangle test).


--------------------------------------
Charles Bloom           www.cbloom.com