Sign in to follow this  

checking quadtree code

This topic is 4279 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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

This topic is 4279 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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