#ifndef _ViewCell_H__
#define _ViewCell_H__

#include "Mesh.h"
#include "Containers.h"
#include "Ray.h"
#include "Statistics.h"
#include "Material.h"
#include "gzstream.h"
#include "ObjectPvs.h"

namespace GtpVisibilityPreprocessor {

struct Triangle3;

class BspInterior;
class BspPvs;
class BspLeaf;
class VspLeaf;
class KdLeaf;
class ViewCellInterior;
class MergeCandidate;
class ViewCellsManager;
class ViewCellLeaf;



/** Statistics for a view cell partition.
*/
class ViewCellsStatistics: public StatisticsBase
{
public:

	/// number of view cells
	int viewCells;
	/// cost of the PVS
	float pvsCost;
	/// largest PVS of all view cells
	float maxPvs;
	/// smallest PVS of all view cells
	float minPvs;
	/// view cells with empty PVS
	int emptyPvs;
	/// number of leaves covering the view space
	int leaves;
	/// largest number of leaves covered by one view cell
	int maxLeaves;
	/// number of invalid view cells
	int invalid;

    // Constructor
	ViewCellsStatistics()
	{
		Reset();
	}

	double AvgLeaves() const {return (double)leaves / (double)viewCells;};
	double AvgPvs() const {return (double)pvsCost / (double)viewCells;};

	void Reset()
	{
		viewCells = 0;
		pvsCost = 0;
		maxPvs = 0;

		minPvs = 999999;
		emptyPvs = 0;
		leaves = 0;
		maxLeaves = 0;
		invalid = 0;
	}

	void Print(std::ostream &app) const;

	friend std::ostream &operator<<(std::ostream &s, const ViewCellsStatistics &stat)
	{
		stat.Print(s);
		return s;
	}
};


/** Statistics for a view cells tree.
*/
class ViewCellsTreeStats
{
public:
	int mPass;
    
	int mNumViewCells;
		
	float mRenderCostDecrease;

    float mTotalRenderCost;
    
	float mCurrentPvsCost;
							
	float mExpectedCost;
    
	float mAvgRenderCost;
	
	float mDeviation;
			
	float mTotalPvsCost;
	
	int mEntriesInPvs;
    
	float mMemoryCost;
	
	int mPvsSizeDecr;
  
	float mVolume;


	void Reset()
	{
		mPass = 0;
		mNumViewCells = 0;
		mRenderCostDecrease = 0;
		mTotalRenderCost = 0;
		mCurrentPvsCost = 0;
		mExpectedCost = 0;
		mAvgRenderCost = 0;
		mDeviation = 0;
		mTotalPvsCost = 0;
		mEntriesInPvs = 0;
		mMemoryCost = 0;
		mPvsSizeDecr = 0;
		mVolume = 0;
	}


	void Print(std::ostream &app) const;

	friend std::ostream &operator<<(std::ostream &s, const ViewCellsTreeStats &stat)
	{
		stat.Print(s);
		return s;
	}
};


/** This class represents a view cell, which is a region in view space. 
	The objects seen by the view cell are stored in a pvs.
	A view cell can be represented in many different ways, e.g., as a mesh.
*/
class ViewCell: public MeshInstance
{
	friend class ViewCellsTree;
	friend class ViewCellsManager;

public:

	ViewCell();
	/** Constructor taking a mesh representing the shape of	the viewcell.
	*/
	ViewCell(Mesh *mesh);
	/** Default destructor.
	*/
	virtual ~ViewCell();
	/** Returns const reference to pvs.
	*/
	const ObjectPvs &GetPvs() const;
	/** Returns reference to pvs.
	*/
	ObjectPvs &GetPvs();
	/** Completely substitutes the pvs.
	*/
	void SetPvs(const ObjectPvs &pvs);
	/** Type of view cell.
	*/
	int Type() const;
	/** Adds a passing ray to the passing ray container.
	*/
	void AddPassingRay(const Ray &ray, const int contributions);
	/** Returns volume of the view cell.
	*/
	inline float GetVolume() const
	{
		return mVolume;
	}
	/** Sets the volume of the view cell.
	*/
	inline void SetVolume(float volume)
	{
		mVolume = volume;
	}
	/** Returns area of the view cell.
	*/
	inline float GetArea() const
	{
		return mArea;
	}
	/** Sets the area of the view cell.
	*/
	void SetArea(float area)
	{
		mArea = area;
	}
	/** if this view cell is the root of a view cell hierarchy
	*/
	bool IsRoot() const;
	/** Returns parent view cell.
	*/
	ViewCellInterior *GetParent() const;
	/** Sets parent of this view cell.
	*/
	void SetParent(ViewCellInterior *parent);
	/** Sets the mesh for this view cell.
	*/
	void SetMesh(Mesh *mesh);
	/** Sets this view cell to be a valid view cell according to some criteria.
	*/
	void SetValid(const bool valid);
	/** Returns true if this view cell is considered to be valid according to
		some criteria.
	*/
	bool GetValid() const;
	/** Returns estimated render cost of this view cell.
	*/
	float GetRenderCost() const;
	/** set color for visiualizations.
	*/
	void SetColor(const RgbColor &color);
	/** get color for visualuzations.
	*/
    RgbColor GetColor() const;
	/** Adds a sample to the pvs.
		@param sample the sample to be added
		@param pdf a continuos measure of visibility
		@param contribution returns the contribution of this sample to the pvs
	*/
	bool AddPvsSample(Intersectable *sample, const float pdf, float &contribution);
	/** if this is a view cell correspending to a leaf in a hierarchy.
	*/
	virtual bool IsLeaf() const = 0;

	friend inline bool SmallerPvs(const ViewCell *a, const ViewCell *b);
	friend inline bool GreaterOrEqualPvs(const ViewCell *a, const ViewCell *b);
	friend inline bool SmallerRenderCost(const ViewCell *a, const ViewCell *b);
	friend inline bool LargerRenderCost(const ViewCell *a, const ViewCell *b);
	

	/** Sets merge cost used for merging this view cell from other cells. 
		@hack The function is available for leaves also to have a common interface,
		but it should be less than zero for leaves.
	*/
	void SetMergeCost(const float mergeCost);
	/** Returns merge cost needed to merge this leaf from other cells.
		@hack The function is available for leaves also to have a common interface,
		but it should be less than zero for leaves.
	*/
	float GetMergeCost() const;

	void UpdatePvsCost() {
		mPvsCost = GetPvs().EvalPvsCost();
	}

	void SetTrianglesInPvs(const float c) {
		mPvsCost = c;
	}

	void SetEntriesInPvs(const int e) {
		mEntriesInPvs = e;
	}

	float GetTrianglesInPvs() const {
		return mPvsCost;
	}

	int GetEntriesInPvs() const {
		return mEntriesInPvs;
	}

	int GetFilteredPvsSize() const 
	{
		return mFilteredPvsSize;
	}

	void SetFilteredPvsSize(const int s) {
		mFilteredPvsSize = s;
	}

	//virtual int ViewCellType;

protected:

	/// parent view cell in the view cell hierarchy
	ViewCellInterior *mParent;
	/// the potentially visible objects
	ObjectPvs mPvs;
	/// the volume of this view cell
	float mVolume;
	/// the area of this view cell
	float mArea;
	/// the cost that were paid for merging this view cells from two others.
	float mMergeCost;
	/// if the view cell is valid view space
	bool mValid;
	/// color used for consistent visualization
	RgbColor mColor;
	/// store pvs size, used for evaluation purpose when pvss are stored only in the leaves
	float mPvsCost;
	/// stores number of entries in pvs
	int mEntriesInPvs;
	/** if the pvs size scalar (+ entries into pvs)
		is up to date and corresponding to the real pvs size
	*/
	bool mPvsSizeValid;

