Hello,

Bilinear interpolation generates visible crosses, see image from wikipedia to see what I mean, I mean the horizontal and vertical structures and sharp edges:

Bicubic interpolation looks much rounder:

Imagine now that the colors are types of world (tundra, desert, grass, ...): the rounder shapes are *highly* preferable over the ugly "crosses" of bilinear interpolation.

However, bicubic interpolation has two disadvantages (the second being the most problematic for me):

1.) It requires 16 points, rather than only 4 points. It would be highly preferable for me to only have to use the 4 corners of a square zone, not corner points of neighboring zones as well

2.) Values can overshoot, that is, they can become lower or higher than the 4 corners of this zone. I really don't want this, "conditions" in a zone should be bounded by its corners for convenience reasons (predictable range of values in a zone).

So, the question is:

Does there exist a way of 2D interpolating that only uses 4 corner points and only returns values in that range, but, looks "rounder" than bilinear interpolation?

Thanks!

Yes and no.

What you essentially have there is value noise. With value noise you can get approximately smooth by using a smoothstep function http://en.wikipedia.org/wiki/Smoothstep and that will look a little less blocky but boundaries will still be visible. In order for value noise to be smooth across boundaries points on both sides are needed. So to look like the bicubic version you will need 4 points for a 1D signal, 16 for a 2D or 64 for a 3D signal. I personally prefer Bezier (it doesn't overshoot, hits each control point exactly, and look absolutely gorgeous) or Catmull-Rom interpolation over Bicubic.

The other common option is gradient noise. You can get smoother results with less points. Perlin and Simplex noise are 2 common examples.

I personally prefer value noise, as it is less prone to obvious patterns, and tend to look more interesting; but for real-time applications gradient noise is often the way to go due to being so much faster to compute.

*edit: I think I made a mistake there

Awesome! That is a great idea and works great, thanks!

EDIT: never mind the other comment I posted here, Smoothstep does look visually better than http://dinodini.wordpress.com/2010/04/05/normalized-tunable-sigmoid-functions/ :)

I personally prefer Bezier (it doesn't overshoot, hits each control point exactly, and look absolutely gorgeous).

How does that work? The cubic bezier on Wikipedia does not hit each control point, only the outer two - but then it's also 2D intead of 1D:

http://en.wikipedia.org/wiki/B%C3%A9zier_curve

Can this be calculated in a way similar to bicubic interpolation? I couldn't find anything.

THanks a lot!

I personally prefer Bezier (it doesn't overshoot, hits each control point exactly, and look absolutely gorgeous).

How does that work? The cubic bezier on Wikipedia does not hit each control point, only the outer two - but then it's also 2D intead of 1D:

http://en.wikipedia.org/wiki/B%C3%A9zier_curve

Can this be calculated in a way similar to bicubic interpolation? I couldn't find anything.

Look no further than Wikipedia: http://en.wikipedia.org/wiki/Bezier_patch

Basically, you do Bézier interpolation between Bézier curves along the additional parameter dimension.

However, a really good looking surface is going to need data beyond the 4 vertex heights of one rectangular grid cell, because it needs good looking normals at grid vertices, and figuring them out from other grid vertices is better than assigning fixed normals (all up, like in "smoothstep" C1 alternatives to C0 linear interpolation) or random normals (which would show patterns). Storing a precomputed normal (or even a normal and curvature) for each vertex might be more convenient than looking up adjacent vertices.

I personally prefer Bezier (it doesn't overshoot, hits each control point exactly, and look absolutely gorgeous).

How does that work? The cubic bezier on Wikipedia does not hit each control point, only the outer two - but then it's also 2D intead of 1D:

http://en.wikipedia.org/wiki/B%C3%A9zier_curve

Can this be calculated in a way similar to bicubic interpolation? I couldn't find anything.

THanks a lot!

You may be right... I implemented it all years ago, so TBH I can't find my source material. The code I use for interpolation has served me very well over the years, but perhaps I was mistaken and I thought I was using a bezier spline when in fact I was using another type. Or perhaps it actually doesn't hit every control point exactly. Clearly I'll have to take another look at it.

Perhaps I was thinking of Catmull-Rom splines when I said they hit every control point exactly and don't overshoot. And when I said Bezier spline I probably meant BSpline.

Mathematically, the Bezier formulation is equivalent to the normal bicubic and bilinear interpolation formulas. It's really only a different basis: power vs Bernstein basis. However, the Bezier form handles the "control point" vertices more naturally than the power basis.