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.
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.
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:
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.
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.
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.
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.
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.
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.
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/
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.
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.
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.
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.
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
It's just a parameter and thinking of it as time is not helpful. When you get to Bezier surfaces they have 2 such parameters often called U and V. Thinking of it as time breaks down then.
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.
36 comments
[ 3.0 ms ] story [ 89.4 ms ] threadI 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.
http://nishitalab.org/user/nis/cdrom/cad/CAGD90Curve.pdf
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.
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 be happy to discuss it though.
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=...
[0] assuming intersection multiplicity degeneracy is handled elsewhere, but maybe not having to do that is what winding number provides?
Cool! Is it going to be a part of Skia or something Google internal?
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.
- 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/
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.
Ohhh, did you animate them? Were you rendering to SVG?
Inquiring minds want to know.
https://www.youtube.com/watch?v=7RTg89WEsXQ
[1]: https://raphlinus.github.io/curves/2021/02/19/parallel-curve...
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.