Edge Flip Algorithm and Intrinsic Delaunay Triangulations

Media

---

Description

---

Delaunay triangulations play an important role in the field of Digital Geometry Processing as they give rise to better numerical behavior of mesh manipulating algorithms. Having “well-formed” triangles, they facilitate geometry processing in applications like surface denoising, geometric modeling, surface parametrization. A triangulation is said to be Delaunay if the interior of the triangles’ circumcircles are empty. While the construction of such triangulations for domains in $\mathbb{R}^2$ is now standard textbook material, the picture for immersed surfaces in $\mathbb{R}^3$, which are given as simplicial 2-manifold meshes (possibly with boundary), is not nearly as clear. A classic way to convert a given planar triangulation into a Delaunay triangulation is to iteratively flip the non-Delaunay edges until no such edge remains. In the same vein, one can construct an intrinsic Delaunay triangulation (see Figure 4) of a simplicial surface in $\mathbb{R}^3$ by performing intrinsic edge flips (see Figure 8). In both cases every triangulation can be transformed into a Delaunay one with a finite number of edge flips.

Based on [1] we developed a python program that performs the intrinsic edge flip algorithm and visualizes the resulting intrinsic Delaunay triangulation in Blender. The relevant data read off from the input mesh are the combinatorics of its edge graph as well as the length of each edge. After flipping the intrinsic Delaunay triangulation is returned together with information about its the relationship to the original mesh. While an extrinsic flip would change the geometry of the surface, the procedure of flipping intrinsically does not change the shape of the original mesh at all (cf. Figure 8). This is important for geometry processing, where we want to use the original surface geometry but do numerical processing with the best triangulation. But regard that intrinsic edge flips may produce non-regular triangulations, which contain self-loops and or faces with only two edges (cf. Figure 3). Therefore, we use a halfedge data structure in order to handle the fact that the intrinsic Delaunay triangulation is not necessarily regular.

Our program covers a broader range of applications for establishing a Delaunay triangulation. Besides choosing whether to flip in extrinsic or intrinsic manner, one may hand over user defined functions for the evaluation of the Delaunay property and the calculation of the new edgelengths. Thus it might also be used in other geometries, for example a hyperbolic setting.

References

---

Authors

See also