#include "roam.h"
extern ViewFrustum * g_pFrustum ;
extern LPDIRECT3DDEVICE8	g_pD3dDev;
//***********************************************************************
//
//TriangleTreeNode implementation
//



//-----------------------------------------------------------------------
//
// statics members of the Triangle node
//

TriangleTreeNode *TriangleTreeNode::dpool=NULL;
TriangleTreeNode *TriangleTreeNode::spool=NULL; 
int	TriangleTreeNode::spmax=0; 
int TriangleTreeNode::psp=0;   
int TriangleTreeNode::dcnt=0;   



//-----------------------------------------------------------------------
//
// constructor
//
TriangleTreeNode::TriangleTreeNode()
{
	LChild=NULL;		
	index=0xffff;		
	lvar=1110;
	fov=1|0xfc;
	deff=0;
}

//-----------------------------------------------------------------------
//
// operator new handles allocating new node
//
void *TriangleTreeNode::operator new(size_t)
{
	TriangleTreeNode *p;

	if (dpool) 
	{ 
		//if there is smth in the dynamic pool get it form there
		p=dpool;
		//move to the next node in the pool
		dpool=dpool->DNeighbor; 
		dcnt--;
	}
	else 
	{ 
		//if dynamic pool is emtpy get it form static pool
		if (psp<spmax) 
		{
			p=spool+psp++;
		} 
		else
			throw MyException("Triangle Node Pool exhausted");
			//return NULL;
	}
	return p;
}

//-----------------------------------------------------------------------
//
// delete operator
//
// add node to the dynamic pool...
//
void TriangleTreeNode::operator delete(void *m)
{
	if (!m) return;
	//just insert in the dynamic pool
	((TriangleTreeNode *)m)->DNeighbor=dpool;
	dpool=(TriangleTreeNode *)m;
	dcnt++;
}

//-----------------------------------------------------------------------
//
// alocate memory for the static pool
//
bool TriangleTreeNode::Init(int nodesmax)
{
	//reinitialization...??!! ok  
	if (spmax) CleanUp(); 

	//size
	int sz=nodesmax*sizeof(TriangleTreeNode);
	
	//allocation
 	spool=(TriangleTreeNode *)malloc(sz); 

	//check for failure and exit
	if (spool) 
	{
		spmax=nodesmax;			
		psp=0;
	} 
	else 
		return false;

	return true;
}

//-----------------------------------------------------------------------
//
// frees the mem allocated for the pool
// static...
//
bool TriangleTreeNode::CleanUp()
{
	if (spmax) 
	{
		free(spool);
		spmax=0;
		Reset();
		return true;
	}
	return false;
}

//-----------------------------------------------------------------------
//
// reset dynamic and static pool
//
void TriangleTreeNode::Reset()
{
	dpool=NULL;
	psp=0;
	dcnt=0;
}

//-----------------------------------------------------------------------
//
// clears all indices in the allocated nodes...
//
void TriangleTreeNode::ClearIndices()
{
	for(int i=0;i<psp;i++) 
		spool[i].index=0xffff;
}

//-----------------------------------------------------------------------
//
// clears all Fov information in the allocated nodes...
//
void TriangleTreeNode::ClearFov()
{
	for(int i=0;i<psp;i++) 
		spool[i].fov=1|0xfc;
}

//***********************************************************************
//
// Patch class implementation
//
//-----------------------------------------------------------------------
//
// statics members of the Triangle node
//
BYTE * Patch::pb_mp = NULL;

//PC속도가 느릴 경우 이 값을 실시간으로 증가시키면 좋을 듯... by dhkwon, 단, WJ_VERTEXBUFFERSIZE값도 같이 변화되어야 한다.
float Patch::lVariance=0.5f;   // limit variance, 
//ViewFrustum Patch::frst;       // View frustrum.. 
int Patch::var_cnt;
int Patch::tvar=0;
int Patch::vcnt=0;			  //vertex counter
int Patch::tempcount=0;			  //vertex counter
CUSTOMVERTEX *Patch::pvert=0; //pointer to the vetrtices array
float Patch::hypo[32];        //hypotenuse precomputed
int Patch::sroam = 0;
float Patch::m_fMaxHeight = 0.0f;
float Patch:: m_fMin = 0.0f;
float Patch:: m_fMax = 0.0f;
//----------------------------------------------------------------------
//
// constructor
//
Patch::Patch() 
{
	//clear the neghbours of the patch
	m_Pup=m_Pdown=m_Pleft=m_Pright=NULL;

	//mirroring...
	mirrorx=0;
	mirrory=0;

	//other members
	m_map=NULL;
	m_dh=0;
	m_xoffset=0;
	m_yoffset=0;
	pind = NULL;
}

//-----------------------------------------------------------------------
//
// init function initializes the 
// member variables of width,height and offsets
//
bool Patch::Init(patchmap *map,int x_off,int y_off)
{
	m_map=map;
	m_xoffset=x_off;
	m_yoffset=y_off;

	//compute the m_dh and the xy factors
	m_dh=1<<(map->m_vd);

	//factors are used to calculate the texture coordinates
	xfac=1.0f/((float)(m_map->GetX())-1);
	yfac=1.0f/((float)(m_map->GetY())-1);

	//precompute the hypotenuse (see the artice occlusion section)
	hypo[0]=(float)map->GetX();
	for(int i=1;i<32;i++) hypo[i]=hypo[i-1]*0.7071067f;

	//reset the info in the base nodes
	Reset();	

	return true;
};

//-----------------------------------------------------------------------
//
// reset the indices in the Patch class...
// and base nodes..
//
void Patch::ClearIndices()
{
	m_RBase.index=0xffff;
	m_LBase.index=0xffff;
	itl=itr=idl=idr=0xffff;
}

//-----------------------------------------------------------------------
//
// clear the fov info in the base nodes
//
void Patch::ClearFov()
{
	m_RBase.fov=1|0xfc;
	m_LBase.fov=1|0xfc;
}

