Half-Life BSP viewer

From GPWiki

This is a great reference for both how to load and render the data stored in BSPv30 files which is the BSP version used for Half-Life 1.

There is some collision detection code but apparently it has problems.

/*
* HL rendering engine
* Copyright (c) 2000,2001 Bart Sekura
*
* Permission to use, copy, modify and distribute this software
* is hereby granted, provided that both the copyright notice and
* this permission notice appear in all copies of the software,
* derivative works or modified versions.
*
* THE AUTHOR ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
* CONDITION AND DISCLAIMS ANY LIABILITY OF ANY KIND FOR ANY DAMAGES
* WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
*
* core engine logic
* XXX this file is way too big...
*/
 
#include "common.h"
#include "engine.h"
#include "texture.h"
#include "wad.h"
#include "bsp.h"
#include "exception.h"
#include "image.h"
#include "bitset.h"
#include "Model_MDL.h"
#include "glext.h"
#include "matrix.h"
 
#include "fastmath.h"
#include <math.h>
 
#include <mmsystem.h>
 
#include <fstream>
#include <string>
using namespace std;
 
////////////////////////////////////////////////////////////////
static bool use_multi = true;
////////////////////////////////////////////////////////////////
static Model_MDL model;
 
////////////////////////////////////////////////////////////
class texture_t {
public:
    texture_t() : t(0) {}
    ~texture_t() { if(t) delete t; }
 
    void bind() { t->bind(); }
    Texture* t;
    string name;
};
 
#define MAX_LIGHTMAPS    (4)
class face_t {
public:
    face_t() : texture(-1), lightmap(0), next(0) {
        for(int i = 0; i < MAX_LIGHTMAPS;i++) {
            styles[i] = -1;
            lightmaps[i] = 0;
        }
    }
    ~face_t() {
        for(int i = 0; i < MAX_LIGHTMAPS; i++) {
            if(lightmaps[i]) {
                delete lightmaps[i];
                lightmaps[i] = 0;
                styles[i] = -1;
            }
        }
    }
 
    int type;
    int flags;
    int texture; // index into texture
    Texture* lightmap; // current lightmap
    Texture* lightmaps[MAX_LIGHTMAPS];
    int         styles[MAX_LIGHTMAPS];
 
    dplane_t plane;
    plane_t p;
    int side;
 
    int first;
    int count;
 
    face_t* next;
};
 
struct frustum_plane_t {
    vec3_t normal;
    float dist;
};
 
template<const int elem_size>
class array_t {
public:
#define CHUNK   (4096)
    array_t() {
        size = CHUNK*elem_size;
        data = new float[size];
        count = 0;
    }
 
    ~array_t() {
        if(data) {
            delete data;
            data = 0;
        }
    }
 
    void add(float* src) {
        if(count >= size/elem_size) {
            //resize
            int s = size;
            size += CHUNK*elem_size;
            float* n = new float[size];
            for(int i = 0; i < s; i++) {
                n[i] = data[i];
            }
            delete data;
            data = n;
        }
 
        float* dst = data + count*elem_size;
        for(int i = 0; i < elem_size; i++) {
            *dst++ = *src++;
        }
        count++;
    }
 
    operator float*(void) const { return data; }
    const float* operator[](int i) const { return data + i*elem_size; }
 
    int current() const { return count; }
 
private:
    int size;
    int count;
    float* data;
};
 
static array_t<3> vt_array;
static array_t<2> st_array;
static array_t<2> lst_array;
 
///////////////////////////////////////////////////////
typedef vector<int> int_vec;
 
class world_t {
public:
    world_t() : bsp(0), mark_faces(0) {}
    ~world_t() { cleanup(); }
 
    void load(const char* file);
    void wad(const char* file) { wads.add(file); }
 
    void projection_setup(int width, int height);
    void process_visible_faces(const Camera& cam);
    void render_visible_faces();
    void render_model(int i);
 
    // collision stuff
    vec3_t check_collisions(const vec3_t& src, const vec3_t& dir);
 
    //accessors
    int render_count() const { return rendered; }
 
protected:
    void cleanup();
 
    int find_texture(const char* name) {
        for(int i = 0; i < textures.size(); i++) {
            if(textures[i]->name == name) {
                return i;
            }
        }
 
        return -1;
    }
 
    void frustum_setup(const Camera& cam);
    bool frustum_cull(const short* mins, const short* maxs);
    int find_leaf(const vec3_t& coords);
    void render_face(const face_t* f);
    void decompress();
 
private:
    bsp_file_t*         bsp;
    bitset*             mark_faces;
    vector<face_t*>     faces;
    vector<texture_t*>  textures;
    wad_man_t           wads;
    vector<int_vec>     leaf_visibility;
 
    // visible faces by texture index
    vector<face_t*>     visible_faces;
 
    // frustum clipping planes
    frustum_plane_t frustum_planes[5];
 
    // frustum params
    double projection;
    double angle_horiz;
    double angle_vert;
    double sin_horiz;
    double cos_horiz;
    double sin_vert;
    double cos_vert;
 
    // statistics
    int clip_count;
    int rendered;
};
 
void
world_t::cleanup()
{
    int i;
    for(i = 0; i < faces.size(); i++) {
        if(faces[i]) delete faces[i];
    }
    for(i = 0; i < textures.size(); i++) {
        if(textures[i]) delete textures[i];
    }
    if(mark_faces) {
        delete mark_faces, mark_faces = 0;
    }
    if(bsp) {
        delete bsp, bsp = 0;
    }
    for(i = 0; i < visible_faces.size(); i++) {
        visible_faces[i] = 0;
    }
    leaf_visibility.clear();
}
 
void
world_t::decompress()
{
    for(int i = 0; i < bsp->leaf_count; i++) {
        int_vec visible;
        dleaf_t& leaf = bsp->leaves[i];
        int v = leaf.visofs;
        const byte* vis = bsp->vis;
        for(int c = 1; c < bsp->models[0].visleafs; v++) {
            if(vis[v] == 0) {
                v++;
                c+=(vis[v]<<3);
            }
            else {
                for(byte bit = 1; bit; bit<<=1,c++) {
                    if(vis[v] & bit) {
                        visible.push_back(c);
                    }
                }
            }
        }    
 
        leaf_visibility.push_back(visible);
    }
}
 
