# Trilinear 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

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{aligned}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{aligned}}$
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{aligned}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{aligned}}$
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{aligned}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{aligned}}$
Finally one interpolates these values along $z$ (walking through a line):
    $c=c_{0}(1-z_{\text{d}})+c_{1}z_{\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

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}xy+a_{5}xz+a_{6}yz+a_{7}xyz$
where the coefficients are found by solving the linear system
    ${\begin{aligned}{\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{aligned}}$
yielding the result
    ${\begin{aligned}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{aligned}}$