#ifndef _ViewCellBsp_H__
#define _ViewCellBsp_H__

#include "Mesh.h"
#include "Containers.h"
#include <queue>

class ViewCell;
class Plane3;
//class Mesh;

//namespace GtpVisibilityPreprocessor {
class BspTree;  
class BspInterior;
class Polygon;

  /**
     BspNode abstract class serving for interior and leaf node implementation
  */
  class BspNode 
  {
	  friend BspTree;

  public:
	  /** Determines whether this node is a leaf or not
	  @return true if leaf
	  */
	  virtual bool IsLeaf() const = 0;
    
	  /** Determines whether this node is a root
	  @return true if root
	  */
	  virtual bool IsRoot() const;

	  /** Returns parent node.
	  */
	  BspInterior *GetParent();
	  
  protected:

	  /// parent of this node
	  BspInterior *mParent;
  };

  /** BSP interior node implementation 
  */
  class BspInterior : public BspNode 
  {
  public:
	  /** Standard contructor taking split plane as argument.
	  */
	  BspInterior(Plane3 plane);
	  /** @return false since it is an interior node 
	  */
	  bool IsLeaf() const;

	  BspNode *GetBack();
	  BspNode *GetFront();

	  Plane3 *GetPlane();

	  void ReplaceChildLink(BspNode *oldChild, BspNode *newChild);
	  void SetupChildLinks(BspNode *b, BspNode *f);

  protected:
		
	  /// Splitting plane corresponding to this node
	  Plane3 mPlane;
	  /// back node
	  BspNode *mBack;
	  /// front node
	  BspNode *mFront;
  };
  
  
  /** BSP leaf node implementation */
  class BspLeaf : public BspNode 
  {
  public:
	  BspLeaf(ViewCell *viewCell = NULL);
    
	  /** @return true since it is an interior node */
	  bool IsLeaf() const;
	  ViewCell *GetViewCell();

  protected:
   
	  /// polygonal representation of this viewcell
	  /// if NULL this note does not correspond to feasible viewcell
	  ViewCell *mViewCell;
  };
  
  typedef std::queue<Polygon *> PolygonQueue;

  /** Class representing a polygon.
  */
  class Polygon
  {
  public:
	  Polygon();
	  Polygon(const VertexContainer &vertices);

	  /** Copies all the vertices of the face.
	  */
	  Polygon(Face *face, Mesh *parent);
	 
	   /** Returns supporting plane of this polygon.
	  */
	  Plane3 GetSupportingPlane();

	  /** Splits polygon.
		  @param partition the split plane
		  @param front the front polygon
		  @param back the back polygon
	  */
	  void Split(Plane3 *partition, Polygon *front, Polygon *back);

	  enum {BACK_SIDE, FRONT_SIDE, SPLIT, COINCIDENT};

	  /** Side of the plane where the polygon is located.
	      @returns one of BACK_SIDE, FRONT_SIDE, SPLIT, COINCIDENT
	  */
	  int Side(Plane3 *plane);

	  static void DeletePolygons(PolygonQueue *polys);

	  /// vertices are connected in counterclockwise order.
	  VertexContainer mVertices;
  };

  /** Implementation of the ViewCell BSP tree. */
  class BspTree 
  {
  public:
	 	  
	  /** Additional data which is passed down the BSP tree during traversal.
	  */
	  struct BspTraversalData
	  {  
		  /// the current node
		  BspNode *mNode;
		  /// parent of current node
		  BspInterior *mParent;
		  /// polygonal data for splitting
		  PolygonQueue *mPolys;
		  /// current depth
		  int mDepth;
		      
		  BspTraversalData() {}
		  
		  BspTraversalData(BspNode *node, BspInterior *parent, PolygonQueue *polys, const int depth): 
		  mNode(node), mParent(parent), mPolys(polys), mDepth(depth) {}
      };


	  /** Constructs BSP tree from list of view cells.
	  */ 
	  BspTree(const ViewCellContainer &viewCells);
	  /** Constructs BSP tree from list of objects.
		  @param object list of intersectables
		  @param maxPolys maximal allowed number of polygons
		  @param maxDepth maximal allowed BSP tree depth
	  */
	  BspTree(const ObjectContainer &objects, int maxPolys, int maxDepth);
  
	  ~BspTree();

  protected:
	  /** Selects a splitting plane from the given polygons. 
	  */
	  Plane3 SelectPlane(PolygonQueue *polyQueue);

	  /** Filters next viewcell down the tree and inserts it into the appropriate leaves
		  (i.e., possibly more than one leaf).
	  */
	  void InsertViewCell(ViewCell *viewCell);

	  /** Subdivides tree according to the given list of viewcells.
	  */
	  void Subdivide(const ViewCellContainer &viewCells);
	  /** Subdivides tree according to the given list of objects.
	  */
	  void Subdivide(const ObjectContainer &objects);
	   
	  /** Subdivides leaf.
		  @param leaf the leaf to be subdivided
		  @param parent the parent node of this leaf
		  @param polys the input polygons
		  @param depth the current tree depth
		  @param frontPolys the polygons of the front child node as a result from splitting
		  @param backPolys the polygons of the back child node as a result from splitting
	  */
	  BspNode *SubdivideNode(BspLeaf *leaf, BspInterior *parent, 
							 PolygonQueue *polys, const int depth, 
							 PolygonQueue *frontPolys, PolygonQueue *backPolys);

	  /** Extracts the mesh instances of the objects and copies them into the mesh.
	  */
	  static void Copy2PolygonSoup(const ObjectContainer &objects, PolygonQueue &polys);

	  static void CopyMesh2Polygon(Mesh *mesh, PolygonQueue &polys);

	  /// Pointer to the root of the tree
	  BspNode *mRoot;
	  /// Pointer to the root cell of the viewspace
	  // ViewCell *mRootCell;
	  /// maximal number of polygons allowed in leaf
	  int mMaxPolys;
	  /// maximal depth
	  int mMaxDepth;
  };
  
//}; // GtpVisibilityPreprocessor

#endif