Graphics Reference
In-Depth Information
interval is recursed over. In this example, the recursion eventually terminates with
an intersection. Interval halving for the case of a moving sphere against a stationary
sphere can be implemented as follows.
// Intersect sphere s0 moving in direction d over time interval t0 <= t <= t1, against
// a stationary sphere s1. If found intersecting, return time t of collision
int TestMovingSphereSphere(Sphere s0, Vector d, float t0, float t1, Sphere s1, float &t)
{
// Compute sphere bounding motion of s0 during time interval from t0 to t1
Sphere b;
float mid = (t0 + t1) * 0.5f;
b.c=s0.c+d*mid;
b.r = (mid - t0) * Length(d) + s0.r;
// If bounding sphere not overlapping s1, then no collision in this interval
if (!TestSphereSphere(b, s1)) 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 (t1 - t0 < INTERVAL_EPSILON) {
t = t0;
return 1;
}
// Recursively test first half of interval; return collision if detected
if (TestMovingSphereSphere(s0, d, t0, mid, s1, t)) return 1;
// Recursively test second half of interval
return TestMovingSphereSphere(s0, d, mid, t1, s1, t);
}
In general, this algorithm will terminate in
O
(log
n
) time. However, there are cases
in which it will not. One worst-case scenario for this algorithm occurs when the sphere
is moving parallel to a surface, just slightly farther away from it than the preset distance
used to terminate the recursion. In this instance, both subintervals are recursed over at
each step of the algorithm, causing the sphere movement to be subdivided in many
small steps, with each step being tested for collision. A tighter bounding volume,
such as an OBB, would exhibit better behavior in this situation. OBBs, however, can
be quite expensive. In some scenes, architectural scenes in particular, an AABB may
serve as a good substitute, as it aligns well with floors and walls, which tend to be
aligned at 90 degrees to each other as well as being aligned to the world coordinate
system.
The interval-halving method trivially adapts to handling complex objects with
both objects under arbitrary motion. Let
MaximumObjectMovementOverTime()
be a
