3D Programming - Weekly : Feet To Terrain

To keep a character's feet on an uneven terrain, you need to know the terrain height under each of the feet. Setting the joint rotations barely takes any computation time compared to some of the other calculations in a 3D engine, so I first animate the character normally, then in another pass adjust the height of the character's feet to the terrain.

This article isn't only for feet to terrain, you can use the terrain height for many other types of collision detection, like keeping a camera from going below the terrain, or bouncing objects off the terrain.

Finding the Terrain Height

I'm assuming the terrain is rendered in triangles from a heightmap( eg. a 2D grayscale texture where each pixel represents height ) so at any location(x,z) there is only one height(y) value. I'll describe how to compute the exact height of the terrain mesh at a location, by finding which triangle it is over, then computing where a vertical line intersects that triangle. If your triangles are small enough( at least when close to the viewpoint,) you could ignore the fact that it's a mesh of triangles without noticing visually that the feet aren't exactly on the terrain, but this usually isn't the case for me.

In the code for the formula:
m_pTerrainMap is an array of unsigned chars in the 0-255 range.
The points TerX and TerY are in terrain map coordinates, and the function assumes they're known to be over the terrain.

float GetTerrainHeight( float TerX, float TerY )
{
// we first get the height of 4 points of the quad underneath the point
int x = int(TerX);
int y = int(TerY);

float TriY[4];
TriY[0] = (m_pTerrainMap[ x + y*m_width ] ) * m_scale.y / 256.0f;
TriY[1] = (m_pTerrainMap[ x+1 + y*m_width ] ) * m_scale.y / 256.0f;
TriY[2] = (m_pTerrainMap[ x + (y+1)*m_width ] ) * m_scale.y / 256.0f;
TriY[3] = (m_pTerrainMap[ x+1 + (y+1)*m_width ] ) * m_scale.y / 256.0f;

// find which of the 2 triangles the point is over (depends on how you render)
// then take the height at a triangle point
// and adjust by the slope down right-angle edges * distance along that edge.

float SqX = TerX - x;
float SqY = TerY - y;
if ( (SqX + SqY) < 1 )
	{
	Height = TriY[0];
	Height += ( TriY[1] - TriY[0] ) * SqX;
	Height += ( TriY[2] - TriY[0] ) * SqY;
	} else {
	Height = TriY[3];
	Height += ( TriY[1] - TriY[3] ) * ( 1.0f - SqY);
	Height += ( TriY[2] - TriY[3] ) * ( 1.0f - SqX);
	}
return Height;
}

Adjusting the Joint Rotations

Once you have the points where the feet need to be, you'll have to adjust the skeleton appropriately, which isn't so simple. In my IK Tutorial I describe the method I use for moving arms and limbs to a certain point. You can adjust the target points up a bit if the thickness of the character model's feet goes beyond the skeleton foot joint. The straightforward implementation of using the feet positions as targets, optionally adjusting the center point to make the hip to heel IK goal lengths average the same as in the unadjusted animation, should look good enough if the terrain below the character isn't steep. If it is really steep there isn't much you can do to stop it from looking funny.

Falling onto the Terrain

Also some characters may fall on the terrain, which means more than just the feet need to be adjusted. A good way to do this is to use 6 points, the center point(hips), one for the shoulders, two feet, and two hands. If more accuracy is needed you could add points, like elbows, knees, and head. As a point goes below terrain height, it's adjusted the terrain height. The details of adjusting the skeleton to all these points are more complex, so perhaps this subject will show up again in a later article.