碰撞检测算法研究综述

王嘉+李孔清

摘要：碰撞检测算法作为虚拟现实技术的关键问题之一得到了广泛的研究和发展，并且具有重大的意义和广阔的前景。首先，从静态和动态两方面介绍了碰撞检测算法的研究现状，其中，动态碰撞检测算法是目前研究的热点；其次，介绍了动态碰撞检测算法中的离散碰撞检测算法和连续碰撞检测算法，其中，离散碰撞检测算法是目前研究的热点；再次，介绍了离散碰撞检测算法中的基于物体空间的碰撞检测算法和基于图像空间的碰撞检测算法，其中，着重介绍了基于物体空间的碰撞检测算法中的空间分割法和层次包围盒法；最后，提出了一些热门碰撞检测算法中存在的问题及发展建议。

关键词：碰撞检测；静态；动态；基于物体空间；基于图像空间；空间分割；包围盒

1背景

近十几年来，虚拟现实技术得到了快速发展，也广泛应用在其他行业中，比如游戏、医疗、建筑等。其中，虚拟现实的关键问题之一是碰撞检测，由于对场景的真实性和对交互的实时性要求越来越高，使得碰撞检测算法成为计算机仿真领域研究的热点。国内外学者做了大量的研究和实验，提出了许多可靠的技术来提高碰撞检测的效率。

2碰撞检测算法分类

碰撞检测算法总的可以分为两类，一类是静态碰撞检测算法，其针对的是静止状态下各物体是否发生碰撞，要求精度较高；一类是动态碰撞检测算法，其针对的是位置变化状态下各物体是否发生碰撞，如三维游戏中人在行走时是否会与墙壁、树木等的碰撞。动态碰撞检测算法又可分为离散碰撞检测算法和连续碰撞检测算法。其中，离散碰撞检测算存在一些问题，比如在离散的时间间隔内，两个物体占有了同一空间等，但由于其检测速度快，目前仍旧是研究的重点。连续碰撞检测算法能够精确的建模，较好的模拟出物体之间的碰撞，但其检测速度较慢。基于空间的不同，离散碰撞检测算法可分为基于物体空间的碰撞检测算法和基于图像空间的碰撞检测算法。基于物体空间的碰撞检测算法应用较为广泛，是目前研究的重难点，其又可分为层次包围盒法和空间分割法。

3静态碰撞检测算法

静态碰撞检测算法是指在某一时刻或者在某一位置时物体之间是否发生碰撞，该算法对精度的要求较高且计算复杂性也较高。

Uchiki，Ohashi和Tokoro等人研究了一种在运动仿真中的碰撞检测算法，该算法被称作空间占有法，即利用两个物体在虚拟运动时共同占有了同一空间来模拟碰撞。

李辉提出了平面内互不相交的两个凸多边形P和Q，分别有n和m个顶点。在其中一个沿任意给定的方向移动时不与另一个相撞以及一个凸多边形相对于另一个的所有可移动方向等两个问题，并分别给出了凸多边形可移动性的最优算法：0（10g（n+m））和0（n+m）。

汪嘉业引研究了平面上顶点数分别为m，n的简单多边形平移时确定碰撞部位的最优算法，该算法在两个凸多边形不相交的条件下，利用单调折线可确定二者是否相碰，并计算出其时间复杂度为O（m+n）。

曲吉林采用平面扫描法，通过提取两个边数分别为n和m的多边形的单调链来确定任意多边形平移时的碰撞部位，并计算出了时间复杂度为0“m+n）log（m+n））的算法。

申静波和唐国维等人提出了基于夹边边对的空间平面凸多边形快速相交检测算法，该算法将应用对象从三角形扩展到任意空间平面凸多边形，直接进行多边形间求交计算。

静态碰撞检测算法不需要预处理，对平面内凸多边形的研究较多，而对凹多边形研究较少。笔者认为可通过将凹多边形分解为多个凸多边形来进行研究。

4动态碰撞检测算法

4.1基于物体空间的碰撞检测算法

基于物体空间的碰撞检测算法利用物体三维几何特征来展开计算，主要分为空间分割法和层次包围盒法。

4.1.1空间分割法

空间分割法是指将整个虚拟空间划分为一系列等体积单元格，只对处于同一单元格的物体进行检测。当空间中有物体运动时，只需要重新计算物体占有的空间即可。常见的有均匀网格、八叉树和BSP树等。均匀网格的关键是选择适当尺寸的网格，使得计算准确且效率较高，均匀网格适合软体对象的碰撞检测；八叉树的关键是将空间分解为八个均等立方体，将检测到碰撞的立方体再分解为八个立方体，直到检测出碰撞部位為止，一般用于三维空间；BSP树是将空间分割成两个子空间，关键是在物体之间找出分割平面，若存在分割平面则两物体不相交，可用在任意维度的场景中。

