/***************************************************************************
 *   Copyright (C) 2007 by A.J. Tavakoli                                   *
 *                                                                         *
 *   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 of the License, or     *
 *   (at your option) any later version.                                   *
 *                                                                         *
 *   This program is distributed in the hope that it will be useful,       *
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of        *
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the         *
 *   GNU General Public License for more details.                          *
 *                                                                         *
 *   You should have received a copy of the GNU General Public License     *
 *   along with this program; if not, write to the                         *
 *   Free Software Foundation, Inc.,                                       *
 *   59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.             *
 ***************************************************************************/

#include <cstring>
#include <stdexcept>
#include "BSP.h"
#include "TGAFile.h"
#include "Physics.h"


BSP::BSP(): 
     root(NULL),
     numTextures(0),
     texIDs(NULL),
     normalMapIDs(NULL),
     pvsWidth(0),
     pvs(NULL) {

}


BSP::~BSP() {
  clear();
}


// clears any data in BSP
void BSP::clear() {
  if ( root != NULL ) {
    delete root;
    root = NULL;
  }

  if ( texIDs != NULL ) {
    for ( int i=0; i < numTextures; i++ ) {
      if ( texIDs[i] > 0 )
        Video::deleteTexture(texIDs[i]);
    }
    delete [] texIDs;
    texIDs = NULL;
  }

  if ( normalMapIDs != NULL ) {
    for ( int i=0; i < numTextures; i++ ) {
      if ( normalMapIDs[i] > 0 )
        Video::deleteTexture(normalMapIDs[i]);
    }    
    delete [] normalMapIDs;
    normalMapIDs = NULL;
  }

  if ( pvs != NULL ) {
    delete [] pvs;
    pvs = NULL;
  }

  // clear entities
  for ( size_t i=0; i < entities.size(); i++ )
    if ( entities[i] != NULL && entities[i]->getCleanUp() == true )
      delete entities[i];

  entities.clear();

  leafNodes.clear();
  numTextures = 0;
  pvsWidth = 0;
}


void BSP::insertEntity(Entity *entity) {
  if ( NULL == entity )
    return;

  // make sure entity is not already in BSP
  for ( size_t i=0; i < entities.size(); i++ )
    if ( entities[i] == entity )
      return;

  // since the entity is not in BSP, insert it
  entities.push_back(entity);

  // now try to place entity in BSP
  Node *node = root;
  while ( node != NULL  ) {
    // classify entity relative to splitting plane of node
    const Plane &plane = node->getPlane();
    int side = plane.classifyAABB( entity->getAABB() );

    // try to push entity further down tree, but if it crosses the splitting
    // plane or the current node is a leaf then it must be inserted in
    // this node
    if ( side > 0 && node->getFront() != NULL )
      node = node->getFront();
    else if ( side < 0 && node->getBack() != NULL )
      node = node->getBack();
    else {
      node->insertEntity(entity);
      break;
    }
  }
}


// attempts to trace light position to a leaf node in BSP.
// if successful then inserts light in leaf.
void BSP::insertLight(const Video::Light &l) {
  // only insert light if it is a point light
  // (this is the case if l.pos[3] == 1.0)
  if ( l.pos[3] < 1.0f )
    return; // not a point light

  // get light position
  Point3 lightPos(l.pos[0], l.pos[1], l.pos[2]);

  // try to place light in BSP
  Node *node = NULL;
  if ( root != NULL )
    node = root->tracePoint(lightPos);

  // if light position was traced to a leaf, insert light there
  if ( node != NULL && node->isLeaf() )
    node->insertLight(l);
}


void BSP::updateEntities(float dt) {
  for ( size_t i=0; i < entities.size(); i++ )
    entities[i]->update(dt, *this);
}


