Revamp Boolean Operations #761
Comments
|
@lehni I test for overlap before the bezier clip algorithm, because it would return an infinite (or very large) amount of points. The source path is first split into curves that increase in the x direction, so there can be no self overlap. The winding contribution is based on the direction of that segment. |
|
@kuribas we do exactly the same, see here: https://github.com/paperjs/paper.js/blob/develop/src/path/Curve.js#L1488 The edge cases turned out to be a bug in the code that sorted the found intersections before merging duplicates, and due to variations in precision, the sequence of the time parameters wasn't always the same (tiny variations lead to a different sequence of the found intersections). That's all fixed now! And I start feeling much more confident in the current solution again. The only part missing now is handling self-intersecting source paths, and more testing... But what you say about the performance still holds, I am sure. Still better to have a working implementation than none : ) |
|
While I understand the algorithms for finding intersections quite well, I am still trying to get into the boolean operations algorithm. Are there any resources/papers that describe the used algorithm? There is of course the Vatti algorithm, and I found this resource: http://davis.wpi.edu/~matt/courses/clipping/ Do you have any other links? Regarding performance: I have already seen a bunch of potential improvements in the code, so I wouldn't worry too much. Let's make it work first. |
|
I have documented sweep line implementation: http://kuribas.hcoop.net/Overlap.html |
|
For clarity: this is another boolean operations algorithm than the one implemented in paperjs. |
|
@kuribas This is great, but I think Jürg is correct, we should first try to make the current algorithm work, because it already works pretty well in the implementation is more or less finished. The big question is: Will is be possible to resolve the remaining cases where the current implementations still fails or are we on a dead end? |
|
@iconexperience The algorithm that @hkrish fleshed out in 2013 is based on this video here about Path Operations by Google Chrome engineer Cary Clark who is working on Skia: @kuribas that's really great, thanks for putting it online! It sounds quite a bit smarter than what we're doing currently. I don't think I have the skills to port this over to JS though, unfortunately, having never written a single line of Haskell so far. |
|
PS: I find it interesting that in order to find intersections, Cary suggests approximating cubics with multiple quadratics, solving their intersections mathematically and then going back to the cubics from there. |
|
@iconexperience yes I'm aware of that. I'm quite happy with our fat line clipping code currently though... |
|
@lehni I agree, finding intersections has become pretty good recently. I watched the video and luckily the algorithm does not seem to be very difficult. It would be nice to have the canvs he uses for PaperJS. Let's see if I can produce something that will help with debugging. |
|
I watched the whole video. At 19:40 he states that it is hard to solve a cubic using math. However Sederberg and Nishita have shown that it is possible using implicitization. According to the paper this method is faster than the bezier clip algorithm. It reduces to a maximum 9th degree polynomial equation, which can be solved numerically. For example using Polynomial Real Root Finding in Bernstein Form |
|
It seems he wasn't aware of this research, or his method predates it. |
|
@kuribas neither was I : ) What did you think of his approach otherwise? How does it compare to what you are doing? |
|
@lehni I linked to the wrong paper, implicitization is explained in cagd. I am using bezier clipping like you do. According to the paper imlicitization is the fastest method for curves of degree 2 and 3, so I assume it will be faster than approximating a quadratic bezier, but I haven't tested it. The algorithm in the video does O(n*n) comparisons, while my one does O((n+m)log(n+m)) comparisons (n = number of segments, m = number of intersections). For a large number of segments, this may give a significant performance improvement. For a few segments I don't know, that would need to be tested. I actually look at all points, since that is necessary for the sweepline algorithm to test intersections. For the rest both methods seem to be the very similar. I actually test if two curves are overlapping, or if a point comes near a curve. |
|
So, hate to be late to the party but my 2 cents is this: Has anyone thought about:
I'm under the impression that some info about the curves was kept, just before flattening, that would help on the accuracy of reconstructing them back after clipping has been done. AFAIK, this was discussed at a point in Angus Johnson's Clipper Lib, somewhere here Clipper is pretty much based on Vatti which as far as I know is the most 'input tolerant' clipping algorithm. It handles self-intersections/shapes-with-holes just fine but it works only on polygons. |
|
@nicholaswmin according to sederbergh recursive subdivision is much slower than implicitisation. He gives the following relative speed for cubic beziers: ex1: clipping 2.5, implicitisation 1, subdivision 15 ex2: clipping 1.8, implicitisation 1, subdivison 6 |
|
@nicholaswmin I've heard this suggestion before but your link is the first time I see it described in detail. We've gone very far down the current road which works very well for a whole lot of cases (on the Ideally I'd like to see @kuribas approach based on the sweepline algorithm implemented in paper.js, but that's another project... I'm already happy when we can finally say that our current implementation is robust, which it almost is now : ) |
|
@lehni True - I also doubt the approach I described would be anyplace near as fast than what you already have in place anyway. |
|
@nicholaswmin it looks like we just finally managed to resolve all known issues with boolean operations, except this one rare edge case (#773) Even operations on self-intersecting paths are now supported! What's left to do is more testing and some optimizations. This was a very long time in the making, very exciting news! |
|
Btw: Someone ported Andy Finnell's VectorBoolean to Swift (https://github.com/lrtitze/Swift-VectorBoolean). So it could be a little bit easier to port it to JS. |
|
@petrbrzek thanks for pointing that out! In the meantime we've made so much progress on the current implementation that I don't think we require a port anymore. Our implementation also works with a whole lot less code, which is welcome in a browser environment. But it's always good to compare edge cases. Did you already compile it? If so, could you compare and see how it handles cases where paths only touch or overlap along curves / lines? e.g. #450 and #449? |
|
The recent improvements on the boolean operations are quite impressive, but whenever a change to the code was made, we could see the effect of the change on some cases, but we had no way to quantize the effect of the change regarding the quality of the boolean operations. Therefore I wrote a test case based on my first curve offset approach, which takes a curve, splits it into several subcurves, creates an offest path for reach subcurve, and finally merges the offset path using boolean operations. The test automatically runs through 8000 curves, making about 42000 calls to
You should note that the results are not very representative, but the give an indication of the effectiveness of each commit. I hope this is helpful. I will make this test available here, but please be patient, as it need some cleaning first. |
|
This is very useful, thanks! It'd be great if you could share the code for this with me, so I can immediately see the impact of my changes on the result. |
|
I will, but I need to clean it first, because it's a mess. I will post more examples if you do not mind? |
|
Sure keep sending them : ) I'm curious about the +2 in 8073183... That doesn't really make sense, so I'd like to play with it to understand what happened. |
|
So after a ton of more work, the current implementation works with all known edge cases from @iconexperience's test suite. It's been a long and bumpy road to get here, but the code is now very sturdy and clean. I'm super happy with how it all turned out. I am closing this issue now, as all that's left to do is implement some unit tests to protect against regressions, and roll it all out. For those curious about the implementation, the code is mainly in these files: https://github.com/paperjs/paper.js/blob/develop/src/path/PathItem.Boolean.js |
|
@lehni is it possible to create a separate library which deals with boolean operations only, since paper is a bit too large. |
|
@be5invis too large for what? And without paper.js, on what kind of data-structures would it operate on? SVG? Many things are possible, but I don't have the urge work on this particular project. The boolean code relies heavily on many of the data structures in paper.js, which is one of the reasons why the library was built this way. I'm happy with that structure, because it makes working with bezier paths much more simple and enjoyable. I don't think that a 180kb library is too heavy for handling the complex math involved with such bezier curve operations. Having to maintain two separate libraries that do the same thing on the other hand would be too heavy in a whole different way. |
|
@lehni: Nice job man! 👍 |
|
@lehni When you plan to release a new version? |
Despite all the recent improvements on boolean operations in the https://github.com/paperjs/paper.js/tree/boolean-fix branch, built on top of @iconexperience's code that checks for curve overlaps, I start to agree with @hkrish in his observation that the current approach is too complex to fix for all failing edge cases:
@hkrish and @kuribas seem to think that using a sweep-line based algorithm for beziers is the way to go:
#371 (comment)
#371 (comment)
I have found an open-source implementation in Objective C that I believe is based on sweep-line, outlined here:
http://losingfight.com/blog/2011/07/09/how-to-implement-boolean-operations-on-bezier-paths-part-3/
These two posts lead up to that final post:
http://losingfight.com/blog/2011/07/07/how-to-implement-boolean-operations-on-bezier-paths-part-1/
http://losingfight.com/blog/2011/07/08/how-to-implement-boolean-operations-on-bezier-paths-part-2/
The code lives here:
https://bitbucket.org/andyfinnell/vectorboolean/
And in 2014, @BohemianCoding sponsored him to improve the algorithm for inclusion in Sketch app:
http://losingfight.com/blog/2014/01/24/fixes-and-performance-enhancements-for-vectorboolean/
We could attempt porting this to JavaScript? But first we should perform some tests with the complex shapes that our current implementation chokes on, directly in the Objective C code base.
The text was updated successfully, but these errors were encountered: