/***************************************************************************
 *   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.             *
 ***************************************************************************/

#ifndef BSP_H
#define BSP_H

#include <cstddef>
#include <vector>
#include <map>
#include <set>
#include "common.h"
#include "Entity.h"
#include "Q3Map.h"
#include "Camera.h"
#include "FaceContainer.h"


// BSP that is used to accelerate both collision detection and rendering
class BSP {
public:
  BSP();
  ~BSP();

  void clear();
  void loadQ3Map(const Q3Map &q3map);
  void insertEntity(Entity *entity);
  void insertLight(const Video::Light &l);
  void updateEntities(float dt);
  void render(const Camera &camera);
  bool checkCollisions(const Entity *entity,
                       const Point3 &startPos, const Point3 &endPos,
                       float &hitFraction, Vector3 &hitNormal) const;

  // accessor methods for entities
  inline size_t        getNumEntities()    const { return entities.size(); }
  inline const Entity* getEntity(size_t i) const { return entities[i];     }
  inline Entity*       getEntity(size_t i)       { return entities[i];     }
protected:
  inline bool potentiallyVisible(int pvsIndex1, int pvsIndex2) const;

  class Node {
  public:
    Node();
    Node(const Q3Map &q3map, 
         std::vector<Node *> &leafNodes,
         int nodeIndex);
    ~Node();

    inline bool isLeaf() const { return NULL == front && NULL == back; }
    inline const Plane& getPlane() const { return plane; }
    inline const AABB& getAABB() const { return aabb; }
    inline int getPVSIndex() const { return pvsIndex; }

    inline Node* getFront() { return front; }
    inline Node* getBack()  { return back;  }

    inline void insertEntity(Entity *entity) { entities.insert(entity); }
    inline void insertLight(const Video::Light &l) { lights.push_back(l); }

    void render(const int *texIDs,
                const int *normalMapIDs);
    void traceEntity(const Entity *entity,
                     const AABB &aabbStart, const AABB &aabbEnd,
                     float &hitFraction, Vector3 &hitNormal) const;
    const Node* tracePoint(const Point3 &p) const;
    Node *tracePoint(const Point3 &p);
  protected:
    void tessellateQ3Patch(const Q3Map &q3map, const Q3Map::Face &face);

    void checkBrushAABB(const Plane *planes, int numPlanes,
                        const AABB &aabbStart, const AABB &aabbEnd,
                        float &hitFraction, Vector3 &hitNormal) const;
    void checkBrushesAABB(const AABB &aabbStart, const AABB &aabbEnd,
                          float &hitFraction, Vector3 &hitNormal) const;
    void checkEntitiesAABB(const Entity *entity,
                           const AABB &aabbStart, const AABB &aabbEnd,
                           float &hitFraction, Vector3 &hitNormal) const;

    // container for collision information
    // (Brush - convex volume defined by the intersection of n planes)
    class Brush {
    public:
      Brush();
      ~Brush();

      int numPlanes;
      Plane *planes;
    };

    // splitting plane
    Plane plane;

    // axis-aligned bounding box of node
    AABB aabb;

    // front and back subtrees
    Node *front, *back;

    int numBrushes;
    Brush *brushes;

    // rendering information (only used in leafs)
    FaceContainer *faceContainer;
    int pvsIndex;

    std::set<Entity *> entities;
    std::vector<Video::Light> lights;
  };

  Node *root;
  std::vector<Node *> leafNodes;
  int numTextures;
  int *texIDs;
  int *normalMapIDs;
  int pvsWidth;
  char *pvs;
  std::vector<Entity *> entities;
};


// determines if one leaf is potentially visible from another using
// data in pvs
bool BSP::potentiallyVisible(int pvsIndex1, int pvsIndex2) const {
  if ( NULL == pvs   || pvsIndex1 == pvsIndex2 ||
       pvsIndex1 < 0 || pvsIndex2 < 0 )
    return true;

  int bitIndex = pvsIndex1*pvsWidth + (pvsIndex2 >> 3);

  return ( pvs[bitIndex] & (1 << (pvsIndex2 & 7)) ) == 0;
}


#endif
