ESOLID - Exact boundary evaluation for low-degree curved solids

ESOLID

ESOLID is a program for performing exact boundary evaluation of low-degree curved solids. It has been developed over the past few years by the UNC Modeling Research Group.

Motivation

Two of the major representations for solid models are CSG and B-rep. A CSG (Constructive Solid Geometry) model is stored as a set of Boolean operations (union, intersection, and difference) on primitive solids. The standard CSG primitive solids generally have low degree surfaces. Ths standard CSG solids include polyhedra, cones, cylinders, spheres, ellipsoids, and tori. B-rep (Boundary Representation) models, on the other hand, store a solid as a collection of surfaces which define the boundary of the solid. Each of these representation formats has advantages and disadvantages, and so conversion from one to the other is often desired.

Boundary evaluation is a process used to convert from CSG models to B-rep models. Specifically, boundary evaluation performs Boolean combinations of B-rep models. So, to convert from CSG to B-rep, the primitive CSG solids are converted to B-rep, and then boundary evaluation is performed on those converted primitives to form the overall solid.

A significant problem can arise when performing boundary evaluation, however. This is the problem of numerical error. Slight inaccuracies in the representations or the computations can cause numerical errors, which can lead to seriously incorrect output or program crashes. Even seemingly minor errors can eventually compound until they are serious enough to cause these problems. These problems with numerical error are magnified considerably when dealing with curved surfaces. Our own experience with development of a curved boundary evaluation system (BOOLE) which used standard floating-point arithmetic (which is inexact) highlighted the need for increased accuracy.

The approach that we chose to follow has been to use exact computation. Exact computation means that all numerical values are determined to a precision guaranteed to make any decision based on that number correct. The drawback to exact computation is that it can be extremely slow (many orders of magnitude). The goal of our work has been to create a boundary evaluation program that uses exact computation (thus eliminating all numerical errors) that runs on low-degree curved solids (i.e. the types found in most CSG models), at speeds no more than two orders of magnitude slower than a comparable inexact program.

The result of this work has been the creation of ESOLID. ESOLID is a program for exact boundary evaluation on low-degree curved solids. It has been successfully applied to real-world data from the Army Research Lab's Bradley Fighting Vehicle model, and has converted from CSG to B-rep within the time frame set as a goal (two orders of magnitude slower than BOOLE). It has been shown to work on cases that an inexact approach (BOOLE) failed on, as well as cases that require precision unattainable by standard floating-point based methods. Some sample output is shown below.

Sample Output

Bradley Fighting Vechicle Sample Output

Following are four images of data converted from the Bradley Fighting Vehicle data set. The Bradley Fighting Vehicle is a model developed by the Army Research Lab within their BRL-CAD solid modeling system. BRL-CAD is a CSG-based solid modeling system. ESOLID was used to convert parts of the Bradley model from a CSG format to an exact curved B-rep format. All times are in seconds on a 300 MHz R12000 processor. Note that some parts of these models (e.g. in the crew member) are defined by a "join" rather than a "union," thus not requiring a Boolean operation.

An M16 Rifle:
6 Boolean Operations
Time for ESOLID: 620
Time for BOOLE: 6.76


A track link:
11 Boolean Operations
Time for ESOLID: 145
Time for BOOLE: 28.5


A crew member:
2 Boolean Operations
Time for ESOLID: 35
Time for BOOLE: Fail


An engine access hatch:
16 Boolean Operations
Time for ESOLID: 59
Time for BOOLE: Fail

More Sample Output

A web page for ESOLID Sample Output has been created to show examples of the various hand-created examples. These examples include several of the different types of primitive solids that can be handled by ESOLID.

Contributors

