#include "QuadTree.h"

QuadTree::QuadTree(const unsigned levels)
{
	m_Levels = levels;

	m_Leaves = new QuadTreeNode*[m_Levels];

	for (unsigned l = 0; l < m_Levels; l++)
	{
		unsigned n = (1 << (l << 1));
		m_Leaves[l] = new QuadTreeNode[n];
	}

	//link nodes
	for (unsigned l = 0; l < m_Levels - 1; l++)
	{
		for (unsigned y = 0; y < (1 << l); y++)
		{
			for (unsigned x = 0; x < (1 << l); x++)
			{
				QuadTreeNode* pNode = GetNode(l, x, y);
				pNode->m_Childs.Push(GetNode(l + 1, (x<<1), (y<<1)));
				pNode->m_Childs.Push(GetNode(l + 1, (x<<1)+1, (y<<1)));
				pNode->m_Childs.Push(GetNode(l + 1, (x<<1), (y<<1)+1));
				pNode->m_Childs.Push(GetNode(l + 1, (x<<1)+1, (y<<1)+1));
			}
		}
	}

	m_pRoot = m_Leaves[0];
}

QuadTree::~QuadTree(void)
{
	for (unsigned l = 0; l < m_Levels; l++)
	{
		delete [] m_Leaves[l];
	}
	delete [] m_Leaves;
}

void QuadTree::AddObject(SceneObject* const obj)
{
	//QuadTreeNode* n = ((QuadTree*)m_pSPT)->GetLeaf(px / 2049 * (1<<5), py / 2049 * (1<<5));
	//n->m_Objects.AddTail(obj, 0);
}

/*VISIBLETYPE QuadTreeNode::IsVisible(const Frustum& f)
{
	DWORD nvis = 0,pv[6+5][8]={0,0,0,0,0,0,0};
	ZeroMemory(pv,sizeof(DWORD)*(6+5)*8);

	int nplanes = f.planes.size();

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

	int i = 0;



	for (std::vector<DXPlane>::const_iterator it = f.planes.begin(); it != f.planes.end(); it++, i++)
	{
		DXPlane p = *it;
		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))
		if (it->DotCoord(m_Points[0]) > 0)
		{
			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))
		if (it->DotCoord(m_Points[1]) > 0)
		{
			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))
		if (it->DotCoord(m_Points[2]) > 0)
		{
			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))
		if (it->DotCoord(m_Points[3]) > 0)
		{
			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))
		if (it->DotCoord(m_Points[4]) > 0)
		{
			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))
		if (it->DotCoord(m_Points[5]) > 0)
		{
			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))
		if (it->DotCoord(m_Points[6]) > 0)
		{
			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))
		if (it->DotCoord(m_Points[7]) > 0)
		{
			pv[i][7]++;n++;
		}
		if(!n)//all points failed this plane
		{
			//SetNodeVT(node,QTVT_NONE);
			//return;
			return VT_NONE;
		}
	}


	//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<nplanes;j++)
			{
				if(!pv[j][i])
					break;
			}
			if(j == nplanes)
				break;
		}
		
		if(j<nplanes)
		{
			//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)
			{
				return VT_PARTLY;
				//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
			{
				return VT_NONE;
				//SetNodeVT(node,QTVT_NONE);
			}
		}
		else
		{
			//check if all points passed all tests
			for(i=0;i<8;i++)
			{
				for(j=0;j<nplanes;j++)
				{
					if(pv[j][i])
						break;
				}
				if(j < nplanes)
					break;
			}

			if(i==8 && j==nplanes)
			{
				return VT_FULL;
				//SetNodeVT(node,QTVT_FULL);
			}
			else
			{
				return VT_PARTLY;

				//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]);
			}
		}
	}
}*/