# Line triangle intersection - last bits

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

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;
}

• Thanks very much for this. I'd like to know; is it fast enough to use on relatively high poly models colliding with other objects of the same ilk? – Bojangles Nov 18 '10 at 11:10
• That Equaliser project looks incredible! I must try this some time! – Bojangles Nov 18 '10 at 11:13
• @JamWaffles, I don't know if it's high performance. I'm sure there's an OpenCL implementation that would be lightning fast, but that's beyond me. Equalizer is a great project. Distributed graphics is impressive when you see your scene rendering on a wall of 12 monitors. :D – Stephen Furlani Nov 18 '10 at 12:53

http://www.cs.virginia.edu/~gfx/Courses/2003/ImageSynthesis/papers/Acceleration/Fast%20MinimumStorage%20RayTriangle%20Intersection.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.

• I've used this extensively. It works, it's fast, it comes with the code, and the paper explains in great detail what the algorithm does. – Crowley9 Nov 16 '10 at 7:47

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?

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;