Shape Operation: an Algorithm for Binary Combining Boundary Model Solids

The attractiveness of shape operators to end-users of geometric modelling systems stems from their intuitive clarity. Their implementation, however, is one of the most difficult algorithms in computational geometry. This complexity is further increased by the special properties of surfaces, such as orientation, that places the algorithm in the domain of manifold theory more than of set theory. A theoretical base for applying the set-theoretic operators of union, intersection and difference to spatial domains is presented, along with an algorithm that is successful in negotiating these complexities and all their special cases (in particular the presence of coincidental surfaces). The general principles of representing solids through their bounding surfaces and topics in manifold theory and boolean algebra relevant to understanding the algorithm are also discussed. The algorithm has been successfully implemented in three different geometric modelling systems over a period of four years. Some example of its application are include