Efficient and Robust Solid Modeling with

SolidTool(tm) V1.05

1. Overview

The SolidTool(tm) is a fully reentrant, very fast, very compact, yet powerful

solid modeling library developed by J&L Associates. It is best suited for

interactive solid modeling and Internet applications because of its speed and small

size. The entire library is written in ANSI C and is thus platform independent.

It features boolean set operations (union, intersection, difference and symmetric difference)

and CSG operations on polyhedrons in 3D and on polygons in 2D, using Binary Space

Partitioning (BSP) Trees.

One feature that distinguishes SolidTool(tm) from other solid modeling libraries is

its implementation of boolean operations using 3 (yes, three!) different methods:

1) "Incremental" method for boolean operations between a BSP tree and a solid,

2) "CSG" method for boolean operations on a CSG tree that may contain unlimited

(limited by RAM, off course) number of boolean operations and primitive

solids;

3) "Tree-Merging" method for boolean operations between two BSP trees that

may contain no boundary information;

In the below, we use the single term "polytopes" to refer to polyhedrons in

3D and polygons in 2D.

2. Advantages of the BSP Tree Solid Modeling

The most common method for representing polyhedron appears to be

Boundary Representation (B-rep) where a polyhedron is represented by faces,

edges and vertices, as well as their relationships through topology. Efficiency

considerations necessitate some kind of spatial search structure, one that is

extrinsic to the representation and is typically an axis aligned spatial

decomposition, say an octree structure. Such a spatial structure does not transform

with the representation and so must be reconstructed after each transformation,

further complicating an already complex problem.

The BSP tree is a binary tree representing a recursive partitioning of d-

space by hyper-planes, for any dimension d. The methodology ignores topological

properties of polyhedrons and deals with geometry only. It provides a general way

of representing polyhedra: any genus (handles/holes) is permissible and any

number of connected components, and regions of connectivity with no interior,

such as two parts connected by a vertex (which is known as non-manifold

geometry). While handling non-manifold geometry with B-rep is extremely

complex, no distinction is made between manifold and non-manifold geometry the

with the BSP tree approach, making its implementation much more compact and

potentially more robust.

Besides, the spatial search structure is already built-in with the BSP tree

approach. The expected time for any boolean operations is n*log(n) where n is

roughly (2*Number of faces of the polyhedra+1) and the worst case complexity is

quadratic when the tree is highly unbalanced, say, as a linear list, which is not the

case most of the time.

3. Assumptions

For boolean operations on polyhedra, the faces of a polyhedron must satisfy

the following restrictions:

(1) All faces must be planar, i.e., they are polygons. Concave polygons are

allowed.

(2) No faces may intersect any other faces in the object.

For boolean operations on polygons, all polygons are assumed to be

coplanar (can be concave or convex), and no edge crossing is allowed. If the

polygon is oriented counter-clockwise, the space enclosed is "solid", otherwise

it is void.

The library DOES NOT CHECK these conditions. It is up to the calling

program to ensure that the objects being combined satisfy the restrictions. Note

also that objects must enclose space properly. There can be no dangling edges or

faces.

The library DOES CHECK for the following degenerate cases:

(1) If three vertices in the polygon are collinear, the middle one will be

eliminated.

(2) If an input face is too small, i.e. all of their vertices are nearly collinear,

the face will be eliminated prior to computation.

Solid modeling usually assumes that the face normals of a solid are consistently

oriented, i.e., the vertices of faces are either all oriented counter-clockwise

when viewed from outside the object, or all clockwise so that polygon normals

may be used to determine the interior (and exterior) of the object. In the

former case, the space enclosed by the polyhedron is 'solid' whereas in the

later case, it is void. With SolidTool(tm), this assumption is not necessary.

SolidTool(tm) provides an API that allows the user to detect and correct any

violating normals so as to "solidify" the input data.

It is felt that the above restriction is not too limiting and in fact, they are

pretty "loose" for polyhedra modeling. The only restriction that may be of a

concern to some users is that the library does NOT support curved surfaces yet. A

workaround might be to tessellate the surface into triangles, which can then be

handled naturally by the library. However, this is only an approximation and

precise representation is not possible. Research is being conducted to remove this

limitation in future releases.

4. Library Capabilities

The library is best suited for interactive solid modeling and Internet

applications because of its speed and small size.

The current version of SolidTool(tm) library support the following operations:

(1) Boolean operations between a BSP tree and a polytype using "Incremental"

method;

(2) CSG evaluations on multiple polytopes using "CSG" method. The calling

program can construct a CSG tree with leaf nodes containing polytopes and

internal nodes representing set operations (Intersection, Union, Difference

and Symmetric Difference). The library provides an API call to evaluate

such a CSG tree, producing either a BSP tree or a boundary representation

of the composite polytope. Alternatively, this can be accomplished by