// renders geometry in BSP, but not in any particular order.
// simply iterates through leafs and renders each one.
void BSP::render(const Camera &camera) {
  if ( NULL == root )
    return;

  // trace view position into a leaf
  const Point3 &cameraPos = camera.getPos();
  const Node *viewNode = root->tracePoint(cameraPos);

  // get pvs index of node that view position is in
  int pvsIndex = -1;
  if ( viewNode != NULL )
    pvsIndex = viewNode->getPVSIndex();

  Video::setupLights();

  // extract view frustum so it can be used to do frustum culling
  Frustum frustum = Video::getFrustum();

  // iterate through leafs and render each one
  for ( size_t i=0; i < leafNodes.size(); i++ ) {
    Node *leaf = leafNodes[i];

    // if this node is not potentially visible, don't render it
    //if ( !potentiallyVisible(pvsIndex, leafNodes[i]->getPVSIndex()) )
    //  continue;

    // FRUSTUM CULLING
    if ( frustum.classifyAABB(leaf->getAABB()) < 0 )
      continue; // outside of view frustum

    leaf->render(texIDs, normalMapIDs);
  }

  ///// render entities /////

  // iterate through entities, and render each one
  for ( size_t i=0; i < entities.size(); i++ ) {
    // only render entity if its bounding box is inside the view frustum
    if ( frustum.classifyAABB( entities[i]->getAABB() ) >= 0 )
      entities[i]->render();
  }
}


void BSP::Node::render(const int *texIDs,
                       const int *normalMapIDs) {
  // if this is a leaf, render any static geometry in it
  if ( isLeaf() ) {
    if ( faceContainer != NULL ) {
      // render each batch of faces
      for ( size_t i=0; i < faceContainer->getNumBatches(); i++ ) {
        const FaceContainer::FaceBatch &batch = faceContainer->getBatch(i);
        
        Video::useTexture( texIDs[batch.matID] );
        Video::useNormalMap( normalMapIDs[batch.matID] );

        // render each face in batch
        for ( size_t j=0; j < batch.faces.size(); j++ ) {
          const FaceContainer::Face &face = batch.faces[j];

          Video::renderTris( face.getVerts(), face.getNumVerts()/3 );
        } // for (faces)
      } // for (batches)
    } // if ( faceContainer non-NULL )
  } // if (leaf)
  else {
    // not a leaf, so recurse into child nodes
    // (not rendering in any particular order, so just do a depth-first traversal)
    if ( front != NULL )
      front->render(texIDs, normalMapIDs);
    if ( back != NULL )
      back->render(texIDs, normalMapIDs);
  } // else (not a leaf)
}


// checks for collisions with axis-aligned bounding-box where startPos
// is the starting position of the box, and endPos is the final position
// of the box.  If there is a collision, the parametric distance
// (between 0.0 and 1.0) along displacement vector is stored in hitFraction
// and normal of surface that was hit is stored in hitNormal.  returns true
// if there is an intersection, false otherwise.
bool BSP::checkCollisions(const Entity *entity,
                          const Point3 &startPos, const Point3 &endPos,
                          float &hitFraction, Vector3 &hitNormal) const {
  if ( root != NULL ) {
    hitFraction = 1.0f;
    hitNormal = Vector3(0.0f, 0.0f, 0.0f);

    const AABB &aabb = entity->getAABB();
    AABB aabbStart(startPos, aabb.getExt()),
         aabbEnd(endPos, aabb.getExt());

    root->traceEntity(entity, aabbStart, aabbEnd, hitFraction, hitNormal);

    if ( hitFraction >= 0.0f && hitFraction < 1.0f )
      return true;
  }

  return false;
}


void BSP::Node::traceEntity(const Entity *entity,
                            const AABB &aabbStart, const AABB &aabbEnd,
                            float &hitFraction, Vector3 &hitNormal) const {
  // if there are any entities in this node, check for intersections with them
  if ( entities.size() > 0 )
    checkEntitiesAABB(entity, aabbStart, aabbEnd, hitFraction, hitNormal);

  // if this is a leaf, check for intersections with brushes, and
  // then return
  if ( isLeaf() && numBrushes > 0 ) {
    checkBrushesAABB(aabbStart, aabbEnd, hitFraction, hitNormal);
    return;
  }

  // classify box relative to splitting plane at start position
  int startSide = plane.classifyAABB(aabbStart);

  // classify box relative to splitting plane at end position
  int endSide = plane.classifyAABB(aabbEnd);

  // if object is intersecting or in front of the plane at either start
  // or end points then must traverse front side
  if ( startSide >= 0 || endSide >= 0 )
    if ( front != NULL )
      front->traceEntity(entity, aabbStart, aabbEnd, hitFraction, hitNormal);

  // if object is intersecting or in back of the plane at either start
  // or end points then must traverse back side
  if ( startSide <= 0 || endSide <= 0 )
    if ( back != NULL )
      back->traceEntity(entity, aabbStart, aabbEnd, hitFraction, hitNormal);
}


