Graphics Reference
In-Depth Information
B
1
B
2
A
+
v
2
A
A
+
v
(a)
A
+
3
v
4
B
3
(b)
Figure 5.33
A few steps of determining the collision of a moving sphere against a stationary
object using an interval-halving method.
other objects. If there is no collision,
S
can clearly move unobstructed to its end
destination. However, if a collision is detected, halve the movement and recursively
test the first half in the same manner, and if no collision is detected during the first
half perform the same recursive test for the second half. If a collision has not been
ruled out before the movement becomes less than some preset minimum motion, a
collision can be assumed and the recursion is terminated.
Figure 5.33a illustrates the procedure of interval halving at the point where the
initial sphere encompassing the complete movement has been found colliding with
an object. At this point, the midpoint of the movement is computed, and a recursive
call is issued for each half of the movement of
S
. In the first recursive call, the sphere
B
1
bounding the motion of
S
from its starting point to the movement midpoint is
found not to be colliding with any object, and the recursion terminates with no
collision. The procedure continues with the second recursive call, finding that the
sphere
B
2
bounding the second half does intersect with an object. A new midpoint
of the current half-interval is computed, and the two halves of the interval are again
recursed over (Figure 5.33b). The sphere
B
3
bounding the half corresponding to the
first subinterval is also found colliding with an object, and thus again the movement
