One approach to understanding the utility of boolean intersection predicates is by considering the specific example of a tri-tri intersection in 3 space. Figure 1 shows a view of two intersecting triangles as a model for discussion. Each intersecting tri-tri pair will contribute one segment to the final polyhedra which comprise the wetted surface of the configuration. The assumption of general as opposed to arbitrary positioned data indicates that the intersection is always non-degenerate. Triangles don't share vertices and edges of tri-tri pairs do not intersect exactly. Thus, all intersections will be proper (as opposed to improper or "degenerate"). This restriction will be lifted in the section on tie-breaking algorithms.
Figure 1: An intersecting pair of generally positioned triangles in three dimensions.
Several approaches exist to compute such intersections but a particularly attractive technique offers itself as a Boolean test. This predicate has the advantage that it can be performed robustly and quickly using only multiplication and addition, thus avoiding the inaccuracy and robustness pitfalls associated with division using fixed width representations of floating point numbers. It is useful to present a rather comprehensive treatment of this intersection primative not only for illustrating the development of the basic geometric computations, but also because the important topics of robustness, floating-point round-off-error and tie-breaking will return to the expressions and assumptions exposed.
For two triangles to properly intersect in three dimensional space, the following conditions must exist:
1. Two edges of one triangle must span the plane of the other.
2. If condition (1) exists, there must be a total of two edges (of the six available) which pierce within the boundaries of the triangles (e.g. edge ab pierces (0,1,2) and edge 02 pierces (a,b,c) ).
An alternative to this slope-pierce test is to consider a Boolean check based on computation of a triple product without division. A series of such logical checks have the attractive property that they permit one to establish the existence and connectivity of the segments without relying on the problematic computation of the actual pierce point locations. The final step of computing the locations of these points may then be relegated to post-processing where they may be grouped together and, since the connectivity is already established, floating point errors will not have fatal consequences.
The Boolean primitive for the 3D intersection
of an edge and a triangle is based on the concept of the signed volume
of a tetrahedra. This signed volume is based on the well established relationship
for the computation of the volume of a simplex, T, in n dimensions
in determinate form (see for example the excellent discussion in Ref.[1]).
The signed volume Vol(T) of the simplex T with vertices
{v0,v1,v2,...,vn) in n dimensions is:
{1}
and
In 3 dimensions,
eq. {1} gives six times the signed volume of the tetrahedron
Tabcd.
{2}
This volume serves as the fundamental building
block of the geometry engine used in intersect and cubes.
It is positive when (a,b,c) forms a counterclockwise loop when viewed
from an observation point on the side of the plane defined by (a,b,c)
which is opposite from point d. Positive and negative volumes define
the two states of a Boolean test, while zero indicates that the four vertices
are exactly coplanar. If the vertices are indeed coplanar, then the situation
constitutes a "tie" which will be resolved with a general tie-breaking
algorithm. In applying this logical test to edge
ab and triangle
(0,1,2) in fig. 1, ab spans the plane if and only if (iff)
the signed volumes
T012a and T012b
have opposite signs. Figure 2 presents a graphical look at the application
of this test.
With a and b established
as spanning the plane (0,1,2) all that remains is to determine if
ab
pierces within the boundary of the triangle (0,1,2). This will be
the case iff the three tetrahedra formed by connecting the endpoints of
ab with the three vertices of the triangle (0,1,2) (taken
two at a time) all have the same sign, that is:
{3}
After determining the existence of all the segments which result from intersections between tri-tri pairs and connecting a linked list of all such segments to the triangles that intersect to produce them, all that remains is to actually compute the locations of the pierce points. This is accomplished by using a parametric representation of each intersected triangle and the edge which pierces it. The technique is a straightforward three dimensional generalization of the 2D method presented in [1].
The signed volume computation of eq.{2} is also used for performing inCircle/inSphere tests, for in/out determination in ray-casting algorithms and for a variety of other topological predicates. Due to its obvious importance, a great deal of research has gone into developing rapid and robust evaluations of this determinant. References [2] and [3] treat this topic in detail.
[2] Shewchuk, J.R., Robust Adaptive Floating-Point Geometric Predicates, Proceedings of the Twelfth Annual Symposium on Computational Geometry, pages 141-150, ACM, May 1996. Abstract
[3] Edelsbrunner, H., and Mücke, E.P., "Simulation of Simplicity: A Technique to Cope with Degenerate Cases in Geometric Algorithms." ACM Transactions of Graphics, 9(1):66-104,1990.
| For more information mail to: aftosmis@nas.nasa.gov |
| Return to Cart3d or Michael Aftosmis's homepage |