Ray-Triangle Intersection

Member

Posts: 281
Joined: 2009.04

Post: #1

Aug 14, 2010 — 08:48 AM

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 ~

Skorche

Sage

Posts: 1,478
Joined: 2002.09

Post: #2

Aug 14, 2010 — 10:27 AM

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.

mikey

Member

Posts: 281
Joined: 2009.04

Post: #3

Aug 15, 2010 — 05:11 AM

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,521	Feb 6, 2009 12:13 PM Last Post: scgames
	Triangle Normal Calculations	merrill541	2	2,888	Feb 1, 2009 07:06 PM Last Post: merrill541
	Get super triangle/bounding triangle of points	Danny77uk	12	6,700	Mar 15, 2008 12:30 PM Last Post: Danny77uk
	2D Polygon intersection testing	unknown	6	6,589	Aug 15, 2006 04:17 PM Last Post: unknown
	Box to Plane Intersection With Quaternions	KiroNeem	6	4,124	Jun 25, 2006 05:44 PM Last Post: KiroNeem