碰撞检测技术及在桥梁视景仿真中的应用

袁丽娜 ， 赵贵斌

（1. 北京航空航天大学机械工程及自动化学院，北京 100191； 2. 五邑大学机电工程学院，广东 江门 529020）

碰撞检测(Collision Detection)及优化是视景仿真技术中一项非常重要的技术，是影响视景仿真系统逼真度和现实感的重要因素。碰撞检测问题是基于现实生活中一个普遍存在的事实：两个不可穿透的对象不可能共享相同的空间区域。因此，碰撞检测的基本任务是确定两个或多个物体彼此之间是否发生接触或穿透。碰撞检测涉及到3D 空间、几何模型表示、分层数据结构、测试方法等，它实质上是通过判断两个物体之间的距离（即距离检测）或重叠与相交（即碰撞检测）情况来实现的[1]。

在计算机图形学和仿真系统中，碰撞检测是一个最为基本且重要的组成部分，主要应用领域包括视景仿真系统、虚拟制造、计算机动画、游戏、机器人技术、CAD /CAM 等。随着计算机硬件和软件的发展，虚拟物体越来越逼真，动作也越来越细腻，这就要求虚拟物体要用更精细的模型来表示，由此也要消耗更多的时间进行虚拟物体的碰撞检测，这就对检测算法提出更高的要求，故对碰撞检测技术的研究就显得尤为重要。

1 碰撞检测概述

通常碰撞检测分为静态碰撞检测、伪动态碰撞检测和动态碰撞检测。其中，静态碰撞检测是判断某一活动对象在某个特定的位置和方向上是否与环境中的对象相交；伪动态碰撞检测是根据活动对象的运动路径检测它是否在某一离散的采样位置方向上与环境中的对象相交；动态碰撞检测则是检测活动对象扫过的空间区域是否与环境中的对象相交。三者的侧重点各不相同，静态碰撞检测一般没有实时性的要求，在计算几何中有着广泛的研究；动态碰撞检测的研究一般都考虑到四维时空问题并要求结构空间精确的建模；而伪动态碰撞检测有关于时间点和运动参数之间的信息，可以通过开发时空相关性获得较好的性能。虚拟环境中的碰撞检测一般属于伪动态碰撞检测的范围[2]。大多数的仿真系统中的碰撞检测也属于伪动态碰撞检测的范畴。

仿真环境中的碰撞检测问题可简化描述为：碰撞检测系统的输入模型为环境对象和活动对象的几何模型，模型由基本的几何元素构成。环境对象可以是刚体对象，也可以是弹性体对象，它们的位置和方向不发生变化，但弹性体对象在外力的作用下可发生形变。活动对象可以在仿真环境中自由运动，方向和大小完全取决于仿真过程或者用户控制的输入设备，很难用关于时间的运动方程来表示，只能得到某一时间采样点相对于前一时间采样点或一固定参照物的运动信息（旋转角度和平移量）表示。其任务是确定在某一时刻两个几何模型是否发生干涉，即判断它们的交集是否为空，一旦碰撞发生，还需确定碰撞点[2]。

碰撞检测的开始一般是假设当前仿真环境中物体还未发生碰撞，再根据用户的操作，开始更新移动对象的位置。若有碰撞发生，则将对象回移到移动前的位置，则避免了它穿越被碰撞物。如果两个完全封闭的多面体发生碰撞时，其中一个多面体至少会有一个面与另一个多面体的至少一个面发生相交。若能在碰撞发生时立刻检测到相交，然后将两个物体的位置稍做调整，则可消除碰撞现象。以上是实现碰撞检测的基本方法[3]。

2 碰撞检测算法

碰撞检测算法可从时间域和空间域对其进行分类。

从时间域的角度，碰撞检测算法可分为静态碰撞检测算法、离散碰撞检测算法和连续碰撞检测算法三类。

静态碰撞检测算法是指当场景中物体在整个时间轴t 上都不发生变化时，用于检测在这个静止状态中各物体之间是否发生碰撞的算法。静态碰撞检测问题在计算几何中有着广泛的应用与研究，一般对这类算法没有实时性的要求，但对算法精度要求较高。

离散碰撞检测算法则是指在时间轴的每个 离散点 nttt ,,,10… 上不断地检测场景中所有物体 之间是否发生碰撞的算法。从本质上说，离散碰撞检测算法在每一时间离散点上可以通过类似于静态碰撞检测算法的方法来实现的，但它更注重算法效率。从整个时间轴来看，由于算法的时间离散特性，这类算法至少存在以下两个问题：① 存在刺穿现象。当时间步长过大时，两物体可能在发生了一定深度的刺穿后才被检测到已发生碰撞，因此无法保证物体的运动真实性；② 存在碰撞遗漏的情况。对于较狭窄的物体，当运动物体在相邻时间离散点上的两个位置恰好处于该狭窄物体两侧时，离散算法将无法正确地检测出物体所发生的碰撞。

连续碰撞检测算法是指在一个连续的时间 间隔[ t0, tn]内，判断运动物体是否与其他物体相 交的算法。连续碰撞检测算法的研究一般涉及到四维时空问题及结构空间精确的建模，这类算法能较好地解决离散碰撞检测算法存在的上述两个问题，但通常计算速度比较慢，尤其是在大规模场景中很难实现实时碰撞检测。

离散碰撞检测算法尽管存在一些问题，但由于其检测过程的快速性能较好地迎合大多数对实时碰撞检测的需求，所以仍是目前碰撞检测算法研究的重点和热点。此外，人们还可通过一些优化方法在一定程度上减轻或降低离散碰撞检测算法的上述两个问题的影响。例如，采用自适应步长技术和可中断的碰撞检测技术等来改善这两个问题。因此，在视景仿真系统中大多采用离散算法作为系统的碰撞检测算法。

从空间域的角度来分，碰撞检测算法大体可分为两大类：一类是基于物体空间的碰撞检测算法；一类是基于图像空间的碰撞检测算法。这两类算法的主要区别是利用物体三维几何特性进行相交判断还是利用物体二维投影的图像加上深度信息来进行相交分析。

基于图像空间的碰撞检测算法是一类较新的算法，它能有效地利用图形硬件的绘制加速功能来提高碰撞检测算法的效率。近几年图形硬件技术的飞速发展，图形加速卡在性能不断迅速提高的同时甚至出现了可编程的功能，使得基于图像空间的碰撞检测算法进入了一个新的发展阶段。

（1） 基于物体空间的碰撞检测算法

基于物体空间的碰撞检测算法一直是人们研究的重点，已有相当的研究成果，如层次表示法、几何推理、代数范式、空间划分、解析方法和最优化方法等技术的应用，使碰撞检测有了更好的实时效果。基于物体空间的碰撞检测算法可进一步分为基于物体的不同表示模型和基于不同的空间结构的表示模型。

物体的表示模型不同，所采用的碰撞检测算法就不同。因此，合理的选择物体的表示模型能提高碰撞检测算法的效率。目前在三维图形和CAD/CAM 领域中存在多种几何表示模型，但最主要的是多边形表示模型和非多边形表示模型。

面向不同表示模型的碰撞检测技术各有特点，算法效率也各有不同。合理的空间结构选择可提高碰撞检测算法的效率，根据所用空间结构的不同可将碰撞检测算法分为两类：空间剖分法(Space Partition)和层次包围盒树(Hierarchical Bounding Volume Trees)。这两类方法都是通过尽可能减少进行精确求交的物体或图元对数来提高算法的效率。不同的是，空间剖分法采用对整个场景的层次剖分来实现简化，而层次包围盒树是对场景中的每个物体构建合理的层次包围盒树来实现简化。

场景的层次剖分方法主要有均匀剖分、BSP树、k-d 树和八叉树(Octree)等。基于这些空间剖分技术的碰撞检测算法也频繁出现，但这类碰撞检测算法在处理不同的场景和具有不同形状及复杂度的物体时较难保持比较一致的检测效率。

物体的层次包围体树可以根据其所采用包围体类型的不同来加以区分，主要包括层次包围球树、AABB 层次树、OBB 层次树、k-dop 层次树、QuoSpo 层次树、凸块层次树以及混合层次包围体树等。图1～图5 分别给出了层次包围球、AABB 盒、OBB 层次树、6-dop 包围盒、凸包围盒的示意图。

建构物体层次包围体树既可采取自顶向下的策略，也可自底向上来进行。目前基于层次包围体树的算法多数采取自顶向下的方式来建构物体的层次包围体树。

图1 层次包围球树构建图

图2 AABB 包围盒

图3 OBB 层次树

图4 6-dop 包围盒

图5 凸包围盒

（2） 基于图像间的碰撞检测算法

基于图像空间的碰撞检测算法一般利用图形硬件对物体的二维图像采样和相应的深度信息来判别两个物体之间的相交情况。这类算法的优势在于能有效利用图形硬件加速技术来减轻CPU 的计算负荷，从而达到提高算法效率的目的。基于图像空间的碰撞检测算法由于其检测结果的不精确性和对于硬件支持的依赖而一直发展较慢。近年，随着图形硬件计算性能的迅速增长，基于图像空间的碰撞检测算法也随之进入了一个新的快速发展阶段。

3 碰撞检测的优化[4]

消减碰撞检测中不必要的数据及计算，可大大提高碰撞检测的效率；通过运动填充、检测预判也可节省用于碰撞检测的时间。

消减数据的方法有网格分割法和球体覆盖法等方式。网格分割是将虚拟空间划分成规则的格网，由此将场景中的物体分割成更小的群组（如图6）。此方法的目的是为了减少系统进行碰撞检测时实体与实体的比较次数，每当移动一个物体，就计算出该物体所在的网格；对于实体相互叠置的情况，虽然是三维场景，亦可采用映射二维网格来分割场景。

