Unintuitive Optimization For Performing Paths Union

I was once tasked with processing any vector graphics the user input into the software and calculating the outlines of all shapes from them. The outline is then transferred to the printer. Most of the time, users upload vector art they made using tools like Illustrator, and these artworks can be Very Complex. In this post I’m going to take a real SVG I had to work with, which contained approximately 1981 paths.

Computing the contours boils down to performing the union of all shapes. Here is a basic example of what a union is:

As you can see, it literally gets the outline of all objects, rather than “cutting” inside any shape. In general, it is extremely difficult to compute unions on paths. User-uploaded paths are arbitrary: they can intersect themselves, they can have overlapping edges, they can have holes (even nested holes), etc. Fortunately, there are already existing solutions, such as Skia’s PathOps module and Paper.js. I use Skia for this specific task.

This is the SVG I have to deal with:

In order to solve this problem, Skia provides us with two methods of executing path union:

• a function Op It takes two paths and returns the new path.
• A path builder where we can add many paths and operations and finally parse everything into the resulting path we need.

The path builder claims it’s even optimized for unioning everything, so it looks like that’s exactly what I need. At first I tried the naive version:

def perform_union_naive(paths):
    if len(paths) == 0:
        return None
    if len(paths) == 1:
        return paths[0]

    result = paths[0]

    for path in paths[1:]:
        new_path = pathops.op(result, path, pathops.PathOp.UNION)
        result = new_path

    return result

So I just take the first path, calculate the union with the next path, store the result, and repeat this for all other paths. I ran this program on an M2 Pro chip, and while I expected it to be slow, I didn’t expect it to take more than a minute. I thought maybe I was doing something stupid with Python, but that’s not the case, everything was fast up until a certain point (around the first 1500 paths), but then everything started getting slower and slower. So it definitely has to do with the actual joint steps.

Next I tried a smarter version, which should be very fast:

builder = pathops.OpBuilder()
for path in paths:
    builder.add(path, pathops.PathOp.UNION)
result = builder.resolve()

This command takes approximately 23 seconds to execute. While the seconds can vary significantly depending on the environment, what is relevant is that the function is now approximately three times faster. While this is great, it still feels too slow. There was the possibility of giving up: after all, I used Skia’s fastest version directly, and it was still slow. Considering it’s generally difficult to get joints going, and that Skia has put in years of engineering to achieve great performance everywhere, it’s understandable that one might conclude that’s just the way it is. But I still wanted to at least try something different, change it up a bit and see if I could change anything.

Remember that union operations are commutative, a simple “fix” might just be to distribute the work to multiple threads and then combine the results. This is something I want to avoid completely. It might improve things a bit, but it won’t solve the core problem or even guarantee it will be much faster. Not to mention that adding threads where there’s no obvious need is already like opening a can of worms.

So what I tried to do next was to better understand how Skia’s path manipulation works under the hood. have a great Promotional meeting How it all works is told by Cary Clark himself. I also read some of the source code and extracted some interesting parts:

• A path may switch its winding (e.g. from even to odd to non-zero while keeping the path looking the same). I believe Skia only performs path operations on one type of wrap (possibly non-zero), anything different will be converted to that wrap. This is far from a simple (or fast) operation, but there’s nothing I can do about it.
• It has to iterate over the curves/segments of the path and calculate the self-intersection points. This is easily O(n²) Operation.
• It has to iterate over the curves/segments of each path and calculate the intersection between them. Again, this is easily O(n²).
• There are other things happening, such as: converting cubic equations into a series of quadratic equations, analytically performing intersections between quadratic equations, simplifying paths, etc. I cannot modify the user’s path.

The details here may be wrong, I don’t know if the operation is actually O(n²). But what do I Do We know that the performance of an operation depends on a lot of The number of curves/segments each path has. While I can’t change the path I receive, I can change the specific way the union is performed.

There is one thing about unions that is very relevant to us:

In this example, the resulting outline is simply a square because the stars are completely contained within it. This means that unions can reduce The number of segments in the result. Of course, in other cases it might result in more curves, but the core idea is that when the two paths don’t overlap, the number of curves cannot get smaller. Since we’ve seen that the runtime performance of path operations depends heavily on the number of segments, this is a good hint as to why it’s so slow in our case. When we do more than 1900 unions in a row, even a few paragraphs that are not eliminated early add a lot of overhead.

So now we at least know why everything is taking so long to complete. But how to improve this?

Remember that union is commutative. It doesn’t matter in what order we do it. So I thought maybe I could localize the paths without reducing the number of segments so they don’t affect too many other unions. I tried a very simple “divide and conquer” approach, just perform a union for every N paths (where N=100, chosen arbitrarily) and then combine the results (possibly divide and conquer again).

def perform_union_intervals(paths, interval_length=100):
    if len(paths) == 0:
        return None
    if len(paths) == 1:
        return paths[0]

    if len(paths) > interval_length:
        results = []
        iterations = int(len(paths) / interval_length)
        for i in range(iterations + 1):
            start_index = i * interval_length
            end_index = (i + 1) * interval_length
            results.append(perform_union_naive(paths[start_index:end_index]))
        return perform_union_intervals(results)

    return perform_union_naive(paths)

If I use the slowest version perform_union_naive (the first one covered in this article), the entire process takes less than six seconds to complete. While still a bit slow, this time it’s acceptable and about four times faster than the best result we’ve had so far. I remind you again that it uses the slowest version and just does the union one by one. If I use the path builder version, everything takes just over two seconds. This is really awesome. But this is unintuitive: I’m performing more Joint operations are faster and faster than before.

While the results are great, I’m still curious if it could be done faster. The default interval length of 100 was chosen completely arbitrarily, so the first thing I did was try to test multiple interval lengths. Note that when I call the function recursively, I don’t pass it the same interval length, I just keep the preset value. This is because, when using the path builder, the script will segfault. I haven’t bothered to debug it, so I don’t know why it does this. But I’ve also tried passing the interval length recursively (using the slowest version), and it doesn’t really change that much in terms of performance.

Trying different interval lengths brought me a surprising result: if I choose a length of 2, the runtime cost is now just over a second. This is better, but I still want to try and see if I can do it faster.

I’m trying to use a heuristic to sort the paths before performing the actual union. I tried sorting the paths in reverse order by their number of segments. The theory goes that the more complex the paths, the more likely they are to overlap with something else. Of course, this isn’t always true, but it’s just an inspiration. This fails horribly, and the runtime cost is even greater than just doing a simple union of everything. Note that I only measure the union steps, not the sorting time.

I have another theory: maybe I can see which paths overlap the most and sort them based on that criterion. Paths that overlap most with other paths are processed first, which may eliminate a large number of segments very early. Calculating path overlap is not easy, but we can do a trick. While it’s very difficult to handle paths mathematically, we can render them to a buffer more easily (and robustly). So I created a basic renderer that knows which paths overlap per pixel. Summing each overlap will give the overall overlap for each path. This also failed.

This one is even more unintuitive because this is my understanding of why my optimization works in the first place. Maybe my ordering is incorrect, or maybe I need to pair the paths in a smarter way. But this is more of a research project right now, so I won’t delve into it right now.

Feel free to try everything I show you here. I created a repurchase agreement There you can see all the things I’ve implemented.

This is one of the least intuitive problems I’ve ever had to solve. A lot of my intuitions kept being proven wrong. While I’m glad I was able to come up with a solution to make everything faster, I’m still surprised that I was able to perform unions on paths faster than Skia’s preset way. I’ve also tried explaining this to other people, people who don’t necessarily work with graphics, but it’s quite difficult to explain. That’s still the case, but this blog post hopefully helps provide more context while serving as a real-world example of an extremely niche graphics problem.