Optimization And Parallelization Of Hierarchical Bounding Box Collision Detection Algorithm

With the development of virtual reality and the improvement of people's requirement of experience, the instantaneity and accuracy of collision detection is also increased. The hierarchical bounding box collision detection algorithms divide object into different scale of bounding box, so these algorithm has higher accuracy and lower instantaneity. This paper optimizes the traditional hierarchical bounding box collision detection algorithm and implements the algorithm's parallelization using GPU, accelerating the speed of collision detection algorithm. The following parts are included in this article:(1) Based on the existing collision detection algorithm, this paper summarizes the collision detection algorithm based on space decomposition and the collision detection algorithm based on hierarchical bounding box, analyzing and comparing the advantages and disadvantages of these collision detection algorithm.(2) The algorithm of constructing the hierarchical bounding box tree is optimized. This paper analyzes how to construct the hierarchical bounding box tree using Huffman method, and proposes optimization scheme of using balanced binary tree to construct hierarchical bounding box tree.(3) The parallel algorithm of constructing hierarchical bounding box tree with balanced binary tree is realized. Firstly, the feasibility analysis of the parallel algorithm is given, then parallel algorithm is realized on the CUDA platform.(4) The parallel algorithm of hierarchical bounding box collision detection algorithm is realized. By analyzing the way of double traversal hierarchical bounding box tree, arming at the shortcoming of invalid traversal increased time consuming, this paper proposes the solution of traverse tree using parallel way. Traverse hierarchical bounding box tree using parallel way can cover the time consuming of invalid traversal, and increase the speed of collision detection algorithm.The experimental results show that the optimized hierarchical bounding box collision detection algorithm has higher efficiency, which can improve the speed of constructing and traversing the hierarchical bounding box tree.