= Axis-aligned bounding box
{title2=$B=\prod_{i=1}^{d}[m_i,M_i]$}
= AABB
{c}
{synonym}
An <axis-aligned bounding box> is a <Cartesian product> of <closed intervals> aligned with a chosen <Cartesian coordinate system>:
$$
B=\prod_{i=1}^{d}[m_i,M_i],\qquad m_i\leq M_i.
$$
Only the two opposite corners $(m_1,\ldots,m_d)$ and $(M_1,\ldots,M_d)$ need to be stored. In two dimensions it is a <rectangle>. Changing the <Cartesian coordinate system> can change how tightly the <axis-aligned bounding box> fits the same object.<Physically Based Rendering: From Theory to Implementation (4th edition) by Matt Pharr and others/3.7 Bounding Boxes>[§3.7, two-point representation and Figure 3.9]{ref}
For a nonempty <finite set> of <points> $P$, the smallest such <axis-aligned bounding box> has
$$
m_i=\min_{p\in P}p_i,\qquad M_i=\max_{p\in P}p_i.
$$
These <minimum> and <maximum> values also enclose the <convex hull> of $P$: each <coordinate> of a <convex combination> lies between the smallest and largest input <coordinates>. In particular, three <vertices of a polygon> determine the <axis-aligned bounding box> of a filled <triangle>. For a general nonempty <compact set>, the same formulas use all its <points>; inspecting only an arbitrary finite sample is insufficient.
Given nonempty boxes $B=\prod_i[m_i,M_i]$ and $C=\prod_i[n_i,N_i]$, the <closed interval> convention gives
$$
B\cap C\ne\varnothing\quad\Longleftrightarrow\quad
\max(m_i,n_i)\leq\min(M_i,N_i)\quad\text{for every }i.
$$
Equivalently, reject as soon as $M_i<n_i$ or $N_i<m_i$ in any <coordinate>. The surviving <set intersection> has endpoints $\max(m_i,n_i)$ and $\min(M_i,N_i)$. This is an exact box test, while its conclusion about enclosed objects remains a <conservative enclosure test>.<Physically Based Rendering: From Theory to Implementation (4th edition) by Matt Pharr and others/3.7 Bounding Boxes>[§3.7, Intersect() and Overlaps(): coordinate-wise intersection and inclusive comparisons]{ref}
Equality counts as touching: $[0,1]\times[0,1]$ and $[1,2]\times[0,1]$ share an edge, so their <set intersection> is nonempty. Replacing every $\leq$ in the overlap formula by $<$ tests intersection of the <interiors> of full-dimensional boxes and excludes this contact. A zero-width <closed interval> can represent a <point> or a lower-dimensional enclosure, and must not automatically be discarded when touching counts. A box with some $m_i>M_i$ is empty; test emptiness before applying rules intended for nonempty boxes. The <broad phase> must retain touching candidates whenever the <narrow phase> counts touching as a hit.
For nonempty boxes, the smallest enclosing <axis-aligned bounding box> of their <set union> is
$$
\prod_{i=1}^{d}\bigl[\min(m_i,n_i),\max(M_i,N_i)\bigr].
$$
This operation supplies the parent boxes in a <bounding volume hierarchy>. It is an enclosure of the <set union>, rather than generally the <set union> itself. In <floating-point arithmetic>, comparisons are conclusive only for endpoints that still enclose the intended exact objects; use certified bounds such as <interval arithmetic> with <outward rounding> when that guarantee is required.
// Target: analysis.bigb
Back to article page
