The Main Idea

Modern synthetic images use a lot of textures. But theoretically correct filtering is mathematically complex, and slow. The basic idea is to find the average value of a texture within some region, most often a 4-sided convex polygon. Computing this on the fly for any polygon is too slow for almost all everyday use, and definitely far too slow for real-time applications like games.

The most common way to speed things up is called mip-mapping, where we pretend that each polygon is a square. This is very fast, but it can give us incorrect values when the polygon is long and skinny, or some other non-square shape. A more accurate approach is to use sum tables, which pretend that every polygon is a rectangle. Of course, if the polygon is not rectangle-like, this too can give us wrong results.

My idea was to use a sum table not once, but several times. For any 4-sided polygon, find the rectangle that encloses it, and from the sum table get the average color. We also save a measure of how much the texture is changing. If the texture has a lot of variation in that rectangle, then “chip away” at it by finding the biggest rectangle that fits between the original polygon and the rectangle that encloses it, and remove the average color in that rectangle from the polygon’s average. If there’s still a lot of variation, continue chipping away, removing ever-smaller rectangles. This gives you an ever-better answer, and you simply stop when it’s good enough.

Here’s an example from the paper. Please note that I don’t have the original files, so I scanned this in and cleaned it up a little in Photoshop.

The bottom images show a checkerboard in perspective. In the bottom-left corner I used sum tables for texturing. 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 used my algorithm, in the upper-right I show a blown-up version. It’s not perfect, of course, but it’s a lot better!

Reference

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