> 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.
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.
OK, so reading a bit further this boils down to clipping the polygon to the pixel and then using the shoelace formula for finding the area? Why call it "box filter" then?
It’s very useful to point out that it’s a Box Filter because the article moves on to using other filters, and larger clipping regions than a single pixel. This is framing the operation in known signal processing terminology, because that’s what you need to do in order to fully understand very high quality rendering.
Dig a little further into the “bilinear filter” and “bicubic filter” that follow the box filter discussion. They are more interesting than the box filter because the contribution of a clipped polygon is not constant across the polygon fragment, unlike the box filter which is constant across each fragment. Integrating non-constant contribution is where Green’s Theorem comes in.
It’s also conceptually useful to understand the equivalence between box filtering with analytic computation and box filtering with multi-sample point sampling. It is the same mathematical convolution in both cases, but it expressed very very differently depending on how you sample & integrate.
Oh interesting, I hadn’t thought about it, but why does it seem like poor naming? I believe “filter” is totally standard in signal processing and has been for a long time, and that term does make sense to me in this case because what we’re trying to do is low-pass filter the signal, really. The filtering is achieve through convolution, and to your point I think there might be cases in which referring to the filter function as a basis function occurs.
I would think that conceptually that a basis function is different form a filter function because a basis function is usually about transforming a point in one space to some different space, and basis functions come in a set that’s the size of the dimensionality of the target space. Filters, even if you can think of the function as a sort of basis, aren’t meant for changing spaces or encoding & decoding against a different basis than the signal. Filters transform the signal but keep it in the same space it started from, and the filter is singular and might lose data.
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).
This kind of makes sense from a mathematical point of view, but how would this look implementation-wise, in a scenario where you need to render a polygon scene? The article states that box filters are "the simplest form of filtering", but it sounds quite non-trivial for that use case.
If it essentially calculates the area of the polygon inside the pixel box and then assigns a colour to the pixel based on the area portion, how would any spatial aliasing artifacts appear? Shouldn't it be equivalent to super-sampling with infinite sample points?
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.
But as I understand it, the article is about rasterization, so if we filter after rasterization, the sampling has already happened, no? In other words: Isn't this about using the intersection of polygon x square instead of single sample per pixel rasterization?
This is about taking an analytic sample of the scene with an expression that includes and accounts for the choice of filter, instead of integrating some number of point samples of the scene within a pixel.
In this case, the filtering and the sampling of the scene are both wrapped into the operation of intersection of the square with polygons. The filtering and the sampling are happening during rasterization, not before or after.
Keep in mind a pixel is an image sample, which is different from taking one or many point-samples of the scene in order to compute the pixel color.
The problem is determining the coverage, the contribution of the polygon to a pixel's final color, weighted by a filter. This is relevant at polygon edges, where a pixel straddles one or more edges, and some sort of anti-aliasing is required to prevent jaggies[1] and similar aliasing artifacts, such as moiré, which would result from naive discretization (where each pixel is either 100% or 0% covered by a polygon, typically based on whether the polygon covers the pixel center).
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?