Heightmap Physics Optimization/Improvement

Question

I'm working on implementing the physics surrounding a player walking on a heightmap. A heightmap is a grid of points which are evenly spaced on the x and z axes, with varying heights. The physical representation of my player (what is exposed to my physics engine/manager) is simply a point-mass where his feet are, rather than complicating the problem by treating him as a sphere or a box.

This image should help further explain heightmaps and show how triangles are generated from the points. This picture would be looking straight down on a heightmap, and each intersection would be a vertex that has some height.

Feel free to move this over to math, physics, or stack overflow, but I'm pretty sure this is where it belongs as it is a programming question related to games.

Here's my current algorithm:

1. Calculate the player's velocity from input/gravity/previous velocity/etc
2. Move the player's position (nextPos = prevPos + velocity * timeSinceLastFrame)
3. Figure out which triangle (all graphics is done in triangles!) of my heightmap the player's new position is vertically aligned with
4. Use the three vertices of that triangle to calculate the equation for the plane which that triangle lies in
5. Plug in the player's x and z coordinates into the plane's equation to get the y coordinate for the player's position on that plane
6. Set the y coordinate of the player's position to this (if newPos.y < y)

This is all fine and dandy, but I'm wondering if there's anything that I can optimize. For example, my first thought is to store the plane's equation with the triangle's vertex information. This way all I have to do is plug in the x and z values to the equation to get the y. However, this would require adding 4 floats to every vertex of the heightmap which is a little ridiculous memory wise. Also, my heightmaps are dynamic (meaning the heights will change at runtime), which would mean changing the plane equations every time a vertex's height changes.

Is there a faster way to calculate that point than digging up the plane's equation and then plugging in x and z? Should I store the plane equations and update them on vertex height change or should I just regenerate the plane equations for every triangle every time the player moves on that triangle? Is there a better way to do heightmap physics that maintains this simplicity? (this seems very simple to me as far as physics engines go)

Answer 1

It's easy to improve on the height computation. For simplicity I will consider that the size of a square is 1; you can always get back to this case by switching coordinates:

                x A
  ^ z         ,'|
  |         ,'  |
  |       ,'    | M'
  |     ,'  M   x
  |   ,'   x    |
  | ,'          |
  x'------------x-----> x
 B               C

Let M have coordinates (x,z). First, project M onto the AC edge along BM. The coordinates of M' are (1,z/x). Linear interpolation gives the height of M' as yM' = yC + (z/x)(yA-yC). Finally, the height of M is yM = yB + x(yM' - yB). Or:

yM = yB + x(yC-yB) + z(yA-yC)

Also, I see several problems with what you are doing.

• nextPos = prevPos + velocity * timeSinceLastFrame is most certainly wrong, you should be integrating velocity over the whole elapsed frame rather than using only the current velocity value. Averaging the new velocity with the previous frame’s velocity is almost always a better approximation, and is even the right thing to do in the case of constant acceleration (such as gravity), because it exactly simulates newtonian mechanics.

• the kind of heightmap triangulation will probably give rendering artifacts because triangle subdivisions are always in the same direction; one way to compensate for this is to switch the direction of the diagonal every odd and even cell. Another solution is to use a regular hexagonal/triangular mesh rather than a square pattern.

• you do not seem to be taking the vertical component of the player velocity into account; the walking distance varies with elevation variations, so if the triangle you land on has a different slope than the one you left, you may end with an error in the linear momentum. Actually this is best illustrated by your clamping of the y value: when doing this, you're modifying the energy of the player, without compensating elsewhere. One solution for this would be to perform your physics step several times per frame in order to compensate as soon as possible for the slope variation.