基于AABB包围盒的文化粒子群碰撞检测算法的研究与实现

摘要

随着虚拟现实技术和仿真技术的兴起，快速、健壮的碰撞检测检测算法在虚拟现实、计算机游戏、计算机辅助设计等领域扮演着重要角色。 在刚体对象的碰撞处理中，由于模型不会发生形变，所以其包围盒等关键数据都可以在预处理阶段处理完毕。对于软体对象即变形体对象，由于在移动时其对象顶点之间的相对位置要发生变化，导致包围盒不断发生改变，必须更新大量的数据以重构包围盒，而这种庞大的运算量在虚拟现实系统中会严重影响到系统的实时性。因此，优化碰撞检测算法的研究已成为虚拟现实领域的热点。 粒子群优化算法是一种新型的群体智能算法，系统初始化为一组随机解，通过叠代搜寻最优值。文化粒子群算法则将粒子群算法融合到文化算法框架中，它在群体空间的基础上增加了一个知识空间，两个空间交互通信，以指导粒子的优化飞行，同时提高算法的收敛速度。 为了提高碰撞检测的实时效率，本文提出了基于AABB包围盒的文化粒子群优化算法AABB-CAPSO。该算法首先利用AABB包围盒做粗略检测，如果变形体模型碰撞后发生形变，则利用文化粒子群算法进行精确的碰撞信息计算。本文将粒子群算法与文化算法相结合，组成基于粒子群算法的主群体空间和知识空间,两空间独立并行演化，下层主群体空间定期贡献优选个体给上层知识空间,上层知识空间经演化后,也定期贡献优选个体给下层主群体空间,这种“双演化双促进”机制避免了PSO可能因为“早熟”现象而陷入局部最优解，提高了AABB包围盒寻优更新数据的运算效率。 本文的创新点在于将文化算法框架同粒子群算法相结合，基于AABB包围盒碰撞检测策略，提出了AABB-CAPSO检测算法。AABB-CAPSO基于文化算法框架，增加了粒子群算法的群体多样性，充分利用了历史信息，为后期的寻优过程提供了良好的指导。本文的实验结果表明，AABB-CAPSO算法提高了碰撞检测的实时效率，在虚拟仿真的应用中有实用价值。