The problem

Suppose you have a heightmap. At each position, you store a height value. How do you find heights for positions "between" ones in your map?

For example, we have a small number of terrain values in our array, and we want to draw the terrain to our 5K display. How do we pick a height for some pixel?

Standard approaches

Well, there a billion ways to interpolate betwen some number of arbitrary points, as you may recall from your compsci math classes. Let's work an example. Here's a gentle cliff:

Side note: I will work with 1-dimensional problems in this post, although the problem is easily extendible to higher dimensions.

Let's start with the easiest solution, a line:

This is, you know, pretty much fine. It looks how we imagine terrian would look with this data: 1. There's a flat part on top 2. And flat part on bottom 3. And a steep slope in the middle

At this point you are, you know, 80% of the way there. Depending on your requirements you can probably ship this line off to the GPU, which will be connecting them with lines (e.g., triangles) anyway.

But now you want to shade in between your polygons. And maybe light them. Well, for that, we want a nice curve and a clean derivative. Here's the derivative of our line:

It doesn't even exist at very reasonable positions like $3$. So, you might go looking for a nicer curve that's easier to work with.

Cosine

So, you consult Paul Borke, the internet authority on practical interpolations. First, cosine interpolation.

Most people have the reasonable intuition that terrain doesn't wriggle around like that. Only if you are a programmer or a mathematician would you ask, "but maybe a wriggle is okay if it's very small?"

It isn't okay, as we see in the derivative.

If you told a GPU to draw something like the line as a geometry (or you just have in your mind somewhere that that's how it's supposed to look). And then you light it based on this function, you're going to have a bad time. Your cliff is supposed to be a slope, but it has these flat regions inside it. That's no good.

Cubic

So you go back to Paul and ask for a better function. One which offers true continuity between segments. One with a continuous derivative. This time, he recommends the cubic interpolation:

This is... not even a little bit how terrain looks. $0-3$ is supposed to be flat!

Then, you look at the derivative:

Hoo boy. I mean it is technically continuous. It isn't, you know... sensible in any way.

The solution:

Just go back to the top of this post and draw the terrain between the points. Here is the curve I drew:

I submit that you or anyone would draw a curve "about like this". It is the curve that terrain ought to look like. We can break down its properties more formally:

1. As described earlier, it is flat when the line is flat, sloped when the line is sloped. This is unlike the cosine and cubic interpolations.
2. It has a smooth arc, unlike linear interpolation.
3. It's biased symmetrically, pulling the ground inwards toward the slope. We can imagine a function that pulls outwards, or that does one thing on the left and the other on the right, but a lot of those functions tend to violate our "terrain intuition" on some inputs.
   1. (Alternatively some are global in scope, requiring some in-order process of the whole heightfield to ensure consistent results.)

4. It's obviously going to have a nice derivative.

So to derive this curve, we start with the cubic bezier $b(a,c_1,c_2,b)$. The nice thing about bezier curves is that points $a$ and $b$ define the points between which we are interpolating, (so, that part is done!) while points $c1$ and $c2$ indirectly control the tangent at $a,b$. So, by clever choice of $c_1,c_2$ we can guarantee a continuous derivative.

Suppose we want a function $terrain(l,a,b,r)$ which interpolates from $a$ to $b$ (with $l$ on the left of $a$ and $r$ on the right of $b$.) We first define points on either side of $a,b$:

$scale$ here is a constant between $[0,1]$. I generally like $0.4$.

To "pull inwards", we choose for our slope from $a,b$ the minimum of these, taking care to get our signs correct:

Then we simply calculate control points:

Now that we've defined our function, let's check out the derivative:

This should be relatively sensible to do shading and lighting with. And of course, Batman is clearly the correct derivative for any situation.

Here is a comparison with the line derivative, showing a moderate correpsondance. For an effect that is different enough to be be worth implementing, but not so different as to look wrong, this is a good result.

There is a "easy" extension of this approach to three dimensions following the linear => bilinear transformation.