	/// Filter cost of the pvs
	int mFilteredPvsSize;

};

inline bool SmallerPvs(const ViewCell *a, const ViewCell *b) 
{
	// HACK: take scalar value because pvs may not have been stored properly
#if 1
	return a->mPvsCost < b->mPvsCost;
#else
	return a->GetPvs().EvalPvsCost() < b->GetPvs().EvalPvsCost();
#endif
}

inline bool GreaterOrEqualPvs(const ViewCell *a, const ViewCell *b) 
{
	return !SmallerPvs(a, b);
}

inline bool SmallerRenderCost(const ViewCell *a, const ViewCell *b) 
{
	return a->GetRenderCost() < b->GetRenderCost();
}

inline bool LargerRenderCost(const ViewCell *a, const ViewCell *b) 
{
	return a->GetRenderCost() > b->GetRenderCost();
}

class ViewCellInterior: public ViewCell
{
	friend class ViewCellsManager;

public:
	ViewCellInterior();
	~ViewCellInterior();

	ViewCellInterior(Mesh *mesh);

	/** Sets pointer from parent to child and vice versa.
	*/
	void SetupChildLink(ViewCell *l);
	void ReplaceChildLink(ViewCell *prev, ViewCell *cur);

	void RemoveChildLink(ViewCell *l);
	bool IsLeaf() const;

	void SetCost(const float c) {
		mCost = c;
	}

	float GetCost() const {
		return mCost;
	}

	ViewCellContainer mChildren;

protected:

	/// Pverall cost resulting from the merge.
	float mCost;
};


/**
	Leaf of the view cell.
*/
class ViewCellLeaf: public ViewCell
{
public:
	
	ViewCellLeaf()  
	{  
		mActiveViewCell = this; 
	}
	
	ViewCellLeaf(Mesh *mesh): ViewCell(mesh) 
	{ 
		mActiveViewCell = this; 
	}

	bool IsLeaf() const
	{
		return true;
	}

	/** Returns active view cell, i.e. this view cell or
		a parent view cell which is set as active view cell.
	*/
	ViewCell *GetActiveViewCell() const 
	{ return mActiveViewCell; }

	/** Sets this view cell to be an active view cell.
	*/
	void SetActiveViewCell(ViewCell *vc)
	{ mActiveViewCell = vc;}
	
	/** points to the currently active view cell. This is the
		view cell representing the current brach.
	*/
	ViewCell *mActiveViewCell;
};


/** Leaf of the view cell hierarchy corresponding 
	to a leaf in a spatial hierarchy.
*/
template<typename T>
class HierarchyLeafViewCell: public ViewCellLeaf
{
public:

	HierarchyLeafViewCell<T>(): ViewCellLeaf() {  }
	HierarchyLeafViewCell<T>(Mesh *mesh):
	ViewCellLeaf(mesh) {  }
		
	bool IsLeaf() const
	{
		return true;
	}

	/// Leaves of some hierarchy which contains this view cell.
	vector<T> mLeaves;
};


typedef HierarchyLeafViewCell<VspLeaf *> VspViewCell;
typedef HierarchyLeafViewCell<BspLeaf *> BspViewCell;
typedef HierarchyLeafViewCell<KdLeaf *> KdViewCell;




class ViewCellsTree
{
	friend class ViewCellsManager;
	friend class ViewCellsParseHandlers;

public:

