#ifndef _VECT3D_H
#define _VECT3D_H

/*
	TODO:
		Make entirely quaternion based Vector lib
	For right now though, this works more than addequitly
*/

#include <cmath>
class Matrix;
class Vect3D;
typedef Vect3D Point3D;

struct P3D {   // quick hack to be compatibly with Chris Hecker
	fixed28_4 x,y;
	float z,u,v;
};

class Vect3D {
	friend class Matrix;
protected:
			double x,y,z;
			float u,v;  // currently unused
public:
	Vect3D(): x(0),y(0),z(0),u(0),v(0) {}
	Vect3D(const Vect3D &vec): x(vec.x), y(vec.y), z(vec.z), u(vec.u), v(vec.u) {}
	Vect3D(double X,double Y,double Z, float U=0, float V=0):x(X),y(Y),z(Z),u(U),v(V) {}

	const double&  getx() const {return x;}
	const double&  gety() const {return y;}
	const double&  getz() const {return z;}
	const float&   getu() const {return u;}
	const float&   getv() const {return v;}

	void  set(double X,double Y,double Z, float U=0, float V=0 ) {x=X; y=Y; z=Z; u=U; v=V;}
	void  setx(double val) {x=val;}
	void  sety(double val) {y=val;}
	void  setz(double val) {z=val;}
	void  setu(float val)  {u=val;}
	void  setv(float val)  {v=val;}
	void  insure_0();

	Vect3D operator-() {return Vect3D(-x,-y,-z);}
	Vect3D operator+(const Vect3D &v) const {return Vect3D(x+v.x, y+v.y, z+v.z);}
	Vect3D operator-(const Vect3D &v) const {return Vect3D(x-v.x, y-v.y, z-v.z);}

	Vect3D& operator+=(const Vect3D &v)	{x+=v.x;  y+=v.y; z+=v.z; return *this;}
	Vect3D& operator-=(const Vect3D &v)	{x-=v.x;  y-=v.y; z-=v.z; return *this;}
	Vect3D& operator*=(double scalar)		{x*=scalar; y*=scalar; z*=scalar; return *this;}

	friend Vect3D operator* (double scalar, const Vect3D &v) {return Vect3D(scalar*v.x, scalar*v.y, scalar*v.z);}
	friend Vect3D operator* (const Vect3D &v, double scalar) {return Vect3D(scalar*v.x, scalar*v.y, scalar*v.z);}

	friend ostream &operator<<(ostream &, const Vect3D &);
	friend istream &operator>>(istream &, Vect3D &);

	bool operator!=(const Vect3D &v) const {if (x!=v.x  ||  y!=v.y  ||  z!=v.z) return true; return false;}
	bool operator==(const Vect3D &v) const {if (x==v.x  &&  y==v.y  &&  z==v.z) return true; return false;}
	Vect3D &operator=(const Vect3D &v) {x=v.x; y=v.y; z=v.z; return *this;}

	double dot(const Vect3D &v)	const	{return (x*v.x + y*v.y + z*v.z);}
	double length()							const	{return (sqrt(x*x + y*y + z*z));}

	Vect3D cross(const Vect3D &v) const {return Vect3D(y*v.z - z*v.y, z*v.x - x*v.z,  x*v.y - y*v.x);}

	Vect3D norm();
	Vect3D surface_norm(const Vect3D &, const Vect3D &, const Vect3D &, const Vect3D &) const;
};

void  Vect3D::insure_0() {
	if(x<CLIP_PLANE_EPSILON && x>-CLIP_PLANE_EPSILON) x=0;
	if(y<CLIP_PLANE_EPSILON && y>-CLIP_PLANE_EPSILON) y=0;
	if(z<CLIP_PLANE_EPSILON && z>-CLIP_PLANE_EPSILON) z=0;
}

ostream &operator<<(ostream &out, const Vect3D &v) {
	out.setf(ios::left, ios::adjustfield);
	out << "  " << setprecision(4) << setw(5) << v.x << "  " << setw(5) << v.y << "  " << setw(5) << v.z << '\n';
	return out;
}
istream &operator>>(istream &in, Vect3D &vec) {
	in >> vec.x >> vec.y >> vec.z /* >> vec.u >> vec.v */;
	return in;
}

Vect3D Vect3D::norm() {
	double lngth = length();
	if(lngth == 0) return (*this);
	lngth=1/lngth;
	x *= lngth;
	y *= lngth;
	z *= lngth;
	return *this;
}

Vect3D Vect3D::surface_norm(const Vect3D &v1, const Vect3D &v2, const Vect3D &v3, const Vect3D &v4) const {
	Vect3D dir1,dir2,srfnorm1,srfnorm2;
	double lngth,lngth2;
	dir1 = v2-v1;
	dir2 = v4-v1;
	srfnorm1 = dir1.cross(dir2);
	lngth = srfnorm1.length();
	dir1 = v4-v3;
	dir2 = v2-v3;
	srfnorm2 = dir1.cross(dir2);
	lngth2 = srfnorm2.length();
	if (lngth == 0)
		return (srfnorm2.norm());
	else {
		srfnorm1.norm();
		if (lngth2 != 0) {
			srfnorm2.norm();
			srfnorm1 += srfnorm2;
			srfnorm1 *= 0.5;
		}
	}
	return srfnorm1;
}
#endif
 

#ifndef _BSP_TREE_H
#define _BSP_TREE_H

/*
*****************************************************************************************
	Main Header for BSP Tree
	This is very 'inefficient'
	It will still build a tree quickly but the use or virtual functions can be avoided
	I only coded it this way because my philosphy is to:
		MAKE IT RIGHT  then
		MAKE IT FAST
	And im still in exploration phase of my 3d career
******************************************************************************************
*/

extern num_NON_backface_polys;
extern double current_speed;

class BSP_Tree;

class BSP_Node {
	friend BSP_Tree;
protected:
	bool isLeaf;
	BSP_Node *front, *back;
public:
	BSP_Node(bool is_a_Leaf): isLeaf(is_a_Leaf), front(0),back(0) {}

	virtual void draw() {}
	virtual double facing(const Camera &c) const {return 0;}
	virtual Plane get_partition() const {return Plane();};
 };

class BSP_Partition: public BSP_Node {
private:
	Plane partition;
public:
	BSP_Partition(Plane &p): BSP_Node(false), partition(p) {}
	virtual ~BSP_Partition() {}

	virtual Plane  get_partition() const  {return partition;}
	virtual double facing(const Camera &c) const {return partition.dist(c.pos);}
};

class BSP_Leaf: public BSP_Node {
private:
	Poly_List polygons;
	Vect3D center;
	float radius;
	void bound_sphere();  // EXPERIMENTAL as of 2000/7/14
public:
	BSP_Leaf(Poly_List &list): BSP_Node(true), polygons(list) {bound_sphere();}
	virtual ~BSP_Leaf() {}

	virtual void draw() {
		for(poly_Iter=polygons.begin(); poly_Iter!=polygons.end(); ++poly_Iter) {
			if((*poly_Iter).plane.dist(player.pos)>=0.0F) {
			  (*poly_Iter).draw();
				num_NON_backface_polys++;
			}
		}
	}
};
/*
===========
BSP_Leaf::bound_sphere
	Graphics Gems modified source
	to find smallest bounding sphere of a given set of points
	Uses entire polygon list to find the leaf's bounding sphere
===========
*/
void BSP_Leaf::bound_sphere() {
	Poly curr_poly;
	Point3D curr_point, delta;
	Point3D xmin, xmax, ymin, ymax, zmin, zmax, dia1, dia2;
	double xspan, yspan, zspan, maxspan;
	double old_to_p, old_to_p_sq, old_to_new;
	double rad_sq;
	register int i;

	xmin.setx(INT_MAX); ymin.sety(INT_MAX); zmin.setz(INT_MAX);
	xmax.setx(INT_MIN); ymax.sety(INT_MIN); zmax.setz(INT_MIN);
	
	for (poly_Iter=polygons.begin(); poly_Iter!=polygons.end(); ++poly_Iter) {
		curr_poly=*poly_Iter;
		for(i=0; i<curr_poly.num_vertexes; i++) {
			curr_point=curr_poly.vertex[i];
			if (curr_point.getx() < xmin.getx())
				xmin = curr_point;
			if (curr_point.getx() > xmax.getx())
				xmax = curr_point;
			if (curr_point.gety() < ymin.gety())
				ymin = curr_point;
			if (curr_point.gety() > ymax.gety())
				ymax = curr_point;
			if (curr_point.getz() < zmin.getz())
				zmin = curr_point;
			if (curr_point.getz() > zmax.getz())
				zmax = curr_point;
			xmin.insure_0(); xmax.insure_0();
			ymin.insure_0(); ymax.insure_0();		
			zmin.insure_0(); zmax.insure_0();
		}
	}
	delta = xmax-xmin;
	xspan = delta.dot(delta);
	delta = ymax-ymin;
	yspan = delta.dot(delta);
	delta = zmax-zmin;
	zspan = delta.dot(delta);

	dia1 = xmin; dia2 = xmax;
	maxspan = xspan;
	if (yspan>maxspan) {
		maxspan = yspan;
		dia1 = ymin; dia2 = ymax;
	}
	if (zspan>maxspan) {
		dia1 = zmin; dia2 = zmax;
	}

	center.setx((dia1.getx()+dia2.getx())/2.0);
	center.sety((dia1.gety()+dia2.gety())/2.0);
	center.setz((dia1.getz()+dia2.getz())/2.0);
	center.insure_0();
	delta = dia2-center;
	rad_sq = delta.dot(delta);
	radius = sqrt(rad_sq);

	for (poly_Iter=polygons.begin(); poly_Iter!=polygons.end(); ++poly_Iter) {
		curr_poly=*poly_Iter;
		for(i=0; i<curr_poly.num_vertexes; i++) {
			curr_point=curr_poly.vertex[i];
			delta = curr_point-center;
			old_to_p_sq = delta.dot(delta);
			if (old_to_p_sq > rad_sq)	{
				old_to_p = sqrt(old_to_p_sq);
				radius = (radius + old_to_p) / 2.0;
				rad_sq = radius*radius;
				old_to_new = old_to_p - radius;
				center.setx((radius*center.getx() + old_to_new*curr_point.getx()) / old_to_p);
				center.sety((radius*center.gety() + old_to_new*curr_point.gety()) / old_to_p);
				center.setz((radius*center.getz() + old_to_new*curr_point.getz()) / old_to_p);
				center.insure_0();
			}	
		}
	}
}
//******************************************************************************************

