Slab method: Difference between revisions

Revision as of 20:34, 5 August 2023

Latest revision as of 13:47, 23 April 2025

(8 intermediate revisions by 7 users not shown)

Line 1:

{{Short description|Ray-box intersection method}}

In [[computer graphics]], the '''slab method''' is an [[algorithm]] used to solve the ray-box intersection problem in case of an [[Axis-aligned object|axis-aligned]] [[bounding box]] (AABB), i.e. to determine the intersection points between a [[ray (geometry)|ray]] and the box. Due to its efficient nature, that can allow for a [[branch (computer science)|branch]]-free implementation, it is widely used in computer graphics applications.{{sfn|Shirley|Wald|Marrs|2021}}{{sfn|Majercik|Crassin|Shirley|MorganMcGuire|2018}}

== Algorithm ==

Line 10:

:<math>\boldsymbol p(t) = \boldsymbol o + t \boldsymbol r</math>.

Assuming that all intersections existsexist, i.e. <math>r_i \ne 0 \; \forall i</math>, solving for <math>t</math> gives

:<math>t = \frac{\boldsymbol p - \boldsymbol o}{\boldsymbol r}</math>

Line 50:

</math>

While the equations above are well defined for [[real number|real-valued]] variables only if <math>r_i \ne 0 \; \forall i</math>, i.e. if the ray is not parallel to any of the coordinate axes, the algorithm can be applied to an [[Extended real number line|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 <math>t = +\infty</math> or <math>t = -\infty</math>, and the algorithm will still work as expected. If the origin lies on a face of the bounding box, then for some <math>i</math> it will happen that <math>t_i = \frac{0}{0}</math>, which is undefined (in IEEE 754 it is represented by [[NaN]]). However, implementations of the [[IEEE 754-2008 revision|IEEE 754-2008]] <tt>{{mono|minNum</tt>}} and <tt>{{mono|maxNum</tt>}} functions<ref>For example, <tt>{{mono|fmin</tt>}} and <tt>{{mono|fmax</tt>}} in [[C99]].</ref> 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,{{sfn|IEEE Standards Committee|2008}} 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.{{sfn|Kay|Kajiya|1986|p=273}}

== References ==

Line 56:

== Sources ==

* {{cite book|authorsauthor=IEEE Standards Committee|title=IEEE standard for floating-point arithmetic: 754-2008|___location=Washington, DC|publisher=IEEE Computer Society|year=2008}}

* {{cite conference|last1=Kay|first1=Timothy L.|last2=Kajiya|first2=James T.|title=Ray tracing complex scenes|conference=ACM SIGGRAPH computer graphics|volume=20|number=4|year=1986|date=August 18-22, 1986|pppages=269-278269–278|___location=Dallas}}

* {{cite journal|first1=Alexander|last1=Majercik|first2=Cyril|last2=Crassin|first3=Peter|last3=Shirley|first4=Morgan|last4=McGuire|title=A Ray-Box Intersection Algorithm and Efficient Dynamic Voxel Rendering|journal=Journal of Computer Graphics Techniques (JCGT)|volume=7|number=3|pppages=66-8166–81|year=2018}}

* {{cite book|title=Ray Tracing Gems II|chapter=Ray Axis-Aligned Bounding Box Intersection|first1=Peter|last1=Shirley|first2=Ingo|last2=Wald|first3=Adam|last3=Marrs|publisher=Apress|___location=Berkeley, CA|year=2021}}

== External links ==

* {{cite web|last=Barnes|first=Travian|year=2022Tavian|date=27 July 2022|url=https://tavianator.com/2022/ray_box_boundary.html|title=Fast, Branchless Ray/Bounding Box Intersections, Part 3: Boundaries|archive-url=https://web.archive.org/web/20230722162519/https://tavianator.com/2022/ray_box_boundary.html|archive-date=2023-07-22|url-status=live}}

{{DEFAULTSORT:Slab method}}