Intersection of Line and Triangle in 3-D Space

Date: 11/30/2003 at 02:37:35
From: Spiro
Subject: Line through a polygon (3-D)

For a 3-D game, I am writing my own line-of-sight function which will 
take a 3-D ray (X, Y, Z, Xd, Yd, Zd) and a polygon (Px1, Py1, Pz1, 
Px2, Py2, Pz2, Px3, Py3, Pz3) and return true or false, determining 
whether the ray passes through the polygon.

So, with the starting position and the direction of the ray, and three
(X,Y,Z) coordinates defining the polygon, how can I determine if the 
ray passes through the polygon?

The problem is straightforward but I have no idea how to even start on 
it.  I hope there is some formula to plug in here which will be faster 
than translating the polygon a million times and drawing imaginary 
rays.

Date: 11/30/2003 at 09:37:05
From: Doctor Tom
Subject: Re: Line through a polygon (3-D)

Hi Spiro -

I'm assuming that the Xd, Yd, Zd are distances in those three 
directions from the starting point (X, Y, Z) and that you are 
interested in intersections anywhere along the ray starting at 
(X, Y, Z) and passing through the point at those distances from the
origin of the ray.  If so, it's not too bad.

Find the equation of the plane passing through the three points of the
triangle.  In other words, find A, B, C and D such that:

  A Px1 + B Py1 + C Pz1 = D
  A Px2 + B Py2 + C Pz2 = D
  A Px3 + B Py3 + C Pz3 = D

It looks at first like there are three equations and four unknowns,
but any multiples of A, B, C and D work, so first try to solve it with
D = 1.  If that fails, solve it with D = 0.  Now you have the equation
of the plane in 3-space.

To find the intersection of your ray with the plane, solve this 
(again, I assume (X, Y, Z) is the starting point and (Xd, Yd, Zd) is
the direction of the ray):

  A(X + a Xd) + B(Y + a Yd) + C(Z + a Zd) = D.

The point of intersection will be:

  (X + a Xd, Y + a Yd, Z + a Zd) = (Ix, Iy, Iz)

If a is negative, it's behind you; not on the ray.  If it's positive,
it's in front of you.  Ix is the intersection x-coordinate, et cetera.

Now you know the coordinates of the point of intersection in space of 
your ray and the plane, but you've got to see if that point is inside 
the triangle.  To do that, solve this system:

  Ix = f Px1 + g Px2 + h Px3
  Iy = f Py1 + g Py2 + h Py3
  Iz = f Pz1 + g Pz2 + h Pz3

If all three (Ix, Iy, Iz) are larger than or equal to zero, the point
is inside (or on the boundary of) the triangle.  If any is negative,
it's outside.

What you've done in this last system of linear equations is to
express the intersection point in barycentric coordinates relative
to the vertices of the triangle--it's some fraction (f) of (Px1, Py1, 
Pz1), and some fractions (g and h) of the other points.  If you're 
interested, look up "barycentric coordinates" for more information.

- Doctor Tom, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 11/30/2003 at 12:53:18
From: Spiro
Subject: Line through a polygon (3-D)

Thank you - that seems to help a lot.