摘要
碰撞检测一直是VR/AR/MR中的关键技术，用来防止物体间碰撞时发生穿透现象，使模拟效果更加符合客观规律，增强虚拟世界的真实感。碰撞检测过程中选择合适的检测技术对碰撞检测效率及精度的提高都有很大作用，近年来，随着计算机硬件的发展和人们需求的不断提高，精确而高效的碰撞检测成为相关学者不断追求的目标。 本文针对并行碰撞检测过程中检测速度较慢、负载不均衡等问题，提出了一种基于层次八叉包围盒的并行碰撞检测算法，本文采用任务分配策略解决并行碰撞检测过程中的负载均衡问题，主要工作如下： （1）提出了层次八叉包围盒的最佳划分层次：对层次八叉包围盒的构造过程进行详细描述并对各层包围盒碰撞检测的时间进行分析；提出根据层次八叉包围盒的边长来衡量检测的精度，给出误差值的表示形式，实验得出不同划分层次下各层包围盒之间的碰撞时间及误差值之间的关系，确定层次八叉包围盒的最佳划分层数。 （2）提出了基于静态任务分配策略的薄壳模型并行碰撞检测算法：改进一般的碰撞检测算法，在碰撞检测阶段用4个CPU内核模拟8线程的处理器实现算法的并行，将串行执行的任务平均分到各个线程上完成并行计算，在碰撞检测前用八叉划分方式构造层次包围盒并将层次包围盒间的碰撞检测技术与基于静态任务分配策略的并行算法相结合，实现了层次八叉包围盒间的静态并行碰撞检测过程。 （3）提出了基于动态任务分配策略的薄壳模型并行碰撞检测算法：采用静态任务分配策略无法达到很好的负载均衡，因此，改进静态任务分配策略，将动态任务分配策略应用到层次八叉包围盒间的检测中，通过各线程抢占任务的方式有效提高负载均衡度从而加快碰撞检测速度。 实验结果表明：本文采用的层次八叉包围盒技术保证了碰撞检测的精度；本文提出的基于静态任务分配策略的多线程并行碰撞检测算法优于一般的碰撞检测算法；本文改进静态任务分配策略，最终采用的基于动态任务分配策略的碰撞检测算法有效改善了并行过程中的负载均衡问题，提高了碰撞检测的效率。本文提出的算法可应用于虚拟空间中刚性物体之间的碰撞检测。
NETL