#if !defined(ROAM_H__C4F6F8E5_CA48_46AF_8E84_DD50489CBCF1__INCLUDED_)
#define ROAM_H__C4F6F8E5_CA48_46AF_8E84_DD50489CBCF1__INCLUDED_

#ifndef WARJO_ROAM_H
#define WARJO_ROAM_H

#include<math.h>
//#include "dxinclude.h"
#include <d3dx8.h>

#ifndef BYTE
typedef unsigned char BYTE;
#endif 
#include <stdio.h>
#include "texture.h"
#include "roam_map.h"
#include "ViewFrustum.h"




#define MAX_TRIANGLE_NODES		16*8192	//4*8192	// 256 <-> 512 ¹Ù²Ü °÷.?
#define WJ_VERTEXBUFFERSIZE 8192*4	// by dhkwon map size*40

//conditional compilation depending on the SDK version
	typedef LPDIRECT3D8 LPWJD3D;
	typedef LPDIRECT3DDEVICE8 LPWJD3DDEVICE;
	typedef LPDIRECT3DVERTEXBUFFER8  LPWJD3DVERTEXBUFFER;

	//custom vetex definition for dx8
	struct CUSTOMVERTEX
		{
		D3DXVECTOR3 position; // The 3D position for the vertex	
		DWORD	color;        // The color for the vertex
		float tu,tv;
		
		};

	// Our custom FVF, which describes our custom vertex structure
	#define D3DFVF_CUSTOMVERTEX (D3DFVF_XYZ|D3DFVF_DIFFUSE|D3DFVF_TEX1)
	
//#endif

//******************************************************************
//
// TriangleTreeNode
//
// The node in my tesselation engine
//
struct TriangleTreeNode {

	//conectivity information
	TriangleTreeNode *LChild;
	TriangleTreeNode *RChild;  

	//down/base neighbor
	TriangleTreeNode *DNeighbor; 

	TriangleTreeNode *LNeighbor;
	TriangleTreeNode *RNeighbor;
	TriangleTreeNode *Parent;

	//last computed variance 
	float lvar;

	//index in the vertex buffer for rendering...
	//the index points the the split vertex of the hipotenuse
	WORD index; 

	//frame to defer the variance computation 
	BYTE deff;

	//FOV information 
	BYTE fov;

	//id of the patch this node is child of
	BYTE pid;

	//constructor
	TriangleTreeNode();
	
private:
	//memory management static stuff
	//nodes in dpool... just for tracking..
	static int dcnt;
	
	//dynamyc pool - DNeigh - next in the pool
	static TriangleTreeNode *dpool; 

	//static pool  - array of structs
	static TriangleTreeNode *spool;
	
	//maximum in the spool
	static int	spmax; 

	//pointer to current available in the spool
	static int  psp;   

public:
	//memory operators
	void* operator new(size_t);
	void operator delete(void*);

	//clear indices of all alocated nodes
	static void ClearIndices();

	//clear the fov information for all allocated
	static void ClearFov();

	//how many nodes are allocated?
	static int GetTriCount() 
	{ 
		return psp-dcnt; //static - dinamic available 
	}

	//intialization - allocate momery for the pool
	static bool Init(int nodesmax); 

	//deallocate 
	static bool CleanUp();
	
	//reset for new start of allocation nodes
	static void Reset(); 
};

//***********************************************************************
//
// Patch 
//
// The heart of the ROAM algorytm.... represents one square patch
// of the landscape...
//
#include <vector>
#include <stack>

class Patch {
	//level of recursion - just a helper
	BYTE l;

	//xfactor and yfactor for 1/MapX and 1/MapY	- used in texture coordinates
	float xfac,yfac; 	

    //yoffset corresponds to z...where is this patch in the space?
	int m_xoffset,m_yoffset;  
	
	//current variance tree
	bte *m_CVariance;        

	//the left and the right base children
	TriangleTreeNode m_LBase,m_RBase; 
							  
	//lmit depth in the variance h
	int m_dh;				  

	//the map derived from the general map
	patchmap *m_map;   

	//precomputed hypotenuse - initalized in Init member function
	static float hypo[32];

	//Precomputed variance
	//
	//recurseCV computes recursevly the variance down the tree...for
	//the current map ... variance is stored in the map so it should
	///not be computed for another patch that uses the same map...
	float RecurseCV(float lx,float ly,float lz,float rx,float ry,
		float rz,float ax,float ay,float az,int node);

	void CVup(int node);

    //Split merge stuff

	//force split
	//split is quite the same as in the original algorythm...
	void Split(TriangleTreeNode *tri); 

	//merges single node keeping the connections...
	void Merge(TriangleTreeNode *tri); 

	//is this triangle node good for merge?
	bool GoodForMerge(TriangleTreeNode *tri);

	//go down in the tree and merges the leafs if good for merge
	void MergeDown(TriangleTreeNode *tri); 
	

	//tesselates the patch - recursive version
	void RecurseTesselate(TriangleTreeNode *tri,
							 int lx,  int ly,
							 int rx, int ry,
							 int ax,  int ay,
							 int node, BYTE binf);

	//tesselates the patch - iterative version
	void IterateTesselate(TriangleTreeNode *tri,
							 int lx,  int ly,
							 int rx,  int ry,
							 int ax,  int ay,
							 int node, BYTE binf );

    //Render stuff
	
    //starting indices for the corners of the patch
	//top left,top right,down left,downright
	WORD itl,itr,idl,idr; 	
	
	//get the real variance for the current point
	inline float GetVariance(float x,float y,float z,int node);

    //insert 3 indices for this triangle
	inline void PutTriIndeces(WORD i1,WORD i2,WORD i3);

	//insert a vertex and return an index
	inline WORD PutVertex(float x,float y,float z,float tu,float tv);
	
	//recurses the tree rendering... node,coordinates of the three points,
	//indeces for three points (0xffff) means the index is empty...
	void 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 );


	
	//some internal methods...
	// I know I know there are some STL ones.. let us keep it clear...
	float maxm(float m1,float m2) { return ((m1>m2)?m1:m2); }
	float minm(float m1,float m2) { return ((m1<m2)?m1:m2); }
	float ABS(float f1) {return (f1<0)?-f1:f1;}
	float cGetMax(float z1,float z2,float z3) 
	{ 
		if (z1>z2) 
		{
			if (z1>z3) 
				return z1;
			else 
				return z3;
		} 
		else 
		{
			if (z2>z3) 
				return z2;
			else 
				return z3;
		}
	}
	float GetH(float x,float y) 
	{
		return m_map->GetH((int)x,(int)y);
	}



public:

	//do we mirror textures - which axis are mirrored
	BYTE mirrorx;
	BYTE mirrory;

	//texture id for this patch
	WORD texID;

	//pointer to indeces array
	WORD *pind;

	//the index counter is the first val in the buffer
	WORD *picnt;
	#define icnt (*picnt)	

	//gets the maximum altitude in the patch of landscape...
	void GetMaxH(float &maxh) 
	{
		maxh=m_map->m_LVariance[0].height;
	} 

	//counts the variance computation - just for tracking
	static int var_cnt;
	
	//static vertex buffer - it is a single one for all patches
	//pointer to the vetrtices array
	static CUSTOMVERTEX *pvert;

	//vertex counter
	static int vcnt;
	static int tempcount;

	//type of variance
	static int tvar;

	//static roam?
	static int sroam;

	//patch id
	BYTE pid; 

	//patch modified array of flags
	static BYTE *pb_mp; 

	//clear the indices of the base nodes
	void ClearIndices();

	//clear the FOV information in the base nodes
	void ClearFov();

	//neighbor patches... for conectivity information
    //public so they can be set from outside
	Patch *m_Pup,*m_Pdown,*m_Pleft,*m_Pright;
							  
	//construction and initialization
	Patch();
	bool Init(patchmap *map,int x_off,int y_off);
	
	//resets the connections for new general tesselation...
	void Reset();

	//tessellate recursive and iterative
	void Tesselate();
	void ITesselate(); 

	//render
	void Render();

	//precompute the variance
	void ComputeVariance();

	//we need the frusturm... for the culling
//	static    ViewFrustum frst; 

	//lVariance - limit variance
	static float     lVariance; 
	static float      m_fMaxHeight, m_fMin, m_fMax;
};

//***********************************************************************
//
// MyException
//
// derived from bad_alloc to conform the new standart behavior
//
class MyException: std::bad_alloc {
	char message[256];
public:
	MyException(const char *text) 
	{
		strcpy(message,text);
	}
	const char * const GetMessage() const { return message; }
};

//***********************************************************************
//
// Terrain
//
// the main terrain class
// contains the pathches, implements recursive quadtree
//
class Terrain {
	//dimentions of the quadtree
	int m_dp;  
	int m_md; //m_dp*m_dp
	int m_lv; //levels for the quadtree

	//the bmp height map
	bmpmap bmap; 

	//array of patches (maximum 16x16) - owner flag in the triangle tree is BYTE
	Patch *m_Patches[256];  
	
	//maxheight for the quadtree - for ocllusion, 185
	float m_qmaxh[1024];

	//offsets for the children in the quadtree
 	static int q_childc[4][2];

	//previous value of the vertices count used for vertex buffer update
	DWORD m_last_vcnt;

	//render stuff - directx device & buffer
	LPWJD3DDEVICE m_pd3dDevice;
	LPWJD3DVERTEXBUFFER  m_pVB;

// Function members

	//initial traverse of the quadtree - fills the max heights...
	void CreateQuad(int l,int levels,float cx,float cy,int ix,int iy,float &maxh);
	
	//tesselates all quads...
	void TesselateQuad();

	//Render patches traversin the quadtree - early rejection
	void RenderQuad(int l,int levels,float cx,float cz,int ix,int iy,BYTE binf);

	//draw index primitives for the flags
	void FlagDIP(BYTE flag);
public:
	//side of single patch
	static float side;

	//texture prefix name
	char texname[32];

	//texuture initial resolution & number of mipmaps
	int iResolution,iNumMips;

// Meber functions

	//init and clear of direcx devices
	void InitDevices(LPWJD3DDEVICE pdev);
	void ClearDevices();

	//construction destruction
	Terrain();
	~Terrain();

	//Loads the height map and inits the patches
	void Init(char *szMap);
	void Init(float* pfHeightMap, float fMaxHeight, int nWidth, int nHeight);

	void Reset();
	void Render();
//	void sRender(); //static render
	void Tesselate();

};

#endif
#endif

