基于空间剖分和分类遍历的碰撞检测算法

Collision detection algorithm based on space subdivision and classified traversal

针对碰撞检测实时性与精确性不高的问题,提出一种基于空间剖分和分类遍历的碰撞检测算法。首先在空间剖分阶段利用八叉树空间剖分剔除不相交的物体对,在剖分子空间内构建混合层次包围盒,利用分类遍历的方法对层次包围盒进行遍历,有效减少了相交测试的次数。实验表明,该算法有效缩短了碰撞检测所需时间,在复杂环境下算法优势明显。

In order to solve the shortcoming of real-time and accuracy in collision detection, a novel collision detection algorithm based on space subdivision and classified traversal was proposed. In the space subdivision stage, the octree division was used to get rid of object pairs without intersecting. Then Create hybrid bounding box in the subspace and use classified traversal method to traverse them, aim to reduce the times of intersect tests efficiently. Experimental analyses show that this algorithm can reduce the time cost of collision detection, especially in complex situation.