Adaptive Precision
in Texture Mapping
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 triangle or 4-sided convex polygon. In 1986, computing this on the fly for any polygon was too slow for real-time applications like flight simulators and 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. Since I don’t have the original files, I scanned this in from a copy of the SIGGRAPH Proceedings 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, because like mip-maps and sum tables this method is still an approximation, but it’s a lot better!
Looking at this now, I see a noticeable transition about halfway up the enlargement in the upper right, and then an unexpected jump about 2/5 of the way up from there. That might be an artifact of my approximation, or a coding error. I’d love to go back to the code and investigate this, but it’s been long since lost to the mists of time.
References
Glassner, Andrew S., “Adaptive Precision in Texture Mapping”, Proceedings of SIGGRAPH 86, Computer Graphics Volume 20, Number 4, pp. 297-306