Jump to content
• Advertisement

# 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

##### Share on other sites
Advertisement

• Advertisement
• Advertisement

• ### Popular Contributors

1. 1
2. 2
3. 3
Rutin
16
4. 4
5. 5
• Advertisement

• 10
• 14
• 30
• 13
• 11
• ### Forum Statistics

• Total Topics
631788
• Total Posts
3002356
×

## 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!