SELF-DELAUNAY MESHES FOR SURFACES

Abstract

In the Euclidean plane, a Delaunay triangulation can be characterized by the requirementthat the circumcircle of each triangle be empty of vertices of all other triangles. For triangulatinga surface S in R3, the Delaunay paradigm has typically been employed in the formof the restricted Delaunay triangulation, where the empty circumcircle property is definedby using the Euclidean metric in R3 to measure distances on the surface. More recently, theintrinsic (geodesic) metric of S has also been employed to define the Delaunay condition.In either case the resulting mesh M is known to approximate S with increasing accuracyas the density of the sample points increases. However, the use of the reference surface Sto define the Delaunay criterion is a serious limitation. In particular, in the absence of theoriginal reference surface, there is no way of verifying if a given mesh meets the criterion.We define a self-Delaunay mesh as a triangle mesh that is a Delaunay triangulation ofits vertex set with respect to the intrinsic metric of the mesh itself. This yields a discretesurface representation criterion that can be validated by the properties of the mesh alone,independent of any reference surface the mesh is supposed to represent. The intrinsic Delaunaytriangulation that characterizes self-Delaunay meshes makes them a natural domainfor discrete differential geometry, and the discrete exterior calculus in particular.We examine self-Delaunay meshes and their relationship with other Delaunay structuresfor surface representation. We study sampling conditions relevant to the intrinsic approach,and compare these with traditional sampling conditions which are based on extrinsic quantitiesand distances in the ambient Euclidean space. We also provide practical and provablycorrect algorithms for constructing self-Delaunay meshes. Of particular interest in thiscontext is the extrinsic edge flipping algorithm which extends the familiar algorithm forproducing planar Delaunay triangulations.