Thursday, January 22, 2015

Interpolation

Interpolation is basically just the creation of intermediate points between two points.  In games, this is quite often used to move an object smoothly from one place to another over several frames.

Linear Interpolation


The basic form of interpolation is linear interpolation (lerp).  This basically looks like:

p = p0*(1 - t) + p1*t

where:
p0 is the start value
p1 is the end value
t is a value between 0 and 1 representing the interpolation amount
p is the current value

This basically represents a straight line segment between p0 and p1, with t representing how far along the line we are.

An equivalent representation is:
p = p0 + (p1 - p0)*t

This form does have some possible performance advantages.  First, there is only one multiplication to perform.  Second, since p0 and p1 are constants, it is also possible to pre-compute the subtraction.

This basic formula also works for vectors, so p0 and p1 can be single floating point values, 2D or 3D points, or vectors of any other size.

This is such a common and basic function that it is an intrinsic function in shader languages.

Normalization


Quite often you will find that the values you want to use as the interpolation amount (t) are not between 0 and 1.

If you have a low and high range, it's fairly straightforward to normalize the values to a range between 0 and 1:

t = clamp((t0 - x0) / (x1 - x0))
where:
x0 is the minimum range value
x1 is the maximum range value
t0 is the current value
clamp is a function that forces values less than 0 to be come 0, and greater than 1 to become 1
t is the normalized value

Smooth Interpolation


Suppose we have three points, p0, p1, and p2.  We can interpolate between p0 and p1, and then from p1 to p2.  This allows us to follow a path through multiple points, but the results are usually not very satisfactory.  For motion of an object, changes in speed and direction are very abrupt and unnatural. 

One easy way to smooth out these transitions is to modify the value of t before doing the interpolation.  The main advantage to this is the ability to reuse the basic linear interpolation function for various non-linear interpolation methods.

Smoothstep is a commonly used function for this purpose.  The smoothstep function, with its first and second derivatives:
t = 3*t0^2 - 2*t0^3
t' = 6*t0 - 6*t0^2
t'' = 6 - 12*t0
where:
t0 is the initial value
t is the new value
t' and t'' are the first and second derivatives

Because t' (the first derivative) is zero at t0=0 and t0=1, there will be less apparent discontinuity as we pass through each point.

The second derivative is still non-zero at t0=1, which may still be perceived as a discontinuity.  In terms of physics, this would be the same as having zero velocity at the end point, but non-zero acceleration.

This function is common enough to be, like lerp, implemented in shader languages.  Implementations for smoothstep typically also include the normalization step, so t = smoothstep(0, 1, t0) is equivalent to the basic smoothstep function.

A smoother possible function is:

t = 6*t0^5 - 15*t0^4+10*t0^3
t' = 30*t0^4 - 60*t0^3 + 30*t0^2
t'' = 120*t0^3 - 180*t0^2 + 60*t0

This will have first and second derivatives equal to zero at t0=0 and t0=1.


Other Curves



There are many other possible functions that you may find useful, depending on the circumstances.  In general, any function that gives output values in the range [0,1] for input in the range [0,1] will work.

t = t0^2
Fast End - starts slowly at t=0, but increases rapidly towards t=1:

t = t0*(2-t0) = 1-(1-t0)*(1-t0)
Fast Start - essentially the inverse of Fast End

t = 2*t0^3 - 3*t0^2 + 2*t0
Fast Start End - fast start, slow middle and fast end values

t = 0.5 - cos(PI*t0)*0.5
Cosine interpolation

Conclusion


I have found it useful to have all of these curves available (and their derivatives and integrals) available in a general-purpose library.

Hopefully there is some useful information here that helps you with your own programming!


1 comment:

  1. You forgot to mention my personal favorite!

    p(t) = r * ( pd - p(t-1) )

    where:
    - r is a constant in the ]0,1] range
    - pd is the desired destination of the value

    I really like it because:
    1. It handles preemption of the destination naturally, which is great in applications like head tracking
    2. It requires no transient data. Notice the absence of p0,

    Point 2 is particularly great because it makes implementations super clean and robust naturally.

    ReplyDelete

Note: Only a member of this blog may post a comment.