[HN Gopher] Fitting Cubic Bezier Curves
___________________________________________________________________
Fitting Cubic Bezier Curves
Author : raphlinus
Score : 165 points
Date : 2021-03-13 17:27 UTC (1 days ago)
(HTM) web link (raphlinus.github.io)
(TXT) w3m dump (raphlinus.github.io)
| Voltage wrote:
| 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.
|
| http://www.cemyuksel.com/research/interpolating_splines/a_cl...
|
| https://www.youtube.com/watch?v=pK4zy5OKbHs
| jansan wrote:
| That is some pretty amazing stuff, an presented in an very
| digestible form, which is unusual in this field.
| raphlinus wrote:
| 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 :)
| erichocean wrote:
| 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.
| [deleted]
| jansan wrote:
| 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.
| raphlinus wrote:
| 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.
| layoutIfNeeded wrote:
| Or display the heightmap as a 3D surface?
| The_rationalist wrote:
| It would be nice to see an overview comparison of existing
| software approaches
| https://en.m.wikipedia.org/wiki/Category:Regression_and_curv...
| juanbyrge wrote:
| 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.
| raphlinus wrote:
| 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
| Beziers is something that might be useful even to artists and
| designers as opposed to tool builders.
| FullyFunctional wrote:
| I only skimmed it (so far) but the immediate application that
| intrigued me was G code compression. arcwelder fits points on
| arcs, but Bezier curves would be so much more powerful (I
| don't know if 3D printer firmware currently support that, but
| that's a technicality)
| jacobolus wrote:
| My understanding is that most available CAM tools deal
| exclusively with circle arcs and straight segments.
|
| Personally I don't think cubic Beziers 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.
| chrismorgan wrote:
| 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
| tobmlt wrote:
| 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
| srean wrote:
| That seems a lot of fun. Would love browsing through that code
| eyelidlessness wrote:
| 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!
| jbluepolarbear wrote:
| 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.
| NHQ wrote:
| 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/
| raphlinus wrote:
| 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 Beziers.
| dr_dshiv wrote:
| 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.
| yuretz wrote:
| Have you evaluated something like Frechet distance or one of
| its simplified variations?
| jjgreen wrote:
| Minimise XOR of A, B over all scalings, rotations and
| translations of B?
| vlmutolo wrote:
| 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.
| raphlinus wrote:
| 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.
| PaulHoule wrote:
| 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?
| dahart wrote:
| Oh hey this might solve a problem I've been working on, to
| resample connected strands of Bezier 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?
| raphlinus wrote:
| 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.
| delhanty wrote:
| 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 Beziers. Originally
| published in Chinese in 1989 - Chinese shipbuilding industry
| splines. Maybe of interest? (IIRC you don't reference it in your
| thesis.)
|
| https://twitter.com/delhanty/status/1370618402654461953
|
| In chapter 4, they have a construction for a GC2 Bezier spline
| space curves - pairs of quadratics and cubics.
|
| Generally, they cover a lot of the same material that you do in
| your thesis.
| raphlinus wrote:
| 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.
| delhanty wrote:
| 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/pi
| i/001044...
| raphlinus wrote:
| 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.
| delhanty wrote:
| 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.
|
| Yes.
|
| 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,
|
| https://arxiv.org/a/kurnosenko_a_1.html
| delhanty wrote:
| 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.)
| raphlinus wrote:
| 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.
| delhanty wrote:
| Thanks for those ideas.
___________________________________________________________________
(page generated 2021-03-14 23:02 UTC)