xref: /dports/games/cake/cake_src/cake/q3bsp.cpp

//-----------------------------------------------------------------------------
// Q3 Binary Space Tree
//-----------------------------------------------------------------------------

#include "cake.h"
#include "q3bsp.h"
#include "types.h"
#include "console.h"
#include "logfile.h"
#include "render.h"
#include "vars.h"
#include "math.h"
#include "skybox.h"
#include "overlay.h"
#include "mem.h"
#include "frustum.h"
#include "sound.h"
#include "timer.h"
#include "framework.h"
#include "system.h"

// PVS test macro: PVS table is a packed single bit array, rowsize
// bytes times numclusters rows
#define BSP_TESTVIS(from,to) \
  (*(r_visibility->data + (from)*r_visibility->rowsize + \
  ((to)>>3)) & (1 << ((to) & 7)))

#define DIST_EPSILON (0.03125f)

Var r_drawsky("r_drawsky", 1);
Var r_drawworld("r_drawworld", 1);
Var r_drawmodels("r_drawmodels", 1);
Var r_showcluster("r_showcluster", 0);
Var r_showlbrushes("r_showlbrushes", 0);
Var r_showleafs("r_showleafs", 0);
Var r_showcamleaf("r_showcamleaf", 0);
Var r_nofaces("r_nofaces", 0);
Var r_nocurves("r_nocurves", 0);
Var r_nomesh("r_nomesh", 0);
Var r_noflares("r_noflares", 0);
Var r_noportals("r_noportals", 0);
Var r_nofrustum("r_nofrustum", 0);
Var r_lockpvs("r_lockpvs", 0);
Var r_novis("r_novis", 0);
Var r_surfsky("r_surfsky", 0);
Var r_fillside("r_fillside", -1, VF_DEBUG);
Var r_grid("r_grid", 0);
Var r_normals("r_normals", 0);
Var r_showbbox("r_showbbox", 0);
Var v_selectsurface("v_selectsurface", -1);
Var v_selectpatch("v_selectpatch", -1);
Var v_selectmodel("v_selectmodel", -1);
Var v_bspdebug("v_bspdebug", 0, VF_DEBUG);
Var sys_bspstate("sys_bspstate", INACTIVE, VF_SYSTEM);

int num_leafs = 0, num_leafs_last_frame;
int cam_leaf = -1;          /**< Camera leaf number */
int cam_cluster = -1;       /**< Camera cluster number */

// Initialization
Q3BSP::Q3BSP(char *name, World* w, int *res):LumpFile(name, BSPHEADERID, BSPVERSION, NUM_LUMPS)
{
  sys_bspstate = INACTIVE;

  r_shaderrefs = NULL;
  r_planes = NULL;
  r_nodes = NULL;
  r_leafs = NULL;
  r_leaffaces = NULL;
  r_leafbrushes = NULL;
  r_leafpatches = NULL;
  r_models = NULL;
  r_brushes = NULL;
  r_brushsides = NULL;
  r_verts = NULL;
  r_elems = NULL;
  r_lightmapinfos = NULL;
  r_effects = NULL;
  r_visibility = NULL;
  face_list = NULL;
  r_surfaces = NULL;
  r_patchesgroups = NULL;
  r_skybox = NULL;
  r_lightvols = NULL;
  r_faces = NULL;
  r_patches = NULL;
  r_meshes = NULL;
  r_flares = NULL;
  r_patches = NULL;
  r_entities = NULL;

  worldname = NULL;

  levelshotdetail = levelshot = -1;

  if (!mem)
  {
    gConsole->Insertln("^1ERROR: %s is not a valid map name", name);
    *res = 0;
    return;
  }

  world = w;

  // --- Loading
  gConsole->Insertln("--- Loading bsp \"%s\"", name);

  // Remove the path and extension from map name
  char map_name[256] = { '\0' };
  int lname = (int) strlen(name)-1;
  while (lname >= 0 && name[lname] != '/' && name[lname] != '\\') --lname;
  strcpy(map_name, &name[lname+1]);
  f_StripExtension(map_name);
  LoadLevelshot(map_name);
  DisplayLevelshot();
  gRender->SwapBuffers();

  LoadShaders();
  LoadEntities();
  LoadPlanes();
  LoadNodes();
  LoadLFaces();   // leaf faces before leafs
  LoadLBrushes();   // leaf brushes before leafs
  LoadBrushSides(); // brush sides before brushes
  LoadBrushes();
  LoadLeafs();
  LoadVerts();
  LoadElems();
  LoadEffects();
  LoadFaces();
  LoadModels();
  LoadLightmaps();
  LoadLightVols();
  LoadVisibility();

  // shader references not needed any more (all shaders have been
  // transfered in the world shader manager
  if (r_shaderrefs) cake_free(r_shaderrefs); r_shaderrefs = NULL;

  // init counters
  nodecount = 0;
  viscount = 0;
  checkcount = 0;

  // delete after loading
  delete [] mem;
  mem = NULL;

  gVars->RegisterVar(r_drawsky);
  gVars->RegisterVar(r_drawworld);
  gVars->RegisterVar(r_drawmodels);
  gVars->RegisterVar(r_showcluster);
  gVars->RegisterVar(r_showlbrushes);
  gVars->RegisterVar(r_showleafs);
  gVars->RegisterVar(r_showcamleaf);
  gVars->RegisterVar(r_novis);
  gVars->RegisterVar(r_nofrustum);
  gVars->RegisterVar(r_nofaces);
  gVars->RegisterVar(r_nocurves);
  gVars->RegisterVar(r_nomesh);
  gVars->RegisterVar(r_noflares);
  gVars->RegisterVar(r_noportals);
  gVars->RegisterVar(r_lockpvs);
  gVars->RegisterVar(r_surfsky);
  gVars->RegisterVar(r_fillside);
  gVars->RegisterVar(r_grid);
  gVars->RegisterVar(r_normals);
  gVars->RegisterVar(r_showbbox);
  gVars->RegisterVar(v_selectsurface);
  gVars->RegisterVar(v_selectpatch);
  gVars->RegisterVar(v_selectmodel);
  gVars->RegisterVar(v_bspdebug);
  gVars->RegisterVar(sys_bspstate);

  *res = 1; // success
}

// Shutdown
Q3BSP::~Q3BSP(void)
{
  int i;

  gConsole->Insertln("--- Deleting BSP...");

  sys_bspstate.ivalue = SHUTING;

  world = NULL;

  if (worldname) delete [] worldname;         worldname = NULL;

  if (r_shaderrefs) cake_free(r_shaderrefs);      r_shaderrefs = NULL;
  if (r_planes) cake_free(r_planes);          r_planes = NULL;
  if (r_nodes) cake_free(r_nodes);          r_nodes = NULL;
  if (r_leafs) cake_free(r_leafs);          r_leafs = NULL;
  if (r_leaffaces) cake_free(r_leaffaces);      r_leaffaces = NULL;
  if (r_leafbrushes) cake_free(r_leafbrushes);    r_leafbrushes = NULL;
  if (r_leafpatches) cake_free(r_leafpatches);    r_leafpatches = NULL;
  if (r_models) cake_free(r_models);          r_models = NULL;
  if (r_brushes) cake_free(r_brushes);        r_brushes = NULL;
  if (r_brushsides) cake_free(r_brushsides);      r_brushsides = NULL;
  if (r_verts) cake_free(r_verts);          r_verts = NULL;
  if (r_elems) cake_free(r_elems);          r_elems = NULL;

  for (i = 0; i < r_numlightmaps[0]; ++i) gRender->UnregisterTexInfo(&r_lightmapinfos[i]);
  if (r_lightmapinfos) cake_free(r_lightmapinfos);  r_lightmapinfos = NULL;

  if (r_effects) cake_free(r_effects);        r_effects = NULL;

  if (r_visibility) cake_free(r_visibility);      r_visibility = NULL;

  if (r_skybox) { r_skybox->Shut(); // must be done before face_list destruction
          delete r_skybox; }          r_skybox = NULL;

  if (face_list) delete [] face_list;         face_list = NULL;

  if (r_cpatches) cake_free(r_cpatches);        r_cpatches = NULL;

  if (r_faces)
  {
    for (i = 0; i < r_numfaces[0]; ++i) r_faces[i] = NULL;
    delete [] r_faces;
    r_faces = NULL;
  }

  if (r_patches)
  {
    for (i = 0; i < r_numpatches[0]; ++i) r_patches[i] = NULL;
    delete [] r_patches;
    r_patches = NULL;
  }

  if (r_meshes)
  {
    for (i = 0; i < r_nummeshes[0]; ++i) r_meshes[i] = NULL;
    delete [] r_meshes;
    r_meshes = NULL;
  }

  if (r_flares)
  {
    for (i = 0; i < r_numflares[0]; ++i) r_flares[i] = NULL;
    delete [] r_flares;
    r_flares = NULL;
  }

  if (r_surfaces)
  {
    for (i = 0; i < r_numsurfaces[0]; ++i)
    {
      if (r_surfaces[i].facetype == FACETYPE_PATCH)
      {
        for (int l = 1; l < r_surfaces[i].levels; ++l)
        {
          cake_free(r_surfaces[i].firstvert[l]);
          cake_free(r_surfaces[i].firstelem[l]);
        }
      }
      r_surfaces[i].Shut();
    }
    delete [] r_surfaces;
    r_surfaces = NULL;
  }

  if (r_patchesgroups) delete [] r_patchesgroups;   r_patchesgroups = NULL;

  if (r_lightvols) cake_free(r_lightvols);      r_lightvols = NULL;
  if (r_entities) delete r_entities;          r_entities = NULL;

  gVars->UnregisterVar(r_drawsky);
  gVars->UnregisterVar(r_drawworld);
  gVars->UnregisterVar(r_drawmodels);
  gVars->UnregisterVar(r_showcluster);
  gVars->UnregisterVar(r_showlbrushes);
  gVars->UnregisterVar(r_showleafs);
  gVars->UnregisterVar(r_showcamleaf);
  gVars->UnregisterVar(r_novis);
  gVars->UnregisterVar(r_nofrustum);
  gVars->UnregisterVar(r_nofaces);
  gVars->UnregisterVar(r_nocurves);
  gVars->UnregisterVar(r_nomesh);
  gVars->UnregisterVar(r_noflares);
  gVars->UnregisterVar(r_noportals);
  gVars->UnregisterVar(r_lockpvs);
  gVars->UnregisterVar(r_surfsky);
  gVars->UnregisterVar(r_fillside);
  gVars->UnregisterVar(r_grid);
  gVars->UnregisterVar(r_normals);
  gVars->UnregisterVar(r_showbbox);
  gVars->UnregisterVar(v_selectsurface);
  gVars->UnregisterVar(v_selectpatch);
  gVars->UnregisterVar(v_selectmodel);
  gVars->UnregisterVar(v_bspdebug);
  gVars->UnregisterVar(sys_bspstate);
}

// more initialization
void Q3BSP::Init(void)
{
  sys_bspstate = INITIALIZING;

  Surface *surf;
  Shader *shad;
  int i;

  cam_leaf = -1;
  cam_cluster = -1;

  DisplayLoadingMessage("Initializing faces...");
  InitSurfaces();

  DisplayLoadingMessage("Sorting faces...");
  gConsole->Insertln("Sorting faces...");

  for (i = 0; i < r_numsurfaces[0]; ++i)
  {
    surf = face_list[i].face;
    if (!surf) continue;

    if (surf->shader > -1)
    {
      shad = world->shaders.GetShader(surf->shader);
      face_list[i].sort_value = ((shad->sortvalue) << 16) +
                     (surf->shader << 8) +
                     (surf->lm_texnum + 1);

      // Rotate sprites to default position
      for (int k = 0; k < MAX_DEFORMS; ++k)
      {
        if (shad->deformVertexes[k].type == DEFORMVERTEXES_AUTOSPRITE ||
          shad->deformVertexes[k].type == DEFORMVERTEXES_AUTOSPRITE2)
        {
          InitAutosprite(surf, shad->deformVertexes[k].type);
          break;
        }
      }
    }
    else
    {
      face_list[i].sort_value = 0;
    }

    // Initialize fog parameter for surface
    // FIXME: can it be done at face or effect loading ?
#if MODIF_FOG
    if (surf->effect >=0 && surf->effect < r_numeffects[0])
    {
      if (world->shaders.GetShader(r_effects[surf->effect].shader))
      {
        surf->fogplane = r_planes + r_effects[surf->effect].planeidx;
      }
      else
      {
        surf->fogplane = NULL;
        gConsole->Insertln("^1Face has effect with no shader !!");
      }
    }
    else
    {
      //  if (surf->effect > -1 && r_numeffects[0] == 0)
      //    gConsole->Insertln("^1Face %d/%d uses inexistent effect %d/%d !", i, r_numsurfaces[0], surf->effect, r_numeffects[0]);
      surf->fogplane = NULL;
    }
#else
    if (surf->effect >= 0 && surf->effect < r_numeffects[0] && r_effects[surf->effect].planeidx >= 0)
    {
      cplane_t *p = r_planes + r_effects[surf->effect].planeidx;
      surf->fog[0] = p->normal[0];
      surf->fog[1] = p->normal[1];
      surf->fog[2] = p->normal[2];
      surf->fog[3] = p->dist;
      surf->fog[4] = p->type;
    }
    else
    {
      //if (surf->effect > -1 && r_numeffects[0] == 0)
      //  gConsole->Insertln("^1Face %d/%d uses inexistent effect %d/%d !", i, r_numsurfaces[0], surf->effect, r_numeffects[0]);
      surf->fog[0] = 0;
      surf->fog[1] = 0;
      surf->fog[2] = 1;
      surf->fog[3] = 0;
      surf->fog[4] = 2;
    }
#endif
  }

  // that should be done each time we go int or out water
  qsort((void*)face_list, r_numsurfaces[0], sizeof(render_face_s), FaceCmp);

  // initialize vertice
  DisplayLoadingMessage("Overbrighting verts...");
  float overbright = gVars->ValueForKey("v_overbrightbits");
  if (overbright > 1)
  {
    unsigned int top, r, g, b, a;
    for (int i = 0; i < r_numverts[0]; ++i)
    {
      // overbrighting vertex colors
      top = r = (unsigned int) ((float) r_verts[i].colour[0] * overbright);
      g = (unsigned int) ((float) r_verts[i].colour[1] * overbright);
      b = (unsigned int) ((float) r_verts[i].colour[2] * overbright);
      a = r_verts[i].colour[3];
      if (g > top) top = g;
      if (b > top) top = b;
      if (top > 255)
      {
        top = (255 << 8) / top;
        r = (r * top) >> 8;
        g = (g * top) >> 8;
        b = (b * top) >> 8;
      }

      r_verts[i].colour[0] = r;
      r_verts[i].colour[1] = g;
      r_verts[i].colour[2] = b;
      r_verts[i].colour[3] = a;
    }
  }

  MarkLeafs(-1);

  // Calculate bsp bounding box
  DisplayLoadingMessage("Generating world bounding box...");
  gConsole->Insertln("Generating world bounding box...");
  GenerateBoundingBox(bbox, 0, r_numsurfaces[0]);

  // Adapt camera settings to scene
  vec3_t diag;
  VectorSub(&bbox[3], &bbox[0], diag);
  gVars->SetKeyValue("v_camfar", VectorLength(diag));

  // We generate skybox here because it needs shaders update (cf. world.Init).
  DisplayLoadingMessage("Generating skybox...");
  GenerateSkyBox();

  // Load the entities sounds
  DisplayLoadingMessage("Loading... sounds");
  gConsole->Insertln("Loading sounds...");
  r_entities->Init();

  // Play the background music
  toggleBGMusicPause();

  sys_bspstate = RUNNING;
}

void Q3BSP::SetWorldName(const char *name)
{
  if (!name) return;

  if (worldname) delete [] worldname;
  int l = (int) strlen(name)+1;
  worldname = new char[l];
  memset(worldname, '\0', l);
  strcpy(worldname, name);
}

void Q3BSP::GenerateBoundingBox(bboxf_t destbox, int firstface, int numfaces)
{
  if (!r_surfaces || !r_numsurfaces) return;

  BoxCopy(r_surfaces[firstface].bbox, destbox);

  for (int i = 1; i < numfaces; ++i)
  {
    destbox[0] = min(destbox[0], r_surfaces[firstface+i].bbox[0]);
    destbox[1] = min(destbox[1], r_surfaces[firstface+i].bbox[1]);
    destbox[2] = min(destbox[2], r_surfaces[firstface+i].bbox[2]);
    destbox[3] = max(destbox[3], r_surfaces[firstface+i].bbox[3]);
    destbox[4] = max(destbox[4], r_surfaces[firstface+i].bbox[4]);
    destbox[5] = max(destbox[5], r_surfaces[firstface+i].bbox[5]);
  }
}

void Q3BSP::GenerateSkyBox(void)
{
  gConsole->Insertln("Generating skybox...");

  // Tricky method to get sky shader
  Surface* surf;
  Shader *shad;
  int i, j, k, n = 0, shader_found = 0;

  // Add all sky surfaces to skybox surfaces list
  // Note: I could check only shaders, but I need the number of surfaces that
  //       are skysurfaces. Those faces will be added to skybox skylist to
  //       perform sky polygons clipping at runtime.
  for (i = 0; i < r_numsurfaces[0]; ++i)
  {
    surf = &r_surfaces[i];
    if (!surf || surf->shader < 0) continue;

    shad = world->shaders.GetShader(surf->shader);

    if (shad->surface_flags & SURF_SKY)
    {
      if (!shader_found && surf->effect < 0)
      {
        r_skybox = new SkyBox;
        r_skybox->Init(shad->sky_params.cloudheight);
        r_skybox->clouds_shader = surf->shader;

        for (j = 0; j < 6; ++j)
        {
          for (k = 0; k < shad->sky_params.num_layers; ++k)
          {
            r_skybox->box_shader[j]->num_layers = shad->sky_params.num_layers;
            r_skybox->box_shader[j]->layer[k] = shad->sky_params.layer[k][j];
            r_skybox->box_shader[j]->cull = shad->cull;
            r_skybox->box_shader[j]->flags = shad->flags;
            r_skybox->box_shader[j]->sortvalue = shad->sortvalue;
            r_skybox->box_shader[j]->surface_flags = shad->surface_flags;
            r_skybox->box_shader[j]->content_flags = shad->content_flags;
          }
        }
        shader_found = 1;
      }

      ++n;
    }
  }

  // Define skybox size in function of camera near plane distance
  // @todo Replace v_camnear with a function that check this and autoupdate it
  if (r_skybox) r_skybox->skyboxsize = max(gVars->ValueForKey("v_camfar")/2.f, r_skybox->skyboxsize);

  if (!shader_found)
  {
    gConsole->Insertln("^5WARNING: No sky shader found");
    return;
  }

  // Generate sky surfaces list
  r_skybox->MakeSkyList(n);
  for (i = 0; i < r_numsurfaces[0]; ++i)
  {
    surf = &r_surfaces[i];
    if (!surf || surf->shader < 0) continue;

    shad = world->shaders.GetShader(surf->shader);

    if (shad->surface_flags & SURF_SKY) r_skybox->AddToList(surf);
  }
}

void Q3BSP::CreatePatchesGroups(void)
{
  gConsole->Insertln("Generating patch groups...");

  r_numpatchesgroups[0] = 0;
  r_numpatchesgroups[1] = r_numpatches[0];
  r_patchesgroups = new PatchesGroup[r_numpatchesgroups[1]];
  if (!r_patchesgroups) ThrowException(ALLOCATION_ERROR, "Q3BSP::CreatePatchesGroups.r_patchesgroups");

  bool *rel = new bool[r_numpatches[0]];
  if (!rel) ThrowException(ALLOCATION_ERROR, "Q3BSP::CreatePatchesGroups.rel");
  memset(rel, false, r_numpatches[0]*sizeof(bool)); // initialize the boolean table

  int i, j, k, l, m;
  bool patchadded, addpatch;
  Surface *surf;
  const int deflvl = 0;
  for (i = 0; i < r_numpatches[0]; ++i)
  {
    if (rel[i]) continue; // slip if already in a group

    // add patch i in a new group
    r_patchesgroups[r_numpatchesgroups[0]].Add(i);
    rel[i] = true;      // patch is now in a group

    do
    {
      // While a new patch is added to group, it can have common points with
      // another patch (that had no common point with group before). So we
      // force the loop until no new patch is added
      patchadded = false;   // by default, no new patch is added to group

      for (j = i+1; j < r_numpatches[0]; ++j)   // check all other patches...
      {
        if (rel[j]) continue;         // ...that haven't been added to any patch

        for (m = 0; m < r_patchesgroups[r_numpatchesgroups[0]].nsurf; ++m)
        {
          surf = r_patches[r_patchesgroups[r_numpatchesgroups[0]].surfidx[m]];

#if 0
          // We check if both patches have at the least one common vertex
          addpatch = false;   // let's suppose the patch does not belong to group
          for (k = 0; k < surf->numverts[deflvl]; ++k)
          {
            for (l = 0; l < r_patches[j]->numverts[deflvl]; ++l)
            {
              if (surf->firstvert[deflvl][k].v_point[0] == r_patches[j]->firstvert[deflvl][l].v_point[0]
                && surf->firstvert[deflvl][k].v_point[1] == r_patches[j]->firstvert[deflvl][l].v_point[1]
                && surf->firstvert[deflvl][k].v_point[2] == r_patches[j]->firstvert[deflvl][l].v_point[2])
              {
                addpatch = true;
                break;
              }
            }
            if (addpatch) break;
          }
#else
          // We check if the patch in inside the bounding box of another patch
          // Note: In the bsp file, it seems that patch bounding box are either
          //       (0, 0, 0, 0, 0, 0) or the bounding box of the group
          addpatch = true;    // let's suppose the patch belongs to group
          for (l = 0; l < r_patches[j]->numverts[0]; ++l)
          {
            if (r_patches[j]->firstvert[deflvl][l].v_point[0] < surf->bbox[0] || r_patches[j]->firstvert[deflvl][l].v_point[0] > surf->bbox[3] ||
              r_patches[j]->firstvert[deflvl][l].v_point[1] < surf->bbox[1] || r_patches[j]->firstvert[deflvl][l].v_point[1] > surf->bbox[4] ||
              r_patches[j]->firstvert[deflvl][l].v_point[2] < surf->bbox[2] || r_patches[j]->firstvert[deflvl][l].v_point[2] > surf->bbox[5])
            {
              addpatch = false;
              break;
            }
          }
#endif

          if (addpatch)   // Add the patch j in the group of i
          {
            r_patchesgroups[r_numpatchesgroups[0]].Add(j);
            rel[j] = true;
            patchadded = true;
            break;
          }
        }
      }
    } while(patchadded);

    // the new group is finished
    ++r_numpatchesgroups[0];
  }

  delete [] rel;

  // Calculate the middle vertex of each group
  // TODO: Calculate the bounding box and make tests with the bounding box
  int nverts;
  for (i = 0; i < r_numpatchesgroups[0]; ++i)
  {
    nverts = 0;
    surf = r_patches[r_patchesgroups[i].surfidx[0]];
    r_patchesgroups[i].middle[0] = r_patchesgroups[i].middle[1] = r_patchesgroups[i].middle[2] = 0.f;
    r_patchesgroups[i].bbox[0] = surf->bbox[0];
    r_patchesgroups[i].bbox[1] = surf->bbox[1];
    r_patchesgroups[i].bbox[2] = surf->bbox[2];
    r_patchesgroups[i].bbox[3] = surf->bbox[3];
    r_patchesgroups[i].bbox[4] = surf->bbox[4];
    r_patchesgroups[i].bbox[5] = surf->bbox[5];
    for (j = 0; j < r_patchesgroups[i].nsurf; ++j)
    {
      // middle vertex
      for (k = 0; k < r_patches[r_patchesgroups[i].surfidx[j]]->numverts[deflvl]; ++k)
      {
        r_patchesgroups[i].middle[0] += r_patches[r_patchesgroups[i].surfidx[j]]->firstvert[deflvl][k].v_point[0];
        r_patchesgroups[i].middle[1] += r_patches[r_patchesgroups[i].surfidx[j]]->firstvert[deflvl][k].v_point[1];
        r_patchesgroups[i].middle[2] += r_patches[r_patchesgroups[i].surfidx[j]]->firstvert[deflvl][k].v_point[2];
        ++nverts;
      }

      // bounding box
      if (j > 0)  // j = 0 is already done before the loop
      {
        r_patchesgroups[i].bbox[0] = min(r_patchesgroups[i].bbox[0], r_patches[r_patchesgroups[i].surfidx[j]]->bbox[0]);
        r_patchesgroups[i].bbox[1] = min(r_patchesgroups[i].bbox[1], r_patches[r_patchesgroups[i].surfidx[j]]->bbox[1]);
        r_patchesgroups[i].bbox[2] = min(r_patchesgroups[i].bbox[2], r_patches[r_patchesgroups[i].surfidx[j]]->bbox[2]);
        r_patchesgroups[i].bbox[3] = max(r_patchesgroups[i].bbox[3], r_patches[r_patchesgroups[i].surfidx[j]]->bbox[3]);
        r_patchesgroups[i].bbox[4] = max(r_patchesgroups[i].bbox[4], r_patches[r_patchesgroups[i].surfidx[j]]->bbox[4]);
        r_patchesgroups[i].bbox[5] = max(r_patchesgroups[i].bbox[5], r_patches[r_patchesgroups[i].surfidx[j]]->bbox[5]);
      }

    }
    // size
    r_patchesgroups[i].size = max(r_patchesgroups[i].bbox[3]-r_patchesgroups[i].bbox[0],
                    r_patchesgroups[i].bbox[4]-r_patchesgroups[i].bbox[1]);
    r_patchesgroups[i].size = max(r_patchesgroups[i].size, r_patchesgroups[i].bbox[5]-r_patchesgroups[i].bbox[2]);

    if (!nverts) ThrowException(DIVISION_BY_ZERO, "Q3BSP::CreatePatchesGroups.nverts");
    r_patchesgroups[i].middle[0] /= (float) nverts;
    r_patchesgroups[i].middle[1] /= (float) nverts;
    r_patchesgroups[i].middle[2] /= (float) nverts;
  }

  gConsole->Insertln("\t%d patch groups created", r_numpatchesgroups[0]);
}

// Face comparator for qsort
int Q3BSP::FaceCmp(const void *a, const void *b)
{
  return ((render_face_s*)a)->sort_value - ((render_face_s*)b)->sort_value;
}

// Report info of the bsp
void Q3BSP::Report(void)
{
  int i;

  gLogFile->OpenFile();

  // report info
  gConsole->Insertln("BSP Report:");
  gConsole->Insertln("\tnum surfaces = %d", r_numsurfaces[0]);
  gConsole->Insertln("\t\tnum faces = %d", r_numfaces[0]);
  gConsole->Insertln("\t\tnum patches = %d (%d groups)", r_numpatches[0], r_numpatchesgroups[0]);
  gConsole->Insertln("\t\tnum meshes = %d", r_nummeshes[0]);
  gConsole->Insertln("\t\tnum flares = %d", r_numflares[0]);
  gConsole->Insertln("\tnum lightmaps = %d", r_numlightmaps[0]);
  gConsole->Insertln("\tnum shaders = %d", r_numshaders[0]);
  gConsole->Insertln("\tnum planes = %d", r_numplanes[0]);
  gConsole->Insertln("\tnum nodes = %d", r_numnodes[0]);
  gConsole->Insertln("\tnum leafs = %d", r_numleafs[0]);
  gConsole->Insertln("\tnum leaffaces = %d", r_numleaffaces[0]);
  gConsole->Insertln("\tnum brushes = %d", r_numbrushes[0]);
  gConsole->Insertln("\tnum leafbrushes = %d", r_numleafbrushes[0]);
  gConsole->Insertln("\tnum leafpatches = %d", r_numleafpatches[0]);
  gConsole->Insertln("\tnum models = %d", r_nummodels[0]);
  for (i = 1; i < r_nummodels[0]; ++i)  // model 0 is the map
  {
    gConsole->Insertln("\t\tmodel %d:", i);
    gConsole->Insertln("\t\t\tfirstface %d", r_models[i].firstface);
    gConsole->Insertln("\t\t\tnumfaces %d", r_models[i].numfaces);
  }
  gConsole->Insertln("\tnum verts = %d", r_numverts[0]);
  gConsole->Insertln("\tnum elems = %d", r_numelems[0]);
  gConsole->Insertln("\tnum lightvols = %d", r_numlightvols[0]);
  gConsole->Insertln("\tnum effects = %d", r_numeffects[0]);

  gLogFile->CloseFile();
}

EntityManager* Q3BSP::GetEntities(void)
{
  return r_entities;
}

//-----------------------------------------------------------------------------
// Updating and Drawing
//-----------------------------------------------------------------------------

// Render a new frame of the bsp
void Q3BSP::Update(void)
{
  if (r_drawworld.ivalue) UpdateFaces();
  if (r_skybox && r_drawsky.ivalue) UpdateSky();
}

void Q3BSP::UpdateFaces(void)
{
  Camera *camera = gRender->current_camera;

  // Find camera cluster
  int new_cam_leaf = FindLeaf(camera->pos);
  cleaf_t* currleaf = &r_leafs[new_cam_leaf];
  int i;

  if (new_cam_leaf != cam_leaf)
  {
    cam_leaf = new_cam_leaf;

    if (r_showlbrushes.ivalue)
    {
      char str[1024];
      sprintf(str, "%d leafbrushes: ", currleaf->numleafbrushes);
      for (int i = 0; i < currleaf->numleafbrushes; ++i)
        sprintf(str, "%s%d/", str, r_leafbrushes[currleaf->firstleafbrush+i]);
      gConsole->Insertln(str);
    }

    if (r_showcamleaf.ivalue)
    {
      gConsole->Insertln("leaf: %d\tmiddle: %d %d %d",
        new_cam_leaf,
        (currleaf->bbox[0]+currleaf->bbox[3])/2,
        (currleaf->bbox[1]+currleaf->bbox[4])/2,
        (currleaf->bbox[2]+currleaf->bbox[5])/2);
    }
  }

  // Check if camera is in water
  // FIXME: Can I do that somewhere else... here is not really the good place !
  camera->inWater = false;
  if (currleaf->numleafbrushes)
  {
    Shader* shad;
    int *lbrush = &r_leafbrushes[currleaf->firstleafbrush];
    for (i = 0; i < currleaf->numleafbrushes; ++i, lbrush++)
    {
      if (!(shad = world->shaders.GetShader(r_brushes[*lbrush].shader))) continue;
      if (shad->content_flags & CONTENTS_WATER &&
        PointInsideBrush(*lbrush, camera->pos))
      {
        camera->inWater = true;
        break;
      }
    }
  }

  if (currleaf->cluster != cam_cluster && !r_lockpvs.ivalue)
  {
    if (r_showcluster.ivalue)
      gConsole->Insertln("cluster: %d\tarea: %d", currleaf->cluster, currleaf->area);

    ++nodecount;
    MarkLeafs((r_novis.ivalue)?-1:currleaf->cluster);
    cam_cluster = currleaf->cluster;
  }

  num_leafs = 0;
  ++viscount; // Set current visibility number (only faces with this number are rendered in the frame)
  WalkTree(0, true);

  if (r_showleafs.ivalue && num_leafs != num_leafs_last_frame)
  {
    gConsole->Insertln("number of visible leafs: %d/%d", num_leafs, r_numleafs[0]);
    num_leafs_last_frame = num_leafs;
  }

  // Update patches levels
  if (!r_nocurves.ivalue)
  {
    float dx1, dy1, dz1, dx2, dy2, dz2, d[3], v;
    for (i = 0; i < r_numpatchesgroups[0]; ++i)
    {
      if (!r_nofrustum.ivalue && !camera->BoxInFrustum(r_patchesgroups[i].bbox)) continue;
      dx1 = camera->pos[0]-r_patchesgroups[i].bbox[0];
      dx2 = camera->pos[0]-r_patchesgroups[i].bbox[3];
      dy1 = camera->pos[1]-r_patchesgroups[i].bbox[1];
      dy2 = camera->pos[1]-r_patchesgroups[i].bbox[4];
      dz1 = camera->pos[2]-r_patchesgroups[i].bbox[2];
      dz2 = camera->pos[2]-r_patchesgroups[i].bbox[5];
      VectorSub(r_patchesgroups[i].middle, camera->pos, d);
      dx1 *= dx1; dx2 *= dx2;
      dy1 *= dy1; dy2 *= dy2;
      dz1 *= dz1; dz2 *= dz2;

      v = (min(dx1,dx2)+min(dy1,dy2)+min(dz1,dz2)+d[0]*d[0]+d[1]*d[1]+d[2]*d[2]);
      if (r_patchesgroups[i].size > 0) v /= r_patchesgroups[i].size;
      r_patchesgroups[i].Update(v, r_patches);
    }
  }
}

void Q3BSP::UpdateSky(void)
{
  if (r_fillside.ivalue > 5)
  {
    // All sky planes are rendered
    r_skybox->NewFrame(1);
  }
  else if (r_fillside.ivalue < 0)
  {
    // Sky planes are clipped and rendered if visible
    r_skybox->NewFrame(0);
    r_skybox->AutoFill(gRender->current_camera, r_novis.ivalue?-1:viscount);
  }
  else
  {
    // Only sky plane "r_fillside.ivalue" is rendered
    // Report to sky class to know about sky planes values
    r_skybox->NewFrame(0);
    r_skybox->FillSide(r_fillside.ivalue);
  }
}

// Finds leaf of the current position
int Q3BSP::FindLeaf(vec3_t p, int headnode)
{
  cnode_t   *node;
  cplane_t  *plane;
  int     idx;
  float   dot;

  idx = headnode;

  while (idx >= 0)        // if idx < 0 we have found a leaf.
  {
    node = &r_nodes[idx];
    plane = r_planes + node->planeidx;

    if (plane->type < PLANE_NON_AXIAL)
      dot = p[plane->type] - plane->dist;
    else
      dot = DotProduct(p, plane->normal) - plane->dist;

    if (dot >= 0.0f) idx = node->children[0];
    else idx = node->children[1];
  }

  return ~idx;    //return (-(idx+1));
}

// update leaf framenum according to the visibility
// TODO: write 8 leafs at once
void Q3BSP::MarkLeafs(int vis_cluster)
{
  cnode_t *node;

  if (!r_numvisibility[0] || vis_cluster == -1)
  {
    for (int i = 0; i < r_numleafs[0]; ++i)
    {
      r_leafs[i].framenum = nodecount;
      node = r_leafs[i].parent;
      while (node)
      {
        if (node->framenum == nodecount) break;

        node->framenum = nodecount;
        node = node->parent;
      }
    }
  }
  else
  {
    for (int i = 0; i < r_numleafs[0]; ++i)
    {
      if (r_leafs[i].cluster > -1 && BSP_TESTVIS(vis_cluster, r_leafs[i].cluster))
      {
        r_leafs[i].framenum = nodecount;
        node = r_leafs[i].parent;
        while (node)
        {
          if (node->framenum == nodecount) break;

          node->framenum = nodecount;
          node = node->parent;
        }
      }
    }
  }
}

/**
 * Walk trough pv nodes inside the frustum.
 * @todo We could iterate while we have only one visible node.
 */
void Q3BSP::WalkTree(int idx, bool checkFrustum)
{
  if (idx >= 0) // node
  {
    if (r_nodes[idx].framenum != nodecount) return;

    if (r_nofrustum.ivalue || checkFrustum)
    {
      switch (gRender->current_camera->BoxInFrustum(r_nodes[idx].bbox))
      {
        case COMPLETE_OUT:
          return;
        case COMPLETE_IN:
          checkFrustum = false;
          break;
        default:
          break;
      }
    }
    WalkTree(r_nodes[idx].children[0], checkFrustum); // front
    WalkTree(r_nodes[idx].children[1], checkFrustum); // back
  }
  else      // leaf
  {
    idx = ~idx;
    if (r_leafs[idx].framenum != nodecount) return;   // cluster not visible

    if (r_nofrustum.ivalue || checkFrustum)
      if (!gRender->current_camera->BoxInFrustum(r_leafs[idx].bbox)) return;

    int *p = &r_leaffaces[r_leafs[idx].firstleafface];
    int i = r_leafs[idx].numleaffaces;
    while (i--) r_surfaces[*p++].framenum = viscount;
    ++num_leafs;
  }
}

void Q3BSP::Render(void)
{
  gRender->gridpass = 0;

  if (r_drawsky.ivalue && r_skybox) DrawSky();
  if (r_drawworld.ivalue) DrawFaces();
//  if (r_drawmodels.ivalue) DrawModels();
  gRender->ForceFlush();

  if (r_grid.ivalue)
  {
    gRender->gridpass = 1;

    if (r_drawsky.ivalue && r_skybox) DrawSky();
    if (r_drawworld.ivalue) DrawFaces();
    //  if (r_drawmodels.ivalue) DrawModels();
    gRender->ForceFlush();

    gRender->gridpass = 0;

    // Rendering origin and axis
    GLboolean depthtest, texture;
    glGetBooleanv(GL_TEXTURE_2D, &texture);
    glGetBooleanv(GL_DEPTH_TEST, &depthtest);
    glDisable(GL_TEXTURE_2D);
    glDisable(GL_DEPTH_TEST);

    glBegin(GL_LINES);
      glColor3f(1.f, 0.f, 0.f);
      glVertex3f(0, 0, 0);
      glVertex3f(1000, 0, 0);
    glEnd();

    glBegin(GL_LINES);
      glColor3f(0.f, 1.f, 0.f);
      glVertex3f(0, 0, 0);
      glVertex3f(0, 1000, 0);
    glEnd();

    glBegin(GL_LINES);
      glColor3f(0.f, 0.f, 1.f);
      glVertex3f(0, 0, 0);
      glVertex3f(0, 0, 1000);
    glEnd();
    gRender->CheckGLError(19);

    if (depthtest) { glEnable(GL_DEPTH_TEST); gRender->CheckGLError(); }
    if (texture) { glEnable(GL_TEXTURE_2D); gRender->CheckGLError(); }
  }

  if (r_showbbox.ivalue) DrawBoundingBoxes();
  if (v_selectsurface.ivalue >= 0 && v_selectsurface.ivalue < r_numsurfaces[0])
  {
    colour_t colorline = { 255, 255, 255, 255 };
    colour_t colorface = {   0,   0, 255,  32};
    DrawBoundingBox(r_surfaces[v_selectsurface.ivalue].bbox, colorline, colorface);
  }
  if (v_selectpatch.ivalue >= 0 && v_selectpatch.ivalue < r_numpatches[0])
  {
    colour_t colorline = { 255, 255, 255, 255 };
    colour_t colorface = {   0, 255,   0,  32};
    DrawBoundingBox(r_patches[v_selectpatch.ivalue]->bbox, colorline, colorface);
  }
  if (v_selectmodel.ivalue >= 0 && v_selectmodel.ivalue < r_nummodels[0])
  {
    colour_t colorline = { 255, 255, 255, 255 };
    colour_t colorface = { 255,   0,   0,  32};
    DrawBoundingBox(r_models[v_selectmodel.ivalue].bbox, colorline, colorface);
  }

  if (r_normals.ivalue) DrawNormals();
}

void Q3BSP::DrawFaces(void)
{
  Surface *surf;
  Shader *shad;
  int last_shader = -1;
  int last_lightmap = -1;
  int last_effect = -2;

  for (int i = 0; i < r_numsurfaces[0]; ++i)
  {
    surf = face_list[i].face;

    if (surf->model > 0)
    {
      if (!r_drawmodels.ivalue) continue;
      if (surf->model >= r_nummodels[0]) continue;
      if (!r_models[surf->model].render) continue;
      // Tricky way that disables PVS test for models
      // TODO: link entities into tree
    }
    else if (!surf || surf->shader < 0 ||
             (!r_novis.ivalue && surf->framenum != viscount)) continue;  // PVS optimization

    shad = world->shaders.GetShader(surf->shader);

    // Sky surfaces are only renderd if specified with r_surfsky
    // variable of if it has an effect (cf. q3tourney5)
    if (shad->surface_flags & SURF_SKY && surf->effect < 0 && !r_surfsky.ivalue) continue;

    // Don't draw portals
    // TODO: Finish this - portals are not implemented yet
    if (r_noportals.ivalue && shad->flags & SF_PORTAL) continue;

    if (!r_nofrustum.ivalue)
    {
      if (surf->model > 0 && surf->model < r_nummodels[0])
      {
        if (r_models[surf->model].entity)
        {
          if (!gRender->current_camera->BoxInFrustum(r_models[surf->model].entity->bbox)) continue;
        }
        else
        {
          if (!gRender->current_camera->BoxInFrustum(r_models[surf->model].bbox)) continue;
        }
      }
      else if (surf->facetype == FACETYPE_PATCH ||
           surf->facetype == FACETYPE_MESH)
      {
        if (!gRender->current_camera->BoxInFrustum(surf->bbox)) continue;
      }
    }

    if (surf->shader != last_shader ||
        surf->lm_texnum != last_lightmap ||
        surf->effect != last_effect)
    {
      gRender->SetRenderState(shad,
                  surf->lm_texnum==~0?~0:r_lightmapinfos[surf->lm_texnum].num,
                  (surf->effect>-1&&r_numeffects[0]&&surf->facetype!=FACETYPE_FLARE)?world->shaders.GetShader(r_effects[surf->effect].shader):NULL);
      last_shader = surf->shader;
      last_lightmap = surf->lm_texnum;
      last_effect = surf->effect;
    }

    if (surf->model > 0 && r_models[surf->model].entity)
    {
      gRender->ForceFlush();
      glMatrixMode(GL_MODELVIEW);
      glPushMatrix();
      glMultMatrixf(r_models[surf->model].entity->transformation);
      gRender->CheckGLError(2);
    }

    switch (surf->facetype)
    {
      case FACETYPE_NORMAL: // Normal faces
        if (r_nofaces.ivalue) break;

    //    Following test causes problems on some faces if camera has negative z component
    //    if ((shad->cull == CULL_FRONT && DotProduct(surf->v_norm, gRender->current_camera->pos) > surf->dist) ||
    //      (shad->cull == CULL_BACK  && DotProduct(surf->v_norm, gRender->current_camera->pos) < surf->dist)) break;

        gRender->PushTriangles(surf);
        break;
      case FACETYPE_PATCH:  // BezierPatches
        if (r_nocurves.ivalue) break;
        gRender->PushTriangles(surf);
        break;
      case FACETYPE_MESH:   // Meshes
        if (r_nomesh.ivalue) break;
        gRender->PushTriangles(surf);
        break;
      case FACETYPE_FLARE:  // Flares
        break;        // not supported yet
        if (r_noflares.ivalue) break;
        gRender->PushTriangles(surf);
        break;
      default:
        break;
    }

    if (surf->model > 0 && r_models[surf->model].entity)
    {
      gRender->ForceFlush();
      glPopMatrix();
      gRender->CheckGLError();
    }
  }
}
/*
void Q3BSP::DrawModels(void)
{
  Surface *surf;
  Shader *shad;
  int last_shader = -1;
  int last_lightmap = -1;
  int last_effect = -2;
  int lod = 0;
  cmodel_t *model = NULL;

  for (int i = 1; i < r_nummodels[0]; ++i)
  {
    if (!r_models[i].numfaces) continue;

    lod = 0;
    model = &r_models[i];

    if (model->entity)
    {
      gRender->ForceFlush();
      glMatrixMode(GL_MODELVIEW);
      glPushMatrix();
      glMultMatrixf(model->entity->transformation);
      gRender->checkGLError(3);

      // Get the lod for rendering

      if (model->entity->num_lods)
      {
        vec_t m[16];
        glGetFloatv(GL_MODELVIEW_MATRIX, m);
        vec3_t dist;
        VectorCopy(&m[12], dist);
        // quick'n dirty lod based on distance
        // looks quite good though
        lod = (int) fabsf(dist[2]/200.f);
        if (lod > model->entity->num_lods-1) lod = model->entity->num_lods-1;
      }

      model = model->entity->models[lod];
    }

    if (!model) continue;

    for (int j = 0; j < model->numfaces; ++j)
    {
      surf = &r_surfaces[model->firstface+j];

      if (!(shad = world->shaders.GetShader(surf->shader))) continue;

      // Sky surfaces are only renderd if specified with r_surfsky
      // variable of if it has an effect (cf. q3tourney5)
      if (shad->surface_flags & SURF_SKY && surf->effect < 0 && !r_surfsky.ivalue) continue;

      // Don't draw portals
      // TODO: Finish this - portals are not implemented yet
      if (r_noportals.ivalue && shad->flags & SF_PORTAL) continue;

      if (surf->shader != last_shader ||
        surf->lm_texnum != last_lightmap ||
        surf->effect != last_effect)
      {
        gRender->SetRenderState(shad,
                    surf->lm_texnum==~0?~0:r_lightmapinfos[surf->lm_texnum].num,
                    (surf->effect>-1&&r_numeffects[0]&&surf->facetype!=FACETYPE_FLARE)?world->shaders.GetShader(r_effects[surf->effect].shader):NULL);
        last_shader = surf->shader;
        last_lightmap = surf->lm_texnum;
        last_effect = surf->effect;
      }

      switch (surf->facetype)
      {
        case FACETYPE_NORMAL: // Normal faces
          if (r_nofaces.ivalue) continue;

      //    Following test causes problems on some faces if camera has negative z component
      //    if ((shad->cull == CULL_FRONT && DotProduct(surf->v_norm, gRender->current_camera->pos) > surf->dist) ||
      //      (shad->cull == CULL_BACK  && DotProduct(surf->v_norm, gRender->current_camera->pos) < surf->dist)) continue;

          gRender->PushTriangles(surf);
          break;
        case FACETYPE_PATCH:  // BezierPatches
          if (r_nocurves.ivalue) continue;
          gRender->PushTriangles(surf);
          break;
        case FACETYPE_MESH:   // Meshes
          if (r_nomesh.ivalue) continue;
          gRender->PushTriangles(surf);
          break;
        case FACETYPE_FLARE:  // Flares
          break;        // not supported yet
          if (r_noflares.ivalue) continue;
          gRender->PushTriangles(surf);
          break;
        default:
          break;
      }
    }
    if (model->entity)
    {
      gRender->ForceFlush();
      glPopMatrix();
      gRender->checkGLError();
    }
  }
}
*/
void Q3BSP::DrawSky(void)
{
  Shader *shad = NULL;

  if (r_skybox->clouds_shader >= 0)
    shad = world->shaders.GetShader(r_skybox->clouds_shader);

  if (!shad) return;

  // Don't need to test depth value, sky is rendered as background
  glDisable(GL_DEPTH_TEST);

  // Center skybox on camera to give the illusion of a larger space
  glMatrixMode(GL_MODELVIEW);
  glPushMatrix();
  glTranslatef(gRender->current_camera->pos[0],
               gRender->current_camera->pos[1],
               gRender->current_camera->pos[2]);
  glScalef(r_skybox->skyboxsize, r_skybox->skyboxsize, r_skybox->skyboxsize);
  gRender->CheckGLError(5);

  // Farbox and NearBox
  if (shad->sky_params.num_layers)
  {
    if (r_skybox->usedskysides[0]) { gRender->SetRenderState(r_skybox->box_shader[0]); r_skybox->skyface[0].currentlevel = 1; gRender->PushTriangles(&r_skybox->skyface[0]); }
    if (r_skybox->usedskysides[1]) { gRender->SetRenderState(r_skybox->box_shader[1]); r_skybox->skyface[1].currentlevel = 1; gRender->PushTriangles(&r_skybox->skyface[1]); }
    if (r_skybox->usedskysides[2]) { gRender->SetRenderState(r_skybox->box_shader[2]); r_skybox->skyface[2].currentlevel = 1; gRender->PushTriangles(&r_skybox->skyface[2]); }
    if (r_skybox->usedskysides[3]) { gRender->SetRenderState(r_skybox->box_shader[3]); r_skybox->skyface[3].currentlevel = 1; gRender->PushTriangles(&r_skybox->skyface[3]); }
    if (r_skybox->usedskysides[4]) { gRender->SetRenderState(r_skybox->box_shader[4]); r_skybox->skyface[4].currentlevel = 1; gRender->PushTriangles(&r_skybox->skyface[4]); }
    if (r_skybox->usedskysides[5]) { gRender->SetRenderState(r_skybox->box_shader[5]); r_skybox->skyface[5].currentlevel = 1; gRender->PushTriangles(&r_skybox->skyface[5]); }
  }

  // Clouds
  if (shad->num_layers)
  {
    gRender->SetRenderState(shad);
    if (r_skybox->usedskysides[0]) { r_skybox->skyface[0].currentlevel = 0; gRender->PushTriangles(&r_skybox->skyface[0], r_skybox->framenum[0]); }
    if (r_skybox->usedskysides[1]) { r_skybox->skyface[1].currentlevel = 0; gRender->PushTriangles(&r_skybox->skyface[1], r_skybox->framenum[1]); }
    if (r_skybox->usedskysides[2]) { r_skybox->skyface[2].currentlevel = 0; gRender->PushTriangles(&r_skybox->skyface[2], r_skybox->framenum[2]); }
    if (r_skybox->usedskysides[3]) { r_skybox->skyface[3].currentlevel = 0; gRender->PushTriangles(&r_skybox->skyface[3], r_skybox->framenum[3]); }
    if (r_skybox->usedskysides[4]) { r_skybox->skyface[4].currentlevel = 0; gRender->PushTriangles(&r_skybox->skyface[4], r_skybox->framenum[4]); }
    if (r_skybox->usedskysides[5]) { r_skybox->skyface[5].currentlevel = 0; gRender->PushTriangles(&r_skybox->skyface[5], r_skybox->framenum[5]); }
  }

  // Flushing sky
  gRender->ForceFlush();

  // Restore world space
  glMatrixMode(GL_MODELVIEW);
  glPopMatrix();

  // Re-enable depth test for other faces
  glEnable(GL_DEPTH_TEST);

  // clearing depth buffer
  // Note: I would prefer using the glDepthMask() function but depth masking state
  //       is sometimes modified by shaders so and is not always constant.
  State::setDepthWrite(GL_TRUE);        // must be true before clearing!
  glClear(GL_DEPTH_BUFFER_BIT);
  gRender->CheckGLError(4);
}

void Q3BSP::DrawBoundingBoxes(void)
{
  int i;
  Surface *surf;

  colour_t colorline, colorface;

  for (i = 0; i < r_numsurfaces[0]; ++i)
  {
    surf = face_list[i].face;

    if (surf->facetype == FACETYPE_PATCH)
    {
      ColorSet(colorline, 255, 255, 255, 255);
      ColorSet(colorface, 0, 255, 255, 8);
    }
    else if (surf->facetype == FACETYPE_MESH)
    {
      ColorSet(colorline, 255, 255, 255, 255);
      ColorSet(colorface, 255, 255, 0, 8);
    }
    else if (surf->facetype == FACETYPE_NORMAL)
    {
      ColorSet(colorline, 255, 255, 255, 255);
      ColorSet(colorface, 255, 0, 255, 8);
    }
    else
    {
      ColorSet(colorline, 255, 255, 255, 255);
      ColorSet(colorface, 255, 0, 0, 8);
    }

    if (surf->model > 0 && surf->model < r_nummodels[0])
    {
      // TODO Update model
      if (!r_drawmodels.ivalue) continue;
      if (r_nofrustum.ivalue && gRender->current_camera->BoxInFrustum(surf->bbox))
        DrawBoundingBox(surf->bbox, colorline, colorface);
      else if (r_models[surf->model].entity && gRender->current_camera->BoxInFrustum(r_models[surf->model].entity->bbox))
        DrawBoundingBox(r_models[surf->model].entity->bbox, colorline, colorface);
    }
    else if (!surf || surf->shader < 0 ||
      (!r_novis.ivalue && surf->framenum != viscount)) continue;  // PVS optimisation

    switch (surf->facetype)
    {
      case FACETYPE_PATCH:
      case FACETYPE_MESH:
        if (r_nofrustum.ivalue || gRender->current_camera->BoxInFrustum(surf->bbox))
          DrawBoundingBox(surf->bbox, colorline, colorface);
        break;
      default:
        break;
    }
  }

  // Patches groups (for debug)
  ColorSet(colorline, 255, 255, 255, 255);
  ColorSet(colorface, 0, 255, 0, 8);
  for (i = 0; i < r_numpatchesgroups[0]; ++i)
    DrawBoundingBox(r_patchesgroups[i].bbox, colorline, colorface);
}

void Q3BSP::DrawBoundingBox(bboxf_t bbox, colour_t colorline, colour_t colorface)
{
  vec3_t v[8] = {
    { bbox[0], bbox[1], bbox[2] },
    { bbox[3], bbox[1], bbox[2] },
    { bbox[3], bbox[1], bbox[5] },
    { bbox[0], bbox[1], bbox[5] },
    { bbox[0], bbox[4], bbox[2] },
    { bbox[3], bbox[4], bbox[2] },
    { bbox[3], bbox[4], bbox[5] },
    { bbox[0], bbox[4], bbox[5] }
  };

  State::setAlphaFunc(GL_ALWAYS, 0);
  State::setCulling(CULL_NONE);   // disable culling

  GLboolean texture, depthtest;
  glGetBooleanv(GL_TEXTURE_2D, &texture);
  glGetBooleanv(GL_DEPTH_TEST, &depthtest);
  glDisable(GL_TEXTURE_2D);
  glDisable(GL_DEPTH_TEST);
  gRender->CheckGLError(4);

  State::setBlend(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);
  glColor4ubv(colorface);
  glBegin(GL_QUADS);
    glVertex3fv(v[0]);
    glVertex3fv(v[1]);
    glVertex3fv(v[2]);
    glVertex3fv(v[3]);

    glVertex3fv(v[4]);
    glVertex3fv(v[5]);
    glVertex3fv(v[6]);
    glVertex3fv(v[7]);

    glVertex3fv(v[0]);
    glVertex3fv(v[1]);
    glVertex3fv(v[5]);
    glVertex3fv(v[4]);

    glVertex3fv(v[1]);
    glVertex3fv(v[5]);
    glVertex3fv(v[6]);
    glVertex3fv(v[2]);

    glVertex3fv(v[2]);
    glVertex3fv(v[6]);
    glVertex3fv(v[7]);
    glVertex3fv(v[3]);

    glVertex3fv(v[3]);
    glVertex3fv(v[7]);
    glVertex3fv(v[4]);
    glVertex3fv(v[0]);
  glEnd();
  State::setBlend(GL_ONE, GL_ZERO);

  glColor4ubv(colorline);
  gRender->CheckGLError();

  glBegin(GL_LINE_LOOP);
    glVertex3fv(v[0]);
    glVertex3fv(v[1]);
    glVertex3fv(v[2]);
    glVertex3fv(v[3]);
  glEnd();

  glBegin(GL_LINE_LOOP);
    glVertex3fv(v[4]);
    glVertex3fv(v[5]);
    glVertex3fv(v[6]);
    glVertex3fv(v[7]);
  glEnd();

  glBegin(GL_LINES);
    glVertex3fv(v[0]);
    glVertex3fv(v[4]);
    glVertex3fv(v[1]);
    glVertex3fv(v[5]);
    glVertex3fv(v[2]);
    glVertex3fv(v[6]);
    glVertex3fv(v[3]);
    glVertex3fv(v[7]);
  glEnd();

  gRender->CheckGLError(53);

  if (texture) { glEnable(GL_TEXTURE_2D); gRender->CheckGLError(); }
  if (depthtest) { glEnable(GL_DEPTH_TEST); gRender->CheckGLError(); }
}

void Q3BSP::DrawNormals(void)
{
  vec3_t vnorm;

  GLboolean texture, depthtest;
  glGetBooleanv(GL_TEXTURE_2D, &texture);
  glGetBooleanv(GL_DEPTH_TEST, &depthtest);
  glDisable(GL_TEXTURE_2D);
  glDisable(GL_DEPTH_TEST);
  gRender->CheckGLError(4);

  glColor3f(1.f, 1.f, 1.f);

  glBegin(GL_LINES);
  for (int i = 0; i < r_numverts[0]; ++i)
  {
    VectorMA(r_verts[i].v_point, fabsf(r_normals.fvalue), r_verts[i].v_norm, vnorm);
    glVertex3fv(r_verts[i].v_point);
    glVertex3fv(vnorm);
  }
  glEnd();
  gRender->CheckGLError(r_numverts[0]+3);

  if (texture) { glEnable(GL_TEXTURE_2D); gRender->CheckGLError(); }
  if (depthtest) { glEnable(GL_DEPTH_TEST); gRender->CheckGLError(); }
}

// ClearLink is used for new headnodes
void Q3BSP::ClearLink(link_t *l)
{
  l->prev = l->next = l;
}

void Q3BSP::RemoveLink(link_t *l)
{
  l->next->prev = l->prev;
  l->prev->next = l->next;
}

void Q3BSP::InsertLinkBefore(link_t *l, link_t *before)
{
  l->next = before;
  l->prev = before->prev;
  l->prev->next = l;
  l->next->prev = l;
}

void Q3BSP::LinkEntity(Entity* ent)
{
  // Put the entity in the BSP tree
}

void Q3BSP::UnlinkEntity(Entity *ent)
{
  // Remove the entity from the BSP tree
}

cmodel_t* Q3BSP::CreateNewModel(int *modelnum)
{
  // No more free memory for models
  if (r_nummodels[0] == r_nummodels[1])
  {
    // TODO: Implement reallocation
    gConsole->Insertln("^1ERROR: Models buffer is too small for additional model.");
    return NULL;
  }

  *modelnum = r_nummodels[0];
  return &r_models[r_nummodels[0]++];
}

Surface* Q3BSP::CreateNewSurface(int facetype, int *facenum)
{
  // No more free memory for surfaces
  if (r_numsurfaces[0] == r_numsurfaces[1])
  {
    // TODO: Implement reallocation
    gConsole->Insertln("^1ERROR: Faces buffer is too small for additional faces.");
    return NULL;
  }

  switch (facetype)
  {
    case FACETYPE_NORMAL:
      r_surfaces[r_numsurfaces[0]].indextype = r_numfaces[1]++;
      break;
    case FACETYPE_PATCH:
      r_surfaces[r_numsurfaces[0]].indextype = r_numpatches[1]++;
      break;
    case FACETYPE_MESH:
      r_surfaces[r_numsurfaces[0]].indextype = r_nummeshes[1]++;
      break;
    case FACETYPE_FLARE:
      r_surfaces[r_numsurfaces[0]].indextype = r_numflares[1]++;
      break;
    default:
      gConsole->Insert("^1Invalid facetype!");
      return NULL;
  }

  r_surfaces[r_numsurfaces[0]].facetype = facetype;
  face_list[r_numsurfaces[0]].face = &r_surfaces[r_numsurfaces[0]];

  *facenum = r_numsurfaces[0];
  return &r_surfaces[r_numsurfaces[0]++];
}

//-----------------------------------------------------------------------------
// Data Loading Routines
//-----------------------------------------------------------------------------

// Load Entities
void Q3BSP::LoadEntities(void)
{
  char *      ent;      // Total entities lump
  int entitieslen = ReadLump(ENTITIES, (void**)&ent, 1);

  r_entities = new EntityManager;
  if (!r_entities)
  {
    gConsole->Insertln("^1ERROR: Cannot allocate memory for entity manager.");
    return;
  }

  if (!r_entities->Load(ent, entitieslen))
  {
    gConsole->Insertln("^1ERROR: entity loading aborted.");
    return;
  }

  cake_free(ent);
}

// Load Shaders
void Q3BSP::LoadShaders(void)
{
  r_numshaders[0] = r_numshaders[1] = ReadLump(SHADERREFS, (void**)&r_shaderrefs, sizeof(shaderref_t));
}

// Build clip planes
void Q3BSP::LoadPlanes(void)
{
  plane_t   *planes;

  r_numplanes[0] = r_numplanes[1] = ReadLump(_PLANES, (void**)&planes, sizeof(plane_t));

  r_numplanes[1] += (MAX_CM_PLANES+12); // increase buffer because if will filled later
  r_planes = (cplane_t*) cake_malloc(r_numplanes[1]*sizeof(cplane_t), "Q3BSP::LoadPlanes.r_planes");

  for (int i = 0; i < r_numplanes[0]; ++i)
  {
    r_planes[i].normal[0] = planes[i].normal[0];
    r_planes[i].normal[1] = planes[i].normal[1];
    r_planes[i].normal[2] = planes[i].normal[2];
    r_planes[i].dist = planes[i].dist;

    CategorizePlane(&r_planes[i]);
  }

  cake_free(planes); planes = NULL;
}

// Load the nodes
void Q3BSP::LoadNodes(void)
{
  node_t *nodes;

  r_numnodes[0] = r_numnodes[1] = ReadLump(NODES, (void**)&nodes, sizeof(node_t));

  r_numnodes[1] += (MAX_CM_NODES+6); // increase buffer because if will filled later
  r_nodes = (cnode_t*) cake_malloc(r_numnodes[1]*sizeof(cnode_t), "Q3BSP::LoadNodes.r_nodes");

  for (int i = 0; i < r_numnodes[0]; ++i)
  {
    r_nodes[i].planeidx = nodes[i].plane;
    r_nodes[i].children[0] = nodes[i].children[0];
    r_nodes[i].children[1] = nodes[i].children[1];
    BoxCopy(nodes[i].bbox, r_nodes[i].bbox);  // Copy the node bounding box
  }

  cake_free(nodes); nodes = NULL;
}

// this are the indices of the leafs to the faces and the brushes:
// @todo this way it is very easy to load the map, but there is a lot of indirection
//       we could avoid that by using non-fixed sized leaf structures but that hurts me.
void Q3BSP::LoadLFaces(void)
{
  r_numleaffaces[0] = r_numleaffaces[1] = ReadLump(LFACES, (void**)&r_leaffaces, sizeof(int));
}

void Q3BSP::LoadLBrushes(void)
{
  int *leafbrushes;
  r_numleafbrushes[0] = r_numleafbrushes[1] = ReadLump(LBRUSHES, (void**)&leafbrushes, sizeof(int));

  r_numleafbrushes[1] += (MAX_CM_BRUSHES+1);
  r_leafbrushes = (int*) cake_malloc(r_numleafbrushes[1]*sizeof(int), "Q3BSP::LoadLBrushes.r_leafbrushes");

  memcpy(r_leafbrushes, leafbrushes, r_numleafbrushes[0]*sizeof(int));

  cake_free(leafbrushes);
}

// Load the leafs
void Q3BSP::LoadLeafs(void)
{
  leaf_t *leafs;
  cbrush_t *brush;

  r_numleafs[0] = r_numleafs[1] = ReadLump(LEAFS, (void**)&leafs, sizeof(leaf_t));

  r_numleafs[1] += (MAX_CM_LEAFS+1);
  r_leafs = (cleaf_t*) cake_malloc(r_numleafs[1]*sizeof(cleaf_t), "Q3BSP::LoadLeafs.r_leafs");

  emptyleaf = -1;

  for (int i = 0; i < r_numleafs[0]; ++i)
  {
    r_leafs[i].parent = NULL;
    r_leafs[i].cluster = leafs[i].cluster;
    r_leafs[i].area = leafs[i].area;
    BoxCopy(leafs[i].bbox, r_leafs[i].bbox);
    r_leafs[i].firstleafface = leafs[i].firstface;
    r_leafs[i].numleaffaces = leafs[i].numfaces;
    r_leafs[i].firstleafbrush = leafs[i].firstbrush;
    r_leafs[i].numleafbrushes = leafs[i].numbrushes;
    r_leafs[i].firstleafpatch = 0;
    r_leafs[i].numleafpatches = 0;
    r_leafs[i].contents = 0;

    // Update leaf content through brushes references
    for (int j = 0; j < r_leafs[i].numleafbrushes; ++j)
    {
      brush = &r_brushes[r_leafbrushes[r_leafs[i].firstleafbrush+j]];
      r_leafs[i].contents |= brush->contents;
    }

    if (!r_leafs[i].contents) emptyleaf = i;
  }

  // if map doesn't have an empty leaf - force one
  if (emptyleaf == -1)
  {
    if (r_numleafs[0] >= r_numleafs[1]) ThrowException(OVERFLOW_ERROR, "Q3BSP::LoadLeafs");

    r_leafs[r_numleafs[0]].cluster = -1;
    r_leafs[r_numleafs[0]].area = -1;
    r_leafs[r_numleafs[0]].numleafbrushes = 0;
    r_leafs[r_numleafs[0]].contents = 0;
    r_leafs[r_numleafs[0]].firstleafbrush = 0;

    gConsole->Insertln("Forging an empty leaf: %i", r_numleafs[0]);
    emptyleaf = r_numleafs[0]++;
  }

  cake_free(leafs); leafs = NULL;

  SetParent(0, NULL);
}

void Q3BSP::LoadModels(void)
{
  int i, j, m;
  model_t *models;

  r_nummodels[0] = r_nummodels[1] = ReadLump(MODELS, (void**)&models, sizeof(model_t));

  r_nummodels[1] += MAX_CM_MODELS;
  r_models = (cmodel_t*) cake_malloc(r_nummodels[1]*sizeof(cmodel_t), "Q3BSP::LoadModels.r_models");
  if (!r_models) ThrowException(ALLOCATION_ERROR, "Q3BSP::LoadModels.r_models");

  for (i = 0; i < r_nummodels[0]; ++i)
  {
#if 1
    BoxCopy(models[i].bbox, r_models[i].bbox);
#else
    // spread the mins / maxs by a pixel
    r_models[i].bbox[0] = models[i].bbox[0] - 1;
    r_models[i].bbox[3] = models[i].bbox[3] + 1;
    r_models[i].bbox[1] = models[i].bbox[1] - 1;
    r_models[i].bbox[4] = models[i].bbox[4] + 1;
    r_models[i].bbox[2] = models[i].bbox[2] - 1;
    r_models[i].bbox[5] = models[i].bbox[5] + 1;
#endif
    r_models[i].firstbrush  = models[i].firstbrush;
    r_models[i].firstface = models[i].firstface;
    r_models[i].numbrushes  = models[i].numbrushes;
    r_models[i].numfaces  = models[i].numfaces;

    r_models[i].entity    = NULL;
    r_models[i].render    = true;

    // Associate faces with model
    Surface *surf = r_surfaces + r_models[i].firstface;
    j = r_models[i].numfaces;
    while (j--)
    {
      surf->model = i;
      ++surf;
    }
/*
    if (i == 0)
    {
      r_models[i].headnode = 0;
    }
    else
    {
      r_models[i].headnode = -1 - r_numleafs[0];

      while (r_numleafs[0] >= r_numleafs[1])
      {
        // force reallocation
        r_numleafs[1] += MAX_CM_LEAFS;
        if (!(r_leafs = (cleaf_t*) cake_realloc(r_leafs, r_numleafs[1]*sizeof(cleaf_t), "Q3BSP::LoadModels.r_leafs")))
        {
          gConsole->Insertln("^1Q3BSP::LoadModels.r_leafs: Cannot allocate required size");
          continue;
        }
      }

      cleaf_t *bleaf = &r_leafs[r_numleafs[0]++];
      bleaf->numleafbrushes = r_models[i].numbrushes;
      bleaf->firstleafbrush = r_numleafbrushes[0];
      bleaf->contents = 0;
      bleaf->parent = NULL;

      int *leafbrush = &r_leafbrushes[r_numleafbrushes[0]];
      for (j = 0; j < bleaf->numleafbrushes; j++, leafbrush++)
      {
        *leafbrush = r_models[i].firstbrush + j;
        bleaf->contents |= r_brushes[*leafbrush].contents;
      }

      r_numleafbrushes[0] += bleaf->numleafbrushes;
    }
*/
  }

  cake_free(models);
  models = NULL;

  // Perform entities processing
  if (!r_entities->ProcessEntities(this))
  {
    gConsole->Insertln("^1ERROR: entity processing aborted.");
    return;
  }

  // Associate entities with model
  for (i = 0; i < r_entities->num_entities; ++i)
  {
    m = r_entities->entities[i].model;
    if (m > 0 && m < r_nummodels[0])
    {
      r_entities->entities[i].SetModel(&r_models[m]);
    }

    // Associate children
    for (j = 0; j < r_entities->entities[i].numchildren; ++j)
    {
      m = r_entities->entities[i].children[j]->model;
      if (m > 0 && m < r_nummodels[0])
      {
        r_entities->entities[i].children[j]->SetModel(&r_models[m]);
      }
    }
  }
}

void Q3BSP::LoadBrushes(void)
{
  brush_t *brushes;
  r_numbrushes[0] = r_numbrushes[1] = ReadLump(BRUSHES, (void**)&brushes, sizeof(brush_t));

  r_numbrushes[1] += (MAX_CM_BRUSHES+1); // increase buffer because if will filled later
  r_brushes = (cbrush_t*) cake_malloc(r_numbrushes[1]*sizeof(cbrush_t), "Q3BSP::LoadBrushes.r_brushes");

  for (int i = 0; i < r_numbrushes[0]; ++i)
  {
    r_brushes[i].shader = world->shaders.AddShader(r_shaderrefs[brushes[i].shader].name,
                                                   r_shaderrefs[brushes[i].shader].surface_flags,
                                                   r_shaderrefs[brushes[i].shader].content_flags);
    r_brushes[i].effect = -1;
    r_brushes[i].firstbrushside = brushes[i].firstside;
    r_brushes[i].numsides = brushes[i].numsides;
    r_brushes[i].checkcount = 0;
    if (brushes[i].shader >= 0 && brushes[i].shader < r_numshaders[0])
      r_brushes[i].contents = r_shaderrefs[brushes[i].shader].content_flags;
    else
      r_brushes[i].contents = 0;
  }

  cake_free(brushes); brushes = NULL;
}

void Q3BSP::LoadBrushSides(void)
{
  brushside_t* brushsides;
  r_numbrushsides[0] = r_numbrushsides[1] = ReadLump(BRUSH_SIDES, (void**)&brushsides, sizeof(brushside_t));

  r_numbrushsides[1] += (MAX_CM_BRUSHSIDES+6); // increase buffer because if will filled later
  r_brushsides = (cbrushside_t*) cake_malloc(r_numbrushsides[1]*sizeof(cbrushside_t), "Q3BSP::LoadBrushSides.r_brushsides");

  for (int i = 0; i < r_numbrushsides[0]; ++i)
  {
    r_brushsides[i].planeidx = brushsides[i].planeidx;
    r_brushsides[i].shader = world->shaders.AddShader(r_shaderrefs[brushsides[i].shader].name,
                                                      r_shaderrefs[brushsides[i].shader].surface_flags,
                                                      r_shaderrefs[brushsides[i].shader].content_flags);
  }

  cake_free(brushsides);
}

void Q3BSP::LoadVerts(void)
{
  vertex_t *verts;
  r_numverts[0] = r_numverts[1] = ReadLump(VERTS, (void**)&verts, sizeof(vertex_t));
  r_numverts[1] += MAX_CM_VERTEXES;
  r_verts = (vertex_t*) cake_malloc(r_numverts[1]*sizeof(vertex_t), "Q3BSP::LoadVerts.r_verts");

  for (int i = 0; i < r_numverts[0]; ++i)
  {
    ColorCopy(verts[i].colour, r_verts[i].colour);
    TexcoordCopy(verts[i].lm_st, r_verts[i].lm_st);
    TexcoordCopy(verts[i].tex_st, r_verts[i].tex_st);
    VectorCopy(verts[i].v_norm, r_verts[i].v_norm);
    VectorCopy(verts[i].v_point, r_verts[i].v_point);
  }

  cake_free(verts);
}

void Q3BSP::LoadElems(void)
{
  int *elems;
  r_numelems[0] = r_numelems[1] = ReadLump(ELEMS, (void**)&elems, sizeof(int));
  r_numelems[1] += MAX_CM_VERTEXES;
  r_elems = (int*) cake_malloc(r_numelems[1]*sizeof(int), "Q3BSP::LoadElems.r_elems");

  for (int i = 0; i < r_numelems[0]; ++i)
    r_elems[i] = elems[i];

  cake_free(elems);
}

void Q3BSP::LoadEffects(void)
{
  effect_t *effects;
  r_numeffects[0] = r_numeffects[1] = ReadLump(EFFECTS, (void**)&effects, sizeof(effect_t));

  r_effects = (ceffect_t*) cake_malloc(r_numeffects[1]*sizeof(ceffect_t), "Q3BSP::LoadEffects.r_effects");

  // Associate effects with brushes
  for (int i = 0; i < r_numeffects[0]; ++i)
  {
    r_effects[i].shader = world->shaders.AddShader(effects[i].name, 0, 0, FACETYPE_MESH);
    r_effects[i].brush = effects[i].brush;
    r_effects[i].visibleside = effects[i].visibleside;
    if (effects[i].visibleside >= 0)
      r_effects[i].planeidx = r_brushsides[r_brushes[effects[i].brush].firstbrushside+effects[i].visibleside].planeidx;
    else
      r_effects[i].planeidx = -1;
    r_brushes[r_effects[i].brush].effect = i;
  }

  cake_free(effects); effects = NULL;
}

void Q3BSP::LoadFaces(void)
{
  face_t *faces;
  int i;

  r_numsurfaces[0] = r_numsurfaces[1] = ReadLump(FACES, (void**)&faces, sizeof(face_t));
  r_numsurfaces[1] += MAX_MAP_FACES;

  r_numfaces[0] = r_numfaces[1] = 0;
  r_numpatches[0] = r_numpatches[1] = 0;
  r_nummeshes[0] = r_nummeshes[1] = 0;
  r_numflares[0] = r_numflares[1] = 0;

  int subdivs = gVars->IntForKey("r_subdivision");
  if (subdivs < 1) subdivs = 1;
  else if (subdivs > MAX_SUBDIV) subdivs = MAX_SUBDIV;
  gVars->SetKeyValue("r_subdivision", subdivs);

  r_surfaces = new Surface[r_numsurfaces[1]];
  if (!r_surfaces) ThrowException(ALLOCATION_ERROR, "Q3BSP::LoadFaces.r_surfaces");

  face_list = new render_face_s[r_numsurfaces[1]];
  if (!face_list) ThrowException(ALLOCATION_ERROR, "Q3BSP::LoadFaces.face_list");

  for (i = 0; i < r_numsurfaces[0]; ++i)
  {
    switch (faces[i].facetype)
    {
      case FACETYPE_PLANAR:
      {
        r_surfaces[i].Init();
        r_surfaces[i].shader        = world->shaders.AddShader(r_shaderrefs[faces[i].shader].name,
                                      r_shaderrefs[faces[i].shader].surface_flags,
                                      r_shaderrefs[faces[i].shader].content_flags,
                                      faces[i].facetype);
        r_surfaces[i].facetype      = faces[i].facetype;
        r_surfaces[i].firstvert[0]  = r_verts + faces[i].firstvert;
        r_surfaces[i].numverts[0]   = faces[i].numverts;
        r_surfaces[i].firstelem[0]  = r_elems + faces[i].firstelem;
        r_surfaces[i].numelems[0]   = faces[i].numelems;
        r_surfaces[i].lm_texnum     = faces[i].lm_texnum;
        r_surfaces[i].effect        = faces[i].effect;
        r_surfaces[i].dist          = (int) DotProduct(faces[i].v_orig, faces[i].v_norm);
        Vector2Copy(faces[i].mesh_cp, r_surfaces[i].patch_cp);
        VectorCopy(faces[i].v_norm, r_surfaces[i].v_norm);
        VectorCopy(faces[i].v_orig, r_surfaces[i].v_orig);
        BoxCopy(faces[i].bbox, r_surfaces[i].bbox);
        r_surfaces[i].indextype     = r_numfaces[1]++;
        face_list[i].face           = &r_surfaces[i];
        break;
      }
      case FACETYPE_PATCH:
      {
        r_surfaces[i].Init(subdivs+1);  // create the levels
        r_surfaces[i].shader        = world->shaders.AddShader(r_shaderrefs[faces[i].shader].name,
                                      r_shaderrefs[faces[i].shader].surface_flags,
                                      r_shaderrefs[faces[i].shader].content_flags,
                                      faces[i].facetype);
        r_surfaces[i].facetype      = faces[i].facetype;
        r_surfaces[i].firstvert[0]  = r_verts + faces[i].firstvert;
        r_surfaces[i].numverts[0]   = faces[i].numverts;
        r_surfaces[i].firstelem[0]  = r_elems + faces[i].firstelem;
        r_surfaces[i].numelems[0]   = faces[i].numelems;
        r_surfaces[i].lm_texnum     = faces[i].lm_texnum;
        r_surfaces[i].effect        = faces[i].effect;
        r_surfaces[i].dist          = (int) DotProduct(faces[i].v_orig, faces[i].v_norm);
        Vector2Copy(faces[i].mesh_cp, r_surfaces[i].patch_cp);
        VectorCopy(faces[i].v_norm, r_surfaces[i].v_norm);
        VectorCopy(faces[i].v_orig, r_surfaces[i].v_orig);
        BoxCopy(faces[i].bbox, r_surfaces[i].bbox);
        r_surfaces[i].indextype     = r_numpatches[1]++;
        face_list[i].face           = &r_surfaces[i];
        break;
      }
      case FACETYPE_MESH:
      {
        r_surfaces[i].Init();
        r_surfaces[i].shader        = world->shaders.AddShader(r_shaderrefs[faces[i].shader].name,
                                      r_shaderrefs[faces[i].shader].surface_flags,
                                      r_shaderrefs[faces[i].shader].content_flags,
                                      faces[i].facetype);
        r_surfaces[i].facetype      = faces[i].facetype;
        r_surfaces[i].firstvert[0]  = r_verts + faces[i].firstvert;
        r_surfaces[i].numverts[0]   = faces[i].numverts;
        r_surfaces[i].firstelem[0]  = r_elems + faces[i].firstelem;
        r_surfaces[i].numelems[0]   = faces[i].numelems;
        r_surfaces[i].lm_texnum     = faces[i].lm_texnum;
        r_surfaces[i].effect        = faces[i].effect;
        Vector2Copy(faces[i].mesh_cp, r_surfaces[i].patch_cp);
        VectorCopy(faces[i].v_norm, r_surfaces[i].v_norm);
        VectorCopy(faces[i].v_orig, r_surfaces[i].v_orig);
        BoxCopy(faces[i].bbox, r_surfaces[i].bbox);
        r_surfaces[i].indextype     = r_nummeshes[1]++;
        face_list[i].face           = &r_surfaces[i];
        break;
      }
      case FACETYPE_FLARE:
      {
        r_surfaces[i].Init();
        r_surfaces[i].shader        = world->shaders.AddShader(r_shaderrefs[faces[i].shader].name,
                                      r_shaderrefs[faces[i].shader].surface_flags,
                                      r_shaderrefs[faces[i].shader].content_flags,
                                      faces[i].facetype);
        r_surfaces[i].facetype      = faces[i].facetype;
        r_surfaces[i].firstvert[0]  = r_verts + faces[i].firstvert;
        r_surfaces[i].numverts[0]   = faces[i].numverts;
        r_surfaces[i].firstelem[0]  = r_elems + faces[i].firstelem;
        r_surfaces[i].numelems[0]   = faces[i].numelems;
        r_surfaces[i].lm_texnum     = faces[i].lm_texnum;
        r_surfaces[i].effect        = faces[i].effect;
        Vector2Copy(faces[i].mesh_cp, r_surfaces[i].patch_cp);
        VectorCopy(faces[i].v_norm, r_surfaces[i].v_norm);
        VectorCopy(faces[i].v_orig, r_surfaces[i].v_orig);
        BoxCopy(faces[i].bbox, r_surfaces[i].bbox);
        r_surfaces[i].indextype     = r_numflares[1]++;
        face_list[i].face           = &r_surfaces[i];
        break;
      }
      default:
        face_list[i].face           = NULL;
        break;
    }
  }

  cake_free(faces);

  // Reset other faces
  for (i = r_numsurfaces[0]; i < r_numsurfaces[1]; ++i) face_list[i].face = NULL;
}

void Q3BSP::InitSurfaces(void)
{
  gConsole->Insertln("Initializing faces...");

  int i;

  if (!(r_faces = new Surface*[r_numfaces[1]]))
    ThrowException(ALLOCATION_ERROR, "Q3BSP::InitSurfaces.r_faces");
  if (!(r_patches = new Surface*[r_numpatches[1]]))
    ThrowException(ALLOCATION_ERROR, "Q3BSP::InitSurfaces.r_patches");
  if (!(r_meshes = new Surface*[r_nummeshes[1]]))
    ThrowException(ALLOCATION_ERROR, "Q3BSP::InitSurfaces.r_meshes");
  if (!(r_flares = new Surface*[r_numflares[1]]))
    ThrowException(ALLOCATION_ERROR, "Q3BSP::InitSurfaces.r_flares");

  int cfactor = gVars->IntForKey("r_curvefactor");
  if (cfactor < 1) cfactor = 1;
  gVars->SetKeyValue("r_curvefactor", cfactor);

  for (i = 0; i < r_numsurfaces[0]; ++i)
  {
    switch (r_surfaces[i].facetype)
    {
      case FACETYPE_PLANAR:
        r_faces[r_numfaces[0]++] = &r_surfaces[i];
        break;
      case FACETYPE_PATCH:
        {
          r_patches[r_numpatches[0]++] = &r_surfaces[i];
          BuildBezierPatch(&r_surfaces[i], cfactor);
        }
        break;
      case FACETYPE_MESH:
        r_meshes[r_nummeshes[0]++] = &r_surfaces[i];
        break;
      case FACETYPE_FLARE:
        r_flares[r_numflares[0]++] = &r_surfaces[i];
        break;
      default:
        break;
    }
  }

  // Creates the patches groups
  CreatePatchesGroups();

  // Compute the bounding box of each face
  // Note: The bounding box should not be calculated before because patches
  //       have special bounding box that are used for the patches groups
  //       construction.
  for (i = 0; i < r_numsurfaces[0]; ++i) CalcFaceBounds(&r_surfaces[i]);

  // Creates the patch brushes for collisions with patches
  CreatePatchesForLeafs();
}

void Q3BSP::BuildBezierPatch(Surface* surf, int curvefactor)
{
  // Generate the patches
  // Get patch flatness
  int flat[2], tess[2], size[2], n;
  vertex_t *v;

  vec4_t *in_xyz =     (vec4_t*) cake_malloc(surf->numverts[0]*sizeof(vec4_t), "Q3BSP::BuildBezierPatch.in_xyz");
  vec4_t *in_colors =  (vec4_t*) cake_malloc(surf->numverts[0]*sizeof(vec4_t), "Q3BSP::BuildBezierPatch.in_colors");
  vec4_t *in_normals = (vec4_t*) cake_malloc(surf->numverts[0]*sizeof(vec4_t), "Q3BSP::BuildBezierPatch.in_normals");
  vec4_t *in_lm_st =   (vec4_t*) cake_malloc(surf->numverts[0]*sizeof(vec4_t), "Q3BSP::BuildBezierPatch.in_lm_st");
  vec4_t *in_tex_st =  (vec4_t*) cake_malloc(surf->numverts[0]*sizeof(vec4_t), "Q3BSP::BuildBezierPatch.in_tex_st");
  if (!in_xyz || !in_colors || !in_normals || !in_lm_st || !in_tex_st)
  {
    gConsole->Insertln("^1Q3BSP::BuildBezierPatch.inBuffers: Cannot allocate required size");
    return;
  }

  v = surf->firstvert[0];
  for (n = 0; n < surf->numverts[0]; ++n, ++v)
  {
    VectorCopy(v->v_point, in_xyz[n]);
    VectorCopy(v->v_norm, in_normals[n]);
    Vector4Scale(v->colour, (1.f/255.f), in_colors[n]);
    Vector2Copy(v->tex_st, in_tex_st[n]);
    Vector2Copy(v->lm_st, in_lm_st[n]);
  }
  v = NULL;

  Patch_GetFlatness((float) curvefactor, in_xyz, surf->patch_cp, flat);

  // Create levels
  for (int lvl = 1; lvl < surf->levels; ++lvl)
  {
    int *tempElemsArray, *elems, p, numverts, numelems;
    vec4_t *tmp_buffer;

    tess[0] = (((flat[0]*(lvl-1))>>1)+1)*(1<<flat[0]);
    tess[1] = (((flat[1]*(lvl-1))>>1)+1)*(1<<flat[1]);
    size[0] = (surf->patch_cp[0]>>1)*tess[0]+1;
    size[1] = (surf->patch_cp[1]>>1)*tess[1]+1;
    numverts = size[0]*size[1];

    surf->numverts[lvl] = numverts;

    // Allocate vertices memory
    surf->firstvert[lvl] = (vertex_t*) cake_malloc(numverts*sizeof(vertex_t), "Q3BSP::BuildBezierPatch.surf->firstvert[lvl]");
    if (!surf->firstvert[lvl])
    {
      gConsole->Insertln("^1Q3BSP::BuildBezierPatch.surf->firstvert[lvl]: Cannot allocate required size");
      continue;
    }

    // Create temp buffer
    tmp_buffer = (vec4_t*) cake_malloc(numverts*sizeof(vec4_t), "Q3BSP::BuildBezierPatch.tmp_buffer");
    if (!tmp_buffer)
    {
      gConsole->Insertln("^1Q3BSP::BuildBezierPatch.tmp_buffer: Cannot allocate required size");
      continue;
    }

    // vertices
    Patch_Evaluate(in_xyz, surf->patch_cp, tess, tmp_buffer);
    for (n = 0; n < numverts; ++n)
    {
      VectorCopy(tmp_buffer[n], surf->firstvert[lvl][n].v_point);
    }

    // colours
    vec4_t c;
    Patch_Evaluate(in_colors, surf->patch_cp, tess, tmp_buffer);
    for (n = 0; n < numverts; ++n)
    {
      ColorNormalize(tmp_buffer[n], c);
      surf->firstvert[lvl][n].colour[0] = (unsigned char) (255.f * c[0]);
      surf->firstvert[lvl][n].colour[1] = (unsigned char) (255.f * c[1]);
      surf->firstvert[lvl][n].colour[2] = (unsigned char) (255.f * c[2]);
      surf->firstvert[lvl][n].colour[3] = (unsigned char) (255.f * c[3]);
    }

    // normals
    Patch_Evaluate(in_normals, surf->patch_cp, tess, tmp_buffer);
    for (n = 0; n < numverts; ++n)
    {
      VectorNormalize2(tmp_buffer[n], surf->firstvert[lvl][n].v_norm);
    }

    // lightmap coords
    Patch_Evaluate(in_lm_st, surf->patch_cp, tess, tmp_buffer);
    for (n = 0; n < numverts; ++n)
    {
      Vector2Copy(tmp_buffer[n], surf->firstvert[lvl][n].lm_st);
    }

    // texture coords
    Patch_Evaluate(in_tex_st, surf->patch_cp, tess, tmp_buffer);
    for (n = 0; n < numverts; ++n)
    {
      Vector2Copy(tmp_buffer[n], surf->firstvert[lvl][n].tex_st);
    }

    // Free temp variables
    cake_free(tmp_buffer);

    // Compute new elems avoiding adding invalid triangles

    numelems = 0;
    tempElemsArray = (int*) cake_malloc(6*numverts*sizeof(int), "Q3BSP::BuildBezierPatch.tempElemsArray");
    if (!tempElemsArray)
    {
      gConsole->Insertln("^1Q3BSP::BuildBezierPatch.tempElemsArray: Cannot allocate required size");
      continue;
    }

    elems = tempElemsArray;
    for (int y = 0; y < size[1]-1; ++y)
    {
      for (int x = 0; x < size[0]-1; ++x)
      {
        elems[0] = p = y * size[0] + x;
        elems[1] = p + size[0];
        elems[2] = p + 1;

        if (!VectorCompare(surf->firstvert[lvl][elems[0]].v_point, surf->firstvert[lvl][elems[1]].v_point) &&
          !VectorCompare(surf->firstvert[lvl][elems[0]].v_point, surf->firstvert[lvl][elems[2]].v_point) &&
          !VectorCompare(surf->firstvert[lvl][elems[1]].v_point, surf->firstvert[lvl][elems[2]].v_point))
        {
          if (numelems >= 6*numverts)
          {
            gConsole->Insertln("Array overflow !");
            continue;
          }
          elems += 3;
          numelems += 3;
        }

        elems[0] = p + 1;
        elems[1] = p + size[0];
        elems[2] = p + size[0] + 1;

        if (!VectorCompare(surf->firstvert[lvl][elems[0]].v_point, surf->firstvert[lvl][elems[1]].v_point) &&
          !VectorCompare(surf->firstvert[lvl][elems[0]].v_point, surf->firstvert[lvl][elems[2]].v_point) &&
          !VectorCompare(surf->firstvert[lvl][elems[1]].v_point, surf->firstvert[lvl][elems[2]].v_point))
        {
          if (numelems >= 6*numverts)
          {
            gConsole->Insertln("Array overflow !");
            continue;
          }
          elems += 3;
          numelems += 3;
        }
      }
    }

    // Allocate elems table
    surf->numelems[lvl] = numelems;
    surf->firstelem[lvl] = (int*) cake_malloc(numelems*sizeof(int), "Q3BSP::BuildBezierPatch.surf->firstelem[lvl]");
    if (!surf->firstelem[lvl])
    {
      gConsole->Insertln("^1Q3BSP::BuildBezierPatch.surf->firstelem[lvl]: Cannot allocate required size");
      continue;
    }
    memcpy(surf->firstelem[lvl], tempElemsArray, numelems*sizeof(int));
    cake_free(tempElemsArray);
  }

  cake_free(in_tex_st);
  cake_free(in_lm_st);
  cake_free(in_normals);
  cake_free(in_colors);
  cake_free(in_xyz);
}

// Load the lightmaps from the bsp
void Q3BSP::LoadLightmaps(void)
{
  BYTE *lightmapdata;

  int lightmapsize = ReadLump(LIGHTMAPS, (void**)&lightmapdata, 1);
  r_numlightmaps[0] = r_numlightmaps[1] = lightmapsize/LIGHTMAP_SIZE;
  r_lightmapinfos = (texinfo*) cake_malloc(r_numlightmaps[1]*sizeof(texinfo), "Q3BSP::LoadLightmaps.r_lightmapinfos");
  // lightmaps are allways overbrightened
  const float overbright = 4.0f;
  unsigned int top, r, g, b;
  for (int i = 0; i < r_numlightmaps[0]; ++i)
  {
    r_lightmapinfos[i].mem = &lightmapdata[i * LIGHTMAP_SIZE];
    r_lightmapinfos[i].bpp = 3;
    r_lightmapinfos[i].height = 128;
    r_lightmapinfos[i].width = 128;
    r_lightmapinfos[i].num = ~0;

    if (overbright != 1.0f)
    {
      int j;
      BYTE *c;

      c = &lightmapdata[i * LIGHTMAP_SIZE];

      for (j = 0; j < LIGHTMAP_SIZE/3; ++j, c += 3)
      {
        top =
        r = (unsigned int) ((float) c[0] * overbright);
        g = (unsigned int) ((float) c[1] * overbright);
        b = (unsigned int) ((float) c[2] * overbright);
        if (g > top) top = g;
        if (b > top) top = b;
        if (top > 255)
        {
          top = (255 << 8) / top;
          r = (r * top) >> 8;
          g = (g * top) >> 8;
          b = (b * top) >> 8;
        }

        c[0] = r;
        c[1] = g;
        c[2] = b;
      }
    }

    gRender->RegisterTexInfo(&r_lightmapinfos[i],
                 LF_LIGHTMAP | LF_NOMIPMAP | LF_NOPICMIP | LF_CLAMP);

    r_lightmapinfos[i].mem = NULL;
  }

  // We don't need this data any more
  cake_free(lightmapdata);
  lightmapdata = NULL;
}

void Q3BSP::LoadLightVols(void)
{
  r_numlightvols[0] = r_numlightvols[1] = ReadLump(LIGHTVOLS, (void**)&r_lightvols, sizeof(*r_lightvols));
}

void Q3BSP::LoadVisibility(void)
{
  r_numvisibility[0] = r_numvisibility[1] = ReadLump(VISIBILITY, (void**)&r_visibility, 1);
}

void Q3BSP::DisplayLevelshot(void)
{
  gOver->Quad(levelshot, 0, 0, (float) gRender->GetWidth(), (float) gRender->GetHeight());
  gOver->Quad(levelshotdetail, 0, 0, (float) gRender->GetWidth(), (float) gRender->GetHeight(), 2.5, 2);
  gOver->Render(&gFramework->shaders);
}

void Q3BSP::DisplayLoadingMessage(const char *msg, int line)
{
  float l = (float) (SMALL_CHAR_HEIGHT*line);
  if (l < 0) l = (float)(gRender->GetHeight()-SMALL_CHAR_HEIGHT)/2.f;

  gOver->Quad(levelshot, 0, 0, (float) gRender->GetWidth(), (float) gRender->GetHeight());
  gOver->Quad(levelshotdetail, 0, 0, (float) gRender->GetWidth(), (float) gRender->GetHeight(), 2.5, 2);

  if (worldname)
  {
    gOver->String(worldname,
                  gFramework->GetFont(NORMAL_CHAR),
                  (float) (gRender->GetWidth()-SMALL_CHAR_WIDTH*strlen(worldname))/2.f,
                  l - 2*SMALL_CHAR_HEIGHT);
  }
  gOver->String(msg,
                gFramework->GetFont(NORMAL_CHAR),
                (float) (gRender->GetWidth()-SMALL_CHAR_WIDTH*strlen(msg))/2.f,
                l);

  gOver->Render(&gFramework->shaders);
  gRender->SwapBuffers();
}

// Loads a levelshot in framework
void Q3BSP::LoadLevelshot(const char* map_name)
{
  char levelshot_name[256] = { '\0' };
  int levelshot_found = 0;

  // search levelshot having TGA or JPG extension
  sprintf(levelshot_name, "levelshots/%s.jpg", map_name);
  levelshot_found = FileExist(levelshot_name, 1, 0);
  if (!levelshot_found)
  {
    sprintf(levelshot_name, "levelshots/%s.tga", map_name);
    levelshot_found = FileExist(levelshot_name, 1, 0);
  }

  if (!levelshot_found)
    strcpy(levelshot_name, "menu/art/unknownmap.jpg");

  levelshotdetail = gFramework->shaders.AddShader("levelShotDetail", 0, 0, FACETYPE_MESH);
  levelshot = gFramework->shaders.AddShader(levelshot_name, 0, 0, FACETYPE_MESH);

  gFramework->Update();
}

//-----------------------------------------------------------------------------
// Data Preprocessing Routines
//-----------------------------------------------------------------------------

// Calculate the parent of each leaf and each node
void Q3BSP::SetParent(int node, cnode_t *parent)
{
  if (node < 0) // is a leaf
  {
    r_leafs[~node].parent = parent;
    return;
  }

  r_nodes[node].parent = parent;
  SetParent(r_nodes[node].children[0], &r_nodes[node]);
  SetParent(r_nodes[node].children[1], &r_nodes[node]);
}

void Q3BSP::InitAutosprite(Surface *surf, int type)
{
  float mat[16], tmp;
  vec3_t n, s, t, m, backup[4];
  int i;

  VectorClear(m);
  tmp = 1.f/(float)surf->numverts[0];
  for (i = 0; i < surf->numverts[0]; ++i)
  {
    VectorAdd(m, surf->firstvert[0][i].v_point, m);
  }
  VectorScale(m, tmp, m);

  VectorSub(surf->firstvert[0][surf->firstelem[0][1]].v_point, surf->firstvert[0][surf->firstelem[0][0]].v_point, s);
  tmp = InverseSqrt(s[0]*s[0]+s[1]*s[1]+s[2]*s[2]);
  VectorScale(s, tmp, s);

  VectorSub(surf->firstvert[0][surf->firstelem[0][0]].v_point, surf->firstvert[0][surf->firstelem[0][2]].v_point, t);
  tmp = InverseSqrt(t[0]*t[0]+t[1]*t[1]+t[2]*t[2]);
  VectorScale(t, tmp, t);

  CrossProduct(s, t, n);

  mat[0]  = s[0]; mat[1]  = s[1]; mat[2]  = s[2]; mat[3]  = 0;
  mat[4]  = t[0]; mat[5]  = t[1]; mat[6]  = t[2]; mat[7]  = 0;
  mat[8]  = n[0]; mat[9]  = n[1]; mat[10] = n[2]; mat[11] = 0;
  mat[12] = 0;    mat[13] = 0;    mat[14] = 0;    mat[15] = 1;

  glMatrixMode(GL_MODELVIEW);
  glPushMatrix();
  glLoadMatrixf(mat);
  glRotatef( 90, 1, 0, 0);
  glRotatef(-90, 0, 1, 0);
  glGetFloatv(GL_MODELVIEW_MATRIX, mat);
  glPopMatrix();
  gRender->CheckGLError(7);

  for (int v = 0; v < surf->numverts[0]; v += 4)
  {
    VectorCopy(surf->firstvert[0][v].v_point, backup[0]);
    VectorSub(surf->firstvert[0][v].v_point, m, surf->firstvert[0][v].v_point);
    MultVect4x4(mat, surf->firstvert[0][v].v_point, surf->firstvert[0][v].v_point);
    VectorAdd(surf->firstvert[0][v].v_point, m, surf->firstvert[0][v].v_point);

    VectorCopy(surf->firstvert[0][v+1].v_point, backup[1]);
    VectorSub(surf->firstvert[0][v+1].v_point, m, surf->firstvert[0][v+1].v_point);
    MultVect4x4(mat, surf->firstvert[0][v+1].v_point, surf->firstvert[0][v+1].v_point);
    VectorAdd(surf->firstvert[0][v+1].v_point, m, surf->firstvert[0][v+1].v_point);

    VectorCopy(surf->firstvert[0][v+2].v_point, backup[2]);
    VectorSub(surf->firstvert[0][v+2].v_point, m, surf->firstvert[0][v+2].v_point);
    MultVect4x4(mat, surf->firstvert[0][v+2].v_point, surf->firstvert[0][v+2].v_point);
    VectorAdd(surf->firstvert[0][v+2].v_point, m, surf->firstvert[0][v+2].v_point);

    VectorCopy(surf->firstvert[0][v+3].v_point, backup[3]);
    VectorSub(surf->firstvert[0][v+3].v_point, m, surf->firstvert[0][v+3].v_point);
    MultVect4x4(mat, surf->firstvert[0][v+3].v_point, surf->firstvert[0][v+3].v_point);
    VectorAdd(surf->firstvert[0][v+3].v_point, m, surf->firstvert[0][v+3].v_point);

    if (type == DEFORMVERTEXES_AUTOSPRITE2)
    {
      // get longer axis
      float dx = (float) (pow(surf->firstvert[0][v+1].v_point[0]-surf->firstvert[0][v].v_point[0], 2)+
                          pow(surf->firstvert[0][v+2].v_point[0]-surf->firstvert[0][v].v_point[0], 2)+
                          pow(surf->firstvert[0][v+3].v_point[0]-surf->firstvert[0][v].v_point[0], 2));
      float dy = (float) (pow(surf->firstvert[0][v+1].v_point[1]-surf->firstvert[0][v].v_point[1], 2)+
                          pow(surf->firstvert[0][v+2].v_point[1]-surf->firstvert[0][v].v_point[1], 2)+
                          pow(surf->firstvert[0][v+3].v_point[1]-surf->firstvert[0][v].v_point[1], 2));
      float dz = (float) (pow(surf->firstvert[0][v+1].v_point[2]-surf->firstvert[0][v].v_point[2], 2)+
                          pow(surf->firstvert[0][v+2].v_point[2]-surf->firstvert[0][v].v_point[2], 2)+
                          pow(surf->firstvert[0][v+3].v_point[2]-surf->firstvert[0][v].v_point[2], 2));
      if (dx > dz)
      {
        surf->autosprite2_axis = 0;
        // restore initial rotation
        // TODO: terminate this stuff !!
        VectorCopy(backup[0], surf->firstvert[0][v  ].v_point);
        VectorCopy(backup[1], surf->firstvert[0][v+1].v_point);
        VectorCopy(backup[2], surf->firstvert[0][v+2].v_point);
        VectorCopy(backup[3], surf->firstvert[0][v+3].v_point);
      }
      else surf->autosprite2_axis = 2;
    }
  }

  VectorCopy(m, surf->v_orig);
  MultVect4x4(mat, n, surf->v_norm);
}

#define cm_subdivlevel  15

void Q3BSP::CreateBrush(cbrush_t *brush, vec3_t *verts, int surface_shader)
{
  int i, j, k, sign;
  vec3_t v1, v2, v3, v4, v5, v6, normal, absmins, absmaxs;
  cbrushside_t *side;
  cplane_t *plane;
  static cplane_t mainplane, patchplanes[20];
  bool skip[20];
  int numpatchplanes = 0;

  // calc absmins & absmaxs
  ClearBounds(absmins, absmaxs);
  AddPointToBounds(verts[0], absmins, absmaxs);
  AddPointToBounds(verts[1], absmins, absmaxs);
  AddPointToBounds(verts[2], absmins, absmaxs);

  PlaneFromPoints(verts, &mainplane);

  // front plane
  plane = &patchplanes[numpatchplanes++];
  *plane = mainplane;

  // back plane
  plane = &patchplanes[numpatchplanes++];
  VectorNegate(mainplane.normal, plane->normal);
  plane->dist = -mainplane.dist;

  // axial planes
  for (sign = -1; sign <= 1; sign += 2)
  {
    plane = &patchplanes[numpatchplanes++];
    VectorClear(plane->normal);
    plane->normal[0] = (vec_t) sign;
    plane->dist = sign > 0 ? absmaxs[0] : -absmins[0];
  }
  for (sign = -1; sign <= 1; sign += 2)
  {
    plane = &patchplanes[numpatchplanes++];
    VectorClear(plane->normal);
    plane->normal[1] = (vec_t) sign;
    plane->dist = sign > 0 ? absmaxs[1] : -absmins[1];
  }
  for (sign = -1; sign <= 1; sign += 2)
  {
    plane = &patchplanes[numpatchplanes++];
    VectorClear(plane->normal);
    plane->normal[2] = (vec_t) sign;
    plane->dist = sign > 0 ? absmaxs[2] : -absmins[2];
  }

  // edge planes

  VectorCopy(verts[0], v1);
  VectorCopy(verts[1%3], v2);
  VectorCopy(verts[1], v3);
  VectorCopy(verts[2%3], v4);
  VectorCopy(verts[2], v5);
  VectorCopy(verts[3%3], v6);

  for (k = 0; k < 3; k++)
  {
    normal[k] = 0;
    normal[(k+1)%3] =   v1[(k+2)%3] - v2[(k+2)%3];
    normal[(k+2)%3] = -(v1[(k+1)%3] - v2[(k+1)%3]);

    if (normal[0] != 0 || normal[1] != 0 || normal[2] != 0)
    {
      plane = &patchplanes[numpatchplanes++];

      VectorNormalize(normal);
      VectorCopy(normal, plane->normal);
      plane->dist = DotProduct(plane->normal, v1);

      if (DotProduct(verts[(0+2)%3], normal) - plane->dist > 0)
      {
        // invert
        VectorInverse ( plane->normal );
        plane->dist = -plane->dist;
      }
    }

    normal[k] = 0;
    normal[(k+1)%3] =   v3[(k+2)%3] - v4[(k+2)%3];
    normal[(k+2)%3] = -(v3[(k+1)%3] - v4[(k+1)%3]);

    if (normal[0] != 0 || normal[1] != 0 || normal[2] != 0)
    {
      plane = &patchplanes[numpatchplanes++];

      VectorNormalize(normal);
      VectorCopy(normal, plane->normal);
      plane->dist = DotProduct(plane->normal, v3);

      if (DotProduct(verts[3%3], normal) - plane->dist > 0)
      {
        // invert
        VectorInverse ( plane->normal );
        plane->dist = -plane->dist;
      }
    }

    normal[k] = 0;
    normal[(k+1)%3] =   v5[(k+2)%3] - v6[(k+2)%3];
    normal[(k+2)%3] = -(v5[(k+1)%3] - v6[(k+1)%3]);

    if (normal[0] != 0 || normal[1] != 0 || normal[2] != 0)
    {
      plane = &patchplanes[numpatchplanes++];

      VectorNormalize(normal);
      VectorCopy(normal, plane->normal);
      plane->dist = DotProduct(plane->normal, v5);

      if (DotProduct(verts[4%3], normal) - plane->dist > 0)
      {
        // invert
        VectorInverse ( plane->normal );
        plane->dist = -plane->dist;
      }
    }
  }

  // set plane->type and mark duplicate planes for removal
  for (i = 0; i < numpatchplanes; i++)
  {
    CategorizePlane(&patchplanes[i]);
    skip[i] = false;

    for (j = i + 1; j < numpatchplanes; j++)
      if (patchplanes[j].dist == patchplanes[i].dist &&
        VectorCompare(patchplanes[j].normal, patchplanes[i].normal))
      {
        skip[i] = true;
        break;
      }
  }

  brush->numsides = 0;
  brush->firstbrushside = r_numbrushsides[0];

  for (k = 0; k < 2; k++)
  {
    for (i = 0; i < numpatchplanes; i++)
    {
      if (skip[i]) continue;

      // first, store all axially aligned planes
      // then store everything else
      // does it give a noticeable speedup?
      if (!k && patchplanes[i].type >= 3) continue;

      skip[i] = true;

      while (r_numplanes[0] >= r_numplanes[1])
      {
        // force reallocation
        r_numplanes[1] += (MAX_CM_PLANES+12);
        if (!(r_planes = (cplane_t*) cake_realloc(r_planes, r_numplanes[1]*sizeof(cplane_t), "Q3BSP::CreateBrush.r_planes")))
          ThrowException(ALLOCATION_ERROR, "Q3BSP::CreateBrushr_planes");
      }

      plane = &r_planes[r_numplanes[0]];
      *plane = patchplanes[i];

      while (r_numbrushsides[0] >= r_numbrushsides[1])
      {
        // force reallocation
        r_numbrushsides[1] += (MAX_CM_BRUSHSIDES+6);
        if (!(r_brushsides = (cbrushside_t*) cake_realloc(r_brushsides, r_numbrushsides[1]*sizeof(cbrushside_t), "Q3BSP::CreateBrush.r_brushsides")))
          ThrowException(ALLOCATION_ERROR, "Q3BSP::CreateBrush.r_brushsides");
      }

      side = &r_brushsides[r_numbrushsides[0]++];
      side->planeidx = r_numplanes[0]++;

      if (DotProduct(plane->normal, mainplane.normal) >= 0) side->shader = surface_shader;
      else side->shader = -1; // don't clip against this side

      brush->numsides++;
    }
  }
}

void Q3BSP::CreatePatch(cpatch_t *patch, int numverts, vec4_t *verts, int *patch_cp)
{
  int step[2], size[2], flat[2], i, u, v;
  vec4_t points[MAX_CM_PATCH_VERTS];
  vec3_t tverts[4], tverts2[4];
  Shader* shad = world->shaders.GetShader(patch->shader);
  int brushidx;

  // find the degree of subdivision in the u and v directions
  Patch_GetFlatness(cm_subdivlevel, verts, patch_cp, flat);

  step[0] = (1 << flat[0]);
  step[1] = (1 << flat[1]);
  size[0] = (patch_cp[0]>>1) * step[0] + 1;
  size[1] = (patch_cp[1]>>1) * step[1] + 1;

  if (size[0]*size[1] > MAX_CM_PATCH_VERTS)
  {
    gConsole->Insertln("CM_CreatePatch: patch has too many vertices");
    return;
  }

  // fill in
  Patch_Evaluate(verts, patch_cp, step, points);

  patch->firstbrush = brushidx = r_numbrushes[0];
  patch->numbrushes = 0;

  ClearBounds(patch->absmins, patch->absmaxs);

  // create a set of brushes
  for (v = 0; v < size[1]-1; v++)
  {
    for (u = 0; u < size[0]-1; u++)
    {
      while (r_numbrushes[0] >= r_numbrushes[1])
      {
        // force reallocation
        r_numbrushes[1] += (MAX_CM_BRUSHES+1);
        if (!(r_brushes = (cbrush_t*) cake_realloc(r_brushes, r_numbrushes[1]*sizeof(cbrush_t), "Q3BSP::CreateBrush.r_brushes")))
          ThrowException(ALLOCATION_ERROR, "Q3BSP::CreateBrush.r_brushes");
      }

      i = v*size[0]+u;
      VectorCopy(points[i],           tverts[0]);
      VectorCopy(points[i+size[0]],   tverts[1]);
      VectorCopy(points[i+1],         tverts[2]);
      VectorCopy(points[i+size[0]+1], tverts[3]);

      AddPointToBounds(tverts[0], patch->absmins, patch->absmaxs);
      AddPointToBounds(tverts[1], patch->absmins, patch->absmaxs);
      AddPointToBounds(tverts[2], patch->absmins, patch->absmaxs);
      AddPointToBounds(tverts[3], patch->absmins, patch->absmaxs);

      // create two brushes
      CreateBrush(&r_brushes[brushidx], tverts, patch->shader);

      r_brushes[brushidx].contents = shad?shad->content_flags:0;
      brushidx++; r_numbrushes[0]++; patch->numbrushes++;

      VectorCopy(tverts[2], tverts2[0]);
      VectorCopy(tverts[1], tverts2[1]);
      VectorCopy(tverts[3], tverts2[2]);
      CreateBrush(&r_brushes[brushidx], tverts2, patch->shader);

      r_brushes[brushidx].contents = shad?shad->content_flags:0;
      brushidx++; r_numbrushes[0]++; patch->numbrushes++;
    }
  }
}

void Q3BSP::CreatePatchesForLeafs(void)
{
  gConsole->Insertln("Creating patches for leafs...");

  int i, j, k;
  cleaf_t *leaf;
  Surface *face;
  cpatch_t *patch;
  Shader *shad;
  int *checkout = new int [r_numsurfaces[0]];

  memset(checkout, -1, sizeof(int)*r_numsurfaces[0]);

  // Destroy existing (shouldn't exist one) leafpatches
  if (r_leafpatches)
  {
    cake_free(r_leafpatches);
    gConsole->Insertln("^5WARNING: leafpatch structure deleted (shouldn't be defined !)");
  }
  r_numleafpatches[0] = 0;
  r_numleafpatches[1] = MAX_CM_LEAFFACES;
  if (!(r_leafpatches = (int*) cake_realloc(r_leafpatches, r_numleafpatches[1]*sizeof(int), "Q3BSP::CreatePatchesForLeafs.r_leafpatches")))
  {
    gConsole->Insertln("^1Q3BSP::CreatePatchesForLeafs.r_leafpatches: Cannot allocate required size");
    return;
  }

  // Destroy existing cpatches (shouldn't exist any)
  r_numcpatches[0] = 0;
  r_numcpatches[1] = MAX_CM_PATCHES;
  if (!(r_cpatches = (cpatch_t*) cake_malloc(r_numcpatches[1]*sizeof(cpatch_t), "Q3BSP::CreatePatchesForLeafs.r_cpatches")))
  {
    gConsole->Insertln("^1Q3BSP::CreatePatchesForLeafs.r_cpatches: Cannot allocate required size");
    return;
  }
  memset(r_cpatches, 0, r_numcpatches[1]*sizeof(cpatch_t));

  for (i = 0, leaf = r_leafs; i < r_numleafs[0]; i++, leaf++)
  {
    leaf->numleafpatches = 0;
    leaf->firstleafpatch = r_numleafpatches[0];

    if (leaf->cluster == -1) continue;

    for (j = 0; j < leaf->numleaffaces; j++)
    {
      k = leaf->firstleafface + j;
      if (k >= r_numleaffaces[0]) break;

      k = r_leaffaces[k];
      face = &r_surfaces[k];

      if (face->facetype != FACETYPE_PATCH || face->numverts[0] <= 0) continue;
      if (face->patch_cp[0] <= 0 || face->patch_cp[1] <= 0) continue;
      if (!(shad = world->shaders.GetShader(face->shader))) continue;
      if (!shad->content_flags || (shad->surface_flags & SURF_NONSOLID)) continue;

      while (r_numleafpatches[0] >= r_numleafpatches[1])
      {
        // force reallocation
        r_numleafpatches[1] += MAX_CM_LEAFFACES;
        if (!(r_leafpatches = (int*) cake_realloc(r_leafpatches, r_numleafpatches[1]*sizeof(int), "Q3BSP::CreatePatchesForLeafs.r_leafpatches")))
          ThrowException(ALLOCATION_ERROR, "Q3BSP::CreatePatchesForLeafs.r_leafpatches");
      }

      // the patch was already built
      if (checkout[k] != -1)
      {
        r_leafpatches[r_numleafpatches[0]] = checkout[k];
        patch = &r_cpatches[checkout[k]];
      }
      else
      {
        while (r_numcpatches[0] >= r_numcpatches[1])
        {
          // force reallocation
          r_numcpatches[1] += MAX_CM_PATCHES;
          if (!(r_cpatches = (cpatch_t*) cake_realloc(r_cpatches, r_numcpatches[1]*sizeof(cpatch_t), "Q3BSP::CreatePatchesForLeafs.r_patches")))
            ThrowException(ALLOCATION_ERROR, "Q3BSP::CreatePatchesForLeafs.r_patches");
        }

        patch = &r_cpatches[r_numcpatches[0]];
        patch->shader = face->shader;
        r_leafpatches[r_numleafpatches[0]] = r_numcpatches[0];
        checkout[k] = r_numcpatches[0]++;

        // Create a verts array for the CreatePatch function
        vec4_t *verts = new vec4_t[face->numverts[0]];
        if (!verts) ThrowException(ALLOCATION_ERROR, "Q3BSP::BuildBezierPatch.verts");

        for (int n = 0; n < face->numverts[0]; ++n)
        {
          VectorCopy(face->firstvert[0][n].v_point, verts[n]);
        }

        CreatePatch(patch, face->numverts[0], verts, face->patch_cp);

        delete [] verts;
      }

      if ((shad = world->shaders.GetShader(patch->shader)))
        leaf->contents |= shad->content_flags;
      else
        leaf->contents |= -1;
      leaf->numleafpatches++;

      r_numleafpatches[0]++;
    }
  }

  delete [] checkout;
}

// ----------------------------------------------------------------------------

#define PLANE_EPSILON   0.001f
bool Q3BSP::PointInsideBrush(int brushnum, vec3_t p)
{
  cbrush_t *brush = &r_brushes[brushnum];
  cbrushside_t *side;

  for (int i = 0; i < brush->numsides; ++i)
  {
    side = &r_brushsides[brush->firstbrushside+i];
    if (PointDistance(p, r_planes+side->planeidx) > PLANE_EPSILON) return false;
  }

  return true;
}

// ------------------------------------------------------------
//  Movement clipping
// ------------------------------------------------------------
trace_t Q3BSP::CheckMove(vec3_t start, vec3_t mins, vec3_t maxs, vec3_t end, int head_node, int brushmask)
{
  trace_t trace_trace;
  vec3_t point;

  ++checkcount;   // for multi-check avoidance

  // fill in a default trace
  memset(&trace_trace, 0, sizeof(trace_trace));
  trace_trace.fraction = 1;
  trace_trace.contents = 0;
  trace_trace.shader = -1;
//  trace_trace.ent = NULL;

  if (!r_numnodes[0]) return trace_trace;

  trace_trace.tracemask = brushmask;
  VectorCopy(start, trace_trace.start);
  VectorCopy(end, trace_trace.end);
  VectorCopy(mins, trace_trace.mins);
  VectorCopy(maxs, trace_trace.maxs);

  // build a bounding box of the entire move
  ClearBounds(trace_trace.absmins, trace_trace.absmaxs);
  VectorAdd(start, trace_trace.mins, point);
  AddPointToBounds(point, trace_trace.absmins, trace_trace.absmaxs);
  VectorAdd(start, trace_trace.maxs, point);
  AddPointToBounds(point, trace_trace.absmins, trace_trace.absmaxs);
  VectorAdd(end, trace_trace.mins, point);
  AddPointToBounds(point, trace_trace.absmins, trace_trace.absmaxs);
  VectorAdd(end, trace_trace.maxs, point);
  AddPointToBounds(point, trace_trace.absmins, trace_trace.absmaxs);

  // Check for position test special case
  if (start[0] == end[0] && start[1] == end[1] && start[2] == end[2])
  {
    int     leafs[1024];
    int     i, numleafs;
    vec3_t  c1, c2;
    int     topnode;

    VectorAdd(start, mins, c1);
    VectorAdd(start, maxs, c2);

    c1[0] -= 1; c2[0] += 1;
    c1[1] -= 1; c2[1] += 1;
    c1[2] -= 1; c2[2] += 1;

    numleafs = BoxLeafnums_headnode(c1, c2, leafs, 1024, head_node, &topnode);
    for (i = 0; i < numleafs; ++i)
    {
      TestInLeaf(leafs[i], &trace_trace);
      if (trace_trace.allSolid) break;
    }
    VectorCopy(start, trace_trace.end);
    return trace_trace;
  }

  // check for point special case
  if (mins[0] == 0 && maxs[0] == 0 &&
      mins[1] == 0 && maxs[1] == 0 &&
      mins[2] == 0 && maxs[2] == 0)
  {
    trace_trace.isPoint = true;
    VectorClear(trace_trace.size);
  }
  else
  {
    trace_trace.isPoint = false;
    trace_trace.size[0] = -mins[0] > maxs[0] ? -mins[0] : maxs[0];
    trace_trace.size[1] = -mins[1] > maxs[1] ? -mins[1] : maxs[1];
    trace_trace.size[2] = -mins[2] > maxs[2] ? -mins[2] : maxs[2];
  }

  RecursiveHullCheck(0, 1, start, end, head_node, &trace_trace);

  // Calculate final coordinates
  if (trace_trace.fraction == 1)
  {
    VectorCopy(end, trace_trace.end);
  }
  else
  {
    trace_trace.end[0] = start[0] + trace_trace.fraction * (end[0] - start[0]);
    trace_trace.end[1] = start[1] + trace_trace.fraction * (end[1] - start[1]);
    trace_trace.end[2] = start[2] + trace_trace.fraction * (end[2] - start[2]);
  }

  return trace_trace;
}

