Real-Time Boolean Operations for 3-D Conceptual Design and Geometric Modeling


Dr. Ari Rappoport
Institute of Computer Science
The Hebrew University, Jerusalem, Israel


Of all stages in the design process, conceptual design is the most difficult to computerize. Conceptual design is difficult since it poses requirements both for increased expressive power (the types of operations the user can use) and for interactive performance (the user expects rapid feedback in order to freely experiment with a large number of ideas). This statement holds for most kinds of design; we concentrate on the design of 3-D objects for industrial design, the graphics arts, and mechanical CAD.

The well known CSG modeling technique provides the user with simple parameterized primitives (e.g. blocks, spheres, cylinders, cones, torii), affine transformations and Boolean operations (union, difference and intersection). Complex objects are built from combinations of simpler ones. In conjunction with simple positioning constraints, these operations are highly attractive to designers. However, supporting them in real-time is possible today only on extremely expensive, dedicated hardware.

In this talk I will present an algorithm for real-time display of 3-D CSG objects. The algorithm represents a CSG object as a union of cells. Each cell is the difference between a containing convex object and a set of contained convex objects. The special nature of this representation allows us to utilize efficient convex hull techniques so that the result of the Boolean operations can be displayed in real-time using standard graphics APIs (e.g., an OpenGL machine with a single Z-buffer and a single stencil plane). I will show a video of a prototype system implementing the algorithm. I will also discuss how the presented algorithm fits in a more general framework for geometric modeling, in which a representation in only used to support a specific need. We utilize this principle in that we do not actually compute the Boolean operation; we only compute something which allows us to _display_ it on a screen.

Speaker's biography:

Ari Rappoport completed his B.Sc. in mathematics and computer science (1987) and his Ph.D. in computer science (1990) at the Hebrew University, Jerusalem, Israel. He was a postdoc at the geometric modeling and animation groups at the IBM T.J. Watson Research Center, NY. Since 1992 he is a lecturer at the Institute of Computer Science at The Hebrew University. His areas of interest include geometric and solid modeling, computer graphics and animation, image and video processing, and object-oriented analysis and architectures. Current projects include fundamentals of geometric modeling, parametric representations, modeling with constraints, feature-based font representations, interactive design systems, computation and application of the 3-D medial axis, and modeling 3-D objects from video and image sequences.