Computational issues in solid boundary evaluation

Abstract

Boundary representation is an attractive formalism for describing the geometry of three-dimensional solid objects, providing a complete and explicit enumeration of the contiguous surface elements constituting their bounding surfaces. The computational procedure whereby boundary representations are derived from informationally complete but implicit input specifications for solids (e.g., a sequence of Boolean operations acting on elementary solid primitives) is known as boundary evaluation. Recent research in boundary evaluation has emphasized the topological adjacency relationships defined by the surface elements of a boundary file, which furnish an organized data structure for storing and accessing boundary information. However, the issues of the computational procedures by which these surface elements are actually derived and their formal mode of representation have been largely neglected. Consequently, reliable boundary evaluation has not made significant progress beyond polyhedral and quadric surface objects. The basic computational problem in boundary evaluation is the reliable determination of surface intersections. The surface elements participating in a boundary file are known as trimmed surfaces, since one can imagine them as being cut out of unbounded analytic parent surfaces along intersection curve segments. The issues of surface intersection computation and trimmed surface representation are thus intimately coupled, and their consistent treatment is the key to reliable boundary evaluation. In this paper we survey the available procedures for computing surface intersections, representing trimmed surfaces, and processing solid boundary representations, and briefly describe a novel trimmed-surface formulation which adopts a unified, systematic approach to the boundary evaluation problem. The focus is on the reliable computation and representation of individual trimmed surface elements, rather than data structures for expressing their topological adjacencies or the processing and applications of boundary files per se. Since boundary evaluation is usually not an end in itself, however, we describe elementary interrogation functions which form the basis for real applications. © 1988.