Mathematical definition for Interpolation Algorithms

Grasshopper
1

Just questions/clarifications for how the Interpolate Data component works.

Here’s how I understand each algorithm although I’m not sure if they’re correct.

  1. Block - looks like applying floor/ceiling
  2. Linear - drawing lines along the data points, new points would lie inside the lines
  3. Catmull - approaches a spline?, i.e. if my understanding of Catmull-Clark is correct.

I can’t get a feel for Cubic though. How does it work?

image
image.png1164×636 99.3 KB

2

Block just takes the value of the nearest sample.
Linear interpolates between the nearest samples on either side according to x_t = (1-\hat{t})x_0 + \hat{t}x_1 where x_t is the interpolated value at t and \hat{t} is the normalised parameters between the adjacent samples x_0 and x_1.
Cubic relies on four samples (the nearest two on either side) and uses a polynomial instead of a linear expression.

3

http://paulbourke.net/miscellaneous/interpolation/

4

Thanks!

5

Huh, I’ve never used the Interpolate Data component before, but the behavior of Cubic doesn’t seem to make any sense, either by the standard algorithm (as presented in Paul Bourke’s website) or @DavidRutten’s explanation

E.g. in the screenshot below, shouldn’t the interpolated interval between t_1 and t_2 be a cubic polynomial that passes through the four sample points circled in blue? It certainly doesn’t look that way though…

image
image1670×598 64.4 KB
cubic-interpolation-oddity.gh (12.3 KB)

1 Like
6

Yeah it seems to be off, I always use Catmull instead.

7

Ah, would that be considered a bug or is there some other underlying logic to the interpolation?

Also, does “Catmull” (I’m assuming Catmull-Rom spline, not Catmull-Clark subdivision) use uniform, centripetal or chordal parameterization? Just curious.

8

Both to be perfectly accurate. But changing it now would make files using the existing algorithm behave differently. I probably won’t change it for GH1 any more. Here are the interpolation schemes that will be available in GH2:

interpschemes
interpschemes1352×739 62.1 KB

  • Block: nearest value wins (same as in GH1)
  • Linear: straight interpolation between adjacent values (same as GH1)
  • Log-Linear: straight interpolation between adjacent values, but “straight” in a logarithmic sense. Only works on positive values.
  • Cubic: standard cubic interpolation, but correct unlike in GH1
  • Cubic Monotone: a cubic scheme which prevents any overshooting. If a sample is higher than both its immediate neighbours, the highest value on the interpolation spline is guaranteed to be at that sample.
  • Akima: a cubic scheme with reduces overshoots.
  • Equidistant Polynomial: fit a polynomial function to the samples, only works reasonably well if the samples are equi-spaced.
  • Neville Polynomial: more robust polynomial fitter.
  • Floater-Hormann: for a rational (as opposed to polynomial) function to the samples.
  • Bulirsch-Stoer: an early rational fitter, often yields poles within the interpolation domain where the values on either side go to infinity.

There’s also a Fourier transform, which can be used as an interpolation scheme. It has an interesting feature that it is a cyclical interpolation, meaning the pattern repeats smoothly all along the x-axis. The samples are necessarily equi-spaced with this scheme.

fourier
fourier1410×709 93.6 KB

I also added a Blend Curve interpolation which assumes a constant value before and after the first and last grips. It also supports various interpolation schemes including cosine, smooth, smoother (degree=5) and smoothest (degree=7):

blend
blend1597×625 45.5 KB

5 Likes
9

Nice, looks like lots of thought went into this :slight_smile: Looking forward to that first release of GH2!

10

Is this some kind of new graph editor?

11

Not finished yet, but yes, this is the Graph Mapper in GH2.

2 Likes
12

Add Grip - most excellent. :grinning: