碰撞检测技术

1、碰撞检测技术碰撞检测技术2011-05-06 23 : 00技术-引擎2008-09-05 19 : 50: 55阅读251 10.3碰撞检测技术到目前为止，构造的各种对象都是相互独立的，在场景中漫游各种物体， 墙壁、树木对玩家（视点）好像是虚设，可以任意从其中穿越。为了使场景人物 更加完善，还需要使用碰撞检测技术。10.3.1碰撞检测技术简介无论是PC游戏，还是移动应用，碰撞检测始终是程序开发的难点，甚至可 以用碰撞检测作为衡量游戏引擎是否完善的标准。好的碰撞检测要求人物在场景中可以平滑移动，遇到一定高度的台阶可以 自动上去，而过高的台阶则把人物挡住，遇到斜率较小的斜坡可以上去，斜率 过大则

2、会把人物挡住，在各种前进方向被挡住的情况下都要尽可能地让人物沿 合理的方向滑动而不是被迫停下。在满足这些要求的同时还要做到足够精确和稳定，防止人物在特殊情况下 穿墙而掉出场景。做碰撞检测时，该技术的重要性容易被人忽视，因为这符合日常生活中的 常识。如果出现Bug,很容易被人发现，例如人物无缘无故被卡住不能前进或 者人物穿越了障碍。所以，碰撞检测是让很多程序员头疼的算法，算法复杂， 容易出错。对于移动终端有限的运算能力，几乎不可能检测每个物体的多边形和顶点 的穿透，那样的运算量对手机等设备来讲是不可完成的，所以移动游戏上使用 的碰撞检测不可能使用太精确的检测，而且对于3D碰撞检测问题，还没有几乎

3、完美的解决方案。目前只能根据需要来取舍运算速度和精确性。目前成功商业3D游戏普遍采用的碰撞检测是 BSP树及AABB（axiallyaligned bounding box） 包装盒（球）方式。简单地讲，AABB检测法就是采用一 个描述用的立方体或者球形体包裹住 3D物体对象的整体（或者是主要部分），之 后根据包装盒的距离、位置等信息来计算是否发生碰撞，如图10-24所示。除了球体和正方体以外，其他形状也可以作包装盒，但是相比计算量和方 便性来讲还是立方体和球体更方便些，所以其他形状的包装只用在一些特殊场 合使用。BSP树是用来控制检测顺序和方向的数据描述。在一个游戏场景中可能存在很多物体，它

4、们之间大多属于较远位置或者相 对无关的状态，一个物体的碰撞运算没必要遍历这些物体，同时还可以节省重 要的时间。如果使用单步碰撞检测，需要注意当时间步长较大时会发生两个物体完全 穿透而算法却未检测出来的问题，如图 10-25所示。其解决方案是产生一个4D 空间，在物体运动的开始和结束时间之间产生一个4D超多面体，用于穿透测试。图10-24 AABB包装盒图10-25碰撞检测的单步失控和4D测试读者在程序开发初期有必要对碰撞检测有一个初步的估计，以免最后把大 量精力消耗在碰撞检测问题上，从而降低了在基础的图形编程之上的注意力。10.3.2球体碰撞检测真实的物理模拟系统需要非常精确的碰撞检测算法，但

5、是游戏中常常只需 要较为简单的碰撞检测，因为只需要知道物体什么时候发生碰撞，而不用知道 模型的哪个多边形发生了碰撞，因此可以将不规则的物体投影成较规则的物体 进行碰撞检测。球体只有一个自由度，其碰撞检测是最简单的数学模型，我们只需要知道 两个球体的球心和半径就能进行检测。那么球体碰撞是如何工作的？主要过程如下。n计算两个物体中心之间的距离，并且将其与两个球体的半径和进行比较n如果距离大于半径和，则没有发生碰撞。n否则，如果距离小于半径和，则发生了物体碰撞。考虑由球心cl、c2和半径r1、r2定义的两个球，如图10-26所示。设d 为球心间的距离。很明显，当 d<r1+r2时相交，在实践中

6、通过比较 d2<(r1+2，可以避免包括计算d在内的平方根运算。对两个运动的球进行碰撞检测要麻烦一些，假设两个球的运动向量为di和d2,球与位移向量是一一对应的，它们描述了所讨论时间段中的运动方式。事实上，物体的运动是相对的，例如两列在两条平行轨道上相向行驶的火 车，在其中一列中观察，对方的速度是两车速度之和。同样，也可以从第一个 球的角度来简化问题，假设第一个球是"静止"的，另一个是"运动"的，那么该 运动向量等于原向量di和d2之差，如图10-27所示。图10-27动态球的检测过程球体碰撞的优点是非常适用于需要快速检测的游戏，因为它不需要精确的

7、 碰撞检测算法。执行速度相对较快，不会给 CPU带来过大的计算负担。球体碰撞的另一个劣势是只适用于近似球形物体，如果物体非常窄或者非 常宽，该碰撞检测算法将会失效，因为会在物体实际发生碰撞之前，碰撞检测 系统就发出碰撞信号，如图10-28所示是球体碰撞检测中可能出现的坏情况， 其解决方法是缩小检测半径，或者使用其他检测模型，如图 10-29所示。图10-28球体碰撞的坏情况图10-29缩小检测半径为了解决包容球精确度不高的问题，人们又提出了球体树的方法。球体树实际上是一种表达 3D物体的层次结构。对一个形状复杂的 3D物体, 先用一个大球体包容整个物体，然后对物体的各个主要部分用小一点的球体来

8、 表示，然后对更小的细节用更小的包容球体，这些球体和它们之间的层次关系 就形成了一个球体树。举例来说，对一个游戏中的人物角色，可以用一个大球来表示整个人，然 后用中等大小的球体来表示四肢和躯干，然后用更小的球体来表示手脚等。这 样在对两个物体进行碰撞检测时，先比较两个最大的球体。如果有重叠，则沿树结构向下遍历，对小一点的球体进行比较，直到没有 任何球体重叠，或者到了最小的球体，这个最小的球体所包含的部分就是碰撞 的部分，如图10-30所示。1033 AABB立方体边界框检测用球体去近似地代表物体运算量很小，但在游戏中的大多数物体是方的或 者长条形的，应该用方盒来代表物体。另一种常见的检测模型是

9、立方体边界框， 如图10-31展示了一个AABB检测盒和它里面的物体。坐标轴平行(Axially-aligned)不仅指盒体与世界坐标轴平行，同时也指盒体的每个面都和一条坐标轴垂直，这样一个基本信息就能减少转换盒体时操作 的次数。AABBJ术在当今的许多游戏中都得到了应用，开发者经常用它们作为 模型的检测模型，再次指出，提高精度的同时也会降低速度。因为AABB总是与坐标轴平行，不能在旋转物体时简单地旋转AABB而是应该在每一帧都重新计算。如果知道每个对象的内容，这个计算就不算困难， 也不会降低游戏的速度。然而，还面临着精度的问题。假如有一个3D的细长刚性直棒，并且要在每一帧动画中都重建它的AA

10、BB可以看到每一帧中的包装盒都不一样而且精度也会随之改变，如图10-32所示。图10-31 3D模型与AABB检测盒图10-32不同方向的AABB可以注意到AABB寸物体的方向很敏感，同一物体的不同方向，AABB也可能不同(由于球体只有一个自由度，所以检测球对物体方向不敏感)。当物体在场景中移动时，它的 AABB也需要随之移动，当物体发生旋转时， 有两种选择：用变换后的物体来重新计算 AABB或者对AABB做和物体同样的 变换。如果物体没有发生扭曲，可以通过"变换后的AABB重新计算，因为该方法 要比通过"变换后的物体"计算快得多，因为AABB只有8个顶点。变换A

11、ABB得 出新的AABB要比变换物体的运算量小，但是也会带来一定的误差，如图10-33所示。比较图中原AABB灰色部分)和新AABB右边比较大的方框)，它是通过旋转 后的AABB计算得到的，新AABB几乎是原来AABB的两倍，注意，如果从旋转后 的物体而不是旋转后的AABB来计算新AABB它的大小将和原来的AABB相同。先介绍AABB的表达方法，AABB内的点满足以下条件：xmin < x < xmax ymin < y < ymax zmin < z < zmax因此只需要知道两个特别重要的顶点 (xmin，ymin，zmin)、(xmax，ymax zm

12、ax)，记作：float min=new float0.0f,0.0f,0.0f；float max=n ew float0.0f,0.0f,0.0f；中心点是两个顶点的中点，代表了包装盒的质点。float ce nter=new float0.0f,0.0f,0.0f;中心点的计算方法如下：float cen ter()ce nter0=(mi n0+max0)*0.5f;ce nter1=(mi n1+max1)*0.5f；ce nter2=(mi n2+max2)*0.5f；通过这两个顶点可以知道以下属性。return cen ter:float xSize()return(maxO-m

13、i n0)float ySize()return(max1-mi n1)float zSize()return(max2-mi n2)float size()return(maxO-mi n0)*(max1-mi n1)*(max2- min2) ； 当添加一个顶点到包装盒时，需要先与这两个顶点进行比较void add(float p)if(p0mi n0)mi n0=p0；if(p0max0)max0=p0；if(p1mi n1)mi n1=p1；if(p1max1)max1=p1；if(p2mi n2)mi n2=p2；if(p2max2)max2=p2；检测包装盒是否为空，可以将这两个顶