void Q3BSP::RecursiveHullCheck(float sf, float ef,
                               const vec3_t sp, const vec3_t ep,
                               int node_num, trace_t *trace_trace)
{
  float t1, t2, offset;

  // If the path was blocked by a nearer obstacle, don't bother checking
  if (trace_trace->fraction <= sf) return;

  // We found a leaf, check the whole path against its brushes
  if (node_num < 0)
  {
    TraceToLeaf(~node_num, trace_trace);
    return;
  }

  cnode_t* node = r_nodes + node_num;
  cplane_t* plane = r_planes + node->planeidx;

  if (plane->type < 3)
  {
    t1 = sp[plane->type] - plane->dist;
    t2 = ep[plane->type] - plane->dist;
    offset = trace_trace->size[plane->type];
  }
  else
  {
    t1 = DotProduct(sp, plane->normal) - plane->dist;
    t2 = DotProduct(ep, plane->normal) - plane->dist;
    if (trace_trace->isPoint)
      offset = 0;
    else
      offset = (fabsf(trace_trace->size[0]*plane->normal[0]) +
                fabsf(trace_trace->size[1]*plane->normal[1]) +
                fabsf(trace_trace->size[2]*plane->normal[2]));
  }

#if 0
  RecursiveHullCheck(sf, ef, sp, ep, node->children[0], trace_trace); // front
  RecursiveHullCheck(sf, ef, sp, ep, node->children[1], trace_trace); // back
  return;
#endif

  // The whole volume is in front of the plane
  // See which sides we need to consider
  if ((t1 >= offset) && (t2 >= offset))
  {
    RecursiveHullCheck(sf, ef, sp, ep, node->children[0], trace_trace); // front
    return;
  }

  // The whole volume is in the back of the plane
  if ((t1 < -offset) && (t2 < -offset))
  {
    RecursiveHullCheck(sf, ef, sp, ep, node->children[1], trace_trace); // back
    return;
  }

  // Else, the box is split. Check the two halves.
  int side;
  float idist, frac, frac2, midf;
  vec3_t midp;

  // Put the crosspoint DIST_EPSILON pixels on the near side
  if (t1 < t2)
  {
    idist = 1.f / (t1 - t2);
    side  = 1;  // back
    frac  = (t1 - offset + DIST_EPSILON) * idist;
    frac2 = (t1 + offset + DIST_EPSILON) * idist;
  }
  else if (t1 > t2)
  {
    idist = 1.f / (t1 - t2);
    side  = 0;  // front
    frac  = (t1 + offset + DIST_EPSILON) * idist;
    frac2 = (t1 - offset - DIST_EPSILON) * idist;
  }
  else
  {
    side  = 0;  // front
    frac  = 1;
    frac2 = 0;
  }

  // Move from start to the plane (move up to the node)
  if (frac < 0) frac = 0;
  if (frac > 1) frac = 1;

  midf = sf + (ef - sf)*frac;
  midp[0] = sp[0] + frac*(ep[0] - sp[0]);
  midp[1] = sp[1] + frac*(ep[1] - sp[1]);
  midp[2] = sp[2] + frac*(ep[2] - sp[2]);

  RecursiveHullCheck(sf, midf, sp, midp, node->children[side], trace_trace);

  // Move from the plane to the end
  // Go past the node
  if (frac2 < 0) frac2 = 0;
  if (frac2 > 1) frac2 = 1;

  midf = sf + (ef - sf)*frac2;
  midp[0] = sp[0] + frac2*(ep[0] - sp[0]);
  midp[1] = sp[1] + frac2*(ep[1] - sp[1]);
  midp[2] = sp[2] + frac2*(ep[2] - sp[2]);

  RecursiveHullCheck(midf, ef, midp, ep, node->children[side^1], trace_trace);
}

void Q3BSP::TraceToLeaf(int leafnum, trace_t *trace_trace)
{
  cleaf_t* leaf = &r_leafs[leafnum];
  if (!(leaf->contents & trace_trace->tracemask)) return;

  int i, brushnum, patchnum;
  cbrush_t *cbrush;
  cpatch_t *cpatch;
  Shader* shad;

  for (i = 0; i < leaf->numleafbrushes; ++i)
  {
    brushnum = r_leafbrushes[leaf->firstleafbrush+i];
    cbrush = &r_brushes[brushnum];

    if (cbrush->checkcount == checkcount) continue; // already checked this brush in another leaf
    cbrush->checkcount = checkcount;

    if (!(cbrush->contents & trace_trace->tracemask)) continue;

    ClipBoxToBrush(cbrush, trace_trace);

    // Already fully blocked
    if (!trace_trace->fraction) return;
  }

  if (r_nocurves.ivalue) return;

  for (i = 0; i < leaf->numleafpatches; ++i)
  {
    patchnum = r_leafpatches[leaf->firstleafpatch+i];
    cpatch = &r_cpatches[patchnum];

    if (cpatch->checkcount == checkcount) continue; // already checked this patch in another leaf
    cpatch->checkcount = checkcount;

    if (!(shad = world->shaders.GetShader(cpatch->shader))) continue;
    if (!(shad->content_flags & trace_trace->tracemask)) continue;
    if (!BoundsIntersect(cpatch->absmins, cpatch->absmaxs, trace_trace->absmins, trace_trace->absmaxs)) continue;

    for (int j = 0; j < cpatch->numbrushes; ++j)
    {
      ClipBoxToPatch(&r_brushes[cpatch->firstbrush+j], trace_trace);
      if (!trace_trace->fraction) return;
    }
  }
}

void Q3BSP::TestInLeaf(int leafnum, trace_t *trace_trace)
{
  cleaf_t* leaf = &r_leafs[leafnum];
  if (!(leaf->contents & trace_trace->tracemask)) return;

  int i, brushnum, patchnum;
  cbrush_t *cbrush;
  cpatch_t *cpatch;
  Shader *shad;

  for (i = 0; i < leaf->numleafbrushes; ++i)
  {
    brushnum = r_leafbrushes[leaf->firstleafbrush+i];
    cbrush = &r_brushes[brushnum];

    if (cbrush->checkcount == checkcount) continue; // already checked this brush in another leaf
    cbrush->checkcount = checkcount;

    if (!(cbrush->contents & trace_trace->tracemask)) continue;

    TestBoxInBrush(cbrush, trace_trace);

    // Already fully blocked
    if (!trace_trace->fraction) return;
  }

  if (r_nocurves.ivalue) return;

  for (i = 0; i < leaf->numleafpatches; ++i)
  {
    patchnum = r_leafpatches[leaf->firstleafpatch+i];
    cpatch = &r_cpatches[patchnum];

    if (cpatch->checkcount == checkcount) continue; // already checked this patch in another leaf
    cpatch->checkcount = checkcount;

    if (!(shad = world->shaders.GetShader(cpatch->shader))) continue;
    if (!(shad->content_flags & trace_trace->tracemask)) continue;
    if (!BoundsIntersect(cpatch->absmins, cpatch->absmaxs, trace_trace->absmins, trace_trace->absmaxs)) continue;

    for (int j = 0; j < cpatch->numbrushes; ++j)
    {
      TestBoxInPatch(&r_brushes[cpatch->firstbrush+j], trace_trace);
      if (!trace_trace->fraction) return;
    }
  }
}

void Q3BSP::ClipBoxToBrush(cbrush_t *brush, trace_t *trace)
{
  if (brush->numsides <= 0) return;

  cbrushside_t *side, *leadside = NULL;
  cplane_t* plane, *clipplane = NULL;
  vec3_t ofs;
  float d1, d2, f;
  float enterfrac = -1;
  float leavefrac = 1;
  bool startout = false;
  bool getout = false;
  vec3_t hitNormal = { 0, 0, 0 };

  for (int i = 0; i < brush->numsides; ++i)
  {
    side = &r_brushsides[brush->firstbrushside+i];
    plane = &r_planes[side->planeidx];

    // FIXME: special case for axial

    if (!trace->isPoint)
    {
      // Calculate distances, taking the bounding box dimensions into account
      if (plane->normal[0] < 0) ofs[0] = trace->maxs[0]; else ofs[0] = trace->mins[0];
      if (plane->normal[1] < 0) ofs[1] = trace->maxs[1]; else ofs[1] = trace->mins[1];
      if (plane->normal[2] < 0) ofs[2] = trace->maxs[2]; else ofs[2] = trace->mins[2];

      if (plane->type < 3)
      {
        d1 = trace->start[plane->type] + ofs[plane->type] - plane->dist;
        d2 = trace->end[plane->type] + ofs[plane->type] - plane->dist;
      }
      else
      {
        d1 = (trace->start[0] + ofs[0]) * plane->normal[0] +
             (trace->start[1] + ofs[1]) * plane->normal[1] +
             (trace->start[2] + ofs[2]) * plane->normal[2] - plane->dist;
        d2 = (trace->end[0] + ofs[0]) * plane->normal[0] +
             (trace->end[1] + ofs[1]) * plane->normal[1] +
             (trace->end[2] + ofs[2]) * plane->normal[2] - plane->dist;
      }
    }
    else
    { // special point case
      if (plane->type < 3)
      {
        d1 = trace->start[plane->type] - plane->dist;
        d2 = trace->end[plane->type] - plane->dist;
      }
      else
      {
        d1 = DotProduct(trace->start, plane->normal) - plane->dist;
        d2 = DotProduct(trace->end, plane->normal) - plane->dist;
      }
    }

    #if 0
      if (d2 >= -DIST_EPSILON) getout = true;
      if (d1 >= -DIST_EPSILON) startout = true;
    #else
      if (d2 > 0) getout = true;
      if (d1 > 0) startout = true;
    #endif

    // Both in front of face : outside this brush (completely in front of face, no intersection)
    if ((d1 > 0) && (d2 >= d1)) return;

    // Both behind the face : will get clipped by another plane
    if ((d1 <= 0) && (d2 <= 0)) continue;

    // crosses face
    if (d1 > d2)  // Entering the brush
    {
      f = (d1 - DIST_EPSILON) / (d1 - d2);
      if (f > enterfrac)
      {
        enterfrac = f;
        VectorCopy(plane->normal, hitNormal);
        clipplane = plane;
        leadside = side;
      }
    }
    else
    {
      f = (d1 + DIST_EPSILON) / (d1 - d2);
      if (f < leavefrac) leavefrac = f;
    }
  }

  if (!startout)
  {
    // original point was inside brush
    trace->startSolid = true;
    if (!getout) trace->allSolid = true;
    return;
  }

  if (enterfrac < leavefrac)
  {
    if (enterfrac > -1 && enterfrac < trace->fraction)
    {
      if (enterfrac < 0) enterfrac = 0;
      trace->fraction = enterfrac;
      trace->plane = *clipplane;
      trace->shader = leadside->shader;
      trace->contents = brush->contents;
    }
  }
}

void Q3BSP::ClipBoxToPatch(cbrush_t *brush, trace_t *trace)
{
  if (brush->numsides <= 0) return;

  cbrushside_t *side, *leadside = NULL;
  cplane_t* plane, *clipplane = NULL;
  vec3_t ofs;
  float d1, d2, f;
  float enterfrac = -1;
  float leavefrac = 1;
  bool startout = false;
  vec3_t hitNormal = { 0, 0, 0 };

  for (int i = 0; i < brush->numsides; ++i)
  {
    side = &r_brushsides[brush->firstbrushside+i];
    plane = &r_planes[side->planeidx];

    if (!trace->isPoint)
    {
      if (plane->normal[0] < 0) ofs[0] = trace->maxs[0]; else ofs[0] = trace->mins[0];
      if (plane->normal[1] < 0) ofs[1] = trace->maxs[1]; else ofs[1] = trace->mins[1];
      if (plane->normal[2] < 0) ofs[2] = trace->maxs[2]; else ofs[2] = trace->mins[2];

      if (plane->type < 3)
      {
        d1 = trace->start[plane->type] + ofs[plane->type] - plane->dist;
        d2 = trace->end[plane->type]   + ofs[plane->type] - plane->dist;
      }
      else
      {
        d1 = (trace->start[0] + ofs[0]) * plane->normal[0] +
             (trace->start[1] + ofs[1]) * plane->normal[1] +
             (trace->start[2] + ofs[2]) * plane->normal[2] - plane->dist;
        d2 = (trace->end[0]   + ofs[0]) * plane->normal[0] +
             (trace->end[1]   + ofs[1]) * plane->normal[1] +
             (trace->end[2]   + ofs[2]) * plane->normal[2] - plane->dist;
      }
    }
    else
    { // special point case
      if (plane->type < 3)
      {
        d1 = trace->start[plane->type] - plane->dist;
        d2 = trace->end[plane->type]   - plane->dist;
      }
      else
      {
        d1 = DotProduct(trace->start, plane->normal) - plane->dist;
        d2 = DotProduct(trace->end,   plane->normal) - plane->dist;
      }
    }

    if (d1 > 0) startout = true;

    // if completely in front of face, no intersection
    if (d1 > 0 && d2 >= d1) return;
    if (d1 <= 0 && d2 <= 0) continue;

    // crosses face
    if (d1 > d2)
    { // enter
      f = (d1-DIST_EPSILON) / (d1-d2);
      if (f > enterfrac)
      {
        enterfrac = f;
        clipplane = plane;
        VectorCopy(plane->normal, hitNormal);
        leadside = side;
      }
    }
    else
    { // leave
      f = (d1 /*+ DIST_EPSILON*/) / (d1-d2);
      if (f < leavefrac) leavefrac = f;
    }
  }

  if (!startout) return;    // original point is inside the patch

  if (enterfrac < leavefrac)
  {
    if (leadside && leadside->shader >= 0 && enterfrac < trace->fraction)
    {
      if (enterfrac < 0) enterfrac = 0;
      trace->fraction = enterfrac;
      trace->plane = *clipplane;
      trace->shader = leadside->shader;
      trace->contents = brush->contents;
    }
  }
}

void Q3BSP::TestBoxInBrush(cbrush_t *brush, trace_t *trace)
{
  if (brush->numsides <= 0) return;

  int           i;
  vec3_t        ofs;
  float         d1;
  cbrushside_t *side;
  cplane_t*     plane;

  for (i = 0; i < brush->numsides; ++i)
  {
    side = &r_brushsides[brush->firstbrushside+i];
    plane = r_planes + side->planeidx;

    // general box case

    // push the plane out appropriately for mins/maxs

    // FIXME: use signbits into 8 way lookup for each mins/maxs
    if (plane->normal[0] < 0) ofs[0] = trace->maxs[0]; else ofs[0] = trace->mins[0];
    if (plane->normal[1] < 0) ofs[1] = trace->maxs[1]; else ofs[1] = trace->mins[1];
    if (plane->normal[2] < 0) ofs[2] = trace->maxs[2]; else ofs[2] = trace->mins[2];

    if (plane->type < 3)
    {
      d1 = trace->start[plane->type] + ofs[plane->type] - plane->dist;
    }
    else
    {
      d1 = (trace->start[0] + ofs[0]) * plane->normal[0] +
           (trace->start[1] + ofs[1]) * plane->normal[1] +
           (trace->start[2] + ofs[2]) * plane->normal[2] - plane->dist;
    }

    // if completely in front of face, no intersection
    if (d1 > 0) return;
  }

  // inside this brush
  trace->startSolid = trace->allSolid = true;
  trace->fraction = 0;
  trace->contents = brush->contents;
}

void Q3BSP::TestBoxInPatch(cbrush_t *brush, trace_t *trace)
{
  if (brush->numsides <= 0) return;

  int           i;
  vec3_t        ofs;
  float         d1, maxdist;
  cbrushside_t *side;
  cplane_t  *   plane;

  maxdist = -9999;

  for (i = 0; i < brush->numsides; ++i)
  {
    side = &r_brushsides[brush->firstbrushside+i];
    plane = r_planes + side->planeidx;

    // general box case

    // push the plane out appropriately for mins/maxs

    // FIXME: use signbits into 8 way lookup for each mins/maxs
    if (plane->normal[0] < 0) ofs[0] = trace->maxs[0]; else ofs[0] = trace->mins[0];
    if (plane->normal[1] < 0) ofs[1] = trace->maxs[1]; else ofs[1] = trace->mins[1];
    if (plane->normal[2] < 0) ofs[2] = trace->maxs[2]; else ofs[2] = trace->mins[2];

    if (plane->type < 3)
    {
      d1 = trace->start[plane->type] + ofs[plane->type] - plane->dist;
    }
    else
    {
      d1 = (trace->start[0] + ofs[0]) * plane->normal[0] +
           (trace->start[1] + ofs[1]) * plane->normal[1] +
           (trace->start[2] + ofs[2]) * plane->normal[2] - plane->dist;
    }

    // if completely in front of face, no intersection
    if (d1 > 0) return;

    if (side->shader >= 0 && d1 > maxdist) maxdist = d1;
  }

  // FIXME
  //  if (maxdist < -0.25)
  //    return;   // deep inside the patch

  // inside this patch
  trace->startSolid = trace->allSolid = true;
  trace->fraction = 0;
  trace->contents = brush->contents;
}

int Q3BSP::BoxLeafnums_headnode(vec3_t mins, vec3_t maxs, int *list, int listsize, int headnode, int *topnode)
{
  leaf_list = list;
  leaf_count = 0;
  leaf_maxcount = listsize;
  leaf_mins = mins;
  leaf_maxs = maxs;
  leaf_topnode = -1;

  BoxLeafnums_r(headnode);

  if (topnode) *topnode = leaf_topnode;

  return leaf_count;
}

void Q3BSP::BoxLeafnums_r(int nodenum)
{
  cplane_t  *plane;
  cnode_t   *node;
  int        s;

  while (1)
  {
    if (nodenum < 0)
    {
      if (leaf_count >= leaf_maxcount) return;
      leaf_list[leaf_count++] = -1 - nodenum;
      return;
    }

    node = &r_nodes[nodenum];
    plane = r_planes + node->planeidx;
    s = BoxOnPlaneSide(leaf_mins, leaf_maxs, plane);
//    s = BOX_ON_PLANE_SIDE(leaf_mins, leaf_maxs, plane);
    if (s == 1) nodenum = node->children[0];
    else if (s == 2) nodenum = node->children[1];
    else
    { // go down both
      if (leaf_topnode == -1)
        leaf_topnode = nodenum;
      BoxLeafnums_r(node->children[0]);
      nodenum = node->children[1];
    }
  }
}