Add a multisampling mode to Pathfinder

[mtklein]

Hi! Have you put any thought in how to handle situations where this sort of area-summing rasterization algorithm fails? We keep wishing we could use this type of algorithm in Skia for its simplicity, precision, and parallelism, but we keep running up against really simple cases that fail dramatically in terms of accuracy, like this sort of shape:

<svg width="50" height="50" xmlns="http://www.w3.org/2000/svg">

  <circle cx="24.5"
          cy="24.5"
          r ="24.5" fill="red"/>

  <path d="M  0  0
           L 49 49
           L  0 49
           L  0  0
           L 49 49
           L 49  0
           L  0  0" fill="green"/>

</svg>

It ought to be that none of the red circle shows through, but in my Pathfinder Demo it does show along the middle diagonal where the path doubles back on itself. The math ends up thinking there's zero area covered in those diagonal pixels, where it's really fully covered. I think I've attached a .png:

We've also run into this same sort of issue in the wild, in the area where caps overlap on http://matteosistisette.github.io/jquery-ui-labyrinth/. This case is kind of the opposite end of things compared to the .svg above, where instead of undercounting what should be 1.0 coverage as 0, I think we were overcounting what should have been 0.5 up to 1.0. It was a situation where 0.5 + 0.5 = 0.5, because of the way the overlap lays spatially.

We've mostly come to the somewhat depressing conclusion that there's no way around not tracking some aspect of the subpixel positioning. Seems like with only area we really don't know how to merge coverages within a pixel... do they sum, max, or make an independent product? I think we can't know without knowing how the two overlap, right?

Have you ever put any thought into this problem? I imagine it mostly just doesn't come up for typefaces, but with general sorts of inputs we'd really like to at least find a way to detect this might be an issue and fall back on sampling or something that's not sensitive to this issue.

[pcwalton]

Hi,

I think this issue is just a less common instance of the more commonly-encountered problem that arises when you have multiple paths with coincident non-pixel-aligned edges. (This was common when running Flash content in canvas via Shumway, because Flash used a supersampling rasterizer.) While I could perhaps solve it at the individual path level by using MSAA instead of area coverage in each tile (probably with increased tile size), that still wouldn't solve the general problem that arises from multiple paths. For instance, I think you'd more commonly see your example written as:

<svg width="50" height="50" xmlns="http://www.w3.org/2000/svg">

<circle cx="24.5"
        cy="24.5"
        r ="24.5" fill="red"/>

<path d="M  0  0 L 49 49 L  0 49 z" fill="green"/>
<path d="M  0  0 L 49 49 L 49  0 z" fill="green"/>
</svg>

If it's written like this, then no solution based on alpha blending individual paths on top of one another can possibly render it properly, because the area information is lost.

So if we want to handle these types of situations properly I'm inclined to handle them holistically, probably by using MSAA for the entire framebuffer. Solving the problem only for individual subpaths (or portions of subpaths) within a single path strikes me as an incomplete solution that pleases few.

If I implement MSAA, it'll probably be an option and not the default. MSAA has a big memory and performance cost, especially on Intel GPUs, and I think folks would prefer antialiasing quality at the cost of a few rendering errors in edge cases.

[pcwalton]

One thing I realized is that is as a mitigation I think you could break paths like this into subpaths and canonicalize all nonintersecting paths with coincident edges to have a consistent winding (CW or CCW). This is a total hack, though, and I don't really want to do it unless we find some real content that needs it.

[pcwalton]

Oh, regarding your in-the-wild example: I was thinking that most weirdness regarding strokes can be resolved by having a special shader for them. This is consistent with Pathfinder's design. (https://github.com/pcwalton/pathfinder/issues/145)

[mtklein]

Yeah, handling strokes specially seems like a promising way to avoid this issue for strokes. If you make sure all your stroke outset geometry winds the same way, maybe the whole issue just goes away?

I guess we're still spooked about the general fill case. You could imagine a site that draws the same shapes using fills instead of strokes, and don't have much of an answer for what to do then.

[raphlinus]

I think this is a hard problem to solve, and am punting on it in piet-metal. That said, here are some thoughts.

Both MPVG and Li's work do MSAA-like supersampling, and avoid this problem. If it's a hard requirement, maybe it pushes you in that direction.

But I think it might be possible to approach this more analytically. I think the key observation is that it only happens when edges from two different paths are incident on the same pixel (actually I'm not sure why the example above triggers the problem, as all edges are from the same path - either there's a bug somewhere or something missing in my understanding) ((Edit added afterwards: I think maybe it's because those two subpaths wind in opposite directions)). I think it's possible to detect that in the tiler (whether CPU or GPU implemented) and fall back to a slower rendering technique in that case. It's likely to be a smallish subset of total paths.

In any case, it's an interesting problem to try to solve!

[pcwalton]

@raphlinus I think the reason why it happens on the path in the original issue is that the two triangles are wound differently. So you get +0.5 from the upper triangle and -0.5 from the lower triangle, which sum to zero along the diagonal.

[raphlinus]

Yup, I get it now :) Very tricky to solve, and yes, you pretty much don't need to worry about this for font rendering. And it actually invalidates the assertion I made above about requiring edges from two different paths in order to trigger.

[pcwalton]

I still tend to think that this is not a problem worth solving if you're only going to solve it within a single path, because that's the rare case. The common case is when you have multiple overlapping paths with coincident edges. Off the top of my head, I don't see any way to solve the problem in its full generality without multisampling or supersampling of some sort.

[mtklein]

Yeah, it's looking like our plan is to sample coverage a few times per pixel. It's sad to lose the high precision we got from area... tempted us for a while into looking at hybrid sampler / area rasterizers, but didn't really get anywhere with that.

It may be splitting hairs, but we see this as an issue that comes up only within a single path. When drawing multiple paths, folks tend to be somewhat settled on (or resigned to) the convention that each path resolves and blends with the framebuffer in turn, conflating alpha and coverage and all that unless you're storing more than one sample per pixel.

[pcwalton]

My instinct tells me that the best option is to simply let the user choose globally between analytic AA and MSAA, perhaps via a flag on the canvas context. Making the flag global would allow users such as Shumway to opt into an actual fix for the issue in its full generality. Trying to get the best of both worlds automatically seems like the kind of thing we could spend a ton of time on without ever really reaching a satisfactory conclusion.

[pcwalton]

@mtklein I don't really agree with that point in the design space, but obviously Skia is free to set its own priorities :)

[pcwalton]

Based on this conversation, I'll edit the issue title to reflect the likely feature work that will happen to implement this: a multisampling mode as an alternative to analytic AA. This should not be that hard to implement: we simply need to allocate a multisample framebuffer for the tiles and replace the fill shader with one that simply emits -1/+1 for in or out (taking care to ensure a consistent rule for overlapping fragments that hit the exact fragment center). Also, we may want to adjust the tile size in this mode. Happily, the tiling code and all the rest should be unchanged, so I don't see this becoming too much of a maintenance burden.

One could imagine two kinds of multisampling modes: one that multisamples the tiles only (like Skia), and one that multisamples the framebuffer as well. I'm not super inclined to implement the former at this time, but I could be convinced otherwise if that's what people want.

[pcwalton]

Note that the tiles in this case might well just be a stencil buffer with no fragment shader at all, to take advantage of double pumping on some GPUs. In this case Pathfinder would be similar to NVPR, but with much better batching and less overdraw due to the tiling step.

[nical]

I still tend to think that this is not a problem worth solving if you're only going to solve it within a single path, because that's the rare case. The common case is when you have multiple overlapping paths with coincident edges. Off the top of my head, I don't see any way to solve the problem in its full generality without multisampling or supersampling of some sort.

FWIW I think that authors do expect coincident edges to not bleed through when they belong to the same path. The issue was brought up a couple of years ago by some of the moz gfx folks when I showed an early version of lyon and I ended up fixing this issue by detecting and merging coincident active edges in the sweep line of the tessellator. The same could be done in PF I believe, without supersamping.

[pcwalton]

@nical Well, I'd like to see some real content in the wild before making a decision on what to do. Anything short of supersampling is going to be an incomplete solution that handles some cases but not all, so I think it's best to proceed in a data-driven way.

[pcwalton]

@nical It might actually be simpler to just have a prepass that detects coincident edges and merges them up. Since this is a rare case, as long as you can check quickly and bail out, this shouldn't be expensive.

[nical]

Lyon does it when an edge is inserted in the active edge list in the same logic that ensures active edges are correctly sorted. Works well at least in teh way lyon's sweep line is structured (it's never stood up in profiles at least).