Interpolating Yourself

Suppose you have 3 cats at the beginning of the year, and 13 by the end. How many do you 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 you have just applied is linear interpolation. You are plotting a linear path between two known data points and guessing 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:

You have recently learned that WebGL interpolates colors between texels. It does this automatically in hardware. However, there will be occasions in which you need to interpolate values in software. As a graphics developer, therefore, you should have your 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: "You 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. You work out your intermediate height by starting at 150 and tacking on 20% of the height difference:

$$ 150 + 0.2 \times (175 - 150) = 150 + 0.2 \times 25 = 155 $$

This can be generalized. You 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. You must also be given \(\mathrm{mid}_x\), an x-coordinate whose y-coordinate is unknown. The job of your 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:

$$ t = \frac{\mathrm{mid}_x - \mathrm{start}_x}{\mathrm{end}_x - \mathrm{start}_x} $$

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

$$ \mathrm{mid}_y = \mathrm{start}_y + t \times (\mathrm{end}_y - \mathrm{start}_y) $$

That's the formula for your lerp function. You can also work it out using an argument based on similar triangles.

Sometimes you'll see the right-hand side of this formula expressed differently. Distribute \(t\), regroup, and factor to derive this equivalent form:

$$ \begin{aligned} \mathrm{mid}_y &= \mathrm{start}_y + t \times (\mathrm{end}_y - \mathrm{start}_y) \\ &= \mathrm{start}_y + t \times \mathrm{end}_y - t \times \mathrm{start}_y \\ &= \mathrm{start}_y - t \times \mathrm{start}_y + t \times \mathrm{end}_y \\ &= (1 - t) \times \mathrm{start}_y + t \times \mathrm{end}_y \\ \end{aligned} $$

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. You are expected to pass in \(\mathrm{start}_y\), \(\mathrm{end}_y\), and \(t\).

Bilinear Interpolation

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

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 third along the other dimension. Maybe you can guess how to interpolate between eight points in three dimensions and what you'd call it.

You're about to learn how to generate terrain from a texture. To move smoothly across the undulating but discrete terrain, you'll need a bilinear interpolation function.