Computing Restricted Voronoi Diagram on Graphics Hardware

Abstract

The 3D restricted Voronoi diagram (RVD), defined as the intersection of the 3D Voronoi diagram of a pointset with a mesh surface, has many applications in geometry processing. There exist several CPU algorithms for computing RVDs. However, such algorithms still cannot compute RVDs in realtime. In this short paper, we propose an efficient algorithm for computing RVDs on graphics hardware. We demonstrate the robustness and the efficiency of the proposed GPU algorithm by applying it to surface remeshing based on centroidal Voronoi tessellation.