terrain collision

iv'e added a heightmap terrain, but no matter how i go about it, I cant get the camera to collide/stay on top of the terrain....any thoughts?
terrain code:

Code:

const char heightmapFilename[] = "Terrains/heightmap.raw";

const float MAX_HEIGHT = 30.0f;
const float SCALE_FACTOR = 256.0f / MAX_HEIGHT;

void DrawTerrain()
{
	glActiveTextureARB		= (PFNGLACTIVETEXTUREARBPROC)		wglGetProcAddress("glActiveTextureARB");
	glMultiTexCoord2fARB	= (PFNGLMULTITEXCOORD2FARBPROC)		wglGetProcAddress("glMultiTexCoord2fARB");

	FILE *pFile = fopen(heightmapFilename, "rb");
	
	fread(&heightmap, TERRAIN_SIZE * TERRAIN_SIZE, 1, pFile);
	fclose(pFile);
	
	
	for (int z = 0; z < TERRAIN_SIZE - 1; ++z)
	{
		glActiveTextureARB(GL_TEXTURE0_ARB);
		glEnable(GL_TEXTURE_2D);
		glBindTexture(GL_TEXTURE_2D,  g_Texture[14]);
		glActiveTextureARB(GL_TEXTURE1_ARB);
		glEnable(GL_TEXTURE_2D);
		glBindTexture(GL_TEXTURE_2D,  g_Texture[0]);
		glActiveTextureARB(GL_TEXTURE2_ARB);
		glEnable(GL_TEXTURE_2D);
		glBindTexture(GL_TEXTURE_2D,  g_Texture[0]);
		glBegin(GL_TRIANGLE_STRIP);
		for (int x = 0; x < TERRAIN_SIZE; ++x)
		{
			// render two vertices of the strip at once
			float scaledHeight = heightmap[z * TERRAIN_SIZE + x] / SCALE_FACTOR;
			float nextScaledHeight = heightmap[(z + 1)* TERRAIN_SIZE + x] / SCALE_FACTOR;
			float color = 0.5f + 0.5f * scaledHeight / MAX_HEIGHT;
			float nextColor = 0.5f + 0.5f * nextScaledHeight / MAX_HEIGHT;
			
			//glColor3f(color, color, color);
			glTexCoord2f((GLfloat)x/TERRAIN_SIZE*8, (GLfloat)z/TERRAIN_SIZE*8);
			glVertex3f(static_cast<GLfloat>(x - TERRAIN_SIZE/2), scaledHeight - 5, static_cast<GLfloat>(z - TERRAIN_SIZE/2));
			
			//glColor3f(nextColor, nextColor, nextColor);
			glTexCoord2f((GLfloat)x/TERRAIN_SIZE*8, (GLfloat)(z+1)/TERRAIN_SIZE*8);
			glVertex3f(static_cast<GLfloat>(x - TERRAIN_SIZE/2), nextScaledHeight - 5, static_cast<GLfloat>(z + 1 - TERRAIN_SIZE/2));	
		}
		glEnd();
	}
	
	glActiveTextureARB(GL_TEXTURE0_ARB);
	glEnable(GL_TEXTURE_2D);
	glBindTexture(GL_TEXTURE_2D,  g_Texture[11]);
	glActiveTextureARB(GL_TEXTURE1_ARB);
	glEnable(GL_TEXTURE_2D);
	glBindTexture(GL_TEXTURE_2D,  g_Texture[0]);
	glActiveTextureARB(GL_TEXTURE2_ARB);
	glEnable(GL_TEXTURE_2D);
	glBindTexture(GL_TEXTURE_2D,  g_Texture[0]);
	glBegin(GL_QUADS);
	glTexCoord2f(-40.0, 0.0);glVertex3f(-200, 0, 200);
	glTexCoord2f(-40.0, 40.0);glVertex3f(-200, 0, -200);
	glTexCoord2f(40.0, 40.0);glVertex3f(200, 0, -200);
	glTexCoord2f(40.0, 0.0);glVertex3f(200, 0, 200);
	glEnd();
}

all help will be much appreciated..
-psychopath

Bilinear interpolation.

Given 4 height values h1 through h4 and 2 floats fx and fy to represent how far into the 'cell' we are in:

h1*****h2
*............*
*............*
*............*
h3*****h4

float heightx=h1+fx*(h2-h1)
float heighty=h3+fx*(h4-h3);
float finalheight=heightx+fy*(heighty-heightx);

This can be done very fast in assembly.

Code:

...
fld	  [h2]
fsub	[h1]
fmul	[fx]
fadd	[h1]
fstp	[heightx]
 
fld	  [h4]
fsub	[h3]
fmul	[fx]
fadd	[h3]
 
fsub	[heightx]
fmul	[fy]
;result in ST(0) - return float back to C
fadd	[heightx]
...

But you must also figure out which triangle you are in. I leave that to you. If you have any more problems I will post the entire function that will accurately compute camera height given any terrain coordinate.

i don't get it :P
my assumption was that you would test the camera view Y (g_Camera.m_vView.y) against scaledHeight and/or nextScaledHeight, ex:
if(g_Camera.m_vView.y < scaledHeight)
{
g_Camera.m_vView.y = scaledHeight + 0.6;
}
i made this assumption because from what I gather the terrain gets its height values from scaledHeight and nextScaledHeight

-psychopath

Well the premise is this. Take the problem in one dimension - say X. Let's say our line starts at x=0. It ends at x=20. We have calculated that we currently reside 70% of the way between x=0 and x=20 or 0 and 20. What is the value on the number line at .7 between 0 and 20?

value=0+.7*(20-0)
value=0+.7*(20)
value=0+14
value=14

The value is 14.

Ok a 2D representation is not what we need for a terrain, but it is close to what we need. Essentially you do two linear interpolations, one for x, and one for y. You are basically drawing a straight line from the upper left corner of the cell or terrain quad you are in to the point where you are.

Let's say your cell unit size is 20x20. Our world coordinates are 400,y,200. Notice that I'm using x and z to displace our position in 2D. The third value, height, is the y value which is what we need to find.

So the problem boils down to this: what is the height of the terrain at world coordinates 400,200?

First we need to find what cell we are in before we can begin to index into the heightmap to figure out the four corners of the cell we are in so that we can do the bilinear interpolation.

To compute cell coords from world coords we simply divide both coords by their respective cell sizes. Since we chose a size of 20x20 we divide our world coords by 20 in both dimensions. I use the same size for x as z since it does not make sense to have terrain grids that are EDIT: not squares.

int cellx=(int)(world.x/cellsize.x);
int celly=(int)(world.y/cellsize.y);

Now we need to find the four corners of our square. This is simple. Since we know we are at cellx, celly we can simply use that as the upper left corner.

cellx,celly.......................cellx+1,celly
.................................................. ......
.................................................. ......
cellx,celly+1...............cellx+1,celly+1

However note that there is a huge problem here. While we know that we are exactly at cellx,celly in this case, but this will not always be true. It is possible to be some distance into cellx,celly but still be inside the cell. This is where the bilinear interpolants come into play.
In our example the height at HeightMap[cellx,celly] will do, but in most cases this will not work. We need a formula to find the height at some arbitrary distance into the cell in question, taking into account the height values at the corners of the cell. Bilinear interpolation will do this.

To illustrate here is a picture I've created. If it only serves to confuse I will post the entire code snippet here for you, but it is important that you understand what is taking place. This will allow you to do a lot of things in your terrain engine. It will allow you to have objects move over the contour of the terrain based on the slope of the current cell and many other cool effects, not to mention the least of which is relatively inexpensive ground collision testing.

Here is a sample of the math involved to find the grid or cell coords from the world coords. Also I have put samples of the results you would get using different cell sizes. F1 and F2 are simply the normalized distance between H1 and H2 and H3 and H4. There are several ways to compute this. I've only shown one and it is not the fastest. I chose to superimpose this over one of my terrain engine screenshots (tiled). The engine uses bilinear interpolation to figure out the height of the camera at any point in the terrain.

Good stuff

