This is an electronic version of a Technical Sketch which I presented at SIGGRAPH 99 - a computer graphics conference held in Los Angeles in August 1999. Further details concerning this research may be found here.
Constructive Solid Geometry has many features that make it attractive for conceptual design, e.g hierarchical modeling and intuitive operations. Existing techniques for interactive CSG [3] update the geometry of the entire model for every object manipulation. For larger models, such techniques cannot achieve the responsiveness required for interactive work. We use a space-subdivision technique to reduce the amount of computation by recomputing only those parts of the model that have changed since the last update.
Every primitive is polygonized in order to take advantage of graphics display hardware. This is done by dividing each primitive's surface up into a number of rectangular areas of space. We trace rays in a three-dimensional grid inside these areas, and find all intersection points of the primitive's algebraic surface with the grid. These points are polygonized by an implicit surface tiler [2] to generate a number of triangles inside every grid cell.
The modeling workspace is subdivided into an octree, typically three to four levels deep. Each node in the CSG graph contains an octree data structure that stores empty / full information. At the bottom level of the octree, if the object's surface is present, a 'leaf node' stores a reference to every grid that intersects that area of space. Octrees which represent a CSG combination will reference grids that belong to a number of different primitives.
When a primitive object is created or moved, its octree is found by testing each section of the octree against the algebraic function. The octree is subdivided down to the bottom level, where each leaf node tests to see which grids overlap its area. References to these grids are stored, and if there are any changes from the previous octree then a 'changed' flag is set. This changed flag is propagated up the octree structure, so that higher-level nodes are changed if any of their children are.
|
To perform a CSG operation between two objects, we traverse the changed sections of the octrees, looking for grids that overlap each other. For each cell in each grid (e.g. the red cell in the orange grid), we find which cells it overlaps in each of the opposing grids that overlap its section of the octree (e.g. the highlighted cells in the blue grids). We use a triangle-splitting algorithm based on Laidlaw et al [1] to split the triangles in a cell against the opposing triangles, determining for each split triangle whether it lies inside or outside the opposing object. The CSG operation determines which triangle subset is inserted into the combined octree. |
| Complex cutting operations may be performed on models such as this one with approximately five updates per second (Pentium II - 450
MHz). This lets us build CSG objects interactively, using a
direct-manipulation interface. This system meets many of the
requirements of conceptual design; it allows rapid prototyping of
objects and gives immediate feeedback on changes, while retaining the
features that make CSG attractive for solid modeling. The split operation is O(n*m) in the number of triangles, however the octree division of the workspace reduces the number of grids that must be tested, and the uniform subdivision of each grid reduces the number of cells whose triangles must be split against. This allows us to keep n and m down to 2-10 triangles in almost all cases, although a few cells that lie on corners of the model may have up to 40 triangles. |
 |