Research On Heterogenenous Accelerating For Collision Detection In Virtual Reality

In recent years the development of GPU general computing provides favorable conditions for improving algorithm in virtual reality field, and provides opportunities for parallelism solving efficiency problem. Heterogeneous computing environment which composed of CPU+GPU provides a better way for virtual reality algorithm to solve the problem of real-time.Virtual reality technology is widely used in computer games, the computer aided teaching, computer aided design, and other fields, and VR has gotten huge development in recent years. As the request of people to scene fidelity and high interactive in virtual reality system enhances increasingly, the data calculation quantity that system requirements have improved significantly. Among them, the calculation of collision detection in the scene is an important part of the whole calculation. The solution for real-time collision detection calculation is often the key element for the high-efficient virtual reality system.Collision detection is a process that judge whether two or more object have intersection or not. Collision detection study is an important branch of computer graphics, virtual reality, and medical simulation field. In some situation, the moving objects don't allow occurrence and moving through each other in the virtual scene map, real-time object of collision detection algorithm is essential to solve this kind of problem.BVH and space division technology are the basic methods for collision detection algorithm; they reduce the computational complexity of collision detection process from two aspects. Although there were some measured valuable achievements in collision detection this years, but as the scale of the scene and model growing complexity, meanwhile, human-computer interaction of real-time and precision requirements from the users increasing fast, core calculate method requires higher efficiency. But classic BVH and space division technology are unfit for the GPU accelerated calculation directly, both of them should adapt to the need for the hardware multi-processing GPU.This thesis focus on the collision detection problem in virtual scene, analyzed and studied the improvement of test efficiency in complex scene, based on the thorough understanding of various basic collision detection algorithm, combined with NVIDIA CUDA general computing platform, improved the algorithm with heterogeneous programming idea as the following aspects:First, we analyzed the data structure of object's bounding box hierarchical tree and triangle ball data sets in detail, then transformed the complex problem to several sub problems based on the CPU+GPU heterogeneous calculation thoughts, discussed the preliminary test and large scale objects detection in the wide phase. In the broad phase and the narrow phase collision detection, algorithm improves the CPU execution part to adapt to the input data of GPU requirements, isolates computation-intensive parts for GPU; Then, creates suitable intersection test logic for GPU processing, then maps the intersect test to CUDA threads execute model; Finally, performs efficiency optimization according to the GPU memory model. Specifically, in the broad phase collision detection, the CPU is responsible for the construction of the sphere bounding box hierarchical tree and traversal; GPU is responsible for bounding box hierarchical tree-triangle set parallel intersection test, eliminates the impossible intersection of triangle sets, gets the potential intersection set; In the narrow phase collision detection, GPU uses the previous stage data for input, performs precise parallel intersection test for the set of triangle, and eventually gets test results. For multiple objects scene, first, groups the objects at the CPU part, then, performs detection between multiple objects and takes many times, furthermore, utilizes the kernel concurrent execution to enhance the efficiency.Comparing with the Rapid and OBBs CG algorithm, the results show that:in real-time aspect heterogeneous collision detection algorithm has more outstanding performance, and as the ascension of scene model complexity, the processing time growth leisurely, also has the high stability. At the same time, the heterogeneous collision detection method can guarantee real time performance in the scene that has multiple objects.