hmmm....interesting but it's gonna take me a while to digest it. I'll post if i figure it out (or if i don't )

-psychopath

ok....Iv'e looked at what you posted, and tried to figure it out, without much luck...I did however look at the heightmap tutorial on gametutorials.com, and applied their collision code to mine, but its not working:

Geometry.cpp (snippet):

Code:

const char heightmapFilename[] = "Terrains\\heightmap.raw";

const float MAX_HEIGHT = 30.0f;
const float SCALE_FACTOR = 256.0f / MAX_HEIGHT;

int Height(BYTE *pHeightMap, int X, int Y)
{
	// Make sure we don't go past our array size
	int x = X % TERRAIN_SIZE;					// Error check our x value
	int y = Y % TERRAIN_SIZE;					// Error check our y value

	if(!pHeightMap) return 0;				// Make sure our data is valid

	// Use the equation: index = (x + (y * arrayWidth) ) to find the current height
	return pHeightMap[x + (y * TERRAIN_SIZE)];	// Index into our height array and return the height
}

void DrawTerrain(int DrawWater)
{
	glActiveTextureARB		= (PFNGLACTIVETEXTUREARBPROC)		wglGetProcAddress("glActiveTextureARB");
	glMultiTexCoord2fARB	= (PFNGLMULTITEXCOORD2FARBPROC)		wglGetProcAddress("glMultiTexCoord2fARB");
	
	FILE *pFile = fopen(heightmapFilename, "rb");
	
	fread(&heightmap, TERRAIN_SIZE * TERRAIN_SIZE, 1, pFile);
	fclose(pFile);
	
	for (int z = 0; z < TERRAIN_SIZE - 1; ++z)
	{
		glActiveTextureARB(GL_TEXTURE0_ARB);
		glEnable(GL_TEXTURE_2D);
		glBindTexture(GL_TEXTURE_2D,  g_Texture[14]);
		glActiveTextureARB(GL_TEXTURE1_ARB);
		glEnable(GL_TEXTURE_2D);
		glBindTexture(GL_TEXTURE_2D,  g_Texture[2]);
		glActiveTextureARB(GL_TEXTURE2_ARB);
		glEnable(GL_TEXTURE_2D);
		glBindTexture(GL_TEXTURE_2D,  g_Texture[0]);
		glBegin(GL_TRIANGLE_STRIP);
		for (int x = 0; x < TERRAIN_SIZE; ++x)
		{
			// render two vertices of the strip at once
			float scaledHeight = heightmap[z * TERRAIN_SIZE + x] / SCALE_FACTOR;
			float nextScaledHeight = heightmap[(z + 1)* TERRAIN_SIZE + x] / SCALE_FACTOR;
			float color = 0.5f + 0.5f * scaledHeight / MAX_HEIGHT;
			float nextColor = 0.5f + 0.5f * nextScaledHeight / MAX_HEIGHT;
			
			glColor3f(color, color, color);
			glTexCoord2f((GLfloat)x/TERRAIN_SIZE*8, (GLfloat)z/TERRAIN_SIZE*8);
			glVertex3f(static_cast<GLfloat>(x - TERRAIN_SIZE/2), scaledHeight, static_cast<GLfloat>(z - TERRAIN_SIZE/2));
			
			glColor3f(nextColor, nextColor, nextColor);
			glTexCoord2f((GLfloat)x/TERRAIN_SIZE*8, (GLfloat)(z+1)/TERRAIN_SIZE*8);
			glVertex3f(static_cast<GLfloat>(x - TERRAIN_SIZE/2), nextScaledHeight, static_cast<GLfloat>(z + 1 - TERRAIN_SIZE/2));	
		}
		glEnd();
	}
	
	if(DrawWater == 1)
	{
		glColor4f(0.9f, 0.9f, 0.9f, 0.15f);
		glEnable(GL_BLEND);	
		glBlendFunc(GL_ONE, GL_ONE);
		glActiveTextureARB(GL_TEXTURE0_ARB);
		glEnable(GL_TEXTURE_2D);
		glBindTexture(GL_TEXTURE_2D,  g_Texture[18]);
		glActiveTextureARB(GL_TEXTURE1_ARB);
		glEnable(GL_TEXTURE_2D);
		glBindTexture(GL_TEXTURE_2D,  g_Texture[0]);
		glActiveTextureARB(GL_TEXTURE2_ARB);
		glEnable(GL_TEXTURE_2D);
		glBindTexture(GL_TEXTURE_2D,  g_Texture[0]);
		glBegin(GL_QUADS);
		glTexCoord2f(-40.0, 0.0);glVertex3f(-SEA_SIZE / 2, SEA_LEVEL, SEA_SIZE / 2);
		glTexCoord2f(-40.0, 40.0);glVertex3f(-SEA_SIZE / 2, SEA_LEVEL, -SEA_SIZE / 2);
		glTexCoord2f(40.0, 40.0);glVertex3f(SEA_SIZE / 2, SEA_LEVEL, -SEA_SIZE / 2);
		glTexCoord2f(40.0, 0.0);glVertex3f(SEA_SIZE / 2, SEA_LEVEL, SEA_SIZE / 2);
		glEnd();
		glDisable(GL_BLEND);
	}
	
	CVector3 currentPos = g_Camera.Position();
	CVector3 newPos = currentPos;
	if (currentPos.y < Height(g_HeightMap, currentPos.x, currentPos.y) + 10)
	{
		newPos.y = (float)Height(g_HeightMap, currentPos.x, currentPos.y)  + 10;
		float temp = newPos.y - currentPos.y;
		CVector3 vView = g_Camera.View();
		vView.y += temp;
			
		g_Camera.PositionCamera(newPos.x, newPos.y, newPos.z,
			vView.x, vView.y, vView.z,
			0, 1, 0);
	}
}

Terrain.h:

Code:

const int TERRAIN_SIZE = 260;
GLubyte g_HeightMap[TERRAIN_SIZE*TERRAIN_SIZE];
GLubyte heightmap[TERRAIN_SIZE * TERRAIN_SIZE];
void DrawTerrain();

all help will be appreciated

-psychopath

Code:

 
int Height(BYTE *pHeightMap, int X, int Y)
{
	// Make sure we don't go past our array size
	int x = X % TERRAIN_SIZE;					// Error check our x value
	int y = Y % TERRAIN_SIZE;					// Error check our y value

	if(!pHeightMap) return 0;				// Make sure our data is valid

	// Use the equation: index = (x + (y * arrayWidth) ) to find the current height
	return pHeightMap[x + (y * TERRAIN_SIZE)];	// Index into our height array and return the height
}

Code:

int Height(BYTE *pHeightMap, int X, int Y,float fx,float fy)
{
  Added
  //If TERRAIN_SIZE is a power of 2 then
  //x % terrain_size is the same as
  //x & (terrain_size-1)
 
   // Make sure we don't go past our array size
  int adj_terrain_size=TERRAIN_SIZE-1;
 
  int x = X & adj_terrain_size;   
  int y = Y & adj_terrain_size; 
 
  //Added
  int x2=(X+1) & adj_terrain_size;
  int y2=(Y+1) & adj_terrain_size;

  //No need to check this pointer
  //If you are calling this function it should be
  //or you have no business using this engine
  //if(!pHeightMap) return 0;				  // Make sure our data is valid

  WORD offset1=(y*TERRAIN_SIZE)+x;
  WORD offset2=(y*TERRAIN_SIZE)+x+1;
  WORD offset3=((y+1)*TERRAIN_SIZE)+x;
  WORD offset4=((y+1)*TERRAIN_SIZE)+x+1;
 
  int height1=pHeightMap[offset1];
  int height2=pHeightMap[offset2];
  int height3=pHeightMap[offset3];
  int height4=pHeightMap[offset4];
 
  int heightx1=(int)((float)height1+fx*((float)height2-(float)height1));
  int heightx2=(int)((float)height3+fx*((float)height4-(float)height3));
  return (int)((float)heightx1+fy*((float)heightx2-(float)heightx1));
 
}

But this is not the fastest code on earth. Lots of data type conversions which will hog cycles.
But the algo is correct. This would work for a voxel renderer, but it needs more for a tri-based renderer. You must figure out which triangle of the quad you are in first.