How could I optimise my 3D terrain algo? // Terrain3D.h: interface for the Terrain3D class. // ////////////////////////////////////////////////////////////////////// #if !defined(AFX_TERRAIN_H__72155EE2_65CA_11D5_B877_A51463FD174D__INCLUDED_) #define AFX_TERRAIN_H__72155EE2_65CA_11D5_B877_A51463FD174D__INCLUDED_ #include "bob.h" #include "FrustumCulling.h" #include "Repere3D.h" const MAP_SIZE = 256; #define MAP_INDEX(x, y) (((x)&255) + (((y)&255) << 8)) class Terrain3D { struct TerrainColor { uint8 r, g, b, a; }; public: Repere3D *camera; uint treeTexture; void SetBilinearFiltering(bool enable); Terrain3D(char *elevation_file, char *color_file, char *texture_file, real _y_scale = 10.0, real _espacement = 256.0); void Render(real y); void create_fractal(); real GetHeight(real pos_x, real pos_z); void Draw(uint x, uint z, uint w); void RenderNode(uint x, uint z, uint w); Terrain3D(); ~Terrain3D(); real espacement;//distance entre 2 points de la map real y_scale;//facteur d''altitude real max_y2;//hauteur maximale divisé par 2 uint min_size;//dimension minimale d''un bloc à découper real espacement_lod;// = espacement * lod; real elevations[MAP_SIZE * MAP_SIZE]; TerrainColor colors[MAP_SIZE * MAP_SIZE]; uint texID; uint lod; };//class Terrain3D #endif // !defined(AFX_TERRAIN_H__72155EE2_65CA_11D5_B877_A51463FD174D__INCLUDED_) // Terrain.cpp: implementation of the Terrain3D class. // ////////////////////////////////////////////////////////////////////// #include "Terrain.h" #include "Image2D.h" #include #include "Particule3D.h" #include "GameEngine.h" ////////////////////////////////////////////////////////////////////// // Construction/Destruction ////////////////////////////////////////////////////////////////////// Terrain3D::Terrain3D() { espacement = 128.0; min_size = 2; create_fractal(); texID = 0; Image2D *img = LoadImage2D("./fonds/terrain.tga"); if(LoadInTexture(img)) texID = img->texID; FreeImage2D(img); }//Terrain3D::Terrain3D() Terrain3D::~Terrain3D() { glDeleteTextures(1, &texID); } void Terrain3D::Draw(uint x, uint z, uint w) { Box3D box; box.x = real(x * espacement); box.y = max_y2;//128 * y_scale; box.z = real(z * espacement); box.w = real(w * espacement); box.p = real(w * espacement); box.h = max_y2;//128 * y_scale;; switch( BoxInFrustum(box) ) { case 2: RenderNode(x, z, w); break; case 0: break; case 1: if(w > min_size) { w = w >> 1; Draw(x + w, z + w, w); Draw(x - w, z + w, w); Draw(x + w, z - w, w); Draw(x - w, z - w, w); } else RenderNode(x, z, w); };//switch }//void Terrain3D::Draw() void Terrain3D::RenderNode(uint x_pos, uint z_pos, uint w) { uint x, z; /*Vector up, pos_vector; up.Set(0.0, 1.0, 0.0); glBindTexture(GL_TEXTURE_2D, treeTexture); pos_vector.Set(x_pos * espacement, elevations[MAP_INDEX(x_pos,z_pos)] + 50.0, z_pos * espacement); glColor3ub(255, 255, 255); glDisable(GL_CULL_FACE); glBlendFunc(GL_SRC_ALPHA, GL_ONE); glEnable(GL_BLEND); DrawBillboard(pos_vector, *camera, up, 100.0); glDisable(GL_BLEND); glEnable(GL_CULL_FACE); glBindTexture(GL_TEXTURE_2D, texID); */ /* //dessine les box de l''octree glDisable(GL_TEXTURE_2D); glPushMatrix(); glTranslate(x_pos * espacement, 128.0, z_pos * espacement); glColor3ub(x_pos % 255, z_pos % 256, 255); glutWireCube(w * espacement * 2); glPopMatrix(); glEnable(GL_TEXTURE_2D);*/ const real u1 = 0.0; const real v1 = 0.0; const real u2 = 1.0 * lod; const real v2 = 1.0 * lod; uint max_x = x_pos + w, max_z = z_pos + w; uint min_x = x_pos - w, min_z = z_pos - w; real x1, z1, x2, z2; real min_z1 = min_z * espacement; x1 = min_x * espacement; for(x = min_x; x < max_x; x+=lod, x1 += espacement_lod) { x2 = x1 + espacement_lod; z1 = min_z1; for(z = min_z; z < max_z; z+=lod, z1+=espacement_lod) { z2 = z1 + espacement_lod; glBegin(GL_TRIANGLE_STRIP); glColor3ub(colors[MAP_INDEX(x,z)].r, colors[MAP_INDEX(x,z)].g, colors[MAP_INDEX(x,z)].b); glTexCoord2f(u1, v1); glVertex3f(x1, elevations[MAP_INDEX(x,z)], z1); glColor3ub(colors[MAP_INDEX(x+lod,z)].r, colors[MAP_INDEX(x+lod,z)].g, colors[MAP_INDEX(x+lod,z)].b); glTexCoord2f(u2, v1); glVertex3f(x2, elevations[MAP_INDEX(x+lod,z)], z1); glColor3ub(colors[MAP_INDEX(x,z+lod)].r, colors[MAP_INDEX(x,z+lod)].g, colors[MAP_INDEX(x,z+lod)].b); glTexCoord2f(u1, v2); glVertex3f(x1, elevations[MAP_INDEX(x,z+lod)], z2); glColor3ub(colors[MAP_INDEX(x+lod,z+lod)].r, colors[MAP_INDEX(x+lod,z+lod)].g, colors[MAP_INDEX(x+lod,z+lod)].b); glTexCoord2f(u2, v2); glVertex3f(x2, elevations[MAP_INDEX(x+lod,z+lod)], z2); glEnd(); }//for z }//for x }//Terrain3D::RenderNode real Terrain3D::GetHeight(real pos_x, real pos_z) { real x0, x1, lx, lz, x, z, midpoint; int fx, fz; x = pos_x/espacement; z = pos_z/espacement; fx = (int)(x); fz = (int)(z); lx = x - fx; lz = z - fz; x0 = elevations[MAP_INDEX(fx,fz)] + (elevations[MAP_INDEX(fx,fz+1)] - elevations[MAP_INDEX(fx,fz)])*lz; x1 = elevations[MAP_INDEX(fx+1,fz)] + (elevations[MAP_INDEX(fx+1,fz+1)] - elevations[MAP_INDEX(fx+1,fz)])*lz; midpoint = x0 + (x1 - x0)*lx; return midpoint; }//real Terrain3D::GetHeight(real x, real y) void Terrain3D::create_fractal() { //int bsize, csize; int x, z;//, i; int r = 512; float gradient, shadow = 0.5; /*for(x=0;x<=MAP_SIZE;x++) for(z=0;z<=MAP_SIZE;z++) elevations[MAP_INDEX(x,z)] = 0; bsize = MAP_SIZE; for(i=0; i<8; i++) { for(x=0;x for(z=0;z elevations[MAP_INDEX(x,z)] += (rand()%(r+1)-r/2); if(i>4) r=r/2; csize = bsize/2; if(csize>0) { for(x=0; x { for(z=0; z { if( x < MAP_SIZE) elevations[MAP_INDEX(x+csize,z)] = (elevations[MAP_INDEX(x+bsize,z)]+elevations[MAP_INDEX(x,z)])/2; if( z < MAP_SIZE) elevations[MAP_INDEX(x,z+csize)] = (elevations[MAP_INDEX(x,z+bsize)]+elevations[MAP_INDEX(x,z)])/2; if ( x < MAP_SIZE && z < MAP_SIZE ) elevations[MAP_INDEX(x+csize,z+csize)] = ( elevations[MAP_INDEX(x,z)] + elevations[MAP_INDEX(x+bsize,z)] + elevations[MAP_INDEX(x,z+bsize)] + elevations[MAP_INDEX(x+bsize,z+bsize)]) / 4; }//for(z=0; z }//for(x=0; x }//if(csize>0) bsize = csize; }//for(i=0; i<8; i++) const real div_coef = 4.0; for(x=0; x { for(z=0; z { elevations[MAP_INDEX(x,z)] = elevations[MAP_INDEX(x,z)] + elevations[MAP_INDEX(x+1,z)] + elevations[MAP_INDEX(x+1,z+1)] + elevations[MAP_INDEX(x,z+1)]; elevations[MAP_INDEX(x,z)] /= div_coef; } } */ for(x=0; x<=MAP_SIZE; x++) { for(z=0; z<=MAP_SIZE; z++) { gradient = ((GLfloat) (elevations[MAP_INDEX(x,z)]-elevations[MAP_INDEX(x+1,z)])) / 100.0; if(elevations[MAP_INDEX(x,z)]>64) { if((elevations[MAP_INDEX(x,z)]-elevations[MAP_INDEX(x,z+1)])<8 && (elevations[MAP_INDEX(x,z)]-elevations[MAP_INDEX(x,z+1)])>-8 && (elevations[MAP_INDEX(x,z)]-elevations[MAP_INDEX(x+1,z)])<8 && (elevations[MAP_INDEX(x,z)]-elevations[MAP_INDEX(x+1,z)])>-8) { colors[MAP_INDEX(x,z)].g = (gradient + 0.75) * 255; colors[MAP_INDEX(x,z)].r = colors[MAP_INDEX(x,z)].g; colors[MAP_INDEX(x,z)].b = colors[MAP_INDEX(x,z)].g; } else { colors[MAP_INDEX(x,z)].r = (gradient + 0.75) * 255; colors[MAP_INDEX(x,z)].g = colors[MAP_INDEX(x,z)].r * 0.8; colors[MAP_INDEX(x,z)].b = colors[MAP_INDEX(x,z)].r * 0.5; } }//if(elevations[MAP_INDEX(x,z)]>64) else if(elevations[MAP_INDEX(x,z)]>0) { colors[MAP_INDEX(x,z)].g = (gradient + 0.75) * 255; colors[MAP_INDEX(x,z)].r = colors[MAP_INDEX(x,z)].g * 0.6; colors[MAP_INDEX(x,z)].b = 0.0; } else { colors[MAP_INDEX(x,z)].r = (gradient + 1.0) * 255; colors[MAP_INDEX(x,z)].g = colors[MAP_INDEX(x,z)].r * 0.75; colors[MAP_INDEX(x,z)].b = colors[MAP_INDEX(x,z)].r * 0.5; } }//for(z=0; z<=MAP_SIZE; z++) }//for(x=0; x<=MAP_SIZE; x++) }//Terrain3D::create_fractal void Terrain3D::Render(real y) { glEnable(GL_TEXTURE_2D); glBindTexture(GL_TEXTURE_2D, texID); //glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_WRAP_S, GL_REPEAT); //glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_WRAP_T, GL_REPEAT); glTexParameteri( GL_TEXTURE_2D,GL_TEXTURE_MAG_FILTER,GL_LINEAR_MIPMAP_LINEAR ); glTexParameteri( GL_TEXTURE_2D,GL_TEXTURE_MIN_FILTER,GL_LINEAR_MIPMAP_LINEAR ); glEnable(GL_DEPTH_TEST); glShadeModel(GL_SMOOTH); glEnable(GL_CULL_FACE); glCullFace(GL_FRONT); glEnable(GL_FOG); //bool fps_insuffisent = OutRun::currentFPS < 50.0; if(y > max_y2 * 256) lod = 32; else if(y > max_y2 * 128) lod = 16; else if(y > max_y2 * 64) lod = 8; else if(y > max_y2 * 32) lod = 4; else if(y > max_y2 * 16) lod = 2; else lod = 1; //lod = 4; if(lod > 4) min_size = lod; else min_size = 4; espacement_lod = espacement * lod; GetCurrentFrustum(); Draw(65536, 65536, 65536); glColor3ub(255, 255, 255); }//void Terrain3D::Render() Terrain3D::Terrain3D(char *elevation_file, char *color_file, char *texture_file, real _y_scale, real _espacement) { uint index=0; Image2D *img; y_scale = _y_scale * 4.0; max_y2 = 255.0 * y_scale / 2.0; espacement = _espacement; min_size = 2; lod = 1; texID = 0; img = LoadImage2D(texture_file); if(LoadInTexture(img, IMG_MIPMAP)) texID = img->texID; FreeImage2D(img); img = LoadImage2D(elevation_file); if(img) if( (img->w == MAP_SIZE) && (img->h == MAP_SIZE) && (img->bpp == 24)) for(uint x=0; x for(uint y=0; y { elevations[MAP_INDEX(x, y)] = real( img->pixel8[index] ) * y_scale; index += 3; } FreeImage2D(img); img = LoadImage2D(color_file); if(img) if( (img->w == MAP_SIZE) && (img->h == MAP_SIZE)) { index = 0; if(img->bpp == 32) for(uint x=0; x for(uint y=0; y { colors[MAP_INDEX(x, y)].r = img->pixel8[index]; colors[MAP_INDEX(x, y)].g = img->pixel8[index+1]; colors[MAP_INDEX(x, y)].b = img->pixel8[index+2]; colors[MAP_INDEX(x, y)].a = img->pixel8[index+3]; index+=4; } if(img->bpp == 24) for(uint x=0; x for(uint y=0; y { colors[MAP_INDEX(x, y)].r = img->pixel8[index]; colors[MAP_INDEX(x, y)].g = img->pixel8[index+1]; colors[MAP_INDEX(x, y)].b = img->pixel8[index+2]; index += 3; } }//if( (img->w == MAP_SIZE) && (img->h == MAP_SIZE) FreeImage2D(img); //DirectLoadTexture(treeTexture, "./terrains/tree.tga"); //create_fractal(); }//Terrain3D::Terrain3D(char *elevation_file, char *color_file, char *texture_file) void Terrain3D::SetBilinearFiltering(bool enable) { glBindTexture(GL_TEXTURE_2D, texID); if(enable) { glTexParameteri( GL_TEXTURE_2D,GL_TEXTURE_MAG_FILTER,GL_NEAREST_MIPMAP_NEAREST); glTexParameteri( GL_TEXTURE_2D,GL_TEXTURE_MIN_FILTER,GL_NEAREST_MIPMAP_NEAREST); } else { glTexParameteri( GL_TEXTURE_2D,GL_TEXTURE_MAG_FILTER,GL_NEAREST_MIPMAP_NEAREST); glTexParameteri( GL_TEXTURE_2D,GL_TEXTURE_MIN_FILTER,GL_NEAREST_MIPMAP_NEAREST); } }//void Terrain3D::SetBilinearFiltering(bool enable)

Well you can always optimize somewhat by replacing your * and / with bit shifting. Bit shifting is much faster than multiplication and division.

Thanks, but I search algorythmic optimization. For example how can I add LOD without building a tree?