• Advertisement

navigation on terrain

This topic is 3453 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

hello can anyone tell me how do i navigate on my terrain. i am able to move forward/back/left/right by increasing the x/z values, but what i want is if there is an elevation or a hill, i should be able to go up on the hill and come down.. how do i go abt it?? is it possible to do it using camera position??

Share this post

Share on other sites
Advertisement
One method is to project forward a distance (dx), then project a ray downward and do an intersection test against the world polygons.

so the start of your test ray would be something like (x + dx, y - dy, z) projected straight down.

Share this post

Share on other sites
thanks for your response...

but i am a beginner in this so i am not able to understand clearly what you have mentioned..

can u be a little elaborate or give me some good tutorial suggestions/source code??

Share this post

Share on other sites
Hi,

a relatively easy method to figure out a point on the surface of your terrain would be to use a method called bilinear interpolation, or bilerping for short.

There are quite a few threads already on this board concerning this method but I will post some code that I use which works nicely.

float BilinearInterpolation(float iX, float iZ){	float temp[4];		//store the 4 heights next to our position	temp[0] = GetHeight((int)iX, (int)iZ);	temp[1] = GetHeight((int)(iX + 1), (int)iZ);	temp[2] = GetHeight((int)(iX + 1), (int)(iZ + 1));	temp[3] = GetHeight((int)iX, (int)(iZ + 1));		float x, z;	x = floor(iX); // get the lower x for height	z = floor(iZ); // get the lower z for height	//now for the interpolation	float tx = iX - x;	float tz = iZ - z;	float txtz = tx * tz;	//bilinear interpolation to get the current height above the surface	return ((temp[0] * (1 - tz - tx + txtz)) + (temp[1] * (tx - txtz)) + (temp[2] * txtz) + (temp[3] * (tz - txtz)));}

What happens here is you have an x, and a z coordinate (assuming you are using a right handed coordinate system) which is your player's (camera's) position along the horizontal axis.

In order to find the height (y) of the player (camera) we sample heights from the closest four vertices surrounding the camera and interpolate between them to get a y value. This is assuming that you are using a heightmap for your terrain, or something similar where you have access to height values of points at any given x,z.

The code I posed was based on some code that I found in a thread somewhere on the forum. Can't remember who/where so I give credit to this person indirectly. :)

If you seek more info just search the gamedev forum for "bilinear interpolation terrain" or something and you'll get tons of results. ;)

Enjoy...
--Jonathan Janevski

Share this post

Share on other sites
[EDIT] jjanevski posted at the same time and his code looks real (whereas mine is off the top of my head). I'd go with his version of it ;)

If your terrain is generated from a height-map, then you can determine the correct height by sampling the height-map.

E.g. you have a 128*128 8-bit greyscale height-map. You use this to generate a triangle-mesh with the horizontal (x/z) extents of (-500,-500) to (500,500) and a vertical (y) scale of 0 to 100.

Given an x/z coordinate, you can find the y coordinate by:

1) Converting from world-space to "height-map-space"
float pixX = (wrldX + 500)/1000.0 * 128.0;
float pixZ = (wrldZ + 500)/1000.0 * 128.0;

2) Taking a weighted average from the height-map's pixels
struct sample {  unsigned char rawByte;  float weight;}sample samples[4];int wholeX = (int)pixX;int wholeZ = (int)pixZ;float fracX = pixX - wholeX;float fracZ = pixZ - wholeZ;samples[0].rawByte = heightMap.getAt( wholeX, WholeZ );samples[0].weight = sqrt( fracX*fracX + fracY*fracY );samples[1].rawByte = heightMap.getAt( wholeX+1, WholeZ );samples[1].weight = sqrt( (1-fracX)*(1-fracX) + fracY*fracY );samples[2].rawByte = heightMap.getAt( wholeX, WholeZ+1 );samples[2].weight = sqrt( fracX*fracX + (1-fracY)*(1-fracY));samples[3].rawByte = heightMap.getAt( wholeX+1, WholeZ+1 );samples[3].weight = sqrt( 1-fracX)*(1-fracX) + (1-fracY)*(1-fracY));float rawY = 0;float weightSum = 0;for( int i=0; i<4; ++i ){  rawY += samples[i].rawByte * samples[i].weight;  weightSum += samples[i].weight;}rawY /= weightSum;
3) Convert the weighted height-map sample into world-space:
float y = rawY/255.0f * 100;

Share this post

Share on other sites
when we navigate on terrain, is it the camera navigating??
so if we have to move over a slope we need to move the camera over the slope, is it??

when we navigate using the keys we change the x/z values but if there is a slope how do we calculate the height over which the camera has to navigate??

hope u understood my point...

Share this post

Share on other sites
The x and z coordinates of the camera position is given, so you need to adjust the y coordinate (height) of the camera so that the camera stands on top of the terrain.
You need to define a function (look at above posts), to return the height of a point on the terrain, given the point's x,z coordinates (x and z coordinates of the camera).

As a next step you can add an offset value, so that camera doesn't sit exactly on the ground of the terrain:

CamPos.y = pTerrain->GetHeight(CamPos.x, CamPos.z) + offsetHeight;

[Edited by - Hiyar on July 31, 2008 7:14:05 AM]

Share this post

Share on other sites
Quote:
 Original post by HiyarThe x and z coordinates of the camera position is given, so you need to adjust the y coordinate (height) of the camera so that the camera stands on top of the terrain.

the x and z coordinates of the camera are the x/z values which change when we navigate the keys,right??

Quote:
 You need to define a function (look at above posts), to return the height of a point on the terrain, given the point's x,z coordinates (x and z coordinates of the camera).

i am using a 2d array for the heightmap,so the y value will be the value at the array[x][z]..but x/z in this case is float value..so??

regards

Share this post

Share on other sites
Quote:
 Original post by vpki am using a 2d array for the heightmap,so the y value will be the value at the array[x][z]..but x/z in this case is float value..so??
So instead of reading a single value from the 2d array, you read 4 values and take a weighted average.

Instead of doing this:
float x = ..., z = ...;float y = array[int(x)][int(z)];
Do something like this:
float y1 = array[int(x)  ][int(z)  ];float y2 = array[int(x)+1][int(z)  ];float y3 = array[int(x)  ][int(z)+1];float y4 = array[int(x)+1][int(z)+1];float y = y1*w1 + y2*w2 + y3*w3 + y4*w4;

The code that jjanevski and I posted earlier shows how to perform a weighted average using bilinear filtering (i.e. it will show you how to do the above example properly).

Share this post

Share on other sites
Quote:
 Original post by HodgmanThe code that jjanevski and I posted earlier shows how to perform a weighted average using bilinear filtering (i.e. it will show you how to do the above example properly).

but in the code posted by you

int wholeX = (int)pixX;
int wholeZ = (int)pixZ;
float fracX = pixX - wholeX;
float fracZ = pixZ - wholeZ;

what is pixX and pixZ?? is it the x and z values at that point???

Share this post

Share on other sites
Quote:
 Original post by vpkwhat is pixX and pixZ?? is it the x and z values at that point???

Your height-map is probably a different size to your terrain in the world. For example, your height-map might be 128x128 pixels (e.g. char array[128][128]), but you might draw the terrain as being 1000x1000 units.

I don't know if this is the case or not (you haven't told us how you are drawing your terrain), so I'm just guessing ;)

If you tell us how you are creating the terrain mesh from the height-map, then I can give you a more accurate answer ;)
Also, how is the height-map being stored? Is it an array of char's, short's, int's, float's?

If your height-map *is* a different size to your terrain, then you need to convert from terrain coordinates (world-space) into height-map coordinates (image/pixel-space).

Let's say for example that your height-map is 128x128, but you are drawing the terrain from (0,0) to (1000,1000).
In this case, an x/z position of (0,0) relates to array[0][0] in the height-map. An x/z position of (1000,1000) relates to array[127][127]. an x/z position of (500,500) relates to array[64][64], etc...

So in my previous code example, "pixX" and "pixZ" represent array coordinates for the height-map, and "wrldX" and "wrldZ" represent the original (camera) terrain coordinates.

Share this post

Share on other sites
Quote:
 Original post by vpkthe x and z coordinates of the camera are the x/z values which change when we navigate the keys,right??

