在碰撞检测应用中，常用的空间分割方法包括：均匀网格、八叉树和BSP树等。一般来说，BSP树、八叉树或kd一树都是对象相关的。八叉树的建立很耗时 间，所以不适合在动态环境中实时碰撞检测。而使用均匀网格的空间分割与对象无关，使得它特别适合软体对象。均匀空间分割的关键问题是确定适当的单元格尺 寸，适当选择单元格尺寸大小，可使算法的计算能保持一定的准确度又不致开销太大。

论文[3]提出一种基于均匀空间分割的快速多体碰撞检测算法，同时依据对象的分布密度，提出了一个计算单元格尺寸的优化方法。与Cohen等人提出的I— COLLIDE算法的比较实验表明，在均匀分布条件下，当物体数量较大时，该算法的效率高于I—COLLIDE算法，而且其效率基本不受物体运动相关性的 影响。

论文[14]使用均匀网格的空间散列来检测可变形四面体网格的碰撞和自身碰撞。提出使用哈希函数来映射3D网格到一个哈希表，从而实现快速的隐式的空间分 割。该方法不仅节省存储空间，而且很灵活。此外，还讨论了最佳的单元大小。实验表明最佳单元大小和单个物体几何元的包围盒一样大，此时算法的计算效率最 高。在20k个四面体的环境中可以实时地检测碰撞和自身碰撞，算法给出的准确的位置信息可用于正确的碰撞响应。

其性能与对象的数量无关，只与对象几何元的数量有关。所以该方法可用于多个对象的环境中。

当对象较少且均匀分布于空间时，空间分割方法效率较高；当对象较多且距离很近时，需进行单元格的进一步递归分割，并需要大量的单元格相交测试和存储空间，效率明显降低。空间分割由于存储量大及灵活性不好，使用不如包围盒层次法广泛。

4.3 随机方法

随机方法按使用随机方法的方式的不同可分为average—case方法和基于随机选择几何元的碰撞检测方法。

Average—case方法使用随机方法来估计碰撞的可能性。其主要思想是考虑层次包围盒的内部节点的多边形集，遍历时快速地计算一对包围盒的多边形问的碰撞可能性，然后把这个可能性作为优先权来指导遍历那些有更高可能性的BV树部分。

该方法可用于BVHs上，所以能扩展许多基于层次包围盒的碰撞检测方法。 首次提出把一般的层次碰撞检测算法转换为以可控制的方式来平衡计算效率和准确度的方法，并比较了扩展AABB树的average—case方法和基于 DOP树的算法，结果显示前者成倍地增加计算效率而不明显降低准确性。

基于随机选择几何元的碰撞检测方法在碰撞对象内通过随机取样作为初始的潜在的交互区域的猜测。准确的碰撞区域通过使用时空一致性来缩小。该方法与任何层次 无关，可直接用于几何元对。如果相邻两次最近特征的距离，即模型的相干性高，那么算法的效率较高，相反相干性越低，算法效率就越低。Lin和Canny提 出的解决方法 考虑了时空一致性。如果特征对在上一个时间步上足够近，它很可能是下一个时间步上交互的特征对。J 利用了时间一致性，提出了一个分两步来计算曲面结构的局部距离最小值的更新方法，把时间复杂度从O(mn)减/J,N O(m+n)，m和n是邻近几何元的数目。

虽然两种随机方法各不相同，但它们有共同的特点，即都可以平衡碰撞检测的计算效率和准确性，能获得有意义的接触信息用于处理碰撞，但不能用于精确的碰撞检测。对于时间关键的碰撞检测，随机方法具有较大的发展前景。

4.4 距离场

距离场定义了场中所有点到闭合曲面的最小距离。距离场D：R3一R定义了一个曲面作为零等值面。为了区分内部和外部，距离是有符号的。用距离场表示闭合曲 面有不限制拓扑的优点。另外，碰撞检测和响应所需要的距离和法线的估计非常快，而且和对象的几何复杂性无关。为了降低存储需求或距离场生成时间，可以减少 距离场的求解，降低准确度。所以距离场方法能平衡计算效率和准确度。表示距离场的数据结构有多种，例如均匀3D网格、八叉树和BSP树。

论文[17]提曲了刚体和软体对象问的快速距离计算的问题。为了改善碰撞检测的准确度，对可变形网格上每条边的中心均进行了测试。实验显示，该方法能以交互的速度仿真织物，准确地检测复杂非凸对象的碰撞。

距离场方法提供了很健壮的碰撞检测，因为它们把空间严格地分成内部和外部。距离场方法用于在非交互应用中检测碰撞和自身碰撞。尽管最近提出了高效率的计算距离场的算法，但由于变形几何体距离场必须在运行时间内更新，所以相对于交互应用的要求，距离场方法仍不够快。

4.5 图像空间方法

基于图像空间的碰撞检测算法一般将三维几何对象通过投影绘制到图像平面上，降维得到一个二维的图像空间；然后分析该空间中保存在各类缓存的信息；进而检测出对象之间是否发生干涉 ，如图3所示。

图3 利用深度缓存降维

这是一类较新的碰撞检测算法，由于它们不需要任何预处理，特别适合于包含动态软体对象的环境。图像空间方法中对象是离散表示的，它不提供准确的碰撞信息，碰撞检测的准确度取决于离散误差。准确度和计算效率可以通过改变绘制过程的分辨率在一定范围内平衡。

论文[2]提出虚拟外科手术的图像空间方法。该方法依靠图形硬件来测试虚拟可变形器官和使用者控制的刚性工具间的穿透，可以实时检测碰撞。在四个特殊的应用中，该方法比著名的OBB方法运行起来快约100倍。

在许多图像空间碰撞方法中，Layered DepthImage LDI是基本的数据结构。LDI数据结构的本质是存储每个像素的多个深度值。因而，LDI能用于近似表示对象的体积。_1 中的图像空间方法可用于任意形状软体对象的碰撞检测，但不检测自身碰撞。提出了改进的算法而且考虑自身碰撞。_2。。给出了三种不同的产生 LayeredDepth Image LDI的实现。其中两种基于图形硬件和一种软件方法。结果显示，在几何复杂环境中图形硬件加速了图像空间碰撞检测，但在小型环境的情况下基于CPU的实现 提供了更灵活和更好的性能。

论文[18]提出的基于图像空间的碰撞检测算法主要采用对物体表面进行自动分解，将凸分解结果合理地组织成层次二叉树结构，以及绘制加速等技术，能处理任 意形状的多面体。该算法在性能上有较大的提高。_2 给出了两种有效的优化技术以提升算法效率。与常规图象空间碰撞检测算法相比，除了在性能上的优势之外，其准确性不取决于绘制视窗的分辨率的大小，而与基于 几何的碰撞检测算法精度一致；其通用性更好，可处理任意三角形网格物体而不限于凸体。但将算法应用于软体对象间的实时碰撞检测和进一步提高算法效率，仍有 待进一步研究。

图像空间方法的优点是不需要耗时的预处理，能检测碰撞和自身碰撞，对象的拓扑可以改变，这些使得它特别适合于动态软体对象。缺点是图像空间方法不提供准确的碰撞信息，而这些信息在基于物理特性的仿真环境中用于进一步计算碰撞响应是必需的。

5 结束语

由于不同的方法输入的数据不同，提供的碰撞信息不同，环境中的对象数量不同，目前无法对所有的方法进行完全一致的比较。软体碰撞检测的关键问题是在实时性和准确性之间确定最佳折衷。

软体碰撞检测同时要求较高的实时性和准确性，如何实现最佳折衷是难点所在。