Hodge-optimized triangulations - Archive ouverte HAL Access content directly
Journal Articles ACM Transactions on Graphics Year : 2011

Hodge-optimized triangulations

Patrick Mullen
  • Function : Author
Fernando de Goes
  • Function : Author
Mathieu Desbrun


We introduce Hodge-optimized triangulations (HOT), a family of well-shaped primal-dual pairs of complexes designed for fast and accurate computations in computer graphics. Previous work most commonly employs barycentric or circumcentric duals: while barycentric duals guarantee that the dual of each simplex lies within the simplex, circumcentric duals are often preferred due to the induced orthogonality between primal and dual complexes. We instead promote the use of weighted duals (power diagrams). They allow much greater flexibility in the location of dual vertices while keeping primal-dual orthogonality, thus providing an invaluable extension to the usual choices of dual by only adding one additional scalar per primal vertex. Furthermore, we introduce a family of functionals on pairs of complexes that we derive from bounds on the errors induced by diagonal Hodge stars, commonly used in discrete computations. The minimizers of these functionals, called HOT meshes, are shown to be generalizations of Centroidal Voronoi Tesselations and Optimal Delaunay Triangulations, and to provide increased accuracy and flexibility for a variety of computational purposes.
Not file

Dates and versions

hal-02286600 , version 1 (13-09-2019)


  • HAL Id : hal-02286600 , version 1


Patrick Mullen, Pooran Memari, Fernando de Goes, Mathieu Desbrun. Hodge-optimized triangulations. ACM Transactions on Graphics, 2011, 30 (4), pp.103,1-12. ⟨hal-02286600⟩
24 View
0 Download


Gmail Facebook Twitter LinkedIn More