The Design And Implementation Of The Rigid Body Collision Detection Algorithm On A Hybrid Hierarchical Bounding Volume

With the constant development of computer hardware, a new type of human-computer interaction technology-Virtual Reality(VR), has gradually become a hot issue. It requires the targets in virtual world to possess their actual physical features. So it is indispensable for a collision detection with good performance to have VR technology with high fidelity. Except for Virtual Reality, there are many other regions concerning Collision Detection(CD), such as robot technology,animated simulation,computer games and computer graphics.There are two factors to assess the performance of collision detection algorithm: real-time performance and accuracy. To real-time performance, certain refresh rate(at least 24 frames per second) should be detected to meet the requirements for visual display. Accuracy requires all collision at certain time be detected in the virtual environment, and the position of collision be located accurately. Over the years, there emerged many algorithms about collision detection, while they focus on different aspects.This paper fully studies current collision detection algorithms, summarizes their principle, features and limitations, and designs a hybrid hierarchical bounding volume collision detection algorithm of spatial domain based on real-time performance. The main work and study contents are as follows:1.This paper studies and analyzes all kinds of collision detection algorithms by classifying them into temporal and spatial domain. Focusing on bounding volume hierarchy algorithm based on spatial domain, Oriented bounding box(OBB) hierarchical tree is analyzed and constructed according to different aspects, such as intersection test principle, the selection of bounding box, partition rules of objects, the selection of hierarchy tree degree, constructing sequence of hierarchy tree and updating of bounding volume tree.2.Aimed at the problems in traditional bounding volume hierarchies, a hybrid bounding volume hierarchy is proposed based on the idea of OBB hierarchical algorithm. It combines Sphere bounding volume and K-Dops bounding volume.3.This paper constructs two sets of collision detection systems, conducts collision detection experiments by traditional OBB hierarchical tree algorithm and hybrid bounding hierarchical volume algorithm respectively, obtains the detection time of both algorithms with same steps, analyzes the experiment results and makes conclusion.The experiment results show that the real-time performance of hybrid bounding hierarchical volume algorithm is better than traditional OBB hierarchical tree algorithm, and it can adjust the height of two different bounding box layer according to the needs in specific experiment scenario. It is more flexible for the practical application of virtual reality technology.