Texture mapping is an important step in creating realistic images. It's very important that textures look like they "belong" on a surface. This requires artists to create textures that work well, and then use programs that filter those textures when rendering.

Correct filtering is hard, and slow. The most common approach is called mip-mapping, which uses square, or isotropic, filters. This means that if an object is in sharp perspective, with part of it very close and part far away, the texture will appear warped. To fix this problem, we must use anisotropic filters, which are slower. A nice compromise is the sum table, which uses rectangular filters rather than just a square.

I wanted to make an even better filter that would only be used when necessary. Suppose that you have a four-sided shape, and you want to know the color of the pixels inside it. And you have the surrounding, or bounding, box. Then you could just use the average color inside the box. Or, you could "chip away" at that surrounding box, removing smaller boxes that are outside the region you care about, until you're left with a very finely-grained chunky approximation of the shape you want.

One nice aspect of this approach is that you can run it only as much as you need it. If the color of the enclosing box is fine, just use that. If you want a little more precision, chip away at it a little. If you want more precision, chip away some more.

I show how to do this "chipping away" in the most efficient fashion, and also give some metrics for deciding how much of this area removal one needs to do for any given pixel.

Here are two examples from the paper. Please note that I don't have the original files, so I scanned these in and tried to clean them up a little in Photoshop.

The picture on the left shows a checkerboard in perspective. In the bottom-left corner I use sum tables (which perform even better than mipmaps). The region in the red box is blown up in the upper-left corner, and you can see that the image first begins to alias, and then turns into a grey smear. In the bottom-right I use the algorithm presented here, in the upper-right I show a blown-up version. Notice that it looks like right out to the horizon!

The image on the right follows the same layout, but uses a checkerboard at a 45-degree angle.

The fun part of this algorithm is that it's all about geometry!

On the left is a table that summarizes all the different ways that four points can create a quadrilteral, including the degenerate ones. There are only a few cases that lead to interesting regions the can contain texture.

The flowchart on the right shows how to categorizing the non-trivial cases using just a couple of geometric measurements. The algorithm is fast, accurate, and efficient.

You can find all the details, including larger and cleaner versions of the figures above, in the published paper. Here's the complete citation:

Glassner, Andrew S., "Adaptive Precision in Texture Mapping", Proceedings of SIGGRAPH 86, Computer Graphics Volume 20, Number 4, pp. 297-306