I'm creating a three-dimensional model of the earth based on SRTM height data. The data set is pretty huge, so only a small fraction of the data is available at any given time.

The height data is organized in 1° x 1° tiles which come in different resolutions (from 1x1 to 1200x1200, roughly in power-of-two steps). For visualization purposes, I'm sampling the surface in equidistant steps. The sampling theorem gives me an optimal tile resolution to work on, and as long as the point is in the middle of a tile or all neighbouring tiles have the same resolution, this is pretty straightforward.

I'm currently employing cubic splines to get a continuously differentiable surface function. Data points are grey, the sampled point is the red x, used data points are green.

Bicubic interpolation

The problem appears when a point is near the border of two differently-resolved tiles.

Using the point's nearest neighbours and linearly interpolating between them gives me a continuous surface, but not a differentiable one:

Differently-Resolved tiles

The most common of such neighbourships is unfortuanely a large (1200x1200 or 600x600) tile being next to a 1x1 one.

I need an algorithm for interpolating smoothly on these borders that offers

  • near-exact results if the queried point coincides with a tile data point
  • continuous differentiability in both directions
  • high-frequency features fading out quickly into low-resolution tiles
  • good performance (possibly at the expense of accuracy)
  • 1
    $\begingroup$ One relatively uninformed idea: when you reach a spot near a resolution barrier like you illustrated above, you could interpolate the lower-resolution tile to match the sampling grid of the higher-resolution tile. In the plot you gave above, you could interpolate the right tile in the Y direction first so that its grid lines up with the tile on the left, then interpolate across the X direction to get the right sampling interval on that axis. You would only need to do this extra processing near the tile boundaries, based on the size of your interpolation kernel. $\endgroup$ – Jason R Mar 24 '14 at 16:24
  • $\begingroup$ So I'd basically have to scale up the low-resolution tile near the border in a linear fashion like above, and then do bicubic interpolation as before. That seems to be worth a shot, yes. $\endgroup$ – trion Mar 24 '14 at 17:19
  • $\begingroup$ You could still use cubic interpolation to scale up the low-res tiles for the most part. If you ever hit a case where you had a low-res tile surrounded by high-res tiles on multiple sides, then you would potentially need to drop down to a linear interpolator in those corners. I hope that makes sense without an illustration. $\endgroup$ – Jason R Mar 24 '14 at 17:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.