Isotropic Remeshing with Fast and Exact Computation of Restricted Voronoi Diagram

Autor: Feng Sun, Dong-Ming Yan, Wenping Wang, Yang Liu, Bruno Levy
Přispěvatelé: Geometry and Lighting (ALICE), INRIA Lorraine, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS), Department of Computer Science [Hong Kong], City University of Hong Kong [Hong Kong] (CUHK)
Jazyk: angličtina
Rok vydání: 2009
Předmět:
Zdroj: Computer Graphics Forum
Computer Graphics Forum, Wiley, 2009, 28 (5), pp.1445-1454. ⟨10.1111/j.1467-8659.2009.01521.x⟩
Computer Graphics Forum, 2009, 28 (5), pp.1445-1454. ⟨10.1111/j.1467-8659.2009.01521.x⟩
ISSN: 0167-7055
1467-8659
DOI: 10.1111/j.1467-8659.2009.01521.x⟩
Popis: International audience; 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(mlogn), 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.
Databáze: OpenAIRE
Externí odkaz: