• Advertisement
Sign in to follow this  

Really Simple Quadtree Class in C++

This topic is 4163 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

Advertisement
You're right. That is extremely simple. You can't get any simpler than that. However, is it really a quadtree? [wink]

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
with occlusion culling builtin too. haha

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Works only with dimensions sized 0.

It is easily mutated into an OctTree(3D) and a TesseractTree(4D) (and any dimensions above that...)

Share this post


Link to post
Share on other sites
HA, HA. You guys are funny ;)

Actually, Gamedev wasn't working the day I posted this (I know, I tried several times, and even rebooted). Anyway, I'll try to post it again. Need to get the code, hold on...

Share this post


Link to post
Share on other sites
OK, Gamedev does not like my code, or perhaps it's not as simple as I thought (too big). So I'm going to try this in several posts...

Any criticisms, suggestions, etc, would be appreciated. Obviously, much more could be done to optimize this code. Right now, without any further optimization, on my 1.2 GH/512 MB RAM PC, I can get about 60 - 65 fps (with frustum culling), as opposed to the 15 - 20 I was getting trying to render everything brute force. Most of this code is adapted from several sources, most of which is from the Gamedev article found here. Anywa, here's the code:


terrainquadtree.h

#ifndef TERRAINQUADTREE_H
#define TERRAINQUADTREE_H
#define NOMINMAX
#pragma once

#define ROOT_TYPE 0
#define NODE_TYPE 1
#define LEAF_TYPE 2
#define SECTOR_TYPE 3

#define TOTALTERRAINVERTEXWIDTH 64 * 8
#define PATCHVERTEXWIDTH 64

struct node {
D3DXVECTOR3 vBoundingCoordinates[4];
D3DXVECTOR3 center;
float radius;
int Type;
int ID;
node *Child[4];

node () {
Type = NULL;
ID = NULL;
}
~node () {
Type = NULL;
ID = NULL;
}
};

class TerrainQuadTree {

public:
TerrainQuadTree();
node *CreateTerrainTree(D3DXVECTOR3 Bounding[4]);
void DrawTerrainTree(const node *pNode);
void DeleteTerrainTree (const node *pNode);
int numofnodesdrawn;
~TerrainQuadTree();
};

extern TerrainQuadTree *theTerrainTree;

#endif



[Edited by - mike_ix on August 30, 2006 2:40:37 PM]

Share this post


Link to post
Share on other sites
terrainquadtree.cpp

#include "terrainquadtree.h"

TerrainQuadTree::TerrainQuadTree() {

}
TerrainQuadTree::~TerrainQuadTree() {

}

void TerrainQuadTree::DeleteTerrainTree (const node *pNode) {

if (pNode->Child[0] != NULL) {
DeleteTerrainTree(pNode->Child[0]);
}
if (pNode->Child[1] != NULL) {
DeleteTerrainTree(pNode->Child[1]);
}
if (pNode->Child[2] != NULL) {
DeleteTerrainTree(pNode->Child[2]);
}
if (pNode->Child[3] != NULL) {
DeleteTerrainTree(pNode->Child[3]);
}
delete pNode;
return;

}

void TerrainQuadTree::DrawTerrainTree(const node *pNode) {


//Do culling here. Uncomment the code below to get a count of the recursion steps
/*
static int recursestep = 0;
char worda[40];
sprintf(worda, "%s%i", "The recurse step is: ", recursestep);
MessageBox(NULL, worda, "Yes!",
MB_ICONEXCLAMATION | MB_OK);
recursestep++;
*/


// Put frustum testing here: If bounding sphere/box is in frustum,
// then do code below, else return.

if (pNode == NULL) {
//MessageBox(NULL, "the node is null!", "Error!",
//MB_ICONEXCLAMATION | MB_OK);
return;
}
else if (pNode->Type == LEAF_TYPE) {
//MessageBox(NULL, "found a leaf!", "Error!",
//MB_ICONEXCLAMATION | MB_OK);


//Draw using the data in the leaf here!

return;
}
else {
DrawTerrainTree(pNode->Child[0]);
DrawTerrainTree(pNode->Child[1]);
DrawTerrainTree(pNode->Child[2]);
DrawTerrainTree(pNode->Child[3]);
}
return;

}

node *TerrainQuadTree::CreateTerrainTree(D3DXVECTOR3 Bounding[4])
{
static int leafcount = 0;
static int nodecount = 300;
static int sectornodecount = -1;
unsigned int uiNodeType;
D3DXVECTOR3 vecWidth = Bounding[1] - Bounding[0];
int intWidth = Bounding[1].x - Bounding[0].x;

node *temp;
temp = new node;

temp->vBoundingCoordinates[0] = Bounding[0];
temp->vBoundingCoordinates[1] = Bounding[1];
temp->vBoundingCoordinates[2] = Bounding[2];
temp->vBoundingCoordinates[3] = Bounding[3];

D3DXVECTOR3 vectemp = (Bounding[3] - Bounding[0]) * 0.5;
temp->radius = sqrt (pow(vectemp.x, 2) + pow(vectemp.z, 2));
temp->center = vectemp + Bounding[0];

if (intWidth==TOTALTERRAINVERTEXWIDTH) {
uiNodeType = ROOT_TYPE;
temp->ID = 0;
}
else if(intWidth==PATCHVERTEXWIDTH)
{
uiNodeType = LEAF_TYPE;
temp->ID = leafcount;
leafcount++;
}
else
{
uiNodeType = NODE_TYPE;
temp->ID = nodecount;
nodecount++;
}


temp->Type = uiNodeType;

if(uiNodeType == LEAF_TYPE)
{

//Fill leaf with data here

temp->Child[0] = NULL;
temp->Child[1] = NULL;
temp->Child[2] = NULL;
temp->Child[3] = NULL;
return(temp);
}
else
{
D3DXVECTOR3 BoundingBox[4];

BoundingBox[0] = Bounding[0];
BoundingBox[1] = Bounding[0]+((Bounding[1]-Bounding[0])/2);
BoundingBox[2] = Bounding[0]+((Bounding[2]-Bounding[0])/2);
BoundingBox[3] = Bounding[0]+((Bounding[2]-Bounding[0])/2)+((Bounding[1]-Bounding[0])/2);
temp->Child[0] = CreateTerrainTree(BoundingBox);

BoundingBox[0] = Bounding[0]+((Bounding[1]-Bounding[0])/2);
BoundingBox[1] = Bounding[1];
BoundingBox[2] = Bounding[0]+((Bounding[2]-Bounding[0])/2)+((Bounding[1]-Bounding[0])/2);
BoundingBox[3] = Bounding[0]+((Bounding[2]-Bounding[0])/2)+((Bounding[1]-Bounding[0]));
temp->Child[1] = CreateTerrainTree(BoundingBox);

BoundingBox[0] = Bounding[0]+((Bounding[2]-Bounding[0])/2);
BoundingBox[1] = Bounding[0]+((Bounding[2]-Bounding[0])/2)+((Bounding[1]-Bounding[0])/2);
BoundingBox[2] = Bounding[2];
BoundingBox[3] = Bounding[2]+((Bounding[3]-Bounding[2])/2);
temp->Child[2] = CreateTerrainTree(BoundingBox);

BoundingBox[0] = Bounding[0]+((Bounding[2]-Bounding[0])/2)+((Bounding[1]-Bounding[0])/2);
BoundingBox[1] = Bounding[0]+((Bounding[2]-Bounding[0])/2) + vecWidth;
BoundingBox[2] = Bounding[2]+((Bounding[3]-Bounding[2])/2);
BoundingBox[3] = Bounding[3];
temp->Child[3] = CreateTerrainTree(BoundingBox);

}
return(temp);
}

TerrainQuadTree createTree;
TerrainQuadTree *theTerrainTree = &createTree;


[Edited by - mike_ix on August 30, 2006 2:41:33 PM]

Share this post


Link to post
Share on other sites
To use this class, simply #include "terrainquadtree.h" in your application and set it like this:



D3DXVECTOR3 rootBounds[4];
rootBounds[0] = D3DXVECTOR3(0.0f, 0.0f, 0.0f);
rootBounds[1] = D3DXVECTOR3(TOTALTERRAINVERTEXWIDTH, 0.0f, 0.0f);
rootBounds[2] = D3DXVECTOR3(0.0f, 0.0f, TOTALTERRAINVERTEXWIDTH);
rootBounds[3] = D3DXVECTOR3(TOTALTERRAINVERTEXWIDTH, 0.0f, TOTALTERRAINVERTEXWIDTH);

node *root;
root = theTerrainTree->CreateTerrainTree(rootBounds);



then to draw, simply call:



theTerrainTree->DrawTerrainTree(root);


Share this post


Link to post
Share on other sites
Wouldn't uploading the code files have been easier? :)

Anyway, I've got some remarks on the code itself. Using some for loops would save you some typing there, making the code more maintainable as well. You generally have some large function bodies there for what it's really doing.
I'd use an enumeration for those _TYPE's rather than use #define. And I really don't see why you NULL those ints in the con- and destructor of the node struct. They get initialized at a default value anyway afaik. Otherwise, set them to 0 and don't worry about them in the destructor.
As for code style, I'd advise adopting a more consistent style, such as starting all class and struct names with Capitals and keeping variabele names lowercase. It'll be easier to read when you return to the code later on.

