source: orxonox.OLD/trunk/src/lib/graphics/importer/bsp/bsp_manager.cc

/*
   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 "limits.h"
#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 "tools/camera.h"
#include "vertex_array_model.h"
#include "world_entities/player.h"
#include "world_entities/playable.h"

// STL Containers
#include <vector>
#include <deque>
#include "movie_player.h"

#include "world_entity.h"

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

#include "aabb.h"
#include "cr_engine.h"
#include "collision_tube.h"


//CREATE_FACTORY( BspManager, CL_BSP_MODEL);

BspManager::BspManager(WorldEntity* parent)
{

  this->lastTex = -1;
  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);
} */

BspManager::~BspManager()
{
  if(this->bspFile)
    delete this->bspFile;
}

int BspManager::load(const char* fileName, float scale)
{
  // open a BSP file


  this->bspFile = new BspFile();
  this->bspFile->scale =  scale;
  if(this->bspFile->read(Resources::ResourceManager::getInstance()->prependAbsoluteMainPath(fileName).c_str()) == -1)
    return -1;

  this->bspFile->build_tree();
  this->root  = this->bspFile->get_root();
  this->alreadyVisible = new bool [this->bspFile->numFaces];

  this->outputFraction = 1.0f;

  return 0;
}


/*
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();

        }
  */


  this->lastTex = -1;
  // 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 < -70.0 && dMaxs < -70.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


  // now sort the transparent faces in the right order
  if (this->sortTransparency == 1) {
      int size = this->trasparent.size();
      
      // bubble sort
      bool hasSwapped = true;
      Vector v1, v2;

      // initialize distance array
      float * distToPlayer = new float [size];
      for (int i = 0; i < size; i++)
      {
          face& fac1 =  (this->bspFile->faces)[this->trasparent[i]];
//          face& fac2 =  (this->bspFile->faces)[this->trasparent[i+1]];

          // get center of face 1
          const BspVertex* curVertex = (BspVertex *) this->bspFile->vertice;

          if (this->sortTransparencyMore == 1)
          {
              // assign the values of the vertices
              float maxDist = 0;
              float curDist = 0;
              int maxVert = fac1.vertex;
              for (int v = 0; v < fac1.n_vertexes; v++)
              {
                    v1(curVertex[fac1.vertex + v].position[0], curVertex[fac1.vertex + v].position[1], curVertex[fac1.vertex + v].position[2]);
                    curDist = (this->cam - v1).len();
                    if (curDist > maxDist)
                    {
                        maxDist = curDist;
                        maxVert = fac1.vertex + v;
                    }
              }
              v1(curVertex[maxVert].position[0], curVertex[maxVert].position[1], curVertex[maxVert].position[2]);
          }
          else
          {
              v1(curVertex[fac1.vertex].position[0], curVertex[fac1.vertex].position[1], curVertex[fac1.vertex].position[2]);
          }

          // relativly to observer
          v1 = this->cam - v1;

          // save in array
          distToPlayer[i] = v1.len();
      }

      while( hasSwapped)
      {
        hasSwapped = false;

        for( int i = 0; i < size - 1; i++)
        {
/*
          // sorting test
          face& fac1 =  (this->bspFile->faces)[this->trasparent[i]];
          face& fac2 =  (this->bspFile->faces)[this->trasparent[i+1]];

          // get center of face 1
          const BspVertex* curVertex = (BspVertex *) this->bspFile->vertice;
          
          if (this->sortTransparencyMore == 1)
          {
              // assign the values of the vertices
              float maxDist = 0;
              float curDist = 0;
              int maxVert = fac1.vertex;
              for (int v = 0; v < fac1.n_vertexes; v++)
              {
                    v1(curVertex[fac1.vertex + v].position[0], curVertex[fac1.vertex + v].position[1], curVertex[fac1.vertex + v].position[2]);
                    curDist = (this->cam - v1).len();
                    if (curDist > maxDist)
                    {
                        maxDist = curDist;
                        maxVert = fac1.vertex + v;
                    }
              }
              v1(curVertex[maxVert].position[0], curVertex[maxVert].position[1], curVertex[maxVert].position[2]);

              maxDist = 0;
              curDist = 0;
              maxVert = fac1.vertex;
              for (int v = 0; v < fac2.n_vertexes; v++)
              {
                    v2(curVertex[fac2.vertex + v].position[0], curVertex[fac2.vertex + v].position[1], curVertex[fac2.vertex + v].position[2]);
                    curDist = (this->cam - v2).len();
                    if (curDist > maxDist)
                    {
                        maxDist = curDist;
                        maxVert = fac2.vertex + v;
                    }
              }
              v2(curVertex[maxVert].position[0], curVertex[maxVert].position[1], curVertex[maxVert].position[2]);
          }
          else
          {
              v1(curVertex[fac1.vertex].position[0], curVertex[fac1.vertex].position[1], curVertex[fac1.vertex].position[2]);
              v2(curVertex[fac2.vertex].position[0], curVertex[fac2.vertex].position[1], curVertex[fac2.vertex].position[2]);
          }

          // relativly to observer
          v1 = this->cam - v1;
          v2 = this->cam - v2;


*/
          // swap if necessary
//          if( v1.len() - v2.len() > 1)
          if( distToPlayer[i] - distToPlayer[i+1] > 1)
          {
            // swap elements
            float tmp1 = distToPlayer[i+1];
            distToPlayer[i+1] = distToPlayer[i];
            distToPlayer[i] = tmp1;
            
            int tmp2 = this->trasparent[i+1];
            this->trasparent[i+1] = this->trasparent[i];
            this->trasparent[i] = tmp2;

            //printf( "has swapped: %d\n", i );

            //v1.debug();
            //v2.debug();
            hasSwapped = true;
          }
        }
      }
      //printf("hasSwapped == false\n");
  }


  // draw all solid faces
  while(!this->opal.empty()) {
    this->draw_face(this->opal.back()); // front()
    this->opal.pop_back();              // pop_back()
  }

  // draw all transparent faces
  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);
  }
  
  if (State::showWireframe())
  {
    glPolygonMode(GL_FRONT_AND_BACK, GL_LINE);
    glBindTexture(GL_TEXTURE_2D, this->bspFile->whiteLightMap );
    glTexEnvi(GL_TEXTURE_ENV, GL_TEXTURE_ENV_MODE, GL_DECAL);
  }

  glBlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);

  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);
  
  if (State::showWireframe())
  {
    glPolygonMode(GL_FRONT_AND_BACK, GL_FILL);
    glTexEnvi(GL_TEXTURE_ENV, GL_TEXTURE_ENV_MODE, GL_MODULATE);
  }
}


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);
  }
 
  if (State::showWireframe())
  {
    glPolygonMode(GL_FRONT_AND_BACK, GL_LINE);
    glBindTexture(GL_TEXTURE_2D, this->bspFile->whiteLightMap );
    glTexEnvi(GL_TEXTURE_ENV, GL_TEXTURE_ENV_MODE, GL_DECAL);
  }


  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 );
  
  if (State::showWireframe())
  {
    glPolygonMode(GL_FRONT_AND_BACK, GL_FILL);
    glTexEnvi(GL_TEXTURE_ENV, GL_TEXTURE_ENV_MODE, GL_MODULATE);
  }
}

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

  //TODO valgrind complains about uninitialised value here
  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;

  this->checkCollisionX(worldEntity);
  this->checkCollisionZ(worldEntity);

  if(!(this->checkCollisionY(worldEntity)))
  this->checkCollisionWay(worldEntity);


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


  Vector forwardDir = Vector(0.0,0.0,1.0);
  Vector upDir = Vector(0.0,1.0,0.0);
  Vector position = worldEntity->getAbsCoor();

  bool SolidFlag = false;
  bool collision = false;
  Vector position1 = position;
  Vector position2 = position + Vector(0.0,1.0,0.0);
  Vector position3 = position;
  Vector position4 = position + Vector(0.0,1.0,0.0);
  Vector dest = worldEntity->getAbsCoor() - upDir*40.0f; //
  Vector dest1 = position + forwardDir*4.0f;
  Vector dest2 = position2 + forwardDir*4.0;
  Vector dest3 = position + forwardDir*4.0f;
  Vector dest4 = position2 + forwardDir*4.0;
  dest = position - Vector(0.0, 40.0,0.0);
  Vector out = dest;
  Vector out1;
  Vector out2;


  plane* testPlane;

  bool xCollision = false;
  bool zCollision = false;


  float height = 40;


  if( box != NULL) {
    position = worldEntity->getAbsCoor() +  box->center; // + Vector(0.0, 1.0, 0.0) * box->halfLength[1] * 1.0f;
    dest     = worldEntity->getAbsCoor() +  box->center - Vector(0.0, 1.0, 0.0) * (box->halfLength[1] + BSP_Y_OFFSET) *   100;

    Vector dirX =  worldEntity->getAbsDirX(); dirX.y = 0.0f; dirX.normalize();

    //position1 = worldEntity->getAbsCoor() +  box->center - dirX * (box->halfLength[0]  + BSP_X_OFFSET);
    dest1     = worldEntity->getAbsCoor() +  box->center + dirX * (box->halfLength[0]  + BSP_X_OFFSET);
    dest2     = worldEntity->getAbsCoor() -  box->center + dirX * (box->halfLength[0]  + BSP_X_OFFSET);

    Vector dirZ =  worldEntity->getAbsDirZ(); dirX.y = 0.0f; dirZ.normalize();
    //position2 = worldEntity->getAbsCoor() +  box->center - dirZ * (box->halfLength[2]  + BSP_Z_OFFSET);
    dest3     = worldEntity->getAbsCoor() +  box->center + dirZ * (box->halfLength[2]  + BSP_Z_OFFSET);
    dest4     = worldEntity->getAbsCoor() -  box->center + dirZ * (box->halfLength[2]  + BSP_Z_OFFSET);
  } else {
    // Init positions and destinations to anything useful!

  }



  // 1st Ray: Y RAY
  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;
        SolidFlag = 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;
    }
  }
    testPlane = this->collPlane;


  bool xCollisionNeg = false;
  bool zCollisionNeg = false;



    // 2nd Collision Detection X-RAY
    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 );

    if(this->outputFraction < 1.0f) {
      out.x = dest1.x + (dest1.x -position1.x) * this->outputFraction;
      dest1 = position1 + (dest1 -position1) * this->outputFraction;
      xCollision = true;
      testPlane = this->collPlane;
    }
    if(this->outputAllSolid ) {

      this->collPlane = new plane;
      this->collPlane->x = 0.0f;
      this->collPlane->y = 0.0f;
      this->collPlane->z = 0.0f;
      testPlane = this->collPlane;
      SolidFlag = true;
      xCollision = true;
    }
    //out.z = this->outputFraction;



      // 3rd Collision Detection Z-RAY
      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;

      if(this->outputFraction < 1.0f ) {
        out.z = out.z = dest2.z + (dest2.z -position2.z) * this->outputFraction;
        dest2 = position2 + (dest2 -position2) * this->outputFraction;
        zCollision = true;
        testPlane = this->collPlane;

      }
      if(this->outputAllSolid ) {
        this->collPlane = new plane;
        this->collPlane->x = 0.0f;
        this->collPlane->y = 0.0f;
        this->collPlane->z = 0.0f;
        testPlane = this->collPlane;

        SolidFlag = true;
        zCollision = true;
      }


  // Return the normal here: Normal's stored in this->collPlane;
  if( collision) {
    worldEntity->registerCollision(COLLISION_TYPE_AXIS_Y , this->parent, worldEntity, Vector(testPlane->x, testPlane->y, testPlane->z), out, SolidFlag);
}
  if(xCollision) {
    worldEntity->registerCollision(COLLISION_TYPE_AXIS_X , this->parent, worldEntity, Vector(testPlane->x, testPlane->y, testPlane->z),dest1 , SolidFlag);
  }

  if(zCollision) {
    worldEntity->registerCollision(COLLISION_TYPE_AXIS_Z , this->parent, worldEntity, Vector(testPlane->x, testPlane->y, testPlane->z), dest2 , SolidFlag);
  }
