Jump to content

  • Log In with Google      Sign In   
  • Create Account

Something between bilinear and bicubic interpolation?


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
7 replies to this topic

#1 Lode   Members   -  Reputation: 982

Like
0Likes
Like

Posted 03 August 2014 - 02:35 PM

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:

 

jLg2YP4.png

 

Bicubic interpolation looks much rounder:

 

RedJIfK.png

 

 

 

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! smile.png


Edited by Lode, 03 August 2014 - 03:58 PM.


Sponsor:

#2 Ryan_001   Prime Members   -  Reputation: 1486

Like
3Likes
Like

Posted 03 August 2014 - 06:12 PM

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 unsure.png  


Edited by Ryan_001, 20 August 2014 - 05:57 AM.


#3 Lode   Members   -  Reputation: 982

Like
0Likes
Like

Posted 04 August 2014 - 12:20 PM

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/ :)


Edited by Lode, 04 August 2014 - 12:48 PM.


#4 Lode   Members   -  Reputation: 982

Like
0Likes
Like

Posted 16 August 2014 - 02:35 AM

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!



#5 LorenzoGatti   Crossbones+   -  Reputation: 2779

Like
0Likes
Like

Posted 19 August 2014 - 07:39 AM

 

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.


Produci, consuma, crepa

#6 Ryan_001   Prime Members   -  Reputation: 1486

Like
1Likes
Like

Posted 20 August 2014 - 05:57 AM

 

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.


Edited by Ryan_001, 20 August 2014 - 06:09 AM.


#7 Hodgman   Moderators   -  Reputation: 32028

Like
0Likes
Like

Posted 20 August 2014 - 06:06 AM

This might also be of interest:
http://iquilezles.org/www/articles/texture/texture.htm

#8 cadjunkie   Members   -  Reputation: 1354

Like
0Likes
Like

Posted 20 August 2014 - 12:44 PM

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.






Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS