Abstract: Aiming at the accuracy and instantaneity of collision detection algorithm, a collision detection algorithm which is fused with intelligent algorithm is proposed. On the basis of random collision detection, a hybrid algorithm which is mixed quantum behavior particle swarm optimization algorithm and differential evolution algorithm is used to search with the hybrid bounding technique using to reduce the particle search space. The local attractor is used as the basis of differential variation, and the convergence rate of the algorithm is accelerated while expanding the diversity of the population, which effectively solves the problems of the traditional intelligent algorithm not suitable for the discrete space computation and the premature convergence. Aiming at the characteristics of random collision particle search space, the introduction of hybrid algorithm greatly improves the detection efficiency of collision detection algorithm, and solves the phenomenon of puncture and omission in the detection process. The experimental results show that this method improves the real-time and accuracy of deformable object collision detection.

Key words: collision detection, hybrid bounding box, hybrid algorithm, quantum behaved particle swarm optimization, differential evolution

摘要： 针对变形体碰撞检测算法的准确性与实时性问题，提出了一种融合智能算法的变形体碰撞检测算法。在随机碰撞检测的基础上，使用层次包围技术缩小粒子搜索空间，采用一种融合基于量子行为的粒子群算法与差分进化算法的混合智能算法进行搜索。该方法以局部吸引子作为差分变异基础，在扩大种群多样性的同时加快了算法收敛速度，有效地解决了传统智能算法不适应离散空间计算问题以及早熟收敛问题。针对随机碰撞粒子搜索空间特点，混合算法的引入大大提高了碰撞检测算法的检测效率，解决了检测过程中的穿刺与遗漏现象。经实验验证该方法在很大程度上提高了变形体碰撞检测的实时性与准确性。

关键词: 碰撞检测, 层次包围盒, 混合算法, 量子粒子群算法, 差分进化算法