Blog

Jun 3

Written by:
Friday, June 03, 2011 

Scattered Interpolation is a very useful mathematical method, but it is not widely known among game developers. Once you understand it, it can solve many problems. Creating smooth height fields from random points or smoothly interpolating animations are only two examples. It is definitely worth to dig through a bit of mathematics to add a handy new tool to your toolbox. This tool is also readily available in the DigitalRune Mathematics library.

In this post we are going to look at an example. In future blog posts, we will look at other examples and explain Scattered Interpolation with all the scary mathematics.

Definition

A scattered interpolation method provides a function

y = f(x)

that takes an m-dimensional input vector x and computes an n-dimensional output vector y. y is computed by interpolation of k reference data pairs:

(x₁, y₁), (x₂, y₂), …, (x_k, y_k).

Reference data is not given at regular grid positions. Thus, the interpolation is called “scattered”.

Scattered Interpolation in DigitalRune Mathematics

In DigitalRune Mathematics Scattered Interpolation is available through the class RadialBasisRegressionF (and related classes, see Online Documentation and the examples that come with DigitalRune Mathematics).

Example 1 – Creating a smooth height field from random points

Let’s jump right to an example to translate the abstract definition to a useful example: Suppose we have k points in 3D space and we want to use this input data to create a height field. The height field should be smooth and all points should lie on the surface of the height field.

Here is an example image:

 

The black dots are the random input points.

Now we need to formulate this problem as Scattered Interpolation problem as described above:

• We have k input points p₁, p₂, …, p_k.
• Each point p_i is a 3D vector (x_i, y_i, z_i).
• In this example, the grid is defined in the xy plane and the z values define the heights of the height field.
• What we are really looking for is a method z = f(x, y) that computes a z (height) value for any given (x, y) position on the height field grid.
• Scattered Interpolation provides us with a method y = f(x). In this case y = (z) and x = (x, y).
• Each random point p_i provides one reference data pair (x_i, y_i) with x = (x_i, y_i) and y = (z_i).

After a bit of variable and symbol juggling we can see that scattered interpolation provides a method to compute smooth height values by interpolating a few given random reference points. This can be used in a terrain editor. The user can start with a flat height field and change the height of a few points. Scattered Interpolation computes a smooth height field. Scattered interpolation also allows to control the influence of the points: Points can have only local influence (creating a narrow mountain) or a wider influence (creating a wider mountain).

And this is only one application of scattered interpolation. In the next blog articles, we will show how scattered interpolation can be used to solve animation problems and we will discuss how scattered interpolation works.