Hobby’s algorithm is a technique for fitting a curve onto a sequence of points on the plane, such that it passes through all of the points in order. The resulting curves appear smooth and tend to form pleasant, relaxed shapes.
Here’s an interactive example—try dragging some of the points around.
Hobby’s algorithm can be used to create simple but effective user input systems for manipulating curves. Users only need to place points, and the software can automatically fit a curve onto those points that has a reasonably smooth and unsurprising shape.
Hobby curves are related to another curve which is quite common in computer graphics: Bézier curves. In fact, Hobby curves are Bézier curves, and Hobby’s algorithm is simply a technique for choosing a particular Bézier curve that passes through the given points and has a smooth, rounded shape. The rest of this post discusses the relationship between Bézier curves and Hobby curves, and why Hobby curves might be preferred in certain applications.
The JavaScript implementation of Hobby’s algorithm used for the interactive examples in this post is available under the ISC license. I have thoroughly commented it in the hope that it may be useful as a reference when implementing Hobby’s algorithm in other languages.
Curves
A Bézier curve (pronounced BEH-zee-ay) is a type of curve commonly used in computer graphics.
Bézier curves are defined by a sequence of control points P0 though Pn. The points P0 and Pn form the endpoints of the curve. The other control points influence the shape of the curve, but don’t necessarily lie on it. The value n is called the order of the curve. The most commonly used Bézier curves are quadratic (order 2) and cubic (order 3).
Bézier curves are parametric curves, meaning that their shape is defined by a function of a parameter called t. By plugging in a value of t in the range [0, 1], we get back a point on the curve.
The function that defines a Bézier curve’s shape can be thought of as repeated linear interpolation between adjacent control points. We first lerp between each adjacent pair of control points using the parameter t to find an intermediate point that lies on the line between them. Then we use those points as new control points and lerp between each adjacent pair again. Each time we reduce the number of points by one. After repeated iteration we’ll have just one point left. That point lies on the curve.
By varying t from 0 to 1, we can sweep out the shape of the curve. Below is an example of a cubic Bézier curve being swept out using the technique described above.
For a more thorough introduction to Bézier curves, see Freya Holmér’s excellent video.
Splines
A spline is a sequence of connected curves. A Bézier spline is a spline made up of Bézier curves.
In the example below, each curve in the spline is a cubic Bézier curve. The spline connects a sequence of anchor points called knots. Each knot is the end of one Bézier curve segment and the beginning of another. Between each pair of knots are two control points that influence the shape of that segment. It’s common to represent these intermediate control points as “handles”, with a line attaching them to their adjacent knot. You may have seen this kind of interface when using the Pen tool in Inkscape, Illustrator, or Photoshop.
You may have noticed that we’ve also added an additional constraint: around each knot, the adjacent control points are symmetric. This ensures that the spline is smooth. More specifically, it ensures that the spline is C1 continuous, which means continuous in its first derivative (i.e. no sharp corners). You can create splines that violate this constraint (hold Shift while dragging a control point to try this). But for the rest of this post, we’ll mainly be focusing on curves that are smooth, by some definition.
Problems with Bézier splines as an input system
Lots of software uses Bézier splines as an input system to allow users to manipulate curves. While this offers a great deal of expressive power, it can also be challenging to use. In particular, adjusting the handles in order to produce a pleasant curve tends to require lots of fiddling.
In some situations, it may make more sense to sacrifice some flexibility in order to make the interface easier and quicker to use. One way to do this is to only require the user to choose the positions of the knots, and to automatically compute appropriate positions for the handles based on some metric that tends to produce pleasing curves.
Natural cubic splines
One way to choose handle positions for a sequence of knots is to require that the second derivative of the resulting spline is continuous. This means that if a particle were traveling along the spline at a constant speed, it would not experience any sudden changes in acceleration. This is called C2 continuity. A cubic Bézier spline that is C2 continuous is called a natural cubic spline.
It turns out that for any sequence of knots, there is one unique Bézier spline that fits those knots and is C2 continuous, and finding the required handle positions for that spline is fairly straightforward.1 Here’s an example in which the natural cubic spline is computed automatically to fit a given sequence of knots.
The resulting spline is smooth, mathematically speaking, and for many applications this is very useful. But I became interested in these curves mostly for aesthetics, and the appearance of the natural cubic spline isn’t quite what I had been hoping for. In many configurations the spline appears contorted, with small regions of very high curvature. It looks unnatural to me, in the sense that an elastic rod which were forced to pass through those knots would take a more relaxed shape with less variation in curvature.
It seems that by requiring that curvature be continuous, we have also created large variance in curvature along the spline. Could relaxing this constraint lead to more pleasing curves?
Hobby’s algorithm
Hobby’s algorithm2 is an alternative technique for choosing handle positions given a sequence of knots, in order to produce a Bézier spline. Instead of requiring continuity of true curvature, as with the natural cubic spline above, Hobby’s algorithm produces splines that have continuity of mock curvature (a first-order approximation of true curvature).
In this example, you can see the difference between a Hobby spline and the natural cubic spline.
Continuity of Hobby splines
Unlike natural cubic splines, Hobby splines are not C2 continuous. In fact, they aren’t even C1 continuous. If you enable “show handles” in the example above, you’ll see that they are not symmetric around their knots, which is required for C1. But the handles at each knot are always placed directly opposite each other, which grants the curve a closely related property called G1 continuity.
To understand the difference between C1 and G1 continuity, imagine moving a particle along the curve by varying the input parameter t at a constant rate. In order for the curve to be C1 continuous, the particle’s velocity vector must change continuously as it moves. But for the curve to be G1 continuous, only the direction of the velocity vector needs to be continuous; the length of the vector is allowed to change abruptly. A G1 curve still looks just as smooth as a C1 curve; you can only tell the difference if you’re using t to drive movement along the curve.
So Hobby curves still look smooth, even though mathematically they aren’t necessarily continuous in their first derivative with respect to t. And compared to natural cubic splines, they exhibit much less variation in curvature, which tends to give them pleasant, rounded shapes.
Other properties of Hobby splines
Much like the natural cubic Bézier spline, the curve produced by a Hobby spline passes through all of its input points. This makes the spline intuitive to use for creating curves in a user interface. Hobby’s algorithm can be computed very efficiently (in linear time), which means the UI can easily recompute the curve every frame while a user is dragging a knot around. And Hobby curves “compile down” to ordinary Bézier curves, which can be efficiently rendered and are widely supported in graphics libraries.
The main drawback of using Hobby splines as a user input mechanism is that they are less flexible than unconstrained Bézier curves. Users cannot create curves with sharp corners, nor can they intentionally vary the curvature along the length of the curve. Hobby curves are also unstable: moving a knot may cause the resulting curve to “snap” into an entirely new shape, which does not happen with natural cubic splines. And moving a knot affects the entire curve (although the effect is strongest near the knot). By contrast, in an unconstrained Bézier curve, moving a knot only affects the curve segments adjacent to that knot.
Conclusion
Overall, Hobby curves offer less flexibility than unconstrained Bézier curves, but can create aesthetically pleasing shapes with less effort. And because Hobby curves are really just Bézier curves whose handles have been placed automatically, they retain all of the benefits of Bézier curves: easy to work with programmatically, efficient to render, and widely supported.
If you’re interested in implementing Hobby’s algorithm in your own projects, have a look at the source code I used to create the interactive visualizations in this post. It’s is free to use under the terms of the ISC license, and is very thoroughly commented in case you need to port it to another language.