interpolation.md

   1 # Interpolation
   2
   3 Interpolation (*inter* = between, *polio*= polish) means computing (usually a gradual) transition between some specified values, i.e. creating additional intermediate points between some already existing points. For example if we want to change a screen [pixel](pixel.dm) from one color to another in a gradual manner, we use some interpolation method to compute a number of intermediate colors which we then display in rapid succession; we say we interpolate between the two colors. Interpolation is a very basic [mathematical](math.md) tool that's commonly encountered almost everywhere, not just in [programming](programming.md): some uses include drawing a graph between measured data points, estimating function values in unknown regions, creating smooth [animations](animation.md), drawing [vector](vector_graphics.md) curves, [digital](digital.md) to [analog](analog.md) conversion, enlarging pictures, blending transition in videos and so on. Interpolation can be used to generalize, e.g. if we have a mathematical [function](function.md) that's only defined for [whole numbers](whole_number.md) (such as [factorial](factorial.md) or [Fibonacci sequence](fibonacci.md)), we may use interpolation to extend that function to all [real numbers](real_number.md). Interpolation can also be used as a method of [approximation](approximation.md) (consider e.g. a game that runs at 60 FPS to look smooth but internally only computes its physics at 30 FPS and interpolates every other frame so as to increase performance). All in all interpolation is one of the most important things to learn.
   4
   5 The opposite of interpolation is **[extrapolation](extrapolation.md)**, an operation that's *extending*, creating points OUTSIDE given interval (while interpolation creates points INSIDE the interval). Both interpolation and extrapolation are similar to **[regression](regression.md)** which tries to find a [function](function.md) of specified form that best fits given data (unlike interpolation it usually isn't required to hit the data points exactly but rather e.g. minimize some kind of distance to these points).
   6
   7 There are many methods of interpolation which differ in aspects such as complexity, number of dimensions, type and properties of the mathematical curve/surface ([polynomial](polynomial.md) degree, continuity/smoothness of [derivatives](derivative.md), ...) or number of points required for the computation (some methods require knowledge of more than two points).
   8
   9 ```
  10
  11       .----B           _B          _.B        _-'''B-.
  12       |              .'          .'         .'
  13       |           _-'           /          :
  14       |         .'            .'          /
  15  A----'       A'           A-'        _.A'
  16
  17   nearest       linear       cosine         cubic
  18 ```
  19
  20 *A few common 1D interpolation methods.*
  21
  22 The base case of interpolation takes place in one dimension (imagine e.g. interpolating sound volume, a single number parameter). Here interpolation can be seen as a [function](function.md) that takes as its parameters the two values to interpolate between, *A* an *B*, and an **interpolation parameter** *t*, which takes the value from 0 to 1 -- this parameter says the percentage position between the two values, i.e. for *t = 0* the function returns *A*, for *t = 1* it returns *B* and for other values of *t* it returns some intermediate value (note that this value may in certain cases be outside the *A*-*B* interval, e.g. with cubic interpolation). The function can optionally take additional parameters, e.g. cubic interpolation requires to also specify [slopes](slope.md) at the points *A* and *B*. So the function signature in [C](c.md) may look e.g. as
  23
  24 ```
  25 float interpolate(float a, float b, float t);
  26 ```
  27
  28 Many times we apply our interpolation not just to two points but to many points, by segments, i.e. we apply the interpolation between each two neighboring points (a segment) in a series of many points to create a longer curve through all the points. Here we are usually interested in how the segments transition into each other, i.e. what the whole curve looks like at the exact locations of the points.
  29
  30 **[Nearest neighbor](nearest_neighbor.md)** is probably the simplest interpolation (so simple that it's sometimes not even called an interpolation, even though it technically is). This method simply returns the closest value, i.e. either *A* (for *t* < 0.5) or *B* (otherwise). This creates kind of sharp steps between the points, the function is not continuous, i.e. the transition between the points is not gradual but simply jumps from one value to the other at one point.
  31
  32 **[Linear interpolation](lerp.md)** (so called lerp) is probably the second simplest interpolation which steps from the first point towards the second in a constant step, creating a straight line between them. This is simple and [good enough](good_enough.md) for many things, the function is continuous but not smooth, i.e. there are no "jumps" but there may be "sharp turns" at the points, the curve may look like a "saw".
  33
  34 **[Cosine](cos.md) interpolation** uses part of the [cosine](cos.md) function to create a continuous and smooth line between the points. The advantage over linear interpolation is the smoothness, i.e. there aren't "sharp turns" at the points, just as with the more advanced cubic interpolation against which cosine interpolation has the advantage of still requiring only the two interval points (*A* and *B*), however for the price of a disadvantage of always having the same horizontal slope at each point which may look weird in some situations (e.g. multiple points lying on the same sloped line will result in a curve that looks like smooth steps).
  35
  36 **[Cubic](cubic.md) interpolation** can be considered a bit more advanced, it uses a [polynomial](polynomial.md) of degree 3 and creates a nice smooth curve through multiple points but requires knowledge of one additional point on each side of the interpolated interval (this may create slight issues with the first and last point of the sequence of values). This is so as to know at what slope to approach an endpoint so as to continue in the direction of the point behind it.
  37
  38 Besides these we may potentially use many other functions, curves and splines (for example Akima spline, Steffen spline and so on).
  39
  40 The above mentioned methods can be generalized to more dimensions (the number of dimensions are equal to the number of interpolation parameters) -- we encounter this a lot e.g. in [computer graphics](graphics.md) when upscaling [textures](texture.md) (sometimes called texture filtering). 2D nearest neighbor interpolation creates "blocky" images in which [pixels](pixel.md) simply "get bigger" but stay sharp squares if we upscale the texture. Linear interpolation in 2D is called [bilinear interpolation](bilinear.md) and is visually much better than nearest neighbor, [bicubic interpolation](bicubic.md) is a generalization of cubic interpolation to 2D and is yet smoother that bilinear interpolation.
  41
  42 TODO: simple C code pls, maybe linear interpolation without floats
  43
  44 ## See Also
  45
  46 - [extrapolation](extrapolation.md)
  47 - [regression](regression.md)
  48 - [smoothstep](smoothstep.md)