Parallel Computation of 3D Accurate Power Diagrams on GPU

The computation of power diagram (or weighted Voronoi diagram) is a fundamental task in computer graphics and computational geometry etc. Given the high time cost of serial methods and non-accurate results generated by parallel methods, a novel parallel computing method on GPU is proposed in this paper. We first give the equivalent construction from power diagrams to restricted Voronoi diagrams in one dimension higher, allowing us to extend the meshless method for generating Voronoi diagrams to the computation of power diagrams. Based on which, the given weighted sites are placed into a set of grids in the space with one dimension higher, from where 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, which can efficiently obtain accurate power diagrams in the 3D space. By comparing the time cost under different domains and 50 thousand sites, the proposed method possesses more than three times the acceleration ratio with existing methods.