Isotropic Remeshing with Fast and Exact Computation of Restricted Voronoi Diagram
Loading...
Date
2009
Journal Title
Journal ISSN
Volume Title
Publisher
The Eurographics Association and Blackwell Publishing Ltd
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(mlog 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.
Description
@article{10.1111:j.1467-8659.2009.01521.x,
journal = {Computer Graphics Forum},
title = {{Isotropic Remeshing with Fast and Exact Computation of Restricted Voronoi Diagram}},
author = {Yan, Dong-Ming and Levy, Bruno and Liu, Yang and Sun, Feng and Wang, Wenping},
year = {2009},
publisher = {The Eurographics Association and Blackwell Publishing Ltd},
ISSN = {1467-8659},
DOI = {10.1111/j.1467-8659.2009.01521.x}
}