First off, before I go on with the explanation, here is the demo. The demo generates several points which are joined together with curves. The points can be animated by using the animate button, which makes them start a random walk (x, y += (Math.random() - 0.5)*2). You can add or delete points using the stepper, and show the bezier cage. The purpose of the overshoot option will be made clear below, but you can play with it to see the visual results.

All right, on with the explanation. I needed an algorithm that could join several points together with a curve. Off the top of my head, I could think of at least a half-dozen ways of doing it, some of which have been talked about thoroughly by Jim Armstrong. The purpose of this was to create real-time ‘hair’ that would blow in the wind. Basically the hair is simulated by a chain in a physics engine, and then the joints on the chain were to be joined by curves in a way that would look smooth. The physics engine (Flade) already took quite a bit of processing power, so I needed something that was very fast but not very accurate, but that nevertheless looked good.

Now in order to get that speed my painting loop needed to be as tiny as possible. Doing lineTo’s at two pixel intervals was not an option. Therefore I needed a solution which would use curveTo. Two obvious solutions came to mind: either do piecewise quad beziers, or do piecewise cubic beziers. The latter of which seemed like a better solution since there are more open parameters when creating the curve. The problem with the quad bezier solution is that when you create a quad bezier cage, the cage is entirely determined by the slope of the first and last beziers. Yet in my system there was no obvious way of figuring out what were the right values of the slopes of the first and last beziers.

Therefore piecewise cubic seemed the way to go. The problem with that one is that there are quite a few open parameters, namely the slopes of the bezier handles at every points and the length of each side of the bezier handle. So I came up the following algorithm:

For every point, look at the previous point and the next point. Figure out the slope between the next point and the previous point. Let that be the slope of the bezier handle for the current point. As for the length of the left bezier handle, project the previous point on the slope line of the current point. Take the length of projection, divide by 3, and let that be the length of the left hand side bezier handle. Repeat for the right hand side bezier handle. For the first point, let the slope be the one between the first and second point, and similarly for the last and second-to-last points. Then render the cubic beziers using Timothée Groleau’s fixed midpoint approach. You can play with the ‘cage’ setting and move points to figure out how it’s done.

Now there is a runaway scenario which happens when three consecutive points are in a rectangular triangle formation with each other, where the joining angle will look much too sharp. Thus I introduced the ‘overshoot’ fudge factor which makes sure the handles are at least a certain length, so the joins are never too jagged.

Certainly, this is not an accurate way to interpolate points, but it is very fast and looks quite good: 30 fps is maintained with 100 points on this computer. I am a bit dissatisfied with the ‘overshoot’ fudge factor, but I am sure someone here can figure out a better way of handling this runaway scenario.

Here is the source. Enjoy!

Update: I found a better solution, indeed. I will post it tomorrow.