Basic Math: Interpolation
27 May 2015 - Jon Hall
The dreaded field of mathematics: Numbers! Letters! Symbols! It had to rear its ugly head sooner or later.
Whenever we need to cover something that probably isn't simple common math, I'll try to slip in a post to explain the concept as humanely as possible.
This time around, I'll cover Interpolation and its counterpart, Extrapolation.
What is it?
Interpolation is a method of constructing new data points within the range of a discreet data set of known data points.
Simply put, it's a way to connect the dots with a line, knowing what kind of shape we want.
The prefix inter- usually infers along the lines of 'between' or 'among', and when switched with the prefix extra- (meaning 'outside' or 'beyond') you can establish a definition for extrapolation: estimating a value beyond the original observation range, on the basis of its relationship with another variable.
The linear Interpolant and Extrapolant based off two Points
Experiment with the interactive Realmscape Labs Interpolation demonstration.
There are a variety of different methods we can use, based off mathematical functions that dictate the way we join, or extend, the data set.
(These are to show the variety, you don't need to properly understand anything other than linear methods, for now)
Linear inter/extrapolation (often known as lerp) is the most simple method, being the result of two values directly proportional to each other, resulting in a straight line.
Polynomial inter/extrapolation is a generalisation of linear interpolation, we replace the interpolant (mathematical function used to interpolate) with a polynomial of higher degree. The result of this is a curve which goes through points we can define explicitly with the polynomial. Polynomials are (comparatively) computationally expensive, even for a computer, so you'll generally avoid using these in real-time applications and games.
Spline interpolation yields a similar result to polynomial interpolation, but uses a series of low-degree polynomials to link the known points. This makes it more suited to real-time use, because calculating a series of small(er) polynomials will always be faster than evaluating a polynomial of high degree (even better, splines split the range into smaller sets, so even if the entire spline interpolant consists of ten polynomials, you'd likely only need to evaluate one of those to find your interpolated value).
Conic extrapolation creates a conic section using five points near the end of the known data set. It may result in an ellipse (or circle), or a parabolic or hyperbolic curve. Something like this is a lot more complex than what you'll encounter during my tutorials.
Why would we use it?
Keeping to the simplicity of linear inter/extrapolation, if we have a data set of two points (the 'start' and 'finish') then we can use a linear interpolant to calculate a data point anywhere between our start and finish. Plotted on a graph, given your X axis is distance and Y axis is time (generally, when interpolation is used in conjunction with visual output, one of the axis represents time), you can determine the exact 'height' at any given time between the 'start' and 'finish'.
We can use linear extrapolation to estimate a 'height' beyond the 'finish', with the assumption that the height keeps changing in a uniform manner (the same way as it had previously changed).
The age-old example of 'X = Y'
Spline interpolants may be used to simulate acceleration and deceleration, springs or bounciness, fluid movement of limbs, or even the path of a slalom skier.
How do we use it?
Experiment with the interactive Realmscape Labs Interpolation demonstration.
When used in the context of a variable time step game loop model (as in the previous blog post), your set of points refer to known values at given intervals (in animation these would be your transformation keyframes).
We can use interpolation to calculate the value(s) between those points at any given time (considered to be the X axis), obtaining analogue values from the set of discreet values.
No matter how much time has passed between 'ticks' of your engine, the precise position/rotation/transformation of your entity can be calculated and applied.
/r/realmscape