关键词: 碰撞检测, 拓扑层次图, 方向包围盒树, A*算法

Abstract: To improve realtime and accurate performance of collision detection in virtual environment, a collision detection method based on topology hierarchy graph was proposed. Firstly, the original model was separated into convex set using the relationship of topology, and combining the merit of convex set and Oriented Bounding Box (OBB), a topology hierarchy graph for model was constructed, which effectively eliminated nonintersected bounding box and enhanced detection accuracy. By using intelligent search algorithm-improved A* algorithm to search for Potential Collision Sets (PCS), thus the speed and accuracy of collision detection were improved. The experimental results show that the algorithm has higher accuracy and efficiency for realtime collision detection in virtual environment.

Key words: collision detection, topology hierarchy graph, Oriented Bounding Box (OBB) tree, A* algorithm