7 ms·

I am quite convinced that if the goal is the best possible output quality, then the best approach is to analytically compute the non-overlapping areas of each p

I am quite convinced that if the goal is the best possible output quality, then the best approach is to analytically compute the non-overlapping areas of each polygon within each pixel. Resolving all contributions (areas) together in the same single pass for each pixel.

muyyatin2 2y ago
I've been looking into how viable this is as a performant strategy. If you have non-overlapping areas, then contributions to a single pixel can be made independently (since it is just the sum of contributions). The usual approach (computing coverage and blending into the color) is more constrained, where the operations need to be done in back-to-front order.
- mfabbri77 2y ago
  I've been researching this field for 20 years (I'm one of the developers of AmanithVG). Unfortunately, no matter how fast they are made, all the algorithms to analytically decompose areas involve a step to find intersections and therefore sweepline approaches that are difficult to parallelize and therefore must be done in CPU. However, we are working on it for the next AmanithVG rasterizer, so I'm keeping my eyes open for all possible alternatives.
  - muyyatin2 2y ago
    I ran across https://dl.acm.org/doi/pdf/10.1145/72935.72950 https://dl.acm.org/doi/pdf/10.1145/72935.72950 a few weeks ago, it seems like a potential non-sweepline highly-parallel method. I've had some promising results for first doing a higher-dimensional Hilbert-sort (giving spatial locality), and then being able to prune a very large percentage of the quadratic search space. It might still be too slow on the GPU. I'm curious if you have any write-ups on things that have been explored, or if I'd be able to pick your brain some time!
  - dvdkon 2y ago
    I believe Vello does this for AA (though I can't find the source now), and it's very fast, running on the GPU via compute shaders.
    - raphlinus 2y ago
      No, Vello does not analytically find intersections. Compositing is (currently) done by alpha blending, which is consistent with the W3C spec but has its own tradeoffs.
  - whenc 2y ago
    Here's one to look at: https://dl.acm.org/doi/10.1145/2980179.2982434 https://dl.acm.org/doi/10.1145/2980179.2982434
enriquto 2y ago
> compute the non-overlapping areas of each polygon within each pixel In the given example (periodic checkerboard), that would be impossible because the pixels that touch the horizon intersect an infinite amount of polygons. Not that TFA solves that problem either. As far as I know the exact rendering of a periodic pattern in perspective is an open problem.
shiandow 2y ago
If there's one thing I've learned from image processing it's that the idea of a pixel as a perfect square is somewhat overrated. Anti-aliasing is exactly as it sounds, a low-pass filter to prevent artefacts. Convolution with a square pulse is serviceable, but is not actually that good a low-pass filter, you get all kinds of moire effects. This is why a Bicubic kernel that kind of mimics a perfect low-pass filter (which would be a sinc kernel), can perform better. It is tempting to use a square kernel though, because it's pretty much the sharpest possible method of acceptable quality.
dahart 2y ago
Why are you convinced of this, and can I help unconvince you? ;) What you describe is what’s called “Box Filtering” in the article. Box filtering is well studied, and it is known to not be the best possible output quality. The reason this is not the best approach is because a pixel is not a little square, a pixel is a sample of a signal, and it has to be approached with signal processing and human perception in mind. (See the famous paper linked in the article: A Pixel is Not a Little Square, A Pixel is Not a Little Square, A Pixel is Not a Little Square http://alvyray.com/Memos/CG/Microsoft/6_pixel.pdf http://alvyray.com/Memos/CG/Microsoft/6_pixel.pdf) It can be surprising at first, but when you analytically compute the area of non-overlapping parts of a pixel (i.e., use Box Filtering) you can introduce high frequencies that cause visible aliasing artifacts that will never go away. This is also true if you are using sub-sampling of a pixel, taking point samples and averaging them, no matter how many samples you take. You can see the aliasing I’m talking about in the example at the top of the article, the 3rd one is the Box Filter - equivalent to computing the area of the polygons within each pixel. Look closely near the center of the circle where all the lines converge, and you can see little artifacts above and below, and to the left and right of the center, artifacts that are not there in the “Bilinear Filter” example on the right.
- raphlinus 2y ago
  I think the story is a lot more complicated. Talking about "the best possible output quality" is a big claim, and I have no reason to believe it can be achieved by mathematically simple techniques (ie linear convolution with a kernel). Quality is ultimately a function of human perception, which is complex and poorly understood, and optimizing for that is similarly not going to be easy. The Mitchell-Netravali paper[1] correctly describes sampling as a tradeoff space. If you optimize for frequency response (brick wall rejection of aliasing) the impulse response is sinc and you get a lot of ringing. If you optimize for total rejection of aliasing while maintaining positive support, you get something that looks like a Gaussian impulse response, which is very smooth but blurry. And if you optimize for small spatial support and lack of ringing, you get a box filter, which lets some aliasing through. Which is best, I think, depends on what you're filtering. For natural scenes, you can make an argument that the oblique projection approach of Rocha et al[2] is the optimal point in the tradeoff space. I tried it on text, though, and there were noticeable ringing artifacts; box filtering is definitely better quality to my eyes. I like to think about antialiasing specific test images. The Siemens star is very sensitive in showing aliasing, but it also makes sense to look at a half-plane and a thin line, as they're more accurate models of real 2D scenes that people care about. It's hard to imagine doing better than a box filter for a half-plane; either you get ringing (which has the additional negative impact of clipping when the half-planes are at the gamut boundary of the display; not something you have to worry about with natural images) or blurriness. In particular, a tent filter is going to be softer but your eye won't pick up the reduction in aliasing, though it is certainly present in the frequency domain. A thin line is a different story. With a box filter, you get basically a non antialiased line of single pixel thickness, just less alpha, and it's clearly possible to do better; a tent filter is going to look better. But a thin line is just a linear combination of two half-planes. So if you accept that a box filter is better visual quality than a tent filter for a half-plane, and the other way around for a thin line, then the conclusion is that linear filtering is not the correct path to truly highest quality. With the exception of thin lines, for most 2D scenes a box filter with antialiasing done in the correct color space is very close to the best quality - maybe the midwit meme applies, and it does make sense to model a pixel as a little square in that case. But I am interested in the question of how to truly achieve the best quality, and I don't think we really know the answer yet. [1] https://www.cs.utexas.edu/~fussell/courses/cs384g-fall2013/lectures/mitchell/Mitchell.pdf https://www.cs.utexas.edu/~fussell/courses/cs384g-fall2013/l... [2] https://www.inf.ufrgs.br/~eslgastal/SBS3/Rocha_Oliveira_Gastal_EG2020_Sharp_Filter_SBS3.pdf https://www.inf.ufrgs.br/~eslgastal/SBS3/Rocha_Oliveira_Gast...

muyyatin2 2y ago

I've been looking into how viable this is as a performant strategy. If you have non-overlapping areas, then contributions to a single pixel can be made independently (since it is just the sum of contributions). The usual approach (computing coverage and blending into the color) is more constrained, where the operations need to be done in back-to-front order.

mfabbri77 2y ago
I've been researching this field for 20 years (I'm one of the developers of AmanithVG). Unfortunately, no matter how fast they are made, all the algorithms to analytically decompose areas involve a step to find intersections and therefore sweepline approaches that are difficult to parallelize and therefore must be done in CPU. However, we are working on it for the next AmanithVG rasterizer, so I'm keeping my eyes open for all possible alternatives.
- muyyatin2 2y ago
  I ran across https://dl.acm.org/doi/pdf/10.1145/72935.72950 https://dl.acm.org/doi/pdf/10.1145/72935.72950 a few weeks ago, it seems like a potential non-sweepline highly-parallel method. I've had some promising results for first doing a higher-dimensional Hilbert-sort (giving spatial locality), and then being able to prune a very large percentage of the quadratic search space. It might still be too slow on the GPU. I'm curious if you have any write-ups on things that have been explored, or if I'd be able to pick your brain some time!