Moore和Wilhelms提出了两种碰撞检测方法。一种算法用来处理物体的三角面片化，且其适用于柔软或刚性表面；另一种算法基于Cyrus-Beck裁剪算法，通过检测凸多面体顶点是否互相包含来判断碰撞与否，对于凹多面体可将其分解为凸多面体，其适用于刚性多面体。

Ganter和Isarankura提出了空间划分法，该技术将包含一个给定物体的空间进行细分。使用这些分区，所有的测试可以被限制在两个物体之间的重叠的局部区域，包含在重叠区域的子空间基于最小值和最大值来排序以进一步降低检测时间。

刘雁翎和诸昌钤一研究出了一种适合处理动态场景的交互树，该算法首先利用物体之间的位置关系及从属关系将物体组织在树状层级结构中，之后在关系树的基础上对叶结点进行八叉树剖分，最终生成交互树。该算法既保持了八叉树优点又可以规律地剖分对象。

王国锋等人利用HV分割算法将三维物体分割成更小的包围盒，当两个物体距离相当近时可以精确检测出是否碰撞。由于使用HV分割后可以容易地实现包围盒的重构，因此也适用于旋转的三维物体。

空间分割法适合于物体分布均匀且稀疏的场景。对于移动的物体，只需要重新计算物体所占的单元格即可。当物体较多且分布不均匀时需要将单元格分割成更小的单元格，大量的单元格之间的相交测试降低了碰撞检测速度并且会占用大量的存储空间，从而导致效率降低。

4.1.2层次包围盒法

层次包围盒法是指用体积略大且形状相似的盒子来包围物体。首先检测两包围盒是否相交，相交后再详细检测包围盒之间的重叠部分，从而判断出物体之间是否碰撞。该算法可减少参与测试的包围盒的数量，提高了效率。层次包围盒法可分为AABB、包围球、OBB和K-DOPs包围盒。简单性较好的是AABB和包围球；紧密性较好的是OBB和K-DOPs；更新性较好的是包围球和0BB；存储量较少的是AABB和包围球；适用于软体对象的是AABB和K-DOPs。其中AABB是最早使用的包围盒。

1）AABB

Smith等人提出了一种针对物体在运动过程中变形的算法，该算法基于AABB，在每一步都重新计算物体的包围盒，且对凹凸物体均适用。

Gino提出了一个基于AABBs的复杂模型间进行刚性运动和变形的碰撞检测方法。该方法通过递归细分，自上而下构建包围盒树，加速了AABBs间的重叠测试，并且在模型变形时快速更新了AABB树。

潘振宽和李建波通过对AABB包围盒的压缩优化了AABB方法，提高了测试的速度。

方彬等人在初步检测阶段采用基于时间的AABB包围盒和间隔减半法剔除场景中不相交的物体；在详细检测阶段通过对物体建立AABB来精确相交区域。该方法较好地处理了高速运动物体的遗漏和刺穿问题。

2）包围球

Palmer和Grimsdale首次提出了包围球法，该算法使用球体来包围物体，可快速定位潜在的碰撞区域。

rru等人提出了一种计算边界球与边界CSG基元间距离的算法，通过将整个空间分解为相对位置和考虑球面几何特征，得到闭式距离公式。该算法对于复杂物体的实时碰撞有较好的效果。

Benitez等人用球面结构来近似任意非凸物体从而来检测物体间的碰撞。该算法在预处理阶段是自动的，每级的球面树可用于产生近似响应且效率较高。

靳雁霞等人-提出了一种融合R-Sphere包围球的变形体碰撞检测算法，该算法将有公共顶点的三角片构造成包围球，首先利用包围球快速剔除不相交的物体，之后利用粒子群算法将三维问题转换成二维问题。该算法可有效解决变形体碰撞的问题。

3）OBB

Gottschalk等人提出了方向包围盒树，由于该包围盒树方向的任意性使得它可以紧密的包围物体，该算法可高效地检测出复杂模型间的碰撞，且对于一般的多边形模型均适用。

章勤等人提出了一种基于OBB的改进算法，该算法利用帧之间的关联性，对虚拟环境中已发生的碰撞进行缓冲，同时利用预测试的方法有效提高了碰撞检测的效率。

王鹏等人通过在三角形网格中增加特征元素的信息（点、边、面）形成特征描述三角形，再结合OBB法来进行碰撞检测。该算法可有效减少基元测试的数量。

胡咏梅研究了一种AABB和OBB相结合的碰撞检测算法，首先通过对象投影来快速剔除不相交的物体，接着用AABB构建剩下的物体，初步判断出可能相交的物体，最后用OBB来精确检测。该算法实时性较好。

4）K-DOPs

Kay和Kajiya提出了层次包围盒技术，该技术依据物体形状选取若干组不同方向的平行平面对来包围物体，该包围盒能够更紧密地包围物体，使测试精度更高，这就是最早的K-DOPs的概念。

