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


“GPU-Assisted Computation of Centroidal Voronoi Tessellation”
G. Rong, Y. Liu, W. Wang, X. Yin, X. Gu and X. Guo
IEEE Transactions on Visualization and Computer Graphics - To appear

Abstract: Centroidal Voronoi tessellations (CVT) are widely used in computational science and engineering. The most commonly used method is Lloyd's method, and recently the L-BFGS method is shown to be faster than Lloyd's method for computing the CVT. However, these methods run on the CPU and are still too slow for many practical applications. We present techniques to implement these methods on the GPU for computing the CVT on 2D planes and on surfaces, and demonstrate significant speedup of these GPU-based methods over their CPU counterparts. For CVT computation on a surface, we use a geometry image stored in the GPU to represent the surface for computing the Voronoi diagram on the surface. In our implementation a new technique is proposed for parallel regional reduction on the GPU for evaluating integrals over Voronoi cells.

BibTex reference

   AUTHOR     = "G. Rong and Y. Liu and W. Wang and X. Yin and X. Gu and X. Guo",
   TITLE      = "GPU-Assisted Computation of Centroidal Voronoi Tessellation",
   JOURNAL    = "IEEE Transactions on Visualization and Computer Graphics",
   NOTE       = "To appear",