The Future of Anti Aliasing? Will the Quincunx-Like Blur Technologies Return?

[aths]

As you can see, the sine wave is not remotely close to gone, it is just aliased down to another frequency.

That is why we need a good amount of AA subpixels. AA used in realtime games is not invented to smooth extremely small triangles. To have extreme small triangles is not the typical case. To antialias a heavily undersampled checkerbox pattern does not represent the normal case. In the special case of an undersampled checkerbox pattern, blurring helps to get rid of some noise. But a smooth result with heavy undersampling is – imho – only one given test case. In other cases, AA without smoothing delivers a result which I would describe as "better".

If the color values in your pixmap are fully independent everywhere in the entire picture, then you have a picture that contains nothing but random noise. A human-recognizable feature in a picture generally relies on a fairly large region around any given pixel; upon upscaling an image, you would ideally wish to take an entire such "region" into consideration in order to reproduce the feature as faithfully as possible. As such, it should be rather clear that you can do much better than just plain bilinear. This is in particularly true if the amount of upsampling done is very large (an "ideal" algorithm would in this case probably just look blurred as if it is seriously out of focus; a bilinear-filtered upsampling will be chock full of highly unrealistic Mach bands everywhere.)

Yes, bilinear upsampling leads to numerous artifacts. Still, we have to interpolate data. Linear interpolation looks not very good, but filters with higher orders making additional assumtions about the content.

Nysquist is irrelevant, as are sinc filters ... there are no ideal reconstruction filters. That's the wonderfull thing about image processing for the purpose of display, it's more of an art than a science.

I try to find criteria independent of personal taste. Now I will have to do some research before I post again.

 

[EasyRaider]

Well, here's one way I think about it.

Imagine a program that renders a black line on a white background that is just barely narrow enough that it never slips between the samples of a sparse grid that is being used for MSAA. This line is horizontal, and slowly creeping up the screen.

Now, consider what's going to happen with basic MSAA here: each pixel that includes the line will be the same shade of grey, at all times. As it moves up, the grey pixels will suddenly jump.

That's not what you want when viewing a line moving up the screen. What you want is a smooth transition between pixels. Here is where a gaussian filter would look better: the next pixel that the line is to move into starts turning grey before the line leaves the current pixel, creating a smooth transition.

In this case sampling frequency is roughly equal to signal frequency. In other words, you'd need twice the sampling frequency to reconstruct the line. While some filters will give more pleasing results than others, ideally the line should have been lowpassed away to avoid aliasing.

Correct me if I'm wrong.

 

[EasyRaider]

Nysquist is irrelevant, as are sinc filters ... there are no ideal reconstruction filters. That's the wonderfull thing about image processing for the purpose of display, it's more of an art than a science.

Well, the final (subjective) result is what counts, not how you got there, or whether it follows theory. As such, I agree. Still, I'd think sampling theory can give very valuable pointers.

 

[arjan de lumens]

Please correct me if I'm wrong here, but it seems that a simple application of Nyquist theorem implies that to eliminate aliasing, one should implement a filter at half the spatial frequency of the pixel pitch, in other words, 2 pixels wide.
ERK

Not really. Such a filter would leave you essentially unable to represent any feature that is smaller than 2 pixels, with a blurry mess as a result. In frequency space, the 2-pixel-wide box filter would appear to be a lowpass filter with a nominal cutoff frequency that is only half of the Nyquist frequency. It would also not eliminate all aliasing; as I indicated in my previous post, a box filter does not actually do a particularly good job of eliminating frequencies above its nominal cutoff frequency.

Unfortunately, the theoretically ideal lowpass filter (the sinc-filter) is infinitely wide and tends to suffer spatial ringing artifacts if you just use it as-is on a 2d picture.

 

[MfA]

The problem is that our eyes don't do point sampling of band limited signals ... what it does behaves far more like area integration, like a camera. Aliasing in Nyquist frequency sense is a different beast from aliasing in an image processing sense, I think it's far more important to realise the differences than the similarities. If you have got a hammer everything starts to look like a nail and all ...

 

[arjan de lumens]

In this case sampling frequency is roughly equal to signal frequency. In other words, you'd need twice the sampling frequency to reconstruct the line. While some filters will give more pleasing results than others, ideally the line should have been lowpassed away to avoid aliasing.

Correct me if I'm wrong.

