《Computational Geometry》lecnotes 19 Prof. N.m. Patrikalakis

13472J/1.128J/2158J/16940J COMPUTATIONAL GEOMETRY Lecture 19 Prof. N.m. Patrikalakis Copyright 2003 Massachusetts Institute of Technology Contents Decomposition models 19.2 Exhaustive enumeration 19.2.1 Definition and construction methods 19. 2.2 Applications 19.2.3 Properties of exhaustive enumeration methods 19.3 Space subdivision 19.3.1 Motivation and definitions 2233356677 19.3.2 Construction of octrees 19.3.3 Algorithms for octrees 19.3.4 Properties of octrees 19.3.5 Binary space subdivision 19.4 Cell decompositions 11 19.4.1 Motivation 11 19.4.2 Cell tuple data structure 19.4.3 Properties of cell decompositions Integral properties of geometric models 14 19.5 Introduction 19.6 Integral properties of curves 19.6.1 Planar curves 4556 19.6.2 3D curves 19.7 Integral properties of surface patches 17 19.7.1 Planar regions 19.7.2 Curved surface patch 19.8 Solids 19.9 Example: solid of revolution 19.10Appendix: Review of numerical integration methods 19. 10.1 Trapezoidal rule of integratio 19.10.2 Simpson's rule of integration 19 10.3 Romberg integration 19.10.4 Double integrals Bibliography

13.472J/1.128J/2.158J/16.940J COMPUTATIONAL GEOMETRY Lecture 19 Prof. N. M. Patrikalakis Copyright c 2003 Massachusetts Institute of Technology Contents Decomposition models 2 19.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 19.2 Exhaustive enumeration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 19.2.1 Definition and construction methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 19.2.2 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 19.2.3 Properties of exhaustive enumeration methods . . . . . . . . . . . . . . . . . . . . . . . 5 19.3 Space subdivision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 19.3.1 Motivation and definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 19.3.2 Construction of octrees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 19.3.3 Algorithms for octrees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 19.3.4 Properties of octrees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 19.3.5 Binary space subdivision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 19.4 Cell decompositions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 19.4.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 19.4.2 Cell tuple data structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 19.4.3 Properties of cell decompositions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 Integral properties of geometric models 14 19.5 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 19.6 Integral properties of curves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 19.6.1 Planar curves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 19.6.2 3D curves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 19.7 Integral properties of surface patches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 19.7.1 Planar regions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 19.7.2 Curved surface patch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 19.8 Solids . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 19.9 Example: solid of revolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 19.10Appendix: Review of numerical integration methods . . . . . . . . . . . . . . . . . . . . . 25 19.10.1 Trapezoidal rule of integration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 19.10.2 Simpson’s rule of integration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 19.10.3 Romberg integration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 19.10.4 Double integrals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 Bibliography 31 1

Decomposition models 19.1 Introduction Decomposition models are representations of solids via combinations(unions) of basic special building blocks glued together. Alternatively, decomposition models may be considered te represent solids in terms of a subdivision of space(see also Lecture 1 for more details on the classification of these models). Various types of decomposition models are created by various building blocks various combination methods used to create the model In order of increasing complexity, decomposition models are classified as follows 1. Exhaustive enumeration 2. Space subdivision 3. Cell decomposition

Decomposition models 19.1 Introduction Decomposition models are representations of solids via combinations (unions) of basic special building blocks glued together. Alternatively, decomposition models may be considered to represent solids in terms of a subdivision of space (see also Lecture 1 for more details on the classification of these models). Various types of decomposition models are created by: • various building blocks • various combination methods used to create the model. In order of increasing complexity, decomposition models are classified as follows: 1. Exhaustive enumeration 2. Space subdivision 3. Cell decomposition 2

