Sign in to follow this  
daniel_i_l

checking quadtree code

Recommended Posts

Now I've completed my first quadtree (which I called BSP) but I did it without reading anymore than basic theory. Can someone please check the code and tell me if there is anything I should do to make it better, and in generel if this is good code or not:

struct BSP{
 float height, width, depth;
 float centerX, centerY, centerZ;
 MinMax limits;
 BSP *p_sec1, *p_sec2, *p_sec3, *p_sec4;
 bool found_limits;
 bool is_leaf;
};

class CBspTree{
 public: 
   CBspTree();
  ~CBspTree();
   int number_of_parts;
   void GetHeightMap(BYTE *pH){p_HeightMap = pH;}
   void GetBoxes(){map->limits = FindLimits(map);}
   void RenderMap();
 private:
  BSP* map;
  BYTE* p_HeightMap;
  void InitTree(BSP* node, float x, float y, float h, float w);
  void EraseBSP(BSP* node);
  void Render(BSP* node);
  MinMax FindLimits(BSP* node);
  MinMax FindLimitsOfArea(float blX, float blY, float trX, float trY);
};

extern CFrustum Frustum;

float Smallest(float a, float b, float c, float d)
{
  float smallest=10000;
  
  if(a < smallest)
   smallest = a;
  if(b < smallest)
   smallest = b;
  if(c < smallest)
   smallest = c;
  if(d < smallest)
   smallest = d;
  
  return(smallest);
}

float Biggest(float a, float b, float c, float d)
{
  float biggest=10000;
  
  if(a > biggest)
   biggest = a;
  if(b > biggest)
   biggest = b;
  if(c > biggest)
   biggest = c;
  if(d > biggest)
   biggest = d;
  
  return(biggest);
}


CBspTree :: CBspTree()
{
  map = new BSP;
  number_of_parts = 0;
  InitTree(map,MAP_SIZE/2, MAP_SIZE/2, MAP_SIZE, MAP_SIZE);
}

CBspTree :: ~CBspTree()
{
  EraseBSP(map);
}

void CBspTree :: InitTree(BSP* node, float x, float y, float h, float w)
{
   node->centerX = x; node->centerZ = y; node->centerY = 0; 
   node->depth = h; node->width = w; node->height = 0;
   node->found_limits = false;
   number_of_parts++;
   if(w>32)
   {
     node->is_leaf = false;     
     node->p_sec1 = new BSP;
     node->p_sec2 = new BSP;
     node->p_sec3 = new BSP;
     node->p_sec4 = new BSP;

     InitTree(node->p_sec1, x-w/4, y-h/4, h/2, w/2);
     InitTree(node->p_sec2, x+w/4, y-h/4, h/2, w/2);
     InitTree(node->p_sec3, x+w/4, y+h/4, h/2, w/2);
     InitTree(node->p_sec4, x-w/4, y+h/4, h/2, w/2);
   }
   
   else
   {
     node->is_leaf=true;
   }
}

void CBspTree :: EraseBSP(BSP* node)
{
   if(!node->is_leaf)
    {
      EraseBSP(node->p_sec1); 
      EraseBSP(node->p_sec2); 
      EraseBSP(node->p_sec3); 
      EraseBSP(node->p_sec4); 
      delete node;
    } 
    else
      delete node;
}

MinMax CBspTree :: FindLimitsOfArea(float blX, float blY, float trX, float trY)
{
  MinMax limit;
  float y;
  
  limit.min = 10000;  limit.max = -10000;
  for(int i = blX; i <= trX; i+=STEP_SIZE)
   {
     for(int j = blY; j <= trY; j+=STEP_SIZE)
      {
        y = (float)(SCALE_HEIGHT*Height(p_HeightMap, (float)i, (float)j ));  
        if(y>limit.max)
         limit.max = y;
        if(y<limit.min)
         limit.min = y;
         }
   }
  return(limit);
}



MinMax CBspTree :: FindLimits(BSP* node)
{
   if(!node->is_leaf)
    {
      node->limits.min = Smallest(FindLimits(node->p_sec1).min,
                                  FindLimits(node->p_sec2).min,
                                  FindLimits(node->p_sec3).min,
                                  FindLimits(node->p_sec4).min);
      
      node->limits.max =  Biggest(FindLimits(node->p_sec1).max,
                                  FindLimits(node->p_sec2).max,
                                  FindLimits(node->p_sec3).max,
                                  FindLimits(node->p_sec4).max);
      
      node->centerY = (node->limits.min + node->limits.max)/2;
      node->height = node->limits.max - node->limits.min;
      node->found_limits = true;
    }
   else
    {
      //node->limits.max = Height(p_HeightMap, node->centerX, node->centerZ);
      //node->limits.min = 20;
      node->limits = FindLimitsOfArea(node->centerX - node->width/2, node->centerX + node->width/2,
                                     node->centerZ - node->depth/2, node->centerZ + node->depth/2);
      
      node->centerY = (node->limits.min + node->limits.max)/2;
      node->height = node->limits.max - node->limits.min;
      node->found_limits = true;
    }
}

