3D-power图的快速生成方法

3D-power图在图形学和流体仿真等领域应用广泛。为解决已有的3D-power图计算方法时间性能较差的问题，提出了基于GPU的power图构造算法，给出了一种用于计算power图各区域之间的面积估值方法，使基于GPU的构造算法与Lloyd算法、牛顿法相结合，生成满足约束条件的3D质心容量限制power图（3D-centroidal capacity constrained power diagram，3D-CCCPD）。结果表明，本文算法的时间性能较已有的3D-power图构造方法提高了几个数量级。

An efficient computation method of 3D-power diagram

3D-power diagrams have a wide range of applications in the fields of graphics and fluid simulation. To overcome the poor time performance of the existing 3D-power diagram construction algorithms, a novel GPU-based construction algorithm is proposed. We introduce an estimation algorithm for computing the area between power cells. The estimation algorithm enables the construction algorithm to be coupled with the Lloyd algorithm and Newton's algorithm to generate a 3D-centroidal capacity constrained power diagram(3D-CCCPD). Experiment results show that our approach raises the efficiency of the 3D-power diagram construction up to several orders of magnitude.