Computing Centroidal Voronoi Tessellation Using the GPU

Jiaqi Zheng and Tiow-Seng Tan

jiaqi.zheng.ac@outlook.com, tants@comp.nus.edu.sg

School of Computing

National University of Singapore

Abstract

We propose a novel algorithm to compute centroidal Voronoi tessellation using the GPU. It is based on the iterative approach of Lloyd’s method while having good considerations to address the two major challenges of achieving fast convergence with few iterations, and at the same time achieving fast computation within each iteration. Our implementation of the algorithm can complete the computation for a large image in the order of hundreds of milliseconds and is faster than all prior work on a state-of-the-art GPU. As such, it is now easier to integrate centroidal Voronoi tessellations into interactive applications.

CCS Concepts: Theory of computation → Computational Geometry, Computing methodologies → Graphics processors

Keywords: GPGPU, Computational Geometry, Digital Geometry, Lloyd's Method, Voronoi Diagram, PBA

Paper in Symposium on Interactive 3D Graphics and Games (I3D’20). May 5-7, 2020, San Francisco, CA, USA.

Related Projects: Parallel Banding Algorithm, Surface Remesher

Download: available at Github repository

Dated: 29 February 2020, 19 March 2020

©NUS