class BSP_Tree {
private:
	void build_tree(Poly_List &, BSP_Node *);
	void render_tree(BSP_Node *);
protected:
	int num_elements, num_leafs;
	BSP_Node *root;
public:
	BSP_Tree(): num_elements(0), num_leafs(0), root(0) {}
	~BSP_Tree() { }

	int size()  {return num_elements;}
	int leafs() {return num_leafs;}

	void build(Poly_List &);
	void render() {render_tree(root);}
};
//******************************************************************************************
void BSP_Tree::build(Poly_List &polygons) {
	root=new BSP_Partition(polygons.front().plane);
	polygons.front().used=true;
	build_tree(polygons, root);
}

void BSP_Tree::build_tree(Poly_List &polygons, BSP_Node *node) {
	Poly_List front_list, back_list;

	partition(polygons, node->get_partition(), front_list, back_list);

	if(back_list.empty()) {
		node->back=0;
	}
	else {
		if(convex(back_list)) {
			num_elements+=back_list.size();
			num_leafs++;
			node->back=new BSP_Leaf(back_list);
		}
		else {
			for(poly_Iter=back_list.begin(); poly_Iter!=back_list.end(); ++poly_Iter) {
				if(!(*poly_Iter).used)	break;
			}
			(*poly_Iter).used=true;
			node->back=new BSP_Partition((*poly_Iter).plane);
			build_tree(back_list, node->back);
		}
	}
	if(front_list.empty()) {
		node->front=0;
	}
	else {
		if(convex(front_list)) {
			num_elements+=front_list.size();
			num_leafs++;
			node->front=new BSP_Leaf(front_list);
		}
		else {
			for(poly_Iter=front_list.begin(); poly_Iter!=front_list.end(); ++poly_Iter) {
				if(!(*poly_Iter).used)	break;
			}
			(*poly_Iter).used=true;
			node->front=new BSP_Partition((*poly_Iter).plane);
			build_tree(front_list, node->front);
		}
	}
}

void BSP_Tree::render_tree(BSP_Node *node) {
	if(node) {
		if(node->isLeaf) {
			node->draw();
			return;
		}
		if(node->facing(player) >= 0.0F) {
			render_tree(node->back);
			render_tree(node->front);
		}
		else {
			render_tree(node->front);
			render_tree(node->back);
		}
	}
}
#endif
 

#ifndef _BSP_UTILS_H
#define _BSP_UTILS_H

/*
===========
split
	do the actual poly split into
	front and back pieces
===========
*/
void split(const Poly &poly, const Plane &plane, Poly &front_split, Poly &back_split) {
	register int offsetA, offsetB;
	double dA, dB, scalar;
	Point3D isect;
	// loop through vertexes to find splits
	for(int i=0; i<poly.num_vertexes; i++) {
		offsetA=i;
		offsetB=(i+1) % poly.num_vertexes;
		dA=poly.vertex[offsetA].dot(plane.normal);
		dB=poly.vertex[offsetB].dot(plane.normal);
		if((dA>=plane.dist_origin) == (dB>=plane.dist_origin)) {
			if(dA>=plane.dist_origin) {
				front_split.add(poly.vertex[offsetA]);
				front_split.add(poly.vertex[offsetB]);
			}
			else {
				back_split.add(poly.vertex[offsetA]);
				back_split.add(poly.vertex[offsetB]);
			}
		}
		else {
			scalar = (plane.dist_origin-dA) / (dB-dA);
			isect.setx(poly.vertex[offsetA].getx() + (poly.vertex[offsetB].getx() - poly.vertex[offsetA].getx())*scalar);
			isect.sety(poly.vertex[offsetA].gety() + (poly.vertex[offsetB].gety() - poly.vertex[offsetA].gety())*scalar);
			isect.setz(poly.vertex[offsetA].getz() + (poly.vertex[offsetB].getz() - poly.vertex[offsetA].getz())*scalar);
			front_split.add(isect);
			back_split.add(isect);
			if(dA>=plane.dist_origin)
				back_split.add(poly.vertex[offsetB]);
			else
				front_split.add(poly.vertex[offsetB]);
		}
	}
	front_split.solve();
	back_split.solve();
}

/*
===========
convex
	determines if a list is elibable to become a leaf
===========
*/
bool convex(Poly_List &list) {
	Poly_List::iterator po_Iter, pi_Iter;
	Poly test_poly;
	bool front, behind;
	int status;
	// list is convex if only 1 poly or every other poly is one the same(relatively) side of a given poly
	// FIXED: Bug in 'exaflops' code   didnt reset bool front and behind after each loop iteration
	if(list.size()==1) return true;
	for(po_Iter=list.begin(); po_Iter!=list.end(); ++po_Iter) {
		front=behind=false;  // BUGFIX
		test_poly = (*po_Iter);
		for (pi_Iter=list.begin(); pi_Iter!=list.end(); ++pi_Iter) {
			if ((*pi_Iter)==test_poly)	continue;
			status = test_poly.plane.classify(*pi_Iter);
			switch(status) {
				case	FRONT:
					if(behind)
						return false;
					else
						front=true;
					break;
				case	BACK:
					if(front)
						return false;
					else
						behind=true;
					break;
				case	CO_PLANAR: break;
				case	SPANNING:	return false;
			}
		}
	}
	return true;
}

/*
===========
partition
	This is what you see very often  
	partition input list of polys against give plane
	creating front and back lists
===========
*/
void partition(Poly_List &list, const Plane &plane, Poly_List &front, Poly_List &back) {
	Poly_List::iterator p_Iter;
	Poly front_split, back_split;
	for(p_Iter=list.begin(); p_Iter!=list.end(); ++p_Iter) {
		switch (plane.classify(*p_Iter)) {
			case CO_PLANAR:  // push down either side   should intelligently choose
			case BACK:
				back.push_back(*p_Iter);
				break;
			case FRONT:
				front.push_back(*p_Iter);
				break;
			case SPANNING:
				Poly front_split, back_split;
				split(*p_Iter, plane, front_split, back_split);
				back.push_back(back_split);
				front.push_back(front_split);
				break;
		}
	}
}
#endif 

#ifndef _CAM_H
#define _CAM_H

class Camera {
public:
	Matrix orientation;
	Point3D pos;
};

Camera player;
#endif 

#ifndef	_DRAW3D_H
#define	_DRAW3D_H

P3D points[MAX_VERTEXES+1];
extern int num_polys, num_tris;
extern BITMAP *TestTexture[4];
extern int tex_LUT;

void SCR_project() {
	register double	zrecip;
	register int i;
	float x,y;
	for(i=0; i<Poly::clipped_poly.num_vertexes; i++) {
		zrecip = 1.0 / (points[i].z=Poly::clipped_poly.vertex[i].getz());
		x=(h_X + V_DX*Poly::clipped_poly.vertex[i].getx()*zrecip);
		y=(h_Y - V_DY*Poly::clipped_poly.vertex[i].gety()*zrecip);
		points[i].x=(x<XRES) ? x*16 : (XRES-1)*16;
		points[i].y=(y<YRES) ? y*16 : (YRES-1)*16;
		points[i].z*=16;
	}

	// hard code in some texels because i dont know how to do it automatically
	// as you can see, this is only gona work with a quad
	points[0].u = 0.5;
	points[0].v = 0.5;
	points[1].u = TestTexture[tex_LUT]->w-0.5;
	points[1].v = 0.5;
	points[2].u = TestTexture[tex_LUT]->w-0.5;
	points[2].v = TestTexture[tex_LUT]->w-0.5;
	points[3].u = 0.5;
	points[3].v = TestTexture[tex_LUT]->w-0.5;

	points[i]=points[0]; // code depends on having first vertex repeated at end of list
}

void SCR_render()	{
	int i;

	// profiling
	num_polys++;
	num_tris+=Poly::clipped_poly.num_vertexes-2;
	// sit back awhile
	// droping below 60 FPS when
	// drawing a mind blowing   <2> yes  2 polys
	// when up close to screen is gona win me some awards

	// this is simply just a polygon triangulation routine  
	// NON 'fan' style
	// and NO HOLES please
	for(i=0; i<Poly::clipped_poly.num_vertexes-1; i+=2)
		TextureMapTri(offscreen, points+i, TestTexture[tex_LUT]);
}
#endif 

#ifndef _MATH_3D_H
#define _MATH_3D_H

#include <cmath>

const double PI_180 = PI/180;
typedef long fixed28_4;
typedef long fixed16_16;

inline fixed28_4 fto28_4(float val) {return val*16;}
inline fixed16_16 fto16_16(float val) {return val*65536;}
inline float fixed28_4tof(fixed28_4 val) {return val/16.0;}
inline float fixed16_16tof(fixed16_16 val) {return val/65536.0;}

inline fixed28_4 fixed28_4Mul(fixed28_4 lhs, fixed28_4 rhs) {return (lhs*rhs)/16;}

inline void FloorDivMod(long num, long denom, long &Floor,	long &Mod) {
	if(num >= 0) {
		Floor = num / denom;
		Mod = num % denom;
	}
	else {
		Floor = -((-num) / denom);
		Mod = (-num) % denom;
		if(Mod) {
			Floor--; Mod = denom - Mod;
		}
	}
}

inline long ceil28_4(fixed28_4 val) {
	long rVal;
	long num = val - 1 + 16;
	if(num >= 0) {
		rVal = num/16;
	}
	else {
		rVal = -((-num)/16);
		rVal -= ((-num) % 16) ? 1 : 0;
	}
	return rVal;
}

#include "Vect3D.h"
#include "Matrix.h"


#endif 

#ifndef _MATRIX_H
#define _MATRIX_H

#include <cmath>
#include "Vect3D.h"

/*
*****************************************************************************************
	THIS Matrix Class is optimized for 3D operations.
	ITS USE DEPENDS ON THE USE OF ITS OWN MEMBER FUNCTIONS
		NAMELY THE TRANSFORM FUNC.
			Currently translate and scale dont work right in my system
			Great for rotations though  :)
	IT IS MEANT TO MIMICK A 4x4 MATRIX BUT...
		-multiplication is only done on 3x3 component of actual 3x4 SIGNIFICANT components
		-Hence operator= only copies first 12 elements
		-HOWEVER a 4x4 structure is still used to provide better alignment in memory
	IT IS NOT SUITED FOR PROJECTION MATRICIES SINCE 4th ROW IS EFFECTIVELY IGNORED
	ALL Matrix ops that depend on that 4th row should not be attempted
	NEEDS FIXME's ALL FFFREAKEEEN OVER THE PLACE   :(
*/

const double _IDENTITY_[16] = {1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1};

class Matrix {
protected:
	double *elements;
public:
	Matrix();
	Matrix(double *);
	Matrix(const Matrix &);
	~Matrix() {delete[] elements;}

	void  set(double *elems) {memcpy(elements,elems,16*sizeof(double));}
	void  setIdentity()			 {memcpy(elements,_IDENTITY_,16*sizeof(double));}
	double operator[](int index) const {return elements[index];}

	Matrix operator* (const Matrix &) const;

	void rotate		(int ,double);
	void rotate		(const Vect3D &);
	void scale		(const Vect3D &);
	void translate(const Vect3D &);

	Matrix transform	(const Vect3D &, const Vect3D &, const Vect3D &) ;
	Vect3D cross			(const Vect3D &) const;
	Vect3D back_rotate(const Vect3D &) const;

	Matrix& operator=(const Matrix &);
};

Matrix::Matrix() {
	elements = new double[16];
	memcpy(elements,_IDENTITY_,16*sizeof(double));
}
Matrix::Matrix(double *elems) {
	elements = new double[16];
	memcpy(elements,elems,16*sizeof(double));
}
Matrix::Matrix(const Matrix &rMat1) {
	elements = new double[16];
	memcpy(elements,rMat1.elements,16*sizeof(double));
}

Matrix Matrix::operator*(const Matrix &rhs) const {
	Matrix temp;
	temp.elements[0]=elements[0]*rhs.elements[0] + elements[1]*rhs.elements[4] +
				elements[2]*rhs[8];
	temp.elements[1]=elements[0]*rhs.elements[1] + elements[1]*rhs.elements[5] +
				elements[2]*rhs[9];
	temp.elements[2]=elements[0]*rhs.elements[2] + elements[1]*rhs.elements[6] +
				elements[2]*rhs[10];

	temp.elements[4]=elements[4]*rhs.elements[0] + elements[5]*rhs.elements[4] +
				elements[6]*rhs[8];
	temp.elements[5]=elements[4]*rhs.elements[1] + elements[5]*rhs.elements[5] +
				elements[6]*rhs[9];
	temp.elements[6]=elements[4]*rhs.elements[2] + elements[5]*rhs.elements[6] +
				elements[6]*rhs[10];

	temp.elements[8]=elements[8]*rhs.elements[0] + elements[9]*rhs.elements[4] +
				elements[10]*rhs[8];
	temp.elements[9]=elements[8]*rhs.elements[1] + elements[9]*rhs.elements[5] +
				elements[10]*rhs[9];
	temp.elements[10]=elements[8]*rhs.elements[2] + elements[9]*rhs.elements[6] +
				elements[10]*rhs[10];

	return temp;
}

void Matrix::rotate(int axis, double angle) {
	Matrix temp;
	double c,s;
	int i = (axis%3) + 1;
	int j = i%3;
	i -= 1;
	c = cos(angle*PI_180);
	s = sin(angle*PI_180);
	temp.elements[(i<<2)+i] = c; temp.elements[(i<<2)+j] = s;
	temp.elements[(j<<2)+j] = c; temp.elements[(j<<2)+i] = -s;
	(*this) = (*this)*temp;
}
void Matrix::rotate(const Vect3D &ro) {
	rotate(1,ro.x);
	rotate(2,ro.y);
	rotate(3,ro.z);
}
void Matrix::scale(const Vect3D &sc) {
	elements[0] = sc.x;
	elements[5] = sc.y;
	elements[10] = sc.z;
}
void Matrix::translate(const Vect3D &tr) {
	elements[3] = -tr.x;
	elements[7] = -tr.y;
	elements[11] = -tr.z;
}

Matrix Matrix::transform(const Vect3D &sc,const Vect3D &tr,const Vect3D &ro) {
	scale(sc);
	rotate(ro);
	translate(tr);
	return *this;
}

Vect3D Matrix::cross(const Vect3D &v) const {
	double x = elements[0]*v.x + elements[1]*v.y + elements[2]*v.z; // + elements[3];
	double y = elements[4]*v.x + elements[5]*v.y + elements[6]*v.z; // + elements[7];
	double z = elements[8]*v.x + elements[9]*v.y + elements[10]*v.z; // + elements[11];
	return Vect3D(x,y,z);
}

Vect3D Matrix::back_rotate(const Vect3D &v) const {
	double x = v.x*elements[0] + v.y*elements[4] + v.z*elements[8];
	double y = v.x*elements[1] + v.y*elements[5] + v.z*elements[9];
	double z = v.x*elements[2] + v.y*elements[6] + v.z*elements[10];
	return Vect3D(x,y,z);
}

Matrix& Matrix::operator=(const Matrix &rhs) {
	if(&rhs != this) {
		memcpy(elements,rhs.elements,12*sizeof(double));
	}
	return *this;
}

#endif 

#ifndef _OBJ_H
#define _OBJ_H

/*
FILE TYPES:
	T3D:	[T]ext [3D] object file (raw text)
	B3D:	[B]inary [3D] object file (compiled bytes)

	Needs updated:
		Support [object] 'center' so to make verticies relative to the center and not globalized
		Find way to incorporate u,v coordinates in with the vertex and face lists of [objects]
		Find way to AUTOMATICALLY map texture to a face of any [object] [sphere] [cone] or [cylinder]
			Please send any helpful info to goku_supersaiyan@netzero.net
			
		Possible conflict with [sphere]
			Ok to use but might crash system
			BSP is not constructing one leaf for the sphere
				either due to my own tessilation algo or BSP code itself
*/

// *********************************************************
void read_OBJ(char *, Poly_List &);
void read_binary_OBJ(char *, Poly_List &);
// *********************************************************

// *********************************************************
void read_OBJ(char *file, Poly_List &polygons) {
	ifstream vin;
	ofstream bout;
	char buf[128];
	bool done=false;

	cout << "Inputing vertex file " << file << " ... ";
	vin.open(file, ios::in);
	if(!vin) {
		cout << "\n\tNo such file: " << file << endl;
		return;
	}
	strcpy(buf, file);
	strcpy(buf+strlen(buf)-3, "b3d");
	bout.open(buf, ios::out|ios::binary);

	memset(buf, 0, 128);
	skip_white(vin, buf);
	do {
		obj_count++;
		if(strcmp(buf, "[object]")==0)			
			if(!parse_object(vin, bout, polygons)) break;
		if(strcmp(buf, "[sphere]")==0)
			if(!parse_sphere(vin,bout,polygons)) break;
		if(strcmp(buf, "[cylinder]")==0)
			if(!parse_cylinder(vin,bout,polygons)) break;
		if(strcmp(buf, "[cone]")==0)
			if(!parse_cone(vin,bout,polygons)) break;

		do {
			vin.getline(buf, 128);
			if(vin.eof()) {
				done=true;
				break;
			}
		} while(buf[0]==0  ||  buf[0]=='#');
		buf[10]=0;
		if(strcmp(buf, "[end_file]")==0)
				done=true;
	} while(!done);
	vin.close();
	bout.close();
	cout << endl;
}

void read_binary_OBJ(char *file, Poly_List &polygons) {
	ifstream bin;
	char type;

	cout << "Inputing binary vertex file " << file << " ... ";
	bin.open(file, ios::in|ios::binary);
	if(!bin) {
		cout << "\n\tNo such file: " << file << endl;
		return;
	}

	do {
		bin.read((unsigned char*)&type, 1);
		if(bin.eof())
			break;
		switch (type) {
			case OBJECT:
				parse_binary_object(bin,polygons);
				break;
			case SPHERE:
				parse_binary_sphere(bin, polygons);
				break;
			case CYLINDER:
				parse_binary_cylinder(bin, polygons);
				break;
			case CONE:
				parse_binary_cone(bin, polygons);
				break;
			default: break;
		}
	} while(1);
	bin.close();
	cout << endl;
}

// *********************************************************
#endif 

#ifndef _OBJ_IO_H
#define _OBJ_IO_H

// *********************************************************
int obj_count;
bool parse_object(ifstream &, ofstream &, Poly_List &);
bool parse_sphere(ifstream &, ofstream &, Poly_List &);
bool parse_cylinder(ifstream &, ofstream &, Poly_List &);
bool parse_cone(ifstream &, ofstream &, Poly_List &);

void parse_binary_object(ifstream &, Poly_List &);
void parse_binary_sphere(ifstream &, Poly_List &);
void parse_binary_cylinder(ifstream &, Poly_List &);
void parse_binary_cone(ifstream &, Poly_List &);
// *********************************************************

// *********************************************************
bool parse_object(ifstream &vin, ofstream &bout, Poly_List &polygons) {
	Poly curr_polygon;
	Vect3D vertex[MAX_VERTEXES];

	int count, v_count, face_count, pos, list_counter, curr_vertex_num;
	int face_list[32][MAX_VERTEXES], num_in_list[32];
	char buf[128], type;
	bool done=false, dup_error=false;

	count=v_count=face_count=pos=list_counter=curr_vertex_num=0;	

	dup_error=false;

	skip_white(vin, buf);
	if(buf[0]=='v') {
		v_count=atoi(buf+1);
		if(v_count>MAX_VERTEXES) {
			error(obj_count, 0);
			return false;
		}

		for(int i=0; i<v_count; i++)
			vin >> vertex[i];
	}

	skip_white(vin, buf);
	if(buf[0]=='f') {
		face_count=atoi(buf+1);
		for(int i=0; i<face_count; i++) {
			skip_white(vin, buf);
			list_counter=count_commas(buf) + 1;
			if(list_counter==1) {
				error(obj_count, 1);
				done=true;
				break;
			}
			pos=0;
			curr_polygon.clear();
			num_in_list[i]=list_counter;
			for(int j=0; j<list_counter; j++) {
				curr_vertex_num=atoi(buf+pos);
				if(curr_vertex_num>=v_count) {
					error(obj_count, 2);
					done=true;
					break;
				}
				face_list[i][j]=curr_vertex_num;
				curr_polygon.add(vertex[curr_vertex_num]);
				pos=next_comma(buf,pos)+1;
			}
			if(done) break;
			curr_polygon.solve();
			if(!duplicate(curr_polygon, polygons)) {
				polygons.push_back(curr_polygon);
				count++;
			}
			else
				dup_error=true;
		}
		if(done) return false;
	}

	skip_white(vin, buf);
	buf[5]=0;
	if(strcmp(buf, "[end]")!=0) {
		error(obj_count, 3);
		return false;
	}

	if(dup_error)
		error(obj_count, 4);
	
	type=OBJECT;
	bout.write((unsigned char*)&type, 1);
	bout.write((unsigned char*)&v_count,4);
	bout.write((unsigned char*)&face_count,4);
	bout.write((unsigned char*)vertex, v_count*sizeof(Vect3D));
	for(int i=0; i<face_count; i++) {
		bout.write((unsigned char*)&num_in_list[i], sizeof(int));
		bout.write((unsigned char*)&face_list[i][0], num_in_list[i]*sizeof(int));
	}

	return true;
}
bool parse_sphere(ifstream &vin, ofstream &bout, Poly_List &polygons) {
	Vect3D center;
	int properties[4];
	char buf[128], type;

	skip_white(vin, buf);
	vin >> center;
	vin >> properties[0] >> properties[1] >> properties[2] >> properties[3];
	skip_white(vin, buf);
	buf[5]=0;
	if(strcmp(buf, "[end]")!=0) {
		error(obj_count, 3);
		return false;
	}
	if(properties[2]>MAX_VERTEXES) {
		error(obj_count, 0);
		return false;
	}
	if(properties[2]<3 || properties[3]<3) {
		error(obj_count, 5);
		return false;
	}

	type=SPHERE;
	bout.write((unsigned char*)&type, 1);
	bout.write((unsigned char*)¢er, sizeof(Vect3D));
	bout.write((unsigned char*)properties, 4*sizeof(int));
	tessilate_sphere(center, properties[0], properties[1], properties[2], properties[3], polygons);
	return true;	
}
bool parse_cylinder(ifstream &vin, ofstream &bout, Poly_List &polygons) {
	Vect3D cent_orient[2];
	int properties[3];
	char buf[128], type;

	skip_white(vin, buf);
	vin >> cent_orient[0] >> cent_orient[1];
	vin >> properties[0] >> properties[1] >> properties[2];
	skip_white(vin, buf);
	buf[5]=0;
	if(strcmp(buf, "[end]")!=0) {
		error(obj_count, 3);
		return false;
	}
	if(properties[2]>MAX_VERTEXES) {
		error(obj_count, 0);
		return false;
	}
	if(properties[2]<3) {
		error(obj_count, 5);
		return false;
	}

	type=CYLINDER;
	bout.write((unsigned char*)&type, 1);
	bout.write((unsigned char*)cent_orient, 2*sizeof(Vect3D));
	bout.write((unsigned char*)properties, 3*sizeof(int));
	tessilate_cone(cent_orient[0], cent_orient[1], properties[0], properties[0], properties[1], properties[2], polygons);
	return true;	
}
bool parse_cone(ifstream &vin, ofstream &bout, Poly_List &polygons) {
	Vect3D cent_orient[2];
	int properties[4];
	char buf[128], type;

	skip_white(vin, buf);
	vin >> cent_orient[0] >> cent_orient[1];
	vin >> properties[0] >> properties[1] >> properties[2] >> properties[3];
	skip_white(vin, buf);
	buf[5]=0;
	if(strcmp(buf, "[end]")!=0) {
		error(obj_count, 3);
		return false;
	}
	if(properties[3]>MAX_VERTEXES) {
		error(obj_count, 0);
		return false;
	}
	if(properties[3]<3) {
		error(obj_count, 5);
		return false;
	}

	type=CONE;
	bout.write((unsigned char*)&type, 1);
	bout.write((unsigned char*)cent_orient, 2*sizeof(Vect3D));
	bout.write((unsigned char*)properties, 4*sizeof(int));
	tessilate_cone(cent_orient[0], cent_orient[1], properties[0], properties[1], properties[2], properties[3], polygons);
	return true;	
}
// *********************************************************

// *********************************************************
void parse_binary_object(ifstream &bin, Poly_List &polygons) {
	Poly curr_poly;
	Vect3D vertex[MAX_VERTEXES];
	int properties[2];
	int num_in_list[MAX_VERTEXES], face_list[32][MAX_VERTEXES];

	bin.read((unsigned char*)properties, 2*sizeof(int));
	bin.read((unsigned char*)vertex, properties[0]*sizeof(Vect3D));
	for(int i=0; i<properties[1]; i++) {
		bin.read((unsigned char*)&num_in_list[i], sizeof(int));
		bin.read((unsigned char*)&face_list[i][0], num_in_list[i]*sizeof(int));
	}

	for(int i=0; i<properties[1]; i++) {
		curr_poly.clear();
		for(int j=0; j<num_in_list[i]; j++)
			curr_poly.add(vertex[face_list[i][j]]);
		curr_poly.solve();
		polygons.push_back(curr_poly);
	}
}
void parse_binary_sphere(ifstream &bin, Poly_List &polygons) {
	Vect3D center;
	int properties[4];

	bin.read((unsigned char*)¢er,sizeof(Vect3D));
	bin.read((unsigned char*)properties, 4*sizeof(int));
	tessilate_sphere(center, properties[0], properties[1],  properties[2], properties[3], polygons);
}
void parse_binary_cylinder(ifstream &bin, Poly_List &polygons) {
	Vect3D cent_orient[2];
	int properties[3];

	bin.read((unsigned char*)cent_orient,2*sizeof(Vect3D));
	bin.read((unsigned char*)properties, 3*sizeof(int));
	tessilate_cone(cent_orient[0], cent_orient[1], properties[0], properties[0], properties[1], properties[2], polygons);
}
void parse_binary_cone(ifstream &bin, Poly_List &polygons) {
	Vect3D cent_orient[2];
	int properties[4];

	bin.read((unsigned char*)cent_orient,2*sizeof(Vect3D));
	bin.read((unsigned char*)properties, 4*sizeof(int));
	tessilate_cone(cent_orient[0], cent_orient[1], properties[0], properties[1], properties[2], properties[3], polygons);
}
#endif 

#ifndef _OBJ_UTILS_H
#define _OBJ_UTILS_H

char error_list[][32]={"TOO MANY VERTEXES", "MISSING FACE LIST", "BAD FACE INDEX", "NO END", "DUPLICATE", "NOT ENOUGH TESSILATIONS"};

void tessilate_sphere(Vect3D &, int, int, int, int, Poly_List &);
void tessilate_cone(Vect3D &, Vect3D &, int, int, int, int, Poly_List &);

//********************************************************
inline void error(int obj_num, int err) {
	cout << "\n\t\t MALFORMED OBJECT  < " << obj_num << " >\n";
	cout << "\t\t  - " <<  error_list[err] << endl;
}
inline void skip_white(ifstream &in, char *buf) {
	do { 
		in.getline(buf, 128, '\n');
	} while(buf[0]==0  ||  buf[0]=='#');
}
int count_commas(char *buf) {
	int count=0;
	for(unsigned int i=0; i<strlen(buf); i++)
		if(buf[i]==',') count++;
	return count;
}
int next_comma(char *buf, int pos) {
	int comma_pos=0;
	for(unsigned int i=pos; i<strlen(buf); i++)
		if(buf[i]==',') {	comma_pos=i;	break; }
	return comma_pos;
}
bool duplicate(Poly &poly, Poly_List &polygons) {
	for(poly_Iter=polygons.begin(); poly_Iter!=polygons.end(); ++poly_Iter)
		if(poly==(*poly_Iter)) return true;
	return false;
}
//********************************************************

