source: orxonox.OLD/branches/single_player_map/src/lib/graphics/importer/bsp_manager.cc @ 8864

/*
   orxonox - the future of 3D-vertical-scrollers

   Copyright (C) 2006 orx

   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2, or (at your option)
   any later version.

   ### File Specific:
   main-programmer: bottac@ee.ethz.ch

   Inspired by:
   Rendering Q3 Maps by Morgan McGuire                  http://graphics.cs.brown.edu/games/quake/quake3.html
   Unofficial Quake 3 Map Specs by Kekoa Proudfoot      http://graphics.stanford.edu/~kekoa/q3/

   Collision detection adapted from:
   Quake 3 Collision Detection by Nathan Ostgard        http://www.devmaster.net/articles/quake3collision/
*/


#include "vector.h"
#include "bsp_file.h"
#include "bsp_manager.h"
#include "bsp_tree_leaf.h"
#include "p_node.h"
#include "state.h"
#include "debug.h"
#include "material.h"
#include "camera.h"
#include "vertex_array_model.h"
#include "world_entities/player.h"
#include "world_entities/playable.h"
#include "util/loading/resource_manager.h"
// STL Containers
#include <vector>
#include <deque>
#include "movie_player.h"

#include "world_entity.h"

#include "util/loading/load_param.h"
#include "util/loading/factory.h"

#include "aabb.h"
#include "cr_defs.h"


//CREATE_FACTORY( BspManager, CL_BSP_MODEL);

BspManager::BspManager(WorldEntity* parent)
{

  this->parent = parent;
  /*// open a BSP file
  this->bspFile = new BspFile();
  this->bspFile->scale = 0.4f;
  this->bspFile->read(ResourceManager::getFullName("test.bsp").c_str());
  this->bspFile->build_tree();
  this->root  = this->bspFile->get_root();
  this->alreadyVisible = new bool [this->bspFile->numFaces];
  */

}


/*
BspManager::BspManager(const TiXmlElement* root)
{


  if( root != NULL)
    this->loadParams(root);

  CDEngine::getInstance()->setBSPModel(this);
} */

void BspManager::load(const char* fileName, float scale)
{
  // open a BSP file
  this->bspFile = new BspFile();
  this->bspFile->scale =  scale;
  this->bspFile->read(ResourceManager::getFullName(fileName).c_str());
  this->bspFile->build_tree();
  this->root  = this->bspFile->get_root();
  this->alreadyVisible = new bool [this->bspFile->numFaces];

  this->outputFraction = 1.0f;
}
/*
BspManager::BspManager(const char* fileName, float scale)
{
  // open a BSP file
  this->bspFile = new BspFile();
  this->bspFile->scale =  scale;
  this->bspFile->read(fileName);
  this->bspFile->build_tree();
  this->root  = this->bspFile->get_root();
  this->alreadyVisible = new bool [this->bspFile->numFaces];

  CDEngine::getInstance()->setBSPModel(this);
}
*/

const void BspManager::tick(float time)
{

  if(!this->bspFile->MovieMaterials.empty()) {
    ::std::vector<MoviePlayer *>::iterator it = this->bspFile->MovieMaterials.begin() ;
    while(it != this->bspFile->MovieMaterials.end()) {
      (*it)->tick(time);
      it++;
    }
    //this->bspFile->MovieMaterials.front()->tick(time );


  }

}
const void BspManager::draw()
{

  /*
  this->drawDebugCube(&this->out);
  this->out1 = this->out;
  this->out2 = this->out;
  if(this->collPlane != NULL) {
    this->out1.x += this->collPlane->x*5.0;
    this->out1.y += this->collPlane->y*5.0;
    this->out1.z += this->collPlane->z*5.0;

    this->out2.x += this->collPlane->x*10.0;
    this->out2.y += this->collPlane->y*10.0;
    this->out2.z += this->collPlane->z*10.0;
  }
  this->drawDebugCube(&this->out1);
  this->drawDebugCube(&this->out2);

  */


  // Draw Debug Terrain
  /*
  this->bspFile->Materials[0]->select();
  for(int i = 0; i <  this->bspFile->numPatches ; i++)
        {
                this->bspFile->VertexArrayModels[i]->draw();

        }
  */



  // erase alreadyVisible
  for(int i = 0; i < this->bspFile->numFaces; i++) this->alreadyVisible[i] = false;
  float tmp = 0;
  //this->opal.clear();
  //this->trasparent.clear();
  // Find all visible faces...

  this->cam = State::getCamera()->getAbsCoor() ;
  //this->ship = State::getCameraTargetNode()->getAbsCoor();





  this->viewDir=    State::getCamera()->getAbsDirX();
  float d = (cam.x*viewDir.x + cam.y*viewDir.y + cam.z * viewDir.z);

  BspTreeNode*  ActLeaf = this->getLeaf(this->bspFile->root, &ship);
  int viscluster = -1;
  viscluster =((leaf*)(this->bspFile->leaves))[ ActLeaf->leafIndex].cluster; // get the players cluster (viscluster)




  // this->checkCollision(this->root, &this->cam);   //!< Test Collision Detection


  this->outputStartsOut = true;
  this->outputAllSolid = false;
  this->outputFraction = 1.0f;

  if ( viscluster < 0  || ((int *)(this->bspFile->header))[35] == 0 )  //!< if (sizeof(Visdata) == 0)
  {



    // Iterate through all Leafs
    for(int i = 0; i <  this->bspFile->numLeafs   ; i++ )
    {
      // cluster =  (this->bspFile->leaves)[i].cluster;
      leaf& curLeaf = (this->bspFile->leaves)[i];
      if(curLeaf.cluster<0) continue;

      /** Do Frustum culling and draw 'em all **/

      Vector dir = State::getCameraNode()->getAbsDirX();

      float dist =  dir.x*this->cam.x +dir.y*this->cam.y +dir.z*this->cam.z;
      //if(dist < 0) dist = -dist;
      const float dMins = dir.x*(float)curLeaf.mins[0] +dir.y*(float)curLeaf.mins[1] +dir.z*(float)curLeaf.mins[2] - dist ;
      const float dMaxs = dir.x*(float)curLeaf.maxs[0] +dir.y*(float)curLeaf.maxs[1] +dir.z*(float)curLeaf.maxs[2] - dist ;

      if(dMins < -300.0 && dMaxs < -300.0) {
        continue;
      }
      if( (this->cam - Vector(curLeaf.mins[0],curLeaf.mins[1], curLeaf.mins[2])).len() > 2000  && (this->cam - Vector(curLeaf.maxs[0],curLeaf.maxs[1], curLeaf.maxs[2])).len() > 2000) {
        continue;
      }


      // Iterate through all faces
      for (int j = 0; j < curLeaf.n_leaffaces ; ++j) {
        const int g = (j +  curLeaf.leafface);
        const int f = ((int *)this->bspFile->leafFaces)[g];
        if (f >=0 && !this->isAlreadyVisible(f)) {
          this->alreadyVisible[f] = true;
          addFace(f); // "visibleFaces.append(f)"
        }
      }




    } //for
  } else {


    unsigned int v;
    unsigned char  visSet;

    // Iterate through all Leafs

    for(int i = 0; i <  this->bspFile->numLeafs   ; ++i ) {
      leaf& camLeaf =  (this->bspFile->leaves)[ActLeaf->leafIndex] ;
      leaf& curLeaf =  (this->bspFile->leaves)[i] ;
      int& cluster =  curLeaf.cluster;

      if(cluster < 0) continue;
      v = ((viscluster *  ( ((int *)this->bspFile->visData)[1]) ) + (cluster / 8));
      visSet =((char*) (this->bspFile->visData))[v + 8];

      // gets bit of visSet
      if( ((visSet) & (1 << (cluster &  7))) != 0 ) {

        // Frustum culling

        Vector dir;
        dir.x = State::getCameraNode()->getAbsDirX().x;
        dir.y =  State::getCameraNode()->getAbsDirX().y;
        dir.z =  State::getCameraNode()->getAbsDirX().z;
        const float dist =  dir.x*this->cam.x +dir.y*this->cam.y +dir.z*this->cam.z;
        //if(dist < 0) dist = -dist;
        const float dMins = dir.x*(float)curLeaf.mins[0] +dir.y*(float)curLeaf.mins[1] +dir.z*(float)curLeaf.mins[2] - dist;
        const float dMaxs = dir.x*(float)curLeaf.maxs[0] +dir.y*(float)curLeaf.maxs[1] +dir.z*(float)curLeaf.maxs[2] - dist;

        if(dMins < -50.0 && dMaxs < -  50.0) {
          continue;
        }


        // Iterate through all faces
        for (int j = 0; j < curLeaf.n_leaffaces ; ++j) {
          const int g = (j +  curLeaf.leafface);
          const int f = ((int *)this->bspFile->leafFaces)[g];

          if (!this->isAlreadyVisible(f) && f>=0) {
            this->addFace(f);
            this->alreadyVisible[f] = true;
          }

        }

      }// if

    }//for

  }//else

  while(!this->opal.empty()) {
    this->draw_face(this->opal.front());
    this->opal.pop_front();
  }
  while(!this->trasparent.empty()) {
    this->draw_face(this->trasparent.back());
    this->trasparent.pop_back();
  }
  //glEnable(GL_TEXTURE_2D);
  glActiveTextureARB(GL_TEXTURE1_ARB);
  glBindTexture(GL_TEXTURE_2D, this->bspFile->whiteLightMap);



}//draw



void BspManager::draw_face(int curface)
{
  face& curFace =  (this->bspFile->faces)[curface];
  const BspVertex* curVertex = (BspVertex *) this->bspFile->vertice;
  int stride = sizeof(BspVertex);  // sizeof(Vertex)
  int offset    = curFace.vertex;
  if (curFace.effect != -1) return;
  // PRINTF(0)("BSP Manager: ");
  // PRINTF(0)("BSP Manager: type: %i  \n", curFace.texture);

  //  if(  curFace.texture < 0 ) return;
  if(curFace.type == 2) {
    this->draw_patch( &curFace);
    return;
  }
  // if(curFace.type != 1) return;
  if((char*)(this->bspFile->textures)[curFace.texture*72]== 0) return;

  if(this->lastTex != curFace.texture) {
    if(this->bspFile->Materials[curFace.texture].animated) {
      // glBlendFunc(GL_ZERO,GL_ONE);



      if(this->bspFile->Materials[curFace.texture].aviMat->getStatus() == 2) this->bspFile->Materials[curFace.texture].aviMat->start(0);
      //this->bspFile->Materials[curFace.texture].aviMat->tick(0.005);
      int n =  this->bspFile->Materials[curFace.texture].aviMat->getTexture();
      glActiveTextureARB(GL_TEXTURE0_ARB);
      glBindTexture(GL_TEXTURE_2D, n );
      this->lastTex = curFace.texture;

    } else {
      this->bspFile->Materials[curFace.texture].mat->select();
      this->lastTex = curFace.texture;
    }
  }

  if(curFace.lm_index < 0) {
    glBlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);
    glActiveTextureARB(GL_TEXTURE1_ARB);
    glBindTexture(GL_TEXTURE_2D, this->bspFile->whiteLightMap );
    glEnable(GL_TEXTURE_2D);
  } else {
    // glEnable(GL_BLEND);
    //glBlendFunc(GL_ONE, GL_ONE_MINUS_SRC_ALPHA);
    glBlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);
    glActiveTextureARB(GL_TEXTURE1_ARB);
    glBindTexture(GL_TEXTURE_2D, this->bspFile->glLightMapTextures[curFace.lm_index]);
    glEnable(GL_TEXTURE_2D);
    //  glDisable(GL_BLEND);
  }

  glBlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);

  // glColor4f(3.0,3.0,3.0,1.0);
  glEnableClientState(GL_VERTEX_ARRAY );
  glEnableClientState(GL_TEXTURE_COORD_ARRAY );
  glEnableClientState(GL_NORMAL_ARRAY );
  //  glEnableClientState(GL_COLOR_ARRAY);


  glVertexPointer(3, GL_FLOAT, stride, &(curVertex[offset].position[0]));

  glClientActiveTextureARB(GL_TEXTURE0_ARB);
  glTexCoordPointer(2, GL_FLOAT, stride, &(curVertex[offset].texcoord[0]));
  //glEnableClientState(GL_TEXTURE_COORD_ARRAY);

  glClientActiveTextureARB(GL_TEXTURE1_ARB);
  glTexCoordPointer(2, GL_FLOAT, stride, &(curVertex[offset].texcoord[1]));
  //glEnableClientState(GL_TEXTURE_COORD_ARRAY);


  glNormalPointer( GL_FLOAT, stride, &(curVertex[offset].normal[0]));
  // glColorPointer(4, GL_BYTE, stride, &(curVertex[offset].color[0]));
  glDrawElements(GL_TRIANGLES, curFace.n_meshverts,
                 GL_UNSIGNED_INT, &(((meshvert *)this->bspFile->meshverts) [curFace.meshvert]));

  glDisableClientState(GL_TEXTURE0_ARB);
  glDisableClientState(GL_TEXTURE1_ARB);
  glDisableClientState(GL_VERTEX_ARRAY );
  glDisableClientState(GL_TEXTURE_COORD_ARRAY );
  glDisableClientState(GL_NORMAL_ARRAY );
  // glDisableClientState(GL_COLOR_ARRAY);

}


