cocos2dx 精确碰撞

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

1. OBB包围盒

1.1 OBB包围盒概述

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包围盒的碰撞检测常采用分离轴定理。分离轴定理（separating axis theorem）指出：如果能找到一个轴，使得两个凸形状在该轴上的投影不重叠，那么这两个形状不相交。如果这样的轴不存在，且这些形状是凸形的，则可以确定两个形状相交（凹形不适用，例如月牙形状，即使找不到分离轴，两个月牙形也可能不相交）。 该定理也可以这样理解：如果能找到一条直线，使包围盒A完全在直线的一侧，包围盒B完全在另一侧，那么两包围盒不重叠。这条直线称为分离线（在三维世界中称为分离面），且一定垂直于分离轴。

2.2 二维世界中的演示

我们先以二维世界中的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轴方向的边矢量分别与B的三个轴方向的边矢量做叉积，再取A的y轴方向与B的三个轴方向的边矢量做叉积，最后取A的z轴方向的边矢量与B的三个轴方向的边矢量做叉积，共得到3 * 3个分离轴。

2.4 代码问题及修改

在Cocos2d-x 3.3beta0版本的OBB碰撞检测函数bool OBB::intersects(const OBB& box) const中存在一个小问题，在最后的3 * 3边矢量求分离轴时，貌似调用错了方法，仍然调用的是取三个坐标轴做分离轴。以下是修改后的源码：

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

通过上述内容，我们详细介绍了OBB包围盒及其碰撞检测方法，希望能帮助开发者更好地理解和应用Cocos2d-x中的精确碰撞检测。