Heightmap Physics Optimization/Improvement

Andrew Rasmussen
  • Heightmap Physics Optimization/Improvement Andrew Rasmussen

    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. Heightmap

    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)

  • 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.

opengl c++ collision-detection physics heightmap
Related questions and answers
  • ->texCoordY); glVertex3f(pos[0], pos[1], pos[2]); } } glEnd(); What I'd like to do is to calculate all positions before hand, store them in a Vertex array and then draw... at the same time: glBegin(GL_TRIANGLES); for(int i = 0; i < numTriangles; i++) { MD2Triangle* triangle = triangles + i; for(int j = 0; j < 3; j++) { MD2Vertex* v1....... Maybe I'm doing something extra here? I managed to implement a std::vector collection like recommended: for(int i = 0; i < numTriangles; i++) { MD2Triangle* triangle = triangles + i

  • a problem with smoothness. If I reduce my physics updates to 25 per second which I have only done as an experiment then it is a bit jerky. But the game easily runs at higher rates than that so there may... my game working at the moment without interpolation. It does physics updates using fixed step time deltas. The frame display rate is decoupled from this. So, it might be doing 40 Physics updates per... are examples of actual calculated interpolation value i.e. the proportion of the physics update that is complete at the time the frame is being drawn. I am going to have to change the draw code to draw

  • well... I'm building the animation system of my game engine (the skeletal and skinned animation stuff), and I came to a point where I added so much functionality in the frame and node structures... shader in every node. Other option I was thinking was making some helper functions to deal with the simpler cases, which would set some default parameters and would ask only the most basic ones... animation I would end up storing a lot of data that I don't really need, even if I'm indexing node and frame data when saving and then store the hierarchy with the indices to the actual data. I don't

  • physics properties. I know there will be errors here as I get the items colliding with the ground but not with each other properly. So I would appreciate some input on what I am doing wrong. void... - Y * W))); TEuler.setZ(atan2f(2.0f * (X * Y + Z * W), XSquared - YSquared - ZSquared + WSquared)); TEuler *= RADTODEG; } I seem to have issues with the cubes not colliding with each other... code shows the changes I made to get accurate physics. void GameState::createScene() { m_pSceneMgr->createLight("Light")->setPosition(75,75,75); // Physics // As a test we want a floor plane

  • , Enemy, Powerup are NOT game classes. An entity is only defined by the components it owns (and that can change during time). So the player Airship starts with Sprite, Position, Health and Input... remove_component(C* c) { components.at<C>() = 0; } void serialize(filestream, op) { /* Serialize all componets*/ } ... }; std::list<Entity*> entity_list; With this design I can get #1... components and that would require searching each other component's list at each step. Which approch do you think is better? is boost::fusion map suited to be used in that way?

  • I have two components I'd like to connect them to each other. PhysicalComponent containing rigid body(position, rotation, velocity) and is holding body from physics engine. GraphicsComponent onscreen representation(position too, rotation too). I'd like to sync this components, how to do it? Read position, and rotation in GraphicsComonent from Physical comopnent. Add one more component that sync them. But problem is that I want to change on screen representation (other class such as PositionInerpolator do it, and it can work only with GraphicsComponent), and it must change physical

  • I'm creating a component-based game object system. Some tips: GameObject is simply a list of Components. There are GameSubsystems. For example, rendering, physics etc. Each GameSubsystem contains... coupling. A. We can add new GameSubsystem. For example, let's add GameSubsystemTitles that registers all ComponentTitle and guarantees that every title is unique and provides interface to quering objects..., GameSubsystemParticleEmmiter can be merged into GameSubsystemSpatial (to place all audio, emmiter, render Components in the same hierarchy and use parent-relative transforms). con. Every-to-every check. Very

  • component associated with it). No problem until this point. For this function I want to use a scientifically tested, accurate N-body simulation algorithm (like this). It's my field so I already know how to do that. The challenge is how to make the game activate the function efficiently. This is what I've thought of so far: The algorithm can calculate a lot of time steps in a short time, so I could activate it in one loop, save the trajectory data, and go on for several game loops using that data. During this time the spacecraft's position is updated every loop, but the algorithm is sleeping. When

  • Hey so I'm making a pong game with SFML and in the process made a function that takes a Time, Speed, Angle of movement, buffer for the movement on the X axis, and buffer for the movement on the Y axis. I then implemented this function into my custom mySprite class, more specifically into it's update() function which updates its Position using the above function to calculate its new position...); CalculateMove(frameTime,velocity,angle,X,Y); Move(X,-Y); }; void Accelerate(float PPS){velocity+=PPS;}; void Turn(float degrees){ angle=(float)((angle+degrees)-(int)(angle

Data information