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.
The BOOLE system. 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, and ray-shooting, it computes the boundaries of the resulting solids after the Boolean operation. The system has been tested on a number of industrial models, for instance the Bradley fighting vehicle (pictured).
Current Work. 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 where four surfaces meet at a point or where two surfaces are coincident. The other class of robustness problems is 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 cases. 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, Appeared in Proceedings of ACM Solid Modeling '97.
[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] BOOLE: A System to Compute Boolean Combinations of Sculptured Solids. S. Krishnan and D. Manocha, Technical Report TR95-008, Department of Computer Science, University of N. Carolina, Chapel Hill. Proc. of CSG'96