Parallel Computation of 3D Clipped Voronoi Diagrams

Results of Lloyd's iterations using our method.


Computing the Voronoi diagram for a given set of points in a restricted domain (2D polygons, 3D surfaces, or volumes) is a crucial task in many applications. Although existing algorithms can compute 2D and surface Voronoi diagrams in parallel on graphics hardware, computing clipped Voronoi diagrams in 3D volume is still a challenge. In this paper, we propose an efficient GPU algorithm to tackle this problem. We first discretize the input 3D volume into a tetrahedral mesh in a pre-processing step, and then take advantage of our efficient parallel algorithm to compute 3D clipped Voronoi diagrams. The key contribution of our approach is that we use the four planes of each tetrahedron to clip the Voronoi cells, instead of using the bisecting planes of Voronoi cells to clip tets like previous approaches. This simple strategy drastically reduces computational complexity. The proposed method outperforms the state-of-the-art CPU methods up to one order of magnitude.

In Computational Visual Media Conference 2020 (recommended for publication in IEEE TVCG)