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 1119.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