○ Figure 19.3: Quadtree representation 19.3 Space subdivision 19.3. 1 Motivation and definitions Some of the motivations behind space subdivision methods include Exhaustive enumeration is memory intensive and typically has low accuracy Smaller memory requirements are possible, if adaptive subdivision is used Octree/quadtree representations lead to a recursive subdivision into 8 octants(or 4 qua rants)that can be represented as an 8-ary tree (or 4-ary tree) for which efficient algo- rithms are also known In an octree representation a solid region is represented by hierarchically decomposing a usually cubic volume of space into successively smaller cubes( 8 of them). Hierarchical division and cube orientation usually follows the spatial coordinate system. An example of quadtree, the two dimensional analogue, is shown Figure 19.3 This is a trivial example. The method can continue to many more levels for a much more complex model. Some tolerance for the minimum size block is required. In addition, this very concise representation would become very large if the coordinate system was changed; for example, rotated 45 degrees This method leads to a quick way to compute the area and other integral properties of a region. It is often used in data analysis in fields such as medical applications and sonar ging
1 2 3 4 empty 1 2 3 4 full partially full Figure 19.3: Quadtree representation. 19.3 Space subdivision 19.3.1 Motivation and definitions Some of the motivations behind space subdivision methods include: • Exhaustive enumeration is memory intensive and typically has low accuracy. • Smaller memory requirements are possible, if adaptive subdivision is used; • Octree/quadtree representations lead to a recursive subdivision into 8 octants (or 4 quadrants) that can be represented as an 8-ary tree (or 4-ary tree) for which efficient algorithms are also known. In an octree representation a solid region is represented by hierarchically decomposing a usually cubic volume of space into successively smaller cubes (8 of them). Hierarchical division and cube orientation usually follows the spatial coordinate system. An example of quadtree, the two dimensional analogue, is shown Figure 19.3. This is a trivial example. The method can continue to many more levels for a much more complex model. Some tolerance for the minimum size block is required. In addition, this very concise representation would become very large if the coordinate system was changed; for example, rotated 45 degrees. This method leads to a quick way to compute the area and other integral properties of a region. It is often used in data analysis in fields such as medical applications and sonar imaging. 6
19.3.2 Construction of octrees To create an octree, we apply a classification procedure to a given solid (represented using the Boundary Representation, Constructive Solid Geometry, or Exhaustive Enumeration methods etc. )and decide if a given node of the octree is Exterior to solid(white) Interior to solid(black); Partially interior to solid(grey) The classification procedure is used recursively. It is based on Boolean solid operations especially intersection. Figure 19.4 provides an simple example of octree representation In general, the decision if a given node of the octree is white, black, or grey is not an easy task. For the simple case of a convex solid object, it is sufficient to classify the eight vertices of the given node of the octree(which is a cube) with respect to the solid. Thi can be accomplished by for example casting a half-infinite ray from the point intersectin the solid's surfaces in a number of (multiplicity one) intersection points. If the number of such intersection points is even /odd, the point is outside/in(or on the surface of the solid) However, for a concave solid object, classification of the six faces of the cube with respect to the solid is necessary, see Figure 19.5 for an illustration in the 2-D case. This requires surface intersections with a planar patch. The memory and processing computation required for a 3-D bject is on the order of the surface area of the object [129. Depending on the object and the resolution, this can still represent a large storage requirement 19.3.3 Algorithms for octrees Various algorithms for octrees are developed in Meagher [12 and are summarized here 1. Tree generation or conversion from other representation methods were discussed above in Section 19.3.2 2. Set operators(union, intersection, difference): A low resolution tree could be an effective preprocessor for a B-rep model in processes like interference checking 3. Geometric transformations(translation, rotation, scaling) 4. Analysis procedures(integral, volume properties, connected components 5. Rendering [16 As an example we consider set or Boolean operations. Set operations lead to simple tree Intersection(Tree A, Tree B)= Tree C Trees are traversed in synchronous fashion and a case analysis for the types of nodes performed. We use the terms black"= in-solid, white"= out-of-solid. At each level of ubdivision there are three cases 11
19.3.2 Construction of octrees To create an octree, we apply a classification procedure to a given solid (represented using the Boundary Representation, Constructive Solid Geometry, or Exhaustive Enumeration methods, etc.) and decide if a given node of the octree is: • Exterior to solid (white); • Interior to solid (black); • Partially interior to solid (grey). The classification procedure is used recursively. It is based on Boolean solid operations, especially intersection. Figure 19.4 provides an simple example of octree representation. In general, the decision if a given node of the octree is white, black, or grey is not an easy task. For the simple case of a convex solid object, it is sufficient to classify the eight vertices of the given node of the octree (which is a cube) with respect to the solid. This can be accomplished by for example casting a half-infinite ray from the point intersecting the solid’s surfaces in a number of (multiplicity one) intersection points. If the number of such intersection points is even/odd, the point is outside/in (or on the surface of the solid). However, for a concave solid object, classification of the six faces of the cube with respect to the solid is necessary, see Figure 19.5 for an illustration in the 2-D case. This requires surface intersections with a planar patch. The memory and processing computation required for a 3-D object is on the order of the surface area of the object [12] [9]. Depending on the object and the resolution, this can still represent a large storage requirement. 19.3.3 Algorithms for octrees Various algorithms for octrees are developed in Meagher [12] and are summarized here: 1. Tree generation or conversion from other representation methods were discussed above in Section 19.3.2. 2. Set operators (union, intersection, difference): A low resolution tree could be an effective preprocessor for a B-rep model in processes like interference checking. 3. Geometric transformations (translation, rotation, scaling). 4. Analysis procedures (integral, volume properties, connected components). 5. Rendering [16]. As an example we consider set or Boolean operations. Set operations lead to simple tree traversal Intersection(Tree A, Tree B) = Tree C Trees are traversed in synchronous fashion and a case analysis for the types of nodes is performed. We use the terms “black”= in-solid,“white” = out-of-solid. At each level of subdivision there are three cases [11]: 7
( Figure 19.4: An octree model Figure 19.5: Classification of an quadtree node with respect to a concave object 8
Figure 19.4: An octree model. Figure 19.5: Classification of an quadtree node with respect to a concave object 8
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 9
1. 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 representation. • 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
19.3.5 Binary space subdivision Z y d·d● Figure 19.6: Binary subdivision tree Beyond octrees, an alternative type of tree representation involves dividing nodes into 2 ather than 8 components, see Mantyla [ll] and Figure 19.6. Subdivisions are performed in the X,Y, and Z coordinate directions sequentially. Binary trees are typically somewhat smaller than octrees and they can be converted to linear arrays containing special symbols 11
19.3.5 Binary space subdivision Figure 19.6: Binary subdivision tree. Beyond octrees, an alternative type of tree representation involves dividing nodes into 2 rather than 8 components, see M¨antyl¨a [11] and Figure 19.6. Subdivisions are performed in the X, Y, and Z coordinate directions sequentially. Binary trees are typically somewhat smaller than octrees and they can be converted to linear arrays containing special symbols [11]. 10