Slab method
≈ 4 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
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.
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. A tridimensional AABB can be represented by two triples \boldsymbol l = (l_0, l_1, l_2) and \boldsymbol h = (h_0, h_1, h_2) denoting the low and high bounds of the box along each dimension. A point \boldsymbol p(t) = (p_0(t), p_1(t), p_2(t)) along a ray with origin \boldsymbol o = (o_0, o_1, o_2) and direction \boldsymbol r = (r_0, r_1, r_2) can be expressed in parametric form as \boldsymbol p(t) = \boldsymbol o + t \boldsymbol r . Assuming that all intersections exist, i.e. r_i \ne 0 \; \forall i , solving for t gives t = \frac{\boldsymbol p - \boldsymbol o}{\boldsymbol r} and therefore the two intersections of the ray with the two planes orthogonal to the i -th coordinate axis will be given by \begin{align} t_i^{\text{low}} &= \frac{l_i - o_i}{r_i} \\ t_i^{\text{high}} &= \frac{h_i - o_i}{r_i} . \end{align} The close and far extrema of the segment within the i -th slab will be given by \begin{align} 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{align} and the intersection of all these segments is \begin{align} t^{\text{close}} &= \max_i \left\{ t_i^{\text{close}} \right\} \\ t^{\text{far}} &= \min_i \left\{ t_i^{\text{far}} \right\} . \end{align} Such resulting segment will be inside the box, and therefore an intersection exists, only if t^{\text{close}} \le t^{\text{far}} . The sign of 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 \begin{align} \boldsymbol p^{\text{close}} &= \boldsymbol o + t^{\text{close}} \boldsymbol r \\ \boldsymbol p^{\text{far}} &= \boldsymbol o + t^{\text{far}} \boldsymbol r . \end{align} While the equations above are well defined for real-valued variables only if r_i \ne 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 t = +\infty or t = -\infty , and the algorithm will still work as expected. If the origin lies on a face of the bounding box, then for some i it will happen that t_i = \frac{0}{0} , which is undefined (in IEEE 754 it is represented by NaN). However, implementations of the IEEE 754-2008 and functions 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, 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.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1321078483 under CC BY-SA 4.0; modifications have been made.