As for the design, I wouldn't hardcode the tree depth and node-count if I were you. It makes for some very inflexible code. Provide them as arguments to the CreateTerrainTree() function. Also, don't use a D3DXVECTOR3[4] for the bounding rectangle. What if i gave your code some random quadrilateral? Use two vectors instead. Whether one is the center and the other is a half-offset, or one is a corner and the other is a whole offset to the opposite corner is up to you. It's advisable to be consistent with this across your programs though, such things easily become confusing.
Also, have you considered writing a template quadtree class instead? Quadtrees can be usefull for collision detection and perhaps other situations as well, so writing one generic class for all these situations can be usefull.

Of course, that's just my point of view, and I can't guarantee my way is the best, but hopefully it helps you reconsider your design somewhat. :)

Share this post


Link to post
Share on other sites
I rewrote what you offered here. Functionally it is almost identical (so I dont think you'd get any real appreciable speed difference).

In the end the focus was on more encapsulation and a cleaner coding style.

quadtree.h

////////////////////////////////////////////////////////////

class cNode
{
public:
vec3 b[4], center;
cNode *child[4];
bool leaf;

cNode()
{
for (int i = 0; i < 4; ++i)
child = NULL;
leaf = false;
}
};

////////////////////////////////////////////////////////////

class cQuadTree
{
private:
cNode *root;
cNode *initNode(vec3 bound[4]);
void closeNode(const cNode *pcNode);
void renderNode(const cNode *pcNode);
unsigned int patchVertexSize;

public:
cQuadTree() { patchVertexSize = 0; root = NULL; }
~cQuadTree(){ if (root != NULL) delete root; }

void init(float size, unsigned int finalVertSize);
void render();
};

////////////////////////////////////////////////////////////




and quadtree.cpp

////////////////////////////////////////////////////////////

void getBounds(vec3 out[4], vec3 offset, float size, unsigned int i)
{
vec3 shift;

if (i == 1) shift = vec3(size, 0.0f, 0.0f);
else if (i == 2) shift = vec3(0.0f, 0.0f, size);
else if (i == 3) shift = vec3(size, 0.0f, size);

out[0] = offset + shift;
out[1] = offset + vec3(size, 0.0f, 0.0f) + shift;
out[2] = offset + vec3(0.0f, 0.0f, size) + shift;
out[3] = offset + vec3(size, 0.0f, size) + shift;
}

////////////////////////////////////////////////////////////

cNode *cQuadTree::initNode(vec3 bound[4])
{
float size = bound[1].x - bound[0].x;
unsigned int i;

cNode *newcNode = new cNode;
newcNode->center = (bound[3] - bound[0]) * 0.5 + bound[0];

for (i = 0; i < 4; ++i)
newcNode->b = bound;

if ((int)size == patchVertexSize)
{
newcNode->leaf = true;
//insert leaf data
}
else
{
vec3 b[4];
for (int i = 0; i < 4; ++i)
{
getBounds(b, bound[0], size/2.0f, i);
newcNode->child = initcNode(b);
}
}
return newcNode;
}

////////////////////////////////////////////////////////////

void cQuadTree::closeNode(const cNode *pcNode)
{
for (int i = 0; i < 4; ++i)
if (pcNode->child != NULL)
closecNode(pcNode->child);
delete pcNode;
}

////////////////////////////////////////////////////////////

void cQuadTree::renderNode(const cNode *pcNode)
{
if (pcNode == NULL)
return;

if (!pcNode->leaf)
for (int i = 0; i < 4; ++i)
rendercNode(pcNode->child);
else
{
//render leaf data
}
}

////////////////////////////////////////////////////////////

void cQuadTree::render()
{
rendercNode(root);
}

////////////////////////////////////////////////////////////

void cQuadTree::init(float size, unsigned int finalVertSize)
{
vec3 b[4];
patchVertexSize = finalVertSize;
getBounds(b, vec3(0.0f, 0.0f, 0.0f), size, 0);
root = initcNode(b);
}

////////////////////////////////////////////////////////////




note that I have taken out the initial requirement of specifying the bounds - this was intentional; as I see it, almost all applications of a quadtree would require a square shape (as opposed to some arbitrary quad)

also in this example we could put the quadtree::init code into the constructor instead (and it would probably be a bit cleaner) but I kept it seperated in case there was an issue of "timing" later down the line (ie the data to fill the leafs was not yet loaded etc)

depending on the end result you are looking for it may be better to initially construct this (within the constructor) and then add any data ("parsing" it as it comes down among the quadtree nodes and placing it within the correct nodes)

Another thing, if you wish to make this general purpose you are going to have to look at the possibility of a piece of leaf data spanning more than one node and evaluate what you want to do with it. It may be possible to split the data amongst the overlap, or to simply add the data to the node that encompasses it whilst maintaining the ability for other data to drop to the other node children - this would effectively allow nodes to contain leaf information as well as children.

so, anyway, to create the quadtree we simply do this:

cQuadTree qTree;
qTree.init(512, 64);
...
qTree.render();




If anyone has any questions / comments please share...

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement