Due to preparing for a week of vacation, and then going on a week of vacation, and then recovering from a week of vacation, this blog has fallen from the wayside a bit. But I’m back, and I’ll try to wrap up this topic in a couple of postings.
When last we left our intrepid heroes, we were discussing Newton-Raphson root finding, how it’s used for reparameterizing a curve, and when it fails (namely when the speed on the curve approaches zero). The solution hinted at was the bisection method.
The bisection method is another root finding method. 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. they have opposite signs) then there is some value p between a and b where f(p) = 0. To find this point, we can use binary search.
This definitely applies 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.
Reparameterization code which uses the bisection method is as follows:
[cpp]
// FindParameterByDistance() - bisection version
float
IvBezier::FindParameterByDistance( float t1, float s )
{
// ensure that we remain within valid parameter space
if ( s >= ArcLength(t1, mTimes[mCount-1]) )
return mTimes[mCount-1];
if ( s <= 0.0f )
return t1;
// compute endpoints
float a = t1;
float b = mTimes[mCount-1];
for ( u_int i = 0; i < 32; ++i )
{
// compute midpoint
float p = (a + b)*0.5f;
// compute function value and test against zero
float func = ArcLength(t1, p) - s;
if ( ::IvAbs(func) < 1.0e-03f )
{
return p;
}
// perform bisection step
if ( func < 0.0f )
{
a = p;
}
else
{
b = p;
}
}
// done iterating, return failure case
return FLT_MAX;
} // End of IvBezier::FindParameterByDistance()
[/cpp]
So in some sense we've solved our problem. Given enough iterations, this code will converge even if the speed is zero. However, it won't converge very fast, so on average it will take more iterations than Newton-Raphson. The solution, hinted at before, is to combine the two: use Newton-Raphson whenever possible, and bisection when not. We'll cover that and wrap this topic up in the next update.
Hi Jim, it was nice meeting you at GDC.
I have run into a similar problem with our spline code. I wanted to take splines and drive a rigid body along it. Now there are two modes that I considered. The first is where a constraint is pushing the body along the spline according the original authored velocity.
The second, more interesting mode, is where the body can slide along the spline according to gravity, like a roller coaster. This works well until the spline has a point of zero velocity, because the constraint equations need a tangent vector. My solution? I decided to view this as a degeneracy and require that spline always have nonzero velocity. How nice!
Anyhow, I just found your blog and thought it was interesting that you ran into a similar problem.
Comment by Erin Catto — 5/30/2005 @ 3:10 am
Hi, Erin, good to hear from you! Yeah, I’m not really sure how the designers created a spline where the derivative of the length hit zero, but they managed it. The alternative, which I thought of as I was working on these postings, is that there was something wrong in the spline code that was producing a degeneracy. Still, probably better to handle the case robustly.
I’ve been working on a book review in my spare time for the past week, so I’ll relieve the suspense and get the final post up next week sometime.
Comment by Jim Van Verth — 5/30/2005 @ 3:30 pm