Show HN: A new spline | Hacker News Reader

Show HN: A new spline

raphlinus.github.io

341 pointsraphlinus72 comments

I'm up to page 9 on your thesis, and have already learned many things. Your "empirical testing of fairness" section is great.

From your thesis: > Intuitively, curvature is the position of the steering wheel when driving a car along the curve. Therefore, G2 continuity is equivalent to the lack of jerks of the steering wheel

I particularly like this analogy because I've worked simulating NPC cars in computer games and I found lack of G2 continuity of 3 Beziers annoying - the jerk of the steering wheel clearly put a sudden change of cornering forces through the suspension simulation which looked very unnatural.

This looks really awesome.

I'm curious, because I haven't seen much work built on top of Knuth and Hobby's "Most Pleasing Curve" as defined by Mathematical Typography [0] and Hobby's follow-up papers [1] [2] [3]. Has anybody investigated these? As far as I know they're just not very convenient to rasterize.

[0] http://www.math.lsa.umich.edu/~millerpd/docs/501_Winter13/Kn... [1] http://i.stanford.edu/pub/cstr/reports/cs/tr/85/1047/CS-TR-8... [2] http://ect.bell-labs.com/who/hobby/thesis.pdf [3] http://ect.bell-labs.com/who/hobby/87_2-04.pdf

Well, there's my thesis :)

There has been some work on this. Apple's Pages uses an implementation of the Hobby spline, demonstrating that it can be used in real consumer products. I think if you put these two side-by-side though, mine comes out quite a bit better; when you push the Hobby spline you get curvature extrema quite a distance from the control points, and mine doesn't do that.

Hobby's work has of course been an inspiration for mine for a long time, and it holds up academically quite well too - it has just the right blend of practical and aesthetic considerations and theoretical analysis; his solver runs in linear time and there's a proof it always converges (as long as tension values are within a reasonable range).

And of course there's the k-Curve work from Adobe. I think it is a step forward from Hobby in some ways (more robust) but a step back in others (it's not as smooth and most especially doesn't form true inflections).

It would be great to be able to compare this with Béziers of arbitrary degree. Some people get frustrated with degree 3 Béziers, but you can do great things with degree 5, 6, 7, or even higher - and they're C^infinity internally. If you could add curvature combs to your demo it would help in evaluating what it can do. I can see from the curve itself that I can get pretty nice results, but occasionally I notice small wobbles that would be more obvious with a curvature plot. Is it possible with this type of curve to vary the weights of the tangent vectors?

I'll add curvature combs in a future revision. I'll also point out that you can see a curvature plot of the underlying 2-parameter curve family by playing with beztoy.html in the linked github repo, which is one of the main ways I evaluated this.

Higher degree Béziers illustrate the "curse of too many parameters." Yes, they're very expressive, and yes you can have very high degrees of continuity, but it's also easy to make very wiggly or lumpy curves. I don't know of anyone who uses them, certainly not for font design.

Class-A automotive surfacing (using Alias, ICEM, Catia, NX) is all done with higher degree Béziers. I use them all the time in SolidWorks for consumer and medical product design engineering.

It’s certainly tricky to figure out how to manage Béziers, but with the right tools and some knowledge of the math, you can do amazing things. Using the sketcher constraint tools in the SolidWorks it’s possible to join higher degree Béziers with G3 tangency (or even higher). I also build approximate offset curves of the same degree using a modified version of Tiller and Hansen’s method (I keep the control polygon legs parallel, but I add constraints to control the offset distance of the curve at n-2 places along the curve).

If I was doing font design, I’d love to have higher degree Béziers. Being able to make a sans-serif ‘S’ with single span curves would be great. Or lining up 3 control points on either end of the top of a lower case ‘n’ with vertical straight lines to have it be G3 would be nice.

Actually manipulating higher-degree Bézier curves (or B splines, etc.) is a pain in the butt. In theory you can make any possible shape, but in practice it’s very difficult to get it to do what you want using the standard provided user interface.

> weights of the tangent vectors

Is this a synonym for curvature? In theory you could directly specify the curvature at a knot.

Or do you mean something more explicitly like weights in NURBS? Those could also conceivably be added, but IMO the hit to human intuition / intelligible UIs makes it not worth the trouble.

They are not very handy because the controls points don't mean much to the user.

Speaking as someone who's never touched splines before, this looks pretty nice. I was able to very quickly reproduce the "a" from your screenshot using your demo.

Thanks, that's music to my ears! A major focus of this work was making a primitive that would be intuitive and that you could build a good UX around. Considering the nontrivial learning curve for Béziers, I think your report is significant.

Also as someone who's never touched splines before, I found it pretty difficult to replicate. The "a" from the screenshot looks fairly smooth everywhere (except possibly the upper-right outside curve), but I found that unless I got the positioning just right, I could run into some degree of "bumpiness". This may, of course, say more about me than about Raph's new splines :P.

If I wanted to try Raph's prior work on spiro splines for comparison, is there some way to do that that's easier than learning to use Fontforge? (When I last tried Fontforge, it didn't seem to handle hi-DPI screens well...)

There's a downloadable demo here: https://levien.com/spiro/

> For the impatient, click on the screenshot below to try the demo yourself.

You should add a link to the demo in the word "demo" for the people like me that can't follow instructions :). I tried to drag the points in the screenshot instead of clicking it.

You might want to add some basic instructions somewhere too. I had to dig through the source to figure out what some of the keyboard and tool tricks are. Perhaps they are standard in Illustrator or some other tool, but double clicking, shift-clicking, option/alt-clicking, nudging etc... I only figured out by poking around the .js.

Done, thanks for the suggestion.

Just reading your thesis: Very interesting stuff! Thanks for sharing it.

Thinking about "fairness" of a spline: Intuitively I'd say a curve is "most fair" as compared to other curves when it minimizes the sum of squared centrifugal forces of a body moving along the path. In other words: The faster I can drive a car along the path the fairer the path :)

Would such a definition make any sense?

This is very similar to the "Minimum Energy Curve" fairness metric, which minimizes sum of of bending energy, which in turn is proportional to curvature squared. And, thanks to basic physics, curvature is proportional to the centripetal force given a constant velocity.

The problem with MEC is that it tends to optimize for low tension; for inputs that are not well behaved, it sometimes optimizes for infinitely low tension, ie an infinitely long road. So there are other metrics, like Minimum Variation of Curvature, that work better for actual spline use, even though they have an energy metric that's "worse."

These curves are absolutely useful for path planning. A lot of the literature on "clothoids" from a hundred years or so ago is on transition curves for railroads. The G2 continuity condition basically means that you never have to suddenly turn the steering wheel to follow the curve, it's always moving continuously.

For what it’s worth it makes beautiful sense to me. Both as a motorcyclist and also as someone who has thought a lot about splines.

My favorite spline editor is the Bezigon tool in Macromedia Freehand of yore. It sprang to mind as I read the passages you wrote.

Very nice! I've used a spline tool in SolidWorks that I found useful and was hoping to find something outside of solid modeling that was similar and this seems to be it, super intuitive and clean!

Probably not the use it was intended for, but I wonder if this could be used to improve imagemap polylines. I use Wikipedia's imagemap tool [0] and I wish the interface was like this (actually, I use a separate site [1] to generate the polyline values).

[0] https://www.mediawiki.org/wiki/Extension:ImageMap

[1] http://maschek.hu/imagemap/imgmap/

This is very interesting!

I'm mostly familiar with b-splines and NURBS and such, and there's some behaviour in this demo that I don't understand. If I create a round control point, and spin that point's handles around, sometimes the curve coming in and out of the point is a beautifully smooth tangent, coming in one side and out the other, and sometimes it forms a spike, doubling back on itself. Is there a term for that? Why does it happen? I find it fascinating and would like to learn more.

It's likely it could be reworked to not make those spikes. The reason it happens is tricky. The basic curve family (what you get when you don't add explicit tangents) has a π-periodicity in the angles. Essentially it cares about the slope of the tangent but not the signed direction, and reverses the sign as needed. The curvature blending uses the same family but the sign reversals don't always "make sense" in terms of producing a smooth result. It's not obvious it would be better, as what you'd get would be more "twisty," and it's also possible the twistiness would snap as you rotated the handles. So making a direction reversal might be one of the less visually objectionable ways to handle the problem.

This is one of those "deep UX" questions I find fascinating.

When the bar is turned through 360 degrees its adjustment effect seems to go through 2 complete cycles. A single ended adjustment line which begins perpendicular in a default orientation and goes through just 1 complete adjustment cycle when turned 360 might be easier to control and understand, even though it would be less like the familiar bezier tweak lines.

This spline only depends on the orientation of the tangent line, not on the direction of the tangent ray. i.e. it is periodic every half turn, as you found.

That’s actually the whole point of this type of curve (and also Adobe’s recent “k-curve” tool) – knots are more or less at the curvature extremes; pulling a knot outward will make first a ruffle shape, then a sharp cusp, then a loop; the curve in general doesn’t extend far outside the rough shape of a polygon through the knots; and the solver is robust.

There exist plenty of curve primitives more like what you are suggesting here (see Raph’s PhD thesis), with a full-turn periodicity. But they end up creating shapes which loop out past the knots, and they also tend to not have unique solutions all the time, with the result that they sometimes will discretely jump from one local minimum to another as you make slight changes in the inputs.

> There exist plenty of curve primitives more like what you are suggesting here.

The only thing difference I suggest is the control. Its the difference between:

effect = control_angle mod PI ,or

effect = control_angle / 2

When a full turn of the control produces a full cycle of effect a better ergonomic relationship might result.

Yes, but the generated shapes are based on the curve primitives used. The whole point of this particular curve primitive is that the “default” shape of the spline (if you don’t try to set the tangents explicitly) doesn’t extend much past the knots, because of the half-turn periodicity. As you drag a knot away from the spline, you will get a cusp shape with the knot at the cusp, and if you drag further it will turn into a loop with the knot at the peak of the loop.

If you instead had a full-turn periodicity, you would have substantially different properties for the curve shape. Several such curve primitives exist, you can use one of those if you want. This is one of the trade-offs involved in the choice of tool.

With this particular type of curve primitive, the primary way to change the spline is by adding and moving control points, not by trying to manually specify tangents. The latter should not be used for general shape design but should be seen as a specialty tool to support niche technical requirements (such as straight segment to curve interfaces), and tangent adjustments should be sparing because large tangent adjustments will create lumpy shapes.

Sorry I dont share your idea of correctness between this control parameter and its formulaic effect. We might say the formula naturally wraps this angle, but the formula doesn't mind what space we prefer to map from.

> If you instead had a full-turn periodicity, you would have substantially different properties for the curve shape

We would have precisely the same effect on curve shape from a 360 degree control than with a wrapped 180 degree control, but have twice as much travel to adjust the outcome more finely.

Makes sense. Personally, I like it, though it does make the curve slightly less predictable.

Wow Raph is pretty busy/productive: xi, druid, a his company and this.

What is his company doing?

It's not really a company, just me, but I'm making a music video game. And yes, the last few months have been a burst of creativity, after something of a slump the first half of the year. Leaving Google and going out on my own has been good for me. Now, if only I had a source of income...

Did you ever think about doing a Kickstarter project?

For example, the guy who is writing Prosemirror (an editor), started such a project, and was able to secure a source of income.

https://www.indiegogo.com/projects/prosemirror#/

You could start a bunch of these projects, see which one is funded first, and then focus all your energy on that project.

Low-maintenance boring companies can generate a lot of income if done right. I would love to talk a bit more about this with you

Having written the TCB spline (Kochanek–Bartels spline) implementation for a few animation pipelines, I am curious what you see as the problems with the TCB spline? Having explicit controls for tension, continuity and bias feels pretty comprehensive and I'm not aware of animators unhappy with it.

It's very good, but I think the problem is "too many parameters." In some contexts that's fine (animators are used to it) but in others it might not be ideal. People don't use that spline for font design work; why? The Hobby spline has a tension parameter, which is said to be "very useful" in the paper, but when Apple adapted it for Pages, they left it out of the UI. Was that a mistake, or did they make an informed user experience tradeoff? (Incidentally, I believe tension is in there, as part of the illusion of extensibility, but deeply hidden)

So whether this spline is better for, say, animation, is what I consider a fascinating research question. Hopefully putting it out there will start to get answers.

I can't tell from your online demo if there is any control over the trade off between only dropping curve points where tangentially required verses even distances between curve points. (I'm sure there is some shorter term for that.) I remember a talented animator remarking to me how he had acceleration control with TCB Splines that allowed him to achieve the same curve shapes but with control where curve points are emitted, giving him timing controls for objects in motion. He liked using TCBs for everything.

> Kochanek–Bartels spline

YMMV, but the problem I have is that it generally makes ugly shapes unless you are very skilled/practiced with it and very careful about twiddling parameters, because the control parameters are based on the implementation details of the mathematical tool rather than directly on features of human perception.

There’s basically a mismatch between human-centered goals and the mathematical model of those.

As an analogy, you might think of it like trying to learn how to dance vs. learning how to make a puppet dance by manipulating a control bar with your fingers to pull on its strings. The latter involves more indirection, which makes it harder for novices to get approximately their desired result.

For anyone unfamiliar with this tool, see the image in https://en.wikipedia.org/wiki/Kochanek%E2%80%93Bartels_splin...

It's interesting to me, to think about how curves like this can be useful in robotic path planning.

This looks great. I appreciate the article as an example of how the specifics of an algorithm impacts user experience. Far too often we think of user experience as being independent of the implementation, like it’s just a layer on top.

"I intend to port to at least C++ so that it can be more easily integrated into real systems" - disregarding the implication that C++ is a more "real" system than Javascript what steps are necessary to make the numerical methods that are not perfect and if pushed hard will sometimes get a slightly wrong answer along with addressing not being able to make multiple subpaths required to draw font shapes?

I tweaked the language, thanks for pointing that out. Obviously JavaScript is capable of very real systems and many of the potential applications of this work. Regarding the timeline, I'm hoping soon, but it's going to depend on where I want to take this codebase; I still haven't really decided, and it will depend in large part on what kind of interest I see. The multiple subpaths question is of course not a problem with the spline itself but whether the test app has a sophisticated enough document model to manage multiple path objects.

This will be amazing for shape optimization. As it seems one can describe various shapes with very little control points and parameters. Furthermore the relation between the control points and the final spline is very well behaved and thus great for use in an optimization. Great work!

What do you mean by “shape optimization”?

It’s a field in engineering where optimization is used to optimize a engineering design for a certain purpose (e.g. a beam for stiffness).

Topology optimization is the broader field that allows topological changes to the design (e.g. the addition or removal of nodes). These optimization’s often have a solution that first have to be interpreted by an engineer to turn it into a manufacturable design.

A shape optimization performs optimization only of certain variables of a predefined design. The splines as described here seems to fit well for describing for instance sheet metal parts or cross-sections of beams.

I must say, that "a" looks good given the number of control points.

The code is in a research repo... with a GPL license

This seems like the sort of thing that LGPL is really well-suited for. Any reason for going with GPL? Not many people are going to want to GPL-infect an entire project just to adopt a new spline solver.

I don't understand how is this different to somethigng in Inkscape?

> and solves most of the problems that held that back from wider popularity.

> …

> and is in JavaScript with a GPL license.

If you want them to be widely adopted outside of research circles, you should avoid the GPL. Many companies would be interested in a curve like this but would avoid GPL just avoid any possible litigation. It's not great, and it's probably not a popular opinion I have but it's what I've seen from experience.

This comment kinda rubs me the wrong way, especially since the author notes that I also want to preserve full ownership of the code so that I can do commercial licensing of code derived from it. If there are many companies that want a curve like this (which means it presumably took non-trivial time and skills to develop), maybe they should come to a commercial agreement with the author?

What is it with pushing people to unpaid labour to make megacorps happy with some fuzzy notion of potential "wide adoption" as the only reward?

Thank you. As you note, the story here is very clear. It's under GPL so there is no friction for it being used in open source creative apps like Inkscape, and for uses outside GPL I want people to buy an exception[0]. I've had success with this licensing model in the past and am hopeful it can continue.

[0] https://www.gnu.org/philosophy/selling-exceptions.en.html

Good for you. That's exactly as intended.

The intent of making something open source is usually for others to use it. The parent is remarking that by choosing GPL the code would probably never be used. Which, in theory, would defeat the reason for making it open source in the first place.

I'm assuming the idea behind making such a comment is the realization that many people, especially in academia, do not realize how unusable GPL is.

> The parent is remarking that by choosing GPL the code would probably never be used.

Nonsense. Raph Levien's spiro spline code already is used in Inkscape and Fontforge, as you could easily have found out yourself. How exactly is releasing code under GPL going to to prevent its adoption in widely used GPL'ed software?

And if the approach is any good, why would a commercial software vendor not be convinced by the GPL'ed prototype to reach out to Raph to find a licensing deal or commission work from him rather than doing it themselves?

> people [...] do not realize how unusable GPL is.

The GPL is so unusable that almost every computer or device you touch is full of GPL'ed software.

I think the "unusability" of the GPL is exactly what many people want when they release GPLed code.

GPLed code can be used by other researchers (good for popularity), but you can't use it for proprietery software.So if Adobe wants to use this curve, they have to license it.

If it actually works out, I don't know, but that's been the intention of some researchers that I asked why they used GPL.

> The intent of making something open source is usually for others to use it.

The intent of releasing something under a MIT or BSD license, maybe.

You can release the source code without any license. Adding a license means you want other people to "license" it from you - I.E. using your code.

The GP actually quoted the article "and solves most of the problems that held that back from wider popularity."

Which imply the author wanted people to adopt it. I'm assuming it wasn't about other academics adoptions but of hobbyists and commercial ventures.

> Many companies […] would avoid GPL just avoid any possible litigation

There are so many examples of GPL software being blacklisted by commercial companies and dying out as a result. Linux, Bash, gcc, Blender, Ansible, MySQL, git… It really is quite a graveyard.

