Isotropic Remeshing with Fast and Exact Computation of Restricted Voronoi Diagram |
| |
Authors: | Dong-Ming Yan,Bruno Lé vy,Yang Liu,Feng Sun, Wenping Wang |
| |
Affiliation: | Department of Computer Science, The University of Hong Kong, Hong Kong, China;Project Alice, INRIA, Nancy, France |
| |
Abstract: | We propose a new isotropic remeshing method, based on Centroidal Voronoi Tessellation (CVT) . Constructing CVT requires to repeatedly 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 with the state-of-art approaches. |
| |
Keywords: | I.3.3 [Computer Graphics]: Picture/Image Generation—Line and curve generation |
|
|