虚拟环境中碰撞检测问题的研究

碰撞检测问题在机器人运动规划、计算机图形学等领域中有很长的研究历史，近年来随着虚拟现实、分布交互仿真等技术的兴起，碰撞检测，特别是软体碰撞检测问题开始成为研究的热点。精确的碰撞检测对提高虚拟环境的真实性、增强虚拟环境的沉浸感有着至关重要的作用，而虚拟环境自身的复杂性和实时性又对碰撞检测提出了更高的要求。 层次包围盒方法是解决碰撞检测问题固有时间复杂性的一种有效的方法，它是用体积略大而几何特性简单的包围盒来近似地描述复杂的几何对象，并通过构造树状层次结构来逼近对象的几何模型，从而在对包围盒树进行遍历的过程中，通过包围盒间的快速相交测试来及早地排除明显不可能相交的基本几何元素对，而只对包围盒重叠的部分元素进行进一步的相交测试，以提高碰撞检测的速度。包围盒类型的选择是层次包围盒方法的基础和关键。 本文以虚拟手术仿真为应用背景，着重论述了一种基于固定方向凸包包围盒层次的碰撞检测方法。固定方向凸包是一种特殊类型的凸包，它的所有面方向都来自一个固定的方向集合，它克服了以往包围盒类型的缺点，在紧密性和简单性之间达到了一定的折衷。本文在充分研究了固定方向凸包的固有特性的基础上，开发并证明了它适用于复杂环境中软体碰撞检测的性质，并着重解决了包围盒间的相交测试、对象运动后包围盒的更新、对象变形后包围盒树的更新等问题。 文中提出并证明了一种快速区间测试法以解决两个固定方向凸包包围盒间的相交测试问题，通过查找两个包围盒在由固定方向集合所定义的方向轴上的范围区间是否存在不重叠的情况，来判断它们是否不相交。通过这种简单的区间测试法，两个包围盒间的相交测试最多只需要k次比较运算(k为固定方向集合的大小)。 对象运动后包围盒的更新是层次包围盒方法中的一个重要问题。根据固定方向凸包的定义和性质，文中提出了一种基于线性规划的更新算法，不需要在构造包围盒层次时增加任何额外的计算量和存储量，在对象运动后可以仅通过3k次乘法得到更新后的包围盒。 对象变形后的处理是碰撞检测问题的一个难点。本文在对几种变形情况进行分析的基础上，分别提出了相应的解决方法，并着重提出了一种自底向上的包围盒树快速更新算法，通过k次比较运算由子结点的包围盒得到父结点的包围盒，以解决拉压变形和拓扑变化后包围盒树的更新问题。 此外，本文在充分开发和利用虚拟环境中对象运动的时空相关性的基础上，提出了加速对象间碰撞检测速度的遍历跟踪策略。这是一个启发式的策略，通过跟踪 国防科学技术大学研究生院学位论文 上一时间采样点对包围盒树的遍历过程，确定当前时间采样点的遍历路径，从而有 效地减少了遍历过程中包围盒相交测试的次数，提高了算法效率，同时通过对跟踪 表的维护，保证了碰撞检测的正确性和有效性。 实验结果和具体应用表明，基于固定方向凸包包围盒层次的碰撞检测方法不仅 能很好地解决刚体间的碰撞检测，而且为解决和处理软体对象环境中的碰撞检测问 题提供了一种可靠而有效的途径。本文的研究成果，对大规模复杂环境中的碰撞检 测有重要的理论价值和实际意义。