虚拟环境中碰撞检测是计算机图形学、计算机动画、机器人学、计算几何和计算可视化等研究领域的经典问题。实现实时、精确的碰撞检测对提高虚拟环境的真实性、增强虚拟环境的沉浸感起着至关重要的作用。尽管针对碰撞检测问题国内外已有了大量的、有价值的、实用的研究成果,但随着虚拟现实等新领域的涌现以及人们对场景真实性要求和用户交互实时性要求的不断提高,碰撞检测技术所面临的问题也日益突出。所以如何提高碰撞检测算法的效率和精度一直以来是人们研究的重点,其中,最核心的问题是如何有效地提高碰撞检测的速度以保持虚拟环境的真实性。本文对各类碰撞检测算法作了全面分析,深入研究。在总结现有碰撞检测算法特点及其局限性的基础上,针对目前碰撞检测技术存在的问题,设计、实现并验证了一组新的性能良好的碰撞检测算法,本文的主要研究工作及成果如下:1.提出了一种新的面向对象的并行碰撞检测算法。算法保证了碰撞响应的唯一性。当运动的物体远远少于静止的物体时,时间复杂性为O (n ),其中n为虚拟环境中物体的数目。与其它方法相比,该方法有效合理地降低了检测的时间复杂性,而且我们引入并行的思想,进一步加快检测的速度。算法具备良好的通用性,能很好地适用于各种运动形式的物体运动,实时进行物体运动状态更新,完成动态碰撞检测。同时也很好地保证各仿真节点的自治性和仿真监控系统的可扩展性。2.提出了一种改进的基于包围盒树的碰撞检测算法。通过优化AABB包围盒存储结构,并在包围盒树中建立了一定的优先级策略,来提高碰撞检测速度,超时计数器的引入又避免了漏检的发生。并设计了两种包围盒树的搜索算法,第一种自上而下的搜索算法实现了碰撞检测的精确计算,并且提供了碰撞部位、物体间的距离、速度等信息。而第二种自下而上的搜索算法主要针对前次检测已发生碰撞的情况,它的目的是快速判断是否碰撞。第二种算法在很大程度上避免许多不必要的检测。3.提出了一种新的将任意多面体剖分为系列四面体的算法,在此基础上,引入并行的思想,实现了并行碰撞检测。由此将两个复杂的多面体间的碰撞检测转化为系列四面体间的并行碰撞检测,在保证高精度的前提条件下,有效的满足了碰撞检测的实时要求,同时也解决了一般碰撞检测算法只适用于凸多面体的不足。并结合包围盒方法,完成了基于包围盒的并行碰撞检测算法。4.提出了一种新的基于粒子群优化的并行碰撞检测算法,该算法把碰撞检测问题转化为两个模型的特征对序号构成的空间内的优化问题,利用粒子群算法智能优化搜索特性,来完成碰撞检测过程中局部最小特征对的搜索过程。并结合多面体剖分算法,将优化模型充分并行化,然后采用粒子群优化算法并行求解。算法在继承一般基于相交的碰撞检测算法优点的同时,突破了它们的局限性,能够在保证效率的前提下处理任意形状多面体之间的碰撞检测问题,并引入并行技术,还可以通过调节节点数提高检测的速度。5.提出了一种新的基于遗传算法的并行碰撞检测算法,该算法将多面体模型相交问题转化为带约束条件的线性规划问题,进化过程划分到不同计算节点上,并行进行,在对约束条件处理后,并通过一定的种群间信息交换策略实现优良基因的交换,来求解多面体模型相交问题,实现碰撞检测算法。与传统方法进行比较,基于遗传算法的并行碰撞检测算法不仅提高了碰撞检测速度,同时保证了较高的精度,而且适用于任意形状的多面体之间的实时动态碰撞检测。实验结果与相关应用表明,本文提出的面向对象的碰撞检测算法具备良好的通用性,很好地保证各仿真节点的自治性和系统的可扩展性。提出的其他几类碰撞检测算法均能保证较高精度和速度,适用于任意多面体的碰撞检测,很好地满足了虚拟环境下对碰撞检测技术的要求。