Editing Trilinear interpolation (section)

==Formulation==
[[Image:Enclosing_points.svg|right|thumb|Eight corner points on a cube surrounding the interpolation point C]]

On a periodic and cubic lattice, let <math>x_\text{d}</math>, <math>y_\text{d}</math>, and <math>z_\text{d}</math> 
be the differences between each of <math>x</math>, <math>y</math>, <math>z</math> and the smaller coordinate related, that is:

:<math>\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}</math>

where <math> x_0 </math> indicates the lattice point below <math> x </math>, and <math> x_1 </math> indicates the lattice point above <math> x </math> and similarly for
<math>y_0, y_1, z_0</math> and <math>z_1</math>.

First one interpolates along <math>x</math> (imagine one is "pushing" the face of the cube defined by <math>C_{0jk}</math> to the opposing face, defined by <math>C_{1jk}</math>), giving:
: <math>\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}</math>

Where <math>c_{000}</math> means the function value of <math> (x_0, y_0, z_0). </math> Then one interpolates these values (along <math>y</math>, "pushing" from <math>C_{i0k}</math> to <math>C_{i1k}</math>), giving:
: <math>\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}</math>

Finally one interpolates these values along <math>z</math> (walking through a line):
:<math>c = c_0(1 - z_\text{d}) + c_1z_\text{d} .</math>
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 <math>x</math>, then along <math>y</math>, and finally along <math>z</math>, produces the same value.

===Algorithm visualization===
[[File:Trilinear_interpolation_visualisation.svg|thumb|A geometric visualisation of trilinear interpolation. The product of the value at the desired point and the entire volume is equal to the sum of the products of the value at each corner and the partial volume diagonally opposite the corner.]]

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 <math>c_{000}</math>, <math>c_{100}</math>, <math>c_{010}</math>, <math>c_{110}</math>, <math>c_{001}</math>, <math>c_{101}</math>, <math>c_{011}</math>, <math>c_{111}</math>.

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

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

In practice, a trilinear interpolation is identical to two [[bilinear interpolation]] combined with a linear interpolation:
:<math>c \approx l\left( b(c_{000}, c_{010}, c_{100}, c_{110}),\, b(c_{001}, c_{011}, c_{101}, c_{111})\right)</math>

===Alternative algorithm===
An alternative way to write the solution to the interpolation problem is
:<math>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</math>

where the coefficients are found by solving the linear system
:<math>\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}</math>

yielding the result

:<math>\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}</math>