13 ms·

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

226 points by jarek-foksa 1y ago

Syzygies 1y ago
I'm hoping to code Bezier animation in OCaml/F# in four dimensional space time, with a moving vantage point. Offload rendering each time slice frame to worker threads. I'm surprised Bezier-rs is all about curves. Sure, fonts, but I can't be alone here in seeing curves as a special case. It's easy as a pure mathematician to write off Bezier theory as "specialized" but it's simply the right way to work with polynomials on a simplex.
- ttd 1y ago
  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 hodographs could be a better fit for your application. I am not a mathematician though, so if you have other insight I'd be glad to hear it.
  - ttoinou 1y ago
    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
    - ttd 1y ago
      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.
      - ttoinou 1y ago
        Great, I'm looking at P-H and it's very interesting and useful
shmerl 1y ago
Is the documentation using the library itself for visualizations?
- LoganDark 1y ago
  Yep, WASM
  - Nicole9 1y ago
    Wasm in the browser?
    - formerly_proven 1y ago
      wasm = WebAssembly = a simple stack-based VM with one flat heap for memory.
      - bravesoul2 1y ago
        Sure... but people are running Wasm on the server side too so fair question.
        tialaramex 1y ago
        Barely, this is Rust, so if you're on a server you can just... use that already ?
  - shmerl 1y ago
    That's neat!
continuational 1y ago
Very neat. I'm not sure if I missed it, but is there any way to get n equidistant points on the curve? E.g. for moving an object at constant speed along the curve.
- jamwaffles 1y ago
  There is indeed: Bezier::compute_lookup_table[1]. You'll want to use a `TValueType` of `Euclidean` to get equidistant points. [1]: https://docs.rs/bezier-rs/latest/bezier_rs/struct.Bezier.html#method.compute_lookup_table https://docs.rs/bezier-rs/latest/bezier_rs/struct.Bezier.htm...
pjmlp 1y ago
Great example, this is the kind of stuff that we could make use of interactive documents for, and not bend them into applications.
Fraterkes 1y ago
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 https://github.com/r-flash/PathBool.js) in Rust) https://github.com/GraphiteEditor/Graphite/tree/master/libraries/path-bool 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)
- QuantumNomad_ 1y ago
  Link to the code for the mentioned Rust path-bool crate: https://github.com/GraphiteEditor/Graphite/tree/master/libraries/path-bool https://github.com/GraphiteEditor/Graphite/tree/master/libra...
  - tonyedgecombe 1y ago
    Interesting, I’m writing some code to find the interception of two clipping paths at the moment. I can’t use this because I have a no dependency rule but will take a look.
    - Fraterkes 1y ago
      In case you end up coming up with your own solution: this is one of the best collections of info for what is currently out there Ive seen: https://github.com/linebender/kurbo/issues/277 https://github.com/linebender/kurbo/issues/277
- stuaxo 1y ago
  Oh, that's definitely interesting - would be good for creative coding. I could do with python bindings for this.
- meindnoch 1y ago
  "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.
childintime 1y ago
Bezier curves in painting software never gave me the results I wanted. And I mean never. I sincerely wonder who succeeds at using them? From these graphs I see that I always wanted the simple Quadratic version, and would use 2 of them in sequence to approximate a Cubic version. That would be so much easier. But if the software could allow me to adjust the midpoint, and maintain a smooth transition, that would be perfect. I think. So I basically wish for a different interface, one that has more thought put into it. Now it's a "give access to the parameters, and be done with it" kind. As if novices don't have the need for a nice smooth curve between known points.
- panzerboiler 1y ago
  A Bézier curve is not an interpolating spline. It is a parametric curve defined by a set of control points, which the curve typically does not pass through (except the first and last points). Bézier curves exhibit local control (changing a control point influences only a portion of the curve, especially in piecewise Bézier constructions). Interpolating splines may seem more user-friendly at first, since the curve passes exactly through all the given points. However, this can lead to unintuitive behavior: modifying a single point can cause global changes in the curve, including in areas far from the edited point. In some cases, these changes can be drastic, making precise control difficult or impossible. I may be biased by my 20+ years of graphic design work, but I prefer the precision and control given by Bézier curves.
  - ttoinou 1y ago
    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
    - panzerboiler 1y ago
      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.
