As you know, a Bézier curve (here meaning specifically a cubic Bézier) is often used for drawing all kinds of things in vector graphics. It has the nice property that the endpoints and control points form a bounding box, and deCasteljau’s algorithm is a nice numerically stable way of evaluating the curve at a particular point. Of course, the same algorithm trivially gives the tangent to the curve at that point and from there it’s a hop and a skip to find the normal.
All well and good so far. The problem I wanted to tackle was that of spacing points equally along the curve (and incidentally, pushing these same points out along the normal), so that I can easily modulate a pattern (e.g. sawtooth, square wave) on to an arbitrary Bézier curve.
But there’s a slight problem with the naive method for doing this. Recall that a Bézier curve is in fact a parametric curve, specified by the parameter t which varies from 0 to 1 along the curve. The problem is that a linear increment of the parameter t does not correspond to a linear step along the curve length. For some curves, it’s not a bad approximation, but the more “curvy” the Bézier, the worse the discrepancy. This picture is a clear illustration of this problem.
The picture shows points (and points pushed along the normal) plotted on the curve, as t increments linearly from 0 to 1. As you can see, stepping along with constant increments of the parameter t gives the wrong result. These points are not equally spaced along the curve.
So far, I have a naive “correct” solution to this problem as follows: I sample the curve at a high frequency (say 1000). Each segment between points I then treat as a straight line, and I compute the length of the curve (simply the sum of the Pythagorean distance between successive points). I can then step along the curve linearly with respect to the curve length, and recover the parameter t (to actually evaluate the curve at a given point) by a simple calculation (binary search and interpolation between nearest neighbours). The result of this approach:
Much better.
That’s very cool. Now I’m curious to see the addition of a scratchpad area in which people can modify a bezier which you then string repeatedly along the original path, allowing people to create their own decorative line styles. I’d add a scale, and flip, each in both in U, and V to the editor, just to round out the features. Offset from the line itself would be a function of the base line’s thickness, and where in the scratch pad the sub line existed. That brings up the need to be able to move all the control points together – a so-called ‘drag’ for whole bezier.
Now I’m rambling.
Well, I’m not actually making a drawing package. I figure Inkscape et al. have that covered. However, I do want to be able to modulate a Bézier on to a Bézier. (Or more accurately, a Bézier spline on to a Bézier spline.) Of course, c1 continuity is required too.
But I think the first thing to do is clean this up a bit – it’s a couple of hundred lines of hacked together lisp code. I’ve also got spacing solutions for a line and a circular arc – which are trivial – which I should generalise to an elliptical arc and further generalise all three spacing mechanisms into one API. Also, my lisp is very naive – the simplest thing that could work. For example, I’m not even doing a binary search right now to recover t, because I’m using a list of points rather than an array.