in C#, Maths, Tutorial

Piecewise Interpolation

This is the second part of the tutorial dedicated to one of the most used Mathematical tools in Game Development: linear interpolation! In this part, we will explore how to extend the concept of linear interpolation to non-linear mappings. The final part will explore how to use them to correct colour curves.

You can find a link to download the C# scripts and the Unity package used at the end of this post.

Introduction

In the first part of this series, we introduced a mathematical technique known as linear interpolationlerp for short—which can be rather handy for game developers and programmers in general. From “blending” colours to “moving” between points, lerp is a very well known and loved tool that is present—in one form or another—in virtually all libraries and engines.

In its most basic form, lerp takes a number from \left[0, 1\right] and remaps it onto a different interval \left[a, b\right]. The opposite is also possible, and it is sometimes called inverse lerp. However, we can generalise linear interpolation so that it remaps a number x \in \left[a, b\right] to an arbitrary interval \left[c, d\right]. Some libraries, such as Arduino, calls this map, but in this tutorial we will keep call referencing it a a more generalised version of lerp.

The lerping equation is also rather simple:

(1)   \begin{equation*} y = c + \frac{d-c}{b-a} \left(x - a\right)\end{equation*}

and has a very well known geometrical interpretation. The original interval \left[a, b\right] is first shifted back, so that a lies on 0. It is then rescaled to \left[0, 1\right], and the same process repeat in reverse to stretch it and shift it back to \left[c, d\right]:

Equation (1) easily translates to the following function, giving us an easy and efficient way to lerp between numbers from any two arbitrary intervals:

Easing Curves

One of linear interpolation’s biggest strength—its simplicity—is also one of its worst limitations. As the name suggest, lerp can only be used to link two objects with a linear relationship. Geometrically, this means that lerp can only represents linear functions.

The diagram below shows how lerping from \left[a, b\right] to \left[c, d\right], really means deriving the equation of the line passing from \left(a, c\right) and \left(b, d\right):

This becomes apparent if you move an object lerping between its start and target positions. Because the movement is movement is linear, the object will start and stop moving very suddenly, resulting in a non-realistic behaviour.

Ones easy way to fix this is to use the so-called easing curves of functions. Those are mathematical functions that takes a number between \left[0, 1\right] and typically produce another number between \left[0, 1\right].

Linear interpolation always passes through the interval \left[0, 1\right]; this gives a way to plug in one of those functions inside our lerp equation, so tweak its overall behaviour.

Easing curves are very popular in UX and web design, where they can be used to create smooth and reactive movements.

The table below, from 1ucasvb’s lab, shows some common ones, and the overall effect they have on lerp:

⭐ Suggested Unity Assets ⭐
Unity is free, but you can upgrade to Unity Pro or Unity Plus subscriptions plans to get more functionality and training resources to power up your projects.

Piecewise Interpolation

Thanks to easing curves, linear interpolation can be used to create some more nuanced movements. However, this does not solve all of the problems that we might encounter, or the many problems that lerp can solve.

Linear interpolation only models a single line. But it is possible to approximate any arbitrary curve with a series of linear segments. The diagram below shows a curve (solid grey) being approximated with four segments. Each segment is linear, meaning that by using lerp on four different segments we can have a rough approximation of the original curve:

This techniques is known as piecewise linear interpolation, although sometimes multilinear interpolation is used as well (not to be confused with multivariate interpolation, which is linear interpolation in a higher dimension).

Piecewise interpolation can be a good way to approximate non-linear functions that would otherwise be impossible to model with lerp alone. This has many applications. For instance, it can be used to replace a very expensive function with a relatively inexpensive linear approximation. All that is needed is to sample the value of the function at some points x_i, and to get its values y_i. Linear interpolation will do the rest.

Construction

Let’s imagine that we have a function F that we want to approximate with piecewise interpolation. What we need is to store the values at which the function was sampled (float[] Xs) and its results (float[] Ys). The snipped below samples the function F every xStep, in the interval between xMin and xMax:

The arrays Xs and Ys is really all we need to perform piecewise interpolation.

Additionally, nothing stops us from using intervals of different lengths on the X axis. This means that if such an uniform sampling is underperforming in certain parts of the function, we can increase its precision where needed and use fewer points where the function is relatively well behaved.

Implementation

Once Xs and Ys are available, performing piecewise interpolation means taking an arbitrary value x and finding in which segment it is contained. This means finding the index inside the array so that Xs[index-1] <= Xs[index].

There are countless way to do this. The naïve one is to loop through Xs, stopping when x > Xs[index]. However, it is not the most efficient way; in fact, it can potentially loop through the entire array. When there is the risk that an algorithm will loop through the entire length of an array to perform its task, it is said that it has a liner complexity. The Big O notation is often used to summarise this: \mathcal{O}\left(n\right).

However, we can take advantage of the fact that the values inside Xs are sorted. After all, when you are searching for a word in a dictionary, you do not leaf through the pages starting from the cover! An efficient approach to find an value inside an array is to use the so-called binary search. In a nutshell, at every step it splits the array into two parts, and focuses on the one that should contain the value:

With every new iteration, binary search reduces the search space in half. If the value is not present in the array, it will continue to subdivide until it reaches a single element. The number of steps is, therefore, logarithmic in the length of the array. This is because \log_2 \left( n\right) represents the number of times you need to divide n by 2 to reach 1. For this reason, we can say that the binary search algorithm has logarithmic complexity; or \mathcal{O}\left(\log{n}\right) in the Big O notation.

Luckily for us, C# has a good implementation of the binary search algorithm: Array.BinarySearch:

The returned index is the exact position in the array Xs where the value x was found. If not found, the method returns a negative number which, according to the official .NET documentation:

The index of the specified value in the specified array, if value is found; otherwise, a negative number.

If value is not found and value is less than one or more elements in array, the negative number returned is the bitwise complement of the index of the first element that is larger than value.

If value is not found and value is greater than all elements in array, the negative number returned is the bitwise complement of (the index of the last element plus 1).

This allows us to design a simple function to finally perform piecewise interpolation:

Inverting Functions

There is another vey useful case for the piecewise linear interpolations: inverting functions. Let’s imagine a function F so that y=F\left(x\right); the inverse of F (often indicated at F^{-1}, which is not \frac{1}{F}) is a function so that F^{-1}\left(y\right)=x.

Inverting a function is highly non-trivial and computationally expensive. Not all functions admit an inverse, while some are not in a closed-form (meaning that they cannot be calculated with a finite number of “standard” operations).

Geometrically speaking, however, inverting a functions is easy. All we need to do is to flip the X and Y axes! For this reason, if Lerp(Xs, Ys, x) is the piecewise approximation for F, Lerp(Ys, Xs, y) is the piecewise approximation for F^{-1}. And this allows to invert functions for free!

In all fairness, things are a bit more complicated. In fact, for this to work it is necessary that even the produced Ys are sorted. If not, function cannot be inverted as there would be multiple possible answers for a single value.

Gradient Interpolation

One very interesting applications of piecewise linear interpolation is the creation of colour gradients. The original code presented above was designed for floats, so a few small changes are required:

In the code above, the array of floats has been replaced with an array of Colors.

Now, it is easy to create a hue gradient just with an array of colours and their positions:

What’s Next…

The third and final part of this series will show how piecewise linear interpolation can be used to correct colour curves and gradients.

Download Unity Package

The Standard package contains the script to perform piecewise linear interpolation. It uses extension methods which allows to easily interpolated numbers, vectors, colours and even quaternions! The Advanced package, instead, contains a test scene which also shows how to correct colour curves.

FeatureStandardAdvanced
Linear Interpolation
Piecewise Interpolation
Test scene
Colour Curve Correction

💖 Support this blog

This websites exists thanks to the contribution of patrons on Patreon. If you think these posts have either helped or inspired you, please consider supporting this blog.

Twitter_logo

YouTube_logo
📧 Stay updated

You will be notified when a new tutorial is relesed!

📝 Licensing

You are free to use, adapt and build upon this tutorial for your own projects (even commercially) as long as you credit me.

You are not allowed to redistribute the content of this tutorial on other platforms. Especially the parts that are only available on Patreon.

If the knowledge you have gained had a significant impact on your project, a mention in the credit would be very appreciated. ❤️🧔🏻

Write a Comment

Comment

  1. Very helpful article!
    When reading through it I thought there was another simpler way to get to the right index of the function samples, assuming that the step between the samples is consistent. This approach would have an O(1) complexity. Here is an untested implementation – I hope it can show the basic idea:

    public static float Lerp (float[] Xs, float[] Ys, float x)
    {
    float n = Xs.Length;
    float xMinOriginal = Xs[0];
    float xMaxOriginal = Xs[n – 1];
    // Don’t support extrapolation:
    if (x = xMaxOriginal)
    return Ys[n – 1];
    // Map to values that correspond to the array index progression
    float percent = Mathf.InverseLerp(xMinOriginal, xMaxOriginal, x);
    float step = 1f / (n – 1);
    int matchedRangeStartIndex = (int) (percent / step);
    float matchedRangePct = (percent % step) / step;
    return Mathf.LerpUnclamped(Ys[matchedRangeStartIndex], Ys[matchedRangeStartIndex + 1], matchedRangePct);
    }

    • When I copied this method from my code editor, it seems like I missed a line for the extrapolation checks. Here is the revised version:

      public static float Lerp (float[] Xs, float[] Ys, float x)
      {
      float n = Xs.Length;
      float xMinOriginal = Xs[0];
      float xMaxOriginal = Xs[n – 1];
      // Don’t support extrapolation:
      if (x = xMaxOriginal)
      return Ys[n – 1];
      // Map to values that correspond to the array index progression
      float percent = Mathf.InverseLerp(xMinOriginal, xMaxOriginal, x);
      float step = 1f / (n – 1);
      int matchedRangeStartIndex = (int) (percent / step);
      float matchedRangePct = (percent % step) / step;
      return Mathf.LerpUnclamped(Ys[matchedRangeStartIndex], Ys[matchedRangeStartIndex + 1], matchedRangePct);
      }

Webmentions

  • Linear Interpolation - Alan Zucconi February 24, 2021

    Hi again!
    I have now tested my alternative method with the O(1) complexity and posted it on github if anyone is interested:

    https://gist.github.com/FleshMobProductions/194a4f98f0b397e4fe8d9c79592c3a7f