Basic Primitive Tests - Real-Time Collision Detection - page 218

function taking an object and a time interval as arguments. As a result, it computes
the maximum length of the paths taken by points on the surface of the object during its
movement over the time interval. Furthermore, let MinimumObjectDistanceAtTime()
be a function taking two objects and a time value as arguments. Its function result
is the smallest distance between the surfaces of the objects at the given time. Given
these two functions, the generic implementation of the interval-halving method now
becomes:
// Test collision between objects a and b moving over the time interval
// [startTime, endTime]. When colliding, time of collision is returned in hitTime
int IntervalCollision(Object a, Object b, float startTime, float endTime, float &hitTime)
{
// Compute the maximum distance objects a and b move over the time interval
float maxMoveA = MaximumObjectMovementOverTime(a, startTime, endTime);
float maxMoveB = MaximumObjectMovementOverTime(b, startTime, endTime);
float maxMoveDistSum = maxMoveA + maxMoveB;
// Exit if distance between a and b at start larger than sum of max movements
float minDistStart = MinimumObjectDistanceAtTime(a, b, startTime);
if (minDistStart > maxMoveDistSum) return 0;
// Exit if distance between a and b at end larger than sum of max movements
float minDistEnd = MinimumObjectDistanceAtTime(a, b, endTime);
if (minDistEnd > maxMoveDistSum) return 0;
// Cannot rule collision out: recurse for more accurate testing. To terminate the
// recursion, collision is assumed when time interval becomes sufficiently small
if (endTime - startTime < INTERVAL_EPSILON) {
hitTime = startTime;
return 1;
}
// Recursively test first half of interval; return collision if detected
float midTime = (startTime + endTime) * 0.5f;
if (IntervalCollision(a, b, startTime, midTime, hitTime)) return 1;
// Recursively test second half of interval
return IntervalCollision(a, b, midTime, endTime, hitTime);
}
For convex polygonal objects, after having located the closest time just before initial
contact a subsequent separating-axis test can provide a collision normal to be used
for collision response (given by the separating axis itself). The separating-axis test can
also be used to determine the collision of moving convex objects directly, as explained
in the next section.