#include "quadtree.h"
#include "..\Utilities\util.h"
#include "camera.h"

#include "..\Utilities\XString.h"
#include "..\utilities\clock.h"

Quadtree::Quadtree(DWORD xl,DWORD yl)
{
	m_xl = xl;
	m_yl = yl;

	//clac size
	DWORD sx,sy,nx,ny;
	for (sx=1,nx=1;sx<xl;sx*=2,nx++);
	for (sy=1,ny=1;sy<yl;sy*=2,ny++);
	if(sx<sy)
	{
		m_Quadsize = sy;
		m_Levels = ny;
	}
	else
	{
		m_Quadsize = sx;
		m_Levels = nx;
	}

	m_Leaves = new QuadtreeNode*[m_Levels];

	for(DWORD l=0;l<m_Levels;l++)
	{
		DWORD n = (1 << (l << 1));
		m_Leaves[l] = new QuadtreeNode[n];
		ZeroMemory(m_Leaves[l],sizeof(QuadtreeNode)*n);
	}

	m_Root = m_Leaves[0];
	m_Root->x = 0;
	m_Root->y = 0;
	m_Root->size = (WORD)m_Quadsize;
	m_Root->visible = QTVT_NONE;
	m_Root->level = 0;

	DXVector3 n(0,0,1),b(0,1,0),t(1,0,0),o;

	D3DXVec3Cross(o, b, n);
	D3DXVec3Cross(o, n, t);

	if(m_Quadsize > 1)
	{
		InitChild(0,m_Root);
		InitChild(1,m_Root);
		InitChild(2,m_Root);
		InitChild(3,m_Root);
	}
	else
	{
		m_Root->childs[0] = NULL;
		m_Root->childs[1] = NULL;
		m_Root->childs[2] = NULL;
		m_Root->childs[3] = NULL;
	}
}

void Quadtree::InitChild(DWORD ind,QuadtreeNode*parent)
{
	DWORD nodex,nodey;
		
	if(ind == 0 || ind == 2)
		nodex = parent->x; 
	else
	{
		nodex = parent->x + parent->size/2;
		if(nodex >= m_xl)
		{
			parent->childs[ind] = NULL;
			return;
		}
	}

	if(ind == 0 || ind == 1)
		nodey = parent->y; 
	else
	{
		nodey = parent->y + parent->size/2;
		if(nodey >= m_yl)
		{
			parent->childs[ind] = NULL;
			return;
		}
	}

	DWORD size = parent->size/2;
	DWORD level = parent->level+1;
	QuadtreeNode* node = m_Leaves[level]+nodex/size+nodey/size*(int)pow(2.f,(int)level);
	node->x = (WORD)nodex;
	node->y = (WORD)nodey;
	node->size = (WORD)size;
	node->visible = QTVT_NONE;
	node->level = (WORD)level;

	parent->childs[ind] = node;

	if(node->size > 1)
	{
		InitChild(0,node);
		InitChild(1,node);
		InitChild(2,node);
		InitChild(3,node);
	}
	else
	{
		node->childs[0] = NULL;
		node->childs[1] = NULL;
		node->childs[2] = NULL;
		node->childs[3] = NULL;
	}
}

Quadtree::~Quadtree(void)
{
	for(DWORD l=0;l<m_Levels;l++)
	{
		SAFEDELETEARRAY(m_Leaves[l])
	}
	SAFEDELETEARRAY(m_Leaves)
}

