
8.2 Finding Collisions between Moving O b jects 449
G
t
k
t
k + 1
t
first
Figure 8.21 Newton’s method to locate the first root of G(t).
sequence must converge to a limit. In our case, that limit is the root. From a numer ical
perspective, what is important is how many iterations must be computed to obtain
a root estimate t
k
that is acceptable for the application. Collision detection needs to
be fast, so the fewer the iterates the better. Collision detection needs to be accurate,
which might require more iterates. A reasonable system needs to balance speed with
accuracy, so the decision of when to stop iterating is important. Ideally, we would
like |t
k
− t
first ...