The length the curve monotonically increasing

482 Chapter 10 Interpolation

// make first guess
float p = u1 + s/len;

Computing the derivative of the curve is simple, as this is easily derived from the definition of the curve, as we did for clamped and natural splines. However, there is a serious problem if Length(Derivative(p)) is zero or near zero. This will lead to a division by zero and we will end up subtracting NaN from p, which will give us a garbage result.

The solution is to use an alternative root-finding technique known as bisection. It makes use of the mean value theorem, which states that if you have a function f(x) that’s continuous on [a, b] and f(a)f(b) < 0 (i.e., f(a) and f(b) have opposite signs), then there is some value p between a and b where f(p) = 0. This is definitely true in our case. The length of the curve is monotonically increasing, so there will be only one zero. If it’s not at the beginning, then f(a) = length(a) − s = −s, which is less than zero. If it’s not at the end, then f(b) = length(b) − s, which is greater than zero. Our endpoints have differing signs, so we can use the bisection method.

// ensure that we remain within valid parameter space

// get total length of curve

// done iterating, return last guess return p;
}

The only remaining question is how we determine to use bisection over Newton-Raphson. One obvious possibility is to check whether the speed is zero, as that got us into trouble in the first place. However, that’s not