The Theory and Pratice of Robust Geometric Computation, or, How toBuild Robust Solid Modelers
Stewart, A. James
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 agorithms are expecting infinite precision arthmetic on real numbers. These algorithms are not robust. This dissertation presents a theory of robustness. With this theory, a robust point location algorithm is developed. This algorithm determines whether a point lies inside a polygon, where both the point and the polygon are represented approximately. 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 dissertation 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.
computer science; technical report
Previously Published As