void
world_t::load(const char* file)
{
    cleanup();
    bsp = new bsp_file_t(file);
    if(!bsp) throw out_of_memory();
 
    // basic setup
    decompress();
 
    // setup...
    mark_faces = new bitset(bsp->face_count);
    if(!mark_faces) throw out_of_memory();
    faces.resize(bsp->face_count); // for 1:1 index mapping
 
    // setup textures, faces and lightmaps...
    for(int i = 0; i < bsp->face_count; i++) {
 
        dface_t* f = bsp->faces + i;
        face_t* face = new face_t;
        if(!face) throw out_of_memory();
 
        // get plane info
        memcpy(&face->plane, bsp->planes + f->planenum, sizeof(dplane_t));
        face->side = f->side;
 
        // determine best primitive type
        switch(f->numedges) {
        case 3: face->type = GL_TRIANGLES; break;
        case 4: face->type = GL_QUADS; break;
        default: face->type = GL_POLYGON;
        }
 
        // get texture
        // create a new one if it doesn't exist yet
        texinfo_t* ti = bsp->texinfo + f->texinfo;
        face->flags = ti->flags;
        const char* tex_name = strlwr(bsp->textures[ti->miptex].name);
        int x = find_texture(tex_name);
        if(x == -1) {
            texture_t* t = new texture_t;
            if(!t) throw out_of_memory();
            t->name = tex_name;
 
            rgb_image_t r;
            wads.get(tex_name, &r);            
            if(!r.data) {
                throw basic_exception("r.data");
            }
 
            t->t = new Texture(r.data, r.width, r.height, GL_RGB);
            if(!t->t) throw out_of_memory();
            textures.push_back(t);
            x = textures.size()-1;
        }
        face->texture = x; // texture index
 
        //
        // the following computations are based on:
        // PolyEngine (c) Alexey Goloshubin
        //
        
        // compute s and t extents
        float min[2],max[2];
        min[0]=min[1]=100000;
        max[0]=max[1]=-100000;
 
        for(int c = 0; c < f->numedges; c++) {
            dvertex_t* v;
            int eidx = bsp->edge_list[f->firstedge + c];
            if(eidx >= 0) {
                v = bsp->vertices + bsp->edges[eidx].v[0];
            } else {
                v = bsp->vertices + bsp->edges[-eidx].v[1];
            }
 
            // compute extents
            for(int x = 0; x < 2; x++) {
                float d = v->point[0] * ti->vecs[x][0] +
                          v->point[1] * ti->vecs[x][1] +
                          v->point[2] * ti->vecs[x][2] +
                          ti->vecs[x][3];
 
                if(d < min[x]) min[x] = d;
                if(d > max[x]) max[x] = d;
            }            
        }
 
        int lw,lh;
        if(face->flags==0) {
            // compute lightmap size
            int size[2];
            for(c = 0; c < 2; c++) {
                float tmin = (float) floor(min[c]/16.0f);
                float tmax = (float) ceil(max[c]/16.0f);
 
                size[c] = (int) (tmax-tmin);
            }
            lw = size[0]+1;
            lh = size[1]+1;
 
            int lsz = lw*lh*3;
            // generate lightmaps texture
            for(c = 0; c < 1/*MAX_LIGHTMAPS*/; c++) {
                if(f->styles[c] == -1) break;
                face->styles[c] = f->styles[c];
                rgb_image_t r;
                r.width = lw;
                r.height = lh;
                r.data = new byte[lsz];
                memcpy(r.data,bsp->lightmaps+f->lightofs+(lsz*c),lsz);
                face->lightmaps[c] =
                    new Texture(r.data, r.width, r.height, GL_RGB,
                                Texture::nearest_mipmap_nearest);
            }
 
            face->lightmap = face->lightmaps[0];
        }
 
#if 0
        static ofstream o("lightmaps.log");
        o << "face[" << i << "]: ";
        for(c = 0; c < MAX_LIGHTMAPS; c++) {
            o << face->styles[c] << " ";
        }
        o << endl;
#endif        
        
        //////////////////////////////////////////////////////
 
        float is = 1.0f/(float)bsp->textures[ti->miptex].width;
        float it = 1.0f/(float)bsp->textures[ti->miptex].height;
 
        face->first = vt_array.current();
        face->count = f->numedges;
        for(c = 0; c < f->numedges; c++) {
            float v[7];
            int eidx = *(bsp->edge_list + f->firstedge + c);
            if(eidx < 0) {
                eidx = -eidx;
                dedge_t* e = bsp->edges + eidx;
                v[0] = bsp->vertices[e->v[1]].point[0];
                v[1] = bsp->vertices[e->v[1]].point[1];
                v[2] = bsp->vertices[e->v[1]].point[2];
            }
            else {
                dedge_t* e = bsp->edges + eidx;
                v[0] = bsp->vertices[e->v[0]].point[0];
                v[1] = bsp->vertices[e->v[0]].point[1];
                v[2] = bsp->vertices[e->v[0]].point[2];
            }
 
            vec3_t vertex = v;
            float s = vertex.dot(ti->vecs[0]) + ti->vecs[0][3];
            float t = vertex.dot(ti->vecs[1]) + ti->vecs[1][3];
 
            v[3] = s*is;
            v[4] = t*it;
 
            if(face->flags==0) {
                // compute lightmap coords
                float mid_poly_s = (min[0] + max[0])/2.0f;
                float mid_poly_t = (min[1] + max[1])/2.0f;
                float mid_tex_s = (float)lw / 2.0f;
                float mid_tex_t = (float)lh / 2.0f;
                float ls = mid_tex_s + (s - mid_poly_s) / 16.0f;
                float lt = mid_tex_t + (t - mid_poly_t) / 16.0f;
                ls /= (float) lw;
                lt /= (float) lh;
 
                v[5] = ls;
                v[6] = lt;
            }
 
            ////////////////////////
            vt_array.add(v);
            st_array.add(v+3);          
            lst_array.add(v+5);
        }
        
        ///////////////////////////////
        vec3_t n = face->plane.normal;
        float d = face->plane.dist;
        if(face->side) {
            face->p = plane_t(-n,d);
        }
        else {
            face->p = plane_t(n,-d);
        }
 
        // add face
        faces[i] = face;
    }
 
    // set visible faces size to total texture count
    visible_faces.resize(textures.size());
 
    // setup vertex arrays
    glEnableClientState(GL_VERTEX_ARRAY);
    glEnableClientState(GL_TEXTURE_COORD_ARRAY);
    glVertexPointer(3, GL_FLOAT, 0, vt_array);
 
    if(use_multi) {
        glClientActiveTextureARB(GL_TEXTURE0_ARB);
        glEnableClientState(GL_TEXTURE_COORD_ARRAY);
        glTexCoordPointer(2, GL_FLOAT, 0, st_array);
 
        glClientActiveTextureARB(GL_TEXTURE1_ARB);
        glEnableClientState(GL_TEXTURE_COORD_ARRAY);
        glTexCoordPointer(2, GL_FLOAT, 0, lst_array);
    }
}
 
static double znear = 1.0;
 
struct frustum_t {
    double left;
    double right;
    double bottom;
    double top;
    double znear;
    double zfar;
};
 
static frustum_t frustum;
 
static void
set_znear()
{
    glMatrixMode(GL_PROJECTION);
    glLoadIdentity();
    glFrustum(frustum.left, frustum.right,
              frustum.bottom, frustum.top,
              znear, frustum.zfar);
    glMatrixMode(GL_MODELVIEW);
}
 
void
world_t::projection_setup(int width, int height)
{
    glViewport(0, 0, width, height);
    glMatrixMode(GL_PROJECTION);
 
    double aspect = (double) height/ (double) width;
    double fovx   = 80;
    double rprojz = tan(deg2rad(fovx)*0.5);
 
    glLoadIdentity();
    glFrustum(-rprojz, +rprojz, -aspect*rprojz, +aspect*rprojz, znear, 6000.0);
 
    frustum.left = -rprojz;
    frustum.right = +rprojz;
    frustum.bottom = -aspect*rprojz;
    frustum.top = +aspect*rprojz;
    frustum.znear = 1.0;
    frustum.zfar = 6000.0;
 
    double s = sin(deg2rad(fovx)*0.5);
    double c = cos(deg2rad(fovx)*0.5);
 
    // precompute stuff for frustum culling
    projection = (c*(double)(width>>1))/s;
    angle_horiz = atan2((double)(width>>1),projection);
    angle_vert = atan2((double)(height>>1),projection);
    sin_horiz = sin(angle_horiz);
    sin_vert = sin(angle_vert);
    cos_horiz = cos(angle_horiz);
    cos_vert = cos(angle_vert);
 
    // back to model view
    glMatrixMode(GL_MODELVIEW);
}
 
void
world_t::frustum_setup(const Camera& c)
{
    const matrix_t& m = c.matrix();
    const vec3_t& cam = c.eye();
 
    int i = 0;
    vec3_t v;
 
    // znear plane
    v = vec3_t(0,0,1);
    frustum_planes[i].normal = m*v;
    frustum_planes[i].dist = cam.dot(frustum_planes[i].normal);
    i++;
 
    // left plane
    v = vec3_t(cos_horiz,0,sin_horiz);
    frustum_planes[i].normal = m*v;
    frustum_planes[i].dist = cam.dot(frustum_planes[i].normal);
    i++;
 
    // right plane
    v = vec3_t(-cos_horiz,0,sin_horiz);
    frustum_planes[i].normal = m*v;
    frustum_planes[i].dist = cam.dot(frustum_planes[i].normal);
    i++;
 
    // top plane
    v = vec3_t(0,cos_vert,sin_vert);
    frustum_planes[i].normal = m*v;
    frustum_planes[i].dist = cam.dot(frustum_planes[i].normal);
    i++;
 
    // bottom plane
    v = vec3_t(0,-cos_vert,sin_vert);
    frustum_planes[i].normal = m*v;
    frustum_planes[i].dist = cam.dot(frustum_planes[i].normal);
    i++;
}
 
