Partitioning Polyhedral Objects into Non-Intersecting Parts
Technical Report Identifier: CSD-86-284
Abstract: An algorithm for partitioning intersecting polygons embedded in three-space into disjoint parts is described. Polygons, or faces, need not be convex and may contain multiple holes. Pairwise intersections between faces are removed by slicing faces apart along their regions of intersection. To help reduce the number of face pairs examined, bounding boxes are found for objects consisting of groups of faces, and these boxes are checked for overlap.
The intersection algorithm has also been expanded to implement set-theoretic operations on polyhedra. Information gathered during face cutting is used to determine which portions of the original boundaries may be present in the result of an intersection, union, or difference of solids.
Tolerances are calculated for computed vertices, edges and faces and are used to locate regions in which numerical inaccuracy may lead to erroneous results. Various heuristics overcome most such situations, but some require further information from the user.