Hobby's algorithm for aesthetic Bézier splines (2020)
Comments
Etherlord87
alejohausner
Apple used straight segments and circular arcs on its icons upto iOS 6, and switched to 2nd-order continuous shapes on version 7. Here is a side-by-side comparison :
https://blog.mikeswanson.com/photoshop-script-for-ios-7-roun...
Your visual system can actually see those discontinuities.
Etherlord87
It's actually much more prominent in 3D reflections, because this 2nd derivative ("acceleration") affects the "flow" of the reflection: https://i.stack.imgur.com/pctnj.png
I wrote a post about this on Blender Stack Exchange: https://blender.stackexchange.com/a/306616/60486
ReleaseCandidat
> Your visual system can actually see those discontinuities.
Because it's also the biggest difference of curvature (actually the radius of curvature, the inverse of the curvature value, which is what is geometrically significant, "what we see") possible, the one between infinity (a line is a circle with an infinite radius) and a "normal" (finite) value.
ReleaseCandidat
> knowledge on 2nd derivative continuity
Which means that the radius of curvature of the "seams" of the spline is the same for both curves in the common point - the spline is "smoother", there is no jump in the curvature. Like C1 means, that each point (except for start and end) of the spline has a tangent (the samé tangent from the left and the right side), no spikes. And C3 is about the torsion of (3D, as in "not contained in a plane") curves.
lupusreal
Practically speaking, what tiled video games could take advantage of this? I think generally it's important for tracks in these kind of games to be aligned with the grid and to minimize the number of sprites needed. Having discrete straight and curved pieces like a toy train set seems like a good fit for the problem game designers face.
mdswanson
Indeed. And this is where arc-length parameterization would help by linearizing t so you can then overlay it with various timing and easing functions.
ReleaseCandidat
Exactly, differential geometry is the easiest when using arc lengths as parameters.
weinzierl
Real world roads and tracks follow the principle that the curvature changes linearly with the curve length. This has the advantage that at constant driving speed the steering wheel has to be turned with constant speed as well.
So, the curve should really be a clothoid, sometimes called Euler spiral, but a cubic Bézier can be a good enough approximation.
raphlinus
Most of the applications of Hobby's spline would be better served by using Euler spirals instead. These are G2 continuous and have less curvature varation (in fact, Euler spirals are solutions of the Minimum Variation Curvature problem). I think it's fair to characterize Hobby's spline as an approximation to Euler spiral splines, just less expensive to compute.
I think there's even more to be done on this topic. In particular, I think the tension should increase as angles go up, which can solve the "flipping" behavior you see with both Hobby and Euler spiral splines. This is true for the Adobe κ-curves paper (which considerably overstates the extent to which it's the basis for the "curvature" tool in Adobe Illustrator; the latter has not to my knowledge been adequately documented).
levocardia
I was just going to comment to ask if Hobby spines were the minimal solution to any mathematical loss. Natural cubic splines are the solution to minimum L2 penalty on "roughness" (integrated squared second derivative).
raphlinus
No. Among other things, they'd have a higher degree of continuity if they were.
I personally find this a fascinating topic, so much so that I did a PhD on it. The most natural loss function to optimize for is minimizing bending energy, and there are solutions to that going back about 300 years. However, in practice that's unlikely to be what you want - the problem with it is that its scaling properties give an advantage to curves with a longer arclength even if they have more curvature variation. Intuitively, the smoothest curve through a set of co-circular points should be a circular arc, but that's not what you get from the minimum energy curve, at least unless you impose an additional arc length constraint.
The long story is of course much more complicated, but the short version is that the Euler spiral fixes these scaling issues and has some other really nice properties. If your problem is "what is the smoothest curve that goes through this sequence of points" then arguably the piecewise Euler spiral G2 continuous spline is the distinguished answer.
jake-low
Hi Raph! I'm the author of the blog post. I actually read your PhD thesis when I was working on this project and trying to wrap my head around splines. It was a huge help to me in understanding the landscape of the field and how to think about and compare different classes of splines. Just wanted to say thanks!
ReleaseCandidat
> then arguably the piecewise Euler spiral spline [...] is the answer
It is the easiest "not wrong" answer, as it doesn't for example work with points on a circle either, where the (not only "intuitive") solution would be a circle. An Euler spiral is the answer on how to ("easily") "sufficient smoothly" connect 2 points with a given radius of curvature (and therefore tangent) at both points, and no constraints between those two points.
weinzierl
This is a bit of a tangent but your expertise makes you the best person to ask, so I'll give it a try:
The OP talks about aesthetic curves, but most comments are about continuity and smoothness. Intuitively that makes sense. Do you happen to know if there is any serious research that looked into which 2D curve properties do people find aesthetically pleasing?
raphlinus
It's a good question. I touch on it a little in my thesis (mostly chapter 2). First, there is psychology literature from the 50's [1] that indicates that curvature minima and maxima are salient, so having superfluous curvature extrema makes a curve less aesthetically pleasing. Hobby splines suffer from this, if you arrange the control points in a zigzag to make a serpentine, it places curvature extrema just on either side of the control point.
Second, there's all the log-aesthetic stuff from Japan, [2] has links to a lot of papers. Honestly, I find their claims of aesthetic beauty to be fluffy, not backed up by hard empirical evidence. I did do a small amount of human evaluation research in [3], which suggests that the log-aesthetic curves are visually pleasing, but the math for their use in an interpolating spline (which is the subject of TFA) is less stable than Hobby splines, Euler spiral splines, or Minimum Energy Curves (all of which are fairly similar).
I think there's more that could be done here. Thanks for your question.
[1]: Fred Attneave. Some informational aspects of visual perception. Psychological Review, 61(3):183–193, 1954.
[2]: https://www.yoshida-lab.net/english/research-e/log-aesthetic...
hansvm
Sure. Hobby splines minimize the supremal difference between your favorite curve and a Hobby spline.
raphlinus
That's a joke answer, as you meant it to be trivially true for any curve family, but there is an important sense in which it is not true - Hobby splines are not closed under subdivision. So if you put an additional point down that lies exactly on the spline, then you won't in fact minimize the supremal difference (I assume you mean Hausdorff or Fréchet distance) to the original Hobby spline.
hansvm
Fun! Thank you :)
> supremal ==? something else
Yeah, I couldn't come up with the name as I was writing the comment and didn't want to splay a bunch of definitions across HN, hoping that "supremal" would evoke something kind of like what was in my mind.
In particular, I was imagining something closer to the Fréchet distance (allowing arbitrary indexing sets and not requiring continuity or anything nice in the reparameterization -- the infimum across all possible bijections (inf if there are none) of the suprememum of the set of distances between each bijected pair of points), but Fréchet, Hausdorff, and whatever that idea is called all have the same unique solution for this problem.
xaellison
As the article mentions, the curves are unstable. This is delightfully apparent when you drag one control point in a circle around another. Interestingly, it can also make fairly sharp corners if the control points approach each other.
nrjames
I saw this p5.js usage of Hobby’s algorithm yesterday:
graphviz
The Graphviz project often wished to find a convincing formal definition of what it means for curves (spline sequences) that connect two points and are routed around obstacles to be "natural". Maybe machine learning will help with this before long. Something similar could be said for other geometric properties of diagrams. Many aesthetics have been proposed and studied, but do we know what blend is preferred by human subjects? How much do individuals vary in this?
ixwt
I didn't really understand Bézier splines until I watched this excellent video [0] from Freya Holmér. It talks about various kinds of splines, and the various equations behind them. Explains the importance of the derivatives of splines (as other comments here have pointed out).
jake-low
For anyone interested in implementing Hobby's algorithm in their own projects, I recommend the paper "Typographers, programmers and mathematicians, or the case of an aesthetically pleasing interpolation" by Bogusław Jackowski [0]. It was my primary reference when working on the code for the examples in the blog post, and I found it easier to understand than Hobby's original paper. I mention this paper in a comment in the linked source code but it looks like I left it out of the post itself so figured I should share it here.
jfk13
Seems to me that a post about this algorithm really should have included a mention of Metafont.
jimhefferon
And also Asymptote, which extends to 3D.
flobosg
Related: Drawing better-looking Bézier curves – https://news.ycombinator.com/item?id=16364621
In many tiled video games, roads, tracks and other paths tend to be designed without the knowledge on 2nd derivative continuity (or ignoring it for aesthetic reasons). So it would consist of straight segments, and rounded segments (and maybe some intersections). The rounded segments will be simply quarters of a circle. The problem with this is that while the path is continuous (no teleportation), and the velocity is continuous (no sudden direction change), the acceleration isn't continuous - there's no acceleration on the straight segments, and then suddenly there is acceleration on the rounded segment, and that acceleration, for an arc, is constant. In real life there's an easing added to the paths of e.g. railways, so that the sudden acceleration doesn't surprise passengers. In tiles you could also design the turns to be C² continuous, but it might be aesthetically displeasing by looking like being handdrawn rather than mathematically constructed.
I'm saying all this, because it seems Hobby's algorithm is something designed precisely to construct splines that maximize this aesthetically pleasing C¹ continuity... However it tends to explode splines by favoring arc connections, so I think some optimization is needed to limit that behavior: https://i.imgur.com/W9ssWTu.png