//-----------------------------------------------------------------------
//
// Reset
// reset creates connectivity information for the 
// base children of the patch
//
// connect the patch children to the children of the neighbor patches
// specified by the m_Pup,m_Pdown,m_Pleft,m_Pright
//
void Patch::Reset() 
{
	//clear starting relations
	m_LBase.RNeighbor=m_LBase.LNeighbor=m_RBase.RNeighbor=
	m_RBase.LNeighbor=NULL;
	m_LBase.RChild=m_LBase.LChild=m_RBase.RChild=
	m_RBase.LChild=NULL;
	
	m_RBase.Parent=m_LBase.Parent=NULL;

	//clear the indices
	ClearIndices();
	
	//attach both base children together
	m_LBase.DNeighbor=&m_RBase;
	m_RBase.DNeighbor=&m_LBase;

	//set identification information in order to span it down
	m_LBase.pid=pid;
	m_RBase.pid=pid;

	//connect to neighbor patches..
	if (m_Pup) 
		m_LBase.RNeighbor=&(m_Pup->m_RBase);
	
	if (m_Pdown) 
		m_RBase.RNeighbor=&(m_Pdown->m_LBase);

	if (m_Pleft)
		m_LBase.LNeighbor=&(m_Pleft->m_RBase);

	if (m_Pright)
		m_RBase.LNeighbor=&(m_Pright->m_LBase);
}

//-----------------------------------------------------------------------
//
// helper: computing of the heights during recurse compute variance
//
void Patch::CVup(int node)
{
	int m1=m_CVariance[node-1].height;
	int m2=m_CVariance[node].height;
	m_CVariance[node>>1].height=(unsigned char)maxm((float)m1,(float)m2)+1;
}

//-----------------------------------------------------------------------
//
// ComputeVariance 
// will use a recurse function to compute and fill 
// implicit variance trees for both nodes
//
void Patch::ComputeVariance()
{
	//set the current variance tree to the left
	m_CVariance=m_map->m_LVariance;

	int qy=m_map->GetY()-1;
	int qx=m_map->GetX()-1;

	//run the left recursion
	m_CVariance[0].var=(unsigned char)RecurseCV(0.0f,(float)qy,m_map->GetH(0,qy),
							(float)qx,0.0f,m_map->GetH(qx,0),
							0.0f,0.0f,m_map->GetH(0,0),1);

	//set the current variance tree to the right
	m_CVariance=m_map->m_RVariance;

	//run the right recursion
	m_CVariance[0].var=(unsigned char)RecurseCV((float)qx, 0.0f,m_map->GetH(qx,0),
						     0.0f ,(float)qy,m_map->GetH(0,qy),
							 (float)qx,(float)qy,m_map->GetH(qx,qy),
							 1);

	//ajust the final height value
	int m1=m_map->m_LVariance[1].height;
	int m2=m_CVariance[1].height;
	m_CVariance[0].height=(unsigned char)maxm((float)m1,(float)m2)+1;
	m_map->m_LVariance[0].height=m_CVariance[0].height;
}

//-----------------------------------------------------------------------
//
// RecurseCV
// recursively computes the variance as splitting
// the nodes
//
float Patch::RecurseCV(float lx,float ly,float lz,float rx,float ry,
		float rz,float ax,float ay,float az,int node)
{
	//the next split point is
	float cx=(lx+rx)*0.5f;
	float cy=(ly+ry)*0.5f;
	
	//the exact height at that point is
	float cz=GetH(cx,cy);

	//variance  
	float var=0;

	//the implicit tree 
	node<<=1; 
	if (node>m_dh*8) // test code
	{
		//we exceeded the depth of the tree so -> go up
		//calculate the maximum height for the current triangle
		m_CVariance[node>>1].height=(unsigned char)cGetMax(lz,rz,az)+1;
		return 0;   
	}

	//the variance is the sum of the recurse variance and current
	var=maxm(var,RecurseCV(ax,ay,az,lx,ly,lz,cx,cy,cz,node));
	node++;
	var=maxm(var,RecurseCV(rx,ry,rz,ax,ay,az,cx,cy,cz,node));

	//use the helper to adjust the heights
	CVup(node);

	//add the current variance
	//the hardcoded constant 4.0f has to be moved: TODO
	var+=ABS((float)cz-(lz+rz)*0.5f)*4.0f;

	//limit to a byte
	var=(var>255)?255:var;

	//put it in the variance tree -> implicit binary tree 
	//parent set -> node >> 1
	m_CVariance[node>>1].var=(unsigned char)var;

	return var; 
}

//-----------------------------------------------------------------------
//
// Split - does the work with the childnodes
//
// attaches them each to other as well as connects them with the neighbors...
//
// pretty same as in Bryan's article
//
void Patch::Split(TriangleTreeNode *tri)
{
	//if already split... 
	if (tri->LChild) return;

	//mark the patch as modified - > we introduce a split operation
	pb_mp[tri->pid]=1;

	//if this is not a diamond make it so by spliting base
	if (tri->DNeighbor && (tri->DNeighbor->DNeighbor != tri)) 
	{
		Split(tri->DNeighbor);
	}

	//crate nodes...
	tri->LChild=new TriangleTreeNode();
	tri->RChild=new TriangleTreeNode();

	//currently exception
	//if (!(tri->LChild))  //!!?? Handle thi situation !!!!!
	//	return;			 //TODO::: failed allocation

	//spawn the patch owner info to the children
	tri->RChild->pid=tri->LChild->pid=tri->pid;
	
	//parental info
	tri->LChild->Parent=tri;
	tri->RChild->Parent=tri;
	
	//attach neighbors
	tri->LChild->DNeighbor  = tri->LNeighbor;
	tri->LChild->LNeighbor  = tri->RChild;

	tri->RChild->DNeighbor  = tri->RNeighbor;
	tri->RChild->RNeighbor  = tri->LChild;

	//some special cases.... link neigbors to our children not us
	//left
	if (tri->LNeighbor != NULL)
	{
		if (tri->LNeighbor->DNeighbor == tri) //if the left nghb has us as base
			tri->LNeighbor->DNeighbor = tri->LChild;
		else if (tri->LNeighbor->LNeighbor == tri) //if the left ngb has us a left 
			tri->LNeighbor->LNeighbor = tri->LChild;
		else if (tri->LNeighbor->RNeighbor == tri) //if the left ngb has us a right 
			tri->LNeighbor->RNeighbor = tri->LChild;
		else ;// what the hell went wrong
	}

	//  Right 
	if (tri->RNeighbor != NULL)
	{
		if (tri->RNeighbor->DNeighbor == tri)
			tri->RNeighbor->DNeighbor = tri->RChild;
		else if (tri->RNeighbor->RNeighbor == tri)
			tri->RNeighbor->RNeighbor = tri->RChild;
		else if (tri->RNeighbor->LNeighbor == tri)
			tri->RNeighbor->LNeighbor = tri->RChild;
		else ;// Illegal Right Neighbor!
	}

	// down -base - a bit diferrent scheme
	if (tri->DNeighbor != NULL)
	{
		if (( tri->DNeighbor->LChild ) && (tri->DNeighbor->DNeighbor==tri)) //if has children
		{
			//link our children to his
			tri->DNeighbor->LChild->RNeighbor = tri->RChild;
			tri->DNeighbor->RChild->LNeighbor = tri->LChild;
			//link his to ours...
			tri->LChild->RNeighbor = tri->DNeighbor->RChild;
			tri->RChild->LNeighbor = tri->DNeighbor->LChild;
		}
		else
			Split( tri->DNeighbor);  // Base Neighbor (in a diamond with us) was not split yet, so do that now.
	}
	else
	{
		// An edge triangle, trivial case.
		tri->LChild->RNeighbor = NULL;
		tri->RChild->LNeighbor = NULL;
	}

}

//-----------------------------------------------------------------------
//
// GetVariance computes the variance
//
// has to be improved....
//
float Patch::GetVariance(float x,float y,float z,int node)
{
	var_cnt++;

	//vector A is a relative vector of the camera
	//to the point x,y,z and B is the same by with y 
	//latered with the variance
//	D3DXVECTOR3 A(x-g_pFrustum->cam.x,y-g_pFrustum->cam.y,z-g_pFrustum->cam.z);
//	D3DXVECTOR3 A(x-g_pFrustum->cam.x/40.078125f,y-g_pFrustum->cam.y*255/2000,z-g_pFrustum->cam.z/40.078125f);// by dhkwon map size*40
	D3DXVECTOR3 A(x-g_pFrustum->cam.x/40.078125f,y-(g_pFrustum->cam.y-Patch::m_fMin)/Patch::m_fMaxHeight*255.0f,z-g_pFrustum->cam.z/40.078125f);// by dhkwon 2011.4.4
	D3DXVECTOR3 B(A.x,A.y+m_CVariance[node].var*2.0f,A.z);

	//dot product of A B ... sqared
	float dt=D3DXVec3Dot(&A,&B);
		  dt*=dt; 

	//sqared lengths of A and B multiplied
	float t=D3DXVec3Dot(&A,&A);  
	float dv=t*D3DXVec3Dot(&B,&B);
	
	//cosine squared
	float cs=dt/dv; 
	float tn,m,c;

	//squared tang
	tn=(1-cs)/cs; 
	
	//variance metric type?
	if (tvar==1) 
	{		
		t=ABS(A.x)+ABS(A.y)+ABS(A.z);
		m=tn*1000.0f/t;
		c=m_CVariance[node].var*10.0f/t;
	}
	else 
	{		
		m=tn*100.0f;
		c=m_CVariance[node].var*0.1f;
	}

	if (tvar==2) 
	{
		m=0;
		c*=10.0f;
	}

	//combine components
	//m - is the metric... c is static component...
	return m+c;
}

//-----------------------------------------------------------------------
//
// RecursTesselate 
//
// tessellates and updates our landscape
//
void Patch::RecurseTesselate(TriangleTreeNode *tri,
							 int lx,  int ly,
							 int rx, int ry,
							 int ax,  int ay,
							 int node, BYTE binf )
{
	float var;

	//calculate the center point (eventual split one)
	int cx=(lx+rx)>>1;
	int cy=(ly+ry)>>1;

	//if there is some different FOV info in the fov member use it
	if (tri->fov!=(1|0xfc))
			binf=tri->fov;
	else 
	{
		//else compute the visibility
		if (binf&1) 
		{
			D3DXVECTOR3 vec=D3DXVECTOR3((float)(m_xoffset+cx),0.0f,(float)(m_yoffset+cy));
		
			//check for a cylinder with height from the binary tree
//			switch(g_pFrustum->IsCylinderUpIn(vec*40.078125f,hypo[l]*40.078125f,(float)m_CVariance[node>>1].height/255*2000,binf)) // by dhkwon map size*40
			switch(g_pFrustum->IsCylinderUpIn(vec*40.078125f,hypo[l]*40.078125f,(float)m_CVariance[node>>1].height/255.0f*Patch::m_fMaxHeight+Patch::m_fMin,binf)) // by dhkwon 2011.4.4
//			switch(g_pFrustum->IsCylinderUpIn(vec,hypo[l],m_CVariance[node>>1].height,binf))
			{
				case 0:
					//if completely out then MergeDown and return
					if (tri->LChild) 
						MergeDown(tri);
					return;

				case 2:
					//if completly in -> do not perform this check again for the children
					binf=0;
			}

			//if there is a base neighbor share the fov information with him
			if	(tri->DNeighbor!=NULL)
				if (tri->DNeighbor->DNeighbor==tri) 
					tri->DNeighbor->fov=binf;
		}
	}

	// check if we havent exceeded the binary tree dept then proceed otherwise exit 
	if (node<m_dh*8) // test code
	{

		//check metric computation defferal
		if (tri->deff) 
		{
			    //this computation is beeng defered, reuse the old variance
				var=tri->lvar;
				tri->deff--;
		}
		else 
		{
			//compute the real view dependent variance 
			var=GetVariance((float)(cx+m_xoffset),m_map->GetH(cx,cy),(float)(cy+m_yoffset),node);

			//store the varinace in the node and caluclate the frame deferal 
			tri->lvar=var;
			int d=(int)(ABS(var-lVariance)*5.0f); // 프레임 지연 공식 by dhkwon. 값이 커질수록 느려진다.
			d=d>255?255:d;
			tri->deff=d;
		}
	} 
	else 
	{
		return; 
	}

	//if our variance is above the limit then split
	if ((var>lVariance)) 
	{ 
		//split operation - for update it will just exit
		Split(tri);

		//go down in the implicit tree
		node<<=1;

		//recurse the left and right leafs
		if (tri->LChild) 
		{
			l++;
			RecurseTesselate(tri->LChild,ax,ay,lx,ly,cx,cy,node,binf);
			RecurseTesselate(tri->RChild,rx,ry,ax,ay,cx,cy,node+1,binf);
			l--;
		}
	} 
	else 
	{ 
		 	//if current variance is lower and this node is split...
			if (tri->LChild) 
				MergeDown(tri);
	}

}

//-----------------------------------------------------------------------
//
// IterateTesselate 
//
// tessellates and updates our landscape - iterative version
//
// I think Ihavent managed this well .. at least it does not
// run faster than the recursive one
//
void Patch::IterateTesselate(TriangleTreeNode *tri,
							 int lx,  int ly,
							 int rx,  int ry,
							 int ax,  int ay,
							 int node, BYTE binf )
{
	float var;
	
	//DWORD stack and stack pointer
	DWORD dwStack[640];
	DWORD wip=0;
	
	D3DXVECTOR3 vec(0,0,0);

	//helper macros for the stack push and pop
	//it is just type saving time... but it is baddd to the bone..
    #define SPUSH(x) dwStack[++wip]=(DWORD)(x)
    #define SPOP()	 dwStack[wip];wip--

	int cx;
	int cy;

	for(;;) 
	{
		cx=(lx+rx)>>1;
		cy=(ly+ry)>>1;
		if (tri->fov!=(1|0xfc))
			binf=tri->fov;
		else 
		{
			if (binf&1) 
			{
				vec.x=(float)(m_xoffset+cx);
				vec.z=(float)(m_yoffset+cy);
				switch(g_pFrustum->IsCylinderUpIn(vec,hypo[l],m_CVariance[node>>1].height,binf)) 
				{
					case 0:
						if (tri->LChild) MergeDown(tri);
						goto localret;
					case 2:
						binf=0;
				}
			if	(tri->DNeighbor!=NULL)
				if (tri->DNeighbor->DNeighbor==tri) tri->DNeighbor->fov=binf;
			}
		}

		if (node<m_dh*8) // test code
		{
				if (tri->deff) 
				{
					var=tri->lvar;
					tri->deff--;
				}
				else 
				{
					var=GetVariance((float)(cx+m_xoffset),m_map->GetH(cx,cy),(float)(cy+m_yoffset),node);
					tri->lvar=var;
					int d=(int)(ABS(var-lVariance)*5.0f);// 프레임 지연 공식 by dhkwon. 값이 커질수록 느려진다.
					d=d>255?255:d;
					tri->deff=d;
				}
		} 
		else 
		{
			goto localret; //if exceeded the variance depth just exit
		}

		if ((var>lVariance)) 
		{  //if obove the allowed variance then go down..
			Split(tri);
			node<<=1;
			if (tri->LChild) 
			{
				l++;
				SPUSH(tri->LChild);
				SPUSH(ax);
				SPUSH(ay);
				SPUSH(lx);
				SPUSH(ly);
				SPUSH(cx);
				SPUSH(cy);
				SPUSH(node);
				SPUSH(binf);
				SPUSH(l);

				SPUSH(tri->RChild);
				SPUSH(rx);
				SPUSH(ry);
				SPUSH(ax);
				SPUSH(ay);
				SPUSH(cx);
				SPUSH(cy);
				SPUSH(node+1);
				SPUSH(binf);
				SPUSH(l);
			}
		} 
		else 
		{ //if current variance is bigger and this node is split...
			if (tri->LChild) 
				MergeDown(tri);
		}
	localret:
		if (wip==0) break;

		l=(BYTE)SPOP();
	    binf=(BYTE)SPOP();
		node=SPOP();
		ay=SPOP();
		ax=SPOP();
		ry=SPOP();
		rx=SPOP();	
		ly=SPOP();
		lx=SPOP();
		tri=(TriangleTreeNode *)SPOP();
	}

}

//-----------------------------------------------------------------------
//
// Tessellates/updates the patch
// runs recurse tesselate function
//
void Patch::Tesselate() 
{
	l=0;
	m_CVariance=m_map->m_LVariance;
	RecurseTesselate(&m_LBase,0,m_map->GetY()-1,
						  m_map->GetX()-1 ,0,
						  0		,0,
						  1,(sroam)?0:1|0xfc);
	l=0;
	m_CVariance=m_map->m_RVariance;
	RecurseTesselate(&m_RBase,m_map->GetX()-1 ,0,
						  0		,m_map->GetY()-1,
						  m_map->GetX()-1 ,m_map->GetY()-1,
						 1,(sroam)?0:1|0xfc);

}

//-----------------------------------------------------------------------
//
// Tessellates/updates the patch
// runs iterative tesselate function
//
void Patch::ITesselate() 
{
	l=0;
	m_CVariance=m_map->m_LVariance;
	IterateTesselate(&m_LBase,0,m_map->GetY()-1,
						  m_map->GetX()-1 ,0,
						  0		,0,
						  1,1|0xfc);
	l=0;
	m_CVariance=m_map->m_RVariance;	
	IterateTesselate(&m_RBase,m_map->GetX()-1 ,0,
						  0		,m_map->GetY()-1,
						  m_map->GetX()-1 ,m_map->GetY()-1,
						 1,1|0xfc);

}

//-----------------------------------------------------------------------
//
// recurse render follows the logical structure and costructs the vertex 
// and index info... adding verteces to the vertex buffer and indices to 
// the index one...
//
void Patch::RecurseRender(TriangleTreeNode *tri,
							 int lx,  int ly,
							 int rx,  int ry,
							 int ax,  int ay,
							 WORD *il,WORD *ir,WORD *ia, BYTE binf,int node)	// binf, node 사용안함. by dhkwon
{
	
	int cx=(lx+rx)>>1;
	int cy=(ly+ry)>>1;

	//are there any children?
	if (tri->LChild!=NULL) 
	{ 
		

		//traverse the children
		node<<=1;
		l++;
			RecurseRender(tri->LChild,ax,ay,lx,ly,cx,cy,ia,il,&(tri->index),binf,node);
			RecurseRender(tri->RChild,rx,ry,ax,ay,cx,cy,ir,ia,&(tri->index),binf,node+1);
		l--;

		//share the aquired index information with our base neighbor
		if (tri->DNeighbor)
			if (tri->DNeighbor->DNeighbor==tri) //if is our diamond
//				if (tri->DNeighbor->index==0xffff) 
					tri->DNeighbor->index=tri->index;
		
	}
	else 
	{ 
	

		//leaf - let us view it 
		if (*il==0xffff) 		
			*il=PutVertex((float)(lx+m_xoffset),m_map->GetH(lx,ly),(float)(ly+m_yoffset),(float)lx*xfac,(float)ly*yfac);	
	
		
			
		if (*ir==0xffff) 		
			*ir=PutVertex((float)(rx+m_xoffset),m_map->GetH(rx,ry),(float)(ry+m_yoffset),(float)rx*xfac,(float)ry*yfac);			
	
		
			
		if (*ia==0xffff) 		
			*ia=PutVertex((float)(ax+m_xoffset),m_map->GetH(ax,ay),(float)(ay+m_yoffset),(float)ax*xfac,(float)ay*yfac);		
	
			
		

		
		PutTriIndeces(*ia,*ir,*il);
	

	}
}




//-----------------------------------------------------------------------
//
// PutTriIndeces insert the tree indeces of the triangle
// into the index buffer...
//
inline void Patch::PutTriIndeces(WORD i1,WORD i2,WORD i3)
{
	pind[icnt]=i1;
	pind[++icnt]=i2;
	pind[++icnt]=i3;
	++icnt;

	
	
}

//-----------------------------------------------------------------------
//
// adds a new vertex in the vertex array and returns the index
//
inline WORD Patch::PutVertex(float x,float y,float z,float tu,float tv)
{
	pvert[vcnt].position.x=x*40.078125f;// by dhkwon map size*40
//	pvert[vcnt].position.y=y/255*2000;// by dhkwon map size*40
	pvert[vcnt].position.y=y/255.0f*Patch::m_fMaxHeight+Patch::m_fMin;// by dhkwon 2011.4.4
	pvert[vcnt].position.z=z*40.078125f;// by dhkwon map size*40

	pvert[vcnt].color=0xffffffff;
	

	//check for mirroring and mirror the texture cordinates
	if (mirrorx) 
		pvert[vcnt].tu=1.0f-tu;
	else 
		pvert[vcnt].tu=tu;

	if (mirrory)
		pvert[vcnt].tv=1.0f-tv;
	else
		pvert[vcnt].tv=tv;

	return vcnt++;
}

//-----------------------------------------------------------------------
//
// calls recursive render funcs - initial render /reset
//
void Patch::Render() {

	l=0;
	float qx=(float)(m_map->GetX()-1);
	float qy=(float)(m_map->GetY()-1);

	//set the current variance to the left and run a left traversal...
	m_CVariance=m_map->m_LVariance;
	RecurseRender(&m_LBase,0				,m_map->GetY()-1,
						  m_map->GetX()-1 ,0,
						  0,0,
						  &idl,&itr,&itl,1|0xfc,1);
	l=0;
	//set the current variance to the right and run a right traversal...
	m_CVariance=m_map->m_RVariance;
	RecurseRender(&m_RBase,m_map->GetX()-1 ,0,
						  0,m_map->GetY()-1,
						  m_map->GetX()-1 ,m_map->GetY()-1,
						  &itr,&idl,&idr,1|0xfc,1);

	//update indices of the neighbor patches...
	//in the corners the patches share their vertices..
	//this is some how tedious but cant be avoided...
	if (m_Pup) {
		if (m_Pup->idl==0xffff)
					m_Pup->idl=itl;
		if (m_Pup->idr==0xffff)
					m_Pup->idr=itr;

		if (m_Pup->m_Pleft) 
			if (m_Pup->m_Pleft->idr==0xffff)
				m_Pup->m_Pleft->idr=itl;

		if (m_Pup->m_Pright) 
			if (m_Pup->m_Pright->idl==0xffff)
				m_Pup->m_Pright->idl=itr;

	}
	if (m_Pdown) {
		if (m_Pdown->itr==0xffff)
					m_Pdown->itr=idr;
		if (m_Pdown->itl==0xffff)
					m_Pdown->itl=idl;

		if (m_Pdown->m_Pleft)
			if (m_Pdown->m_Pleft->itr==0xffff)
				m_Pdown->m_Pleft->itr=idl;

		if (m_Pdown->m_Pright)
			if (m_Pdown->m_Pright->itl==0xffff)
				m_Pdown->m_Pright->itl=idr;

	}
	if (m_Pleft) {
		if (m_Pleft->itr==0xffff)
					m_Pleft->itr=itl;
		if (m_Pleft->idr==0xffff)
					m_Pleft->idr=idl;

		if (m_Pleft->m_Pup)
			if (m_Pleft->m_Pup->idr==0xffff)
				m_Pleft->m_Pup->idr=itl;

		if (m_Pleft->m_Pdown)
			if (m_Pleft->m_Pdown->itr==0xffff)
				m_Pleft->m_Pdown->itr=idl;

	}
	if (m_Pright) {
		if (m_Pright->itl==0xffff)
					m_Pright->itl=itr;
		if (m_Pright->idl==0xffff)
					m_Pright->idl=idr;

		if (m_Pright->m_Pup)
			if (m_Pright->m_Pup->idl==0xffff)
				m_Pright->m_Pup->idl=itr;

		if (m_Pright->m_Pdown)
			if (m_Pright->m_Pdown->itl==0xffff)
				m_Pright->m_Pdown->itl=idr; 
	}
	
}

//-----------------------------------------------------------------------
//
// GoodForMerge determines if this node's children are leaves and whether
// they are ready to be merged (i.e. the variance is high enough)
//
bool Patch::GoodForMerge(TriangleTreeNode *tri)
{
	//already merged?
	if (tri->LChild==NULL)
		return false; 

	//lvar is more than the desired variance...this is not good
	//in case of fov.. lvar is 0
	if (tri->lvar>lVariance) 
		return false;

	//there are no grandchildren
	if ((tri->LChild->LChild==NULL)&& 
		(tri->RChild->LChild==NULL))
		return true;
	
	return false;
}

//-----------------------------------------------------------------------
//
// merge down goes down in the tree and when leafs are found they are 
// deleted so the parent node remains
//
void Patch::MergeDown(TriangleTreeNode *tri)
{
	if (tri->LChild==NULL) return; //leaf!!??

	//clear the information for the variance 
	//merge down occurs mainly due to fov info...
	tri->lvar=0;
	tri->deff=0;

	//good for merge
	if (GoodForMerge(tri)) 
	{
		//we are about to merge - check the neighbor if we have a diamont
		if (tri->DNeighbor==NULL) 
		{
			//no diamond
			//at the border - trivial  merge
			Merge(tri);  
		} 
		else 
		{
			// diamond!!!
			// check the base for good children...
			if (GoodForMerge(tri->DNeighbor))  
			{
				Merge(tri->DNeighbor);
				Merge(tri);
				return;
			}
			else ; // base diamond neighbor is not ready for merge...
			return;
		}
		return;
	}

	//merge down until we find some leafs 
	MergeDown(tri->LChild);
	MergeDown(tri->RChild);
}

//-----------------------------------------------------------------------
//
// merges the children of the spcified triangle node and "frees" the memory
//
void Patch::Merge(TriangleTreeNode *tri)
{
	//set patch modified flag to true
	pb_mp[tri->pid]=1;

	//keep the connectivity information prior to deleteing nodes

	//get the base neighbor of the left child and connect to parent...
	if (tri->LChild->DNeighbor) {
		if (tri->LChild->DNeighbor->LNeighbor==tri->LChild)
			tri->LChild->DNeighbor->LNeighbor=tri;
		if (tri->LChild->DNeighbor->RNeighbor==tri->LChild)
			tri->LChild->DNeighbor->RNeighbor=tri;
		if (tri->LChild->DNeighbor->DNeighbor==tri->LChild) 
		{
			tri->LChild->DNeighbor->DNeighbor=tri;
			if (tri->LNeighbor == tri->LChild->DNeighbor->Parent)
				tri->LNeighbor=tri->LChild->DNeighbor;
		}
		
		//parent of the base neighbor of the left child should be 
		//checked
		TriangleTreeNode *par=tri->LChild->DNeighbor;
		
		//if there is such parent 
		if (par=par->Parent) 
		{
			if (par->LNeighbor==tri->LChild)
				par->LNeighbor=tri;
			if (par->RNeighbor==tri->LChild)
				par->RNeighbor=tri;
			if (par->DNeighbor==tri->LChild)
				par->DNeighbor=tri;
		}
	}
	
	//same for the rchild
	if (tri->RChild->DNeighbor) 
	{
		if (tri->RChild->DNeighbor->LNeighbor==tri->RChild)
			tri->RChild->DNeighbor->LNeighbor=tri;
		if (tri->RChild->DNeighbor->RNeighbor==tri->RChild)
			tri->RChild->DNeighbor->RNeighbor=tri;
		if (tri->RChild->DNeighbor->DNeighbor==tri->RChild) 
		{
			tri->RChild->DNeighbor->DNeighbor=tri;
			if (tri->RNeighbor == tri->RChild->DNeighbor->Parent)
				tri->RNeighbor=tri->RChild->DNeighbor;
		}

		TriangleTreeNode *par=tri->RChild->DNeighbor;
		if (par=par->Parent) 
		{ 
			if (par->LNeighbor==tri->RChild)
				par->LNeighbor=tri;
			if (par->RNeighbor==tri->RChild)
				par->RNeighbor=tri;
			if (par->DNeighbor==tri->RChild)
				par->DNeighbor=tri;
		}
	}

	//"delete" the nodes		
	delete(tri->LChild);
	delete(tri->RChild);

	//make the current node a "leaf"
	tri->LChild=NULL;
	tri->RChild=NULL;
}


//***********************************************************************
//
// Terrain class implementation
//
//-----------------------------------------------------------------------
//
// statics members 
//
int Terrain::q_childc[4][2]={{0,0},{1,0},{0,1},{1,1}};
float Terrain::side=64.0f;

//-----------------------------------------------------------------------
//
// constructore (may be italian for constuctor!!??)
//
Terrain::Terrain()
{
	//set the directx stuff to null
	m_pd3dDevice=NULL;
	m_pVB=NULL;

	strcpy(texname,"texture");
	iResolution=128;
	iNumMips=1;
}

//-----------------------------------------------------------------------
//
// destructore
//
Terrain::~Terrain()
{
	ClearDevices();	
}

//-----------------------------------------------------------------------
//
// Init 
//
// loads the map and initilizes the terrain class
//
void Terrain::Init(float* pfHeightMap, float fMaxHeight, int nWidth, int nHeight)
{
	bmap.Load(pfHeightMap, fMaxHeight, nWidth, nHeight);
	Init(NULL);
}

void Terrain::Init(char *szMap)
{
	int d, l;

	//load the bmp
	if(szMap) // NULL일 경우는 Init(float* pfHeightMap, int nWidth, int nHeight) 함수 이용.
		bmap.Load(szMap);

	//number of patches
	d=(int)((float)bmap.GetWidth()/side);

	//calculate levels
	l=0;
	for(int q=1;q<d;q*=2,l++);		// 버그 수정 by dhkwon

	//initializes members
	m_dp=d;
	m_md=d*d;
	m_lv=l;

	//allocate space for the patches modifier flags
	Patch::pb_mp=new BYTE [d*d];
	
	//create patches, 한번에 배열로 만들면 더 좋을듯.by dhkwon
	for(int c=0;c<d*d;c++) 
	{
		m_Patches[c]=new Patch();
		m_Patches[c]->pid=c;
	}

	//initialize patches... create a patch map for each
	BYTE mirx=0,miry=0;
	for(int j=0;j<d;j++,miry=j&1)
		for(int i=0;i<d;i++,mirx=i&1) 
		{
			//attach patch neighbors in the grid
			if (j!=0) 
				m_Patches[i+j*d]->m_Pup=(m_Patches[i+(j-1)*d]);
			if (j!=d-1) 
				m_Patches[i+j*d]->m_Pdown=(m_Patches[i+(j+1)*d]);
			if (i!=0) 
				m_Patches[i+j*d]->m_Pleft=(m_Patches[i-1+j*d]);
			if (i!=d-1) 
				m_Patches[i+j*d]->m_Pright=(m_Patches[i+1+j*d]);

			//create the bmpatch (map)
			bmpatch *bp=new bmpatch(bmap.pbmap,i*(int)side,j*(int)side,bmap.GetWidth(),bmap.GetHeight(),(int)side);

			//init the patch
//			m_Patches[i+j*d]->Init(bp,i*(int)side-((int)side*d/2),j*(int)side-((int)side*d/2)); // by dhkwon 100728 이 코드는 (0,0)이 중심.
			
			m_Patches[i+j*d]->Init(bp,i*(int)side,j*(int)side); // by dhkwon 100728 (0,0)이 시작점.
			m_Patches[i+j*d]->mirrorx=(i&1);
			m_Patches[i+j*d]->mirrory=(d-j)&1;//miry;// org: (d-1-j)
			m_Patches[i+j*d]->ComputeVariance(); 

			//textures 
			char szt[MAX_PATH];
			//sprintf(szt,"%s%dat%dx%d.bmp",texname,iResolution,i,j);
//			sprintf(szt,"%s%02d.jpg",texname,(d-1-i)+j*d);
			sprintf(szt,"%s%02d.jpg",texname,i+(d-1-j)*d);
			//sprintf(szt,"map%02d",i+j*d>15?15:i+j*d);

			//8192 is highly exaggerated - usualy they are under 2048.... 뭔가 있다. by dhkwon
			WORD id = g_texture.AddTexture(szt,8192);

			if (id==0xffff) 
			{
				//throw MyException("Texture missing");
				m_Patches[i+j*d]->texID=i+(d-1-j)*d;
			}
			else
				m_Patches[i+j*d]->texID=id;

		
		}

	//create the quad tree
//	CreateQuad(1,l,0,0,0,0,m_qmaxh[1]);// by dhkwon 100728 이 코드는 (0,0)이 중심.
	CreateQuad(1,l,bmap.GetWidth()/2,bmap.GetWidth()/2,0,0,m_qmaxh[1]);// by dhkwon 100728 (0,0)이 시작점.
}

//-----------------------------------------------------------------------
//
// Resets for new tessselation
//
void Terrain::Reset(void) {
	TriangleTreeNode::Reset();
	for(int j=0;j<m_md;j++)
			m_Patches[j]->Reset();
}

//-----------------------------------------------------------------------
//
// create quad fills the infromation into the m_qmaxh quadratic 
// implicit tree of heights for the purpose of occlusion
//
void Terrain::CreateQuad(int l,int levels,float cx,float cy,int ix,int iy,float &maxh)
{
	if (levels==0) 
	{
		// leaf - get the maximum height in the patch
		m_Patches[ix+iy*m_dp]->GetMaxH(maxh);
	}
	else 
	{
		//proceed with children
		float fqside=(float)(1<<levels)*side;
		levels--;
		fqside*=0.25f;

		//for each child
		for(int i=0;i<4;i++) 
		{
			float mxh=-100.0f;//,mnh=100.0f;
			float x=(float)(q_childc[i][0]*2-1)*fqside;
			float z=(float)(q_childc[i][1]*2-1)*fqside;

			CreateQuad((l<<2)+i,levels,x,z,
							   ix+(q_childc[i][0]<<levels),
							   iy+(q_childc[i][1]<<levels),mxh);
			//store the height
			m_qmaxh[(l<<2)+i]=mxh;

			//chose the bigger height
			if (mxh>maxh) 
					maxh=mxh;			
		}
	}
}

//-----------------------------------------------------------------------
//
// renders the virtual quadratic hierarchy
//
void Terrain::RenderQuad(int l,int levels,float cx,float cz,int ix,int iy,BYTE binf)
{
	float fqside=(float)(1<<levels)*side;


	//occlusion
	if (binf&1)
	//	switch(g_pFrustum->IsCylinderUpIn(D3DXVECTOR3(cx,0,cz),fqside,m_qmaxh[l],binf))
	switch(g_pFrustum->IsCylinderUpIn(D3DXVECTOR3(cx,0,cz)*40.078125f,fqside*40.078125f,(float)m_qmaxh[l]/255.0f*Patch::m_fMaxHeight+Patch::m_fMin,binf)) // by dhkwon 2011.4.4
	{
	//out of the FOV
		case 0:
 			if (levels==0) 
			{
 				g_texture.SetTris(m_Patches[ix+iy*m_dp]->texID,0);
				return;
 			}
 			else ;
 			//about the else
 			//generally it should return at that point because that
 			//means - children are out of FOV too... 
 			//we have a valid index buffers for them and they have 
 			//to be marked false not to render... this is TODO...
 			// 뭔가 할일이 남아있다. by dhkwon.
 
			break;
		case 1:
		case 2:
			binf=0;
			
	}

	if (levels==0) 
	{
		//get into the buffer
		WORD off=ix+iy*m_dp;
		WORD help_icnt=0;
	

		//pathc was modified???
		if (Patch::pb_mp[off]) 
		{
			//texture/index buffer id..
			WORD id=m_Patches[off]->texID;

			IDirect3DIndexBuffer8* pIB=g_texture.GetIndexStream(m_Patches[off]->texID);
			
			if (pIB)
			{
				pIB->Lock(0,8192*2,(BYTE**)&(m_Patches[off]->pind),D3DLOCK_DISCARD);
				//메모리가 새는 부분이 있는 것 같아 수정 요망
				m_Patches[off]->picnt= &(help_icnt);
				
				//run rendering step
				m_Patches[off]->Render();
				
				pIB->Unlock();	
			
			}		

			//store the number of primitives in the manager
			g_texture.SetTris(id,help_icnt/3);
			
			//lock the index buffer with dicard... we will fully reconstruct it
		

		}
	}
	else 
	{
		//children
		levels--;
		fqside*=0.25f;
		for(int i=0;i<4;i++) 
		{
			float x=cx+(float)(q_childc[i][0]*2-1)*fqside;
			float z=cz+(float)(q_childc[i][1]*2-1)*fqside;
			RenderQuad((l<<2)+i,levels,x,z,ix+(q_childc[i][0]<<levels),iy+(q_childc[i][1]<<levels),binf);
		}
	}
}

//-----------------------------------------------------------------------
//
// tesselates all the patches
//
void Terrain::TesselateQuad() 
{
	int j = 0;
	for(j=0;j<m_md;j++)
			m_Patches[j]->ClearFov();

	for(j=0;j<m_md;j++)
		    m_Patches[j]->Tesselate();
}

//-----------------------------------------------------------------------
//
// Tesselate the landscape
// 
void Terrain::Tesselate() 
{
	TesselateQuad();	
}

//-----------------------------------------------------------------------
//
// Output primitives with this flag
// 
/*
#ifdef WJO_DX7

void Terrain::FlagDIP(BYTE flag)
{
	//interate though all patches
	for(int i=0;i<m_md;i++) 
		//if the modify flag is matchin the desired then render
		if (Patch::pb_mp[i]==flag) 
		{
			WORD *pis=g_texture.GetIndexStream(m_Patches[i]->texID);
			if (*pis==0) continue;
			m_pd3dDevice->SetTexture( 0, D3DTextr_GetSurface(g_texture.GetTextureName(i)));
			m_pd3dDevice->DrawIndexedPrimitiveVB( D3DPT_TRIANGLELIST,m_pVB,0,Patch::vcnt,
				pis+1,(*pis),0);
		}
}

#else
*/
// directx9 version
void Terrain::FlagDIP(BYTE flag)
{
	//set the vertex buffer - stream source
	HRESULT hr=m_pd3dDevice->SetStreamSource(0,m_pVB, sizeof(CUSTOMVERTEX));

	for(int i=0;i<m_md;i++) 
		//if the modify flag is matchin the desired then render
	{
		if (Patch::pb_mp[i]==flag) 
		{
			IDirect3DIndexBuffer8* pis=g_texture.GetIndexStream(m_Patches[i]->texID);
			// if no index buffer or 0 primitives then skip
			if (pis==NULL) continue;
			int numTri = g_texture.GetTris(i);
			if (numTri==0) continue;

			//set texture
			m_pd3dDevice->SetTexture( 0, g_texture.GetTexture(i));
			
			//set indices
			m_pd3dDevice->SetIndices(pis,0);

			//i = g_texture.GetTris(i);
			//render
			m_pd3dDevice->DrawIndexedPrimitive( 
			//	D3DPT_TRIANGLELIST,0,m_last_vcnt,0,	g_texture.GetTris(i),0);
			D3DPT_TRIANGLELIST,0,m_last_vcnt,0,numTri);
		}
	}
}

//#endif
//-----------------------------------------------------------------------
//
// Renders the landscape
// 

void Terrain::Render()   //directx8 version
{
	DWORD dwLockFlags;

	//if the vertice counter went above some limit
	if (m_last_vcnt>4096) {

		//NEW RENDER
		Patch::vcnt=0;
		Patch::tempcount = 0;

		//clear indices and modifier flags.
		for(int j=0;j<m_md;j++) 
		{
			m_Patches[j]->ClearIndices();
			Patch::pb_mp[j]=1;
		}

		//clear all indices in allcoated nodes 
		TriangleTreeNode::ClearIndices();

		m_last_vcnt=0;

		//clear all indices
		g_texture.Reset();

		//chose discard method for the buffer
		dwLockFlags=D3DLOCK_DISCARD;
	}
	else  
		//chose NOOVERWRITE flag
		dwLockFlags=D3DLOCK_NOOVERWRITE;

	//render all the patches that are not marked modified...
	FlagDIP(0);


	//update indices of all the modified patches
//	RenderQuad(1,m_lv,0,0,0,0,1|0xfc);// by dhkwon 100728 이 코드는 (0,0)이 중심.
	RenderQuad(1,m_lv,bmap.GetWidth()/2,bmap.GetWidth()/2,0,0,1|0xfc);// by dhkwon 100728 (0,0)이 시작점.
	
	 
	//if there are new vertices - VB has beend added to
	if (m_last_vcnt!=Patch::vcnt) 
	{
		LPVOID pv;

		//lock with the appropriate flag
		m_pVB->Lock(m_last_vcnt*sizeof(CUSTOMVERTEX),sizeof(CUSTOMVERTEX)*(Patch::vcnt-m_last_vcnt),
					(BYTE**)&pv,dwLockFlags);

		//move the data
		memmove((CUSTOMVERTEX*)(pv),Patch::pvert+m_last_vcnt,sizeof(CUSTOMVERTEX)*(Patch::vcnt-m_last_vcnt));
			
		//unlock
		m_pVB->Unlock();

		m_last_vcnt=Patch::vcnt;
	}

	//render all the patches that are marked modified...
	FlagDIP(1);

	//clear modified information
	for(int i=0;i<m_md;i++) 
		Patch::pb_mp[i]=0;
}

//-----------------------------------------------------------------------
//
// Init devices 
// allocates the vertex buffer
//
void Terrain::InitDevices(LPWJD3DDEVICE pdev)
{
	//cancel if already initialized
	if (m_pVB) return; 
	m_pd3dDevice=pdev;

	//directx8 vertex buffer creation
	HRESULT hr=m_pd3dDevice->CreateVertexBuffer(WJ_VERTEXBUFFERSIZE*sizeof(CUSTOMVERTEX),
				D3DUSAGE_DYNAMIC | D3DUSAGE_WRITEONLY,D3DFVF_CUSTOMVERTEX,
				D3DPOOL_DEFAULT,&m_pVB);
	if (hr!=D3D_OK )
		m_pVB=NULL;

	//mark vertex buffer as full in order to be rebuild by new traversal
	m_last_vcnt=WJ_VERTEXBUFFERSIZE;
}

//-----------------------------------------------------------------------
//
// all references to the 3d hardware should be descarted...
//
void Terrain::ClearDevices()
{
	//clear allocated device objects
	if (m_pVB) m_pVB->Release();
	m_pVB=NULL;
	m_last_vcnt=WJ_VERTEXBUFFERSIZE;
}
/*
//-----------------------------------------------------------------------
//
// this is not currently used ... I've created the static raw files with it...
//
void Terrain::sRender()
{

	Patch::vcnt=0;

	//clear indices and modifier flags.
	for(int j=0;j<m_md;j++) 
	{
		m_Patches[j]->ClearIndices();
		Patch::pb_mp[j]=1;
	}

	//clear all indices in the nodes - in the pool
	TriangleTreeNode::ClearIndices();
	m_last_vcnt=0;

	//clear all indices
	g_texture.Reset();

	//update indices of all the modified patches
	RenderQuad(1,m_lv,0,0,0,0,0);
	printf("Triangles: %d\nVertices: %d",g_texture.GetTriangleCount(),
			Patch::vcnt);
}
*/