multiple pairwise set operations using the Incremental or Tree-Merging method.

But, evaluating a CSG tree would be much faster in this case. A test case,

where 180 unions was perfomed on 360 cubes, each of which is obtained by

successive rotation of a unit cube by 1 degrees around z axis, took 14 seconds

on a Pentium 133, reesulting in a solid whose volume is 1.55724. Replacing the

180 unions with 180 intersections in this case took 17 seconds, resulting in a

solid whose volume is 0.785418. Replacing the 180 unions with 180 differences

took 3 seconds, resulting in an empty set.

(3) Boolean operations between two BSP trees through generic Tree-Merging.

This is useful when the input data consist only of BSP trees with no boundary

information; This alows one not to store boundary informatin with store

(4) BSP tree creation from polytypes;

(5) Efficient generation of boundary from a BSP tree with no boundary information.

This alows one not storing boundary information with a BSP tree in order to

save disk space and loading time.

(6) Ability to detect and correct in-consistent faces whose normals are not properly

oriented so as to "solidify" the input data.

(7) Faces of the polyhedron resulted from a set operation are all convex.

But the library is capable of merging coplanar faces (also known as

boundary minimization), if required.

(8) The faces of an input polyhedron can be concave polygons;

(9) profile generation from solid bodies by slicing;

(10) Spliting of a solid body into two solid bodies.

(11) Any linear transformations can be applied to a solid body.

(12) Interrogations or collision detections are possible: point, lines and

polygons can be classified with respect to a solid body to determine

the parts that are 'inside', 'outside', and 'on' the body.

(13) Model statistics, such as surface area and body volume can be easily

obtained.

(14) BSP trees can be serilized to disk with or without boundary information.

(15) Creation of popular primitives: cube, cylinder, sphere, ellipsoid,

pyramid, cone, tetrahedra, and torus, etc.;

(16) Complex objects can also be created through 'lathe' and 'lofting'

(to be available);

(17) Export to DXF file is provided.

5. Efficiency and Robustness

All of the three algorithms have expected time complexity of n*log(n), where n is

roughly (2*Number of faces of the polyhedra+1). When the polyhedra are seperable,

the time complexity is reduced to linear.

When the input data are two polytopes, both Incremental method and Tree-Merging methods

can be used. But the former is faster due to its algorithmic simplicity and non-recursive

implementation. The Tree-Merging algorithm is implemented in a recursive fashion, making

it slower, but potentially more robust since the only floating point calculation is the

partitining of a polygon by a plane whose primitive operation is the dot product of a point

and a plane to determine the location of that point with respect to the plane.

When performing boolean operations on more than two polytypes, the CSG method is much

faster than repeated applications of either Incremental or Tree-Merging method.

All of the three methods employ two defenses to achieve robustness: 1) using variable tolerance

and 2) forcing the sematics of the neighborhood operation when it fails due to numerical problems.

The result is robust set operations in the sense that the program will not fail and its output

is in the neighborhood of the ideal output over a large numerical range.

6. Implementation Issues

Currently only the Tree-Merging method is implemented recursively. Both Incremental and

CSG algorithms are implemented in a non recursive fashion, eliminating the posibility of stack

overflow when processing large binary trees and noticably improving the excusion speed. Future

release of SolidTool(tm) will make the Tree-Merging method non-recursive as well.

The source code is 25,000 lines (about 1.4MB). It uses no global or static variables, and is

multi-thread-safe and fully re-entrant, making it an ideal compact software component. It is

available as LIB, DLL or (in-place) COM server. Source code is also available.

For Windows 95 and Windows NT, the library is UNICODE capable.

7. The Demo Program

A demo program using the library is available upon request.

8. Pricing

Very affordable. The license fee is only a small fraction of those on the market,

such as ACIS from Spatial Technologies Inc.

There are basically two options, both enjoy six months free support through e-mail, and

pays no royalty!

1). Single Product/Platform Binary Code License: $1000US (one thousand US dollars)

per product per platform. The product you produced, as a result of linking

with the SolidTool library (either a DLL or a LIB), can be distributed by you

without paying any royalty; 50% discount applied to additional licences per

product per platform.

2). Muiti-product/platform Source Code License: $10,000US (ten thousand US dollars) per

copy. You can modify the source for your own needs. The compiled library

(either object code, or DLL) produced from the source (either modified or unmodified)

can be linked with ANY of your software packages without paying any royalty. However,

you cannot disclose or sell the source to other parties, neither can you distribute

the compiled library as part of another third party library.

8. Further Information

Our web page is under re-construction and will be available soon.

For further information, please contact Qi Liu through email:

dt...@freenet.carleton.ca

Thank you for your interest in SolidTool(tm).

--

Qi Liu

J&L Accociates

dt...@freenet.carleton.ca