The ray/triangle intersection test is very expensive so, in the next three lectures, we'll look at methods to accelerate ray tracing.

These acceleration methods use subdivisions of space to reduce the number of triangles that are tested; the eliminated triangles are said to be culled.

The central idea is to subdivide 3D space into regions and to test whether the ray intersects a region. If the ray does not intersect a region, all triangles within that region are culled, saving a lot of ray/triangle intersection tests.

Another key idea is that the regions are arranged hierarchically. Each region is, itself, subdivided into smaller interior regions. If a ray intersects a region, then the next step is to check whether the ray intersects any of the ("child") interior regions.

This hierarchical ray/region test continues recursively until a region does not contain many triangles. Such a region is at the leaf of the hierarchy. Upon reaching such a leaf, all triangles inside that leaf region are tested exhaustively using the usual ray/triangle intersection test.

An axis-aligned bounding box, or AABB, is a box with axes that are aligned with the coordinate axes.

In 2D, an AABB is a rectangle with faces parallel to the $x$ and $y$ axes.

In 3D, an AABB is a rectangular prism, or "cuboid", with faces parallel to the $xy$, $yz$, and $xz$ planes.

AABBs are used to surround groups of primitives (e.g. spheres and triangles). Before testing ray intersection with any of the primitives in the group, the ray is tested for intersection with the AABB. If the ray does not intersect the AABB, it doesn't intersect any of the primitives, so those primitives don't have to be tested.

Below is a 2D AABB enclosing a set of triangles. Since the ray misses the AABB, it also misses all of the triangles. Note that the AABB tightly fits its enclosed triangles.

Thus, AABBs can accelerate ray tracing.

AABBs are often used hierarchically, as with the octtrees and k-d trees described below.

Intersecting a ray with an AABB is very efficient. Consider the 2D case below:

Since the ray is travelling in the positive $x$ direction and it starts to the left of $x_0$, we must test the intersection with the plane $x = x_0$. That plane can be written in the usual way as

$(1,0) \cdot (x,y) = x_0$

Substituting $P+tD$ for $(x,y)$ gives

$\begin{array}{l} (1,0) \cdot (P + t \; D) = x_0 \\ P_x + t \; D_x = x_0 \\ t = {\Large x_0 - P_x \over \Large D_x} \end{array}$

The value $y$ is then

$y = P_y + t \; D_y = P_y + {\Large x_0 - P_x \over \Large D_x} D_y$

In the diagram above, $y > y_1$, so there is no intersection with the $x_0$ face of the AABB.

The $y$ direction is similar: Since the ray is travelling in the negative $y$ direction and it starts above $y_1$, we must test the intersection with the plane $y = y_1$. The same derivation as above yields

$x = P_x + {\Large y_1 - P_y \over \Large D_y} D_x$

Since $x_0 \leq x \leq x_1$, the ray intersects the $y_1$ face of the AABB.

So ray/AABB intersection can be done very efficiently.