出處 :http://blog.csdn.net/u012945598/article/details/39524343
在Cocos2d-x 3.x版本添加了對(duì)3D物體的支持后檩帐,3D物體的碰撞檢測(cè)方法也隨之更新悔详,其中一種最簡(jiǎn)單的碰撞檢測(cè)方法就是AABB碰撞檢測(cè)。
? ? ? ? 在游戲中,為了簡(jiǎn)化物體之間的碰撞檢測(cè)運(yùn)算歹河,通常會(huì)對(duì)物體創(chuàng)建一個(gè)規(guī)則的幾何外形將其包圍史隆。
? ? ? ? 其中,AABB(axis-aligned bounding box)包圍盒被稱為軸對(duì)其包圍盒脂男。
? ? ? ? 二維場(chǎng)景中的AABB包圍盒具備特點(diǎn):(注:由于Cocos2d-x是基于Opengl ES的晴竞,所以下圖中的所有坐標(biāo)系均采用右手直角坐標(biāo)系)
? ? ? ?(1) 表現(xiàn)形式為四邊形,即用四邊形包圍物體狠半。
? ? ? ?(2) 四邊形的每一條邊噩死,都會(huì)與坐標(biāo)系的軸垂直。
? ? ? ? 如圖 1-1 所示:
? ? ? ? ? ?圖1-1
? ? ? ? ?三維場(chǎng)景中的AABB包圍盒特點(diǎn):
? ? ? ?(1) 表現(xiàn)形式為六面體神年。
? ? ? ?(2) 六面體中的每條邊都平行于一個(gè)坐標(biāo)平面已维。
? ? ? ? 如圖 1-2 所示:
圖 1-2(圖片來(lái)源百度)
在圖1-2中,為了更明顯的展示AABB包圍盒的特點(diǎn)已日,在最右側(cè)展示了一個(gè)OBB(Oriented Bounding Box)包圍盒垛耳,也稱作有向包圍盒。
? ? ? ? 可以看出,AABB包圍盒與OBB包圍盒的最直接的區(qū)別就是堂鲜,AABB包圍盒是不可以旋轉(zhuǎn)的栈雳,而OBB包圍盒是可以旋轉(zhuǎn)的,也就是有向的缔莲。
2. 二維場(chǎng)景中的AABB碰撞檢測(cè)原理
? ? ? ? 首先來(lái)看一張二維場(chǎng)景中的物體碰撞圖:
圖 2-1
? ? ? ? 在圖 2-1中哥纫,分別做物體A與物體B在X,Y軸方向的投影,物體A的Y軸方向最大點(diǎn)坐標(biāo)為Y1痴奏,最小點(diǎn)坐標(biāo)Y2蛀骇,X軸方向最小點(diǎn)坐標(biāo)X1,最大點(diǎn)坐標(biāo)X2读拆,物體B同理擅憔。
圖中紅色區(qū)域?yàn)槲矬wA與物體B投影的重疊部分。
? ? ? ? 可以看出檐晕,AABB碰撞檢測(cè)具有如下規(guī)則:
? ? ? ? 物體A與物體B分別沿兩個(gè)坐標(biāo)軸做投影暑诸,只有在兩個(gè)坐標(biāo)軸都發(fā)生重疊的情況下,兩個(gè)物體才意味著發(fā)生了碰撞棉姐。
? ? ? ? 所以屠列,在程序中做二維游戲的AABB碰撞檢測(cè)時(shí),只需驗(yàn)證物體A與物體B是否滿足如下條件:
? ? ? ? (1)物體A的Y軸方向最小值大于物體B的Y軸方向最大值伞矩;
? ? ? ? (2)物體A的X軸方向最小值大于物體B的X軸方向最大值笛洛;
? ? ? ? (3)物體B的Y軸方向最小值大于物體A的Y軸方向最大值;
? ? ? ? (4)物體B的X軸方向最小值大于物體A的X軸方向最大值乃坤;
? ? ? ? 若滿足上述條件苛让,則證明物體A與物體B并未發(fā)生重合,反之湿诊,則證明物體A與物體B重合狱杰。
3. 三維場(chǎng)景中的AABB碰撞檢測(cè)原理
? ? ? ?首先,再來(lái)看一下圖2-1中的二維物體A和物體B的包圍盒厅须,可以發(fā)現(xiàn)實(shí)際上判斷物體A與物體B是否發(fā)生重合只需要知道兩個(gè)信息:
? ? ? ?(1) 物體A的最小點(diǎn)的信息仿畸,即圖2-1中A的左下角點(diǎn);以及物體A的最大點(diǎn)的信息朗和,即圖2-1中A的右上角點(diǎn)错沽。
? ? ? ?(2) 物體B的最小點(diǎn)的信息,物體B的最大點(diǎn)的信息眶拉。
? ? ? ?也就是說(shuō)在二維場(chǎng)景的碰撞檢測(cè)中千埃,每個(gè)物體的頂點(diǎn)坐標(biāo)信息都可以由兩個(gè)坐標(biāo)來(lái)確定,即兩個(gè)坐標(biāo)就可以標(biāo)識(shí)一個(gè)物體了忆植,所以兩個(gè)物體的碰撞檢測(cè)只需要獲得到四個(gè)點(diǎn)坐標(biāo)就可以了放可。
? ? ? ?之前在圖1-2中已經(jīng)看到谒臼,三維場(chǎng)景中物體的AABB包圍盒是一個(gè)六面體,其坐標(biāo)系對(duì)于二維坐標(biāo)系來(lái)講只是多了一個(gè)Z軸耀里,所以實(shí)際上在三維場(chǎng)景中物體的AABB碰撞檢測(cè)依然可以采用四個(gè)點(diǎn)信息的判定來(lái)實(shí)現(xiàn)蜈缤。即從物體A的八個(gè)頂點(diǎn)與物體B的八個(gè)頂點(diǎn)分別選出兩個(gè)最大與最小的頂點(diǎn)進(jìn)行對(duì)比。三維物體的AABB包圍盒的八個(gè)頂點(diǎn)依舊可以用兩個(gè)頂點(diǎn)來(lái)標(biāo)識(shí)备韧,如圖 3-1 所示:
圖3-1
? ? ? ? 只要確定了圖中黑色點(diǎn)部分的坐標(biāo)劫樟,就可以確定八個(gè)頂點(diǎn)的全部信息了。
在Cocos2d-x 3.x版本中织堂,為開(kāi)發(fā)者提供了AABB類叠艳,用于保存包圍盒的最大頂點(diǎn)與最小頂點(diǎn)的信息,并且為每個(gè)Sprite3D對(duì)象提供了獲取AABB包圍盒的接口易阳,在AABB類同時(shí)提供了判斷相應(yīng)的碰撞檢測(cè)的方法附较。有一點(diǎn)需要注意的是,CCAABB類中一開(kāi)始保存的最大頂點(diǎn)與最小頂點(diǎn)的信息實(shí)際上是物體坐標(biāo)系中的信息潦俺,而實(shí)際上在碰撞檢測(cè)時(shí)需要將其轉(zhuǎn)換成世界坐標(biāo)系中的點(diǎn)拒课,這一過(guò)程在Sprite3D中的getAABB()方法中實(shí)現(xiàn),可通過(guò)CCAABB中的
transform()方法來(lái)完成事示。
? ? ? ? 下面對(duì)AABB的源碼進(jìn)行分析:
CCAABB.h 文件
class CC_3D_DLL AABB
{
public:
? ? /**
? ? * 構(gòu)造函數(shù)
? ? */
? ? AABB();
? ? /**
? ? * 構(gòu)造函數(shù) 參數(shù):最小頂點(diǎn)坐標(biāo)早像,最大頂點(diǎn)坐標(biāo)
? ? */
? ? AABB(const Vec3& min, const Vec3& max);
? ? /**
? ? * 構(gòu)造函數(shù) 參數(shù):AABB包圍盒
? ? */
? ? AABB(const AABB& box);
? ? /**
? ? * 獲取包圍盒中心點(diǎn)坐標(biāo)
? ? */
? ? Vec3 getCenter();
? ? /* 獲取包圍盒八個(gè)頂點(diǎn)信息
? ? * Z軸正方向的面
? ? * verts[0] : 左上頂點(diǎn)
? ? * verts[1] : 左下頂點(diǎn)
? ? * verts[2] : 右下頂點(diǎn)
? ? * verts[3] : 右上頂點(diǎn)
? ? *
? ? * Z軸負(fù)方向的面
? ? * verts[4] : 右上頂點(diǎn)
? ? * verts[5] : 右下頂點(diǎn)
? ? * verts[6] : 左下頂點(diǎn)
? ? * verts[7] : 左上頂點(diǎn)
? ? */
? ? void getCorners(Vec3 *dst) const;
? ? /**
? ? * 判斷兩個(gè)包圍盒是否重合
? ? */
? ? bool intersects(const AABB& aabb) const;
? ? /**
? ? * 判斷一個(gè)點(diǎn)是否在包圍盒內(nèi)
? ? */
? ? bool containPoint(const Vec3& point) const;
? ? /**
? ? 由兩個(gè)包圍盒生成一個(gè)能同時(shí)包圍這兩個(gè)包圍盒的最小包圍盒
? ? */
? ? void merge(const AABB& box);
? ? /**
? ? * 設(shè)置包圍盒的最大頂點(diǎn)與最小頂點(diǎn)
? ? */
? ? void set(const Vec3& min, const Vec3& max);
? ? /**
? ? * 復(fù)位函數(shù) 初始化最大最小頂點(diǎn)信息
? ? */
? ? void reset();
? ? bool isEmpty() const;
? ? /**
? ? * 更新最大頂點(diǎn)與最小頂點(diǎn)信息
? ? */
? ? void updateMinMax(const Vec3* point, ssize_t num);
? ? /**
? ? * 由一個(gè)矩陣對(duì)對(duì)包圍盒進(jìn)行頂點(diǎn)變換
? ? */
? ? void transform(const Mat4& mat);
public:
? ? Vec3 _min;? //三維向量 保存最小點(diǎn)坐標(biāo)
? ? Vec3 _max;? //三維向量 保存最大點(diǎn)坐標(biāo)
};
NS_CC_END
CCAABB.cpp 文件
#include "3d/CCAABB.h"
NS_CC_BEGIN
//構(gòu)造函數(shù)
AABB::AABB()
{
? ? reset(); //初始化最大頂點(diǎn)與最小頂點(diǎn)
}
AABB::AABB(const Vec3& min, const Vec3& max)
{
? ? set(min, max); //設(shè)置最大頂點(diǎn)與最小頂點(diǎn)
}
AABB::AABB(const AABB& box)
{
set(box._min,box._max); //設(shè)置最大頂點(diǎn)與最小頂點(diǎn)
}
//獲取包圍盒中心點(diǎn)坐標(biāo)
Vec3 AABB::getCenter()
{
? ? Vec3 center;
center.x = 0.5f*(_min.x+_max.x);
center.y = 0.5f*(_min.y+_max.y);
center.z = 0.5f*(_min.z+_max.z);
? ? return center;
}
//獲取包圍盒八個(gè)頂點(diǎn)信息
void AABB::getCorners(Vec3 *dst) const
{
? ? assert(dst);
? ? // 朝著Z軸正方向的面
? ? // 左上頂點(diǎn)坐標(biāo)
? ? dst[0].set(_min.x, _max.y, _max.z);
? ? // 左下頂點(diǎn)坐標(biāo)
? ? dst[1].set(_min.x, _min.y, _max.z);
? ? // 右下頂點(diǎn)坐標(biāo)
? ? dst[2].set(_max.x, _min.y, _max.z);
? ? // 右上頂點(diǎn)坐標(biāo)
? ? dst[3].set(_max.x, _max.y, _max.z);
? ? // 朝著Z軸負(fù)方向的面
? ? // 右上頂點(diǎn)坐標(biāo)
? ? dst[4].set(_max.x, _max.y, _min.z);
? ? // 右下頂點(diǎn)坐標(biāo)
? ? dst[5].set(_max.x, _min.y, _min.z);
? ? // 左下頂點(diǎn)坐標(biāo)
? ? dst[6].set(_min.x, _min.y, _min.z);
? ? // 左上頂點(diǎn)坐標(biāo)
? ? dst[7].set(_min.x, _max.y, _min.z);
}
//判斷兩個(gè)包圍盒是否碰撞
bool AABB::intersects(const AABB& aabb) const
{
? ? return ((_min.x >= aabb._min.x && _min.x <= aabb._max.x) || (aabb._min.x >= _min.x && aabb._min.x <= _max.x)) &&
? ? ? ? ? ((_min.y >= aabb._min.y && _min.y <= aabb._max.y) || (aabb._min.y >= _min.y && aabb._min.y <= _max.y)) &&
? ? ? ? ? ((_min.z >= aabb._min.z && _min.z <= aabb._max.z) || (aabb._min.z >= _min.z && aabb._min.z <= _max.z));
}
//判斷點(diǎn)和包圍盒是否碰撞
bool AABB::containPoint(const Vec3& point) const
{
if (point.x < _min.x) return false;
if (point.y < _min.y) return false;
if (point.z < _min.z) return false;
if (point.x > _max.x) return false;
if (point.y > _max.y) return false;
if (point.z > _max.z) return false;
return true;
}
//生成一個(gè)新的包圍盒 同時(shí)容納兩個(gè)包圍盒
void AABB::merge(const AABB& box)
{
? ? // 計(jì)算新的最小點(diǎn)坐標(biāo)
? ? _min.x = std::min(_min.x, box._min.x);
? ? _min.y = std::min(_min.y, box._min.y);
? ? _min.z = std::min(_min.z, box._min.z);
? ? // 計(jì)算新的最大點(diǎn)坐標(biāo)
? ? _max.x = std::max(_max.x, box._max.x);
? ? _max.y = std::max(_max.y, box._max.y);
? ? _max.z = std::max(_max.z, box._max.z);
}
//設(shè)置最大頂點(diǎn)與最小頂點(diǎn)
void AABB::set(const Vec3& min, const Vec3& max)
{
? ? this->_min = min;
? ? this->_max = max;
}
//頂點(diǎn)復(fù)位 初始化信息
void AABB::reset()
{
_min.set(99999.0f, 99999.0f, 99999.0f);
_max.set(-99999.0f, -99999.0f, -99999.0f);
}
//檢測(cè)坐標(biāo)信息是否有誤
bool AABB::isEmpty() const
{
? ? return _min.x > _max.x || _min.y > _max.y || _min.z > _max.z;
}
//由給定點(diǎn)坐標(biāo)點(diǎn)重新確定最大最小的坐標(biāo)向量
void AABB::updateMinMax(const Vec3* point, ssize_t num)
{
? ? for (ssize_t i = 0; i < num; i++)
? ? {
? ? ? ? // 最小x坐標(biāo)
? ? ? ? if (point[i].x < _min.x)
? ? ? ? ? ? _min.x = point[i].x;
? ? ? ? // 最小y坐標(biāo)
? ? ? ? if (point[i].y < _min.y)
? ? ? ? ? ? _min.y = point[i].y;
? ? ? ? // 最小z坐標(biāo)
? ? ? ? if (point[i].z < _min.z)
? ? ? ? ? ? _min.z = point[i].z;
? ? ? ? // 最大x坐標(biāo)
? ? ? ? if (point[i].x > _max.x)
? ? ? ? ? ? _max.x = point[i].x;
? ? ? ? // 最大y坐標(biāo)
? ? ? ? if (point[i].y > _max.y)
? ? ? ? ? ? _max.y = point[i].y;
? ? ? ? // 最大z坐標(biāo)
? ? ? ? if (point[i].z > _max.z)
? ? ? ? ? ? _max.z = point[i].z;
? ? }
}
//通過(guò)給定的變換矩陣對(duì)包圍盒進(jìn)行變換
void AABB::transform(const Mat4& mat)
{
? ? Vec3 corners[8]; //保存包圍盒八個(gè)頂點(diǎn)
? ? //朝向z軸正方向的面
? ? //左上頂點(diǎn)坐標(biāo)
? ? corners[0].set(_min.x, _max.y, _max.z);
? ? //左下頂點(diǎn)坐標(biāo)
? ? corners[1].set(_min.x, _min.y, _max.z);
? ? //右下頂點(diǎn)坐標(biāo)
? ? corners[2].set(_max.x, _min.y, _max.z);
? ? //右上頂點(diǎn)坐標(biāo)
? ? corners[3].set(_max.x, _max.y, _max.z);
? ? //朝向z軸負(fù)方向的面
? ? //右上頂點(diǎn)坐標(biāo)
? ? corners[4].set(_max.x, _max.y, _min.z);
? ? //右下頂點(diǎn)坐標(biāo)
? ? corners[5].set(_max.x, _min.y, _min.z);
? ? //左下頂點(diǎn)坐標(biāo)
? ? corners[6].set(_min.x, _min.y, _min.z);
? ? //左上頂點(diǎn)坐標(biāo)
? ? corners[7].set(_min.x, _max.y, _min.z);
? ? //頂點(diǎn)變換
? ? for (int i = 0; i < 8; i++)
? ? ? ? mat.transformPoint(&corners[i]);
? ? //復(fù)位最大頂點(diǎn)最小頂點(diǎn)
? ? reset();
? ? //重新計(jì)算最大最小點(diǎn)信息
? ? updateMinMax(corners, 8);
}
NS_CC_END
4. 總結(jié)
最后,AABB碰撞檢測(cè)算法雖然計(jì)算方法簡(jiǎn)單肖爵,速度快卢鹦,但是僅適用于精度不搞的游戲中。相對(duì)于AABB碰撞檢測(cè)劝堪,還有一種更逼近物體并更為精確的一種算法——OBB碰撞檢測(cè)冀自。在Cocos2d-x 中同樣提供了OBB碰撞檢測(cè)的相應(yīng)方法,如圖 4-1所示: