Hacker News new | past | comments | ask | show | jobs | submit login
Fitting Cubic Bézier Curves (raphlinus.github.io)
178 points by raphlinus on March 14, 2021 | hide | past | favorite | 36 comments

This is a really nice to have detailed write up of a common and vexing problem: how best to combine to curves for (insert your problem here).

A few years ago I faced A good many curve splitting and curve join issues when automatically building topologically complex shapes out of simpler bspline primatives — where things had to conform to various layers of constraints along the way.

Seeing something like this could have been helpful!

Ah, and because I can’t help myself, here is a sketch of the things I was building-together for this bspline generation/optimization extravaganza. Eh hem,

I’ve had much fun in related spaces...

Automatic differentiation of B-splines let’s you optimize (Newton style) Bspline curves and surfaces (and if efficiency matters not, higher dimensional bsplines I suppose).

The solver I made allowed you to compose constraints and objectives on the fly, and it would build and solve the newton system for you.

Then I tried it with interval valued control points. That worked too. Plus you get to use, e.g. Brouwer's fixed point theorem and simpler tests to exclude infeasible portions of the space. That was fun, but it needed help getting started when intervals where big. It needed a constraint solver to narrow the space first.

So I made an interval valued constraint solver based on minikanren, extended to handle interval arithmetic of course. Worked beautifully.

As a demo I had it randomly sample the design space (to a point or to a finite interval) 1D at a time, let the constraint solver kill off everything made infeasible by that choice in the other design dimensions, and then sample the next design parameter. Carrying that through the design spec arrived at a random design quickly. Then the newton solver took over and generated the geometry. At that point I realized I didn’t need the interval Newton solver for my problem... the interval constraint solver was good enough and then the real valued Newton solver could finish the job.

(Of course it could also tile the space entirely, but I’d need some fancy compute to get something back for a real problem.)

Lots of fun anyway! I still think i should make something of it, as soon as I have time... ah well

That seems a lot of fun. Would love browsing through that code

I won't pretend to understand the intricacies in your article here, but have you seen this paper / video by Cem Yuksel (University of Utah)....

By my layman understanding the curves discussed in the following paper may be of use.



I have seen it, and agree it's interesting. There's one idea in there that I think is more broadly applicable - circle-like forms when the deflection angles are relatively small, and higher tension (in this case, based on ellipses) as deflections increase.

Whether these particular splines are useful for, eg, font design, I'm not yet sold :)

Holy shit, what a great link! This is what keeps me coming back to the comment section…

If I could gift you 100 point of Karma, I would.

That is some pretty amazing stuff, an presented in an very digestible form, which is unusual in this field.

For the Prior Work, I gave you this reference on Twitter in response to your tweeted question.