void Quadtree::CalcVisible(const Camera &cam)
{
	DXVector3 dirtl,dirtr,dirbl,dirbr,v;
	D3DXMATRIX matInvView;
	D3DXMATRIX matProj = cam.GetProjMatrix();
	D3DXMatrixInverse( &matInvView, NULL, (D3DXMATRIX*)&cam.GetViewMatrix() );

	m_FarPlane = cam.GetFarPlane();

	if(m_FarPlane < 0.f)
	{
		SetNodeVT(m_Root, QTVT_NONE);
		return;
	}

	v.z =  1.0f;

	//topleft
	v.x = ( - 1 ) / matProj._11;
    v.y = ( + 1 ) / matProj._22;
    dirtl.x  = v.x*matInvView._11 + v.y*matInvView._21 + v.z*matInvView._31;
    dirtl.y  = v.x*matInvView._12 + v.y*matInvView._22 + v.z*matInvView._32;
    dirtl.z  = v.x*matInvView._13 + v.y*matInvView._23 + v.z*matInvView._33;

	//topright
	v.x = ( + 1 ) / matProj._11;
    v.y = ( + 1 ) / matProj._22;
    dirtr.x  = v.x*matInvView._11 + v.y*matInvView._21 + v.z*matInvView._31;
    dirtr.y  = v.x*matInvView._12 + v.y*matInvView._22 + v.z*matInvView._32;
    dirtr.z  = v.x*matInvView._13 + v.y*matInvView._23 + v.z*matInvView._33;

	//bottomleft
	v.x = ( - 1 ) / matProj._11;
    v.y = ( - 1 ) / matProj._22;
    dirbl.x  = v.x*matInvView._11 + v.y*matInvView._21 + v.z*matInvView._31;
    dirbl.y  = v.x*matInvView._12 + v.y*matInvView._22 + v.z*matInvView._32;
    dirbl.z  = v.x*matInvView._13 + v.y*matInvView._23 + v.z*matInvView._33;

	//bottomright
	v.x = ( + 1 ) / matProj._11;
    v.y = ( - 1 ) / matProj._22;
    dirbr.x  = v.x*matInvView._11 + v.y*matInvView._21 + v.z*matInvView._31;
    dirbr.y  = v.x*matInvView._12 + v.y*matInvView._22 + v.z*matInvView._32;
    dirbr.z  = v.x*matInvView._13 + v.y*matInvView._23 + v.z*matInvView._33;

	//0 = left, 1 = right, 2 = top, 3 = bottom, 4 = far
	//this vectors arent normalized, but thats no problem
	/*D3DXVec3Cross(m_CullNormals + 0,&dirtl,&dirbl); 
	D3DXVec3Cross(m_CullNormals + 1,&dirbr,&dirtr);
	D3DXVec3Cross(m_CullNormals + 2,&dirtr,&dirtl);
	D3DXVec3Cross(m_CullNormals + 3,&dirbl,&dirbr);*/
	D3DXVec3Normalize((D3DXVECTOR3*)(m_CullNormals + 0), D3DXVec3Cross((D3DXVECTOR3*)(m_CullNormals + 0), dirtl, dirbl)); 
	D3DXVec3Normalize((D3DXVECTOR3*)(m_CullNormals + 1), D3DXVec3Cross((D3DXVECTOR3*)(m_CullNormals + 1), dirbr, dirtr));
	D3DXVec3Normalize((D3DXVECTOR3*)(m_CullNormals + 2), D3DXVec3Cross((D3DXVECTOR3*)(m_CullNormals + 2), dirtr, dirtl));
	D3DXVec3Normalize((D3DXVECTOR3*)(m_CullNormals + 3), D3DXVec3Cross((D3DXVECTOR3*)(m_CullNormals + 3), dirbl, dirbr));
	m_CullNormals[4] = cam.GetViewDirVector();
	m_CullNormals[5] = -cam.GetViewDirVector();

	m_CamPos = cam.GetPosition();

	//for reverse box test (special case of checknode) we also need the corners of the frustum
	//just project corners of an indentity box with the inverse viewproj matrix
	static const DXVector3 Box[8] = 
		{DXVector3(-1,-1,0),DXVector3(1,-1,0),DXVector3(1,1,0),DXVector3(-1,1,0),
		DXVector3(-1,-1,1),DXVector3(1,-1,1),DXVector3(1,1,1),DXVector3(-1,1,1)};

	//build matrix
	D3DXMATRIX matInvViewProj;
	D3DXMatrixInverse(&matInvViewProj,NULL,D3DXMatrixMultiply(&matInvViewProj,(D3DXMATRIX*)&cam.GetViewMatrix(),(D3DXMATRIX*)&cam.GetProjMatrix()));

	//tranform all points
	D3DXVec3TransformCoordArray((D3DXVECTOR3*)m_FrustumPoints, sizeof(DXVector3),(D3DXVECTOR3*)Box, sizeof(DXVector3), &matInvViewProj, 8);

	m_Frustum.Update(cam);

	if(m_Root)
		CheckNode(m_Root);
}

void Quadtree::CheckNode(QuadtreeNode* const node)
{
	DWORD nvis = 0,pv[6][8]={0,0,0,0,0,0,0};
	ZeroMemory(pv,sizeof(DWORD)*6*8);


	//CClock clk;
	//clk.StartCapture(1);

	int i;

	/*for(int hk=0;hk<100000;++hk)
	{*/

	for(i=0;i<6;i++)
	{
		DWORD n=0;
		//if(PointVisible(DXVector3(node->box.GetMin().x,node->box.GetMin().y,node->box.GetMin().z),i))
		if(PointVisible(node->points[0],i))
		{
			pv[i][0]++;n++;
		}
		if(PointVisible(node->points[1],i))
		//if(PointVisible(DXVector3(node->box.GetMin().x,node->box.GetMin().y,node->box.GetMax().z),i))
		{
			pv[i][1]++;n++;
		}
		if(PointVisible(node->points[2],i))
		//if(PointVisible(DXVector3(node->box.GetMin().x,node->box.GetMax().y,node->box.GetMin().z),i))
		{
			pv[i][2]++;n++;
		}
		if(PointVisible(node->points[3],i))
		//if(PointVisible(DXVector3(node->box.GetMin().x,node->box.GetMax().y,node->box.GetMax().z),i))
		{
			pv[i][3]++;n++;
		}
		if(PointVisible(node->points[4],i))
		//if(PointVisible(DXVector3(node->box.GetMax().x,node->box.GetMin().y,node->box.GetMin().z),i))
		{
			pv[i][4]++;n++;
		}
		if(PointVisible(node->points[5],i))
		//if(PointVisible(DXVector3(node->box.GetMax().x,node->box.GetMin().y,node->box.GetMax().z),i))
		{
			pv[i][5]++;n++;
		}
		if(PointVisible(node->points[6],i))
		//if(PointVisible(DXVector3(node->box.GetMax().x,node->box.GetMax().y,node->box.GetMin().z),i))
		{
			pv[i][6]++;n++;
		}
		if(PointVisible(node->points[7],i))
		//if(PointVisible(DXVector3(node->box.GetMax().x,node->box.GetMax().y,node->box.GetMax().z),i))
		{
			pv[i][7]++;n++;
		}
		if(!n)//all points failed this plane
		{
			SetNodeVT(node,QTVT_NONE);
			return;
		}
	}
	/*}

	clk.EndCapture(1);
	LONGLONG t = clk.GetCaptureTime(1);
	double ft = t/(double)clk.GetTicksPerSec();
	
	MessageBox(0,XString((float)ft).getbuffer(),0,0);*/

	int j;
	{
		//try to find point that passed all tests
		for(i=0;i<8;i++)
		{
			for(j=0;j<6;j++)
			{
				if(!pv[j][i])
					break;
			}
			if(j == 6)
				break;
		}
		
		if(j<6)
		{
			//no point is visible and the points are behind different faces, so there is a chance that parts are visible
			//this case can occur if the box is bigger than the view frustum
			//also if just a side from the box cuts the frustum
			
//			OBS sphere(node->box.Center,D3DXVec3Length(&(node->box.GetMax()-node->box.GetMin()))*0.5f);
			//this test is always true ... ?
//			if(Intr_OBS_Frustum(sphere,m_Frustum))
			if(1)
			{
				node->visible = QTVT_PARTLY;
				if(node->childs[0])
					CheckNode(node->childs[0]);
				if(node->childs[1])
					CheckNode(node->childs[1]);
				if(node->childs[2])
					CheckNode(node->childs[2]);
				if(node->childs[3])
					CheckNode(node->childs[3]);
			}
			else
			{
				SetNodeVT(node,QTVT_NONE);
			}
		}
		else
		{
			//check if all points passed all tests
			for(i=0;i<8;i++)
			{
				for(j=0;j<6;j++)
				{
					if(pv[j][i])
						break;
				}
				if(j < 6)
					break;
			}

			if(i==8 && j==6)
			{
				SetNodeVT(node,QTVT_FULL);
			}
			else
			{
				node->visible = QTVT_PARTLY;
				if(node->childs[0])
					CheckNode(node->childs[0]);
				if(node->childs[1])
					CheckNode(node->childs[1]);
				if(node->childs[2])
					CheckNode(node->childs[2]);
				if(node->childs[3])
					CheckNode(node->childs[3]);
			}
		}
	}
}



void Quadtree::CalcVisible(const OBS& obs)
{

}

void Quadtree::CalcVisible(const OBB& obb)
{

}

void Quadtree::SetNodeVT(QuadtreeNode* const node,const QT_VISIBLETYPE vt)
{
	node->visible = vt;

	if(node->childs[0])
		SetNodeVT(node->childs[0],vt);
	if(node->childs[1])
		SetNodeVT(node->childs[1],vt);
	if(node->childs[2])
		SetNodeVT(node->childs[2],vt);
	if(node->childs[3])
		SetNodeVT(node->childs[3],vt);
}	

QuadtreeNode* Quadtree::GetLeaf(const DWORD level, const DWORD x, const DWORD y)
{
	if(level < m_Levels && x < (unsigned)(1<<(m_Levels-1)) && y < (unsigned)(1<<(m_Levels-1)))
		return m_Leaves[level]+x+y*(1<<level);
	else
		return NULL;
}

void Quadtree::SumChildNodes(QuadtreeNode* const node)
{
	if(!node->childs[0])
		return;

	DXVector3 minv(9.e20f,9.e20f,9.e20f),maxv(-9.e20f,-9.e20f,-9.e20f);

	for(int n=0;n<4;n++)
	{
		if(node->childs[n])
		{
			SumChildNodes(node->childs[n]);

			minv.x = _min(node->childs[n]->box.GetMin().x,minv.x);
			minv.y = _min(node->childs[n]->box.GetMin().y,minv.y);
			minv.z = _min(node->childs[n]->box.GetMin().z,minv.z);

			maxv.x = _max(node->childs[n]->box.GetMax().x,maxv.x);
			maxv.y = _max(node->childs[n]->box.GetMax().y,maxv.y);
			maxv.z = _max(node->childs[n]->box.GetMax().z,maxv.z);
		}
	}

	node->SetPoints(minv,maxv);
}
