Generation of surface meshes remains an active research problem despite the many publications addressing this topic. Acquiring a 3D model is a tedious and error-prone procedure. The process of simplifying highly detailed scanned models does not emphasize the quality of their elements, and results in meshes which usually cannot be used as-is. An intermediate step, known as remeshing, is required to correct the basic mesh geometry and connectivity. High-quality meshes are necessary for the engineering community, where the emphasis is on numerical accuracy, as well as for the computer graphics and modeling community. The latter focus on the tradeoff between the visual quality of the result and the rendering speed, achieved by reducing the number of elements.
The main issues, which must be treated by a good remeshing algorithm, are: element quality, sizing control, approximation accuracy, robustness and efficiency. One reason surface meshing is such a challenging problem is the fact that using the Euclidean metric to measure distances between points on the surface can generate large discrepancies between the original surface and the constructed mesh. We solve this problem by using geodesic distances on the surface. The ability to accurately and efficiently compute geodesic distances, and propagate them across the mesh, permits us to generate quality surface meshes, which closely approximate the input without resorting to costly parameterization techniques.