Generation And Properties Of High-Quality Triangular Mesh

In modern computer graphics application and research fields, triangular mesh achieves the following advantages:high degrees of freedom and accuracy when approximating the continues surface, simple data structure and the rapid rendering procedure, thus has already been extensively used in many branch domains including digital geometry processing, ren-dering and geometric modeling. Basically all these works aim at proposing respectively different definitions of high-quality triangular mesh based on different application and re-search purposes, and investigating corresponding generation algorithms. Since the data structure of triangular mesh is divided into two parts:the geometry coordinates of mesh vertices and the triangle topology connectivities between vertices, the algorithms for gen-erating high-quality triangular mesh could be categorized into three classes, namely given geometry of vertices to find the optimal topology, given topology of vertices to compute their optimal geometry positions and modify the geometry and topology of input mesh simultaneously to generate mesh with higher quality. In this paper, we focus on the defini-tion of high-quality triangular mesh and discuss the above three different types of triangular meshes. We investigate both the theoretical properties and the actual applications of high-quality triangular meshes and also present corresponding generation methods so as to solve the Delaunay triangulation problem in computational geometry field, the mesh deforma-tion problem in digital geometry processing field and the blue noise sampling problem in sampling research domain. The contributions of our work are summarized as follows:1. Investigate the theoretical characteristics of Delaunay triangulation-the high-quality triangular mesh in planar case that has optimal topology structure under the given geometry positions of vertices. We characterize the influence of an edge flip oper-ation to the geometric Laplacian of triangulation and reprove a classic theorem in computational geometry field with simpler form. Applying this theorem, we further characterize the spectral properties of Delaunay triangulation and provide a simpler proof of another well-known theorem about Delaunay triangulation.2. Investigate the optimal geometry positions of mesh vertices when applying the high-quality triangular mesh of given topology structure to planar mesh deformation prob-lem. We define the high-quality triangular mesh in this application as a valid triangu-lation, namely the mapping between the initial mesh and the deformed mesh which is embedded inside some target boundary shape should be one-to-one mapping. We analyze the geometric meaning of one-to-one mapping in this problem and propose an iterative embedding algorithm to alternatively update the geometry positions of vertices and corresponding geometric Laplacian until converges. We prove that our algorithm will always converge to a valid embedding if it exists, otherwise the al-gorithm could not converge. Furthermore, we present a post-processing routine to "fatten" those skinny triangles that exist inside the embedding in order to improve the quality of generated triangulation.3. Propose a high-quality triangular remeshing technique that simultaneously modify the geometry and topology so as to solve the blue noise sampling problem in pla-nar case. In this application, the high-quality triangular mesh is defined as capacity-constrained Delaunay triangulation, whose triangle areas are as uniform as possible and the topology keeps as Delaunay triangular connectivity. We present an itera-tive generating algorithm which alternatively optimizes the geometry positions of vertices and the corresponding Delaunay triangulation topology until converges to some stable status. We apply spectral analysis to show that the vertex distribution of capacity-constrained Delaunay triangulation possess superior blue noise characteris-tics, and the efficiency of the generating algorithm achieves an order of magnitude faster than the best competitor. We also generalize our algorithm to arbitrary den-sity function defined inside the sampling domain to generate non-uniform blue noise sampling pattern which could be applied to image halftone problem. 4. We generalize the concept of capacity-constrained Delaunay triangulation to sur-face meshes in three-dimensional space so as to solve the blue noise sampling prob-lem on manifold surface. The high-quality triangular mesh in this case is defined as capacity-constrained surface triangulation, which keeps the uniformity of trian-gle areas while also keeping the topology structure as some well-shaped "Delaunay" triangulation on surface. We follow the idea in planar case to iteratively optimize the geometry positions of vertices and the topology structure on surface. The differ-ential analysis on surface shows that the mesh vertex distribution generated by our algorithm provides typical blue noise characteristics. Our algorithm is the first blue noise sampling algorithm on surface that allows precise control over the number of sampling points, and the algorithm is competitive compared with other methods. We also introduce density function into objective energy of the iterations such that our algorithm could generate non-uniform blue noise sampling pattern on surface, such as curvature-aware samples.