Path.crossingRemoved() produces wrong result #66
Comments
ghenania
changed the title
|
@ghenania thanks for the data. I will look into the cause. For the time being does the problem get resolved if you use a smaller value for |
|
Yes, it generally solves the issue but not in all cases and takes much more time. And I need to run boolean operations (almost) in real time while user is drawing. |
|
I am planning on improving the performance impact of increased accuracy by using the Bezier Clipping algorithm for intersections. One thing you will also find is that the API runs much faster (about 5x or more) when running in release mode. BezierKit is used in deployment in some very performance sensitive applications, so performance is always on my mind. If you send me a trace from XCode's performance instrument I'm always willing to take a look at it to see where performance improvements might need focus. Anyway, I'll take a look at the data soon and see if the issue can be fixed without using a smaller accuracy parameter -- it could still be a bug. |
|
Indeed, just tested in Release and it runs pretty fast even with accuracy = 0.01 🚀. Does this performance gain come only from the code compilation? Curious to learn more about the Bezier Clipping algorithm you plan to implement and happy to be an early tester! |
|
Hey @hfutrell! |
|
@ghenania I looked at the test data you sent me and created a unit test with it, but I haven't been able to introduce a good fix. The data presents a difficult case because there are nearly tangent intersections. My goal is that I'd like to both speed up the intersection routine so that this isn't an issue, and also improve the error handling when intersections aren't resolved with enough accuracy so that the output could still be reasonable instead of empty. I haven't had time to code these fixes yet, unfortunately. The most recent commits can speed up |
|
Hey @hfutrell. Any plan for this issue? |
|
@ghenania I still plan to improve this issue but it's non-trivial. I did a deep dive with your test data and I didn't see areas the performance could be improved except for moving to a faster intersection algorithm (though even then tangent intersections can be very difficult): http://nishitalab.org/user/nis/cdrom/cad/CAGD90Curve.pdf Besides that I think the library could use better error handling when the intersections are not found with enough precision. |
|
Thanks for this article. I'll have a look, not sure I can help... |
|
@hfutrell Any suggestion on my previous comment? |
|
@ghenania You might try pre-processing the paths by converting them to series of line segments. The advantage here is that line-line intersection is O(1) for very-high accuracy and BezierKit has a spatial acceleration data structure to prevent unnecessary intersection checks. Then run the same crossings removed code. If the end result is acceptable you could either use it directly, or write some code to use it to reconstruct a path made of curves once more. I do aim to get your use case working, but just keep in mind that BezierKit is a side project for me and your case is tough because it requires both a high degree of accuracy and speed when dealing with curves directly. |
Hey @hfutrell
I randomly get some invalid results from
Path.crossingsRemoved(accuracy: 1)I haven't identified any simple repeatable use case for now.
So here us a dump of a case where it happens. Note that I've used the method you mentioned here (Not sure this issue is linked with issue #64 btw).
Original Path:
Resulting Path:
Super thanks for your support 🙏
The text was updated successfully, but these errors were encountered: