Abstract: In the problem of collision detection, the speed and accuracy is one of the key challenges for many computer application programs. A new detection algorithm is proposed that can improve the detection speed and the accuracy, it is based on two phases：Firstly, in the preprocessing detection stage, uniformly dissect the space which is measured to determine the adjacent objects and constructs the AABB-OBB mixed hybrid bounding box. The structure of the bounding box and the task structure are optimized which accelerate the ergodic process; then, in detailed test phase, a new calculation of coordinate system based on M?ller algorithm is improved. The space geometric triangle is projected and reduced aiming at the space problems in two-dimensional plane, so that the total calculation of the algorithm is reduced. Compared with the traditional algorithm, the experimental results show that the detection speed of the new algorithm is greatly improved under the premise of ensuring the accuracy of collision detection.

Key words: collision detection, hybrid bounding box, task structure, triangle-triangle intersection, coordinate system transformation, dimension reduction

摘要： 碰撞检测的速度与准确性是众多计算机应用程序的关键难题之一。为了提高检测速度同时兼顾准确性，将检测分为两个阶段：预处理检测阶段首先均匀剖分待测空间以确定相邻对象，然后对相邻的对象构造AABB-OBB混合层次包围盒，改进包围盒的构造方式，同时改善任务结构加速遍历过程；详细检测阶段在M?ller算法基础上加以改进，构造新的计算坐标系，对空间几何三角形进行投影降维，在二维平面上解决空间问题，从而减少算法总的计算量。实验结果表明，在保证碰撞检测准确性的前提下其检测速度大幅提高。

关键词: 碰撞检测, 混合包围盒, 任务结构, 三角形相交, 坐标系变换, 降维