论文部分内容阅读
虚拟环境中的碰撞检测问题是触觉渲染、物理仿真、机器人的路径规划、计算机游戏以及CAD/CAM等领域中的经典问题。实现实时的、高精确度的连续碰撞检测对增强虚拟场景的沉浸感以及真实性起着非常重要的作用。由于大部分虚拟现实系统都需要进行实时的人机交互,只有连续碰撞检测的速度达到一定的帧数时,才可以流畅的进行人机交互。虚拟环境中所有图元之间的碰撞都需要准确的检测结果,否则在视觉上会产生明显的不真实感。因而,如何提高连续碰撞检测算法的速度与准确度一直都是研究的重点内容。本论文在对各种碰撞检测算法进行全面了解的基础上,针对可变形物体之间的连续碰撞检测算法中存在的问题,进行了研究。本论文的主要研究内容包括以下几个方面:本论文分析了在设计以及实现可变形物体之间的连续碰撞检测算法过程中需要考虑的几个因素。首先,对于物体模型的表示方式,选择了本论文所提出的算法所适用的三角形网格模型。其次,把整个连续碰撞检测过程分为两步执行,即初步检测阶段和详细检测阶段。其中,初步检测阶段主要是把可能发生碰撞的物体分在同一个子集中,然后在详细检测阶段对这些子集分别执行进一步的测试。在详细检测阶段中对于图元之间的碰撞测试,使用点面图元对检测算法和边边图元对检测算法。最后,对于可能出现的健壮性问题进行了分析,并采取了一些措施来避免产生这些问题。详细的介绍了本论文所使用的k-DOPs包围盒以及层次包围树结构。层次包围树结构可以用于加速连续碰撞检测的初步检测阶段以及详细检查阶段。对于初步测试阶段,可以使用虚拟场景中所有物体的层次包围树来进行碰撞检测,从而剔除不可能发生碰撞的物体对;对于详细测试阶段,使用由组成物体的图元构建的层次包围树来进行碰撞检测,从而剔除那些不可能发生碰撞的图元。还详细介绍了本论文所使用的层次包围树的构建方法、执行相交测试时所使用的遍历方法以及当物体发生变形时所使用的层次包围树的更新方法。详细的说明了本论文所提出的一种用于自碰撞检测的算法。该算法分别对自碰撞检测的曲率测试和轮廓投影线测试这两个测试条件进行了改进。对于可变形物体,根据它的几何图元之间的邻接信息使用自底向上的方法构建物体的层次包围树。在构建层次包围树的过程中,计算每一个节点内的子三角形网格区域的最小法向量锥。将最小法向量锥思想应用到轮廓投影线的自碰撞测试中,避免了轮廓投影线中各条线段之间的两两测试。同时,还根据子三角形网格区域之间的邻接信息减少自碰撞检测过程中大量不必要的检测。最后实验结果说明,该算法能较好的提高自碰撞检测的速度。详细的阐述了本论文所提出的一种用于连续碰撞检测算法中的基于子空间的剔除算法。在连续碰撞检测过程中两个非常接近但是实际上没有发生碰撞的图元往往会产生误报。针对这种问题,首先使用基于一维子空间的剔除算法,然后对剩余的图元对使用基于二维子空间的剔除算法。若是三维空间中的两个图元在一维子空间或者二维子空间内没有发生碰撞,那么它们在三维空间中也不会发生碰撞。最后实验结果表明,该剔除算法能够显著的减少连续碰撞检测中的误报数量,从而避免了大量的三次方程的求解运算,提高了连续碰撞检测的速度。