Coverage - flaw in the algorithm - how to get rid of its use?

Question

Introduction

Many of the mainline vector graphics rendering engines have an algorithmic flaw in them. They render each shape separately, and antialias by calculating pixel coverage and then compose them on top of each other. Yes it is simple but the correct solutions are even simpler.

This leads to a conflation problem as it conflates coverage by transparency. Alpha blending follows a rule that does not represent the situation accurately for example take a pixel that is 50% covered that is neighboring with a pixel that is also 50% complementary covered does not end up with 100% coverage it ends up with 75% coverage. What this looks like depends on how the algorithm is tuned and other details but in essence this is a known error. Somebody did even go trough the trouble of documenting the different engine errors along with writing a paper showing how it could be done better.

Image 1: Totally non-representative sample, of rendering a shape that's made out of triangles showing magnified error on top row. SVG source

The problem has a simple naive solution* just super sample without coverage calculation and filter the image down. As a bonus you get to use better image reconstruction algorithms than box filtering (read A Pixel is Not a Square³). There are even solutions that have comparable speed as current solutions and these solutions are much easier to do in hardware rasterization pipelines (and you seldom see this error on GPU because it built to avoid just this problem).

This is also not a problem without a cost. There are many people working in graphics design that spend nontrivial amount of time trying to circumvent this problem manually by making sure there's overlap here and no overlap there to fix the problem that the computer should do for them. And failing spectacularly in many cases. But their clients do not care why the error is there they must fix it.

Question

How does the error propagate? Since they are all doing the same error one could conclude that they use the same source for their algorithm. What could have caused the designers to choose this algorithm? Why did only the 3D programmers recognize this error and even codify its part in their API's and teaching while 2D programmers did not?

How to ensure that this error stops propagating further?

---

Addendum (but i am not asking about this)

*Apparently my claim that super sampling works without flaw is extraordinary and requires extraordinary proof. Ok, so the key to super sampling working is that the super sampling does not do coverage processing. In essence the super sampler treats each sample as a point sample. Since the point sample makes no assumption of the underlying area it is not causing alpha comparison where it does not happen.

For it to work consistently, as described in one of the answers. We need to make to process the samples with integer sampling for consistency. This assures us that each point once transformed to screen space get exactly the same solution for equal coordinates and that no sample is shaded by a pixel border 2 times. To do this a sample may not trigger a pixel ot is exactly on if it is the for example left side bottom sample (so we make a rule that exact edges are processed in > vs <=). All but one console graphics card work like this. It ensures that no extra data needs to be cached and no extra nearby testing needs to be made. This solution is as stable, more general and consistent than coverage based solutions.

The algorithm is exactly the same as the original with slightly less code and slightly more samples. It is thus as consistent if not more so than the coverage based algorithm. We know this because we have been using such methods for ages in nearly any other signal processing field as well as graphics cards.

So does this method have a downside? Well it is a tad slower if you would just make a naive assumption. It has theoretically a faster asymptotic behavior than the coverage rasterizer, bit like a raytracer it is still only at par in typical scenes. Also it could make the usage of convolution based effects more painful to implement.

Answer 1

Supersampling, when done naively, is computationally expensive, since if you use for example half the pixel size of your display, you need four times the memory and band width. Wikipedia mentions this and also names adaptive supersampling as a possible solution. But that starts to make the algorithm much more sophisticated, complex and harder to implement.

And I guess that is the reason you are looking for: if you want an algorithm which does not need a lot of more memory and running time, things are getting much more complicated than in the naive "transparency" approach.

Answer 2

Supersampling won't solve the problem in general: it will merely make it less noticeable. With pixels half the size, the problem will be half as noticeable but it won't go away.

The architectural point behind these designs is that we want the command "render triangle ABC" to have a definite meaning. We do not want it to be ambiguous except when considered as part of a collection of drawing commands – for example, having one meaning when "render triangle BCD" is also in the collection (with the same or a different colour) and another meaning when it isn't.

Considering, for example, a thousand triangles, even finding all the triangles that share a side or part of a side with ABC is computationally heavy (remembering that it has to be re-done a thousand times). There are plenty of other practical problems as well: notably that all the original rendering requests have to be kept around, even if they were drawn a long time ago, in case they need to be reassessed because of a new, additional request.

The bottom line is that a perfectly consistent solution is not practicable. There remains the question: should we try to improve the current situation when we can? In general, the answer to that question is No. A perfectly consistent implementation of a model is always better, even if the model itself has the limitations you have illustrated. The alternative would be an implementation that sometimes does better and sometimes doesn't, with no way for the programmer to know which of these two is going to hold in any particular case. Moreover, it can jump from "does better" to "doesn't do better" as a result of tiny changes made by the programmer – or even as a result of ones outside the programmer's control. Predictability, in a programming context, is far, far better than occasional correctness.