Associated Topics || Dr. Math Home || Search Dr. Math

### 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

- 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.
```
Associated Topics:
College Higher-Dimensional Geometry

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search