Boolean operations in solid modeling: Boundary evaluation and merging algorithms
- 1 January 1985
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in Proceedings of the IEEE
- Vol. 73 (1) , 30-44
- https://doi.org/10.1109/proc.1985.13108
Abstract
Solid modeling plays a key role in electromechanical CAD/CAM, three-dimensional computer graphics, computer vision, robotics, and other disciplines and activities that deal with spatial phenomena. Almost all contemporary solid modeling systems support Boolean operations akin to set intersection, union, and difference on solids. Boundary representations (face/edge/vertex structures) for solids defined through Boolean operations are generated in these modelers by using so-called boundary evaluation and boundary merging procedures. These are the most complex and delicate software modules in a solid modeler. This paper describes boundary evaluation algorithms used by the PADL solid modeling systems developed at the University of Rochester, and discusses other known approaches in terms of concepts that emerged from the PADL work, notably set membership classification and neighborhood manipulation.Keywords
This publication has 21 references indexed in Scilit:
- Geomap-III: Designing Solids With Free-Form SurfacesIEEE Computer Graphics and Applications, 1984
- A note on the modeling space of Euler operatorsComputer Vision, Graphics, and Image Processing, 1984
- Solid Modeling: Current Status and Research DirectionsIEEE Computer Graphics and Applications, 1983
- OYSTER: A Study of Integrated Circuits as Three-Dimensional StructuresIBM Journal of Research and Development, 1983
- Algorithms for computing the volume and other integral properties of solids. I. known methods and open issuesCommunications of the ACM, 1982
- Geometric modeling using octree encodingComputer Graphics and Image Processing, 1982
- Solid Modeling: A Historical Summary and Contemporary AssessmentIEEE Computer Graphics and Applications, 1982
- Representations for Rigid Solids: Theory, Methods, and SystemsACM Computing Surveys, 1980
- Closure of Boolean operations on geometric entitiesComputer-Aided Design, 1980
- Finding the intersection of two convex polyhedraTheoretical Computer Science, 1978