# Guided bilinear interpolation: is it a known algorithm?

I have a function that's sampled relatively coarsely along one direction, $$x$$, and much more finely along another, $$y$$. Sampling grid is regular. I need to interpolate between all these samples, with the following requirements:

1. Computation of the interpolated function must be $$O(1)$$ with respect to data resolution (it'll be done in a GLSL shader, with data being in a texture);
2. Overshoots and ringing, like Runge or Gibbs phenomena, are undesirable;
3. The interpolation shouldn't look aligned to the sampling grid, it should look more "natural" (see below for details).

The first two points are satisfied by the usual bilinear interpolation. But the third one isn't.

Let's consider the following example function:

$$f(x,y)=\sqrt{\frac{x-1}2}\exp\left(-\frac{\left(y-18-6\sin\left(\frac{x-1}2\right)\right)^2}{x^2-2x+5}\right).$$

Its domain is taken to be $$x\in[1,10],$$ $$y\in[1,30],$$ and sampling will be done over integral points: $$x=\{1,2,...,10\},$$ $$y=\{1,2,...,30\}.$$

Plotting the function as a density plot, we'll get the following smooth blob:

After sampling at integral points and doing bilinear upsampling, we'll get this "fluffy" blob, with noticeable rectangular cells:

This fluff is due to interpolation being done along horizontal directions between finely-sampled rows, thus missing the actual direction of isolines of the original function, leading to this steppy effect.

I've made a customization where an additional step is performed before actually computing the interpolation: matching the points of the neighboring well-sampled 1D functions to find direction along which to interpolate. The results are saved into an additional table to enable $$O(1)$$ computation. The result looks as follows:

This interpolating function still crosses all the sampling points, but does it in a more intelligent way, trying to follow the isolines of the original function.

My question is: have I reinvented a wheel? Is there a well-known algorithm that does something similar to improve the result of interpolation and satisfy all three requirements listed above?

• I bet this only works properly for your particular case and your particular data. A more general approach that would solve your problem is using a higher-order interpolation scheme, for example cubic spline interpolation works really well. Jul 20, 2022 at 13:19
• @CrisLuengo: I was thinking "I'm gonna suggest spline interpolation, but I'm not sure how that looks in an image!" Now I know... Jul 20, 2022 at 15:03
• @CrisLuengo cubic spline interpolation can lead to overshoot, see a simple example: i.stack.imgur.com/wMYkr.png . Thus, it explicitly doesn't satisfy requirement #2. Jul 20, 2022 at 15:19
• It won't lead to overshoot if your data is sampled correctly. Jul 20, 2022 at 15:37
• @CrisLuengo, There are splines which doesn't overshoot. Like MATLAB's pchip() and to some degree makima().
– Royi
Jul 8, 2023 at 19:36