1. If nodes n1 and n2 are both leaves, then the resulting node n is black if n1 and n2 are both black; otherwise ns is white 2. Either nI or n2 is a leaf. If the leaf node is black, then the subtree of the non-leaf node is copied to the resultant octree; otherwise the resulting node is white 3. If nodes n and n, are non-leaves, then the algoritm considers recursively their children The complexity of such an intersection algorithm is proportional to the size of the smaller tree Not all algorithms are in the form of a simple tree traversal. Some algorithms may require at worst, a traversal up to the root and back down to a neighbor. Examples of such algorithms are urface rendering(shading), transparency rendering, and extraction of connected components 19.3. 4 Properties of octrees Some of the properties of octrees include: Expressive power: they are an approximation scheme and do not form a primary repre- sentation Validity: if no special connectivity is required, all octrees are valid Unambiguity and uniqueness: for a fixed resolution there is only one compacted- octree Memory requirements: not as large as exhaustive enumeration models, yet typically much larger than Boundary Representation and Constructive Solid Geometry models Closure of operations: for example for Boolean operations and transformations Computational ease: octrees are somewhat more complex than exhaustive enumeration Algorithms such as set operations can create octrees with unnecessary nodes(eg an internal nodes whose children are all black). Such nodes can be removed with a relatively simple tree traversal algorithm 91. If nodes n1 and n2 are both leaves, then the resulting node n3 is black if n1 and n2 are both black; otherwise n3 is white. 2. Either n1 or n2 is a leaf. If the leaf node is black, then the subtree of the non–leaf node is copied to the resultant octree; otherwise the resulting node is white. 3. If nodes n1 and n2 are non-leaves, then the algoritm considers recursively their children as above. The complexity of such an intersection algorithm is proportional to the size of the smaller tree. Not all algorithms are in the form of a simple tree traversal. Some algorithms may require at worst, a traversal up to the root and back down to a neighbor. Examples of such algorithms are surface rendering (shading), transparency rendering, and extraction of connected components. 19.3.4 Properties of octrees Some of the properties of octrees include: • Expressive power: they are an approximation scheme and do not form a primary repre￾sentation. • Validity: if no special connectivity is required, all octrees are valid. • Unambiguity and uniqueness: for a fixed resolution there is only one compacted2 octree; • Memory requirements: not as large as exhaustive enumeration models, yet typically much larger than Boundary Representation and Constructive Solid Geometry models; • Closure of operations: for example for Boolean operations and transformations; • Computational ease: octrees are somewhat more complex than exhaustive enumeration. 2Algorithms such as set operations can create octrees with unnecessary nodes (eg. an internal nodes whose children are all black). Such nodes can be removed with a relatively simple tree traversal algorithm. 9