Tie-Breaking, Degeneracies, and Floating Point Arithmetic

go back to Cart3d, goto The Cartesian Origin mail to: aftosmis@nas.nasa.gov

The discussion on Boolean predicates argues that polygon intersection, re-triangulation and ray-casting algorithms in Rn may all be cast in a unified framework which requires only the evaluation of the determinant:

{1}
where vk j denotes the jth coordinate of the kth vertex with and In 3 dimensions, this equation yields six times the signed volume of the tetrahedron Tabcd.
 

{2}

As a result, the robustness of the overall procedure equates to a robust implementation of this signed volume calculation. Fortunately, accurate and rapid evaluation of this determinant has long been the subject of study in computational geometry and computer science.

 Computing the sign of eq.{2} constitutes a topological primitive, which is an operation that tests an input and always yields one of a prespecified number of results. Of course, such primitives can only classify, and new objects - like the the actual locations of intersection points (see fig.1 boolean intersections) - cannot be determined without further work. Such topological primitives do, however, provide the intersections implicitly and this information is all that is really needed to establish the connectivity of the segment list describing the intersection.

Exact Arithmetic

The signed volume computation for arbitrarily positioned geometry can return a result which is positive (return +1), negative (return -1) or zero (return 0), where +/-1 are non-degenerate cases and zero represents some geometric degeneracy. Distinguishing between these cases on finite precision hardware, however, is not necessarily a trivial task. Two approaches are common, the first may be thought of as an integer inflation strategy (cf. [1]). In this approach all vertex locations are preprocessed so that the data is inflated and adjusted to span the maximum allowable integer space which is representable by the hardware (±(231 - 1) with 32 bits or ±(263 - 1) with 64 bits). New data is then constrained to its nearest allowable integer location. The second approach is to use exact (arbitrary precision) arithmetic. Unfortunately, while much hardware development has gone into rapid (round-off prone) floating point computation, few hardware architectures are optimized for either the arbitrary precision or integer math alternatives .

In an effort to perform as much of the computation as possible on the floating-point hardware, the Cart3d codes first compute eq.{2} in floating point, and then make an a-posteriori estimate of the round-off error (cf. [2],[3]) If the round-off error is of the same order as the signed volume, then the case is considered indeterminate and we look to exact arithmetic and introduce the tie-breaking algorithm for truly degenerate cases. This approach may be characterized as a floating point filter, since only cases that are "dangerous" are selected for further processing. A brief discussion of these topics is available on the web at the Robust Predicates Page along with substantial downloadable documentation. Since only a very small fraction of the computations fall through the filter, the speed penalty for using exact arithmetic on virtually all realistic examples is essentially negligible. To further speed things up, the routines presented in [2] have been optimized for float and double data types on IEEE compliant hardware. 

"Simulating" Simplicity and Tie-Breaking

The tie-breaking algorithm stems from work done by Edelsbrunner and Mücke[4] and is known as Simulation of Simplicity (appropriately abbreviated as "SoS"). The technique resolves geometric degeneracies by assuming a consistent set of virtual perturbations sufficient to insure that geometry is always in general position - in accordance with the assumptions outlined in the discussion on boolean intersections). The attraction of this approach is that the topological primitives never return a zero (degenerate) result, thus alleviating the need to consider specialized treatments for degenerate geometry. Moreover, since the perturbations are "virtual" and "consistent", data is never altered and ties are always resolved with the same result. Symbolic perturbation schemes like SoS are attractive for many reasons. Prinmarilly, however, whats important is that they represent an algorithmic approach to tie-breaking. They do not depend on the experience of the programmer to foresee all possible diabolical cases, and virtually eliminate the need for special-case coding to trap out degeneracies arising from objects or data in special position.

 -- more details coming soon --

References

[1] Knuth, D.E., The Art of Computer Programming: Semi-numerical Algorithms Addison Wesley, 1973.

[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] Priest, D.M., "Algorithms for Arbitrary Precision Floating Point Arithmetic", Tenth Symposium on Computer Arithmetic, pp. 132-143, IEEE Comp. Soc. Press, 1991.

 [4] 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 
last update 3 Sep 96