Summed-area tables for texture mapping

F. Crow

article1984SIGGRAPH1,564 citations

Introduces summed-area tables, a foundational texture-filtering technique that computes exact rectangular area averages in constant time using four table lookups to avoid anisotropic blurring common in standard mipmapping.

Palo Alto Research Center interpolation algorithms random access memory spline interpolation summed-area tables texture mapping texture coordinates

Crow (1984).pdf

Cover for Summed-area tables for texture mapping

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.

Topics

interpolation algorithms random access memory spline interpolation local texture shape information graphics hardware real-time rendering

Keywords

summed-area tables texture mapping texture coordinates texture memory incremental interpolation

1.0 Introduction
2.0 Using A Table Of Summed Areas For Texture Mapping
2.1 The Basic Technique
2.2 Comparisons with the Multiple Table Mip Map
2.3 Calculating Texture Coordinates
2.4 Handling Texture Image Boundaries
3.0 Building And Storing A Summed Area Table
4.0 Conclusions
References

Knowls

Knowl 1 — Definition of Summed-Area Table
definition
A summed-area table (also known as an integral image) is a two-dimensional data structure $T$ derived from a discrete texture or image $I$ of dimensions $W \times H$ , where each entry $T[x, y]$ at discrete coordinates $(x, y)$ stores the sum of all pixel intensity values within the axis-aligned rectangular region spanning from the origin $(0, 0)$ at the lower-left corner up to and including $(x, y)$ :

$T[x, y] = \sum_{u=0}^{x} \sum_{v=0}^{y} I[u, v]$

where $0 \le x < W$ and $0 \le y < H$ , and $I[u, v]$ represents the discrete intensity value of the texture element at $(u, v)$ .
Knowl 2 — Rectangular Area Intensity Evaluation via Inclusion-Exclusion
equation
Given a precomputed summed-area table $T$ , the sum of texture intensities over an arbitrary axis-aligned rectangular region bounded by horizontal coordinates $[x_l, x_r]$ and vertical coordinates $[y_b, y_t]$ (with $x_l \le x_r$ and $y_b \le y_t$ ) is calculated in $O(1)$ time using four table lookups via the principle of inclusion-exclusion:

$\text{Sum}(x_l, x_r, y_b, y_t) = T[x_r, y_t] - T[x_r, y_b] - T[x_l, y_t] + T[x_l, y_b]$

where $T[x, y]$ denotes the summed-area table entry at coordinate $(x, y)$ .

The average texture intensity $\bar{I}$ over this rectangular region is obtained by dividing the sum by the region's continuous area:

$\bar{I} = \frac{\text{Sum}(x_l, x_r, y_b, y_t)}{\text{Area}} = \frac{T[x_r, y_t] - T[x_r, y_b] - T[x_l, y_t] + T[x_l, y_b]}{(x_r - x_l)(y_t - y_b)}$

where $(x_r - x_l)(y_t - y_b)$ is the total area of the sampled rectangular box-filter footprint in texture coordinate space.
Knowl 3 — Anisotropic Rectangular Filtering Capability of Summed-Area Tables
theoretical result
When textured surfaces are viewed obliquely or curve away from the viewer, pixel footprints map to anisotropic regions in texture space that are compressed much more along one dimension than the other.
- MIP mapping limitation: MIP maps precompute isotropic (square) downsampled representations. To avoid aliasing, the MIP level must be chosen based on the axis of maximum compression, which causes excessive over-blurring along the less-compressed axis.
- Summed-area table advantage: Summed-area tables evaluate independent rectangular footprints $[x_l, x_r] \times [y_b, y_t]$ . The horizontal and vertical dimensions of the integration box vary independently, allowing the filter to adapt to asymmetric texture compression and preserve sharp detail along the weakly compressed axis while filtering out aliasing along the strongly compressed axis.
Knowl 4 — Efficient Incremental Summed-Area Table Construction
algorithm
A summed-area table $T$ can be generated from an input texture image $I$ of width $W$ and height $H$ with an arithmetic complexity of only two addition operations per pixel by maintaining a running horizontal scanline sum.
Input: Texture image $I$ of size $W \times H$ with coordinates $(x, y) \in [0, W-1] \times [0, H-1]$
Output: Summed-area table $T$ of size $W \times H$
for $y \leftarrow 0$ to $H - 1$ do
     $\text{row\_sum} \leftarrow 0$
    for $x \leftarrow 0$ to $W - 1$ do
         $\text{row\_sum} \leftarrow \text{row\_sum} + I[x, y]$
        if $y = 0$ then
             $T[x, y] \leftarrow \text{row\_sum}$
        else
             $T[x, y] \leftarrow T[x, y - 1] + \text{row\_sum}$
        end if
    end for
