Cocos2d-x教程(33)－三維物體AABB碰撞檢測(cè)算法

出處 :http://blog.csdn.net/u012945598/article/details/39524343

在Cocos2d-x 3.x版本添加了對(duì)3D物體的支持后，3D物體的碰撞檢測(cè)方法也隨之更新，其中一種最簡(jiǎn)單的碰撞檢測(cè)方法就是AABB碰撞檢測(cè)。

1. AABB包圍盒

? ? ? ? 在游戲中，為了簡(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所示：


?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書(shū)系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

  • 深入理解傅里葉變換Mar 12, 2017 這原本是我在知乎上對(duì)傅立葉變換、拉普拉斯變換、Z變換的聯(lián)系？為什么要進(jìn)...
    價(jià)值趨勢(shì)技術(shù)派閱讀 5,935評(píng)論 2贊 2
  • 這是侑虎科技第239篇原創(chuàng)文章，感謝作者馮委供稿，歡迎轉(zhuǎn)發(fā)分享，未經(jīng)作者授權(quán)請(qǐng)勿轉(zhuǎn)載。當(dāng)然，如果您有任何獨(dú)到的見(jiàn)解...
    瑪瑪哈哈m閱讀 3,934評(píng)論 2贊 3
  • 在頂點(diǎn)著色器處理圖元頂點(diǎn)之后進(jìn)入圖元裝配階段。這一階段，執(zhí)行裁剪、透視分割和Viewport變換操作。 光柵化是將...
    cain_huang閱讀 5,527評(píng)論 0贊 4
  • 以前一直做持續(xù)發(fā)布使用xcbuild和xctool這些工作進(jìn)行打包，但是經(jīng)常遇到證書(shū)相關(guān)的問(wèn)題，各種Provisi...
    炸雞叔閱讀 8,464評(píng)論 12贊 53
  • 一 我出生地叫由來(lái)村，這個(gè)村子里到處是擁有奇妙能力的人，比如說(shuō)會(huì)噴火、會(huì)呼風(fēng)喚雨和可以預(yù)見(jiàn)未來(lái)的人。我們被稱為異人...
    人造月球閱讀 898評(píng)論 11贊 19

友情鏈接更多精彩內(nèi)容