trilinear interpolation

{{short description|Method of multivariate interpolation on a 3-dimensional regular grid}}

{{No footnotes|date=October 2024}}

Image:3D_interpolation2.svgs followed by a linear interpolation.]]

Trilinear interpolation is a method of multivariate interpolation on a 3-dimensional regular grid. It approximates the value of a function at an intermediate point (x, y, z) within the local axial rectangular prism linearly, using function data on the lattice points.

Trilinear interpolation is frequently used in numerical analysis, data analysis, and computer graphics.

Related methods

Trilinear interpolation is the extension of linear interpolation, which operates in spaces with dimension D = 1, and bilinear interpolation, which operates with dimension D = 2, to dimension D = 3. These interpolation schemes all use polynomials of order 1, giving an accuracy of order 2, and it requires 2^D = 8 adjacent pre-defined values surrounding the interpolation point. There are several ways to arrive at trilinear interpolation, which is equivalent to 3-dimensional tensor B-spline interpolation of order 1, and the trilinear interpolation operator is also a tensor product of 3 linear interpolation operators.

For an arbitrary, unstructured mesh (as used in finite element analysis), other methods of interpolation must be used; if all the mesh elements are tetrahedra (3D simplices), then barycentric coordinates provide a straightforward procedure.

Formulation

Image:Enclosing_points.svg

On a periodic and cubic lattice, let x_\text{d}, y_\text{d}, and z_\text{d}

be the differences between each of x, y, z and the smaller coordinate related, that is:

:\begin{align}

x_\text{d} = \frac{x - x_0}{x_1 - x_0} \\

y_\text{d} = \frac{y - y_0}{y_1 - y_0} \\

z_\text{d} = \frac{z - z_0}{z_1 - z_0}

\end{align}

where x_0 indicates the lattice point below x , and x_1 indicates the lattice point above x and similarly for

y_0, y_1, z_0 and z_1.

First one interpolates along x (imagine one is "pushing" the face of the cube defined by C_{0jk} to the opposing face, defined by C_{1jk}), giving:

: \begin{align}

c_{00} &= c_{000} (1 - x_\text{d}) + c_{100} x_\text{d} \\

c_{01} &= c_{001} (1 - x_\text{d}) + c_{101} x_\text{d} \\

c_{10} &= c_{010} (1 - x_\text{d}) + c_{110} x_\text{d} \\

c_{11} &= c_{011} (1 - x_\text{d}) + c_{111} x_\text{d}

\end{align}

Where c_{000} means the function value of (x_0, y_0, z_0). Then one interpolates these values (along y, "pushing" from C_{i0k} to C_{i1k}), giving:

: \begin{align}

c_0 &= c_{00}(1 - y_\text{d}) + c_{10}y_\text{d} \\

c_1 &= c_{01}(1 - y_\text{d}) + c_{11}y_\text{d}

\end{align}

Finally one interpolates these values along z (walking through a line):

:c = c_0(1 - z_\text{d}) + c_1z_\text{d} .

This gives us a predicted value for the point.

The result of trilinear interpolation is independent of the order of the interpolation steps along the three axes: any other order, for instance along x, then along y, and finally along z, produces the same value.

=Algorithm visualization=

File:Trilinear_interpolation_visualisation.svg

The above operations can be visualized as follows: First we find the eight corners of a cube that surround our point of interest. These corners have the values c_{000}, c_{100}, c_{010}, c_{110}, c_{001}, c_{101}, c_{011}, c_{111}.

Next, we perform linear interpolation between c_{000} and c_{100} to find c_{00}, c_{001} and c_{101} to find c_{01}, c_{011} and c_{111} to find c_{11}, c_{010} and c_{110} to find c_{10}.

Now we do interpolation between c_{00} and c_{10} to find c_{0}, c_{01} and c_{11} to find c_{1}. Finally, we calculate the value c via linear interpolation of c_{0} and c_{1}

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

:c \approx l\left( b(c_{000}, c_{010}, c_{100}, c_{110}),\, b(c_{001}, c_{011}, c_{101}, c_{111})\right)

=Alternative algorithm=

An alternative way to write the solution to the interpolation problem is

:f(x, y, z) \approx a_0 + a_1 x + a_2 y + a_3 z + a_4 x y + a_5 x z + a_6 y z + a_7 x y z

where the coefficients are found by solving the linear system

:\begin{align}

\begin{bmatrix}

1 & x_0 & y_0 & z_0 & x_0 y_0 & x_0 z_0 & y_0 z_0 & x_0 y_0 z_0 \\

1 & x_1 & y_0 & z_0 & x_1 y_0 & x_1 z_0 & y_0 z_0 & x_1 y_0 z_0 \\

1 & x_0 & y_1 & z_0 & x_0 y_1 & x_0 z_0 & y_1 z_0 & x_0 y_1 z_0 \\

1 & x_1 & y_1 & z_0 & x_1 y_1 & x_1 z_0 & y_1 z_0 & x_1 y_1 z_0 \\

1 & x_0 & y_0 & z_1 & x_0 y_0 & x_0 z_1 & y_0 z_1 & x_0 y_0 z_1 \\

1 & x_1 & y_0 & z_1 & x_1 y_0 & x_1 z_1 & y_0 z_1 & x_1 y_0 z_1 \\

1 & x_0 & y_1 & z_1 & x_0 y_1 & x_0 z_1 & y_1 z_1 & x_0 y_1 z_1 \\

1 & x_1 & y_1 & z_1 & x_1 y_1 & x_1 z_1 & y_1 z_1 & x_1 y_1 z_1

\end{bmatrix}\begin{bmatrix}

a_0 \\ a_1 \\ a_2 \\ a_3 \\ a_4 \\ a_5 \\ a_6 \\ a_7

\end{bmatrix} = \begin{bmatrix}

c_{000} \\ c_{100} \\ c_{010} \\ c_{110} \\ c_{001} \\ c_{101} \\ c_{011} \\ c_{111}

\end{bmatrix},

\end{align}

yielding the result

:\begin{align}

a_0 ={}

&\frac{-c_{000} x_1 y_1 z_1 + c_{001} x_1 y_1 z_0 + c_{010} x_1 y_0 z_1 - c_{011} x_1 y_0 z_0}{(x_0 - x_1) (y_0 - y_1) (z_0 - z_1)} +{} \\

&\frac{ c_{100} x_0 y_1 z_1 - c_{101} x_0 y_1 z_0 - c_{110} x_0 y_0 z_1 + c_{111} x_0 y_0 z_0}{(x_0 - x_1) (y_0 - y_1) (z_0 - z_1)}, \\[4pt]

a_1 ={}

&\frac{ c_{000} y_1 z_1 - c_{001} y_1 z_0 - c_{010} y_0 z_1 + c_{011} y_0 z_0}{(x_0 - x_1) (y_0 - y_1) (z_0 - z_1)} +{} \\

&\frac{-c_{100} y_1 z_1 + c_{101} y_1 z_0 + c_{110} y_0 z_1 - c_{111} y_0 z_0}{(x_0 - x_1) (y_0 - y_1) (z_0 - z_1)}, \\[4pt]

a_2 ={}

&\frac{ c_{000} x_1 z_1 - c_{001} x_1 z_0 - c_{010} x_1 z_1 + c_{011} x_1 z_0}{(x_0 - x_1) (y_0 - y_1) (z_0 - z_1)} +{} \\

&\frac{-c_{100} x_0 z_1 + c_{101} x_0 z_0 + c_{110} x_0 z_1 - c_{111} x_0 z_0}{(x_0 - x_1) (y_0 - y_1) (z_0 - z_1)}, \\[4pt]

a_3 ={}

&\frac{ c_{000} x_1 y_1 - c_{001} x_1 y_1 - c_{010} x_1 y_0 + c_{011} x_1 y_0}{(x_0 - x_1) (y_0 - y_1) (z_0 - z_1)} +{} \\

&\frac{-c_{100} x_0 y_1 + c_{101} x_0 y_1 + c_{110} x_0 y_0 - c_{111} x_0 y_0}{(x_0 - x_1) (y_0 - y_1) (z_0 - z_1)}, \\[4pt]

a_4 ={}

&\frac{-c_{000} z_1 + c_{001} z_0 + c_{010} z_1 - c_{011} z_0 + c_{100} z_1 - c_{101} z_0 - c_{110} z_1 + c_{111} z_0}{(x_0 - x_1) (y_0 - y_1) (z_0 - z_1)}, \\[4pt]

a_5 =

&\frac{-c_{000} y_1 + c_{001} y_1 + c_{010} y_0 - c_{011} y_0 + c_{100} y_1 - c_{101} y_1 - c_{110} y_0 + c_{111} y_0}{(x_0 - x_1) (y_0 - y_1) (z_0 - z_1)}, \\[4pt]

a_6 ={}

&\frac{-c_{000} x_1 + c_{001} x_1 + c_{010} x_1 - c_{011} x_1 + c_{100} x_0 - c_{101} x_0 - c_{110} x_0 + c_{111} x_0}{(x_0 - x_1) (y_0 - y_1) (z_0 - z_1)}, \\[4pt]

a_7 ={}

&\frac{ c_{000} - c_{001} - c_{010} + c_{011} - c_{100} + c_{101} + c_{110} - c_{111}}{(x_0 - x_1) (y_0 - y_1) (z_0 - z_1)}.

\end{align}

See also