#ifndef _ViewCellsManager_H__
#define _ViewCellsManager_H__

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


namespace GtpVisibilityPreprocessor {

class ViewCell;
class Intersectable;
class RenderSimulator;
class Renderer;
class Mesh;
struct Triangle3;
class SimulationStatistics;
class BspTree;
class KdTree;
class VspOspTree;
class VspBspTree;
class KdNode;
class KdLeaf;
class AxisAlignedBox3;
class BspLeaf;
class ViewCellsStatistics;
class Exporter;
class Beam;
class Preprocessor;
class ViewCellsTree;
class MergeCandidate;
class BoundingBoxConverter;
class VspTree;
class OspTree;
class VspNode;
class HierarchyManager;
class BvHierarchy;
class ViewCellsTree;
class ViewCell;
class MixtureDistribution;
struct AxisAlignedPlane;
struct BspRay;
class BspTree;



struct PvsFilterStatistics 
{
	PvsFilterStatistics(): 
	mAvgFilterRadius(0.0f), mLocalFilterCount(0), mGlobalFilterCount(0) {}
	
	float mAvgFilterRadius;
	int mLocalFilterCount;
	int mGlobalFilterCount;
};

/** 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 stored as well
};


class LocalMergeNode
{
public:
	virtual ~LocalMergeNode() {};
	virtual bool IsLeaf() const = 0;
};

typedef pair<ViewCell *, SimpleRayContainer> ViewCellPoints;

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

	struct PerViewCellStat 
	{
		float pvsSize;
		float relPvsIncrease;
	};

	struct SamplesStatistics 
	{
		int mRays;
		int mViewCells;
		int mContributingRays;
		int mPvsContributions;
		void Reset() 
		{
			mRays = 0;
			mViewCells = 0;
			mContributingRays = 0;
			mPvsContributions = 0;
		};
	};

	struct PvsStatistics 
	{
		float minPvs;
		float maxPvs;
		float avgPvs;
		float renderCost;
		float avgPvsEntries;

		float avgFilteredPvs;
		float avgFilteredPvsEntries;

		float avgFilterContribution;
		float avgFilterRadius;
		float avgFilterRatio;
		float avgRelPvsIncrease;
		float devRelPvsIncrease;
		int viewcells;

		float mem;
	};
  
	/// view cell container types
	enum {BSP, KD, VSP_KD, VSP_BSP, VSP_OSP};
  
	/// render cost evaluation type
	enum {PER_OBJECT, PER_TRIANGLE};

	friend class X3dViewCellsParseHandlers;

	/** Default constructor.
	*/
	ViewCellsManager(ViewCellsTree *viewCellsTree);

	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,
									 const bool useHitObject = false);

	/** Computes sample contribution of a simgle ray to the view cells PVS.
		@param ray finds intersections with view cells and holds the contribution
		@param addSample if sample should be added to the pvs
        	  
		@returns number of sample contributions
	*/
	virtual float ComputeSampleContribution(VssRay &ray, 
											const bool addContributions,
											const bool storeViewCells,
											const bool useHitObject = false);

	/** Compute sample contribution only for current view cell.
	*/
	virtual float ComputeSampleContribution(VssRay &ray, 
											const bool addContributions,
											ViewCell *currentViewCell,
											const bool useHitObject = false);

	/** Prints out statistics of the view cells.
	*/
	virtual void PrintStatistics(std::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;

	/** collect objects intersecting a given spatial box.
	*/
	virtual void CollectObjects(const AxisAlignedBox3 &box, ObjectContainer &objects);

	/** 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 view cells manager
		is responsible for building a hierarchy over these view cells.
		
		@param filename file to load
		@return true on success
	*/
	virtual bool LoadViewCellsGeometry(const string filename, const bool extrudeBaseTriangle);
	
	/** 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 the type specified by this manager
	*/
	virtual ViewCell *GenerateViewCell(Mesh *mesh = NULL) const = 0;

	/** Constructs view cell from base triangle. 
		The view cell 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;

	virtual Intersectable *GetIntersectable(const VssRay &ray, const bool isTermination) 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 are 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;

	/** Tests if this line segment intersects a particular view cell.
	*/
	virtual bool LineSegmentIntersects(const Vector3 &origin,
									   const Vector3 &termination,
									   ViewCell *viewCell) = 0;

	/** Returns a stats about the global pvs.
	*/
	virtual void GetPvsStatistics(PvsStatistics &stat);

	virtual void GetPrVS(const Vector3 &viewPoint, PrVs &prvs, const float filterWidth);
  
	/** Get a viewcell containing the specified view point.
		@param active if the active or elementary view cell should be returned.
	*/
	virtual ViewCell *GetViewCell(const Vector3 &point, const bool active = false) const = 0;
  
	ViewCell *GetViewCell(const int idx) const {return mViewCells[idx];}

	virtual void PrintPvsStatistics(std::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;
  
	virtual bool GetViewPoint(Vector3 &viewPoint, const Vector3 &params) 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, 
								 const bool exportPvs, 
								 const ObjectContainer &objects);

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


	// resort pvss after a pass of the algorithm
	void  SortViewCellPvs();

	// map the ray intersection objects from triangles to high level objects...
	void DeterminePvsObjects(VssRayContainer &rays,
							 const bool useHitObjects = false);
	
	/** 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);

	/** Returns number of valid view cells.
	*/
    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 AxisAlignedBox3 *box,
										const AxisAlignedPlane *clipPlane = NULL
										) const = 0;

	/** Brings the view cells into their final state, computes meshes and volume.
	*/
	virtual void FinalizeViewCells(const bool createMesh);

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

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

	/** Collect candidates for the view cell merge.
	*/
	virtual void CollectMergeCandidates(const VssRayContainer &rays, 
										vector<MergeCandidate> &candidates);

	/** Collects n view cells and stores it as the active view cells.
	*/
	void CollectViewCells(const int n);

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

	/** Evaluates render cost statistics of current view cell hierarchy.
	*/
	virtual void EvalViewCellPartition();

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

	/** Returns maximal filter size.
	*/
	int GetMaxFilterSize() const;

	/** 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);

	void EvalViewCellHistogramForPvsSize(const string filename, 
										 ViewCellContainer &viewCells);

	/** Evaluates the render cost of a view cell.
	*/
	static float EvalRenderCost(Intersectable *obj);
   
	/** Sets pvs size of view cell as a scalar. Used when storing pvs only in the leaves
		of the hierarchy.
	*/
	void UpdateScalarPvsSize(ViewCell *vc, 
							 const float pvsCost, 
							 const int entriesInPvs) const;

	/** Returns bounding box of a view cell.
	*/
	AxisAlignedBox3 GetViewCellBox(ViewCell *vc);

	/** Exports bounding boxes of objects to file.
	*/
	bool ExportBoundingBoxes(const string filename, 
							 const ObjectContainer &objects) const;
    
	/** Load the bounding boxes into the container.
	*/
	bool LoadBoundingBoxes(const string filename, 
						  IndexedBoundingBoxContainer &boxes) const;

	/** Returns true if pvs should be exported together with the view cells.
	*/
	bool GetExportPvs() const;

	/** Efficiently merges the view cells in the container.
	*/
	void MergeViewCellsRecursivly(ObjectPvs &pvs, 
								  const ViewCellContainer &viewCells) const;

	/** Compress the view cells.
	*/
	virtual void CompressViewCells();

	ViewCell *GetViewCellById(const int id);

	/** Returns number of view cells.
	*/
	int GetNumViewCells() const;

	bool GenerateRandomViewCells(ViewCellContainer &viewCells, 
								 const int numViewCells);

	bool GenerateRandomViewCells(vector<ViewCellPoints *> &viewCells,
								 const int nViewCells,
								 const int nViewPoints);


	bool GenerateViewPoints(ViewCell *viewCell, 
							const int numViewPoints,
							SimpleRayContainer &viewPoints);

	bool ImportRandomViewCells(const string &filename, 
							   vector<ViewCellPoints *> &viewCells);

	bool ImportRandomViewCells(const string &filename);

	bool ExportRandomViewCells(const string &filename,
							   const vector<ViewCellPoints *> &viewCells);

	bool ExportRandomViewCells(const string &filename);

	bool GenerateViewPoint(ViewCell *viewCell, SimpleRay &ray);

	bool IsValidViewSpace(ViewCell *vc);


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

		@param filename the filename of the view cells
		@param objects the scene objects
		@param finalizeViewCells if the view cells should be post processed, i.e.,
			   a mesh is created representing the geometry
		@param bconverter a conversion routine working with the similarities of bounding
			   boxes: if there is a certain similarity of overlap between 
			   bounding boxes, two tested candidate objects are considered 
			   to be the same objects
		@returns the view cells manager if loading was successful, false otherwise
	*/
	static ViewCellsManager *LoadViewCells(const string &filename, 
										   ObjectContainer &pvsObjects,
										   ObjectContainer &preprocessorObjects,
										   bool finalizeViewCells = false,
										   BoundingBoxConverter *bconverter = NULL);

	static ViewCellsManager *LoadViewCells(const string &filename, 
										   ObjectContainer &pvsObjects,
										   bool finalizeViewCells = false,
										   BoundingBoxConverter *bconverter = NULL);

	///////////////////////
	// visiblity filter options

	// TODO: write own visibiltiy filter class
	void ApplyFilter(KdTree *kdTree,
					 const float viewSpaceFilterSize,
					 const float spatialFilterSize);

	// new adaptive version of the filter
	PvsFilterStatistics ApplyFilter2(ViewCell *viewCell,
									 const bool useViewSpaceFilter,
									 const float filterSize,
									 ObjectPvs &pvs,
									 vector<AxisAlignedBox3> *filteredBoxes = NULL);

	void ApplySpatialFilter(KdTree *kdTree,
							const float spatialFilterSize,
							ObjectPvs &pvs);

	 void ApplyFilter(ViewCell *viewCell,
					  KdTree *kdTree,
					  const float viewSpaceFilterSize,
					  const float spatialFilterSize,
					  ObjectPvs &pvs);

	float GetFilterWidth();

	float GetAbsFilterWidth();

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



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


	/** If true, the kd nodes are stored instead of the object pvs.
	*/
	void SetStoreKdPvs(const bool storeKdPvs);

	/** Returns true if the kd nodes are stored instead of the object pvs.
	**/
	bool GetStoreKdPVs() const;

	/** Exports single view cells for visualization.
		@param objects the scene objects
		@param limit the maximal number of output view cells
		@param sortViewCells if the view cells should be sorted by pvs size
		@param exportPvs if the pvs should also be exported
		@param exportRays if sample rays should be exported as well
		@param maxRays maximum number of rays to export
		@param prefix the prefix for the output file
		@param visRays additional rays
	*/
	virtual void ExportSingleViewCells(const ObjectContainer &objects,
									   const int maxViewCells,
									   const bool sortViewCells,
									   const bool exportPvs,
									   const bool exportRays,
									   const int maxRays,
									   const string prefix,
									   VssRayContainer *visRays = NULL) = NULL;


	void ResetPvs();

	Preprocessor *GetPreprocessor() const {
		return mPreprocessor;
	}

	void SetPreprocessor(Preprocessor *p) {
		mPreprocessor = p;
	}

	vector<ViewCellPoints *> *GetViewCellPoints()
	{
		return &mViewCellPoints;
	}

	void UpdatePvsForEvaluation();

