论文部分内容阅读
连续碰撞检测(Continuous Collision Detection, CCD)在物理仿真、计算机游戏、机器人路径规划等领域都有着重要的研究意义。随着计算机图形学的不断发展,以及包括虚拟现实在内的新兴领域的涌现,实际应用中对碰撞检测的实时性和准确性要求越来越高。本文针对由三角形构成的柔性物体,采用插值方法描述在连续时间间隔中顶点运动轨迹,检测其碰撞。研究内容包括CCD加速算法及其在有限元仿真、流布耦合等领域的应用。主要研究成果如下：(1)通过分析影响并行碰撞检测算法的主要因素,提出一种基于数据分块思想的并行碰撞检测算法。在初始化阶段将场景数据从空间角度进行分块,在碰撞检测阶段由每个处理器处理一块数据以实现包围盒并行更新,同时利用静态和动态相结合的任务分配策略,提升碰撞检测的并行度。通过在16核和24核处理器模式下与之前算法的对比,证明本算法能够提升碰撞检测速度,同时具有很好的兼容性。(2)在并行算法的基础上,提出了一种针对三角网格的低层碰撞检测剔除算法-非共线过滤器(Deforming Non-collinear Filters, NCF),该方法的主要思想是通过共线测试剔除掉不可能发生碰撞的三角形特征对。实验证明,相比之前的方法,NCF能够减小伪真率,改进CCD性能,对大步长效果更佳。(3)提出一种流布耦合方法,解决了流体和布料高速碰撞过程中流体穿透布料的问题,本方法采用Smoothed Particle Hydrodynamics对流体建模,首先提出一种膨胀式连续碰撞检测方法(Dilated Continuous Collision Detection, DCCD)检测流体粒子与布料之间是否发生了碰撞,然后提出一种改进的惩罚法来处理碰撞。(4)碰撞检测作为有限元分析中非常重要的一个环节,之前的碰撞检测方法大多只能检测有限元模型表面单元之间是否发生碰撞,我们将CCD引入有限元仿真,解决了之前方法无法检测到模型内部单元之间碰撞的问题。利用以上这些技术,我们首先将并行碰撞检测算法集成到一款开源的机器人操作系统软件中(Robot Operation System, ROS),然后将碰撞处理算法集成到开源有限元仿真平台Impact和Opentissue中,取得了很好的效果。