Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Bezier-rs – algorithms for Bézier segments and shapes

graphite.rs

Post reply on HN
Print view View original

41–50 of 57 posts

Re: Bezier-rs – algorithms for Bézier segments and shapes

#41

Post by LegionMammal978 »

CyLith wrote: post #39
LegionMammal978 wrote: post #34

This library has a very interesting algorithm for computing the curve point closest to a given point, seemingly based on a root-finder that doesn't need any complex numbers. Does anyone know of any resources about such an algorithm?

The library only solves up to cubic equations, and the comments have a link to the following page: https://momentsingraphics.de/CubicRoots.html For general polynomials, it matters a great deal in what basis it is represented. The typical monomial basis is usually not the best from a numerical standpoint. I am aware of some modern methods such as this: https://arxiv.org/pdf/1611.02435 For polynomials expressed in e.g.…

That doesn't sound right, nearest-point queries for cubic Béziers take at least a quintic solver, and this library uses a subdivision-based algorithm with Bernstein polynomials that is seemingly designed to work with any degree [0]. (Or at least, it doesn't have any code that complains when the degree is too large.)

[0] https://github.com/GraphiteEditor/Graphite/blob/master/libra...

Re: Bezier-rs – algorithms for Bézier segments and shapes

#43

Post by llimllib »

nartho wrote: post #30

So this is a long shot but, as a software engineer lacking in the math department who has slowly been trying to improve calculus and geometry, what are some good resources/requirements to get to a point where I can implement something like that ?

Pomax's primer on bézier curves is the reference they used: https://pomax.github.io/bezierinfo/

They do a pretty good job introducing the mathematics gently I think. But maybe work backwards from whatever you don't understand?

Re: Bezier-rs – algorithms for Bézier segments and shapes

#44

Post by neutronicus »

ttoinou wrote: post #31
panzerboiler wrote: post #25

Earlier quoted context omitted.

I probably misunderstood their message. By the way, two quadratic curves can approximate well a tiny subset of what a cubic bezier can represent. The number of quadratics required in the general case can grow quite substantially, very quickly.

You're right we probably need at least 3 quadratic bezier curves to cover most uses cases of 3rd degree bezier curves. (In general, not all shapes of 3rd degree bezier curves are used in the wild, that would lead to too much deformation and impossible paths). But I agree with the OP, artists might only need new tools that use quadratic bezier curves in a different ways

To your point:

I work on a commercial CAD application (architecture space) and we have a Polyline Tool (misnomer) that lets users add quadratic Bezier curves and arc segments and they are not clamoring for anything more than that. There is the ability to specify the quadratic segments by point on curve at t=1/2, and various different ways of specifying arc segments. But this is all just UI, under the hood it's arc segments, line segments, and quadratic Bezier and it seems to meet their needs.

There is also a NURBS curve tool but my impression is that the vast majority of our users just stick with the 2D Polyline.

Re: Bezier-rs – algorithms for Bézier segments and shapes

#45

Post by bjornsing »

LegionMammal978 wrote: post #41
CyLith wrote: post #39

Earlier quoted context omitted.

The library only solves up to cubic equations, and the comments have a link to the following page: https://momentsingraphics.de/CubicRoots.html For general polynomials, it matters a great deal in what basis it is represented. The typical monomial basis is usually not the best from a numerical standpoint. I am aware of some modern methods such as this: https://arxiv.org/pdf/1611.02435 For polynomials expressed in e.g.…

That doesn't sound right, nearest-point queries for cubic Béziers take at least a quintic solver, and this library uses a subdivision-based algorithm with Bernstein polynomials that is seemingly designed to work with any degree [0]. (Or at least, it doesn't have any code that complains when the degree is too large.) [0] https://github.com/GraphiteEditor/Graphite/blob/master/libra...

Reference sounds interesting but I’m getting 404 there.

Re: Bezier-rs – algorithms for Bézier segments and shapes

#46

Post by LegionMammal978 »

bjornsing wrote: post #45
LegionMammal978 wrote: post #41

Earlier quoted context omitted.

That doesn't sound right, nearest-point queries for cubic Béziers take at least a quintic solver, and this library uses a subdivision-based algorithm with Bernstein polynomials that is seemingly designed to work with any degree [0]. (Or at least, it doesn't have any code that complains when the degree is too large.) [0] https://github.com/GraphiteEditor/Graphite/blob/master/libra...

Reference sounds interesting but I’m getting 404 there.

My apologies, it looks like it was switched over [0] to an external root-finder crate poly-cool [1] soon after I wrote my comment. (I should know better than to link to branches directly, but there weren't any useful tags on the repo, so I got lazy. For reference, I was trying to link to [2].)

Curiously, the poly-cool crate appears to use the monomial basis instead of the Bernstein basis that the old version was using.

[0] https://github.com/GraphiteEditor/Graphite/pull/3031

[1] https://crates.io/crates/poly-cool

[2] https://github.com/GraphiteEditor/Graphite/blob/beb1c6ae6489...

Re: Bezier-rs – algorithms for Bézier segments and shapes

#48

Post by bruckie »

Fraterkes wrote: post #10

Almost even more interesting is the Bezier Boolean-Operations lib they use (it’s a rewrite of Pathbool.js ( https://github.com/r-flash/PathBool.js ) in Rust) https://github.com/GraphiteEditor/Graphite/tree/master/libra... There’s not a ton of robust curve boolean libs out there that aren’t just part of some huge package of tools. This is the only one I know of that isn’t Js. (Edit: added a link)

Kurbo (https://github.com/linebender/kurbo) is another Rust Bézier curve library. It apparently doesn't have boolean operations yet, although https://github.com/linebender/kurbo/issues/277 documents potential work in that direction.

Re: Bezier-rs – algorithms for Bézier segments and shapes

#50

Post by ttoinou »

ttd wrote: post #40
ttoinou wrote: post #23

Earlier quoted context omitted.

Instead of using closed form, they can easily computed with the approximation of the curve with segments, and you place the points where there is most curvature or where the 1st derivative isn't close to zero

Yes - but there are other curve classes (like P-H) that have an exact solution and don't need approximation. Bezier curves have tons of nice properties but also a lot of shortcomings, for example not being able represent conic sections like circles and ellipses without introducing weighting (rationals), which complicate computations even further. So, depending on what you're doing with them, it's worth exploring othe…

Great, I'm looking at P-H and it's very interesting and useful
Post reply on HN