Bilinear Filtering
What is "filtering" anyway?
When an image is transformed (scaled, rotated, etc.) you often face the problem that there is simply not enough data to assign values to all pixels. If an image's height and width are doubled, you are increasing the number of pixels by a factor of four. You can assign data to a quarter of those pixels 100% reliably, but you need to guess, or interpolate values for all the pixels in between. The simplest way is just to use the value of the nearest known pixel. This is known as point or nearest neighbour interpolation, and can result in a blocky, unappealing image to look at and - in the case of a size reduction - can even cause large, noticable gaps in lines.
Bilinear interpolation is a way of guessing pixel values in order to create a smoother image.
|
|
|
![[texture_filter_example_small]](images/texture-filter-example-small.png)
![[texture_filter_example_point]](images/texture-filter-example-point.png)
![[texture_filter_example_bilinear]](images/texture-filter-example-bilin.png)
So what uses bilinear filtering?
In games, bilinear filtering is primarily used to apply a texture to a surface. As you look around the world, the 2D shape of the surface is altered (vertices further away from the viewpoint appear closer together), and the texture must be transformed to fit the new shape. If you've played older shooters (i.e. Doom) you can see how aliased and pixelated the texture looks when using point filtering for this process.
Bilinear filtering will make these textures look smoother and more convincing. However, on a surface that extends into the distance, the texture can get less and less clear as it gets further from the viewpoint. This is where the mipmapping technique comes in to play - by creating several smaller, clear versions of the same texture, you can apply the larger versions close to the viewpoint and the smaller versions further away to result in an overall sharper texture application.
However even this has its drawbacks: Now that we're applying multiple textures to one surface and filtering them separately, there is often noticable lines where there is a change in mip level. These lines look VERY unrealistic when you move, as they maintain a constant distance from the viewpoint (thus you have lines which appear to move as you move). This is where Trilinear Filtering comes into play, by adding a third linear filter between the mipmap levels, these lines are eliminated.
There is another type of filtering, called [Anisotropic Filtering]?, which works WITH bilinear/trilinear filtering to make far away textures appear *very* clear.
The math behind bilinear interpolation
The general idea when interpolating bilinearly is that the colour of an unknown pixel should be spaced proportionally between the colour values of the pixels around it. Therefore if an unknown pixel is halfway between two known pixels, its colour value should be halfway between their values. If the unknown pixel is closer to one of the known pixels, it should be closer to that pixel's colour.
More specifically, if the known pixels have values V1 and V2, and the distances from the unknown pixels are D1 and D2, the unknown pixel should have the value:
V = (V1 * D2 + V2 * D1) / (D1 + D2)
This equation will work for interpolating along a line, and is called linear interpolation However, it is a bit more complicated for images, as they are comprised of horizontal and vertical lines. We must use a combination of 2 linear filters - horizontal and vertical - to create the desired effect. This results in a bilinear interpolation.
When interpolating bilinearly, four reference pixels are required. The pixel we are trying to determine the value of will lie somewhere in the square defined by those reference pixels. Say we are trying to find the value of pixel at (X0, Y0), with our 4 reference pixels being at (x1, y1), (x2, y1), (x1, y2), (x2, y2). If those pixels have values of V11, V12, V21, and V22, we will start by interpolating horizontally between the 2 horizontal pairs of pixels.
V1 = (V11 * dx2 + V21 * dx1) / (dx1 + dx2) V2 = (V12 * dx2 + V22 * dx1) / (dx1 + dx2)
We will then interpolate these new values vertically to get our known value.
V = [(V11 * dx2 + V21 * dx1) / (dx1 + dx2) * dy2 + (V12 * dx2 + V22 * dx1) / (dx1 + dx2) * dy1)] / (dy1 + dy2) = (V11 * dx2 * dy2 + V21 * dx1 * dy2 + V12 * dx2 * dy1 + V22 * dx1 * dy1) / (dx1 + dx2) / (dy1 + dy2)
Now since all our reference pixels are adjacent to each other, dx1 + dx2 = 1, and dy1 + dy2 = 1. Substitute:
V = V11 * dx2 * dy2 + V21 * dx1 * dy2 + V12 * dx2 * dy1 + V22 * dx1 * dy1
Draconx: I'm not very good at explaining myself when it comes to equations. I also don't think I formatted this particularly well. Perhaps someone could clean this up a bit? 
Foxpaw: Err, isn't the title of this page extremely misleading? Bilinear filtering is one method by which different mipmaps are interpolated between when a frame is rendered, not the method by which the mipmaps are generated.
Bilinear interpolation would be a much more accurate name for this page.
Draconx: I added a thing about bilinear filtering's application in games. A bilinear filter is simply a transformation that uses bilinear interpolation, but it is not technically a requirement for mipmapping, nor is mipmapping a requirement for bilinear filtering of textures onto a surface. And interpolating BETWEEN the mipmaps is a function of Trilinear Filtering - which mipmaps are required for. Trilinear filtering is simply bilinearly filtered mipmaps with linear interpolation between them.
