Path: utzoo!mnetor!uunet!lll-winken!lll-tis!ames!mailrus!rutgers!iuvax!pur-ee!uiucdcs!uiucdcsm!shirley
From: shirley@uiucdcsm.cs.uiuc.edu
Newsgroups: comp.graphics
Subject: Re: ray to triangle
Message-ID: <4400019@uiucdcsm>
Date: 17 Apr 88 12:53:00 GMT
References: <15@<Apr>
Lines: 34
Nf-ID: #R:<Apr:15:uiucdcsm:4400019:000:1040
Nf-From: uiucdcsm.cs.uiuc.edu!shirley    Apr 17 06:53:00 1988




The fastest way I know of to do this is to first find the point p
where the ray hits the plane.  Then write down the following equation:

           p = v1 + u * (v2 - v1) + v * (v3 - v1)

where v1, v2, v3 are the vertices of the triangle, and u,v are
parametric cooordinates on the plane containing the triangle.
The meaning of this equation is apparent in a diagram.  Now rewrite
this equation to get three linear equations (from x/y/z coordinates)
with two unknowns (u/v).  Use two equations and cramer's rule to
solve for u and v.  Be sure to use the best two equations-- if the
triangle lies in the xy plane discard the z equation, etc.

Now that you have u and v,  the point p is in the triangle iff

             1.  u > 0
             2.  v > 0
             3.  u+v < 1

Again, draw a diagram to see why this is true.

You can use the same equations for intersection with parallelogram,
except that condition three is replaced by

            3.  u < 1
            4.  v < 1


Hope this helps!

Peter Shirley
U of Illinois at UC