void BSP::Node::checkBrushAABB(const Plane *planes, int numPlanes,
                               const AABB &aabbStart, const AABB &aabbEnd,
                               float &hitFraction, Vector3 &hitNormal) const {
  AABB tempAABB( Point3(0.0f, 0.0f, 0.0f), aabbStart.getExt() );
  float startFraction = -1.0f;
  float endFraction = 1.0f;
  bool startsOut = false;
  bool endsOut = false;
  int closest = 0;

  // iterate through planes
  for ( int i=0; i < numPlanes; i++ ) {
    const Plane &plane = planes[i];

    Vector3 offset;
    for ( int j = 0; j < 3; j++ ) {
      if ( plane.getNormal()[j] < 0 )
        offset[j] = tempAABB.getMax()[j];
      else
        offset[j] = tempAABB.getMin()[j];
    }

    float startDistance = (aabbStart.getCenter()[0] + offset[0]) * plane.getNormal()[0] +
                          (aabbStart.getCenter()[1] + offset[1]) * plane.getNormal()[1] +
                          (aabbStart.getCenter()[2] + offset[2]) * plane.getNormal()[2] -
                          plane.getOffset();
    float endDistance = (aabbEnd.getCenter()[0] + offset[0]) * plane.getNormal()[0] +
                        (aabbEnd.getCenter()[1] + offset[1]) * plane.getNormal()[1] +
                        (aabbEnd.getCenter()[2] + offset[2]) * plane.getNormal()[2] -
                        plane.getOffset();

    if ( startDistance > 0.0f )
      startsOut = true;
    if ( endDistance > 0.0f )
      endsOut = true;

    // if entiy starts and ends in front of this plane, then entity cannot
    // be inside brush
    if ( startDistance > 0.0f && endDistance > 0.0f )
      return; // outside of brush

    // if entity starts and ends behind plane, then check next plane
    if ( startDistance <= 0.0f && endDistance <= 0.0f )
      continue;

    if ( startDistance > endDistance ) {
        // line is entering into the brush
        float fraction = (startDistance - EPSILON)/
                        (startDistance - endDistance);
        if (fraction > startFraction) {
          closest = i;
          startFraction = fraction;
        }
    }
    else
    {   // line is leaving the brush
        float fraction = (startDistance + EPSILON)
                          /(startDistance - endDistance);
        if ( fraction < endFraction )
          endFraction = fraction;
    }
  } // for (brush planes)

  if ( false == startsOut )
    return;

  if (startFraction < endFraction) {
    if ( startFraction > -1.0f &&
          startFraction < hitFraction ) {
      if (startFraction < 0.0f)
          startFraction = 0.0f;
      hitFraction = startFraction;
      hitNormal = planes[closest].getNormal();
    }
  } // for (planes)
}


void BSP::Node::checkBrushesAABB(const AABB &aabbStart, const AABB &aabbEnd,
                                 float &hitFraction, Vector3 &hitNormal) const {
  for ( int i=0; i < numBrushes; i++ )
    checkBrushAABB(brushes[i].planes, brushes[i].numPlanes,
                   aabbStart, aabbEnd,
                   hitFraction, hitNormal);
}


