Bilinear interpolation for height approximation

I've been playing around some with 3D graphics on Android using the awesome libgdx library. Its more or less a platform independent OpenGL wrapper with some nice extra features, for example an .obj file loader. Its so nice to build and test in an x86 environment, and not have to use the terribly slow Android emulator.

So, I needed some way to get my models to move smoothly over my terrain. This is something I guess most 3D programmers have encountered, and there are many ways to do this. It comes down to a tradeoff between speed and accuracy, and really smooth height tracing is not inexpensive, especially if you have many objects moving around.

Normally the problem is that you have a low-res heightmap, typically one pixel per world unit. So we need to calculate the height if we for example are at (x,z) (17.3f, 33.8f), that is, somewhere between the coordinates (17,33), (18, 33), (17, 34) and (18,34), for which we have height information.

For my case I chose the popular and fairly calculation-inexpensive bilinear interpolation. It comes down to letting the 4 corners with known height form a plane, and approximating the value somewhere on this plane by analyzing one dimension at a time. Here is the code.

private dobule getHeightAtPos(Vector3 pos) {

// bilinear interpolation

float fract_x = pos.x - (int) pos.x; // decimal position in x

float fract_z = pos.z - (int) pos.z; // decimal position in y

// create a map with the four known heights we are somewhere in between, as follows

// (o is our position between the points):

// ...........z

// ...........|

// (1,1) (1,0)|

// ......o....|

// (0,1) (0,0)|

// x ----------

float h_00 = heightmap.get((int)pos.x, (int)pos.z);

float h_10 = heightmap.get((int)pos.x, (int)Math.ceil(pos.z));

float h_01 = heightmap.get((int)Math.ceil(pos.x), (int)pos.z);

float h_11 = heightmap.get((int)Math.ceil(pos.x), (int)Math.ceil(pos.z));

// Creates two parallell heightlines along x at the sides of the square which corresponds to the plane slope.

// Then calculate the height at our position between the points

float proj_x_near = h_00 + (h_01 - h_00)*fract_x; // the point on the line along x on lower z side

float proj_x_far = h_10 + (h_11 - h_10)*fract_x; // the point on the line along x on higher z side

// Now draw a heightline crossing the two points calculated above and find the height for our z position

// The resulting height is the approximate height we were looking for

float cross = proj_x_near + (proj_x_far - proj_x_near)*fract_z;

return heightMapToWorldScale(cross);