Walking on terrain
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?
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
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
I used this some time ago. The function returns the height value from the heightmap for the given position.
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).
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).
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:
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
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
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
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
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
?
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
?
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:
hth
Jack
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
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
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
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.
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.
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.
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;
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement