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

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

Ok, you have a good point, but isn't it even simpler than that?

I have one plane for the triangle, and 3 planes through the edges that
are perpendicular to the plane of the triangle.

To test for bbox-triangle do :

1. bbox must intersect the plane of the triangle.
2. bbox must be intersect or behind all 3 edge planes.

That's it !  Four tests, all of them providing great quick-rejection.
This is simpler, I guess, because my BBox is not moving, and I guess
you're doing moving-BBox tests like Quake.

At 07:15 PM 8/4/2000 +0200, you wrote:
>
>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).
>
>
>_______________________________________________
>GDAlgorithms-list mailing list
>GDA...@li...
>http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>
>
--------------------------------------
Charles Bloom           www.cbloom.com