GPU-based efficient computation of power diagram

Abstract Power diagram has been widely used in graphics and engineering. In the computation process for the centroidal capacity constrained power diagram, the geometrical construction of the power diagram is time consuming, and accounts for more than 50% of the total computing time, which severely affects the efficiency. A novel GPU-based power diagram construction algorithm is proposed to improve the efficiency. We introduce the jump flooding algorithm for parallelly rendering the power diagram, and present an approach for extracting the geometrical vertices and edges to generate the power diagram. Then, to accelerate the power diagram computation process, we propose a GPU–CPU hybrid algorithm by coupling the existing CPU-based algorithm with our proposed GPU algorithm. Furthermore, to accelerate further, a pure GPU algorithm is proposed. It utilizes the discrete Lloyd’s algorithm for centroidal constraints and a GPU-based analytical algorithm for weights and capacities. Experiment results exhibit that our proposed GPU algorithms can improve the efficiency of the power diagram construction by several orders of magnitude.