On the Representation and Manipulation of Rigid Solids

Abstract

Solid modeling studies how to represent geometric properties of solids by computer. A fundamental operation is the construction of representations of solids. Algorithms for set ooperations construct boundary representations of solids from boundary representations of other solids. A correct and efficient intersection algorithm for polyhedral solids that uses boundary representations is described. A finite-precision implementation of the slgorithm uses incidence tests that use symbolic inference in order to limit errors due to finite-precision approximations. The incidence tests are described and experimental evidence is presented to show that the incidence tests are both empirically reliable and practical. The intersection algorithm uses a new boundary representation called the Star-Edge representation. A complementation algorithm for solids that uses the new representation is given, and an algorithm is given that uses the new representation to determine if two boundary representations describe the same solid. A canonical boundary representation for solids is described and used to prove a lower bound for the same-object problem.