适用于复杂场景的一种并行碰撞检测算法

摘要

针对传统碰撞检测算法检测时间太长的局限性,提出了一种改进算法,即在DS(Dynamic Sorted Algorithm)算法和时空相关性的基础上,采用基于MPI并行处理的方法。主要根据当前待检测物体的状态并采用DS算法找出其相邻物体,并构建更新物体的list链表(链表中存放其相邻物体)且构建其包围盒树。通过时空相关性确定树的遍历次序,并采用基于MPI(Message Passing Interface)的并行处理方式执行各子任务来加快碰撞检测。实验结果表明该算法提高了碰撞检测的速度,保证了碰撞检测的实时性。