High-Quality And Controllable Quadrangulation Methods

Quad mesh is of great interest due to its bilinear nature and superior performance in many graphics and scientific computing applications, such as finite element analysis, parameterization, texture atlas and B-spline fitting. However, it is very challenging to remesh a surface into a provably high quality quad mesh. The first challenge is there are very diverse requirements in quadrangu-lation, such as shape, the orientation and the size of the quads, the alignment of features, and the regularity of the mesh in term of singularity points. All these requirements are connected, affected and even conflicted with each other. The algorithm needs to take all these issues into account glob-ally, optimize them automatically and try to find the most satisfying result. The second challenge is that the quality of quad mesh mainly depends on its topology. Users always prefer pure quad meshes, the singularity points need to be distributed reasonably and the base mesh must be as sim-ple as possible. Thus the algorithm has to optimize the topology globally under the constraints of all the above requirements.However, existing quadrangulation methods always contain some limitations. They lack con-trollability, or require extra user interaction, or depend on vector field excessively such that the mesh topology is hard to be optimized. Consequently it is necessary to devise new techniques for quadrangulation. This dissertation mainly focuses on generating high quality quad meshes under diverse requirements, the major contributes are as follows:1. A new spectral quadrangulation method with orientation and alignment control is proposed. This method is an extension of the spectral surface quadrangulation approach where the coarse quad structure is derived from the Morse-Smale complex of an eigenfunction to the Laplace operator on the input mesh. In contrast to the original scheme, we provide flexible explicit control of the shape, size, orientation and feature alignment of the quad faces. We achieve this by proper selection of the optimal eigenvalue (shape), by adaption of the area term in the Laplace operator (size), and by adding special constraints to the Laplace eigen- problem (quad orientation and the alignment of patch boundaries). By solving a generalized eigenproblem we can generate scalar fields on the mesh whose Morse-Smale complex is of high quality and satisfies all the user requirements. The final quad mesh is generated from the Morse-Smale complex by computing a globally smooth parametrization.2. A new technique for remeshing a surface into anisotropically sized quads is presented. The basic idea is to construct a special standing wave on the surface to generate the global quadri-lateral structure. This wave based quadrangulation method is capable of controlling the quad size in two directions and precisely aligning the quads with feature lines. Similar to the previ-ous methods, we augment the input surface with a vector field to guide the quad orientation. The anisotropic size control is achieved by using two size fields on the surface. In order to reduce singularity points, the size fields are optimized by a new curl minimization method. The experimental results show that the proposed method can successfully handle various quadrangulation requirements and complex shapes.3. A new divide-and-conquer quadrangulation technique is proposed. Given a model repre-sented in triangular mesh, we first segment it into a set of sub-meshes, and compare them with some pre-defined quad mesh templates. For the sub-meshes that are similar to a pre-defined template, we remesh them as the template up to a number of subdivisions. For the others, we adopt the wave-based quadrangulation technique to remesh them with extensions to preserve symmetric structure. To ensure that the individually remeshed sub-meshes can be seamlessly stitched together, we formulate a mixed-integer optimization problem and design a heuristic solver to optimize it. Since the sub meshes can be remeshed individually in any order, the re-meshing procedure can run in parallel. Experimental results showed that the proposed method can preserve the high-level structures, and process large complex surfaces robustly and efficiently.