ray-triangle intersections

Hi BlueGrass,

I''ve just redesigned my site Maybe Plane - Ray Collision is what you''re looking for...?

After you got the colision on the plane, make 2d-planes of the triangle sides, if the point lies on the inside of the 3 planes it´s inside the triangle

Here is the pseudocode that they give in the book Real-Time Rendering:

RayTriIntersect( O, D, V0, V1, V2 ) returns ({REJECT,INTERSECT}, u, v, t); 1: E1 = V1 - V0; 2: E2 = V2 - V0; 3: P = D X E2; 4: a = E1 . P; 5: if( a > -epsilon and a < epsilon ) return (REJECT,0,0,0); 6: f = 1 / a; 7: S = O - V0; 8: u = f( S . P ); 9: if( u < 0.0 or u > 1.0 ) return (REJECT,0,0,0); 10: Q = S X E1; 11: v = f( D . Q ); 12: if( v < 0.0 or u + v > 1.0 ) return (REJECT,0,0,0); 13: t = f( E2 . Q ); 14: return (INTERSECT, u, v, t );

Now, let me explain this just a bit. First off in the above code all vectors are represented with capital letters and all floating point values are in lowercase letters.

The parameters O and D are used to contruct the ray that you are testing the intersection for in the following fashion: r(t) = O + tD. Where O is the origin of the ray and D (which is usually normalized) is the direction of the ray. The parameters V0, V1, and V2 are the three vertices of the triangle.

The pseudofunction returns if the ray actually did intersect the triangle and if it did it also returns the barycentric coordinates (the uv pair) and the distance along the ray that the collision took place (the t variable).

Now for a line by line explaination:
1: This computes the vector for the second point on the triangle to the first point on the triangle.
2: The same as step 1 but from the third point to the first.
3: This is the cross product of the direction and the vector computed in step 2.
4: This computes the determinate of the matrix M which is not shown.
5: This checks if the intersection actually occurs. Note that epsilon is just a small value for which 1.0e-5 works fine.
6: Computes the inverse of step 4.
7: Computes the vector from the origin of the ray to the first point in the triangle.
8: Computes the u-barycentric coordinate.
9: Rejects the intersection if the u coordinate is out of range.
10: Computes the cross product of the vectors found in steps 1 and 7.
11: Computes the v-barycentric coordinate.
12: Rejects the intersection if the v coordinate is out of range.
13: Computes the distance along the ray that the intersection took place.
14: The intersection is returned.

To find the actual point of intersection you just need to put the t variable that is returned back into the ray equation r(t) = O + tD.

Also, this method does not backface cull your triangle. However, I believe that C-code for a function that does backface cull the triangle as well as the C-code for this function can be found on the Real-Time Rendering Website.

Edited by - Ranok on September 26, 2000 2:38:13 PM