Sunday, February 16, 2014

Interpolation

In many cases, you want a smooth transition from one value to the next. This is because, jagged color changes look very unnatural. Enter interpolation. Interpolation is simply a technical term for finding intermediate values between two known values. Interpolation has many applications, from smoothing noise arrays to simple gui fade-ins. Here is what simple interpolation looks like:



But there are many different methods of interpolation. In the example, I used linear interpolation. Other types include cosine and cubic interpolation.

It is easiest to show to differences in 1D.

Linear Interpolation just uses the slope of the points to find a value. This results in sharp edges and discontinuities.
It looks like this in 1D:




The code looks like this:
public double linear(double bottom, double top, double mu)
{
    return (bottom * (1 - mu)) + (top * mu);
}

Bottom is the lower bounding value, top is the higher, and mu is the distance between them (with 0 being bottom and 1 being top).

Cosine interpolation uses the cos function to get a much smoother interpolation. It is the interpolation function that I use most often, because it is a good tradeoff of speed and smoothness.




Here's the code for it:
public double cosine(double bottom, double top, double mu)
{
    double newMu = (1 - Math.cos(mu * Math.PI)) / 2;
    return linear(bottom, top, newMu);
}

Next there is cubic interpolation. Cubic tries to "extend" the values to get the smoothest curve possible. Because of this, it can't be used in cases where the values must stay within certain ranges. It also requires 1 more value in each direction beyond top and bottom. This limits it's usefulness because more values have to be calculated.

The code is also a lot more complicated:
public double cubic(double past, double bottom, double top, double future, double mu)
{
    double muSq = mu * mu;
    double a0 = (future - top) - (past - bottom);
    double a1 = (past - bottom) - a0;
    double a2 = (top - past);
    double a3 = bottom;
    return (a0 * mu * muSq) + (a1 * muSq) + (a2 * mu) + a3;
}

There is also a modified version of cubic called Catmull-Rom that uses multipliers on some of the values to reduce the overshoot. Code for it is not shown here, but is included with the srcs for download.

Finally we have Hermite. Hermite is simliar to cubic in that it needs more values and can "extend" values. However, with Hermite, there are extra parameters that allow you to control the amount of overshoot, as well as "bias" the interpolation toward the top or the bottom.



The code, naturally, is even more complex than cubic.
public double hermite(double past, double bottom, double top, double future, double mu, double tension, double bias)
{
    double muSq = mu * mu;
    double muCu = muSq * mu;
    double tenMulti = (1 - tension) / 2;
  
    double m0 = (bottom - past) * (1 + bias) * tenMulti;
          m0 += (top -  bottom) * (1 - bias) * tenMulti;
    double m1 = (top -  bottom) * (1 + bias) * tenMulti;
          m1 += (future -  top) * (1 - bias) * tenMulti;
        
    double a0 =  (2 * muCu) - (3 * muSq) + 1;
    double a1 =      (muCu) - (2 * muSq) + mu;
    double a2 =      (muCu) -     (muSq);
    double a3 = -(2 * muCu) + (3 * muSq);
  
    return (a0 * bottom) + (a1 * m0) + (a2 * m1) + (a3 * top);
}

All of these methods can be extended to multiple dimensions by applying them to each of the coordinates individually (with the exception of cosine with becomes the same as linear in more than 1D). These interpolation functions are also what you would use to smooth out a noise function so it is less jagged.

If you want to play around with these functions, here is an applet that will let you get your feet wet.
Controls: Space = next function
Q = more tension.
E = less tension
A = bias toward bottom.
D = bias toward top.
S = reset bias
Enter (downloadable version only) = save screenshot


If the applet doesn't load, trying refreshing the webpage. May not work on mobiles.

Demos: https://drive.google.com/folderview?id=0B_jXYEquMamINGVGQTM0cTJzdmM&usp=sharing
Source Code: https://github.com/f4113nb34st/Println/

No comments:

Post a Comment