Linear Feature Collisions

This set of collision tests have in common the need to process linear features; a line, ray, or line segment are part of their solutions.

Point-to-Line/Ray

Although not strictly a collision test, finding the closest point on a line is useful for many other collision tests, such as determining nearby objects or for object selection. As we shall see, it also introduces the concept of Vector Projection, which is the foundation for the series of collisions of linear features as well as many other types.

Given: Line and Test Point

Line point = Ppt

Ray direction vector = N

Test point = Tpt

The first step is to create a vector from P point to the test point:

V = Tpt – Ppt

See Figure 16.10.

Figure 16.10: Closest point on a line.

The main technique in this test is the next step. Called vector projection, we will build a new vector that is equal to the projection of vector V onto the vector N. The approach we will take is to require that the line direction vector N be normalized prior to performing vector projection. This routine could normalize N, but in some cases this may be a waste of time when the line direction vector is already normalized.

In any case, N must be known to be unit-length to continue. If and when it is, then compute the vector projection of V onto N.

Let d = the dot product of vectors N and V, then scale vector N by d to create vector N'. It can be written as the following formula:

Vector Projection: N' = N(N dot V))

Finally, add the new vector N' to the line point P to find a test point projected onto the line, or the closest point to Tpt on the line.

Closest Point to Tpt = Ppt + N'

Line/Ray-to-Sphere

Ray-to-sphere, as well as the remaining linear feature collisions in this section, are simply modifications of the closest point on a line technique. Refer back to that test for more details.

Given: Line/Ray and Sphere

Line point = Ppt

Ray direction vector = N

Sphere center point = Cpt

Sphere radius = r

See Figure 16.11.

Figure 16.11: Ray-to-sphere collision.

First, create the vector from point P to the sphere center point.

V = Cpt – Ppt

Next, compute the vector projection of V onto N as defined in Point-to-Line/Ray.

Let d = the dot product of vectors N and V, then scale vector N by d to create N'.

The difference between computing ray-to-sphere and line-to-sphere lies in this step.

Because d is the scalar projection of V along N, if d is negative, that means that the sphere is behind the line point Ppt with respect to the direction vector N. In that case, the ray would not collide with the sphere, so a quick check of d < 0 before continuing can reject failed ray collision. Otherwise, the sphere is in front of the ray and still can be a possible collision, and the rest of the test will need to be completed.

For a line, no extra test is needed, because by definition a line is meant to go on to infinity in both directions.

For Ray

d = N dot V

if (d < 0) // if d is negative no collision

{ return false; }

else N' = (N)d; // scale N by d

For Line

Vector Projection: N' = N(N dot V))

Now, add the vector N' to point P to find the sphere center projected onto the line and call it ProjPt.

ProjPt = Ppt + N'

Finally, compute the distance between point ProjPt and sphere center Cpt and compare it to the sphere radius. If the distance is less than the radius, there is collision. As with sphere-to-sphere collision, the distance squared can be computed and compared to the radius square as an optimization.

if ( distance( ProjPt, Cpt ) < r ) { return true; } //collision

Alternate:

if ( distanceSquared( ProjPt, Cpt ) < r*r ) { return true; } //alternate test using more efficient distance squared.

Point-to-Cylinder

Point-to-cylinder is nearly the same as the previous test, with the exception that cylinder has a base point and length. Unlike the line/ray, this means that the body of the cylinder is a line segment, and the base and length must be tested for rejecting projected points beyond those points on the line.

Given Cylinder and Test Point:

Cylinder base point = Bpt

     Cylinder normal = N

     Cylinder radius = r

     Cylinder length = L

     Test point = Tpt

See Figure 16.12.

Figure 16.12: Point-to-cylinder collision.

First, create the vector from base point to the test point:

V = Tpt – Bpt

Next, let d = the dot product of vectors N and V, and compare d against 0 and the cylinder length to determine if the test point falls within the bottom and top of the cylinder. When N is normalized, as was required for these algorithms in the beginning of this section, the value of d is equal to the distance along vector N of vector V’s projection. Because of this fact, d can be used to compare against the cylinder length for rejecting test points beyond the end of the cylinder.

d = N dot V : if ( d < 0 || d > L ) { return false; } //no collision