void BspManager::draw_debug_face(int curface)
{
  face& curFace =  (this->bspFile->faces)[curface];
  const BspVertex* curVertex = (BspVertex *) this->bspFile->vertice;
  int stride = 44;  // sizeof(Vertex)
  int offset    = curFace.vertex;

  // PRINTF(0)("BSP Manager: ");
  // PRINTF(0)("BSP Manager: type: %i  \n", curFace.texture);

  //  if(  curFace.texture < 0 ) return;
  if(curFace.type == 2) {
    this->draw_patch( &curFace);
    return;
  }
  if(curFace.type == 3) return;
  // if(this->bspFile->Materials[curFace.texture] != NULL)

  this->bspFile->Materials[2].mat->select();
  this->lastTex = 2;

  glEnableClientState(GL_VERTEX_ARRAY );
  glEnableClientState(GL_TEXTURE_COORD_ARRAY );
  glEnableClientState(GL_NORMAL_ARRAY );
  //glEnableClientState(GL_COLOR_ARRAY);
  // glEnableClientState(GL_VERTEX_ARRAY );
  glClientActiveTextureARB(GL_TEXTURE0_ARB);
  glVertexPointer(3, GL_FLOAT, stride, &(curVertex[offset].position[0]));
  glEnableClientState(GL_TEXTURE_COORD_ARRAY);
  // glClientActiveTextureARB(GL_TEXTURE0_ARB);
  glClientActiveTextureARB(GL_TEXTURE1_ARB);
  glTexCoordPointer(2, GL_FLOAT, stride, &(curVertex[offset].texcoord[0]));
  glEnableClientState(GL_TEXTURE_COORD_ARRAY);
  // glClientActiveTextureARB(GL_TEXTURE1_ARB);
  // glTexCoordPointer(2, GL_FLOAT, stride, &(curVertex[offset].texcoord[1]));
  //glEnableClientState(GL_NORMAL_ARRAY );

  glNormalPointer( GL_FLOAT, stride, &(curVertex[offset].normal[0]));
  //  glColorPointer(4, GL_BYTE, stride, &(curVertex[offset].color[0]));
  glDrawElements(GL_TRIANGLES, curFace.n_meshverts,
                 GL_UNSIGNED_INT, &(((meshvert *)this->bspFile->meshverts) [curFace.meshvert]));

}

void BspManager::draw_patch(face* Face)
{
  if(this->lastTex != Face->texture) {
    this->bspFile->Materials[Face->texture].mat->select();
    this->lastTex = Face->texture;
  }
  if (Face->effect != -1) return;


  if(Face->lm_index < 0) {
    glActiveTextureARB(GL_TEXTURE1_ARB);
    glBindTexture(GL_TEXTURE_2D, this->bspFile->whiteLightMap);
    glEnable(GL_TEXTURE_2D);
  } else {
    glActiveTextureARB(GL_TEXTURE1_ARB);
    glBindTexture(GL_TEXTURE_2D, this->bspFile->glLightMapTextures[Face->lm_index]);
    glEnable(GL_TEXTURE_2D);
  }
  //glColor4f(3.0,3.0,3.0,1.0);

  glBlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);
  glEnable( GL_AUTO_NORMAL);
  glEnableClientState(GL_VERTEX_ARRAY );
  glEnableClientState(GL_TEXTURE_COORD_ARRAY );
  for(int i = Face->n_meshverts -1; i >=0   ; i--) {
    //glFrontFace(GL_CW);
    //PRINTF(0)("BSP Manager: Face->size[0]: %i . \n", Face->size[0]);


    //glEnableClientState(GL_NORMAL_ARRAY );

    glVertexPointer(3, GL_FLOAT,44, &((((BspVertex*)(this->bspFile->patchVertice))[8*8*(Face->meshvert+i)]).position[0]));


    glClientActiveTextureARB(GL_TEXTURE0_ARB);
    glEnableClientState(GL_TEXTURE_COORD_ARRAY);
    glTexCoordPointer(2, GL_FLOAT, 44, &((((BspVertex*)(this->bspFile->patchVertice))[8*8*(Face->meshvert+i)]).texcoord[0][0]));



    glClientActiveTextureARB(GL_TEXTURE1_ARB);
    glTexCoordPointer(2, GL_FLOAT, 44, &((((BspVertex*)(this->bspFile->patchVertice))[8*8*(Face->meshvert+i)]).texcoord[1][0]));
    //glEnableClientState(GL_TEXTURE_COORD_ARRAY);


    //  glNormalPointer( GL_FLOAT, 44,&((((BspVertex*)(this->bspFile->patchVertice))[8*8*(Face->meshvert+i)]).normal[0]) );




    for(int row=6; row>=0; --row) {
      glDrawElements(GL_TRIANGLE_STRIP, 2*(8), GL_UNSIGNED_INT,
                     & (     (((GLuint*)  (this->bspFile->patchIndexes))[7*8*2*(Face->meshvert+i)+ row*2*8]  ))  );
    }

    //glFrontFace(GL_CCW);
  }
  glDisableClientState(GL_TEXTURE0_ARB);
  glDisableClientState(GL_TEXTURE1_ARB);
  glDisable(GL_AUTO_NORMAL);
  glDisableClientState(GL_VERTEX_ARRAY );
  glDisableClientState(GL_TEXTURE_COORD_ARRAY );


}

