Computer Graphics Volume 18, Number 3 July 1984 Summed-Area Tables for Texture Mapping Franklin C. Crow Computer Sciences Laboratory Xerox Palo Alto Research Center Abstract Texture-map computations can be made tractable through use of precalculated tables which allow computational costs independent of the texture density. The first example of this technique, the "mip" map, uses a set of tables containing successively lower-resolution representations filtered down from the discrete texture function. An alternative method using a single table of values representing the integral over the texture function rather than the function itself may yield superior results at similar cost. The necessary algorithms to support the new technique are explained. Finally, the cost and performance of the new technique is compared to previous techniques. CR Categories and Subject Headings: 1.3.3 [Computer Graphics]: Picture/Image Generation - display algorithms; 1.3.7 [Computer Graphics]: Three-Dimensional Graphics and Realism - color, shading, shadowing and texture. General Terms: Algorithms, Performance Additional Keywords and Phrases: antialiasing, texture mapping, shading algorithms, table lookup algorithms 1.0 Introduction A frequent criticism of early attempts at realism in computer-synthesized images was that the surfaces lacked interest. At first all surfaces had a dull matte finish. Later surfaces acquired shininess and transparency. However, much of the attraction of real surfaces lies in the incredibly complex local surface variations known as texture. These variations are much too complicated to be modeled by conventional means which require enough vertices or control points to accurately reproduce the surface. In 1974, Catmull [3] conceived and implemented the first system to use images of texture applied to surfaces to give the affect of actual texture. Blinn and Newell [1] generalized Catmull's work and extended it to include environmental reflections. Blinn [2] then further extended the notion (rather spectacularly!) to achieve the appearance of undulations on the surface (the earlier efforts achieved only flat texture, such as the fake wood texturing found on many plastic desk tops). Carrying things a bit farther, researchers at Ohio State [7] experimented with various expansions of polygonal surfaces to achieve "real" texture. Although some very interesting Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Association for Computing Machinery. To copy otherwise, or to republish, requires a fee and/or specific permission. © 1984 ACM 0-89791-138-5/84/007/0207 $00.75 images resulted, the technique would be too cumbersome for anything very complex. When texture is mapped onto a surface it must be stretched here and compressed there in order to fit the shape of the surface. 3-D perspective views further distort texture mapped onto a curving surface. As a digital image is synthesized, a pair of texture coordinates must be calculated for each pixel representing a textured surface. The most straightforward implementation of texture mapping simply chooses the pixel from the texture image which lies closest to the computed texture coordinates (the "nearest pixel" algorithm). This works well for a certain class of textures and surfaces. A frequent example of texture mapping uses a rectangular texture image mapped onto a sphere. Here the compression that each part of the texture image will undergo when mapped is known in advance. The texture can be designed in such a way that it is "pre-stretched" along the top and bottom where it will be mapped near the poles of the sphere. However, unless the texture image is very smooth, with no sharp detail, aliasing becomes an immediate problem. Sharp details will become jagged and the texture will break up where it is highly compressed. Where the mapping is not known in advance, aliasing cannot be controlled just by judiciously designing the texture. Blinn [2] and later Feibush et al [5] discuss this problem in detail and implemeuted good, but very expensive solutions. If the pixel being computed is considered a small area, texture coordinates may be computed for the corners of each such area. The pixel intensity is then the average of all texture elements bounded by the corners, weighted by a filter function. In places where the texture is highly compressed (e.g., at the poles of a sphere), this operation may require a weighted sum of hundreds of texture values. Catmull and Smith [4] show a way of simplifying the calculation of the texture intensity by separating the convolution into two passes. The method was initially applied just to represent transformed images on a raster. A horizontal pass over the texture is followed by a vertical pass, producing texture values as they should appear in the image. The simplicity of the process makes it amenable to hardware implementation; a similar technique is currently very much in vogue for special-effects in television. However, where the texture is highly compressed, many texture pixels must still be processed to yield a single image pixel. Norton, Rockwood and Skomolski [9] report a method for limiting texture detail to the appropriate level by expressing 207@SIGGRAPH'84 Figure 1: Texture distortion texture as a sum of band-limited terms of increasing frequencies. Where the frequency of a term (i.e., its level of detail) exceeds the pixel frequency, that term is "clamped" (forced to the local average value for the term). The method has been applied, in a very restricted way, but with excellent effecL in a real-time visual system for flight simulators. In order to use this method the texture must be divided into terms using Fourier analysis or similar techniques. Alternatively, the texture may be synthesized from Fourier terms. In a remotely similar vein, Haruyama