If we make it this far, then scale N by d. (This completes the vector projection of V onto N, N'=N(N dot V).)

N' = D(N)

Now, add the new vector N' to the base point to find a test point projected onto the cylinder (closest point on line):

ProjPt = Bpt + N'

Finally, compute the distance between point ProjPt and the test point Tpt and compare it to the cylinder radius. If the distance is less than the radius, there is collision. As with sphere-to-sphere collision, the distance squared can be computed and compared to the radius square as an optimization.

if ( Distance( ProjPt, Tpt ) < r ) { return true; } //collision

Alternate:

if ( distanceSquared( ProjPt, Tpt ) < r*r ) { return true;} //alternate test using more efficient distance squared.

Sphere-to-Cylinder

Sphere-to-cylinder is the same as point-to-cylinder with two exceptions. First, when testing for the end of the cylinder, the sphere radius must be concerned. Second, the final distance is modified to test between two spheres.

Given Cylinder and Sphere:

     Cylinder base point = Bpt

     Cylinder normal = N

     Cylinder radius = rC

     Cylinder length = L

     Sphere center point = Cpt

     Sphere radius = rS

See Figure 16.13.

Figure 16.13: Sphere-to-cylinder collision.

First, create the vector from the base point to the test point:

V = Tpt – Bpt

Next, let d = the dot product of vectors N and V and compare d against 0–rC and length+rC to determine if the test point falls within the bottom and top of the cylinder. By using 0–rC and length+rC we are extending the cylinder in both directions to account for the spheres radius. When the test sphere is near the ends of the cylinder it would fail to produce collisions when the center point was past the ends of the cylinder without this extra step.

d = N dot V : if ( d < –rC || d > L+rC ) { return false; } // no collision

If d passes the previous test, then scale N by d. (This completes the vector projection of V onto N, N'=N(N dot V).)

N' = D(N)

Now, add the new N' to the base point to find a test point projected onto the cylinder (closest point on line):

ProjPt = Bpt + N'

Compute distance between ProjPt and Cpt and compare it to the sum of the radii:

if ( Distance( ProjPt, Cpt ) < ( rC + rS ) ) { return true } // collision

Finally, compute the distance between point ProjPt and the sphere center point Cpt and compare it to the sum of the cylinder radius and the sphere radius. If the distance is less than that sum, there is collision. As with sphere-to-sphere collision, the distance squared can be computed and compared to the radius squared as an optimization.

if ( Distance( ProjPt, Cpt ) < rC+rS ) { return true; } // collision

Alternate:

if ( distanceSquared( ProjPt, Cpt ) < (rC+rS)2 ) { return true; } // alternate test using more efficient distance squared.

Ray-to-AABB

Given: Ray and AABB:

Line point = Ppt

Ray direction vector = N

Box min point = Min

Box max point = Max

Box center = Cpt

Box radius vector = R (Max – Cpt)

See Figure 16.14.

Figure 16.14: Ray-to-AABB collision. Frames 1 and 2 show a miss, frames 3 and 4 a hit.

This test introduces the idea of a separating axis to our collision detection test.

The idea is to define a vector that represents an axis that separates the ray from the AABB. The final test will be whether the distance from the ray to AABB is greater than the box’s “radius.” Vector projection will be used similarly to the ray- to-sphere test.

First, create the vector from the line point Ppt to the box’s center point:

V = Cpt – Ppt

Next, compute the vector projection of V onto N as defined in Point-to-Line/Ray.

Let d = the dot product of vectors N and V, then scale vector N by d to create N'.

To create the separating axis vector, simply subtract V from N':

S = N' – V

The two distances to compare are the length of S and the length of the box’s radius projected onto S, which is defined as R dot S if S were normalized. We could do it this way, but it would be more optimized to recognize that we don’t need the actual distances because relative distances work similarly to the square distance optimization of sphere collision. In this case, the dot product alone gives us the solution.

if ( (S dot S) < ( R dot S ) { return true; } // collision

This works also because no matter how the ray is oriented to the AABB, the AABB’s radius as defined always produces the correct dot/distance for testing, even though it probably won’t be pointing toward the ray as shown in the figure.