Variational Anisotropic Surface Meshing with Voronoi Parallel Linear Enumeration

Bruno Lévy (1) , Nicolas Bonneel (2)

1 ALICE - Geometry and Lighting
2 Harvard University

This paper introduces a new method for anisotropic surface meshing. From an input polygonal mesh and a specified number of vertices, the method gen- erates a curvature-adapted mesh. The main idea consists in transforming the 3d anisotropic space into a higher dimensional isotropic space (typically 6d or larger). In this high dimensional space, the mesh is optimized by com- puting a Centroidal Voronoi Tessellation (CVT), i.e. the minimizer of a $C^2$ objective function that depends on the coordinates at the vertices (quantiza- tion noise power). Optimizing this objective function requires to compute the intersection between the (higher dimensional) Voronoi cells and the surface (Restricted Voronoi Diagram). The method overcomes the $d$-factorial cost of computing a Voronoi diagram of dimension $d$ by directly computing the re- stricted Voronoi cells with a new algorithm that can be easily parallelized (Vorpaline: Voronoi Parallel Linear Enumeration). The method is demonstrated with several examples comprising CAD and scanned meshes.

Mots clés: Voronoi Diagram; Delaunay Triangulation; Voronoi Cell; Anisotropic Mesh; Power Diagram

Domaines: Automatique

Bruno Lévy, Nicolas Bonneel. Variational Anisotropic Surface Meshing with Voronoi Parallel Linear Enumeration. Proceedings of the 21st International Meshing Roundtable, Springer Berlin Heidelberg, pp.349-366, 2012, 978-3-642-33572-3. ⟨10.1007/978-3-642-33573-0_21⟩. ⟨hal-00804558⟩