Sign in to follow this  
Krelian

Slow terrain code, need help

Recommended Posts

Hi i made this code to generate at flat terrain grid ( for use with at height map which will come later once i know how to read a bmp file >< ) however at a certain size (over 65536 points) the frustum culling, seems to make the code even slower. so any tips on how to make it better or faster would be much appreciated in short it generates rows of points and the normals, which are stored in a array as a vector. Then it renders it as triangles.. *pMap is the height map, not really used yet vTriangle is the array of points vTriNormal is the array for the normals of the points Rows is the number of rows and colums of quads (2 triangle polygons), for example 4 rows would need 25 points, see below . . . . . . . . . . . . . . . . . . . . . . . . . hopefully my code isn't to shabby' Oh and a link for a good tutorial for a BSP or octree would be appreciated too :) thanks
int LoadMapFile2(char *pMap, vector vTriangle[],vector vTriNormal[],unsigned long rows,unsigned short smoothness)
{
glDisable(GL_LIGHTING);
#define SCALE 0.50f;

unsigned long length = (rows+1) * (rows+1);
unsigned long i=0,j=0,counter=0;
unsigned long currentRow = 0;

	for (j=0;j<rows+1;j++)
	{
		for(i=0;i<rows+1;i++)
		{
			
		vTriangle[(((1+i)+(j*rows))+j)-1].x = float(i)*SCALE; // Scales our Terrain down on the x side
		vTriangle[(((1+i)+(j*rows))+j)-1].y = float(j)*SCALE; // Scales our Terrain down on the y side
		vTriangle[(((1+i)+(j*rows))+j)-1].z = 0;
		
		activePixel[(((1+i)+(j*rows))+j)-1] = 1; // 0 means not active, 1 means active (default)
		vTriNormal[(((1+i)+(j*rows))+j)-1] = vector(0,0,0);
		
		}
	}

counter=0;
i = 0;
j = 0;


//This smooths our terrain
for(i=0;i<smoothness;i++)
{
	for(j=0;j<length;j++)
	{
	vTriangle[j].z = (vTriangle[(j+6)+(rows-4)].z,vTriangle[(j+5)+(rows-4)].z,vTriangle[(j+4)+(rows-4)].z,vTriangle[(j+6)-(rows-4)].z,vTriangle[(j+5)-(rows-4)].z,vTriangle[(j+4)-(rows-4)].z,vTriangle[j-1].z,vTriangle[j+1].z)/9;
	}
}

//Rutine to find the vertex normals >< omg!!

//Main LOOP!!

for(j=0;j<length;j++)
{


// These if's find each point in each corner. :>
if(j==0) // The first point in the first row DOH!!! ><
{
	vector tempN = (normal(vTriangle[j],vTriangle[(j+6)+(rows-4)],vTriangle[j+1])+normal(vTriangle[j],vTriangle[(j+5)+(rows-4)],vTriangle[j+1]));
	tempN = tempN / 2;
	vTriNormal[j] = tempN;
}else{
if(j==rows) // the last point in the first row.
{
	vector tempN = (normal(vTriangle[j],vTriangle[j-1],vTriangle[j+5+(rows-4)]));
	vTriNormal[j] = tempN;
}else{
if(j == (length-1)) // The final point
{
vector tempN;
tempN = (normal(vTriangle[j],vTriangle[(j - 6)-(rows-4)],vTriangle[j-1]) + normal(vTriangle[j],vTriangle[(j - 5)-(rows-4)],vTriangle[(j - 6)-(rows-4)]));
tempN = tempN / 2;
vTriNormal[j] = tempN;
}else{
if(j == ((length-1)-rows)) // The first point in the highest row
{
	vTriNormal[j] = normal(vTriangle[j],vTriangle[j+1],vTriangle[(j-5)-(rows-4)]);
}}}}


if(j>0 && j < rows)
{
if(j%2==0)
{
vector tempN = vector(0,0,0);
tempN = (normal(vTriangle[j],vTriangle[j-1],vTriangle[(j+4)+(rows-4)])
	   + normal(vTriangle[j],vTriangle[(j+4)+(rows-4)],vTriangle[(j+5)+(rows-4)])
	   + normal(vTriangle[j],vTriangle[(j+5)+(rows-4)],vTriangle[(j+6)+(rows-4)])
	   + normal(vTriangle[j],vTriangle[(j+6)+(rows-4)],vTriangle[j+1]));
tempN = tempN / 4;
vTriNormal[j] = tempN;
}else{
vector tempN = vector(0,0,0);
tempN = (normal(vTriangle[j],vTriangle[j-1],vTriangle[(j+5)+(rows-4)])
	   + normal(vTriangle[j],vTriangle[(j+5)+(rows-4)],vTriangle[j+1]));
tempN = tempN / 2;
vTriNormal[j] = tempN;
}}


if(j == ((rows*currentRow)+rows)+currentRow && j != rows) // RIGHT ROW
{
	vector tempN = vector(0,0,0);
	if(j%2==0)
	{
		tempN = (normal(vTriangle[j],vTriangle[(j-5)-(rows-4)],vTriangle[(j-6)-(rows-4)])
			   + normal(vTriangle[j],vTriangle[(j-6)-(rows-4)],vTriangle[j-1])
			   + normal(vTriangle[j],vTriangle[j-1],vTriangle[(j+4)+(rows-4)])
			   + normal(vTriangle[j],vTriangle[(j+4)+(rows-4)],vTriangle[(j+5)+(rows-4)]));
		tempN = tempN / 4;
		vTriNormal[j] = tempN;
	}
	else
	{
		tempN = (normal(vTriangle[j],vTriangle[(j-5)-(rows-4)],vTriangle[j-1])
			   + normal(vTriangle[j],vTriangle[j-1],vTriangle[(j+5)+(rows-4)]));
		tempN = tempN / 2;
		vTriNormal[j] = tempN;
	}
}


if(j==rows+(rows*currentRow)+currentRow && currentRow < (rows-1)) // OUR ROW COUNTER!!
{
currentRow++;
}

if(j >= 1+(rows*currentRow)+currentRow && j <= rows+(rows*currentRow)+currentRow-1 && j > rows) // MIDDLE ROWS
{
	vector tempN = vector(0,0,0);
	if(j%2==0)
	{

tempN = (normal(vTriangle[j],vTriangle[j-1],vTriangle[(j+4)+(rows-4)])
	   + normal(vTriangle[j],vTriangle[(j+4)+(rows-4)],vTriangle[(j+5)+(rows-4)])
	   + normal(vTriangle[j],vTriangle[(j+5)+(rows-4)],vTriangle[(j+6)+(rows-4)])
	   + normal(vTriangle[j],vTriangle[(j+6)+(rows-4)],vTriangle[j+1]));
		tempN = tempN / 4;
		vTriNormal[j] = tempN;
	}
	else
	{

tempN = (normal(vTriangle[j],vTriangle[j-1],vTriangle[(j+5)+(rows-4)])
	   + normal(vTriangle[j],vTriangle[(j+5)+(rows-4)],vTriangle[j+1]));
		tempN = tempN / 2;
		vTriNormal[j] = tempN;
	}
	
}else{
	if(j == ((rows+1)*currentRow) && j != 0) // LEFT ROW
	{
	vector tempN = vector(0,0,0);
		if(j%2==0)
		{
			tempN = (normal(vTriangle[j],vTriangle[(j-4)-(rows-4)],vTriangle[(j-5)-(rows-4)])
				   + normal(vTriangle[j],vTriangle[j+1],vTriangle[(j-5)-(rows-4)])
				   + normal(vTriangle[j],vTriangle[(j+6)+(rows-4)],vTriangle[j+1])
				   + normal(vTriangle[j],vTriangle[(j+5)+(rows-4)],vTriangle[(j+6)+(rows-4)]));
		tempN = tempN / 4;
		vTriNormal[j] = tempN;
		}	
		else
		{
		tempN = (normal(vTriangle[j],vTriangle[j+1],vTriangle[(j-5)-(rows-4)])
			   + normal(vTriangle[j],vTriangle[(j+5)+(rows-4)],vTriangle[j+1]));
		tempN = tempN / 2;
		vTriNormal[j] = tempN;
		}
	}

}

if(j > ((length-rows)-1) && j < (length-1)) // TOP ROW
{
	vector tempN = vector(0,0,0);
	if(j%2==0)
	{
		tempN = (normal(vTriangle[j],vTriangle[j+1],vTriangle[(j-4)-(rows-4)])
			   + normal(vTriangle[j],vTriangle[(j-4)-(rows-4)],vTriangle[(j-5)-(rows-4)])
			   + normal(vTriangle[j],vTriangle[(j-5)-(rows-4)],vTriangle[(j-6)-(rows-4)])
			   + normal(vTriangle[j],vTriangle[(j-6)-(rows-4)],vTriangle[j-1]));
		tempN = tempN / 4;
		vTriNormal[j] = tempN;
	}
	else
	{
		tempN = (normal(vTriangle[j],vTriangle[j+1],vTriangle[(j-5)-(rows-4)])
			   + normal(vTriangle[j],vTriangle[(j-5)-(rows-4)],vTriangle[j-1]));
		tempN = tempN / 2;
		vTriNormal[j] = tempN;
	}
}

}

glEnable(GL_LIGHTING);

return 2;
}

void RenderMap(vector vTriangle[],vector vTriNormal[], unsigned long rows,bool wireframe, unsigned long* activePixel)
{
unsigned long length = (rows+1) * (rows+1);
unsigned long i=0,j=0,counter=0;
unsigned long currentRow = 0;

	for (i=0;i<length;i++)
	{
		if(currentRow-1 == rows)
		{
			glNormal3f(vTriNormal[i].x,vTriNormal[i].y,vTriNormal[i].z);
		}else{
		if(i != ((rows*currentRow)+currentRow)-1)
		{
			if(vTriangle[(i+6)+(rows-4)].z == vTriangle[i].z && vTriangle[(i+5)+(rows-4)].z == vTriangle[i].z && vTriangle[i+1].z == vTriangle[i].z)
			{
			glBindTexture(GL_TEXTURE_2D, texture[2]);
			
			if(wireframe == false)
			{
			glBegin(GL_QUADS);
			}else{
			glBegin(GL_LINE_LOOP);
			}

if(useFrustum)
{      
       if(PointInFrustum(vTriangle[i]) || PointInFrustum(vTriangle[i+1]) || PointInFrustum(vTriangle[(i+6)+(rows-4)]) || PointInFrustum(vTriangle[(i+5)+(rows-4)]))
       {
			glNormal3f(vTriNormal[i].x,vTriNormal[i].y,vTriNormal[i].z);	
			glTexCoord2f(1.0f, 1.0f);
			glVertex3f(vTriangle[i].x,vTriangle[i].y,vTriangle[i].z);
      
			glNormal3f(vTriNormal[(i+1)].x,vTriNormal[(i+1)].y,vTriNormal[(i+1)].z);
			glTexCoord2f(0.0f, 1.0f);
			glVertex3f(vTriangle[(i+1)].x,vTriangle[i+1].y,vTriangle[i+1].z);

			glNormal3f(vTriNormal[(i+6)+(rows-4)].x,vTriNormal[(i+6)+(rows-4)].y,vTriNormal[(i+6)+(rows-4)].z);
			glTexCoord2f(0.0f, 0.0f);
			glVertex3f(vTriangle[(i+6)+(rows-4)].x,vTriangle[(i+6)+(rows-4)].y,vTriangle[(i+6)+(rows-4)].z);

			glNormal3f(vTriNormal[(i+5)+(rows-4)].x,vTriNormal[(i+5)+(rows-4)].y,vTriNormal[(i+5)+(rows-4)].z);
			glTexCoord2f(1.0f, 0.0f);
			glVertex3f(vTriangle[(i+5)+(rows-4)].x,vTriangle[(i+5)+(rows-4)].y,vTriangle[(i+5)+(rows-4)].z);
      }
}else{
			glNormal3f(vTriNormal[i].x,vTriNormal[i].y,vTriNormal[i].z);	
			glTexCoord2f(1.0f, 1.0f);
			glVertex3f(vTriangle[i].x,vTriangle[i].y,vTriangle[i].z);
      
			glNormal3f(vTriNormal[(i+1)].x,vTriNormal[(i+1)].y,vTriNormal[(i+1)].z);
			glTexCoord2f(0.0f, 1.0f);
			glVertex3f(vTriangle[(i+1)].x,vTriangle[i+1].y,vTriangle[i+1].z);

			glNormal3f(vTriNormal[(i+6)+(rows-4)].x,vTriNormal[(i+6)+(rows-4)].y,vTriNormal[(i+6)+(rows-4)].z);
			glTexCoord2f(0.0f, 0.0f);
			glVertex3f(vTriangle[(i+6)+(rows-4)].x,vTriangle[(i+6)+(rows-4)].y,vTriangle[(i+6)+(rows-4)].z);

			glNormal3f(vTriNormal[(i+5)+(rows-4)].x,vTriNormal[(i+5)+(rows-4)].y,vTriNormal[(i+5)+(rows-4)].z);
			glTexCoord2f(1.0f, 0.0f);
			glVertex3f(vTriangle[(i+5)+(rows-4)].x,vTriangle[(i+5)+(rows-4)].y,vTriangle[(i+5)+(rows-4)].z);
}
      
			glEnd();

			}else{
			if(i%2==0)
			{
			glBindTexture(GL_TEXTURE_2D, texture[3]);

			if(wireframe == false)
			{
			glBegin(GL_TRIANGLES);
			}else{
			glBegin(GL_LINE_LOOP);
			}

			glNormal3f(vTriNormal[i].x,vTriNormal[i].y,vTriNormal[i].z);	
			glTexCoord2f(1.0f, 1.0f);
			glVertex3f(vTriangle[i].x,vTriangle[i].y,vTriangle[i].z);

			glNormal3f(vTriNormal[(i+6)+(rows-4)].x,vTriNormal[(i+6)+(rows-4)].y,vTriNormal[(i+6)+(rows-4)].z);
			glTexCoord2f(0.0f, 0.0f);
			glVertex3f(vTriangle[(i+6)+(rows-4)].x,vTriangle[(i+6)+(rows-4)].y,vTriangle[(i+6)+(rows-4)].z);
		
			glNormal3f(vTriNormal[(i+5)+(rows-4)].x,vTriNormal[(i+5)+(rows-4)].y,vTriNormal[(i+5)+(rows-4)].z);
			glTexCoord2f(1.0f, 0.0f);
			glVertex3f(vTriangle[(i+5)+(rows-4)].x,vTriangle[(i+5)+(rows-4)].y,vTriangle[(i+5)+(rows-4)].z);

		
			glNormal3f(vTriNormal[i].x,vTriNormal[i].y,vTriNormal[i].z);
			glTexCoord2f(1.0f, 1.0f);
			glVertex3f(vTriangle[i].x,vTriangle[i].y,vTriangle[i].z);
		
			glNormal3f(vTriNormal[(i+1)].x,vTriNormal[(i+1)].y,vTriNormal[(i+1)].z);
			glTexCoord2f(0.0f, 1.0f);
			glVertex3f(vTriangle[(i+1)].x,vTriangle[i+1].y,vTriangle[i+1].z);
		
			glNormal3f(vTriNormal[(i+6)+(rows-4)].x,vTriNormal[(i+6)+(rows-4)].y,vTriNormal[(i+6)+(rows-4)].z);
			glTexCoord2f(0.0f, 0.0f);
			glVertex3f(vTriangle[(i+6)+(rows-4)].x,vTriangle[(i+6)+(rows-4)].y,vTriangle[(i+6)+(rows-4)].z);
			glEnd();
			}else{
			glBindTexture(GL_TEXTURE_2D, texture[4]);
			
			if(wireframe == false)
			{
			glBegin(GL_TRIANGLES);
			}else{
			glBegin(GL_LINE_LOOP);
			}

			glNormal3f(vTriNormal[i].x,vTriNormal[i].y,vTriNormal[i].z);
			glTexCoord2f(1.0f, 1.0f);
			glVertex3f(vTriangle[i].x,vTriangle[i].y,vTriangle[i].z);

			glNormal3f(vTriNormal[(i+1)].x,vTriNormal[(i+1)].y,vTriNormal[(i+1)].z);
			glTexCoord2f(0.0f, 1.0f);
			glVertex3f(vTriangle[(i+1)].x,vTriangle[i+1].y,vTriangle[i+1].z);
	
			glNormal3f(vTriNormal[(i+5)+(rows-4)].x,vTriNormal[(i+5)+(rows-4)].y,vTriNormal[(i+5)+(rows-4)].z);
			glTexCoord2f(1.0f, 0.0f);
			glVertex3f(vTriangle[(i+5)+(rows-4)].x,vTriangle[(i+5)+(rows-4)].y,vTriangle[(i+5)+(rows-4)].z);


			glNormal3f(vTriNormal[(i+6)+(rows-4)].x,vTriNormal[(i+6)+(rows-4)].y,vTriNormal[(i+6)+(rows-4)].z);	
			glTexCoord2f(0.0f, 0.0f);
			glVertex3f(vTriangle[(i+6)+(rows-4)].x,vTriangle[(i+6)+(rows-4)].y,vTriangle[(i+6)+(rows-4)].z);

			glNormal3f(vTriNormal[(i+5)+(rows-4)].x,vTriNormal[(i+5)+(rows-4)].y,vTriNormal[(i+5)+(rows-4)].z);
			glTexCoord2f(1.0f, 0.0f);
			glVertex3f(vTriangle[(i+5)+(rows-4)].x,vTriangle[(i+5)+(rows-4)].y,vTriangle[(i+5)+(rows-4)].z);

			glNormal3f(vTriNormal[(i+1)].x,vTriNormal[(i+1)].y,vTriNormal[(i+1)].z);
			glTexCoord2f(0.0f, 1.0f);
			glVertex3f(vTriangle[(i+1)].x,vTriangle[i+1].y,vTriangle[i+1].z);
			glEnd();
			}}
			if(i==0)
			currentRow++;

		}
		else
		{
			currentRow++;
		}}
		
	}
}

