论文摘要
碰撞检测在计算机图形学、虚拟现实、计算机游戏、动画、计算机辅助设计、机器人及虚拟制造等领域中均是经典而关键的问题,多年来一直受到较多的关注。目前,大多数虚拟对象的几何模型都是由成千上万个基本几何元素组成。由于虚拟环境的几何复杂性的增加,使得碰撞检测的计算复杂性大大提高,复杂场景的交互消耗了大量的计算机资源,因此,碰撞检测往往成为虚拟环境中的一个瓶颈。如何设计出能够满足实时性、精确性、普遍性的高效的碰撞检测算法,成为当前亟待解决的问题。在现代智能仿生算法的快速发展中,智能优化算法给研究人员带来了前所未有的机遇和挑战。许多智能算法,例如模拟退火,遗传算法,蚁群算法,粒子群算法,鱼群算法等开始运用到碰撞检测算法中,但是将蚁群优化算法,粒子群优化算法技术应用到碰撞检测中还是没有形成比较完善的方法。针对交互式系统中碰撞检测实时性,精确性的要求,本文深入研究智能优化算法技术,研究结合人工智能技术和随机碰撞检测算法。将群体智能中经典的粒子群优化算法引入改进的随机碰撞检测算法中。本文主要包括以下几部分内容：(1)基于粒子群的快速碰撞检测算法：算法结合了粒子群和包围盒的优势,首先构造层次包围盒树,先判断物体的根节点是否相交,若不相交则物体没有发生碰撞,若物体空间有相交,则采用粒子群搜索算法对树的叶子节点进行遍历,若遍历中叶子节点有相交,则物体发生了碰撞。此算法发挥了层次包围盒和粒子群算法的优势。进一步提高了碰撞检测的效率。(2)基于并行化蚁群的快速碰撞检测算法：算法将蚁群优化算法和随机碰撞检测相结合,本算法利用了并行化思想加速碰撞检测的速度,在初步检测阶段先用层次包围盒树快速排除不相交的物体,然后将并行化蚁群算法应用到碰撞检测中,把物体的基本单元及叶子看作“蚂蚁”,然后再遍历搜索。通过实验证明本算法进一步加速了碰撞检测的效率。降低了时间复杂度。