#ifndef _ViewCellsManager_H__
#define _ViewCellsManager_H__

#include "Ray.h"
#include "VssRay.h"
#include "Containers.h"
#include "ViewCell.h"
#include "ViewCellBsp.h"

class ViewCell;
class Intersectable;
class RenderSimulator;
class Renderer;
class Mesh;
struct Triangle3;
class SimulationStatistics;
class BspTree;
class KdTree;
class VspKdTree;
class VspBspTree;
class KdNode;
class KdLeaf;
class VspKdTree;
class AxisAlignedBox3;
class BspLeaf;
class ViewCellsStatistics;
class Exporter;
class Beam;
class Preprocessor;
class ViewCellsTree;
class MergeCandidate;

struct BspRay;


/** Probably Visible Set */
class PrVs 
{
public:
  /// root of view cells tree
  ViewCell *mViewCell;

  // input parameter is the render budget for the PrVS
  float mRenderBudget;

  /// some characteristic values could be here
  
};

/**
	Manages different higher order operations on the view cells.
*/
class ViewCellsManager
{
public:
	struct PvsStatistics 
	{
		int minPvs;
		int maxPvs;
		float avgPvs;
		int viewcells;
  };

	/// view cell container types
	enum {BSP, KD, VSP_KD, VSP_BSP};
  
	/// view cells evaluation type
	enum {PER_OBJECT, PER_TRIANGLE};

	/** Constructor taking the initial and construction samples.
		@param initialSamples the maximal number of samples used for creating the hierarchy
		of view cells
		@param constructionSamples the maximal number of samples used for construction
	*/
	ViewCellsManager(const int initialSamples, const int constructionSamples);

	ViewCellsManager();

	virtual ~ViewCellsManager();

	/** Constructs view cells container taking a preprocessor
		@returns the output rays (if not null)
	*/ 
	int Construct(Preprocessor *preprocessor, VssRayContainer *outRays = NULL);

	/** Constructs view cell container with a given number of samples.
	*/
	virtual int ConstructSubdivision(const ObjectContainer &objects, 
						  const VssRayContainer &rays) = 0;

	/** Computes sample contributions of the rays to the view cells PVS.
	
		@param rays bundle of rays used to find intersections with view cells and 
		adding the contribution
		@param addRays true if rays should be added to the PVSs of the viewcells they
		intersect 
		@param storeViewCells true if view cells should be stored in the ray
	*/
	float ComputeSampleContributions(const VssRayContainer &rays,
								   const bool addContributions,
								   const bool storeViewCells);

	/** Add sample contributions to the viewcells they intersect */
	void AddSampleContributions(const VssRayContainer &rays);
  

	/** Computes sample contribution of a simgle ray to the view cells PVS.
		@param ray finds intersections with view cells and holds the contribution
		@param castRay true if ray should be cast to gain the information, false if ray
		is already holding the information and need not be recast.
	  
		@returns number of sample contributions
	*/
	virtual float ComputeSampleContributions(VssRay &ray, 
											 const bool addRays, 
											 const bool storeViewCells);

	virtual void AddSampleContributions(VssRay &ray);

	/** Prints out statistics of the view cells.
	*/
	virtual void PrintStatistics(ostream &s) const;

	/** Post processes view cells givem´a number of rays.
	*/
	virtual int PostProcess(const ObjectContainer &objects, 
							const VssRayContainer &rays) = 0;

	/** Show visualization of the view cells.
	*/
	virtual void Visualize(const ObjectContainer &objects,
						   const VssRayContainer &sampleRays) = 0;

	/** type of the view cell container.
	*/
	virtual int GetType() const = 0;

	/** Load the input viewcells. The input viewcells should be given as a collection
		of meshes. Each mesh is assume to form a bounded polyhedron defining the interior of
		the viewcell. The method then builds a BSP tree of these view cells.
		
		@param filename file to load
		@return true on success
    */
    virtual bool LoadViewCellsGeometry(const string filename);

	
	/** Constructs view cell from base triangle. The ViewCell is extruded along the normal vector.
		@param the base triangle
		@param the height of the newly created view cell
	*/
	ViewCell *ExtrudeViewCell(const Triangle3 &baseTri, const float height) const;

	/** Merges two view cells.
		@note the piercing rays of the front and back will be ordered	
		@returns new view cell based on the merging.
	*/
	ViewCellInterior *MergeViewCells(ViewCell *front, ViewCell *back) const;

	/** Merges a container of view cells.
		@returns new view cell based on the merging.
	*/
	ViewCellInterior *MergeViewCells(ViewCellContainer &children) const;
	
	/** Generates view cell of type specified by this manager
	*/
	virtual ViewCell *GenerateViewCell(Mesh *mesh = NULL) const = 0;

	/** Adds a new view cell to the list of predefined view cells.
	*/
	void AddViewCell(ViewCell *viewCell);

	/** Derive view cells from objects.
	*/
	void DeriveViewCells(const ObjectContainer &objects, 
						 ViewCellContainer &viewCells, 
						 const int maxViewCells) const;

	/** Sets maximal number of samples used for the 
		construction of the view cells.
	*/
	void SetVisualizationSamples(const int visSamples);

	/** Sets maximal number of samples used for the construction of the view cells.
	*/
	void SetConstructionSamples(const int constructionSamples);

	/** Sets maximal number of samples used for the visualization of the view cells.
	*/
	void SetInitialSamples(const int initialSamples);

	/** Sets maximal number of samples used for the post processing of the view cells.
	*/
	void SetPostProcessSamples(const int postProcessingSamples);

	/** See set.
	*/
	int GetVisualizationSamples() const;

	/** See set.
	*/
	int GetConstructionSamples() const;

	/** See set.
	*/
	int GetPostProcessSamples() const;

	/** Returns true if view cells wer already constructed.
	*/
	virtual bool ViewCellsConstructed() const = 0;

	/** cast line segment to get a list of unique viewcells which are intersected
		by this line segment 
	*/
  
	virtual int CastLineSegment(const Vector3 &origin,
							  const Vector3 &termination,
							  ViewCellContainer &viewcells
							  ) = 0;

	virtual void GetPvsStatistics(PvsStatistics &stat);

	virtual void GetPrVS(const Vector3 &viewPoint, PrVs &prvs);
  
	/** Get a viewcell containing the specified point 
	*/
	virtual ViewCell *GetViewCell(const Vector3 &point) const = 0;
  
	virtual void PrintPvsStatistics(ostream &s);

	/** Updates pvs of the view cell hierarchy if necessary.
	*/
	void UpdatePvs();

	/** Returns probability that view point lies in one view cell.
	*/
	virtual float GetProbability(ViewCell *viewCell) = 0;

	/** Returns render cost of a single view cell given the render cost of an object.
	*/
	float GetRendercost(ViewCell *viewCell) const;

	/** Returns reference to container of loaded / generated view cells.
	*/
	ViewCellContainer &GetViewCells();

	/** Helper function used to split ray sets uniformly 
		into one that is currently used and the other that 
		is saved for later processing.
		@param sourceRays the input ray set
		@param maxSize the maximal number of rays that will be used
		@param usedRays returns the used ray set
		@param savedRays if not null, returns the saved ray set
	*/
	void GetRaySets(const VssRayContainer &sourceRays,
					const int maxSize,
					VssRayContainer &usedRays, 
					VssRayContainer *savedRays = NULL) const;
	
	/** Returns accumulated area of all view cells.
	*/
	float GetAccVcArea();

	/** Returns area of one view cell.
	*/
	virtual float GetArea(ViewCell *viewCell) const;

	/** Returns volume of view cell.
	*/
	virtual float GetVolume(ViewCell *viewCell) const;

	/** Sets the current renderer mainly for view cells statistics.
	*/
	void SetRenderer(Renderer *renderer);

	/** Computes a (random) view point in the valid view space.
		@returns true if valid view point was found
	*/
	virtual bool GetViewPoint(Vector3 &viewPoint) const;

	/** Returns true if this view point is in the valid view space.
	*/
	virtual bool ViewPointValid(const Vector3 &viewPoint) const;

	/** Sets a view space boundary.
	*/
	void SetViewSpaceBox(const AxisAlignedBox3 &box);

	AxisAlignedBox3 GetViewSpaceBox() const;

	/** Creates mesh for this view cell.
	*/
	virtual void CreateMesh(ViewCell *vc) = NULL;

	/** Writes view cells to disc.
	*/
	virtual bool ExportViewCells(const string filename);

	/** Casts beam to collect view cells.
	*/
	virtual int CastBeam(Beam &beam);

	/** Checks if view cell is considered as valid.
	*/
	virtual bool CheckValidity(ViewCell *vc, 
							   int minPvsSize, 
							   int maxPvsSize) const;

	
	/** Sets validity of view cell
	*/
	virtual void SetValidity(ViewCell *vc, 
							 int minPvsSize, 
							 int maxPvsSize) const;

	/** sets validy of all viewcells 
	*/
  	virtual void SetValidity(int minPvsSize, 
							 int maxPvsSize) const;


	/** set valid viewcells in the range of pvs. sorts the viewcells
	  according to the pvs and then pickups those in the ranges 
	  */
	void SetValidityPercentage(const float minValid, const float maxValid);

    int CountValidViewcells() const;

	/** Returns maximal allowed pvs size.
	*/
	int GetMaxPvsSize() const;

	/** Returns maximal allowed pvs size.
	*/
	int GetMinPvsSize() const;

	/** Returns maximal ratio. i.e., currentPVs / maxPvs,
		where pvs is still considered valid.
	*/
	float GetMaxPvsRatio() const;

	/** Exports view cell geometry.
	*/
	virtual void ExportViewCellGeometry(Exporter *exporter, 
										ViewCell *vc,
										const Plane3 *clipPlane = NULL) const = 0;

	virtual void FinalizeViewCells(const bool createMesh);


	/** Loads view cells from file. The view cells manager is created with 
		respect to the loaded view cells.

		@returns the view cells manager if loading was successful, false otherwise
	*/
	static ViewCellsManager *LoadViewCells(const string filename, 
										   ObjectContainer *objects);

	/** Evaluates statistics values on view cells.
	*/
	void EvaluateRenderStatistics(float &totalRenderCost,
								  float &expectedRenderCost,
								  float &deviation,
								  float &variance,
								  int &totalPvs,
								  float &avgRenderCost);


	/** Returns hierarchy of the view cells.
	*/
	ViewCellsTree *GetViewCellsTree();

	virtual void CollectMergeCandidates(const VssRayContainer &rays, 
										vector<MergeCandidate> &candidates) = 0;

	void CollectViewCells(const int n);

	/** Returns true if this (logical) view cell is equal to a spatial node.
	*/
	virtual bool EqualToSpatialNode(ViewCell *viewCell) const;

	/** Sets current view cells set to active, i.e., the sampling is done in this view cell set.
	*/
	void SetViewCellsActive();

	/** Evaluates worth of current view cell hierarchy.
	*/
	void EvalViewCellPartition(Preprocessor *preprocessor);

	/** Sets maximal size of a view cell filter.
	*/
	void SetMaxFilterSize(const int size);

  int GetMaxFilterSize() {
	return mMaxFilterSize;
  }

  /** deletes interior nodes from the tree which have negative merge cost set (local merge) */
  void
  DeleteLocalMergeTree(ViewCell *vc
					   ) const;
  
	/** Evaluautes histogram for a given number of view cells.
	*/
	void EvalViewCellHistogram(const string filename, const int nViewCells);

	/** Evaluautes histogram for a given number of view cells.
	*/
	void EvalViewCellHistogramForPvsSize(const string filename, const int nViewCells);

	/** Evaluates the render cost of a view cell.
	*/
	float EvalRenderCost(Intersectable *obj) const;

protected:

	/** Returns the bounding box of filter width.
	*/
	AxisAlignedBox3 GetFilterBBox(const Vector3 &viewPoint, const float width) const;

	/** Intersects box with the tree and returns the number of intersected boxes.
		@returns number of view cells found
	*/
	virtual int ComputeBoxIntersections(const AxisAlignedBox3 &box, 
										ViewCellContainer &viewCells) const;

	virtual void TestFilter(const ObjectContainer &objects) {};

	/**
		if the view cells tree was already constructed or not.
	*/
	bool ViewCellsTreeConstructed() const;

	int CastPassSamples(const int samplesPerPass, 
						const int sampleType, 
						VssRayContainer &vssRays) const;

	void ParseEnvironment();

	/** Creates unique view cell ids.
	*/
	void CreateUniqueViewCellIds();

	/** Finalizes, i.e., creates mesh, volume, area etc. for the view cell.
	*/
	virtual void Finalize(ViewCell *viewCell, const bool createMesh);