#endif

}



/**
 * check the collision in the x direction (forward, backward)
 */
bool BspManager::checkCollisionX(WorldEntity* entity)
{
  // Retrieve Bounding box
  AABB* box = entity->getModelAABB();


  plane*            testPlane          = NULL;  //!< the collision test plane

  Vector            forward;                    //!< left collision ray
  Vector            backward;                   //!< right collision ray
  Vector            collPos;                    //!< the collision position

  bool              xCollisionForward  = false; //!< flag true if right collision
  bool              xCollisionBackward = false; //!< flag true if left collision
  bool              SolidFlag          = false; //!< flag set true if solid

  Vector            position;                   //!< current position of the entity
  Vector            dirX;                       //!< direction x

  position = entity->getAbsCoor();
  dirX =  entity->getAbsDirX(); dirX.y = 0.0f; dirX.normalize();

  // calculate the rays
  if( box != NULL)
  {
    forward  = entity->getAbsCoor() +  box->center + dirX * (box->halfLength[0]  + BSP_X_OFFSET);
    backward = entity->getAbsCoor() +  box->center - dirX * (box->halfLength[0]  + BSP_X_OFFSET);
  }
  else
  {
    forward  = position + dirX * 4.0f;
    backward = position + Vector(0.0, 1.0, 0.0) + dirX * 4.0;
  }


  /*   X Ray forward  */
  // init some member variables before collision check
  this->outputStartsOut = true;
  this->outputAllSolid = false;
  this->outputFraction = 1.0f;
  this->inputStart =  position;
  this->inputEnd =   forward;
  this->checkCollisionRayN(this->root, 0.0f, 1.0f, &position, &forward );

  // collision occured
  if( this->outputFraction < 1.0f)
  {
    collPos = position + (forward - position) * this->outputFraction;
    xCollisionForward = true;
    testPlane = this->collPlane;
  }
  if(this->outputAllSolid )
  {
    this->collPlane = new plane;
    this->collPlane->x = 0.0f;
    this->collPlane->y = 0.0f;
    this->collPlane->z = 0.0f;
    testPlane = this->collPlane;
    SolidFlag = true;
    xCollisionForward = true;
  }

  // collision registration
  if( xCollisionForward)
  {
    CoRe::CollisionTube::getInstance()->registerCollisionEvent( CoRe::CREngine::CR_COLLISION_TYPE_AXIS_X ,
                              entity, this->parent,
                              Vector(testPlane->x, testPlane->y, testPlane->z),
                              collPos,
                              SolidFlag);
  }



  /*   X Ray backward  */
  // init some member variables before collision check
  this->outputStartsOut = true;
  this->outputAllSolid = false;
  this->outputFraction = 1.0f;
  this->inputStart =  position;
  this->inputEnd =   backward;
  this->checkCollisionRayN(this->root, 0.0f, 1.0f, &position, &backward );

  // collision occured
  if( this->outputFraction < 1.0f)
  {
    collPos = position + (backward - position) * this->outputFraction;
    xCollisionBackward = true;
    testPlane = this->collPlane;
  }
  if( this->outputAllSolid)
  {
    this->collPlane = new plane;
    this->collPlane->x = 0.0f;
    this->collPlane->y = 0.0f;
    this->collPlane->z = 0.0f;
    testPlane = this->collPlane;
    SolidFlag = true;
    xCollisionBackward = true;
  }

  // collision registration
  if( xCollisionBackward)
  {
    CoRe::CollisionTube::getInstance()->registerCollisionEvent( CoRe::CREngine::CR_COLLISION_TYPE_AXIS_X_NEG,
                              entity, this->parent,
                              Vector(testPlane->x, testPlane->y, testPlane->z),
                              collPos,
                              SolidFlag);
  }

 return (xCollisionBackward || xCollisionForward);
}


/**
 * check the collision in the z direction (up, down)
 */
bool BspManager::checkCollisionY(WorldEntity* entity)
{

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


  plane*            testPlane          = NULL;  //!< the collision test plane

  Vector            up;                         //!< up collision ray
  Vector            down;                       //!< down collision ray
  Vector            collPos;                    //!< the collision position

  bool              yCollisionUp       = false; //!< flag true if right collision
  bool              yCollisionDown     = false; //!< flag true if left collision
  bool              SolidFlag          = false; //!< flag set true if solid

  Vector            position;                   //!< current position of the entity
  Vector            dirY;                       //!< direction x

  position = entity->getAbsCoor();
  collPos = position;
  dirY =  Vector(0.0, 1.0, 0.0);

  // calculate the rays
  if( box != NULL)
  {
    up   = position +  box->center + dirY * (box->halfLength[1]/*  + BSP_Y_OFFSET*/);
    down = position +  box->center - dirY * (box->halfLength[1]  + BSP_Y_OFFSET);
  }
  else
  {
    up   = position + dirY * 4.0f;
    down = position + Vector(0.0, 1.0, 0.0) + dirY * 4.0;
  }




  /*   Y Ray up */
  // init some member variables before collision check
  this->inputStart = position;
  this->inputEnd   = up;
  this->checkCollisionRayN(this->root,0.0f,1.0f, &position, &up );

  if( !this->outputStartsOut )
  {
    this->collPlane = new plane;
    this->collPlane->x = 0.0f;
    this->collPlane->y = 0.0f;
    this->collPlane->z = 0.0f;
    yCollisionUp = 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;
        yCollisionUp = true;
        SolidFlag = true;
      }
      else
      {
        yCollisionUp = false;
        collPos = up;
      }
    }
    else
    {
      yCollisionUp = true;
      collPos = position + (up - position) * this->outputFraction;
      this->out = collPos;        // why this????
    }
  }
  testPlane = this->collPlane;

  // collision registration
  if( yCollisionUp)
  {
    CoRe::CollisionTube::getInstance()->registerCollisionEvent( CoRe::CREngine::CR_COLLISION_TYPE_AXIS_Y,
                              entity, this->parent,
                              Vector(testPlane->x, testPlane->y, testPlane->z),
                              collPos, SolidFlag);
  }




  /*   Y Ray down */
  // init some member variables before collision check
  this->inputStart = position;
  this->inputEnd   = down;
  this->checkCollisionRayN(this->root,0.0f,1.0f, &position, &down );

  if( !this->outputStartsOut )
  {
    this->collPlane = new plane;
    this->collPlane->x = 0.0f;
    this->collPlane->y = 0.0f;
    this->collPlane->z = 0.0f;
    yCollisionDown = true;
  }
  else
  {
    if( this->outputFraction == 1.0f) // No collision Detected
    {
      if( this->outputAllSolid )
      {
        this->collPlane = new plane;
        this->collPlane->x = 0.0f;
        this->collPlane->y = 0.0f;
        this->collPlane->z = 0.0f;
        yCollisionDown = true;
        SolidFlag = true;
      }
      else      // No collision happened
      {
        yCollisionDown = false;
        collPos = down;
      }
    }
    else           // A collision has happended
    {
      yCollisionDown = true;
      collPos = position + (down - position) * this->outputFraction;
    }
  }
  testPlane = this->collPlane;

  // collision registration
  if( yCollisionDown)
  {
    CoRe::CollisionTube::getInstance()->registerCollisionEvent( CoRe::CREngine::CR_COLLISION_TYPE_AXIS_Y_NEG ,
                              entity, this->parent,
                              Vector(testPlane->x, testPlane->y, testPlane->z),
                              collPos, SolidFlag);
  }

 return (yCollisionUp || yCollisionDown);
}




