计算机科学技术学报 ›› 2022,Vol. 37 ›› Issue (3): 731-740.doi: 10.1007/s11390-022-0331-x

所属专题: Computer Graphics and Multimedia

• • 上一篇    

以BVH为中心的基于GPU的可变形物体距离场构建算法

  

  • 收稿日期:2020-03-31 修回日期:2022-03-15 接受日期:2022-04-02 出版日期:2022-05-30 发布日期:2022-05-30

BADF: Bounding Volume Hierarchies Centric Adaptive Distance Field Computation for Deformable Objects on GPUs

Xiao-Rui Chen1 (陈潇瑞), Min Tang1 (唐敏), Member, CCF, ACM, Cheng Li1 (李澄), Dinesh Manocha2, Member, CCF, ACM, IEEE, and Ruo-Feng Tong1 (童若锋), Member, CCF        

  1. 1Laboratory of Geometry, Image and Video Processing Enterprise Intelligent Computing, College of Computer Science and Technology, Zhejiang University, Hangzhou 310007, China
    2Geometric Algorithms for Modeling, Motion, and Animation Laboratory, University of Maryland, Maryland 20742, U.S.A.
  • Received:2020-03-31 Revised:2022-03-15 Accepted:2022-04-02 Online:2022-05-30 Published:2022-05-30
  • Contact: Xiao-Rui Chen E-mail:chenxiaorui@zju.edu.cn
  • About author:Xiao-Rui Chen received his B.S. degree in computer science from Shandong University, Jinan, in 2016. He is currently working as a Ph.D. candidate in Zhejiang University, Hangzhou. His current research interests include clothes simulation, GPU-algorithm, collision detection, and collision response.
  • Supported by:
    This work was supported by the National Key Research and Development Program of China under Grant No. 2018AAA0102703, and the National Natural Science Foundation of China under Grant Nos. 61972341, 61972342, and 61732015.

目前的距离场构建时间消耗过于漫长。而目前各种场景要求有稳定高速的距离场构建算法。因此我们提出了一种快速的方法BADF(基于包围盒层次结构的自适应距离场),用于加速GPU上刚性和可变形模型的ADF(自适应距离场)的构建。我们的方法基于BVH,我们使用 该BVH生成基于八叉树的ADF。 我们利用连续帧之间的连贯性,并对八叉树的网格点进行排序,以加快计算速度。 我们的方法适用于刚性和变形模型。 我们的基于GPU的算法比基于CPU的算法快20-50倍。 我们的BADF算法可以在NVIDIA GTX GeForce 1060上以交互速率构造具有60K三角形的可变形模型的距离场,此外,我们观察到的速度是以前基于GPU的ADF的3倍。
1、 研究背景(context): 距离场可以应用到许多的场景中,例如运动规划,物理仿真,几何变换等。但是当前距离场加速算法却不是非常普遍,现有的算法针对大规模物体构建距离场非常耗时,对于可变形物体来说,距离场算法就在时间计算上过度消耗。
2、目的(Objective):在针对可变形物体和刚体的碰撞中,我们发现对刚体距离场计算耗时过长,因此我们就对算法进行改进,现有的刚体距离场已经可以进行中规模的实时计算。
3、方法(Method):我们的方法基于BVH,我们使用该BVH生成基于八叉树的ADF。 我们利用连续帧之间的连贯性,并对八叉树的网格点进行排序,以加快计算速度。 我们的方法适用于刚性和变形模型。我们先对每个三角形面片生成Morton Code,然后基于Morton Code对三角形进行排序。同时我们基于Morton Code在GPU上对三角形进行并行的空间划分,构建出三角形所在的空间八叉树。
4、结果(Result & Findings):BADF算法针对上下帧连续的物体进行了GPU上构造的优化,构造时间快速降低。我们的基于GPU的算法比基于CPU的算法快20-50倍。 我们的BADF算法可以在NVIDIA GTX GeForce 1060上以交互速率构造具有60K三角形的可变形模型的距离场,此外,我们观察到的速度是以前基于GPU的ADF的3倍。目前的构造距离场的速度可以针对中等规模的物体实时构造。
5、结论(Conclusions):实验结果表明,过去的并行构造八叉树的算法在构造树形结构的时候并行度不高,而且构造了过多的数据结构。因此我们在增加算法并行度的情况下,复用了数据结构,因此就对算法速度有较大的提升。

