Isotropic Remeshing with Fast and Exact Computation of Restricted Voronoi Diagram.

Dong-Ming Yan and Bruno Levy and Yang Liu and Feng Sun and Wenping Wang. ( 2009 )
in: Proc. 29th Gocad Meeting, Nancy

Abstract

We propose a new isotropic remeshing method, based on Constrained Centroidal Voronoi Tessellation (CCVT). Constructing CCVT requires to compute Restricted Voronoi Diagrams (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 is achieved using a quasi-Newton method, which proves 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.

Download / Links

BibTeX Reference

@inproceedings{YanGM2009,
 abstract = { We propose a new isotropic remeshing method, based on Constrained Centroidal Voronoi Tessellation (CCVT). Constructing CCVT requires to compute Restricted Voronoi Diagrams (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 is achieved using a quasi-Newton method, which proves 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. },
 author = { Yan, Dong-Ming AND Levy, Bruno AND Liu, Yang AND Sun, Feng AND Wang, Wenping },
 booktitle = { Proc. 29th Gocad Meeting, Nancy },
 title = { Isotropic Remeshing with Fast and Exact Computation of Restricted Voronoi Diagram. },
 year = { 2009 }
}