3531 articles – 5253 Notices  [english version]

inria-00602490, version 1

GPU-Assisted Computation of Centroidal Voronoi Tessellation

Guodong Rong 1, Yang Liu () a, 2, Wenping Wang () 3, Xaotian Yin 4, Xianfeng Gu 4, Xiaohu Guo 1

IEEE Transactions on Visualization and Computer Graphics 17, 3 (2011) 345-356

Résumé : 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.

  • a –  INRIA
  • 1 :  Computer Science Department [Austin]
  • University of Texas at Austin
  • 2 :  ALICE (INRIA Lorraine - LORIA)
  • INRIA – CNRS : UMR7503 – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine (INPL)
  • 3 :  Department of Computer Science [Hong Kong]
  • City University of Hong Kong
  • 4 :  Department of Computer Science [Stonybrook - NY]
  • State University of New-York at Stonybrook
  • Domaine : Informatique/Géométrie algorithmique
 
  • inria-00602490, version 1
  • http://hal.inria.fr/inria-00602490
  • oai:hal.inria.fr:inria-00602490
  • Contributeur : Bruno Levy <>
  • Soumis le : Mercredi 22 Juin 2011, 16:19:02
  • Dernière modification le : Mercredi 22 Juin 2011, 16:22:00