
454 Chapter 8 Collision Detection
t
0
– h
t
first
t
0
t
1
t
1
t
0
+ h
t
1
b
n
f
Figure 8.22 Choices of next iterate based on backward differences, forward differences, and the
tangent line.
(a) This is the best of all possibilities. The iterate satisfies t
1
<t
first
and is a better
estimate of the root than what Newton’s method produced. Notice that G(t
1
)>0
and G
(t
1
)<0.
(b) The iterate exceeded the first time of contact but not the last time of contact,
so t
first
<t
1
<t
last
. Notice that G(t
0
+ h) < 0 and G(t
1
)<0. Bisection is applied
while the iterates produce negative G values. Once a positive value is reached, an-
other forward difference step is applied. This is a hybrid