[mfabbri77]

I've been researching this field for 20 years (I'm one of the developers of AmanithVG). Unfortunately, no matter how fast they are made, all the algorithms to analytically decompose areas involve a step to find intersections and therefore sweepline approaches that are difficult to parallelize and therefore must be done in CPU. However, we are working on it for the next AmanithVG rasterizer, so I'm keeping my eyes open for all possible alternatives.

[muyyatin2]

I ran across https://dl.acm.org/doi/pdf/10.1145/72935.72950 a few weeks ago, it seems like a potential non-sweepline highly-parallel method. I've had some promising results for first doing a higher-dimensional Hilbert-sort (giving spatial locality), and then being able to prune a very large percentage of the quadratic search space. It might still be too slow on the GPU. I'm curious if you have any write-ups on things that have been explored, or if I'd be able to pick your brain some time!

[whenc]

Here's one to look at: https://dl.acm.org/doi/10.1145/2980179.2982434

[dvdkon]

I believe Vello does this for AA (though I can't find the source now), and it's very fast, running on the GPU via compute shaders.

[raphlinus]

No, Vello does not analytically find intersections. Compositing is (currently) done by alpha blending, which is consistent with the W3C spec but has its own tradeoffs.