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.

- Part 1: Linear Interpolation
- Part 2:
**Piecewise Interpolation** - Part 3: Color Curve Correction

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 interpolation**—*lerp* 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 and remaps it onto a different interval . The opposite is also possible, and it is sometimes called **inverse lerp**. However, we can generalise linear interpolation so that it remaps a number to an arbitrary interval . 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)

and has a very well known geometrical interpretation. The original interval is first shifted back, so that lies on . It is then rescaled to , and the same process repeat in reverse to stretch it and shift it back to :

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

public static float Lerp (float x0, float x1, float y0, float y1, float x) { float d = x1 - x0; if (d == 0) return (y0 + y1) / 2; return y0 + (x - x0) * (y1 - y0) / d; }

## 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 to , really means deriving the equation of the line passing from and :

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 and typically produce another number between .

Linear interpolation always passes through the interval ; 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 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 , and to get its values . 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`

:

float[] Xs new float[N]; float[] Ys new float[N]; // Samples the function F in the [xMin, xMax] interval float xStep = (xMax - xMin) / (N-1); for (float x = xMin; x <= xMax; x += xStep) { Xs[i] = x; Ys[i] = F(x); }

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: .

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 represents the number of times you need to divide by to reach . For this reason, we can say that the binary search algorithm has **logarithmic complexity**; or in the Big O notation.

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

int index = Array.BinarySearch(Xs, s);

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:

public static float Lerp (float[] Xs, float[] Ys, float x) { // Finds the right interval int index = Array.BinarySearch(Xs, x); // If the index is non-negative // an exact match has been found! if (index >= 0) return Ys[index]; // If the index is negative, it represents the bitwise // complement of the next larger element in the array. index = ~index; // index == 0 => result smaller than Ys[0] if (index == 0) return Ys[0]; // index == Ys.Length => result greater than Ys[Ys.Length-1] if (index == Ys.Length) return Ys[Ys.Length - 1]; // else => result between Ys[index-1] and Ys[index] // Lerp return Lerp ( Xs[index - 1], Xs[index], Ys[index - 1], Ys[index], x ); }

### Inverting Functions

There is another vey useful case for the piecewise linear interpolations: inverting functions. Let’s imagine a function so that ; the inverse of (often indicated at , which is *not* ) is a function so that .

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 , `Lerp(Ys, Xs, y)`

is the piecewise approximation for . 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 `float`

s, so a few small changes are required:

public static Color Lerp (float[] Xs, Color[] Cs, float x) { ... // Color Lerp return Color.Lerp ( Xs[index - 1], Xs[index], Cs[index - 1], Cs[index], x ); }

In the code above, the array of `float`

s has been replaced with an array of `Color`

s.

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

Color[] Cs = new Color[] { Color.red, // 0° Color.yellow, // 60° Color.green, // 120° Color.cyan, // 180° Color.blue, // 240° Color.purple, // 300° Color.red, // 360° }; float[] Xs = new float[] { 0, 60, 120, 180, 240, 300, 360 }; Color c = Lerp (Xs, Cs, 30); // Between red and yellow

## 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.

- Part 1: Linear Interpolation
- Part 2:
**Piecewise Interpolation** - Part 3: Color Curve Correction

### Download Unity Package

Become a Patron!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.

Feature | Standard | Advanced |
---|---|---|

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.

##### 📧 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. ❤️🧔🏻

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);

}

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