- dvdkon 2y ago
  I believe Vello does this for AA (though I can't find the source now), and it's very fast, running on the GPU via compute shaders.
  - raphlinus 2y ago
    No, Vello does not analytically find intersections. Compositing is (currently) done by alpha blending, which is consistent with the W3C spec but has its own tradeoffs.
- whenc 2y ago
  Here's one to look at: https://dl.acm.org/doi/10.1145/2980179.2982434 https://dl.acm.org/doi/10.1145/2980179.2982434

enriquto 2y ago

> compute the non-overlapping areas of each polygon within each pixel In the given example (periodic checkerboard), that would be impossible because the pixels that touch the horizon intersect an infinite amount of polygons. Not that TFA solves that problem either. As far as I know the exact rendering of a periodic pattern in perspective is an open problem.

shiandow 2y ago

If there's one thing I've learned from image processing it's that the idea of a pixel as a perfect square is somewhat overrated. Anti-aliasing is exactly as it sounds, a low-pass filter to prevent artefacts. Convolution with a square pulse is serviceable, but is not actually that good a low-pass filter, you get all kinds of moire effects. This is why a Bicubic kernel that kind of mimics a perfect low-pass filter (which would be a sinc kernel), can perform better. It is tempting to use a square kernel though, because it's pretty much the sharpest possible method of acceptable quality.

dahart 2y ago

Why are you convinced of this, and can I help unconvince you? ;) What you describe is what’s called “Box Filtering” in the article. Box filtering is well studied, and it is known to not be the best possible output quality. The reason this is not the best approach is because a pixel is not a little square, a pixel is a sample of a signal, and it has to be approached with signal processing and human perception in mind. (See the famous paper linked in the article: A Pixel is Not a Little Square, A Pixel is Not a Little Square, A Pixel is Not a Little Square http://alvyray.com/Memos/CG/Microsoft/6_pixel.pdf http://alvyray.com/Memos/CG/Microsoft/6_pixel.pdf) It can be surprising at first, but when you analytically compute the area of non-overlapping parts of a pixel (i.e., use Box Filtering) you can introduce high frequencies that cause visible aliasing artifacts that will never go away. This is also true if you are using sub-sampling of a pixel, taking point samples and averaging them, no matter how many samples you take. You can see the aliasing I’m talking about in the example at the top of the article, the 3rd one is the Box Filter - equivalent to computing the area of the polygons within each pixel. Look closely near the center of the circle where all the lines converge, and you can see little artifacts above and below, and to the left and right of the center, artifacts that are not there in the “Bilinear Filter” example on the right.

raphlinus 2y ago
I think the story is a lot more complicated. Talking about "the best possible output quality" is a big claim, and I have no reason to believe it can be achieved by mathematically simple techniques (ie linear convolution with a kernel). Quality is ultimately a function of human perception, which is complex and poorly understood, and optimizing for that is similarly not going to be easy. The Mitchell-Netravali paper[1] correctly describes sampling as a tradeoff space. If you optimize for frequency response (brick wall rejection of aliasing) the impulse response is sinc and you get a lot of ringing. If you optimize for total rejection of aliasing while maintaining positive support, you get something that looks like a Gaussian impulse response, which is very smooth but blurry. And if you optimize for small spatial support and lack of ringing, you get a box filter, which lets some aliasing through. Which is best, I think, depends on what you're filtering. For natural scenes, you can make an argument that the oblique projection approach of Rocha et al[2] is the optimal point in the tradeoff space. I tried it on text, though, and there were noticeable ringing artifacts; box filtering is definitely better quality to my eyes. I like to think about antialiasing specific test images. The Siemens star is very sensitive in showing aliasing, but it also makes sense to look at a half-plane and a thin line, as they're more accurate models of real 2D scenes that people care about. It's hard to imagine doing better than a box filter for a half-plane; either you get ringing (which has the additional negative impact of clipping when the half-planes are at the gamut boundary of the display; not something you have to worry about with natural images) or blurriness. In particular, a tent filter is going to be softer but your eye won't pick up the reduction in aliasing, though it is certainly present in the frequency domain. A thin line is a different story. With a box filter, you get basically a non antialiased line of single pixel thickness, just less alpha, and it's clearly possible to do better; a tent filter is going to look better. But a thin line is just a linear combination of two half-planes. So if you accept that a box filter is better visual quality than a tent filter for a half-plane, and the other way around for a thin line, then the conclusion is that linear filtering is not the correct path to truly highest quality. With the exception of thin lines, for most 2D scenes a box filter with antialiasing done in the correct color space is very close to the best quality - maybe the midwit meme applies, and it does make sense to model a pixel as a little square in that case. But I am interested in the question of how to truly achieve the best quality, and I don't think we really know the answer yet. [1] https://www.cs.utexas.edu/~fussell/courses/cs384g-fall2013/lectures/mitchell/Mitchell.pdf https://www.cs.utexas.edu/~fussell/courses/cs384g-fall2013/l... [2] https://www.inf.ufrgs.br/~eslgastal/SBS3/Rocha_Oliveira_Gastal_EG2020_Sharp_Filter_SBS3.pdf https://www.inf.ufrgs.br/~eslgastal/SBS3/Rocha_Oliveira_Gast...