Uniform and adaptive (re)meshing of surfaces

Triangle meshes are frequently used for computer representations of surfaces, with applications in computer graphics, visualization, and finite element analysis. Many geometry processing operations require meshes with high-quality triangles as input, but tend to degrade the quality of the output. This drives the need for remeshing algorithms, which take a poor mesh as input, and improve the sizes and shapes of the triangles while keeping the geometry the same. While a wide variety of geometry processing operations operate only on meshes, many surfaces are acquired with different underlying representations. For example, isosurfaces are often acquired from CT and MRI scans, and point set surfaces are acquired from laser range scans. This drives the need for generating meshes from other surface representations. This dissertation presents novel methods for meshing and remeshing surfaces in both uniform and adaptive ways. A novel parameterization-based method for generating highly-uniform remeshes is presented. This method considers the fully general problem of creating a map between two arbitrary triangle meshes. Whereas previous approaches compose parameterizations over a simpler intermediate domain, the presented method directly creates and optimizes a continuous map between the meshes. The distortion of the map is measured with a new symmetric metric, and is minimized during interleaved coarse-to-fine refinement of both meshes. By explicitly favoring low intersurface distortion, maps are obtained that naturally align corresponding shape elements. Typically, the user need only specify a handful of feature correspondences for initial registration, and even these constraints can be removed during optimization. The method robustly satisfies hard constraints if desired. This general intersurface mapping framework can be applied to parameterize surfaces onto simplicial domains, such as coarse meshes, and octahedral and toroidal domains. These parameterizations can be used to create high-quality remeshes. This dissertation also presents a novel surface meshing algorithm that is closely related to surface reconstruction techniques, and requires no explicit parameterization. This approach is based on the advancing front paradigm, augmented with a guidance field to both adapt the triangle sizes to the surface curvature and bound rate at which they can change. Simple and intuitive user controls are given for the size and adaptivity of the triangles. The method can be used to mesh surfaces with a wide variety of underlying definitions, including isosurfaces, point set surfaces, as well as other meshes. It is accurate, fast, robust, and suitable for use with interactive mesh processing applications that require local remeshing. A number of applications are shown, including Boolean operations between surfaces with different underlying definitions, extraction of large out-of-core isosurfaces that do not fit in working memory, and reconstruction of point set surfaces with sharp features.