Home
Blogs
Forums
News
Portfolios
Projects
Tutorials
42 users logged in
New? Learn about game development.
Before posting, review our community guidelines.
Follow Us
Chat in the GameDev.net Discord!
Mastodon
Back to General and Gameplay Programming

Slow terrain code, need help

Started by
2 comments, last by FlyingDodo 18 years, 1 month ago
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.x,vTriNormal.y,vTriNormal.z);
		}else{
		if(i != ((rows*currentRow)+currentRow)-1)
		{
			if(vTriangle[(i+6)+(rows-4)].z == vTriangle.z && vTriangle[(i+5)+(rows-4)].z == vTriangle.z && vTriangle[i+1].z == vTriangle.z)
			{
			glBindTexture(GL_TEXTURE_2D, texture[2]);
			
			if(wireframe == false)
			{
			glBegin(GL_QUADS);
			}else{
			glBegin(GL_LINE_LOOP);
			}

if(useFrustum)
{      
       if(PointInFrustum(vTriangle) || PointInFrustum(vTriangle[i+1]) || PointInFrustum(vTriangle[(i+6)+(rows-4)]) || PointInFrustum(vTriangle[(i+5)+(rows-4)]))
       {
			glNormal3f(vTriNormal.x,vTriNormal.y,vTriNormal.z);	
			glTexCoord2f(1.0f, 1.0f);
			glVertex3f(vTriangle.x,vTriangle.y,vTriangle.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.x,vTriNormal.y,vTriNormal.z);	
			glTexCoord2f(1.0f, 1.0f);
			glVertex3f(vTriangle.x,vTriangle.y,vTriangle.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.x,vTriNormal.y,vTriNormal.z);	
			glTexCoord2f(1.0f, 1.0f);
			glVertex3f(vTriangle.x,vTriangle.y,vTriangle.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.x,vTriNormal.y,vTriNormal.z);
			glTexCoord2f(1.0f, 1.0f);
			glVertex3f(vTriangle.x,vTriangle.y,vTriangle.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.x,vTriNormal.y,vTriNormal.z);
			glTexCoord2f(1.0f, 1.0f);
			glVertex3f(vTriangle.x,vTriangle.y,vTriangle.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++;
		}}
		
	}
}
Advertisement
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.
~CGameProgrammer( );Developer Image Exchange -- New Features: Upload screenshots of your games (size is unlimited) and upload the game itself (up to 10MB). Free. No registration needed.
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.
SlimDX | Ventspace Blog | Twitter | Diverse teams make better games. I am currently hiring capable C++ engine developers in Baltimore, MD.
It seems you are checking to see if every single point is visible, thats not a good idea. If you want to have the culling and have speed then you're going to need a quad tree.

This topic is closed to new replies.

Advertisement

Popular Topics

Aybe One
How do you manage yourself and your time as years pass on? GDNet Lounge
Jikoob
Too many managers? General and Gameplay Programming
aigan
The promise of freedom in story games Game Design and Theory
robertrobert
Facebook Ads for sales on steam, does it work? Games Business and Law
Aybe One
Which design pattern to dodge the craziness of immediate mode? General and Gameplay Programming
pbivens67
AABB collision For Beginners
Advertisement

Recommended Tutorials

gdarchive
Substance Painter Review Visual Arts
Myopic Rhino
Demo Night VIII Event Coverage
tduindam
Breaking Out of Breakout Game Design and Theory
Myopic Rhino
Triangle Game Conference 2010 Event Coverage
fabienbk
Procedural Level Generation for a 2D Platformer General and Gameplay Programming

Reticulating splines

About GameDev.net
Community Guidelines
Terms of Service
Privacy Policy
Contact Us
Copyright (c) 1999-2024 GameDev.net, LLC
Back to Top