	/** Recollects view cells and resets statistics.
	*/
	void ResetViewCells();
	
	/** Collects the view cells in the view cell container.
	*/
	virtual void CollectViewCells() = 0;
	
	/** Evaluates view cells statistics and stores it in
		mViewCellsStatistics.
	*/
	void EvaluateViewCellsStats();

	//-- helper functions for view cell visualization

	/** Exports the view cell partition.
	*/
	void ExportViewCellsForViz(Exporter *exporter) const;

	/** Sets exporter color.
	*/
	virtual void ExportColor(Exporter *exporter, ViewCell *vc) const = 0;


	virtual float GetViewSpaceVolume();
	
	/** Creates meshes from the view cells.
	*/
	void CreateViewCellMeshes();

	/** Takes different measures to prepares the view cells after loading them from disc.
	*/
	virtual void PrepareLoadedViewCells() {};

	/** Constructs local view cell merge hierarchy.
	*/
	ViewCell *ConstructLocalMergeTree(ViewCell *currentViewCell, 
									  const ViewCellContainer &viewCells);

	/** Constructs local view cell merge hierarchy based solely on similarity with the
		current viewcell
	*/
  	ViewCell *ConstructLocalMergeTree2(ViewCell *currentViewCell, 
									   const ViewCellContainer &viewCells);
  

	/** Creates clip plane for visualization.
	*/
	void CreateClipPlane();

	virtual void UpdatePvsForEvaluation(ViewCell *root, ObjectPvs &pvs) = 0;


	int mPvsExportMode;

	Plane3 mClipPlane;

	bool mUseClipPlaneForViz;


	/// Renders the view cells.
	Renderer *mRenderer;

	/// Loaded view cells
	ViewCellContainer mViewCells;

	ViewCellsTree *mViewCellsTree;

	bool mPruneEmptyViewCells;

	bool mViewCellPvsIsUpdated;
	/// maximum number of samples taken for construction of the view cells
	int mConstructionSamples;
	int mSamplesPerPass;
	int mInitialSamples;
	int mPostProcessSamples;
	int mVisualizationSamples;

	float mTotalAreaValid;
	float mTotalArea;

	int mMaxPvsSize;
	int mMinPvsSize;
	float mMaxPvsRatio;

	int mSamplingType;
	int mEvaluationSamplingType;
	int mNumActiveViewCells;
	bool mCompressViewCells;

	ViewCellsStatistics mCurrentViewCellsStats;
	/// the scene bounding box
	AxisAlignedBox3 mViewSpaceBox;
	/// holds the view cell meshes
	MeshContainer mMeshContainer;
	/// if view cells should be exported
	bool mExportViewCells;

	//bool mMarchTree);
	bool mOnlyValidViewCells;

	/// if rays should be used to collect merge candidates
	bool mUseRaysForMerge;
	/// merge the view cells?
	bool mMergeViewCells;

	/// the width of the box filter
	float mFilterWidth;
	int mMaxFilterSize;

	//-- visualization options
	
	/// color code for view cells
	int mColorCode;
	bool mExportGeometry;
	bool mExportRays;

	bool mViewCellsFinished;

	bool mEvaluateViewCells;

	bool mShowVisualization;

	// HACK in order to detect empty view cells
	void CollectEmptyViewCells();
	void TestEmptyViewCells(const ObjectContainer &obj);

	ViewCellContainer mEmptyViewCells;

	int mRenderCostEvaluationType;
};



/**
	Manages different higher order operations on the view cells.
*/
class BspViewCellsManager: public ViewCellsManager
{

public:
	/** Constructor taking the bsp tree and the number of samples
		used to construct the bsp tree.
	*/
	BspViewCellsManager(BspTree *tree);

	~BspViewCellsManager();

	int ConstructSubdivision(const ObjectContainer &objects, 
				  const VssRayContainer &rays);

	int PostProcess(const ObjectContainer &objects, 
					const VssRayContainer &rays);

	void Visualize(const ObjectContainer &objects,
				   const VssRayContainer &sampleRays);

	int GetType() const;
	
	ViewCell *GenerateViewCell(Mesh *mesh = NULL) const;

	bool ViewCellsConstructed() const;

	//void PrintStatistics(ostream &s) const;

