4 ms·

Hobby's algorithm for aesthetic Bézier splines (2020)

75 points by abetusk 2y ago

Etherlord87 2y ago
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 https://i.imgur.com/W9ssWTu.png
- mdswanson 2y ago
  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 2y ago
    Exactly, differential geometry is the easiest when using arc lengths as parameters.
- alejohausner 2y ago
  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-rounded-rectangles/ https://blog.mikeswanson.com/photoshop-script-for-ios-7-roun... Your visual system can actually see those discontinuities.
  - ReleaseCandidat 2y ago
    > 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.
  - Etherlord87 2y ago
    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 https://i.stack.imgur.com/pctnj.png I wrote a post about this on Blender Stack Exchange: https://blender.stackexchange.com/a/306616/60486 https://blender.stackexchange.com/a/306616/60486
- ReleaseCandidat 2y ago
  > 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 2y ago
  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.
- weinzierl 2y ago
  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.
- infogulch 2y ago
  The Continuity of Splines - https://www.youtube.com/watch?v=jvPPXbo87ds https://www.youtube.com/watch?v=jvPPXbo87ds
xaellison 2y ago
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.
jfk13 2y ago
Seems to me that a post about this algorithm really should have included a mention of Metafont.
- jimhefferon 2y ago
  And also Asymptote, which extends to 3D.
nrjames 2y ago
I saw this p5.js usage of Hobby’s algorithm yesterday: https://openprocessing.org/sketch/2257597/ https://openprocessing.org/sketch/2257597/
raphlinus 2y ago
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 2y ago
  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 2y ago
    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.
    - 2y ago
ixwt 2y ago
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). [0]: https://youtu.be/jvPPXbo87ds https://youtu.be/jvPPXbo87ds
flobosg 2y ago
Related: Drawing better-looking Bézier curves – https://news.ycombinator.com/item?id=16364621 https://news.ycombinator.com/item?id=16364621
jake-low 2y ago
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. [0]: https://tug.org/TUGboat/tb34-2/tb107jackowski.pdf https://tug.org/TUGboat/tb34-2/tb107jackowski.pdf
graphviz 2y ago
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?

75 points by abetusk 2y ago

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 https://i.imgur.com/W9ssWTu.png

mdswanson 2y ago
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 2y ago
  Exactly, differential geometry is the easiest when using arc lengths as parameters.
alejohausner 2y ago
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-rounded-rectangles/ https://blog.mikeswanson.com/photoshop-script-for-ios-7-roun... Your visual system can actually see those discontinuities.
- ReleaseCandidat 2y ago
  > 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.
- Etherlord87 2y ago
  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 https://i.stack.imgur.com/pctnj.png I wrote a post about this on Blender Stack Exchange: https://blender.stackexchange.com/a/306616/60486 https://blender.stackexchange.com/a/306616/60486
ReleaseCandidat 2y ago
> 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 2y ago
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.
weinzierl 2y ago
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.
infogulch 2y ago
The Continuity of Splines - https://www.youtube.com/watch?v=jvPPXbo87ds https://www.youtube.com/watch?v=jvPPXbo87ds

xaellison 2y ago

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.

jfk13 2y ago

Seems to me that a post about this algorithm really should have included a mention of Metafont.

jimhefferon 2y ago
And also Asymptote, which extends to 3D.

nrjames 2y ago

I saw this p5.js usage of Hobby’s algorithm yesterday: https://openprocessing.org/sketch/2257597/ https://openprocessing.org/sketch/2257597/

raphlinus 2y ago

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 2y ago
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 2y ago
  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.
  - 2y ago

ixwt 2y ago

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). [0]: https://youtu.be/jvPPXbo87ds https://youtu.be/jvPPXbo87ds

flobosg 2y ago

Related: Drawing better-looking Bézier curves – https://news.ycombinator.com/item?id=16364621 https://news.ycombinator.com/item?id=16364621

jake-low 2y ago

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. [0]: https://tug.org/TUGboat/tb34-2/tb107jackowski.pdf https://tug.org/TUGboat/tb34-2/tb107jackowski.pdf

graphviz 2y ago

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?