Conforming Weighted Delaunay Triangulations

Given a set of points together with a set of simplices we show how to compute weights associated with the points such that the weighted Delaunay triangulation of the point set contains the simplices, if possible. For a given triangulated surface, this process provides a tetrahedral mesh conforming to the triangulation, i.e. solves the problem of meshing the triangulated surface without inserting additional vertices. The restriction to weighted Delaunay triangulations ensures that the orthogonal dual mesh is embedded, facilitating common geometry processing tasks.

We show that the existence of a single simplex in a weighted Delaunay triangulation for given vertices amounts to a set of linear inequalities, one for each vertex. This means that the number of inequalities for a given triangle mesh is quadratic in the number of mesh elements, making the naive approach impractical. We devise an algorithm that incrementally selects a small subset of inequalities, repeatedly updating the weights, until the weighted Delaunay triangulation contains all constrained simplices or the problem becomes infeasible. Applying this algorithm to a range of triangle meshes commonly used graphics demonstrates that many of them admit a conforming weighted Delaunay triangulation, in contrast to conforming or constrained Delaunay that require additional vertices to split the input primitives.

Write-Up

The paper has been accepted for publication in ACM Transactions on Graphics (SIGAsia 2020). Here is a preprint.

Presentations

An early presentation has been given in a seminar at the University of Toronto (todo: make slides available)

Code

The current implementation includes a simple splitting heuristic to handle on infeasible constraints. It is based on floating point arithmetic and is not robust. It depends on Gurobi for solving the linear system, CGAL for computing the triangulations and geometric data structures, Eigen for computational linear algebra, and libigl for computing winding numbers.