Thayer Watkins Silicon Valley & Tornado Alley USA 


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 socalled 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, (Q_{1},Q_{2},Q_{3}). The vector normal (perpendicular) to the plane of the triangle is found as the vector cross product of vectors representing two sides; i.e.,
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 Q_{1}, is perpendicular to the normal vector for the plane; i.e.,
Two triangles will define two planes which will have a line of intersection. Suppose the two planes are given by:
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:
where P_{0} 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 P_{0}. These are not uniquely determined. The direction vector V is easy to establish. V must be perpendicular to both N_{1} and N_{2}, therefore V must be proportional N_{1}×N_{2}. It can be taken at equal to this cross product. Finding aP_{0} is not difficult; it is a matter of choosing among the myriad possibilities. Since P_{0} is in both planes:
These equations reduce to
One component of P_{0} can be chosen arbitrarily. Let us
choose the third component to be zero; i.e., the pooint
P_{0} is the intersection of the line with the xyplane. Thus there
are two unknowns to be determined by the two equations above.
The line through the points Q_{1} and Q_{2} has the parametric form
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 X_{0} of the side of the triangle and the line of intersection of their planes satisfies the condition
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 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 Thayer Watkins 