bool
world_t::frustum_cull(const short* mins, const short* maxs)
{
    for(int i = 0; i < 5; i++) {
        const short* min = mins, *max = maxs;
        const float* n = frustum_planes[i].normal;
        float d = -frustum_planes[i].dist;
        d += (*n>0 ? (*n*(float)*min) : (*n*(float)*max)); min++, max++; n++;
        d += (*n>0 ? (*n*(float)*min) : (*n*(float)*max)); min++, max++; n++;
        d += (*n>0 ? (*n*(float)*min) : (*n*(float)*max)); min++, max++; n++;
        if(d>0) { clip_count++; return true; }
    }
    return false;
}
 
int
world_t::find_leaf(const vec3_t& coords)
{
    int i = bsp->models[0].bsp_node;
    while(i>=0) {
        dnode_t* n = &bsp->nodes[i];
        dplane_t* p = &bsp->planes[n->planenum];
 
        float d;
        if(p->type <= PLANE_Z) { // easier for axial planes
            d = coords[p->type] - p->dist;
        }
        else {
            // f(x,y,z) = Ax+Ay+Az-D
            d = p->normal[0]*coords[0]
               +p->normal[1]*coords[1]
               +p->normal[2]*coords[2]
               -p->dist;
        }
 
        if(d >= 0) { // in front or on the plane
            i = n->front;
        }
        else { // behind the plane
            i = n->back;
        }
    }
 
    return -(i+1);
}
 
void
world_t::render_face(const const face_t* f)
{
    if(use_multi) {
        glActiveTextureARB(GL_TEXTURE0_ARB);
        textures[f->texture]->bind();
        glEnable(GL_TEXTURE_2D);
 
        if(f->lightmap) {
            glActiveTextureARB(GL_TEXTURE1_ARB);
            f->lightmap->bind();
            glEnable(GL_TEXTURE_2D);
        }
 
        glDrawArrays(f->type, f->first, f->count);
 
        if(f->lightmap) {
            glActiveTextureARB(GL_TEXTURE1_ARB);
            glDisable(GL_TEXTURE_2D);
        }
        glActiveTextureARB(GL_TEXTURE0_ARB);
        glDisable(GL_TEXTURE_2D);
    }
    else {
 
        textures[f->texture]->bind();
        glTexCoordPointer(2, GL_FLOAT, 0, st_array);
        glDrawArrays(f->type, f->first, f->count);
        
        if(f->lightmap) {
            glBlendFunc(GL_ZERO, GL_SRC_COLOR);
            glEnable(GL_BLEND);
            glDepthMask(GL_FALSE);
            glDepthFunc(GL_EQUAL);
 
            f->lightmap->bind();
            glTexCoordPointer(2, GL_FLOAT, 0, lst_array);
            glDrawArrays(f->type, f->first, f->count);
        
            glDisable(GL_BLEND);
            glDepthMask(GL_TRUE);
            glDepthFunc(GL_LESS);
        }
    }
}
 
////////////////////////////////////////////////////////////
 
class collision_data {
public:
    collision_data() : found(false), nearest(-1.0f), dir_len(0.0f) {}
 
    vec3_t src;
    vec3_t dir;
    vec3_t ndir;
    float  dir_len;
 
    bool found;
    float nearest;
    vec3_t nearest_poly;
};
 
static bool
point_in_poly(const vec3_t& p, const face_t* f)
{
    vec3_t v[32]; // BAD SHIT
    for(int i = 0; i < f->count; i++) {
        int c = f->first + i;
        v[i] = p - vec3_t(vt_array[c]);
        v[i].normalize();
    }
 
    float total = 0.0f;
    for(i = 0; i < f->count-1; i++) {
        total += (float) acos(v[i].dot(v[i+1]));
    }
    total += (float) acos(v[f->count-1].dot(v[0]));
 
    if(fabsf(total-6.28f)<0.01f) {
        return true;
    }
 
    return false;
}
 
static vec3_t
closest_on_line(const vec3_t& a, const vec3_t& b, const vec3_t& p)
{
    vec3_t c = p-a;
    vec3_t v = b-a;
    float d = v.len();
    if(d) v/=d; // normalize avoiding len() again (nasty sqrt)
    float t = v.dot(c);
    if(t < 0.0f) return a;
    if(t > d) return b;
    return a+v*t;
}
 
static vec3_t
closest_on_poly(const vec3_t& p, const face_t* f)
{
    vec3_t v[32];
    float d[32];
    for(int i = 0; i < f->count-1; i++) {
        int c = f->first + i;
        v[i] = closest_on_line(vec3_t(vt_array[c]),
                               vec3_t(vt_array[c+1]),
                               p);
        vec3_t t = p-v[i];
        d[i] = t.len();
    }
    i = f->count-1;
    v[i] = closest_on_line(vec3_t(vt_array[f->first + i]),
                           vec3_t(vt_array[f->first]),
                           p);
    vec3_t t = p-v[i];
    d[i] = t.len();
 
    float min = d[0];
    vec3_t r = v[0];
 
    for(i = 1; i < f->count; i++) {
        if(d[i] < min) {
            min = d[i];
            r = v[i];
        }
    }  
 
    return r;
}
 
static float
intersect(const vec3_t& r0,
          const vec3_t& rn,
          const vec3_t& p0,
          const vec3_t& pn)
{
    float d = -pn.dot(p0);
 
    float numer = pn.dot(r0) + d;
    float denom = pn.dot(rn);
  
    if(denom <= -0.001f || denom >= 0.001f) {
        return -(numer/denom);
    }
    return -1.0f;
}
 
static float
intersect_sphere(const vec3_t& r,
                 const vec3_t& rv,
                 const vec3_t& s,
                 float sr)
{
    vec3_t q = s-r;
    float c = q.len();
    float v = q.dot(rv);
    float d = sr*sr - (c*c-v*v);
 
    if(d < 0.0f) return -1.0f;
    return v-sqrt(d);
}
 
static void
check_collision(const face_t* f, collision_data& coldat)
{
    vec3_t r;
    vec3_t pt(vt_array[f->first]);
    vec3_t n = f->p.normal();
    float radius = 15.0f;
    vec3_t s = coldat.src - n*radius;
    float t = f->p.dist_to_point(s);
 
    if(t > coldat.dir_len) {
        return;
    }
    if(t < -2*radius) {
        return;
    }
 
    if(t < 0.0f) {
        //t = intersect(s,n,pt,n);
        //r = s + n*t;
        if(!f->p.intersect(s,n*radius,pt,r)) return;
    }
    else {
        //t = intersect(s,coldat.ndir,pt,n);
        //r = s + coldat.ndir*t;
        if(!f->p.intersect(s,coldat.dir,pt,r)) return;
    }
 
    if(!point_in_poly(r,f)) {
        r = closest_on_poly(r,f);
    }
 
    t = intersect_sphere(r,-coldat.ndir,coldat.src,radius);
    if(t >= 0.0f && t <= coldat.dir_len) {
        if(!coldat.found || t < coldat.nearest) {
            coldat.found = true;
            coldat.nearest = t;
            coldat.nearest_poly = r;
        }
    }
}
 
static int cutoff = 0;
 
vec3_t
world_t::check_collisions(const vec3_t& src, const vec3_t& dir)
{
    if(++cutoff>5) return src;
 
    collision_data coldat;
    coldat.src = src;
    coldat.dir = dir;
    coldat.dir_len = dir.len();
 
    if(coldat.dir_len < 0.001f) {
        return src;
    }
 
    coldat.ndir = coldat.dir/coldat.dir_len;
    for(int i = 0; i < visible_faces.size(); i++) {
        face_t* f = visible_faces[i];
        while(f) {
            check_collision(f, coldat);
            f = f->next;
        }
    }
 
    if(coldat.found) {
        vec3_t s = src;
        if(coldat.nearest >= 0.001f) {
            s += coldat.ndir*(coldat.nearest-0.001f);
        }
 
        vec3_t dst = src+dir;
        vec3_t n = s - coldat.nearest_poly;
 
        n.normalize();
        float t = intersect(dst,n,coldat.nearest_poly,n);
 
        vec3_t newdst = dst + n*t;
        vec3_t newdir = newdst - coldat.nearest_poly;
 
        return check_collisions(s,newdir);    
    }
 
    return src+(coldat.ndir*(coldat.dir_len-0.001f));
}
 
//////////////////////////////////////////////////////////////
 
static int current_style = 0;
 
void
world_t::process_visible_faces(const Camera& c)
{
    rendered = 0;
    // setup for frustum culling
    frustum_setup(c);
    const vec3_t& cam = c.eye();
 
    // clear stuff
    mark_faces->clear_all();
    zero_dwords((void*) &visible_faces[0], visible_faces.size());
 
    // find leaf we're in
    int idx = find_leaf(cam);
    int_vec& v = leaf_visibility[idx];
 
    // go thru leaf visibility list
    for(int i = 0; i < v.size(); i++) {
        const dleaf_t& leaf = bsp->leaves[v[i]];
 
        // discard leafs outside frustum
        if(!frustum_cull(leaf.mins, leaf.maxs)) {
            unsigned short* p = bsp->marksurfaces + leaf.firstmarksurface;
            for(int x = 0; x < leaf.nummarksurfaces; x++) {
                // don't render those already rendered
                int face_idx = *p++;
                if(!mark_faces->test(face_idx)) {
 
                       // back face culling
                    face_t* f = faces[face_idx];
                    float d = cam.dot(f->plane.normal)-f->plane.dist;
                    if(f->side) {
                        if(d>0) { continue; }
                    } else {
                        if(d<0) { continue; }
                    }
 
                    // mark face as visible
                    mark_faces->set(face_idx);
                    int idx = f->texture;
                    f->next = visible_faces[idx];
                    visible_faces[idx] = f;
                    rendered++;
 
                    // chose lightmap style
                    f->lightmap = f->lightmaps[0];
                    if(current_style != 0) {
                        for(int c = 0; c < MAX_LIGHTMAPS; c++) {
                            if(f->styles[c] == current_style) {
                                f->lightmap = f->lightmaps[c];
                                break;
                            }
                        }
                    }
                }
            }
        }        
    }
}
 
void
world_t::render_visible_faces()
{
    for(int i = 0; i < visible_faces.size(); i++) {
        face_t* f = visible_faces[i];
        while(f) {
            render_face(f);
            f = f->next;
        }
    }
}
 
void
world_t::render_model(int i)
{
    if(i >= 0 && i < bsp->model_count) {
        glPushMatrix();
        dmodel_t* m = &bsp->models[i];
        glTranslatef(m->origin[0],m->origin[1],m->origin[2]);
        for(int c = 0; c < m->numfaces; c++) {
            render_face(faces[m->firstface + c]);
        }
        glPopMatrix();
    }
}
 
////////////////////////////////////////////////////////////////
static world_t world;
 
static matrix_t mm;
 
////////////////////////////////////////////////////////////////
 
Engine::Engine()
: m_font(0),
  m_overlay(false), menu_mode(false),
  m_xcenter(0.0f), m_ycenter(0.0f)
{
}
 
Engine::~Engine()
{
    if(m_font) {
        delete m_font;
        m_font = 0;
    }
}
 
void
Engine::resize()
{
    worl