Optimal Voronoi Tessellations with Hessian-based Anisotropy

Abstract : This paper presents a variational method to generate cell complexes with local anisotropy conforming to the Hessian of any given convex function and for any given local mesh density. Our formulation builds upon approximation theory to offer an anisotropic extension of Centroidal Voronoi Tessellations which can be seen as a dual form of Optimal Delaunay Triangulation. We thus refer to the resulting anisotropic polytopal meshes as Optimal Voronoi Tessel-lations. Our approach sharply contrasts with previous anisotropic versions of Voronoi diagrams as it employs first-type Bregman diagrams , a generalization of power diagrams where sites are augmented with not only a scalar-valued weight but also a vector-valued shift. As such, our OVT meshes contain only convex cells with straight edges, and admit an embedded dual triangulation that is combinatorially-regular. We show the effectiveness of our technique using off-the-shelf computational geometry libraries.
Keywords : anisotropic Voronoi
Type de document :
Article dans une revue
ACM Transactions on Graphics, Association for Computing Machinery, 2016, Proceedings of SIGGRAPH Asia, pp.12
Liste complète des métadonnées

Littérature citée [39 références]  Voir  Masquer  Télécharger


https://hal.inria.fr/hal-01376243
Contributeur : Pierre Alliez <>
Soumis le : mardi 4 octobre 2016 - 15:13:46
Dernière modification le : jeudi 11 janvier 2018 - 16:47:00
Document(s) archivé(s) le : vendredi 3 février 2017 - 15:52:27

Fichiers

ovt-author-version.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01376243, version 1

Collections

Citation

Max Budninskiy, Beibei Liu, Fernando De Goes, Yiying Tong, Pierre Alliez, et al.. Optimal Voronoi Tessellations with Hessian-based Anisotropy. ACM Transactions on Graphics, Association for Computing Machinery, 2016, Proceedings of SIGGRAPH Asia, pp.12. 〈hal-01376243〉

Partager

Métriques

Consultations de la notice

364

Téléchargements de fichiers

931