1 引言
几何模型间的碰撞检测是织物仿真、计算机动画、机器人、CAD/CAM 等多领域的关键问题之一。快速而准确的碰撞检测对提高与人交互的虚拟环境的真实感至关重要，尤其对于需要力触觉感知的虚拟环境 。在虚拟环境仿真中，碰撞检测往往是系统计算效率的瓶颈 。目前对刚体之间的碰撞检测算法的研究已趋向成熟 ～ ，但对软体碰撞检测的算法研究较少，尤其是对准确性的考虑。对于虚拟外科手术训练、织物仿真、计算机动画、伤残人力觉功能恢复等实用的虚拟环境中的交互对 象，软体对象比刚体对象更普遍。虚拟环境中的软体对象不仅自身的复杂度高，而且会在外力的作用下发生形变，甚至发生拓扑结构的改变，这给碰撞检测问题带来 了新的挑战 。
2 碰撞检测的实时性与准确性
就实时性而言，满足虚拟环境中视觉再现的实时性要求，碰撞检测的速度只需达到24Hz以上，而要满足人对虚拟环境中力觉再现的真实感知，碰撞检测的速度要 达到300Hz以上才能维持交互系统的稳定性 。这使得其所受的实时性约束比纯视觉虚拟环境的要严厉得多。就准确性而言，包括时间准确性和空间准确性，对于环境漫游系统，一般只要粗略地计算碰撞时刻和 位置。而对于虚拟手术仿真、虚拟装配等应用，就要求实时而准确地检测碰撞发生的时刻和部位。对于准确性的评价方法现有文献论述较少，目前见到的有采用检测 报告出错率的方法 ，而对出错的判定则与具体应用及要求相关。
虚拟现实系 统对虚拟环境的实时性和准确性要求往往相互抵触，真实性越高，要求模型越准确精细，相应的数据量越大，碰撞检测的时间开销也更大，甚至不能承受，目前许多 实际的系统对碰撞响应处理只能采用近似方法 。因此碰撞检测必须依据实际应用对实时性和真实性的具体要求，在准确性和实时性之间折衷。
3 软体对象碰撞检测的特点
3.1 计算效率高
对软体对象的物理模型的力和变形等计算比刚体要复杂得多，这导致了对碰撞检测算法的计算效率和准确性的高要求。
3.2 提供准确的碰撞信息
刚体物理模型为集中式参数，而软体对象的物理模型往往具有分布式参数，软体发生碰撞的部位不同，其随后的碰撞响应不同。准确的碰撞时刻和位置信息是计算随后的逼真的碰撞响应所必须的。
3.3 要求数据结构更新快
对于刚体碰撞检测算法可在预处理阶段建立对象的表示，例如层次包围盒、距离场、或其它空间分割方式等空间数据结构，这样做效率很高。但是，对于软体对象，由于在交互中会产生变形，这些预处理的数据结构必须频繁且快速地更新。
3.4 需考虑自身碰撞
与刚体间的碰撞检测不同，为了逼真地仿真与软体对象及它们之间的交互，必须考虑所有的接触点并且包括自身碰撞。例如在织物仿真中，织物与织物间的碰撞经常发生。
4 软体对象的碰撞检测方法
软体碰撞检测方法按照所采用的方法其基本思想的不同，主要可分为层次包围盒、空间分割、随机方法、距离场和图像空间方法。
4.1 层次包围盒
层次包围盒方法以三维形体的边界表示法为基础，其基本思想是用体积稍大且几何特性简单的包围盒来近似地描述复杂的几何对象，并通过构造树状层次结构逐渐逼 近对象的几何特性。进行重叠测试时只需对包围盒重叠的部分进行进一步的相交测试，从而可大大减少参与相交测试的包围盒的数目，提高碰撞检测的效率。
层次包围盒方法中每个节点的孩子数量的选择也是一个关键点。对于刚体通常选择二叉树，但对于软体对象，四叉或八又树总体性能更好。因为更少的节点需要更新和总的更新代价降低了。另外，重叠测试的递归深度更低，所以在存储空间上的需求更低。
层次包围盒方法的效率和准确性关键在于包围盒类型的选取。包围盒类型有多种，例如球，方向包围盒(OBB)，DOPs，Boxtrees，轴向包围盒(AABB)，spherical shells和凸包，如图1所示。
图1 各种包围盒类型
其中方向包围盒OBB和k—DOP这两种值得注意。OBB是比较常用的一种类型。在大多数情况下其总体性能要优于AABB和包围球，但因对象变形后OBB 树的更新太慢不适合用于包含软体对象的复杂环境中。k—DOP又称为固定方向凸包FDH(在此我们也称其为FDH)。在软体对象环境中，FDH的使用最为 常见。实际上，AABB是k—DOP中k=6时的一个特例。包含k个固定方向向量的两个FDH间的相交测试最多只需k次比较运算，当对象发生形变时更新一 个结点的FDH只需要k次比较运算，计算效率较高。同时，FDH在很大程度上改善了AABB的紧密性差的缺点，因此可提高碰撞检测的准确性。
论文[6]通过一种自底向上的方法解决了软体变形后的FDH树的更新问题。但变形后包围盒层次的调整更新是软体环境碰撞检测的瓶颈，如何提高FDH树的更新速度仍有待进一步研究。
论文[13]中使用FDH了进行织物仿真，提出进一步加速FDH层次更新的方法，使碰撞检测不再成为织物模拟系统的瓶颈。由于任何穿透都是可见的，织物的 碰撞检测的准确度要求非常高。就碰撞检测和响应的准确度两方面与采用Maya的比较结果看，此方法可正确地检测所有的碰撞，而采用Maya时出现了穿透现 象。
层次包围盒方法应用非常广泛，为复杂模型间准确的碰撞检测提供一个快速有效的方法。
4.2 空间分割
基于空间分割的碰撞检测基本思想是，对整个场景空间△，沿X、Y、z轴进行分割，形成一系列单元格。只对同处于一个单元格内对象之间进行碰撞检测。空间分 割可用于检测碰撞和自身碰撞，对象拓扑可以改变，不限制以三角形作为对象的基本几何元。空间分割方法中于用于表示3D空间数据结构选择很重要，如图2所 示。
图2 表示3D空间数据结构
这种数据结构在计算时间和存储上必须是灵活的和有效率的。
