Boolean Operations in Solid Modelling: Boundary Evaluation and Merging Algorithms

Solid modelling plays a key role in electromechanical CAD/CAM (Computer Aided Design and Manufacture), three-dimensional computer graphics, computer vision, robotics, and other disciplines and activities that deal with spatial phenomena. All of the twenty-or-so solid modellers currently available in the U.S. support Boolean operations akin to set intersection, union and difference on solid objects. Boundary representations, i.e., face/edge/vertex structures, for solids defined through Boolean operations are generated in these modellers by using socalled boundary evaluation and merging procedures. These are the most complex and delicate software modules in a solid modeller. This paper describes boundary evaluation algorithms used by the PADL solid modelling systems developed at the University of Rochester, and discusses other known approaches in terms of the concepts of set membership classification and neighborhood manipulation, which emerged from the PADL work