An improved optimal algorithm for collision detection of hybrid hierarchical bounding box

PubDate: February 2021

Teams: Guangzhou Nanyang Polytechnic College

Writers: Baiqiang Gan & Qiuping Dong

PDF: An improved optimal algorithm for collision detection of hybrid hierarchical bounding box

Abstract

Collision detection is currently a hot issue in virtual reality and other fields. The efficiency and accuracy of collision detection directly affect the real-time update effect of the virtual reality environment, and it is also an important indicator that affects the user’s interactive experience. In a complex virtual reality scene, if the traditional collision detection algorithm (Sphere-OBB) is adopted and the tree structure traversal is used to realize the bounding box traversal detection, the accuracy remains unchanged, but the detection complexity is reduced. If the RAPID collision detection algorithm is used, the separated axis test method and the two-layer hybrid hierarchical surrounding tree structure are used, although the amount of calculation is large, the detection efficiency is improved. Using the separation axis (SAT) algorithm and using the separation axis theorem to determine the vector axis can save a lot of calculation time. The purpose of this research is to propose an improved hybrid-level bounding box collision detection optimization algorithm (ASO) based on the traditional hybrid-level bounding box collision detection algorithm. Firstly, based on the spatio-temporal correlation theory, the hybrid hierarchical bounding box hierarchical tree structure is improved to AABB and OBB from top to bottom. The synchronous descent rule is used to realize the traversal of nodes, and then the triangle area weighting method is used to improve the calculation method of the bottom OBB bounding box node center, solve the bounding box vertex covariance matrix, and improve the efficiency and accuracy of collision detection. The experimental results show that the algorithm proposed in this paper is 35.6% faster than the RAPID detection speed and 29.9% faster than the separation axis (SAT) detection speed under the same accuracy. In the multi-object collision detection, compared with the latest research, the algorithm in this paper shortens the intersection detection time, improves the collision detection efficiency, and meets the real-time update requirements of complex virtual reality scenes.