Partitioning polyhedral objects into nonintersecting parts

An algorithm is described for partitioning intersecting polyhedrons into disjoint pieces and, more generally, removing intersections from sets of planar polygons embedded in three space. Polygons, or faces, need not be convex and may contain multiple holes. Intersections are removed by considering pairs of faces and slicing the faces apart along their regions of intersection. To reduce the number of face pairs examined, bounding boxes around groups of faces are checked for overlap. The intersection algorithm also computes set-theoretic operations on polyhedrons. Information gathered during face cutting is used to determine which portions of the original boundaries may be present in the result of an intersection, a union, or a difference of solids. The method includes provisions to detect and in some cases overcome, the effects of numerical inaccuracy on the topological decisions that the algorithm must make. The regions in which ambiguous results are possible are flagged so that the user can take appropriate action.<>