碰撞检测

二维碰撞检测算法碰撞检测（CollisionDetection,CD）也称为干涉检测或者接触检测，用来检测不同对象之间是否发生了碰撞，它是计算机动画、系统仿真、计算机图形学、计算几何、机器人学、CAD\CAM等研究领域的经典问题。碰撞物体可以分为两类：面模型和体模型。面模型是采用边界来表示物体，而体模型则是使用体元表示物体。面模型又可根据碰撞后物体是否发生形变分为刚体和软体，刚体本身又可根据生成方式的不同分为曲面模型和非曲面模型。目前对于碰撞的研究多集中于面模型的研究，因为体模型是一种三维描述方式，对它进行碰撞检测代价较高。而在面模型的研究中，对刚体的研究技术更为成熟。下面列举几种常用的碰撞检测技术：1：包围盒（boundingbox）是由Clark提出的，基本思想是使用简单的几何形体包围虚拟场景中复杂的几何物体，当对两个物体进行碰撞检测时，首先检查两个物体最外层的包围盒是否相交，若不相交，则说明两个物体没有发生碰撞，否则再对两个物体进行检测。基于这个原理，包围盒适合对远距离物体的碰撞检测，若距离很近，其物体之间的包围盒很容易相交，会产生大量的二次检测，这样就增大了计算量。包围盒的类型主要有AABB(AlignedAxisBoundingBox)沿坐标轴的包围盒、包围球、OBB(OrientedBoundingBox)方向包围盒和k-DOP(kDiscreteOrientationPolytopes)离散方向多面体等。AABB是包含几何对象且各边平行于坐标轴的最小六面体，两个AABB包围盒相交当且仅当它们三个坐标轴上的投影均重叠，只要存在一个方向上的投影不重叠，那么它们就不相交。AABB间的相交测试和包围体的更新速度比其他算法效率高，因此使用最广泛，尤其适用于多物体运动的大规模环境和变形体碰撞检测。OBB包围盒的相交测试基于分离轴的理论的，它的构造关键在于包围盒最佳方向的确定，最佳方向必须保证在该方向上包围盒的尺寸最小。由于其较好的紧密性，大大提高了算法的效率，但需要较多的存储空间，构造和更新包围体的速度都比较慢，不能有效地处理变形体等情况。k-DOP使用k/2对的平行平面来包围物体，如果在由k-DOP的边构成的固定方向集合种的某个方向上的投影不重叠，则包围盒必不相交；如果在所有方向上的投影都重叠，则包围盒必相交。通过调整k的取值，k-DOP可以在简单性、紧密性中达到一定的折衷，从而提高碰撞检测的效率。包围盒是目前应用最为广泛的碰撞检测方法，包围盒本身的简单性和所包围物体的紧密性是相互矛盾的，简单性越高其紧密性差，反之如此，所以如何解决这个矛盾是包围盒技术的关键。2.空间剖分法空间剖分法是依据某种规则将场景空间划分成若干小单元，并记录所有单元内的特征，通过查询同一个单元或相邻单元内的特征间的相交情况来判断是否发生碰撞检测。按照剖分空间的方法可分为均匀剖分和非均匀剖分。均匀剖分是将场景中的空间均匀的划分为大小一致的单元格，非均匀剖分的方法很多，如BSP树和Kd树等。空间剖分法使用于物体之间距离较远的场景，因为如果物体之间的距离很近，需要对单元格进行更深的递归分割，这样需要更多的空间存储单元格，并需要进行更多的单元格相交测试，从而降低了效率。3.距离场距离场是一种基本的图形表示模型，表示距离物体表面的最小距离。距离场是矢量场，距离的正负可表示物体在外部或内部，用距离场表示表面封闭的物体不需要物体的拓扑信息和约束信息，能快速计算碰撞后的穿刺距离和法向量。距离场的空间划分方法有很多种，标准栅格法、八叉树和BSP树等，[1]中提出了自适应的采样距离场(ADFs)，它在距离场含有细节的时候采用较高的采样率，在场变化小的时候，采用较低的采样率，从而避免在细节部分采样数量不够多，导致整体碰撞检测精度下降。采样策略在建立距离场之前确定，从而控制了精确度，能最有效地利用内存。距离场进行碰撞检测是逐点进行的，通过把一个物体的顶点逐个与另一个物体的距离场进行检测，确定是否发生碰撞。当然碰撞还存在边与边之间的相交，在[2]中提出了一种类似划分的方法，他们通过增加测试变形特征的每条边的中心来增加碰撞检测的精确度。4.图像空间方法图像空间的碰撞检测方法不需要为物体建立层次包围体树模型，它利用图形硬件将三维物体降为二维图像，对二维图像进行采样并建立相应的深度信息，通过对信息的分析判断是否发生碰撞。图像空间法不需要预处理，适合动态的变形体，但是它需要降物体光栅化，其精度取决于对物体的离散化程度，不能提供准确的碰撞信息，是用效率换取精度。但是，图像空间法是一类较新的碰撞检测方法，[3]和[4]提出过利用两个深度缓存分别保存物体的最小和最大深度(对应于物体的最前层和最后层)，通过判断第二个物体象素的最大深度值是否介于第一个物体象素的最大最小深度值之间来确定是否碰撞，但只能判断凸体。[5]提出了利用模板缓存来保存窗口中每个象素上所代表的射线进入物体和离开其他物体的次数，之后读取模板缓存中的值来判断两物体是否相交，进一步改善了图像空间碰撞检测算法的局限性。[6]将图象空间碰撞检测算法率先用到动态布料仿真中，利用图形硬件的深度缓存和颜色缓存来判别衣服和虚拟人体模型是否发生碰撞，该算法也是只能用于凸体。[7]提出了能检测任意物体碰撞的方法，为物体计算层次深度图LDI(LayeredDepthImage)来标识物体的体积，先用AABB包围盒进行相交测试，对相交的包围盒中的物体构建LDI，再进行相交测试，计算相交体积，这就要求物体必须是封闭的。LDI是图像空间方法的基本结构，所以对LDI的改进是提高图像空间方法的关键。[8]中用三中方法改进了LDI，两种是通过图形硬件加速，另一种是通过改进程序，结果显示图形硬件适合几何形态复杂的场景，而以使用程序加速的方法比较灵活，更适合场景较小的情况。5.随机碰撞检测方法随机碰撞检测是用效率换取精度的一类碰撞检测方法，注重碰撞后的实时模拟，是碰撞领域的一个热点。随机碰撞检测可分为Average-case方法和基于随机选择几何元的碰撞检测方法。Average-case方法是以包围盒相交区内两个物体的特征个数的比作为是否发生碰撞的标准，算法灵活，能控制碰撞检测的精确度。随机选择几何元的碰撞检测方法是通过在碰撞对象内部随机取样作为初始的潜在的碰撞区域，然后跟踪采样对。[9]中提出采用k-dop来限制采样点在两物体之间较接近的部分，采用爬山法来逐步逼近局部最小并保留一个哈希表纪录访问过的特征对。[10]和[11]分别提出利用时空一致性和时间一致性，对随机选择几何元的碰撞检测方法进行改进。6.智能算法智能算法是目前一个比较新的领域，是受自然规律的启迪，根据仿生原理，模仿求解问题的算法，这方面的内容很多，如人工神经网络技术、遗传算法、模拟退火算法、模拟退火技术和群集智能技术等。[12]从求解物体的最短距离的角度判断物体碰撞的可能性，将对最短距离的计算问题变成对约束条件的非线性规划问题，利用遗传算法对其求解，实验证明，该算法计算速度快、计算精度高。[13]提出利用粒子群算法和随机碰撞检测方法相结合，通过在物体特征域内采样把三维物体空间内碰撞检测问题转换到二维空间解决，增加了算法的适应性，实验证明该算法能有效的处理变形体的碰撞检测问题。[14]提出用顶点的凸包来表示凸多面体，将物体间距离的问题归结为约束条件的非线性规划问题,利用模拟退火遗传算法对该问题进行求解，结果表明，该算法有较高的计算效率和计算速度。智能算法在碰撞检测领域的应用目前还不广泛，但它本身在解决优化等问题上的优势，对今后碰撞检测技术的提高具有一定的意义。由于对于不同的物体，比如刚体和软体，所采用的方法不同，并且对于不同的使用领域对碰撞检测要求的方面不同，比如速度和精确度更侧重哪一方面，等等这些要求，就决定了对碰撞检测算法的筛选和优化。碰撞检测技术在虚拟现实领域的重要性，决定了对它的研究将是一个漫长的过程，而且将会有更多新的算法融入其中。参考文献：[1]FriskenS.F.,PerryR.N.,RockwoodP.,JonesT.R.,Adaptivelysampleddistancefields:Ageneralrepresentationofshapeforcomputergraphics.SIGGRAPH2000,ComputerGraphicsProceedings(2000),249-254.[2]A.Fuhrmann,G.Sobotka,andC.Gross.Distancefieldsforrapidcollisiondetectioninphysicallybasedmodeling.InProceedingsofGraphiCon,2003,58–65.[3]ShinyaandM.Forgue.Interferencedetectionthroughrasterization.TheJournalofVisualizationandComputerAnimation,1991,132-134.[4]G.Baciu,W.S.-K.Wong,andH.Sun.RECODE:animage–basedcollisiondetectionalgorithm.TheJournalofVisualizationandComputerAnimation,1999,181-192.[5]K.Myszkowski,O.Okunev,andT.Kunii.Fastcollisiondetectionbetweencomplexsolidsusingrasterizinggraphicshardware.TheVisualComputer,11(9),1995,497-12.[6]T.Vassilev,B.Spanlang,andY.Chrysanthou.Fastclothanimationonwalkingavatars.InProceedingsofEurographics,2001,137-150.[7]B.Heidelberger,M.Teschner,andM.Gross.Real-timevolumetricintersectionsofdeformingobjects.InProceedingsofVision,Modeling,Visualization,2003，461–468.[8]StefanKimmerle，collisiondetectionandpost-processingforphysicalclothsimulation,Dissertation,Tübingen,2005,28-31.[9]S.Kimmerle,M.Nesme,andF.Faure.,Hierarchyacceleratedstochasticcollisiondetection.InProceedingsofVision,Modeling,Visualization,2004,307–314.[10]LIN.M.C，CANNYJ．F．EfficientCollisionDetectionforAnimation[C],Proc．3rdEurographicsWorkshoponAnimationandSimulation,Cambridge,1992．[11]LaksRaghupathi,LaurentGrisoni,FrancoisFaure,eta1．Anintestinesurgerysimulator：Real—timecollisionprocessingandvisualization[J],IEEETransactiononVisualizationandComputerGraphics，2004，708-718[12]金汉均,李朝晖,张晓亮等,基于遗传算法的凸多面体间碰撞检测算法研究[J],华中师范大学学报,2006.3,40卷1期，25-28[13]李文辉,王天柱,王炜等,基于粒子群面向可变形物体的随机碰撞检测算法[J],系统仿真学报,2006.8,18