Thesis (Ph. D.)--University of Texas at Austin, 2001. / Vita. Includes bibliographical references (leaves 156-171). Available also in a digital version from Dissertation Abstracts.

Includes bibliographical references (p. 95-104).

Discrete representation of a surface, especially the triangle mesh, is ubiquitous in numerical simulation and computer graphics. Compared with isotropic triangle meshes, anisotropic triangle meshes provide more accurate results in numerical simulation by capturing anisotropic features more faithfully. Furthermore, emerging applications in computer graphics and geometric modeling require reliable differential geometry information estimated on these anisotropic meshes. The first part of this thesis proposes a special type of anisotropic meshes, called shape-preserving meshes, provides guaranteed convergence of discrete differential operators on these meshes and devises an algorithm for generating shape-preserving meshes on free-form surfaces based on the mesh optimization framework with centroidal Voronoi tessellation (CVT). To improve the numerical stability in simulation, we discuss how to reduce the number of obtuse triangles in the mesh. The second part of the thesis discusses the non-uniqueness of anisotropic meshes to represent the same anisotropy defined on a domain, shows that of all anisotropic meshes, there exists one instance minimizing the number of obtuse triangles, and proposes a variational approach to suppressing obtuse triangles in anisotropic meshes by introducing a Minkowski metric in the CVT framework. On a complex shape, its topological information is also highly useful to guide the mesh generation. To extract topology properties, the Morse-Smale complex (MSC) is a classical tool and widely used in computer graphics. However, on a manifold with boundary, its MSC is not well defined. The final part of this thesis generalizes the MSC to manifolds with boundaries. Based on this generalized MSC (GMSC), an operator to merge n GMSCs of manifolds partitioning a large manifold is proposed. The merging operator is used in a divide-and-conquer approach on a massive data set, providing the potential to employ the computational power in a parallel manner. / published_or_final_version / Computer Science / Doctoral / Doctor of Philosophy

The medial axis is an important shape representation and the computation of the medial axis is a fundamental research problem in computer graphics. Practically, the medial axis is widely used in various aspects of computer graphics, such as shape analysis, image segmentation, skeleton extraction and mesh generation and so forth. However, the applications of the medial axis have been limited by its sensitivity to boundary perturbations. This characteristic may lead to a number of noise branches and increase the complexity of the medial axis. To solve the sensitivity problem, it is critical to simplify the medial axis. This thesis first investigates the algorithms for computing medial axes of different input shapes. Several algorithms for the filtration of medial axes are then reviewed, such as the local importance measurement algorithms, boundary smoothness algorithms, and the global algorithms. Two novel algorithms for the simplification of the medial axis are proposed to generate a stable and simplified medial axis as well as its reconstructed boundary. The developed Global Geodesic Slope(GGS) algorithm for the medial axis simplification is based on the global geodesic slope defined in this thesis, which combines the advantages of the global and the local algorithms. The GGS algorithm prunes the medial axis according to local features as well as the relative size of the shape. It is less sensitive to boundary noises than the local algorithms, and can maintain the features of the shape in highly concave regions while the global algorithms may not. The other simplification algorithm we propose is the Accumulated Hyperbolic Distance(AHD) algorithm. It directly uses the evaluation criterion of the error, accumulated hyperbolic distance defined in this thesis, as the pruning measurement in the filtration process. It guarantees the upper bound of the error between the reconstructed shape and the original one within the defined threshold. The AHD algorithm avoids sudden changes of the reconstructed shape as the defined threshold changes. / published_or_final_version / Computer Science / Master / Master of Philosophy

Computer graphics applications call for various mesh generation techniques to visualize objects, store shape data, perform numerical analyses, etc. Mesh generation is also a fundamental research topic in many other engineering areas related to physical models described by partial differential equations. The reason that meshed surfaces are preferred over spline surfaces in many engineering applications is its flexibility in handling complex objects, while sharp features and boundaries can be represented without trimming, which is highly desired in numerical simulations. In this thesis, we study two methods for generating meshes with sharp features. Sharp features, such as creases and corners, are very common in mechanical objects. Hence effectively handling sharp features is of great importance to this kind of objects. The first method is to generate triangular subdivision surfaces with sharp features. Although there have been various methods to fit subdivision surfaces to different types of shape data, e.g., dense meshes and point clouds, none of these methods can handle sharp features effectively. We present a new exact evaluation scheme for all types of sharp features in Loop subdivision, and integrate the new evaluation scheme into the optimization framework to fit Loop subdivision surfaces to dense meshes. The second method is to generate quadrilateral meshes with varying element sizes which observe the user requirement. This method is inspired by the idea of spectral quadrangulation, but existing spectral quadrangulation methods are limited to closed surfaces due to its lack of proper boundary treatment. We present a new set of boundary conditions, and introduce the Quasi-Eigenfunction to assist the mesh generation process. The proposed boundary treatment is further applied to sharp features to handle mechanical objects. The quasi-eigenfunction based quadrangulation framework is also extended to 3D volumetric domain to generate hexahedral meshes. Experimental results and comparisons with existing methods are presented in each chapter to demonstrate the effectiveness of the proposed methods. / published_or_final_version / Computer Science / Doctoral / Doctor of Philosophy

Shape representation is a fundamental topic in geometric modeling, which is ubiquitous in computer graphics. Compared with the explicit and implicit shape representations, the medial representation possesses many advantages. It provides a comprehensive understanding of the shapes, since it gives direct access to both the boundaries and the interiors of the shapes. Although there are many medial axis computation algorithms which are able to filter noises in the medial axis, introduced by the perturbations on the boundary, and generate stable medial axis transforms of the input shapes, the medial axis transforms are usually represented in a redundant way with numerous primitives, which brings down the flexibility of the medial axis transform and hinders the popularity of the medial axis transform in geometric applications. In this thesis, we propose compact representations of the medial axis transforms for 2D and 3D shapes. The first part of this thesis proposes a full pipeline for computing the medial axis transform of an arbitrary 2D shape. The instability of the medial axis transform is overcome by a pruning algorithm guided by a user-defined Hausdorff distance threshold. The stable medial axis transform is then approximated by spline curves in the 3D space to produce a smooth and compact representation. These spline curves are computed by minimizing the approximation error between the input shape and the shape represented by the medial axis transform. The second part of this thesis discusses improvements on the existing medial axis computation algorithms, and represent the medial axis transform of a 3D shape in a compact way. The CVT remeshing framework is applied on an initial medial axis transform to promote the mesh quality of the medial axis. The simplified medial axis transform is then optimized by minimizing the approximation error of the shape reconstructed from the medial axis transform to the original 3D shape. Our results on various 2D and 3D shapes suggest that our method is practical and effective, and yields faithful and compact representations of medial axis transforms of 2D and 3D shapes. / published_or_final_version / Computer Science / Doctoral / Doctor of Philosophy

Not available / text

published_or_final_version / abstract / Computer Science / Doctoral / Doctor of Philosophy

published_or_final_version / abstract / toc / Computer Science and Information Systems / Doctoral / Doctor of Philosophy

published_or_final_version / Computer Science / Master / Master of Philosophy