Collision Detection (Advanced Methods in Computer Graphics) Part 3

Intersection Testing

The bounding volumes introduced in the previous section are often associated with methods that determine if two bounding volumes intersect. In this section, we will consider three different types of intersection tests using bounding volumes:

•    Intersection between a bounding volume and a ray. Such intersection tests are used in advanced ray tracing algorithms where bounding volumes are employed to minimize the computation of ray intersections.

•    Intersection between a bounding volume and a plane. Intersection testing of objects with planes is used in acceleration algorithms such as view frustum culling.

•    Intersection between two bounding volumes of the same type. Collision detection algorithms often require the testing of intersections between bounding volumes.

A ray can be represented by the pair {p, m}, wherep = (xp, yp, zp) denotes the origin of the ray, and m = (xm, ym, zm) a unit vector along the ray’s direction. In parametric form (see also Eq. 2.13), the ray is given by the following equations:

A plane always has a linear representation ax + by + cz + d = 0, where the vector n = (a, b, c) is along the direction of its normal vector. As shown in Eq. 2.22, the equivalent vector representation of a plane is rm = —d. If we assume that n is a unit normal vector, then the signed distance D of a point v to this plane is simply given by the expression v^n+ d (see Eq. 2.24).

The following sections discuss methods of testing whether a bounding volume with a given representation intersects these primitive geometrical elements.

AABB Intersection

We first consider the intersection of an AABB given by the parameter set {xmin, xmax, y min, ymax, zmin, zmax} with a ray {p, m} as in Eq. 9.22. A naive approach is to check if the ray intersects any of the six sides of the AABB. For example, one of the sides parallel to the xy-plane is given by the equation z = zmin. We first compute the value of t from Eq. 9.22 by substituting z = zmin, and then use this value to find (z) x and y. The value of t is denoted as tmin. The ray intersects this plane if and only if the following three conditions are simultaneously satisfied:

Fig. 9.11 AABB intervals along the principal axes, and a non-intersecting ray

Similarly, the ray can be tested against the other planes of the AABB. A moment’s thought will reveal that it is not always necessary to test all six planes for intersection with the ray. At most three sides of the AABB will be visible to the point p if the point is outside the box (which is usually the case). We can also make use of the axis-aligned nature of the sides to determine if the ray is directed away from the AABB and therefore would not intersect the volume (Fig. 9.11). If a ray satisfies any of the following six conditions, it will not intersect the AABB.

If none of the above conditions is true, then we can identify the three faces visible top by comparing its coordinates against the corresponding intervals of the AABB. As an example, if (xp > xmax) and (yp < ymin) and (zp > zmax), then the ray need be compared only with the planes x = xmax, y = ymin, and z = zmax.

Fig. 9.12 AABB-Plane intersection test using the projected distances along the normal vector

The testing of intersection of an AABB with a plane r*n = —d, |n| = 1, can be done by computing the signed distances of the vertices v,, i = 1..8, of the AABB with respect to the plane. If some vertices are on or above the plane, and some below the plane, then the plane intersects the AABB. In other words, if D, = v,*n C d is nonzero and has a positive value for all i, then the AABB is entirely above the plane; if D, is non-zero and has a negative value for all i, then the AABB is below the plane; otherwise the plane intersects the AABB. The amount of computation can be reduced by first determining the diagonal of the AABB that is closely aligned with the normal vector n, and then using only the two opposite endpoints of this diagonal to check if they are on either sides of the plane. Note that an AABB has only four principal diagonals, and the selection of the diagonal closest to n is done by using the dot-product between n and the unit vectors along the four diagonals.

Another AABB-plane intersection test (which will be extended to OBBs in the next section) uses the projection of diagonal vectors (vectors from the centre of the AABB to the vertices) on the normal vector n of the plane (Fig. 9.12). For this method, we use the representation of the AABB given by the centre c = (xmid, y^, zmid) and the three half-width extents xr, yr, zr. The largest projected distance by any vertex of the AABB on the unit normal vector n = (xn, yn, zn) is given by

The shortest distance of the centre from the plane is Dc = cm C d. The plane intersects the AABB if and only if

The overlap test using two AABBs can be easily performed taking advantage of their axis-aligned property. Since the respective axes are always parallel, two AABBs overlap only if their projected intervals (see Fig. 9.11) along each axis overlap. Thus, two AABBs represented asand

do not overlap if any of the following conditions is satisfied:

If the AABBs are represented using their midpoint and half-width extents as ly.1) v(1)  7(1) X(1) V(1)  7(1^ ix(2) y(2) 7(2) x(2) y(2) 7(2h    then the as    {Xmid , ymid , zmid >Xr ,yr , zr } and {Xmid , ymid , zmid ,xr ,yr , zr },    then the  overlap test can be suitably modified as follows. In this case, the requirement for bounding volume overlap is that the projected distance between the centres must be less than or equal to the sum of the corresponding half-width extents along each axis. Conversely, if any of the following conditions is satisfied, the two AABBs do not overlap.

Since an AABB is also an OBB, the intersection tests given in the next section can also be applied to an AABB.

OBB Intersection

If an OBB is given by the parameters {X, y, z, w1, w2, w3, e1, e2, e3}, the eight vertices of the bounding volume are given by

where c = (x, y, z). The six faces of the OBB have the following equations:

To test the intersection of a ray {p, m} (see Eq. 9.22) with the above OBB, a brute force algorithm would first identify the faces visible to the point p by taking the dot-product of m with the unit vectors e1, e2, e3. For example, the positive side of e1 is not in the direction of (and therefore will not intersect) the ray if any of the following two conditions is satisfied.

The point of intersection is obtained by the value of the ray parameter t by substituting the ray equation r = p C t m in the equations of the planes that are visible to the ray. The point of intersection is further checked if it is within the corresponding faces, with the help of their vertex coordinates.

A faster ray intersection test was introduced by Kay and Kajiya (1986) based on the representation of the OBB using three slabs, where each slab is bounded by a pair of planes given in Eq. 9.30. The parameter values ^, ti^for each slab (i = 1..3) are computed as shown in the example for i = 1 below:

After computing the minimum and maximum values for all three slabs, the following values are obtained:

The ray intersects the OBB if Mmin < Mmax. This condition means that the intersection of the three [tmin, tmax] intervals on the ray is non-zero. The twodimensional version of the above method is depicted using an intersecting and a non-intersecting ray in Fig. 9.13.

The testing of intersection of an OBB with a plane r*n = —d, |n| = 1, can be done exactly like the methods outlined for a AABB in the previous section. The first method computes the signed distances of the vertices v,, i = 1..8, of the OBB with respect to the plane, and if some vertices are found to be on or above the plane, while others below the plane, then it is concluded that the plane intersects the OBB.

Fig. 9.13 The intersection of rays with the slabs of an OBB

This method could be further simplified using only the two end-vertices of the principal diagonal that is closely aligned to n. We can also extend the method based on projected distances (Fig. 9.12) to OBBs. The longest projected distance on n generated by vectors from the centre of the OBB to its vertices is given by

The above quantity is then compared with the shortest distance of the centre c of the OBB from the plane given by Dc = c*n C d. As previously shown in the case of an AABB, the plane intersects the OBB if Dc < p.

A naive algorithm for overlap test between two OBBs would compare every edge of one OBB with every face of the other OBB. In total, such a method would require 12 x 6 x 2 = 144 edge-face intersection tests. The number of intersection tests can be considerably reduced if we use the separating axis theorem. The theorem states that if two OBBs do not overlap, then there exists a separating plane between them, and equivalently, the vertices of the OBBs project into disjoint intervals on any axis perpendicular to the separating plane. The direction perpendicular to the separating plane is called the separating axis direction. The theorem further states that the separating plane, if it exists, is parallel to either a face of one of the OBBs, or a plane formed by two edges, one from each OBB. The 15 possible directions for the separating axis are: e1(1), e2(1), e3(1), e1(2), e2(2), e3(2), e1(1) x e1(2), e1(1) x e2(2), e1(1) x e3(2), e2(1) x e1(2), e2(1) x e2(2), e2(1) x e3(2), e3(1) x e1(2), e3(1) x e2(2), e3(1) x e3(2).

Fig. 9.14 Computation of projected distances on a separating axis

We denote these directions by li (i = 1..15). Note that some of these vectors are not unit vectors.

In Fig. 9.14, r1 denotes a vector from the centre of the first OBB to one of its vertices that give the largest projection on the separating axis li. Let us momentarily assume that li is a unit vector. Then, the projected distance is given by pf1 = |r1 •i,- |. From Eq. 9.29, the eight possible values for r1 are ± w1e1 ± w2e2 ± w3e3. The maximum projected distance is obtained by taking the positive values for each projected component. Noting that w1, w2 and w3 are always positive, we can define

Similarly, for the second OBB we obtain pi(2> = |r2^l,j. In the following, we use superscripts in the summation to distinguish between parameters associated with the first and the second OBBs.

The projected distance of the line of centres onThe two OBBs are separated if, for some i,

The above inequality remains unchanged if we multiply both sides by a constant |lj. This means that the separating axis directions l, can be used in the above equations without converting them to unit vectors. From Fig. 9.14, we observe that the vector (c(2)— c(1)) represents the translation of OBB2 with respect to the coordinate frame of OBB1. We therefore denote this vector by T. Similarly, let

denote the rotational transformation of OBB2 relative to the coordinate frame of OBB1 . We can now represent all OBB axes directions relative to the coordinate system of OBB1 with the origin at its centre:

In this reference system, we can also writewhere

It can be seen that with the above selection of the reference frame, the expressions for D,, p(1), p(2) get highly simplified, reducing the number of operations needed to evaluate the inequality in Eq. 9.37. For example, when l, = e1(1) x e1(2), we get the following expressions for the projected distances:

The last expression given above is derived based on the fact that e1(2) x e2(2) = e3(2) and e1(2) x e3(2) = —e2(2). The complete set of expressions for the above quantities for the 15 possible choices of l, is given in Table 9.1.

Table 9.1 Formulae for computing projected distances of OBB radii and the line of centres for 15 separating axis directions