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

An efficient computation method of 3D-power diagram

作　　者：桂志强[1] 姚裕友 张高峰[1] 徐本柱[1] 郑利平[1] GUI Zhiqiang;YAO Yuyou;ZHANG Gaofeng;XU Benzhu;ZHENG Liping(School of Computer Science and Information Engineering,Hefei University of Technology,Hefei 230009,China)

机构地区：[1]合肥工业大学计算机与信息学院,安徽合肥230009

出　　处：《浙江大学学报（理学版）》2021年第4期410-417,共8页Journal of Zhejiang University（Science Edition）

基　　金：国家自然科学基金资助项目(61972128,61702155);安徽省自然科学基金资助项目(1808085MF176)。

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

关 键 词：3D-power图 GPU加速 质心 容量 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术]