Abstract: In order to meet the high requirements of real-time collision detection in increasingly complex virtual environment, a fast collision detection algorithm based on image space was proposed. It made efficiently use of the Graphics Processing Unit (GPU). Based on the hierarchical binary tree and the collision detection between Oriented Bounding Boxes (OBB), the algorithm could quickly eliminate disjoint bumps of the virtual scene. With the potential collision set, the efficiency of the algorithm has a significantly improvement on the basis of RECODE algorithm. The experimental results show that the algorithm achieves good results, and has a higher efficiency, especially in a highly complex virtual environment.

Key words: collision detection, image space, hierarchical binary tree, Oriented Bounding Box (OBB), depth buffer, stencil buffer

摘要： 为了满足日益复杂的虚拟环境中碰撞检测的高实时性要求，提出一种基于图像空间的快速碰撞检测算法，有效利用了图形处理器(GPU)的加速功能。该算法以基于物体空间的凸块层次二叉树技术及方向包围盒(OBB)之间的碰撞检测为前提，可快速排除场景中明显不相交的凸块;然后通过生成的凸块潜在碰撞检测集，在RECODE算法的基础上，得到一种运行效率更高的碰撞检测算法。实验结果表明，在同等复杂的虚拟环境中，尤其是复杂度较高的虚拟环境中，该算法具有更高的碰撞检测实时性，取得了良好的效果。

关键词: 碰撞检测, 图像空间, 层次二叉树, 方向包围盒, 深度缓存, 模板缓存