bool BspManager::isAlreadyVisible(int Face)
{
  return this->alreadyVisible[Face];
}


BspTreeNode*  BspManager::getLeaf(BspTreeNode* node, Vector* cam)
{
  float dist = 0;
  while(!(node->isLeaf)) {
    dist = (node->plane.x * this->cam.x + node->plane.y*this->cam.y + node->plane.z*this->cam.z) - node->d;
    if(dist >= 0.0f) {
      node = node->left;
    } else {
      node = node->right;
    }
  }
  return  node;
}

void BspManager::checkBrushRay(brush* curBrush)
{
  float EPSILON = 0.000001;
  float startDistance;
  float endDistance;

  float startFraction = -1.0f;
  float endFraction = 1.0f;
  bool startsOut = false;
  bool endsOut = false;

  Vector inputStart = State::getCameraTargetNode()->getLastAbsCoor();
  Vector inputEnd   = State::getCameraTargetNode()->getAbsCoor();

  for (int i = 0; i < curBrush->n_brushsides; i++) {
    brushside& curBrushSide =   this->bspFile->brushSides[curBrush->brushside + i]   ;
    plane& curPlane  =   this->bspFile->planes[curBrushSide.plane] ;

    startDistance = inputStart.x * curPlane.x + inputStart.y * curPlane.y+ inputStart.z * curPlane.z - curPlane.d;
    endDistance = inputEnd.x * curPlane.x +inputEnd.y * curPlane.y +inputEnd.z * curPlane.z -curPlane.d;

    if (startDistance > 0)
      startsOut = true;
    if (endDistance > 0)
      endsOut = true;

    // make sure the trace isn't completely on one side of the brush
    if (startDistance > 0 && endDistance > 0) {   // both are in front of the plane, its outside of this brush
      return;
    }
    if (startDistance <= 0 && endDistance <= 0) {   // both are behind this plane, it will get clipped by another one
      continue;
    }

    // MMM... BEEFY
    if (startDistance > endDistance) {   // line is entering into the brush
      float fraction = (startDistance - EPSILON) / (startDistance - endDistance);  // *
      if (fraction > startFraction)
        startFraction = fraction;
      // don't store plane
      // this->collPlane = &curPlane;

    } else {   // line is leaving the brush
      float fraction = (startDistance + EPSILON) / (startDistance - endDistance);  // *
      if (fraction < endFraction)
        endFraction = fraction;
      // don't store plane
      //this->collPlane = & curPlane;

    }

  }
  if (startsOut == false) {
    this->outputStartsOut = false;
    if (endsOut == false)
      this->outputAllSolid = true;
    return;
  }

  if (startFraction < endFraction) {
    if (startFraction > -1.0f && startFraction < outputFraction) {
      if (startFraction < 0)
        startFraction = 0;
      this->outputFraction = startFraction;
    }
  }

}

void BspManager::checkBrushRayN(brush* curBrush)
{
  float EPSILON = 0.000001;
  float startDistance;
  float endDistance;

  float startFraction = -1.0f;
  float endFraction = 1.0f;
  bool  startsOut = false;
  bool  endsOut = false;

  // Vector inputStart = State::getCameraTargetNode()->getLastAbsCoor();
  // Vector inputEnd   = State::getCameraTargetNode()->getAbsCoor();

  for (int i = 0; i < curBrush->n_brushsides; i++) {
    brushside& curBrushSide =   this->bspFile->brushSides[curBrush->brushside + i]   ;
    plane& curPlane  =   this->bspFile->planes[curBrushSide.plane] ;

    startDistance = inputStart.x * curPlane.x + inputStart.y * curPlane.y+ inputStart.z * curPlane.z - curPlane.d;
    endDistance = inputEnd.x * curPlane.x +inputEnd.y * curPlane.y +inputEnd.z * curPlane.z -curPlane.d;

    if (startDistance > 0)
      startsOut = true;
    if (endDistance > 0)
      endsOut = true;

    // make sure the trace isn't completely on one side of the brush
    if (startDistance > 0 && endDistance > 0) {   // both are in front of the plane, its outside of this brush
      return;
    }
    if (startDistance <= 0 && endDistance <= 0) {   // both are behind this plane, it will get clipped by another one
      continue;
    }

    // MMM... BEEFY
    if (startDistance > endDistance) {   // line is entering into the brush
      float fraction = (startDistance - EPSILON) / (startDistance - endDistance);  // *
      if (fraction > startFraction)
        startFraction = fraction;
      // store plane
      this->collPlane = &curPlane;

    } else {   // line is leaving the brush
      float fraction = (startDistance + EPSILON) / (startDistance - endDistance);  // *
      if (fraction < endFraction)
        endFraction = fraction;
      // store plane
      this->collPlane = & curPlane;

    }

  }
  if (startsOut == false) {
    this->outputStartsOut = false;
    if (endsOut == false)
      this->outputAllSolid = true;
    return;
  }

  if (startFraction < endFraction) {
    if (startFraction > -1.0f && startFraction < outputFraction) {
      if (startFraction < 0)
        startFraction = 0;
      this->outputFraction = startFraction;
    }
  }

}

void BspManager::checkBrushRayN(brush* curBrush, Vector& inputStart, Vector& inputEnd)
{
  float EPSILON = 0.000001;
  float startDistance;
  float endDistance;

  float startFraction = -1.0f;
  float endFraction = 1.0f;
  bool  startsOut = false;
  bool  endsOut = false;

  //Vector inputStart = State::getCameraTargetNode()->getLastAbsCoor();
  //Vector inputEnd   = State::getCameraTargetNode()->getAbsCoor();

  for (int i = 0; i < curBrush->n_brushsides; i++) {
    brushside& curBrushSide =   this->bspFile->brushSides[curBrush->brushside + i]   ;
    plane& curPlane  =   this->bspFile->planes[curBrushSide.plane] ;

    startDistance = inputStart.x * curPlane.x + inputStart.y * curPlane.y+ inputStart.z * curPlane.z - curPlane.d;
    endDistance = inputEnd.x * curPlane.x +inputEnd.y * curPlane.y +inputEnd.z * curPlane.z -curPlane.d;

    if (startDistance > 0)
      startsOut = true;
    if (endDistance > 0)
      endsOut = true;

    // make sure the trace isn't completely on one side of the brush
    if (startDistance > 0 && endDistance > 0) {   // both are in front of the plane, its outside of this brush
      return;
    }
    if (startDistance <= 0 && endDistance <= 0) {   // both are behind this plane, it will get clipped by another one
      continue;
    }

    // MMM... BEEFY
    if (startDistance > endDistance) {   // line is entering into the brush
      float fraction = (startDistance - EPSILON) / (startDistance - endDistance);  // *
      if (fraction > startFraction)
        startFraction = fraction;
      // store plane
      this->collPlane = &curPlane;

    } else {   // line is leaving the brush
      float fraction = (startDistance + EPSILON) / (startDistance - endDistance);  // *
      if (fraction < endFraction)
        endFraction = fraction;
      // store plane
      this->collPlane = & curPlane;

    }

  }
  if (startsOut == false) {
    this->outputStartsOut = false;
    if (endsOut == false)
      this->outputAllSolid = true;
    return;
  }

  if (startFraction < endFraction) {
    if (startFraction > -1.0f && startFraction < outputFraction) {
      if (startFraction < 0)
        startFraction = 0;
      this->outputFraction = startFraction;
    }
  }

}


void BspManager::checkCollisionRay(BspTreeNode* node, float startFraction, float endFraction, Vector* start, Vector* end)
{


  float EPSILON = 0.000001;
  float  endDistance = (end)->x * (node->plane.x) +(end)->y * (node->plane.y) +(end)->z * (node->plane.z)  - node->d;
  float  startDistance = (start)->x * (node->plane.x)+ (start)->y * (node->plane.y)+ (start)->z * (node->plane.z)- node->d;


  if(node->isLeaf) {
    leaf& curLeaf = this->bspFile->leaves[node->leafIndex];
    for (int i = 0; i <  curLeaf.n_leafbrushes ; i++) {
      brush& curBrush = this->bspFile->brushes[((int*)(this->bspFile->leafBrushes))[curLeaf.leafbrush_first+i]];
      //object *brush = &BSP.brushes[BSP.leafBrushes[leaf->firstLeafBrush + i]];
      if (curBrush.n_brushsides > 0   &&
          ((((BspTexture*)(this->bspFile->textures))[curBrush.texture]).contents & 1))
        // CheckBrush( brush );
        this->checkBrushRay(&curBrush);
      if(curBrush.n_brushsides <=0) this->outputAllSolid = true;
    }
    return;
  }


  if (startDistance >= 0 && endDistance >= 0)     // A
  {   // both points are in front of the plane
    // so check the front child
    this->checkCollisionRay(node->left,0,0,start,end);
  } else if (startDistance < 0 && endDistance < 0)  // B
  {   // both points are behind the plane
    // so check the back child
    this->checkCollisionRay(node->right,0,0,start,end);
  } else                                            // C
  {   // the line spans the splitting plane
    int side;
    float fraction1, fraction2, middleFraction;
    Vector middle;

    // STEP 1: split the segment into two
    if (startDistance < endDistance) {
      side = 1; // back
      float inverseDistance = 1.0f / (startDistance - endDistance);
      fraction1 = (startDistance + EPSILON) * inverseDistance;
      fraction2 = (startDistance + EPSILON) * inverseDistance;
    } else if (endDistance < startDistance) {
      side = 0; // front(start)->x * (node->plane.x)+
      float inverseDistance = 1.0f / (startDistance - endDistance);
      fraction1 = (startDistance + EPSILON) * inverseDistance;
      fraction2 = (startDistance - EPSILON) * inverseDistance;
    } else {
      side = 0; // front
      fraction1 = 1.0f;
      fraction2 = 0.0f;
    }

    // STEP 2: make sure the numbers are valid
    if (fraction1 < 0.0f) fraction1 = 0.0f;
    else if (fraction1 > 1.0f) fraction1 = 1.0f;
    if (fraction2 < 0.0f) fraction2 = 0.0f;
    else if (fraction2 > 1.0f) fraction2 = 1.0f;

    // STEP 3: calculate the middle point for the first side
    middleFraction = startFraction +
                     (endFraction - startFraction) * fraction1;

    middle.x = start->x + fraction1 * (end->x - start->x);
    middle.y = start->y + fraction1 * (end->y - start->y);
    middle.z = start->z + fraction1 * (end->z - start->z);

    // STEP 4: check the first side
    //CheckNode( node->children[side], startFraction, middleFraction, start, middle );
    if(side == 0) this->checkCollisionRay(node->left,startFraction, middleFraction, start, &middle );

    else this->checkCollisionRay(node->right,startFraction, middleFraction,
                                   start, &middle );

    // STEP 5: calculate the middle point for the second side
    middleFraction = startFraction +
                     (endFraction - startFraction) * fraction2;

    middle.x = start->x + fraction2 * (end->x - start->x);
    middle.y = start->y + fraction2 * (end->y - start->y);
    middle.z = start->z + fraction2 * (end->z - start->z);

    // STEP 6: check the second side
    if(side == 1)this->checkCollisionRay(node->left,middleFraction, endFraction, &middle, end);

    else this->checkCollisionRay(node->right,middleFraction, endFraction,&middle, end );


  }

}



void BspManager::checkCollisionRayN(BspTreeNode* node, float startFraction, float endFraction, Vector* start, Vector* end)
{


  float EPSILON = 0.000001;

  float endDistance = end->dot(node->plane) - node->d;
  float startDistance = start->dot(node->plane) - node->d;


  if( node->isLeaf) {
    leaf& curLeaf = this->bspFile->leaves[node->leafIndex];
    for (int i = 0; i <  curLeaf.n_leafbrushes ; i++) {
      brush& curBrush = this->bspFile->brushes[((int*)(this->bspFile->leafBrushes))[curLeaf.leafbrush_first+i]];
      //object *brush = &BSP.brushes[BSP.leafBrushes[leaf->firstLeafBrush + i]];
      if (curBrush.n_brushsides > 0   &&
          ((((BspTexture*)(this->bspFile->textures))[curBrush.texture]).contents & 1))
        // CheckBrush( brush );
        this->checkBrushRayN(&curBrush);
      if(curBrush.n_brushsides <=0) this->outputAllSolid = true;
    }

    return;
  }


  if (startDistance >= 0 && endDistance >= 0)     // A
  {   // both points are in front of the plane
    // so check the front child
    this->checkCollisionRayN(node->left,0,0,start,end);
  } else if (startDistance < 0 && endDistance < 0)  // B
  {   // both points are behind the plane
    // so check the back child
    this->checkCollisionRayN(node->right,0,0,start,end);
  } else                                            // C
  {   // the line spans the splitting plane
    int side;
    float fraction1, fraction2, middleFraction;
    Vector middle;

    // STEP 1: split the segment into two
    if (startDistance < endDistance) {
      side = 1; // back
      float inverseDistance = 1.0f / (startDistance - endDistance);
      fraction1 = (startDistance + EPSILON) * inverseDistance;
      fraction2 = (startDistance + EPSILON) * inverseDistance;
    } else if (endDistance < startDistance) {
      side = 0; // front(start)->x * (node->plane.x)+
      float inverseDistance = 1.0f / (startDistance - endDistance);
      fraction1 = (startDistance + EPSILON) * inverseDistance;
      fraction2 = (startDistance - EPSILON) * inverseDistance;
    } else {
      side = 0; // front
      fraction1 = 1.0f;
      fraction2 = 0.0f;
    }

    // STEP 2: make sure the numbers are valid
    if (fraction1 < 0.0f) fraction1 = 0.0f;
    else if (fraction1 > 1.0f) fraction1 = 1.0f;
    if (fraction2 < 0.0f) fraction2 = 0.0f;
    else if (fraction2 > 1.0f) fraction2 = 1.0f;

    // STEP 3: calculate the middle point for the first side
    middleFraction = startFraction + (endFraction - startFraction) * fraction1;
    middle = (*start) + ((*end) - (*start)) * fraction1;


    // STEP 4: check the first side
    //CheckNode( node->children[side], startFraction, middleFraction, start, middle );
    if(side == 0) this->checkCollisionRayN(node->left,startFraction, middleFraction, start, &middle );

    else this->checkCollisionRayN(node->right,startFraction, middleFraction,
                                    start, &middle );

    // STEP 5: calculate the middle point for the second side
    middleFraction = startFraction + (endFraction - startFraction) * fraction2;
    middle = (*start) + ((*end) - (*start)) * fraction2;

    // STEP 6: check the second side
    if(side == 1)this->checkCollisionRayN(node->left,middleFraction, endFraction, &middle, end);

    else this->checkCollisionRayN(node->right,middleFraction, endFraction,&middle, end );


  }

}

float BspManager::checkPatchAltitude(BspTreeNode* node)
{
  leaf& curLeaf = this->bspFile->leaves[node->leafIndex];
  for(int i = 0; i < curLeaf.n_leaffaces ; i++) {
  }
  return 10.0f;
}

void BspManager::checkCollisionBox(void)
{
}
;

void BspManager::TraceBox( Vector& inputStart, Vector& inputEnd,
                           Vector& inputMins, Vector& inputMaxs )
{
  if (inputMins.x == 0 && inputMins.y == 0 && inputMins.z == 0 &&
      inputMaxs.x == 0 && inputMaxs.y == 0 && inputMaxs.z == 0) {   // the user called TraceBox, but this is actually a ray
    //!> FIXME TraceRay( inputStart, inputEnd );
  } else {   // setup for a box
    //traceType = TT_BOX;
    this->traceMins = inputMins;
    this->traceMaxs = inputMaxs;
    this->traceExtents.x = -traceMins.x > traceMaxs.x ?
                           -traceMins.x : traceMaxs.x;
    this->traceExtents.y = -traceMins.y > traceMaxs.y ?
                           -traceMins.y : traceMaxs.y;
    this->traceExtents.z = -traceMins.z > traceMaxs.z ?
                           -traceMins.z : traceMaxs.z;
    //!> FIXME Trace( inputStart, inputEnd );
  }
}

