Extended octtrees, in contrast to common octtrees, have an extended set of terminal nodes: besides the black and white nodes there are face, edge and vertex nodes. The extended octtree preserves many of the advantages of a common octtree; furthermore a polyhedral boundary representation can be converted into an extended octtree representation, and it is possible to reconstruct a polyhedral boundary representation from the extended octtree. However, the simplicity of Boolean shape operations of common octtrees is lost. At the lowest level a full polyhedral Boolean intersection algorithm is needed for certain cases of pairs of nodes. The problems involved in using extended octtrees for Boolean shape operations on polyhedra are analyzed to some depth. In addition, some simple and efficient algorithms are presented for use in taking the intersection of two objects represented by extended octtrees. (Copyright (c) 1987 by Faculty of Mathematics and Informatics, Delft, The Netherlands.)
展开▼
