HOME

TheInfoList



OR:

In
computer graphics Computer graphics deals with generating images and art with the aid of computers. Computer graphics is a core technology in digital photography, film, video games, digital art, cell phone and computer displays, and many specialized applications. ...
, the slab method is an
algorithm In mathematics and computer science, an algorithm () is a finite sequence of Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...
used to solve the ray-box intersection problem in case of an axis-aligned
bounding box In geometry, the minimum bounding box or smallest bounding box (also known as the minimum enclosing box or smallest enclosing box) for a point set in dimensions is the box with the smallest measure (area, volume, or hypervolume in higher dime ...
(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 A branch, also called a ramus in botany, is a stem that grows off from another stem, or when structures like veins in leaves are divided into smaller veins. History and etymology In Old English, there are numerous words for branch, includ ...
-free implementation, it is widely used in computer graphics applications.


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 Slab or SLAB may refer to: Physical materials * Concrete slab, a flat concrete plate used in construction * Stone slab, a flat stone used in construction * Slab (casting), a length of metal * Slab (geology), that portion of a tectonic plate that ...
, 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. 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 and therefore the two intersections of the ray with the two planes orthogonal to the i-th coordinate axis will be given by : \begin t_i^ &= \frac \\ t_i^ &= \frac . \end The close and far extrema of the segment within the i-th slab will be given by : \begin t_i^ &= \min \left\ \\ t_i^ &= \max \left\ \end and the intersection of all these segments is : \begin t^ &= \max_i \left\ \\ t^ &= \min_i \left\ . \end Such resulting segment will be inside the box, and therefore an intersection exists, only if t^ \le t^. The sign of t^ determines if the intersection happens ahead or behind the origin of the ray, which might be interesting in applications such as
ray casting Ray casting is the methodological basis for 3D CAD/CAM solid modeling and image rendering. It is essentially the same as ray tracing (graphics), ray tracing for computer graphics where virtual light rays are "cast" or "traced" on their path from th ...
, where only intersections in front of the camera are of interest. The two intersection points will therefore be given by : \begin \boldsymbol p^ &= \boldsymbol o + t^ \boldsymbol r \\ \boldsymbol p^ &= \boldsymbol o + t^ \boldsymbol r . \end While the equations above are well defined for
real-valued In mathematics, value may refer to several, strongly related notions. In general, a mathematical value may be any definite mathematical object. In elementary mathematics, this is most often a number – for example, a real number such as or an ...
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 In mathematics, the extended real number system is obtained from the real number system \R by adding two elements denoted +\infty and -\infty that are respectively greater and lower than every real number. This allows for treating the potential ...
arithmetic (such as the one implemented by
IEEE 754 The IEEE Standard for Floating-Point Arithmetic (IEEE 754) is a technical standard for floating-point arithmetic originally established in 1985 by the Institute of Electrical and Electronics Engineers (IEEE). The standard #Design rationale, add ...
) 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, which is undefined (in IEEE 754 it is represented by NaN). However, implementations of the
IEEE 754-2008 The Institute of Electrical and Electronics Engineers (IEEE) is an American 501(c)(3) public charity professional organization for electrical engineering, electronics engineering, and other related disciplines. The IEEE has a corporate office ...
and functionsFor example, and in
C99 C99 (previously C9X, formally ISO/IEC 9899:1999) is a past version of the C programming language open standard. It extends the previous version ( C90) with new features for the language and the standard library, and helps implementations mak ...
.
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.


References


Sources

* * * *


External links

* {{DEFAULTSORT:Slab method Computer graphics algorithms