Confused about spline interpolation in 3D space

Question

I have to confess that I am really confused about the available code and algorithms for 3D spline interpolation. For my application I need a path: given some point, defined in 3D space, I need to interpolate them using a spline function (cubic, bezier, etc...). Research on the internet did not yield me a solution, only more confusion.

This algorithm caught my attention algorithm. It defines some 3D points (using MATLAB):

[X, Y, Z] = meshgrid(x, y, z);

and then calls the MATLAB interpolation function:

s = exp(-sqrt(X.^2 + Y.^2 + Z.^2));

sinterp = interp3(x, y, z, s, 0., 0., 0.)

What is the function s for!? The interpolation clearly just needs three points and that's all. What is this function for?

Since I m a C++ programmer I was trying to use the following alglib library which comes up with some useful functions. But even there 3 points aren't sufficient, I have to invoke a function that I don't know.

In my application the 3D points are scattered randomly in space as follows picture. My problem doesn't presume that I need a function for joining the points. Even if I do need it, I don't know how to define it.

What is wrong in how I am approaching this problem? Am I using the wrong library functions? or am I supposed to have a function for spline generation? If yes, how to do I get this function?

Regards

Answer 1

Don't get confused. The matlab example you provided has little (or nothing) to do with interpolating lines between points in 3D space. Also s is not a symbolic function but just a 3D Matrix of scalar values.

What this matlab example does is to create 3 3D matrices (X, Y, Z). Each holding the x,y or z components respectively of the points in a 3-D grid, for which the "sample planes" in each dimension where specified by the arrays x, y, z.

Then, the function f=exp(-sqrt(x^2 + y^2 + z^2)) is evaluated for each of those gridpoints and the results are stored in s (another 3D-Matrix). So f is a scalar function, mapping a scalar value to a point in 3D-space and s holds the evaluated results.

Finally, the value for f at the point (0,0,0) is extrapolated from the calculated values for grid points in the neighborhood of (0,0,0).

Unfortunately I can't point you to a proper c++ library that will do what you actually want to achieve, but again: Don't get confused by this example (or any other matlab example), because
A) It is a different problem
B) Matlab's syntax is very different from C's, so it is easy to misinterpret those examples.

Answer 2

A parametric curve has the form X = Fx(t), Y = Fy(t), Z = Fz(t), where t is an independent parameter and the F are three continuous functions. This generalizes to any number of dimensions.

In the case of a Bezier, the F are defined to be the Bernstein polynomials multiplied by the respective coordinates of the control points. For example, a Bezier quadric is

X = P0x (1-t)² + 2 P1x (1 - t)t + P2x t²
Y = P0y (1-t)² + 2 P1y (1 - t)t + P2y t²
Z = P0z (1-t)² + 2 P1z (1 - t)t + P2z t²

In the case of a cubic spline, the F are defined piecewise using Hermite interpolation and computing the derivatives (tangent vectors) in a way that ensures continuity across the pieces.

Actually, curve interpolation in space can be seen as three independent 1D interpolations.

(This is no completely true when there is a dependency between the locations of the data points and the way the independent parameter t is computed.)

Answer 3

interp3() is supposed to do interpolation for volumetric data points (Xi, Yi, Zi, Si), i=1~N. It will generate a function S=f(X, Y, Z). This is the reason why it needs the additional input 's' as noted in your post.

When you encounter an interpolation problem/algorithm, the first thing you need to figure out is what kind of function you are looking for. Namely, whether the function is univariate (y=f(x)), bivariate (z=f(x,y)) or multivariate ( s=f(x, y, z, ....) ). For your particular problem where you want to interpolate a series of 3D points using a spline, basically it is a univariate interpolation problem. However, since a space curve cannot be represented as y=f(x), the spline function will be represented in parametric form as S(t)=(x(t), y(t), z(t)).

There are many ways for doing spline interpolation thru 3D data points. Among them, the two algorithms that are very easy to implement are Catmull Rom spline and Overhauser spline. Both are cubic spline and differ only in how the first derivatives at the data points are estimated. You can google them to find out the details.