Terrain walking

OpenGL Development JOGL Development
#1

I’ve tried for hours through blood sweat and tears and searched high and low for some tips on how to get terrain walking working correctly, but there’s still a problem in my code.

Ok, so first the background. I’m drawing a heightmap using triangle strips. One ‘quad’ made up of 2 triangles is oriented in the following way (it’s supposed to be square!) with point (0,0,0) at point (p1) :


p2........p4
\         |
|\        |
| \       |
|  \      |
|   \     |
|    \    |
|     \   |
|      \  |
|       \ |
|        \|
p1........p3

With my heightmap stored as an array of bytes containing the height value at that point, I’m using the following code to determine the height by interpolating between the points. It’s a mixture of my own plus some stuff I saw on flipcode ages ago:


    // pass in the heightmap array, plus exact x,z of player
    static final double HeightAtPointTris (byte[] pHeightMap, double xPos, double zPos)
    {
        double retVal = 0.0;
        
        int ixPos = (int)(xPos);
        int izPos = (int)(zPos);
        
        g_p1.x = (int) xPos;
        g_p1.z = (int) zPos;
        
        g_p2.x = (int) xPos+1;
        g_p2.z = (int) zPos;
        
        g_p3.x = (int) xPos;
        g_p3.z = (int) zPos+1;
        
        g_p4.x = (int) xPos+1;
        g_p4.z = (int) zPos+1;
        
        g_p1.y = Height (pHeightMap, (int)g_p1.x, (int)g_p1.z);
        g_p2.y = Height (pHeightMap, (int)g_p2.x, (int)g_p2.z);
        g_p3.y = Height (pHeightMap, (int)g_p3.x, (int)g_p3.z);
        g_p4.y = Height (pHeightMap, (int)g_p4.x, (int)g_p4.z);
        
        // 1 unit here is the length side of 1 quad.
        int quadlength = 1;
        
        double coordX = xPos - ixPos;
        double coordZ = zPos - izPos;
        double h1, h2, h3, yfactor, xfactor;

        if (coordX + coordZ < quadlength)
        {
            // closest to p1 point (upper left triangle)
            h1 = g_p1.y;
            h2 = g_p3.y;
            h3 = g_p2.y;
            yfactor = coordZ * (h2 - h1);
        }
        else
        {
            // closest to p4 point (lower right triangle)
            h1 = g_p3.y;
            h2 = g_p2.y;
            h3 = g_p4.y;
            yfactor = coordZ * (h2 - h3);
        }
        
        double hleft = yfactor + h1;
        double hright = yfactor + h3;
    
        xfactor = coordX * (hright - hleft);
        retVal = xfactor + hleft;
        
        return retVal;
    }

Now this seems to work for the most part. However if I refer you to an image of a 3x3 tile (18 triangle) terrain I’m drawing:

http://vault101.co.uk/screenshots/s051015.jpg

…if you imagine the point closest to the camera (just out of view at the bottom of the screen) as being the origin (0,0,0) and the eight tiles around the center one being points on a compass:


 NW - N - NE
 |    |   |
 W  - C - E
 |    |   |
 SW - S - SE

then when the character runs from the SW tile to the SE tile, he disappears below into the S tile only to reappear at the SE tile.
Also, when the character is running from the NE tile to the NW tile,
he ‘jumps’ in the air as he enters the N tile, and slowly descends until reaching the NW tile’s correct height.

Anyway, go play. Hope someone can make use of the code I’ve posted and suggestions on how to fix would be great! This is doing my head in !

#2

When I am working on similar problems, I take a completely different approach; I see what point the player is moving to, then fire a ray directly down from what will be thier new mid point (center of their boundiing box for example), then determine the intersection with the terrain poly of that ray. Then adjust the players Y by the delta distance from their current Y. As far as I know, that’s the standard way to do it, and it’s never let me down. It sounds a heck of alot simpler then what your trying as well :slight_smile:

#3

ah, i’m close then but I agree - firing a line down through the player’s midpoint and finding the intersection point given the poly’s known points may be easier! (digs out linear algebra and geometry book to look for line intersecting with plane!)

#4

In my engine, every frame I move all the particles by some amount in their respective directions. x and z values are in some way calculated (plane where terrain is), and for y (height) I ask terrain class. Interpolation is pretty smooth, I didn’t have big problems with that. Code for getting Height at some point on terrain is:


       public float getHeightAt(float x, float z) {

        try {
            // get the height of the four corners of the grid the camera is in
            float h00 = heightmap[(int) (x / Constants.MAP_GRID_SCALE)][(int) (z / Constants.MAP_GRID_SCALE)];
            float h01 = heightmap[(int) (x / Constants.MAP_GRID_SCALE)][(int) (z / Constants.MAP_GRID_SCALE) + 1];
            float h10 = heightmap[(int) (x / Constants.MAP_GRID_SCALE) + 1][(int) (z / Constants.MAP_GRID_SCALE)];
            float h11 = heightmap[(int) (x / Constants.MAP_GRID_SCALE) + 1][(int) (z / Constants.MAP_GRID_SCALE) + 1];

            // determine the relative location in the grid (between 0 and 1)
            float modx = (x % Constants.MAP_GRID_SCALE) / Constants.MAP_GRID_SCALE;
            float modz = (z % Constants.MAP_GRID_SCALE) / Constants.MAP_GRID_SCALE;

            // calculate a weighted average for the height
            float avg_height = h00 * (1 - modx) * (1 - modz) + h01 * (1 - modx) * (modz) + h10 * (modx) * (1 - modz) + h11 * (modx) * (modz);

            // scale it and return it
            return avg_height * Constants.HEIGHT_SCALE;
        } catch (Exception e) {
            System.out.println("error while fetcing height()!!!");
            System.out.println("x: " + x + " z:" + z);
            e.printStackTrace();
            return 0;
        }
    }

Maybe your problem is that grid is too big so interpolation isn’t working good? ???

#5

The easiest way is to think the tile is planar. This is incorrect, but is required to do the next step.

Think of the tile (quad) as 1 triangles. both triangles are half of the tile. Now find out which triangle you’re at. Seems you solved this part already.

Now the final part: extrapolate the current triangle to a planar quad. This is fairly easy. Now you have a planar quad, which you can use for 3 interpolation-steps:

  1. T = top Left … x … Right
  2. B = bottom Left … x … Right
  3. P = T … z … B
#6

Thanks Vorax - things are now working perfectly! Your ray/plane intersection suggestion did the trick!

Cheers,
Pete