Abstract: To improve the accuracy and real-time of collision detection algorithm, this paper proposes a fast collision detection algorithm based on improved particle swarm optimization. This paper introduces PSO algorithm into random collision detection problems and reduces the search space of particles by using hybrid hierarchical bounding. In the virtual space complex collision detection algorithm is converted to a particle searching problem of the two-dimensional discrete space by using features sampling. In order to improve the accuracy of the algorithm effectively standard particle swarm algorithm has been optimized：accelerate the convergence speed of later period by removing velocity item and accelerate the particles to overstep the local extreme value by introducing Gaussian disturbance. Experiments verify that the algorithm can meet the application requirements of collision detection with higher precision and real time.

Key words: collision detection, hybrid bounding box, particle swarm optimization, evolutionary computation, Gaussian disturbance

摘要： 针对碰撞检测算法精度低、实时性差等问题，提出了一种基于改进粒子群的快速碰撞检测算法。将粒子群优化算法引入到随机碰撞检测问题中，通过混合层次包围盒缩小粒子搜索空间。利用特征采样将虚拟空间内复杂的碰撞检测转换为二维离散空间中的搜索问题。算法对标准粒子群方程进行了优化处理，通过去除速度项来加快算法后期的收敛速度，在算法中引入高斯扰动缩短粒子跳出局部最优的时间，有效提高了算法的精度。通过实验验证，该算法具有较高的精度、实时性好，能够满足碰撞检测的应用要求。

关键词: 碰撞检测, 混合包围盒, 粒子群优化, 进化计算, 高斯扰动