5 ms·

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 w

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.

082349872349872 4y ago
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)
- yorwba 4y ago
  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 4y ago
    [deleted]
jansan 4y ago
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
logicalshift 4y ago
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/index.html 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_intersects_curve_clip.html 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.
- vardump 4y ago
  Rust is fine, C++ is fine. Thanks for the pointers!
raphlinus 4y ago
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/ https://skia.org/docs/dev/present/pathops/
- ux 4y ago
  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.
  - raphlinus 4y ago
    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=2206&context=etd https://scholarsarchive.byu.edu/cgi/viewcontent.cgi?article=...
  - 082349872349872 4y ago
    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?
dazilcher 4y ago
Skia includes a module for path operations: https://github.com/google/skia/blob/main/include/pathops/SkPathOps.h https://github.com/google/skia/blob/main/include/pathops/SkP...

082349872349872 4y ago

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)

yorwba 4y ago
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 4y ago
  [deleted]

jansan 4y ago

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

logicalshift 4y ago

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/index.html 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_intersects_curve_clip.html 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.

vardump 4y ago
Rust is fine, C++ is fine. Thanks for the pointers!

raphlinus 4y ago

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/ https://skia.org/docs/dev/present/pathops/

ux 4y ago
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.
- raphlinus 4y ago
  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=2206&context=etd https://scholarsarchive.byu.edu/cgi/viewcontent.cgi?article=...
- 082349872349872 4y ago
  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?

dazilcher 4y ago

Skia includes a module for path operations: https://github.com/google/skia/blob/main/include/pathops/SkPathOps.h https://github.com/google/skia/blob/main/include/pathops/SkP...