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)
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.
"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.
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.
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
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.
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:
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.
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.
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.
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?
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 ?
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?
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.
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.)
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.
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.
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.
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
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.
Users can specify them by three points on the perimeter, by tangents at endpoints (up to 180deg of course), with various other conveniences (you can place two tangent arc or bezier vertices in a row and create an implicit g1 interface between the two arc / bezier segments).
Constraint solvers are good at circles and you can offset them analytically so they make a lot of sense for CAD.
I can't really say this rigorously but I also think that Bezier segments and circle segments are good "partners" for approximating smooth curves - each has just enough degrees of freedom for you to require g1 continuity between them, one of them always has constant non-zero curvature, the other cannot have constant non-zero curvature, and the locality aspect matches the intuition of a human operator.
If you just do a start/end point it will create a cubic with 2 endpoints and 2 control points. But if you drop a whole series of points (up to 12 I think) it will create a curve that passes though all of them. This is done by internally creating a bunch of cubic splines where the control points are automatically positioned and not shown. You still get 2 control points for the derivatives at the ends, unless you create a closed loop.
- put nodes at extrema and points of inflection (extreme left/right, top/bottom, middle of _S_ curve)
- rule of 30 --- off curve nodes should be ~30% away from the matching on curve node for smoothest appearance unless the shape one is trying to achieve dictates a different placement
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.
"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.
Link to the code for the mentioned Rust path-bool crate:
https://github.com/GraphiteEditor/Graphite/tree/master/libra...
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.
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
Oh, that's definitely interesting - would be good for creative coding.
I could do with python bindings for this.
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/
[1] https://doc.servo.org/kurbo/stroke/index.html
[2] https://fontforge.org/docs/techref/stroke.html
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 (73 minutes)
https://www.youtube.com/watch?v=aVwxzDHniEw (24 minutes)
Great example, this is the kind of stuff that we could make use of interactive documents for, and not bend them into applications.
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...
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.
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.
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.
Great, I'm looking at P-H and it's very interesting and useful
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?
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.
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.htm...
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.
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?
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.
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...
Interesting, thanks!
https://www.youtube.com/shorts/dFpkZiU4ptQ
Is the documentation using the library itself for visualizations?
Yep, WASM
Wasm in the browser?
wasm = WebAssembly = a simple stack-based VM with one flat heap for memory.
Sure... but people are running Wasm on the server side too so fair question.
Barely, this is Rust, so if you're on a server you can just... use that already ?
That's neat!
Is there anything interesting about this package beyond the fact that it's written in Rust?
I'm particularly impressed with the Offsetting - very nice looking library.
If only you could make a perfect circle out of bezier curves.. then P=NP
With rational Bézier curves you can!
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.
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.
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
That's it, thank you for discussing this.
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.
Interesting. Arc segments are arc circles ?
Yep, subsets of circles.
Users can specify them by three points on the perimeter, by tangents at endpoints (up to 180deg of course), with various other conveniences (you can place two tangent arc or bezier vertices in a row and create an implicit g1 interface between the two arc / bezier segments).
Constraint solvers are good at circles and you can offset them analytically so they make a lot of sense for CAD.
I can't really say this rigorously but I also think that Bezier segments and circle segments are good "partners" for approximating smooth curves - each has just enough degrees of freedom for you to require g1 continuity between them, one of them always has constant non-zero curvature, the other cannot have constant non-zero curvature, and the locality aspect matches the intuition of a human operator.
Thanks ! I don't think Offsets are straightforward (closed form equation) with Bezier but it can be approximated
You might like the spline tool in Solvespace:
https://solvespace.com/
If you just do a start/end point it will create a cubic with 2 endpoints and 2 control points. But if you drop a whole series of points (up to 12 I think) it will create a curve that passes though all of them. This is done by internally creating a bunch of cubic splines where the control points are automatically positioned and not shown. You still get 2 control points for the derivatives at the ends, unless you create a closed loop.
Now that's the UI people like me need.
A markedly different UI is that of FutureWave SmartSketch which has been reimplemented in
https://www.wickeditor.com/
For Beziér curves remember the basics:
- put nodes at extrema and points of inflection (extreme left/right, top/bottom, middle of _S_ curve)
- rule of 30 --- off curve nodes should be ~30% away from the matching on curve node for smoothest appearance unless the shape one is trying to achieve dictates a different placement