Research On Continuous Collision Detection Algorithm In Virtual Reality

Collision detection in the virtual environment is a classic topic in research area of haptic rendering, physical simulation, robot path planning, computer games and CAD/CAM. The real-time and high accuracy continuous collision detection plays a very important role in enhancing the immersion and improving the authenticity of the virtual environment. Since most of the virtual reality systems require real-time human-computer interaction. Only when the speed of continuous collision detection is fast enough, the systems can achieve the goal of the real-time interaction. All collisions between the primitives in the virtual environment need the accurate results, otherwise there is not realistic. Therefore, how to improve the speed and accuracy of the continuous collision detection algorithm has always been the focus of the research.After a comprehensive understanding for a variety of collision detection algorithm, the paper studies the continuous collision detection algorithm between the deformable objects. In this paper, the main research contents are described as follows:This paper analyzes several factors those need to be considered in the process of the design and implementation of the continuous collision detection algorithm between the deformable objects. First of all, for the representation of the object model, the algorithms proposed in this paper apply the triangular mesh model. Secondly, the whole continuous collision detection process is divided into two phases, those are the broad-phase and the narrow-phase. In the broad-phase the algorithms put the objects those may be colliding in a group, and then in the narrow-phase the algorithms perform pair-wise tests within these groups. In the narrow-phase the algorithms use vertex-face and edge-edge elementary tests between the primitives. Finally, the robustness problems that may occur are analyzed, and then some measures are taken to avoid these problems.This paper gives a detailed description of the k-DOPs bounding box and the bounding volume hierarchies. Bounding volume hierarchies can be used to accelerate the broad-phase and the narrow-phase of the continuous collision detection. In the broad-phase, the hierarchy of all the objects in the virtual environment can be used for collision detection, thereby it can excludes those objects that are not colliding; In the narrow-phase, the hierarchy of all the primitives of the object can be used for collision detection, thereby it can excludes those primitives that are not colliding. This paper also describes the construction methods of the bounding volume hierarchies, the traversal methods of the intersection test and the update methods of the bounding volume hierarchies of the deforming objects.This paper gives a detailed description of a self-collision detection algorithm. The algorithm improves the curvature test and contour test of the self-collision detection. The bounding volume hierarchy of the deformable objects is built by the bottom-up method based on the adjacency information between its geometric primitives. In the process of building the bounding volume hierarchy, the minimum normal cone of the sub-triangle mesh area of each node is calculated. Apply the minimum normal cone to the contour test to avoid the pair-wise test of the contour projection lines. Moreover, according to the adjacency information between sub-triangular mesh area, the algorithm can reduce a large number of unnecessary collision detection during the self-collision detection process. Finally, the experimental results demonstrate that the algorithm can improve the speed of self-collision detection.This paper gives a detailed description of a subspace culling algorithm for continuous collision detection. When two primitives are very close and in fact there is no collision between them, they may produce a false positive in the process of continuous collision detection. In order to solve this problem, at first we use a culling algorithm based on the one-dimensional subspace, and then use the culling algorithm based on the two-dimensional subspace for the remaining primitive-pair. If two primitives in the three-dimensional space are not colliding in the one-dimensional subspace or two-dimensional subspace, then they don’t collide each other in the three-dimensional space. The experimental results show that the culling algorithm can significantly reduce the number of false positives in the continuous collision detection, thus the algorithm can avoid solving a large number of the cubic equations to improve the speed of continuous collision detection.