“Constructive solid geometry for polyhedral objects” by Laidlaw, Trumbore and Hughes

Constructive Solid Geometry (CSG) is a powerful way of describing solid objects for computer graphics and modeling. The surfaces of any primitive object (such as a cube, sphere or cylinder) can be approximated by polygons. Being abile to find the union, intersection or difference of these objects allows more interesting and complicated polygonal objects to be created. The algorithm presented here performs these set operations on objects constructed from convex polygons. These objects must bound a finite volume, but need not be convex. An object that results from one of these operations also contains only convex polygons, and bounds a finite volume; thus, it can be used in later combinations, allowing the generation of quite complicated objects. Our algorithm is robust and is presented in enough detail to be implemented.

1. Foley, J. D. and A. van Dam, Fundamentals of Interactive Computer Graphics, Addison-Wesley, 1982.
2. Requieha, A. A. G. and H. B. Voelcker, “Construcvive Solid Geometry,” Production Aut, oma~ion Project Technical Memorandum TM-25, April 1980.
3. Requicha, A. A. G. and H. B. Voelcker, “Mathematical Foundations of Constructive Solid Geometry: General Topology of Closed Regular Sets”, Production Automation Project Technical Memorandum TM-27a, November 1980.
4. Requicha, A. A. G. and H. B. Voelcker, “Solid Modeling: Current Status and Research Directions,” IEEE Computer Graphics and Applicatione, 3 (7), October 1983.
5. Requieha, A. A. G. and H. B. Voelcker, “Boolean Operations in Solid Modeling: Boundary Evaluation and Merging Algorithms,” Proceedings of the IEEE January 1985, pp. 30-44.
6. Roth, Scott, “Ray Casting for Modeling Solids,” Computer Graphics and Image ProcesMng 18 (1982), pp. 109-144.
7. Strauss, P., M. Shantzis and D. Laidlaw, “SCEFO: A Standard Scene Format for Image Creation and Animation,” Brown University Graphics Group Memo, Providence, R.I., 1984, 32 pp.
8. Turner, James A., “A Set-Operation Algorithm for Twoand Three-Dimensional Geometric Objects,” Architecture and Planning Research Laboratory, College of Architecture, University of Michigan, Ann Arbor, MI, August, 1984.
9. Johnson, Rober~ H., Solid Modeling: A State of the Art Report (Second Edition), CAD/CI}%4 Alert, Management Roundtable, Inc., 1986.