The line adds frequency content much lower than e.g. 1/width. If the line is e.g. white on a black background, it increases the average brightness of the entire frame, so it clearly has a DC term, for example. As such, lowpass filtering should blur the line outwards (presumably making the sharp white-on-black line it appear as a diffuse, wide gray line) but not actually remove it.

 

[ERK]

I'm sorry MfA and arjan, but after further thought, I'm convinced Nyquist applies.

Obviously there is a more optimum AA filter than a box--one has to trade off the filter frequency (aliasing vs blurring) and slope (aliasing and blurring vs ringing). Likely a gaussian, Butterworth or linear (tent?) filter would be good (or better, some custom filter). But I still maintain that a filter width of ~2 pixels has got to be close to ideal or else there will be horrid aliasing.

As for being able to represent things smaller than 2 pixels, the only way that can be done is if they lie on center with the pixel grid--if the object lies half way between pixels, then it's really 2-pixels wide anyway--even worse, as it moves it oscillates in size; in other words, it has aliasing noise.

Sampling theory is correct. How one utilizes it to balance aliasing and blur is obviously an art to some degree.
ERK

 

[arjan de lumens]

The problem is that our eyes don't do point sampling of band limited signals ... what it does behaves far more like area integration, like a camera. Aliasing in Nyquist frequency sense is a different beast from aliasing in an image processing sense, I think it's far more important to realise the differences than the similarities. If you have got a hammer everything starts to look like a nail and all ...

Area integration itself is generally very easy to shoehorn into standard DSP algorithms; the main problem here is more that the feature detection mechanisms of the eye (and the brain that receives the signal from the eye) are poorly understood and apparently not that well modelled by the plain old fourier-transform. The main point of anti-aliasing is then ultimately to remove, as far as possible, any eye/brain-detectable features that result from the gpu/monitor not having infinite resolution.

 

[arjan de lumens]

I'm sorry MfA and arjan, but after further thought, I'm convinced Nyquist applies.

ERK

I am still quite sure that you have a 2x scaling factor figured out wrong, but if you are still convinced, here is what you can do to easily convince the rest of us:

Find a screenshot from a game that has anti-aliasing enabled (they can all be assumed to use an approximate 1x1 box filter so far, unless they use quincunx or 4x9 on nvidia cards), fire up an image processing program (gimp, photoshop, paint-shop-pro, whatever), locate its "convolution matrix" or "user-defined filter" function ( filters > generic > convolution matrix under gimp), set a 2x2 block of entries in it to 0.25, and run it on the screenshot. This will give you a reasonably accurate 2x2 box filter, and it will show you exactly what it does to image quality. If you, at that point, are still convinced, then please post the image (as it looks before and after the 2x2 box filtering).

 

[ERK]

Well, I agree with you that doing such a thing would be very blurry. *sigh* perhaps I'm wrong. Let me think about it some more...

 

[aths]

I have some preliminary notes:

If we have no AA at all, we sample at the center of the pixel. If we have only a single edge in the pixel, the center's color is the color of the biggest area in the pixel:

Lets assume we have 4x AA, but all subpixels are on the same position, still in the center. Obviously we don't have any AA at all. If we move the subpixels in the corners of the pixel, we get to a point where we have no AA again, but blurring only. (Remember XGI's "AA" solution) because this is like to treating the whole no-AAed image with a 2x2 block filter.


So, 4x ordered grid looks quite ok. But sparse grids deliver better edge resolution where it is needed the most: At only very slightly rotated edges.


I tried to visualize the "catchment area" for 4x and 5x sparse AA:

Because the subpixels are farther away from the center than with 4x OG, we already have some blurriness. Now we can argue, that the downsampling should be:

- Any subpixel inside is weighted with 5/24, the adjacent outer subpixel with 1/24.

With 5x sparse AA, the inner subpixel could be weightet with 4/20, the border-subpixels with 3/20, the outer subpixels with 1/20.


Buuut, this only applies for supersampling. For multisampling, I assume a "color error value" of the square of the distance to the texture sampling coordinate. The border subpixels have high color error values. They should not be used for blurring since their color is already quite incorrect.


Temporal Aliasing can only be reasonable fighted with motion blur. (Real motion blur, no more motion trail, please.)

 

[Xmas]

I am still quite sure that you have a 2x scaling factor figured out wrong, but if you are still convinced, here is what you can do to easily convince the rest of us:

