Making Boolean Operations Faster

[photopea]

Hi, my name is Ivan. I am the creator a popular photo editor www.photopea.com, used by 1 million people every day.

I use Paper.js in Photopea to allow my users to do boolean operations on vector shapes (cubic bezier curves). However, it tends to be very slow wor complex shapes. It might take 20 seconds up to several minutes to process it.

Is there any way to make it faster? In your interface, you need to create many objects using constructors, these objects have properties and methods, etc. You even have to specify a color, which seems to be totally unrelated to a purely geometric problem.

Could it be slow because of your geometry representation / overhead? Is there any library in Javascript (or maybe even C++, I could compile it to WASM), that you could recommend me instead of paper.js? Or could you make it faster by removing some bottlenecks in Paper.js?

[northamerican]

@photopea nice project. i use clipper wasm for faster boolean operations. i've made a package that interfaces paper with clipper here: https://github.com/northamerican/paper-clipper maybe it is worth tinkering with.

[photopea]

@northamerican wow, that sounds great! Can it handle cubic bézier curves, or just polygons?

[northamerican]

@northamerican wow, that sounds great! Can it handle cubic bézier curves, or just polygons?

clipper doesn't support bezier curves as far as i know. the primary and maybe only practical use for my tool may be for offsetting (growing/shrinking) bezier curves because it's already a lossy operation. what it does is it flattens the curve, offsets, then re-integrates it using a custom simplifying algorithm. it's practical for my use but might not cut it as it will distort bezier curves. probably even if you flatten with fine precision, then 'simplify' the shape again.

[r-flash]

Hello Ivan, I just published a low-level TypeScript library with the sole purpose (at least for now :slightly_smiling_face:) of performing boolean operations on SVG paths. It's available here. It's still in development and in desperate need of testing. It would be a tremendous help for me if you could try implementing it in Photopea and gave me feedback on potential problems or missing features.

[photopea]

@r-flash Hi Adam, that looks amazing! Could you provide me Javascript file with a function inside it? I never worked with Typescript or NPM so I dont know what native programs should I download and install, and learn how to use, to be able to use your library.

[r-flash]

I've added the built files here. You probably want to use the UMD version which you can just <script src=... into your project to have the global PathBool variable available.

[photopea]

It does seem to work a bit faster than paper.js! Do you have any specific examples of complex paths, which take a long time to process? I used to have such paths, but I can not find them.

[photopea]

@r-flash I did a test on large shapes with many points, and your library is 4x faster than Paper.js . That is amazing!

BTW. your path representation seems a bit too complicated. Could you maybe switch to something like this: https://www.youtube.com/watch?v=vb4XFNC4MvU . It has two arrays: array of strings and array of numbers, while you have an array for each coordinate.

BTW. it seems like your library contains an SVG path parser. Your library could be smaller without it, I already have it on my side.

Does your library relly work with Lines and Arcs? I would expect that you convert everything to cubic bézier splines to simplify your algorithms.

[r-flash]

Thank you very much for testing the library! Regarding your suggestions, let's maybe not spam the issue tracker of an unrelated project and open new separate issues in my repo instead?