《碰撞检测技术》word版

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

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

3、来取舍运算速度和准确性。目前成功商业3D游戏普遍采用的碰撞检测是BSP树及AABBaxially aligned 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否那么，假设间隔 小于半径和，那么发生了物体碰撞。考虑由球心c1、c2和半径r1、r2定义的两个球，如图10-26所示。设d为球心间的间隔 。很明显，当d<r1+r2时相交，在理论中通过比较d2<r1+r22，可以防止包括计算d在内的

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

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

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

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

10、型与AABB检测盒图10-32不同方向的AABB可以注意到AABB对物体的方向很敏感，同一物体的不同方向，AABB也可能不同由于球体只有一个自由度，所以检测球对物体方向不敏感。当物体在场景中挪动时，它的AABB也需要随之挪动，当物体发生旋转时，有两种选择：用变换后的物体来重新计算AABB，或者对AABB做和物体同样的变换。假设物体没有发生扭曲，可以通过"变换后的AABB"重新计算，因为该方法要比通过"变换后的物体"计算快得多，因为AABB只有8个顶点。变换AABB得出新的AABB要比变换物体的运算量小，但是也会带来一定的误差，如图10-33所示。比较图中

11、原AABB灰色部分和新AABB右边比较大的方框，它是通过旋转后的AABB计算得到的，新AABB几乎是原来AABB的两倍，注意，假设从旋转后的物体而不是旋转后的AABB来计算新AABB，它的大小将和原来的AABB一样。先介绍AABB的表达方法，AABB内的点满足以下条件：xminxxmax yminyymax zminzzmax因此只需要知道两个特别重要的顶点xmin，ymin，zmin、xmax，ymax，zmax，记作：float min=new float0.0f,0.0f,0.0f；float max=new float0.0f,0.0f,0.0f；中心点是两个顶点的中点，代表了包装盒的

12、质点。float center=new float0.0f,0.0f,0.0f；中心点的计算方法如下：float centercenter0=min0+max0*0.5f；center1=min1+max1*0.5f；center2=min2+max2*0.5f；return center；通过这两个顶点可以知道以下属性。float xSizereturnmax0-min0；float ySizereturnmax1-min1；float zSizereturnmax2-min2；float sizereturnmax0-min0*max1-min1*max2-min2；当添加一个顶点到包装盒

13、时，需要先与这两个顶点进展比较。void addfloat pifp0min0min0=p0；ifp0max0max0=p0；ifp1min1min1=p1；ifp1max1max1=p1；ifp2min2min2=p2；ifp2max2max2=p2；检测包装盒是否为空，可以将这两个顶点进展比较。boolean isEmptyreturnmin0max0|min1max1|min2max2；检测某个点是否属于AABB范围之内的代码如下：boolean containsfloat preturnp0=min0&&p0=max0&&p1=min1&&

14、;p1=max1&&p2=min2&&p2=max2；AABB的静态检测比较简单，检测两个静止包装盒是否相交，它是一种布尔测试，测试结果只有相交或者不相交。这里我们还提供了获取相交范围信息的方法，一般来说，这种测试的目的是为了返回一个布尔值。碰撞的示意如图10-34所示。图10-34包装盒的碰撞检测静态AABB碰撞的方法如下：boolean intersectAABBsAABB box2,AABB boxIntersectfloat box2_min=box2.getMin；float box2_max=box2.getMax；ifmin0box2_max0re

15、turn false；ifmax0box2_min0return false；ifmin1box2_max1return false；ifmax1box2_min1return false；ifmin2box2_max2return false；ifmax2box2_min2return false；ifboxIntersect！=nullfloat box_intersect_min=new float3；float box_intersect_max=new float3；box_intersect_min0=Math.maxmin0,box2_min0；box_intersect_max

16、0=Math.minmax0,box2_max0；box_intersect_min1=Math.maxmin1,box2_min1；box_intersect_max1=Math.minmax1,box2_max1；box_intersect_min2=Math.maxmin2,box2_min2；box_intersect_max2=Math.minmax2,box2_max2；return true；可以利用AABB的构造来加快新的AABB的计算速度，而不用变换8个顶点，再从这8个顶点中计算新AABB。下面简单地回忆4×4矩阵变换一个3D点的过程。通过原边界框xmin，ymin

17、，zmin，xmax，ymax，zmax计算新边界框，如今的任务是计算的速度。换句话说，希望找到m11x+m12y+m13z+m14的最小值。其中x，y，z是原8个顶点中的任意一个。变换的目的是找出这些点经过变换后哪一个的x坐标最小。看第一个乘积m11x，为了最小化乘积，必须决定是用xmin还是xmax来交换其中的x。显然，假设m11>0，用xmin能得到最小化的乘积；假设m11<0，那么用xmax能得到最小化乘积。比较方便的是，不管xmin还是xmax中哪一个被用来计算，都可以用另外一个来计算。可以对矩阵中的9个元素中的每一个都应用这个计算过程其他元素不影响大小。根据变换矩阵和原

18、有的AABB包装盒计算新的AABB包装盒的代码如下：void setToTransformedBoxTransform tifisEmpty/判断包装盒是否为空return；float m=new float16；t.getm；/将变换矩阵存入数组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方向上平移ifm00.0fminx+=m0*min0；ma

19、xx+=m0*max0；elseminx+=m0*max0；maxx+=m0*min0；ifm10.0fminx+=m1*min1；maxx+=m1*max1；elseminx+=m1*max1；maxx+=m1*min1；ifm20.0fminx+=m2*min2；maxx+=m2*max2；elseminx+=m2*max2；maxx+=m2*min2；ifm40.0fminy+=m4*min0；maxy+=m4*max0；elseminy+=m4*max0；maxy+=m4*min0；ifm50.0fminy+=m5*min1；maxy+=m5*max1；elseminy+=m5*max

20、1；maxy+=m5*min1；ifm60.0fminy+=m6*min2；maxy+=m6*max2；elseminy+=m6*max2；maxy+=m6*min2；ifm80.0fminz+=m8*min0；maxz+=m8*max0；elseminz+=m8*max0；maxz+=m8*min0；ifm90.0fminz+=m9*min1；maxz+=m9*max1；elseminz+=m9*max1；maxz+=m9*min1；ifm100.0fminz+=m10*min2；maxz+=m10*max2；elseminz+=m10*max2；maxz+=m10*min2；min0=mi

21、nx；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 AABBfloat getMinreturn min；float getMaxreturn max；void setMinfloat x,float y,float zmin0=x；min1=

22、y；min2=z；void setMaxfloat x,float y,float zmax0=x；max1=y；max2=z；void resetforint i=0；i 3；i+mini=0；maxi=0；/其他方法同上为了检验碰撞检测的使用构造了两个立方体，并各自绑定了一个包装盒。/*立方体1*/mesh1=createCube；/创立立方体1 mesh1.setTranslation1.0f,0.0f,0.0f；/平移mesh1.setOrientation90,0.0f,1.0f,0.0f；/旋转mesh1.setScale0.5f,0.5f,0.5f；/缩放box1=new AAB

23、B；/包装盒box1.setMin-1.0f,-1.0f,-1.0f；/设置包装盒1的最小顶点box1.setMax1.0f,1.0f,1.0f；/设置包装盒1的最大顶点mesh1.getCompositeTransformcubeTransform；/获取立方体1的混合矩阵box1.setToTransformedBoxcubeTransform；/将变换矩阵应用到包装盒中world.addChildmesh1；/将立方体1添加到场景中/*立方体2*/mesh2=createCube；/创立立方体2 mesh2.setTranslation-0.5f,0.0f,0.0f；/平移mesh2.s

24、etScale0.5f,0.5f,0.5f；/缩放box2=new AABB；/包装盒box2.setMin-1.0f,-1.0f,-1.0f；/设置包装盒2的最小顶点box2.setMax1.0f,1.0f,1.0f；/设置包装盒2的最大顶点mesh2.getCompositeTransformcubeTransform；/获取立方体2的混合矩阵box2.setToTransformedBoxcubeTransform；/将变换矩阵应用到包装盒2中world.addChildmesh2；/将立方体2添加到场景中检测包装盒1和包装盒2是否碰撞的代码如下：isCollided=e

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

26、撞到静态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不管物体从哪个方向运动，

27、碰撞过程中，肯定是先入后出，所以有tenter<tleave。n假设tenter和tleave超出运动时间范围，那么在此范围内它们是不相交的。检测出某一维的碰撞还不够，还需要进展其他两维的检测，然后取结果的交集。假设交集为空，那么两AABB包装盒没有相交，假设区间范围在时间段0，1之外，那么在此区间也不相交。对AABB进展动态检测的方法定义如下：float intersectMovingAABBAABB stationaryBox,AABB movingBox,float sfloat NoIntersection=1e30f；/没有碰撞那么返回大数float tEnter=0.0f；/

28、初始化碰撞时间float tLeave=1.0f；/初始化分开时间float Swap=0.0f；/交换操作中间变量float sBoxmin=stationaryBox.getMin；/静止包装盒的最小值顶点float sBoxmax=stationaryBox.getMax；/静止包装盒的最大值顶点float mBoxmin=movingBox.getMin；/运动包装盒的最小值顶点float mBoxmax=movingBox.getMax；/运动包装盒的最大值顶点ifs0=0.0f/假设x方向速度为0 ifsBoxmin0=mBoxmax0|sBoxmax0=mBoxmin0retur

29、n NoIntersection；/进展静态检测elsefloat xEnter=sBoxmin0-mBoxmax0/s0；/计算碰撞时间float xLeave=sBoxmax0-mBoxmin0/s0；/计算分开时间ifxEnter xLeave/检查顺序Swap=xEnter；xEnter=xLeave；xLeave=Swap；ifxEnter tEntertEnter=xEnter；/更新区间ifxLeave tLeavetLeave=xLeave；iftEnter tLeave/是否导致空重叠区return NoIntersection；/没有碰撞ifs1=0.0f/y轴速度为0 i

30、fsBoxmin1=mBoxmax1|sBoxmax1=mBoxmin1return NoIntersection；/没有相交elsefloat yEnter=sBoxmin1-mBoxmax1/s1；float yLeave=sBoxmax1-mBoxmin1/s1；ifyEnter yLeaveSwap=yEnter；yEnter=yLeave；yLeave=Swap；ifyEnter tEntertEnter=yEnter；/更新区间ifyLeave tLeavetLeave=yLeave；iftEnter tLeavereturn NoIntersection；ifs2=0.0f/z方

31、向速度为0 ifsBoxmin2=mBoxmax2|sBoxmax2=mBoxmin2return NoIntersection；elsefloat oneOverD=1.0f/s2；float zEnter=sBoxmin2-mBoxmax2/s2；float zLeave=sBoxmax2-mBoxmin2/s2；ifzEnter zLeaveSwap=zEnter；zEnter=zLeave；zLeave=Swap；ifzEnter tEntertEnter=zEnter；/更新区间ifzLeave tLeavetLeave=zLeave；iftEnter tLeavereturn No

32、Intersection；return tEnter；/返回碰撞时间为了对挪动AABB进展检测，创立两个AABB如图10-37所示。两个包装盒间隔 0.5，速度为3。图10-37挪动AABB检测检测代码如下：float speed=new float3.0f,0.0f,0.0f；float tEnter=intersectMovingAABBbox1,box2,speed；输出结果为0.16667，完全符合预期的猜测。10.3.4 OBB树碰撞检测前面提到了长条物体在旋转时AABB盒的变化，那么是否有可以在任意方向都更为准确的检测方式，答案是肯定的，这是一种基于OBB即定向包容盒子Orient

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

34、任意的网格模型创立OBB树可能是算法里最难的一个部分，而且它还要调整以适宜特定的引擎或游戏类型。从图中可以看出，不得不找出包围给定模型的最近似的包装盒或者其他3D体。如今得到了所有的包装盒，下一步将构造一棵树。从最初的AABB包装盒开场从上至下地反复分割它。另外，还可以用从下至上的方式，逐步地合并小包装盒从而得到最大的包装盒。把大的包装盒分割成小的包装盒，应该遵守以下几条原那么。1用一个面这个面垂直于包装盒中的一条坐标轴来分割包装盒上最长的轴，然后根据多边形处在分割轴的哪一边把多边形别分开来如图10-38所示。2假设不能沿着最长的轴进展分割，那就沿第二长的边分割。持续地分割直到包装盒不能再分割

35、为止。3根据需要的精度比方，是否真的要判断单个三角形的碰撞，可以按选择的方式是按树的深度或是按包装盒中多边形的数目以任意的条件停顿分割。正如读者所看到的，创立阶段相当复杂，其中包括了大量的运算，很明显不能实时地创立树，只能是事先创立。事先创立可以免去实时改变多边形的可能。另一个缺点是OBB要求进展大量的矩阵运算，不得不把它们定位在适当的地方，并且每棵子树必须与矩阵相乘。如今假设已经有了OBB或者AABB树。那么该怎么进展碰撞检测呢?首先检测最大的包装盒是否相交AABB级别，假设相交了，它们可能注意，只是可能发生了碰撞，接下来将进一步地递归处理它们OBB级别，不断地递归用下一级进展处理。假设沿着

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