整理3d碰撞检测技术文档格式.docx
《整理3d碰撞检测技术文档格式.docx》由会员分享，可在线阅读，更多相关《整理3d碰撞检测技术文档格式.docx（24页珍藏版）》请在冰点文库上搜索。
10.3.2
球体碰撞检测
真实的物理模拟系统需要非常精确的碰撞检测算法，但是游戏中常常只需要较为简单的碰撞检测，因为只需要知道物体什么时候发生碰撞，而不用知道模型的哪个多边形发生了碰撞，因此可以将不规则的物体投影成较规则的物体进行碰撞检测。
球体只有一个自由度，其碰撞检测是最简单的数学模型，我们只需要知道两个球体的球心和半径就能进行检测。
那么球体碰撞是如何工作的？
主要过程如下。
n
计算两个物体中心之间的距离，并且将其与两个球体的半径和进行比较。
如果距离大于半径和，则没有发生碰撞。
否则，如果距离小于半径和，则发生了物体碰撞。
考虑由球心c1、c2和半径r1、r2定义的两个球，如图10-26所示。
设d为球心间的距离。
很明显，当d＜r1+r2时相交，在实践中通过比较d2＜（r1+r2）2，可以避免包括计算d在内的平方根运算。
对两个运动的球进行碰撞检测要麻烦一些，假设两个球的运动向量为d1和d2，球与位移向量是一一对应的，它们描述了所讨论时间段中的运动方式。
事实上，物体的运动是相对的，例如两列在两条平行轨道上相向行驶的火车，在其中一列中观察，对方的速度是两车速度之和。
同样，也可以从第一个球的角度来简化问题，假设第一个球是“静止”的，另一个是“运动”的，那么该运动向量等于原向量d1和d2之差，如图10-27所示。
图10-27
动态球的检测过程
球体碰撞的优点是非常适用于需要快速检测的游戏，因为它不需要精确的碰撞检测算法。
执行速度相对较快，不会给CPU带来过大的计算负担。
球体碰撞的另一个劣势是只适用于近似球形物体，如果物体非常窄或者非常宽，该碰撞检测算法将会失效，因为会在物体实际发生碰撞之前，碰撞检测系统就发出碰撞信号，如图10-28所示是球体碰撞检测中可能出现的坏情况，其解决方法是缩小检测半径，或者使用其他检测模型，如图10-29所示。
图10-28
球体碰撞的坏情况
图10-29
缩小检测半径
为了解决包容球精确度不高的问题，人们又提出了球体树的方法。
球体树实际上是一种表达3D物体的层次结构。
对一个形状复杂的3D物体，先用一个大球体包容整个物体，然后对物体的各个主要部分用小一点的球体来表示，然后对更小的细节用更小的包容球体，这些球体和它们之间的层次关系就形成了一个球体树。
举例来说，对一个游戏中的人物角色，可以用一个大球来表示整个人，然后用中等大小的球体来表示四肢和躯干，然后用更小的球体来表示手脚等。
这样在对两个物体进行碰撞检测时，先比较两个最大的球体。
如果有重叠，则沿树结构向下遍历，对小一点的球体进行比较，直到没有任何球体重叠，或者到了最小的球体，这个最小的球体所包含的部分就是碰撞的部分，如图10-30所示。
10.3.3
AABB立方体边界框检测
用球体去近似地代表物体运算量很小，但在游戏中的大多数物体是方的或者长条形的，应该用方盒来代表物体。
另一种常见的检测模型是立方体边界框，如图10-31展示了一个AABB检测盒和它里面的物体。
坐标轴平行（Axially-aligned）不仅指盒体与世界坐标轴平行，同时也指盒体的每个面都和一条坐标轴垂直，这样一个基本信息就能减少转换盒体时操作的次数。
AABB技术在当今的许多游戏中都得到了应用，开发者经常用它们作为模型的检测模型，再次指出，提高精度的同时也会降低速度。
因为AABB总是与坐标轴平行，不能在旋转物体时简单地旋转AABB，而是应该在每一帧都重新计算。
如果知道每个对象的内容，这个计算就不算困难，也不会降低游戏的速度。
然而，还面临着精度的问题。
假如有一个3D的细长刚性直棒，并且要在每一帧动画中都重建它的AABB。
可以看到每一帧中的包装盒都不一样而且精度也会随之改变，如图10-32所示。
图10-31
3D模型与AABB检测盒
图10-32
不同方向的AABB
可以注意到AABB对物体的方向很敏感，同一物体的不同方向，AABB也可能不同（由于球体只有一个自由度，所以检测球对物体方向不敏感）。
当物体在场景中移动时，它的AABB也需要随之移动，当物体发生旋转时，有两种选择：
用变换后的物体来重新计算AABB，或者对AABB做和物体同样的变换。
如果物体没有发生扭曲，可以通过“变换后的AABB”重新计算，因为该方法要比通过“变换后的物体”计算快得多，因为AABB只有8个顶点。
变换AABB得出新的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，zmax），记作：
float[]min=newfloat[]{0.0f,0.0f,0.0f};
float[]max=newfloat[]{0.0f,0.0f,0.0f};
中心点是两个顶点的中点，代表了包装盒的质点。
float[]center=newfloat[]{0.0f,0.0f,0.0f};
中心点的计算方法如下：
float[]center（）{
center[0]=（min[0]+max[0]）*0.5f;
center[1]=（min[1]+max[1]）*0.5f;
center[2]=（min[2]+max[2]）*0.5f;
returncenter;
}
通过这两个顶点可以知道以下属性。
floatxSize（）{return（max[0]-min[0]）;
}
floatySize（）{return（max[1]-min[1]）;
floatzSize（）{return（max[2]-min[2]）;
floatsize（）{return（max[0]-min[0]）*（max[1]-min[1]）*（max[2]-min[2]）;
当添加一个顶点到包装盒时，需要先与这两个顶点进行比较。
voidadd（float[]p）{
if（p[0]<
min[0]）min[0]=p[0];
if（p[0]>
max[0]）max[0]=p[0];
if（p[1]<
min[1]）min[1]=p[1];
if（p[1]>
max[1]）max[1]=p[1];
if（p[2]<
min[2]）min[2]=p[2];
if（p[2]>
max[2]）max[2]=p[2];
检测包装盒是否为空，可以将这两个顶点进行比较。
booleanisEmpty（）{
return（min[0]>
max[0]）||（min[1]>
max[1]）||（min[2]>
max[2]）;
检测某个点是否属于AABB范围之内的代码如下：
booleancontains（float[]p）{
return
（p[0]>
=min[0]）&
&
（p[0]<
=max[0]）&
（p[1]>
=min[1]）&
（p[1]<
=max[1]）&
（p[2]>
=min[2]）&
（p[2]<
=max[2]）;
AABB的静态检测比较简单，检测两个静止包装盒是否相交，它是一种布尔测试，测试结果只有相交或者不相交。
这里我们还提供了获取相交范围信息的方法，一般来说，这种测试的目的是为了返回一个布尔值。
碰撞的示意如图10-34所示。
图10-34
包装盒的碰撞
检测静态AABB碰撞的方法如下：
booleanintersectAABBs（AABBbox2,AABBboxIntersect）
{
float[]box2_min=box2.getMin（）;
float[]box2_max=box2.getMax（）;
if（min[0]>
box2_max[0]）returnfalse;
if（max[0]<
box2_min[0]）returnfalse;
if（min[1]>
box2_max[1]）returnfalse;
if（max[1]<
box2_min[1]）returnfalse;
if（min[2]>
box2_max[2]）returnfalse;
if（max[2]<
box2_min[2]）returnfalse;
if（boxIntersect!
=null）{
float[]box_intersect_min=newfloat[3];
float[]box_intersect_max=newfloat[3];
box_intersect_min[0]=Math.max（min[0],box2_min[0]）;
box_intersect_max[0]=Math.min（max[0],box2_max[0]）;
box_intersect_min[1]=Math.max（min[1],box2_min[1]）;
box_intersect_max[1]=Math.min（max[1],box2_max[1]）;
box_intersect_min[2]=Math.max（min[2],box2_min[2]）;
box_intersect_max[2]=Math.min（max[2],box2_max[2]）;
returntrue;
可以利用AABB的结构来加快新的AABB的计算速度，而不用变换8个顶点，再从这8个顶点中计算新AABB。
下面简单地回顾4×
4矩阵变换一个3D点的过程。
通过原边界框（xmin，ymin，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个元素中的每一个都应用这个计算过程（其他元素不影响大小）。
根据变换矩阵和原有的AABB包装盒计算新的AABB包装盒的代码如下：
voidsetToTransformedBox（Transformt）
if（isEmpty（））{
//判断包装盒是否为空
return;
float[]m=newfloat[16];
t.get（m）;
//将变换矩阵存入数组
floatminx=0,miny=0,minz=0;
floatmaxx=0,maxy=0,maxz=0;
minx+=m[3];
//x方向上平移
maxx+=m[3];
miny+=m[7];
//y方向上平移
maxy+=m[7];
minz+=m[11];
//z方向上平移
maxz+=m[11];
if（m[0]>
0.0f）{
minx+=m[0]*min[0];
maxx+=m[0]*max[0];
}else{
minx+=m[0]*max[0];
maxx+=m[0]*min[0];
if（m[1]>
minx+=m[1]*min[1];
maxx+=m[1]*max[1];
minx+=m[1]*max[1];
maxx+=m[1]*min[1];
if（m[2]>
minx+=m[2]*min[2];
maxx+=m[2]*max[2];
minx+=m[2]*max[2];
maxx+=m[2]*min[2];
if（m[4]>
miny+=m[4]*min[0];
maxy+=m[4]*max[0];
miny+=m[4]*max[0];
maxy+=m[4]*min[0];
if（m[5]>
miny+=m[5]*min[1];
maxy+=m[5]*max[1];
miny+=m[5]*max[1];
maxy+=m[5]*min[1];
if（m[6]>
miny+=m[6]*min[2];
maxy+=m[6]*max[2];
miny+=m[6]*max[2];
maxy+=m[6]*min[2];
if（m[8]>
minz+=m[8]*min[0];
maxz+=m[8]*max[0];
minz+=m[8]*max[0];
maxz+=m[8]*min[0];
if（m[9]>
minz+=m[9]*min[1];
maxz+=m[9]*max[1];
minz+=m[9]*max[1];
maxz+=m[9]*min[1];
if（m[10]>
minz+=m[10]*min[2];
maxz+=m[10]*max[2];
minz+=m[10]*max[2];
maxz+=m[10]*min[2];
min[0]=minx;
min[1]=miny;
min[2]=minz;
//用新的AABB坐标替换原有坐标
max[0]=maxx;
max[1]=maxy;
max[2]=maxz;
为了使用AABB包装盒进行碰撞检测，将这些方法和属性封装为AABB类，代码如下：
importjava.lang.Math;
importjavax.microedition.m3g.Transform;
classAABB{
publicAABB（）{}
float[]getMin（）{returnmin;
float[]getMax（）{returnmax;
voidsetMin（floatx,floaty,floatz）{min[0]=x;
min[1]=y;
min[2]=z;
voidsetMax（floatx,floaty,floatz）{max[0]=x;
max[1]=y;
max[2]=z;
voidreset（）{
for（inti=0;
i<
3;
i++）
min[i]=0;
max[i]=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=newAABB（）;
//包装盒
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=newAABB（）;
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中
升级会员 