论文部分内容阅读
碰撞检测是虚拟现实、动画仿真、计算机辅助设计等领域不可回避的问题之一,其基本任务是确定两个或多个物体彼此之间是否发生接触或穿透。尽管人们已经取得了一系列成果,但是这些算法侧重于考虑碰撞检测的精确性,很少涉及实时性。随着计算机软硬件及网络等技术的日益成熟,交互实时性、场景真实性要求令碰撞检测再度成为图形学研究的热点。层次包围盒方法是解决碰撞检测问题固有时间复杂性的一种有效的方法,它是用体积略大而几何特性简单的包围盒来近似地描述复杂的几何对象,并通过构造树状层次结构来逼近对象的几何模型,从而在对包围盒树进行遍历的过程中,通过包围盒间的快速相交测试来及早地排除明显不可能相交的基本几何元素对,而只对包围盒重叠的部分元素进行进一步的相交测试,以提高碰撞检测的速度。包围盒类型的选择是层次包围盒方法的基础和关键。文章首先对各类包围盒算法进行了全面的分析,然后重点探讨基于OBB层次包围盒算法的思想和流程,并在此基础上研究提高基于OBB层次包围盒算法执行效率的措施。本文主要研究了以下几个方面的内容:(1)在研究OBB等层次包围盒固有特性的基础上,通过具体实现构建OBB和OBB树、包围盒间重叠测试等技术,比较了OBB适用于复杂环境中刚体碰撞检测的优势,并针对OBB存在的缺点和不足加以优化。(2)针对虚拟环境中物体移动时每帧之间的时空相关性,在原有的二叉树结点结构和遍历算法基础上,研究利用缓存、排序等方法优化碰撞检测算法。(3)针对基于OBB碰撞检测算法存在的缺陷,研究利用包围盒与基本几何元素相交测试的优化方法,消除叶子结点包围盒,精简OBB层次结构;同时在基本几何元素相交测试中引入类似分离轴的方法,加快检测速度。通过多种检测方法的组合,得出基于OBB的优化层次结构和混合算法。实验结果和具体应用表明,基于OBB的碰撞检测方法能很好地解决复杂环境中刚体间的碰撞检测问题。本文的研究成果对大规模复杂环境中的碰撞检测有一定的理论价值和实际意义。