# Interpolation

## Introduction

Interpolation is a commonly used technique in computer graphics. Data is often specified on a regular grid (values are written at the vertex positions of a 2D or 3D grid) or on a line (in the 1D case), but the program needs to evaluate values at random positions on that grid. If the sample is located on a grid vertex, we can simply use the value stored there. However, if the sample is located anywhere else on the grid (somewhere in the cell), and we have no data there, we need to compute a value by averaging the values stored at the cell vertices. This technique is called interpolation because the key idea is to "interpolate" existing values at fixed grid locations to compute values anywhere else on the grid.

In 2D, the technique is called bilinear interpolation. Its 3D counterpart is called trilinear interpolation. Both techniques will be described in the next two chapters, and the source code will be provided as well. The word "linear" is in both terms because, for this particular technique, only linear interpolations are performed. Linear interpolation is an equation of the form:

$$a(1-t)+bt \quad \text{with} \quad 0 \le t \le 1$$

This is very similar to the process of evaluating a linear function. This method is simple and requires only two values (a and b) and a few simple arithmetic operations. Notice that t is in the range 0 to 1. However, as we will show in the next chapter, linear interpolation creates "visual" patterns that are not always acceptable or desirable. It is possible to use interpolation methods of higher degrees that provide smoother results (depending on the context, such results are not always considered better). To achieve such interpolation, it is often necessary to consider more than the four cell corners surrounding a sample point. Therefore, they provide better results but at a higher computation cost because they usually need a larger set of points and use functions of degree two or more. The function used to interpolate the values on the regular grid is called the interpolant.

Interpolation techniques are commonly used in image processing (to resize images, for instance). But 3D techniques can also make use of 3D or 2D grids (textures can be seen as 2D grids) in applications such as fluid simulation, volume rendering, texture mapping, and irradiance caching, to name a few. Wherever grids are involved, interpolation techniques are usually also needed.

-next