ANN: BSP Solid Modeling

ANN: BSP Solid Modeling

Post by Guiqi L » Sat, 12 Jul 1997 04:00:00



                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