Linear Interpolation

Suppose we have 3 cats at the beginning of the year, and 13 by the end. How many do we expect to have on July 1? In the absence of any other information, 8 is a reasonable answer. Just as July 1 is 50% of the way through the year, 8 is 50% of the way between 3 and 13.

The strategy we have just applied is linear interpolation. We plot a linear path between two known data points and guess that values between the two points fall on the line. Here's the line spanning the days of the year on the x-axis and the number of cats on the y-axis:

We have recently learned that WebGL interpolates colors between texels. It does this automatically in hardware. However, there will be occasions in which we need to interpolate values in software. As a graphics developer, therefore, we should have our own linear interpolation function at the ready. Graphics developers call this function lerp, which is a contraction of linear interpolation. It is used as a verb: "We gotta lerp the bee from this flower to that one."

Here's another problem to help you develop the lerp algorithm. Suppose you are 150 centimeters tall at age 12 and 175 centimeters tall at age 17. How tall are you at age 13? 13 years is 20% of the way between 12 and 17 years. We work out your intermediate height by starting at 150 and tacking on 20% of the height change:

Let's generalize this formula. We must be given two coordinate pairs. Call them \(\mathrm{start}\) and \(\mathrm{end}\). The x-coordinates of these data points represent space or time. The y-coordinates represent size, color, position, or some other value that changes across time or space. We must also be given \(\mathrm{mid}_x\), an x-coordinate whose y-coordinate is unknown. The job of our lerp function is to compute \(\mathrm{mid}_y\).

The first step is to figure out the percentage of the domain that \(\mathrm{mid}_x\) represents. This percentage is often given the name \(t\) and is defined as follows:

The percentage is then applied to the range to produce \(\mathrm{mid}_y\):

That's one expression of the lerp formula. However, sometimes we see the right-hand side expressed differently. Distribute \(t\), regroup, and factor to derive this equivalent form:

Performance buffs favor this second formula because it can be compiled down to two vectorized instructions on the GPU.

Game engines usually provide a three-parameter version of lerp. Both Unity and the Unreal Engine do. With these functions we precompute \(t\) and pass in just \(\mathrm{start}_y\), \(\mathrm{end}_y\), and \(t\).

To lerp a vector, we lerp its scalar components independently.

Bilinear Interpolation

Our lerp function only handles interpolation along one dimension and between two known data points. When the graphics card does a texture lookup, it interpolates along two dimensions and between four known texels. Step through this breakdown of the algorithm to see how it's done:

Here lies a point that doesn't land neatly on the grid. This point doesn't have a defined value, so we are going to make one up.

We aren't going to make up a random value, however. The four neighbors around the point will guide our decision.

We need to know the integer coordinates of the four neighbors.

This point's coordinates will be between the integer coordinates of the neighbors. Here the point is at [18.7, 33.2].

We also need to know what the values are at the four neighbors. For textures, these values will be RGB triplets. For simplicity, this example sticks with scalar values.

Time to start calculating the in-between point's value. Blending all four neighbors together at once is too confusing. Instead we think about this bottom point, which is between just two neighbors.

That bottom point's fractional x-component is 0.7. That's means it's 70% of the way along the southern edge of the cell. Our lerp function tells us its value: $$ \begin{array}{c} 75 + 0.7 \times (97 - 75) \\ \downarrow \\ 90.4 \end{array} $$

Next we turn our attention to the top point, which is between the other two neighbors.

The top point's fractional x-component is also 0.7. Our lerp function tells us its value: $$ \begin{array}{c} 94 + 0.7 \times (62 - 94) \\ \downarrow \\ 71.6 \end{array} $$

Look at that. Now the point in the middle lies on a line between two known values.

The middle point's fractional y-component is 0.2. Our lerp function tells us its value: $$ \begin{array}{c} 90.4 + 0.2 \times (71.6 - 90.4) \\ \downarrow \\ 86.64 \end{array} $$ Three lerps later, we have the point's value.

previous next

Linearly interpolating between four points in two dimensions is called bilinear interpolation. Bilinear interpolation reduces down to three linear interpolations, two along one of the dimensions and a third along the other dimension.