Slab method

In computer graphics, the slab method is an algorithm used to solve the ray-box intersection problem in case of an axis-aligned bounding box (AABB), i.e. to determine the intersection points between a ray and the box. Due to its efficient nature, that can allow for a branch-free implementation, it is widely used in computer graphics applications. ^{[1] [2]}

Algorithm

The idea behind the algorithm is to clip the ray with the planes containing the six faces of the box. Each pair of parallel planes defines a slab, and the volume contained in the box is the intersection of the three slabs. Therefore, the portion of ray within the box (if any, given that the ray effectively intersects the box) will be given by the intersection of the portions of ray within each of the three slabs. ^[3]

A tridimensional AABB can be represented by two triples ${\displaystyle {\boldsymbol {l}}=(l_{0},l_{1},l_{2})}$ and ${\displaystyle {\boldsymbol {h}}=(h_{0},h_{1},h_{2})}$ denoting the low and high bounds of the box along each dimension. A point ${\displaystyle {\boldsymbol {p}}(t)=(p_{0}(t),p_{1}(t),p_{2}(t))}$ along a ray with origin ${\displaystyle {\boldsymbol {o}}=(o_{0},o_{1},o_{2})}$ and direction ${\displaystyle {\boldsymbol {r}}=(r_{0},r_{1},r_{2})}$ can be expressed in parametric form as

${\displaystyle {\boldsymbol {p}}(t)={\boldsymbol {o}}+t{\boldsymbol {r}}}$.

Assuming that all intersections exist, i.e. ${\displaystyle r_{i}\neq 0\;\forall i}$, solving for ${\displaystyle t}$ gives

${\displaystyle t={\frac {{\boldsymbol {p}}-{\boldsymbol {o}}}{\boldsymbol {r}}}}$

and therefore the two intersections of the ray with the two planes orthogonal to the ${\displaystyle i}$-th coordinate axis will be given by

${\displaystyle {\begin{aligned}t_{i}^{\text{low}}&={\frac {l_{i}-o_{i}}{r_{i}}}\\t_{i}^{\text{high}}&={\frac {h_{i}-o_{i}}{r_{i}}}.\end{aligned}}}$

The close and far extrema of the segment within the ${\displaystyle i}$-th slab will be given by

${\displaystyle {\begin{aligned}t_{i}^{\text{close}}&=\min \left\{t_{i}^{\text{low}},t_{i}^{\text{high}}\right\}\\t_{i}^{\text{far}}&=\max \left\{t_{i}^{\text{low}},t_{i}^{\text{high}}\right\}\end{aligned}}}$

and the intersection of all these segments is

${\displaystyle {\begin{aligned}t^{\text{close}}&=\max _{i}\left\{t_{i}^{\text{close}}\right\}\\t^{\text{far}}&=\min _{i}\left\{t_{i}^{\text{far}}\right\}.\end{aligned}}}$

Such resulting segment will be inside the box, and therefore an intersection exists, only if ${\displaystyle t^{\text{close}}\leq t^{\text{far}}}$. ^[4] The sign of ${\displaystyle t^{\text{close}}}$ determines if the intersection happens ahead or behind the origin of the ray, which might be interesting in applications such as ray casting, where only intersections in front of the camera are of interest. The two intersection points will therefore be given by

${\displaystyle {\begin{aligned}{\boldsymbol {p}}^{\text{close}}&={\boldsymbol {o}}+t^{\text{close}}{\boldsymbol {r}}\\{\boldsymbol {p}}^{\text{far}}&={\boldsymbol {o}}+t^{\text{far}}{\boldsymbol {r}}.\end{aligned}}}$

While the equations above are well defined for real-valued variables only if ${\displaystyle r_{i}\neq 0\;\forall i}$, i.e. if the ray is not parallel to any of the coordinate axes, the algorithm can be applied to an extended real number arithmetic (such as the one implemented by IEEE 754) to handle rays parallel to an axis, as long as the origin of the ray itself does not lie on one of the faces of the bounding box. In such arithmetic, the intersections with the planes parallel to the ray will be given by ${\displaystyle t=+\infty }$ or ${\displaystyle t=-\infty }$, and the algorithm will still work as expected. If the origin lies on a face of the bounding box, then for some ${\displaystyle i}$ it will happen that ${\displaystyle t_{i}={\frac {0}{0}}}$, which is undefined (in IEEE 754 it is represented by NaN). However, implementations of the IEEE 754-2008 minNum and maxNum functions ^[5] will treat NaN as a missing value, and when comparing a well-defined value with a NaN they will always return the well-defined value, ^[6] and they will therefore be able to handle even such corner case. An alternative approach to handle corner cases is to avoid divisions by zero altogether, which can be achieved by replacing the inverse of zero with a large arbitrary constant number. ^[4]

References

1. Shirley, Wald & Marrs 2021.
2. Majercik et al. 2018.
3. Kay & Kajiya 1986, p. 272.
4. Kay & Kajiya 1986, p. 273.
5. For example, fmin and fmax in C99.
6. IEEE Standards Committee 2008.

Sources

• IEEE Standards Committee (2008). IEEE standard for floating-point arithmetic: 754-2008. Washington, DC: IEEE Computer Society.
• Kay, Timothy L.; Kajiya, James T. (1986). Ray tracing complex scenes. ACM SIGGRAPH computer graphics. Vol. 20. Dallas. pp. 269–278.
• Majercik, Alexander; Crassin, Cyril; Shirley, Peter; McGuire, Morgan (2018). "A Ray-Box Intersection Algorithm and Efficient Dynamic Voxel Rendering". Journal of Computer Graphics Techniques (JCGT). 7 (3): 66–81.
• Shirley, Peter; Wald, Ingo; Marrs, Adam (2021). "Ray Axis-Aligned Bounding Box Intersection". Ray Tracing Gems II. Berkeley, CA: Apress.

External links

• Barnes, Tavian (27 July 2022). "Fast, Branchless Ray/Bounding Box Intersections, Part 3: Boundaries". Archived from the original on 2023-07-22.