Tech Report CS-90-07

Constructive Solid Geometry for Triangulated Polyhedra

Philip M. Hubbard

September 1, 1990

Abstract:

Triangulated polyhedra are simpler to process than arbitrary polyhedra for many graphics operations. Algorithms that compute the boundary representation of a constructive solid geometry (CSG) model, however, may perform poorly if the model involves triangulated polyhedral primitives. A new CSG algorithm specifically tailored to triangulated primitives is presented. The key features of this algorithm are its global processing of intersections between polyhedra and its avoidance of ray-casting when classifying polyhedra against one another. The new algorithm is shown to perform substantially better than one published algorithm, and arguments are presented suggesting its benefits over several others in the context of an interactive modeling environment.

Keywords: constructive solid geometry, Boolean set operations, solid modeling, polyhedra, triangulation.

(complete text in pdf or gzipped postscript)