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

31–40 of 57 posts

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

#31

Post by ttoinou »

panzerboiler wrote: post #25
ttoinou wrote: post #22

Earlier quoted context omitted.

The person you're answering to is not suggesting interpolating curves. Piecewise quadratic bezier curves are very local, two quadratic bezier curves can approximate well a 3rd degree bezier curve

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

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

#32

Post by ajs1998 »

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 ?

Maybe not exactly what you're looking for, but this video is excellent. And her other video on Splines is also great.

https://www.youtube.com/watch?v=aVwxzDHniEw

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

#33

Post by stuaxo »

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)

Oh, that's definitely interesting - would be good for creative coding.

I could do with python bindings for this.

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

#37

Post by meindnoch »

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)

"The boolean operations are implemented using a graph-based approach. After the parsing the input, self-intersecting cubic beziers curves are simplified. Then the intersection points between all edges are calculated. These are then turned into a graph representation where every intersection becomes a new vertex. We then apply edge contractions to remove vertices with a degree of 2 to compute the graph minor. At this stage, identical edges are deduplicated. Because we are ultimately interested in the faces of the graph to decide if they should be included in the final output, we then compute the dual graph in which the faces become vertices and vertices become the new faces. That dual structure is then used to determine which faces (dual vertices) should be included in the final output."

This would be such a pain in the ass to implement with good precision and performance.

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

#38

Post by junon »

ajs1998 wrote: post #32
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 ?

Maybe not exactly what you're looking for, but this video is excellent. And her other video on Splines is also great. https://www.youtube.com/watch?v=aVwxzDHniEw

+1, Freya's courses are always awesome.

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

#39

Post by CyLith »

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. a Bernstein basis, there are often much faster and stable tailored methods working solving for the eigenvalues of a companion matrix of a different form.

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

#40

Post by ttd »

ttoinou wrote: post #23
ttd wrote: post #14

Earlier quoted context omitted.

If you're not restricted to Bezier for graphics (it's a very common choice as the path primitive for vector graphics), there are other classes of curves that you may find are a better fit. In particular, I think animations typically feel better if they move at constant speed - which is nontrivial with Bezier curves because they do not have an exact closed-form arc length parameterization. Something like pythagorean h…

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 other curve types IMO.
Post reply on HN