Collision Detection (Advanced Methods in Computer Graphics) Part 4

Sphere Intersection

Sphere intersection tests are relatively simpler than the tests required for other types of bounding volumes. Collision detection algorithms often use spheres as the first level of bounding volumes so that intersection tests could be quickly carried out. In such situations, more accurate computations using tighter bounding volumes are performed only if necessary. The condition for the intersection of a ray {p, m} with a sphere {c, r} can be easily obtained by substituting the ray’s parametric representation (see Eq. 9.22) into the sphere’s equation:

Since m is a unit vector, the above equation can be re-written as follows:

The above quadratic in t will have real roots only if

The above inequality gives the necessary condition for the intersection of the ray. Depending on the signs of the real roots of the equation (if the above condition is satisfied), we can classify the solution into four different categories:

•    Roots are equal and positive. The ray is tangential to the sphere.

•    Roots are unequal and positive. The ray intersects the sphere at two distinct points. The minimum value of t gives the point closest to the origin of the ray.

•    One root is positive and the other negative. The origin of the ray is inside the sphere.

•    Both roots are negative. The ray is directed away from the sphere and the points of intersection are behind the origin of the ray.

The last condition mentioned above can also be checked using a simple test. If m^(c — p) < 0, then the sphere is behind the ray.

A plane given by rm = —d intersects the sphere {c, r} if the distance of the centre of the sphere from the plane is less than the sphere’s radius r. Assuming that |n| = 1, the necessary condition for intersection is (see also Eq. 2.24)

Two spheres {c1, r1} and {c2, r2} intersect if and only if the distance between their centres is less than the sum of their radii:

k-DOP Intersection

We saw in Sect. 9.1.4 that a k-DOP can be represented by k/2 slabs {dminj, dmaxj, nj}, j = 0 ••• (k/2)—1, where njs are unit normal directions associated with the slabs. The slab-based intersection test outlined in Sect. 9.2.2 can be directly extended for a k-DOP as shown below. For a given ray {p, m}, the interval of intersection on each slab can be obtained using the following equations (see Eq. 9.32):

where wj = (dmaxj — dminj)/2. After computing the minimum and maximum values for all the slabs, the following values are obtained:

The ray intersects the k-DOP if and only if the intersection of the slab intervals is non-empty. The necessary and sufficient condition for intersection is Mmin < Mmax.

An overlap test involving a k-DOP and a plane can be implemented by first computing the vertices of the k-DOP and comparing them with the plane to determine if some of them are located either on the plane or on either sides of the plane. The vertex positions are obtained by taking three planes of the k-DOP at a time and computing their point of intersection using the method described in Sect. 2.4.

The complexity of intersection tests using only k-DOPs can be significantly reduced if they are all constructed using the same set of normal directions. Two such k-DOPs {dminj(1), dmaxjil\ nj}, {dmin/2), dmaxf-2\ nj}, j = 0 …(k/2)—1, overlap if and only if all corresponding pairs of intervals [dminj(1), dmaxj(1)], [dmin/2), dmaxj(2)] overlap. Thus, if the following condition is satisfied for any j, then the two k-DOPs do not overlap.

Triangle Intersection

Bounding volume hierarchies (detailed in the next section) have to facilitate overlap tests using not only bounding volumes but also primitives at the lowermost levels of the tree. Since triangles are the most widely used mesh primitives, we discuss below the intersection tests using triangles. A triangle T will be represented by its three vertices as {p1, p2, p3}. The unit normal vector of the plane of the triangle will be denoted by n. In the following, we assume that the triangle and the primitive it is tested against are both defined in a common reference frame.

The intersection of a ray {q, m} with the triangle T is computed by first checking if the ray intersects the plane of the triangle, and then determining if the point of intersection lies within the triangle. If the ray is not parallel to the plane of the triangle (m*n ^ 0), the intersection point is given by the value of the parameter t in Eq. 2.23. If t > 0, the ray intersects the plane of the triangle, and the point of intersection given by s = q C tm. If the three vector scalar triple products ((p2 — p1) x (s — p1))*m, ((p3 — p2) x (s — p2))*m and ((p — p3) x (s — p3))*m all have the same sign (see Eq. 2.10), then the point of intersection lies inside the triangle. If any of the cross product is zero, the intersection point lies on the boundary of the triangle. If it is not necessary to compute the actual point of intersection with the triangle, then the above test can be simplified into the condition that the values of ((p1 — q) x (p2 — q))*m, ((p2 — q) x p — q)>m, ((p — q) x (p — q)>m have the same sign for a valid intersection. We now deal with the case m*n = 0 separately. In this case, the ray must also lie on the plane of the triangle in order to possibly intersect it. The necessary condition for this is (q — p1)*n = 0. If the condition is satisfied, then we compare the ray with the edges of the triangle to determine the intersection points. As an example, we consider the intersection of the ray {q, m} with the line segment p1p2 (Fig. 9.15), assuming that both lines are coplanar. Let u = p2 — p1, and w = q — p1.

Fig. 9.15 Intersection of a ray with an edge of a triangle given by the line segment p1p2

If the ray intersects the line segment, then their projections on to any of the principal planes must also intersect. The intersection test can thus be reduced to a two-dimensional problem, by selecting only two coordinates for which both u and m are non-zero and non-coincident vectors. In this two-dimensional space, let u = (u1, u2), m = (m1, m2), and w = (w1, w2). Any point on the line segmentp1p2 is given in parametric form asp1 + su (0 < s < 1), and any point on the ray as q +1m. At a valid intersection point, we must havep1 + su = q +1m. This equation leads to the following two simultaneous linear equations in s and t:

from which we get

If the above values for s and t satisfy the conditions 0 < s < 1, t > 0, then the ray intersects the edge p1p2 of the triangle. The denominators in the above expressions become zero when the vectors u and m become parallel, in which case, the ray does not intersect the triangle.

Intersection tests with a triangle and a plane rm = —d can be performed as previously discussed in the context of AABB intersections, by computing the signed distances D, of the vertices of the triangle from the plane as D, = p^n + d, i = 1,2,3. If any of the signed distances is zero, or if any two distances have opposite signs, then the plane intersects the triangle.

We now consider the problem of computing the intersection of one triangle with another. Here, we assume that the triangles are on two different planes, and as previously done for the ray intersection test, we will deal with the intersection of two coplanar triangles separately. Let the two triangles be T1 = {p1, p2, p3}, and T2 = {q1, q2, q3}. The plane T1 containing the first triangle is given by r*n1 = —d1, where n1 is obtained by normalizing the vector (p2 — p1) x (p3 — p1), and d1 =-p1*n1. Similarly the plane T2 containing the second triangle is also obtained as r*n2 = —d2. We then use the procedure outlined in the previous paragraph to determine if the first triangle T1 is intersected by the plane T2, and if the second triangle T2 is intersected by the plane T1. If any of these tests fails, then the triangles do not intersect. Otherwise, the plane of each triangle intersects the other triangle as shown in Fig. 9.16. The line of intersection L of the planes also intersects both triangles.

Fig. 9.16 An example showing the configuration of two triangles where the plane containing one intersects the other

The two triangles overlap if the intervals of the triangles on the line L overlap. The equation of the line L is given by

where, v is a point on the line. To determine this point, we first select a component of n1 x n2 which is non-zero. If the x component of n1 x n2 is non-zero, we will be able to find a point v = (0, y, z) on L by solving the following two equations obtained from the fact that this point lies on both the planes.

Having obtained the parameters defining the equation of the line L, the next step is to find the points of intersection of the line with the triangles. Consider an edge of the triangle T2 that intersects the line L as shown in Fig. 9.17. Such an edge can be identified as having vertices that give opposite signs for signed distances with respect to the plane T1. Let the vertices be q,, qj, with D^, |Dj| denoting the magnitudes of the respective signed distances.

Fig. 9.17 Computation of the point of intersection of an edge of triangle T2 with the line L

The point of intersection w of the edge with the line L can be computed as follows:

The position of w corresponds to a value of the parameter t on the line L. This value can be obtained from Eq. 9.52, by substituting w for r, and choosing any component that has a non-zero value for n1 x n2. Similarly, we can obtain another value of the parameter t for the other edge of T2 that intersects L. Thus we have the interval [t1, t2] of the line segment on L obtained by its intersection with T2. Repeating the whole process for the triangle T1, and computing the signed distances of its vertices with respect to r2, we can find the interval [s1, s2] intersected by the triangle on L. If both intervals overlap, then the two triangles intersect.

Another approach to determining if the triangles overlap in three dimensions was recently proposed by Raabe et al. (2009). It uses the separating axis theorem (see Sect. 9.2.2), considering triangles as degenerate polytopes. If u1, u2, u3 and v1, v2, v3 denote the vectors along the sides of the two triangles (e.g., u1 = p2—p1) then 9 separating axes directions can be formed as l = u, x vj (i, j = 1, 2, 3). The vertices p, and q, are projected on to each separating axis l, and intervals [t1, t2], [s1, s2] computed as follows:

If the intervals do not overlap for any of the separating axes directions, then the triangles do not overlap. We now consider the problem of determining if two triangles on the same plane intersect. Here we can use a simplified version of the separating axis theorem. Two non-overlapping triangles lying on a common plane can be separated by a line parallel to one of the six sides. This means that if the triangles do not overlap, their vertices can be projected on to disjoint intervals on a line orthogonal to one of the sides (Fig. 9.18).

Fig. 9.18 The separating axis theorem applied to a pair of co-planar triangles

We need to consider only six separating axis directions given by u, x n and v, x n (i = 1,2,3). The vertices of each triangle are projected on to the separating axis vector, and the projected intervals for the triangles computed as outlined above (Eq. 9.55). If any of the interval pairs are disjoint, then the triangles do not overlap.