● 摘要
碰撞检测问题在机器人运动规划、计算机图形学等领域中有很长的研究历史，近年来随着虚拟现实、分布交互仿真等技术的兴起，碰撞检测，特别是可变形模型碰撞检测问题开始成为研究的热点。层次包围盒方法是解决碰撞检测问题固有时间复杂性的一种有效的方法，它是用体积略大而几何特性简单的包围盒来近似地描述复杂的几何对象，并通过构造树状层次结构来逼近对象的几何模型，从而在对包围盒树进行遍历的过程中，通过包围盒间的快速相交测试来及早地排除明显不可能相交的基本几何元素对，而只对包围盒重叠的部分元素进行进一步的相交测试，以提高碰撞检测的速度。本文以国家十五“863”课题“分布式虚拟环境技术”为背景，论述了一种基于轴对齐包围盒（axis-aligned bounding boxes, AABB）层次包围盒的碰撞检测方法。在充分研究了AABB适用于虚拟环境中可变形模型碰撞检测的性质的基础上，着重解决了包围盒间的相交测试、包围盒树的创建、对象变形后包围盒树的更新等问题。 文中实现了一种快速区间测试法以解决两个AABB包围盒间的相交测试问题。通过查找两个包围盒在x、y、z三个坐标轴上的投影区间是否存在不重叠的情况，来判断它们是否不相交。通过这种简单的区间测试法，两个包围盒间的相交测试最多只需要6次比较运算。本文采用了一种基于分裂平面的方法，自上而下，递归地创建平衡的包围盒树。在每一个递归步中，先计算基本几何元素集合的AABB，选定分裂平面，然后根据组成对象的基本几何元素相对于分裂平面的几何位置进行划分。如此反复，直到每个基本几何元素集合中只有一个基本几何元素。对象变形后的包围盒树的更新是碰撞检测问题的一个难点。本文实现了一种混合的更新算法，在进行碰撞检测之前，先对上层节点进行自下而上的更新，在碰撞检测的同时，对涉及到的下层节点进行有选择的自上而下的更新，从而减少了不需要更新的包围盒的数目，提高了算法效率。此外，本文在充分开发和利用虚拟环境中对象运动的时空相关性的基础上，提出了加速对象间碰撞检测速度的遍历跟踪策略。这是一个启发式的策略，通过跟踪上一时间采样点对包围盒树的遍历过程，确定当前时间采样点的遍历路径，从而有效地减少了遍历过程中包围盒相交测试的次数，提高了算法效率，同时通过对跟踪表的维护，保证了碰撞检测的正确性和有效性。 实验结果表明，基于AABB包围盒层次的碰撞检测方法不仅能很好地解决刚体间的碰撞检测，而且为解决和处理可变形模型碰撞检测问题提供了一种可靠而有效的途径。