碰撞检测技术

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

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

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

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

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

6、运算。对两个运动的球进行碰撞检测要麻烦一些，假设两个球的运动向量为dl和d2,球与位移向量是一一对应的，它们描述了所讨论时间段中的运动方式。事实上，物体的运动是相对的，例如两列在两条平行轨道上相向行驶的火车，在其中一列中观察，对方的速度是两车速度之和。同样，也可以从第一个球的角度来简化问题，假设第一个球是静止的，另一个是运动的，那么该运动向量等于原向量dl和d2之差，如图10-27所示。图10-27动态球的检测过程球体碰撞的优点是非常适用于需要快速检测的游戏，因为它不需要精确的碰撞检测算法。执行速度相对较快，不会给CPU带来过大的计算负担。球体碰撞的另一个劣势是只适用于近似球形物体，如果物体非

7、常窄或者非常宽，该碰撞检测算法将会失效，因为会在物体实际发生碰撞之前，碰撞检测系统就发出碰撞信号，如图10-28所示是球体碰撞检测中可能出现的坏情况，其解决方法是缩小检测半径，或者使用其他检测模型，如图10-29所示。图10-28球体碰撞的坏情况图10-29缩小检测半径为了解决包容球精确度不高的问题，人们乂提出了球体树的方法。球体树实际上是一种表达3D物体的层次结构。对一个形状复杂的3D物体，先用一个大球体包容整个物体，然后对物体的各个主要部分用小一点的球体来表示，然后对更小的细节用更小的包容球体，这些球体和它们之间的层次关系就形成了一个球体树。举例来说，对一个游戏中的人物角色，可以用一个大球

8、来表示整个人，然后用中等大小的球体来表示四肢和躯干，然后用更小的球体来表示手脚等。这样在对两个物体进行碰撞检测时，先比较两个最大的球体。如果有重叠，则沿树结构向下遍历，对小一点的球体进行比较，直到没有任何球体重叠，或者到了最小的球体，这个最小的球体所包含的部分就是碰撞的部分，如图10-30所示。10.3.3AABB立方体边界框检测用球体去近似地代表物体运算量很小，但在游戏中的大多数物体是方的或者长条形的，应该用方盒来代表物体。另一种常见的检测模型是立方体边界框，如图10-31展示了一个AABB检测盒和它里面的物体。坐标轴平行(Axially-aligned)不仅指盒体与世界坐标轴平行，同时也指

9、盒体的每个面都和一条坐标轴垂直，这样一个基本信息就能减少转换盒体时操作的次数。AABB技术在当今的许多游戏中都得到了应用，开发者经常用它们作为模型的检测模型，再次指出，提高精度的同时也会降低速度。因为AABB总是与坐标轴平行，不能在旋转物体时简单地旋转AABB,而是应该在每一帧都重新计算。如果知道每个对象的内容，这个计算就不算困难，也不会降低游戏的速度。然而，还面临着精度的问题。假如有一个3D的细长刚性直棒，并且要在每一帧动画中都重建它的AABBo可以看到每一帧中的包装盒都不一样而且精度也会随之改变，如图10-32所示。图10-313D模型与AABB检测盒图10-32不同方向的AABB可以注意

10、到AABB对物体的方向很敏感，同一物体的不同方向，AABB也可能不同(由于球体只有一个自由度，所以检测球对物体方向不敏感)。当物体在场景中移动时，它的AABB也需要随之移动，当物体发生旋转时，有两种选择：用变换后的物体来重新计算AABB,或者对AABB做和物体同样的变换。如果物体没有发生扭曲，可以通过变换后的AABB重新计算，因为该方法要比通过变换后的物体计算快得多，因为AABB只有8个顶点。变换AABB得出新的AABB要比变换物体的运算量小，但是也会带来一定的误差，如图10-33所示。比较图中原AABB（灰色部分）和新AABB（右边比较大的方框），它是通过旋转后的AABB计算得到的，新AAB