	/** Default constructor.
	*/
	ViewCellsTree();
	/** View cells tree constructor taking a view cell mnanager as parameter
	*/
	ViewCellsTree(ViewCellsManager *vcm);
	/** Destructor.
	*/
	~ViewCellsTree();
	/** Returns number of leaves this view cell consists of.
	*/
	int GetNumInitialViewCells(ViewCell *vc) const;
	/** Collects leaves corresponding to a view cell.
	*/
	void CollectLeaves(ViewCell *vc, ViewCellContainer &leaves) const;
	/** Merges view cells according to some cost heuristics.
	*/
	int ConstructMergeTree(const VssRayContainer &rays, const ObjectContainer &objects);
	/** Refines view cells using shuffling, i.e., border leaves 
		of two view cells are exchanged if the resulting view cells
		are tested to be "better" than the old ones.
		@returns number of refined view cells
	*/
	int RefineViewCells(const VssRayContainer &rays, const ObjectContainer &objects);
	/** Assign colors to the viewcells so that they can be renderered interactively without
	    color flickering.  
	*/
	void AssignRandomColors();
	/** Updates view cell stats for this particular view cell.
	*/
	void UpdateViewCellsStats(ViewCell *vc, ViewCellsStatistics &vcStat);
	/** Get costs resulting from each merge step. 
	*/
	void GetCostFunction(vector<float> &costFunction);
	/** Returns storage cost resulting from each merge step.
	*/
	void GetStorageFunction(vector<int> &storageCost);
	/** Returns optimal set of view cells for a given number of view cells.
	*/
	void CollectBestViewCellSet(ViewCellContainer &viewCells, const int numViewCells);
	/** Root of view cells tree.
	*/
	ViewCell *GetRoot() const;
	/** Returns pvs of view cell.
		@note pvs is returned per reference if tree is not compressed,
		per copy else.
	*/
	void GetPvs(ViewCell *vc, ObjectPvs &pvs) const;
	/** Returns pvs size (i.e. the render cost of the stored objects)
	*/
	float GetTrianglesInPvs(ViewCell *vc) const;
	/** Returns number of entries associated with this view cell. 

		This returns the same value as the "GetPvsSize" function for object pvs
		but most likely different values if we use object space grouping.
		E.g., using bounding volumes.
	*/
	int GetPvsEntries(ViewCell *vc) const;
	/** Returns the number of physically stored entries in the view cells sub tree.
		This can vary based on the current storage method
	*/
	int CountStoredPvsEntries(ViewCell *root) const;
	/** Returns memory cost of this view cell.
	*/
	float GetMemoryCost(ViewCell *vc) const;
	/** Sets method of storage for view cells.
	*/
	void SetViewCellsStorage(int type);
	/** pvs storage methods 
	*/
	enum {PVS_IN_INTERIORS, COMPRESSED, PVS_IN_LEAVES};
	/** If view cells in this tree have compressed pvs.
	*/
	int ViewCellsStorage() const;
	/** Returns active view cell that is in the path of this view cell.
	*/
	ViewCell *GetActiveViewCell(ViewCellLeaf *vc) const;
	/** Sets the leaves to be the currently active view cells.
	*/
    void SetActiveSetToLeaves();
	/** Propagates pvs up the tree to the root and downwards the tree.
	*/
	void PropagatePvs(ViewCell *vc);
	/** Exports view cells to file.
	*/
	bool Export(OUT_STREAM &stream, const bool exportPvs = false);
	/** Export statistics of this view cell tree.
	*/
	void ExportStats(const std::string &mergeStats);
	/** Sets root of hierarchy.
	*/
	void SetRoot(ViewCell *root);
	/** Assignes unique ids to view cells.
	*/
	void CreateUniqueViewCellsIds();
	/** Resets pvs of whole tree.
	*/
	void ResetPvs();
	/** Counts pvs of the view cell taking the kd cells into account.
	*/
	int CountKdPvs(const ViewCellLeaf *vc) const;
	/** Sets pointer to view cells manager.
	*/
	void SetViewCellsManager(ViewCellsManager *vcm);

	ViewCellInterior *ImportBinInterior(IN_STREAM  &stream, ViewCellInterior *parent);

	ViewCellLeaf *ImportBinLeaf(IN_STREAM &stream, 
		                        ViewCellInterior *parent,
								const ObjectContainer &pvsObjects);

	void ExportBinInterior(OUT_STREAM &stream, ViewCellInterior *interior);

	void ExportBinLeaf(OUT_STREAM &stream, ViewCell *leaf);

	bool ExportBinary(OUT_STREAM &stream);
	
	bool ImportBinary(IN_STREAM &stream, const ObjectContainer &pvsObjects);

	ViewCell *ImportNextNode(IN_STREAM &stream, 
							 ViewCellInterior *parent,
							 const ObjectContainer &objects);

protected:

	/** Reads the environment and sets member variables.
	*/
	void ReadEnvironment();


	//////////////////////////////////////////////////////////////
	//                    merge related stuff                   //
	//////////////////////////////////////////////////////////////


	/** Computes render cost of the merged pvs.
	*/
	float ComputeMergedPvsCost(const ObjectPvs &pvs1, const ObjectPvs &pvs2) const;
	/** Returns cost of this leaf according to current heuristics.
	*/
	float GetCostHeuristics(ViewCell *vc) const;
	/** Returns cost of leaf.
	*/
	float GetRenderCost(ViewCell *vc) const;
	/** Evaluates the merge cost of this merge candidate pair.
	*/
	void EvalMergeCost(MergeCandidate &mc) const;
	/** Variance of leaf.
	*/
	float GetVariance(ViewCell *vc) const;
	/** Standard deviation of leaf.
	*/
	float GetDeviation(ViewCell *vc) const;
	/** Tries to set this merge candidate to valid. 
		@returns false if both view cells are the same
	*/
	bool ValidateMergeCandidate(MergeCandidate &mc) const;
	/** Merge view cells of leaves l1 and l2.
		@returns difference in pvs size
	*/
	ViewCellInterior *MergeViewCells(ViewCell *l, ViewCell *r, float &pvsDiff);
	/** Shuffles, i.e. takes border leaf from view cell 1 and adds it 
		to view cell 2.
	*/
	void ShuffleLeaf(ViewCell *leaf, ViewCellInterior *vc1, ViewCellInterior *vc2) const;	
	/** Shuffles the leaves, i.e., tests if exchanging
		the leaves helps in improving the view cells.
	*/
	bool ShuffleLeaves(MergeCandidate &mc) const;
	/** Calculates cost for merge of view cell 1 and 2.
	*/
	float EvalShuffleCost(ViewCell *leaf, 
						  ViewCellInterior *vc1, 
						  ViewCellInterior *vc2) const;
	/** Exports a snapshot of the merged view cells to disc.
	*/
	void ExportMergedViewCells(ViewCellContainer &viewCells, 
							   const ObjectContainer &objects,
							   const int numNewViewCells);
	/** Merge queue must be reset after some time because expected value
		may not be valid.
	*/
	void ResetMergeQueue();
	/** Updates the current cut of view cells.
		@returns number of newly merged view cells
	*/
	int UpdateActiveViewCells(ViewCellContainer &viewCells);
	/** Helper function pullling pvs as high up in the tree as possible.
	*/ 
	void PullUpVisibility(ViewCellInterior *interior);
	/** Compress pvs of view cell and children.
	*/
	void CompressViewCellsPvs(ViewCell *root);
	/** Returns memory usage of view cells.
	*/
	float GetMemUsage() const;
	/**	Exports single view cell.
		NOTE: should be in exporter!!
	*/
	void ExportViewCell(ViewCell *viewCell, OUT_STREAM &stream, const bool exportPvs);	
	/** Exports pvs of a view cell.
	*/
	void ExportPvs(ViewCell *viewCell, OUT_STREAM &stream);
	/** Counts the logical number of entries in the pvs this view cell.
		The pvs is assumed to be stored using lossless compression.
	*/
	int GetEntriesInPvsForCompressedStorage(ViewCell *vc) const;
	/** Computes pvs size of this view cell.
		The pvs is assumed to be stored using lossless compression.
	*/
	float GetPvsCostForCompressedStorage(ViewCell *vc) const;
	/** Computes pvs size of this view cell.
		The pvs is assumed to be stored in the leaves.
	*/
	float GetPvsCostForLeafStorage(ViewCell *vc) const;
	/** Counts the logical number of entries in the pvs this view cell.
		The pvs is assumed to be stored using the leaves.
	*/
	int GetEntriesInPvsForLeafStorage(ViewCell *vc) const;
	/** Update stats for the log.
	*/
	void UpdateStats(std::ofstream &stats,
					 const ViewCellsTreeStats &vcStats);
	

