[HN Gopher] Bezier-rs - algorithms for Bezier segments and shapes
___________________________________________________________________
Bezier-rs - algorithms for Bezier segments and shapes
Author : jarek-foksa
Score : 210 points
Date : 2025-08-09 14:33 UTC (4 days ago)
(HTM) web link (graphite.rs)
(TXT) w3m dump (graphite.rs)
| Syzygies wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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.
| shmerl wrote:
| Is the documentation using the library itself for visualizations?
| LoganDark wrote:
| Yep, WASM
| Nicole9 wrote:
| Wasm in the browser?
| formerly_proven wrote:
| wasm = WebAssembly = a simple stack-based VM with one flat
| heap for memory.
| bravesoul2 wrote:
| Sure... but people are running Wasm on the server side
| too so fair question.
| tialaramex wrote:
| Barely, this is Rust, so if you're on a server you can
| just... use that already ?
| shmerl wrote:
| That's neat!
| continuational wrote:
| 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 wrote:
| 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...
| pjmlp wrote:
| Great example, this is the kind of stuff that we could make use
| of interactive documents for, and not bend them into
| applications.
| Fraterkes wrote:
| 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)
| QuantumNomad_ wrote:
| Link to the code for the mentioned Rust path-bool crate:
|
| https://github.com/GraphiteEditor/Graphite/tree/master/libra...
| tonyedgecombe wrote:
| 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 wrote:
| 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
| stuaxo wrote:
| Oh, that's definitely interesting - would be good for creative
| coding.
|
| I could do with python bindings for this.
| meindnoch wrote:
| _" 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 wrote:
| 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 wrote:
| A Bezier 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). Bezier curves exhibit local control (changing a
| control point influences only a portion of the curve,
| especially in piecewise Bezier 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 Bezier curves.
| ttoinou wrote:
| 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 wrote:
| 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.
| ttoinou wrote:
| 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
| neutronicus wrote:
| 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.
| WillAdams wrote:
| A markedly different UI is that of FutureWave SmartSketch which
| has been reimplemented in
|
| https://www.wickeditor.com/
|
| For Bezier 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
| phkahler wrote:
| 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.
| __jonas wrote:
| 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
| graphviz wrote:
| 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?
| phkahler wrote:
| 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...
| viggity wrote:
| Anytime beziers are mentioned on HN, I feel compelled to share
| these absolutely incredible videos from Freya Holmer
|
| https://www.youtube.com/watch?v=jvPPXbo87ds (73 minutes)
|
| https://www.youtube.com/watch?v=aVwxzDHniEw (24 minutes)
| nartho wrote:
| 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 wrote:
| 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
| junon wrote:
| +1, Freya's courses are always awesome.
| llimllib wrote:
| Pomax's primer on bezier 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?
| LegionMammal978 wrote:
| 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 wrote:
| 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.
| LegionMammal978 wrote:
| That doesn't sound right, nearest-point queries for cubic
| Beziers 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/li
| bra...
| bjornsing wrote:
| Reference sounds interesting but I'm getting 404 there.
| LegionMammal978 wrote:
| 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/beb1c
| 6ae6489...
| brcmthrowaway wrote:
| If only you could make a perfect circle out of bezier curves..
| then P=NP
| Sharlin wrote:
| With rational Bezier curves you can!
| neutronicus wrote:
| I'm particularly impressed with the Offsetting - very nice
| looking library.
| sciencesama wrote:
| https://www.youtube.com/shorts/dFpkZiU4ptQ
___________________________________________________________________
(page generated 2025-08-13 23:01 UTC)