carrier image

Variational Anisotropic Surface Meshing with Voronoi Parallel Linear Enumeration

Levy, Bruno and Nicolas Bonneel

21st International Meshing Roundtable, Springer-Verlag, pp.344-366, October 7-10 2012


21st International Meshing Roundtable
San Jose, CA
October 7-10,2012

Project ALICE, INRIA Nancy Grand-Est and LORIA

This paper introduces a new method for anisotropic surface meshing. From an input polygonal mesh and a specified number of vertices, the method generates 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 computing a Centroidal Voronoi Tessellation (CVT), i.e. the minimizer of a C2 objective function that depends on the coordinates at the vertices (quantization 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 restricted 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.

Download Full Paper (PDF Format)

Contact author(s) or publisher for availability and copyright information on above referenced article