Isotropic Remeshing with Fast and Exact Computation of Restricted Voronoi Diagram

Dong-Ming Yan 1, 2 Bruno Lévy 1 Yang Liu 1 Feng Sun 2 Wenping Wang 2
1 ALICE - Geometry and Lighting
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
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(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.
Type de document :
Article dans une revue
Computer Graphics Forum, Wiley, 2009, 28 (5), pp.1445-1454. 〈10.1111/j.1467-8659.2009.01521.x〉
Liste complète des métadonnées

Littérature citée [27 références]  Voir  Masquer  Télécharger
Contributeur : Dongming Yan <>
Soumis le : vendredi 17 décembre 2010 - 15:10:47
Dernière modification le : jeudi 11 janvier 2018 - 06:20:18
Document(s) archivé(s) le : vendredi 18 mars 2011 - 03:19:14


Fichiers produits par l'(les) auteur(s)




Dong-Ming Yan, Bruno Lévy, Yang Liu, Feng Sun, Wenping Wang. Isotropic Remeshing with Fast and Exact Computation of Restricted Voronoi Diagram. Computer Graphics Forum, Wiley, 2009, 28 (5), pp.1445-1454. 〈10.1111/j.1467-8659.2009.01521.x〉. 〈inria-00547790〉



Consultations de la notice


Téléchargements de fichiers