Triangle Ray Intersection Algorithm [works perfectly]

Hi,

Edit: This actually works just fine. Rays don't end at their magnitude, so of course this would return true.

---------------------------------

Enclosed is a photo of a ray and a triangle. The ray does not visibly intersect the triangle. But according to every triangle intersection algorithm I can find, it does.

This one's stumped me for an entire weekend and now I'm pissed. Normally when someone gets an algorithm that won't work right, simply changing the algorithm or copying and pasting in some else's algorithm is all you have to do. Then, look for differences, and figure out where yours went wrong.

Not this time.

This is a simple triangle intersection algorithm I've changed over and over. I've googled the hell out of this, and modified several others' algorithms (see below) with my data. I have looked over other forum threads, and others' source code, which is where I got the original versions of some of this code.

Basically, they all seems to work right for many triangles and rays, but occasionally they all get stumped on one. This particular one (and some variations on it) are always "wrong", and it's driving me nuts. I put wrong in quotes because clearly it's doing what I'm telling it to do, it's just that the results aren't what I want.

For the sake of convenience, I have added all necessary code here so you can copy and paste it into a project and see it fail for yourself. In every case below, it's checking to see if the ray intersects the triangle, and in every case, it returns 'true'. It should be false.

Please help, I'm at the end of my rope, and I'm pretty sure this rope doesn't intersect a triangle either.

-Chilton

--------------

Code (CSharp):

1.     bool BetweenTriangleAndRay()
2.     {
3.  
4.         //ref Vector3 p1, ref Vector3 p2, ref Vector3 p3, ref Vector3 rayForward, ref Vector3 rayOrigin
5.     Vector3 rayOrigin = new Vector3(1,0,0);
6.     Vector3 rayForward = new Vector3(0,2,0);
7.     //Ray ray = new Ray(P0,P1);
8.     Vector3 p1 = new Vector3(3,     2.3f,     -4);
9.     Vector3 p2 = new Vector3(-7,     2.3f,     2);
10.     Vector3 p3 = new Vector3(3,     2.3f,      2);
11.  
12.     Debug.DrawLine(rayOrigin,rayForward, Color.red, 10);
13.  
14.     Debug.DrawLine(p1, p2, Color.blue, 10);
15.     Debug.DrawLine(p2, p3, Color.blue, 10);
16.     Debug.DrawLine(p3, p1, Color.blue, 10);
17.  
18.  
19.         //Find vectors for two edges sharing vertex/point p1
20.         var e1 = p2 - p1;
21.         var e2 = p3 - p1;
22.  
23.         // calculating determinant
24.         var p = Vector3.Cross( rayForward,  e2);
25.  
26.         //Calculate determinat
27.         var det = Vector3.Dot( e1,  p);
28.  
29.         //if determinant is near zero, ray lies in plane of triangle otherwise not
30.         if (det > -0.000001f && det < 0.000001f) { return false; }
31.         var invDet = 1.0f / det;
32.  
33.         //calculate distance from p1 to ray origin
34.         var t = rayOrigin - p1;
35.  
36.         //Calculate u parameter
37.         var u = Vector3.Dot( t,  p) * invDet;
38.  
39.         //Check for ray hit
40.         if (u < 0 || u > 1) { return false; }
41.  
42.         //Prepare to test v parameter
43.         var q = Vector3.Cross( t,  e1);
44.  
45.         //Calculate v parameter
46.         var v = Vector3.Dot( rayForward,  q) * invDet;
47.  
48.         //Check for ray hit
49.         if (v < 0 || u + v > 1) return false;
50.  
51.         if ((Vector3.Dot(e2, q) * invDet) > 0.000001)
52.         {
53.             //ray does intersect
54.             return true;
55.         }
56.  
57.         // No hit at all
58.         return false;
59.     }

Another attempt, found this algorithm in another place, adapted it for the same test...

Code (CSharp):

1.      public static bool Intersect()
2.      {
3.  
4.     Vector3 P0 = new Vector3(1,0,0);
5.     Vector3 P1 = new Vector3(0,2,0);
6.     Ray ray = new Ray(P0,P1);
7.     Vector3 p1 = new Vector3(3,     2.3f,     -4);
8.     Vector3 p2 = new Vector3(-7,     2.3f,     2);
9.     Vector3 p3 = new Vector3(3,     2.3f,      2);
10.  
11.  
12.          // Vectors from p1 to p2/p3 (edges)
13.          Vector3 e1, e2;
14.          Vector3 p, q, t;
15.          float det, invDet, u, v;
16.          //Find vectors for two edges sharing vertex/point p1
17.          e1 = p2 - p1;
18.          e2 = p3 - p1;
19.          // calculating determinant
20.          p = Vector3.Cross(ray.direction, e2);
21.          //Calculate determinat
22.          det = Vector3.Dot(e1, p);
23.          //if determinant is near zero, ray lies in plane of triangle otherwise not
24.          if (det > -Mathf.Epsilon && det < Mathf.Epsilon) { return false; }
25.          invDet = 1.0f / det;
26.          //calculate distance from p1 to ray origin
27.          t = ray.origin - p1;
28.          //Calculate u parameter
29.          u = Vector3.Dot(t, p) * invDet;
30.          //Check for ray hit
31.          if (u < 0 || u > 1) { return false; }
32.          //Prepare to test v parameter
33.          q = Vector3.Cross(t, e1);
34.          //Calculate v parameter
35.          v = Vector3.Dot(ray.direction, q) * invDet;
36.          //Check for ray hit
37.          if (v < 0 || u + v > 1) { return false; }
38.          if ((Vector3.Dot(e2, q) * invDet) > Mathf.Epsilon)
39.          {
40.              //ray does intersect
41.              return true;
42.          }
43.          // No hit at all
44.          return false;
45.      }