Share this post


Link to post
Share on other sites
Even though frustum culling is popular, it's actually a bad idea. The main reason is you have to remove or add new geometry to the 3D card every time the user changes orientation, which he is constantly doing. That's very slow. An optimized render only sends new data to the 3D card once in a while, and that's easy to do with CLOD because the player's position does not change much from frame to frame. You can wait until he's a certain distance from the previous update position, then re-evaluate the CLOD and set the update position to his current location.

And if you do frustum culling, when the map is very large, there are many regions/polygons that would need to be tested, and that's really slow.

You might consider frustum culling for the parts of the world very near the player, since those are the highest-polygon and you don't have to test many regions.

Share this post


Link to post
Share on other sites
Quote:
Original post by Krelian
hopefully my code isn't to shabby'
Bad news.

First of all, the video card already does per-vertex frustum culling, so you've duplicated the hardware's task slowly in software. (Really slowly. You check each point as many as 8 times!) Second, you're using glNormal/glTexCoord/glVertex -- you cannot actually get any slower (without intentionally wasting time).

You need to divide the terrain into patches (I find 65x65 works best). Each patch needs to get a VBO of its own (and don't forget to use an indexed triangle list). Then you give each of those patches its own bounding box, and cull away entire bounding boxes at a time. Add a quadtree on top for added effect. This is still a very naive implementation, but it'll be an few orders of magnitude faster than what you're doing now, which is actually slower than brute forced rendering.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this