In all seriousness, the licensing choice seems very reasonable for someone wishing to partner with commercial companies rather than have their work lifted without royalties.

There's a difference between using GPL software, and shipping GPL software as part of your product.

I use lots of GPL software for building my product (like git), but I can't ship any as a part of it.

I presume that code for a curve is meant to be included in a product, rather than being used on its own.

libgit2 is used by GitHub (a Microsoft product); bash is packaged in macOS (an Apple product); MySQL is served in RDS (an Amazon product).

Companies find various ways to ship GPL software, depending on the situation. Sometimes it requires discussing it with the authors. Overall, it does ensure greater protection on the authors and on the propagation of the software.

libgit2 has a "linking excemption", which is probably the only reason why Github can use it, so that's a bad example, because it isn't really GPL (it's more like LGPL).

Shipping bash as a part of macOS is not what I had in mind. (and it's funny, because macOS ships an ancient version of bash, because they don't want to touch GPL3...)

As for Amazon RDS, I thought that was SaaS? So they don't "ship" it either...

I mean the whole purpose of GPL is to make using it with closed source difficult / impossible.

And in practice, apart from the big Open Source projects, GPL is used a lot by people who don't want to give away their code for free, they just want to get people to pay for a commercial license. Which is odd, because it feels like it is totally against the spirit of the free software movement.

> Which is odd, because it feels like it is totally against the spirit of the free software movement.

And yet, it is completely within the original intended spirit. It is not about "giving source code away for free", it is about the user (who may very well have paid for the right to use the software) being "free" to do whatever they want with it...up to and including modifying the source code for their own benefit. With traditional proprietary (aka "non-free") software, even if you had access to the source code, you are not legally allowed to modify it. And then GPL goes a step further and allows you to redistribute your modifications! That's freedom.

The idea that "open source" means "give everything away" is imho one of the primary mistakes of the "free software" movement. and why RMS now encourages the term "libre software" instead.

https://www.gnu.org/philosophy/free-sw.en.html

He considers commercial licensing.

GPL is perfect, we get to play around with it and the author may make money from it. And if it doesn't work, the author can still switch to a more permissive license (MIT, BSD,...), the other way around won't work.

Also worth noting that it is presumably not patented, so nothing prevent companies from rewriting the algorithm.

The author is still able to give out commercial licences to companies, so where is the problem?

Anyone interested is free to obtain a better license aligned with their needs.

Surely the curve function is worth something. Take that something and invest in a non GPL license.

GPL = Share and share alike

A company using the curve function for profit is not sharing. And that is OK, but they should also be paying for that, due to the fact that they are unwilling to pay by contributing more open code.

The open code comes from people who have to eat. It makes perfect sense for closed projects to pay for a suitable license. The author makes mention of all this, indicating commercial license plans.

That's exactly as it should be.

Agree, GPL effectively means non-commercial.

Most companies won't touch GPL code with a barge-pole.

Would you want to use code the author explicitly describes as not yet complete research-code and not for production commercially?

If it doesn't belong in a commercial product, does it belong in Inkscape or OpenOffice?

That was previous millennium. We're in 2018 now.

Hello Ralph.

It looks great but you should add some basic usage howto. It is obvious that you know how to use it, you created it, but other people do not.

The first time I used it it was very frustrating because I only created circle handlers, and said: This is sh*t!! Then I close the window and looked back at the sample image and saw square pointers, so I said: There must be some key that creates square pointers. After trying again I discover it creates square handlers by default.

This is the typical engineer mindset, after having spent years doing something they consider obvious what it is not.

Read "The Design of everyday things" for more design concepts if you are interested.

> This is the typical engineer mindset, after having spent years doing something they consider obvious what it is not.

More charitably, this is the way all research prototypes work in any field.

Production vector illustration packages hire a team of people who spend man-years of effort canvassing customers, collecting bug reports, adding features and affordances and refining the user interface, writing documentation, and so on. Someone making a research prototype where the UI per se was built in a few weeks is not going to have the same feature richness, level of polish, or clarity of outward-facing documentation.

Give it some time.

"The Design of Everyday Things" is a great book, I enjoyed it.

Part of why I put it up with no instructions is to get feedback on how intuitive it is to use without any explicit instruction. I've gotten mixed response; some people seem to get it, others don't. So thanks for this bit of feedback. There's a basic help panel now.

There is an odd mishap, when you are dragging one of the circle handlers, and drag outside of the gridded area, then through the center of the circle. It flips into a corner

I just clicked around on it and figured it out in 10 seconds. Maybe you should not approach new things with prior assumptions.

Reply on news.ycombinator.com