10

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.

enter image description here

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 Square3). 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.

  • Will add pictures for my amnendum once my work day is over. After all this is graphics processing it has a visual interpretation – joojaa Sep 27 '16 at 4:43
6

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.

  • You do not actually need to store the samples all you need to do is store rasterisation setup. The coverage based method does not store them either so this is not a step backwards. The naive method is only presented because its easy to understand, you can easily do priority based sampling. Also if you want to move your coverage based solutions to the GPU you will need to do a lot of extra work and you will be incompatible with its model. – joojaa Sep 28 '16 at 7:44
  • @joojaa: can you outline what you mean by "storing rasterisation setup", or give a link where the approach is explained in a way one don't has to dig himself through a >20 page scientific paper? – Doc Brown Sep 28 '16 at 8:31
  • Each pixel is independent of each other, so you only need to save the samples while you are doing the pixel, you can safely discard them after this. If you want to use a higher order fiter then you can only store a limited view. So all you really need to do is allocate memory for your processing core so maybe (16-256 bytes per thread) – joojaa Sep 28 '16 at 9:13
  • oh sorry you dont even need to store the samples if youy do box filtering you can just use the formula for moving/running average which does not need you to store individual samples – joojaa Sep 28 '16 at 9:22
  • @joojaa: I don't get it - don't you need to calculate the samples first of all related shapes, maybe hundreds or thousands, and afterwards filter down to your raster display? – Doc Brown Sep 28 '16 at 9:50
6

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.

  • This is a problem of the coverage calculation if my supersampling does NOT do coverage calculation then it does not have problems as it will converge to the rea answer not just diminish the problem. Doo you need some code to prove this? This is how your graphics card works and it does not get this problem. Otherwise every game you see would exhibit the problem. Im not buying this answer as it is based on false logic. – joojaa Sep 26 '16 at 19:11
  • @joojaa games either don't do any anti-aliasing or use super-sampling for anti-aliasing, which gives typically four levels of anti-aliasing. This is not good enough for presentation quality graphics where you want about 64 levels on anti-aliasing. So games swap the one problem for another. – Pete Kirkham Sep 28 '16 at 8:21
  • @PeteKirkham depends on your setting some gamnes allow you to specify sample amounts. Anyway you dont need more than 16 samples to produce presentation level AA if you use a higher order filter than box filtering. Note the no error image in my example IS done by supersampling inside the hardware reasterizer. – joojaa Sep 28 '16 at 9:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.