Exact Polygonal Filtering: Using Green's Theorem and Clipping for Anti-Aliasing (opens in new tab)

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.

There’s a picture of the exact operation in the article. Under “Filters”, the first row of 3 pictures has the caption “Box Filter”. The one on the right (with internal caption “Contribution (product of both)”) demonstrates the analytic box filter. The analytic box filter is computed by taking the intersection of the pixel boundary with all visible polygons that touch the pixel, and then summing the resulting colors weighted by their area. Note the polygon fragments also have to be non-overlapping, so if there are overlapping polygons, the hidden parts need to be first trimmed away using boolean clipping operations. This can all be fairly expensive to compute, depending on how many overlapping polygons touch the pixel.

It is more similar to the convolution of the shape with the filter (you can take the product of the filter, at various offsets, with the polygon)

Essentially if you have a polygon function p(x,y) => { 1 if inside the polygon, otherwise 0 }, and a filter function f(x,y) centered at the origin, then you can evaluate the filter at any point x_0,y_0 with the double-integral / total sum of f(x-x_0,y-y_0)*p(x,y).

It literally means that you take a box-shaped piece of the polygon, ie. the intersection of the polygon and a box (a square, in this case the size of one pixel). And do this for each pixel as they’re processed by the rasterizer. If you think of a polygon as a function from R^2 to {0, 1}, where every point inside the polygon maps to 1, then it’s just a signal that you can apply filters to.

If it's textured, an anisotropic filter is a good approximation of the constant colour over the pixel area. The main source of aliasing is the polygon edge, not the texture

Anything is constant colour if you dice it up into small enough pieces! :-)

But the blurring example has a gradient on the star?

Ahh yes, for exact filtering it does need to be constant colour. I'm looking into seeing whether it can be done for gradients. However in practice, it works quite well visually to compute the "average color of the polygon" for each piecewise section, and blend those together.

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)

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.

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.

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.

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

You might be making some incorrect assumptions about what this article is describing. It’s not limited to a single polygon against a background.

Analytic integration is always superior to multisampling, assuming the same choice of filter, and as long as the analytic integration is correct. Your comment is making an assumption that the analytic integration is incorrect in the presence of multiple polygons. This isn’t true though, the article is using multiple polygons, though the demo is limited in multiple ways for simplicity, it doesn’t appear to handle any arbitrary situation.

The limitations of the demo (whether it handles overlapping polygons, stitched meshes, textures, etc.) does not have any bearing on the conceptual point that computing the pixel analytically is better than taking multiple point samples. GPUs use multisampling because it’s easy and finite to compute, not because it’s higher quality. Multisampling is lower quality than analytic, but it’s far, far easier to productize, and it’s good enough for most things (especially games).

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.

The web page is able to slow down my Android phone to the point that it stops responding to power button click. If you told me this page exploits a 0-day vulnerability in Android I would have believed it. Impressive.

(Android 14, Android WebView/Chrome 127)

The analytic approach to occlusion definitely does seem like a "humbling parallelism" type of problem on the GPU. My curiosity is leading me to explore it, and it may be reasonable if I find alternatives to large GPU sorts (although I understand you've done some work on that recently). I think the Vello approach is very likely the superior option for the best general quality/performance tradeoff.

You order your operations by depth.

If you want to go hardcore into the frequency domain, may I suggest "A Fresh Look at Generalized Sampling" by Nehab and Hoppe[1]. That said, while a frequency-centric approach works super well for audio, for images you need to keep good track of what happens in the spatial domain, and in particular the support of sampling filters needs to be small.

[1]: https://hhoppe.com/filtering.pdf