Ray-triangle intersetion

Question

Hello! How can I test intersesion ray and triangle, and if it exist how to get distance from ray origin to intersection point?? What optimization I can use, if in my program I've got to check 1 ray to ~10000 triangles ??

Answer 1

A single polygon-ray intersection test is trivial and just involves making sure that the ray crosses at least one side of it (check them individually) or across the plane defined by the triangle between the sides of it. The optimization comes into not checking against polygons that the ray has no chance at all of crossing. Depending on how high of a dimension you're working in, how big the area is, and how many polygons you're dealing with the most typical optimizations are quadtrees, octrees, and kd-trees. This is also approximately the order of difficulty of implementation (although quad and octtrees are very similar).

Answer 2

Probably the first time I needed to implement it I looked at these slides, which I find very useful.

http://www.cs.princeton.edu/courses/archive/fall00/cs426/lectures/raycast/sld016.htm

First make sure you understand how it works then you can do a lot of different optimizations. For example:

if (dot(V, N) >= 0)     // no intersection - ray points away from the triangle face
if (dot(P0, N) + d < 0) // no intersection - ray origin is behind the triangle face

Another think I used to do is once I find the intersection point of the ray and the face. I used to do the check for point inside triangle in 2D while I was zeroing the axis with maximum absolute value of the normal... if abs(N.x) > abs(N.y) > abs(N.z) I'll do the check in YZ plane.

I can suggest another simple to implement optimization find the center and radius of the circumscribed circle (well depends if you need to do it often you can choose a easer center like center of mass). Now this point and radius define a bounding sphere around your triangle. Now you can do much faster ray sphere culling.

http://www.cs.princeton.edu/courses/archive/fall00/cs426/lectures/raycast/sld012.htm

Don't solve the whole polynomial you don't need the intersection point of ray/sphere just check for existing roots.

There are many other optimizations you can do for example: If your vertices and normals can be arranged in more SSE friendly structure you can do 4 checks at a time. Which roughly can go to around 2.5 times faster.