The field of solid modeling makes extensive use of a variety of geometric algorithms. When implemented on a computer, these algorithms often fail because the computer only provides floating point arithmetic, while the algorithms are expecting infinite precision arithmetic on real numbers. These algorithms are not robust.
This paper presents a formal theory of robustness. It is then argued that the elegant theoretical approach to robustness is not viable in practice: algorithms like those used in solid modeling are generally too complex for this approach. This paper presents a practical alternative to the formal theory of robustness; this alternative is called local robustness.
Local robustness is applied to the design of a polyhedral intersection algorithm, which is an important component in many solid modelers. The intersection algorithm has been implemented, and, in extensive tests, has never failed to produce a valid polyhedron of intersection. A concise characterization of the locally robust intersection algorithm is presented; this characterization can be used to develop variants of the intersection algorithm, and to develop robust versions of other solid modeling algorithms.
102 Kb compressed Postscript file
@article{Stewart-ijcga94,
author = "A. James Stewart",
title = "Local robustness and its application to polyhedral intersection",
journal = "International Journal of Computational Geometry and Applications",
year = "1994",
volume = "4",
number = "1",
pages = "87--118",
}