#ifndef _ViewCellsManager_H__
#define _ViewCellsManager_H__

#include "Ray.h"
#include "VssRay.h"
#include "Containers.h"
#include "ViewCell.h"
#include "ViewCellBsp.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;

struct AxisAlignedPlane;
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, VSP_OSP};
  
	/// render cost evaluation type
	enum {PER_OBJECT, PER_TRIANGLE};

	/** Default constructor.
	*/
	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 ComputeSampleContribution(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 scene objects. The view ells are created by taking the object
		geometry into account.
	*/
	void DeriveViewCellsFromObjects(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 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;

	virtual void GetPvsStatistics(PvsStatistics &stat);

	virtual void GetPrVS(const Vector3 &viewPoint, PrVs &prvs, const float filterWidth);
  
	/** Get a viewcell containing the specified 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;
  
	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, 
								 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;

	
	/** 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 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,
								  int &totalPvs,
								  float &avgRenderCost);


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

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

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

	/** Evaluates the render cost of a view cell.
	*/
	float EvalRenderCost(Intersectable *obj) const;
   
	/** 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 int pvsSize, 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;

	/** 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 *objects, 
										   const bool finalizeViewCells,
										   BoundingBoxConverter *bconverter = NULL);


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

	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;


	/** Returns true if the view cell is equivalent to a 
		node of the spatial hierarchy. This function can be used for merged
		view cell.
		e.g. to see if the spatial tree can be reduced on this location
	*/
	virtual bool EqualToSpatialNode(ViewCell *viewCell) 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;

	virtual bool AddSampleToPvs(
		Intersectable *obj, 
		const Vector3 &hitPoint,
		ViewCell *vc,
		const float pdf, 
		float &contribution) const;

protected:

	/** Exports bounding boxes as xml stream
	*/
	//bool ExportBoundingBoxes(ofstream &xmlstream, const ObjectContainer &objects) 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;

	int CastPassSamples(const int samplesPerPass, 
						const int sampleType, 
						VssRayContainer &vssRays) 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();
	
	/** 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;

	/** Returns volume of the view space.
	*/
	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();

	/** Updates pvs of all view cells for statistical evaluation after some more sampling
	*/
	void UpdatePvsForEvaluation(ViewCell *root, ObjectPvs &pvs);

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

	Preprocessor *mPreprocessor;
	/// if bounding boxes should be exported together with the view cells
	bool mExportBboxesForPvs;
		
	//Environment *environment;
	AxisAlignedPlane mClipPlane;

	bool mUseClipPlaneForViz;


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

	/// Loaded view cells
	ViewCellContainer mViewCells;
	/// the corresponding view cell tree holding the logical description of view cells
	ViewCellsTree *mViewCellsTree;
	/// if empty view cells should be pruned (i.e., invalidated) from this point on
	bool mPruneEmptyViewCells;

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

	/// 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;
	int mMaxFilterSize;

	//-- visualization options
	
	/// color code for view cells visualization
	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;

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

	bool mStoreObjectPvs;

	VssRayContainer storedRays;
};


/**
	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 bool active = false) const;

	void CreateMesh(ViewCell *vc);

	void ExportViewCellGeometry(Exporter *exporter, 
								ViewCell *vc, 
								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);

	
protected:

	void CollectViewCells();

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

	/** 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(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 AxisAlignedPlane *clipPlane = NULL) const;

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


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(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 AxisAlignedPlane *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;

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

	/** Exports visualization of the BSP PVS.
	*/
	void ExportBspPvs(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 1

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

public:

	VspOspViewCellsManager(VspTree *tree, OspTree *ospTree);
	~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;

	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 Finalize(ViewCell *viewCell, const bool createMesh);

	/** Stores sample contribution for kd cells or objects.
	*/
	virtual float ComputeSampleContribution(VssRay &ray, 
											const bool addRays,
											const bool storeViewCells);

	ViewCellsManager *LoadViewCells(const string &filename, 
		ObjectContainer *objects,
		const bool finalizeViewCells,
		BoundingBoxConverter *bconverter);

	bool AddSampleToPvs(
		Intersectable *obj, 
		const Vector3 &hitPoint,
		ViewCell *vc,
		const float pdf, 
        float &contribution) const;

protected:

#if TEST_EVALUATION
	virtual void EvalViewCellPartition();
#endif
	/** Exports view cell geometry.
	*/
	void ExportViewCellGeometry(Exporter *exporter, 
		ViewCell *vc,
		const AxisAlignedPlane *clipPlane = NULL) const;

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


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


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

	/// the view space / object partition hierarchies
	VspTree *mVspTree;
	OspTree *mOspTree;
	BvHierarchy *mBvHierarchy;

	HierarchyManager *mHierarchyManager;
};


/*class ViewCellsManagerFactory
{
public:
	ViewCellsManager *Create(const string mName);
};*/

}

#endif