• Advertisement
Sign in to follow this  

Really Simple Quadtree Class in C++

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

  • Advertisement