Yes that's right, when you update the x/z values of the camera, you need to adjust the height of the camera.
Quote:
 Original post by vpki am using a 2d array for the heightmap,so the y value will be the value at the array[x][z]..but x/z in this case is float value..so??

The function GetHeight(float x, float z) in my example doesn't return the y value of a terrain vertex, the function should return the height at any given point.Click

PS: offsetHeigth is the heigth of the player.

[Edited by - Hiyar on August 1, 2008 4:23:55 AM]

Share this post

Share on other sites
Quote:
 Original post by HodgmanIf you tell us how you are creating the terrain mesh from the height-map, then I can give you a more accurate answer ;)Also, how is the height-map being stored? Is it an array of char's, short's, int's, float's?

this is how i am creating the terrain mesh
BYTE HeightMap[1024][1024];
fread(HeightMap,1,MapWidth * MapHeight,File);//MapWidth and Height is 1024

Quote:
 So in my previous code example, "pixX" and "pixZ" represent array coordinates for the height-map, and "wrldX" and "wrldZ" represent the original (camera) terrain coordinates.

if i am not wrong in the code posted by you there is no "wrldx and wrldy"..i think pixX represent the original (camera) terrain coordinates..

[Edited by - vpk on August 4, 2008 12:43:09 AM]

Share this post

Share on other sites
no response to my early post yet

Share this post

Share on other sites
Quote:
Original post by vpk
Quote:
 Original post by HodgmanSo in my previous code example, "pixX" and "pixZ" represent array coordinates for the height-map, and "wrldX" and "wrldZ" represent the original (camera) terrain coordinates.
if i am not wrong in the code posted by you there is no "wrldx and wrldy"..i think "pixX represent the original (camera) terrain coordinates..

No... wrldX is in world coordinates (the camera's position in the world). pixX is in pixel coordinates (the camera's position in the height-map array).

Quote:
 Original post by Hodgman1) Converting from world-space to "height-map-space"float pixX = (wrldX + 500)/1000.0 * 128.0;float pixZ = (wrldZ + 500)/1000.0 * 128.0; ^ ^ ^ | | Height array size | Terrain draw size Terrain draw offset

Share this post

Share on other sites
Quote:
 Original post by HodgmanYour height-map is probably a different size to your terrain in the world. For example, your height-map might be 128x128 pixels (e.g. char array[128][128]), but you might draw the terrain as being 1000x1000 units.I don't know if this is the case or not (you haven't told us how you are drawing your terrain), so I'm just guessing ;)If you tell us how you are creating the terrain mesh from the height-map, then I can give you a more accurate answer ;)Also, how is the height-map being stored? Is it an array of char's, short's, int's, float's?

Maybe I can explain it better if you tell us how you are currently drawing your terrain...

Share this post

Share on other sites
Quote:
 Original post by HodgmanMaybe I can explain it better if you tell us how you are currently drawing your terrain...

below is the code for reading the heightmap file and display:

