Research Of Collision Detection Algorithm Based On Closest Points

Collision detection(Collision Detection, CD) plays a decisive role in the virtual reality technology and Games. It has become a research hot in the field of physical simulation, haptic rendering, computer animation and computer visualization and so on. Accuracy and timeliness are two features of CD. High accuracy and good real-time of CD can increase the realism of the virtual environment, and enhance the sense of immersion. It has been the focus of the study how to improve the efficiency and accuracy of CD algorithms.The method of bounding box is the most effective in solving the problem of the early detection of CD. A bounding box represents a regular polygon or polyhedron, which approximately describes a object in the virtual environment. It is used in a large number of game engines to quickly detect collisions between game objects. In this thesis, 2D CD algorithms are investigated concretely, that is,(1) CD algorithms between the axial rectangular bounding box,(2) CD algorithms based on the separation axis theorem. The major research results of the thesis are as follows:1) The improved CD algorithm based on the axis-aligned bounding box is proposed,which is based on the most recent apex with the projection of a straight line to the point. We use the Euclidean distance to determine whether vertexes are surrounded by the axial rectangle. If one of the vertexes meet the conditions, then a collision occurs. If all of the closest vertex pairs don't meet the conditions, then no collision occurs. The improved algorithm reduces detection time of the effective collision and improve the speed of collision detection.2) By studying the characteristics of convex polygons and analysis of the advantages and disadvantages of the known algorithms, we propose the improved CD algorithm based on the separation axis theorem. We regard the normal of the edge of the nearest point as the potential separation axis, a straight line of the central point as the first stage judgment conditions. In the first stage, if the maximum and minimum values of two vertices of the detected convex polygon on a straight line projection does not occur overlap, then there is no collision.Otherwise, enter the second stage. The improved algorithm needs to judge at most five potential separation in the worst case, at least potential separation in the first phase in the best case. It is solved that the number of potential separation axis increase with the number of the convex polygon edges.Experimental data shows that the improved algorithms solve the problem of redundant inter-object collision detection and has a certain theoretical and practical significance.