Domain Delaunay tetrahedrization of curved polyhedra defined in a solid modeling system
Nickolas S. Sapidis · 1993
Automatic discretization of three-dimensional objects is a prerequisite for automating engineering analysis applications in a solid modeling environment. This thesis introduces the 'Domain Delaunay Tetrahedrization' (DDT), a topologically valid definition for a tetradedral approximation of a solid model. This definition establishes a one-to-one correspondence between the elements of the solid's boundary, and the edges and triangulation son the tetrahedrization's boundary. DDT can be applied to arbitrarily shaped curved solids, including objects with holes and certain cases of nonmanifolds. The principal tools used in the construction of a DDT are (1) a boundary representation of the given solid that includes neighborhood information, (2) properties of the standard Delaunay triangulation, and (3) a mechanism for transferring neighborhood information from the solid model to the elements of the tetrahedral model. Construction of a DDT requires solving two problems: (A) Distributing nodes (points) on the boundary of the given solid, so that the corresponding standard Delaunay tetrahedrization (DT) includes as a subset a DDT of the solid, and (B) extracting the DDT from the DT of the node set. Problem (A) is solved by means of refinement operations that insert new nodes on the boundary of the solid on the basis of necessary and sufficient conditions for the existence of a DDT. These refinement operations make extensive use of several properties of the DT, proved in this thesis, that predict local modification of the DT due to node insertion. Problem (B) is expressed as a simplex/triangulation classification problem, and is solved by transferring neighborhood information from the solid's faces to the DT's triangular faces. Simplex/triangulation classification is also used for ensuring that the faces of the solid are approximated satisfactorily by the elements of the DDT. This thesis also addresses certain variations of the domain tetrahedrization problem and focuses on integrating DDT with recursive spatial decomposition (RSD), where the given solid is replaced with a collection of variably-sized cells. In this case, tetrahedrizing the initial solid is accomplished by tetrahedrizing each RSD cell, provided that neighboring cells correspond to tetrahedrizations that are compatible along common cell faces. A modified DDT algorithm is introduced that fulfills the above requirement. (Abstract shortened by UMI.)