HeightMap from a graph

Question

This is just a toy experiment.

I laid out a graph in 2d space, so that every node has x and y coordinates. I'm considering degree of a node as a height value at position x and y of a height map.

I wonder what's the best strategy to interpolate this sparse heightmap with missing values?

Ideally I'd love to have some sort of gravitational pull towards the bottom in the places where I don't have height values. Think of it like somebody dropped fabric on bunch of spikes...

Answer 1

TL;DR: Use bicubic interpolation or spline interpolation.

So, you're looking for a method of two-dimensional interpolation. Unfortunately, this isn't a perfect two-dimensional grid (mathematically, it's not a lattice). We have irregularly-spaced points, and so this makes things slightly less convenient. However, we still have plenty of options:

• Nearest-neighbor interpolation: For each point pi(xi,yi), this method takes into account the value of the nearest point to pi. The result is something like a two-dimensional step function. While this method can be simple, it also results in functions which are discontinuous, and so it's pretty terrible for height maps (unless you like having cliffs everywhere, in which case go for it).
• Bilinear interpolation: Essentially, linearly interpolate in one coordinate (say, the x-direction) for each "slice" of the graph. Next, interpolate in the other (orthogonal) coordinate. The result is a chunky graph of plates at odd angles. While it doesn't have the discontinuities of the nearest-neighbor method, it does lead plenty of places where the terrain isn't differentiable. In some cases, this can lead to sudden shifts in the slope of the surface - again, not great for height maps.
• Bicubic interpolation: This is akin to bilinear interpolation in that it extends a one-dimensional method (cubic interpolation/cubic Hermite spline) to two dimensions. You'll see some benefits here: smooth, continuously differentiable functions (unless you're dealing with an objectively evil set of data), which are helpful in your case. If you want, you can do this to higher degrees by just modifying polynomial interpolation to the nth degree. However, cubic interpolation is often fine. Lagrange polynomials (which I discussed here) are something to be familiar with if you want to implement something like this by hand.
• Spline interpolation: This uses higher-degree polynomials called splines, which are generally smooth. It can remove some difficulties that may arise in polynomial interpolation, such as Runge's phenomenon (basically, freaky oscillations that nobody likes). It also generally has low errors and thus high accuracy.

Here's a visual comparison of these methods:

^{Image courtesy of Wikipedia user Cmglee under the Creative Commons Attribution-Share Alike 4.0 International license.}

You can implement these by hand, if you so desire. However, many numerics libraries have them built-in. Take Python's SciPy, for instance (I'm using Python as an example because it's what I'm most familiar with). It has several methods of interpolation which can be used without too much trouble (I just came across this Stack Overflow answer by Andras Deak, an awesome comparison of some of them):

• scipy.interpolate.interp2d uses spline interpolation. The default is linear, i.e. bilinear interpolation. However, you can also choose cubic (bicubic) or quintic, if you want, both of which should have some advantages over linear - as I discussed earlier. You might see some issues arise, especially if you use the "evil function" Andras Deak took as an example. It's possible that you might see some problems arise here, but for a height map, you could escape with your data (and dignity) intact.
• scipy.interpolate.griddata can also use various methods we discussed before (nearest-neighbor, bilinear, and bicubic). This beats out interp2d for evil cases and is still more accurate on some other challenging functions/data sets, but again, those are probably not going to arise in your applications.
• That SO answer also mentions scipy.interpolate.Rbf. This is a good choice if and only if you have a function whose values are dependent entirely on distance from the origin. This is likely to not be the case for almost any height map you'd realistically want to deal with. I've used it before, and it can have some cool results, but something like bicubic interpolation is often better - at least, in my experience.