Image caption: A CSG model of a Bradley fighting vehicle. Model courtesy of Army Research Lab.
Image caption: The drivewheel for the left track, in boundary representation.
Overview and Motivation. The field of solid modeling deals with the design and representation of physical objects. The two dominant representation schemata used in solid modeling are constructive solid geometry (CSG) and boundary representations (B-rep). Both of these representations have different inherent strengths and weaknesses, and for most applications, the flexibility to handle both representations is desirable. Early solid modelers were able to handle solids composed of linear boundary elements (polyhedra) and of quadric boundary elements (spheres, cylinders, etc.), and to form their Boolean combinations.
Recently, techniques developed in the field of geometric modeling have been used to model sculptured solids composed of higher-degree surfaces. Integrating such models into solid modelers has proven to be a challenge. In particular, there is considerable interest in building complete solid representations from spline surfaces, and computing Boolean combinations of these. However, computing such combinations requires the representation and evaluation of intersections of parametric surfaces. The difficulty of this problem has impeded the development of solid modelers that incorporate sculptured solids.
We have developed algorithms and a system, BOOLE, for generating B-reps of sculptured CSG models. The system provides efficient and accurate algorithms for Boolean combinations of solids. Solids are represented by their B-reps, consisting of trimmed spline surfaces, and a connectivity graph. Based on a geometric kernel of routines for surface intersection, curve fitting, trapezoidation of polygons, partitioning of polygons, and ray-shooting, it computes the boundaries of the resulting solids after the Boolean operation.
High-level algorithm. Every CSG object is built from a set of primitive objects, 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. At each level, the algorithm considers a pair of solids and computes their intersection curve. This curve becomes a collection of new trimming curves for the parametric patches. The extent and orientation of each trimming curve is then determined, and the adjacency information updated, so that we are left with a single, valid solid.
The BOOLE system. Our floating-point implementation has been tested on a number of industrial models, for instance the Bradley fighting vehicle (pictured). (The Bradley model consists of over 8,000 primitive solids.) BOOLE is available for download at http://www.cs.unc.edu/~geom/CSG/boole.html.
Efficiency. BOOLE exploits parallelism at all stages. It has been implemented on a multi-processor SGI workstation and takes one second on average per boolean operation to compute the boundary of high-degree primitives.
Interactivity. The system has also been integrated with an immersive design and manipulation environment. The resulting system is able to interactively evaluate boundaries of the models, display them for model validation and place them at appropriate position using collision detection algorithms.
Robustness. Our current work is focused on robustness issues which arise in solid model designs with curved surfaces. One class of robustness problems is degeneracies. Examples of degeneracies include four surfaces meeting at a point or two coincident surfaces. The other class of robustness problems arises from cases where the use of fixed precision (floating point) arithmetic is not accurate enough to correctly determine a boundary representation. Previous work on robustness issues has dealt primarily with linear (polyhedral) solids. Robustness problems in curved surface cases are both more numerous and more difficult to handle. Experience with the BOOLE system has shown us that robustness problems can arise in a significant number of real-world cases.
Our current approach addresses robustness issues by making use of exact arithmetic and exact representations. This eliminates the problems related to numerical precision. In addition, the use of exact arithmetic will allow us to use perturbation methods to eliminate degeneracies. Perturbation methods have proven to be useful at eliminating degeneracies in the linear case, and may be similarly useful in the curved-surface domain.
The use of exact arithmetic can lead to highly inefficient implementations. In order to increase the efficiency of our approach, we have isolated a few key kernel routines which govern the efficiency of the overall program. We use algebraic techniques and combinations of exact and floating point arithmetic to speed up our kernel functions, and thus the program, as much as possible.
[2] Efficient and Accurate B-rep Generation of Low Degree Sculptured Solids using Exact Arithmetic. J. Keyser, S. Krishnan, D. Manocha, Proceedings of ACM Solid Modeling '97, pp. 42-55.
[3] An Efficient Surface Intersection Algorithm based on Lower Dimensional Formulation. S. Krishnan and D. Manocha, ACM Trans. on Computer Graphics , 16(1), pp. 74-106, 1997.
[4] Efficient representations and techniques for computing B-rep's of CSG models with NURBS primitives. S. Krishnan and D. Manocha, Technical Report TR95-008, Department of Computer Science, University of N. Carolina, Chapel Hill. Proceedings of CSG 1996, pp. 101-122.
[5] Algebraic Loop Detection and Evaluation Algorithms for Curve and Surface Interrogations. S. Krishnan and D. Manocha, Proceedings of Graphics Interface, pp. 87-94, 1996.
[6] Algebraic Pruning: A Fast Technique for Curve and Surface Intersections. D. Manocha and S. Krishnan, CAGD 20(1997), pp. 1-23.
[7] Algorithms for intersecting parametric and algebraic curves I: simple intersections. D. Manocha and J. Demmel, ACM Transactions on Graphics 13, no. 1 (1994), pp. 73-100.
[8] Algorithms for intersecting parametric and algebraic curves II: multiple intersections. D. Manocha and J. Demmel, Computer Graphics, Vision and Image Processing 57, no. 2 (1995), pp. 81-100.