《碰撞检测技术》word版.doc

碰撞检测技术碰撞检测技术2011-05-06 23：00技术-引擎2008-09-05 19：50：55阅读251 10.3碰撞检测技术到目前为止，构造的各种对象都是相互独立的，在场景中漫游各种物体，墙壁、树木对玩家(视点)好像是虚设，可以任意从其中穿越。为了使场景人物更加完善，还需要使用碰撞检测技术。10.3.1碰撞检测技术简介无论是PC游戏，还是移动应用，碰撞检测始终是程序开发的难点，甚至可以用碰撞检测作为衡量游戏引擎是否完善的标准。好的碰撞检测要求人物在场景中可以平滑移动，遇到一定高度的台阶可以自动上去，而过高的台阶则把人物挡住，遇到斜率较小的斜坡可以上去，斜率过大则会把人物挡住，在各种前进方向被挡住的情况下都要尽可能地让人物沿合理的方向滑动而不是被迫停下。在满足这些要求的同时还要做到足够精确和稳定，防止人物在特殊情况下穿墙而掉出场景。做碰撞检测时，该技术的重要性容易被人忽视，因为这符合日常生活中的常识。如果出现Bug，很容易被人发现，例如人物无缘无故被卡住不能前进或者人物穿越了障碍。所以，碰撞检测是让很多程序员头疼的算法，算法复杂，容易出错。对于移动终端有限的运算能力，几乎不可能检测每个物体的多边形和顶点的穿透，那样的运算量对手机等设备来讲是不可完成的，所以移动游戏上使用的碰撞检测不可能使用太精确的检测，而且对于3D碰撞检测问题，还没有几乎完美的解决方案。目前只能根据需要来取舍运算速度和精确性。目前成功商业3D游戏普遍采用的碰撞检测是BSP树及AABB(axially aligned bounding box)包装盒(球)方式。简单地讲，AABB检测法就是采用一个描述用的立方体或者球形体包裹住3D物体对象的整体(或者是主要部分)，之后根据包装盒的距离、位置等信息来计算是否发生碰撞，如图10-24所示。除了球体和正方体以外，其他形状也可以作包装盒，但是相比计算量和方便性来讲还是立方体和球体更方便些，所以其他形状的包装只用在一些特殊场合使用。BSP树是用来控制检测顺序和方向的数据描述。在一个游戏场景中可能存在很多物体，它们之间大多属于较远位置或者相对无关的状态，一个物体的碰撞运算没必要遍历这些物体，同时还可以节省重要的时间。如果使用单步碰撞检测，需要注意当时间步长较大时会发生两个物体完全穿透而算法却未检测出来的问题，如图10-25所示。其解决方案是产生一个4D空间，在物体运动的开始和结束时间之间产生一个4D超多面体，用于穿透测试。图10-24 AABB包装盒图10-25碰撞检测的单步失控和4D测试读者在程序开发初期有必要对碰撞检测有一个初步的估计，以免最后把大量精力消耗在碰撞检测问题上，从而降低了在基础的图形编程之上的注意力。10.3.2球体碰撞检测真实的物理模拟系统需要非常精确的碰撞检测算法，但是游戏中常常只需要较为简单的碰撞检测，因为只需要知道物体什么时候发生碰撞，而不用知道模型的哪个多边形发生了碰撞，因此可以将不规则的物体投影成较规则的物体进行碰撞检测。球体只有一个自由度，其碰撞检测是最简单的数学模型，我们只需要知道两个球体的球心和半径就能进行检测。那么球体碰撞是如何工作的?主要过程如下。n计算两个物体中心之间的距离，并且将其与两个球体的半径和进行比较。n如果距离大于半径和，则没有发生碰撞。n否则，如果距离小于半径和，则发生了物体碰撞。考虑由球心c1、c2和半径r1、r2定义的两个球，如图10-26所示。设d为球心间的距离。很明显，当dr1+r2时相交，在实践中通过比较d20，用xmin能得到最小化的乘积；如果m110，则用xmax能得到最小化乘积。比较方便的是，不管xmin还是xmax中哪一个被用来计算，都可以用另外一个来计算。可以对矩阵中的9个元素中的每一个都应用这个计算过程(其他元素不影响大小)。根据变换矩阵和原有的AABB包装盒计算新的AABB包装盒的代码如下：void setToTransformedBox(Transform t)if(isEmpty()/判断包装盒是否为空return；float m=new float16；t.get(m)；/将变换矩阵存入数组float minx=0,miny=0,minz=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)minx+=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)miny+=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；if(m90.0f)minz+=m9*min1；maxz+=m9*max1；elseminz+=m9*max1；maxz+=m9*min1；if(m100.0f)minz+=m10*min2；maxz+=m10*max2；elseminz+=m10*max2；maxz+=m10*min2；min0=minx；min1=miny；min2=minz；/用新的AABB坐标替换原有坐标max0=maxx；max1=maxy；max2=maxz；/用新的AABB坐标替换原有坐标为了使用AABB包装盒进行碰撞检测，将这些方法和属性封装为AABB类，代码如下：import java.lang.Math；import javax.microedition.m3g.Transform；class AABBpublic AABB()float getMin()return min；float getMax()return max；void setMin(float x,float y,float z)min0=x；min1=y；min2=z；void setMax(float x,float y,float z)max0=x；max1=y；max2=z；void reset()for(int i=0；i 3；i+)mini=0；maxi=0；/其他方法同上为了检验碰撞检测的使用构造了两个立方体，并各自绑定了一个包装盒。/*立方体1*/mesh1=createCube()；/创建立方体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)；/缩放box1=new AABB()；/包装盒box1.setMin(-1.0f,-1.0f,-1.0f)；/设置包装盒1的最小顶点box1.setMax(1.0f,1.0f,1.0f)；/设置包装盒1的最大顶点mesh1.getCompositeTransform(cubeTransform)；/获取立方体1的混合矩阵box1.setToTransformedBox(cubeTransform)；/将变换矩阵应用到包装盒中world.addChild(mesh1)；/将立方体1添加到场景中/*立方体2*/mesh2=createCube()；/创建立方体2 mesh2.setTranslation(-0.5f,0.0f,0.0f)；/平移mesh2.setScale(0.5f,0.5f,0.5f)；/缩放box2=new AABB()；/包装盒box2.setMin(-1.0f,-1.0f,-1.0f)；/设置包装盒2的最小顶点box2.setMax(1.0f,1.0f,1.0f)；/设置包装盒2的最大顶点mesh2.getCompositeTransform(cubeTransform)；/获取立方体2的混合矩阵box2.setToTransformedBox(cubeTransform)；/将变换矩阵应用到包装盒2中world.addChild(mesh2)；/将立方体2添加到场景中检测包装盒1和包装盒2是否碰撞的代码如下：isCollided=ersectAABBs(box2,null)；/检测两个AABB包装盒是否碰撞编译运行程序，设置两个立方体不同的位置和角度，可以比较精确地检测出它们的碰撞情况，如图10-35所示。检测两个静止AABB的碰撞情况比较简单，只需要在每一维上单独检查它们的重合程度即可。如果在所有维上都没有重合，那么这两个AABB就不会相交。AABB间的动态检测稍微复杂一些，考虑一个由顶点smin和smax指定的静态包装盒和一个由顶点mmin和mmax指定的动态包装盒(如果两个都是动态的，可以根据相对运动视作如此)。运动的速度由向量s给出，运动时间t假定为01。图10-35静态物体碰撞检测示意移动检测的目标是计算运动AABB碰撞到静态AABB的时刻，因此需要计算出两个AABB在所有维上的第一个点。为了简化起见，可以把上述问题先归结到某一维，然后再将三维结合到一起。假设把问题投影到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不管物体从哪个方向运动，碰撞过程中，肯定是先入后出，所以有tentertleave。n如果tenter和tleave超出运动时间范围，那么在此范围内它们是不相交的。检测出某一维的碰撞还不够，还需要进行其他两维的检测，然后取结果的交集。如果交集为空，那么两AABB包装盒没有相交，如果区间范围在时间段0，1之外，那么在此区间也不相交。对AABB进行动态检测的方法定义如下：float intersectMovingAABB(AABB stationaryBox,AABB movingBox,float s)float NoIntersection=1e30f；/没有碰撞则返回大数float tEnter=0.0f；/初始化碰撞时间float tLeave=1.0f；/初始化离开时间float Swap=0.0f；/交换操作中间变量float sBoxmin=stationaryBox.getMin()；/静止包装盒的最小值顶点float sBoxmax=stationaryBox.getMax()；/静止包装盒的最大值顶点float mBoxmin=movingBox.getMin()；/运动包装盒的最小值顶点float mBoxmax=movingBox.getMax()；/运动包装盒的最大值顶点if(s0=0.0f)/如果x方向速度为0 if(sBoxmin0=mBoxmax0)|(sBoxmax0=mBoxmin0)return NoIntersection；/进行静态检测elsefloat xEnter=(sBoxmin0-mBoxmax0)/s0；/计算碰撞时间float xLeave=(sBoxmax0-mBoxmin0)/s0；/计算离开时间if(xEnter xLeave)/检查顺序Swap=xEnter；xEnter=xLeave；xLeave=Swap；if(xEnter tEnter)tEnter=xEnter；/更新区间if(xLeave tLeave)tLeave=xLeave；if(tEnter tLeave)/是否导致空重叠区return NoIntersection；/没有碰撞if(s1=0.0f)/y轴速度为0 if(sBoxmin1=mBoxmax1)|(sBoxmax1=mBoxmin1)return NoIntersection；/没有相交elsefloat yEnter=(sBoxmin1-mBoxmax1)/s1；float yLeave=(sBoxmax1-mBoxmin1)/s1；if(yEnter yLeave)Swap=yEnter；yEnter=yLeave；yLeave=Swap；if(yEnter tEnter)tEnter=yEnter；/更新区间if(yLeave tLeave)tLeave=yLeave；if(tEnter tLeave)return NoIntersection；if(s2=0.0f)/z方向速度为0 if(sBoxmin2=mBoxmax2)|(sBoxmax2=mBoxmin2)return NoIntersection；elsefloat oneOverD=1.0f/s2；float zEnter=(sBoxmin2-mBoxmax2)/s2；float zLeave=(sBoxmax2-mBoxmin2)/s2；if(zEnter zLeave)Swap=zEnter；zEnter=zLeave；zLeave=Swap；if(zEnter tEnter)tEnter=zEnter；/更新区间if(zLeave tLeave)tLeave=zLeave；if(tEnter tLeave)return NoIntersection；return tEnter；/返回碰撞时间为了对移动AABB进行检测，创建两个AABB如图10-37所示。两个包装盒距离0.5，速度为3。图10-37移动AABB检测检测代码如下：float speed=new float3.0f,0.0f,0.0f；float tEnter=intersectMovingAABB(box1,box2,speed)；输出结果为0.16667，完全符合预期的猜测。10.3.4 OBB树碰撞检测前面提到了长条物体在旋转时AABB盒的变化，那么是否有能够在任意方向都更为精确的检测方式，答案是肯定的，这是一种基于OBB即定向包容盒子(Oriented Bounding Box,OBB)的技术，它已经广泛用于光线追踪和碰撞检测中。OBB这种方法是根据物体本身的几何形状来决定盒子的大小和方向，盒子无须和坐标轴垂直。这样就可以选择最合适的最紧凑的包容盒子。OBB盒子的生成比较复杂。一般是考虑物体所有的顶点在空间的分布，通过一定的算法找到最好的方向(OBB盒子的几个轴)。一个2D示意图如图10-38所示。这种技术比AABB技术更精确而且更健壮，但OBB实现起来比较困难，执行速度慢，并且不太适合动态的或柔性的物体。特别注意的是，当把一个物体分得越来越小的时候，事实上是在创建一棵有层次的树，如图10-39所示。图10-39 OBB树的生成(曲折线为物体)为任意的网格模型创建OBB树可能是算法里最难的一个部分，而且它还要调整以适合特定的引擎或游戏类型。从图中可以看出，不得不找出包围给定模型的最近似的包装盒(或者其他3D体)。现在得到了所有的包装盒，下一步将构造一棵树。从最初的AABB包装盒开始从上至下地反复分割它。另外，还可以用从下至上的方式，逐步地合并小包装盒从而得到最大的包装盒。把大的包装盒分割成小的包装盒，应该遵守以下几条原则。(1)用一个面(这个面垂直于包装盒中的一条坐标轴)来分割包装盒上最长的轴，然后根据多边形处在分割轴的哪一边把多边形分离开来(如图10-38所示)。(2)如果不能沿着最长的轴进行分割，那就沿第二长的边分割。持续地分割直到包装盒不能再分割为止。(3)依据需要的精度(比如，是否真的要判断单个三角形的碰撞)，可以按选择的方式(是按树的深度或是按包装盒中多边形的数目)以任意的条件停止分割。正如读者所看到的，创建阶段相当复杂，其中包括了大量的运算，很明显不能实时地创建树，只能是事先创建。事先创建可以免去实时改变多边形的可能。另一个缺点是OBB要求进行大量的矩阵运算，不得不把它们定位在适当的地方，并且每棵子树必须与矩阵相乘。现在假设已经有了OBB或者AABB树。那么该怎么进行碰撞检测呢?首先检测最大的包装盒是否相交(AABB级别)，如果相交了，它们可能(注意，只是可能)发生了碰撞，接下来将进一步地递归处理它们(OBB级别，不断地递归用下一级进行处理)。如果沿着下一级，发现子树并没有发生相交，这时就可以停止，并得出结论没有发生碰撞。如果发现子树相交，那么要进一步处理它的子树直到到达叶子节点，并最终得出结论。碰撞检测最直观的想法是把一个OBB盒子的每个边都和另一个盒子的所有面来比较，如果这个边穿过了另一个OBB盒子的一个面，则两个OBB盒子发生了碰撞。显然这种方法的计算量是比较大的，因为要进行1262=144次边和面的比较。但是，在考察两个没有碰撞的OBB盒子时，人们发现一些规律来简化比较。(1)如果两个OBB盒子不互相接触，则应该可以找到一个盒子上的一个面，这个面所在的平面可以把3D空间分为两部分，两个OBB盒子各在两边。(2)如果没有这样的表面存在，则一定可以在两个OBB盒子上各找出一条边，这两条边所在的平面可以把两个OBB盒子分在两边。有了这个平面，就可以找到垂直于它的分割轴(separating axis)，如图10-40所示。(3)进行相交测试时，可以把包装盒投影到分割轴上，并检查它们是否线性相交。两个OBB盒子在这个分割轴上的投影将是分离的。如上所述，要判断两个OBB盒子是否碰撞，只需要看两个OBB盒子之间是否有这样的平面和分割轴存在。如果存在，则没有碰撞。如果不存在，则碰撞。对第一种情况，每个盒子有6个表面(其中每两个平行)，可以决定3个分割轴。两个OBB盒子一共有6个可能的分割轴需要考虑。对第二种情况，两个OBB盒子之间的边的组合可以有33=9种情况，也就是有9个可能的分割轴。这样对任意两个OBB盒子，只需要考察15个分割轴就可以了。如果在任一分割轴上的阴影不重合，则OBB盒子之间没有碰撞。选择AABB还是选择OBB应该根据所需的精确程度而定。对一个需要快速反应的3D射击游戏来说，可能用AABB来进行碰撞检测更好些-可以牺牲一些精度来换取速度和实现的简单化，因此总能在游戏中看到一些小疏漏。当然随着硬件能力的提高，OBB处理会逐渐被重视起来。在做碰撞检测时应当遵循以下的优化理论，这样可以改善检测速度。n分两步检