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

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