1. 定义

AABB（axially aligned bounding box）轴对齐矩形边界框 ：

其边必须垂直于坐标轴，每一边都平行于一个坐标平面。
矩形边界框不一定都是立方体，它的长、宽、高可以彼此不同。

2. AABB 的表达方法

AABB 内的点满足下列不等式：

\begin{aligned} x_{min} \leqslant x \leqslant x_{max} \\ y_{min} \leqslant y \leqslant y_{max} \\ z_{min} \leqslant z \leqslant z_{max} \end{aligned}

其中最重要的两个点：

\begin{cases} \bold{p_{min}} = \begin{bmatrix} x_{min} & y_{min} & z_{min} \end{bmatrix} \\[2ex] \bold{p_{max}} = \begin{bmatrix} x_{max} & y_{max} & z_{max} \end{bmatrix} \end{cases}

中心点 $\bold{c}$ 为：

\bold{c} = \frac{1}{2} (\bold{p_{min}} + \bold{p_{max}})

尺寸向量 $\bold{s}$ ：从 $\bold{p_{min}}$ 指向 $\bold{p_{max}}$ 的向量，包含了矩形边界框的长、宽、高：

\bold{s} = \bold{p_{max}} - \bold{p_{min}}

半径向量 $\bold{r}$ ：从中心点 $\bold{c}$ 指向 $\bold{p_{max}}$ 的向量：

\begin{aligned} \bold{r} &= \bold{p_{max}} - \bold{c} \\[1.5ex] &= \frac{1}{2} \bold{s} \end{aligned}

明确定义一个 AABB 只需要 $\bold{p_{min}}$ ， $\bold{p_{max}}$ ， $\bold{c}$ ， $\bold{s}$ ， $\bold{r}$ 这 5 个向量中的两个（除了 $\bold{s}$ 和 $\bold{r}$ 不能配对外，它们中的任意两个都可配对）。

其中 $\bold{p_{min}}$ ， $\bold{p_{max}}$ 的使用频率远高于 $\bold{c}$ ， $\bold{s}$ ， $\bold{r}$ ，由 $\bold{p_{min}}$ 和 $\bold{p_{max}}$ 计算其余三个中的任意一个都是很容易的。

class AABB3
{
public:
    Vector3 min;
    Vector3 max;
};

3. 计算 AABB

计算一个顶点集合的 AABB ：

先将最小值和最大值设为“正负无穷大”或任何比实际中用到的数都大或小得多的数。
之后，遍历全部点，并扩展边界框直到它包含所有点为止。

先在 AABB 类中引入了两个辅助函数。

3.1 初始化 AABB

empty() 函数负责 “清空” AABB：

//---------------------------------------------------------------------------
// AABB3::empty
//
// 将值赋为 极大 / 极小值 以清空矩形边界框

void	 AABB3::empty() {
	const float kBigNumber = 1e37f;
	min.x = min.y = min.z = kBigNumber;
	max.x = max.y = max.z = -kBigNumber;
}

3.2 向 AABB 添加 “点”

add(const Vector3& p) 函数将单个点“加”到 AABB 中，并在必要的时候扩展 AABB 以包含每个点：

//---------------------------------------------------------------------------
// AABB3::add
//
// 向矩形边界框中加一个点

void AABB3::add(const Vector3& p) {

	// 必要的时候扩张矩形边界框以包含这个点

	if (p.x < min.x) min.x = p.x;
	if (p.x > max.x) max.x = p.x;
	if (p.y < min.x) min.y = p.y;
	if (p.y > max.x) max.y = p.y;
	if (p.z < min.x) min.z = p.z;
	if (p.z > max.x) max.z = p.z;
}

3.3 从点集中计算其 AABB


AABB3 genAABB3(const int n, const Vector3 points[n])
{
    // 首先，初始化一个矩形边界框
    AABB3 box;
    box.empty();

    // 将点添加到矩形边界框中
    for(int i = 0 ; i < n ; ++i)
    {
        box.add(points[i]);
    }

    return box;
}

镜之国的爱丽丝

03 - 三维AABB类