Isotropic Remeshing with Fast and Exact Computation of Restricted Voronoi Diagram
Dong‐Ming Yan, Bruno Lévy, Yang Liu, Feng Rui Sun, Wenping Wang · Computer Graphics Forum · 2009
Abstract We propose a new isotropic remeshing method, based onCentroidal Voronoi Tessellation (CVT). Constructing CVT requires to repeatedly computeRestricted 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 akd‐tree to quickly identify and compute the intersection of each triangle face with its incident Voronoi cells. Its time complexity isO(mlogn), wherenis the number of seed points andmis 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.