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:
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\):
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:
Here lies a point that doesn't land neatly on the grid. This point doesn't have a defined value, so you are going to make one up.
You aren't going to make up a random value, however. The four neighbors around the point will guide your decision.
You 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].
You 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 you 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. Your lerp function tells you its value:
$$
\begin{array}{c}
75 + 0.7 \times (97 - 75) \\
\downarrow \\
90.4
\end{array}
$$
Next you turn your attention to the top point, which is between the other two neighbors.
The top point's fractional x-component is also 0.7. Your lerp function tells you 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. Your lerp function tells you its value:
$$
\begin{array}{c}
90.4 + 0.2 \times (71.6 - 90.4) \\
\downarrow \\
86.64
\end{array}
$$
Three lerps later, you have the point's value.
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.
