3 Nov 2004 raph»(Master)

The election

I'm still in a state of shock. I think things are going to get quite a bit worse before they get better again. I also think this outcome is likely to be bad for free software in many different ways, including strong anti-American sentiment around the world, shoring up of corporate power, and a general devaluation of the public interest as an important factor in political decision-making.

Curves: Ikarus

Ikarus is a near-legendary system for digitizing outline curves for fonts. I had a copy of Karow's 1987 book explaining the system (complete with FORTRAN source code, no less), but somehow managed to let it go. I've been meaning to get back to it for a while.

A month or so ago, I wrote that I was pretty sure that Ikarus used Hermite splines. In response, haruspex disagreed and said it was circular arcs. I was dubious because assigning one circular arc between each pair of adjacent knot points yields an overly rigid numerical system.

It turns that we were both right. The actual Ikarus system uses a hybrid approach. The first step is to fit a cubic spline to the knot points (with weighting based on distance between knots, to improve cases when the knots are not evenly spaced). However, from this phase, only the tangents are preserved; the spline curves themselves are discarded.

At this point, you have position (the original input) and tangent constraints for each knot. Those constraints uniquely determine a biarc for each segment between two knots. Since a biarc is made up of two circular arcs (tangent continuous at the join), you have an extra degree of flexibility that avoids the rigidity I was worried about.

So now I can state clearly the similarities and differences between Ikarus and my Cornu-based approach. They both try to fit a smooth curve through the input points, and both work in two passes, the first of which finds the tangents and the second of which draws instances of the primitive geometric curve. However, I use a Cornu spiral segment where Karow uses a biarc, and I choose the tangents so that the curvature of the final curve is continuous. Ikarus, by contrast, chooses the tangents so that the curvature of the intermediate cubic polynomial is continuous. By nature, you can't make biarcs continuous in curvature, but Karow's solution certainly counts as a rough approximation of that goal.

I need to make a visual illustration of the differences, but I expect the Cornu approach to be better in all respects. Cornu spiral segments, while resembling biarcs (and having precisely the same control parameters) have smoother variation of curvature. Similarly, I expect the tangent solution to be more accurate, not least because it guarantees curvature continuity of the final curve. When there is a large number of points (Ikarus recommends one knot for every 30 degrees of arc, and the illustrations in Karow's book seem to be even finer), the two solutions should be nearly identical. However, I think you can get away with about half as many points with the Cornu spline without sacrificing smoothness. That should make it easier to maintain high quality while editing and otherwise distorting, as well as the obvious savings in time because you don't need to enter as many points.

Btw, the Ikarus book also clears up my hazy memories about previous spiral approaches to curves. I thought there was a historical spiral format due to Coueignoux, but the one I was thinking of is actually by Purdy and McIntosh. A survey paper by Lynn Ruggles has all the details for the curious, or read the patent.