#include "terrain.h"
#define PATCH_SIZE 64 //_MUST_ BE POWER OF 2!!! *Do not mess with*
#define RATIO (1.0f/4.0f) //Height map width and lenght resolution (x and y)
#define RESOL (1.0f/8.0f) //Height map height resolution (z)
#define HFLOATIZE(a) (static_cast<float>(a*RESOL)) //floatize height values from ushort
#define FLOATIZE(a) (a*RATIO) //convert from hMap pixels to world coordinates
#define UNFLOATIZE(a) (static_cast<unsigned int>(a/RATIO)) //convert from world coordinates do hMap pixels
#define LEFT  0
#define RIGHT 1

TERRAIN::TERRAIN(FILE* hmap, const unsigned int gtext, const unsigned int dettext, const unsigned int bumptext, const unsigned short resol)
{
	Erro("Started processing terrain at: ", ERR_TIME);
	__assume (hmap>0);
	detailThr=resol; //store detail threshold for current initialization
	//Load the heightmap
	fread(&sizex, sizeof(sizex), 1, hmap);
	fread(&sizey, sizeof(sizey), 1, hmap);
	fsizex=FLOATIZE(sizex);
	fsizey=FLOATIZE(sizey);
	__assume (sizex>PATCH_SIZE); __assume (sizey>PATCH_SIZE);
	hData=static_cast<unsigned short *>(malloc(sizex*sizey*sizeof(unsigned short)));
	if (hData==nullptr) Erro("Ran out of memory!", ERR_FATAL); //couldn't allocate memory for height data
	memset(hData, 0, sizex*sizey*sizeof(unsigned short));
	fread(hData, sizeof(unsigned short), sizex*sizey, hmap);

	//calculate number of patches per horizontal and vertical side
	__assume(sizex*PATCH_SIZE<255);
	__assume(sizey*PATCH_SIZE<255);
	hPatch=static_cast<unsigned char>(sizex/PATCH_SIZE); //# of patches on XX
	vPatch=static_cast<unsigned char>(sizey/PATCH_SIZE); //# of patches on YY

	//create the nodepool based on map size
	nodes=sizex*sizey/32;
	nodePool=new TreeNode[nodes];
	if (nodePool==nullptr) Erro("Ran out of memory!", ERR_FATAL);
	currNode=0;

	//Based on it's size, generate the Patch Pool. One PATCH every PATCH_SIZE pixels.
	patches=new PATCH*[hPatch*vPatch];
	if (patches==nullptr) Erro("Ran out of memory!", ERR_FATAL);
	//Next, init all the patches
	for (unsigned char Y=0; Y<vPatch; Y++)
		for (unsigned char X=0; X<hPatch; X++)
			patches[Y*hPatch+X]=new PATCH(X*PATCH_SIZE, Y*PATCH_SIZE, this);
	
	//save Texture ID's
	textGlobal=gtext; detalhe=dettext; bump=bumptext;
	Erro("Returning from terrain INIT: ", ERR_TIME);
	return; //terrain INIT complete
}

float TERRAIN::Height(const float fx, const float fy) const
{
	float x=fx; float y=fy;
	if ((x>=0)&&(y>=0)) return HFLOATIZE(Height(UNFLOATIZE(x), UNFLOATIZE(y)));
	return (0.0f);
}

inline unsigned short TERRAIN::Height(const unsigned int x, const unsigned int y) const
{
	if ((x<sizex)&&(y<sizey)) return (hData[y*sizex+x]);
	return 0;
}

void TERRAIN::Reset(const float fX, const float fY, const float fZ, const float rota, const float angle)
{
	currNode=0; //clear node counter
	PATCH *patch, *aux_patch;
	for (unsigned char row=0; row<vPatch; row++)
		for (unsigned char col=0; col<hPatch; col++)
		{
			patch=patches[row*hPatch+col];
			patch->Reset();
			patch->Cull(fX, fY, fZ, rota, angle); //set visibility flag on this patch
			if (patch->NeedsCalculation()) patch->CalcError();
			if (patch->IsVisible()) //bail on non-visible patches
				if (col>0)
				{
					aux_patch=patches[row*hPatch+col-1];
					patch->GetNode(LEFT)->lNeigh=aux_patch->GetNode(RIGHT);
				}
				else patch->GetNode(LEFT)->lNeigh=nullptr;
				if (col<(hPatch-1))
				{
					aux_patch=patches[row*hPatch+col+1];
					patch->GetNode(RIGHT)->lNeigh=aux_patch->GetNode(LEFT);
				}
				else patch->GetNode(RIGHT)->rNeigh=nullptr;
				if (row>0)
				{
					aux_patch=patches[(row-1)*hPatch+col];
					patch->GetNode(LEFT)->rNeigh=aux_patch->GetNode(RIGHT);
				}
				else patch->GetNode(LEFT)->rNeigh=nullptr;
				if (row<(vPatch-1))
				{
					aux_patch=patches[(row+1)*hPatch+col];
					patch->GetNode(RIGHT)->rNeigh=aux_patch->GetNode(LEFT);
				}
				else patch->GetNode(RIGHT)->rNeigh=nullptr;
		}
	return;
}

void TERRAIN::Update(const float cX, const float cY, const float cZ) //camara data
{
	PATCH *patch;
	const unsigned int cam_x=UNFLOATIZE(cX);
	const unsigned int cam_y=UNFLOATIZE(cY);
	const unsigned int cam_z=UNFLOATIZE(cZ);

	for (unsigned int i=0; i<(static_cast<unsigned int>(hPatch*vPatch)); i++)
	{
		patch=patches[i];
		if (patch->IsVisible()) patch->Update(cam_x, cam_y, cam_z);
	}
	return;
}

TERRAIN::TreeNode* TERRAIN::NewNode(void)
{
	if (currNode>=nodes) return nullptr; //no more nodes available
	TreeNode *ret=&nodePool[currNode]; //get a new node
	ret->lChild=ret->rChild=ret->bNeigh=ret->lNeigh=ret->rNeigh=nullptr; //clear new node's affiliations
	currNode++;
	return ret;
}

void TERRAIN::Render(void) const
{
	PATCH* patch;
	glBindTexture(GL_TEXTURE_2D, textGlobal);
	glColor4f(1.0f, 1.0f, 1.0f, 1.0f);
	glEnable(GL_TEXTURE_2D);
	for (unsigned short i=0; i<hPatch*vPatch; i++)
	{
		patch=patches[i];
		if (patch->IsVisible()) patch->Render();
	}
	return;
}

void TERRAIN::AuxRender(const TERRAIN::TreeNode *myNode,
							   const unsigned int fX, const unsigned int fY,
							   const unsigned int lX, const unsigned int lY,
							   const unsigned int rX, const unsigned int rY,
							   const unsigned int aX, const unsigned int aY) const
{
	if (myNode->lChild!=nullptr) //Am I split?
	{
		const unsigned int cX=(lX+rX)/2;
		const unsigned int cY=(lY+rY)/2; //render my children
		AuxRender(myNode->lChild, fX, fY, aX, aY, lX, lY, cX, cY);
		AuxRender(myNode->rChild, fX, fY, rX, rY, aX, aY, cX, cY);
	}
	else
	{
		glNormal3f(0.0f, 0.0f, 1.0f);
		glTexCoord2f(static_cast<float>((fX+aX)/this->fsizex), static_cast<float>((fY+aY)/this->fsizey));
		glVertex3f(FLOATIZE(aX), FLOATIZE(aY), HFLOATIZE(this->Height(aX+fX, aY+fY)));

		glNormal3f(0.0f, 0.0f, 1.0f);
		glTexCoord2f(static_cast<float>((fX+rX)/this->fsizex), static_cast<float>((fY+rY)/this->fsizey));
		glVertex3f(FLOATIZE(rX), FLOATIZE(rY), HFLOATIZE(this->Height(rX+fX, rY+fY)));

		glNormal3f(0.0f, 0.0f, 1.0f);
		glTexCoord2f(static_cast<float>((fX+lX)/this->fsizex), static_cast<float>((fY+lY)/this->fsizey));
		glVertex3f(FLOATIZE(lX), FLOATIZE(lY), HFLOATIZE(this->Height(lX+fX, lY+fY)));
	}
	return;
}

TERRAIN::~TERRAIN(void)
{
	//Confirm with the constructor the correct procedure to clean up memory
	PATCH *patch;
	for (unsigned int i=0; i<(static_cast<unsigned int>(hPatch*vPatch)); i++)
	{
		patch=patches[i];
		patch->~PATCH();
	}
	delete[] patches;
	patches=nullptr;
	free(hData);
	hData=nullptr;
	return;
}

/*********************************\
*         PATCH SUB-CLASS         *
\*********************************/
TERRAIN::PATCH::PATCH(const unsigned int x, const unsigned int y, TERRAIN *father)
{
	//Clear relationships
	Reset();
	needsCalc=true;
	//store my own coordinates
	xx=x; yy=y;
	//save my creator
	this->father=father;
	return; //we're done!
}

void TERRAIN::PATCH::Cull(const float fX, const float fY, const float fZ, const float rota, const float angle)
{
	glPushMatrix();
	glLoadIdentity();
	glRotatef(angle, -1.0f, 0.0f, 0.0f);
	glRotatef(rota, 0.0f, 0.0f, 1.0f);
	glTranslatef(FLOATIZE(xx)+fX, FLOATIZE(yy)+fY, fZ); //move into camera's position + patch coord
	frustum.Update(); //updates frustrum for current PATCH output
	static const float x[]={0.0f, FLOATIZE(PATCH_SIZE), 0.0f, FLOATIZE(PATCH_SIZE)};
	static const float y[]={0.0f, 0.0f, FLOATIZE(PATCH_SIZE), FLOATIZE(PATCH_SIZE)};
	const float z[]={HFLOATIZE(father->Height(xx, yy)), HFLOATIZE(father->Height(xx+PATCH_SIZE, yy)),
		HFLOATIZE(father->Height(xx, PATCH_SIZE+yy)), HFLOATIZE(father->Height(PATCH_SIZE+xx, PATCH_SIZE+yy))};
	isVisible=frustum.IsQuadInside(x, y, z);
	glPopMatrix(); 
	return;
}

void TERRAIN::PATCH::CalcError(void)
{
	//first, calculate error tree on the left side child
	cErr=lErr;
	Calculate(xx, yy+PATCH_SIZE, xx+PATCH_SIZE, yy, xx, yy, 1);
	//then, calculate error tree on the right side child
	cErr=rErr;
	Calculate(xx+PATCH_SIZE, yy, xx, yy+PATCH_SIZE, xx+PATCH_SIZE, yy+PATCH_SIZE, 1);
	needsCalc=false; //just updated!
	return;
}


unsigned short TERRAIN::PATCH::Calculate(
							   const unsigned int lX, const unsigned int lY,
							   const unsigned int rX, const unsigned int rY,
							   const unsigned int aX, const unsigned int aY,
							   const unsigned short node)
{
	const unsigned int cX=(rX+lX)/2; //center point of the hipotnuse
	const unsigned int cY=(rY+lY)/2;
	const unsigned short cZ=father->Height(cX, cY);
	const unsigned short rZ=father->Height(rX, rY);
	const unsigned short lZ=father->Height(lX, lY);
	unsigned short errRatio=static_cast<unsigned short>(abs(cZ-((lZ+rZ)/2))); //this iteraction's primary error ratio
	if (errRatio==0) return 0; //reached perfectness

	//as long as the triangle is bigger than a 2x2 square, keep calculating...
	if ((abs(static_cast<int>(rX-lX))>=2)||(abs(static_cast<int>(rY-lY))>=2))
	{
		//calculate the error of one of the child triangles
		unsigned short tempErrRatio=Calculate(aX, aY, lX, lY, cX, cY, node*2);
		if (errRatio<tempErrRatio) errRatio=tempErrRatio; //error is greater, adopt it
		//and then try the other child
		tempErrRatio=Calculate(rX, rY, aX, aY, cX, cY, node*2+1);
		if (errRatio<tempErrRatio) errRatio=tempErrRatio; //error is greater, adopt it
	}

	if (node<MAX_DEPTH) cErr[node]=errRatio; //store error ratio as we descend on the tree

	return errRatio; //return this node's error calculation
}

void TERRAIN::PATCH::Reset(void)
{
	//clear the visibility flag
	isVisible=true;
	//clear the node tree
	rNode.rNeigh=rNode.lNeigh=rNode.lChild=rNode.rChild=
	lNode.rNeigh=lNode.lNeigh=lNode.lChild=lNode.rChild=nullptr;
	//attach bottom nodes
	rNode.bNeigh=&lNode;
	lNode.bNeigh=&rNode;
	return;
}

void TERRAIN::PATCH::Update(const unsigned int camX, const unsigned int camY, const unsigned int camZ)
{
	cErr=lErr;
	Tesselate(&lNode, xx, yy+PATCH_SIZE, xx+PATCH_SIZE, yy, xx, yy, camX, camY, camZ, 1);
	cErr=rErr;
	Tesselate(&rNode, xx+PATCH_SIZE, yy, xx, yy+PATCH_SIZE, xx+PATCH_SIZE, yy+PATCH_SIZE, camX, camY, camZ, 1);
	return;
}

void TERRAIN::PATCH::Tesselate(TERRAIN::TreeNode *myNode,
							   const unsigned int lX, const unsigned int lY,
							   const unsigned int rX, const unsigned int rY,
							   const unsigned int aX, const unsigned int aY,
							   const unsigned int camX, const unsigned int camY,
							   const unsigned int camZ, const unsigned short node)
{
	const unsigned int cX=(rX+lX)/2; //centre point of the hipotenuse
	const unsigned int cY=(rY+lY)/2;
	const unsigned short cZ=father->Height(cX, cY);
	bool split=false; //should we split this patch?

	if (node<MAX_DEPTH) //not yet at the bottom
	{ //calculate square of distance
		const unsigned long dist=(cX-camX)*(cX-camX)+(cY-camY)*(cY-camY)+(cZ-camZ)*(cZ-camZ);
		const unsigned long threshold=(cErr[node]*father->detailThr)*(cErr[node]*father->detailThr);
#pragma warning(push)
#pragma warning(disable:4018) 
		split=threshold>dist; //if detail is greater than the distance
		//causes warning C4018: signed/unsigned mismatch, but both are unsigned... go figure...
#pragma warning(pop)
	}

	if (split)
	{
		Split(myNode);
		//If I have children and they aren't too small...
		if ((myNode->lChild!=nullptr)&&(myNode->rChild!=nullptr)&&((abs(static_cast<int>(lX-rX))>=2)||(abs(static_cast<int>(lY-rY))>=2)))
		{ //tesselate them both
			Tesselate(myNode->lChild, aX, aY, lX, lY, cX, cY, camX, camY, camZ, node*2);
			Tesselate(myNode->rChild, rX, rY, aX, aY, cX, cY, camX, camY, camZ, node*2+1);
		}
	}
	return;
}

void TERRAIN::PATCH::Split(TERRAIN::TreeNode *myNode)
{
	if (myNode->lChild!=nullptr) return; //already split

	//if the base Neighbour of my base Neighbour is not me, than I'm not a diamond with him
	if ((myNode->bNeigh!=nullptr)&&(myNode->bNeigh->bNeigh!=myNode))
	{
		Split(myNode->bNeigh); //split him, so that I can be split
		if (myNode->bNeigh->lChild==nullptr) return; //neighbour was not split, meaning we don't have more splits
	}

	TreeNode *rChld=father->NewNode(), *lChld=father->NewNode();
	if (lChld==nullptr) return; //not enough freenodes in pool to split
	//define Children's Neighbours
	myNode->lChild=lChld; myNode->rChild=rChld; 
	myNode->lChild->bNeigh=myNode->lNeigh; myNode->lChild->lNeigh=myNode->rChild;
	myNode->rChild->bNeigh=myNode->rNeigh; myNode->rChild->rNeigh=myNode->lChild;
	
	//link my neighbors to my children
	if (myNode->lNeigh!=nullptr) //do I have a left neighbour?
		if (myNode->lNeigh->bNeigh==myNode) myNode->lNeigh->bNeigh=myNode->lChild;
		else
			if (myNode->lNeigh->lNeigh==myNode) myNode->lNeigh->lNeigh=myNode->lChild;
			else if (myNode->lNeigh->rNeigh==myNode) myNode->lNeigh->rNeigh=myNode->lChild;

	if (myNode->rNeigh!=nullptr) //do I have a right neighbour?
		if (myNode->rNeigh->bNeigh==myNode) myNode->rNeigh->bNeigh=myNode->rChild;
		else if (myNode->rNeigh->rNeigh==myNode) myNode->rNeigh->rNeigh=myNode->rChild;
			else if (myNode->rNeigh->lNeigh==myNode) myNode->rNeigh->lNeigh=myNode->rChild;
	
	if (myNode->bNeigh!=nullptr) //do I have a base neighbour?
	{
		if (myNode->bNeigh->lChild!=nullptr)
		{
			myNode->bNeigh->lChild->rNeigh=myNode->rChild;
			myNode->bNeigh->rChild->lNeigh=myNode->lChild;
			myNode->lChild->rNeigh=myNode->bNeigh->rChild;
			myNode->rChild->lNeigh=myNode->bNeigh->lChild;
		}
		else Split(myNode->bNeigh); //Split base. Relations will be taken care of by this one.
	}
	else //I don't have a base neighbour, my children won't have a neighbour either
	{
		myNode->lChild->rNeigh=nullptr;
		myNode->rChild->lNeigh=nullptr;
	}		
	return;
}

bool TERRAIN::PATCH::IsVisible(void) const
{
	return isVisible;
}

bool TERRAIN::PATCH::NeedsCalculation(void) const
{
	return needsCalc;
}

TERRAIN::TreeNode* TERRAIN::PATCH::GetNode(const bool right)
{
	return (right ? &rNode : &lNode);
}

void TERRAIN::PATCH::Render(void) const
{
	glPushMatrix();
	glTranslatef(FLOATIZE(xx), FLOATIZE(yy), 0); //move into camera's position + patch coord
	glBegin(GL_TRIANGLES);
		father->AuxRender(&lNode, xx, yy, 0, PATCH_SIZE, PATCH_SIZE, 0, 0, 0);
		father->AuxRender(&rNode, xx, yy, PATCH_SIZE, 0, 0, PATCH_SIZE, PATCH_SIZE, PATCH_SIZE);
	glEnd();
	glPopMatrix();
	return;
}

TERRAIN::PATCH::~PATCH(void)
{
}

//SPECIAL TERRAIN METHOD

void TERRAIN::Where(const unsigned short mousex, const unsigned short mousey, float &x, float &y) const
{
	double proj[16], modl[16];
	int view[4];
	double objx=-1.0f, objy=-1.0f, objz=-1.0f;
	//retrieve plane data
	glGetDoublev(GL_PROJECTION_MATRIX, proj);
	glGetDoublev(GL_MODELVIEW_MATRIX, modl);
	glGetIntegerv(GL_VIEWPORT, view);
	//invert mouse YY coordinate
	gluUnProject(mousex, mousey, 0.5f, modl, proj, view, &objx, &objy, &objz);
	return;
}