Jump to content
  • Advertisement
Sign in to follow this  
daniel_i_l

checking quadtree code

This topic is 4496 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
Advertisement
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!