__jonas 1y ago
This looks really nice! I’m currently looking for a nice implementation of stroke expansion (here called outlining) that I can run in the browser, this seems like a good option besides skia (pathkit)[0] and vello/kurbo[1]. Ideally I’d love to be able to expand in a non-uniform way, similar to what Metafont does for bitmap fonts, or what Inkscape allows with its power stroke effect, or even just with a non-uniform ‘nib’ as is possible with FontForge[2]. This doesn’t seem to be something that these bezier libraries generally offer which is understandable, probably a rather niche goal. [0] https://skia.org/docs/user/modules/pathkit/ https://skia.org/docs/user/modules/pathkit/ [1] https://doc.servo.org/kurbo/stroke/index.html https://doc.servo.org/kurbo/stroke/index.html [2] https://fontforge.org/docs/techref/stroke.html https://fontforge.org/docs/techref/stroke.html
graphviz 1y ago
Any ideas how these primitives could be used to implement an edge router for drawing natural-looking curves around obstacles in diagrams, as an improvement on the 25-year-old solver in graphviz https://dpd.cs.princeton.edu/Papers/DGKN97.pdf https://dpd.cs.princeton.edu/Papers/DGKN97.pdf?
phkahler 1y ago
If they could extend it to rational Beziers it might be useful for CAD applications. We have a subset of these in C++ as the core of Solvespace. This is one of my favorite source files: https://github.com/solvespace/solvespace/blob/master/src/srf/ratpoly.cpp https://github.com/solvespace/solvespace/blob/master/src/srf...
viggity 1y ago
Anytime béziers are mentioned on HN, I feel compelled to share these absolutely incredible videos from Freya Holmér https://www.youtube.com/watch?v=jvPPXbo87ds https://www.youtube.com/watch?v=jvPPXbo87ds (73 minutes) https://www.youtube.com/watch?v=aVwxzDHniEw https://www.youtube.com/watch?v=aVwxzDHniEw (24 minutes)
nartho 1y ago
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 ?
- ajs1998 1y ago
  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 https://www.youtube.com/watch?v=aVwxzDHniEw
  - junon 1y ago
    +1, Freya's courses are always awesome.
- llimllib 1y ago
  Pomax's primer on bézier curves is the reference they used: https://pomax.github.io/bezierinfo/ 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?
LegionMammal978 1y ago
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?
- CyLith 1y ago
  The library only solves up to cubic equations, and the comments have a link to the following page: https://momentsingraphics.de/CubicRoots.html 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 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.
  - LegionMammal978 1y ago
    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/libraries/bezier-rs/src/symmetrical_basis.rs#L449 https://github.com/GraphiteEditor/Graphite/blob/master/libra...
    - bjornsing 1y ago
      Reference sounds interesting but I’m getting 404 there.
      - LegionMammal978 1y ago
        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 https://github.com/GraphiteEditor/Graphite/pull/3031 [1] https://crates.io/crates/poly-cool https://crates.io/crates/poly-cool [2] https://github.com/GraphiteEditor/Graphite/blob/beb1c6ae64897490819485c711b0f4fcaf97f5ca/libraries/bezier-rs/src/symmetrical_basis.rs#L449 https://github.com/GraphiteEditor/Graphite/blob/beb1c6ae6489...
brcmthrowaway 1y ago
If only you could make a perfect circle out of bezier curves.. then P=NP
- Sharlin 1y ago
  With rational Bézier curves you can!
neutronicus 1y ago
I'm particularly impressed with the Offsetting - very nice looking library.
sciencesama 1y ago
https://www.youtube.com/shorts/dFpkZiU4ptQ https://www.youtube.com/shorts/dFpkZiU4ptQ
throw10920 1y ago
Is there anything interesting about this package beyond the fact that it's written in Rust?
aquarin 1y ago
"The library is now deprecated and has been archived in this repository" "Graphite has moved to Kurbo as of 2025,"