Find a screenshot from a game that has anti-aliasing enabled (they can all be assumed to use an approximate 1x1 box filter so far, unless they use quincunx or 4x9 on nvidia cards), fire up an image processing program (gimp, photoshop, paint-shop-pro, whatever), locate its "convolution matrix" or "user-defined filter" function ( filters > generic > convolution matrix under gimp), set a 2x2 block of entries in it to 0.25, and run it on the screenshot. This will give you a reasonably accurate 2x2 box filter, and it will show you exactly what it does to image quality. If you, at that point, are still convinced, then please post the image (as it looks before and after the 2x2 box filtering).

That's not the result you would get with a pixel-centered 2x2 box filter. A pixel-centered box filter would only contain half the samples of each direct neighbour pixel and a quarter of the samples of the diagonal neighbours.

Anyway, I do think that 2x2 is too big a kernel. A smaller kernel (and the right sample distribution) means that each pixel has an area that belongs to it only. Which is important, I think, because that way you can really have objects that influence less than four pixels.

 

[Geo]

At this point you need to repeat to yourself the words of Alvy Ray Smith.

A Pixel Is Not A Little Square, A Pixel Is Not A Little Square, A Pixel Is Not A Little Square!

(1) The triads on a display screen are not pixels; they do not even map one-to-one to pixels.

I have concluded sadly that I don't really understand what a pixel is. ​

 

[arjan de lumens]

That's not the result you would get with a pixel-centered 2x2 box filter. A pixel-centered box filter would only contain half the samples of each direct neighbour pixel and a quarter of the samples of the diagonal neighbours.

Anyway, I do think that 2x2 is too big a kernel. A smaller kernel (and the right sample distribution) means that each pixel has an area that belongs to it only. Which is important, I think, because that way you can really have objects that influence less than four pixels.

A pixel-centered 2x2 box filter gives the same result as one would get by shifting the viewport 0.5 pixels up & left and then run the gimp filter I described (assuming, of course, supersampling with enough samples that a box filter is a reasonable approximation in the first place). Except for 2d overlays, I really don't see why that would make any difference to 3d image quality at all.

 

[EasyRaider]

The word pixel comes from picture element. On LCDs and other fixed resolution displays, each physical triad is commonly referred to as a pixel. And this is correct, picture elements are what they are.

For digital image data, I suppose it's best to think of pixels as points / point samples.

 

[Xmas]

A pixel-centered 2x2 box filter gives the same result as one would get by shifting the viewport 0.5 pixels up & left and then run the gimp filter I described (assuming, of course, supersampling with enough samples that a box filter is a reasonable approximation in the first place). Except for 2d overlays, I really don't see why that would make any difference to 3d image quality at all.

You're right. Don't know what I was thinking there.

 

[ERK]

Anyway, I finally read the Alvy Ray paper linked above and I agree with the author. I note that he (she?) condemns box filters routinely, and that many of his preferred reconstruction filter broadening extents are larger than a pixel.

Of course, that still doesn't mean that I know what is going on in the present discussion..

 

[arjan de lumens]

On an LCD screen, a pixel is actually very much shaped like a little square (which in turn contains three rectangles, one for each of red, green, blue), whereas on a CRT, a pixel is more closely approximated by a gaussian-like shape that overlaps substantially from one pixel to the next. In neither case is a pixel anywhere close to being a mathematical point.

So the LCD effectively applies a box reproduction filter and the CRT applies a gaussian filter. That does however NOT imply that you should apply a box filter before sending a signal to an LCD and a gaussian-filter before sending a signal to a CRT. In both cases, the screen pixel shapes themselves act as mild lowpass filters; on the digital side, you may wish to counteract rather than repeat/mimic this filtering effect.

@ERK: Much of the discussion over the last couple of pages or so has been based on theoretical concepts from the DSP field - a possible starting point for learning more about DSP in general could be this online book (which at least I found fairly easy to read).

 

[ERK]

Thanks. I'll check it out. My experience is wholly with audio filtering and I seem to be tripping up on the differences here.

 

[ERK]

But I'm still hung up on Simon F's original thought experiment: of the thin line (1/4 pixel wide) moving across the screen. Xmas(?) correctly pointed out that the motion would 'jump' from pixel to pixel. To me this means that if the line were not perfectly vertical, say at some small angle from vertical, then the result would be massive jaggies.

I still don't see how this situation could be fixed with any filter that only samples from within the 'little square.' Even and especially the (infinitely sampled) box filter.

Sorry for being dense.

Oh, and it this related to the reason why consumer cards are not generally useful for pro applications since they don't AA lines very well, whereas the pro cards do? Do the pro cards have a different filter kernel for this, or is it something else?
Thanks again,
ERK