void CBspTree :: Render(BSP* node)
{
  //if((node->is_leaf) && (Frustum.BoxInFrustum( node->centerX, node->centerY, node->centerZ, 32, 50, 32 )) )
  if(node->is_leaf)
   {
     if(Frustum.BoxInFrustum( SCALE_SIDE*node->centerX, node->centerY, SCALE_SIDE*node->centerZ, node->height/2, (SCALE_SIDE*node->width)/2, (SCALE_SIDE*node->depth)/2))
     RenderHeightMap(p_HeightMap, (int)(node->centerX - node->width/2), (int)(node->centerZ - node->depth/2),
                                  (int)(node->centerX + node->width/2), (int)(node->centerZ + node->depth/2) );
   }
  else
   {
    if(Frustum.BoxInFrustum( SCALE_SIDE*node->p_sec1->centerX, node->p_sec1->centerY, SCALE_SIDE*node->p_sec1->centerZ, node->p_sec1->height/2, (SCALE_SIDE*node->p_sec1->width)/2, (SCALE_SIDE*node->p_sec1->depth)/2)) 
     Render(node->p_sec1); 
    if(Frustum.BoxInFrustum( SCALE_SIDE*node->p_sec2->centerX, node->p_sec2->centerY, SCALE_SIDE*node->p_sec2->centerZ, node->p_sec2->height/2, (SCALE_SIDE*node->p_sec2->width)/2, (SCALE_SIDE*node->p_sec2->depth)/2)) 
     Render(node->p_sec2); 
    if(Frustum.BoxInFrustum( SCALE_SIDE*node->p_sec3->centerX, node->p_sec3->centerY, SCALE_SIDE*node->p_sec3->centerZ, node->p_sec3->height/2, (SCALE_SIDE*node->p_sec3->width)/2, (SCALE_SIDE*node->p_sec3->depth)/2)) 
     Render(node->p_sec3); 
    if(Frustum.BoxInFrustum( SCALE_SIDE*node->p_sec4->centerX, node->p_sec4->centerY, SCALE_SIDE*node->p_sec4->centerZ, node->p_sec4->height/2, (SCALE_SIDE*node->p_sec4->width)/2, (SCALE_SIDE*node->p_sec4->depth)/2)) 
     Render(node->p_sec4); 
   }
}

void CBspTree :: RenderMap()
{
   if(!p_HeightMap) return;     
   
   Frustum.CalculateFrustum();
    // Activate the first texture ID and bind the tree background to it
    glActiveTextureARB(GL_TEXTURE0_ARB);
    glEnable(GL_TEXTURE_2D);
    glBindTexture(GL_TEXTURE_2D, g_Texture[0]);

    // If we want detail texturing on, let's render the second texture
    if(g_bDetail)
    {
        // Activate the second texture ID and bind the fog texture to it
        glActiveTextureARB(GL_TEXTURE1_ARB);
        glEnable(GL_TEXTURE_2D);
        
        // Here we turn on the COMBINE properties and increase our RGB
        // gamma for the detail texture.  2 seems to work just right.
        glTexEnvi(GL_TEXTURE_ENV, GL_TEXTURE_ENV_MODE, GL_COMBINE_EXT);
        glTexEnvi(GL_TEXTURE_ENV, GL_RGB_SCALE_EXT, 2);
        
        // Bind the detail texture
        glBindTexture(GL_TEXTURE_2D, g_Texture[1]);
    
        // Now we want to enter the texture matrix.  This will allow us
        // to change the tiling of the detail texture.
        glMatrixMode(GL_TEXTURE);

            // Reset the current matrix and apply our chosen scale value
            glLoadIdentity();
            glScalef((float)g_DetailScale, (float)g_DetailScale, 1);

        // Leave the texture matrix and set us back in the model view matrix
        glMatrixMode(GL_MODELVIEW);
    }
    //if(Frustum.BoxInFrustum( 0, 0, 0, 100, 100, 100 ))
    Render(map);
    
    glPolygonMode( GL_FRONT_AND_BACK, GL_FILL);
    // Turn the second multitexture pass off
    glActiveTextureARB(GL_TEXTURE1_ARB);
    glDisable(GL_TEXTURE_2D);

    // Turn the first multitexture pass off
    glActiveTextureARB(GL_TEXTURE0_ARB);        
    glDisable(GL_TEXTURE_2D);
    glEnable(GL_TEXTURE_2D);
}  
      

Any input would be appreciated. Thanks. Thanks!

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