1

I would like to interpolate a 3D scalar function f(x, y, z). I have coded up a 3D linear interpolation algorithm (http://en.wikipedia.org/wiki/Trilinear_interpolation). This was not so bad.

However, I would like something more sophisticated, e.g. 3D cubic splines. Are there any open source, easy-to-use, publicly available code for interpolating a 3D scalar? I would prefer to use C, but Fortran would be OK as well. I would like to stay away from Matlab.

I have seen similar questions asked here:

Interpolating a scalar field in a 3D space

and

What are some good libraries for 3D interpolation?

The second one was OK with Matlab, which I am not.

As for the first one, the main suggestion was Shepard's method. I am curious how accurate Shepard's method is. For instance, in the case of a uniform grid, one can apply Shepard's method only to nearby grid points, and in that case does it tend to be more accurate than linear interpolation or cubic splines? I imagine not, but wasn't 100% sure, and if in fact it is not better, then I would prefer to find code using something like splines if any such codes are available.

Community
  • 1
  • 1
db1234
  • 797
  • 2
  • 11
  • 28

3 Answers3

5

Take a look at Geometric Tools for Interpolation: templated C++ for tricubic, uniform B-splines, and much more.
(einspline, a C library for B-splines in 1d 2d 3d, seems to be dormant in 2013; the author doesn't answer emails. Also, it's C; C++ templates would reduce code bloat for interpolating floats, colors, vecs ...) I haven't used either of these.

On Inverse distance weighting a.k.a. Shepard's method, you can take any number of neighbors: in 3d, 2^3 or 3^3 or 4^3 ...
A general problem is "sagging" — see the plot in the link.

"Accuracy" of any interpolation method is really hard to measure: what's "golden", for what class of data / what noise ?
And you have two measures, error at the data and smoothness, to trade off — for photo enlargement three:
aliasing, blurring and edge halos. There's some theory on spline interpolation of band-limited functions, but afaik none at all for IDW.

Added: What about the bullseye effect ?

IDW is a terrible choice in almost every case. It assumes that all of your input data points are local minimums or maximums!

Well, IDW can have peaks above nearby data points, if there are high peaks far away. For example in 1d,
IDW( [0 0] [1 0] [2 y] ) = y/7 at x = 1/2. But IDW weights ~ 1 / distance may be too spiky, fall off too fast, for some tasks.
Interpolation methods and kernels have to be chosen to fit specific data and noise — an art.

Community
  • 1
  • 1
denis
  • 21,378
  • 10
  • 65
  • 88
  • +1. I'd add a reference to the classic paper on the subject, by Franke. Its a bit long, at least if you have the version with all of the plots. For that, I once had it on microfiche, but who has a fiche reader these days? http://www.ams.org/journals/mcom/1982-38-157/S0025-5718-1982-0637296-4/ –  Jun 01 '13 at 13:36
  • @woodchips, good link -- cf. matplotlib/delaunay/testfuncs.py. Would you know of a summary of interpolation methods, metrics, test functions since then (1982) ? – denis Jun 01 '13 at 14:46
  • Thanks for the einspline suggestion, I will certainly look into that. And, thanks for the words of wisdom about interpolation in general and the issues with IDW. – db1234 Jun 01 '13 at 14:47
2

The bspline-fortran library does 2d-6d b-spline interpolation for data on a regular grid. It is written in modern Fortran (there is a basic subroutine interface and also an object-oriented interface).

Time Laird
  • 169
  • 1
  • 3
  • Yes Bspline is great! In fact, just heard about it and used it a few months ago, well over a year after I posted this question, lol. This question does seem to need an update, many links in the answer by @denis don't seem to work. Would also be good to know tools for C/C++ to do 3D interpolation. – db1234 Jul 18 '15 at 13:42
0

vspline is a FOSS C++ template library for b-spline processing. It's dimension-agnostic, so you can use it for 3D data. It's focus is on efficiently processing large raster data sets with multithreaded SIMD code. If you're concerned about precision, it can use long doubles for calculations and has extremely precise precomputed constants for maximum fidelity.

Kay F. Jahnke
  • 371
  • 2
  • 7