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.
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.