	//////////////////////////////////////

	/// if the view cell tree hold compressed pvs
	int mViewCellsStorage;
	/// pointer to the view cells manager
	ViewCellsManager *mViewCellsManager;
	/// the root of the view cells hierarchy
	ViewCell *mRoot;

	/// if merge visualization should be shown
	bool mExportMergedViewCells;
	/// intermediate container of merged view cells.
	ViewCellContainer mMergedViewCells;
	/// if merged view cells are refined.
	bool mRefineViewCells;
	/// weights between variance and render cost increase in the range [0 .. 1].
	float mRenderCostWeight;

	/// overall cost used to normalize cost ratio
	float mOverallCost;
	float mExpectedCost;
    float mDeviation;
	float mAvgRenderCost;
	
	/// the area is used for pvs heuristics
	int mUseAreaForPvs;
	/// number of currently active view cells (=current cut)
	int mNumActiveViewCells;
	/// minimal number of view cells
	int mMergeMinViewCells;
	/// maximal cost ratio for the merge
	float mMergeMaxCostRatio;

	typedef std::priority_queue<MergeCandidate> MergeQueue;

	MergeQueue mMergeQueue;

	float mMaxMemory;

	int mMaxMergesPerPass;
	float mAvgCostMaxDeviation;

	int *mPvsIds;
	ObjectContainer mTempObjects;
};


/**
	Candidate for leaf merging based on priority.
*/
class MergeCandidate
{  
	friend class ViewCellsTree;

public:

	MergeCandidate(ViewCell *l, ViewCell *r);

	/** If this merge pair is still valid.
	*/
	bool IsValid() const;

	
	friend bool operator<(const MergeCandidate &leafa, const MergeCandidate &leafb)
	{
		return leafb.GetMergeCost() < leafa.GetMergeCost();
	}

	void SetLeftViewCell(ViewCell *l);
	void SetRightViewCell(ViewCell *l);

	ViewCell *GetLeftViewCell() const;
	ViewCell *GetRightViewCell() const;

	/** Returns leaf view cell initially associated with this merge candidate.
	*/
	ViewCell *GetInitialLeftViewCell() const;
	/** Returns leaf view cell initially associated with this merge candidate.
	*/
	ViewCell *GetInitialRightViewCell() const;

	/** Returns the increase of the standard deviation of this merge candidate.
	*/
	float GetDeviationIncr() const;

	/** Merge cost of this candidate pair.
	*/
	float GetMergeCost() const;

	/** Render cost of this candidate.
	*/
	float GetRenderCost() const;
	
	static float sRenderCostWeight;

protected:

	/// render cost increase by this merge
	float mRenderCost;
	/// increase / decrease of standard deviation
	float mDeviationIncr;

	ViewCell *mLeftViewCell;
	ViewCell *mRightViewCell;

	ViewCell *mInitialLeftViewCell;
	ViewCell *mInitialRightViewCell;
};


class MergeStatistics: public StatisticsBase
{
public:
	
	int merged;
	int siblings;
	int candidates;
	int nodes;

	int accTreeDist;
	int maxTreeDist;
	
	Real collectTime;
	Real mergeTime;

	Real overallCost;

	Real expectedRenderCost;
	Real deviation;
	Real heuristics;

	// Constructor
	MergeStatistics() 
	{
		Reset();
	}
	
	double AvgTreeDist() const {return (double)accTreeDist / (double)merged;}; 

	void Reset() 
	{
		nodes = 0;
		merged = 0;
		siblings = 0;
		candidates = 0;
	
		accTreeDist = 0;
		maxTreeDist = 0;

		collectTime = 0;
		mergeTime = 0;
		overallCost = 0;

		expectedRenderCost = 0;
		deviation = 0;
		heuristics = 0;

	}

	void Print(std::ostream &app) const;

	friend std::ostream &operator<<(std::ostream &s, const MergeStatistics &stat) 
	{
		stat.Print(s);
		return s;
	} 
};

}

#endif