Harmonic Triangulations

We introduce the notion of harmonic triangulations: a harmonic triangulation simultaneously minimizes the Dirichlet energy of all piecewise linear functions. By a famous result of Rippa, Delaunay triangulations are the harmonic triangulations of planar point sets. We prove by explicit counterexample that in 3D a harmonic triangulation does not exist in general. However, we show that bistellar flips are harmonic: if they decrease Dirichlet energy for one set of function values, they do so for all. This observation gives rise to the notion of locally harmonic triangulations. We demonstrate that locally harmonic triangulations can be efficiently computed, and efficiently reduce sliver tetrahedra. The notion of harmonic triangulation also gives rise to a scalar measure of the quality of a triangulation, which can be used to prioritize flips and optimize the position of vertices. Tetrahedral meshes generated by optimizing this function generally show better quality than Delaunay-based optimization techniques. 


An article on this work is appearing as:
Marc Alexa. 2019. Harmonic Triangulations. ACM Trans. Graph. 38, 4, Article 54 (July 2019) (Preprint)


Some of the ideas have been presented at the Workshop on Robust Geometric Algorithms for Computational Fabrication II at The Fields Institute for Research in Mathematical Sciences. The talk has been recorded and the talk sides are available (the pdf contains interactive 3D elements that may not show in all pdf viewers).


An implementation using CGAL to construct the Delaunay triangulation of a set of points in 3D and then applying harmonic flipping to create a locally harmonic triangulation is available here.