14、点进行比较。boolea n isEmpty()return(mi n0max0)|(mi n1max1)|(mi n2max2)检测某个点是否属于AABB范围之内的代码如下：boolea n contain s(float p)(p0=mi n0)&&(p0=max0)&&return(p1=mi n1)&&(p1=max1)&&(p2=mi n2)&&(p2=max2);AABB勺静态检测比较简单，检测两个静止包装盒是否相交，它是一种布尔 测试，测试结果只有相交或者不相交。这里我们还提供了获取相交范围信息的 方

15、法，一般来说，这种测试的目的是为了返回一个布尔值。碰撞的示意如图 10-34所示。图10-34包装盒的碰撞检测静态AABB碰撞的方法如下：boolean in tersectAABBs(AABB box2,AABB boxl ntersect)float box2_m in=box2.getMi n()；float box2_max=box2.getMax()；if(mi n0box2_max0)return false；if(max0box2_mi n 0)return false；if(mi n 1box2_max1)return false；if(max1box2_mi n 1)retu

16、rn false；if(mi n2box2_max2)return false；if(max2box2_mi n 2)return false；if(box In tersect ！ =nu ll)float box_i ntersect_m in=new float3；float box_i ntersect_max=new float3；box_i ntersect_mi n0=Math.max(mi n0,box2_mi n0)；box_i ntersect_maxO=Math. min( max0,box2_max0)；box_i ntersect_mi n1=Math.max(mi

17、n1,box2_mi n1)；box_i ntersect_max1=Math. min( max1,box2_max1)；box_i ntersect_mi n2=Math.max(mi n2,box2_mi n2)；box_i ntersect_max2=Math. min( max2,box2_max2)；return true ;可以利用AABB的结构来加快新的AABB的计算速度，而不用变换8个顶点, 再从这8个顶点中计算新AABB下面简单地回顾4X4矩阵变换一个3D点的过 程。通过原边界框 (xmin , ymin, zmin, xmax, ymax, zmax)计算新边界框 (,)

18、，现在的任务是计算的速度。换句话说，希望找到 m11x+m12y+m13z+m的最小值。其中x , y, z是原8个顶点中的任意一个。变换的目的是找出这些点经过变换后哪一个的x坐标最小。看第一个乘积m11x为了最小化乘积，必须决定是用xmin还是xmax来替换其中的x。显然,如果m11>0用xmin能得到最小化的乘积；如果 m11<0则用xmax能得到最小 化乘积。比较方便的是，不管xmin还是xmax中哪一个被用来计算，都可以用另外 一个来计算。可以对矩阵中的9个元素中的每一个都应用这个计算过程(其他元 素不影响大小)。根据变换矩阵和原有的AABB包装盒计算新的AABB包装盒的代

