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.
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.
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.
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:
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.
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/
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
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.
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.
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.
- 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/