Mark Gordon Segal

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-86-284
February 1986

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1986/CSD-86-284.pdf

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.

BibTeX citation:

@techreport{Segal:CSD-86-284,
    Author = {Segal, Mark Gordon},
    Title = {Partitioning Polyhedral Objects into Non-Intersecting Parts},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1986},
    Month = {Feb},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1986/5374.html},
    Number = {UCB/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.  <p>  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.  <p>  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.}
}

EndNote citation:

%0 Report
%A Segal, Mark Gordon
%T Partitioning Polyhedral Objects into Non-Intersecting Parts
%I EECS Department, University of California, Berkeley
%D 1986
%@ UCB/CSD-86-284
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1986/5374.html
%F Segal:CSD-86-284