19、码如下：void setToTra nsformedBox(Tra nsform t)if(isEmpty()判断包装盒是否为空return ；float m=new float16?t.get(m) ； /将变换矩阵存入数组 float min x=0 ,miny=0,min z=0；float maxx=0,maxy=0,maxz=0 ； minx+=m3 ； /x方向上平移 maxx+=m3; /x方向上平移 miny+=m7 ； /y方向上平移 maxy+=m7； /y方向上平移 minz+=m11 ； /z方向上平移 maxz+=m11； /z 方向上平移 if(m00.0f)min

20、x+=m0*min0 ； maxx+=m0*max0； elseminx+=m0*max0 ； maxx+=m0*min0； if(m10.0f)minx+=m1*min1 ； maxx+=m1*max1； elseminx+=m1*max1 ； maxx+=m1*min1； if(m20.0f)minx+=m2*min2 ； maxx+=m2*max2；elseminx+=m2*max2 ； maxx+=m2*min2；if(m40.0f)miny+=m4*min0 ； maxy+=m4*max0；elseminy+=m4*max0 ； maxy+=m4*min0；if(m50.0f)min

21、y+=m5*min1 ； maxy+=m5*max1；elseminy+=m5*max1 ； maxy+=m5*min1；if(m60.0f)miny+=m6*min2 ； maxy+=m6*max2；elseminy+=m6*max2 ； maxy+=m6*min2；if(m80.0f)minz+=m8*min0 ； maxz+=m8*max0；elseminz+=m8*max0 ； maxz+=m8*min0；float getMax()return max； if(m90.0f)minz+=m9*min1 ； maxz+=m9*max1；elseminz+=m9*max1 ； maxz+

22、=m9*min1；if(m100.0f)minz+=m10*min2 ； maxz+=m10*max2；elseminz+=m10*max2 ； maxz+=m10*min2；min0=minx ； min1=miny ； min2=minz ； / 用新的 AABE坐标替换原有 坐标max0=maxx； max1=maxy； max2=maxz； / 用新的 AABE坐标替换原有 坐标为了使用AABE包装盒进行碰撞检测，将这些方法和属性封装为AABB类，代码如下：import java .Ian g.Math；import javax.microediti on. m3g.Tra nsfor

23、m；class AABBpublic AABB()float getMin()return min ； ；min1=y ;void setMi n(float x,float y,float z)mi n0=x min2=z ； void setMax(float x,float y,float z)max0=x； max1=y ；max2=z ； void reset()for(i nt i=0; i 3 ; i+)mini=0 ；maxi=0 ；/其他方法同上为了检验碰撞检测的使用构造了两个立方体，并各自绑定了一个包装盒/*立方体1*/mesh仁createCube() ； / 创建立方体

24、 1 mesh1.setTranslation(1.0f,0.0f,0.0f)； / 平移mesh1.setOrientation(90,0.0f,1.0f,0.0f)； / 旋转mesh1.setScale(0.5f,0.5f,0.5f)box仁new AABB(); / 包装盒box1.setMi n(-1.0f,-1.0f,-1.0f)box1.setMax(1.0f,1.0f,1.0f)；/缩放；/设置包装盒1的最小顶点；/设置包装盒1的最大顶点mesh1.getCompositeTra nsform(cubeTra nsform) ；/获取立方体1的混合 矩阵float getMax

25、()return max； boxl.setToTransformedBox(cubeTransform) ； / 将变换矩阵应用到包装盒world.addChild(meshl) ； /将立方体1添加到场景中/*立方体2*/mesh2=createCube() ； / 仓U建立方体 2 mesh2.setTranslation(-0.5f,0.0f,0.0f); / 平移；/缩放；/设置包装盒2的最小顶点；/设置包装盒2的最大顶点mesh2.setScale(0.5f,0.5f,0.5f)box2=new AABB(); / 包装盒box2.setMi n(-1.0f,-1.0f,-1.0f

26、)box2.setMax(1.0f,1.0f,1.0f)mesh2.getCompositeTra nsform(cubeTra nsform) ；/获取立方体2的混合矩阵box2.setToTransformedBox(cubeTransform) ； / 将变换矩阵应用到包装盒 2中world.addChild(mesh2) ； /将立方体2添加到场景中检测包装盒1和包装盒2是否碰撞的代码如下：isCollided=ersectAABBs(box2,null)； / 检测两个 AABB包装盒是否碰撞编译运行程序，设置两个立方体不同的位置和角度，可以比较精确地检测 出它们的碰

27、撞情况，如图10-35所示。检测两个静止AABB的碰撞情况比较简单，只需要在每一维上单独检查它们 的重合程度即可。如果在所有维上都没有重合，那么这两个AABB就不会相交。AABB、可的动态检测稍微复杂一些，考虑一个由顶点smin和smax指定的静态包装盒和一个由顶点 mmin和mmaX旨定的动态包装盒（如果两个都是动态的， 可以根据相对运动视作如此）。运动的速度由向量s给出，运动时间t假定为 01。图10-35静态物体碰撞检测示意移动检测的目标是计算运动 AABB碰撞到静态AABB的时刻，因此需要计算 出两个AABB在所有维上的第一个点。为了简化起见，可以把上述问题先归结到 某一维，然后再将三

28、维结合到一起。假设把问题投影到x轴，如图10-36所示。图10-36 AABB的动态检测黑色矩形代表沿坐标轴滑动的 AABB t=0时，运动AABB完全位于静止 AABB勺左边。当t=1时，运动AABB完全位于静止 AABB勺右边。当t=tenter 时，两个AABB刚刚相交，当t=tleave 时，两个AABB兑离碰撞。对照上图，可以推导出两个 AABB接触和离开的时间：AABB勺动态检测有3个要点。n如果速度为0,两个包装盒要么一直相交，要么一直分离。n不管物体从哪个方向运动，碰撞过程中，肯定是先入后出，所以有ten tervtleave 。n如果tenter和tleave超出运动时间范围

29、，那么在此范围内它们是不相 交的。检测出某一维的碰撞还不够，还需要进行其他两维的检测，然后取结果的 交集。如果交集为空，那么两 AABB包装盒没有相交，如果区间范围在时间段0 , 1之外，那么在此区间也不相交。对 AABB进行动态检测的方法定义如下：float in tersectMovi ngAABB(AABB stati on aryBox,AABB movi ngBox,float s)float Nol ntersectio n=1e30f;/没有碰撞则返回大数float tEnter=0.0f ； /初始化碰撞时间float tLeave=1.0f ; /初始化离开时间float S

30、wap=0.0f; /交换操作中间变量float sBoxmin=stationaryBox.getMin()； / 静止包装盒的最小值顶点float sBoxmax=stationaryBox.getMax()； / 静止包装盒的最大值顶点float mBoxmin=movingBox.getMin()； / 运动包装盒的最小值顶点float mBoxmax=movingBox.getMax() ； / 运动包装盒的最大值顶点 if(s0=0.0f)如果x方向速度为0if(sBoxmi n0=mBoxmax0)|(sBoxmax0=mBoxmi n 0)return NoIntersecti

31、on； / 进行静态检测elsefloat xEnter=(sBoxmin0-mBoxmax0)/s0； / 计算碰撞时间float xLeave=(sBoxmax0-mBoxmin0)/s0； / 计算离开时间if(xE nter xLeave)/检查顺序Swap=xE nter；xEnter=xLeave ；xLeave=Swapif(xEnter tEnter)tEnter=xEnter； / 更新区间if(xLeave tLeave)tLeave=xLeave；if(tE nter tLeave)是否导致空重叠区return Nolntersection； / 没有碰撞if(s1=O.

32、Of)/y轴速度为 0if(sBoxmi n1=mBoxmax1)|(sBoxmax1=mBoxmi n 1)return NoIntersection ； / 没有相交elsefloat yE nter=(sBoxmi n 1-mBoxmax1)/s1；float yLeave=(sBoxmax1-mBoxmi n1)/s1；if(yE nter yLeave)Swap=yE nter；yEnter=yLeave ；yLeave=Swapif(yEnter tEnter)tEnter=yEnter； / 更新区间if(yLeave tLeave)tLeave=yLeave；if(tE nte

33、r tLeave)return NoI ntersectio n；if(s2=0.0f)/z方向速度为 0if(sBoxmi n2=mBoxmax2)|(sBoxmax2=mBoxmi n2)return NoI ntersectio n；elsefloat o neOverD=1.0f/s2；float zE nter=(sBoxmi n2-mBoxmax2)/s2；float zLeave=(sBoxmax2-mBoxmi n 2)/s2；if(zE nter zLeave)Swap=zE nter；zEnter=zLeave ；zLeave=Swapif(zEnter tEnter)tE

34、nter=zEnter； / 更新区间if(zLeave tLeave)tLeave=zLeave；if(tE nter tLeave)return Nol ntersectio n；return tEnter ； /返回碰撞时间为了对移动AABB进行检测，创建两个AABB如图10-37所示。两个包装盒 距离0.5，速度为3。图10-37移动AABB检测检测代码如下：float speed=new float3.0f,0.0f,0.0f；float tEn ter=i ntersectMovi ngAABB(box1,box2,speed)；输出结果为0.16667,完全符合预期的猜测。10.

35、3.4 OBB树碰撞检测前面提到了长条物体在旋转时AABB盒的变化，那么是否有能够在任意方向 都更为精确的检测方式，答案是肯定的，这是一种基于OBB即定向包容盒子（Orie nted Bou nding Box,OBB）的技术，它已经广泛用于光线追踪和碰撞检测中。OBB这种方法是根据物体本身的几何形状来决定盒子的大小和方向，盒子 无须和坐标轴垂直。这样就可以选择最合适的最紧凑的包容盒子。OBB盒子的生成比较复杂。一般是考虑物体所有的顶点在空间的分布，通过一定的算法找 到最好的方向（OBB盒子的几个轴）。一个2D示意图如图10-38所示。这种技术比AABB技术更精确而且更健壮，但 OBB实现起来

36、比较困难，执行 速度慢，并且不太适合动态的或柔性的物体。特别注意的是，当把一个物体分 得越来越小的时候，事实上是在创建一棵有层次的树，如图10-39所示。图10-39 OBB树的生成（曲折线为物体）为任意的网格模型创建OBB树可能是算法里最难的一个部分，而且它还要 调整以适合特定的引擎或游戏类型。从图中可以看出，不得不找出包围给定模 型的最近似的包装盒（或者其他3D体）。现在得到了所有的包装盒，下一步将构造一棵树。从最初的AABB包装盒开始从上至下地反复分割它。另外，还可以用从下至 上的方式，逐步地合并小包装盒从而得到最大的包装盒。把大的包装盒分割成 小的包装盒，应该遵守以下几条原则。（1）用

37、一个面（这个面垂直于包装盒中的一条坐标轴）来分割包装盒上最长的轴，然后根据多边形处在分割轴的哪一边把多边形分离开来（如图10-38所示）（2）如果不能沿着最长的轴进行分割，那就沿第二长的边分割。持续地分割 直到包装盒不能再分割为止。（3）依据需要的精度（比如，是否真的要判断单个三角形的碰撞），可以按选 择的方式（是按树的深度或是按包装盒中多边形的数目）以任意的条件停止分割。正如读者所看到的，创建阶段相当复杂，其中包括了大量的运算，很明显 不能实时地创建树，只能是事先创建。事先创建可以免去实时改变多边形的可 能。另一个缺点是OBE要求进行大量的矩阵运算，不得不把它们定位在适当的 地方，并且每棵子

38、树必须与矩阵相乘。现在假设已经有了 OBB或者AABB树。那么该怎么进行碰撞检测呢？首先检 测最大的包装盒是否相交(AABB级别)，如果相交了，它们可能(注意，只是可 能)发生了碰撞，接下来将进一步地递归处理它们 (OBB级别，不断地递归用下 一级进行处理)。如果沿着下一级，发现子树并没有发生相交，这时就可以停止，并得出结 论没有发生碰撞。如果发现子树相交，那么要进一步处理它的子树直到到达叶 子节点，并最终得出结论。碰撞检测最直观的想法是把一个 OBE盒子的每个边都和另一个盒子的所有 面来比较，如果这个边穿过了另一个 OBB盒子的一个面，则两个OBB盒子发生 了碰撞。显然这种方法的计算量是比较

39、大的，因为要进行12X 6X 2=144次边和面的比较。但是，在考察两个没有碰撞的 OBB盒子时，人们发现一些规律来简化比较。(1) 如果两个OBB盒子不互相接触，则应该可以找到一个盒子上的一个面， 这个面所在的平面可以把3D空间分为两部分，两个OBB盒子各在两边。(2) 如果没有这样的表面存在，则一定可以在两个OBB盒子上各找出一条边,这两条边所在的平面可以把两个 OBB盒子分在两边。有了这个平面，就可以找 到垂直于它的分割轴(separating axis)，如图10-40所示。(3) 进行相交测试时，可以把包装盒投影到分割轴上，并检查它们是否线性 相交。两个OBB盒子在这个分割轴上的投影将是分离的。如上所述，要判断两个OB