Jump to content
  • Advertisement
Sign in to follow this  

Walking on terrain

This topic is 4982 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I need some sort of get_height function so i can position my charecter correctly along the terrain surface. Can someone give me the basic math behind the problem while avoiding using any api instructions? I have seen a few discussions about this, what does interpolating mean?

Share this post

Link to post
Share on other sites
Assuming that you're using heightmaps to generate terrain, you need to find the height of the closest vertices (the ones defining the polygon your character supposedly stands on) and "interpolate" the height between them to find the height at the exact location your character is on. At least this is one way to do it, a very basic one. If the height varies a lot from vertex to vertex, it can result in choppy movement and parts of the character "melting" into the terrain. But I guess you'll figure that out for yourself =P
Other methods I guess would be some kind of collision detection. You could also calculate a smoother movement-curve from earlier positions and predicted positions.
It all depends on what you need actually...

Hope this helped clear up your mind a bit =P

Share this post

Link to post
Share on other sites
I used this some time ago. The function returns the height value from the heightmap for the given position.

int GetHeightAt(BYTE *pHeightMap, int x, int y, int mapsize)
// make sure to wrap around, if you exceed
// your heightmap bounds
x = x%mapsize;
y = y%mapsize;

// return index from heightmap
return pHeightMap[x+y*mapsize];

The position (x, y) is the current camera position. You may have to convert/scale your camera values to get it running, but this depends on how you've created your geometry data for the heightmap. The returned value is the y-coordinate of the camera position (here you also may have to scale this value).

Share this post

Link to post
Share on other sites
Interpolating - go and look it up, I can't be arsed to spout out a definition.

There are several possible ways of getting the height at a point. Firstly consider, how your map is actually rendered. Chances are, you're drawing triangle strips between rows of points. so if you have 9 points on your map (for simplicity's sake), your map looks like this from above:

------------- 2,0
------------- 2,2

So you can see, you have 8 triangles.

So one option, is to work out which of the eight triangles the point falls in, then work out the height of that point on the triangle.

BUT, this is quite a complex method of doing it. An easier way, is just to find which square it's in, and use the weighted average of the four heights, based on their distance.

Suppose the point you want to work out the height of, is at 0.8,0.6.

You can find out the height at 0,0.6 by using a weighted average of the height at 0,0 and 0,1. Then you can find out the height at 1,0.6 in the same manner (0,1 and 1,1).

Then find out the weighted average of those two, based on its partial X coordinate.

This method won't give you the height of the point on the triangle, rather the point on a curve of some description which happens to go through the four points. But it's likely to be close enough.

Or something.


Share this post

Link to post
Share on other sites
You want to be careful by just using the weighted average of 4 heights - there are a couple of cases where it can be very wrong and look rubbish. I used this technique as a placeholder in my terrain engine at one point, but replaced it with a mathematically correct technique later on.

Firstly, identify which triangle your point lies in, then use the plane equation ( aX + bY + cZ + d = 0 ) to calculate your missing values.

If you're using DirectX at all, you make your life a bit easier with D3DXPlaneFromPoints( ). This page is the more general mathematics behind it, the first section might well be good enough for you to work out the rest...

Once you have the 4 coefficients (a,b,c,d) then it's a simple case of plugging in the values for the 2 axis' you know, and rearranging for the one you don't know (height).


Share this post

Link to post
Share on other sites
I'm trying to sort this out too.

So far...

I can work out what quad i'm in but haven't cut it down to which triangle in the quad.

Am i correct in thinking i need to:

1. Work out which triangle i'm in
2. Work out the normal of the triangle (gives me a, b, c)
(What about d?)
3. Plug a, b, c and the position x, z into the plane equation to get y


Share this post

Link to post
Share on other sites
To find the specific triangle your point is in, you can use inequalities. It depends on how you create your geometry, but something along the lines of:

Let pX be the percentage (0.0 -> 1.0) along the quads X axis
Let pY be the percentage (0.0 -> 1.0) along the quads Y axis

if( pX + pY == 1.0 )
You are on the center line, just interpolate between corners for height

if( pX + pY < 1.0 )
You're in the top-left triangle

if( pX + pY > 1.0 )
You're in the bottom-right triangle

The rest sounds about right to me. Based on the page I linked to above, your value for 'd' is:

Once you've got those 4 coefficients (and given 'y' is the required variable):

aX + bY + cZ + d = 0
bY = -d - aX - cZ
Y = ( -d - aX - cZ ) / b

Should be all you need to do.

The following function is some code I knocked up in VB6 some years ago (couldn't find a more "modern" example. It's fairly easy to work out whats going on - so might be of some use to this thread:

Public Function FindHeightInQuad(H0 As Single, H1 As Single, H2 As Single, H3 As Single, pX As Single, pY As Single) As Double
'//0. Any variables
Dim D As Double
Const TileSize = LandScale

'//1. Decide which triangle it's in:
If (pX + pY) = 1 Then
'we're on the line
FindHeightInQuad = BLEND(H2, H1, pX) 'BLEND() is just a standard A+T(B-A) operation

ElseIf (pX + pY) < 1 Then
'we're in the top triangle
vN = CalculateNormal(MakeVector(0, H0, 0), MakeVector(TileSize, H1, 0), MakeVector(0, H2, TileSize))
D = -((vN.X * 0) + (vN.Y * H0) + (vN.Z * 0))
FindHeightInQuad = -((vN.X * pX) + (vN.Z * pY) + D) / vN.Y

ElseIf (pX + pY) > 1 Then
'we're in the bottom triangle
vN = CalculateNormal(MakeVector(TileSize, H1, 0), MakeVector(TileSize, H3, TileSize), MakeVector(0, H2, TileSize))
D = -((vN.X * TileSize) + (vN.Y * H1) + (vN.Z * 0))
FindHeightInQuad = -((vN.X * pX) + (vN.Z * pY) + D) / vN.Y

End If

End Function


Share this post

Link to post
Share on other sites

Okay, while I tend to skip reading all the above replies, please bare over with me if this has already been said...

What you need to do is to look up Bilinear interpolation. This is really simple, so I challenge you do read for yourself ;)

Good luck and best regards,

Share this post

Link to post
Share on other sites
Well, I've used what you said in my code below.

Im currently trying to position a ball on my terrain. It works fine with a totally flat terrain but not with a randomly generated (and then smoothed) terrain.

Its picking the correct triangle and the normal is all fine.

Vertex p1, p2, p3;
Vertex d1, d2, normal, middle;
float d;

// Find where we are in the heightmap
int x = floor(g_vBall.x);
int z = floor(g_vBall.z);

// Get the percentage between 0 -> 1
dX = g_vBall.x - g_vHeightmap[x][z].x;
dZ = g_vBall.z - g_vHeightmap[x][z].z;

if (dX + dZ <= 1.0f)
// Top left triangle
p1.x = g_vHeightmap[x][z].x;
p1.y = g_vHeightmap[x][z].y;
p1.z = g_vHeightmap[x][z].z;
p2.x = g_vHeightmap[x+1][z].x;
p2.y = g_vHeightmap[x+1][z].y;
p2.z = g_vHeightmap[x+1][z].z;
p3.x = g_vHeightmap[x][z+1].x;
p3.y = g_vHeightmap[x][z+1].y;
p3.z = g_vHeightmap[x][z+1].z;
// Bottom right triangle
p3.x = g_vHeightmap[x+1][z+1].x;
p3.y = g_vHeightmap[x+1][z+1].y;
p3.z = g_vHeightmap[x+1][z+1].z;
p2.x = g_vHeightmap[x+1][z].x;
p2.y = g_vHeightmap[x+1][z].y;
p2.z = g_vHeightmap[x+1][z].z;
p1.x = g_vHeightmap[x][z+1].x;
p1.y = g_vHeightmap[x][z+1].y;
p1.z = g_vHeightmap[x][z+1].z;

// Calculate normal
d1.x = p1.x - p2.x;
d1.y = p1.y - p2.y;
d1.z = p1.z - p2.z;

d2.x = p3.x - p2.x;
d2.y = p3.y - p2.y;
d2.z = p3.z - p2.z;

normal.x = (d1.y * d2.z) - (d1.z * d2.y);
normal.y = (d1.z * d2.x) - (d1.x * d2.z);
normal.z = (d1.x * d2.y) - (d1.y * d2.x);

float length = sqrt((normal.x * normal.x) + (normal.y * normal.y) + (normal.z * normal.z));
normal.x /= length;
normal.y /= length;
normal.z /= length;

// Middle of our triangle (for drawing the normal)
middle.x = (p1.x + p2.x + p3.x) / 3.0f;
middle.y = (p1.y + p2.y + p3.y) / 3.0f;
middle.z = (p1.z + p2.z + p3.z) / 3.0f;

// D for our plane
d = (normal.x * p1.x) + (normal.y * p1.y) + (normal.z * p1.z);

// Height the ball should be at
float h = -((normal.x * dX) + (normal.z * dZ) + d) / normal.y;

glTranslatef(g_vBall.x, h, g_vBall.z);
glColor3f(0.0f, 1.0f, 0.0f);

Edit: Yes i know i should use a vector class to make it a lot easier, ive got all of my rendering done in another app which has a good vector class but this was a small debug app i whipped up trying to wort out whats wrong.

Share this post

Link to post
Share on other sites
This is what I came up with. I know it worked before I passed off this issue to the collision routines. This was cut from a larger routine, btw.

// Get coordinate of the height sample in top left of square the point is in
fx = floor(x);
fy = floor(y);
dx = (int)fx;
dy = (int)fy;

// Convert to 0.0 - 1.0 range within the height sample square
x -= fx;
y -= fy;

// Look up the four corners of the square the point resides in
tl = Point[x][y].h;
tr = Point[x+1][y].h;
bl = Point[x][y+1].h;
br = Point[x+1][y+1].h;

if (x > y) {

if (x < 0.0001)
return tl;
bl = y / x;
h = tr * (1.0 - bl) + br * bl;
h = tl * (1.0 - x) + h * x;

} else {

if (y < 0.0001)
return tl;
tr = x / y;
h = bl * (1.0 - tr) + br * tr;
h = tl * (1.0 - y) + h * y;


return h;

Share this post

Link to post
Share on other sites
Sign in to follow this  

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!