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 ~
Quote this message in a reply
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.
Quote this message in a reply
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 ~
Quote this message in a reply
Post Reply 

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