void BspManager::checkCollision(WorldEntity* worldEntity)
{

  // Init  Collision Detection
  this->outputStartsOut = true;
  this->outputAllSolid = false;
  this->outputFraction = 1.0f;

  // Retrieve Bounding box
  AABB* box = worldEntity->getModelAABB();


  Vector forwardDir = worldEntity->getAbsDirX();


  Vector upDir = worldEntity->getAbsDirY();
  upDir.x = 0.0;
  upDir.y = 1.0;
  upDir.z = 0.0;
  Vector dest;


  Vector position = worldEntity->getAbsCoor();       //+ upDir*10.0f ;
  dest = worldEntity->getAbsCoor() - upDir*40.0f; //
  Vector out = dest;


  bool collision = false;
  Vector position1 = position;
  Vector position2 = position + Vector(0.0,1.0,0.0);
  Vector dest1 = position + forwardDir*4.0f;
  Vector dest2 = position2 + forwardDir;
  dest = position - Vector(0.0, 40.0,0.0);
  Vector out1;
  Vector out2;



  float height = 40;


  if( box != NULL)
  {
    position = worldEntity->getAbsCoor() +  box->center; // + box->axis[1] * box->halfLength[1];
    dest     = worldEntity->getAbsCoor() +  box->center - box->axis[1] * box->halfLength[1] * 40.0;

    position1 = worldEntity->getAbsCoor() +  box->center + box->axis[0] * box->halfLength[0] * 2.0f;
    dest1     = worldEntity->getAbsCoor() +  box->center - box->axis[0] * box->halfLength[0] *2.0f;


    position2 = worldEntity->getAbsCoor() +  box->center + box->axis[2] * box->halfLength[2] * 2.0f;
    dest2     = worldEntity->getAbsCoor() +  box->center - box->axis[2] * box->halfLength[2] * 2.0f;

  }
  else
  {

  }



  //
  this->inputStart =  position;
  this->inputEnd =   dest;
  this->checkCollisionRayN(this->root,0.0f,1.0f, &position, &dest );


  //
  if(!this->outputStartsOut ) {
    this->collPlane = new plane;
    this->collPlane->x = 0.0f;
    this->collPlane->y = 0.0f;
    this->collPlane->z = 0.0f;
    collision = true;
  } else {

    if( this->outputFraction == 1.0f) {
      if(this->outputAllSolid ) {
        this->collPlane = new plane;
        this->collPlane->x = 0.0f;
        this->collPlane->y = 0.0f;
        this->collPlane->z = 0.0f;
        collision = true;
      } else
        collision = false;


        out = dest;

    } else {
      collision = true;
      out.x = position.x + (dest.x -position.x) * this->outputFraction;
      out.y = position.y + (dest.y -position.y) * this->outputFraction;
      out.z = position.z + (dest.z -position.z) * this->outputFraction;

      Vector out3 = out + Vector(height*this->collPlane->x,height*this->collPlane->y,height*this->collPlane->z);
      this->out = out;
    }


  }

  plane* testPlane = this->collPlane;


  // 2nd Collision Detection
  this->outputStartsOut = true;
  this->outputAllSolid = false;
  this->outputFraction = 1.0f;
  this->inputStart =  position1;
  this->inputEnd =   dest1;
  this->checkCollisionRayN(this->root,0.0f,1.0f, &position1, &dest1 );
  out.x = this->outputFraction;
  //out.z = this->outputFraction;


    // 3rd Collision Detection
  this->outputStartsOut = true;
  this->outputAllSolid = false;
  this->outputFraction = 1.0f;
  this->inputStart =  position2;
  this->inputEnd =   dest2;
  this->checkCollisionRayN(this->root,0.0f,1.0f, &position2, &dest2 );
  //out.x = this->outputFraction;
  out.z = this->outputFraction;


  /*
  This is how you would calculate the Coordinates where worldEntity Collided with the BSP world.
  out.x = position1.x + (dest.x -position1.x) * this->outputFraction;
  out.z = position1.z + (dest.z -position1.z) * this->outputFraction;
  */


  // Return the normal here: Normal's stored in this->collPlane;
  if( collision)
  {
    PRINTF(5)("We got a collision!! Are you sure: outputFraction = %f\n", this->outputFraction);
    worldEntity->registerCollision(COLLISION_TYPE_AXIS_Y, this->parent, worldEntity, Vector(testPlane->x, testPlane->y, testPlane->z), out);
  }
  else  worldEntity->registerCollision(COLLISION_TYPE_AXIS_Y, this->parent, worldEntity, Vector(0.0, 2.0, 0.0), dest);

}


void  BspManager::checkCollision(BspTreeNode* node, Vector* cam)
{
  Vector next = this->cam;
  next.x =   (State::getCameraTargetNode()->getLastAbsCoor()).x ;
  next.y =   (State::getCameraTargetNode()->getLastAbsCoor()).y ;
  next.z =   (State::getCameraTargetNode()->getLastAbsCoor()).z ;

  float dist = 0;
  if(!(node->isLeaf)) {
    dist = (node->plane.x * this->cam.x + node->plane.y*this->cam.y + node->plane.z*this->cam.z) - node->d;
    if(dist > 4.0f) {
      checkCollision(node->left,cam);
      return;
    }
    if(dist < -4.0f) {
      checkCollision(node->right,cam);
      return;
    }
    if(dist<=4.0f && dist >= -4.0f) {
      checkCollision(node->left,cam);
      checkCollision(node->right,cam);
      return;
    }
    return;
  } else {

    leaf& camLeaf =  ((leaf *)(this->bspFile->leaves))[(node->leafIndex ) ];

    if (camLeaf.cluster < 0) {
      this->drawDebugCube(&this->cam);
      this->drawDebugCube(&next);
      // State::getPlayer()->getPlayable()->setRelCoor(-100,-100,-100);
      //State::getPlayer()->getPlayable()->collidesWith(NULL, State::getCameraTargetNode()->getLastAbsCoor());
    }


    /*
        for(int i = 0; i < camLeaf.n_leafbrushes && i < 10; i++ )
        {
                brush& curBrush = ((brush*)(this->bspFile->brushes))[(camLeaf.leafbrush_first +i)%this->bspFile->numLeafBrushes];
                if(curBrush.n_brushsides < 0) return;
                for(int j = 0; j < curBrush.n_brushsides; j++)
                {
                float dist = -0.1;
                brushside& curBrushSide = ((brushside*)(this->bspFile->brushSides))[(curBrush.brushside +j)%this->bspFile->numBrushSides];
                plane&      testPlane = ((plane*)(this->bspFile->planes))[curBrushSide.plane % this->bspFile->numPlanes];
                dist = testPlane.x * this->cam.x +  testPlane.y * this->cam.y  +  testPlane.z * this->cam.z   -testPlane.d ;

                if(dist < -0.01f) dist = -1.0f *dist;
                if(dist < 1.0f){
                                this->drawDebugCube(&this->cam);
                                return;
                              }
                }

        } */

  }
  return;
}