Klosowski等人首次提出了基于K-DOPs的快速碰撞检测算法。K-DOPs被定义为包含该对象且它的所有面的法向量都取自一个固定的方向（k个向量）集合的凸包。该凸包既简单又具有良好的紧密度。

Mezger等人针对纺织品的碰撞处理的精度要求特别严格这一情况，设计出特别的可变形表面，并采用K-DOPs包围盒和四叉树来优化碰撞检测，从而减少了内存和成本。

李文娟等人研究了基于K-DOPs的改进的虚拟服装仿真系统碰撞检测算法，该算法通过引人表面曲率准则及法向量锥的概念，优化了K-DOPs算法并使服装仿真达到了逼真效果。

使用层次包围盒法可以快速剔除场景中不相交的物体，因此在初步检测阶段采用该方法不失为一个较好的选择，可节省检测时间。但是该方法不适用于大规模复杂物体之间的相交检测，因为会增加包围盒的数量，使得相交测试次数增多，从而降低测试速度和占用大量存储空间。可将空间分割法和层次包围盒法结合起来使用，从而在满足实时性的同时也降低时间复杂度。

4.2基于图像空间的碰撞檢测算法

基于图像空间的碰撞检测算法利用图形硬件来判断两物体的相交情况。主要包括两种：第一种是将GPU视为与CPU一样的处理器来加速检测碰撞，利用缓冲区的颜色值和深度值来判断物体之间的相交情况；第二种是将三维物体投影到二维空间中，通过分析保存的缓存信息来判断物体之间的相交，虽然该转化过程较复杂，但是计算过程简单。

Shinya和Forgue提出了一种新的实时干涉检测算法。该算法利用图形硬件技术，在绘制凸体时按照视窗口上像素的大小深度序列来排序，之后检测凸体在像素上的最大深度值与其最小深度值是否相邻来判别相交与否。

Naga等研究了在大型环境中使用图形硬件技术的复杂模型间的碰撞检测。该算法首先利用可见性查询判断潜在的碰撞集，然后在CPU中进行精确的检测。

Han-Young等人提出了一种新的基于图像空间的实时碰撞检测算法，该算法利用GPU计算潜在的碰撞集，利用CPU执行标准的三角形相交测试。该算法可处理动态模型，且不需要任何预处理。

Kim等人提出了一种使用CPU和GPU的混合并行连续碰撞检测算法，即HPCCD。该算法通过使用四个CPU核心和两个GPU实现了超过一个数量级的性能改进，并且解决了由三角面片组成的柔性模型之间的碰撞检测问题。

于海军等人利用图形处理器的加速功能研究了基于图像空间的快速碰撞检测算法。该算法首先利用凸块层次二叉树技术和方向包围盒快速剔除场景中不相交的凸块，然后利用recode算法精确计算。该算法可适用于复杂环境中。

基于图像空间的碰撞检测算法通过将GPU视为与CPU一样的处理器来减轻CPU的计算负荷。该算法可处理不规则形状的物体，并且在预检测阶段有较好的平稳性，适用于复杂体和软体对象的碰撞检测。但是该方法也存在一些缺点：由于其不能提供准确的碰撞信息导致检测结果不够精确且不太适用于大规模的场景。

5结束语

基于物体空间的碰撞检测算法是目前研究的热点，也产生了许多有效的算法。空间分割法可在物体分布均匀的环境中剔除不相交的物体。但是针对物体分布不均匀的情况，如何优化单元格的尺寸是一个仍需研究的问题，若分割不当会造成计算量过大，降低计算效率。笔者认为可将空间分割法与其他算法结合起来使用，利用空间分割法剔除场景中分布均匀的物体，再结合其他算法精确检测非均匀物体之间的相交情况。

层次包围盒法由于构造简单、检测快速、效率较高，使其成为应用比较广泛的一类算法。不同的包围盒的算法效率和适用条件不同，需要根据对象选择适合的包围盒。层次包围盒法也存在一些缺点：当场景中对象较多且较复杂时，会延长相交测试的时间和占用大量的存储空间。笔者认为可采用混合包围盒，即在初步检测阶段选用相交测试简单、快速、紧密性差的包围盒来剔除场景中不相交的物体，如包围球和AABB等；在精确检测阶段选用相交测试复杂、紧密性好的包围盒来进一步判断相交情况，如0BB和K-DOPs等。也可采用与其他算法的混合使用来提高效率。

基于图形空间的碰撞检测算法是目前较新的算法，该类算法不需要预处理，适用于初步检测阶段。囿于图形硬件的发展，该类算法目前还面临着一些问题。例如：如何减轻CPU的负担来有效平衡CPU和GPU之间的负载；如何在检测精度和绘制速度中寻求平衡，以达到既提高检测精度又保持较快的绘制速度；如何开展在大规模场景中的应用等问题。笔者认为在今后的工作中应重点研究该类算法与基于物体空间的碰撞检测算法的结合使用。相信随着计算机技术日新月异，该类算法会得到飞速发展。