Hi all,

I've built an algorithm that displays a B-Spline. I'm not sure if it is working correctly. For example, take this picture:

the red points are the control points and the blue points are the various points on the curve. Each blue point is calculated through a fixed timestep. The Knot vector of this (clamped) curve is [0 0 0 0 0.5 1 1 1 1] and it is calculated using DeBoor's function in the interval [alpha, 1-alpha]. In this clamped case the first and last control points are added back at the end (though there might be some issues with the control points being drawn at their top left corner instead of their center, but it shouldn't matter).

As you can notice, the points towards the first and last control point appear to be more "sparse". I would explain this by it being due to the other control points concentrating the curve in the upper part as the number of points to calculate is constant (100, with alpha incrementing by 0.01).

Are there better ways to sample the curve in order to have a constant displacement between curve segments?

What you want is "constant arc length" or "constant speed and acceleration". On a spline (in general), points are not spaced equidistantly in respect to the parameter, and the arc length in relation to the parameter is not easily calculated (or guessed). Not in a closed form anyway, you can sum up line segments and subdivide recursively until you're below a chosen threshold, but it's not a nice and easy thing.

However, since the spacing depends on the second derivative (points are closer together the higher the curvature), you can get the desired result "backwards" by making the spline C2-continuous (which is possible and relatively easy with a B-Spline, other than with most other spline types). Your sample points will then automatically be equally spaced. The curve that you show is C1 but not C2 continuous (it interpolates or rather approximates "smoothly" (tangents fit together) but the tangents change "non smoothly" in a very obvious manner).

Of course the resulting curve will look radically different from the one you have now. If that is non-agreeable, you can do an estimate on local curvature and modify the step of the t-parameter accordingly. Which is kind of a hack, but may work just good enough.

Thanks for the reply. So how would I go about ensuring C2 continuity? I implemented this algorithm to compute the derivative. However at the moment I haven't Matlab handy so I need to check whether it really works. Assuming that it does, I should be able to recursively obtain the second derivative. How can I use this information to obtain C2 continuity?

I googled a bit using the terms you suggested, but so far I've only landed on research papers suggesting ways to calculate this arc length using integration. Maybe there are more real-time friendly alternatives?

public BSpline Derivative()
{
   Vector2[] newCPs = new Vector2[Count - 1];

   BSpline derivative = new BSpline(Degree - 1);

   for (int i = 0; i < newCPs.Length; i++)
   {
      newCPs[i] = (this[i + 1] - this[i])*(Degree/(knotVector[i + Degree + 1] - knotVector[i + 1]));
   }

   derivative.AddPoints(newCPs);

   float[] newKnotVector = new float[knotVector.Count - 2];
   for (int i = 0; i < newKnotVector.Length; i++)
   {
      newKnotVector[i] = knotVector[i + 1];
   }
   derivative.knotVector.AddRange(newKnotVector);

   return derivative;
}

public BSpline Derivative(int iTh)
{
   BSpline bs = this;
   while (iTh > 0)
   {
      iTh--;
      bs = bs.Derivative();
   }

   return bs;
}

The best book that will give you everything you need on B-splines and NURBS is "The NURBS Book" by Piegl and Tiller. It contains code snippets that can be directly implemented. As well, it does fun computational tricks, like only computing the non-zero basis functions for B-spline point evaluation, and so on. If you're doing any serious work with B-splines, do yourself a favor and pick it up.