protected:

	void ComputeViewCellContribution(ViewCell *viewCell,
									 VssRay &ray, 
									 Intersectable *obj,
									 const Vector3 &pt,
									 const bool addRays);

	void MergeViewCellsRecursivly(ObjectPvs &pvs, 
								  const ViewCellContainer &viewCells, 
								  const int leftIdx, 
								  const int rightIdx) 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;

	/** Tests the visibility filter functionality.
	*/
	virtual void TestFilter(const ObjectContainer &objects) {};

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

	/** Requests preprocessor to cast samplesPerPass samples of a specific type.
	*/
	int CastPassSamples(const int samplesPerPass, 
						const vector<int> &strategies,
						VssRayContainer &vssRays) const;

	int CastEvaluationSamples(const int samplesPerPass, 
							  VssRayContainer &passSamples);// const;

	/** Parse the options from the environment file.
	*/
	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();

	/** Sets this view cell to active.
	*/
	void SetViewCellActive(ViewCell *vc) const;

	/** 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 AxisAlignedBox3 *box,
							   const bool colorCode,
							   const AxisAlignedPlane *clipPlane) const;

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

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

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

	AxisAlignedPlane *GetClipPlane();

	void ExportMergedViewCells(const ObjectContainer &objects);


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

	/** Returns volume of the view space.
	*/
	virtual float GetViewSpaceVolume();

	/** Prepares the view cells for sampling 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);
  
	/** Updates pvs of all view cells for statistical evaluation after some more sampling
	*/
	void UpdatePvsForEvaluation(ViewCell *root, ObjectPvs &pvs);

	virtual void ExportStats(const string &mergeStats);


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


	ofstream mStats;
	Preprocessor *mPreprocessor;
	
	/// if bounding boxes should be exported together with the view cells
	bool mExportBboxesForPvs;
	
	/// the clip plane for visualization
	AxisAlignedPlane mClipPlaneForViz;
	
	/// if the visualization is using the clip plane
	bool mUseClipPlaneForViz;
	
	/// Renders the view cells.
	Renderer *mRenderer;
	
	/// Loaded view cells
	ViewCellContainer mViewCells;
	
	/// the view cell hierarchy (i.e., the logical description of view cells)
	ViewCellsTree *mViewCellsTree;
	
	std::vector<int> mStrategies;

	/** if the values in the view cell leaves and the interiors are up to date
		this is meant for lazy storing of the pvs, where only a scalar indicating
		pvs size is stored in interiors and not the pvs itself.
	*/
	bool mViewCellPvsIsUpdated;

	/// maximum number of samples for the view cell construction
	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;

	vector<ViewCellPoints *> mViewCellPoints;

	/// holds the current view cell statistics
	ViewCellsStatistics mCurrentViewCellsStats;

	/// the scene bounding box
	AxisAlignedBox3 mViewSpaceBox;
	
	/// if view cells should be exported
	bool mExportViewCells;

	// if only valid view cells should be considered for processing
	bool mOnlyValidViewCells;

	/// if rays should be used to collect merge candidates
	bool mUseRaysForMerge;

	/// if there should be an additional merge step after the subdivision
	bool mMergeViewCells;

	/// the width of the box filter
	float mFilterWidth;
	/// Maximal size of the filter in terms of contributing view cells
	int mMaxFilterSize;
	
	// only for debugging
	VssRayContainer storedRays;

	bool mUseKdPvs;
	bool mUseKdPvsAfterFiltering;

	MixtureDistribution *mMixtureDistribution;


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

	/// if pvs should be exported with view cells
	bool mExportPvs;

	static int sRenderCostEvaluationType;

	/// if view cells geometry should be used from other sources
	bool mUsePredefinedViewCells;

  
  vector<PerViewCellStat> mPerViewCellStat;
  SamplesStatistics mSamplesStat;
};


/** 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(ViewCellsTree *viewCellsTree, 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);
	
	/** Returns the probability that the view point lies
		in this view cells.
	*/
	float GetProbability(ViewCell *viewCell);

	/** Get a viewcell containing the specified point.
	*/
	ViewCell *GetViewCell(const Vector3 &point, const bool active = false) const;

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

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

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

	bool ExportViewCells(const string filename, 
						 const bool exportPvs, 
						 const ObjectContainer &objects);

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

	void ExportSingleViewCells(const ObjectContainer &objects,
							   const int maxViewCells,
							   const bool sortViewCells,
							   const bool exportPvs,
							   const bool exportRays,
							   const int maxRays,
							   const string prefix,
							   VssRayContainer *visRays = NULL);

	bool LineSegmentIntersects(const Vector3 &origin,
							   const Vector3 &termination,
							   ViewCell *viewCell);

protected:

	void CollectViewCells();
	
	/// the BSP tree.
	BspTree *mBspTree;
	vector<BspRay *> mBspRays;

private:

	/** Constructs a spatial merge tree only 2 levels deep.
	*/
	ViewCell *ConstructDummyMergeTree(BspNode *root);

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

	/** test if subdivision is valid in terms of volume / area.
	*/
	void TestSubdivision();
};


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

public:

	KdViewCellsManager(ViewCellsTree *viewCellsTree, 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 bool active = false) const 
	{ return NULL; }

	float GetProbability(ViewCell *viewCell);
	
	void CreateMesh(ViewCell *vc);

	void ExportViewCellGeometry(Exporter *exporter,
								ViewCell *vc,
								const AxisAlignedBox3 *box,
								const AxisAlignedPlane *clipPlane = NULL) const;


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

	void ExportSingleViewCells(const ObjectContainer &objects,
							   const int maxViewCells,
							   const bool sortViewCells,
							   const bool exportPvs,
							   const bool exportRays,
							   const int maxRays,
							   const string prefix,
							   VssRayContainer *visRays = NULL);

	bool LineSegmentIntersects(const Vector3 &origin,
							   const Vector3 &termination,
							   ViewCell *viewCell);

protected:

	/** Collects view cells from a hierarchy.
	*/
	void CollectViewCells();

	KdNode *GetNodeForPvs(KdLeaf *leaf);

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

	/// 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.
*/
class VspBspViewCellsManager: public ViewCellsManager
{

public:

	VspBspViewCellsManager(ViewCellsTree *viewCellsTree, 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 active = false) const;

	bool GetViewPoint(Vector3 &viewPoint) const;

	bool ViewPointValid(const Vector3 &viewPoint) const;

	void CreateMesh(ViewCell *vc);

	bool ExportViewCells(const string filename, 
						 const bool exportPvs, 
						 const ObjectContainer &objects);

	int CastBeam(Beam &beam);
	
	void ExportViewCellGeometry(Exporter *exporter,
								ViewCell *vc,
								const AxisAlignedBox3 *box,
								const AxisAlignedPlane *clipPlane = NULL) const;


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

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

	void ExportSingleViewCells(const ObjectContainer &objects,
							   const int maxViewCells,
							   const bool sortViewCells,
							   const bool exportPvs,
							   const bool exportRays,		
							   const int maxRays,
							   const string prefix,
							   VssRayContainer *visRays = NULL);

	
	bool LineSegmentIntersects(const Vector3 &origin,
							   const Vector3 &termination,
							   ViewCell *viewCell);

protected:

	int ComputeBoxIntersections(const AxisAlignedBox3 &box, 
								ViewCellContainer &viewCells) const;
	
	/** Merges view cells according to some criteria
	*/
	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;

	/** 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);

	/// HACK for testing visibility filter functionality
	void TestFilter(const ObjectContainer &objects);

	/** Visualization of the pvs difference to exact visubility using 
		from point queries.
	*/
	void VisualizeWithFromPointQueries();

	/** Evaluate from point queries for the current scene.
	*/
	void EvalFromPointQueries();

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


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

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


private:

	/** test if subdivision is valid in terms of volume / area.
	*/
	void TestSubdivision();
};

#define TEST_EVALUATION 0

/**
	Manages different higher order operations on the view cells.
*/
class VspOspViewCellsManager: public ViewCellsManager
{
	friend class ViewCellsParseHandlers;

public:

	VspOspViewCellsManager(ViewCellsTree *vcTree, 
						   const string &hierarchyType);
	
	~VspOspViewCellsManager();

	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;

	virtual Intersectable *GetIntersectable(
		const VssRay &ray, const bool isTermination) const;

	bool ViewCellsConstructed() const;

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

	bool LineSegmentIntersects(const Vector3 &origin, 
							   const Vector3 &termination, 
							   ViewCell *viewCell);

	float GetProbability(ViewCell *viewCell);
	
	ViewCell *GetViewCell(const Vector3 &point, 
						  const bool active = false) const;

	bool GetViewPoint(Vector3 &viewPoint) const;

	bool ViewPointValid(const Vector3 &viewPoint) const;

	void CreateMesh(ViewCell *vc);

	bool ExportViewCells(const string filename, 
						 const bool exportPvs, 
						 const ObjectContainer &objects);

	int CastBeam(Beam &beam);

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

	void ExportSingleViewCells(const ObjectContainer &objects,
							   const int maxViewCells,
							   const bool sortViewCells,
							   const bool exportPvs,
							   const bool exportRays,
							   const int maxRays,
							   const string prefix,
							   VssRayContainer *visRays = NULL);
	
	float UpdateObjectCosts();

	virtual void FinalizeViewCells(const bool createMesh);

protected:

	VspOspViewCellsManager(ViewCellsTree *vcTree, HierarchyManager *hm);
	
#if 1//TEST_EVALUATION
	virtual void EvalViewCellPartition();
#endif

	/** Exports view cell geometry.
	*/
	void ExportViewCellGeometry(Exporter *exporter,
								ViewCell *vc,
								const AxisAlignedBox3 *box,
								const AxisAlignedPlane *clipPlane = NULL) const;

	int ComputeBoxIntersections(const AxisAlignedBox3 &box, 
								ViewCellContainer &viewCells) const;
	
	void CollectViewCells();

	virtual void CompressViewCells();

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

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

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

	/** Returns a hierarchy manager of the given name.
	*/
	static HierarchyManager *CreateHierarchyManager(const string &name);

	//void ExportStats(const string &mergeStats);

	/** collect objects intersecting a given spatial box 
	*/
	virtual void CollectObjects(const AxisAlignedBox3 &box, ObjectContainer &objects);


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

	bool mCompressObjects;

	HierarchyManager *mHierarchyManager;
};


}

#endif