226 points by jarek-foksa 1y ago

I'm hoping to code Bezier animation in OCaml/F# in four dimensional space time, with a moving vantage point. Offload rendering each time slice frame to worker threads. I'm surprised Bezier-rs is all about curves. Sure, fonts, but I can't be alone here in seeing curves as a special case. It's easy as a pure mathematician to write off Bezier theory as "specialized" but it's simply the right way to work with polynomials on a simplex.

ttd 1y ago
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 hodographs could be a better fit for your application. I am not a mathematician though, so if you have other insight I'd be glad to hear it.
- ttoinou 1y ago
  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
  - ttd 1y ago
    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.
    - ttoinou 1y ago
      Great, I'm looking at P-H and it's very interesting and useful

shmerl 1y ago

Is the documentation using the library itself for visualizations?

LoganDark 1y ago
Yep, WASM
- Nicole9 1y ago
  Wasm in the browser?
  - formerly_proven 1y ago
    wasm = WebAssembly = a simple stack-based VM with one flat heap for memory.
    - bravesoul2 1y ago
      Sure... but people are running Wasm on the server side too so fair question.
      - tialaramex 1y ago
        Barely, this is Rust, so if you're on a server you can just... use that already ?
- shmerl 1y ago
  That's neat!

continuational 1y ago

Very neat. I'm not sure if I missed it, but is there any way to get n equidistant points on the curve? E.g. for moving an object at constant speed along the curve.

jamwaffles 1y ago
There is indeed: Bezier::compute_lookup_table[1]. You'll want to use a `TValueType` of `Euclidean` to get equidistant points. [1]: https://docs.rs/bezier-rs/latest/bezier_rs/struct.Bezier.html#method.compute_lookup_table https://docs.rs/bezier-rs/latest/bezier_rs/struct.Bezier.htm...

pjmlp 1y ago

Great example, this is the kind of stuff that we could make use of interactive documents for, and not bend them into applications.

Fraterkes 1y ago

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 https://github.com/r-flash/PathBool.js) in Rust) https://github.com/GraphiteEditor/Graphite/tree/master/libraries/path-bool 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)

QuantumNomad_ 1y ago
Link to the code for the mentioned Rust path-bool crate: https://github.com/GraphiteEditor/Graphite/tree/master/libraries/path-bool https://github.com/GraphiteEditor/Graphite/tree/master/libra...
- tonyedgecombe 1y ago
  Interesting, I’m writing some code to find the interception of two clipping paths at the moment. I can’t use this because I have a no dependency rule but will take a look.
  - Fraterkes 1y ago
    In case you end up coming up with your own solution: this is one of the best collections of info for what is currently out there Ive seen: https://github.com/linebender/kurbo/issues/277 https://github.com/linebender/kurbo/issues/277
stuaxo 1y ago
Oh, that's definitely interesting - would be good for creative coding. I could do with python bindings for this.
meindnoch 1y ago
"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.

childintime 1y ago

Bezier curves in painting software never gave me the results I wanted. And I mean never. I sincerely wonder who succeeds at using them? From these graphs I see that I always wanted the simple Quadratic version, and would use 2 of them in sequence to approximate a Cubic version. That would be so much easier. But if the software could allow me to adjust the midpoint, and maintain a smooth transition, that would be perfect. I think. So I basically wish for a different interface, one that has more thought put into it. Now it's a "give access to the parameters, and be done with it" kind. As if novices don't have the need for a nice smooth curve between known points.

panzerboiler 1y ago
A Bézier curve is not an interpolating spline. It is a parametric curve defined by a set of control points, which the curve typically does not pass through (except the first and last points). Bézier curves exhibit local control (changing a control point influences only a portion of the curve, especially in piecewise Bézier constructions). Interpolating splines may seem more user-friendly at first, since the curve passes exactly through all the given points. However, this can lead to unintuitive behavior: modifying a single point can cause global changes in the curve, including in areas far from the edited point. In some cases, these changes can be drastic, making precise control difficult or impossible. I may be biased by my 20+ years of graphic design work, but I prefer the precision and control given by Bézier curves.
- ttoinou 1y ago
  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
  - panzerboiler 1y ago
    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.

__jonas 1y ago

This looks really nice! I’m currently looking for a nice implementation of stroke expansion (here called outlining) that I can run in the browser, this seems like a good option besides skia (pathkit)[0] and vello/kurbo[1]. Ideally I’d love to be able to expand in a non-uniform way, similar to what Metafont does for bitmap fonts, or what Inkscape allows with its power stroke effect, or even just with a non-uniform ‘nib’ as is possible with FontForge[2]. This doesn’t seem to be something that these bezier libraries generally offer which is understandable, probably a rather niche goal. [0] https://skia.org/docs/user/modules/pathkit/ https://skia.org/docs/user/modules/pathkit/ [1] https://doc.servo.org/kurbo/stroke/index.html https://doc.servo.org/kurbo/stroke/index.html [2] https://fontforge.org/docs/techref/stroke.html https://fontforge.org/docs/techref/stroke.html

graphviz 1y ago

Any ideas how these primitives could be used to implement an edge router for drawing natural-looking curves around obstacles in diagrams, as an improvement on the 25-year-old solver in graphviz https://dpd.cs.princeton.edu/Papers/DGKN97.pdf https://dpd.cs.princeton.edu/Papers/DGKN97.pdf?

phkahler 1y ago

If they could extend it to rational Beziers it might be useful for CAD applications. We have a subset of these in C++ as the core of Solvespace. This is one of my favorite source files: https://github.com/solvespace/solvespace/blob/master/src/srf/ratpoly.cpp https://github.com/solvespace/solvespace/blob/master/src/srf...

viggity 1y ago

Anytime béziers are mentioned on HN, I feel compelled to share these absolutely incredible videos from Freya Holmér https://www.youtube.com/watch?v=jvPPXbo87ds https://www.youtube.com/watch?v=jvPPXbo87ds (73 minutes) https://www.youtube.com/watch?v=aVwxzDHniEw https://www.youtube.com/watch?v=aVwxzDHniEw (24 minutes)

nartho 1y ago

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 ?

ajs1998 1y ago
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 https://www.youtube.com/watch?v=aVwxzDHniEw
- junon 1y ago
  +1, Freya's courses are always awesome.
llimllib 1y ago
Pomax's primer on bézier curves is the reference they used: https://pomax.github.io/bezierinfo/ 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?

LegionMammal978 1y ago

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?

CyLith 1y ago
The library only solves up to cubic equations, and the comments have a link to the following page: https://momentsingraphics.de/CubicRoots.html 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 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.
- LegionMammal978 1y ago
  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/libraries/bezier-rs/src/symmetrical_basis.rs#L449 https://github.com/GraphiteEditor/Graphite/blob/master/libra...
  - bjornsing 1y ago
    Reference sounds interesting but I’m getting 404 there.
    - LegionMammal978 1y ago
      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 https://github.com/GraphiteEditor/Graphite/pull/3031 [1] https://crates.io/crates/poly-cool https://crates.io/crates/poly-cool [2] https://github.com/GraphiteEditor/Graphite/blob/beb1c6ae64897490819485c711b0f4fcaf97f5ca/libraries/bezier-rs/src/symmetrical_basis.rs#L449 https://github.com/GraphiteEditor/Graphite/blob/beb1c6ae6489...

brcmthrowaway 1y ago

If only you could make a perfect circle out of bezier curves.. then P=NP

Sharlin 1y ago
With rational Bézier curves you can!

neutronicus 1y ago

I'm particularly impressed with the Offsetting - very nice looking library.

sciencesama 1y ago

https://www.youtube.com/shorts/dFpkZiU4ptQ https://www.youtube.com/shorts/dFpkZiU4ptQ

throw10920 1y ago

Is there anything interesting about this package beyond the fact that it's written in Rust?

aquarin 1y ago

"The library is now deprecated and has been archived in this repository" "Graphite has moved to Kurbo as of 2025,"