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.

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.

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

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.

- John Keyser (Texas A&M University)
- Tim Culver (Think3)
- Mark Foskey (UNC)
- Shankar Krishnan (AT&T Research Labs)

- Dinesh Manocha

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

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).

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]

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