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 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.
322 Kb compressed Postscript file
@phdthesis{Stewart-thesis91,
author = "A. James Stewart",
title = "The theory and practice of robust geometric computation,
or, How to build robust solid modelers",
school = "Cornell University",
year = "1991",
}