In the following I will present a method for deforming three dimensional geometry using a technique relying on radial basis functions (RBFs). These are mathematical functions that take a real number as input argument and return a real number. RBFs can be used for creating a smooth interpolation between values known only at a discrete set of positions. The term radial is used because the input argument given is typically computed as the distance between a fixed position in 3D space and another position at which we would like to evaluate a certain quantity.

The tutorial will give a short introduction to the linear algebra involved. However the source code contains a working implementation of the technique which may be used as a black box. First an example of what we achieve in the end:

Source code with Visual Studio 2005 solution can be found here. The code should also compile on other platforms.

Interpolation by radial basis functions

Assume that the value of a scalar valued function is known in distinct discrete points   in three dimensional space. Then RBFs provide a means for creating a smooth interpolation function of in the whole domain of . This function is written as a sum of evaluations of a radial basis function where is the distance between the point to be evaluated and :

 Here are scalar coefficients and the last four terms constitute a first degree polynomial with coefficients to . These terms describe an affine transformation which cannot be realised by the radial basis functions alone. From the known function values we can assemble a system of linear equations:  
 where , and is an matrix :

 Here . A number of choices for will result in a unique solution of the system. In this tutorial we use the shifted log function:

Interpolating displacements

How can RBF's be used for deforming geometry? Well assume that the deformation is known for  3D positions  and that this information is represented by a vector describing 3D displacement of the geometry that was positioned at in the original, undeformed state. You can think of the positions as control points that have been moved to positions . The RBF interpolation method can now be used for interpolating these displacements to other positions. 

Using the notation  and   three linear systems are set up as above letting the displacements be the quantity we called in the previous section:

where is assembled as described above. Solving for , , and involves a single matrix inversion and three matrix-vector multiplications and gives us the coefficients for interpolating displacements in all three directions by the expression

The source code

In the source code accompanying this tutorial you will find the class RBFInterpolator which has an interface like this:

class RBFInterpolator
{
public:
	RBFInterpolator();
	~RBFInterpolator();
 
	//create an interpolation function f that obeys F_i = f(x_i, y_i, z_i)
	RBFInterpolator(vector x, vector y, vector z, vector F);
 
	//specify new function values F_i while keeping the same
	void UpdateFunctionValues(vector F);
 
	//evaluate the interpolation function f at the 3D position (x,y,z)
	real interpolate(float x, float y, float z);
 
private:
            ...
};

This class implements the interpolation method described above using the newmat matrix library. It is quite easy to use: just fill stl::vectors with the , and components of the positions where the value is known and another stl::vector with the values. Then pass these vectors to the RBFInterpolator constructor, and it will be ready to interpolate. The value at any position is then evaluated by calling the 'interpolate' function. If some of the values change at any time, the interpolator can be quickly updated using the 'UpdateFunctionValues' method.

We want to deform a triangle surface mesh. These are stored in a class TriangleMesh, and loaded from OBJ files.
In the source code the allocation of stl::vectors discribing the control points and the initialisation of RBFInterpolators looks like this:

void loadMeshAndSetupControlPoints()
{
	// open an OBJ file to deform
	string sourceOBJ = "test_dragon.obj";
	undeformedMesh = new TriangleMesh(sourceOBJ);
	deformedMesh = new TriangleMesh(sourceOBJ);
 
	// we want 11 control points which we place at different vertex positions
	const int numControlPoints = 11;
 
	const int verticesPerControlPoint = ((int)undeformedMesh->getParticles().size())/numControlPoints;
 
	for (int i = 0; i<numControlPoints; i++)
	{
		Vector3 pos = undeformedMesh->getParticles()[i*verticesPerControlPoint].getPos();
		controlPointPosX.push_back(pos[0]);
		controlPointPosY.push_back(pos[1]);
		controlPointPosZ.push_back(pos[2]);
	}
 
	// allocate vectors for storing displacements
	for (unsigned int i = 0; i<controlPointPosX.size();  i++)
	{
		controlPointDisplacementX.push_back(0.0f);
		controlPointDisplacementY.push_back(0.0f);
		controlPointDisplacementZ.push_back(0.0f);
	}
 
	// initialize interpolation functions
	rbfX = RBFInterpolator(controlPointPosX, controlPointPosY, 
                                           controlPointPosZ, controlPointDisplacementX );
	rbfY = RBFInterpolator(controlPointPosX, controlPointPosY, 
                                           controlPointPosZ, controlPointDisplacementY );
	rbfZ = RBFInterpolator(controlPointPosX, controlPointPosY, 
                                           controlPointPosZ, controlPointDisplacementZ );
}

Now all displacements are set to zero vectors - not terribly exciting! To make it a bit more fun we can vary the displacements with time:

	// move control points
	for (unsigned int i = 0; i<controlPointPosX.size(); i++ )
	{
		controlPointDisplacementX[i] = displacementMagnitude*cosf(time+i*timeOffset);
		controlPointDisplacementY[i] = displacementMagnitude*sinf(2.0f*(time+i*timeOffset));
		controlPointDisplacementZ[i] = displacementMagnitude*sinf(4.0f*(time+i*timeOffset));
	}
 
	// update the control points based on the new control point positions
	rbfX.UpdateFunctionValues(controlPointDisplacementX);
	rbfY.UpdateFunctionValues(controlPointDisplacementY);
	rbfZ.UpdateFunctionValues(controlPointDisplacementZ);
 
	// deform the object to render
	deformObject(deformedMesh, undeformedMesh);

Here the function 'deformObject' looks like this:

// Code for deforming the mesh 'initialObject' based on the current interpolation functions (global variables). 
// The deformed vertex positions will be stored in the mesh 'res'
// The triangle connectivity is assumed to be already correct in 'res'  
void deformObject(TriangleMesh* res, TriangleMesh* initialObject)
{
	for (unsigned int i = 0; i < res->getParticles().size(); i++)
	{
		Vector3 oldpos = initialObject->getParticles()[i].getPos();
 
		Vector3 newpos;
		newpos[0] = oldpos[0] + rbfX.interpolate(oldpos[0], oldpos[1], oldpos[2]);
		newpos[1] = oldpos[1] + rbfY.interpolate(oldpos[0], oldpos[1], oldpos[2]);
		newpos[2] = oldpos[2] + rbfZ.interpolate(oldpos[0], oldpos[1], oldpos[2]);
 
		res->getParticles()[i].setPos(newpos);
	}
}

That's it!!! Now I encourage you to download the source code and play with it. Perhaps you can experiment with other radial basis functions? Or make the dragon crawl like a caterpillar? If you code something interesting based on this tutorial send a link to me and we will link to it from this page

Karsten Noe

I got a mail from Woo Won Kim from Yonsei University in South Korea who has made a head modeling program that can generate 3D human heads from two pictures of the person using code from this RBF tutorial. Check out a video of this here.

Tags: deformation, free form deformation, Geometry deformation, radial basis function, Source Code & Tutorials, triangle mesh, tutorial