How do I accurately compute coverage of overlapping analytical curves?

Question

Antialiasing of 2D shapes boils down to computing the fraction of a pixel that is covered by the shape. For simple non-overlapping shapes, this is not too difficult: clip the shape against the pixel rectangle and calculate the resulting shape's area. But it becomes more difficult if multiple shapes overlap the same pixel. Simply summing areas can cause the computed coverage to be too high, if it neglects the amount that one shape covers another shape. For example, see the Limitations section of this article on font rendering. You might also be in a situation where the two curves come from different objects with different colors (so it's not about the total coverage for the union of the two shapes, but the coverage of each one separately).

How would this be computed if you cared about complete accuracy? Even trickier, how do you compute coverage accurately for overlapping non-polygonal shapes like curves? Is there some point when you have no choice but to fall back to multisampling or stochastic techniques?

Answer 1

There is really no good way of doing this efficiently analytically for all corner cases. Most or all commercial 2D renderers that attempt to do analytic coverage calculation make predictable errors that multisampling methods do not.

A typical problem is two overlapping shapes that share the same edge. The common situation is that alpha channels sum up to a too thick alpha edge that aliases slightly. Or if shapes are differently colored the system confuses what color the background is. This is extremely annoying.

Image 1: The rendering engine confuses the coverage and makes a thin white outline where no outline should be.

Second perfect coverage amounts to box filtering. We can certainly do better. Considering that there are so many special corner cases that would require boolean operations on the shapes to do right, super sampling is still superior. In fact the coverage estimates may be used to concentrate sampling where it's most likely needed.

The situation could be simplified to polygons at sub pixel levels then the discrete analytical solution could be solved. But this at the expense of flexibility. For example its not out of the question that future vector systems might want to allow for variable width blurred lines which pose a problem for analytic solutions, as do other variably colored objects.

How to do it analytically

Image 2: Suppose you have this scene, exploded view on right

Now you can not just do this analytically, each piece separately and then merge the data. Because it results in wrong data. See alpha blending would let the blue shine trough the gaps if you did so.

What you have to so is split the scene up so that each shape eliminates what is under the other:

Image 3: You need to cut the underlying surfaces.

Now if everything is opaque then this is all straight forward. just calculate the area of each piece and multiply that by color and sum them together. Now you can use something like this.

This all breaks down if your individual shapes aren't opaque off course but even that can be done at some level.

Remember:

• AA calculation need to be done in linear color space, and converted back to use space.