GPU-Assisted Computation of Centroidal Voronoi Tessellation

Guodong Rong, Yang Liu, Wenping Wang, Xiaotian Yin, Xianfeng David Gu, Xiaohu Guo


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 it. In our implementation a new technique is proposed for parallel regional reduction on the GPU for evaluating integrals over Voronoi cells.

[APA Style Citation] Rong, G., Liu, Y., Wang, W., Yin, X., Gu, X., & Guo, X. (2010). GPU-Assisted Computation of Centroidal Voronoi Tessellation. Visualization and Computer Graphics, IEEE Transactions on, 17(3), 345-356. doi: 10.1109/TVCG.2010.53

[MLA Style Citation] Rong, Guodong, Yang Liu, Wenping Wang, Xiaotian Yin, Xianfeng David Gu and Xiaohu Guo. "GPU-Assisted Computation of Centroidal Voronoi Tessellation." Visualization and Computer Graphics, IEEE Transactions on 17.3 (2010): 345-356. doi: 10.1109/TVCG.2010.53

Paper Download | Code for 2D CVT | Code for Surface CVT

Point-Based Manifold Harmonics

Yang Liu, Balakrishnan Prabhakaran, Xiaohu Guo

Abstract - This paper proposes an algorithm to build a set of orthogonal Point-Based Manifold Harmonic Bases (PB-MHB) for spectral analysis over point-sampled manifold surfaces. To ensure that PB-MHB are orthogonal to each other, it is necessary to have symmetrizable discrete Laplace-Beltrami Operator (LBO) over the surfaces. Existing converging discrete LBO for point clouds, as proposed by Belkin et al [1], is not guaranteed to be symmetrizable. We build a new point-wisely discrete LBO over the point-sampled surface that is guaranteed to be symmetrizable, and prove its convergence. By solving the eigen problem related to the new operator, we define a set of orthogonal bases over the point cloud. Experiments show that the new operator is converging better than other symmetrizable discrete Laplacian operators (such as graph Laplacian) defined on point-sampled surfaces, and can provide orthogonal bases for further spectral geometric analysis and processing tasks.

[Citation] Yang Liu, Balakrishnan Prabhakaran, Xiaohu Guo, "Point-Based Manifold Harmonics," to appear in IEEE Transactions on Visualization and Computer Graphics, 2011.

Paper Download | Code