GPU-Assisted Computation of Centroidal Voronoi Tessellation

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.
Type de document :
Article dans une revue
IEEE Transactions on Visualization and Computer Graphics, Institute of Electrical and Electronics Engineers, 2011, 17 (3), pp.345-356. 〈10.1109/TVCG.2010.53〉
Liste complète des métadonnées

Littérature citée [43 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00602490
Contributeur : Bruno Levy <>
Soumis le : mercredi 22 juin 2011 - 16:19:02
Dernière modification le : jeudi 11 janvier 2018 - 06:20:18
Document(s) archivé(s) le : vendredi 23 septembre 2011 - 02:25:13

Fichier

GPU-CVT.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Guodong Rong, Yang Liu, Wenping Wang, Xaotian Yin, Xianfeng Gu, et al.. GPU-Assisted Computation of Centroidal Voronoi Tessellation. IEEE Transactions on Visualization and Computer Graphics, Institute of Electrical and Electronics Engineers, 2011, 17 (3), pp.345-356. 〈10.1109/TVCG.2010.53〉. 〈inria-00602490〉

Partager

Métriques

Consultations de la notice

307

Téléchargements de fichiers

273