Parallel Computation of Exact Power Diagrams in 3D Space on GPU

Power diagram (weighted Voronoi diagram) has been widely used in various fields including computer graphics and simulations, its fast and exact computation is a fundamental task in many applications. However, the time cost required to compute 3D power diagrams still stays at a high level. Despite some parallel algorithms having been developed, they produce approximating results of power diagrams. We propose a novel parallel computation method with the assistance of GPU, which enables us to efficiently obtain the exact power diagrams in 3D space. The given weighted sites are first placed into a set of grids in the space with one dimension higher, based on which the neighbors of each site can be identified quickly, then the power cells are clipped in parallel by using the bisectors between the corresponding site and the neighbors. Experimental results demonstrate that our method has remarkable advantages in terms of accuracy and efficiency compared with existing methods.