void tessilate_sphere(Vect3D ¢er, int radius, int degrees, int vert, int horiz, Poly_List &polygons) {
	Poly curr_poly;
	Vect3D n_pole;
	Matrix rotator;
	double cur_y, cur_y2, cur_func, cur_sqrt, step_v, arc_length;
	int radius_2, curr_rotate, rotate_step;
	int offsetA, offsetB, offsetC, offsetD, index, index2;

	radius_2=radius*radius;
	curr_rotate=rotate_step=360/horiz;
	n_pole.set(center.getx(), center.gety()+radius, center.getz());
	arc_length=float(degrees)/360.0F;
	step_v = (float(radius)*arc_length) / ((float(vert)-1)/2.0F);
	Vect3D tessilation[horiz][vert];

	cur_y=0;
	for(index=0; index<vert; index++) {
		cur_y=radius-(index*step_v);
		cur_func=radius_2-(cur_y*cur_y);
		if(cur_func>-0.1 && cur_func<0.1)
			cur_func=0;
		if(cur_func<0) {
			cur_y2=radius-(cur_y-radius);
			cur_func=radius_2-(cur_y2*cur_y2);
		}
		cur_sqrt=sqrt(cur_func);
		tessilation[0][index].setx(n_pole.getx() + cur_sqrt);
		tessilation[0][index].sety(n_pole.gety() - cur_y);
		tessilation[0][index].setz(n_pole.getz());
	}

	for(index=1; index<horiz; index++) {
		rotator.setIdentity();
		rotator.rotate(Vect3D(0,curr_rotate, 0));
		curr_rotate+=rotate_step;
		for(index2=0; index2<vert; index2++) {
			tessilation[index][index2]=rotator.cross(tessilation[0][index2]-center);
			tessilation[index][index2]+=center;
		}	
	}


	for(index=horiz-1; index>-1; index--) {
		offsetA=index;
		offsetB=(index+1) % horiz;
		for(index2=0; index2<vert; index2++) {
			offsetC=index2;
			offsetD=((index2+1)==vert) ? 0 : index2+1;
			curr_poly.add(tessilation[offsetA][offsetD]);
			curr_poly.add(tessilation[offsetB][offsetD]);
			curr_poly.add(tessilation[offsetB][offsetC]);
			curr_poly.add(tessilation[offsetA][offsetC]);
			curr_poly.solve();
			polygons.push_back(curr_poly);
			curr_poly.clear();
		}
	}
}


void tessilate_cone(Vect3D ¢er, Vect3D &orientation, int radius, int radius2, int height, int vert, Poly_List &polygons) {
	Poly curr_poly;
	Vect3D n_pole;
	Matrix rotator;
	double cur_y, cur_y2, cur_func, cur_sqrt, step_v;
	int radius_2, half_limit, index, index2;
	int offsetA, offsetB;

	rotator.rotate(orientation);
	radius_2=radius*radius;
	n_pole.set(center.getx(), center.gety()+radius, center.getz());
  half_limit=(vert/2);
	step_v = (radius*2) / half_limit;
	Vect3D tessilation[2][vert];

	cur_y=0;
	for(index=0; index<half_limit+1; index++) {
		cur_y=radius-(index*step_v);
		cur_func=radius_2-(cur_y*cur_y);
		if(cur_func>-0.1 && cur_func<0.1)
			cur_func=0;
		if(cur_func<0) {
			cur_y2=radius-(cur_y-radius);
			cur_func=radius_2-(cur_y2*cur_y2);
		}
		cur_sqrt=sqrt(cur_func);
		tessilation[0][index].setx(n_pole.getx() + cur_sqrt);
		tessilation[0][index].sety(n_pole.gety() - cur_y);
		tessilation[0][index].setz(n_pole.getz());
		if(index>0 && index<half_limit) {
			tessilation[0][vert-index].setx(n_pole.getx() - (tessilation[0][index].getx()-n_pole.getx()) );
			tessilation[0][vert-index].sety(tessilation[0][index].gety());
			tessilation[0][vert-index].setz(n_pole.getz());
		}
	}

	radius_2=radius2*radius2;
	n_pole.set(center.getx(), center.gety()+radius2+(radius-radius2), center.getz()+height);
	step_v = (radius2*2) / half_limit;

	cur_y=0;
	for(index=0; index<half_limit+1; index++) {
		cur_y=radius2-(index*step_v);
		cur_func=radius_2-(cur_y*cur_y);
		if(cur_func>-0.1 && cur_func<0.1)
			cur_func=0;
		if(cur_func<0) {
			cur_y2=radius2-(cur_y-radius2);
			cur_func=radius_2-(cur_y2*cur_y2);
		}
		cur_sqrt=sqrt(cur_func);
		tessilation[1][index].setx(n_pole.getx() + cur_sqrt);
		tessilation[1][index].sety(n_pole.gety() - cur_y);
		tessilation[1][index].setz(n_pole.getz());
		if(index>0 && index<half_limit) {
			tessilation[1][vert-index].setx(n_pole.getx() - (tessilation[1][index].getx()-n_pole.getx()) );
			tessilation[1][vert-index].sety(tessilation[1][index].gety());
			tessilation[1][vert-index].setz(n_pole.getz());
		}
	}

	for(index=0; index<2; index++) {
		for(index2=0; index2<vert; index2++) {
			tessilation[index][index2]=rotator.cross(tessilation[index][index2]-center);
			tessilation[index][index2]+=center;
		}
	}

	for(index=0; index<vert; index++)
		curr_poly.us_add(tessilation[1][index]);
	curr_poly.solve();
	polygons.push_back(curr_poly);
	curr_poly.clear();

	for(index=vert-1; index>-1; index--)
		curr_poly.us_add(tessilation[0][index]);
	curr_poly.solve();
	polygons.push_back(curr_poly);
	curr_poly.clear();

	for(index=0; index<vert; index++) {
		offsetA=index;
		offsetB=(index+1) % vert;
		curr_poly.us_add(tessilation[1][offsetA]);
		curr_poly.us_add(tessilation[0][offsetA]);
		curr_poly.us_add(tessilation[0][offsetB]);
		curr_poly.us_add(tessilation[1][offsetB]);
		curr_poly.solve();
		polygons.push_back(curr_poly);
		curr_poly.clear();
	}
}

#endif 

#ifndef _Poly_H
#define _Poly_H

/*
******************************************************************************************
	Main Header for Poly
	NOTE:
		Look carefully at my code to check for poly/plane classification
		It is very different than others
			In every other code that iv seen, given a quad defined as points (p0,p1,p2,p3),
				|
				|
			p0*-------* p1
				|				|
				|				|
			p3*-------* p2
				|
				|
			if p0 & p3 were CO_PLANAR and 
				 p1 & p2 were FRONT
			the poly would be split     HELL NO!!!!!
			it could be considered as FRONT in this case since no front->back crossover exists
			ALL other code i have come accros assumes that just because the classification changes
			(ie from CO_PLANAR to FRONT) it must be split
		More robust this way
******************************************************************************************
*/

class Poly;
typedef list<Poly>  	Poly_List;
Poly_List::iterator		poly_Iter;

void SCR_project();
void SCR_render();
bool clip(int);

extern int just_traverse_BSP, no_offscreen_draw;

class Plane {
public:
	Vect3D normal;
	double dist_origin;

	Plane(): dist_origin(0) {}
	Plane(const Plane &plane):normal(plane.normal), dist_origin(plane.dist_origin) {}

	Vect3D point_on_plane() const; // find a point on the plane, trying not to DIV_0
	double dist          (const Point3D &) const; // spatial determination [front/back test]
	int    classify      (const Poly &) const;

	Plane &operator=(const Plane &p);
 };
//******************************************************************************************

class Poly {
protected:
	void transform();
	bool clip_to_fustrum();
public:
	static Poly clipped_poly;

	Vect3D vertex[MAX_VERTEXES];
	Plane  plane;
	int num_vertexes;
	bool used;

	Poly() :num_vertexes(0), used(false) {}
	Poly(const Poly &);
	~Poly() {}

	bool operator==(const Poly &);
	Poly& operator=(const Poly &);
	void set(const Poly &);					// copy only num_vertexes and vertex array    used in clip

	void clear() {num_vertexes=0;}
	void add(const Point3D &);
	void us_add(const Point3D &);  // UnSafe add   does not accound for current vertex number
	void solve();
	void draw();
};
//******************************************************************************************

Plane &Plane::operator=(const Plane &rhs) {
	normal=rhs.normal;
	dist_origin=rhs.dist_origin;
	return *this;
}

int  Plane::classify(const Poly &poly) const {
	double d;
	register int i;
	bool front, back, coplanar;

	front=back=coplanar=false;

	if((poly.plane.normal==normal) && (poly.plane.dist_origin==dist_origin)) {
		return CO_PLANAR;
	}

	for(i=0;i<poly.num_vertexes; i++) {
		d=dist(poly.vertex[i]);

		if(d > -CLIP_PLANE_EPSILON  &&  d < CLIP_PLANE_EPSILON) {
			coplanar=true;
		}
		if(d>CLIP_PLANE_EPSILON) {
			front=true;
		}
		if(d<-CLIP_PLANE_EPSILON) {
			back=true;
		}
	}
	if(front && back) return SPANNING;
	if(coplanar && front) return FRONT;
	if(coplanar && back)  return BACK;
	if(front) 	 return FRONT;
	if(back) 		 return BACK;
	return CO_PLANAR;
}

Vect3D Plane::point_on_plane() const{
	if(normal.getx())
		return Vect3D(dist_origin/normal.getx(),0,0);
	else if(normal.gety())
		return Vect3D(0, dist_origin/normal.gety(),0);
	else
		return Vect3D(0,0,dist_origin/normal.getz());  // FIXME: Possible DIV_0
}

double Plane::dist(const Point3D &point_in_space) const {
	return (point_in_space-point_on_plane()).dot(normal);
}
//******************************************************************************************
Poly::Poly(const Poly &poly): plane(poly.plane), num_vertexes(poly.num_vertexes), used(poly.used) {
	memcpy(vertex, poly.vertex, num_vertexes*sizeof(Vect3D));
}

bool Poly::operator==(const Poly &p) {
	if(num_vertexes!=p.num_vertexes) return false;
	for(int i=0; i<num_vertexes; i++)
		if(vertex[i]!=p.vertex[i]) return false;
	return true;
}

Poly& Poly::operator=(const Poly &rhs) {
	plane=rhs.plane;
	used=rhs.used;
	num_vertexes=rhs.num_vertexes;
	memcpy(vertex, rhs.vertex, num_vertexes*sizeof(Vect3D));
	return *this;
}
void Poly::set(const Poly &rhs) {
	num_vertexes=rhs.num_vertexes;
	memcpy(vertex, rhs.vertex, num_vertexes*sizeof(Vect3D));
}	

void Poly::solve() {
	Vect3D u,v;

	u=vertex[1]-vertex[0];
	v=vertex[2]-vertex[0];

	plane.normal=u.cross(v);	// find raw normal
	plane.normal.insure_0();  // make sure its not something like   -0.0
	plane.normal.norm();			// normalize
	plane.dist_origin=plane.normal.dot(vertex[0]);
}

void Poly::add(const Point3D &v) {
	for(int i=0; i<num_vertexes; i++)  // must check for duplicated points because of way my clip works
		if(vertex[i]==v) return;

	vertex[num_vertexes++]=v;
}
void Poly::us_add(const Point3D &v) {
	vertex[num_vertexes++]=v;
}

void Poly::transform() {
	clipped_poly.clear();
	for(int i=0; i<num_vertexes; i++)
		clipped_poly.us_add(player.orientation.cross(vertex[i]-player.pos));

}
bool Poly::clip_to_fustrum() {
	if(!clip(LEFT)) return false;
	if(!clip(RIGHT)) return false;
	if(!clip(BOTTOM)) return false;
	return clip(TOP);
}

void Poly::draw() {
	if(just_traverse_BSP) return;

	transform();  // object -> world
	if(!clip_to_fustrum())
		return;

	if(no_offscreen_draw) return;
	SCR_project(); // world -> screen
	SCR_render();		// screen ->  well.... to the lowlevel rasterizer for the  SCREEN  doh!
}
//******************************************************************************************
Poly Poly::clipped_poly;
#endif 

#ifndef _SHARE3D_H
#define _SHARE3D_H

Plane fustrum[4];

void build_fustrum() {
	return;
	double angle,c,s;

	angle=(FOV*0.5)*PI_180;
	c=cos(angle);
	s=sin(angle);

	fustrum[TOP].normal.set(0,-s,c);
	fustrum[TOP].dist_origin=fustrum[TOP].normal.dot(player.pos);

	fustrum[BOTTOM].normal.set(0,s,c);
	fustrum[BOTTOM].dist_origin=fustrum[BOTTOM].normal.dot(player.pos);

	fustrum[LEFT].normal.set(s,0,c);
	fustrum[LEFT].dist_origin=fustrum[LEFT].normal.dot(player.pos);

	fustrum[RIGHT].normal.set(-s,0,c);
	fustrum[RIGHT].dist_origin=fustrum[RIGHT].normal.dot(player.pos);
}

void init_space() {
	ASPECT= 0.75*((double)XRES/(double)YRES);
	V_DX = h_X / tan((FOV*0.5)*PI_180);
	V_DY = ((h_Y*ASPECT) / XRES) * V_DX * 2;
	build_fustrum();
}

/*
===========
clip
	World space clip
	All verticies are transformed and then simply comparison tested out
	only works for 90 FOV right now
	DAMN i just cant get this stuff right
	This is also the SLOWWEST part of my rendering pipeline
		next to my TERRIBLY SLOWER subdividing affine tex-mapper  curtesy of Chris Hecker who,
		despite my inability to mimick his greatness, is still quite awesome
	Also this doesnt recalculate the u,v texels for a poly since i dont know how and because the rest
	of the code is not ready for it.
===========
*/
bool clip(int index) {
	Poly inside;
	Point3D isect, pA, pB;
	register double dx,dy,dz,scalar;
	int offsetA, offsetB, num;
	bool dA, dB;

	dA=dB=false;
	scalar=0;
	num=Poly::clipped_poly.num_vertexes;
	for(int i=0; i<num; i++) {
		offsetA=i;
		offsetB=(i+1) % num;
		pA=Poly::clipped_poly.vertex[offsetA];
		pB=Poly::clipped_poly.vertex[offsetB];
		switch(index) {
			case LEFT:
				dA=(pA.getx()>=(-pA.getz()+CLIP_PLANE_EPSILON));
				dB=(pB.getx()>=(-pB.getz()+CLIP_PLANE_EPSILON));
				break;
			case RIGHT:
				dA=(pA.getx()<=(pA.getz()+CLIP_PLANE_EPSILON));
				dB=(pB.getx()<=(pB.getz()+CLIP_PLANE_EPSILON));
				break;
			case BOTTOM:
				dA=(pA.gety()<=(pA.getz()+CLIP_PLANE_EPSILON));
				dB=(pB.gety()<=(pB.getz()+CLIP_PLANE_EPSILON));
				break;
			case TOP:
				dA=(pA.gety()>=(-pA.getz()+CLIP_PLANE_EPSILON));
				dB=(pB.gety()>=(-pB.getz()+CLIP_PLANE_EPSILON));
				break;
		}

		if(dA==dB) {
			if(dA) {
				inside.add(pA);
				inside.add(pB);
			}
		}
		else {
			dx = pB.getx() - pA.getx();
			dy = pB.gety() - pA.gety();
			dz = pB.getz() - pA.getz();
			switch(index) {
				case LEFT:
					scalar=(pA.getx() + pA.getz()) / (-dz-dx);
					break;
				case RIGHT:
					scalar=(pA.getx() - pA.getz()) / (-dx+dz);
					break;
				case BOTTOM:
					scalar=(pA.gety() - pA.getz()) / (-dy+dz);
					break;
				case TOP:
					scalar=(pA.gety() + pA.getz()) / (-dz-dy);
					break;
			}
			isect.setx(pA.getx() + (pB.getx()-pA.getx())*scalar);
			isect.sety(pA.gety() + (pB.gety()-pA.gety())*scalar);
			isect.setz(pA.getz() + (pB.getz()-pA.getz())*scalar);
			inside.us_add(isect);
			if(dB)
				inside.us_add(pB);
		}
	}
	if(inside.num_vertexes<3)
		return false;

	Poly::clipped_poly.set(inside);	
	return true;
}
#endif 

/*

This material is Copyright 1995, 1996 Chris Hecker, All Rights Reserved.
It's for you to read and learn from, not to put in your own articles
or books or on your website, etc.  Thank you.

Chris Hecker
checker@netcom.com


++++++++++++
	Talk to the guy above about this file
	I only quickly converted it using an easier naming convention and to OOP to suit my needs
	NEEDS ASM BADLY
*/

/******** structures, inlines, and function declarations **********/
extern BITMAP *TestTexture[4];
extern BITMAP *offscreen;

class gradients_suba;
class edge_suba;
void DrawScanLine_suba(edge_suba *pLeft, edge_suba *pRight);

class gradients_suba {
public:
	float One_Z[3];				// 1/z for each vertex
	float U_Z[3];				// u/z for each vertex
	float V_Z[3];				// v/z for each vertex
	float One_Z_dX, One_Z_dY;	// d(1/z)/dX, d(1/z)/dY
	float U_Z_dX, U_Z_dY;		// d(u/z)/dX, d(u/z)/dY
	float V_Z_dX, V_Z_dY;		// d(v/z)/dX, d(v/z)/dY
	fixed16_16 dUdXMod;
	fixed16_16 dVdXMod;

	gradients_suba() {}
	void setup(P3D const *pVertices);
};

void gradients_suba::setup(P3D const *pVertices) {
	int counter;
	
	fixed28_4 X1Y0 = fixed28_4Mul(pVertices[1].x - pVertices[2].x, pVertices[0].y - pVertices[2].y);
	fixed28_4 X0Y1 = fixed28_4Mul(pVertices[0].x - pVertices[2].x, pVertices[1].y - pVertices[2].y);
	float OneOverdX = 1.0 / fixed28_4tof(X1Y0 - X0Y1);

	float OneOverdY = -OneOverdX;

	for(counter = 0;counter < 3;counter++) {
		float const OneOverZ = 1/pVertices[counter].z;
		One_Z[counter] = OneOverZ;
		U_Z[counter] = pVertices[counter].u * OneOverZ;
		V_Z[counter] = pVertices[counter].v * OneOverZ;
	}

	One_Z_dX = OneOverdX * (((One_Z[1] - One_Z[2]) *
			fixed28_4tof(pVertices[0].y - pVertices[2].y)) - ((One_Z[0] - One_Z[2]) *
			fixed28_4tof(pVertices[1].y - pVertices[2].y)));
	One_Z_dY = OneOverdY * (((One_Z[1] - One_Z[2]) *
			fixed28_4tof(pVertices[0].x - pVertices[2].x)) - ((One_Z[0] - One_Z[2]) *
			fixed28_4tof(pVertices[1].x - pVertices[2].x)));

	U_Z_dX = OneOverdX * (((U_Z[1] - U_Z[2]) *
			fixed28_4tof(pVertices[0].y - pVertices[2].y)) - ((U_Z[0] - U_Z[2]) *
			fixed28_4tof(pVertices[1].y - pVertices[2].y)));
	U_Z_dY = OneOverdY * (((U_Z[1] - U_Z[2]) *
			fixed28_4tof(pVertices[0].x - pVertices[2].x)) - ((U_Z[0] - U_Z[2]) *
			fixed28_4tof(pVertices[1].x - pVertices[2].x)));

	V_Z_dX = OneOverdX * (((V_Z[1] - V_Z[2]) *
			fixed28_4tof(pVertices[0].y - pVertices[2].y)) -
			((V_Z[0] - V_Z[2]) * fixed28_4tof(pVertices[1].y - pVertices[2].y)));
	V_Z_dY = OneOverdY * (((V_Z[1] - V_Z[2]) *
			fixed28_4tof(pVertices[0].x - pVertices[2].x)) - 	((V_Z[0] - V_Z[2]) * 
			fixed28_4tof(pVertices[1].x - pVertices[2].x)));

	fixed16_16 const Half = 0x8000;
	fixed16_16 const PosModifier = Half;
	fixed16_16 const NegModifier = Half - 1;

	float dUdXIndicator = U_Z_dX * One_Z[0] - U_Z[0] * One_Z_dX;

	if(dUdXIndicator > 0)
		dUdXMod = PosModifier;
	else {
		if(dUdXIndicator < 0)
			dUdXMod = NegModifier;
		else 	{
			float dUdYIndicator = U_Z_dY * One_Z[0] - U_Z[0] * One_Z_dY;

			if(dUdYIndicator >= 0)
				dUdXMod = PosModifier;
			else
				dUdXMod = NegModifier;
		}
	}

	float dVdXIndicator = V_Z_dX * One_Z[0] - V_Z[0] * One_Z_dX;

	if(dVdXIndicator > 0)
		dVdXMod = PosModifier;
	else {
		if(dVdXIndicator < 0)
			dVdXMod = NegModifier;
		else {
			float dVdYIndicator = V_Z_dY * One_Z[0] - V_Z[0] * One_Z_dY;

			if(dVdYIndicator >= 0)
				dVdXMod = PosModifier;
			else
				dVdXMod = NegModifier;
		}
	}
}