... and one more attempt, another algorithm adapted, slightly different input, same result...

Code (CSharp):

1. int intersect3D_RayTriangle()
2. {
3.  
4.     Vector3 P0 = new Vector3(0,0,0);
5.     Vector3 P1 = new Vector3(0,1,0);
6.     Vector3 V0 = new Vector3(3,     2.3f,     -4);
7.     Vector3 V1 = new Vector3(-7,     2.3f,     2);
8.     Vector3 V2 = new Vector3(3,     2.3f,      2);
9.  
10.     Debug.DrawLine(P0,P1, Color.red, 10);
11.  
12.     Debug.DrawLine(V0, V1, Color.blue, 10);
13.     Debug.DrawLine(V1, V2, Color.blue, 10);
14.     Debug.DrawLine(V2, V0, Color.blue, 10);
15.  
16.  
17.     Vector3 I;
18.     Vector3 u, v, n;              // triangle vectors
19.     Vector3 dir, w0, w;           // ray vectors
20.     float     r, a, b;              // params to calc ray-plane intersect
21.  
22.     // get triangle edge vectors and plane normal
23.     u = V1 - V0;
24.     v = V2 - V0;
25.     n = Vector3.Cross(u, v);              // cross product
26.     if (n == Vector3.zero)             // triangle is degenerate
27.         return -1;                  // do not deal with this case
28.  
29.     dir = P1 - P0;              // ray direction vector
30.     w0 = P0 - V0;
31.     a = -Vector3.Dot(n,w0);
32.     b = Vector3.Dot(n,dir);
33.     if (Mathf.Abs(b) < .00001f) {     // ray is  parallel to triangle plane
34.         if (a == 0)                 // ray lies in triangle plane
35.             return 2;
36.         else return 0;              // ray disjoint from plane
37.     }
38.  
39.     // get intersect point of ray with triangle plane
40.     r = a / b;
41.     if (r < 0.0)                    // ray goes away from triangle
42.         return 0;                   // => no intersect
43.     // for a segment, also test if (r > 1.0) => no intersect
44.  
45.     I = P0 + r * dir;            // intersect point of ray and plane
46.  
47.     // is I inside T?
48.     float    uu, uv, vv, wu, wv, D;
49.     uu = Vector3.Dot(u,u);
50.     uv = Vector3.Dot(u,v);
51.     vv = Vector3.Dot(v,v);
52.     w = I - V0;
53.     wu = Vector3.Dot(w,u);
54.     wv = Vector3.Dot(w,v);
55.     D = uv * uv - uu * vv;
56.  
57.     // get and test parametric coords
58.     float s, t;
59.     s = (uv * wv - vv * wu) / D;
60.     if (s < 0.0 || s > 1.0)         // I is outside T
61.         return 0;
62.     t = (uv * wu - uu * wv) / D;
63.     if (t < 0.0 || (s + t) > 1.0)  // I is outside T
64.         return 0;
65.  
66.     return 1;                       // I is in T
67. }

 

Okay, I started off looking for a line segment and somehow ended with a ray cast. I see now that this would of course always work, as a ray doesn't end at the magnitude of the ray.

So, this works just fine. The problem was it wasn't the right tool for the job.

 

nice, thanks for collecting those , here are a few methods to get the vector / point given the triangle normals / points and the barycentric coordinates ( `u` and `v` values ) :

Code (CSharp):

1. public static Vector3 BarycentricPoint(Vector3 p1, Vector3 p2, Vector3 p3, Vector2 uv)
2. {
3.     // https://www.scratchapixel.com/lessons/3d-basic-rendering/ray-tracing-rendering-a-triangle/barycentric-coordinates
4.  
5.     return p2 * uv.x + p3 * uv.y + p1 * (1 - uv.x - uv.y);
6. }
7. public static Vector3 BarycentricLerp( Vector3 a, Vector3 b, Vector3 c, Vector2 uv )
8. {
9.     var l1 = Vector3.Lerp(a, b, uv.x);
10.     var l2 = Vector3.Lerp(a, c, uv.y);
11.     var v = ( l1 + l2 ) / 2f;
12.     return ( v - a ) * 2f + a;
13. }
14. public static Vector3 BarycentricSlerp( Vector3 a, Vector3 b, Vector3 c , Vector2 uv )
15. {
16.     var l1 = Vector3.Slerp( a, b, uv.x );
17.     var l2 = Vector3.Slerp( a, c, uv.y );
18.     return Vector3.Slerp( l1, l2, uv.y / (uv.x + uv.y) );
19. }