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.