Research And Implementation Of Collision Detection Algorithm In Virtual Environment

Collision detection in virtual environment is one of the key problemsin many fields,including computer graphics,robot path planning,virtual assembly and computer animation,etc.Its basic task is to detect whether collisions occur between models in a virtual environment.Theefficient collision detection algorithmplays avery important role in enhancingthe immersion and improvingthe authenticityofthe virtual environment.The 3D models used in the virtual environment are becoming more and more complex,which makes the collision detection between the models more complicated.How to improve the efficiency of collision detection algorithm is the focus of current research.Based on the existing framework of the collision detection system,this paper mainly focuses on the rough detection algorithm and the accurate detection algorithm in the collision detection process.On the basis of deep understanding of the bounding volume hierarchyand triangle-triangle intersectiontest method,we present new improved methods for the collision detection algorithm based on bounding volume hierarchy and triangle-triangle intersectiontest algorithm based on OBB bounding boxrespectively,anda new real-time collision detection system is designed.For the bounding volume hierarchy,this paper presents a dualAABB-OBBboxstructure.Compared with the traditional algorithm,the newalgorithm has the following improvements:(1)Based on principal component analysis,we add the idea of area-weighted method to the OBB;(2)It is proved that the intersection detection of different types of bounding boxes in AABB-OBB box structure is strongly related,so,only five potential separation axes are needed for the OBB-OBB intersection test in the new algorithm;(3)In the process of hierarchy traversal,aheuristic methodbased Depth-First traversal algorithm is used.For the accurate intersection test,this paper presents a triangle-triangle intersection test algorithm suitable for OBB structure.Thenew algorithm replaces the vertex coordinates of the triangles with a rectangular data information,and reuses the coordinate transformation matrixcalculated in the rough detection phase,so a great deal of triangular vertex coordinate transformation is avoidedin the testing process.At the same time,the vertices of the triangle after the replacement contain a number of zero values,which further reduces the amount of computation in the testing process.The experimental results show that the improved algorithm has better performance than the traditional algorithm.