Beyond Bézier Curves (2013)

There is a new feature of Pages and Keynote, not mentioned in any of Apple’s publicity nor in any press coverage I’ve seen, that is really very interesting. Perhaps it will even one day prove to have been revolutionary, in a quiet way.

In case you are not an Apple follower, iWork is Apple’s answer to Microsoft Office. Last month Apple introduced a new version – now free for the first time – with the usual fanfare and to a mixed reception.

Ever since the release of Adobe Illustrator 1.1 in 1987 the way ordinary people draw or edit curves on a computer has been to use Bézier splines. If you’ve ever used a vector graphics program, you’ve probably spent some time tweaking Bézier control handles, perhaps in frustration. Bézier curves were first used by French car designers in the 1960s, but as far as I know it was Adobe who introduced them to the home computer, where they have become ubiquitous.

Bézier curves are a small miracle of practical mathematics. They are conceptually elegant, easy for a computer to draw, and have a graphical representation – with draggable control handles – that is well-suited to interactive computer editing. If you don’t know how a Bézier curve segment is constructed from the control handles, try staring at this animation till it starts to make sense:

Animation by Phil Tregoning, Public Domain.

The downside is that it’s difficult for a non-expert to make attractive smooth curves using Béziers. It’s all too easy to make bumpy, lumpy misshapen things.

Hence the small revolution: the new iWork apps don’t present the user with Bézier curves at all, by default. There is a checkbox in the preferences to change the default curve type back to Bézier, but the default is much more interesting: Hobby splines.

Hobby splines were invented by John Hobby in 1985 or so, originally for Don Knuth’s much celebrated but rarely used Metafont system. They are actually ordinary cubic Béziers, but the control handles are placed not by the user but by an efficient algorithm that ensures smoothness. So of course they interoperate perfectly with software that expects to see Bézier curves, and Keynote and Pages even allow you to mix “smooth” and Bézier points in the same curve.

If you’re interested in the nitty-gritty of how they work, I would recommend reading John Hobby’s 1985 paper. There is also a secondary, unexpected pleasure to be had from this copy of the paper: the scanned document seems to have been processed by an unreliable optical character recognition algorithm, so that deciphering the intended meaning is at times an amusing puzzle.

Some words are in a different font, apparently because they defeated the OCR algorithm and so the text is reproduced from the original document.

It’s easy to guess that ‘o’ should have been ‘0’ in the first line, but takes a little more thought to realise that both ‘8’ and ‘e’ are misreadings of θ in the second.

Like all the best practical algorithms, Hobby’s method is a mixture of deep mathematical insight and low cunning. The essential trick is to use an approximate measure of curvature (“mock curvature”) that is represented by a linear expression. Then the problem of finding a smooth curve given the positions of the control points can be solved very efficiently using standard matrix methods for solving linear equations.

It very quickly becomes clear, playing with them, that Hobby splines are just a better way for casual users to draw attractive curves. All the fine-tuning of control handles is eliminated, though the shape can still be refined by adding additional curve points. Because they are perfectly compatible with industry-standard Béziers, there is very little disadvantage to be had. We’ve been doing it wrong for all these years, and now we know a better way.

Who will be the first to copy Apple’s excellent idea?

from Hacker News https://ift.tt/32aJJOw