码农干货系列【1】--方向包围盒(OBB)碰撞检测

http://www.cnblogs.com/iamzhanglei/archive/2012/06/07/2539751.html


最近一直在删文章，不是要关博洗手什么的，而是被删的文章没有达到“干货”的标准。干货的反义词是水货，比如我们经常吃的注水猪肉，它就是水货，非干货。什么是“干货”。？经过一番搜寻，标准的描述是：实用性比较强的，不含任何吹嘘水分，也没有虚假的成分，所以业内人士通常把这一类分享活动称之为“干货”。

文章是否是干货做如下几点要求：

必备条件：

1.整体样式风格整齐美观；

2.实用性比较强的，逻辑条理清晰；

3.独立性强，一篇文章只写一类东西；

4.码农看完就懂（或者有了search的方向），拿去就能用；

加精条件：

1.图文并茂；

2.在线演示；

3.示例代码下载；

从这篇开始我们的干货之旅~~~~~

简介

包围体是一个简单的几何空间，里面包含着复杂形状的物体。为物体添加包围体的目的是快速的进行碰撞检测或者进行精确的碰撞检测之前进行过滤（即当包围体碰撞，才进行精确碰撞检测和处理）。包围体类型包括球体、轴对齐包围盒（AABB）、有向包围盒（OBB）、8-DOP以及凸壳。如图1所示。

图1 依次是球体、AABB、OBB

可以看到图1是3D包围体，在2D包围体如图2所示：

图2 依次是球体、AABB、OBB

 

OBB

方向包围盒（Oriented bounding box），简称OBB。方向包围盒类似于AABB，但是具有方向性、可以旋转，AABB不能旋转。如图3所示。

图3 矩形和矩形投影检测的四条轴

要计算两个OBB是否碰撞，只需要计算他们在图3上的4个坐标轴上的投影是否有重叠，如果有，则两多边形有接触。这也可以扩展到任意多边形，如图4所示。

图4 矩形和三角形投影检测的五条轴

投影轴来自于多边形自身边的垂线。

判定方式：两个多边形在所有轴上的投影都发生重叠，则判定为碰撞；否则，没有发生碰撞。

OBB存在多种的表达方式，这里使用最常用的一种：一个中心点、2个矩形的边长、两个旋转轴（该轴垂直于多边形自身的边，用于投影计算）。代码如下所示：

(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))

然后基于这个数据结构，进行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的投影。

有了这些，就可以进行相交检测。由上面的判定方式，可以得出，两个矩形之间的碰撞检测需要判断四次（每个投影轴一次）。完整检测代码如下所示：

(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的中心点连线在坐标轴上的投影长度和两个矩形投影半径之和进行对比，如果半径之后都小于或者等于中心连线之后才判定为碰撞，否则判定为分离状态。

集成图形化测试接口

为了更加直观的测试OBB碰撞检测方法，使用Easeljs输出碰撞的状态。当两个矩形没有发生碰撞的时候，两矩形呈现蓝色；当两个矩形发生碰撞的时候，两矩形呈现红色。先引入相关的脚本库以及用于显示的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"> 

然后进行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();

以上代码定义了两个旋转的OBB包围盒，当他们发生碰撞则改变绘制的颜色，使其成为红色。运行代码，效果图5和6所示。

图5 未发生碰撞

图6 发生碰撞

这里是2D情况下的OBB碰撞检测，对于3D OBB碰撞检测，更为复杂。需要测试15个分离轴以确定OBB的相交状态，两个OBB的坐标轴各3个，以及垂直于每个轴的9个轴。除了坐标轴个数不一样，其相交测试思路和本文一致，本文不再探讨。

在线演示

更多干货敬请期待~~~~~