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



typedef struct 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;



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;


		//parrent NODE uiBounding coords
		for (int i=0; i < 4; i++){
			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){}	// if its the parrent node do nothing	

		else

		{	

		 unsigned int BoundingBox[4]; // maybe move this again later.--	


		  for (unsigned int i=0;i < 4;i++) {
			TotalTreeID++;



			pNode->uiBranches[i] = 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);
		  }

	 	}	

}







void ReportNode(NODE *pNode,int TotalNodes) {

int child;

cout<<"Root Node ID: "<<pNode[0].uiID<<"\n";
 cout<<"Node ID: "<<pNode[0].uiID<<"\n";

	for (int h=0; h < 4; h++) { //branches
		for (int z=0; z < 4 ; z++) //get the bounding coords
		{

		child = pNode[0].uiBranches[h];
		cout<<h<<" Child \n";
		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);



}