Optimal voronoi tessellations with hessian-based anisotropy
Authors:
- Yiying TongYTYiying Tong
- Mathieu DesbrunMDMathieu Desbrun
Open Access
- 11 November 2016
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Graphics
- Vol. 35 (6) , 1-12
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 Tessellations. 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
This publication has 35 references indexed in Scilit:
- Obtuse triangle suppression in anisotropic meshesComputer Aided Geometric Design, 2011
- Greedy bisection generates optimally adapted triangulationsMathematics of Computation, 2011
- HOTACM Transactions on Graphics, 2011
- L
p
Centroidal Voronoi Tessellation and its applicationsACM Transactions on Graphics, 2010
- On centroidal voronoi tessellation—energy smoothness and fast computationACM Transactions on Graphics, 2009
- Interleaving Delaunay refinement and optimization for practical isotropic tetrahedron mesh generationACM Transactions on Graphics, 2009
- Anisotropic diagrams: Labelle Shewchuk approach revisitedTheoretical Computer Science, 2008
- Optimal anisotropic meshes for minimizing interpolation errors in 𝐿^{𝑝}-normMathematics of Computation, 2006
- Acceleration schemes for computing centroidal Voronoi tessellationsNumerical Linear Algebra with Applications, 2006
- Variational tetrahedral meshingACM Transactions on Graphics, 2005