Given a set of points together with a set of simplices we show how tocompute weights associated with the points such that the weighted Delaunaytriangulation of the point set contains the simplices, if possible. For a giventriangulated surface, this process provides a tetrahedral mesh conformingto the triangulation, i.e. solves the problem of meshing the triangulatedsurface without inserting additional vertices. The restriction to weightedDelaunay 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 Delaunaytriangulation for given vertices amounts to a set of linear inequalities, onefor each vertex. This means that the number of inequalities for a giventriangle mesh is quadratic in the number of mesh elements, making the naiveapproach impractical. We devise an algorithm that incrementally selectsa small subset of inequalities, repeatedly updating the weights, until theweighted Delaunay triangulation contains all constrained simplices or theproblem becomes infeasible. Applying this algorithm to a range of trianglemeshes commonly used graphics demonstrates that many of them admita conforming weighted Delaunay triangulation, in contrast to conformingor constrained Delaunay that require additional vertices to split the inputprimitives.
展开▼
