This section of the archives stores flipcode's complete Developer Toolbox collection, featuring a variety of mini-articles and source code contributions from our readers.

| Leaf-Based BSP Engine Submitted by

This source, DOS/DJGPP/ALLEGRO, is an implementation of a leafy BSP tree like that used in Quake and such. The code is completely original, x-cept the texture mapper, and can be freely and unrestrictively distributed and used. It will render an input set of polys (loaded from my own personal file format) using Chris Hecker's subdividing-affine persp. texture mapper. Even though the engine itself is very primitive, interest should be based mainly around the BSP construction routines such as the convex test, spliting, polygon list partitioning, and traversal. This code also contains camera-space clipping, simple object tessilation, and a foundation for portals, collsion detection, and other general things like this.

Currently browsing [leafbsp.zip] (36,136 bytes) - [Vect3D.h] - (3,867 bytes)

    #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

Currently browsing [leafbsp.zip] (36,136 bytes) - [BSP.h] - (6,442 bytes)

    #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

Currently browsing [leafbsp.zip] (36,136 bytes) - [BSP_Utils.h] - (3,324 bytes)

    #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

Currently browsing [leafbsp.zip] (36,136 bytes) - [Cam.h] - (124 bytes)

    #ifndef _CAM_H
    #define _CAM_H

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

    Camera player;
    #endif

Currently browsing [leafbsp.zip] (36,136 bytes) - [Draw3D.h] - (1,585 bytes)

    #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

Currently browsing [leafbsp.zip] (36,136 bytes) - [Math3D.h] - (998 bytes)

    #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

Currently browsing [leafbsp.zip] (36,136 bytes) - [Matrix.h] - (4,618 bytes)

    #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

Currently browsing [leafbsp.zip] (36,136 bytes) - [OBJ.h] - (2,802 bytes)

    #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

Currently browsing [leafbsp.zip] (36,136 bytes) - [OBJ_IO.h] - (7,066 bytes)

    #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

Currently browsing [leafbsp.zip] (36,136 bytes) - [OBJ_Utils.h] - (6,110 bytes)

    #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

Currently browsing [leafbsp.zip] (36,136 bytes) - [Poly.h] - (5,616 bytes)

    #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

Currently browsing [leafbsp.zip] (36,136 bytes) - [Share3D.h] - (3,134 bytes)

    #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

Currently browsing [leafbsp.zip] (36,136 bytes) - [SubAffine.h] - (10,778 bytes)

    /*

    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;
    			}
    		}
    	}
    }

Currently browsing [leafbsp.zip] (36,136 bytes) - [Base_3D.h] - (1,052 bytes)

    #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

Currently browsing [leafbsp.zip] (36,136 bytes) - [pobj_BSP.cpp] - (5,619 bytes)

    #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;
    }

The zip file viewer built into the Developer Toolbox made use of the zlib library, as well as the zlibdll source additions.

Copyright 1999-2008 (C) FLIPCODE.COM and/or the original content author(s). All rights reserved.
Please read our Terms, Conditions, and Privacy information.