A couple of the questions I received regarding this post were how well the arc-length parameterization performs in the event the path is rapidly redrawn (i.e. knots are continuously modified) and how it works if the spline degenerates to a line. The intended application was along the lines of using a path to simulate a wave and then have the text move along the wave. It would eventually decay into a line, then the text would be animated along the line, off screen.
Well, that’s a good question because the cubic spline interpolation uses a minimal number of interior interpolation points, but is somewhat expensive to setup and compute. It requires assembling and solving a tridiagonal system of equations, so it is best suited for situations where arc-length is computed once and then sampled many times. If the knots are continuously changed, then the spline’s arc-length also changes continuously, forcing expensive recomputation.
The approach also assumes a smooth transition from knot to knot in terms of t vs s. For splines that are straight lines, the interpolated data is piecewise linear, so the spline tends to over- or under-estimate arc length in regions just past interior knots.
Linear interpolation is faster to setup but requires many interior interpolation points. A scheme that assigns the same number of points per segment easily creates too many points for one segment and too few for another.
I’m currently overhauling the arc-length parameterization for the cubic Bezier spline to use an adaptive algorithm for assigning interior interpolation points. Along with some additional information to speed lookup, this should allow linear interpolation to work reasonably well across a wide variety of knot distributions. It should also perform well with splines that are continuously redrawn with new knot placement.
The image below shows an example of the algorithm (still under development).
Although the knots form a straight line, the spline creates two cubic Bezier curves with C-1 continuity at the interior knot. So, the two straight lines are actually two cubic Bezier curves that happen to have zero quadratic and cubic coefficients.
The distribution of parameter value vs. arc length is not linear along the entire spline because the knots are not equally spaced along the line. The piecewise linear distribution would cause a slight difference in kerning among any letters that happened to lie just beyond that interior point in the previous approach.
The new algorithm handles this case nicely. I still have some work to do on making it more efficient. The tangent and normal calculations will also be overhauled for efficiency. After that, I need to resolve issues like how to handle text that extends beyond the extent of the spline. Lots and lots of details 🙂
The Algorithmist 