void LoadHeightMap (char* Filename, int Width, int Height) {FILE * File;File = fopen( Filename, "rb" );fread(HeightMap,1,MapWidth * MapHeight,File);fclose( File );}void DisplayHeightMap(void){	int Height;	index=glGenLists(1);	glNewList(index, GL_COMPILE);	for (mapX = 1; mapX < MapWidth; mapX +=4)	{ 		for (mapZ = 1; mapZ < MapHeight*3; mapZ+=4)		{ 			numtri++;			glBegin(GL_TRIANGLE_STRIP);			Height = HeightMap[mapX][mapZ];			glTexCoord2f(0,0);			glVertex3f(float(mapX),Height,float(mapZ));		    			Height = HeightMap[mapX][mapZ+4];			glTexCoord2f(0,1);			glVertex3f(float(mapX),Height,float(mapZ+4));			Height = HeightMap[mapX+4][mapZ];			glTexCoord2f(1,0);			glVertex3f(float(mapX+4),Height,float(mapZ));			Height = HeightMap[mapX+4][mapZ+4];			glTexCoord2f(1,1);			glVertex3f(float(mapX+4),Height,float(mapZ+4));			glEnd();		}	}	//glEnd();	glEndList();}

hope u will be able to help me..

regards

Share this post

Share on other sites
hi

i have posted the code, awaiting your reply

Share this post

Share on other sites
Quote:
 Original post by HodgmanIf your height-map *is* a different size to your terrain, then you need to convert from terrain coordinates (world-space) into height-map coordinates (image/pixel-space).Let's say for example that your height-map is 128x128, but you are drawing the terrain from (0,0) to (1000,1000).In this case, an x/z position of (0,0) relates to array[0][0] in the height-map. An x/z position of (1000,1000) relates to array[127][127]. an x/z position of (500,500) relates to array[64][64], etc...

hope u have gone thru the code i had posted earlier, but i havent recd any reply from u..

my heightmap array is of size [1024][1024], but how do i know my terrain size ie what units i am drawing my terrain??

Share this post

Share on other sites
Quote:
 Original post by vpkmy heightmap array is of size [1024][1024], but how do i know my terrain size ie what units i am drawing my terrain??
The size of your terrain is determined by the values that you pass into the glVertex3f function. You seem to be starting your terrain at x/z of (1,1) and ending at (1025,3073)??

Quote:
 Original post by vpkbelow is the code for reading the heightmap file and display:*** Source Snippet Removed ***

* You start your counters at 1, instead of 0, which means you're missing the first pixels.
* You are incrementing your counters by 4, instead of by 1, which means you are only reading 1 out of every 4 pixels (i.e. you skip 3 pixels each iteration).
* You seem to be reading past the bounds of the array
** - your limit for mapX is 'MapWidth' instead of 'MapWidth-incrementSize'
** - your limit for mapZ is 'MapHeight*3' instead of 'MapHeight-incrementSize'

Here's an edited version of your function. I've surrounded my changes with /**/ markers so you can see what I've done:
void DisplayHeightMap(void){	/**/float xzScale = 5.0f;/**/	/**/float yScale = 1.0f;/**/	int Height;	index=glGenLists(1);	glNewList(index, GL_COMPILE);	for (mapX = /**/0/**/; mapX < /**/MapWidth-1/**/; mapX +=/**/1/**/)	{ 		for (mapZ = /**/0/**/; mapZ < /**/MapHeight-1/**/; mapZ+=/**/1/**/)		{ 			numtri++;			glBegin(GL_TRIANGLE_STRIP);			Height = HeightMap[mapX][mapZ];			glTexCoord2f(0,0);			/**/glVertex3f(mapX*xzScale,Height*yScale,mapZ*xzScale);/**/		    			Height = HeightMap[mapX][mapZ+/**/1/**/];			glTexCoord2f(0,1);			/**/glVertex3f(mapX*xzScale,Height*yScale,mapZ*xzScale+xzScale);/**/			Height = HeightMap[mapX+/**/1/**/][mapZ];			glTexCoord2f(1,0);			/**/glVertex3f(mapX*xzScale+xzScale,Height*yScale,mapZ*xzScale);/**/			Height = HeightMap[mapX+/**/1/**/][mapZ+/**/1/**/];			glTexCoord2f(1,1);			/**/glVertex3f(mapX*xzScale+xzScale,Height*yScale,mapZ*xzScale+xzScale);/**/			glEnd();		}	}	//glEnd();	glEndList();}

The new variable xzScale determines the ratio between terrain size and the pixels in your array. A value of 5 means that each pixel in the height-map array covers 5 'units' in world-space.
The new variable yScale just lets you change how tall the terrain is vertically.

Share this post

Share on other sites
So now that we know the size of your terrain, we can use jjanevski's code from earlier.

float xzScale = 5.0f;float yScale = 1.0f;int MapWidth = ...;int MapHeight = ...;int* HeightMap = new int[MapWidth][MapHeight];float GetTerrainHeightFromWorldPosition( float x, float z ){	x = x / xzScale;	z = z / xzScale;	if( x < 0 || x >= MapWidth || z < 0 || z >= MapHeight )	{	//error - outside the array!		return 0;	}	float heightValue = BilinearInterpolation( x, z );	return heightValue * yScale;}float BilinearInterpolation(float iX, float iZ){	if( (int)iX+1 >= MapWidth || (int)iZ+1 >= MapHeight )		return HeightMap[(int)iX][(int)iZ];	float temp[4];		//store the 4 heights next to our position	temp[0] = HeightMap[(int) iX     ][(int) iZ     ];	temp[1] = HeightMap[(int)(iX + 1)][(int) iZ     ];	temp[2] = HeightMap[(int)(iX + 1)][(int)(iZ + 1)];	temp[3] = HeightMap[(int) iX     ][(int)(iZ + 1)];		float x, z;	x = floor(iX); // get the lower x for height	z = floor(iZ); // get the lower z for height	//now for the interpolation	float tx = iX - x;	float tz = iZ - z;	float txtz = tx * tz;	//bilinear interpolation to get the current height above the surface	return ((temp[0] * (1 - tz - tx + txtz)) + (temp[1] * (tx - txtz)) + (temp[2] * txtz) + (temp[3] * (tz - txtz)));}

Share this post

Share on other sites
thanks for your help

but i tried changing my code according to yours, but now the look of my terrain has completely changed..it doesnt look like a terrain at all :(

Share this post

Share on other sites
also i am using a RAW file for heightmap which is of size 1024kb, how do i find out if it is 128*128 or 1024*1024 bit grey scale?

Share this post

Share on other sites
Quote:
 Original post by vpki tried changing my code according to yours, but now the look of my terrain has completely changed..it doesnt look like a terrain at all :(
What is the data-type of the HeightMap array?
Does the height-map file contain colour channels that should be ignored, or does it only contain the height channel?

Quote:
 Original post by vpkalso i am using a RAW file for heightmap which is of size 1024kb, how do i find out if it is 128*128 or 1024*1024 bit grey scale?

It could be 512*512@32bpp or 1024*1024@8bpp or even 256*1024@32bpp, or even 256*256@64bpp!!!

Then even if you assume that it's 512*512@32bpp, it could be one 32bit channel, or two 16 bit channels, or four 8 bit channels...

The only way to find out is to open it in Photoshop (etc...) with different settings until it looks correct - or to ask the person who created the file.

Where did you get the image file from?

[Edited by - Hodgman on August 5, 2008 1:02:14 AM]

Share this post

Share on other sites
Quote:
 Original post by vpki tried changing my code according to yours, but now the look of my terrain has completely changed..it doesnt look like a terrain at all :(
Ahh, ok...
I thought that this was an error in your code:
Quote:
 Original post by Hodgman* You are incrementing your counters by 4, instead of by 1, which means you are only reading 1 out of every 4 pixels (i.e. you skip 3 pixels each iteration).
But it was probably intentional! If your input image has 4 channels (RGBA) then by skipping ahead by 4 (instead of by 1) then you're only reading one of the channels.

The modifications that I suggested will be incorrectly reading all of the channels.

If this is the case, then your RAW file is probably 512x512 pixels.

Here is another version that restores your original increment value of 4.
float xzScale = 5.0f;float yScale = 1.0f;void DisplayHeightMap(void){	int Height;	index=glGenLists(1);	glNewList(index, GL_COMPILE);	for (mapX = 0; mapX < MapWidth-4; mapX +=4)	{ 		for (mapZ = 0; mapZ < MapHeight-4; mapZ+=4)		{ 			numtri++;			glBegin(GL_TRIANGLE_STRIP);			Height = HeightMap[mapX][mapZ];			glTexCoord2f(0,0);			glVertex3f(mapX*xzScale/4.0f,Height*yScale,mapZ*xzScale/4.0f);		    			Height = HeightMap[mapX][mapZ+4];			glTexCoord2f(0,1);			glVertex3f(mapX*xzScale/4.0f,Height*yScale,mapZ*xzScale/4.0f+xzScale);			Height = HeightMap[mapX+4][mapZ];			glTexCoord2f(1,0);			glVertex3f(mapX*xzScale/4.0f+xzScale,Height*yScale,mapZ*xzScale/4.0f);			Height = HeightMap[mapX+4][mapZ+4];			glTexCoord2f(1,1);			glVertex3f(mapX*xzScale/4.0f+xzScale,Height*yScale,mapZ*xzScale/4.0f+xzScale);			glEnd();		}	}	//glEnd();	glEndList();}

Share this post

Share on other sites

• Advertisement