Trilinear interpolation

Trilinear interpolation is a method of multivariate interpolation on a 3-dimensional regular grid. It approximates the value of an intermediate point $\left(x, y, z\right)$ within the local axial rectangular prism linearly, using data on the lattice points. 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.

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

Compared to linear and bilinear interpolation

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$. The order of accuracy is 1 for all these interpolation schemes, and it requires $\left(1 + n\right)^D = 8$ adjacent pre-defined values surrounding the interpolation point. There are several ways to arrive at trilinear interpolation, it 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

Method

On a periodic and cubic lattice with spacing 1, let $x_d$, $y_d$, and $z_d$ be the differences between each of $x$, $y$, $z$ and the smaller coordinate related, that is:

:$x_d = x - lfloor x floor$:$y_d = y - lfloor y floor$:$z_d = z - lfloor z floor$

First we interpolate along $z$(imagine we are pushing the front face of the cube to the back), giving:

:$i_1 = v \left[lfloor x floor,lfloor y floor, lfloor z floor\right] imes \left(1 - z_d\right) + v \left[lfloor x floor, lfloor y floor, lceil z ceil\right] imes z_d$:$i_2 = v \left[lfloor x floor,lceil y ceil, lfloor z floor\right] imes \left(1 - z_d\right) + v \left[lfloor x floor, lceil y ceil, lceil z ceil\right] imes z_d$:$j_1 = v \left[lceil x ceil,lfloor y floor, lfloor z floor\right] imes \left(1 - z_d\right) + v \left[lceil x ceil, lfloor y floor, lceil z ceil\right] imes z_d$:$j_2 = v \left[lceil x ceil,lceil y ceil, lfloor z floor\right] imes \left(1 - z_d\right) + v \left[lceil x ceil, lceil y ceil, lceil z ceil\right] imes z_d.$

Then we interpolate these values (along $y$, as we were pushing the top edge to the bottom), giving:

:$w_1 = i_1\left(1 - y_d\right) + i_2y_d$:$w_2 = j_1\left(1 - y_d\right) + j_2y_d$

Finally we interpolate these values along $x$(walking through a line):

:$IV = w_1\left(1 - x_d\right) + w_2x_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.

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 C000, C100, C010, C110, C001, C101, C011, C111.

Next, we perform linear interpolation between C000 and C100 to find C00, C001 and C101 to find C01, C011 and C111 to find C11, C010 and C110 to find C10.

Now we do interpolation between C00 and C10 to find C0, C01 and C11 to find C1. Finally, we calculate the value C via linear interpolation of C0 and C1

ee also

* Linear interpolation
* Bilinear interpolation
* Tricubic interpolation

* [http://www.grc.nasa.gov/WWW/winddocs/utilities/b4wind_guide/trilinear.html pseudo-code]
*Paul Bourke, [http://local.wasp.uwa.edu.au/~pbourke/other/interpolation/index.html Interpolation methods] , 1999. Contains a section on trilinear interpolation.

Wikimedia Foundation. 2010.

Look at other dictionaries:

• Trilinear filtering — is an extension of the bilinear texture filtering method, which also performs linear interpolation between mipmaps.Bilinear filtering has several weaknesses that make it an unattractive choice in many cases: using it on a full detail texture when …   Wikipedia

• Interpolation — In the mathematical subfield of numerical analysis, interpolation is a method of constructing new data points within the range of a discrete set of known data points. In engineering and science one often has a number of data points, as obtained… …   Wikipedia

• Bilinear interpolation — In mathematics, bilinear interpolation is an extension of linear interpolation for interpolating functions of two variables on a regular grid. The key idea is to perform linear interpolation first in one direction, and then again in the other… …   Wikipedia

• Linear interpolation — is a method of curve fitting using linear polynomials. It is heavily employed in mathematics (particularly numerical analysis), and numerous applications including computer graphics. It is a simple form of interpolation. Lerp is a quasi acronym… …   Wikipedia

• Multivariate interpolation — In numerical analysis, multivariate interpolation or spatial interpolation is interpolation on functions of more than one variable. The function to be interpolated is known at given points and the interpolation problem consist of yielding values… …   Wikipedia

• Tricubic interpolation — In the mathematical subfield numerical analysis, tricubic interpolation is a method for obtaining values at arbitrary points in 3D space of a function defined on a regular grid. The approach involves approximating the function locally by an… …   Wikipedia

• Collocation (remote sensing) — Collocation is a procedure used in remote sensing to match measurements from two or more different instruments. This is done for two main reasons: for validation purposes when comparing measurements of the same variable, and to relate… …   Wikipedia

• Mipmap — In 3D computer graphics texture filtering, MIP maps (also mipmaps) are pre calculated, optimized collections of images that accompany a main texture, intended to increase rendering speed and reduce aliasing artifacts. They are widely used in 3D… …   Wikipedia

• List of mathematics articles (T) — NOTOC T T duality T group T group (mathematics) T integration T norm T norm fuzzy logics T schema T square (fractal) T symmetry T table T theory T.C. Mits T1 space Table of bases Table of Clebsch Gordan coefficients Table of divisors Table of Lie …   Wikipedia

• List of numerical analysis topics — This is a list of numerical analysis topics, by Wikipedia page. Contents 1 General 2 Error 3 Elementary and special functions 4 Numerical linear algebra …   Wikipedia