Deconstructing Bézier Curves(blog.pkh.me)
blog.pkh.me
Deconstructing Bézier Curves
http://blog.pkh.me/p/33-deconstructing-be%CC%81zier-curves.html
36 comments
And when you've got the concepts, some fairly readable GPLed code is here:
https://github.com/solvespace/solvespace/blob/master/src/srf...
It used to culminate in a function for finding a point at the intersection of 3 rational Bezier surfaces, but we had to add something less exciting at the end.
https://github.com/solvespace/solvespace/blob/master/src/srf...
It used to culminate in a function for finding a point at the intersection of 3 rational Bezier surfaces, but we had to add something less exciting at the end.
this video: https://www.youtube.com/watch?v=aVwxzDHniEw is quite instructive as well...
Yes it's a great video, my contribution is modest in comparison. Watching it again it appears some information unsurprisingly overlap (typically the lerp/mix thing!), but I think I’m still covering different aspects of it.
Is there a way to perform direct Bézier-path intersection, union and difference operations?
I lately tried to find some options for a hobby project. The only way I could find was to first break the path into a lot of line segments, then do the logical operations between paths and finally convert them back by trying to fit Bézier curves into the resulting line segments.
Conversions back and forth seem less than optimal and can lead to artefacts. There must be a better way.
I lately tried to find some options for a hobby project. The only way I could find was to first break the path into a lot of line segments, then do the logical operations between paths and finally convert them back by trying to fit Bézier curves into the resulting line segments.
Conversions back and forth seem less than optimal and can lead to artefacts. There must be a better way.
You didn't say which language you're using. If you're interested in Rust, I wrote a crate which deals with a bunch of bezier operations, including boolean path operations: https://docs.rs/flo_curves/latest/flo_curves/bezier/path/ind...
The 'better way' you're talking about here is the curve clipping algorithm, my version of which is here: https://docs.rs/flo_curves/latest/flo_curves/bezier/fn.curve...
Finding the intersections between individual curves is only the first part of this operation: you also need a way to determine which edges are on the outside of the new path (flo_curves uses raycasting for this, same operation that the OP focuses on, essentially) and deal with a fairly large pile of edge cases - literally edge cases here. Things like overlapping edges, nearly overlapping edges, what happens if a ray passes through an intersection point or directly across a straight edge, precision issues, curves with loops, etc.
The 'better way' you're talking about here is the curve clipping algorithm, my version of which is here: https://docs.rs/flo_curves/latest/flo_curves/bezier/fn.curve...
Finding the intersections between individual curves is only the first part of this operation: you also need a way to determine which edges are on the outside of the new path (flo_curves uses raycasting for this, same operation that the OP focuses on, essentially) and deal with a fairly large pile of edge cases - literally edge cases here. Things like overlapping edges, nearly overlapping edges, what happens if a ray passes through an intersection point or directly across a straight edge, precision issues, curves with loops, etc.
Rust is fine, C++ is fine. Thanks for the pointers!
I'm working on this as we speak. As as another commenter has mentioned, the "fat line" Bézier clipping algorithm is the current state of the art, but I'm confident at this point I can do better. The weakness of this class of algorithms is when two curves are very close to each other, then they keep subdividing. Another major challenge is numerical stability - getting a guarantee that no two curve segments in the output cross is tricky and requires careful definition of what correct operation means.
I'd love to work with a more mathematical colleague on the error bounds and so on. Ideally one who knows the way of the land regarding academic publication, as I think even what I have now is publishable.
Another good implementation to be aware of is Skia path ops[1], used quite a bit in production, including fonts.
[1]: https://skia.org/docs/dev/present/pathops/
I'd love to work with a more mathematical colleague on the error bounds and so on. Ideally one who knows the way of the land regarding academic publication, as I think even what I have now is publishable.
Another good implementation to be aware of is Skia path ops[1], used quite a bit in production, including fonts.
[1]: https://skia.org/docs/dev/present/pathops/
Numerical stability is a nightmare for the winding number algorithm. I've spent about 2 years on it already, but I believe I've managed to make it work. I used the paper from Eric Lengyel which worked it out with quadratic and extended it to cubics. I kept the topology classification strategy, but had to work out a different solution for the analytical resolution stitching. I'm planning to write about it; this serie of math articles are actually building up the foundations I need to explain it.
I'd be happy to discuss it though.
I'd be happy to discuss it though.
Yes, very happy to discuss; my email is raph.levien at the mail service operated by Google.
I think my approach may be less difficult, as it's based on accepting numerical errors when curves are within epsilon of each other. Thus, a lot of the guts of my algorithm is computing bounds and geometric intervals (adapting some ideas from North's master's thesis[1]). I'm I'm not yet convinced that precise orientation is even possible with cubics.
[1]: https://scholarsarchive.byu.edu/cgi/viewcontent.cgi?article=...
I think my approach may be less difficult, as it's based on accepting numerical errors when curves are within epsilon of each other. Thus, a lot of the guts of my algorithm is computing bounds and geometric intervals (adapting some ideas from North's master's thesis[1]). I'm I'm not yet convinced that precise orientation is even possible with cubics.
[1]: https://scholarsarchive.byu.edu/cgi/viewcontent.cgi?article=...
If you still have the original paths, mustn't[0] "in" and "out" alternate?
[0] assuming intersection multiplicity degeneracy is handled elsewhere, but maybe not having to do that is what winding number provides?
[0] assuming intersection multiplicity degeneracy is handled elsewhere, but maybe not having to do that is what winding number provides?
This is exactly the hard part. If you have an intersection of even multiplicity, then they won't alternate. In addition, when you're using these things for path intersection, you also want to be notified of "near misses", because adding floating point roundoff could make these curves intersect even if the exact input doesn't.
> I'm working on this as we speak.
Cool! Is it going to be a part of Skia or something Google internal?
Cool! Is it going to be a part of Skia or something Google internal?
The first implementation will be in the kurbo codebase, in Rust, permissively licensed. If it works out as well as I'd like, the code will be only moderately complex, which I hope means others can implement the ideas without too much difficulty as well.
including fonts is a big recommendation, as they are often chock full of tangencies.
paper.js has a decent implementation for boolean path operations. It uses fat line clipping for finding the intersections between two Bézier curves. Here is the research paper that describes the algorithm:
http://nishitalab.org/user/nis/cdrom/cad/CAGD90Curve.pdf
http://nishitalab.org/user/nis/cdrom/cad/CAGD90Curve.pdf
Skia includes a module for path operations: https://github.com/google/skia/blob/main/include/pathops/SkP...
The "Concrete use case: intersecting ray" section implies that it might be reasonable to do logical ops by first intersecting each Bézier-represented curve against the segment-representation of the other, then stitching together the Bézier-represented boundaries of what remains. (with the last step made fiddly by the fact that calculated intersection points of A with Segments(B) are likely to only be "reasonably close" to intersection points of Segments(A) with B)
No need to use the segments. Just as you can compute straight line-Bézier intersections by setting them equal and solving the resulting equation, you can compute Bézier-Bézier intersections by setting them equal and solving the resulting equation.
[deleted]
This Bézier primer is really interesting too, one of the best resources if you need to implement anything related to Bézier curves.
https://pomax.github.io/bezierinfo/
I think this is the best reference on Bézier curves on the internet. Comprehensive, but also useful if you need to accomplish a specific task.
I wish the accompanying code was more readable though. There’s a lot of one letter variables and unexplained tricks that are difficult to work out.
I wish the accompanying code was more readable though. There’s a lot of one letter variables and unexplained tricks that are difficult to work out.
What a great resource. Thank you
Stumbled into this world trying to make pretty Sankey diagrams. Offsetting beziers is much more complex than I anticipated.
An at least pretty good solution to computing parallel curves of Béziers is given in [1]. This can give very accurate results with a modest number of segments, using techniques that are fast to evaluate and not terribly complicated. I know it's possible to do better in terms of number of segments, but it's not obvious to me how to make that faster than doing curve fitting and error bounding.
[1]: https://raphlinus.github.io/curves/2021/02/19/parallel-curve...
[1]: https://raphlinus.github.io/curves/2021/02/19/parallel-curve...
Thanks for the reference! The current solutions are a bit scattered around the internet. I wonder if it’s worth making a collection and comparison of approaches
How did that go? Making your own Sankey diagrams? Was it to learn or did you have another take on how they should be rendered.
Ohhh, did you animate them? Were you rendering to SVG?
Ohhh, did you animate them? Were you rendering to SVG?
Making basic sankey diagrams with SVG is pretty easy but I have complex requirements that mean I can’t use a single path and thus can’t utilize the browsers stroking logic anymore.
I am curious of the domain and your Sankey advancement! Do they terminate at a multilevel object? Alpha blending? Dynamically updating?
Inquiring minds want to know.
Inquiring minds want to know.
Without providing too much context (would take a while), I need more visual control than than what a SVG path can provide. Browsers are also inconsistent with how they handle sharp bends, which can cause artifacts in some cases. Essentially each edge in a graph im displaying is a sankey diagram.
Oh cool, I think I get it. It is like a Pachinko Stankey. Or an output sum attribution graph.
https://www.youtube.com/watch?v=7RTg89WEsXQ
https://www.youtube.com/watch?v=7RTg89WEsXQ
Also relevant: Dividing Bezier Curves Into Two Equal Halves
https://stackoverflow.com/questions/18655135/divide-bezier-c...
what is most interesting to me about bezier curves is how they introduce a 'time' parameter.
referring to how they switch from two coordiates (function arguments) into just the one 'time' argument.
this is most clear in Bartosz Cieachanowski explanation.
then the whole topic gets really going when they add multiple lines all parametrized with the one 'time' argument.
referring to how they switch from two coordiates (function arguments) into just the one 'time' argument.
this is most clear in Bartosz Cieachanowski explanation.
then the whole topic gets really going when they add multiple lines all parametrized with the one 'time' argument.
This sort of calculation, where you map t → (x,y) is normally covered in Calc 3, along with how to rewrite r(t) to r(s) where s is a distance parameter rather than a time parameter which can be useful if you’re plotting the Bézier as individual points rather than as line segments.
- Curves and Surfaces by Bartosz Ciechanowski: https://ciechanow.ski/curves-and-surfaces/ (His whole site is a treasure trove of incredible explanations!)
- Primer on Bézier Curves: https://pomax.github.io/bezierinfo/