Ray-Triangle Intersection

Prev: Ray-Sphere Intersection

Next: Catmull-Rom Spline

 

Given a ray, i.e. a parametric line equation, and a triangle, do they intersect? and if so what is the intersection point?

The solution presented in here is the one from Moller and Trumbore. A point in a triangle can be defined as:

    	point(u,v) = (1-u-v)*p0 + u*p1 + v*p2

	where

	p0,p1,p2 are the vertices of the triangle 

	u >= 0
	v >= 0
	u + v <= 1.0

We also know that the parametric equation of the line is:

    	point(t) = p + t * d

	where 

	p is a point in the line
        d is a vector that provides the line's direction

So if there is a point that belongs both to the line and the triangle we get:

	p + t * d = (1-u-v) * p0 + u * p1 + v * p2

 

Therefore the intersection problem can be redefined as: is there a triplet (t,u,v) that satisfies the equation above, and complies with the restrictions for u and v? If the answer is yes, then the ray intersects the triangle, otherwise it doesn’t. For the maths details of solving this problem see either the reference above or check out the book “Real Time Rendering”. The following C code can be used to test the intersection:

 

/* a = b - c */
#define vector(a,b,c) \
	(a)[0] = (b)[0] - (c)[0];	\
	(a)[1] = (b)[1] - (c)[1];	\
	(a)[2] = (b)[2] - (c)[2];

int rayIntersectsTriangle(float *p, float *d,
			float *v0, float *v1, float *v2) {

	float e1[3],e2[3],h[3],s[3],q[3];
	float a,f,u,v;
	vector(e1,v1,v0);
	vector(e2,v2,v0);

	crossProduct(h,d,e2);
	a = innerProduct(e1,h);

	if (a > -0.00001 && a < 0.00001)
		return(false);

	f = 1/a;
	vector(s,p,v0);
	u = f * (innerProduct(s,h));

	if (u < 0.0 || u > 1.0)
		return(false);

	crossProduct(q,s,e1);
	v = f * innerProduct(d,q);

	if (v < 0.0 || u + v > 1.0)
		return(false);

	// at this stage we can compute t to find out where
	// the intersection point is on the line
	t = f * innerProduct(e2,q);

	if (t > 0.00001) // ray intersection
		return(true);

	else // this means that there is a line intersection
		 // but not a ray intersection
		 return (false);

}

---

 

Check out the cross product and the inner product definitions if you need help.

The code above only tells you if the ray intersects or not the triangle. If you want to know where then you can easily alter the code to return the triplet (t,u,v). Using the return value of t, or u and v, the intersection point, i.e. the values x,y,z where the ray intersects the triangle, can be found.

 

Prev: Ray-Sphere Intersection

Next: Catmull-Rom Spline