19.2 Exhaustive enumeration 19.2.1 Definition and construction methods Exhaustive enumeration is a representation by means of nonoverlapping cubes of uniform size and orientation, see Figure 19.1. An object is represented by a three dimensional boolean array Each cell represents a cubic volume of space. If a cell intersects with the region of interest it has a true value. Otherwise, the value is false. This can be pictured as a box divided into 3D cubical pixels, with 0 assigned if empty and 1 assigned if full. This representation involves lar subdivision of 3D space within a cube of given size which is partitioned and oriented in a certain way within a global coordinate system. The subdivision is made up of sub-cubes (3D pixels)of given size. Reference and access to each sub-cube is made by three integer indices i, 3, h For fixed space of interest we need a 3-D array, Cik of binary data if the sub-cube i, j, k intersects the solid if the sub-cube i,j, k is empty 19.1) Construction of exhaustive enumeration models requires an alternate representation or measurements(eg. digital tomograghy, medical scanning, sonar data, acoustic tomography data,etc). Usually the primary data type for such construction is a B-Rep or a CSg model or another exhaustive enumeration model at different resolution and cube location and orien- tation Operations on exhaustive enumeration models are easy. Boolean operations for example (especially for models within the same cube at the same resolution) are direct. Similarly visualization and integral computations are very easy. However, for higher quality rendering filtering methods to estimate accurate surface normals may be involved 16 The binary matrix(19. 1)typically represents a valid solid. However disconnected cells or cells with low degree of connectivity as in Figure 19.2 are undesirable. For the results of Boolean operations, filtering may be needed to maintain connectivity of cells. Strict connectivity occurs when each full cell has at least one full neighbor across a face 19.2.2 Applications Applications of exhaustive enumeration methods include Underwater environment representation Finite element meshing(first step in an algorithm to build such a mesh) Medical 3D data representation Preprocessing representation for speeding up operations on other representations(eg approximating integral properties such as volume, center of gravity, moments of inertia

19.2 Exhaustive enumeration 19.2.1 Definition and construction methods Exhaustive enumeration is a representation by means of nonoverlapping cubes of uniform size and orientation, see Figure 19.1. An object is represented by a three dimensional Boolean array. Each cell represents a cubic volume of space. If a cell intersects with the region of interest it has a true value. Otherwise, the value is false. This can be pictured as a box divided into 3D cubical pixels, with 0 assigned if empty and 1 assigned if full. This representation involves: • A regular subdivision of 3D space within a cube of given size which is partitioned and oriented in a certain way within a global coordinate system. The subdivision is made up of sub-cubes (3D pixels) of given size. Reference and access to each sub-cube is made by three integer indices i, j, k. • For fixed space of interest we need a 3-D array, Cijk of binary data: Cijk = ( 1 if the sub-cube i, j, k intersects the solid 0 if the sub-cube i, j, k is empty (19.1) Construction of exhaustive enumeration models requires an alternate representation or measurements (eg. digital tomograghy, medical scanning, sonar data, acoustic tomography data, etc). Usually the primary data type for such construction is a B-Rep or a CSG model or another exhaustive enumeration model at different resolution, and cube location and orien￾tation. Operations on exhaustive enumeration models are easy. Boolean operations for example (especially for models within the same cube at the same resolution) are direct. Similarly visualization and integral computations are very easy. However, for higher quality rendering, filtering methods to estimate accurate surface normals may be involved [16]. The binary matrix (19.1) typically represents a valid solid. However disconnected cells or cells with low degree of connectivity as in Figure 19.2 are undesirable. For the results of Boolean operations, filtering may be needed to maintain connectivity of cells. Strict connectivity occurs when each full cell has at least one full neighbor across a face. 19.2.2 Applications Applications of exhaustive enumeration methods include: • Underwater environment representation. • Finite element meshing (first step in an algorithm to build such a mesh). • Medical 3D data representation. • Preprocessing representation for speeding up operations on other representations (eg. approximating integral properties such as volume, center of gravity, moments of inertia). 3

Figure 19. 1: Exhaustive enumeration B 上- Figure 19.2: Various connectivities of cells in exhaustive enumeration models

Figure 19.1: Exhaustive enumeration. Figure 19.2: Various connectivities of cells in exhaustive enumeration models 4

19.2.3 Properties of exhaustive enumeration methods Properties of exhaustive enumeration methods include Expressive power: these methods are an approximation scheme and do not form a primary representation, especially within CAD/CAM applications Unambiguity and uniqueness for fixed space(size, location and orientation of primary cube)and resolution. There do not exist different representations for the same object under these conditions(which is not true of many other representation methods such as B-rep or CSG described before) Memory intensive: eg. for a linear resolution of 256, 256 integer elements for Ciik in equation 19.1 leading to 16M bits and this is a bare minimum. Closure of operations(eg. Booleans) Computational ease for algorithms: VLSI implementation for volume rendering is possi- ble. However, for high resolution the algorithm slows down Closure means that an operation such as Boolean results in an object that can be represented by the same type of data structure

19.2.3 Properties of exhaustive enumeration methods Properties of exhaustive enumeration methods include: • Expressive power: these methods are an approximation scheme and do not form a primary representation, especially within CAD/CAM applications. • Unambiguity and uniqueness for fixed space (size, location and orientation of primary cube) and resolution. There do not exist different representations for the same object under these conditions (which is not true of many other representation methods such as B-rep or CSG described before). • Memory intensive: eg. for a linear resolution of 256, 2563 integer elements for Cijk in equation 19.1 leading to 16M bits and this is a bare minimum. • Closure 1 of operations (eg. Booleans). • Computational ease for algorithms: VLSI implementation for volume rendering is possi￾ble. However, for high resolution the algorithm slows down. 1Closure means that an operation such as Boolean results in an object that can be represented by the same type of data structure. 5

○ 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 quad￾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 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 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

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