cocos2dx 精确碰撞

03月

10304 0

cocos2dx 精确碰撞Cocos2d-x 3.3beta0版本中小乌龟碰撞检测的例子，这个例子使用的并非是AABB碰撞检测，而是比AABB包围盒更加精确的OBB包围盒的碰撞检测方法，本篇文章将对OBB包围盒及其碰撞检测方法进行介绍。

1. OBB包围盒

OBB(Oriented Bounding Box)包围盒也被称作有向包围盒或定向包围盒，它会随着物体的移动、缩放、旋转。简单来说，它就是一个能够旋转的AABB包围盒。在Cocos2d-x中使用过物理引擎的开发者一定见过当我们在物理世界中创建一个物体并开启调试模式时，这个物体会被红色的矩形包围，当物体做平移或旋转时，这个红色矩形也会做同样的操作，这个红色矩形正是该物体的OBB包围盒。如图1-1所示：

图1-1 相对于AABB包围盒来讲，OBB在碰撞精度上要高于AABB，但是精确度的提高同时带来的就是效率的降低，OBB的算法无疑是要比AABB复杂的，同样内存消耗也会更大，这个问题我们可以从OBB的表达式来得到结论。

OBB包围盒的表达式：

表达一个AABB包围盒或OBB包围盒都有若干种方式，但是无疑需要选中里面最优的一种。对于AABB来说，通常只要使用两个顶点的坐标信息标识一个AABB包围盒就可以了，其它的顶点信息都可以通过计算得出。但是对于OBB包围盒的表达方式只有两点信息显然是不够的。
想要唯一标识一个OBB包围盒我们大概会想到，使用8个顶点的集合、6个面的集合、1个顶点和3各彼此正交的边向量，又或者是1个中心点、1个旋转矩阵和3个1/2边长(注：一个旋转矩阵包含了三个旋转轴，若是二维的OBB包围盒则是一个中心点，两个旋转轴，两个1/2边长)。
上述最后一种方法就是最常用的方法，下面来看一段Cocos2d-x 3.3beta0中CCOBB.h中的代码：

Vec3 _center;   // 中心点
		
/*
		
以下三个变量为正交单位向量，
		
定义了当前OBB包围盒的x,y,z轴
		
用于计算矢量投影
		
*/
		
Vec3 _xAxis;    // 包围盒x轴方向单位矢量
		
Vec3 _yAxis;    // 包围盒y轴方向单位矢量
		
Vec3 _zAxis;    // 包围盒z轴方向单位矢量
		
Vec3 _extents;  // 3个1/2边长,半长、半宽、半高

Cocos2d-x 3.0beta0在CCOBB.h中定义了五个成员变量，每一个数据类型都是一个三维向量，包含了3个浮点数。也就是说，表达一个OBB包围盒需要15个float类型的变量，占用60个字节，然而表示一个AABB包围盒仅需要两个顶点，24个字节，从这一点上来说，OBB的内存消耗算很高了。

一种减少开销的方案是：只存储旋转矩阵的两个轴，只是在测试时利用叉积计算第三个轴，这样可以减少CPU操作开销并节省3个浮点数分量，降低20%内存消耗。

OBB包围盒的创建：

如何用一个高效的算法构建一个紧密包围的OBB包围盒或是AABB包围盒是一个很复杂的问题，因为不同的形状物体的包围是不同的，这里我们不去探讨构建OBB包围盒的原理，只了解一下Cocos2d-x 3.3beta0 中为我们提供的构建方法。在Cocos2d-x 中使用了两种方法去计算OBB，第一种方法是一种简化的OBB构建算法，由一个AABB包围盒来确定最终OBB包围盒，另外一种方法是通过协方差矩阵来确定一个方向包围盒(实际上无论是AABB包围盒还是OBB包围盒，真正的难点便在于包围盒的构建上)。
在Cocos2d-x中第一种方法用起来更为简单一些，例如：

1.AABB aabb = _sprite->getAABB();//获取一个Sprite3D对象的aabb包围盒

2.OBB _obbt = OBB(aabb);//创建obb包围盒

2. OBB包围盒的碰撞检测方法

OBB包围盒的碰撞检测方法常采用的是分离轴定理，首先简单说明一下分离轴定理(separating axis theorem)，通过分离轴定理我们可以得到如下结论：如果能找到一个轴，两个凸形状在该轴上的投影不重叠，则这两个形状不相交。如果这个轴不存在，并且那些形状是凸形的，则可以确定两个形状相交(凹形不适用，比如月牙形状，即使找不到分离轴，两个月牙形也可能不相交)。这个定理也可以这样理解，如果能找到一条直线，令包围盒A完全在直线的一边，包围盒B完全在另一边，则两包围盒不重叠。而这条直线便成为分离线(在三维世界中被称为分离面)，并且一定垂直于分离轴。
这里我们还是先来用二维世界中的OBB来进行演示，明白其中原理之后三维物体的OBB便十分容易理解了，如图2-1所示：

图2-1
在图2-1中，针对某一分离轴L，如果包围盒A与包围盒B在轴L上的投影的半径和小于包围盒中心点间距在L的投影距离，那么包围盒A与包围盒B处于分离状态。使用运算式来表达就是：|T * L|>rA + rB。在Cocos2d-x 3.3beta0中验证相交时采用的并非这个方法，Cocos2d-x选用的方法是，取物体A及物体B的最大点和最小点的投影坐标，然后比较A的最大点与B的最小点，B的最小点与A的最大点。注意，尽管这是一个二维图像，但是实际上三维的图面体在分离轴上的投影跟二维的原理是一样的，都是一个线段。现在知道了分离轴定理的原理，下面则是如何选取分离轴。由于潜在的分离轴可能存在无数种，所以我们并非去要逐个验证，而是选取几个可测试的轴即可。例如Cocos2d-x中所选用的OBB包围盒的凸面体均为长方体，我们就以长方体的碰撞为例，两个长方体的碰撞可以将其归结为以下几种组合：面-面碰撞、面-边碰撞、边-边碰撞(顶点视为边的一部分)。所以实际上在取分离轴的时候，只需要分别取第一个包围盒的3个坐标轴，第二个包围盒的3个坐标轴，以及垂直于某一轴的9个轴(其他的分离轴都是跟这15个分离轴中的某一个轴平行的轴，投影所得线段值都一样，无需再验证)。
这里再解释以下什么是垂直于某一轴的9个轴，具体的做法就是，首先取包围盒A的x轴方向的某一边矢量，再取包围盒B的x轴方向的某一边矢量，对两个矢量做叉积，求出一个垂直于A的矢量与B的矢量的方向矢量，这个结果就是需要使用的分离轴。按照这种做法，取A的x轴方向的边矢量分别与B的三个轴方向的边矢量做叉积，再取A的y轴方向与B的三个轴方向的边矢量做叉积，再取A的z轴方向的边矢量与B的三个轴方向的边矢量做叉积，结果一共3*3个分离轴。如图2-2所示：

图2-2
图中的顶点顺序是按照Cocos2d-x中定义的OBB包围盒的顶点顺序定义的。图中的x代表的就是包围盒的x轴方向边的矢量(注意这里写的是矢量，不是x,y,z坐标轴)，当然这个方向的矢量有无数个，我们只需取一个代表性的用来计算叉积即可。
最后在Cocos2d-x 3.3beta0版本中的OBB碰撞检测函数 bool OBB::intersects(const OBB& box) const 中遇到了一点小问题，在最后的3*3边矢量求分离轴的时候2d-x中貌似调用错了方法，仍然你调用的是取三个坐标轴做分离轴，笔者下面做了一些修改，最后附上源码。 CCOBB.h代码如下：

#ifndef __CC_OBB_H__
		
#define __CC_OBB_H__
		
 
		
#include "CCAABB.h"
		
#include "3d/3dExport.h"
		
 
		
NS_CC_BEGIN
		
 
		
class CC_3D_DLL OBB
		
{
		
public:
		
OBB();//默认构造函数
		
 
		
/*
		
* 构造函数 根据一个AABB包围盒初始化一个OBB包围盒
		
*/
		
OBB(const AABB& aabb);
		
 
		
/*
		
* 构造函数 根据点信息初始化一个OBB包围盒
		
*/
		
OBB(const Vec3* verts, int num);
		
 
		
/*
		
* 判断点是否在一个OBB包围盒内
		
*/
		
bool containPoint(const Vec3& point) const;
		
 
		
/*
		
* 指定OBB各成员变量的值
		
*/
		
void set(const Vec3& center, const Vec3& _xAxis, const Vec3& _yAxis, const Vec3& _zAxis, const Vec3& _extents);
		
 
		
/*
		
* 复位函数 将当前OBB对象所占用的内存块置零
		
*/
		
void reset();
		
 
		
/* 面向包围盒z轴负方向
		
* verts[0] : 左上点坐标
		
* verts[1] : 左下点坐标
		
* verts[2] : 右下点坐标
		
* verts[3] : 右上点坐标
		
*
		
* 面向包围盒z轴正方向
		
* verts[4] : 右上点坐标
		
* verts[5] : 右下点坐标
		
* verts[6] : 左下点坐标
		
* verts[7] : 左上点坐标
		
*/
		
void getCorners(Vec3* verts) const;
		
 
		
/*
		
*检测是否和其他OBB盒碰撞
		
*/
		
bool intersects(const OBB& box) const;
		
 
		
/**
		
* 由给定的变换矩阵变换OBB包围盒
		
*/
		
void transform(const Mat4& mat);
		
 
		
protected:
		
/*
		
* 将点投影到目标轴
		
*/
		
float projectPoint(const Vec3& point, const Vec3& axis) const;
		
 
		
/*
		
* 计算最大和最小投影值
		
*/
		
void getInterval(const OBB& box, const Vec3& axis, float &min, float &max) const;
		
 
		
/*
		
* 取边的矢量 获取分离轴使用
		
*/
		
Vec3 getEdgeDirection(int index) const;
		
 
		
/*
		
* 取面的方向矢量 获取分离轴时使用
		
*/
		
Vec3 getFaceDirection(int index) const;
		
 
		
public:
		
Vec3 _center;   // 中心点
		
/*
		
以下三个变量为正交单位向量，
		
定义了当前OBB包围盒的x,y,z轴
		
用于计算矢量投影
		
*/
		
Vec3 _xAxis;    // 包围盒x轴方向单位矢量
		
Vec3 _yAxis;    // 包围盒y轴方向单位矢量
		
Vec3 _zAxis;    // 包围盒z轴方向单位矢量
		
Vec3 _extents;  // 3个1/2边长,半长、半宽、半高
		
};
		
 
		
NS_CC_END
		
 
		
#endif

CCOBB.cpp代码如下:

#include "3d/CCOBB.h"
		
 
		
NS_CC_BEGIN
		
 
		
#define ROTATE(a,i,j,k,l) g=a.m[i + 4 * j]; h=a.m[k + 4 * l]; a.m[i + 4 * j]=(float)(g-s*(h+g*tau)); a.m[k + 4 * l]=(float)(h+s*(g-h*tau));
		
 
		
//生成协方差矩阵
		
static Mat4 _getConvarianceMatrix(const Vec3* vertPos, int vertCount)
		
{
		
int i;
		
Mat4 Cov;
		
 
		
double S1[3];
		
double S2[3][3];
		
 
		
S1[0] = S1[1] = S1[2] = 0.0;
		
S2[0][0] = S2[1][0] = S2[2][0] = 0.0;
		
S2[0][1] = S2[1][1] = S2[2][1] = 0.0;
		
S2[0][2] = S2[1][2] = S2[2][2] = 0.0;
		
 
		
// get center of mass
		
for(i=0; i<vertCount; i++)
		
{
		
S1[0] += vertPos[i].x;
		
S1[1] += vertPos[i].y;
		
S1[2] += vertPos[i].z;
		
 
		
S2[0][0] += vertPos[i].x * vertPos[i].x;
		
S2[1][1] += vertPos[i].y * vertPos[i].y;
		
S2[2][2] += vertPos[i].z * vertPos[i].z;
		
S2[0][1] += vertPos[i].x * vertPos[i].y;
		
S2[0][2] += vertPos[i].x * vertPos[i].z;
		
S2[1][2] += vertPos[i].y * vertPos[i].z;
		
}
		
 
		
float n = (float)vertCount;
		
// now get covariances
		
Cov.m[0] = (float)(S2[0][0] - S1[0]*S1[0] / n) / n;
		
Cov.m[5] = (float)(S2[1][1] - S1[1]*S1[1] / n) / n;
		
Cov.m[10] = (float)(S2[2][2] - S1[2]*S1[2] / n) / n;
		
Cov.m[4] = (float)(S2[0][1] - S1[0]*S1[1] / n) / n;
		
Cov.m[9] = (float)(S2[1][2] - S1[1]*S1[2] / n) / n;
		
Cov.m[8] = (float)(S2[0][2] - S1[0]*S1[2] / n) / n;
		
Cov.m[1] = Cov.m[4];
		
Cov.m[2] = Cov.m[8];
		
Cov.m[6] = Cov.m[9];
		
 
		
return Cov;
		
}
		
//获取一个矢量在某个轴的分量
		
static float& _getElement( Vec3& point, int index)
		
{
		
if (index == 0)
		
return point.x;
		
if (index == 1)
		
return point.y;
		
if (index == 2)
		
return point.z;
		
 
		
CC_ASSERT(0);
		
return point.x;
		
}
		
//获取特征向量
		
static void _getEigenVectors(Mat4* vout, Vec3* dout, Mat4 a)
		
{
		
int n = 3;
		
int j,iq,ip,i;
		
double tresh, theta, tau, t, sm, s, h, g, c;
		
int nrot;
		
Vec3 b;
		
Vec3 z;
		
Mat4 v;
		
Vec3 d;
		
 
		
v = Mat4::IDENTITY;
		
for(ip = 0; ip < n; ip++)
		
{
		
_getElement(b, ip) = a.m[ip + 4 * ip];
		
_getElement(d, ip) = a.m[ip + 4 * ip];
		
_getElement(z, ip) = 0.0;
		
}
		
 
		
nrot = 0;
		
 
		

  
  0