O(N) HIGH QUALITY REMESHING OF SURFACE MESHES

Abstract

Generating high quality surface meshes is necessary as a prerequisite for many differentnumerical tasks. Given an input point cloud of a surface, several implementations exist in software and literature for initial triangulations on the surface. Problems arise, however, when these surface meshes are not of sufficient quality, often leading to problems with stability and floating point errors for numerical methods. Concretely, we observe that this is often the case for Boundary Element Methods. In this thesis, I propose and implement an algorithm for the remeshing of closed, genus 0 surface meshes using parameterization based on the discrete Laplace Beltrami operator. I generate boundary conditions using a cut by adding new points on the surface mesh according to the gradient of one of the parameters, and then generating the following parameter accordingly. After applying appropriate non-linear functions on the parameters such that they become analogous to spherical coordinates on a unit sphere, we can obtain an interpolated point cloud which approximates the underlying surface. The resulting point cloud can then be triangulated to obtain a mesh of higher quality. I describe and detail the use and development of a parallel sparse matrix solver, which mitigates one of the bottle necks of the algorithm, and then conclude by 1) detailing mesh quality improvement on several example meshes to demonstrate the effectiveness of the algorithm, and 2) detailing efficiency of the algorithm and describing future directions.