rendered paste body// credit where credit is due on this one, most of it was borrowed from the tutorial on gamedev.net with a few modifications.
#include <stdlib.h>
#include <math.h>
#include <iostream>
using std::cout;
using std::cin;
float *fVerts;
unsigned int *uiList;
#define LEAF_TYPE 0
#define NODE_TYPE 1
typedef struct vertex{
float x,y,z;
}VERTEX;
class NODE{
int bType;
VERTEX vBoundingCoordinates[4];
unsigned int uiBranches[4];
unsigned int uiVertexStrip1[8];
unsigned int uiVertexStrip2[8];
unsigned int uiVertexStrip3[8];
unsigned int uiVertexStrip4[8];
unsigned int uiID;
unsigned int uiParentID;
}
NODE *pNodeList;
/* uiBoundingCoordinates[0] uiBoundingCoordinates[1]
*---------------------------|--------------------------*
*---------------------------|--------------------------*
uiBoundingCoordinates[2] uiBoundingCoordinates[3]
*/
void CreateNode(unsigned int Bounding[4],unsigned int ParentID,unsigned int NodeID) {
static unsigned int TotalTreeID = 0;
unsigned int uiNodeType;
float uiWidth,uiHeight;
uiWidth = fVerts[(Bounding[1]*3)] - fVerts[(Bounding[0]*3)];
uiHeight = fVerts[(Bounding[2]*3)+2] - fVerts[(Bounding[0]*3)+2];
if(0.5*uiWidth==2) {uiNodeType = LEAF_TYPE;}
else {uiNodeType = NODE_TYPE;}
NODE *pNode = &pNodeList[NodeID]; // pointer to parrent is pNodeList's address malloc'd memfor quadtree
pNode->uiID = NodeID;
pNode->uiParentID = ParentID;
for (int i=0; i < 4; i++) { //parrent NODE uiBounding coords
pNode->vBoundingCoordinates[i].x = fVerts[(Bounding[i]*3)];
pNode->vBoundingCoordinates[i].y = fVerts[(Bounding[i]*3)+1];
pNode->vBoundingCoordinates[i].z = fVerts[(Bounding[i]*3)+2];
}
pNode->bType = uiNodeType;
if(uiNodeType == LEAF_TYPE)
{return;}
else
{
unsigned int BoundingBox[4];
TotalTreeID++;
pNode->uiBranches[0] = TotalTreeID;
BoundingBox[0] = Bounding[0]; //Top-Left i.e. b[0]
BoundingBox[1] = Bounding[0]+((Bounding[1]-Bounding[0])/2); //Between b[0] and b[1]
BoundingBox[2] = Bounding[0]+((Bounding[2]-Bounding[0])/2); //[between b[0] and b[2]
BoundingBox[3] = Bounding[0]+((Bounding[2]-Bounding[0])/2)+((Bounding[1]-Bounding[0])/2); //middle of node
CreateNode(BoundingBox,NodeID,TotalTreeID);
//************************************************************************************************************
TotalTreeID++;
pNode->uiBranches[1] = TotalTreeID;
BoundingBox[0] = Bounding[0]+((Bounding[1]-Bounding[0])/2); // Between b[0] and b[1]
BoundingBox[1] = Bounding[1]; //Top-Right i.e. b[1]
BoundingBox[2] = Bounding[0]+((Bounding[2]-Bounding[0])/2)+((Bounding[1]-Bounding[0])/2); //middle of node
BoundingBox[3] = Bounding[0]+((Bounding[2]-Bounding[0])/2)+((Bounding[1]-Bounding[0])); //between b[1] & b[3]
CreateNode(BoundingBox,NodeID,TotalTreeID);
//************************************************************************************************************
TotalTreeID++;
pNode->uiBranches[2] = TotalTreeID;
BoundingBox[0] = Bounding[0]+((Bounding[2]-Bounding[0])/2); //between b[0] and b[2]
BoundingBox[1] = Bounding[0]+((Bounding[2]-Bounding[0])/2)+((Bounding[1]-Bounding[0])/2); //middle of node
BoundingBox[2] = Bounding[2]; //Bottom-Left i.e. b[2]
BoundingBox[3] = Bounding[2]+((Bounding[3]-Bounding[2])/2); //between b[2] and b[3]
CreateNode(BoundingBox,NodeID,TotalTreeID);
//************************************************************************************************************
TotalTreeID++;
pNode->uiBranches[3] = TotalTreeID;
BoundingBox[0] = Bounding[0]+((Bounding[2]-Bounding[0])/2)+((Bounding[1]-Bounding[0])/2); //middle of node
BoundingBox[1] = Bounding[0]+((Bounding[2]-Bounding[0])/2) + uiWidth; //between b[1] and b[3]
BoundingBox[2] = Bounding[2]+((Bounding[3]-Bounding[2])/2); //between b[2] and b[3]
BoundingBox[3] = Bounding[3]; //Bottom-Right i.e. b[3]
CreateNode(BoundingBox,NodeID,TotalTreeID);
}
}
void ReportNode(NODE *pNode,int TotalNodes) {
int child;
cout<<"Root Node ID: "<<pNode[0].uiID<<"\n";
for (int z=0; z < 4 ; z++) { //get the bounding coords
cout<<" X "<<pNode[0].vBoundingCoordinates[z].x;
cout<<" y "<<pNode[0].vBoundingCoordinates[z].y;
cout<<" z "<<pNode[0].vBoundingCoordinates[z].z<<"\n";
pNode[0].uiVertexStrip1[z];
}
for (int h=0; h < 4; h++){ //branches
cout<<h<<" Child \n";
for (int z=0; z < 4 ; z++) { //get the bounding coords
child = pNode[0].uiBranches[h];
cout<<" X "<<pNode[child].vBoundingCoordinates[z].x;
cout<<" y "<<pNode[child].vBoundingCoordinates[z].y;
cout<<" z "<<pNode[child].vBoundingCoordinates[z].z<<"\n";
}
}
for (int Nodes=1; Nodes < TotalNodes; Nodes+=5){
cout<<"Node ID: "<<pNode[Nodes].uiID<<"\n";
for (int h=0; h < 4; h++){ //branches
cout<<h<<" Child \n";
for (int z=0; z < 4 ; z++) { //get the bounding coords
child = pNode[Nodes].uiBranches[h];
cout<<" X "<<pNode[child].vBoundingCoordinates[z].x;
cout<<" y "<<pNode[child].vBoundingCoordinates[z].y;
cout<<" z "<<pNode[child].vBoundingCoordinates[z].z<<"\n";
}
}
}
}
void CreateGrid(unsigned int w,unsigned int h) {
unsigned int total=0;
unsigned int width = w;
unsigned int height = h;
fVerts = (float*)malloc((sizeof(float))*width*height*3); /* Allocate space for 20 vertices with an x,y and z*/
for(unsigned int ctr=0;ctr<height;ctr++)
{
for(unsigned int ctr2=0;ctr2<width;ctr2++)
{ // Vertex number is total
fVerts[total] = ctr2; // Vertex X component is ctr2
fVerts[total+1] = 0; // Vertex Y component is height field (0)
fVerts[total+2] = ctr; // Vertex Z component is ctr
total+=3; // Increase total to be next vertex number
}
}
total=0;
uiList = (unsigned int*)malloc((sizeof(unsigned int))*(width-1)*(height-1)*6);
for(unsigned int ctr=0;ctr < (height-1);ctr++) {
for(unsigned int ctr2=0;ctr2 < (width-1);ctr2++) {
//Triangles are built in twos, hence
//total+=6 to accomodate two sets of verts
uiList[total] = (ctr*width)+ctr2; //Triangle A's 1st vertex
uiList[total+1] = (ctr*width)+ctr2+width;
uiList[total+2] = (ctr*width)+ctr2+1;
uiList[total+3] = (ctr*width)+ctr2+width; //Triangle B's first vertex
uiList[total+4] = (ctr*width)+ctr2+width+1;
uiList[total+5] = (ctr*width)+ctr2+1;
total+=6; //Increase total by six, because we're using two tri's a loop
}
}
}
unsigned int CalcNodeNum(unsigned int max,unsigned int min) {
int ctr=0;
int var = 0;
while(var==0) {
ctr+=max;
max=max/min;
if(max==1)
{var=1;}
}
ctr++;
return ctr;
}
int main() {
float GridWidth; //Specified in squares/tris, not vertices
float GridHeight;
cout<<"Enter Grid Width: ";
cin>>GridWidth;
// GridWidth=8;
cout<<"\nEnter Grid Height: ";
// GridHeight=8;
cin>>GridHeight;
CreateGrid(GridWidth+1,GridHeight+1);
unsigned int Temp =(GridWidth/4)*(GridWidth/4); // devided into 4 sections ??
unsigned int Temp2 = CalcNodeNum(Temp,4); // max , min
cout<<Temp2;
pNodeList = (NODE*)malloc(sizeof(NODE)*Temp2); //pointer to a NODE allocated resources for NODEs
unsigned int uiBoundingCoordinates[] = {0,GridWidth,(GridHeight*(GridWidth+1)),((GridHeight)*(GridWidth+1))+GridWidth};
CreateNode(uiBoundingCoordinates,0,0);
ReportNode(pNodeList,Temp2);
cout<<"\nSize of tree: "<<sizeof(*pNodeList)*Temp2<<" bytes \ntotalnodes "<<Temp2<<"\n";
free(pNodeList);
free(fVerts);
free(uiList);
}