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

[Ignacio C. <i6...@ho...>]

Hi,
for box-triangle test i use an algorithm similar to the one used to test convex volumes via plane
shifting. I simply take the plane of the triangle, the antiplane, the edge bevels and the axis
aligned bevels to build a 'fake' convex volume. Then shift the planes of the volume depending on the
distance of the plane to the center of the box and last clip the movement segment against the
volume. I have found this algorithm to be the fastest, however it requieres a lot of precomputation,
and is in many cases a waste of space.


Ignacio Castano
ca...@cr...


Charles Bloom wrote:
> 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).