Computing Centroidal Voronoi Tessellations on the GPU

Abstract

In the last decade, commodity Graphics Processing Units (GPUs) specialized for 2D and 3D graphics have dramatically changed in purpose from purely video game hardware to something akin to their general purpose counterpart, the CPU. Currently capable of near teraflop speeds with gigabytes of on-board memory, GPUs have transformed from accessory hardware for a young generation to general purpose coprocessors for scientific computation.

This poster presents results from the first (to our knowl- edge) implementation to compute centroidal Voronoi tessellations of manifolds entirely on the GPU. To complete these tasks, a highly efficient flooding algorithm is used to produce the Voronoi tessellation, while a regularized sampling approach is employed to compute centroids of Voronoi regions. We consider simple surfaces (2-manifolds) of the form (1) partitioned according to Euclidean-based metrics, with the generating points up- dated by a deterministic Lloyd’s method.