Publications by year

2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  

Most documents on this website are protected by copyright. By clicking on a PDF icon, you confirm that you or your institution has the right to do so. Note that the definitive versions of all EG papers (Eurographics,...) can be downloaded from ACM papers (Siggraph, ...) can be downloaded from


“Isotropic Remeshing with Fast and Exact Computation of Restricted Voronoi Diagram”
Dong-ming Yan, Bruno Lévy, Yang Liu, Feng Sun and Wenping Wang
ACM/EG Symposium on Geometry Processing / Computer Graphics Forum, 2009

Abstract: We propose a new isotropic remeshing method, based on Centroidal Voronoi Tessellation (CVT). Constructing CVT requires to 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 the state-of-art approaches.

BibTex reference

   AUTHOR     = "Dong-ming Yan and Bruno Lévy and Yang Liu and Feng Sun and Wen
                   ping Wang",
   TITLE      = "Isotropic Remeshing with Fast and Exact Computation of Restricted Vor
                   onoi Diagram",
   BOOKTITLE  = "ACM/EG Symposium on Geometry Processing / Computer Graphics Forum",
   YEAR       = "2009",

Supplemental material, links, hindsight ...

See also remesh project page in Hong-Kong University website.

See also our paper On Centroidal Voronoi Tesselation