Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
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 
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.
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

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/