Line triangle intersection - last bits

Question

I'm doing line-triangle intersection. I have found the intersection point (vector) on the plane. All I need to do now is work out whether the point is inside the triangle it collided with (not the plane the tri is on)

The line is represented by two 3D vectors, the triangle 3 points and the collision point another vector. If it's any help, I've been reading through this article. I've actually managed to do most of it. I'm just stuck on the last bit which is working out whether the point is inside the triangle.

I've read stuff about summing the angles of 3 internal triangles, but that's extraordinarily slow - can someone help me out?

Thanks,

James

Answer 1

You might be able to use this: P1, P2, P3 are points on the plane. R1 and R2 represent a near and far point on the ray. Vector3f is a fancy vector that I've got from vmml from equalizer. I use this when I use gluUnproject().

/*! @param PIP Point-in-Plane */
bool Channel::testRayThruTriangle( Vector3f P1, Vector3f P2, Vector3f P3, Vector3f R1, Vector3f R2, Vector3f& PIP)
{  
    Vector3f Normal, IntersectPos;

    // Find Triangle Normal
    Normal.cross( P2 - P1, P3 - P1 );
    Normal.normalize(); // not really needed?  Vector3f does this with cross.

    // Find distance from LP1 and LP2 to the plane defined by the triangle
    float Dist1 = (R1-P1).dot( Normal );
    float Dist2 = (R2-P1).dot( Normal );

    if ( (Dist1 * Dist2) >= 0.0f) { 
        //SFLog(@"no cross"); 
        return false; 
    } // line doesn't cross the triangle.

    if ( Dist1 == Dist2) { 
        //SFLog(@"parallel"); 
        return false; 
    } // line and plane are parallel

    // Find point on the line that intersects with the plane
    IntersectPos = R1 + (R2-R1) * ( -Dist1/(Dist2-Dist1) );

    // Find if the interesection point lies inside the triangle by testing it against all edges
    Vector3f vTest;

    vTest = Normal.cross( P2-P1 );
    if ( vTest.dot( IntersectPos-P1) < 0.0f ) { 
        //SFLog(@"no intersect P2-P1"); 
        return false; 
    }

    vTest = Normal.cross( P3-P2 );
    if ( vTest.dot( IntersectPos-P2) < 0.0f ) { 
        //SFLog(@"no intersect P3-P2"); 
        return false; 
    }

    vTest = Normal.cross( P1-P3 );
    if ( vTest.dot( IntersectPos-P1) < 0.0f ) { 
        //SFLog(@"no intersect P1-P3"); 
        return false; 
    }

    NSLog(@"Intersects at ( %f, %f )", IntersectPos.x(), IntersectPos.y());

    PIP = IntersectPos;

    return true;
}

Answer 2

http://www.graphics.cornell.edu/pubs/1997/MT97.pdf

This paper provides (apparently) the most computationally efficient means of calculating ray-triangle intersection. Not sure if it directly addresses the question but thought it may be useful here.

Old link to Webarchive: https://web.archive.org/web/20170517125238/http://www.cs.virginia.edu:80/~gfx/courses/2003/ImageSynthesis/papers/Acceleration/Fast%20MinimumStorage%20RayTriangle%20Intersection.pdf

Answer 3

You can probably use the same method as the generic point/shape interior algorithm I talk a little bit about here: In Cocos2D, how do I check for collisions against an arbitrary user-drawn shape?

Answer 4

3 triangle points: P1, P2, P3. 2 line points L1, L2.

The intersection points T. T lies on the line, so there's a real value c so that T = L1 + c * (L2 - L1)

Also, T lies on the plane, so there're 2 real values a and b so that

T = P1 + a * ( P2 - P1 ) + b * ( P3 - P2 )

Now you've got the system of 3 linear equations with 3 variables:

L1.x + c * (L2.x - L1.x) = P1.x + a * ( P2.x - P1.x ) + b * ( P3.x - P2.x )

L1.y + c * (L2.y - L1.y) = P1.y + a * ( P2.y - P1.y ) + b * ( P3.y - P2.y )

L1.z + c * (L2.z - L1.z) = P1.z + a * ( P2.z - P1.z ) + b * ( P3.z - P2.z )

You solve the system (e.g. read wikipedia for "Inversion of 3×3 matrices", if the matrix can't be inverted, the plane and line doesn't intersect, or the line belongs to the plane, or the triangle is 0-area, or L1=L2 ).

If it has the only solution, you find it, and here's your final check that point is inside the triangle: bool isInTriangle = a >= 0 && b >= 0 && (a+b)<=1;