	int CastLineSegment(const Vector3 &origin,
						const Vector3 &termination,
						ViewCellContainer &viewcells);
	
	float GetProbability(ViewCell *viewCell);
	

	/** Get a viewcell containing the specified point */
	ViewCell *GetViewCell(const Vector3 &point) const;

	void CreateMesh(ViewCell *vc);

	void ExportViewCellGeometry(Exporter *exporter, 
								ViewCell *vc, 
								const Plane3 *clipPlane = NULL) const;
	
	void CollectMergeCandidates(const VssRayContainer &rays, 
								vector<MergeCandidate> &candidates);

	void Finalize(ViewCell *viewCell, const bool createMesh);

	bool ExportViewCells(const string filename);

	/** Constructs merge hierarchy which corresponds to the spatial hierarchy.
	*/
	ViewCell *ConstructSpatialMergeTree(BspNode *root);

	/** Updates the pvs in the view cells tree.
	*/
	void UpdatePvsForEvaluation(ViewCell *root, ObjectPvs &pvs);

protected:


	/** HACK
	*/
	void AddCurrentViewCellsToHierarchy();

	void CollectViewCells();

	void ExportColor(Exporter *exporter, ViewCell *vc) const;
	


	/// the BSP tree.
	BspTree *mBspTree;
	
	vector<BspRay *> mBspRays;

private:

	/** Exports visualization of the BSP splits.
	*/
	void ExportSplits(const ObjectContainer &objects);

	/** Exports visualization of the BSP PVS.
	*/
	void ExportBspPvs(const ObjectContainer &objects);

	void TestSubdivision();
};

/**
	Manages different higher order operations on the KD type view cells.
*/
class KdViewCellsManager: public ViewCellsManager
{

public:

	KdViewCellsManager(KdTree *tree);

	int ConstructSubdivision(const ObjectContainer &objects, 
				  const VssRayContainer &rays);

	int CastLineSegment(const Vector3 &origin,
						const Vector3 &termination,
						ViewCellContainer &viewcells);

	int PostProcess(const ObjectContainer &objects, 
					const VssRayContainer &rays);

	void Visualize(const ObjectContainer &objects,
				   const VssRayContainer &sampleRays);

	int GetType() const;

	bool ViewCellsConstructed() const;

	ViewCell *GenerateViewCell(Mesh *mesh) const;

	/** Prints out statistics of this approach.
	*/
	//  virtual void PrintStatistics(ostream &s) const;
	ViewCell *GetViewCell(const Vector3 &point) const { return NULL; }

	float GetProbability(ViewCell *viewCell);
	

	void CreateMesh(ViewCell *vc);

	void ExportViewCellGeometry(Exporter *exporter, 
								ViewCell *vc,
								const Plane3 *clipPlane = NULL) const;

	void CollectMergeCandidates(const VssRayContainer &rays, 
								vector<MergeCandidate> &candidates);


protected:

	virtual void UpdatePvsForEvaluation(ViewCell *root, ObjectPvs &pvs) {};
	/** Collects view cells from a hierarchy.
	*/
	void CollectViewCells();

	KdNode *GetNodeForPvs(KdLeaf *leaf);

	void ExportColor(Exporter *exporter, ViewCell *vc) const;


	/// the BSP tree.
	KdTree *mKdTree;

	/// depth of the KD tree nodes with represent the view cells
	int mKdPvsDepth;
};

/**
	Manages different higher order operations on the view cells 
	for vsp kd tree view cells.
*/
class VspKdViewCellsManager: public ViewCellsManager
{

public:

	VspKdViewCellsManager(VspKdTree *vspKdTree);

	int ConstructSubdivision(const ObjectContainer &objects, 
				  const VssRayContainer &rays);


	int PostProcess(const ObjectContainer &objects, 
					const VssRayContainer &rays);

	void Visualize(const ObjectContainer &objects,
				   const VssRayContainer &sampleRays);

	int GetType() const;
	
	bool ViewCellsConstructed() const;

	//virtual void PrintStatistics(ostream &s) const;

	ViewCell *GenerateViewCell(Mesh *mesh) const;


    int CastLineSegment(const Vector3 &origin,
						const Vector3 &termination,
						ViewCellContainer &viewcells);

	ViewCell *GetViewCell(const Vector3 &point) const { return NULL; }

