Home
News
Research
People
Classes
Background:
Constructive Solid Geometry (CSG) is a method by which complex 3D
objects are created by combining simpler 3D objects using set
operations such as union, subtraction, and intersection. CSG operations
are the basis for most modern Computer Aided Design programs such as
Autodesk Inventor, CATIA, and Unigraphics.
CSG operations use complex
geometric algorithms and are time-consuming. In case of contiunous
space object representation, while the algorithms are complex (and
highly sensitive to numerical errors), the number of objects (faces,
edges, vertices) are few. In case of tesselated models , while the
algorithms are not complex (dealing with planar geometry), the number
of objects are numerous. Consequently, CSG
operations are very cumbersome.
This research has developed an improved CSG method for objects represented using Binary Space Partitioning (BSP). BSP is the most generalized of space partioning techniques which include, Bounded Volume Hierarchy , Kd trees, and R-Trees. As such, algorithms developed here will be applicable to each of these representations
Method:CSG operations on objects represented using BSPs is achieved using tree-merging. Previously, Neylor et. al. developed a tree-mergining algorithm that relied on BSP partioning using polygon clipping. The new method developed in this research made the key conclusion that tree merging is nothing more than solving linear programming feasibility. Thus any linear programming algorithm such as the one by Sidel can be used to solve this problem. This reduces the complexity of CSG operations from O(n^d) to O(n).
All operations and representations are performed in object space.
Results:
Figure 1 shows the result of set operations between a Stanford bunny mesh and a toroidal knot. These operations have achived interactive speeds. The movie below shows interactive subtractions of dodecahedrons from a pigshroom mesh (pig U mushroom). Note that the movie also illustrates real-time slicing of the complex objects as the boolean operations take place. This is the result of directly slicing the BSP and the slices are guaranteed to be closed. This can have far reaching impact in RP where conventional polygon mesh slicing algorithms can frequently result in open 2D sections.
Publications:
Lysenko M., D'Souza R., Real-time Constructive Solid Geometry, to be submitted (also a sketch in SIGGRAPH 2007)
Acknowledgment:
| Dept.
of Mechanical Engineering-Engineering Mechanics Michigan Tech. University 1400 Townsend Drive Houghton MI 49931 Ph: 906-487-1001 |