Isotropic Remeshing with Fast and Exact Computation
of Restricted Voronoi Diagram

Dong-Ming Yan1,2, Bruno Lévy2, Yang Liu2, Feng Sun1, Wenping Wang1

1Department of Computer Science, The University of Hong Kong, Hong Kong, China
2Project ALICE, INRIA, Villers les Nancy, France

Abstract: We propose a new isotropic remeshing method, based on Centroidal Voronoi Tessellation (CVT). Constructing CVT requires to compute Restricted Voronoi Diagram (RVD), defined as the intersection between a 3D Voronoi diagram and an input mesh surface. Existing methods use some approximations of RVD. In this paper, we introduce an efficient algorithm that computes RVD exactly and robustly. As a consequence, we achieve better remeshing quality than approximation-based approaches, without sacrificing efficiency. Our method for RVD computation uses a simple procedure and a kd-tree to quickly identify and compute the intersection of each triangle face with its incident Voronoi cells. Its time complexity is O(m\log n), where n is the number of seed points and m is the number of triangles of the input mesh. Fast convergence of CVT is achieved using a quasi-Newton method, which proved much faster than Lloyd's iteration. Examples are presented to demonstrate the better quality of remeshing results with our method than the state-of-art approaches.

 

Restricted Voronoi diagram computation and isotropic remeshing of the Kitten model (274k faces, 10k seeds). (a) Input mesh; (b) initial RVD; (c) optimized result (RCVT); (d) remeshing result.

Restricted Voronoi diagram computation on Bunny model (5k faces) with increasing number of seeds, from 1eft to right are 1k, 10k, 100k and 500k seeds

Interleaved topology control / optimization

 

Restricted Voronoi diagram computation and isotropic remeshing of the mask model with density set to 1/lfs2(3k faces, 1.5k seeds)


Errata: in paragraph "Quality measurements" of Section 5, the 4th line, $p_t$ should be the half-perimeter instead of the in-radius of $t$.

Paper: PDF (fixed version)

Video: topo_control.zip; three_holds.avi; joint.avi; fandisk.avi; human.avi

See also remesh page at Alice@loria; CVT project page