Bilinear filtering

The formula

In a mathematical context, bilinear interpolation is the problem of finding a function f(x,y) of the form

satisfying

The usual, and usually computationally least expensive way to compute f is through linear interpolation used twice, for example to compute two functions f 1 and f 2 satisfying

and then to combine these functions (which are linear in y ) into one function f satisfying

In computer graphics, bilinear filtering is usually performed on a texture during texture mapping, or on a bitmap during resizing. In both cases, the source data (bitmap or texture) can be seen as a two-dimensional array of values z i j , or several (usually three) of these in the case of full-color data. The data points used in bilinear filtering are the 2x2 points surrounding the location for which the color is to be interpolated.

Additionally, one does not have to compute the actual coefficients of the function f ; computing the value f ( x , y ) is sufficient.

The largest integer not larger than x shall be called [ x ] , and the fractional part of x shall be { x } . Then, x = [ x ] + { x } , and { x } < 1 . We have x 1 = [ x ] , x 2 = [ x ] + 1 , y 1 = [ y ] , y 2 = [ y ] + 1 . The data points used for interpolation are taken from the texture / bitmap and assigned to z 11 , z 12 , z 21 , and z 22 .

f 1 ( y 1 ) = z 11 , f 1 ( y 2 ) = z 12 are the two data points for f 1 subtracting the former from the latter yields

Because f 1 is linear, its derivative is constant and equal to

Because f 1 ( y 1 ) = z 11 ,

and similarly,

Because y 1 + { y } = y , we have computed the endpoints f 1 ( y ) and f 2 ( y ) needed for the second interpolation step.

The second step is to compute f ( x , y ) , which can be accomplished by the very formula we used for computing the intermediate values:

In the case of scaling, y remains constant within the same line of the rescaled image, and storing the intermediate results and reusing them for calculation of the next pixel can lead to significant savings. Similar savings can be achieved with all "bi" kinds of filtering, i.e. those which can be expressed as two passes of one-dimensional filtering.

In the case of texture mapping, a constant x or y is rarely if ever encountered, and because today's (2000+) graphics hardware is highly parallelized, there would be no time savings anyway.

Another way of writing the bilinear interpolation formula is

Sample code

This code assumes that the texture is square (an extremely common occurrence), that no mipmapping comes into play, and that there is only one channel of data (not so common. Nearly all textures are in color so they have red, green, and blue channels, and many have an alpha transparency channel, so we must make three or four calculations of y, one for each channel). The location of UV-coordinates is at center of texel. For example, {(0.25,0.25), (0.75,0.25), (0.25,0.75), (0.75,0.75)} are values for 2x2 texture.

Limitations

Bilinear filtering is rather accurate until the scaling of the texture gets below half or above double the original size of the texture - that is, if the texture was 256 pixels in each direction, scaling it to below 128 or above 512 pixels can make the texture look bad, because of missing pixels or too much smoothness. Often, in gaming or other 3-D rendering applications, mipmapping is used to provide a scaled-down version of the texture for better performance; however, the transition between two differently-sized mipmaps on a texture in perspective using bilinear filtering can be very abrupt. Trilinear filtering, though somewhat more complex, can make this transition smooth throughout. In the world of 2-D image resising, bicubic interpolation is usually preferred for the illusion of sharpness that it creates and for its superior anti-aliasing properties; however, most bicubics achieve this through a combination of blurring and ringing artifacts. A Hermite filter, which is the only cubic that adds neither blurring nor ringing, does not anti-alias any better than linear interpolation does, but it is still somewhat sharper.

For a quick demonstration of how a texel can be missing from a filtered texture, here's a list of numbers representing the centers of boxes from an 8-texel-wide texture (in red and black), intermingled with the numbers from the centers of boxes from a 3-texel-wide down-sampled texture (in blue). The red numbers represent texels that would not be used in calculating the 3-texel texture at all.

0.0625, 0.1667, 0.1875, 0.3125, 0.4375, 0.5000, 0.5625, 0.6875, 0.8125, 0.8333, 0.9375

Special cases

Textures aren't infinite, in general, and sometimes one ends up with a pixel coordinate that lies outside the grid of texel coordinates. There are a few ways to handle this: