BOOLE: A System for Computing Boundary Representations of CSG Solids
composed of Sculptured Models
Click to view example CSG solid.
We have developed algorithms and a system, BOOLE, for generating B-reps from CSG
solids descriped using sculptured models. We provide efficient and accurate algorithms for Boolean combinations of solids. We represent the surface of these
solids in terms of
trimmed and
un-trimmed spline surfaces and a connectivity graph .
Based on algorithms for trapezoidation of polygons, partitioning
of polygons, surface intersection and ray-shooting, we compute the
boundaries of the resulting solids after the Boolean operation.
The preliminary version of the system is complete and has been tested on a number of industrial models We also address a number of robustness issues and techniques to handle some degenerate cases.
Overview of the method
Every CSG object is built from a set of primitive objects which are of
a simpler structure, and we assume that each of these primitives is an
oriented solid representable as a collection of parametric
surface patches. Apart from the primitive objects, each intermediate
and final solid in the CSG hierarchy is represented as a collection of
trimmed surface patches. Along with the surface definition,
every trimmed patch contains a trimming curve on its
domain which unambiguously determines which part of the surface is to
be retained. We also create a graph that maintains the connectivity
information between the various patches of the solid. The entire
algorithm proceeds in two steps. Initially, the complete intersection
curve between the two solids (at some level in the CSG tree) is
determined. If the set operation on the two solids is well-defined,
the intersection curve partitions each solid. The second step of the
algorithm uses the graph structure of each solid, and depending on the
set operation, computes the new solid and its associated graph
structure .
Click to view graph structure.
Return to
Geometric and Solid Modeling page.
Return to UNC Research Group on
Modeling, Physically-Based Simulation and Applications page.
Click to view graph structure.
Click to view example CSG solid.