A Simple Approach to Performing Set Operations on Polyhedra

Abstract

In performing regularized set operations on two solids, the most difficult step is boundary classification, in which the boundaries of each solid are split into portions that are inside, outside, or on the surface of the other solid. In this paper, we present a method for doing boundary classification on polyhedra solid. The approach is based on recursively decomposing space based on the boundaries of the solids being classified.This approach has several appealing properties: it is simple to describe, efficient (tests indicate O (n log n) complexity in a variety of cases), and can handle both manifold and non-manifold 3-D solids. This approach serves as the basis for set operations in the Protosolid solid modeler.