Help me grasp Anisotropic Filtering (AF) Lately I've been reading about texture filtering, namely Nearest-neighbor filtering, Bilinear filtering, Trilinear filtering, Anisotropic filtering, MIP maps, RIP Maps and so on. 

From a high-level perspective I think I can understand these techniques, how the work and why they exist, with the exception of Anisotropic filtering. Anisotropic filtering is driving me nuts. 

I can see the problem of having to texturize a surface that is at an angle relative to the camera, but I don't get how sampling trapezoidal footprints could solve this (although I can see the result). This is probably because I DO NOT understand how the trapezoidal footprint is calculated and how the enclosed telexes are weighted to sample the texture. 

This article by Nvidia confuses me even more by using sentences as "when a texel is trapezoidal" or "anisotropic filtering scales either the height or width of a mipmap by a ratio relative to the perspective distortion of the texture". Trapezoidal texel? Scaling a MIPmap? What does this even mean?

Could you help me grasp how AF and AF levels work? 

Please note that my goal is NOT to have an OpenGL or DirectX AF implementation, but rather to grasp how AF works from a high-level perspective.
To understand the nature of anisotropic filtering, you need to have a firm understanding of what texture mapping really means.

The term "texture mapping" means to assign positions on an object to locations in a texture. This permits the rasterizer/shader to, for each position on the object, fetch the corresponding data from the texture. The traditional method for doing this is to assign each vertex on an object a texture coordinate, which directly maps that position to a location in the texture. The rasterizer will interpolate this texture coordinate across the faces of the various triangles to produce the texture coordinate used to fetch the color from the texture.

Now, let's think about the process of rasterization. How does that work? It takes a triangle and breaks it up into pixel-sized blocks which we will call "fragments". Now, these pixel-sized blocks are pixel-sized relative to the screen.

But these fragments are not pixel-sized relative to the texture. Imagine if our rasterizer generated a texture coordinate for each corner of the fragment. Now imagine drawing those 4 corners, not in screen space, but in texture space. What shape would this be?

Well, that depends on the texture coordinates. That is, it depends on how the texture is mapped to the polygon. For any particular fragment, it might be an axis-aligned square. It might be a non-axis-aligned square. It might be a rectangle. It might be a trapezoid. It might be pretty much any four-sided figure (or at least, convex ones).

If you were doing texture accessing correctly, the way to get the texture color for a fragment would be to figure out what this rectangle is. Then fetch every texel from the texture within that rectangle (using coverage to scale colors that are on the border). Then average them all together. That would be perfect texture mapping.

It would also be exceedingly slow.

In the interest of performance, we instead try to approximate the real answer. We base things on one texture coordinate, rather than the 4 that cover the entire fragment's area in texel space.

Mipmap-based filtering uses lower-resolution images. These images are basically a shortcut for the perfect method, by pre-computing what large blocks of colors would look like when blended together. So when it selects a lower mipmap, it is using pre-computed values where each texel represents an area of the texture.

Anisotropic filtering works by approximating the perfect method (which can, and should, be coupled with mipmapping) through taking up to a fixed number of additional samples. But how does it figure out the area in texel space to fetch from, since it's still only given one texture coordinate?

Basically, it cheats. Because fragment shaders are executed in 2x2 neighboring blocks, it is possible to compute the derivative of any value in the fragment shader in screen-space X and Y. It then uses these derivatives, coupled with the actual texture coordinate, to compute an approximation of what the true fragment's texture footprint would be. And then it performs a number of samples within this area.

Here's a diagram to help explain it:



The black-and-white squares represent our texture. It's just a checkerboard of 2x2 white and black texels.

The orange dot is the texture coordinate for the fragment in question. The red outline is the fragment's footprint, which is centered on the texture coordinate.

The green boxes represent the texels that an anisotropic filtering implementation might access (the details of anisotropic filtering algorithms are platform specific, so I can only explain the general idea). 

This particular diagram suggests that an implementation might access 4 texels. Oh yes, the green boxes cover 7 of them, but the green box in the center could fetch from a smaller mipmap, thus fetching the equivalent of 4 texels in one fetch. The implementation would of course weight the average for that fetch by 4 relative to the single texel ones.

If the anisotropic filtering limit was 2 rather than 4 (or higher), then the implementation would pick 2 of those samples to represent the fragment's footprint.