applet-magic.com
Thayer Watkins
Silicon Valley
& Tornado Alley
USA

The Intersection of Triangles in 3D Space

In Computer Graphics one standard problem is hidden surface removal. To some extent the matter can be taken care of by ordering the polygonal objects from far to near the observation point. The farther points are covered as the nearer objects are painted on the screen. This is the so-called Painter's Algorithm. But some objects overlap and it is difficult to say which should be painted first. More importantly some of those object may intersect such that part of one object is in front of another object and part of it is behind. In this case painting all of one object before the other gives an erroneous picture.

This matter covers the matter of computing the intersection, if any, between two triangles in space so that they may be partitioned in parts that are unabiguously ordered for display on the computer screeen.

Let one triangle be defined in terms of a triplet of vectors, each representing a vertex of the triangle, (Q1,Q2,Q3). The vector normal (perpendicular) to the plane of the triangle is found as the vector cross product of vectors representing two sides; i.e.,


N1 = (Q2-Q1)×(Q3-Q1 ).
 

A point X, given as a vector, in the plane of the triangle is such that the vector between it any point in the plane, say Q1, is perpendicular to the normal vector for the plane; i.e.,


(X-Q1)·N1 = 0.
 

The Line Intersection of Two Planes

Two triangles will define two planes which will have a line of intersection. Suppose the two planes are given by:


(X-Q1)·N1 = 0
(X-R1)·N2 = 0
 

The two equations above precisely define the intersection line. The problem is to represent the intersection line in a more convenient form that gives the coordinates of the points on the line. That form is the parametric representation of a line:


X = P0 + tV
 

where P0 is any point on the line, V is a vector giving the direction of the line, and t is any real number. As t ranges from -∞ to +∞ the equation traces out all of the points on the line. So to specify the intersection line of two planes we must determine a V and P0. These are not uniquely determined. The direction vector V is easy to establish. V must be perpendicular to both N1 and N2, therefore V must be proportional N1×N2. It can be taken at equal to this cross product. Finding aP0 is not difficult; it is a matter of choosing among the myriad possibilities. Since P0 is in both planes:


N1·(P0-Q1) = 0
and
N2·(P0-R1) = 0
 

These equations reduce to


N1·P0 = N1·Q1
and
N2·P0 = N2·R1
 

One component of P0 can be chosen arbitrarily. Let us choose the third component to be zero; i.e., the pooint P0 is the intersection of the line with the xy-plane. Thus there are two unknowns to be determined by the two equations above.
 

The Intersection of the Line Through One Side of a Triangle

The line through the points Q1 and Q2 has the parametric form


X = Q1 + s(Q2 - Q1)
 

If the parameter s is limited to the range [0, 1] it maps out only the points actually on the side of the triangle.

The point of intersection X0 of the side of the triangle and the line of intersection of their planes satisfies the condition


X0 = Q1 + s(Q2 - Q1) = P0 + tV
which reduces to
(Q2-Q1)s -Vt = P0 Q1
 

This appears to be three equations in the two unknows s and t, but the three equations are not independent so the solution from the first two components of the vectors is suffient to determine values for t and s. The value of s is crucial. If s is in the range [0, 1] then there is an intersection with the triangle side. If s is outside of that range then the point of intersection is beyong the end points of the side. The magnitude of t for the point of intersection is not important.

The Line of Intersection of the Planes of Two Triangles.

The intersections of the line of intersection with the other two sides must be determined and the intersections for the other triangle must be additionally determined. The two triangles must each then be decomposed at their lines of intersection into polygons. These polygons must be checked against the other triangles for intersection.


HOME PAGE OF applet-magic
HOME PAGE OF Thayer Watkins