Please wait a minute...
浙江大学学报(理学版)  2021, Vol. 48 Issue (4): 410-417    DOI: 10.3785/j.issn.1008-9497.2021.04.003
数据可视分析与虚拟现实     
3D-power图的快速生成方法
桂志强, 姚裕友, 张高峰, 徐本柱, 郑利平
合肥工业大学 计算机与信息学院,安徽 合肥 230009
An efficient computation method of 3D-power diagram
GUI Zhiqiang, YAO Yuyou, ZHANG Gaofeng, XU Benzhu, ZHENG Liping
School of Computer Science and Information Engineering, Hefei University of Technology, Hefei 230009, China
 全文: PDF(1990 KB)   HTML  
摘要: 3D-power图在图形学和流体仿真等领域应用广泛。为解决已有的3D-power图计算方法时间性能较差的问题,提出了基于GPU的power图构造算法,给出了一种用于计算power图各区域之间的面积估值方法,使基于GPU的构造算法与Lloyd算法、牛顿法相结合,生成满足约束条件的3D质心容量限制power图(3D-centroidal capacity constrained power diagram,3D-CCCPD)。结果表明,本文算法的时间性能较已有的3D-power图构造方法提高了几个数量级。
关键词: 质心3D-power图GPU加速容量    
Abstract: 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.
Key words: 3D-power diagram    centroidal    capacity    GPU accelerate
收稿日期: 2020-09-23 出版日期: 2021-07-25
CLC:  TP 391.41  
基金资助: 国家自然科学基金资助项目(61972128,61702155);安徽省自然科学基金资助项目(1808085MF176).
通讯作者: ORCID: https://orcid.org/0000-0001-5071-9628,E-mail:zhenglp@hfut.edu.cn.     E-mail: zhenglp@hfut.edu.cn
作者简介: 桂志强(1995—),ORCID: https://orcid.org/0000-0002-9071-1070,男,硕士,主要从事计算机图形学与计算机辅助设计研;
服务  
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章  
桂志强
姚裕友
张高峰
徐本柱
郑利平

引用本文:

桂志强, 姚裕友, 张高峰, 徐本柱, 郑利平. 3D-power图的快速生成方法[J]. 浙江大学学报(理学版), 2021, 48(4): 410-417.

GUI Zhiqiang, YAO Yuyou, ZHANG Gaofeng, XU Benzhu, ZHENG Liping. An efficient computation method of 3D-power diagram. Journal of Zhejiang University (Science Edition), 2021, 48(4): 410-417.

链接本文:

https://www.zjujournals.com/sci/CN/10.3785/j.issn.1008-9497.2021.04.003        https://www.zjujournals.com/sci/CN/Y2021/V48/I4/410

