| Data Visual Analysis and Vitual Reality |
|
|
|
|
| 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 |
|
|
|
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.
|
|
Received: 23 September 2020
Published: 25 July 2021
|
|
|
|
Cite this article:
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.
URL:
https://www.zjujournals.com/sci/EN/Y2021/V48/I4/410
|
3D-power图的快速生成方法
3D-power图在图形学和流体仿真等领域应用广泛。为解决已有的3D-power图计算方法时间性能较差的问题，提出了基于GPU的power图构造算法，给出了一种用于计算power图各区域之间的面积估值方法，使基于GPU的构造算法与Lloyd算法、牛顿法相结合，生成满足约束条件的3D质心容量限制power图（3D-centroidal capacity constrained power diagram，3D-CCCPD）。结果表明，本文算法的时间性能较已有的3D-power图构造方法提高了几个数量级。
关键词：
质心,
3D-power图,
GPU加速,
容量
|
|
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 |
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
| |
Shared |
|
|
|
|
| |
Discussed |
|
|
|
|
