Interactive modeling of 3-D solids is an important and difficult problem in computer graphics. The Constructive Solid Geometry (CSG) modeling scheme is highly attractive for interactive design, due to its support for hierarchical modeling and Boolean operations. Unfortunately, current algorithms for interactive display of CSG models require expensive special-purpose hardware that is not easily available.
In this paper we present a method for interactive display of CSG models using standard, widely available graphics hardware. The method enables the user to interactively modify the affine transformations associated with CSG sub-objects. The application we focus upon is that of conceptual design, a stage in the design process in which rapid, interactive visualization of the model and high-level design operations are of crucial importance, while the objects are relatively simple.
The method converts the CSG graph to a novel Convex Differences Aggregate (CDA) representation. The CDA utilizes graph rewriting techniques, efficient geometric algorithms on convex objects and a built-in hierarchical acceleration scheme. The CDA rendering algorithm is very simple, takes advantage of standard graphics hardware, and makes efficient use of system resources by splitting the work between the graphics system and the CPU.
Here are some examples of objects modeled with the system. On the left, (b-d) show motion of a cylindrical hole inside a cube pattern, (f-g) show rotation of the hole, and (h) shows the intersection between the pattern and the cylinder. On the top right, the object is made of three cylinders, each having a cylindrical hole, and a block minus another smaller block. On the bottom right, we see the union (a,b), intersection (c) and difference (d) between two "ice-cream" cones, each made of a difference between two cones. The affine parameters of the Boolean operations defining these objects can be modified in real-time on a 100 Mhz R4000 SGI Indigo-XZ workstation. |