/**
 * check the collision in the z direction (left, right)
 */
bool BspManager::checkCollisionZ(WorldEntity* entity)
{
  // Retrieve Bounding box
  AABB* box = entity->getModelAABB();


  plane*            testPlane          = NULL;  //!< the collision test plane

  Vector            right;                      //!< right collision ray
  Vector            left;                       //!< left collision ray
  Vector            collPos;                    //!< the collision position

  bool              zCollisionRight    = false; //!< flag true if right collision
  bool              zCollisionLeft     = false; //!< flag true if left collision
  bool              SolidFlag          = false; //!< flag set true if solid

  Vector            position;                   //!< current position of the entity
  Vector            dirZ;                       //!< direction x

  position = entity->getAbsCoor();
  dirZ =  entity->getAbsDirZ(); dirZ.y = 0.0f; dirZ.normalize();

  // calculate the rays
  if( box != NULL)
  {
    right = entity->getAbsCoor() +  box->center + dirZ * (box->halfLength[2]  + BSP_Z_OFFSET);
    left  = entity->getAbsCoor() +  box->center - dirZ * (box->halfLength[2]  + BSP_Z_OFFSET);
  }
  else
  {
    right = position + dirZ * 4.0f;
    left  = position + Vector(0.0, 1.0, 0.0) + dirZ * 4.0;
  }


  /*   Z Ray right */
  // init some member variables before collision check
  this->outputStartsOut = true;
  this->outputAllSolid = false;
  this->outputFraction = 1.0f;
  this->inputStart =  position;
  this->inputEnd =   right;
  this->checkCollisionRayN(this->root, 0.0f, 1.0f, &position, &right );


  // collision occured
  if( this->outputFraction < 1.0f )
  {
    collPos = position + (right - position) * this->outputFraction;
    zCollisionRight = true;
    testPlane = this->collPlane;
  }
  if(this->outputAllSolid )
  {
    this->collPlane = new plane;
    this->collPlane->x = 0.0f;
    this->collPlane->y = 0.0f;
    this->collPlane->z = 0.0f;
    testPlane = this->collPlane;

    SolidFlag = true;
    zCollisionRight = true;
  }


  if( zCollisionRight) {
    CoRe::CollisionTube::getInstance()->registerCollisionEvent( CoRe::CREngine::CR_COLLISION_TYPE_AXIS_Z ,
                              entity, this->parent,
                              Vector(testPlane->x, testPlane->y, testPlane->z),
                              collPos , SolidFlag);
  }



  /*   Z Ray left */
  // init some member variables before collision check
  this->outputStartsOut = true;
  this->outputAllSolid = false;
  this->outputFraction = 1.0f;
  this->inputStart =  position;
  this->inputEnd =    left;
  this->checkCollisionRayN(this->root, 0.0f, 1.0f, &position, &left);


  // collision occured
  if( this->outputFraction < 1.0f )
  {
    collPos = position + (left - position) * this->outputFraction;
    zCollisionLeft = true;
    testPlane = this->collPlane;
  }
  if(this->outputAllSolid )
  {
    this->collPlane = new plane;
    this->collPlane->x = 0.0f;
    this->collPlane->y = 0.0f;
    this->collPlane->z = 0.0f;
    testPlane = this->collPlane;

    SolidFlag = true;
    zCollisionLeft = true;
  }


  if( zCollisionLeft) {
    CoRe::CollisionTube::getInstance()->registerCollisionEvent( CoRe::CREngine::CR_COLLISION_TYPE_AXIS_Z_NEG ,
                               entity, this->parent,
                               Vector(testPlane->x, testPlane->y, testPlane->z),
                               collPos , SolidFlag);
  }

 return (zCollisionLeft || zCollisionRight);

}