The following individuals have contributed to the work on ESOLID:
  • Former UNC Graduate Students
  • UNC Faculty

    References

    Papers which have been published as a part of this ongoing work include the following:

    Publications

    Mark Foskey, Dinesh Manocha, Tim Culver, John Keyser, Shankar Krishnan
    Reliable Geometric Computations with Algebraic Primitives and Predicates
    Proceedings of the Workshop on Uncertainty in Geometric Computations, Sheffield, July 2001 (proceedings to appear 2002)
    [PDF]

    John Keyser, Tim Culver, Mark Foskey, Shankar Krishnan, Dinesh Manocha
    ESOLID-A System for Exact Boundary Evaluation.
    Proceedings of the ACM Conference on Solid Modeling, June 17-21, 2002.
    [PDF]

    John Keyser, Tim Culver, Dinesh Manocha, Shankar Krishnan.
    Efficient and Exact Manipulation of Algebraic Points and Curves.
    Special Issue of Computer Aided Design on Robustness. 2000.
    (Preliminary versions are available as "MAPC: A library for Efficient and Exact Manipulation of Algebraic Points and Curve" or as UNC-CS Technical Report TR98-038)
    [PDF]

    John Keyser, Shankar Krishnan, Dinesh Manocha.
    Efficient and Accurate B-rep Generation of Low Degree Sculptured Solids Using Exact Arithmetic: I -- Representations
    Computer Aided Geometric Design. Vol 16, No. 9. pp. 841-859. October, 1999.
    (Preliminary versions are available as "Efficient and Accurate B-rep Generation of Low Degree Sculptured Solids using Exact Arithmetic" or as UNC-CS Technical Report TR96-040.)

    John Keyser, Shankar Krishnan, Dinesh Manocha.
    Efficient and Accurate B-rep Generation of Low Degree Sculptured Solids Using Exact Arithmetic: II -- Computation
    Computer Aided Geometric Design. Vol 16, No. 9. pp. 861-882. October, 1999.
    (Preliminary versions are available as "Efficient and Accurate B-rep Generation of Low Degree Sculptured Solids using Exact Arithmetic" or as UNC-CS Technical Report TR96-040.)

    John Keyser, Tim Culver, Dinesh Manocha, Shankar Krishnan.
    MAPC: A library for Efficient and Exact Manipulation of Algebraic Points and Curves.
    Proceedings of Fifteenth Annual Symposium on Computational Geometry, pp. 360-369, 1999.
    [gzipped Postscript]
    (A preliminary version is available as UNC-CS Technical Report TR98-038.)

    John Keyser, Shankar Krishnan, Dinesh Manocha and Tim Culver.
    Fast and Accurate Boundary Evaluation of Low-Degree Sculptured Solids.
    Proceedings of IMA Conference on Mathematics of Surfaces, vol. 8, pp. 139-160, 1998.
    [gzipped Postscript] [PDF]

    John Keyser, Shankar Krishnan, Dinesh Manocha.
    Efficient and Accurate B-rep Generation of Low Degree Sculptured Solids using Exact Arithmetic
    Proceedings of Fourth Symposium on Solid Modeling and Applications (ACM Solid Modeling '97), pp. 42-55, 1997.
    [gzipped Postscript]
    (A preliminary version is available as UNC-CS Technical Report TR96-040).

    Technical Reports

    John Keyser, Tim Culver, Dinesh Manocha, Shankar Krishnan.
    MAPC: A library for Efficient and Exact Manipulation of Algebraic Points and Curves.
    Technical Report TR98-038, Department of Computer Science, University of North Carolina, Chapel Hill. 1998.
    [compressed Postscript])

    John Keyser, Shankar Krishnan, Dinesh Manocha, Tim Culver.
    Efficient and Reliable Computation with Algebraic Numbers for Geometric Algorithms.
    Technical Report TR98-012, Department of Computer Science, University of North Carolina, Chapel Hill. 1998.
    [compressed Postscript]

    John Keyser, Shankar Krishnan, Dinesh Manocha.
    Efficient B-rep Generation of Low Degree Sculptured Solids Using Exact Artihmetic
    Technical Report TR96-040, Department of Computer Science, University of North Carolina, Chapel Hill. 1996.
    [compressed Postscript]

    Acknowledgements

    The Bradley Fighting Vehicle Model was provided courtesy of the Army Research Lab.

    Supported in part by an Alfred P. Sloan Foundation Fellowship, ARO Contract DAAH04-96-1-0257, NSF Career Award CCR-9625217, ONR Young Investigator Award (N00014-97-1-0631), Honda, Intel and NSF/ARPA Center for Computer Graphics and Scientific Visualization