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. 

Write-up

ACM DL Authorize serviceMarc Alexa. Harmonic triangulations ACM Transactions on Graphics (TOG), 38, 4, Article 54, July 2019

Presentation

The paper has been presented in the Technical Papers Program of SIGGRAPH 2019. Here are the talk sides.

Some of the ideas have been presented in more detail 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 talks are in pdf format and contain interactive 3D elements that may not show in all pdf viewers. Adobe Acrobat should work on all platforms.

Code

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.