	float GetProbability(ViewCell *viewCell);


	void CreateMesh(ViewCell *vc);

	void ExportViewCellGeometry(Exporter *exporter, 
								ViewCell *vc,
								const Plane3 *clipPlane = NULL) const;

	void CollectMergeCandidates(const VssRayContainer &rays, vector<MergeCandidate> &candidates);

	virtual void UpdatePvsForEvaluation(ViewCell *root, ObjectPvs &pvs) {};
protected:

	void ExportLeaves(const ObjectContainer &objects,
					  const VssRayContainer &sampleRays);

	void CollectViewCells();

	void ExportColor(Exporter *exporter, ViewCell *vc) const;



	/// the BSP tree.
	VspKdTree *mVspKdTree;
};



/**
	Manages different higher order operations on the view cells.
*/
class VspBspViewCellsManager: public ViewCellsManager
{

public:

	VspBspViewCellsManager(VspBspTree *tree);
	~VspBspViewCellsManager();

	int ConstructSubdivision(const ObjectContainer &objects, 
				  const VssRayContainer &rays);

	int PostProcess(const ObjectContainer &objects, 
					const VssRayContainer &rays);

	void Visualize(const ObjectContainer &objects,
				   const VssRayContainer &sampleRays);

	int GetType() const;
	
	ViewCell *GenerateViewCell(Mesh *mesh = NULL) const;

	bool ViewCellsConstructed() const;

	
	int CastLineSegment(const Vector3 &origin,
						const Vector3 &termination,
						ViewCellContainer &viewcells);

	float GetProbability(ViewCell *viewCell);
	
	ViewCell *GetViewCell(const Vector3 &point) const;

	bool GetViewPoint(Vector3 &viewPoint) const;

	bool ViewPointValid(const Vector3 &viewPoint) const;

	void CreateMesh(ViewCell *vc);

	bool ExportViewCells(const string filename);

	int CastBeam(Beam &beam);

	void ExportViewCellGeometry(Exporter *exporter, 
								ViewCell *vc,
								const Plane3 *clipPlane = NULL) const;

	//float GetVolume(ViewCell *viewCell) const;

	void Finalize(ViewCell *viewCell, const bool createMesh);

	void CollectMergeCandidates(const VssRayContainer &rays, vector<MergeCandidate> &candidates);

	/** Returns true if this view cell is equivavalent to a spatial node.
	*/
	bool EqualToSpatialNode(ViewCell *viewCell) const;


protected:

	int ComputeBoxIntersections(const AxisAlignedBox3 &box, ViewCellContainer &viewCells) const;
	
	/** Returns node of the spatial hierarchy corresponding to the view cell
		if such a node exists.
	*/
	BspNode *GetSpatialNode(ViewCell *viewCell) const;

	/** HACK
	*/
	void AddCurrentViewCellsToHierarchy();

	/** Merges the view cells.
	*/
	void MergeViewCells(const VssRayContainer &rays, 
						const ObjectContainer &objects);
	
	void RefineViewCells(const VssRayContainer &rays, const ObjectContainer &objects);

	void CollectViewCells();

	/** Returns maximal depth difference of view cell 
		leaves in tree.
	*/
	int GetMaxTreeDiff(ViewCell *vc) const;
	

	void ExportColor(Exporter *exporter, ViewCell *vc) const;

	/** Prepare view cells for use after loading them from disc.
	*/
	void PrepareLoadedViewCells();

	/** Constructs merge hierarchy which corresponds to the spatial hierarchy.
	*/
	ViewCell *ConstructSpatialMergeTree(BspNode *root);

	void UpdatePvsForEvaluation(ViewCell *root, ObjectPvs &pvs);


	// HACK
	void TestFilter(const ObjectContainer &objects);



	/// the view space partition BSP tree.
	VspBspTree *mVspBspTree;


private:

	/** Exports visualization of the BSP splits.
	*/
	void ExportSplits(const ObjectContainer &objects, 
					  const VssRayContainer &rays);

	/** Exports visualization of the BSP PVS.
	*/
	void ExportBspPvs(const ObjectContainer &objects,
					  const VssRayContainer &rays);

	void TestSubdivision();
};


class ViewCellsManagerFactory
{

public:

	ViewCellsManager *Create(const string mName);

};

#endif