float BspManager::checkCollisionRay(Vector StartPoint, Vector Direction, float length )
{
  Direction.normalize(); // Oder besser vor dem Fkt-Aufruf schon normalisieren
  this->outputStartsOut = true;
  this->outputAllSolid = false;
  this->outputFraction = 1.0f;
  this->inputStart =  StartPoint;
  Vector End =   StartPoint + (Direction)*length;
  this->inputEnd =   End;

  this->checkCollisionRayN(this->root, 0.0f, 1.0f, &StartPoint, &(End) );

  return (this->outputFraction * length);

}



/**
 * check wether a collision occured on the way from the last position to the current position
 */
bool BspManager::checkCollisionWay(WorldEntity* entity)
{


  
  plane*            testPlane          = NULL;  //!< the collision test plane
  Vector            to;
  Vector            collPos;                    //!< the collision position

  bool              yCollisionUp       = false; //!< flag true if right collision
  bool              SolidFlag          = false; //!< flag set true if solid

  Vector            from;                   //!< current position of the entity
  Vector            dirY;                       //!< direction x

  from = entity->getLastAbsCoor();
  to    = entity->getAbsCoor();
  collPos = from;
  dirY =  Vector(0.0, 1.0, 0.0);




  /*   Y Ray up */
  // init some member variables before collision check
  this->inputStart = from;
  this->inputEnd   = to;
  this->checkCollisionRayN(this->root,0.0f,1.0f, &from, &to );

  if( !this->outputStartsOut )
  {
    this->collPlane = new plane;
    this->collPlane->x = 0.0f;
    this->collPlane->y = 0.0f;
    this->collPlane->z = 0.0f;
    yCollisionUp = 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;
        yCollisionUp = true;
        SolidFlag = true;
      }
      else
      {
        yCollisionUp = false;
        collPos = to;
      }
    }
    else
    {
      yCollisionUp = true;
      collPos = from + (to - from) * this->outputFraction;
      this->out = collPos;        // why this????
    }
  }
  testPlane = this->collPlane;

  // collision registration
  if( yCollisionUp)
  {
    CoRe::CollisionTube::getInstance()->registerCollisionEvent( CoRe::CREngine::CR_COLLISION_TYPE_WAY,
                              entity, this->parent,
                              Vector(testPlane->x, testPlane->y, testPlane->z),
                              collPos, SolidFlag);
  }

 return yCollisionUp;

}




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