class edge_suba {
public:
	long X, XStep, Numerator, Denominator;			// DDA info for x
	long ErrorTerm;
	int Y, Height;					// current y and vertical count
	float OneOverZ, OneOverZStep, OneOverZStepExtra;// 1/z and step
	float UOverZ, UOverZStep, UOverZStepExtra;		// u/z and step
	float VOverZ, VOverZStep, VOverZStepExtra;		// v/z and step

	edge_suba(gradients_suba const &Gradients, P3D const *pVertices, int Top, int Bottom);
	inline int Step();
};

edge_suba::edge_suba(gradients_suba const &Gradients, P3D const *pVertices, int Top, int Bottom) {
	Y = ceil28_4(pVertices[Top].y);
	int YEnd = ceil28_4(pVertices[Bottom].y);
	Height = YEnd - Y;

	if(Height) {
		long dN = pVertices[Bottom].y - pVertices[Top].y;
		long dM = pVertices[Bottom].x - pVertices[Top].x;
	
		long InitialNumerator = dM*16*Y - dM*pVertices[Top].y +
					dN*pVertices[Top].x - 1 + dN*16;
		FloorDivMod(InitialNumerator,dN*16,X,ErrorTerm);
		FloorDivMod(dM*16,dN*16,XStep,Numerator);
		Denominator = dN*16;
	
		float YPrestep = fixed28_4tof(Y*16 - pVertices[Top].y);
		float XPrestep = fixed28_4tof(X*16 - pVertices[Top].x);
	
		OneOverZ = Gradients.One_Z[Top] + YPrestep * Gradients.One_Z_dY + XPrestep * Gradients.One_Z_dX;
		OneOverZStep = XStep * Gradients.One_Z_dX + Gradients.One_Z_dY;
		OneOverZStepExtra = Gradients.One_Z_dX;
	
		UOverZ = Gradients.U_Z[Top] + YPrestep * Gradients.U_Z_dY + XPrestep * Gradients.U_Z_dX;
		UOverZStep = XStep * Gradients.U_Z_dX + Gradients.U_Z_dY;
		UOverZStepExtra = Gradients.U_Z_dX;
	
		VOverZ = Gradients.V_Z[Top] + YPrestep * Gradients.V_Z_dY + XPrestep * Gradients.V_Z_dX;
		VOverZStep = XStep * Gradients.V_Z_dX + Gradients.V_Z_dY;
		VOverZStepExtra = Gradients.V_Z_dX;
	}
}

inline int edge_suba::Step() {
	X += XStep; Y++; Height--;
	UOverZ += UOverZStep; VOverZ += VOverZStep; OneOverZ += OneOverZStep;

	ErrorTerm += Numerator;
	if(ErrorTerm >= Denominator) {
		X++;
		ErrorTerm -= Denominator;
		OneOverZ += OneOverZStepExtra;
		UOverZ += UOverZStepExtra;
		VOverZ += VOverZStepExtra;
	}
	return Height;
}	

/******** TextureMapTriangle **********/
gradients_suba Gradients;
BITMAP *dest, *texture;
int dest_deltascan, tex_deltascan;

void TextureMapTri(BITMAP *Dest, P3D const *pVertices, BITMAP *Texture) {
	int Top, Middle, Bottom, MiddleForCompare, BottomForCompare;
	fixed28_4 Y0 = pVertices[0].y, Y1 = pVertices[1].y,	Y2 = pVertices[2].y;

	// put in global lookup so dont have to pass it in drawscanline function call  saves asm 'push' statements
	// ok... so i did modify it    so shoot me!
	texture=Texture;
	dest=Dest;
	dest_deltascan=((dest->w   +3) & ~3);
	tex_deltascan=((texture->w +3) & ~3);
	
 
	if(Y0 < Y1) {
		if(Y2 < Y0) {
			Top = 2; Middle = 0; Bottom = 1;
			MiddleForCompare = 0; BottomForCompare = 1;
		}
		else {
			Top = 0;
			if(Y1 < Y2) {
				Middle = 1; Bottom = 2;
				MiddleForCompare = 1; BottomForCompare = 2;
			}
			else {
				Middle = 2; Bottom = 1;
				MiddleForCompare = 2; BottomForCompare = 1;
			}
		}
	}
	else {
		if(Y2 < Y1) {
			Top = 2; Middle = 1; Bottom = 0;
			MiddleForCompare = 1; BottomForCompare = 0;
		}
		else {
			Top = 1;
			if(Y0 < Y2) {
				Middle = 0; Bottom = 2;
				MiddleForCompare = 3; BottomForCompare = 2;
			}
			else {
				Middle = 2; Bottom = 0;
				MiddleForCompare = 2; BottomForCompare = 3;
			}
		}
	}

	Gradients.setup(pVertices);
	edge_suba TopToBottom(Gradients,pVertices,Top,Bottom);
	edge_suba TopToMiddle(Gradients,pVertices,Top,Middle);
	edge_suba MiddleToBottom(Gradients,pVertices,Middle,Bottom);
	edge_suba *pLeft, *pRight;
	int MiddleIsLeft;

	// the triangle is clockwise, so if bottom > middle then middle is right
	if(BottomForCompare > MiddleForCompare) {
		MiddleIsLeft = 0;
		pLeft = &TopToBottom; pRight = &TopToMiddle;
	}
	else {
		MiddleIsLeft = 1;
		pLeft = &TopToMiddle; pRight = &TopToBottom;
	}

	int Height = TopToMiddle.Height;

	while(Height--) {
		DrawScanLine_suba(pLeft,pRight);
		TopToMiddle.Step(); TopToBottom.Step();
	}

	Height = MiddleToBottom.Height;

	if(MiddleIsLeft) {
		pLeft = &MiddleToBottom;
		pRight = &TopToBottom;
	}
	else {
		pLeft = &TopToBottom;
		pRight = &MiddleToBottom;
	}
	
	while(Height--) {
		DrawScanLine_suba(pLeft,pRight);
		MiddleToBottom.Step(); TopToBottom.Step();
	}
}

void DrawScanLine_suba(edge_suba *pLeft, edge_suba *pRight) {
	int XStart = pLeft->X;
	int Width = pRight->X - XStart;

	// attempting to port a windows DIB BITMAP to Allegro BITMAPS really sucked
	// mostly because i never touced WIN before in my life
	// had to go off of my knowedge of how (id's)Doom did it also
	// dont know how to get out of 8bit color yet as of 2000/7/14

	unsigned char  *pDestBits = &dest->line[pLeft->Y][XStart];
	unsigned char  *pTextureBits = texture->line[0];

	long TextureDeltaScan = tex_deltascan;

	int const AffineLength = 8;

	float OneOverZLeft = pLeft->OneOverZ;
	float UOverZLeft = pLeft->UOverZ;
	float VOverZLeft = pLeft->VOverZ;

	float One_Z_dXAff = Gradients.One_Z_dX * AffineLength;
	float U_Z_dXAff = Gradients.U_Z_dX * AffineLength;
	float V_Z_dXAff = Gradients.V_Z_dX * AffineLength;

	float OneOverZRight = OneOverZLeft + One_Z_dXAff;
	float UOverZRight = UOverZLeft + U_Z_dXAff;
	float VOverZRight = VOverZLeft + V_Z_dXAff;

	float ZLeft = 1/OneOverZLeft;
	float ULeft = ZLeft * UOverZLeft;
	float VLeft = ZLeft * VOverZLeft;

	float ZRight, URight, VRight;
	fixed16_16 U, V, DeltaU(0), DeltaV(0);

	if(Width > 0) {
		int Subdivisions = Width / AffineLength;
		int WidthModLength = Width % AffineLength;

		if(!WidthModLength)	{
			Subdivisions--;
			WidthModLength = AffineLength;
		}

		while(Subdivisions-- > 0)	{
			ZRight = 1/OneOverZRight;
			URight = ZRight * UOverZRight;
			VRight = ZRight * VOverZRight;
	
			U = fto16_16(ULeft) + Gradients.dUdXMod;
			V = fto16_16(VLeft) + Gradients.dVdXMod;
			DeltaU = fto16_16(URight - ULeft) / AffineLength;
			DeltaV = fto16_16(VRight - VLeft) / AffineLength;

			for(int counter = 0;counter < AffineLength;counter++)	{
				int UInt = U>>16;
				int VInt = V>>16;

				*(pDestBits++) = *(pTextureBits + UInt + (VInt * TextureDeltaScan));

				U += DeltaU;
				V += DeltaV;
			}
	
			ZLeft = ZRight;
			ULeft = URight;
			VLeft = VRight;
	
			OneOverZRight += One_Z_dXAff;
			UOverZRight += U_Z_dXAff;
			VOverZRight += V_Z_dXAff;
		}
	
		if(WidthModLength) {
			ZRight = 1/(pRight->OneOverZ - Gradients.One_Z_dX);
			URight = ZRight * (pRight->UOverZ - Gradients.U_Z_dX);
			VRight = ZRight * (pRight->VOverZ - Gradients.V_Z_dX);

			U = fto16_16(ULeft) + Gradients.dUdXMod;
			V = fto16_16(VLeft) + Gradients.dVdXMod;

			if(--WidthModLength) {
				// guard against div-by-0 for 1 pixel lines
				DeltaU = fto16_16(URight - ULeft) / WidthModLength;
				DeltaV = fto16_16(VRight - VLeft) / WidthModLength;
			}
	
			for(int counter = 0;counter <= WidthModLength;counter++) {
				int UInt = U>>16;
				int VInt = V>>16;
	
				*(pDestBits++) = *(pTextureBits + UInt + (VInt * TextureDeltaScan));
		
				U += DeltaU;
				V += DeltaV;
			}
		}
	}
}
 

#ifndef _BASE_3D_H
#define _BASE_3D_H

#include <allegro.h>
#include <list>

#include <fstream>
#include <iomanip>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <climits>

const double CLIP_PLANE_EPSILON = 0.0001;

const double MOVEMENT_SPEED	=	64.0;
const double MAX_MOVEMENT_SPEED	=	256.0;

const int CO_PLANAR =  0;  // BSP classifications
const int BACK      =	-1;
const int FRONT     =	 1;
const int SPANNING  =	-2;

const int TOP				=	0;  // fustrum index
const int BOTTOM		=	1;
const int LEFT			=	2;
const int RIGHT			=	3;

const int OBJECT		=	1;	// object id
const int SPHERE		=	2;
const int CYLINDER	=	3;
const int CONE			=	4;

const int MAX_VERTEXES =	16;


BITMAP *offscreen;
int XRES, YRES;
double ASPECT, h_X, h_Y, V_DX, V_DY, FOV;

#include "Math3D.h"

#include "Cam.h"
#include "Poly.h"

#include "BSP_Utils.h"
#include "BSP.h"

#include "OBJ_Utils.h"
#include "OBJ_IO.h"
#include "OBJ.h"

#include "Share3D.h"
#include "SubAffine.h"
#include "Draw3D.h"

#endif
 

#include <dos.h>
#include <conio.h>

#include "Base_3D.h"

volatile int FPS            =0;
volatile int CURR_FPS       =0;
volatile int FPS_Count			=0;
int  _FPS_   = 60;
int _MSEC_=(int) (1193181 / (_FPS_));
void FPS_counter() {
	FPS=1;
}
END_OF_FUNCTION(FPS_counter);

void increm_FPS_count() {
  FPS_Count++;
}
END_OF_FUNCTION(increm_FPS_count);


BITMAP *TestTexture[4];
int num_NON_backface_polys=0, num_polys=0, num_tris=0;
int just_traverse_BSP=0, no_offscreen_draw=0;
int tex_LUT=0;
long total_frames=0;
double xpos,ypos,zpos,xrot,yrot,zrot,scale;

Vect3D sc,tr,ro, motion, movement;
double current_speed=0;
void process_input();

int main(int argc, char **argv) {
	PALETTE pal;
	BSP_Tree Tree;
	Poly_List polygons;

	char buf[32],ans;
	volatile int T_FPS=0;
	clrscr();
	cout << "\t\t\t-------------------------\n";
	cout << "\t\t\t|  TEST  VERSION 0.7.0  |\n";
	cout << "\t\t\t| ********************* |\n";
	cout << "\t\t\t| Fix Clip (u,v)   .1   |\n";
	cout << "\t\t\t| PerPoly Textures .0.5 |\n";
	cout << "\t\t\t| World Collision  .1.5 |\n";
	cout << "\t\t\t-------------------------\n\n";

	if(argc<2) {
		cout << "Specify vertex file." << endl;
		return 1;
	}

	strcpy(buf, argv[1]);
	if(buf[strlen(buf)-4] != '.')
		strcat(buf, ".t3d");
	
	if(stricmp(buf+strlen(buf)-3, "b3d")!=0)
		read_OBJ(buf, polygons);
	else
		read_binary_OBJ(buf, polygons);
	cout << "  Inserted " << polygons.size() << " (Poly's) into list.\n";

	Tree.build(polygons);
	polygons.clear();
	cout << "  Tree built with " << Tree.size() << " polygons in " << Tree.leafs() << " leafs.\n\n";

	xpos=ypos=zpos=xrot=yrot=zrot=0;
	scale=1;
	ypos=256;
	zpos=-5000;
	player.pos.set(xpos,ypos,zpos);
	ro.set(xrot,yrot,zrot);

	XRES=800;
	YRES=600;
	h_X=XRES/2;
	h_Y=YRES/2;
	FOV=90;
	init_space();

	cout << "About to begin main loop...\n";
	cout << "Proceed with test  [y/n]: ";
	cin >> ans;
	if(ans=='n' || ans=='N')
		return 0;

	allegro_init();
	install_keyboard();
	install_timer();
	set_color_conversion(COLORCONV_TOTAL);
	set_gfx_mode(GFX_AUTODETECT, XRES, YRES, 0, 0);

	TestTexture[0]=load_bmp("TestTexture.bmp", pal);
	TestTexture[1]=load_bmp("TestTexture1.bmp", pal);
	TestTexture[2]=load_bmp("TestTexture2.bmp", pal);
	TestTexture[3]=load_bmp("TestTexture3.bmp", pal);
	set_palette(pal);

	LOCK_VARIABLE(FPS);
	LOCK_VARIABLE(CURR_FPS);
	LOCK_VARIABLE(T_FPS);
	LOCK_FUNCTION(FPS_counter);
	install_int_ex(FPS_counter,MSEC_TO_TIMER(1000));

	LOCK_VARIABLE(FPS_Count);
  LOCK_FUNCTION(increm_FPS_count);
  install_int_ex(increm_FPS_count,_MSEC_);

	offscreen=create_bitmap(XRES,YRES);

	clear(screen);
	clear(offscreen);

	player.orientation.transform(sc, tr, ro);
	clear_keybuf();

	while (!key[KEY_ESC]) {
		while(FPS_Count>0) {
			num_NON_backface_polys=num_polys=num_tris=0;
			clear(offscreen);
			rect(offscreen, 0,0, XRES-1, YRES-1, 255);	

			Tree.render();

			if(FPS==1) {
				FPS=0;
				T_FPS=CURR_FPS;
				CURR_FPS=0;
			}
			itoa(T_FPS,buf,10);
			textout(offscreen, font,buf,10,10,255);	

			total_frames++;
			itoa(total_frames,buf,10);
			textout(offscreen, font,buf,100,10,255);

			itoa(num_NON_backface_polys, buf, 10);
			textout(offscreen, font, buf, 600, 10, 255);
			itoa(num_polys, buf, 10);
			textout(offscreen, font, buf, 600, 20, 255);
			itoa(num_tris, buf, 10);
			textout(offscreen, font, buf, 600, 30, 255);


			itoa((int)current_speed, buf, 10);
			textout(offscreen, font, buf, 10, 420, 255);
			itoa((int)player.pos.getx(), buf, 10);
			textout(offscreen, font, buf, 10, 440, 255);
			itoa((int)player.pos.gety(), buf, 10);
			textout(offscreen, font, buf, 10, 450, 255);
			itoa((int)player.pos.getz(), buf, 10);
			textout(offscreen, font, buf, 10, 460, 255);
		
			blit(offscreen, screen, 0, 0, 0, 0, XRES, YRES);
			process_input();
			CURR_FPS++;
			FPS_Count--;
		}
	}
	clear_keybuf();
	textout(screen, font, "Test ended. Hit a key.", 320, 240, 255);
	readkey();
	return 0;
}

void process_input() {
	movement.set(player.orientation[8], player.orientation[9], player.orientation[10]);
	motion.set(movement.dot(Vect3D(1,0,0)), 0, movement.dot(Vect3D(0,0,1)));

	player.pos += motion*current_speed;

	if(key[KEY_Y]) {
		if (key_shifts & KB_SHIFT_FLAG)
			player.pos.sety(player.pos.gety()+18.0F);
		else
			player.pos.sety(player.pos.gety()-18.0F);
	}

	if(key[KEY_E]) {
			current_speed+=MOVEMENT_SPEED;
			if(current_speed > MAX_MOVEMENT_SPEED) current_speed=MAX_MOVEMENT_SPEED;
	}
	if(key[KEY_D]) {
			current_speed-=MOVEMENT_SPEED;
			if(current_speed < -MAX_MOVEMENT_SPEED) current_speed=-MAX_MOVEMENT_SPEED;
	}

	if(key[KEY_F]) {
			yrot+=0.9F;
	}
	if(key[KEY_A]) {
			yrot-=0.9F;
	}

	if(key[KEY_S]) {
		if (key_shifts & KB_SHIFT_FLAG)
			xrot+=0.9F;
		else
			xrot-=0.9F;
	}

	if(key[KEY_R]) {
		xpos=0;
		ypos=256;
		zpos=-5000;
		xrot=yrot=zrot=0;
		player.pos.set(xpos,ypos,zpos);
	}

	if(key[KEY_B])
		just_traverse_BSP^=1;
	if(key[KEY_O])
		no_offscreen_draw^=1;

	if(key[KEY_0])
		tex_LUT = 0;
	if(key[KEY_1])
		tex_LUT = 1;
	if(key[KEY_2])
		tex_LUT = 2;
	if(key[KEY_3])
		tex_LUT = 3;


	player.orientation.setIdentity();
	ro.set(xrot, yrot, zrot);
	player.orientation.rotate(ro);  // create new xform

	build_fustrum();

  if (current_speed > (MOVEMENT_SPEED  / 2.0))
    current_speed -= MOVEMENT_SPEED / 2.0;
  else if (current_speed < -(MOVEMENT_SPEED  / 2.0))
    current_speed += MOVEMENT_SPEED  / 2.0;
  else
    current_speed = 0;
}