Abstract: In complex virtual environment, where there are massive moving objects, to improve the speed for collision detection in such case, a fast collision detection algorithm is proposed, which is based on uniform spatial subdivision and linear programming. In this algorithm, the computation complexity is reduced with a hybrid scheme, firstly, it uses uniform grid to determine the objects in the same voxels, then, collision detection, based on the scheme of linear programming, is performed accurately these objects which are in a same voxel. It can get the results very fast, even real-time. Compared with the classical algorithm, experimental results show that the algorithm can save test time, and improve the efficiency of collision detection effectively.

Key words: collision detection, uniform spatial subdivision, uniform grid, linear programming

摘要： 为提高在复杂环境下多物体碰撞检测的速度，提出基于空间划分和线性规划的快速碰撞检测算法。该算法首先用均匀网格法来确定处于同一单元格内的对象，然后利用线性规划的方法对处于同一单元格内的对象进行精确测试，并实时得到碰撞检测的结果。实验结果表明，与传统的碰撞检测算法相比，该算法可以缩短计算时间，提高了碰撞检测的效率。

关键词: 碰撞检测, 空间划分, 均匀网格, 线性规划