关键词: 距离场, 可变形物体, GPU, 八叉树, 包围盒

Abstract: We present a novel algorithm BADF (Bounding Volume Hierarchy Based Adaptive Distance Fields) for accelerating the construction of ADFs (adaptive distance fields) of rigid and deformable models on graphics processing units. Our approach is based on constructing a bounding volume hierarchy (BVH) and we use that hierarchy to generate an octree-based ADF. We exploit the coherence between successive frames and sort the grid points of the octree to accelerate the computation. Our approach is applicable to rigid and deformable models. Our GPU-based (graphics processing unit based) algorithm is about 20x--50x faster than current mainstream central processing unit based algorithms. Our BADF algorithm can construct the distance fields for deformable models with 60k triangles at interactive rates on an NVIDIA GTX GeForce 1060. Moreover, we observe 3x speedup over prior GPU-based ADF algorithms.

Key words: distance field, deformable object, graphics processing unit (GPU), octree, bounding volume hierarchy

[1] Jones M W, Bærentzen A, Srámek M. 3D distance fields: A survey of techniques and applications. IEEE Transactions on Visualization and Computer Graphics, 2006, 12(4): 581-599. DOI: 10.1109/TVCG.2006.56.

[2] Jones M W, Chen M. A new approach to the construction of surfaces from contour data. Computer Graphics Forum, 1994, 13(3): 75-84. DOI: 10.1111/1467-8659.1330075.

[3] Liu F, Kim Y J. Exact and adaptive signed distance fields computation for rigid and deformable models on GPUs. IEEE Transactions on Visualization and Computer Graphics, 2014, 20(5): 714-725. DOI: 10.1109/TVCG.2013.268.

[4] Morton G M. A Computer Oriented Geodetic Data Base and a New Technique in File Sequencing. IBM Ltd., 1966.

[5] Frisken S F, Perry R N, Rockwood A P, Jones T R. Adaptively sampled distance fields: A general representation of shape for computer graphics. In Proc. the 27th Annual Conference on Computer Graphics and Interactive Techniques, July 2000, pp.249-254. DOI: 10.1145/344779.344899.

[6] Krayer B, Müller S. Generating signed distance fields on the GPU with ray maps. The Visual Computer, 2019, 35(6/7/8): 961-971. DOI: 10.1007/s00371-019-01683-w.

[7] Jamriška O. Interactive ray tracing of distance fields. In Proc. the 14th Central European Seminar on Computer Graphics, May 2010.

[8] Mitchell N, Aanjaneya M, Setaluri R, Sifakis E. Nonmanifold level sets: A multivalued implicit surface representation with applications to self-collision processing. ACM Transactions on Graphics, 2015, 34(6): Article No. 247. DOI: 10.1145/2816795.2818100.

[9] Calakli F, Taubin G. Ssd: Smooth signed distance surface reconstruction. Computer Graphics Forum, 2011, 30(7): 1993-2002. DOI: 10.1111/j.1467-8659.2011.02058.x.

[10] Hoff K E, Keyser J, Lin M, Manocha D, Culver T. Fast computation of generalized Voronoi diagrams using graphics hardware. In Proc. the 26th Annual Conference on Computer Graphics and Interactive Techniques, August 1999, pp.277-286. DOI: 10.1145/311535.311567.

[11] Kerwin T, Hittle B, Shen H W, Stredney D, Wiet G. Anatomical volume visualization with weighted distance fields. In Proc. Eurographics Workshop on Visual Computing for Biomedicine, July 2010, pp.117-124. DOI: 10.2312/VCBM/VCBM10/117-124.

[12] Frisken S F, Perry R N. Designing with distance fields. In Proc. the 2006 ACM SIGGRAPH International Conference on Computer Graphics and Interactive Techniques, July 30-August 3, 2006, pp.60-66. DOI: 10.1145/1185657.1185675.

[13] Bastos T, Celes W. GPU-accelerated adaptively sampled distance fields. In Proc. the 2008 IEEE International Conference on Shape Modeling and Applications, June 2008, pp.171-178. DOI: 10.1109/SMI.2008.4547967.

[14] Cao T T, Tang K, Mohamed A, Tan T S. Parallel banding algorithm to compute exact distance transform with the GPU. In Proc. the 2010 ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games, Feb. 2010, pp.83-90. DOI: 10.1145/1730804.1730818.

[15] Fischer I, Gotsman C. Fast approximation of high-order Voronoi diagrams and distance transforms on the GPU. Journal of Graphics Tools, 2006, 11(4): 39-60. DOI: 10.1080/2151237X.2006.10129229.

[16] Hsieh H H, Tai W K. A simple GPU-based approach for 3D Voronoi diagram construction and visualization. Simulation Modelling Practice and Theory, 2005, 13(8): 681-692. DOI: 10.1016/j.simpat.2005.08.003.

[17] Rong G, Tan T S. Variants of jump flooding algorithm for computing discrete Voronoi diagrams. In Proc. the 4th International Symposium on Voronoi Diagrams in Science and Engineering, July 2007, pp.176-181. DOI: 10.1109/ISVD.2007.41.

[18] Wu X, Liang X, Xu Q, Zhao Q. GPU-based feature preserving distance field computation. In Proc. the 2008 International Conference on Cyberworlds, Sept. 2008, pp.203-208. DOI: 10.1109/CW.2008.62.

[19] Zhou K, Gong M, Huang X, Guo B. Data-parallel octrees for surface reconstruction. IEEE Transactions on Visualization and Computer Graphics, 2011, 17(5): 669-681. DOI: 10.1109/TVCG.2010.75.

[20] Karras T. Maximizing parallelism in the construction of BVHs, octrees, and k-d trees. In Proc. the 4th Eurographics Conference on High-Performance Graphics, June 2012, pp.33-37. DOI: 10.2312/EGGH/HPG12/033-037.

[21] Bédorf J, Gaburov E, Zwart S P. A sparse octree gravitational N-body code that runs entirely on the GPU processor. Journal of Computational Physics, 2012, 231(7): 2825-2839. DOI: 10.1016/j.jcp.2011.12.024.

[22] Morrical N, Edwards J. Parallel quadtree construction on collections of objects. Computers & Graphics, 2017, 66: 162-168. DOI: 10.1016/j.cag.2017.05.024.

[23] Zhou K, Hou Q, Wang R, Guo B. Real-time KD-tree construction on graphics hardware. ACM Transactions on Graphics, 2008, 27(5): Article No. 126. DOI: 10.1145/1409060.1409079.

[24] Sramek M, Kaufman A E. Alias-free voxelization of geometric objects. IEEE Transactions on Visualization and Computer Graphics, 1999, 5(3): 251-267. DOI: 10.1109/2945.795216.

[25] Breen D E, Mauch S, Whitaker R T. 3D scan conversion of CSG models into distance volumes. In Proc. IEEE Symposium on Volume Visualization, Oct. 1998, pp.7-14. DOI: 10.1109/SVV.1998.729579.

[26] Kimmel R. Fast marching methods for computing distance maps and shortest paths. Technical Report, Lawrence Berkeley National Laboratory, 1996. https://escholarship. org/uc/item/7kx079v5, Nov. 2021.

[27] Yin K, Liu Y, Wu E. Fast computing adaptively sampled distance field on GPU. In Proc. the 19th Pacific Conference on Computer Graphics and Applications, Sept. 2011. DOI: 10.2312/PE/PG/PG2011short/025-030.

[28] Ségonne F, Pacheco J, Fischl B. Geometrically accurate topology-correction of cortical surfaces using nonseparating loops. IEEE Transactions on Medical Imaging, 2007, 26(4): 518-529. DOI: 10.1109/TMI.2006.887364.

[29] Tang M, Wang T T, Liu Z Y, Tong R F, Manocha D. I-Cloth: Incremental collision handling for GPU-based interactive cloth simulation. ACM Transaction on Graphics, 2018, 37(6): Article No. 204. DOI: 10.1145/3272127.3275005.