11、B儿乎是原来AABB的两倍，注意，如果从旋转后的物体而不是旋转后的AABB来计算新AABB,它的大小将和原来的AABB相同。先介绍AABB的表达方法，AABB内的点满足以下条件：xminWxWxmaxyminWyWymaxzniinWzWzniax因此只需要知道两个特别重要的顶点(xmin,ymin,zmin)、(xmax,ymax»zmax)9记作：floatmin=newfloat0.Of,0.Of,0.Of)；f1oatmax=newf1oat0.Of,0.Of,0.Of)；中心点是两个顶点的中点，代表了包装盒的质点。floatcenter=newfloat0.Of,0.Of,

12、0.Of)；中心点的计算方法如下：floatcenter()center0=(min0+max0)*0.5f；center1=(minl+maxl)*0.5f；center2=(min2+max2)*0.5f；returncenter；通过这两个顶点可以知道以下属性。floatxSizeOreturn(max0-min0)；floatySizeOreturn(max1-min1)；floatzSize()return(max2-min2)；floatsize()return(maxEO-min0)*(maxEl-min1)*(max21一min2)；当添加一个顶点到包装盒时，需要先与这两个顶点

13、进行比较。voidadd(floatp)if(p0min0)min0=p0；if(p0max0)max0=p0；if(plminl)minl=pl；if(plmaxl)maxl=pl；if(p2min2)min2=p2；if(p2max2)max2=p2；检测包装盒是否为空，可以将这两个顶点进行比较。booleanisEmpty()return(min0max0)ii(minlmaxll)ii(min2max2)；检测某个点是否属于AABB范围之内的代码如下：booleancontains(floatp)return(p0=min0)&&(p0=max0)&&(

14、pl=minl)&&(pl=maxl)&&(p2=min2)&&(p2=max2)；AABB的静态检测比较简单，检测两个静止包装盒是否相交，它是一种布尔测试，测试结果只有相交或者不相交。这里我们还提供了获取相交范围信息的方法，一般来说，这种测试的目的是为了返回一个布尔值。碰撞的示意如图10-34所示。图10-34包装盒的碰撞检测静态AABB碰撞的方法如下：booleanintersectAABBs(AABBbox2,AABBboxIntersect)floatbox2_min=box2.getMinO；floatbox2_max=box2.get

15、Max()；if(min0box2_max0)returnfalse；if(maxE0box2_min0)returnfalse；if(min1box2_max1)returnfalse；if(max1box2_min1)returnfalse；if(min2box2_max2)returnfalse；if(max2box2_min2)returnfalse；if(boxlntersect!=null)floatbox_intersect_min=newfloat3；floatbox_intersect_max=newfloat3；box_intersect_min0=Math.max(min

16、0,box2_min0)；box_intersect_max0=Math.min(max0,box2_max0)；box_intersect_minl=:Math.max(min1,box2_minl)；box_intersect_maxl:Math.min(max1,box2_maxl)；box_intersect.min2=Math.max(min2,box2_min2)；box_intersect_max2=Math.min(max2,box2_max2)；returntrue；可以利用AABB的结构来加快新的AABB的计算速度，而不用变换8个顶点，再从这8个顶点中计算新AABB。下面简

17、单地回顾4X4矩阵变换一个3D点的过程。通过原边界框(xmin,ymin,zmin,xmax,ymax,zmax)计算新边界框现在的任务是计算的速度。换句话说，希望找到mllx+ml2y+ml3z+ml4的最小值。其中x,y,z是原8个顶点中的任意一个。变换的目的是找出这些点经过变换后哪一个的x坐标最小。看第一个乘积mllx,为了最小化乘积，必须决定是用xmin还是xmax来替换其中的X。显然，如果1nli>0,用xmin能得到最小化的乘积;如果mllXO,则用xmax能得到最小化乘积。比较方便的是，不管xmin还是xmax中哪一个被用来计算，都可以用另外一个来计算。可以对矩阵中的9个元

18、素中的每一个都应用这个计算过程(其他元素不影响大小)。根据变换矩阵和原有的AABB包装盒计算新的AABB包装盒的代码如下：voidsetToTransformedBox(Transformt)if(isEmpty。)判断包装盒是否为空return；floatm=newfloat16；t.get(m)；将变换矩阵存入数组floatminx=O,miny=0,minz=0；floatmaxx=0,maxy=O,maxz=O；minx+=m3；/x方向上平移maxx+=m3；/x方向上平移miny+=m7；/y方向上平移maxy+=m7；y方向上平移minz+=mll；/z方向上平移maxz+=ml

19、l；/z方向上平移if(m00.Of)minx+=m0*niin0；elseminx+=m0*max0；if(ml0.Of)minx+=m1*min1；elseminx+=m1*max1；if(m20.Of)minx+=m2*min2；elseminx+=m2*max2；maxx+=m0*max0；maxx+=m0*min0；maxx+=m2*max2；maxx+=m2*min2；if(m40.Of)miny+=m4*min0；maxy+=m4*max0；elseminy+=m4*max0；maxy+=m4*min0；if(m50.Of)miny+=m5*min1；maxy+=m5*max1；

20、elseminy+=m5*max1；if(m60.Of)miny+=m6*min2；elseminy+=m6*max2；if(m80.Of)minz+=m8*min0；elseminz+=m8*max0；if(m90.Of)minz+=m9*niinl；elseminz+=m9*max1；maxy+=m5*min1；maxy+=m6*max2；maxy+=m6*min2；maxz+=m8*max0；maxz+=m8*min0；maxz+=m9*max1；maxz+=m9*min1；minz+=m10*min2；maxz+=m10*max2；elseminz+=m10*max2；maxz+=m1

21、0*min2；min0=minx；minl=miny；min2=minz；/用新的AABB坐标替换原有坐标maxEOl=maxx；maxl=maxy；max2=maxz；用新的AABB坐标替换原有坐标为了使用AABB包装盒进行碰撞检测，将这些方法和属性封装为AABB类,代码如下：importjava.lang.Math；importjavax.microedition.m3g.Transform：c1assAABBpublicAABB()floatgetMinOreturnmin；floatgetMaxOreturnmax；)voidsetMin(floatx,floaty,floatz)mi

22、n0=x；minl=y；min2=z；voidsetMax(floatx,floaty,floatz)max0=x；maxl=y；max2=z；voidreset()for(inti=0；i3；i+)mini=0；maxi=0；其他方法同上为了检验碰撞检测的使用构造了两个立方体，并各自绑定了一个包装盒。/*立方体1*/meshl=createCube()；创建立方体Imeshl.setTranslation(l.Of,0.Of,0.Of)；平移meshl.setOrientation(90,0.Of,1.Of,0.Of)；旋转meshl.setScale(0.5f,0.5f,0.5f)；缩放b

23、oxl=newAABB()；包装盒boxl.setMin(-1.0f,-l.Of,-1.Of)；设置包装盒1的最小顶点boxl.setMax(l.Of,1.Of,1.Of)；设置包装盒1的最大顶点meshl.getCompositeTransform(cubeTransform)：/获取立方体1的混合矩阵boxl.setToTransformedBox(cubeTransform)；将变换矩阵应用到包装盒中world.addChild(meshl)；将立方体1添加到场景中/*立方体2*/mesh2=createCube()；创建立方体2mesh2.setTranslation(-0.5f,0.

24、Of,0.Of)；/平移mesh2.setScale(0.5f,0.5f,0.5f)；缩放box2二newAABB()；包装盒box2.setMin(-1.0f,-l.Of,-1.Of)；/设置包装盒2的最小顶点box2.setMax(l.Of,1.Of,1.Of)；设置包装盒2的最大顶点mesh2.getCompositeTransform(cubeTransform)；/获取立方体2的混合矩阵box2.setToTransformedBox(cubeTransform)；将变换矩阵应用到包装盒2中world.addChiId(mesh2)；将立方体2添加到场景中检测包装盒1和包装盒2是否碰

25、撞的代码如下：isCollided=ersectAABBs(box2,null)；检测两个AABB包装盒是否碰撞编译运行程序，设置两个立方体不同的位置和角度，可以比较精确地检测出它们的碰撞情况，如图10-35所示。检测两个静止AABB的碰撞情况比较简单，只需要在每一维上单独检查它们的重合程度即可。如果在所有维上都没有重合，那么这两个AABB就不会相交。AABB间的动态检测稍微复杂一些，考虑一个由顶点smin和smax指定的静态包装盒和一个由顶点mmin和mmax指定的动态包装盒(如果两个都是动态的，可以根据相对运动视作如此)。运动的速度由向量s给出，运动时间t假定为01。图10

26、-35静态物体碰撞检测示意移动检测的目标是计算运动AABB碰撞到静态AABB的时刻，因此需要计算出两个AABB在所有维上的第一个点。为了简化起见，可以把上述问题先归结到某一维，然后再将三维结合到一起。假设把问题投影到x轴，如图10-36所示。图10-36AABB的动态检测黑色矩形代表沿坐标轴滑动的AABB,廿0时，运动AABB完全位于静止AABB的左边。当时，运动AABB完全位于静止AABB的右边。当t=tenter时，两个AABB刚刚相交，当廿tleave时，两个AABB脱离碰撞。对照上图，可以推导出两个AABB接触和离开的时间：AABB的动态检测有3个要点。n如果速度为0,两个包装盒要么一

27、直相交，要么一直分离。n不管物体从哪个方向运动，碰撞过程中，肯定是先入后出，所以有tenter<tleaveon如果tenter和11eave超出运动时间范围，那么在此范围内它们是不相交的。检测出某一维的碰撞还不够，还需要进行其他两维的检测，然后取结果的交集。如果交集为空，那么两AABB包装盒没有相交，如果区间范围在时间段0,1之外，那么在此区间也不相交。对AABB进行动态检测的方法定义如下：floatintersectMovingAABB(AABBstationaryBox,AABBmovingBox,floats)floatNoIntersection=le30f；没有碰撞则返回大数

28、floattEnter=0.Of；初始化碰撞时间floattLeave=l.Of；初始化离开时间floatSwap=0.Of；交换操作中间变量floatsBoxmin=stationaryBox.getMinO；静止包装盒的最小值顶点floatsBoxmax=stationaryBox.getMax()；静止包装盒的最大值顶点floatmBoxmin=movingBox.getMinO;运动包装盒的最小值顶点floatmBoxmax=movingBox.getMax()；运动包装盒的最大值顶点if(sO=O.Of)如果x方向速度为Oif(sBoxmin0=mBoxmax0)I.(sBoxmax

29、0=mBoxmin0)returnNoIntersection；进行静态检测elsefloatxEnter=(sBoxmin0-mBoxmax0)/s0；计算碰撞时间floatxLeave=(sBoxmax0-mBoxmin0)/s0；计算离开时间if(xEnterxLeave)检查顺序Swap=xEnter；xEnter=xLeave；xLeave=Swap；if(xEntertEnter)tEnter=xEnter；更新区间if(xLeavetLeave)tLeave=xLeave；if(tEntertLeave)是否导致空重叠区returnNoIntersection；没有碰撞if(sl

30、=0.Of)/y轴速度为0if(sBoxmin1=mBoxmax1)I.(sBoxmax1=mBoxmin1)returnNoIntersection；没有相交elsefloatyEnter=(sBoxmin1-mBoxmaxl)/sl；floatyLeave=(sBoxmax1-mBoxminl)/sl；if(yEnteryLeave)Swap=yEnter；yEnter=yLeave；yLeave=Swap；if(yEntertEnter)tEnter=yEnter；更新区间if(yLeavetLeave)tLeave=yLeave；if(tEntertLeave)returnNoInte

31、rsection；if(s2=0.Of)/z方向速度为Oif(sBoxmin2=mBoxmax2)I.(sBoxmax2=mBoxmin2)returnNoIntersection；elsef1oatoneOverD=1.Of/s2；floatzEnter=(sBoxmin2-mBoxmax2)/s2；floatzLeave=(sBoxmax2-mBoxmin2)/s2；if(zEnterzLeave)Swap=zEnter；zEnter=zLeave；zLeave=Swap；if(zEntertEnter)tEnter=zEnter；更新区间if(zLeavetLeave)tLeave=zL

32、eave；if(tEntertLeave)returnNoIntersection；returntEnter；返回碰撞时间为了对移动AABB进行检测，创建两个AABB如图10-37所示。两个包装盒距离Q5,速度为3。图10-37移动AABB检测检测代码如下：floatspeed=newfloat3,Of,0.Of,0.Of；floattEnter=intersectMovingAABB（boxl,box2,speed）；输出结果为0.16667,完全符合预期的猜测。10.3.40BB树碰撞检测前面提到了长条物体在旋转时AABB盒的变化，那么是否有能够在任意方向都更为精确的检测方式，答案是肯定的

33、，这是一种基于0BB即定向包容盒子（OrientedBoundingBox,OBB）的技术，它已经广泛用于光线追踪和碰撞检测中。OBB这种方法是根据物体本身的几何形状来决定盒子的大小和方向，盒子无须和坐标轴垂直。这样就可以选择最合适的最紧凑的包容盒子。0BB盒子的生成比较复杂。一般是考虑物体所有的顶点在空间的分布，通过一定的算法找到最好的方向（OBB盒子的几个轴）o一个2D示意图如图10-38所示。这种技术比AABB技术更精确而且更健壮，但OBB实现起来比较困难，执行速度慢，并且不太适合动态的或柔性的物体。特别注意的是，当把一个物体分得越来越小的时候，事实上是在创建一棵有层次的树，如图10-3

34、9所示。图10-390BB树的生成（曲折线为物体）为任意的网格模型创建0BB树可能是算法里最难的一个部分，而且它还要调整以适合特定的引擎或游戏类型。从图中可以看出，不得不找出包围给定模型的最近似的包装盒（或者其他3D体）。现在得到了所有的包装盒，下一步将构造一棵树。从最初的AABB包装盒开始从上至下地反复分割它。另外，还可以用从下至上的方式，逐步地合并小包装盒从而得到最大的包装盒。把大的包装盒分割成小的包装盒，应该遵守以下儿条原则。（1）用一个面（这个面垂直于包装盒中的一条坐标轴）来分割包装盒上最长的轴，然后根据多边形处在分割轴的哪一边把多边形分离开来（如图10-38所示）。（2）如果不能沿着

35、最长的轴进行分割，那就沿第二长的边分割。持续地分割直到包装盒不能再分割为止。（3）依据需要的精度（比如，是否真的要判断单个三角形的碰撞），可以按选择的方式（是按树的深度或是按包装盒中多边形的数目）以任意的条件停止分割。正如读者所看到的，创建阶段相当复杂，其中包括了大量的运算，很明显不能实时地创建树，只能是事先创建。事先创建可以免去实时改变多边形的可能。另一个缺点是OBB要求进行大量的矩阵运算，不得不把它们定位在适当的地方，并且每棵子树必须与矩阵相乘。现在假设已经有了OBB或者AABB树。那么该怎么进行碰撞检测呢？首先检测最大的包装盒是否相交（AABB级别），如果相交了，它们可能（注意，只是可能

36、）发生了碰撞，接下来将进一步地递归处理它们（OBB级别，不断地递归用下一级进行处理）。如果沿着下一级，发现子树并没有发生相交，这时就可以停止，并得出结论没有发生碰撞。如果发现子树相交，那么要进一步处理它的子树直到到达叶子节点，并最终得出结论。碰撞检测最直观的想法是把一个OBB盒子的每个边都和另一个盒子的所有面来比较，如果这个边穿过了另一个OBB盒子的一个面，则两个OBB盒子发生了碰撞。显然这种方法的计算量是比较大的，因为要进行12X6X2=144次边和面的比较。但是，在考察两个没有碰撞的OBB盒子时，人们发现一些规律来简化比较。(1)如果两个OBB盒子不互相接触，则应该可以找到一个盒子上的一个面，这个面所在的平面可以把3D空间分为两部分，两个OBB盒子各在两边。(2)如果没有这样的表面存在，则一定可以在两个OBB盒子上各找出一条边，这两条边所在的平面可以把两个OBB盒子分在两边。有了这个平面，就可以找到垂直于它的分割轴(separatingaxis)，如图10-40所示。(3)进行相交测试时，可以把包装盒投影到分割轴上，并检查它们是否线性相交。两个0BB盒子在这个分割轴上的投影将是分离的。如上所述，要判断两个0BB盒子是否碰撞，只需要看两个0BB盒子之间是否有这样的平面和分割轴存在。如果存在，则没有碰撞。如果不存在