基于拓扑层次图的碰撞检测算法

Collision detection based on topology hierarchy graph

为了提高虚拟环境中碰撞检测的实时性和精确性,提出了一种基于拓扑层次图的碰撞检测方法。利用拓扑结构的连接关系将模型分割成凸集;然后利用凸集较强的适应性和OBB紧密性好的优点构造包围盒的拓扑层次图,提高了剔除不相交包围盒的效率,减少了检测时间;利用智能搜索算法———改进的A*算法搜索潜在碰撞集(PCS),进一步提高相交检测的速度和准确性。实验表明,该算法具有较高的速度和精度,能够满足复杂虚拟环境碰撞检测实时性和精确性的要求。

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.