void BspManager::drawDebugCube(Vector* cam)
{
  glBegin(GL_QUADS);

  // Bottom Face.  Red, 75% opaque, magnified texture

  glNormal3f( 0.0f, -1.0f, 0.0f); // Needed for lighting
  glColor4f(0.9,0.2,0.2,.75); // Basic polygon color

  glTexCoord2f(0.800f, 0.800f); glVertex3f(cam->x-1.0f, cam->y-1.0f,cam->z -1.0f);
  glTexCoord2f(0.200f, 0.800f); glVertex3f(cam->x+1.0f, cam->y-1.0f,cam->z -1.0f);
  glTexCoord2f(0.200f, 0.200f); glVertex3f(cam->x+ 1.0f,cam->y -1.0f,cam->z +  1.0f);
  glTexCoord2f(0.800f, 0.200f); glVertex3f(cam->x-1.0f, cam->y-1.0f, cam->z + 1.0f);


  // Top face; offset.  White, 50% opaque.

  glNormal3f( 0.0f, 1.0f, 0.0f);  glColor4f(0.5,0.5,0.5,.5);

  glTexCoord2f(0.005f, 1.995f); glVertex3f(cam->x-1.0f, cam->y+ 1.0f, cam->z -1.0f);
  glTexCoord2f(0.005f, 0.005f); glVertex3f(cam->x-1.0f, cam->y+ 1.0f,  cam->z +1.0f);
  glTexCoord2f(1.995f, 0.005f); glVertex3f(cam->x+ 1.0f,  cam->y+1.0f,  cam->z +1.0f);
  glTexCoord2f(1.995f, 1.995f); glVertex3f(cam->x+ 1.0f, cam->y+ 1.0f, cam->z -1.0f);


  // Far face.  Green, 50% opaque, non-uniform texture cooridinates.

  glNormal3f( 0.0f, 0.0f,-1.0f);  glColor4f(0.2,0.9,0.2,.5);

  glTexCoord2f(0.995f, 0.005f); glVertex3f(cam->x-1.0f, cam->y-1.0f, cam->z -1.3f);
  glTexCoord2f(2.995f, 2.995f); glVertex3f(cam->x-1.0f, cam->y+ 1.0f, cam->z -1.3f);
  glTexCoord2f(0.005f, 0.995f); glVertex3f(cam->x+ 1.0f,cam->y+  1.0f, cam->z -1.3f);
  glTexCoord2f(0.005f, 0.005f); glVertex3f( cam->x+1.0f,cam->y -1.0f, cam->z -1.3f);


  // Right face.  Blue; 25% opaque

  glNormal3f( 1.0f, 0.0f, 0.0f);  glColor4f(0.2,0.2,0.9,.25);

  glTexCoord2f(0.995f, 0.005f); glVertex3f(cam->x+ 1.0f, cam->y -1.0f, cam->z -1.0f);
  glTexCoord2f(0.995f, 0.995f); glVertex3f(cam->x+ 1.0f, cam->y+ 1.0f, cam->z -1.0f);
  glTexCoord2f(0.005f, 0.995f); glVertex3f(cam->x+ 1.0f, cam->y+ 1.0f, cam->z + 1.0f);
  glTexCoord2f(0.005f, 0.005f); glVertex3f(cam->x+ 1.0f, cam->y-1.0f,  cam->z +1.0f);


  // Front face; offset.  Multi-colored, 50% opaque.

  glNormal3f( 0.0f, 0.0f, 1.0f);

  glColor4f( 0.9f, 0.2f, 0.2f, 0.5f);
  glTexCoord2f( 0.005f, 0.005f); glVertex3f(cam->x-1.0f, cam->y-1.0f,  cam->z +1.0f);
  glColor4f( 0.2f, 0.9f, 0.2f, 0.5f);
  glTexCoord2f( 0.995f, 0.005f); glVertex3f(cam->x+ 1.0f, cam->y-1.0f,  cam->z +1.0f);
  glColor4f( 0.2f, 0.2f, 0.9f, 0.5f);
  glTexCoord2f( 0.995f, 0.995f); glVertex3f( cam->x+1.0f,  cam->y+1.0f,  cam->z +1.0f);
  glColor4f( 0.1f, 0.1f, 0.1f, 0.5f);
  glTexCoord2f( 0.005f, 0.995f); glVertex3f(cam->x-1.0f, cam->y+ 1.0f,  cam->z +1.0f);


  // Left Face; offset.  Yellow, varying levels of opaque.

  glNormal3f(-1.0f, 0.0f, 0.0f);

  glColor4f(0.9,0.9,0.2,0.0);
  glTexCoord2f(0.005f, 0.005f); glVertex3f(cam->x-1.0f, cam->y-1.0f, cam->z -1.0f);
  glColor4f(0.9,0.9,0.2,0.66);
  glTexCoord2f(0.995f, 0.005f); glVertex3f(cam->x-1.0f,cam->y -1.0f,  cam->z +1.0f);
  glColor4f(0.9,0.9,0.2,1.0);
  glTexCoord2f(0.995f, 0.995f); glVertex3f(cam->x-1.0f, cam->y+ 1.0f,  cam->z +1.0f);
  glColor4f(0.9,0.9,0.2,0.33);
  glTexCoord2f(0.005f, 0.995f); glVertex3f(cam->x-1.0f, cam->y+ 1.0f, cam->z -1.0f);

  glEnd();
}

void BspManager::addFace(int f)
{
  face& curFace =  ((face *)(this->bspFile->faces))[f];
  if(this->bspFile->Materials[curFace.texture].alpha) this->trasparent.push_back(f);
  else this->opal.push_back(f);
}