More Web Proxy on the site http://driver.im/

research-article

Efficient collision detection using hybrid medial axis transform and BVH for rigid body simulation

Authors:

Qingqi HongAuthors Info & Claims

Volume 128, Issue C

https://doi.org/10.1016/j.gmod.2023.101180

Published: 01 July 2023 Publication History

Abstract

Medial Axis Transform (MAT) has been recently adopted as the acceleration structure of broad-phase collision detection. Compared to traditional BVH-based methods, MAT can provide a high-fidelity volumetric approximation of 3D complex objects, resulting in higher collision culling efficiency. However, due to MAT’s non-hierarchical structure, it may be outperformed in collision-light scenarios because several cullings at the top level of a BVH may take a large number of cullings with MAT. We propose a collision detection method that combines MAT and BVH to address the above problem. Our technique efficiently culls collisions between dynamic and static objects. Experimental results show that our method has higher culling efficiency than pure BVH or MAT methods.

References

[1]

Bergen G.v.d., Efficient collision detection of complex deformable models using AABB trees, J. Graph. Tools 2 (4) (1997) 1–13.

Digital Library

[2]

Hubbard P.M., Collision detection for interactive graphics applications, IEEE Trans. Vis. Comput. Graphics 1 (3) (1995) 218–230.

[3]

de Berg M., Comba J., Guibas L.J., A segment-tree based kinetic BSP, in: Proceedings of the Seventeenth Annual Symposium on Computational Geometry, SCG ’01, Association for Computing Machinery, New York, NY, USA, 2001, pp. 134–140.

[4]

Lan L., Luo R., Fratarcangeli M., Xu W., Wang H., Guo X., Yao J., Yang Y., Medial elastics: Efficient and collision-ready deformation via medial axis transform, ACM Trans. Graph. 39 (3) (2020) 1–17.

[5]

Volino P., Thalmann N.M., Efficient self-collision detection on smoothly discretized surface animations using geometrical shape regularity, Comput. Graph. Forum (1994).

[6]

Wang T., Liu Z., Tang M., Tong R., Manocha D., Efficient and reliable self-collision culling using unprojected normal cones, Comput. Graph. Forum 36 (8) (2017).

[7]

Tang M., Curtis S., Yoon S.-E., Manocha D., Interactive continuous collision detection between deformable models using connectivity-based culling, in: SPM ’08: Proceedings of the 2008 ACM Symposium on Solid and Physical Modeling, ACM, New York, NY, USA, 2008, pp. 25–36.

[8]

Curtis S., Tamstorf R., Manocha D., Fast collision detection for deformable models using representative-triangles, in: Proceedings of the 2008 Symposium on Interactive 3D Graphics and Games, in: I3D ’08, Association for Computing Machinery, New York, NY, USA, 2008, pp. 61–69.

[9]

Tang M., Manocha D., Yoon S.-E., Du P., Heo J.-P., Tong R., VolCCD: Fast continuous collision culling between deforming volume meshes, ACM Trans. Graph. 30 (2011) 111:1–111:15.

[10]

Provot X., Collision and self-collision handling in cloth model dedicated to design garments, in: Thalmann D., van de Panne M. (Eds.), Computer Animation and Simulation ’97, Springer Vienna, Vienna, 1997, pp. 177–189.

[11]

Brochu T., Edwards E., Bridson R., Efficient geometrically exact continuous collision detection, ACM Trans. Graph. 31 (4) (2012) 1–7.

[12]

Wang H., Defending continuous collision detection against errors, ACM Trans. Graph. 33 (4) (2014) 1–10.

[13]

Song S., Lan L., Yao J., Guo X., Continuous collision detection with medial axis transform for rigid body simulation, Commun. Inf. Syst. 22 (1) (2022) 53–78.

[14]

Gottschalk S., Lin M.C., Manocha D., OBBTree: A hierarchical structure for rapid interference detection, in: Computer Graphics and Interactive Techniques, ACM, 1996, pp. 171–180.

[15]

James D.L., Pai D.K., BD-tree: output-sensitive collision detection for reduced deformable models, ACM Trans. Graph. (TOG) 23 (3) (2004) 393–398.

[16]

Zachmann G., Minimal hierarchical collision detection, in: ACM Symposium on Virtual Reality Software and Technology, ACM, 2002, pp. 121–128.

[17]

Krishnan S., Gopi M., Lin M., Manocha D., Pattekar A., Rapid and accurate contact determination between spline models using ShellTrees, in: Computer Graphics Forum, 17, Wiley Online Library, 1998, pp. 315–326.

[18]

Larsson T., Akenine-Möller T., A dynamic bounding volume hierarchy for generalized collision detection, Comput. Graph. 30 (3) (2006) 450–459.

[19]

M.A. Otaduy, O. Chassot, D. Steinemann, M. Gross, Balanced Hierarchies for Collision Detection between Fracturing Objects, in: 2007 IEEE Virtual Reality Conference, 2007, pp. 83–90.

[20]

Yoon S.-E., Curtis S., Manocha D., Ray tracing dynamic scenes using selective restructuring, in: Proceedings of the 18th Eurographics Conference on Rendering Techniques, EGSR ’07, Eurographics Association, Goslar, DEU, 2007, pp. 73–84.

[21]

Lauterbach C., Garland M., Sengupta S., Luebke D.P., Manocha D., Fast BVH construction on gpus, Comput. Graph. Forum 28 (2) (2009) 375–384.

[22]

Kopta D., Ize T., Spjut J., Brunvand E., Davis A., Kensler A., Fast, effective BVH updates for animated scenes, in: Proceedings of the ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games, in: I3D ’12, Association for Computing Machinery, New York, NY, USA, 2012, pp. 197–204.

[23]

Barbiĉ J., James D.L., Subspace self-collision culling, ACM Trans. Graph. (TOG) 29 (4) (2010) 81.

[24]

Zheng C., James D.L., Energy-based self-collision culling for arbitrary mesh deformations, ACM Trans. Graph. (TOG) 31 (4) (2012) 98.

[25]

Wong S.-K., Lin W.-C., Hung C.-H., Huang Y.-J., Lii S.-Y., Radial view based culling for continuous self-collision detection of skeletal models, ACM Trans. Graph. 32 (4) (2013) 1–10.

[26]

Yap C.K., Sharma V., Robust geometric computation, in: Kao M.-Y. (Ed.), Encyclopedia of Algorithms, Springer New York, New York, NY, 2016, pp. 1860–1863.

[27]

Tang M., Tong R., Wang Z., Manocha D., Fast and exact continuous collision detection with bernstein sign classification, ACM Trans. Graph. 33 (6) (2014) 1–8.

[28]

Lan L., Yang Y., Kaufman D., Yao J., Li M., Jiang C., Medial IPC: Accelerated incremental potential contact with medial elastics, ACM Trans. Graph. 40 (4) (2021).

Recommendations

An Image-Space Approach for Collision Detection Between Multiple Volumes and a Surface

Collision detection has been studied for scenes containing only polygonal objects surfaces or only volumes. With the evolution of the graphics hardware, surfaces and volumes can be rendered together, demanding new challenges for the area of collision ...
Fast continuous collision detection among deformable models using graphics processors

We present an interactive algorithm to perform continuous collision detection between general deformable models using graphics processors (GPUs). We model the motion of each object in the environment as a continuous path and check for collisions along ...
Hybrid image-based collision detection in Java 3D

Collision detection is highly important in computer graphics and virtual reality. Most collision detection methods are object-based, relying on testing the geometrical interference of objects, and their performance therefore depends on the geometrical ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Graphical Models

Graphical Models Volume 128, Issue C

Jul 2023

45 pages

ISSN:1524-0703

Issue’s Table of Contents

The Author(s).

Publisher

Academic Press Professional, Inc.

United States

Publication History

Published: 01 July 2023

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

0
Total Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents