#pragma once


typedef std::pair<int,int> IntPair;

typedef std::set<IntPair> IntPairSet;
typedef std::vector<Vector3> PointList;


extern int thevine;

#define EPS 0.0001f
v3 solveintersection(v4 p1, v4 p2, v4 p3);
CLASSY classifypoint(v3 p, v4 plane);

struct polygon
{
	PointList p;
	v4 plane;

	void split(polygon &frontbit, polygon &backbit, v4 xplane)
	{	
		frontbit.plane=plane;
		backbit.plane=plane;
		if (p.empty()) return;
		PointList::iterator i=p.begin();
		CLASSY curside = classifypoint(*i,xplane);
		if (curside==COINCIDENT) curside=INFRONT;
		while (i!=p.begin())
		{
			if (curside==INFRONT) frontbit.p.push_back(*i); else backbit.p.push_back(*i);
			PointList::iterator j=++i;
			if (j==p.end()) j=p.begin();
			CLASSY newside = classifypoint(*j,xplane);
			if (newside==COINCIDENT) newside=curside;
			if (newside!=curside)
			{
				v3 r=*j - *i;
				// (i + tr) dot plane = -d
				// i.plane + tr dot plane = -d
				// t (r dot plane) = -d - i.plane
				// t = (-d - i.plane) / (r dot plane)
				float t = -plane.w - DotProduct(*i,v3(plane.x,plane.y,plane.z)) / DotProduct(r, v3(plane.x,plane.y,plane.z));
				ASSERT(t>=0 && t<=1);
				r = *i + (r*t);
				frontbit.p.push_back(r);
				backbit.p.push_back(r);
				curside=newside;
			}
		}		
	}


	CLASSY classify(v4 xplane)
	{
		if (plane==xplane) return COINCIDENT;
		CLASSY sofar = COINCIDENT;
		for (PointList::iterator i=p.begin();i!=p.end();++i)
		{
			CLASSY r=classifypoint(*i,xplane);
			if (r!=COINCIDENT)
			{
				if (sofar==COINCIDENT) sofar=r; else if (sofar!=r) return SPANNING;
			}
		}
		return sofar;
	}

	bool operator < (const polygon &px) const 
	{
		if (px.p[0].y != p[0].y) return p[0].y < px.p[0].y;
		return &px < this;
	}
};

typedef std::vector<polygon> polygonlist;
typedef std::set<polygon> polygonset;

struct bspnode
{
	v4 partition;
	
	polygonlist polygons;		
	bspnode *front,*back;

	~bspnode()
	{
		delete front;
		delete back;
	}
	bspnode()
	{
		front=back=NULL;
	}

	void drawpolys()
	{
		for (polygonlist::iterator i=polygons.begin(); i!=polygons.end(); ++i)
		{
		}
	}

	void draw(v3 eye)
	{
		CLASSY c = classifypoint(eye,partition);
		if (c==INFRONT || c==COINCIDENT)
		{
			if (front) front->draw(eye);
			if (c!=COINCIDENT) drawpolys();
			if (back) back->draw(eye);
		}
		else 
		{
			if (back) back->draw(eye);
			drawpolys();			
			if (front) front->draw(eye);
		}
	}
};


struct v3p : public v3
{
	v3p *next;
	v3p(float x=0, float y=0, float z=0, v3p *n=NULL) : v3(x,y,z)
	{
		next=n;
	}

	v3p(const v3 &v)
	{
		x=v.x;
		y=v.y;
		z=v.z;
		next=NULL;
	}
};

typedef std::set<v3p> PointSet;


extern PointSet pointlist;

#define MAXX 64
#define MAXY 64
#define MAXZ 64
extern v3p* grid[MAXZ][MAXY][MAXX];

void boundpoint(const v3 &p, int &ix, int &iy, int &iz);
v3 getpoint(int ix, int iy, int iz);

void addpoint(v3 &p);


v3 *findnearestpoint(v3 p, float &bestdist);


float samplegrid(const v3 &p, v3 *nearest);

float samplegrid(const v3 &p);

extern int vine;
extern float vinet;

extern int numbigcubes;

v3 getgrad(const v3 &p, v3 *nearest);

void addcube(m44 orient, v3 size, polygonlist &ps);
v3 splineinterp(v3 *ps, int numps, float t);

v3 randvec();

void makecubestrand(v3 *ps, int numps, int numcubes, v3 minsize, v3 maxsize, polygonlist &polys);



void makecubetree(v3 p, v3 d, float power, float dpower, polygonlist &polys, int level);
void buildbsp(bspnode *tree, polygonlist &polylist);


struct tree 
{
			
	polygonlist mainlist;
	SimpleBuffer linetest;
	int numvines;
	PointList vinepath[400];
	float vinesize[400];
	DWORD vinecol[400];
	SimpleBuffer blah;
	SimpleBuffer2D blah2d;

	tree() ;

	~tree()
	{
		
	
	}

	int drawtree(float frac, float lighting, int alpha, int shadow);
	void gen(int ts);
};
