来源：第三维度
    作者：梁小红,刘少强
    单位：中南大学信息科学与工程学院长沙

    摘要：介绍软体碰撞检测中主要的层次包围盒方法、空间分割、随机方法、距离场和图像空问方法，从碰撞检测的计算效率与准确性的角度，分析这些算法的优势和不足，指出研究的关键点和难点。

    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空间数据结构

    这种数据结构在计算时间和存储上必须是灵活的和有效率的。

    在碰撞检测应用中，常用的空间分割方法包括：均匀网格、八叉树和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 结束语

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

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

    参考文献

    [1]Jean—Christophe Lombardo，Marie—Paule Cani。FabriceNeyret.Real—time collision detection for virtual surgery[C].Proceedings of Computer Animation.Switzerland Ge.neva：IEEE，1999，82～9l

    [2]June Gyu park，Ginter Niemeyer.Haptic Rendering withPredictive Representation of Local Geometry[C].Proceedirigsof 12th International Symposium on Haptie InterfacesFor VirtuM Environment and Teleoperator Systems.Chicago：IEEE Computer Society，2004，331—338

    [3]李焱，卢晓军，贺汉根.USSCD：一个基于均匀空间分割的快速碰撞检测算法[J].中国图象图形学报，2003，8(12)：1444～1449

    [4]Gottschalk S，Lin M C，Manocha D.OBBTree：A hierarchi—cal structure for rapid interference detection[C].Proceed.ings of ACM Siggraph’96.New Orleans：ACM ，1996，171～180

    [5]Cohen J D，Lin M C，Manocha D，et a1.I—COLLIDE：Aninteractive and exact collision detection system for largescaleenvironments[C].Proceedings of ACM Interactive 3DGraphics Conference.Calif：ACM ，1995，1 89～196

    [6]魏迎梅，王涌，吴泉源，等.刚体在软体对象环境中的碰撞检测的研究[J].计算机学报，2001，24(8)：802～808

    [7] Cameron S A.Collision detection by four—Dimensional in.tersection testing[J].IEEE Trans Robotics and Automat，1990，291—302

    [8]魏迎梅，王涌，吴泉源，等.虚拟手术仿真中碰撞检测问题的研究[J].系统仿真学报，2000，12(5)：572～575

    [9]Jan Klein，Gabriel Zachmann Time—Critical Collision DetectionUsing an Average—Case Approach[C].Proceedingsof the ACM symposium on Virtual reality software an dtechnology.Japan Osaka：ACM，2003，22—31

    [10]Murat Cenk Cavusoglu，Frank Tendick.Muhirate simulationfor high fidelity haptic interaction with deformable objectsin virtual environments[C].Proceedings— IEEEInternational Conference on R0botics and Automation.SanFrancisco：Institute of Electrical and Electronics EngineersInc，2000，2458～2465.

    [11]Jung Kim，Suvranu De，Mandayam A.Srinivasan.Computationallyeficient techniques for real time surgical simulationwith force foedback[C].Proceedings of 10th Symp.On Haptic Interfaces For Virtual Environment.＆ Teleop[11]erator Systems.Orlando：IEEE Computer Society，2002.51～57

    [12]G.Zachmann，M.Teschner，S.Kimmerle，B.Heidelberger，L.Raghupathi，and A.Fuhrm ann.Real —TimeCollision Detection for Dynamic Virtual Environments[z]，IEEE Virtual Reality 2005，March 12～16，2005，Bonn，Germany.Pages 1—32.

    [13]Mezger，S.Kimmerle，O.Etzmub.Hierarchical Techniquesin Collision Detection for Cloth Animation『J].Journal ofWSCG 11，2003，322—329

    [14]Matthias Teschner，Bruno Heidelberger，Matthias Mtiller，et a1.Optimized spatial hashing for collision detection ofdeformable objects[C].Proceedings of Vision，Model—ing， Visualization VMV ’ 03. Germ any Munich ：VMV2003，2003.47 —54

    [15]LIN M.C.，CANNY J.F.Efficient Collision Detection forAnimation[C].Proc.3rd Eurographics Workshop on Ani—mation and Simulation.Cambridge.1992.

    [16][aks Raghupathi，Laurent Grisoni，Francois Faure，et a1.An intestine surgery simulator：Real—time collision pro—cessing and visualization[J].IEEE Transaction on Visual—ization and Computer Graphics，2004，708～7 1 8

    [17]Amulph Fuhrmann，Gerrit Sobottka，Clemens Grob.dis—tan ce fields for rapid collision detection in physicallybased modeling[C].Proceedings of GraphiCon.Moscow，2003.58—65

    [18]范昭炜，万华根，高曙明.基于图像的快速碰撞检测算法[J].计算机辅助设计与图形学学报，2002，14(9)：805—810.

    [19]Bruno Heidelberger，Matthias Teschner，Markus Gross.Real — Time Volumetric Intersections of Deforming Ob—jects[C].Proceedings of Vision，Modeling，VisualizationVMV ’03.Germ any Munich：VMV2003。2003，461 468

    [20]Bruno Heidelberger，Matthias Teschner Markus，Gross.detection of collision and self——collisions using image——space techniques[C].Proceedings of Winter School ofComputer Graphics 04.Bohemia：UNION Agency—Sci—ence Press，2004，145—152

    [21]范昭炜，万华根，高曙明.基于流的实时碰撞检测算法[J].软件学报，2004，15(10)：1505—1514

    [22]魏迎梅.虚拟环境中碰撞检测问题的研究[D].长沙：国防科学技术大学，2000，55—62

    [23]Stephane Guy，Gilles Debunne.Monte—Carlo collisiondetection[R].http：//artis.imag.fr/Publications/2004/GD04/，2005— 11—30