end for
Alternatively, direct 2D inclusion-exclusion can construct the table via $T[x, y] = I[x, y] + T[x, y - 1] + T[x - 1, y] - T[x - 1, y - 1]$ (with appropriate zero-boundary conditions), requiring three additions/subtractions per entry.
Knowl 5 — Texture Filtering via Sub-Pixel Bilinear Interpolation of Corner Values
model/method
To prevent aliasing and motion jitter when texture footprint boundaries do not fall exactly on integer grid locations (such as under texture expansion or mild compression), the corners of the bounding rectangle $[x_l, x_r] \times [y_b, y_t]$ are evaluated at real-valued coordinates.

Each of the four corner table values $\tilde{T}(x, y)$ for $(x, y) \in \{(x_l, y_b), (x_r, y_b), (x_l, y_t), (x_r, y_t)\}$ is computed via bilinear interpolation from the four nearest discrete entries in the summed-area table:
1. Locate the four discrete table entries surrounding the continuous coordinate $(x, y)$ : $(\lfloor x \rfloor, \lfloor y \rfloor)$ , $(\lceil x \rceil, \lfloor y \rfloor)$ , $(\lfloor x \rfloor, \lceil y \rceil)$ , and $(\lceil x \rceil, \lceil y \rceil)$ .
2. Perform two linear interpolations along the horizontal axis using fractional offset $\alpha_x = x - \lfloor x \rfloor$ .
3. Perform a final linear interpolation along the vertical axis using fractional offset $\alpha_y = y - \lfloor y \rfloor$ .
Once the continuous values $\tilde{T}(x_r, y_t)$ , $\tilde{T}(x_r, y_b)$ , $\tilde{T}(x_l, y_t)$ , and $\tilde{T}(x_l, y_b)$ are calculated, the average intensity is evaluated as $(\tilde{T}(x_r, y_t) - \tilde{T}(x_r, y_b) - \tilde{T}(x_l, y_t) + \tilde{T}(x_l, y_b)) / ((x_r - x_l)(y_t - y_b))$ .
Knowl 6 — Computational and Memory Access Complexity Comparison with MIP Mapping
theoretical result
The computational cost and memory bandwidth required to evaluate a single texture sample compare as follows:
- Summed-area table with corner bilinear interpolation: Interpolating 4 corners requires $4 \times 4 = 16$ texture memory accesses. Each bilinear interpolation requires 3 linear interpolations ( $b + (c - b)\alpha$ ), giving $4 \times 3 = 12$ additions and $4 \times 3 = 12$ multiplications. Combining corner values adds 3 additions/subtractions, 1 multiplication for the area, and 1 division for averaging, totaling 16 memory accesses, 14 multiplications/divisions, and 27 additions/subtractions.
- Summed-area table under high compression (no corner interpolation): When the footprint spans many pixels, corner interpolation error is negligible. Omission of corner interpolation reduces the cost to 4 memory accesses, 2 multiplications/divisions, and 3 additions/subtractions.
- MIP mapping (trilinear filtering): Accesses two adjacent resolution levels (each requiring a 4-tap bilinear interpolation) followed by linear blending between the two levels, requiring 8 memory accesses, 7 multiplications, and 14 additions.
Knowl 7 — Precision Requirements and Block-Offset Storage for Summed-Area Tables
model/method
Because entries in a summed-area table accumulate pixel intensities across the entire image, the required numeric word length scales with the image dimensions and channel bit depth:
- For an $N \times N$ texture with $B$ -bit intensities (maximum value $2^B - 1$ ), the maximum sum is $N^2(2^B - 1)$ . For a $1024 \times 1024$ texture with 8-bit channels ( $B=8$ ), the maximum sum is $1024 \times 1024 \times 255 \approx 2.67 \times 10^8$ , requiring 28 bits per entry (stored in 32-bit words). A $256 \times 256$ 8-bit texture requires 24 bits per entry.
- Compared to MIP mapping (which adds approximately $33\%$ storage overhead), summed-area tables increase memory requirements by a factor of 2 to 4 over the original 8-bit image.
- To reduce memory consumption, the image can be partitioned into $16 \times 16$ pixel blocks. Within each block, the local sum cannot exceed $256 \times 255 = 65{,}280$ , which fits in 16 bits. Storing a single 32-bit base value per block for its lower-left corner adds an overhead of 2 bits per entry, yielding an effective size of 18 bits per entry (or down to 14 bits per entry with nested 12-bit representations).
Knowl 8 — Texture Footprint Bounding Box Estimation from Screen Derivatives
algorithm
To determine the axis-aligned rectangular footprint $[x_l, x_r] \times [y_b, y_t]$ in texture space for a given screen pixel, horizontal and vertical screen-space derivative increments of the texture coordinates $(u, v)$ are bounded:
Input: Texture coordinates $(u, v)$ at the current pixel, horizontal step increments $(\Delta u_x, \Delta v_x)$ , vertical step increments $(\Delta u_y, \Delta v_y)$
Output: Rectangular texture bounding box $[x_l, x_r] \times [y_b, y_t]$
$\Delta x \leftarrow \max(|\Delta u_x|, |\Delta u_y|)$
$\Delta y \leftarrow \max(|\Delta v_x|, |\Delta v_y|)$
$x_l \leftarrow u - \frac{\Delta x}{2}$
$x_r \leftarrow u + \frac{\Delta x}{2}$
$y_b \leftarrow v - \frac{\Delta y}{2}$
$y_t \leftarrow v + \frac{\Delta y}{2}$
Along each scan segment, horizontal increments $(\Delta u_x, \Delta v_x)$ are constant and computed by linear interpolation across the segment. Vertical increments $(\Delta u_y, \Delta v_y)$ are linearly interpolated across the scanline from the vertical increments maintained at the segment endpoints.
Knowl 9 — Handling Texture Boundaries and Wrapping in Summed-Area Tables
model/method
When a pixel's rectangular filter footprint extends across the boundaries of a texture map:
- Partially covered surfaces: When a texture covers only a part of a surface without repeating, texture coordinates are clamped to the valid texture bounds $[0, W-1] \times [0, H-1]$ when querying the summed-area table, while the area denominator $(x_r - x_l)(y_t - y_b)$ retains its unclipped dimensions. This attenuates the average intensity proportionally to the fraction of the pixel covering the texture.
- Replicated / repeating textures: When a texture repeats periodically across a surface, coordinates wrap around. Lookups beyond a boundary are calculated by adding the total table sum accumulated at the boundary to the wrapped lookup value. If a footprint spans multiple full texture periods in a single pixel, multiple full-table boundary sums are accumulated.

Coverage note — No substantial contributed material was omitted.

References

1.Blinn, J. and Newell, M., "Texture and Reflection on Computer Generated Images", Communications of the ACM, Vol. 19, #10, Oct. 1976.
2.Blinn, J., "Computer Display of Curved Surfaces", PhD. Dissertation, Department of Computer Science, University of Utah, December 1978.
3.Catmull, E., "A Subdivision Algorithm for Computer Display of Curved Surfaces", PhD. Dissertation, Department of Computer Science, University of Utah, Tech. Report UTEC-CSc-74-133, December 1974.
4.Catmull, E. and Smith A. R., "3-D Transformation of Images in Scanline Order", Computer Graphics (Proc. Siggraph '80), Vol. 14, July 1980.
5.Feibush, E. A., Levoy, M., and Cook, R. L., "Synthetic Texturing Using Digital Filters", Computer Graphics (Proc. Siggraph '80), Vol. 14, July 1980.
6.Fournier, A., Fussell, D., and Carpenter, L., "Computer Rendering of Stochastic Models", Communications of the ACM, Vol. 25, #6, June 1982.
7.Hackathorn, R. and Parent, R., Private Communication, 1980.
8.Haruyama, S, and Barsky, B. A., "Using Stochastic Modeling for Texture Generation", IEEE Computer Graphics and Applications, Vol. 4, # 3, March 1984.
9.Norton, A., Rockwood, A. P., and Skomolski, P. S., "Clamping: A Method of Antialiasing Textured Surfaces by Bandwidth Limiting in Object Space", Computer Graphics (Proc. Siggraph '82), Vol. 16, #3, July 1982.
10.Williams, L. "Pyramidal Parametrics", Computer Graphics, Vol. 17, #3, July 1983.

Citation

MLA

Crow, F. C. “Summed-area Tables for Texture Mapping”. Proceedings of the 11th Annual Conference on Computer Graphics and Interactive Techniques, 1984, pp. 207–12, https://doi.org/10.1145/800031.808600.

APA

Crow, F. C. (1984). Summed-area tables for texture mapping. Proceedings of the 11th Annual Conference on Computer Graphics and Interactive Techniques, 207–212. https://doi.org/10.1145/800031.808600

Chicago

Crow, F. C. 1984. “Summed-area Tables for Texture Mapping”. Proceedings of the 11th Annual Conference on Computer Graphics and Interactive Techniques, 207–12. https://doi.org/10.1145/800031.808600.

Harvard

Crow, F.C. (1984) “Summed-area tables for texture mapping”, Proceedings of the 11th annual conference on Computer graphics and interactive techniques. ACM, pp. 207–212. Available at: https://doi.org/10.1145/800031.808600.

Vancouver

1. Crow FC (1984) Summed-area tables for texture mapping. In: Proceedings of the 11th annual conference on Computer graphics and interactive techniques. ACM, pp 207–212

BibTeX

@inproceedings{Crow_1984, series={SIGGRAPH ’84}, title={Summed-area tables for texture mapping}, url={http://dx.doi.org/10.1145/800031.808600}, DOI={10.1145/800031.808600}, booktitle={Proceedings of the 11th annual conference on Computer graphics and interactive techniques}, publisher={ACM}, author={Crow, Franklin C.}, year={1984}, month=Jan, pages={207–212}, collection={SIGGRAPH ’84} }

Metadata:Crossref

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

Summed-area tables for texture mapping

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Definition of Summed-Area Table

Knowl 2 — Rectangular Area Intensity Evaluation via Inclusion-Exclusion

Knowl 3 — Anisotropic Rectangular Filtering Capability of Summed-Area Tables

Knowl 4 — Efficient Incremental Summed-Area Table Construction

Knowl 5 — Texture Filtering via Sub-Pixel Bilinear Interpolation of Corner Values

Knowl 6 — Computational and Memory Access Complexity Comparison with MIP Mapping

Knowl 7 — Precision Requirements and Block-Offset Storage for Summed-Area Tables

Knowl 8 — Texture Footprint Bounding Box Estimation from Screen Derivatives

Knowl 9 — Handling Texture Boundaries and Wrapping in Summed-Area Tables

References

Citation

BibTeX

Access the Paper