Research On Efficient Computation Algorithm Of Power Diagram Based On GPU

Power diagrams are commonly used in graphics and engineering.Among them,CCCPD with centroidal constraints and capacity constraints is particularly prominent.In existing algorithms,one of the most complex operations defined on the CCCPD is the geometrical construction,which takes more than 50% of the total computing time.The centroidal and capacity constraint optimization process also consumes a lot of time.To overcome this performance bottleneck,this dissertation proposes a novel GPU-based construction algorithm for 2D-power diagram and 3D-power diagram.The main works of this dissertation are as follows:1)The research progress of the Voronoi diagram and the power diagram is reviewed.The advantages and disadvantages of the existing Voronoi diagram and power diagram computation algorithms in 2D and 3D are summarized.2)A 2D-CCCPD algorithm based on GPU-CPU is proposed.Firstly,a GPU-based JFA is developed for parallel rendering of power diagrams.Secondly,this dissertation proposes a method which is called connected domain method to extract geometric data structure of the 2D-power diagram.Finally,coupled with CPU-based L-BFGS algorithm and Newton's algorithm as a GPUCPU hybrid algorithm to accelerate the computation of the 2D-power diagram.Experimental results show that the proposed approach can effectively improve the generation efficiency while ensuring the computation accuracy of 2DCCCPD.3)A 3D-CCCPD algorithm based on GPU-CPU is proposed.The JFA is extended to the 3D-power diagram.An estimation algorithm is proposed to calculate the area of the common surface of each power cell.Combined with Lloyd algorithm and Newton's algorithm to generate 3D-CCCPD.Experiment results show that the efficiency of the proposed approach is several hundred times higher than the existing algorithm.