Interpolating 3D Coordinates between known missing

Question

The data is a Path in space. I have 3D location data (x,y,z) and the time the location point was recorded.

The x ,y, and z coordinates are the point locations of something traveling through 3D Space. The time values is the time (beginning at 0) that each point was recorded.

x     y    z    time(s)
0.1   2.2  3.3  0
2.4   2.4  4.2  0.3
4.5   2.5  1.8  0.6

I will eventually miss some recording events. (this is known and accepted as true) And the data stream will continue at a different time interval:

x     y    z    time(s)
0.1   2.2  3.3  0
2.4   2.4  4.2  0.3
//missing x,y,z data point at time 0.6
//missing x,y,z data point at time 0.9
4.5   2.5  1.8  1.2
...
...

Please note the data was simplified. My goal is to interpolate the missing 3D points at the known missing times. I have looked into various interpolating techniques but I am not entirely sure which interpolation method is suited for my problem.

1) Can someone succinctly explain the kind of problem this is? My math is extremely rusty and I am not sure how to properly describe it, which leads me to investigating interpolation techniques that may not be properly suited.

2) Update 1 Tricubic Interpolation should not apply here since I am not working with a grid in 3D space. I am working with a trajectory. I have found a Tricubic Interpolation implementation in the Apache math3 commons, however I am not sure if this is what I need. If you look at the arguments it takes, it takes a double[][][] fval matrix that I am not sure about.

3) If not best suited for Java, what is the best tool to interpolate this data?

Update 2 - Question regarding Spectre's solution

In your edit you provide the following tip regarding "matching first derivations of joint points":

let define our t=<-2,+2> and sample the control point like this (does not really matter how it will just affect the coefficients magnitude and including -1,0,1 will ease up the equations a lot):

p(-2) = p0
p(-1) = p1
p( 0) = p2
p( 1) = p3

now let assume we want to interpolate all the points on the interval t=<0,1> so all points between p2 and p3. And we want continuous piecewise curve so first derivations on joint points should match. We got one more control point on the left side so the second derivation can match there too:

p'(0) = 0.5*((p3-p2)+(p2-p1)) = 0.5*(p3-p1)
p'(1) = 0.5*((p4-p3)+(p3-p2)) = 0.5*(p4-p2)
p''(0)= 0.5*(((p2-p1)-(p1-p0))+((p4-p3)-(p3-p2)))
      = 0.5*((p2-2*p1+p0)+(p4-2*p3+p2))
      = 0.5*(p0+p4)-p1+p2-p3

Hope I did not make any silly mistake in the second derivation. Now just substitute p(t) with known control points and form system of equations and compute a0,a1,a2,a3,a4 algebraically from p0,p1,p2,p3,p4.

1) What do you mean by joint points?

2)Where do

p'(0) = 0.5*((p3-p2)+(p2-p1)) = 0.5*(p3-p1)
p'(1) = 0.5*((p4-p3)+(p3-p2)) = 0.5*(p4-p2)

come from? Do they in any way relate to p(0) = p2 and p(1) = p3 ? Can they be anything you chose ?

It can be re written as p'(0) = 0.5*((p(3)-p(0)) + (p(0)-p(-1)) correct? It is not clear to me why this is being done. Or even why it can be done

2b) Similar question for

p''(0)= 0.5*(((p2-p1)-(p1-p0))+((p4-p3)-(p3-p2)))
      = 0.5*((p2-2*p1+p0)+(p4-2*p3+p2))
      = 0.5*(p0+p4)-p1+p2-p3

but I am assuming that clarifying question 2) will alleviate my ambiguity for 2b) because I have no idea where the equation came from either.

What follows is pretty straight forward,then it's just systems of equations

Answer 1

As your data are most likely just some smooth curve sampled points I would use cubic interpolation polynomial like this:

• Piecewise linear integer curve interpolation in C#/Unity3D

Curve properties are such that it goes through all control points (t={-1,0,+1,+2}) and the direction (1st derivation) at inner control points is average of booth sides to join smoothly (similar to Bezier cubics).

The algo is like this:

1. take 2 point before missing point and 2 after

   lets call them p0,p1,p2,p3 they should be ideally time equidistant ones ... and ordered by time.

2. compute 4 coefficients for each axis

   d1=0.5*(p2.x-p0.x);
   d2=0.5*(p3.x-p1.x);
   ax0=p1.x;
   ax1=d1;
   ax2=(3.0*(p2.x-p1.x))-(2.0*d1)-d2;
   ax3=d1+d2+(2.0*(-p2.x+p1.x));
   
   d1=0.5*(p2.y-p0.y);
   d2=0.5*(p3.y-p1.y);
   ay0=p1.y;
   ay1=d1;
   ay2=(3.0*(p2.y-p1.y))-(2.0*d1)-d2;
   ay3=d1+d2+(2.0*(-p2.y+p1.y));
   
   d1=0.5*(p2.z-p0.z);
   d2=0.5*(p3.z-p1.z);
   az0=p1.z;
   az1=d1;
   az2=(3.0*(p2.z-p1.z))-(2.0*d1)-d2;
   az3=d1+d2+(2.0*(-p2.z+p1.z));
   

3. set parameter t=<0,1> to value corresponding to missing time

   so if you chose points p0,p1,p2,p3 with times t0,t1,t2,t3 then the missing time tm corresponds to parameter:

   t = (tm-t1)/(t2-t1);
   

4. compute missing point.

   x=ax0+ax1*t+ax2*t*t+ax3*t*t*t
   y=ay0+ay1*t+ay2*t*t+ay3*t*t*t
   z=az0+az1*t+az2*t*t+az3*t*t*t
   

You can use polynomials of higher order if this is not enough by deriving similar equations or fitting. Also take a look at this:

• How can i produce multi point linear interpolation?

[Edit1] constructing own polynomial

The answer to your comment is in [edit2] of Impact of cubic and catmull splines on image which is also linked in previous link above. To make 4th degree interpolation polynomial in similar manner you will have 5 points (p0,p1,p2,p3,p4) and equations:

p(t)= a0 + a1*t + a2*t*t + a3*t*t*t + a4*t*t*t*t
p'(t) =    a1 + 2*a2*t + 3*a3*t*t + 4*a4*t*t*t
p''(t) =        2*a2   + 6*a3*t   +12*a4*t*t

let define our t=<-2,+2> and sample the control point like this (does not really matter how it will just affect the coefficients magnitude and including -1,0,1 will ease up the equations a lot):

p(-2) = p0
p(-1) = p1
p( 0) = p2
p( 1) = p3
p( 2) = p4

now let assume we want to interpolate all the points on the interval t=<0,1> so all points between p2 and p3. And we want continuous piecewise curve so first derivations on joint points should match. We got one more control point on the left side so the second derivation can match there too:

p'(0) = 0.5*((p3-p2)+(p2-p1)) = 0.5*(p3-p1)
p'(1) = 0.5*((p4-p3)+(p3-p2)) = 0.5*(p4-p2)
p''(0)= 0.5*(((p2-p1)-(p1-p0))+((p4-p3)-(p3-p2)))
      = 0.5*((p2-2*p1+p0)+(p4-2*p3+p2))
      = 0.5*(p0+p4)-p1+p2-p3

Hope I did not make any silly mistake in the second derivation. Now just substitute p(t) with known control points and form system of equations and compute a0,a1,a2,a3,a4 algebraically from p0,p1,p2,p3,p4. Hint use t=0,t=+1 and t=-1 so you will get linear equations for those. For example:

p( 0) = p2 = a0 + a1*0 + a2*0*0 + a3*0*0*0 + a4*0*0*0*0
        p2 = a0

As you can see a0 is computed really simply the same can be used for derivations:

p'(0) = 0.5*(p3-p1)          = a1 + 2*a2*0 + 3*a3*0*0 + 4*a4*0*0*0
p''(0)= 0.5*(p0+p4)-p1+p2-p3 =      2*a2   + 6*a3*0   +12*a4*0*0
-------------------------------------------------------------------
        0.5*(p3-p1)          = a1  
        0.5*(p0+p4)-p1+p2-p3 =      2*a2
-------------------------------------------------------------------
        0.5*(p3-p1)                 = a1  
        0.25*(p0+p4)-0.5*(p1+p2-p3) = a2
-------------------------------------------------------------------

Now use t=+1 and t=-1 and compute the a3,a4. You can set the joint point derivations to meet your specific needs (not just average of derivation from left and right) but to form continuous curve like yours is this the best (from my experience).