// 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);



}