Another serious potential win in SVG is that you might be able to interleave the area integration with alpha compositing / masking. Could end up pretty darned fast.
1. Render each path to a fresh pixel buffer, alpha-compositing it down onto the final canvas. Advantage: straightforward, works for sure. Disadvantage: you need a lot of multiplies per pixel.
2. Partition paths into "layers" of nonoverlapping paths, render each layer as a unit, and composite each new layer down onto the final canvas. Overlapping opaque paths can be incorporated into the same layer as whatever is below them by cutting an overlap-shaped hole in what's below before adding in the new path; although that involves some intersection tests to know where to stop, my intuition is that it will be a big win. Advantages: straightforward, probably faster than the previous one. Disadvantages: the partitioning is a potentially costly extra step (one of those things that makes me wonder if it's NP-complete to do it optimally), and there are still potentially many multiplies per pixel.
3. Separately accumulate a numerator (total premultiplied color) and denominator (total alpha) for each pixel, then divide in the end. Advantages: You avoid doing lots of work per pixel. Disadvantages: This is a weighted sum, not alpha blending. Alpha blending is a different thing. So the result is wrong. Also, an honest division per pixel is more expensive than quite a number of multiplications, although maybe you could cheat on the final division with a table of approximate multiplicative inverses or something. So this would probably be super slow.
4. Find a different group other than ℤ/256ℤ in which to do prefix-sum that somehow gives you the right results. Then you can just render all the edges into the same buffer and do a single vectorizable prefix-sum operation over it.
Advantages: This sounds super fast.
Disadvantages: It seems clear that this group is going to have to be able to represent the entire Z-ordered stack of colors at every pixel, because if I'm looking at some translucent green on top of translucent red on top of opaque black on top of pale blue, and I reach the right (negative) edge of the opaque black path, somehow I have to have remembered the blue thing underneath in order for it to peek through, which suggests to me that I need an unbounded number of bits per pixel to implement this scheme, which probably is not going to admit an actually fast implementation. In effect it has to reduce to the second approach, except that the software has to deal with the stack of layers once for every pixel. Or is there some magical way around this, at least for a fast-path case?
This part is probably obvious to you, Raph, but you can do SVG linear gradients with two prefix-sum passes instead of one, where the first pass just runs over signed gradient stops and gradient clipping boundaries, and then you draw the signed path boundaries into the buffer before the second prefix-sum pass. (Is that clear? I suspect it may be too abbreviated.)
I suspect that with three prefix-sum passes you could do a decent quadratic-spline† approximation of arbitrary gradients, including the weird skew cone gradients SVG calls "radial gradients". But I haven't worked out the details.
I know you don't have a lot of time to hack on this stuff right now, but would you have time to provide feedback if I were to hack on it a bit? I imagine that I'd run into any number of places where talking to you about it for half an hour could save me days of wasted effort.
† here I'm talking about what Carl de Boor calls "splines", which I know disagrees with your usage of "splines". I think you called them "B-splines" in your dissertation.
I think you're going for something much more complicated than what I had in mind. My idea is simply to have two modes other than accum buffer -> 8 bit alpha mask. One would be accum buffer + constant RGBA color -> update RGBA buffer. (By update I mean read an RGBA pixel, do the compositing, and write the composited pixel in place). The other would be accum buffer + source RGBA buffer -> update RGBA buffer. Of course, it's possible to imagine interleaving even more operations in the generation of the source RGBA buffer, but at some point the register pressure overcomes the r/w bandwidth.
Prefix-sum is not a particularly fast SIMD operation, due to the horizontal data dependency. I chose it for font-rs because I don't know of any faster ones that can get the job done. For just computing gradients, it's almost certainly going to be faster to compute it directly (it's simple multiply-add in the case of linear gradients) than to try to strength reduce. The same is no doubt true for SVG radial (cone) gradients.
When the gradient doesn't have any sharp creases or singularities, a very reasonable strategy is to compute it in lower resolution and then up-res, say 2x or 4x to keep the math super-simple. When it does have creases, it might make sense to decompose into regions and use different approaches in different regions.
In any case, it sounds like you may be re-inventing Cairo or Skia here. Might make sense to take a closer look at what they do and whether there's truly any low-hanging fruit left. I know that Skia has a bunch of SIMD optimizations already.
But this is fun stuff to think about and experiment with. I certainly don't want to discourage you.