[1] Zhi-Guang Chen, Yu-Bo Liu, Yong-Feng Wang, Yu-Tong Lu. 基于GPU的大规模并行文件系统元数据加速[J]. 计算机科学技术学报, 2021, 36(1): 44-55.
[2] Sunghun Jo, Yuna Jeong, Sungkil Lee. 针对OBJ模型的GPU驱动可扩展解析器[J]. , 2018, 33(2): 417-428.
[3] Shi-Yu Jia, Zhen-Kuan Pan, Guo-Dong Wang, Wei-Zhong Zhang, CCF Xiao-Kang Yu. 嵌入任意三角网格的柔性体的稳定实时手术切割仿真[J]. , 2017, 32(6): 1198-1213.
[4] Wen-Jing Ma, Member, CCF, ACM, Kan Gao, Guo-Ping Long. 基于计算重用的GPU上stencil优化代码生成[J]. , 2016, 31(6): 1262-1274.
[5] Jing Li, Lei Liu, Yuan Wu, Xiang-Hua Liu, Yi Gao, Xiao-Bing Feng, Cheng-Yong Wu. 基于制导的GPU共享内存相关优化[J]. , 2016, 31(2): 235-252.
[6] Yun Liang, Shuo Wang. 基于赛道存储的寄存器堆在GPU上的性能优化[J]. , 2016, 31(1): 36-49.
[7] Tao Liu, Yi Liu, Qin Li, Xiang-Rong Wang, Fei Gao, Yan-Chao Zhu, De-Pei Qian. SEIP:基于分布式平台的高效图像处理系统[J]. , 2015, 30(6): 1215-1232.
[8] Peng Du, Jie-Yi Zhao, Wan-Bin Pan, Yi-Gang Wang. 虚拟装配过程中基于GPU的实时碰撞处理算法[J]. , 2015, 30(3): 511-518.
[9] Fatemeh Azmandian, Ayse Yilmazer, Jennifer G. Dy Javed A. Aslam, and David R. Ka. 一种利用GPU处理加速异常探测特征选择的方法[J]. , 2014, 29(3): 408-422.
[10] Yan Li, Yun-Quan Zhang, Yi-Qun Liu, Guo-Ping Long, Hai-Peng Jia. MPFFT: 自动调优GPU FFT库[J]. , 2013, 28(1): 90-105.
[11] Jie-Yi Zhao (赵杰伊), Min Tang* (唐敏), and Ruo-Feng Tong (童若锋), Member, CCF. 针对GPU并行解压缩的网格拓扑分块算法[J]. , 2012, 27(6): 1110-1118.
[12] Ming Wang (王明), Member, CCF, and Jie-Qing Feng (冯结青), Senior Member, CCF. 基于GPU的异质物体二维流形包围面提取[J]. , 2012, 27(4): 862-871.
[13] Xin-Hai Xu (徐新海), Student Member, CCF, ACM Xue-Jun Yang (杨学军), Senior Member, CCF, Member, ACM, IEEE Jing-Ling Xue (薛京灵), Senior Member, IEEE, Member, ACM Yu-Fei Lin (林宇斐), Student Member, CCF, ACM, and Yi-Song Lin (林一松). PartialRC:一种针对GPGPU高效故障恢复的部分复算方法[J]. , 2012, (2): 240-255.
[14] . 加速的并行纹理合成[J]. , 2007, 22(5): 761-769 .
[15] . 隐式曲面的反射和折射绘制[J]. , 2006, 21(2): 166-172 .
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] 周笛;. A Recovery Technique for Distributed Communicating Process Systems[J]. , 1986, 1(2): 34 -43 .
[2] 陈世华;. On the Structure of Finite Automata of Which M Is an(Weak)Inverse with Delay τ[J]. , 1986, 1(2): 54 -59 .
[3] 李万学;. Almost Optimal Dynamic 2-3 Trees[J]. , 1986, 1(2): 60 -71 .
[4] 冯玉琳;. Recursive Implementation of VLSI Circuits[J]. , 1986, 1(2): 72 -82 .
[5] 刘明业; 洪恩宇;. Some Covering Problems and Their Solutions in Automatic Logic Synthesis Systems[J]. , 1986, 1(2): 83 -92 .
[6] C.Y.Chung; 华宣仁;. A Chinese Information Processing System[J]. , 1986, 1(2): 15 -24 .
[7] 孙钟秀; 商陆军;. DMODULA:A Distributed Programming Language[J]. , 1986, 1(2): 25 -31 .
[8] 章萃; 赵沁平; 徐家福;. Kernel Language KLND[J]. , 1986, 1(3): 65 -79 .
[9] 王建潮; 魏道政;. An Effective Test Generation Algorithm for Combinational Circuits[J]. , 1986, 1(4): 1 -16 .
[10] 陈肇雄; 高庆狮;. A Substitution Based Model for the Implementation of PROLOG——The Design and Implementation of LPROLOG[J]. , 1986, 1(4): 17 -26 .
版权所有 © 《计算机科学技术学报》编辑部
本系统由北京玛格泰克科技发展有限公司设计开发 技术支持:support@magtech.com.cn
总访问量: