Optimal Mapping Computation And Mesh Generation

3D digital contents play important roles in scientific research, mechanical engi-neering, and entertainment. Digital geometric processing is a field that utilizes mathe-matical models and algorithms to analyze and manipulate geometric data. It is an inter-disciplinary research relating to computer graphics, applied mathematics, and engineer-ing. Typical geometric processing tasks include mesh acquisition, mesh reconstruction, mesh generation, shape analysis and understanding, mapping computation and geomet-ric modeling. Our research focuses on two topics:optimal mapping computation and optimal mesh generation. Optimal mapping computation is a fundamental task in com-puter graphics, and it is the key to many applications, e.g. mesh parameterizations, mesh deformation, mesh improvement, all-hex mesh generation. Optimal mesh generation is one of the bases of digital geometric processing. For example, anisotropic and all-hex meshes are in great need, because they can provide more accuracy than isotropic and tetrahedral meshes in some applications. Optimal mapping can be used to improve the result of mesh generation.In the thesis we design novel energy functions and optimization algorithms from the perspective of optimal theory and apply them to solve optimal mapping computation, anisotropic mesh generation, and PolyCube structure construction:A good mapping possesses nice properties:inversion-free and low-distortion and its computation need to be efficient. State-of-the-art methods cannot satisfy all re-quirements. By revisiting the well-known MIPS (Most-Isometric ParameterizationS) method, we introduce an advanced MIPS(AMIPS) method that inherits the local injec-tivity of MIPS, achieves as low as possible distortions compared to the state-of-the-art locally injective mapping techniques, and performs one to two orders of magnitude faster in computing a mesh-based mapping. The success of our method relies on two key components. The first one is an enhanced MIPS energy function that penalizes the maximal distortion significantly and distributes the distortion evenly over the do-main for both mesh-based and meshless mappings. The second is a use of the inexact block coordinate descent method in mesh-based mapping in a way that efficiently min-imizes the distortion with the capability not to be trapped early by the local minimum. We demonstrate the capability and superiority of our method in various applications including mesh parameterizations, deformation, and mesh improvement.AMIPS has some limitations:it cannot support many handles in mesh deforma-tion and is sensitive to initial mappings. We present a novel method to compute locally injective mappings with low distortion on simplicial meshes. Given an initial mapping with or without inverted simplices, our method first disassembles it into disjointed and inversion-free simplices by modifying the piecewise affine transformations defined on simplices, then minimizes the mapping distortion and the difference of the disjointed vertices with respect to the piecewise affine transformations. Due to the use of trans-formations as unknowns, our algorithm explicitly guarantees the local injectivity of the mapping via an unconstrained minimization. Compared with existing methods, our method is robust to initial mappings even with many inverted elements and handle con-straints. Our method is also capable of achieving bounded distortion mappings. We demonstrate the efficiency and robustness of our method on a variety of applications.Anisotropic meshes are very important in geometric modeling, physical simulation and mechanical engineering. We present a novel approach for high-quality anisotropic triangle mesh generation, called local convex triangulation(LCT). Given a 2D or surface domain equipped with Riemannian metrics, the anisotropic meshing is transformed into a functional approximation problem. We construct convex functions locally over the mesh to best match Riemannian metrics, and adapt vertex positions and mesh connec-tivity to minimize the interpolation error iteratively to achieve the desired anisotropy. We show that our method is a generalization of Optimal Delaunay Triangulation, and we develop a simple and efficient algorithm that works well for 2D and surface meshing. The superiority of our method in mesh quality and algorithmic efficiency in comparison to existing methods is demonstrated with a variety of models and Riemannian metrics.All-hex meshes possess nice numerical properties, such as a reduced number of elements and high approximation accuracy in physical simulation and mechanical engi-neering. We generate high-quality all-hex meshes based on PolyCubes which are good abstractions of closed shapes. A desired PolyCube construction method should (1) pro-vide a low-distortion map without foldover and degeneracy; (2) offer flexible control on singularity counts; (3) compute the result efficiently and automatically. We introduce a novel method that fulfills these requirements to compute PolyCubes for tetrahedral meshes. We regard the computation as mesh deformation that is driven by face nor-mal smoothing and axis-directional alignment under distortion control. The kernel size of our Gaussian smoothing is used to control the singularity count, and the level of alignment is adjusted automatically to resolve the turning point issue. We formulate the deformation as an optimization problem and propose a very efficient solver. We demonstrate the quality and speed of our method compared to state-of-the-art methods on a variety of models.