cocos2dx 精确碰撞

在Cocos2d-x 3.3beta0版本中，有一个小乌龟碰撞检测的例子，该例子采用的并非AABB碰撞检测，而是比AABB包围盒更为精确的OBB包围盒碰撞检测方法。本文将详细介绍OBB包围盒及其碰撞检测方法。

1. OBB包围盒

1.1 基本概念

OBB（Oriented Bounding Box）包围盒，也被称为有向包围盒或定向包围盒。它会随着物体的移动、缩放和旋转而变化，简单来说，它是一个能够旋转的AABB包围盒。在Cocos2d-x中使用过物理引擎的开发者应该见过，当在物理世界中创建一个物体并开启调试模式时，该物体会被一个红色矩形包围，当物体进行平移或旋转操作时，这个红色矩形也会做相同的动作，这个红色矩形就是该物体的OBB包围盒。

相较于AABB包围盒，OBB在碰撞精度上更高，但精度的提升也带来了效率的降低。OBB的算法比AABB复杂，内存消耗也更大，这一点可以从OBB的表达式中得到印证。

1.2 OBB包围盒的表达式

表达AABB包围盒或OBB包围盒有多种方式，需要选择最优的一种。对于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%的内存消耗。

1.3 OBB包围盒的创建

如何用高效的算法构建紧密包围的OBB包围盒或AABB包围盒是一个复杂的问题，因为不同形状物体的包围方式不同。这里不探讨构建OBB包围盒的原理，仅了解Cocos2d-x 3.3beta0中提供的构建方法。

在Cocos2d-x中，有两种方法用于计算OBB：

• 第一种是简化的OBB构建算法，通过一个AABB包围盒来确定最终的OBB包围盒；
• 第二种是通过协方差矩阵来确定一个方向包围盒（实际上，无论是AABB包围盒还是OBB包围盒，真正的难点都在于包围盒的构建）。

第一种方法在Cocos2d-x中使用起来更为简单，示例代码如下：

AABB aabb = _sprite->getAABB();//获取一个Sprite3D对象的aabb包围盒
OBB  _obbt = OBB(aabb);//创建obb包围盒

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

2.1 分离轴定理

OBB包围盒的碰撞检测方法通常采用分离轴定理。简单来说，分离轴定理指出：如果能找到一个轴，使得两个凸形状在该轴上的投影不重叠，那么这两个形状不相交；如果这样的轴不存在，且这些形状是凸形的，则可以确定两个形状相交（该定理不适用于凹形，例如月牙形状，即使找不到分离轴，两个月牙形也可能不相交）。

也可以这样理解：如果能找到一条直线，使包围盒A完全在直线的一侧，包围盒B完全在另一侧，那么两包围盒不重叠。这条直线被称为分离线（在三维世界中称为分离面），并且一定垂直于分离轴。

2.2 二维OBB碰撞演示

这里先以二维世界中的OBB为例进行演示，理解其原理后，三维物体的OBB碰撞就容易理解了。

在二维情况下，针对某一分离轴L，如果包围盒A与包围盒B在轴L上的投影的半径和小于包围盒中心点间距在L上的投影距离，那么包围盒A与包围盒B处于分离状态，用运算式表示为：|T * L| > rA + rB。

在Cocos2d-x 3.3beta0中验证相交时，采用的方法是：取物体A及物体B的最大点和最小点的投影坐标，然后比较A的最大点与B的最小点，以及B的最小点与A的最大点。需要注意的是，尽管这里是二维图像，但三维图面体在分离轴上的投影原理与二维相同，都是一个线段。

2.3 分离轴的选取

由于潜在的分离轴可能有无数种，不需要逐个验证，只需选取几个可测试的轴即可。以Cocos2d-x中选用的OBB包围盒（凸面体为长方体）为例，两个长方体的碰撞可以归结为以下几种组合：面 - 面碰撞、面 - 边碰撞、边 - 边碰撞（顶点视为边的一部分）。

因此，在选取分离轴时，只需分别取第一个包围盒的3个坐标轴、第二个包围盒的3个坐标轴，以及垂直于某一轴的9个轴（其他分离轴都与这15个分离轴中的某一个轴平行，投影所得线段值相同，无需再验证）。

这里解释一下垂直于某一轴的9个轴的获取方法：首先取包围盒A的x轴方向的某一边矢量，再取包围盒B的x轴方向的某一边矢量，对这两个矢量做叉积，得到一个垂直于A的矢量与B的矢量的方向矢量，这个结果就是所需的分离轴。按照这种方法，分别取A的x轴、y轴、z轴方向的边矢量与B的三个轴方向的边矢量做叉积，一共可得到3 * 3个分离轴。

2.4 代码示例

在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;
//后续代码省略，原文此处未完整给出
}

通过以上内容，我们详细介绍了Cocos2d-x中OBB包围盒的相关知识，包括其定义、表达式、创建方法以及碰撞检测方法，并给出了相应的代码示例。