Fantastic article, exactly my kinda thing :) One significant limitation here is that the polygon needs to have constant colour, unfortunately.
Anything is constant colour if you dice it up into small enough pieces! :-)
Exact Polygonal Filtering: Using Green's Theorem and Clipping for Anti-Aliasing
21–30 of 86 posts
Re: Exact Polygonal Filtering: Using Green's Theorem and Clipping for Anti-Aliasing
#22Fantastic article, exactly my kinda thing :) One significant limitation here is that the polygon needs to have constant colour, unfortunately.
But the blurring example has a gradient on the star?
Re: Exact Polygonal Filtering: Using Green's Theorem and Clipping for Anti-Aliasing
#23The opening statement makes it out that this exact calculation is supposed to be superior to multisampling, but the opposite is the case. Computing the exact mathematical coverage of a single polygon against a background is useless for animations if you can't seamlessly stitch multiple polygons together. And that's why GPUs use multisampling: Each sample is an exact mathematical point that's covered by either polygon…
If you can't stitch polygons together seamlessly, how can you be sure the background doesn't bleed through with sampling? Isn't computing the exact coverage the same as having infinitely many point samples? The bleed-through of the background would then also be proportional to the gap between polygons, so if that one's small, the bleeding would be minor as well.
Re: Exact Polygonal Filtering: Using Green's Theorem and Clipping for Anti-Aliasing
#24The opening statement makes it out that this exact calculation is supposed to be superior to multisampling, but the opposite is the case. Computing the exact mathematical coverage of a single polygon against a background is useless for animations if you can't seamlessly stitch multiple polygons together. And that's why GPUs use multisampling: Each sample is an exact mathematical point that's covered by either polygon…
[dead]
Re: Exact Polygonal Filtering: Using Green's Theorem and Clipping for Anti-Aliasing
#25> This is equivalent to applying a box filter to the polygon, which is the simplest form of filtering. Am I the only one who has trouble understanding what is meant by this? What is the exact operation that's referred to here? I know box filters in the context of 2D image filtering and they're straightforward but the concept of applying them to shapes just doesn't make any sense to me. Can someone clarify?
The operation (filtering an ideal, mathematically perfect image) can be described in two equivalent ways:
- You take a square a single pixel spacing wide by its center and attach it to a sampling point (“center of a pixel”). The value of that pixel is then your mathematically perfect image (of a polygon) integrated over that square (and normalized). This is perhaps the more intuitive definition.
- You take a box kernel (the indicator function of that square, centered, normalized), take the convolution[1] of it with the original perfect image, then sample the result at the final points (“pixel centers”). This is the standard definition, which yields exactly the same result as long as your kernel is symmetric (which the box kernel is).
The connection with the pixel-image filtering case is that you take the perfect image to be composed of delta functions at the original pixel centers and multiplied by the original pixel values. That is, in the first definition above, “integrate” means to sum the original pixel values multiplied by the filter’s value at the original pixel centers (for a box filter, zero if outside the box—i.e. throw away the addend—and a normalization constant if inside it). Alternatively, in the second definition above, “take the convolution” means to attach a copy of the filter (still sized according to the new pixel spacing) multiplied by the original pixel value to the original pixel center and sum up any overlaps. Try proving both of these give the answer you’re already accustomed to.
This is the most honest signal-processing answer, and it might be a bit challenging to work through but my hope is that it’ll be ultimately doable. I’m sure there’ll be neighboring answers in more elementary terms, but this is ultimately a (two-dimensional) signal processing task and there’s value in knowing exactly what those signal processing people are talking about.
[1] (f∗g)(x) = (g∗f)(x) = ∫f(y)g(x-y)dy is the definition you’re most likely to encounter. Equivalently, (f∗g)(x) is f(y)g(z) integrated over the line (plane, etc.) x=y+z, which sounds a bit more vague but exposes the underlying symmetry more directly. Convolving an image with a box filter gives you, at each point, the average of the original over the box centered around that point.
Re: Exact Polygonal Filtering: Using Green's Theorem and Clipping for Anti-Aliasing
#26The opening statement makes it out that this exact calculation is supposed to be superior to multisampling, but the opposite is the case. Computing the exact mathematical coverage of a single polygon against a background is useless for animations if you can't seamlessly stitch multiple polygons together. And that's why GPUs use multisampling: Each sample is an exact mathematical point that's covered by either polygon…
[deleted]
Re: Exact Polygonal Filtering: Using Green's Theorem and Clipping for Anti-Aliasing
#27> This is equivalent to applying a box filter to the polygon, which is the simplest form of filtering. Am I the only one who has trouble understanding what is meant by this? What is the exact operation that's referred to here? I know box filters in the context of 2D image filtering and they're straightforward but the concept of applying them to shapes just doesn't make any sense to me. Can someone clarify?
[deleted]
Re: Exact Polygonal Filtering: Using Green's Theorem and Clipping for Anti-Aliasing
#28The opening statement makes it out that this exact calculation is supposed to be superior to multisampling, but the opposite is the case. Computing the exact mathematical coverage of a single polygon against a background is useless for animations if you can't seamlessly stitch multiple polygons together. And that's why GPUs use multisampling: Each sample is an exact mathematical point that's covered by either polygon…
[deleted]
Re: Exact Polygonal Filtering: Using Green's Theorem and Clipping for Anti-Aliasing
#29The opening statement makes it out that this exact calculation is supposed to be superior to multisampling, but the opposite is the case. Computing the exact mathematical coverage of a single polygon against a background is useless for animations if you can't seamlessly stitch multiple polygons together. And that's why GPUs use multisampling: Each sample is an exact mathematical point that's covered by either polygon…
If you can't stitch polygons together seamlessly, how can you be sure the background doesn't bleed through with sampling? Isn't computing the exact coverage the same as having infinitely many point samples? The bleed-through of the background would then also be proportional to the gap between polygons, so if that one's small, the bleeding would be minor as well.
No, in animated models, there is no gap between polygons. And if you only compute single-polygon coverage, you can’t determine whether for two polygons that each cover 50% of a pixel, they both cover the same 50%, or complementary 50%, or anything in between. In practice, systems like that tend to show something like 25% background, 25% polygon A and 50% polygon B for the seam pixels, depending on draw order. That is, you get 25% background bleed.
Re: Exact Polygonal Filtering: Using Green's Theorem and Clipping for Anti-Aliasing
#30I 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.
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.