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 orientation. 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 possible. 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