>Computational Geometry: Curve and Surface Modeling by Liu Ding-Yuan and Su Buqing - Chapter 2 covers Béziers. Originally published in Chinese in 1989 - Chinese shipbuilding industry splines. Maybe of interest? (IIRC you don't reference it in your thesis.)


In chapter 4, they have a construction for a GC2 Bézier spline space curves - pairs of quadratics and cubics.

Generally, they cover a lot of the same material that you do in your thesis.

Thanks for the reference. I had a quick look now, and I wish I knew about this when I wrote my thesis. For the most part, it seems to cover the standard spline literature (Farin, de Boor, etc), though it goes into more detail than usual about the nonlinear splines.

I didn't find anything in the book about this curve fitting problem specifically, though it's possible I missed it.

You probably didn't.

You seem a concientious author and I thought that, from having read your thesis, you were probably not aware of the book and might like to know about it.

There's interesting material in there on nonlinear splines because its a fairly old book (1989) that summarizes how they used nonlinear splines, biarcs etc in the Chinese shipbuilding industry in the decade or two priot to that.

Particularly, the survey of methods on how to choose free parameter in the biarc is not something you see much these days.

Edit: Interestingly, like you they refer to the "Euler Spiral - rather than "Cornu Spiral" or "Klothid"/"Clothoid". Another name, I see in literature from that era is "LINCE" (Linear Curavture Element) such as in [0].

[0] Two-dimensional curve synthesis using linear curvature elements https://www.sciencedirect.com/science/article/abs/pii/001044...

I'm definitely familiar with biarcs (and did talk about them a little in the thesis) because that's the basis of Ikarus. But generally I'm not a fan of biarcs, I feel Euler spirals can do pretty much anything biarcs can, just more smoothly. The simplicity of the arc as primitive curve has some nice features though, for example the fact that parallel curve is nearly trivial.

Shipbuilding has a long connection with splines, long before digital computation. The Autokon system was built by Even Mehlum in the 60s for the Norwegian shipbuilding industry, and this was a pioneering application of the Euler spiral spline. It's not surprising to learn the Chinese shipbuilding industry was also doing interesting things and engaging with mathematicians such as Liu Ding-Yuan and Su Buqing.

IIRC, in your thesis, the method of approximating Euler spirals is exact at the midpoint and has errors at the end.

Say if instead, one wanted the reverse - an Euler spiral approximation that was exact at the endpoints and was allowed errors in the middle. Do you have any idea of the best method to achieve that?

(So to make it concrete, if one had end points and end tangents that were compatible with fitting a spiral, which should define a unique Euler spiral segment. Let's say it's parameterized by turning angle rather than length.)

I think I understand, you're talking about the numerical integration, right? It's probably something of an academic question because you can just set the error to 1e-9 or whatever, and the convergence of that approximation is so good it doesn't slow you down appreciably.

That said, there are other things you can do. Since the derivatives of an Euler spiral are easy enough to compute analytically, you could do Hermite interpolation with a polynomial of arbitrarily high order. I've worked out how to do it for quintic, which is pretty tractable, but I'm sure it could be done even higher. That definitely meets your stated goal (precise at endpoints, sloppy in the middle), but the order of convergence of a quintic is only moderately good compared to the higher order polynomials in spiro.

Thanks for those ideas.

Fair enough - aware that you're not a fan of biarcs from your thesis.

>The simplicity of the arc as primitive curve has some nice features though, for example the fact that parallel curve is nearly trivial.


Also, IIRC, Alexey Kurnosenko uses them in one of his papers to bound the regions of when it's possible to fit a spiral to end point data,


Actually, they do give a comprehensive analysis of infection points and singularities for the cubic polynomial segment with given endpoints, tangents and magnitudes. There's a diagram of square with some (maybe superficial) similarity to the one in "High Accuracy Geometric Hermite Interpolation".

Chapter III Parametric Cubic Spline Curves

4 A Theorem Concerning Segments of Parametric Cubic Curves

Also, it's based on earlier papers by Su Buqing from around 1977.

Well this probably would have been over my head when I was looking for it (it still is now), but I have a much better ability to take it in after a few months learning how to generate curves for a personal art project (link in profile).

I cheated with SVG filters to get something like the effect I wanted but I’ll definitely be revisiting this to refine it.

Thank you for sharing!

I always admire the visuals you include in your articles. They're informative and simple. Anyone who has tried to create informative and simple graphics knows how deceptively hard it is.

Thanks for noticing and appreciating. It's an iterative process - if you had seen earlier drafts and my notebook, it would be a lot more confusing. I think of it as visual storytelling, and try to pick out the image that explains a certain aspect of the overall narrative. Sometimes it works out pretty well.

One small suggestion: Maybe you can try to change the color scale for your heat maps, so the minima become more visible. It took me a while to understand why the arrows are pointing at those three points, because the colors look all very similar along that "arc". If your color scale was magenta at the minima, it would be much easier to understand.

I'll see if I can do something with this. I kept myself to the viridis color map and just log + clamp because I didn't want to misrepresent the data, but I think you're right.

Or display the heightmap as a 3D surface?

Oh hey this might solve a problem I’ve been working on, to resample connected strands of Bézier curve segments, by splitting and merging the individual segments.

Raph, do you maintain any kind of full path parameter through this process, and if so are there any gotchas or tricks? Are there even any choices you can make? I’m not sure, and I’m asking before thinking about it carefully, so that might be a dumb question. I’m just wondering out loud what happens when merging two segments of different lengths and whether there are any ways to try to preserve roughly the same path parameterization as before merging.

Probably because I’m not very familiar with the prior work, I’m not sure I followed where the area metric came from. Is fitting area a popular way to do this in the prior work, or a recent development, or is that your own new finding?

As far as I know, I'm the first to propose a solution that includes the equal-area constraint as part of the solution, though it is mentioned in the Penner paper as part of the search that led to the saddle point ODF solutions.

The technique should definitely work for path merging, that's a primary motivation. I'm not sure I understand your other questions. It'll probably be clearer when I release some code that implements this algorithm, though I'm not making any promises when that might be.

What do you think about this approach. Given a curve, find the Bezier control points which describe it, using SGD: https://nhq.github.io/beezy/public/

My blog post is basically an angry rant against this kind of technique, though it's polite and civil in tone :) Basically, it's slow because it takes a number of iterations instead of directly calculating the best-matching curve, and it can fall into a local minimum and fail to attain the global optimum in case it's in one of the other two of triplets of similar shapes characteristic of cubic Béziers.

I'm really struggling to find a good Similarity/Distance metric between two vector shapes. E.g., something that would indicate mutual information or edit distance—such that I could quantify the distance between a particular shape instance and a prototypical shape.

In my case, I am trying to quantify the difference in shape between outlines of rock carvings on Stonehenge (purported to be axeheads) and outlines of several different styles of actual bronze age axeheads.

Have you evaluated something like Fréchet distance or one of its simplified variations?

Minimise XOR of A, B over all scalings, rotations and translations of B?

Would using the control points to define the center of mass help solve the s shaped curve issue. Make a polygon defined by the start, end, and control points. Also would then using separation axis theorem on close polygons give enough info for a very accurate, optimized curve blending. This method would probably benefit from a bit of hermite smoothing.

It would be nice to see an overview comparison of existing software approaches https://en.m.wikipedia.org/wiki/Category:Regression_and_curv...

Very interesting article. Got through the first few paragraphs until I got completely lost. This seems like something that should be submitted to an academic journal and OP should be in a research group or academia.

I am currently (as of the first of the year) a research software engineer on the Google Fonts team. I'm doing a bunch of font tools in Rust now, and that gives me an opportunity to revisit classic algorithms and techniques to see if there's a better way to do things than the usual.

I'm sorry you got lost. This particular technique is fairly deeply mathematical, and to really appreciate it I guess you need some grounding in the relevant math as well as familiarity with the curve and geometry concepts. I tried to get the intuition across as much as possible, certainly as opposed to the "wall of greek" I see in a lot of academic papers.

This might well turn into an academic paper - I have as a goal to do one or two of those a year. But I also really wanted to do a blog post because I think this could be useful now, and also because the insight about triplets of similar cubic Béziers is something that might be useful even to artists and designers as opposed to tool builders.

I only skimmed it (so far) but the immediate application that intrigued me was G code compression. arcwelder fits points on arcs, but Bèzier curves would be so much more powerful (I don’t know if 3D printer firmware currently support that, but that’s a technicality)

My understanding is that most available CAM tools deal exclusively with circle arcs and straight segments.

Personally I don't think cubic Béziers per se seem like an especially good CAM primitive, but they are ubiquitous in 2d computer graphics, so they might be convenient for that reason.

I have received the impression (as an outsider) that NURBS get used quite a bit in CAD and CAM too: https://en.wikipedia.org/wiki/Non-uniform_rational_B-spline

I wonder if the difficulty finding solutions that he points out has something to do with how hard it is to make Bezier curves do what u want with a tool like Powerpoint or Illustrator?

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact