Interpolation
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 [1]pixel 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
[2]mathematical tool that's commonly encountered almost everywhere, not
just in [3]programming: some uses include drawing a graph between measured
data points, estimating function values in unknown regions, creating
smooth [4]animations, drawing [5]vector curves, [6]digital to [7]analog
conversion, enlarging pictures, blending transition in videos and so on.
Interpolation can be used to generalize, e.g. if we have a mathematical
[8]function that's only defined for [9]whole numbers (such as
[10]factorial or [11]Fibonacci sequence), we may use interpolation to
extend that function to all [12]real numbers. Interpolation can also be
used as a method of [13]approximation (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.
The opposite of interpolation is [14]extrapolation, an operation that's
extending, creating points OUTSIDE given interval (while interpolation
creates points INSIDE the interval). Both interpolation and extrapolation
are similar to [15]regression which tries to find a [16]function 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).
There are many methods of interpolation which differ in aspects such as
complexity, number of dimensions, type and properties of the mathematical
curve/surface ([17]polynomial degree, continuity/smoothness of
[18]derivatives, ...) or number of points required for the computation
(some methods require knowledge of more than two points).
.----B _B _.B _-'''B-.
| .' .' .'
| _-' / :
| .' .' /
A----' A' A-' _.A'
nearest linear cosine cubic
A few common 1D interpolation methods.
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 [19]function 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
[20]slopes at the points A and B. So the function signature in [21]C may
look e.g. as
float interpolate(float a, float b, float t);
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.
[22]Nearest neighbor 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.
[23]Linear interpolation (so called LERP, not to be [24]confused with
[25]LARP) 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 [26]good enough 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".
[27]Cosine interpolation uses part of the [28]cosine 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).
[29]Cubic interpolation can be considered a bit more advanced, it uses a
[30]polynomial 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.
Besides these we may potentially use many other functions, curves and
splines (for example Akima spline, Steffen spline and so on).
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 [31]computer graphics when upscaling
[32]textures (sometimes called texture filtering). 2D nearest neighbor
interpolation creates "blocky" images in which [33]pixels simply "get
bigger" but stay sharp squares if we upscale the texture. Linear
interpolation in 2D is called [34]bilinear interpolation and is visually
much better than nearest neighbor, [35]bicubic interpolation is a
generalization of cubic interpolation to 2D and is yet smoother that
bilinear interpolation.
TODO: simple C code pls, maybe linear interpolation without floats
See Also
* [36]extrapolation
* [37]regression
* [38]smoothstep
Links:
1. pixel.dm
2. math.md
3. programming.md
4. animation.md
5. vector_graphics.md
6. digital.md
7. analog.md
8. function.md
9. whole_number.md
10. factorial.md
11. fibonacci.md
12. real_number.md
13. approximation.md
14. extrapolation.md
15. regression.md
16. function.md
17. polynomial.md
18. derivative.md
19. function.md
20. slope.md
21. c.md
22. nearest_neighbor.md
23. lerp.md
24. often_confused.md
25. larp.md
26. good_enough.md
27. cos.md
28. cos.md
29. cubic.md
30. polynomial.md
31. graphics.md
32. texture.md
33. pixel.md
34. bilinear.md
35. bicubic.md
36. extrapolation.md
37. regression.md
38. smoothstep.md