在 2D 游戏中经常会进行碰撞检测的逻辑,常用的方法是使用包围体来简化碰撞问题、优化计算速度。矩形是包围体常用的表现形式之一,而本篇的内容主要讲解矩形碰撞中的轴对齐包围盒的计算方法。

轴对齐包围盒(Axis-Aligned Bounding Box,AABB)是最广泛使用的包围体之一。在 2D 空间中,AABB 是一个包含四条边的矩形,且矩形表面的法向量皆平行于给定的坐标轴。

1. 表示方法

AABB 的表示方法很多,常用的方法有下面三种:

矩形表示方法

从左到右,第一种是两点法(最大值-最小值),可以用下面的代码表示:

struct AABB
{
	Point min;
	Point max;
};

第二种是最小值-宽高值:

struct AABB
{
	Point min;
	float w, h;
};

第三种是中心点-半径值:

struct AABB
{
	Point center;
	float rw, rh;
};

这三种表示方法,只要知道其中一种就可以推算出另两种的值。

2. 相交检测

对于 AABB 不同的表示方法,相交测试的代码同样不一样,但是其本质原理是相同的。以两点发表示的矩形为例:

int Test(AABB a, AABB b)
{
	if(a.max.x < b.min.x || a.min.x > b.max.x)
		return 0;
	if(a.max.y < b.min.y || a.min.y > b.max.y)
		return 0;
		
	return 1;
}

函数分别对 x 轴和 y 轴方向做了相交测试,如果相交函数返回 1,否则返回 0。

在某些情况下,除了需要检测是否相交之外,还需要获取相交所构成的矩形信息,包括矩形的位置以及矩形的宽高。获取相交矩形的方法非常简单,因为当两个矩形相交的时候,在同一个坐标轴方向,中心的两个点,正好代表着相交矩形的宽或者高:

相交矩形

具体的源码这里不写了,只需要对水平坐标的四个点和垂直坐标的四个点分别排序,取它们各自中间两个坐标组成的矩形就是相交矩形。

矩形碰撞演示程序

3. AABB 更新

AABB 并不是一直不变的,在物体坐标系下,物体的移动是不会改变 AABB 的坐标,但是如果在世界坐标系下,AABB 实际上会跟随物体的移动而移动。

在简单的 2D 游戏中,我们一般只是用一个坐标系,就是窗口坐标,这个坐标系可以看作是世界坐标系,因为所有的 2D 对象都是通过这个坐标系定位的。

AABB 可以跟随物体本身的移动而改变自身的坐标,这个并不是问题,真正的问题是当物体旋转的时候,原始的 AABB 就会有两种选择,一种是 AABB 跟随物体旋转,这样的 AABB 好处是包裹物体的姿态不变,比较紧凑,但是这种 AABB 本身已经变为了另一种有向包围盒(OBB)的情况了。另一种是随着物体的旋转,AABB 自身不断的改变大小,仍然保持着 AABB 自身的特性,但是这种 AABB 可能没有初始的 AABB 紧凑。

AABB 旋转

如上图所示,最左边是原始的 AABB,中间是 OBB,最右边两个是两种不同的更新策略。本节主要讨论最右边两种更新 AABB 的情况,OBB 这种情况以后再详细讨论。

当 AABB 旋转之后,实际上最简单的方法是图上的第三种,可以通过找到原始 AABB 的四个顶点来确认一个大致的旋转之后的 AABB 框,不过这个 AABB 冗余性较高,但是其有计算优势。另一种可以让 AABB 更紧凑的策略是扫描几何体所有的顶点,找出最小值和最大值,构造出新的 AABB 矩形。这种方法虽然构造出的 AABB 更加紧凑,但是效率上大打折扣。