## Ray-Triangle Intersection

Member
Posts: 281
Joined: 2009.04
Post: #1
Hello everyone,

After five weeks of struggling I have decided to seek help with my Ray-Triangle Intersection function.

The basic steps are:

1. If the ray isn't intersecting with the triangle's plane, exit.
2. Determine the point of intersection between the ray and the triangle's plane.
3. Choose the largest component (x,y or z) of the triangle's normal, and exclude that component from the 2D projection of the triangle and intersection point (p02D,p12D,p22D,planeintersection2D)

4. Using this test, check if the intersection point is in the 2D triangle.

I'm pretty sure my vector functions are OK but I can't really see what the problem is.

It seems as if the problem is to do with the projections but I can't decipher any more.

Ray-Plane
Code:
```float rayPlane(vector3D planepoint, vector3D normal, vector3D origin, vector3D direction) {      //    normal.normalise();                    float D = (planepoint).dot(normal);                         float t = - (normal.x*origin.x + normal.y*origin.y + normal.z*origin.z + D) / (normal.x*direction.x + normal.y*direction.y + normal.z*direction.z );                  cout << "t = " << t << endl;                    return t;      }```
Ray-Triangle:
Code:
```float rayTriangle(vector3D p0 ,vector3D p1,vector3D p2,vector3D origin    ,vector3D direction ) {          // work out planepoint = a point on the plane = a vertex; //    direction.normalise();     vector3D surfacenormal = calcnormal(p0,p1,p2); // work out the triangle's surface normal                   float t = rayPlane(p0,surfacenormal,origin,direction); // is the ray intersecting with the triangle's plane?               if (t < 0)// if the ray is isn't pointing towards the triangle's plane     {         cout << "wrong direction" << endl;         return -1; // exit }                         // the ray is pointing towards the triangle's plane               // work out the absolute position of the ray-triangle intersection               vector3D planeintersection(0,0,0);                    planeintersection.x = (direction.x  * t) ;     planeintersection.y = (direction.y  * t) ;     planeintersection.z = (direction.z  * t) ;                                   planeintersection = planeintersection + origin; // adds the origin               // find the appropriate plane (X, Y or Z)          vector3D planeint2D;          vector3D p02D;     vector3D p12D;     vector3D p22D;                                                  // find the range of the x0,x1,x2          vector3D absnormal(fabs(surfacenormal.x),fabs(surfacenormal.y),fabs(surfacenormal.z));          cout << "absnormal = " << absnormal.x << "," << absnormal.y << "," << absnormal.z << "." << endl;               if (absnormal.x > absnormal.y && (absnormal.x > absnormal.z || absnormal.y == absnormal.z) /* or zrange */) // xrange is the smallest OR the y and z are the same and x is less     {         planeint2D.x = planeintersection.z;         planeint2D.y = planeintersection.y;                  p02D.x = p0.z;         p02D.y = p0.y;                  p12D.x = p1.z;         p12D.y = p1.y;                  p22D.x = p2.z;         p22D.y = p2.y;                  cout << "excluding x\n";              }     if (absnormal.y > absnormal.x && (absnormal.y > absnormal.z || absnormal.x == absnormal.z) /* or zrange */) // yrange is the smallest     {         planeint2D.x = planeintersection.x;         planeint2D.y = planeintersection.z;                  p02D.x = p0.x;         p02D.y = p0.z;                  p12D.x = p1.x;         p12D.y = p1.z;                  p22D.x = p2.x;         p22D.y = p2.z;         cout << "excluding y\n";     }     if ((absnormal.z > absnormal.y && (absnormal.z > absnormal.x || absnormal.y == absnormal.x) /* or zrange */)) // zrange is the smallest     {         planeint2D.x = planeintersection.x;         planeint2D.y = planeintersection.y;                  p02D.x = p0.x;         p02D.y = p0.y;                  p12D.x = p1.x;         p12D.y = p1.y;                  p22D.x = p2.x;         p22D.y = p2.y;         cout << "excluding z\n";     }                    //cout << "surfacenormal: " << absnormal.x << "," << absnormal.y << "," << absnormal.z << "\n";           glPushMatrix();                     glLoadIdentity();      glColor4f(0.0f,0.0f,1.0f,1.0f);           glLineWidth(1.0f);      glBegin(GL_LINE_LOOP);      glVertex3f(p02D.x,p02D.y ,-20.0f);      glVertex3f(p12D.x,p12D.y,-20.0f);      glVertex3f(p22D.x,p22D.y,-20.0f);      glEnd();           glPointSize(5.0f);      glColor3f(1.0f,1.0f,0.0f);      glBegin(GL_POINTS);      glVertex3f(planeint2D.x,planeint2D.y,-20.0f);      glEnd();      glPopMatrix();                                             if (sameside(planeint2D,p02D,p12D,p22D) == 1 && sameside(planeint2D,p12D,p02D,p22D) == 1 && sameside(planeint2D,p22D,p02D,p12D) == 1)         return t;     else         return -1;                     }```

sameside:
Code:
```int sameside(vector3D p1, vector3D p2,vector3D l1,vector3D l2) {     vector3D cp1 =  ((l1 - l2 ) * (p1 - l2));     vector3D cp2 =  ((l1 - l2 ) * (p2 - l2));          if (cp2.dot(cp1) >= 0)         return 1;          return 0;      }```

(whew)

Thanks

mikey

~ Bring a Pen ~
Sage
Posts: 1,482
Joined: 2002.09
Post: #2
Barycentric coordinates are what you are looking for: http://en.wikipedia.org/wiki/Barycentric...a_triangle

Google can probably find a better tutorial.

Scott Lembcke - Howling Moon Software
Author of Chipmunk Physics - A fast and simple rigid body physics library in C.
Member
Posts: 281
Joined: 2009.04
Post: #3
Thanks, but even when I add this:

Code:
```              float u,v; // barycentric (?) coordinates     // Compute vectors             vector3D v0 = p22D - p02D;     vector3D v1 = p12D - p02D;     vector3D v2 = planeint2D - p02D;          // Compute dot products     float dot00 = v0.dot(v0);     float dot01 = v0.dot(v1);     float dot02 = v0.dot(v2);     float dot11 = v1.dot(v1);     float dot12 = v1.dot(v2);          // Compute barycentric coordinates     float invDenom = 1 / (dot00 * dot11 - dot01 * dot01);     u = (dot11 * dot02 - dot01 * dot12) * invDenom;     v = (dot00 * dot12 - dot01 * dot02) * invDenom;          // Check if point is in triangle     if ( (u > 0) && (v > 0) && (u + v < 1)    == 0)         return -1;```

to the end, my results are as unpredictable as ever.

~ Bring a Pen ~

Possibly Related Threads...
 Thread: Author Replies: Views: Last Post Triangle Intersection Tests merrill541 1 2,744 Feb 6, 2009 12:13 PM Last Post: scgames Triangle Normal Calculations merrill541 2 3,043 Feb 1, 2009 07:06 PM Last Post: merrill541 Get super triangle/bounding triangle of points Danny77uk 12 7,260 Mar 15, 2008 12:30 PM Last Post: Danny77uk 2D Polygon intersection testing unknown 6 7,026 Aug 15, 2006 04:17 PM Last Post: unknown Box to Plane Intersection With Quaternions KiroNeem 6 4,577 Jun 25, 2006 05:44 PM Last Post: KiroNeem