Beyond Bézier curves

2013-11-13 § 4 Comments

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.

curves

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.

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’, but takes a little more thought to see that both ‘8’ and ‘e’ are misreadings of θ.

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?

Tagged: , ,

§ 4 Responses to Beyond Bézier curves

  • Thanks for pointing out an interesting change in iWork that I hadn’t noticed.

    I agree that doing away with off-curve control points is a great idea, especially for something designed for general use. That said, using Hobby splines involves some significant tradeoffs, and I’m not convinced they’re the right ones for iWork.

    First, as the angle between control points gets large, Hobby splines produce large, looping arcs that don’t relate in an obvious way to your drawing intent. This behavior is kind of fun to play with, but it’s not generally useful.

    To mitigate this, you need to add control points. This isn’t tragic, but it does mean that altering the shape of your curve can involve tweaks to a lot more control points than a more traditional Bezier approach.

    Second, because the Hobby spline is determined by a system of equations involving all the control points on a curve, as you change one control point, it causes ripple effects in non-adjacent parts of the curve. You can always add more control points to moderate the effect, but the effect never completely goes away. And the more control points you have, the harder it is to alter your curve.

    For my money, a better approach to this particular problem is to use something even less mathematically sophisticated than the Hobby spline: a tangent/chord heuristic (Hobby gives an example of one in the introduction of his paper).

    Something like this provides the same input simplicity of the Hobby spline (no off-curve control points for the user to mess with) but it gives you the significant advantage that moving a control point only affects the adjacent curve segments. In addition, it’s well-behaved regardless of the angle between control points.

    Towards the other end of the mathematical sophistication spectrum, Raph Levien has done some really interesting work on Euler spiral splines (http://levien.com/phd/thesis.pdf). The mathematics is (a lot) more involved, but the results are quite promising. He argues that the Hobby spline amounts to an efficient Bezier approximation of an Euler spline when the angle between control points is small. I’d love to see someone explore this approach further.

    • Thanks for a thoughtful and interesting comment, Jes.

      One of the neat things about Apple’s implementation is the way that they have made adding a new curve point a very low-friction operation: just click on the little blue circle that appears half way between two curve points, and drag to adjust. This wouldn’t really work, I don’t think, if the splines were not (to a good approximation) “extensible” as Hobby calls it – i.e. adding a new curve point on the existing curve should not visibly change the shape of the curve. Wouldn’t a tangent/chord heuristic tend not to be extensible in this sense, making it harder to refine the shape of the curve by adding new points?

      Raph Levien’s work is terrific, and his PhD thesis is a highly enjoyable read – which is not something that can be said about very many PhD theses (certainly not mine), and is testament to the quality of Levien’s prose as well as his research.

      When I played with the prototype Spiro implementation in ppedit back in 2007, there were apparent problems with numerical stability, and the numerics would sometimes even fail to converge. That seems to be quite a serious disadvantage compared to Hobby splines, which have a guaranteed unique solution that can be computed analytically. I’m not sure to what extent this problem has been mitigated since, though. (Do you know?)

  • Had I followed your discussion on Twitter, I would have seen that you were already well aware of Levien’s work–sorry about that!

    You’re quite right that injecting new points using a tangent/chord heuristic would probably deform the curve somewhat. I’d guess that the effect would be fairly subtle given that the spline itself is interpolating the tangent between the knot points, but without trying it out it’s just speculation on my part.

    Even so, it might be a fair trade to get the other characteristics. The real deal-killer for me is that if you lay out a series of points, the Hobby spline is going to look weird unless the angle between adjacent knots is pretty small. And if your knots have that characteristic, it may not matter much how you’re interpolating between them (at least for the kind of application we’re discussing here).

    Regarding Spiro, I don’t know whether you’ve seen this: http://levien.com/garden/js/spiro.html. It only implements a subset of what ppedit does (apparently only the G2 constraint type), but it seems to be pretty stable.

    • Well, you could hardly be expected to have read everything I have ever written anywhere on the internet. :-)

      I’ve realised that I rather overstated the importance of what Hobby calls extensibility and Levien calls extensionality in my last reply to you. For Apple’s curve refinement interface to work, of course all that is needed is for there to be at least ONE point, somewhere roughly in the middle of the curve segment, that can be added without distorting the curve.

      This is much weaker than requiring that ANY point on the curve can be added as a control point, and I can’t see why it wouldn’t be achievable in the sort of model you’re suggesting. I’ll be interested to see how well it works, if you get a chance to try it out!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

What’s this?

You are currently reading Beyond Bézier curves at Bosker Blog.

meta

Follow

Get every new post delivered to your Inbox.

Join 743 other followers

%d bloggers like this: