AI Chat Paper
Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.
{{lang === 'zh_CN' ? '文章概述' : 'Summary'}}
{{lang === 'en_US' ? '中' : 'Eng'}}
Chat more with AI
Powered by AMiner. Clicking this button will take you away from SciOpen.
Home Journal of Computer Science and Technology Article
Article Link
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
Regular Paper

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

Laboratory of Geometry, Image and Video Processing Enterprise Intelligent Computing, College of Computer Science and Technology, Zhejiang University, Hangzhou 310007, China
Geometric Algorithms for Modeling, Motion, and Animation Laboratory, University of Maryland, Maryland 20742, U.S.A.
Show Author Information

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.

Keywords

distance fielddeformable objectgraphics processing unit (GPU)octreebounding volume hierarchy

Electronic Supplementary Material

Download File(s)
jcst-37-3-731-Highlights.pdf (67 KB)

References

[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref
[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.
Crossref
[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.
Crossref
[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.
Crossref
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref
[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.
Crossref
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
Journal of Computer Science and Technology
Volume 37 Issue 3,
May 2022
Pages 731-740
DOI: 10.1007/s11390-022-0331-x
Cite this article:
Chen X-R, Tang M, Li C, et al. BADF: Bounding Volume Hierarchies Centric Adaptive Distance Field Computation for Deformable Objects on GPUs. Journal of Computer Science and Technology, 2022, 37(3): 731-740. https://doi.org/10.1007/s11390-022-0331-x

548

Views

1

Crossref

1

Web of Science

1

Scopus

0

CSCD

Altmetrics
Received: 31 March 2020
Accepted: 02 April 2022
Published: 31 May 2022
©Institute of Computing Technology, Chinese Academy of Sciences 2022
Return