图6 网格分割示意图

球体覆盖是用球形近似地表示物体或物体的一部分，然后再判断这些包围球是否相交。这样仅仅需要测试两个球体中心的距离是否小于它们的半径和，若小于即表示发生了碰撞，如图7。如果用球心距离的平方与半径和的平方进行比较，这样可取得更好的计算效率，因此可在计算距离时除去复杂的开方运算。若检测到发生了碰撞，那么就进一步提高精度，将大的球体分割成一系列小的球体，并检查各小球体是否发生碰撞。通过不断地分割检查直到得到满意的近似值为止。

细节的丢失往往会造成仿真效果失真现象发生，因此在进行仿真时应高度重视这个问题。在仿真系统中物体的运动就是物体从一个空间坐标点直接跳跃到另一个空间坐标点。所谓“平滑的”移动也是通过减少跳动的距离来实现的。物体运动得越快，它在固定的时间段内跳过的距离就越大。如果物体在两帧之间跳过的距离过大，就会发生“细节丢失”现象。因为，其它物体有可能在此时间内经过该物体跳过的空间。因此，需将检测延伸至运动的间隙，也就是运动间隙填充。为了解决“细节丢失”问题，须建立一个围绕物体的凸壳，该凸壳包围了物体移动所经过的空间。当检测碰撞时，可用凸壳代替实体的实际形状（见图8）。

图7 球体覆盖碰撞检测示意图

图8 运动物体的凸壳

碰撞检测的预判断是通过找出每一实体上位于其它实体内的顶点来检测碰撞的。例如，若实体的一个顶点位于另一实体内，就可知它们存在碰撞，无须进行任何多边形相交的检测。虽然，此方法不足以完全确定一个碰撞的发生，但它确实比多边形比较的方法快多了。另一种预判断的方法是判断两个实体的包围盒是否相互叠置，若相互叠置，再用平面分割实体的方法进行检测。

4 碰撞检测在桥梁视景仿真中的应用

这里以船舶与桥墩的碰撞为例说明碰撞检测在视景仿真的应用。在该例中采用柱体来构造桥墩的模型，以凸多面体来构造船舶模型（见图9）。由于在视景仿真中物体的运动特性与现实的物体运动特性有许多不同，在视景仿真中物体的运动是以帧的方式在时间流里进行空间的跃动，仿真中在同样距离的运动中设置的帧数越多越接近现实的物体运动，但同样会带来更多的仿真计算和渲染时间。在该例中先使用球体覆盖技术（见图10）和检测预判断来优化检测计算，再使用OBB 层次树来进行碰撞检测（见图11），得到了理想的效果。

图9 船桥模型

图10 球覆盖检测

图11 船和桥墩的OBB 层次树图

首先计算出可能会与船舶发生碰撞的桥墩以及船舶的凸壳，假设可以得到n 个三角形，记 做△ pkqkrk，其中 pk、qk和 rk分别是三角形k的三个顶点；可以将三角形k 的面积记作 ak，k = 1,2,3,… , n ，那么凸壳的整个面积就可以记作aH，三角形i 的质心为 mi= ( pi+ qi+ ri)/3。整个凸壳的质心 mH是所有三角形质点的加权平 均值

给出计算3×3 协方差矩阵的公式c，其特征向量就是所求包围盒的方向向量

将计算出的特征向量归一化，这些向量就是 OBB 的方向向量 au、 av和 aw。找到OBB 的中 心及其半径，计算出凸壳上的点在向量方向上的投影大小；找到每个方向上的最大值和最小值，从而确定包围盒的大小和位置。

5 结 论

随着计算机硬件的快速发展，普通的PC 机具有了更好的性能，在图形显示和运行速度方面有了显著的提升，以前在普通PC 机无法完成的仿真现在也能够顺利实现了，而随着软件的发展和仿真系统的广泛应用，关于碰撞检测算法的研究也越来越深入，仿真系统也有了更好的细节表现。

[1] 丁 佳. 大型复杂场景中快速碰撞检测技术的研究[D]. 成都： 电子科技大学, 2007.

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

[3] 涂 超. 虚拟空间中的碰撞检测[J]. 武汉理工大学学报, 2001, 11(11)： 84-87.

[4] 涂 超, 颜辉武. 碰撞检测技术研究[J]. 计算机工程与应用. 2001, 19： 142-143.

[5] 王志强, 洪嘉振, 杨 辉. 碰撞检测问题研究综述[J]. 软件学报, 1999, 10(5)： 545-551.

[6] 徐 刚, 陆廷金, 耿汝波. 高速虚拟仿真物体的碰撞检测方法[J]. 弹箭与制导学报, 2008, 28(1)： 323-326.