碼農(nóng)干貨系列【1】--方向包圍盒(OBB)碰撞檢測

2012-06-07 11:40 【當(dāng)耐特】閱讀(34133) 評論(23) 收藏舉報

干貨

最近一直在刪文章，不是要關(guān)博洗手什么的，而是被刪的文章沒有達(dá)到“干貨”的標(biāo)準(zhǔn)。干貨的反義詞是水貨，比如我們經(jīng)常吃的注水豬肉，它就是水貨，非干貨。什么是“干貨”。？經(jīng)過一番搜尋，標(biāo)準(zhǔn)的描述是：實用性比較強的，不含任何吹噓水分，也沒有虛假的成分，所以業(yè)內(nèi)人士通常把這一類分享活動稱之為“干貨”。

文章是否是干貨做如下幾點要求：

必備條件：

1.整體樣式風(fēng)格整齊美觀；

2.實用性比較強的，邏輯條理清晰；

3.獨立性強，一篇文章只寫一類東西；

4.碼農(nóng)看完就懂（或者有了search的方向），拿去就能用；

加精條件：

1.圖文并茂；

2.在線演示；

3.示例代碼下載；

從這篇開始我們的干貨之旅~~~~~

簡介

包圍體是一個簡單的幾何空間，里面包含著復(fù)雜形狀的物體。為物體添加包圍體的目的是快速的進(jìn)行碰撞檢測或者進(jìn)行精確的碰撞檢測之前進(jìn)行過濾（即當(dāng)包圍體碰撞，才進(jìn)行精確碰撞檢測和處理）。包圍體類型包括球體、軸對齊包圍盒（AABB）、有向包圍盒（OBB）、8-DOP以及凸殼。如圖1所示。

圖1 依次是球體、AABB、OBB

可以看到圖1是3D包圍體，在2D包圍體如圖2所示：

圖2 依次是球體、AABB、OBB

OBB

方向包圍盒（Oriented bounding box），簡稱OBB。方向包圍盒類似于AABB，但是具有方向性、可以旋轉(zhuǎn)，AABB不能旋轉(zhuǎn)。如圖3所示。

圖3 矩形和矩形投影檢測的四條軸

要計算兩個OBB是否碰撞，只需要計算他們在圖3上的4個坐標(biāo)軸上的投影是否有重疊，如果有，則兩多邊形有接觸。這也可以擴展到任意多邊形，如圖4所示。

圖4 矩形和三角形投影檢測的五條軸

投影軸來自于多邊形自身邊的垂線。

判定方式：兩個多邊形在所有軸上的投影都發(fā)生重疊，則判定為碰撞；否則，沒有發(fā)生碰撞。

OBB存在多種的表達(dá)方式，這里使用最常用的一種：一個中心點、2個矩形的邊長、兩個旋轉(zhuǎn)軸（該軸垂直于多邊形自身的邊，用于投影計算）。代碼如下所示：

(function (window) {

    var OBB = function (centerPoint, width, height, rotation) {

        this.centerPoint = centerPoint;
        this.extents = [width / 2, height / 2];
        this.axes = [new Vector2(Math.cos(rotation), Math.sin(rotation)), new Vector2(-1 * Math.sin(rotation), Math.cos(rotation))];

        this._width = width;
        this._height = height;
        this._rotation = rotation;
    }

    window.OBB = OBB;
})(window);

其所依賴的Vector2這個類如下所示：

(function (window) {
    Vector2 = function (x, y) {
        this.x = x || 0;
        this.y = y || 0;
    };

    Vector2.prototype = {
        sub: function (v) {
            return new Vector2(this.x - v.x, this.y - v.y)
        },
        dot: function (v) {
            return this.x * v.x + this.y * v.y;
        }
    };
    window.Vector2 = Vector2;
} (window))

然后基于這個數(shù)據(jù)結(jié)構(gòu)，進(jìn)行OBB之間的相交測試。為OBB擴展一個方法，即或者在任意軸上的投影半徑：

OBB.prototype = {
    getProjectionRadius: function (axis) {
        returnthis.extents[0] * Math.abs(axis.dot(this.axes[0])) + this.extents[1] * Math.abs(axis.dot(this.axes[1]));
    }
}

這里你可能需要讀者了解Vector2.dot的幾何意義：若b為單位矢量，則a與b的點積即為a在方向b的投影。

有了這些，就可以進(jìn)行相交檢測。由上面的判定方式，可以得出，兩個矩形之間的碰撞檢測需要判斷四次（每個投影軸一次）。完整檢測代碼如下所示：

