Bilinear Interpolation
Bilinear interpolation (also bilinear filtering) is a simple way of
creating a smooth transition ([1]interpolation) between [2]discrete
samples (values) in 2D, it is a [3]generalization of [4]linear
interpolation to 2 dimensions. It is used in many places, popularly e.g.
in 3D [5]computer graphics for [6]texture filtering; bilinear
interpolation allows to upscale textures to higher resolutions (i.e.
compute new pixels between existing pixels) while keeping their look
smooth and "non-blocky" (even though blurry). On the scale of quality vs
simplicity it is kind of a middle way between a simpler [7]nearest
neighbour interpolation (which creates the "blocky" look) and more complex
[8]bicubic interpolation (which uses yet smoother curves but also requires
more samples). Bilinear interpolation can further be generalized to
[9]trilinear interpolation (in computer graphics trilinear interpolation
is used to also additionally interpolate between different levels of a
texture's [10]mipamap) and perhaps even bilinear [11]extrapolation. Many
frameworks/libraries/engines have bilinear filtering built-in (e.g.
GL_LINEAR in [12]OpenGL). Of course this method may be used to smooth not
just textures but anything, for example terrain [13]heightmaps or just any
discrete mathematical function that we simply want to have defined
everywhere, it's not just graphics thing, but here we will focus on its
application in [14]graphics.
####OOOOVVVVaaaaxxxxssssffffllllcccc////!!!!;;;;,,,,....----
####OOOOVVVVaaaaxxxxxssssffffllllcccc////!!!!;;;;,,,,.....----
####OOOOVVVVaaaaaxxxxssssfffflllllcccc////!!!!!;;;;,,,,....-----
###OOOOOVVVVaaaaaxxxxsssssfffflllllcccc////!!!!!;;;;,,,,,....---
###OOOOVVVVVaaaaaxxxxsssssfffffllllccccc/////!!!!!;;;;,,,,,.....
##OOOOOVVVVVaaaaaxxxxxsssssffffflllllcccc/////!!!!!;;;;;,,,,,...
##OOOOOVVVVVaaaaaxxxxxsssssfffffflllllccccc/////!!!!!;;;;;,,,,,.
#OOOOOOVVVVVaaaaaxxxxxxsssssfffffflllllccccc//////!!!!!;;;;;;,,,
OOOOOOVVVVVVaaaaaaxxxxxssssssfffffflllllcccccc//////!!!!!;;;;;;,
OOOOOOVVVVVVaaaaaaxxxxxxssssssffffffllllllcccccc//////!!!!!!;;;;
OOOOOVVVVVVVaaaaaaxxxxxxsssssssfffffflllllllcccccc///////!!!!!!;
OOOOOVVVVVVaaaaaaaxxxxxxxsssssssffffffflllllllccccccc//////!!!!!
OOOOVVVVVVVaaaaaaaaxxxxxxxsssssssfffffffflllllllccccccc////////!
OOOVVVVVVVVaaaaaaaaxxxxxxxxssssssssffffffffllllllllcccccccc/////
OOVVVVVVVVVaaaaaaaaaxxxxxxxxsssssssssfffffffflllllllllcccccccc//
OVVVVVVVVVVaaaaaaaaaxxxxxxxxxssssssssssffffffffflllllllllccccccc
VVVVVVVVVVaaaaaaaaaaaxxxxxxxxxxssssssssssfffffffffffllllllllllcc
VVVVVVVVVVaaaaaaaaaaaxxxxxxxxxxxxsssssssssssffffffffffffllllllll
VVVVVVVVVVaaaaaaaaaaaaxxxxxxxxxxxxxsssssssssssssffffffffffffflll
VVVVVVVVVaaaaaaaaaaaaaaaxxxxxxxxxxxxxxsssssssssssssssfffffffffff
VVVVVVVVaaaaaaaaaaaaaaaaaxxxxxxxxxxxxxxxxxxsssssssssssssssssffff
VVVVVVVaaaaaaaaaaaaaaaaaaaaaxxxxxxxxxxxxxxxxxxxxssssssssssssssss
VVVVVVaaaaaaaaaaaaaaaaaaaaaaaaaxxxxxxxxxxxxxxxxxxxxxxxxxxsssssss
VVVaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaxxxxxxxxxxxxxxxxxxxxxxxxxxx
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaxxxxxxxxxxxxxxx
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaVVVVVVVVVVVVVVVVVVV
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVV
aaaaaaaaaaaaaaaaaaaaaaaaVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVOOOOOO
aaaaaaaaaaaaaaaaaaaaaVVVVVVVVVVVVVVVVVVVVVVVVVVOOOOOOOOOOOOOOOOO
aaaaaaaaaaaaaaaaaaaaVVVVVVVVVVVVVVVVVVVVOOOOOOOOOOOOOOOOOOOOO###
The above image is constructed by applying bilinear interpolation to the
four corner values.
The principle is simple: first linearly interpolate in one direction (e.g.
horizontal), then in the other (vertical). Mathematically the order in
which we take the dimensions doesn't matter (but it may matter practically
due to rounding errors etc.).
Example: let's say we want to compute the value x between the four
following given corner values:
1 . . . . . . 5
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . x . . .
. . . . . . . .
8 . . . . . . 3
Let's say we first interpolate horizontally: we'll compute one value, a,
on the top (between 1 and 5) and one value, b, at the bottom (between 8
and 3). When computing a we interpolate between 1 and 5 by the horizontal
position of x (4/7), so we get a = 1 + 4/7 * (5 - 1) = 23/7. Similartly b
= 8 + 4/7 * (3 - 8) = 36/7. Now we interpolate between a and b vertically
(by the vertical position of x, 5/7) to get the final value x = 23/7 + 5/7
* (36/7 - 23/7) = 226/49 ~= 4.6. If we first interpolate vertically and
then horizontally, we'd get the same result (the value between 1 and 8
would be 6, the value between 5 and 3 would be 25/7 and the final value
226/49 again).
Here is a [15]C code to compute all the inbetween values in the above,
using [16]fixed point (no [17]float):
#include <stdio.h>
#define GRID_RESOLUTION 8
int interpolateLinear(int a, int b, int t)
{
return a + (t * (b - a)) / (GRID_RESOLUTION - 1);
}
int interpolateBilinear(int topLeft, int topRight, int bottomLeft, int bottomRight,
int x, int y)
{
#define FPP 16 // we'll use fixed point to prevent rounding errors
#if 1 // switch between the two versions, should give same results:
// horizontal first, then vertical
int a = interpolateLinear(topLeft * FPP,topRight * FPP,x);
int b = interpolateLinear(bottomLeft * FPP,bottomRight * FPP,x);
return interpolateLinear(a,b,y) / FPP;
#else
// vertical first, then horizontal
int a = interpolateLinear(topLeft * FPP,bottomLeft * FPP,y);
int b = interpolateLinear(topRight * FPP,bottomRight * FPP,y);
return interpolateLinear(a,b,x) / FPP;
#endif
}
int main(void)
{
for (int y = 0; y < GRID_RESOLUTION; ++y)
{
for (int x = 0; x < GRID_RESOLUTION; ++x)
printf("%d ",interpolateBilinear(1,5,8,3,x,y));
putchar('\n');
}
return 0;
}
The program outputs:
1 1 2 2 3 3 4 5
2 2 2 3 3 4 4 5
3 3 3 3 4 4 4 5
4 4 4 4 4 4 4 5
5 5 5 5 5 5 5 4
6 6 6 6 5 5 5 4
7 7 7 6 6 5 5 4
8 8 7 6 6 5 4 3
Cool [18]hack to improve bilinear interpolation (from
https://iquilezles.org/articles/texture): bilinear interpolation doesn't
looks as good as bicubic but bicubic is a lot more complex on hardware and
bandwidth as it requires fetching more texels -- there is one trick which
[19]shader programmers use to improve the look of bilinear filtering while
not requiring fetching more texels. They use the smoothstep function on
the interpolation parameter which eliminates instant "jumps" at edges
between texels, it replaces straight lines with a smoother curve and so
makes the [20]derivative of the result continuous -- basically it looks a
lot better. Still not as good as bicubic but close enough.
TODO: code for the above
Links:
1. interpolation.md
2. discrete.md
3. generalization.md
4. lerp.md
5. graphics.md
6. texture.md
7. nearest_neighbour.md
8. bicubic.md
9. trilinear.md
10. mipamp.md
11. extrapolation.md
12. ogl.md
13. heightmap.md
14. graphics.md
15. c.md
16. fixed_point.md
17. float.md
18. hacking.md
19. shader.md
20. derivative.md