论文部分内容阅读
为了解决虚拟环境的真实感问题,必须对虚拟环境进行实时的碰撞检测。本文围绕实时碰撞检测问题,就如何提高复杂场景下碰撞检测的效率进行了深入研究。着重探讨了如何利用并行技术来有效提高碰撞检测算法的效率。主要研究成果包括以下八个方面:1.提出了一种基于分治和流水线技术的并行碰撞检测算法。采用并行算法中的流水线技术,通过划分进程来遍历任务树从而加速碰撞检测过程。同时在进程中也应用了多线程技术,因而能快速的检测到碰撞。2.提出了一种基于混合包围体的OpenMP并行化碰撞检测算法。利用OpenMP并行模型来并行遍历混合包围体层次,进一步加速碰撞检测过程。提出了一种基于着色算法的并行碰撞检测算法,在并行机上采用多线程技术执行相同类别的任务树的遍历过程,在遍历过程中检测是否有碰撞发生。3.提出了一种基于时空相关性的MPI并行碰撞检测算法。在空间分割和时空相关性基础上采用基于MPI的并行处理技术。并通过MPI并行处理方式将各子任务分配到各子进程执行。4.提出了一种基于粒子群算法的并行碰撞检测算法。将OpenMP、MPI并行模型来并行化基于粒子群面向可变形物体的随机碰撞检测算法,提出了一种基于遗传算法的并行碰撞检测算法。采用一种快速的基于模拟退火遗传算法的碰撞检测技术,完成整个检测过程,然后将并行技术用于遗产算法,进一步加速碰撞检测的速度。5.提出了一种改进的基于球体混合重建的并行碰撞检测算法。对球体混合表面提出一个子线性时间复杂性的重建过程,利用四元组构造变换范围,扩展了从线性到球形混合的构造变换方法,采用循环划分的方法完成由球体混合到线性混合的分解过程。然后采用OpenMP技术并行化上述算法,可以快速完成虚拟环境下复杂的碰撞检测问题。