Rays

Ray-Shape Intersection Tests

Ray-Shape intersection tests determine whether rays intersect with a shape and where those intersections occur.

Ray-Triangle Intersection

The Möller-Trumbore Intersection Test [MollerT05]

See RayTriangleIntersection(), RayTrianglesIntersection(), RaysTrianglesIntersection().

The Möller-Trumbore test efficiently determines whether a ray, \(R(t) = O + tD\) with origin \(O\) and direction \(D\) intersects the triangle with \(V_0, V_1, V_2\). The test ultimately relies on determining whether the barycentric coordinates \((u,v)\) of the projection of the ray onto the plane of the triangle (\(T(u,v)\)) fall within the triangle (\(u,v \geq 0\) and \(u+v\leq 1\)), with checks along the way to ensure that only as much computation as is necessary is performed.

The intersection point (\(T(u,v)\)) between \(R(t)\) and the triangle is computed by solving \(R(t) = T(u,v)\) or

\[O + tD = (1-u-v)V_0+uV_1 + vV_2\]

The algorithm begins by computing the edge vectors \(E_1=V_1-V_0\) and \(E_2 = V_2 - V_0\) followed by the calculation of the determinant of the \(3\times3\) matrix

\[\begin{split}\det\left(\begin{bmatrix} r_0 & r_1 & r_2 \\ e_{2,0} & e_{2,1} & e_{2,2} \\ e_{1,0} & e_{1,1} & e_{1,2} \end{bmatrix} \right) = E_1 \cdot (R \times E_2) = det.\end{split}\]

If this determinant is zero, then the ray lies in the plane of the triangle and the test concludes that there is no intersection. The small parameter \(\epsilon\) is used to determine if the determinant is sufficiently near-zero, with \(\epsilon=10^{-6}\) used in the original paper. The barycentric coordinate \(u\) is first calculated and then checked for admissibility (\(0 < u < 1\)) followed by calculation of \(v\) and checking that \(0<v\) and \(u+v < 1\). Finally the parameter \(t\) of the intersection point can be calculated as

\[t_i=\frac{1}{det}(E_2 \cdot ((O-V_0) \times E_1))\]

For a unidirectional intersection test (only in the positive direction of \(R(t)\)), \(t\) must be positive. For a bidirectional test, the value of \(t\) is inconsequential for determining if the intersection occurs. The intersection point is then

\[R(t_i) = O + t_i D\]

Ray-Box Intersection

Williams et al. [WBMS05]

See RayBoxIntersection(), RayBoxesIntersection().

This test determines whether a ray, \(R(t) = O + tD = \begin{bmatrix}R_x & R_y & R_z \end{bmatrix}\) with origin \(O\) and direction \(D\) intersects an axis-aligned box with bounds \((x_{min},x_{max}),(y_{min},y_{max}),(z_{min},z_{max})\). The test works by finding the values of the parameter \(t\) that correspond to the points where the ray reaches each bound of the box. For example, \(t_{xmin} = (x_{min} - O_x)/R_x\), \(t_{xmax} = (x_{max} - O_x)/R_x\) correspond to the points where the ray crosses the lower and upper x axis bounds of the box. The order of these calculations is determined based on the sign of each component of the ray vector such that \(t_{xmin} \leq t_{xmax}\) (i.e. if \(R_x<0\), \(t_{xmin}=(x_{max} - O_x)/R_x\)).

For the ray to intersect the box, the limit-intersection parameters (\(t_{xmin}, t_{xmax}, t_{ymin},...\)) for each axis must be consistent with each other. If, for example, \(t_{ymin} > t_{xmax}\), that means that ray intersects with the first \(y\) bound of the box after it has crossed both \(x\) bounds and could not intersect with the box itself. If, instead, \(t_{xmin} \leq t_{ymax}\) and \(t_{ymin} \leq t_{xmax}\) then there may be an intersection and the test can proceed to checking the \(z\) limits. If \(\max{(t_{xmin},t_{ymin})} \leq t_{zmax}\) and \(t_{zmin} \leq \min{(t_{xmax},t_{ymax})}\), then there is a section of the ray that falls between the bounds of the box on all three axes, so the ray must intersect with the box.

Ray-Segment Intersection

See RaySegmentIntersection(), RaySegmentsIntersection()

The ray-segment intersection test checks whether a ray, \(R(t) = O + tD = \begin{bmatrix}R_x & R_y & R_z \end{bmatrix}\) with origin \(O\) and direction \(D\), intersects with a line segment, \(\bar{p_1 p_2}\).

First, to test of the ray is coplanar with the line segment, a test point along the ray can be obtained as \(p = O + (1)D\). To test if the four points \(p_1, p_2, O, p\) are coplanar, the scalar triple product of three vectors, \(\bar{a} = p_2 - p_1\), \(\bar{b} = p - O\), \(\bar{c} = O - p_1\) can be obtained. If the scalar triple product is 0 the points are coplanar, otherwise there is no intersection. (The scalar triple product can be interpreted as giving the volume of a parallelepiped defined by the vectors \(\bar{a}, \bar{b}, \bar{c}\)).

If the ray and line segment are coplanar, the parametric form of the line \(\bar{p_1 p_2}\) can be written as \(p1 + s \bar{a}\). The point of intersection in terms of the parametric terms \(s, t\) can be obtained as

\(s = \frac{(c \times b) \cdot (a \times b)}{(a \times b)^2}\) \(t = \frac{(c \times a) \cdot (a \times b)}{(a \times b)^2}\)

If \(0 \leq t\), the point of intersection is in the positive direction of the ray, and if \(s \in [0,1]\) then the point of intersection is on the line segment. If both conditions are met, the ray and segment intersect.

Plane-Shape Intersection Tests

Plane-Triangle Intersection

The plane-triangle intersection test checks whether a plane intersects with an triangle by calculating the signed distance between each vertex of the triangle and the plane. If all vertices of the triangle are on the same side of the plane, then there is no intersection.

The signed distance between a vertex \(v\) a plane defined by a point \(p\) and a normal vector \(\hat{n}\) is

Plane-Box Intersection

The plane-box intersection test checks whether a plane intersects with an axis-aligned box by calculating the signed distance between each vertex of the box and the plane. If all vertices of the box are on the same side of the plane, then there is no intersection.

The signed distance between a vertex \(v\) a plane defined by a point \(p\) and a normal vector \(\hat{n}\) is

\[d = \hat{n} \cdot v - \hat{n} \cdot p\]

Shape-Shape Intersection Tests

Triangle-Triangle Intersection

Triangle-Box Intersection

Segment-Segment Intersection

See SegmentSegmentIntersection(), SegmentsSegmentsIntersection()

The segment-segment intersection test works very similarly to the ray-segment intersection test. The key difference is that both parametric variables (\(s, t\)) must be in the interval \([0,1]\).

Point Inclusion Tests

Point in Boundary

See PointInBoundary()

To determine whether a point is contained within a closed boundary, the intersections between the boundary and an arbitrary coplanar infinite ray originating at the point can be counted. For a point inside the boundary, the ray will intersect the boundary an odd number of times, while if it’s outside the boundary it will intersect the ray an even number of times, regardless of how intricate the boundary is and how many intersections there are, as long as the boundary is closed and not self-intersecting. This is known as the even-odd rule or the parity rule [HA01].

Point in Surface

See PointInSurf()

To determine whether a point is contained within a closed surface, the intersections between the surface and an arbitrary infinite ray originating at the point can be counted. For a point inside the surface, the ray will intersect the surface an odd number of times, while if it’s outside the surface it will intersect the ray an even number of times, regardless of how intricate the surface is and how many intersections there are, as long as the surface is closed and not self-intersecting. This is known as the even-odd rule or the parity rule [HA01].