bilinear.md

   1 # Bilinear Interpolation
   2
   3 Bilinear interpolation (also bilinear filtering) is a simple way of creating a smooth transition ([interpolation](interpolation.md)) between [discrete](discrete.md) samples (values) in 2D, it is a [generalization](generalization.md) of [linear interpolation](lerp.md) to 2 dimensions. It is used in many places, popularly e.g. in 3D [computer graphics](graphics.md) for **[texture](texture.md) 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 [nearest neighbour](nearest_neighbour.md) interpolation (which creates the "blocky" look) and more complex [bicubic interpolation](bicubic.md) (which uses yet smoother curves but also requires more samples). Bilinear interpolation can further be generalized to [trilinear interpolation](trilinear.md) (in computer graphics trilinear interpolation is used to also additionally interpolate between different levels of a texture's [mipamap](mipamp.md)) and perhaps even bilinear [extrapolation](extrapolation.md). Many frameworks/libraries/engines have bilinear filtering built-in (e.g. `GL_LINEAR` in [OpenGL](ogl.md)). Of course this method may be used to smooth not just textures but anything, for example terrain [heightmaps](heightmap.md) 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 [graphics](graphics.md).
   4
   5 Why is it named *bilinear*? Probably because it's doing linear interpolation twice: once in *X* direction, then in *Y* direction.
   6
   7 ```
   8 ####OOOOVVVVaaaaxxxxssssffffllllcccc////!!!!;;;;,,,,....----
   9 ####OOOOVVVVaaaaxxxxxssssffffllllcccc////!!!!;;;;,,,,.....----
  10 ####OOOOVVVVaaaaaxxxxssssfffflllllcccc////!!!!!;;;;,,,,....-----
  11 ###OOOOOVVVVaaaaaxxxxsssssfffflllllcccc////!!!!!;;;;,,,,,....---
  12 ###OOOOVVVVVaaaaaxxxxsssssfffffllllccccc/////!!!!!;;;;,,,,,.....
  13 ##OOOOOVVVVVaaaaaxxxxxsssssffffflllllcccc/////!!!!!;;;;;,,,,,...
  14 ##OOOOOVVVVVaaaaaxxxxxsssssfffffflllllccccc/////!!!!!;;;;;,,,,,.
  15 #OOOOOOVVVVVaaaaaxxxxxxsssssfffffflllllccccc//////!!!!!;;;;;;,,,
  16 OOOOOOVVVVVVaaaaaaxxxxxssssssfffffflllllcccccc//////!!!!!;;;;;;,
  17 OOOOOOVVVVVVaaaaaaxxxxxxssssssffffffllllllcccccc//////!!!!!!;;;;
  18 OOOOOVVVVVVVaaaaaaxxxxxxsssssssfffffflllllllcccccc///////!!!!!!;
  19 OOOOOVVVVVVaaaaaaaxxxxxxxsssssssffffffflllllllccccccc//////!!!!!
  20 OOOOVVVVVVVaaaaaaaaxxxxxxxsssssssfffffffflllllllccccccc////////!
  21 OOOVVVVVVVVaaaaaaaaxxxxxxxxssssssssffffffffllllllllcccccccc/////
  22 OOVVVVVVVVVaaaaaaaaaxxxxxxxxsssssssssfffffffflllllllllcccccccc//
  23 OVVVVVVVVVVaaaaaaaaaxxxxxxxxxssssssssssffffffffflllllllllccccccc
  24 VVVVVVVVVVaaaaaaaaaaaxxxxxxxxxxssssssssssfffffffffffllllllllllcc
  25 VVVVVVVVVVaaaaaaaaaaaxxxxxxxxxxxxsssssssssssffffffffffffllllllll
  26 VVVVVVVVVVaaaaaaaaaaaaxxxxxxxxxxxxxsssssssssssssffffffffffffflll
  27 VVVVVVVVVaaaaaaaaaaaaaaaxxxxxxxxxxxxxxsssssssssssssssfffffffffff
  28 VVVVVVVVaaaaaaaaaaaaaaaaaxxxxxxxxxxxxxxxxxxsssssssssssssssssffff
  29 VVVVVVVaaaaaaaaaaaaaaaaaaaaaxxxxxxxxxxxxxxxxxxxxssssssssssssssss
  30 VVVVVVaaaaaaaaaaaaaaaaaaaaaaaaaxxxxxxxxxxxxxxxxxxxxxxxxxxsssssss
  31 VVVaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaxxxxxxxxxxxxxxxxxxxxxxxxxxx
  32 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaxxxxxxxxxxxxxxx
  33 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
  34 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
  35 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaVVVVVVVVVVVVVVVVVVV
  36 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVV
  37 aaaaaaaaaaaaaaaaaaaaaaaaVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVOOOOOO
  38 aaaaaaaaaaaaaaaaaaaaaVVVVVVVVVVVVVVVVVVVVVVVVVVOOOOOOOOOOOOOOOOO
  39 aaaaaaaaaaaaaaaaaaaaVVVVVVVVVVVVVVVVVVVVOOOOOOOOOOOOOOOOOOOOO###
  40 ```
  41
  42 *The above image is constructed by applying bilinear interpolation to the four corner values.*
  43
  44 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.).
  45
  46 Example: let's say we want to compute the value *x* between the four following given corner values:
  47
  48 ```
  49 1 . . . . . . 5
  50 . . . . . . . .
  51 . . . . . . . .
  52 . . . . . . . .
  53 . . . . . . . .
  54 . . . . x . . .
  55 . . . . . . . .
  56 8 . . . . . . 3
  57 ```
  58
  59 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).
  60
  61 Here is a [C](c.md) code to compute all the inbetween values in the above, using [fixed point](fixed_point.md) (no [float](float.md)):
  62
  63 ```
  64 #include <stdio.h>
  65
  66 #define GRID_RESOLUTION 8
  67
  68 int interpolateLinear(int a, int b, int t)
  69 {
  70   return a + (t * (b - a)) / (GRID_RESOLUTION - 1);
  71 }
  72
  73 int interpolateBilinear(int topLeft, int topRight, int bottomLeft, int bottomRight,
  74   int x, int y)
  75 {
  76 #define FPP 16 // we'll use fixed point to prevent rounding errors
  77
  78 #if 1 // switch between the two versions, should give same results:
  79   // horizontal first, then vertical
  80   int a = interpolateLinear(topLeft * FPP,topRight * FPP,x);
  81   int b = interpolateLinear(bottomLeft * FPP,bottomRight * FPP,x);
  82   return interpolateLinear(a,b,y) / FPP;
  83 #else
  84   // vertical first, then horizontal
  85   int a = interpolateLinear(topLeft * FPP,bottomLeft * FPP,y);
  86   int b = interpolateLinear(topRight * FPP,bottomRight * FPP,y);
  87   return interpolateLinear(a,b,x) / FPP;
  88 #endif
  89 }
  90
  91 int main(void)
  92 {
  93   for (int y = 0; y < GRID_RESOLUTION; ++y)
  94   {
  95     for (int x = 0; x < GRID_RESOLUTION; ++x)
  96       printf("%d ",interpolateBilinear(1,5,8,3,x,y));
  97
  98     putchar('\n');
  99   }
 100
 101   return 0;
 102 }
 103 ```
 104
 105 The program outputs:
 106
 107 ```
 108 1 1 2 2 3 3 4 5
 109 2 2 2 3 3 4 4 5
 110 3 3 3 3 4 4 4 5
 111 4 4 4 4 4 4 4 5
 112 5 5 5 5 5 5 5 4
 113 6 6 6 6 5 5 5 4
 114 7 7 7 6 6 5 5 4
 115 8 8 7 6 6 5 4 3
 116 ```
 117
 118 **Cool [hack](hacking.md) 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 [shader](shader.md) 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 [derivative](derivative.md) of the result continuous -- basically it looks a lot better. Still not as good as bicubic but [close enough](good_enough.md).
 119
 120 TODO: code for the above
 121
 122 For [suckless](suckless.md) programs that do their own [software rendering](software_rendering.md) an issue of bilinear interpolation, as compared with nearest neighbor, might be that it **creates new colors** by averaging colors in the filtered image, i.e. image filtered this way may have new colors introduced and this may become a problem e.g. if we are using [palettes](palette.md) (indexed mode) with limited number of colors and possible operations with them. This may also complicated e.g. using precomputed scaling tables (used in old games like [wolf 3D](wolf3d.md)) that simply store mapping of the original image to pixels in an upscaled image. A possible attempt at a "fix" -- or rather more of a poor man's bilinear interpolation -- may be in [dithering](dithering.md) the colors rather than averaging; perhaps once we sample in between pixels we assign probabilities to the 4 nearest pixels, based on their distance to the sample position, and then take one of the four pixels at random with those probabilities using some [pseudorandom](pseudorandom.md) generator.
 123
 124 TODO: test the above