void BSP::Node::checkEntitiesAABB(const Entity *entity,
                                  const AABB &aabbStart, const AABB &aabbEnd,
                                  float &hitFraction, Vector3 &hitNormal) const {
  for ( std::set<Entity *>::const_iterator itr = entities.begin();
        itr != entities.end();
        itr++ ) {
    const Entity *entity2 = *itr;

    // don't test against self
    if ( entity2 == entity )
      continue;

    // extract planes from entity's bounding box, so we can test for collisions
    // against it as a brush
    AABB entAABB = entity2->getAABB();
    Plane planes[6] = { Plane( Vector3( 1.0f,  0.0f,  0.0f), entAABB.getMax() ),
                        Plane( Vector3(-1.0f,  0.0f,  0.0f), entAABB.getMin() ),
                        Plane( Vector3( 0.0f,  1.0f,  0.0f), entAABB.getMax() ),
                        Plane( Vector3( 0.0f, -1.0f,  0.0f), entAABB.getMin() ),
                        Plane( Vector3( 0.0f,  0.0f,  1.0f), entAABB.getMax() ),
                        Plane( Vector3( 0.0f,  0.0f, -1.0f), entAABB.getMin() ) };

    // test for collisions against brush representation of AABB
    checkBrushAABB(planes, 6, aabbStart, aabbEnd, hitFraction, hitNormal);
  } // for (entities)
}


// traces a point into a leaf in BSP, and returns const pointer to node
// (should be a leaf)
const BSP::Node* BSP::Node::tracePoint(const Point3 &p) const {
  // if this is a leaf, return a pointer to this
  if ( isLeaf() )
    return this;

  float dist = plane.getNormal()*p - plane.getOffset();

  // if point is in front of plane, traverse front subtree
  if ( dist >= 0.0f )
    if ( front != NULL )
      return front->tracePoint(p);

  // if point is in back of plane, traverse back subtree
  if ( dist < 0.0f )
    if ( back != NULL )
      return back->tracePoint(p);

  return NULL;
}


// traces a point into a leaf in BSP, and returns pointer to node
// (should be a leaf)
BSP::Node *BSP::Node::tracePoint(const Point3 &p) {
  // if this is a leaf, return a pointer to this
  if ( isLeaf() )
    return this;

  float dist = plane.getNormal()*p - plane.getOffset();

  // if point is in front of plane, traverse front subtree
  if ( dist >= 0.0f )
    if ( front != NULL )
      return front->tracePoint(p);

  // if point is in back of plane, traverse back subtree
  if ( dist < 0.0f )
    if ( back != NULL )
      return back->tracePoint(p);

  return NULL;
}


// stores collision information from quake 3 map in BSP
void BSP::loadQ3Map(const Q3Map &q3map) {
  // if there is any data currently in BSP, delete it
  clear();

  // make sure there are nodes in map
  if ( q3map.getNumNodes() <= 0 )
    return;
  
  // create root and build BSP tree from data in quake 3 map
  root = new Node(q3map, leafNodes, 0);
  
  if ( NULL == root )
    throw std::runtime_error("BSP::BSP(): unable to allocate memory "
                             "for root node");
  
  // copy potentially visible set
  if ( q3map.getNumVisVecs() > 0 &&
       q3map.getVisVecs() &&
       q3map.getSizeVisVecs() > 0 ) {
    // get pointer to pvs
    const char *visData = (const char *)q3map.getVisVecs();

    // calculate size of pvs in bytes
    int pvsSize = (q3map.getSizeVisVecs())*
                  int(q3map.getNumVisVecs());

    // allocate storage for pvs
    pvs = new char[pvsSize];

    // copy pvs data
    memcpy(pvs, visData, pvsSize);
  }

  ///// load textures /////
  numTextures = q3map.getNumTextures();

  if ( numTextures > 0 ) {
    // allocate storage for texture ids
    texIDs       = new int[numTextures];
    normalMapIDs = new int[numTextures];

    if ( NULL == texIDs || NULL == normalMapIDs )
      throw std::runtime_error("BSP::loadQ3Map(): unable to allocate "
                               "storage for texture ids");

    // initialize all texture ids to -1 (invalid texture)
    for ( int i=0; i < numTextures; i++ )
      texIDs[i] = normalMapIDs[i] = -1;

    // temporary string to hold texture filename
    char filename[80];

    for ( int i=0; i < numTextures; i++ ) {
      TGAFile image;
      const Q3Map::Texture &texture = q3map.getTexture(i);

      // ignore certain textures
      if ( strcmp(texture.name, "textures/common/caulk") == 0 ||
           strcmp(texture.name, "noshader") == 0 ||
           strcmp(texture.name, "textures/NULL") == 0 )
        continue;

      // append tga extension to filename
      strncpy(filename, texture.name, 64);
      strcat(filename, ".tga");
      texIDs[i] = Video::loadTexture(filename);

      // now try to load normal map corresponding to this texture
      strncpy(filename, texture.name, 64);
      strcat(filename, "_local.tga");
      normalMapIDs[i] = Video::loadTexture(filename, true);
    } // for (textures)
  } // if (number of textures > 0)
}


