A Paradigm for the Robust Design of Algorithms for Geometric Modeling

Abstract

Geometric modelers are becoming faster and more powerful, but they still suffer from reliability problems because of floating point errors. Previous work in the field of robust geometric modeling tends to be problem specific and has proven hard to generalize. The approach described here is a general paradigm for handling the accuracy problem for a large set of geometric algorithms. This approach brings together ideas and techniques from interval arithmetic, constraint management, randomization, and algebraic geometry. It acknowledges that input values have tolerances, that objects within tolerance are equivalent, and that certain geometric singularities must be maintained because they reflect design intent or the laws of geometry. Our approach is systematic, and can be applied almost mechanically to the large domain of problems that can be solved by algorithms using the operations +, ?, * and /. The required theory and algorithms have been developed, and the viability of the concepts has been demonstrated by an experimental implementation involving linear half-spaces in Euclidean 2-dimensional space. The implementation focuses on algorithms for computing the boundaries of objects defined by Constructive Solid Geometry (CSG) trees.