CODEWITHSUNDEEP
algorithmmath3dlinear-interpolation
user1855952
user1855952

Reputation: 1575

Trilinear interpolation

So I'm trying to write a trilinear interpolation function but am having some trouble coming up with it.

So first we have a 1D interpolation:

float interpolate1D(float v1, float v2, float x){
    return v1*(1-x) + v2*x;
}

And then 2D interpolation:

float interpolate2D(float v1, float v2, float v3, float v4, float x, float y){

    float s = interpolate1D(v1, v2, x);
    float t = interpolate1D(v3, v4, x);
    return interpolate1D(s, t, y);
}

But then things get tricky once it gets to 3D. I can't quite figure out how to implement a 3D interpolator using the 2D interpolation function. I don't know why I'm having this mental bock since it should just be a straightforward extension but I guess all of the different variables at play are throwing me off. So I've started off a function below but it's incomplete and I need help finishing it.

float interpolate3D(v1, v2, v3, v4, v5, v6, v7, v8, float x, float y, float z){


     float s = interpolate2D(v1, v2, v3, v4, x, y);
     float t = interpolate2D(v5, v6, v7, v7, x, z);

     //What do I do next?
}

Upvotes: 8

Views: 14507

Answers (3)

DG44
DG44

Reputation: 7

A very good source to understand the trilinear interpolation can be found at: https://en.wikipedia.org/wiki/Trilinear_interpolation

It mentions the following:

In practice, a trilinear interpolation is identical to two bilinear interpolation combined with a linear interpolation:

C = linear(bilinear(C_(000),C_(010),C_(100),C_(110)),
           bilinear(C_(001),C_(011),C_(101),C_(111)))

Upvotes: -1

Tomasz Gandor
Tomasz Gandor

Reputation: 8823

You have 2 problems with your code - v7 appears twice.

Let me spell it out for you:

float interpolate3D(v1, v2, v3, v4, v5, v6, v7, v8, float x, float y, float z)
{
    float s = interpolate2D(v1, v2, v3, v4, x, y);
    float t = interpolate2D(v5, v6, v7, v8, x, y);
    return interpolate1D(s, t, z);
}

Compare this to interpolate2D():

  • interpolate twice by the "lower dimension" (1D for 2D, 2D for 1D), using the same variables (x for 1D, (x, y) for 2D)
  • interpolate the intermediate results 1D, using the remaining variable (y for 2D, z for 3D)

Also note - we don't know how you place your v1 through v8. But if you do it correctly, this function will work.

Upvotes: 7

Sneftel
Sneftel

Reputation: 41454

Linear interpolation does not operate on faces (not every hypercube has faces). It operates on vertices, in pairs.

You can think of nD interpolation as having two parts:

  1. A series of 1D interpolations on pairs of input vertices.
  2. (n-1)D interpolation on the interpolated values from the first part.

2D interpolation, for instance, is 1D interpolation on the 2 pairs of input vertices, followed by 1D interpolation on the 2 results. 3D interpolation is 1D interpolation on the 4 pairs of input vertices, followed by 2D interpolation on the 4 results. 4D interpolation is 1D interpolation on the 8 pairs of input vertices, followed by 3D interpolation on the 8 results.

Basically, the first part reduces the interpolation problem from nD to an equivalent (n-1)D interpolation problem; the second part performs that interpolation.

Upvotes: 2

Related Questions