// recursively constructs internal BSP tree nodes from data in quake 3 map
BSP::Node::Node(const Q3Map &q3map,
                std::vector<Node *> &leafNodes,
                int nodeIndex):
     lights(0) {
  numBrushes = 0;
  front = back = NULL;
  brushes = NULL;
  faceContainer = NULL;
  pvsIndex = -1;

  // is this a leaf?
  if ( nodeIndex < 0 ) {
    // leaf indices are represented as -(leafindex + 1)  
    int leafIndex = -(nodeIndex + 1);

    // make sure leaf index is valid
    if ( leafIndex >= q3map.getNumLeafs() )
      throw std::runtime_error("BSP::Node::Node(): leaf index is >= number of "
                               "leafs");

    // add to array of leaf nodes
    leafNodes.push_back(this);

    // get reference to leaf structure
    const Q3Map::Leaf &leaf = q3map.getLeaf(leafIndex);
    
    ///// store collision detection information /////

    // get number of brushes
    numBrushes = int(leaf.numLeafBrushes);

    // get index of first brush for this leaf
    int firstBrush = int(leaf.leafBrush);

    // allocate storage for brushes
    if ( numBrushes > 0 )
      brushes = new Brush[numBrushes];
    else if ( numBrushes < 0 ) {
      throw std::runtime_error("BSP::Node::Node(): number of brushes in "
                               "leaf is < 0");
    }
    else
      numBrushes = 0;

    // extract each brush
    for ( int i=0; i < numBrushes; i++ ) {
      int brushIndex = int( q3map.getLeafBrush(firstBrush + i) );
      Q3Map::Brush brush = q3map.getBrush(brushIndex);
      int numBrushSides = int(brush.numBrushSides);
      int firstBrushSide = int(brush.brushSide);

      brushes[i].numPlanes = numBrushSides;
      if ( numBrushSides > 0 )
        brushes[i].planes = new Plane[numBrushSides];

      // extract each plane (side) for this brush
      for ( int j=0; j < numBrushSides; j++ ) {
        Q3Map::BrushSide brushSide = q3map.getBrushSide(firstBrushSide + j);
        Q3Map::Plane q3plane = q3map.getPlane( int(brushSide.plane) );

        Vector3 n = Vector3(q3plane.normal[0],
                            q3plane.normal[2],
                           -q3plane.normal[1]);
        brushes[i].planes[j] = Plane(n, q3plane.d);
      } // for (brush sides)
    } // for (brushes)

    ///// now store information for rendering /////

    // get axis-aligned bounding-box of node
    Point3 minP( float(leaf.min[0]), float(leaf.min[2]), float(-leaf.min[1]) ),
           maxP( float(leaf.max[0]), float(leaf.max[2]), float(-leaf.max[1]) );
    aabb = AABB(minP, maxP);

    // if cluster is negative, leaf is invalid, so do not load geometry
    if ( leaf.cluster < 0 )
      return;

    // extract # of leaf faces
    int numLeafFaces = int(leaf.numLeafFaces);
    int firstFace    = int(leaf.leafFace);

    // if there are faces in this leaf, create a face container to store
    // visible static geometry
    if ( numLeafFaces > 0 ) {
      faceContainer = new FaceContainer;

      if ( NULL == faceContainer )
        throw std::runtime_error("BSP::Node::Node(): "
                                 "unable to allocate storage for faces");
    }

    // loop through each face and add to triangle list
    for ( int i=0; i < numLeafFaces; i++ ) {
      // get reference to face
      const Q3Map::Face &face = q3map.getFace( q3map.getLeafFace(firstFace + i) );

      // get texture index
      int tex = int(face.texture);

      // if face has caulk texture, face should be ignored
      if ( strncmp("caulk", q3map.getTexture(tex).name, 5) == 0 )
        continue;
      
      if ( 1 == face.type || 3 == face.type ) {
        // this is a polygon or a mesh face

        int numMeshVerts  = int(face.numMeshVerts);

        FaceContainer::Face tempFace( int(face.numMeshVerts),
                                      int(face.lightMapIndex) );

        // iterate through each triangle of face and compute tangent vectors
        for ( int k=0; k < numMeshVerts; k+=3 ) {
          // vertex order is flipped to maintain counter-clockwise vertex order
          Q3Map::Vertex v[3]= { q3map.getVertex( face.vertex + q3map.getMeshVert(face.meshVert+k+2) ),
                                q3map.getVertex( face.vertex + q3map.getMeshVert(face.meshVert+k+1) ),
                                q3map.getVertex( face.vertex + q3map.getMeshVert(face.meshVert+k  ) ) };

          // convert vertex position to native right-handed coordinate system
          // (and convert texture coordinates also)
          for ( int l=0; l < 3; l++ ) {
            float tmp = v[l].pos[2];
            v[l].pos[2] = -v[l].pos[1];
            v[l].pos[1] = tmp;

            v[l].surfaceTC[1] = 1.0f - v[l].surfaceTC[1];
          }

          // copy vertex positions and texture coordinates into vertex
          // format used by rendering system
          Video::Vertex renderVerts[3];
          for ( int l=0; l < 3; l++ ) {
            renderVerts[l].pos           = Math3D::Vector3<float>(v[l].pos);
            renderVerts[l].tc[0]         = v[l].surfaceTC[0];
            renderVerts[l].tc[1]         = v[l].surfaceTC[1];
          }

          // compute face tangent and normal from vertex positions and
          // texture coordinates
          Video::computeTangentAndNormal(renderVerts[0],
                                         renderVerts[1],
                                         renderVerts[2]);

          // insert vertices into face
          tempFace.setVertex(k  , renderVerts[0]);
          tempFace.setVertex(k+1, renderVerts[1]);
          tempFace.setVertex(k+2, renderVerts[2]);
        } // for (mesh verts)

        // store face for rendering
        faceContainer->insertFace( tempFace, int(face.texture) );
      } // if (polygon or mesh face)
      else if ( 2 == face.type ) {
        // this is a patch
        // TODO: add patch support
        continue;
			} // else-if (patch)
    } // for ( faces )

    pvsIndex = (int)leaf.cluster;
  } // if (leaf)
  else {
    // make sure node index is valid
    if ( nodeIndex >= q3map.getNumNodes() )
      throw std::runtime_error("BSP::Node::Node(): node index is >= "
                               "number of nodes");

    // get reference to node object
    const Q3Map::Node &node = q3map.getNode(nodeIndex);
    
    // get reference to splitting plane for this node
    const Q3Map::Plane &q3plane = q3map.getPlane( int(node.plane) );

    // convert plane normal to native coordinate system
    Vector3 n = Vector3(q3plane.normal[0],
                        q3plane.normal[2],
                       -q3plane.normal[1]);
    plane = Plane(n, q3plane.d);
       
    // create front subtree    
    front = new Node( q3map, leafNodes, int(node.children[0]) );

    if ( NULL == front )
      throw std::runtime_error("BSP::Node::Node(): unable to allocate memory "
                               "for front subtree");

    // create back subtree
    back = new Node( q3map, leafNodes, int(node.children[1]) );

    if ( NULL == back )
      throw std::runtime_error("BSP::Node::Node(): unable to allocate memory "
                               "for back subtree");
  } // if (not a leaf)
}


BSP::Node::Node() {
  numBrushes = 0;
  front = back = NULL;
  brushes = NULL;
  faceContainer = NULL;
  pvsIndex = -1;
}


BSP::Node::~Node() {
  if ( front != NULL )
    delete front;
  if ( back != NULL )
    delete back;
  if ( brushes != NULL )
    delete [] brushes;
  if ( faceContainer != NULL )
    delete faceContainer;
}


void BSP::Node::tessellateQ3Patch(const Q3Map &q3map,
                                  const Q3Map::Face &face) {
  // TODO
}


BSP::Node::Brush::Brush():
     numPlanes(0),
     planes(NULL) {
}


BSP::Node::Brush::~Brush() {
  if ( numPlanes > 0 && NULL != planes )
    delete [] planes;
}
