Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

tcs

fast ray/triangle intersection test

This topic is 6767 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I want to have a fast ray/triangle intersection test alogrithm. I just have a ray start/end vertex and three triangle vertices and want to know if the ray intersects with the triangle, no uv coords needed. Speed is very important. Any ideas ??? Tim

Share this post


Link to post
Share on other sites
Advertisement
Hi there,

find the intersection point with the plane the triangle lies in. Then do a point in polygon test. That is the most used method.

For speeds sake precalculate the triangleplane. And if you wanna go really fast then precalculate the edge planes as well (planes that are perpendicular to the triangle going trough the edge, which are often used for point in poly tests).

Jaap Suter

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
just for reference - a ray does not have an end vertex.

-goltrpoat

Share this post


Link to post
Share on other sites
Yeah I know. But may (light) ray has, it ends on the wall ;-))))

Jaap Suter:

I know the tutorial on flipcode. But the stuff with the anti-planes doesn''t work if you use the alog for lightmap calculation. The start/end point of the light ray may be outside the collision box, but still cross the triangle. To make sure that this don''t happens, the anti-planes of the collsion box must be calculated trough adding the ray''s vector, rather than adding the plane normal. This is slow, you need 3 square roots for each intersection test since you have to recalculate your anti-plane normal....

any idea how to avoid this ????

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
two words - barycentric coordinates.

-goltrpoat

Share this post


Link to post
Share on other sites
http://www.acm.org/jgt/papers/MollerTrumbore97/

can''t get this working. The code seems to be somehow wrong !? Just look at the first macro, the author forgot a "\" this code can''t compile, I guess the writer of this document never compiled it !?

Share this post


Link to post
Share on other sites
Hi Tcs (and others).

The method I mentioned does work but you probably think I mention another method then I did (that must be the worst sentence I ever wrote in a foreign language).

What I always do is calculating the intersection of the ray and the plane (the plane of the polygon I mean). And then I do a point in polygon test. This point in polygontest is done using the edgeplanes (or antiplanes as you call them). This has always worked for me and I couldn''t see why this wouldn''t work.

or.. ?

Jaap

Share this post


Link to post
Share on other sites
I was under the impression that after finding the intersection point on the plane it''s faster to figure the angles between the vertices and the point, add em, and see if they add to 180 degrees or not. :?

Share this post


Link to post
Share on other sites
The problem is that calculating the angle takes a squareroot unless your vectors are normalized. And with the point in poly test with angles your vectors are never normalized. And these can''t be precalculated either (edge (or anti-) planes can).

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!