# Walking on terrain

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

## 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 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 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 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:

0,0------------- 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.

Mark

##### 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).

hth
Jack

##### 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)
3. Plug a, b, c and the position x, z into the plane equation to get y

?

##### 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 vN As D3DVECTOR    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 IfEnd Function

hth
Jack

##### Share on other sites
Hi,

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,
Roquqkie

##### 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;	}	else	{		// 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;	glPushMatrix();		glTranslatef(g_vBall.x, h, g_vBall.z);		glColor3f(0.0f, 1.0f, 0.0f);		auxSolidSphere(0.5f);	glPopMatrix();

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 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 on other sites
don't know if anybody mentioned this, but i always thought
it would be possible to generate a grayscale "heightmap"
of the terrain, and then simply use the pixel values
as "heights".
it might be a retarded idea, but yeah, just thinking. :)

##### Share on other sites
then your guys movement is jerky because there is no transition between the altitudes

##### Share on other sites
i think it'll be easier to interpolate between two values given to you
than to interpolate between randomly placed vertices, dont you think? :)

##### Share on other sites
Quote:
 Original post by fprotoi think it'll be easier to interpolate between two values given to youthan to interpolate between randomly placed vertices, dont you think? :)

Heightmaps generally have the problem of being of discrete size and depth. The depth problem could be fixed using floating-point pixel format on the map, though, but the lack of arbitrary sized domain cannot easily be fixed (if at all).

Furthermore, triangle-ray collision works with any geometry of any size, and doesn't require uniform UV mapping (while a heightmap inherently does).

##### Share on other sites
wow lol. you're so right.
that never occurred to me.
stupid ideas of mine. =)

##### Share on other sites
Quote:
 Original post by fprotowow lol. you're so right.that never occurred to me.stupid ideas of mine. =)

On the contrary, it is always a good idea to spend a healthy amount of time to research alternative solutions to problems. In this particular case, however, my experience on the matter just happens to strongly suggest that the heightmapping is not the most practical solution to the problem at hand.

Kind regards,
-Nik

##### Share on other sites
Now that you mention it, it occurs to me that there's probably something you could do using displacement mapping. You'd probably use it for your terrain in it's entirety, but if you're rendering a character, you bind the map to a texture stage, sample it in the vertex shader to get a height, and add that height to all vertices. That way the hardware does the interpolating for you.

Of course, sampling per-vertex is going to be very wasteful, given that you only really need to do it once per object. OK, ignore me. [grin]

##### Share on other sites
unsigned int nPos = GetVertexIndex(int(floor((kPoint.X() - m_kBigBound.m_kMin.X()) / 7.5f)), int(floor((kPoint.Z() - m_kBigBound.m_kMin.Z()) / 7.5f)), m_uiWidth, m_uiHeight);			float lx = (kPoint.X() - m_akVertex[nPos].X());			float lz = (kPoint.Z() - m_akVertex[nPos].Z());			int	ix = floor(lx);			int	iz = floor(lz);			if (ix < 0) ix = 0;			if (ix > 1) ix = 1;			if (iz < 0) iz = 0;			if (iz > 1) iz = 1;			lx -= ix;			if (lx < 0) lx = 0;			if (lx > 1) lx = 1;						lz -= iz;			if (lx < 0) lz = 0;			if (lz > 1) lz = 1;			nPos = GetVertexIndex(int(0), int(0), m_uiWidth, m_uiHeight);			int cx = floor((kPoint.X() - m_akVertex[nPos].X()) / 7.5f);			int cz = floor((kPoint.Z() - m_akVertex[nPos].Z()) / 7.5f);			nPos = GetVertexIndex(int(cx), int(cz), m_uiWidth, m_uiHeight);			float s00, s01, s10, s11;			nPos = GetVertexIndex(int(cx), int(cz), m_uiWidth, m_uiHeight);			s00 = m_akVertex[nPos].Y();			nPos = GetVertexIndex(int(cx), int(cz + 1), m_uiWidth, m_uiHeight);			s01 = m_akVertex[nPos].Y();			nPos = GetVertexIndex(int(cx + 1), int(cz), m_uiWidth, m_uiHeight);			s10 = m_akVertex[nPos].Y();			nPos = GetVertexIndex(int(cx + 1), int(cz + 1), m_uiWidth, m_uiHeight);			s11 = m_akVertex[nPos].Y();			fHeight = (s00 * (1-lx) + s01 * lx) * (1 - lz) + (s10 * (1-lx) + s11 * lx) * lz;

Just to let you know i got it working with the above code, might help anyone else who's stuck.

##### Share on other sites

I'm walking on sunshine...ohh ohh
I'm walking on sunshine...ohh ohh
And don't it feel good!