论文摘要
随着计算机软硬件以及网络等技术的日益成熟,人们迫切希望能对现实世界进行真实的模拟,以解决实际问题。而碰撞检测问题是计算机动画,物理仿真,计算几何,机器人学,计算机游戏等领域的重要课题。在虚拟环境中,碰撞检测可以为物体之间的交互建立良好的基础。因此,如何在很高的实时交互要求下完成对大量复杂物体的相交测试是碰撞检测研究的首要目标。分析和比较了当前几种常用碰撞检测算法的优势和不足,有效地结合轴对齐包围盒(Aligned Axis Bounding Box,AABB)算法和二叉空间剖分(Binary Space Partitioning,BSP)算法进行碰撞检测。根据两种碰撞检测算法自身的特点,把BSP算法应用于碰撞初步检测阶段,把AABB算法应用于详细碰撞检测阶段,并优化AABB的更新算法,减少计算量,从而提高碰撞检测效率;给出了一种新的分治策略,在多处理器机器上利用多进程和多线程技术,根据虚拟环境中的复杂度,把碰撞检测问题分而治之分配给不同的线程并行处理;通过主从进程模式来进行通信控制。算法充分地利用了硬件资源,从而大大地提高了碰撞检测效率,也增强了虚拟环境的真实性和可靠性。在总体安全监测与评估平台上的三维实时显示与报警模块中,结合基于BSP和AABB的三维碰撞检测并行算法设计了相关的测试案例,并与基本碰撞检测算法、串行碰撞检测算法进行对比,从理论时间复杂度和实际运行时间两方面进行了性能测试。测试结果表明,使用基于BSP和AABB的三维并行碰撞检测时,系统帧率明显增加,系统运行更加流畅。