Journal of Computer Science and Technology ›› 2022, Vol. 37 ›› Issue (3): 731-740.doi: 10.1007/s11390-022-0331-x

Special Issue: Computer Graphics and Multimedia

• Regular Paper • Previous Articles    

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.

PDF (PC)

29

Supplement

1

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] Shi-Yu Jia, Zhen-Kuan Pan, Guo-Dong Wang, Wei-Zhong Zhang, CCF Xiao-Kang Yu. Stable Real-Time Surgical Cutting Simulation of Deformable Objects Embedded with Arbitrary Triangular Meshes [J]. , 2017, 32(6): 1198-1213.
[2] Hsien-Hsi Hsieh(谢咸熙), Chin-Chen Chang(张勤振), Wen-Kai Tai(戴文凯), and Han-Wei Shen(沈汉威). Novel Geometrical Voxelization Approach with Application to Streamlines [J]. , 2010, 25(5): 895-904.
[3] Gabriel Falcão, Student Member, IEEE, Shinichi Yamagiwa, Member, IEEE, Vitor Silva, and Leonel Sousa, Member, ACM, Senior Member, IEEE. Parallel LDPC Decoding on GPUs Using a Stream-Based Computing Approach [J]. , 2009, 24(5): 913-924.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] Zhou Di;. A Recovery Technique for Distributed Communicating Process Systems[J]. , 1986, 1(2): 34 -43 .
[2] Chen Shihua;. On the Structure of Finite Automata of Which M Is an(Weak)Inverse with Delay τ[J]. , 1986, 1(2): 54 -59 .
[3] Li Wanxue;. Almost Optimal Dynamic 2-3 Trees[J]. , 1986, 1(2): 60 -71 .
[4] Feng Yulin;. Recursive Implementation of VLSI Circuits[J]. , 1986, 1(2): 72 -82 .
[5] Liu Mingye; Hong Enyu;. Some Covering Problems and Their Solutions in Automatic Logic Synthesis Systems[J]. , 1986, 1(2): 83 -92 .
[6] C.Y.Chung; H.R.Hwa;. A Chinese Information Processing System[J]. , 1986, 1(2): 15 -24 .
[7] Sun Zhongxiu; Shang Lujun;. DMODULA:A Distributed Programming Language[J]. , 1986, 1(2): 25 -31 .
[8] Zhang Cui; Zhao Qinping; Xu Jiafu;. Kernel Language KLND[J]. , 1986, 1(3): 65 -79 .
[9] Wang Jianchao; Wei Daozheng;. An Effective Test Generation Algorithm for Combinational Circuits[J]. , 1986, 1(4): 1 -16 .
[10] Chen Zhaoxiong; Gao Qingshi;. A Substitution Based Model for the Implementation of PROLOG——The Design and Implementation of LPROLOG[J]. , 1986, 1(4): 17 -26 .

ISSN 1000-9000(Print)

         1860-4749(Online)
CN 11-2296/TP

 Home
Editorial Board
Author Guidelines
Subscription		 Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
Tel.:86-10-62610746
E-mail: jcst@ict.ac.cn
 
  Copyright ©2015 JCST, All Rights Reserved