An Improved Collision Detection Algorithm Based on GPU

Abstract:

In order to improve the speed of collision detection between objects in the large-scale and complex scene, this paper proposed an improved collision detection algorithm based on GPU, In this method, we first divided the virtual space into several grids to rule out the impossible intersecting objects rapidly using the GPU acceleration technology; secondly, we adopted parallel technology to build K - DOP bounding boxes for the objects in the same grids and then detected whether the K - DOP bounding boxes intervene or collide to conform the potential colliding primitive pairs; Finally we traveled the final triangle intersection tests on GPU. Compared to the traditional K-DOP compared bounding box collision detection, The algorithm can effectively improve the real-time collision detection.

• Periodical: Applied Mechanics and Materials (Volumes 687-691)
• Pages: 3893-3896
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.687-691.3893
• Online since: November 2014
• Authors: Ming Quan Wang, Wei Zhao*, Hui Yan Qu
• Keywords: Collision Detection, Human-Computer Interaction, K-DOP Bounding Boxes, Parallel Technology

References

[1] Wei Ying-mei, Wu Quan-yuan, Shi Jiao-ying. Collision detection in the direction of the convex hull of a fixed box surrounded Research . Journal of Software, 2001, 12 (7): 1056-1063.

[2] L in M C, Manocha D. Fast interference detection between geometric models [J] The Visual Computer, 1995, 11 (10) 542-561.

DOI: 10.1007/bf02434040

[3] Gilbert E G, Johnson D W , KeerthiSS. A fast procedure for computing the distance between complex objects in three dimensional space [ J ]. IEEE Trans on Robotics and Automation, 1988, 4 (2) : 193-203.

DOI: 10.1109/56.2083

[4] Ming C Ling Efficient Collision Detection for Animation and Robotics[D]phD thiesis. Department of Electrical Engineering and Computer Science, University of California, Berkeley 1993-12.

[5] James T Klosowski, Martin Held et al Efficient Collision Detection Using Bounding Volume Hierarchies of k-DOPS[J] IEEE Trans Visualization and Computer Graphics 1998: 421-35.

DOI: 10.1109/2945.675649

[6] Zhou Pei-yuan computational geometry - algorithm analysis and design [M] Beijing: Tsinghua University Press, (2000).

[7] Dong Feng Wang Tong-yang, virtual environment fast collision detection algorithm [J] Computer Engineering and Applications.

[8] Cameron S. A Comparison of two fast algorithms for computing the distance between convex polyhedron [J]. IEEE transactions on Robotics and Automation, 1997, 13(6) 915-920.

DOI: 10.1109/70.650170