(function (window) {

    var CollisionDetector = {

        detectorOBBvsOBB: function (OBB1, OBB2) {
            var nv = OBB1.centerPoint.sub(OBB2.centerPoint);
            var axisA1 = OBB1.axes[0];
            if (OBB1.getProjectionRadius(axisA1) + OBB2.getProjectionRadius(axisA1) <= Math.abs(nv.dot(axisA1))) return false;
            var axisA2 = OBB1.axes[1];
            if (OBB1.getProjectionRadius(axisA2) + OBB2.getProjectionRadius(axisA2) <= Math.abs(nv.dot(axisA2))) return false;
            var axisB1 = OBB2.axes[0];
            if (OBB1.getProjectionRadius(axisB1) + OBB2.getProjectionRadius(axisB1) <= Math.abs(nv.dot(axisB1))) return false;
            var axisB2 = OBB2.axes[1];
            if (OBB1.getProjectionRadius(axisB2) + OBB2.getProjectionRadius(axisB2) <= Math.abs(nv.dot(axisB2))) return false;
            return true;

        }
    }

    window.CollisionDetector = CollisionDetector;
})(window)

這里拿兩個OBB的中心點連線在坐標(biāo)軸上的投影長度和兩個矩形投影半徑之和進(jìn)行對比，如果半徑之后都小于或者等于中心連線之后才判定為碰撞，否則判定為分離狀態(tài)。

集成圖形化測試接口

為了更加直觀的測試OBB碰撞檢測方法，使用Easeljs輸出碰撞的狀態(tài)。當(dāng)兩個矩形沒有發(fā)生碰撞的時候，兩矩形呈現(xiàn)藍(lán)色；當(dāng)兩個矩形發(fā)生碰撞的時候，兩矩形呈現(xiàn)紅色。先引入相關(guān)的腳本庫以及用于顯示的canvas畫布：

<script src="Vector2.js" type="text/javascript"></script>
<script src="OBB.js" type="text/javascript"></script>
<script src="CollisionDetector.js" type="text/javascript"></script>
<script src="easel.js" type="text/javascript"></script>
<canvas id="testCanvas" width="980" height="580">

然后進(jìn)行OBB初始化以及碰撞檢測：

var OBB1, OBB1x = 100, OBB1y = 150, OBB1w = 30, OBB1h = 140, OBB1r = 30;
var OBB2, OBB2x = 100, OBB2y = 70, OBB2w = 40, OBB2h = 110, OBB2r = 40;
var canvas;
var stage;
var color;

function init() {

    canvas = document.getElementById("testCanvas");
    stage = new Stage(canvas);

    Ticker.addListener(window);
}
     
function tick() {
    stage.removeAllChildren();

    OBB1r += 2;
    OBB2r += 1;
    OBB1 = new OBB(new Vector2(OBB1x, OBB1y), OBB1w, OBB1h, OBB1r * Math.PI / 180);
    OBB2 = new OBB(new Vector2(OBB2x, OBB2y), OBB2w, OBB2h, OBB2r * Math.PI / 180);
    var r = CollisionDetector.detectorOBBvsOBB(OBB1, OBB2);

    color=r?"red":"#00F";
    OBB1 = new Container();
    stage.addChild(OBB1);
    OBB1.x = OBB1x;
    OBB1.y = OBB1y;
    var frame1 = new Shape();
    frame1.graphics.beginFill(color).drawRect(0, 0, OBB1w, OBB1h);
    frame1.rotation = OBB1r;
    frame1.regX = OBB1w / 2;
    frame1.regY = OBB1h / 2;
    OBB1.addChild(frame1);

    OBB2 = new Container();
    stage.addChild(OBB2);
    OBB2.x = OBB2x;
    OBB2.y = OBB2y;
    var frame2 = new Shape();
    frame2.graphics.beginFill(color).drawRect(0, 0, OBB2w, OBB2h);
    frame2.rotation = OBB2r;
    frame2.regX = OBB2w / 2;
    frame2.regY = OBB2h / 2;
    OBB2.addChild(frame2);

    stage.update();
}
init();

以上代碼定義了兩個旋轉(zhuǎn)的OBB包圍盒，當(dāng)他們發(fā)生碰撞則改變繪制的顏色，使其成為紅色。運行代碼，效果圖5和6所示。

圖5 未發(fā)生碰撞

圖6 發(fā)生碰撞

這里是2D情況下的OBB碰撞檢測，對于3D OBB碰撞檢測，更為復(fù)雜。需要測試15個分離軸以確定OBB的相交狀態(tài)，兩個OBB的坐標(biāo)軸各3個，以及垂直于每個軸的9個軸。除了坐標(biāo)軸個數(shù)不一樣，其相交測試思路和本文一致，本文不再探討。

在線演示

更多干貨敬請期待~~~~~

刷新頁面返回頂部

當(dāng)耐特

碼農(nóng)干貨系列【1】--方向包圍盒(OBB)碰撞檢測

干貨

簡介

可以看到圖1是3D包圍體，在2D包圍體如圖2所示：

OBB

集成圖形化測試接口

在線演示

About