  Intrinsic Delaunay triangulation (IDT) is a fundamental data structure in
computational geometry and computer graphics. However, except for some
theoretical results, such as existence and uniqueness, little progress has been
made towards computing IDT on simplicial surfaces. To date the only way for
constructing IDTs is the edge-flipping algorithm, which iteratively flips the
non-Delaunay edge to be locally Delaunay. Although the algorithm is
conceptually simple and guarantees to stop in finite steps, it has no known
time complexity. Moreover, the edge-flipping algorithm may produce non-regular
triangulations, which contain self-loops and/or faces with only two edges. In
this paper, we propose a new method for constructing IDT on manifold triangle
meshes. Based on the duality of geodesic Voronoi diagrams, our method can
guarantee the resultant IDTs are regular. Our method has a theoretical
worst-case time complexity $O(n^2\log n)$ for a mesh with $n$ vertices. We
observe that most real-world models are far from their Delaunay triangulations,
thus, the edge-flipping algorithm takes many iterations to fix the non-Delaunay
edges. In contrast, our method is non-iterative and insensitive to the number
of non-Delaunay edges. Empirically, it runs in linear time $O(n)$ on real-world
models.