1 BALZER M,SCHLÖMER T,DEUSSEN O. Capacity-constrained point distributions:A variant of Lloyd’s method[J]. ACM Transactions on Graphics,2009,28(3):1-8. DOI:10.1145/1531326. 1531392
2 GOES F de,BREEDEN K,OSTROMOUKHOV V,et al. Blue noise through optimal transport[J]. ACM Transactions on Graphics,2012,31(6):1-11. DOI:10.1145/2366145.2366190
3 ZHANG S,GUO J,ZHANG H,et al. Capacity constrained blue-noise sampling on surfaces[J]. Computers & Graphics,2016,55:44-54. DOI:10. 1016/j.cag.2015.11.002
4 AHMED A G M,GUO J,YAN D M,et al. A simple push-pull algorithm for blue-noise sampling[J]. IEEE Transactions on Visualization and Computer Graphics,2017,23(12):2496-2508. DOI:10.1109/TVCG.2016.2641963
5 郑利平,程亚军,周乘龙,等. 异构群体队形光滑变换控制方法[J]. 计算机辅助设计与图形学学报,2015,27(10):1963-1970. DOI:10.3969/j.issn.1003-9775. 2015.10.020 ZHENG L P,CHENG Y J,ZHOU C L,et al. Research on smooth formation control of heterogeneous crowds[J]. Journal of Computer-Aided Design & Computer Graphics,2015(10):1963-1970. DOI:10.3969/j.issn.1003-9775.2015. 10.020
6 GOES F de,WALLEZ C,HUANG J,et al. Power particles:An incompressible fluid solver based on power diagrams[J]. ACM Transactions on Graphics,2015,34(4):1-11. DOI:10.1145/2766901
7 AANJANEYA M,GAO M,LIU H,et al. Power diagrams and sparse paged grids for high resolution adaptive liquids[J]. ACM Transactions on Graphics,2017,36(4):1-12. DOI:10.1145/3072959.3073625
8 ZHAI X,HOU F,QIN H,et al. Fluid simulation with adaptive staggered power particles on GPUs[J]. IEEE Transactions on Visualization and Computer Graphics,2018,26(6):2234-2246. DOI:10.1109/TVCG.2018.2886322
9 AURENHAMMER F. Power diagrams:Properties,algorithms and applications[J]. SIAM Journal on Computing,1987,16:78-96. DOI:10.1137/0216006
10 AURENHAMMER F. Voronoi diagrams:A survey of a fundamental geometric data structure[J]. ACM Computing Surveys,1991,23(3):345-405. DOI:10.1145/116873.116880
11 BALZER M,HECK D. Capacity-constrained Voronoi diagrams in finite spaces[C]// Proceedings of the 5th International Symposium on Voronoi Diagrams in Science and Engineering. Kiev,Ukraine:IEEE,2008:44-56.
12 BALZER M. Capacity-constrained Voronoi diagrams in continuous spaces[C]// Proceedings of the 6th International Symposium on Voronoi Diagrams.Copenhagen: IEEE,2009:79-88. DOI:10.1109/isvd. 2009.28
13 MULLEN P,MEMARI P,GOES F de,et al. HOT:Hodge-optimized triangulations[J].ACM Transactions on Graphics,2011,30(4):1-11. DOI:10.1145/2010324.1964998
14 XIN S Q,LÉVY B,CHEN Z,et al. Centroidal power diagrams with capacity constraints:Computation,applications,and extension[J]. ACM Transactions on Graphics,2016,35(6):1-12. DOI:10.1145/2980179. 2982428
15 LIU X,MA L,GUO J,et al. Parallel computation of 3D clipped Voronoi diagrams[C]// IEEE Transactions on Visualization and Computer Graphics. Stony Brook:IEEE,2020.DOI:10.1109/TVCG.2020. 3012288
16 HAN J,YAN D M,WANG L,et al. Computing restricted Voronoi diagram on graphics hardware[C]//Proceedings of the 25th Pacific Conference on Computer Graphics and Applications. Maui:IEEE Computer Society,2017:23-26.
17 YAN D M,WANG W,LÉVY B,et al. Efficient computation of 3D clipped Voronoi diagram[C]// HUTCHISON D,KANADE T,KITTLER J,et al. Advances in Geometric Modeling and Processing. Berlin/Heidelberg:Springer,2010:269-282. DOI:10.1007/978-3-642-13411-1_18
18 ALLIZE P, FABRI A. Computational geometry algorithms library[C]// Proceedings of the 2009 ACM SIGGRAPH ASIA. New York : ACM, 2009: 1-133. DOI: 10.1145/1665817.1665821
19 RAY N,SOKOLOV D,LEFEBVRE S,et al. Meshless Voronoi on the GPU[J]. ACM Transactions on Graphics,2018,37(6):1-12. DOI:10.1145/3272127.3275092
20 LIU X,YAN D M. Computing 3D clipped Voronoi diagrams on GPU[C]// SIGGRAPH Asia 2019 Posters. New York:ACM,2019:1-2. DOI:10.1145/3355056.3364581
21 RYCROFT C H. VORO++:A three-dimensional Voronoi cell library in C++[J]. Chaos,2009,19(4):9041111. DOI:10.1063/1.3215722
22 GOLIN M J,NA H S. On the average complexity of 3D-Voronoi diagrams of random points on convex polytopes[J]. Computational Geometry,2003,25(3):197-231. DOI:10.1016/S0925-7721(02)00123-2
23 RONG G D,TAN T S. Jump flooding in GPU with applications to Voronoi diagram and distance transform[C]// Proceeding of the 2006 Symposium on Interative 3D Graphics and Games. Redwood City,CA:ACM, 2006:109-116. DOI:10.1145/1111411.1111431
24 RONG G,TAN T S. Variants of jump flooding algorithm for computing discrete Voronoi diagrams[C]//The 4th International Symposium on Voronoi Diagrams in Science and Engineering. Glamorgan:IEEE Computer Society,2007:176-181. DOI:10.1109/isvd.2007.41
25 ZHENG L,GUI Z,CAI R,et al. GPU-based efficient computation of Power diagram[J]. Computers & Graphics,2019,80:29-36. DOI:10.1016/j.ag.2019. 03.011
[1] 桂彦, 王培玉, 李峰, 刘杨. 基于GPU加速的几何纹理合成方法[J]. 浙江大学学报(理学版), 2016, 43(6): 638-646.