#include "ViewCellsManager.h"
#include "RenderSimulator.h"
#include "Mesh.h"
#include "Triangle3.h"
#include "ViewCell.h"
#include "Environment.h"
#include "X3dParser.h"
#include "ViewCellBsp.h"
#include "KdTree.h"
#include "HierarchyManager.h"
#include "Exporter.h"
#include "VspBspTree.h"
#include "ViewCellsParser.h"
#include "Beam.h"
#include "VssPreprocessor.h"
#include "RssPreprocessor.h"
#include "BoundingBoxConverter.h"
#include "GlRenderer.h"
#include "ResourceManager.h"
#include "IntersectableWrapper.h"
#include "VspTree.h"
#include "OspTree.h"
#include "BvHierarchy.h"
#include "SamplingStrategy.h"
#include "SceneGraph.h"
#include "Timer/PerfTimer.h"


#define USE_RAY_LENGTH_AS_CONTRIBUTION 0
#define DIST_WEIGHTED_CONTRIBUTION 0
#define SUM_RAY_CONTRIBUTIONS 1
#define AVG_RAY_CONTRIBUTIONS 0
#define CONTRIBUTION_RELATIVE_TO_PVS_SIZE 0
#define PVS_ADD_DIRTY 1



namespace GtpVisibilityPreprocessor {


PerfTimer viewCellCastTimer;
PerfTimer pvsTimer;
PerfTimer objTimer;

// HACK
const static bool SAMPLE_AFTER_SUBDIVISION = true;
//const static bool CLAMP_TO_BOX = false;
const static bool CLAMP_TO_BOX = true;



inline static bool ilt(Intersectable *obj1, Intersectable *obj2)
{
	return obj1->mId < obj2->mId;
}


template <typename T> class myless
{
public:
	//bool operator() (HierarchyNode *v1, HierarchyNode *v2) const
	bool operator() (T v1, T v2) const
	{
		return (v1->GetMergeCost() < v2->GetMergeCost());
	}
};


ViewCellsManager::ViewCellsManager(ViewCellsTree *viewCellsTree):
mRenderer(NULL),
mInitialSamples(0),
mConstructionSamples(0),
mPostProcessSamples(0),
mVisualizationSamples(0),
mTotalAreaValid(false),
mTotalArea(0.0f),
mViewCellsFinished(false),
mMaxPvsSize(9999999),
mMinPvsSize(0),
mMaxPvsRatio(1.0),
mViewCellPvsIsUpdated(false),
mPreprocessor(NULL),
mViewCellsTree(viewCellsTree),
mUsePredefinedViewCells(false),
mMixtureDistribution(NULL),
mEvaluationSamples(0)
{
	mViewSpaceBox.Initialize();
	ParseEnvironment();

	mViewCellsTree->SetViewCellsManager(this);
	mSamplesStat.Reset();
	mStats.open("mystats.log");
}


int ViewCellsManager::CastEvaluationSamples(const int samplesPerPass,
											VssRayContainer &passSamples)
{
	static int pass = 0;
	static int totalRays = 0;

	SimpleRayContainer rays;
	rays.reserve(samplesPerPass);
	//passSamples.reserve(samplesPerPass * 2);
  
	long startTime = GetTime();

  	cout<<"Progress :"<<totalRays / 1e6f << " M rays, " << (100.0f * totalRays) / (mEvaluationSamples + 1) << "%" << endl;
	
	//rays.clear();
	//passSamples.clear();
	
	mMixtureDistribution->GenerateSamples(samplesPerPass, rays);
	
	const bool doubleRays = true;
	const bool pruneInvalidRays = true;
	mPreprocessor->CastRays(rays, passSamples, doubleRays, pruneInvalidRays);

	mMixtureDistribution->ComputeContributions(passSamples);
	mMixtureDistribution->UpdateDistributions(passSamples);
	
	Real time = TimeDiff(startTime, GetTime());
	PrintPvsStatistics(mStats);
	
	mStats <<
		"#Pass\n" << pass ++ <<endl<<
		"#Time\n" << time <<endl<<
		"#TotalSamples\n" << totalRays << endl;
	

	totalRays += samplesPerPass;

	return (int)passSamples.size();
}


void ViewCellsManager::ParseEnvironment()
{
	// visualization stuff
 	Environment::GetSingleton()->GetBoolValue("ViewCells.Visualization.exportRays", mExportRays);
	Environment::GetSingleton()->GetBoolValue("ViewCells.Visualization.exportGeometry", mExportGeometry);
	Environment::GetSingleton()->GetFloatValue("ViewCells.maxPvsRatio", mMaxPvsRatio);
	
	Environment::GetSingleton()->GetBoolValue("ViewCells.processOnlyValidViewCells", mOnlyValidViewCells);

	Environment::GetSingleton()->GetIntValue("ViewCells.Construction.samples", mConstructionSamples);
	Environment::GetSingleton()->GetIntValue("ViewCells.PostProcess.samples", mPostProcessSamples);
	Environment::GetSingleton()->GetBoolValue("ViewCells.PostProcess.useRaysForMerge", mUseRaysForMerge);

 	Environment::GetSingleton()->GetIntValue("ViewCells.Visualization.samples", mVisualizationSamples);

	Environment::GetSingleton()->GetIntValue("ViewCells.Construction.samplesPerPass", mSamplesPerPass);
	Environment::GetSingleton()->GetBoolValue("ViewCells.exportToFile", mExportViewCells);
	
	Environment::GetSingleton()->GetIntValue("ViewCells.active", mNumActiveViewCells);
	Environment::GetSingleton()->GetBoolValue("ViewCells.PostProcess.compress", mCompressViewCells);
	Environment::GetSingleton()->GetBoolValue("ViewCells.Visualization.useClipPlane", mUseClipPlaneForViz);
	Environment::GetSingleton()->GetBoolValue("ViewCells.PostProcess.merge", mMergeViewCells);
	Environment::GetSingleton()->GetBoolValue("ViewCells.evaluateViewCells", mEvaluateViewCells);
	Environment::GetSingleton()->GetBoolValue("ViewCells.showVisualization", mShowVisualization);
	Environment::GetSingleton()->GetIntValue("ViewCells.Filter.maxSize", mMaxFilterSize);
	Environment::GetSingleton()->GetFloatValue("ViewCells.Filter.width", mFilterWidth);

	Environment::GetSingleton()->GetBoolValue("ViewCells.exportBboxesForPvs", mExportBboxesForPvs);
	Environment::GetSingleton()->GetBoolValue("ViewCells.exportPvs", mExportPvs);

	Environment::GetSingleton()->GetBoolValue("ViewCells.useKdPvs", mUseKdPvs);

	char buf[100];
	Environment::GetSingleton()->GetStringValue("ViewCells.samplingType", buf);

	Environment::GetSingleton()->GetFloatValue("ViewCells.triangleWeight", mTriangleWeight);
	Environment::GetSingleton()->GetFloatValue("ViewCells.objectWeight", mObjectWeight);

	// choose mix of sampling strategies
	if (0)
	{
		mStrategies.push_back(SamplingStrategy::SPATIAL_BOX_BASED_DISTRIBUTION);
		//mStrategies.push_back(SamplingStrategy::OBJECT_DIRECTION_BASED_DISTRIBUTION);
	}
	else
	{
		//mStrategies.push_back(SamplingStrategy::REVERSE_VIEWSPACE_BORDER_BASED_DISTRIBUTION);

		mStrategies.push_back(SamplingStrategy::OBJECT_BASED_DISTRIBUTION);
		mStrategies.push_back(SamplingStrategy::REVERSE_OBJECT_BASED_DISTRIBUTION);
		        
		mStrategies.push_back(SamplingStrategy::SPATIAL_BOX_BASED_DISTRIBUTION);
	}
		
    Debug << "casting strategies: ";
	for (int i = 0; i < (int)mStrategies.size(); ++ i)
		Debug << mStrategies[i] << " ";
	Debug << endl;

	// sampling type for view cells construction samples
	if (strcmp(buf, "object") == 0)
	{
		mSamplingType = SamplingStrategy::OBJECT_BASED_DISTRIBUTION;
	}
	else if (strcmp(buf, "box") == 0)
	{
		mSamplingType = SamplingStrategy::SPATIAL_BOX_BASED_DISTRIBUTION;
	}
	else if (strcmp(buf, "directional") == 0)
	{
		mSamplingType = SamplingStrategy::DIRECTION_BASED_DISTRIBUTION;
	}
	else if (strcmp(buf, "object_directional") == 0)
	{
		mSamplingType = SamplingStrategy::OBJECT_DIRECTION_BASED_DISTRIBUTION;
	}
	else if (strcmp(buf, "reverse_object") == 0)
	{
		mSamplingType = SamplingStrategy::REVERSE_OBJECT_BASED_DISTRIBUTION;
	}
	/*else if (strcmp(buf, "interior") == 0)
	{
		mSamplingType = Preprocessor::OBJECTS_INTERIOR_DISTRIBUTION;
	}*/
	else
	{
		Debug << "error! wrong sampling type" << endl;
		exit(0);
	}

	// sampling type for evaluation samples
	Environment::GetSingleton()->GetStringValue("ViewCells.Evaluation.samplingType", buf);
	
	if (strcmp(buf, "object") == 0)
	{
		mEvaluationSamplingType = SamplingStrategy::OBJECT_BASED_DISTRIBUTION;
	}
	else if (strcmp(buf, "box") == 0)
	{
		mEvaluationSamplingType = SamplingStrategy::SPATIAL_BOX_BASED_DISTRIBUTION;
	}
	else if (strcmp(buf, "directional") == 0)
	{
		mEvaluationSamplingType = SamplingStrategy::DIRECTION_BASED_DISTRIBUTION;
	}
	else if (strcmp(buf, "object_directional") == 0)
	{
		mEvaluationSamplingType = SamplingStrategy::OBJECT_DIRECTION_BASED_DISTRIBUTION;
	}
	else if (strcmp(buf, "reverse_object") == 0)
	{
		mEvaluationSamplingType = SamplingStrategy::REVERSE_OBJECT_BASED_DISTRIBUTION;
	}
	else
	{
		mEvaluationSamplingType = -1;
		Debug << "error! wrong sampling type" << endl;
		exit(0);
	}


	/** The color code used during visualization.
	*/
	Environment::GetSingleton()->GetStringValue("ViewCells.Visualization.colorCode", buf);

	if (strcmp(buf, "PVS") == 0)
		mColorCode = 1;
	else if (strcmp(buf, "MergedLeaves") == 0)
		mColorCode = 2;
	else if (strcmp(buf, "MergedTreeDiff") == 0)
		mColorCode = 3;
	else
		mColorCode = 0;


	Debug << "************ View Cells Manager options ***************" << endl;
	Debug << "color code: " << mColorCode << endl;

	Debug << "export rays: " << mExportRays << endl;
	Debug << "export geometry: " << mExportGeometry << endl;
	Debug << "max pvs ratio: " << mMaxPvsRatio << endl;
	
	Debug << "process only valid view cells: " << mOnlyValidViewCells << endl;
	Debug << "construction samples: " << mConstructionSamples << endl;
	Debug << "post process samples: " << mPostProcessSamples << endl;
	Debug << "post process use rays for merge: " << mUseRaysForMerge << endl;
	Debug << "visualization samples: " << mVisualizationSamples << endl;
	Debug << "construction samples per pass: " << mSamplesPerPass << endl;
	Debug << "export to file: " << mExportViewCells << endl;
	
	Debug << "active view cells: " << mNumActiveViewCells << endl;
	Debug << "post process compress: " << mCompressViewCells << endl;
	Debug << "visualization use clipPlane: " << mUseClipPlaneForViz << endl; 
	Debug << "post process merge: " << mMergeViewCells << endl;
	Debug << "evaluate view cells: " << mEvaluateViewCells << endl;
	Debug << "sampling type: " << mSamplingType << endl;
	Debug << "evaluation sampling type: " << mEvaluationSamplingType << endl;
	Debug << "show visualization: " << mShowVisualization << endl;
	Debug << "filter width: " << mFilterWidth << endl;
	Debug << "sample after subdivision: " << SAMPLE_AFTER_SUBDIVISION << endl;

	Debug << "export bounding boxes: " << mExportBboxesForPvs << endl;
	Debug << "export pvs for view cells: " << mExportPvs << endl;
	Debug << "use kd pvs " << mUseKdPvs << endl;

	Debug << "triangle weight: " << mTriangleWeight << endl;
	Debug << "object weight: " << mObjectWeight << endl;

	Debug << endl;
}


ViewCell *ViewCellsManager::GetViewCellById(const int id)
{
	ViewCellContainer::const_iterator vit, vit_end = mViewCells.end();

	for (vit = mViewCells.begin(); vit != vit_end; ++ vit)
	{
		if ((*vit)->GetId() == id)
			return (*vit);
	}
	return NULL;
}


bool ViewCellsManager::ExportRandomViewCells(const string &filename,
											 const vector<ViewCellPoints *> &viewCells)
{
	std::ofstream outStream;
	outStream.open(filename.c_str());

	vector<ViewCellPoints *>::const_iterator vit, vit_end = viewCells.end();
    
	for (vit = viewCells.begin(); vit != vit_end; ++ vit)
	{
		ViewCell *vc = (*vit)->first;

		outStream << "v " << vc->GetId() << endl;

		SimpleRayContainer viewPoints;
	
		SimpleRayContainer::const_iterator pit, pit_end = (*vit)->second.end();

		for (pit = (*vit)->second.begin(); pit != pit_end; ++ pit)
		{
			const Vector3 pt = (*pit).mOrigin;
			const Vector3 dir = (*pit).mDirection;

			outStream << "p " << pt.x  << " " << pt.y  << " " << pt.z 
				      << " "  << dir.x << " " << dir.y << " " << dir.z << endl;
		}
	}

	return true;
}


bool ViewCellsManager::GenerateRandomViewCells(vector<ViewCellPoints *> &viewCells,
											   const int nViewCells,
											   const int nViewPoints)
{
	ViewCellContainer rViewCells;

	cout << "generating " << nViewCells << " random view cells" << endl;
	///GenerateRandomViewCells(rViewCells, nViewCells);

	//cout << "finished" << endl;

	//for (int i = 0; i < viewCells.size(); ++ i)
	//	cout << "vc " << i << ": " << viewCells[i]->GetId() << endl;

	cout << "generating " << nViewPoints << " view points per view cell" << endl;
	    
	int generatedViewCells = 0;
	int i = 0;
    while (generatedViewCells < nViewCells)
	{
		++ i;
		
		const int idx = (int)RandomValue(0.0f, (float)mViewCells.size() - 0.5f);
			
		ViewCell *viewCell = GetViewCell(idx);
		
		cout << "testing view cell: " << viewCell->GetId() << endl;

		if (!viewCell->Mailed())
		{
			viewCell->Mail();

			SimpleRayContainer viewPoints;
			
			// generate random view points
			if (IsValidViewSpace(viewCell) && 
				GenerateViewPoints(viewCell, nViewPoints, viewPoints))
			{
				Debug << "vc: " << viewCell->GetId() << endl;

				ViewCellPoints *vcPts = new ViewCellPoints();
				viewCells.push_back(vcPts);

				// valid view cell found
				vcPts->first = viewCell;

				// generate view points
				++ generatedViewCells;

				SimpleRayContainer::const_iterator pit, pit_end = viewPoints.end();

				for (pit = viewPoints.begin(); pit != pit_end; ++ pit)
				{
					Debug << "vp: " << (*pit) << endl;
					vcPts->second.push_back(*pit);	
				}
				cout << "view cell " << generatedViewCells << " generated: " << viewCell->GetId() << endl;	
			}
			else
			{
				cout << "error: invalid view cell " << generatedViewCells << " with id " << viewCell->GetId() << endl;	
			}
		}

		if (i > nViewCells * 1000000) // safety
		{
			cout << "big error" << endl;
			break;
		}
		cout << "processd view cells " << generatedViewCells << " of " << nViewCells << endl << endl;
	}

	return true;
}


bool ViewCellsManager::ImportRandomViewCells(const string &filename, 
											 vector<ViewCellPoints *> &viewCells)
{
	ifstream inStream(filename.c_str());
	if (!inStream.is_open())
		return false;

	ViewCellPoints *currentViewCell = NULL;

 	string buf;
	while (!(getline(inStream, buf)).eof())
	{
		switch (buf[0])
		{
		case 'v':
			{
				int id;
				sscanf(buf.c_str(), "v %d", &id);
			
				currentViewCell = new ViewCellPoints();
				currentViewCell->first = GetViewCellById(id);
						
				viewCells.push_back(currentViewCell);
				break;
			}
		case 'p':
			{
				Vector3 pt, dir;
				sscanf(buf.c_str(), "p %f %f %f %f %f %f", &pt.x, &pt.y, &pt.z, &dir.x, &dir.y, &dir.z);
				
				SimpleRay ray(pt, dir, 0, 1);
				currentViewCell->second.push_back(ray);
				break;
			}
		default:
			break;
		}
	}

	return true;
}


bool ViewCellsManager::ImportRandomViewCells(const string &filename)
{
	return ImportRandomViewCells(filename, mViewCellPoints);
}


bool ViewCellsManager::GenerateViewPoints(ViewCell *viewCell, 
										  const int numViewPoints,
										  SimpleRayContainer &viewPoints)
{
	bool success = true;
	int generatedPts = 0;
	int i = 0;

	cout << "generating view points for view cell " << viewCell->GetId() << endl;

	while (generatedPts < numViewPoints)
	{
		SimpleRay pt;

		if (GenerateViewPoint(viewCell, pt))
		{
			++ generatedPts;
			cout << "generated view point " << generatedPts << endl;
			viewPoints.push_back(pt);
		}

		// savety criterium
		if (++ i > numViewPoints * 3)
		{
			return false;
		}
	}
	
	cout << "view point generation finished" << endl;

	return true;
}


bool ViewCellsManager::ExportRandomViewCells(const string &filename)
{
	const int numViewCells = 100;
	const int numViewPoints = 10;

	preprocessor->mViewCellsManager->
		GenerateRandomViewCells(mViewCellPoints, numViewCells, numViewPoints);

	//cout << "exporting random view cells" << endl;
	return preprocessor->mViewCellsManager->ExportRandomViewCells(filename,  mViewCellPoints);
}


bool ViewCellsManager::GenerateViewPoint(ViewCell *viewCell, 
										 SimpleRay &ray)
{
	// do not use this function since it could return different 
	// viewpoints for different executions of the algorithm

	int tries = 0;
	Vector3 viewPoint, direction;
	const int maxTries = 10;

	while (1) 
	{
		// hack
		if (!viewCell->GetMesh())
			CreateMesh(viewCell);

        Mesh *mesh = viewCell->GetMesh();
		AxisAlignedBox3 box = mesh->mBox;
		
		Vector3 pVector = Vector3(Random(1.0f),
								  Random(1.0f),
								  Random(1.0f));

		viewPoint =  box.GetPoint(pVector);
	
		const Vector3 dVector = Vector3(2 * M_PI * Random(1.0f), M_PI * Random(1.0f), 0.0f);
		direction = Normalize(Vector3(sin(dVector.x), 0.0f, cos(dVector.x)));

		ViewCell *v = GetViewCell(viewPoint);

		if (v && v->GetValid())
		{
			mPreprocessor->GetRenderer()->mViewPoint = viewPoint;
			mPreprocessor->GetRenderer()->mViewDirection = direction;
		
			if (mPreprocessor->GetRenderer()->ValidViewPoint())
			{
				cout << "view point valid " << viewPoint << " " << direction << endl;
				break;
			}
			
		}

		if (++ tries > maxTries)
		{
			cerr << "error: no view point computed" << endl;
			return false;
		}
	}

	ray = SimpleRay(viewPoint, direction, 0, 1);
	//cout << "view point generated: " << viewPoint << " " << direction << endl;

	return true;
}


bool ViewCellsManager::IsValidViewSpace(ViewCell *vc)
{
	SimpleRay simpleRay;
	//check if view point can be generated
	return GenerateViewPoint(vc, simpleRay);
}


bool ViewCellsManager::GenerateRandomViewCells(ViewCellContainer &viewCells, 
											   const int numViewCells)
{
	int generatedViewCells = 0;
	//HaltonSequence halton;
	//float r[1];

	ViewCell::NewMail();

	while (generatedViewCells < numViewCells)
	{
		// savety criterium
		const int tries = 100000 + generatedViewCells;
		int i = 0;

		// generate next view cell
		while (1)
		{
			//halton.GetNext(1, r);
			//const int idx = (int)(r[0] * mViewCells.size() - 1.0f);
			const int idx = (int)RandomValue(0.0f, (float)mViewCells.size() - 0.5f);
			
			ViewCell *viewCell = GetViewCell(idx);

			if (!viewCell->Mailed())
			{
				viewCell->Mail();

				// check for valid view space
				if (IsValidViewSpace(viewCell))
				{
					// valid view cell found
					viewCells.push_back(viewCell);

	                ++ generatedViewCells;
					//cout << "view cell " << generatedViewCells << " generated: " << viewCell->GetId() << endl;	
					break;
				}
				else
				{
					cout << "error: invalid view cell " << generatedViewCells << " with id " << viewCell->GetId() << endl;	
				}
			}

			if (++ i == tries) // no new view cell fond
			{
				cerr << "big error! no view cell found" << endl;
				return false;
			}		
		}			
	}

	return true;
}


ViewCellsManager::~ViewCellsManager()
{
	// HACK: if view cells tree does not 
	// handle view cells, we have to do it here
	// question: rather create view cells resource manager?
	if (!ViewCellsTreeConstructed())
	{
		CLEAR_CONTAINER(mViewCells);
	}
	else
	{
		DEL_PTR(mViewCellsTree);
	}

	DEL_PTR(mMixtureDistribution);
	CLEAR_CONTAINER(mViewCellPoints);
}


Intersectable *ViewCellsManager::GetIntersectable(const VssRay &ray, const bool isTermination) const
{
	if (mUseKdPvs)
	{
		KdNode *node = GetPreprocessor()->
			mKdTree->GetPvsNode(isTermination ?	ray.mTermination : ray.mOrigin);

		return GetPreprocessor()->mKdTree->GetOrCreateKdIntersectable(node);
	}
	else
	{
		return isTermination ? ray.mTerminationObject : ray.mOriginObject;
	}
}


void ViewCellsManager::CollectObjects(const AxisAlignedBox3 &box, ObjectContainer &objects)
{
	GetPreprocessor()->mKdTree->CollectObjects(box, objects);
}


AxisAlignedBox3 ViewCellsManager::GetViewCellBox(ViewCell *vc)
{
	Mesh *m = vc->GetMesh();

	if (m) 
	{
		m->ComputeBoundingBox();
		return m->mBox;
	}

	AxisAlignedBox3 box;
	box.Initialize();

	if (!vc->IsLeaf()) 
	{
		ViewCellInterior *vci = (ViewCellInterior *) vc;

		ViewCellContainer::iterator it = vci->mChildren.begin();
		for (; it != vci->mChildren.end(); ++it) 
		{
			box.Include(GetViewCellBox(*it));
		}
	}

	return box;
}


int ViewCellsManager::CastPassSamples(const int samplesPerPass, 
									  const vector<int> &strategies,
									  VssRayContainer &passSamples
									  ) const
{
	long startTime = GetTime();
	
	SimpleRayContainer simpleRays;
	
	simpleRays.reserve(samplesPerPass);
	// reserve 2 times the size because always creates double rays
	passSamples.reserve(samplesPerPass * 2); 

	// create one third of each type
	int castRays = 0;
	
	const int numRaysPerPass = samplesPerPass / (int)strategies.size();
	vector<int>::const_iterator iit, iit_end = strategies.end();

	for (iit = strategies.begin(); iit != iit_end; ++ iit)
	{
		const int stype = *iit;
		const int newRays = 
			mPreprocessor->GenerateRays(numRaysPerPass, stype, simpleRays);

		cout << "cast " << newRays << " rays of strategy " << stype << endl;
		castRays += newRays;
	}

	cout << "generated " << samplesPerPass << " samples in " 
		 << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;

	startTime = GetTime();

	// shoot simple ray and add it to importance samples
	mPreprocessor->CastRays(simpleRays, passSamples, true);
	
	cout << "cast " <<  samplesPerPass << " samples in " 
		 << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;

	return (int)passSamples.size();
}


/// helper function which destroys rays or copies them into the output ray container
inline void disposeRays(VssRayContainer &rays, VssRayContainer *outRays)
{
	cout << "disposing samples ... ";
	long startTime = GetTime();
	int n = (int)rays.size();

	if (outRays)
	{
		VssRayContainer::const_iterator it, it_end = rays.end();
		for (it = rays.begin(); it != it_end; ++ it)
		{
			outRays->push_back(*it);
		}
	}
	else
	{
		VssRayContainer::const_iterator it, it_end = rays.end();
		for (it = rays.begin(); it != it_end; ++ it)
		{
			if (!(*it)->IsActive())
				delete (*it);
		}
	}

	cout << "finished" << endl;
	Debug << "disposed " << n << " samples in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
}


int ViewCellsManager::Construct(Preprocessor *preprocessor, VssRayContainer *outRays)
{
	int numSamples = 0;

	SimpleRayContainer simpleRays;
	VssRayContainer initialSamples;

	// store pointer to preprocessor for further use during construction
	mPreprocessor = preprocessor;
	
	// now decode distribution string
	char mix[1024];
	Environment::GetSingleton()->GetStringValue("RssPreprocessor.distributions", mix);
	Debug << "using mixture distributions: " << mix << endl;

	mMixtureDistribution = new MixtureDistribution(*mPreprocessor);
	mMixtureDistribution->Construct(mix);

	///////////////////////////////////////////////////////
	//-- Initial sampling for the construction of the view cell hierarchy. 
	//-- We use uniform sampling / box based sampling.
	
	long startTime = GetTime();
	cout << "view cell construction: casting " << mInitialSamples << " initial samples ... " << endl;

	// cast initial samples
	
	// mix of sampling strategies
#if 0
	vector<int>dummy;
	dummy.push_back(SamplingStrategy::OBJECT_BASED_DISTRIBUTION);
	dummy.push_back(SamplingStrategy::SPATIAL_BOX_BASED_DISTRIBUTION);
	dummy.push_back(SamplingStrategy::REVERSE_OBJECT_BASED_DISTRIBUTION);
#endif
	CastPassSamples(mInitialSamples, mStrategies, initialSamples);

	cout << "finished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;

	// construct view cells
	ConstructSubdivision(preprocessor->mObjects, initialSamples);

	// initial samples count for overall samples ...
	numSamples += mInitialSamples;

	// rays can be passed or deleted
	disposeRays(initialSamples, outRays);

	cout << "time needed for initial construction: "
		 << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;

	Debug << "time needed for initial construction: "
		  << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;

	// collect view cells and compute statistics
	ResetViewCells();


	///////////////////
	//-- Initial hierarchy construction finished.
	//-- We can do some stats and visualization
	
	if (0)
	{
		//-- export initial view cell partition
		Debug << "\nView cells after initial sampling:\n" << mCurrentViewCellsStats << endl;

		const string filename("viewcells.wrl");
		Exporter *exporter = Exporter::GetExporter(filename.c_str());
	
		if (exporter)
		{
			cout << "exporting initial view cells (=leaves) to " << filename.c_str() << " ... ";

			if (mExportGeometry)
			{
				exporter->ExportGeometry(preprocessor->mObjects);
			}

			exporter->SetWireframe();
			ExportViewCellsForViz(exporter, NULL, mColorCode, GetClipPlane());

			delete exporter;
			cout << "finished" << endl;
		}
	}


	//////////////////////
	//-- Cast some more sampling after initial construction.
	//-- The additional rays can be used to gain
	//-- some more information before the bottom-up merge
	//-- note: guided rays could be used for this task

	// time spent after construction of the initial partition
	startTime = GetTime();
	const int n = mConstructionSamples; //+initialSamples;

	while (numSamples < n)
	{
		cout << "casting " << mSamplesPerPass << " samples of " << n << " ... ";
		Debug << "casting " << mSamplesPerPass << " samples of " << n << " ... ";

		VssRayContainer constructionSamples;

		// cast new samples
		numSamples += CastPassSamples(mSamplesPerPass, 
									  mStrategies,
									  constructionSamples);

		cout << "finished" << endl;
		cout << "computing sample contribution for " << (int)constructionSamples.size() << " samples ... ";

		// computes sample contribution of cast rays
		if (SAMPLE_AFTER_SUBDIVISION)
			ComputeSampleContributions(constructionSamples, true, false);

		cout << "finished" << endl;

		disposeRays(constructionSamples, outRays);
		cout << "total samples: " << numSamples << endl;
	}

	if (0)
	{
		///////////////
		//-- Get stats after the additional sampling step
		//-- and before the bottom-up merge step

		EvaluateViewCellsStats();
		Debug << "\noriginal view cell partition before post process:\n" 
			  << mCurrentViewCellsStats << endl;
	
		mRenderer->RenderScene();
		SimulationStatistics ss;
		static_cast<RenderSimulator *>(mRenderer)->GetStatistics(ss);

		Debug << ss << endl;
	}

	////////////////////
	//-- post processing of the initial construction
	//-- We can bottom-up merge the view cells in this step
	//-- We can additionally cast some post processing sample rays.
	//-- These rays can be used to store the view cells with the rays

	VssRayContainer postProcessSamples;
	cout << "casting " << mPostProcessSamples << " post process samples ..." << endl;
	
	CastPassSamples(mPostProcessSamples, mStrategies, postProcessSamples);

	cout << "finished post process sampling" << endl;
	cout << "starting post processing and visualization" << endl;

	// store view cells with rays for post processing?
	const bool storeViewCells = true;

	if (SAMPLE_AFTER_SUBDIVISION)
		ComputeSampleContributions(postProcessSamples, true, storeViewCells);

	PostProcess(preprocessor->mObjects, postProcessSamples);

	const float secs = TimeDiff(startTime, GetTime()) * 1e-3f;
	cout << "post processing (=merge) finished in " << secs << " secs" << endl;

	Debug << "post processing time: " << secs << endl;
	disposeRays(postProcessSamples, outRays);


	////////////////
	//-- Evaluation of the resulting view cell partition. 
	//-- We cast a number of new samples and measure the render cost

	if (mEvaluateViewCells)
	{
		EvalViewCellPartition();
	}
	
	/////////////////
	//-- Show some visualizations

	if (mShowVisualization)
	{
		///////////////
		//-- visualization rays, e.g., to show some samples in the scene
		
		VssRayContainer visSamples;
		int numSamples = CastPassSamples(mVisualizationSamples,
										 mStrategies, 
										 visSamples);

		if (SAMPLE_AFTER_SUBDIVISION)
			ComputeSampleContributions(visSamples, true, storeViewCells);

		// various visualizations
		Visualize(preprocessor->mObjects, visSamples);

		disposeRays(visSamples, outRays);
	}

	// recalculate view cells
	EvaluateViewCellsStats();

	// compress the final solution
	if (0) CompressViewCells();

	// write view cells to disc
	if (mExportViewCells)
	{
		char filename[100];

		Environment::GetSingleton()->GetStringValue("ViewCells.filename", filename);
		ExportViewCells(filename, mExportPvs, mPreprocessor->mObjects);
	}

	return numSamples;
}


AxisAlignedPlane *ViewCellsManager::GetClipPlane()
{
	return mUseClipPlaneForViz ? &mClipPlaneForViz : NULL;
}


ViewCellsManager *ViewCellsManager::LoadViewCells(const string &filename, 
												  ObjectContainer &pvsObjects,
												  bool finalizeViewCells,
												  BoundingBoxConverter *bconverter)
												 
{
	if (!Debug.is_open()) Debug.open("debug.log");


	if (strstr(filename.c_str(), ".bn"))
	{
		Debug << "binary view cells format detected" << endl;

		return LoadViewCellsBinary(filename, 
			                       pvsObjects,
								   finalizeViewCells,
								   bconverter);
	}
	else
	{
		Debug << "xml view cells format detected" << endl;

		// give just an empty container as parameter:
		// this loading function is used in the engine, thus it
		// does not need to load the entities the preprocessor works on
		ObjectContainer preprocessorObjects;

		return LoadViewCells(filename, 
			                 pvsObjects,
							 preprocessorObjects,
							 finalizeViewCells,
							 bconverter);
	}
}

void ViewCellsManager::LoadIndexedBoundingBoxesBinary(IN_STREAM &stream, IndexedBoundingBoxContainer &iboxes)
{
	int numBoxes;
	stream.read(reinterpret_cast<char *>(&numBoxes), sizeof(int));

	iboxes.reserve(numBoxes);

	Vector3 bmin;
	Vector3 bmax;
	int id;

	PerfTimer boxTimer;

	boxTimer.Start();
	boxTimer.Entry();
	
	for (int i = 0; i < numBoxes; ++ i)
	{
		stream.read(reinterpret_cast<char *>(&bmin), sizeof(Vector3));
		stream.read(reinterpret_cast<char *>(&bmax), sizeof(Vector3));
		stream.read(reinterpret_cast<char *>(&id), sizeof(int));

		iboxes.push_back(IndexedBoundingBox(id, AxisAlignedBox3(bmin, bmax)));
	}


	boxTimer.Exit();

	Debug << numBoxes << " boxes loaded in " << boxTimer.TotalTime() << " secs" << endl;
}


ViewCellsManager *ViewCellsManager::LoadViewCells(const string &filename, 
												  ObjectContainer &pvsObjects,
												  ObjectContainer &preprocessorObjects,
												  bool finalizeViewCells,
												  BoundingBoxConverter *bconverter)												 
{
	ViewCellsParser parser;
	ViewCellsManager *vm = NULL;

	const long startTime = GetTime();
	const bool success = parser.ParseViewCellsFile(filename, 
												   &vm, 
												   pvsObjects, 
												   preprocessorObjects, 
												   bconverter);

	if (!success)
	{
		Debug << "Error: loading view cells failed!" << endl;
		DEL_PTR(vm);

		return NULL;
	}
	
	if (0) //hack: reset function should work, but something is wrong ..
	{
		vm->ResetViewCells();
	}
	else
	{
		ViewCellContainer leaves;

		vm->mViewCells.clear();
		vm->mViewCellsTree->CollectLeaves(vm->mViewCellsTree->GetRoot(), leaves);
		
		ViewCellContainer::const_iterator it, it_end = leaves.end();

		for (it = leaves.begin(); it != it_end; ++ it)
		{
			vm->mViewCells.push_back(*it);
		}
	}

	vm->mViewCellsFinished = true;
	vm->mMaxPvsSize = (int)pvsObjects.size();

	if (finalizeViewCells)
	{
		// do some final computations, e.g.,
		// create the meshes and compute view cell volumes
		const bool createMeshes = true;
		vm->FinalizeViewCells(createMeshes);
	}

	cout << (int)vm->mViewCells.size() << " view cells loaded in "
		 << TimeDiff(startTime, GetTime()) * 1e-3f << " secs" << endl;

	Debug << (int)vm->mViewCells.size() << " view cells loaded in "
		  << TimeDiff(startTime, GetTime()) * 1e-3f << " secs" << endl;
	
	return vm;
}


bool VspBspViewCellsManager::ExportViewCells(const string filename, 
											 const bool exportPvs, 
											 const ObjectContainer &objects)
{
	// no view cells constructed yet
	if (!ViewCellsConstructed() || !ViewCellsTreeConstructed())
		return false;

	cout << "exporting view cells to xml ... ";

	OUT_STREAM stream(filename.c_str());

	// we need unique ids for each view cell
	CreateUniqueViewCellIds();

	stream << "<?xml version=\"1.0\" encoding=\"UTF-8\"?>"<<endl;
	stream << "<VisibilitySolution>" << endl;

	if (exportPvs) 
	{
		//-- export bounding boxes
		stream << "<BoundingBoxes>" << endl;

		if (mUseKdPvs)
		{
			vector<KdIntersectable *>::iterator kit, kit_end = GetPreprocessor()->mKdTree->mKdIntersectables.end();

			int id = 0;
			for (kit = GetPreprocessor()->mKdTree->mKdIntersectables.begin(); kit != kit_end; ++ kit, ++ id)
			{
				Intersectable *obj = *kit;
				const AxisAlignedBox3 box = obj->GetBox();
		  
				obj->SetId(id);
	
				stream << "<BoundingBox" << " id=\"" << id << "\""
					   << " min=\"" << box.Min().x << " " << box.Min().y << " " << box.Min().z << "\""
					   << " max=\"" << box.Max().x << " " << box.Max().y << " " << box.Max().z << "\" />" << endl;
			}
		}
		else
		{
			ObjectContainer::const_iterator oit, oit_end = objects.end();
		
			for (oit = objects.begin(); oit != oit_end; ++ oit)
			{
				const AxisAlignedBox3 box = (*oit)->GetBox();

				////////////
				//-- the bounding boxes

				stream << "<BoundingBox" << " id=\"" << (*oit)->GetId() << "\""
					   << " min=\"" << box.Min().x << " " << box.Min().y << " " << box.Min().z << "\""
					   << " max=\"" << box.Max().x << " " << box.Max().y << " " << box.Max().z << "\" />" << endl;
			}
		}

		stream << "</BoundingBoxes>" << endl;
	}

	
	/////////////
	//-- export the view cells and the pvs

	const int numViewCells = mCurrentViewCellsStats.viewCells;
	stream << "<ViewCells number=\"" << numViewCells << "\" >" << endl;

	mViewCellsTree->Export(stream, exportPvs);

	stream << "</ViewCells>" << endl;


	//////////
	//-- export the view space hierarchy
	
	stream << "<ViewSpaceHierarchy type=\"bsp\""
		   << " min=\"" << mViewSpaceBox.Min().x << " " << mViewSpaceBox.Min().y << " " << mViewSpaceBox.Min().z << "\""
		   << " max=\"" << mViewSpaceBox.Max().x << " " << mViewSpaceBox.Max().y << " " << mViewSpaceBox.Max().z << "\">" << endl;

	mVspBspTree->Export(stream);
	stream << "</ViewSpaceHierarchy>" << endl;

	stream << "</VisibilitySolution>" << endl;

	stream.close();
	cout << "finished" << endl;

	return true;
}


void ViewCellsManager::EvalViewCellHistogram(const string filename, 
											 const int nViewCells)
{
	std::ofstream outstream;
	outstream.open(filename.c_str());

	ViewCellContainer viewCells;
	
	// the collect best viewcells does not work?
	mViewCellsTree->CollectBestViewCellSet(viewCells, nViewCells);

	float maxRenderCost, minRenderCost;

	// sort by render cost
	sort(viewCells.begin(), viewCells.end(), SmallerRenderCost);

	minRenderCost = viewCells.front()->GetRenderCost();
	maxRenderCost = viewCells.back()->GetRenderCost();

	Debug << "histogram min rc: " << minRenderCost << " max rc: " << maxRenderCost << endl;

    int histoIntervals;
	Environment::GetSingleton()->GetIntValue("Preprocessor.histogram.intervals", histoIntervals);
	const int intervals = min(histoIntervals, (int)viewCells.size());

	int histoMaxVal;
	Environment::GetSingleton()->GetIntValue("Preprocessor.histogram.maxValue", histoMaxVal);
	maxRenderCost = min((float)histoMaxVal, maxRenderCost);

	
	const float range = maxRenderCost - minRenderCost;
	const float stepSize = range / (float)intervals;

	float currentRenderCost = minRenderCost;//(int)ceil(minRenderCost);

	const float totalRenderCost = mViewCellsTree->GetRoot()->GetRenderCost();
	const float totalVol = GetViewSpaceBox().GetVolume();
	//const float totalVol = mViewCellsTree->GetRoot()->GetVolume();

	int j = 0;
	int i = 0;
	
	ViewCellContainer::const_iterator it = viewCells.begin(), it_end = viewCells.end();		

	// count for integral
	float volSum = 0;
	int smallerCostSum = 0;
	
	// note can skip computations for view cells already 
	// evaluated and delete them from vector ...
    while (1)
	{
		// count for histogram value
		float volDif = 0;
		int smallerCostDif = 0;

		while ((i < (int)viewCells.size()) && (viewCells[i]->GetRenderCost() < currentRenderCost))
		{
			volSum += viewCells[i]->GetVolume();
			volDif += viewCells[i]->GetVolume();

			++ i;
			++ smallerCostSum;
			++ smallerCostDif;
		}
		
		if ((i >= (int)viewCells.size()) || (currentRenderCost >= maxRenderCost))
			break;
		
		const float rcRatio = currentRenderCost / maxRenderCost;
		const float volRatioSum = volSum / totalVol;
		const float volRatioDif = volDif / totalVol;

		outstream << "#Pass\n" << j ++ << endl;
		outstream << "#RenderCostRatio\n" << rcRatio << endl;
		outstream << "#WeightedCost\n" << currentRenderCost / totalVol << endl;
		outstream << "#ViewCellsDif\n" << smallerCostDif << endl;
		outstream << "#ViewCellsSum\n" << smallerCostSum << endl;	
		outstream << "#VolumeDif\n" << volRatioDif << endl << endl;
		outstream << "#VolumeSum\n" << volRatioSum << endl << endl;

		// increase current render cost
		currentRenderCost += stepSize;
	}

	outstream.close();
}

void ViewCellsManager::EvalViewCellHistogramForPvsSize(const string filename, 
													   const int nViewCells)
{
	std::ofstream outstream;
	outstream.open(filename.c_str());

	ViewCellContainer viewCells;

#ifdef USE_BIT_PVS
	cout << "objects size: " << (int)ObjectPvsIterator::sObjects.size() << endl;
	cout << "pvs size: " <<  ObjectPvs::sPvsSize << endl;
#endif

	// $$ JB hack - the collect best viewcells does not work?
#if 0
	mViewCellsTree->CollectBestViewCellSet(viewCells, nViewCells);
#else
	viewCells = mViewCells;
#endif

	ViewCellContainer::iterator it = viewCells.begin(), it_end = viewCells.end();		
	
	for (; it != it_end; ++it) 
	{
		(*it)->UpdatePvsCost();
	}

	float maxPvs, maxVal, minVal;
	
	// sort by pvs size
	sort(viewCells.begin(), viewCells.end(), SmallerPvs);

	maxPvs = viewCells.back()->GetTrianglesInPvs();
	minVal = 0;

	// hack: normalize pvs size
	int histoMaxVal;
	Environment::GetSingleton()->GetIntValue("Preprocessor.histogram.maxValue", histoMaxVal);
	maxVal = max((float)histoMaxVal, maxPvs);
		
	Debug << "histogram minpvssize: " << minVal << " maxpvssize: " << maxVal 
		<< " real maxpvs " << maxPvs << endl;

	int histoIntervals;
	Environment::GetSingleton()->GetIntValue("Preprocessor.histogram.intervals", histoIntervals);
	const int intervals = min(histoIntervals, (int)viewCells.size());

	const float range = maxVal - minVal;
	int stepSize = (int)(range / intervals);

	// set step size to avoid endless loop
	if (!stepSize) stepSize = 1;
	
	Debug << "intervals " << histoIntervals << endl;
	Debug << "stepsize: " << stepSize << endl;
	cout << "intervals " << histoIntervals << endl;
	cout << "stepsize: " << stepSize << endl;

	const float totalRenderCost = mViewCellsTree->GetRoot()->GetRenderCost();
	const float totalVol = GetViewSpaceBox().GetVolume();

	float currentPvs = minVal;
	
	int i = 0;
	int j = 0;
	float volSum = 0;
	int smallerSum = 0;

	it = viewCells.begin();
	
	for (int j = 0; j < intervals; ++ j)
	{
		float volDif = 0;
		int smallerDif = 0;

		while ((i < (int)viewCells.size()) && 
			   (viewCells[i]->GetTrianglesInPvs() < currentPvs))
		{
			volDif += viewCells[i]->GetVolume();
			volSum += viewCells[i]->GetVolume();

			++ i;
			++ smallerDif;
			++ smallerSum;
		}
		
		const float volRatioDif = volDif / totalVol;
		const float volRatioSum = volSum / totalVol;

		outstream << "#Pass\n" << j << endl;
		outstream << "#Pvs\n" << currentPvs << endl;
		outstream << "#ViewCellsDif\n" << smallerDif << endl;
		outstream << "#ViewCellsSum\n" << smallerSum << endl;	
		outstream << "#VolumeDif\n" << volRatioDif << endl << endl;
		outstream << "#VolumeSum\n" << volRatioSum << endl << endl;
	
		//-- increase current pvs size to define next interval
		currentPvs += stepSize;
	}

	outstream.close();
}


void ViewCellsManager::EvalViewCellHistogramForPvsSize(const string filename, 
													   ViewCellContainer &viewCells)
{
	std::ofstream outstream;
	outstream.open(filename.c_str());

	float maxPvs, maxVal, minVal;
	
	// sort by pvs size
	sort(viewCells.begin(), viewCells.end(), SmallerPvs);

	maxPvs = viewCells.back()->GetTrianglesInPvs();
	minVal = 0;

	// hack: normalize pvs size
	int histoMaxVal;
	Environment::GetSingleton()->GetIntValue("Preprocessor.histogram.maxValue", histoMaxVal);
	maxVal = max((float)histoMaxVal, maxPvs);
		
	Debug << "histogram minpvssize: " << minVal << " maxpvssize: " << maxVal 
		<< " real maxpvs " << maxPvs << endl;

	int histoIntervals;
	Environment::GetSingleton()->GetIntValue("Preprocessor.histogram.intervals", histoIntervals);
	const int intervals = min(histoIntervals, (int)viewCells.size());

	const float range = maxVal - minVal;
	int stepSize = (int)(range / intervals);

	// set step size to avoid endless loop
	if (!stepSize) stepSize = 1;
	
	Debug << "intervals " << histoIntervals << endl;
	Debug << "stepsize: " << stepSize << endl;
	cout << "intervals " << histoIntervals << endl;
	cout << "stepsize: " << stepSize << endl;

	const float totalRenderCost = mViewCellsTree->GetRoot()->GetRenderCost();
	const float totalVol = GetViewSpaceBox().GetVolume();

	float currentPvs = minVal;
	
	int i = 0;
	int j = 0;
	float volSum = 0;
	int smallerSum = 0;

	//ViewCellContainer::const_iterator it = viewCells.begin(), it_end = viewCells.end();	
	
	for (int j = 0; j < intervals; ++ j)
	{
		float volDif = 0;
		int smallerDif = 0;

		while ((i < (int)viewCells.size()) && 
			   (viewCells[i]->GetTrianglesInPvs() < currentPvs))
		{
			volDif += viewCells[i]->GetVolume();
			volSum += viewCells[i]->GetVolume();

			++ i;
			++ smallerDif;
			++ smallerSum;
		}
		
		//		if (0 && (i < (int)viewCells.size()))
		//		  Debug << "new pvs cost increase: " << mViewCellsTree->GetTrianglesInPvs(viewCells[i]) 
		//				<< " " << currentPvs << endl;
		
		const float volRatioDif = volDif / totalVol;
		const float volRatioSum = volSum / totalVol;

		outstream << "#Pass\n" << j << endl;
		outstream << "#Pvs\n" << currentPvs << endl;
		outstream << "#ViewCellsDif\n" << smallerDif << endl;
		outstream << "#ViewCellsSum\n" << smallerSum << endl;	
		outstream << "#VolumeDif\n" << volRatioDif << endl << endl;
		outstream << "#VolumeSum\n" << volRatioSum << endl << endl;
	
		//-- increase current pvs size to define next interval
		currentPvs += stepSize;
	}

	outstream.close();
}


bool ViewCellsManager::GetExportPvs() const 
{
	return mExportPvs;
}


void ViewCellsManager::ResetPvs()
{
	if (ViewCellsTreeConstructed())
	{
		mViewCellsTree->ResetPvs();
	}
	else
	{
		cout << "view cells tree not constructed" << endl;
	}
}


void ViewCellsManager::ExportStats(const string &fileName)
{
	mViewCellsTree->ExportStats(fileName);
}


void ViewCellsManager::EvalViewCellPartition()
{
	int samplesPerPass;
	int numSamples;
	int castSamples = 0;
	char str[64]; 
	int oldSamples = 0;

	int samplesForStats;

	Environment::GetSingleton()->GetIntValue("ViewCells.Evaluation.samplesPerPass", samplesPerPass);
	Environment::GetSingleton()->GetIntValue("ViewCells.Evaluation.samplesForStats", samplesForStats);
	Environment::GetSingleton()->GetIntValue("ViewCells.Evaluation.samples", numSamples);

	char statsPrefix[100];
	Environment::GetSingleton()->GetStringValue("ViewCells.Evaluation.statsPrefix", statsPrefix);

	Debug << "view cell evaluation samples per pass: " << samplesPerPass << endl;
	Debug << "view cell evaluation samples: " << numSamples << endl;
	Debug << "view cell stats prefix: " << statsPrefix << endl;

	cout << "reseting pvs ... ";
		
	const bool startFromZero = true;

	// reset pvs and start over from zero
	if (startFromZero)
	{
		mViewCellsTree->ResetPvs();
	}
	else // start from current sampless
	{
		// statistics before casting more samples
		cout << "compute new statistics ... ";
		sprintf(str, "-%09d-eval.log", castSamples);
		string fName = string(statsPrefix) + string(str);

		mViewCellsTree->ExportStats(fName);
		cout << "finished" << endl;
	}

	cout << "finished" << endl;
    cout << "Evaluating view cell partition ... " << endl;

	while (castSamples < numSamples)
	{		
		///////////////
		//-- we have to use uniform sampling strategy for construction rays

		VssRayContainer evaluationSamples;
		const int samplingType = mEvaluationSamplingType;

		long startTime = GetTime();

		cout << "casting " << samplesPerPass << " samples ... ";
		Debug << "casting " << samplesPerPass << " samples ... ";

		CastPassSamples(samplesPerPass, mStrategies, evaluationSamples);
		
		castSamples += samplesPerPass;

		Real timeDiff = TimeDiff(startTime, GetTime());
		
		cout << "finished in " << timeDiff * 1e-3f << " secs" << endl;
		cout << "computing sample contributions of " << (int)evaluationSamples.size()  << " samples ... ";
		
		Debug << "finished in " << timeDiff * 1e-3f << " secs" << endl;
		Debug << "computing sample contributions of " << (int)evaluationSamples.size()  << " samples ... ";

		startTime = GetTime();

		ComputeSampleContributions(evaluationSamples, true, false);

		timeDiff = TimeDiff(startTime, GetTime());
		cout << "finished in " << timeDiff * 1e-3 << " secs" << endl;
		Debug << "finished in " << timeDiff * 1e-3 << " secs" << endl;

		if ((castSamples >= samplesForStats + oldSamples) || (castSamples >= numSamples))
		{
			oldSamples += samplesForStats;

			///////////
			//-- output stats

			sprintf(str, "-%09d-eval.log", castSamples);
			string fileName = string(statsPrefix) + string(str);

			///////////////
			//-- propagate pvs or pvs size information

			startTime = GetTime();
			ObjectPvs pvs;

			cout << "updating pvs for evaluation ... " << endl;

			UpdatePvsForEvaluation(mViewCellsTree->GetRoot(), pvs);

			timeDiff = TimeDiff(startTime, GetTime());
			cout << "finished updating the pvs in " << timeDiff * 1e-3 << " secs" << endl;
			Debug << "pvs evaluated in " << timeDiff * 1e-3 << " secs" << endl;
		
			startTime = GetTime();
			cout << "compute new statistics ... " << endl;

			ExportStats(fileName);

			timeDiff = TimeDiff(startTime, GetTime());
			cout << "finished in " << timeDiff * 1e-3 << " secs" << endl;
			Debug << "statistis computed in " << timeDiff * 1e-3 << " secs" << endl;
		}

		disposeRays(evaluationSamples, NULL);
	}
	

	////////////
	//-- histogram

	const int numLeaves = mViewCellsTree->GetNumInitialViewCells(mViewCellsTree->GetRoot());
	bool useHisto;
	int histoStepSize;

	Environment::GetSingleton()->GetBoolValue("ViewCells.Evaluation.histogram", useHisto);
	Environment::GetSingleton()->GetIntValue("ViewCells.Evaluation.histoStepSize", histoStepSize);

	if (useHisto)
	{
		// evaluate view cells in a histogram		
		char s[64];

		for (int pass = histoStepSize; pass <= numLeaves; pass += histoStepSize)
		{
			string filename;

			cout << "computing histogram for " << pass << " view cells" << endl;
#if 0
			//-- evaluate histogram for render cost
			sprintf(s, "-%09d-histo.log", pass);
			filename = string(statsPrefix) + string(s);

			EvalViewCellHistogram(filename, pass);

#endif
			//////////////////////////////////////////
            //-- evaluate histogram for pvs size

			cout << "computing pvs histogram for " << pass << " view cells" << endl;

			sprintf(s, "-%09d-histo-pvs.log", pass);
			filename = string(statsPrefix) + string(s);

			EvalViewCellHistogram(filename, pass);
			//			EvalViewCellHistogramForPvsSize(filename, pass);
		}
	}
}


inline float EvalMergeCost(ViewCell *root, ViewCell *candidate)
{
	return root->GetPvs().GetPvsHomogenity(candidate->GetPvs());
}


/// Returns index of the best view cells of the neighborhood
static int GetBestViewCellIdx(ViewCell *root, const ViewCellContainer &neighborhood)
{
	int bestViewCellIdx = 0;

	float mergeCost = Limits::Infinity;
	int i = 0;

	ViewCellContainer::const_iterator vit, vit_end = neighborhood.end();

	for (vit = neighborhood.begin(); vit != vit_end; ++ vit, ++ i)
	{
		const float mc = EvalMergeCost(root, *vit);
		
		if (mc < mergeCost)
		{
			mergeCost = mc;
			bestViewCellIdx = i;
		}
	}

	return bestViewCellIdx;
}


void ViewCellsManager::SetMaxFilterSize(const int size) 
{
	mMaxFilterSize = size;
}


float ViewCellsManager::ComputeRenderCost(const int tri, const int obj) //const
{
	return max((float)tri * mTriangleWeight, (float)obj * mObjectWeight);
}


ViewCell *ViewCellsManager::ConstructLocalMergeTree(ViewCell *currentViewCell, 
													const ViewCellContainer &viewCells)
{
	ViewCell *root = currentViewCell;
	ViewCellContainer neighborhood = viewCells;

	ViewCellContainer::const_iterator it, it_end = neighborhood.end();

	const int n = min(mMaxFilterSize, (int)neighborhood.size());
	
	/////////////////
	//-- use priority queue to merge leaf pairs
	
	for (int nMergedViewCells = 0; nMergedViewCells < n; ++ nMergedViewCells)
	{
		const int bestViewCellIdx = GetBestViewCellIdx(root, neighborhood);
		
		ViewCell *bestViewCell = neighborhood[bestViewCellIdx];
	
		// remove from vector
		swap(neighborhood[bestViewCellIdx], neighborhood.back());
		neighborhood.pop_back();
	
		if (!bestViewCell || !root)
            cout << "warning!!" << endl;
		
		// create new root of the hierarchy
		root = MergeViewCells(root, bestViewCell);
	}

	return root;	
}


struct SortableViewCellEntry {

	SortableViewCellEntry() {}
	SortableViewCellEntry(const float v, ViewCell *cell):mValue(v), mViewCell(cell) {}

	float mValue;
	ViewCell *mViewCell;

	friend bool operator<(const SortableViewCellEntry &a, const SortableViewCellEntry &b) {
		return a.mValue < b.mValue;
	}
};


ViewCell * ViewCellsManager::ConstructLocalMergeTree2(ViewCell *currentViewCell, 
													  const ViewCellContainer &viewCells)
{
  
  vector<SortableViewCellEntry> neighborhood(viewCells.size());
  int i, j;
  for (i = 0, j = 0; i < viewCells.size(); i++) {
	if (viewCells[i] != currentViewCell) 
	  neighborhood[j++] = SortableViewCellEntry(
												EvalMergeCost(currentViewCell, viewCells[i]),
												viewCells[i]);
  }
  neighborhood.resize(j);
  
  sort(neighborhood.begin(), neighborhood.end());
  
  ViewCell *root = currentViewCell;
  
  vector<SortableViewCellEntry>::const_iterator it, it_end = neighborhood.end();
  
  const int n = min(mMaxFilterSize, (int)neighborhood.size());
  //-- use priority queue to merge leaf pairs
  
  //cout << "neighborhood: " << neighborhood.size() << endl;
  for (int nMergedViewCells = 0; nMergedViewCells < n; ++ nMergedViewCells)
  {
	  ViewCell *bestViewCell = neighborhood[nMergedViewCells].mViewCell;
	  //cout <<nMergedViewCells<<":"<<"homogenity=" <<neighborhood[nMergedViewCells].mValue<<endl;
	  // create new root of the hierarchy
	  root = MergeViewCells(root, bestViewCell);
	  // set negative cost so that this view cell gets deleted
	  root->SetMergeCost(-1.0f);
  }
  
  return root;	
}

void
ViewCellsManager::DeleteLocalMergeTree(ViewCell *vc
									   ) const
{
	if (!vc->IsLeaf() && vc->GetMergeCost() < 0.0f) 
	{	
		ViewCellInterior *vci = (ViewCellInterior *) vc;
		ViewCellContainer::const_iterator it, it_end = vci->mChildren.end();

        for (it = vci->mChildren.begin(); it != it_end; ++ it)
			DeleteLocalMergeTree(*it);
		
		vci->mChildren.clear();
		
		delete vci;
  }
}


bool ViewCellsManager::CheckValidity(ViewCell *vc,
									 int minPvsSize,
									 int maxPvsSize) const
{

	const float pvsCost = vc->GetPvs().EvalPvsCost();

	if ((pvsCost > maxPvsSize) || (pvsCost < minPvsSize))
	{
		cout << "err: " << pvsCost << " " << minPvsSize << " " << maxPvsSize << endl;
		return false;
	}

	return true;
}


int ViewCellsManager::ComputeBoxIntersections(const AxisAlignedBox3 &box, 
											  ViewCellContainer &viewCells) const
{
	return 0;
};


AxisAlignedBox3 ViewCellsManager::GetFilterBBox(const Vector3 &viewPoint, 
												const float width) const
{
  float w = Magnitude(mViewSpaceBox.Size())*width;
  Vector3 min = viewPoint - w * 0.5f;
  Vector3 max = viewPoint + w * 0.5f;
  
  return AxisAlignedBox3(min, max);
}


void ViewCellsManager::GetPrVS(const Vector3 &viewPoint,
							   PrVs &prvs,
							   const float filterWidth)
{
	ViewCell *currentViewCell = GetViewCell(viewPoint);

	if (mMaxFilterSize < 1) {
		prvs.mViewCell = currentViewCell;
		return;
	}

	const AxisAlignedBox3 box = GetFilterBBox(viewPoint, filterWidth);

	if (currentViewCell) 
	{
		ViewCellContainer viewCells;
		ComputeBoxIntersections(box, viewCells);

		ViewCell *root = ConstructLocalMergeTree2(currentViewCell, viewCells);
		prvs.mViewCell = root;

	} 
	else
	{
		prvs.mViewCell = NULL;
		//prvs.mPvs = root->GetPvs();
	}
}


bool ViewCellsManager::ViewCellsTreeConstructed() const
{
    return (mViewCellsTree && mViewCellsTree->GetRoot());
}


void ViewCellsManager::SetValidity(ViewCell *vc,
								   int minPvs,
								   int maxPvs) const
{
	vc->SetValid(CheckValidity(vc, minPvs, maxPvs));
}


void
ViewCellsManager::SetValidity(
							  int minPvsSize,
							  int maxPvsSize) const
{
	ViewCellContainer::const_iterator it, it_end = mViewCells.end();


	for (it = mViewCells.begin(); it != it_end; ++ it) 
	{
		SetValidity(*it, minPvsSize, maxPvsSize);
	}
}

void
ViewCellsManager::SetValidityPercentage(
										const float minValid,
										const float maxValid
										)
{
  ObjectPvs dummyPvs;
  // update pvs sizes
  for (int i = 0; i < (int)mViewCells.size(); ++ i) {
	UpdatePvsForEvaluation(mViewCells[i], dummyPvs);
  }
  
  sort(mViewCells.begin(), mViewCells.end(), SmallerPvs);
  
  int start = (int)(mViewCells.size() * minValid);
  int end = (int)(mViewCells.size() * maxValid);
  
  for (int i = 0; i < (int)mViewCells.size(); ++ i)
	{
	  //	  cout<<"pvs:"<<mViewCells[i]->GetCachedPvsCost()<<endl;
	  mViewCells[i]->SetValid(i >= start && i <= end);
	}
}


int ViewCellsManager::CountValidViewcells() const
{
	ViewCellContainer::const_iterator it, it_end = mViewCells.end();
	int valid = 0;

	for (it = mViewCells.begin(); it != it_end; ++ it) 
	{	
		if ((*it)->GetValid())
			++ valid;
	}

	return valid;
}


bool ViewCellsManager::LoadViewCellsGeometry(const string filename, 
											 const bool extrudeBaseTriangles)
{
	/// we use predefined view cells from now on
	mUsePredefinedViewCells = true;
	X3dParser parser;
	
	if (extrudeBaseTriangles)
	{
		Environment::GetSingleton()->GetFloatValue("ViewCells.height", parser.mViewCellHeight);
		const bool success = parser.ParseFile(filename, *this);

		if (!success)
			return false;
	}
	else
	{
		// hack: use standard mesh loading
		// create temporary scene graph for loading the view cells geometry
		// note: delete the meshes as they are created two times for transformed mesh instances.
		SceneGraphNode *root = new SceneGraphNode();
		const bool success = parser.ParseFile(filename, root, true);
		
		if (!success)
		{
			DEL_PTR(root);
			return false;
		}

		ObjectContainer::const_iterator oit, oit_end = root->mGeometry.end();
		
		for (oit = root->mGeometry.begin(); oit != oit_end; ++ oit)
		{
			Mesh *mesh;
			if ((*oit)->Type() == Intersectable::TRANSFORMED_MESH_INSTANCE)
			{
				TransformedMeshInstance *mit = static_cast<TransformedMeshInstance *>(*oit);
				mesh = MeshManager::GetSingleton()->CreateResource();
				mit->GetTransformedMesh(*mesh);
			}
			else if ((*oit)->Type() == Intersectable::MESH_INSTANCE)
			{
				MeshInstance *mit = static_cast<MeshInstance *>(*oit);
				mesh = mit->GetMesh();
			}
			mesh->ComputeBoundingBox();
			mViewCells.push_back(GenerateViewCell(mesh));
		}

		DEL_PTR(root);
	}

	// set view space box to bounding box of the view cells
	AxisAlignedBox3 bbox;
	bbox.Initialize();
	ViewCellContainer::iterator it = mViewCells.begin(), it_end = mViewCells.end();

	for (; it != it_end; ++ it) 
	{
		bbox.Include((*it)->GetMesh()->mBox);
	}

	SetViewSpaceBox(bbox);
	cout << "view space box: " << bbox << endl;
	cout << "generated " << (int)mViewCells.size() << " view cells using the geometry " << filename << endl;

	return true;
}


bool ViewCellsManager::GetViewPoint(Vector3 &viewPoint) const
{
  viewPoint = mViewSpaceBox.GetRandomPoint();
  return true;
}

bool ViewCellsManager::GetViewPoint(Vector3 &viewPoint, const Vector3 &params) const
{
  viewPoint = mViewSpaceBox.GetRandomPoint(params);
  return true;
}


float ViewCellsManager::GetViewSpaceVolume()
{
	return mViewSpaceBox.GetVolume() * (2.0f * sqr((float)M_PI));
}


bool ViewCellsManager::ViewPointValid(const Vector3 &viewPoint) const
{
	if (!ViewCellsConstructed())
	{
		return mViewSpaceBox.IsInside(viewPoint);
	}
	else 
	{
		if (!mViewSpaceBox.IsInside(viewPoint))
			return false;

		ViewCell *viewcell = GetViewCell(viewPoint);

		if (!viewcell || !viewcell->GetValid())
			return false;
	}

	return true;
}


float
ViewCellsManager::ComputeSampleContributions(const VssRayContainer &rays,
											 const bool addContributions,
   											 const bool storeViewCells,
											 const bool useHitObjects)
{
	float sum = 0.0f;

	VssRayContainer::const_iterator it, it_end = rays.end();

	for (it = rays.begin(); it != it_end; ++ it) 
	{
		if (!ViewCellsConstructed()) 
		{
			// view cells not yet constructed
			// just take the lenghts of the rays as contributions
			if ((*it)->mTerminationObject)
			{
				sum += (*it)->Length();
			}
		} 
		else 
		{
			sum += ComputeSampleContribution(*(*it), addContributions, storeViewCells, useHitObjects);
		}
	}

	cout << "view cell cast time: " << viewCellCastTimer.TotalTime() << " s" << endl;
	Debug << "view cell cast time: " << viewCellCastTimer.TotalTime() << " s" << endl;

	cout << "pvs time: " << pvsTimer.TotalTime() << " s" << endl;
	Debug << "pvs time: " << pvsTimer.TotalTime() << " s" << endl;
	
	return sum;
}


void ViewCellsManager::EvaluateViewCellsStats()
{
	mCurrentViewCellsStats.Reset();
	ViewCellContainer::const_iterator it, it_end = mViewCells.end();

	for (it = mViewCells.begin(); it != it_end; ++ it)
	{
		mViewCellsTree->UpdateViewCellsStats(*it, mCurrentViewCellsStats);
	}
}


void ViewCellsManager::EvaluateRenderStatistics(float &totalRenderCost,
												float &expectedRenderCost, 
												float &deviation,
												float &variance,
												float &totalCost,
												float &avgRenderCost)
{
	////////////
	//-- compute expected value

	totalRenderCost = 0;
	totalCost = 0;

	ViewCellContainer::const_iterator it, it_end = mViewCells.end();

	for (it = mViewCells.begin(); it != it_end; ++ it)
	{
		ViewCell *vc = *it;
		totalRenderCost += vc->GetPvs().EvalPvsCost() * vc->GetVolume();
		totalCost += (int)vc->GetPvs().EvalPvsCost();
	}

	// normalize with view space box
	totalRenderCost /= mViewSpaceBox.GetVolume();
	expectedRenderCost = totalRenderCost / (float)mViewCells.size();
	avgRenderCost = totalCost / (float)mViewCells.size();


	///////////
	//-- compute standard defiation

	variance = 0;
	deviation = 0;

	for (it = mViewCells.begin(); it != it_end; ++ it)
	{
		ViewCell *vc = *it;

		float renderCost = vc->GetPvs().EvalPvsCost() * vc->GetVolume();
		float dev;

		if (1)
			dev = fabs(avgRenderCost - (float)vc->GetPvs().EvalPvsCost());
		else
			dev = fabs(expectedRenderCost - renderCost);

		deviation += dev;
		variance += dev * dev;
	}

	variance /= (float)mViewCells.size();
	deviation /= (float)mViewCells.size();
}


float ViewCellsManager::GetArea(ViewCell *viewCell) const
{
	return viewCell->GetArea();
}


float ViewCellsManager::GetVolume(ViewCell *viewCell) const
{
	return viewCell->GetVolume();
}


void ViewCellsManager::CompressViewCells()
{
	if (!(ViewCellsTreeConstructed() && mCompressViewCells))
		return;

	////////////
	//-- compression
	
	int pvsEntries = mViewCellsTree->CountStoredPvsEntries(mViewCellsTree->GetRoot());

	cout << "number of entries before compress: " << pvsEntries << endl;
	Debug << "number of entries before compress: " << pvsEntries << endl;

	mViewCellsTree->SetViewCellsStorage(ViewCellsTree::COMPRESSED);

	pvsEntries = mViewCellsTree->CountStoredPvsEntries(mViewCellsTree->GetRoot());

	Debug << "number of entries after compress: " << pvsEntries << endl;
	cout << "number of entries after compress: " << pvsEntries << endl;
}


ViewCell *ViewCellsManager::ExtrudeViewCell(const Triangle3 &baseTri,
											const float height) const
{
	// one mesh per view cell
	Mesh *mesh = MeshManager::GetSingleton()->CreateResource();
//ootl::hash_map<int, Intersectable *> hmap(-2, NULL);
	////////////
	//-- construct prism

	// bottom
	mesh->mFaces.push_back(new Face(2,1,0));
	// top
    mesh->mFaces.push_back(new Face(3,4,5));
	// sides
	mesh->mFaces.push_back(new Face(1, 4, 3, 0));
	mesh->mFaces.push_back(new Face(2, 5, 4, 1));
	mesh->mFaces.push_back(new Face(3, 5, 2, 0));


	/////////////
	//-- extrude new vertices for top of prism

	const Vector3 triNorm = baseTri.GetNormal();
	Triangle3 topTri;

	// add base vertices and calculate top vertices
	for (int i = 0; i < 3; ++ i)
	{
		mesh->mVertices.push_back(baseTri.mVertices[i]);
	}

	// add top vertices
	for (int i = 0; i < 3; ++ i)
	{
		mesh->mVertices.push_back(baseTri.mVertices[i] + height * triNorm);
	}

	// do we have to preprocess this mesh (we don't want to trace view cells!)?
	mesh->ComputeBoundingBox();
	
	return GenerateViewCell(mesh);
}


void ViewCellsManager::FinalizeViewCells(const bool createMesh)
{
	ViewCellContainer::const_iterator it, it_end = mViewCells.end();

	// volume and area of the view cells are recomputed 
	// a view cell mesh is created
	for (it = mViewCells.begin(); it != it_end; ++ it)
	{
		Finalize(*it, createMesh);
	}

	mViewCellsTree->AssignRandomColors();

	mTotalAreaValid = false;
}


void ViewCellsManager::Finalize(ViewCell *viewCell, const bool createMesh)
{
	// implemented in subclasses
}


/** fast way of merging 2 view cells.
*/
ViewCellInterior *ViewCellsManager::MergeViewCells(ViewCell *left, ViewCell *right) const
{
	// generate parent view cell
	ViewCellInterior *vc = new ViewCellInterior();

	vc->GetPvs().Clear();
	ObjectPvs::Merge(vc->GetPvs(), left->GetPvs(), right->GetPvs());

	// set only links to child (not from child to parent, maybe not wished!!)
	vc->mChildren.push_back(left);
	vc->mChildren.push_back(right);

	// update pvs size
	UpdateScalarPvsSize(vc, vc->GetPvs().EvalPvsCost(), vc->GetPvs().GetSize());

	return vc;
}


ViewCellInterior *ViewCellsManager::MergeViewCells(ViewCellContainer &children) const
{
	ViewCellInterior *vc = new ViewCellInterior();
	ViewCellContainer::const_iterator it, it_end = children.end();

	for (it = children.begin(); it != it_end; ++ it)
	{
		vc->GetPvs().MergeInPlace((*it)->GetPvs());
	
		vc->mChildren.push_back(*it);
	}

	return vc;
}


void ViewCellsManager::SetRenderer(Renderer *renderer)
{
	mRenderer = renderer;
}


ViewCellsTree *ViewCellsManager::GetViewCellsTree()
{
	return mViewCellsTree;
}


void ViewCellsManager::SetVisualizationSamples(const int visSamples)
{
	mVisualizationSamples = visSamples;
}


void ViewCellsManager::SetConstructionSamples(const int constructionSamples)
{
	mConstructionSamples = constructionSamples;
}


void ViewCellsManager::SetInitialSamples(const int initialSamples)
{
	mInitialSamples = initialSamples;
}


void ViewCellsManager::SetPostProcessSamples(const int postProcessSamples)
{
	mPostProcessSamples = postProcessSamples;
}


int ViewCellsManager::GetVisualizationSamples() const
{
	return mVisualizationSamples;
}


int ViewCellsManager::GetConstructionSamples() const
{
	return mConstructionSamples;
}


int ViewCellsManager::GetPostProcessSamples() const
{
	return mPostProcessSamples;
}


void ViewCellsManager::UpdatePvs()
{
	if (mViewCellPvsIsUpdated || !ViewCellsTreeConstructed())
		return;

	mViewCellPvsIsUpdated = true;

	ViewCellContainer leaves;
	mViewCellsTree->CollectLeaves(mViewCellsTree->GetRoot(), leaves);

	ViewCellContainer::const_iterator it, it_end = leaves.end();

	for (it = leaves.begin(); it != it_end; ++ it)
	{
		mViewCellsTree->PropagatePvs(*it);
	}
}


void ViewCellsManager::GetPvsStatistics(PvsStatistics &stat)
{
  // update pvs of view cells tree if necessary
  if (0) UpdatePvs();
  
  ViewCellContainer::const_iterator it = mViewCells.begin();
  
  stat.viewcells = 0;
  stat.minPvs = 100000000;
  stat.maxPvs = 0;
  stat.avgPvs = 0.0f;
  stat.avgPvsEntries = 0.0f;
  stat.avgFilteredPvs = 0.0f;
  stat.avgFilteredPvsEntries = 0.0f;
  stat.avgFilterContribution = 0.0f;
  stat.avgFilterRadius = 0;
  stat.avgFilterRatio = 0;
  stat.avgRelPvsIncrease = 0.0f;
  stat.devRelPvsIncrease = 0.0f;
  stat.renderCost = 0.0f;
  stat.mem = 0.0f;

  if (mPerViewCellStat.size() != mViewCells.size()) {
	// reset the pvs size array after the first call to this routine
	mPerViewCellStat.resize(mViewCells.size());
	for (int i=0; i < mPerViewCellStat.size(); i++) {
	  mPerViewCellStat[i].pvsSize = 0.0f;
	  mPerViewCellStat[i].relPvsIncrease = 0.0f;
	}
  }
  int i;
  bool evaluateFilter;
  Environment::GetSingleton()->GetBoolValue("Preprocessor.evaluateFilter", evaluateFilter);

  const float vol = mViewSpaceBox.GetVolume();

  for (i = 0; it != mViewCells.end(); ++ it, ++ i) 
  {
	  ViewCell *viewcell = *it;
	  if (viewcell->GetValid()) {
		  const float pvsCost = mViewCellsTree->GetTrianglesInPvs(viewcell);
		  const float renderCost = pvsCost * viewcell->GetVolume() / vol;

		  if (pvsCost < stat.minPvs)
			  stat.minPvs = pvsCost;
		  if (pvsCost > stat.maxPvs)
			  stat.maxPvs = pvsCost;

		  stat.avgPvs += pvsCost;
		  stat.renderCost += renderCost;

		  const float pvsEntries = (float)mViewCellsTree->GetPvsEntries(viewcell);
		  stat.avgPvsEntries += pvsEntries;

		  if (mPerViewCellStat[i].pvsSize > 0.0f)
			  mPerViewCellStat[i].relPvsIncrease = (pvsCost - mPerViewCellStat[i].pvsSize) / mPerViewCellStat[i].pvsSize;

		  stat.avgRelPvsIncrease += mPerViewCellStat[i].relPvsIncrease;

		  // update the pvs size
		  mPerViewCellStat[i].pvsSize = pvsCost;


		  if (evaluateFilter) 
		  {
			  ObjectPvs filteredPvs;

			  PvsFilterStatistics fstat = ApplyFilter2(viewcell, false, mFilterWidth, filteredPvs);

			  const float filteredCost = filteredPvs.EvalPvsCost();

			  stat.avgFilteredPvs += filteredCost;
			  stat.avgFilteredPvsEntries += filteredPvs.GetSize();

			  stat.avgFilterContribution += filteredCost - pvsCost;

			  stat.avgFilterRadius += fstat.mAvgFilterRadius;
			  int sum = fstat.mGlobalFilterCount + fstat.mLocalFilterCount;
			  if (sum) {
				  stat.avgFilterRatio += fstat.mLocalFilterCount /
					  (float) sum;
			  }

		  } else {
			  stat.avgFilteredPvs += pvsCost;
			  stat.avgFilterContribution += 0;
		  }

		  ++ stat.viewcells;
	  }
  }



  if (stat.viewcells) {
	  stat.mem = (float)(ObjectPvs::GetEntrySizeByte() * stat.avgPvsEntries + stat.viewcells * 16) / float(1024 * 1024); 

	  stat.avgPvs/=stat.viewcells;
	  stat.avgPvsEntries/=stat.viewcells;
	  stat.avgFilteredPvsEntries/=stat.viewcells;
	  stat.avgFilteredPvs/=stat.viewcells;
	  stat.avgFilterContribution/=stat.viewcells;
	  stat.avgFilterRadius/=stat.viewcells;
	  stat.avgFilterRatio/=stat.viewcells; 
	  stat.avgRelPvsIncrease/=stat.viewcells;
	  stat.renderCostRatio=stat.renderCost / stat.mem;

	  // evaluate std deviation of relPvsIncrease
	  float sum=0.0f;
	  for (i=0; i < stat.viewcells; i++) {
		  sum += sqr(mPerViewCellStat[i].relPvsIncrease - stat.avgRelPvsIncrease);
	  }
	  stat.devRelPvsIncrease = sqrt(sum/stat.viewcells);
  }

}


void ViewCellsManager::PrintPvsStatistics(ostream &s)
{
  s<<"############# Viewcell PVS STAT ##################\n";
  PvsStatistics pvsStat;
  GetPvsStatistics(pvsStat);
  s<<"#AVG_PVS\n"<<pvsStat.avgPvs<<endl;
  s<<"#AVG_ENTRIES_PVS\n"<<pvsStat.avgPvsEntries<<endl;
  s<<"#RENDERCOST\n"<<pvsStat.renderCost<<endl;
  s<<"#AVG_FILTERED_PVS\n"<<pvsStat.avgFilteredPvs<<endl;
  s<<"#AVG_FILTERED_ENTRIES_PVS\n"<<pvsStat.avgFilteredPvsEntries<<endl;
  s<<"#AVG_FILTER_CONTRIBUTION\n"<<pvsStat.avgFilterContribution<<endl;
  s<<"#AVG_FILTER_RADIUS\n"<<pvsStat.avgFilterRadius<<endl;
  s<<"#AVG_FILTER_RATIO\n"<<pvsStat.avgFilterRatio<<endl;
  s<<"#MAX_PVS\n"<<pvsStat.maxPvs<<endl;
  s<<"#MIN_PVS\n"<<pvsStat.minPvs<<endl;
  s<<"#AVG_REL_PVS_INCREASE\n"<<pvsStat.avgRelPvsIncrease<<endl;
  s<<"#DEV_REL_PVS_INCREASE\n"<<pvsStat.devRelPvsIncrease<<endl;
  s<<"#MEMORY\n"<<pvsStat.mem<<endl;
  s<<"#RATIO\n"<<pvsStat.renderCost / (pvsStat.mem + Limits::Small)<<endl;
  s<<"#CONTRIBUTING_RAYS\n"<<mSamplesStat.mContributingRays<<endl;

  if (mSamplesStat.mRays) {
	s<<"#AVG_VIEWCELLS_PER_RAY\n"<<mSamplesStat.mViewCells/(float)mSamplesStat.mRays<<endl;
  } else {
	s<<"#AVG_VIEWCELLS_PER_RAY\n 1 \n";
  }
  mSamplesStat.Reset();
}


int ViewCellsManager::CastBeam(Beam &beam)
{
	return 0;
}


ViewCellContainer &ViewCellsManager::GetViewCells()
{
	return mViewCells;
}


void ViewCellsManager::SetViewSpaceBox(const AxisAlignedBox3 &box)
{
	mViewSpaceBox = box;
	
	// hack: create clip plane relative to new view space box
	CreateClipPlane();
	// the total area of the view space has changed
	mTotalAreaValid = false;
}


void ViewCellsManager::CreateClipPlane()
{
	int axis = 0;
	float pos;
	bool orientation;
	Vector3 absPos;

	Environment::GetSingleton()->GetFloatValue("ViewCells.Visualization.clipPlanePos", pos);
	Environment::GetSingleton()->GetIntValue("ViewCells.Visualization.clipPlaneAxis", axis);

	if (axis < 0) 
	{
		axis = -axis;
		orientation = false;
		absPos = mViewSpaceBox.Max() -  mViewSpaceBox.Size() * pos;
	}
	else
	{
		orientation = true;
		absPos = mViewSpaceBox.Min() +  mViewSpaceBox.Size() * pos;
	}

	mClipPlaneForViz = AxisAlignedPlane(axis, absPos[axis]);
	mClipPlaneForViz.mOrientation = orientation;
}


AxisAlignedBox3 ViewCellsManager::GetViewSpaceBox() const
{
	return mViewSpaceBox;
}


void ViewCellsManager::ResetViewCells()
{
	// recollect view cells
	mViewCells.clear();
	CollectViewCells();
	
	// stats are computed once more
	EvaluateViewCellsStats();

	// has to be recomputed
	mTotalAreaValid = false;
}


int ViewCellsManager::GetMaxPvsSize() const
{
	return mMaxPvsSize;
}


int ViewCellsManager::GetMinPvsSize() const
{
	return mMinPvsSize;
}



float ViewCellsManager::GetMaxPvsRatio() const
{
	return mMaxPvsRatio;
}


inline static void AddSampleToPvs(ObjectPvs &pvs, 
								  Intersectable *obj, 
								  const float pdf)
{
#if PVS_ADD_DIRTY
	pvs.AddSampleDirtyCheck(obj, pdf);

	if (pvs.RequiresResort()) 
	{
		pvs.SimpleSort();
	}
#else
	pvs.AddSample(obj, pdf);
#endif
}


void ViewCellsManager::SortViewCellPvs()
{
	ViewCellContainer::iterator it, it_end = mViewCells.end();
	
	for (it = mViewCells.begin(); it != it_end; ++ it) 
	{
		ObjectPvs &pvs = (*it)->GetPvs();
		if (pvs.RequiresResortLog())
			pvs.SimpleSort();
	}
}


void ViewCellsManager::ComputeViewCellContribution(ViewCell *viewCell,
												   VssRay &ray, 
												   Intersectable *obj,
												   const Vector3 &pt,
												   const bool addSamplesToPvs)
{
	// check if we are outside of view space
	// $$JB tmp commented to speedup up computations
#if 0
	if (!obj || !viewCell->GetValid())
		return;
#endif

	// if ray not outside of view space
	float relContribution = 0.0f;
	float absContribution = 0.0f;
	bool hasAbsContribution;

	// todo: maybe not correct for kd node pvs
	if (addSamplesToPvs) 
	{
		hasAbsContribution = viewCell->GetPvs().AddSampleDirtyCheck(obj, ray.mPdf);
		//hasAbsContribution = viewCell->GetPvs().AddSample(obj,ray.mPdf);
	}
	else 
	{
		hasAbsContribution = 
			viewCell->GetPvs().GetSampleContribution(obj, ray.mPdf, relContribution);
	}

	// $$ clear the relative contribution as it is currently not correct anyway
	//  relContribution = 0.0f;

	if (hasAbsContribution)  
	{
		++ ray.mPvsContribution;
		absContribution = relContribution = 1.0f;

		if (viewCell->GetPvs().RequiresResort()) 
			viewCell->GetPvs().SimpleSort();

#if CONTRIBUTION_RELATIVE_TO_PVS_SIZE
		relContribution /= viewcell->GetPvs().GetSize();
#endif

#if DIST_WEIGHTED_CONTRIBUTION 
		// recalculate the contribution - weight the 1.0f contribution by the sqr distance to the
		// object-> a new contribution in the proximity of the viewcell has a larger weight!
		relContribution /= 
			SqrDistance(GetViewCellBox(viewcell).Center(), ray.mTermination);

#endif
	}

#if SUM_RAY_CONTRIBUTIONS || AVG_RAY_CONTRIBUTIONS
	ray.mRelativePvsContribution += relContribution;
#else
	// recalculate relative contribution - use max of Rel Contribution
	if (ray.mRelativePvsContribution < relContribution)
		ray.mRelativePvsContribution = relContribution;
#endif
}


int ViewCellsManager::GetNumViewCells() const
{
	return (int)mViewCells.size();
}


void
ViewCellsManager::DeterminePvsObjects(
									  VssRayContainer &rays,
									  const bool useHitObjects)
{
	if (!useHitObjects) 
	{
		// store higher order object (e.g., bvh node) instead of object itself
		VssRayContainer::const_iterator it, it_end = rays.end();
        
		for (it = rays.begin(); it != it_end; ++ it) 
		{
			VssRay *vssRay = *it;

			// set only the termination object
			vssRay->mTerminationObject = GetIntersectable(*vssRay, true);
		}
	}
}


float ViewCellsManager::ComputeSampleContribution(VssRay &ray,
												  const bool addRays,
												  ViewCell *currentViewCell,
												  const bool useHitObjects)
{
	ray.mPvsContribution = 0;
	ray.mRelativePvsContribution = 0.0f;

	if (!ray.mTerminationObject)
		return 0.0f;

	// optain pvs entry (can be different from hit object)
	Intersectable *terminationObj;

	terminationObj = ray.mTerminationObject;

	ComputeViewCellContribution(currentViewCell, 
								ray, 
								terminationObj, 
								ray.mTermination, 
								addRays);
	
#if USE_RAY_LENGTH_AS_CONTRIBUTION
	float c = 0.0f;
	if (terminationObj) 
		c = ray.Length();

	ray.mRelativePvsContribution = ray.mPvsContribution = c;
	return c;
#else
	return ABS_CONTRIBUTION_WEIGHT*ray.mPvsContribution +
	  (1.0f - ABS_CONTRIBUTION_WEIGHT)*ray.mRelativePvsContribution;
#endif
}


float
ViewCellsManager::ComputeSampleContribution(VssRay &ray,
											const bool addRays,
											const bool storeViewCells,
											const bool useHitObjects)
{
	ray.mPvsContribution = 0;
	ray.mRelativePvsContribution = 0.0f;

	++ mSamplesStat.mRays;

	if (!ray.mTerminationObject)
		return 0.0f;

	static Ray hray;
	hray.Init(ray);

	float tmin = 0, tmax = 1.0;

	if (!GetViewSpaceBox().GetRaySegment(hray, tmin, tmax) || (tmin > tmax)) 
	{
		// cerr<<"ray outside view space box\n";
		return 0;
	}

	Vector3 origin = hray.Extrap(tmin);
	Vector3 termination = hray.Extrap(tmax);

	ViewCell::NewMail();

	viewCellCastTimer.Entry();

	static ViewCellContainer viewCells;
	static VssRay *lastVssRay = NULL;

	// check if last ray was not same ray with reverse direction
	if (1) 
		// tmp matt: don't use that before origin objects are accounted for, currently the second ray is lost!!
		//!lastVssRay ||
		//!(ray.mOrigin == lastVssRay->mTermination) ||
		//!(ray.mTermination == lastVssRay->mOrigin)) 
	{
		viewCells.clear();

		// traverse the view space subdivision
		CastLineSegment(origin, termination, viewCells);

		lastVssRay = &ray;
	}

	viewCellCastTimer.Exit();

	mSamplesStat.mViewCells += (int)viewCells.size();

	if (storeViewCells)
	{	
		// cerr << "Store viewcells should not be used in the test!" << endl;
		// copy viewcells memory efficiently
#if VSS_STORE_VIEWCELLS
		ray.mViewCells.reserve(viewCells.size());
		ray.mViewCells = viewCells;
#else
		cerr << "Vss store viewcells not supported." << endl;
		exit(1);
#endif
	}

	Intersectable *terminationObj;

	objTimer.Entry();

	// obtain pvs entry (can be different from hit object)
	terminationObj = ray.mTerminationObject;

	objTimer.Exit();

	pvsTimer.Entry();

	ViewCellContainer::const_iterator it = viewCells.begin();

	for (; it != viewCells.end(); ++ it) 
	{
		ComputeViewCellContribution(*it, 
			                        ray, 
									terminationObj, 
									ray.mTermination, 
									addRays);
	}

	pvsTimer.Exit();

	mSamplesStat.mPvsContributions += ray.mPvsContribution;
	if (ray.mPvsContribution)
		++ mSamplesStat.mContributingRays;

#if AVG_RAY_CONTRIBUTIONS
	ray.mRelativePvsContribution /= (float)viewCells.size();
#endif

#if USE_RAY_LENGTH_AS_CONTRIBUTION
	float c = 0.0f;
	if (terminationObj) 
		c = ray.Length();
	ray.mRelativePvsContribution = ray.mPvsContribution = c;
	return c;
#else
	return ABS_CONTRIBUTION_WEIGHT*ray.mPvsContribution +
		(1.0f - ABS_CONTRIBUTION_WEIGHT)*ray.mRelativePvsContribution;
#endif
}


void ViewCellsManager::GetRaySets(const VssRayContainer &sourceRays,
								  const int maxSize,
								  VssRayContainer &usedRays,
								  VssRayContainer *savedRays) const
{
	const int limit = min(maxSize, (int)sourceRays.size());
	const float prop = (float)limit / ((float)sourceRays.size() + Limits::Small);

	VssRayContainer::const_iterator it, it_end = sourceRays.end();
	for (it = sourceRays.begin(); it != it_end; ++ it)
	{
		if (Random(1.0f) < prop)
			usedRays.push_back(*it);
		else if (savedRays)
			savedRays->push_back(*it);
	}
}


float ViewCellsManager::GetRendercost(ViewCell *viewCell) const
{
	return (float)mViewCellsTree->GetTrianglesInPvs(viewCell);
}


float ViewCellsManager::GetAccVcArea()
{
	// if already computed
	if (mTotalAreaValid)
	{
		return mTotalArea;
	}

	mTotalArea = 0;
	ViewCellContainer::const_iterator it, it_end = mViewCells.end();

	for (it = mViewCells.begin(); it != it_end; ++ it)
	{
		//Debug << "area: " << GetArea(*it);
        mTotalArea += GetArea(*it);
	}

	mTotalAreaValid = true;

	return mTotalArea;
}


void ViewCellsManager::PrintStatistics(ostream &s) const
{
	s << mCurrentViewCellsStats << endl;
}


void ViewCellsManager::CreateUniqueViewCellIds()
{
	if (ViewCellsTreeConstructed())
	{
		mViewCellsTree->CreateUniqueViewCellsIds();
	}
	else // no view cells tree, handle view cells "myself"
	{
		int i = 0;
		ViewCellContainer::const_iterator vit, vit_end = mViewCells.end();
		for (vit = mViewCells.begin(); vit != vit_end; ++ vit)
		{
			if ((*vit)->GetId() != OUT_OF_BOUNDS_ID) 
			{
				mViewCells[i]->SetId(i ++);
			}
		}
	}
}


void ViewCellsManager::ExportViewCellsForViz(Exporter *exporter,
											 const AxisAlignedBox3 *sceneBox,
											 const bool colorCode,
											 const AxisAlignedPlane *clipPlane
											 ) const
{
	ViewCellContainer::const_iterator it, it_end = mViewCells.end();

	for (it = mViewCells.begin(); it != it_end; ++ it)
	{
		if (!mOnlyValidViewCells || (*it)->GetValid())
		{
			ExportColor(exporter, *it, colorCode);	
			ExportViewCellGeometry(exporter, *it, sceneBox, clipPlane);
		}
	}
}


void ViewCellsManager::CreateViewCellMeshes()
{
	// convert to meshes
	ViewCellContainer::const_iterator it, it_end = mViewCells.end();

	for (it = mViewCells.begin(); it != it_end; ++ it)
	{
		if (!(*it)->GetMesh())
		{
			CreateMesh(*it);
		}
	}
}


bool ViewCellsManager::ExportViewCells(const string filename, 
									   const bool exportPvs, 
									   const ObjectContainer &objects)
{
	return false;
}


void ViewCellsManager::CollectViewCells(const int n) 
{
	mNumActiveViewCells = n;
	mViewCells.clear();
	// implemented in subclasses
	CollectViewCells();
}


void ViewCellsManager::SetViewCellActive(ViewCell *vc) const
{
	ViewCellContainer leaves;
	// sets the pointers to the currently active view cells
	mViewCellsTree->CollectLeaves(vc, leaves);

	ViewCellContainer::const_iterator lit, lit_end = leaves.end();
	for (lit = leaves.begin(); lit != lit_end; ++ lit)
	{
		static_cast<ViewCellLeaf *>(*lit)->SetActiveViewCell(vc);
	}
}


void ViewCellsManager::SetViewCellsActive()
{
	// collect leaf view cells and set the pointers to 
	// the currently active view cells
	ViewCellContainer::const_iterator it, it_end = mViewCells.end();

	for (it = mViewCells.begin(); it != it_end; ++ it)
	{
		SetViewCellActive(*it);
	}
}


int ViewCellsManager::GetMaxFilterSize() const
{
	return mMaxFilterSize;  
}


static const bool USE_ASCII = true;


bool ViewCellsManager::ExportBoundingBoxes(const string filename, 
										   const ObjectContainer &objects) const
{
	ObjectContainer::const_iterator it, it_end = objects.end();
	
	if (USE_ASCII)
	{
		ofstream boxesOut(filename.c_str());
		if (!boxesOut.is_open())
			return false;

		for (it = objects.begin(); it != it_end; ++ it)
		{
			MeshInstance *mi = static_cast<MeshInstance *>(*it);
			const AxisAlignedBox3 box = mi->GetBox();

			boxesOut << mi->GetId() << " " 
					 << box.Min().x << " " 
					 << box.Min().y << " " 
					 << box.Min().z << " " 
					 << box.Max().x << " " 
					 << box.Max().y << " " 
                     << box.Max().z << endl;	
		}

		boxesOut.close();
	}
	else
	{
		ofstream boxesOut(filename.c_str(), ios::binary);

		if (!boxesOut.is_open())
			return false;

		for (it = objects.begin(); it != it_end; ++ it)
		{	
			MeshInstance *mi = static_cast<MeshInstance *>(*it);
			const AxisAlignedBox3 box = mi->GetBox();
			
			Vector3 bmin = box.Min();
			Vector3 bmax = box.Max();
			
			int id = mi->GetId();

			boxesOut.write(reinterpret_cast<char *>(&id), sizeof(int));
			boxesOut.write(reinterpret_cast<char *>(&bmin), sizeof(Vector3));
			boxesOut.write(reinterpret_cast<char *>(&bmax), sizeof(Vector3));
		}
		
		boxesOut.close();
	}

	return true;
}


bool ViewCellsManager::LoadBoundingBoxes(const string filename, 
										 IndexedBoundingBoxContainer &boxes) const
{
	Vector3 bmin, bmax;
	int id;

	if (USE_ASCII)
	{
		ifstream boxesIn(filename.c_str());
		
		if (!boxesIn.is_open())
		{
			cout << "failed to open file " << filename << endl;
			return false;
		}

		string buf;
		while (!(getline(boxesIn, buf)).eof())
		{
			sscanf(buf.c_str(), "%d %f %f %f %f %f %f", 
				   &id, &bmin.x, &bmin.y, &bmin.z,
				   &bmax.x, &bmax.y, &bmax.z);
		
			AxisAlignedBox3 box(bmin, bmax);
			//	MeshInstance *mi = new MeshInstance();
			// HACK: set bounding box to new box
			//mi->mBox = box;

			boxes.push_back(IndexedBoundingBox(id, box));
		}

		boxesIn.close();
	}
	else
	{
		ifstream boxesIn(filename.c_str(), ios::binary);

		if (!boxesIn.is_open())
			return false;

		while (1)
		{
			boxesIn.read(reinterpret_cast<char *>(&id), sizeof(Vector3));
			boxesIn.read(reinterpret_cast<char *>(&bmin), sizeof(Vector3));
			boxesIn.read(reinterpret_cast<char *>(&bmax), sizeof(Vector3));
			
			if (boxesIn.eof())
				break;
			
			AxisAlignedBox3 box(bmin, bmax);
			MeshInstance *mi = new MeshInstance(NULL);

			boxes.push_back(IndexedBoundingBox(id, box));
		}

		boxesIn.close();
	}

	return true;
}


float ViewCellsManager::GetFilterWidth() 
{
	return mFilterWidth;
}


float ViewCellsManager::GetAbsFilterWidth() 
{
	return Magnitude(mViewSpaceBox.Size()) * mFilterWidth;
}


void ViewCellsManager::UpdateScalarPvsSize(ViewCell *vc, 
										   const float pvsCost, 
										   const int entriesInPvs) const
{
	vc->mPvsCost = pvsCost;
	vc->mEntriesInPvs = entriesInPvs;

	vc->mPvsSizeValid = true;
}


void
ViewCellsManager::ApplyFilter(ViewCell *viewCell,
							  KdTree *kdTree,
							  const float viewSpaceFilterSize,
							  const float spatialFilterSize,
							  ObjectPvs &pvs
							  )
{
  // extend the pvs of the viewcell by pvs of its neighbors
  // and apply spatial filter by including all neighbors of the objects
  // in the pvs

  // get all viewcells intersecting the viewSpaceFilterBox
  // and compute the pvs union
  
  //Vector3 center = viewCell->GetBox().Center();
  //  Vector3 center = m->mBox.Center();

	//  AxisAlignedBox3 box(center - Vector3(viewSpaceFilterSize/2),
	//					  center + Vector3(viewSpaceFilterSize/2));
	if (!ViewCellsConstructed())
		return;

	if (viewSpaceFilterSize >= 0.0f) 
	{
		const bool usePrVS = false;

		if (!usePrVS)
		{
			AxisAlignedBox3 box = GetViewCellBox(viewCell);
			box.Enlarge(Vector3(viewSpaceFilterSize/2));

			ViewCellContainer viewCells;
			ComputeBoxIntersections(box, viewCells);

			//  cout<<"box="<<box<<endl;
			ViewCellContainer::const_iterator it = viewCells.begin(), it_end = viewCells.end();

			for (; it != it_end; ++ it) 
			{
				ObjectPvs interPvs;
				//cout<<"v"<<i<<" pvs="<<(*it)->GetPvs().mEntries.size()<<endl;
				ObjectPvs::Merge(interPvs, pvs, (*it)->GetPvs());

				pvs = interPvs;
			}
		} 
		else 
		{
			PrVs prvs;
			AxisAlignedBox3 box = GetViewCellBox(viewCell);

			//  mViewCellsManager->SetMaxFilterSize(1);
			GetPrVS(box.Center(), prvs, viewSpaceFilterSize);
			pvs = prvs.mViewCell->GetPvs();
			DeleteLocalMergeTree(prvs.mViewCell);
		}
	} 
	else
	{
		pvs = viewCell->GetPvs();
	}

	if (spatialFilterSize >=0.0f)
		ApplySpatialFilter(kdTree, spatialFilterSize, pvs);

}



void
ViewCellsManager::ApplyFilter(KdTree *kdTree,
							  const float relViewSpaceFilterSize,
							  const float relSpatialFilterSize
							  )
{

	if (!ViewCellsConstructed())
		return;

	ViewCellContainer::const_iterator it, it_end = mViewCells.end();

	ObjectPvs *newPvs;
	newPvs = new ObjectPvs[mViewCells.size()];

	float viewSpaceFilterSize = Magnitude(mViewSpaceBox.Size())*relViewSpaceFilterSize;
	float spatialFilterSize = Magnitude(kdTree->GetBox().Size())*relSpatialFilterSize;
	
	int i;
	for (i=0, it = mViewCells.begin(); it != it_end; ++ it, ++ i) {
	  ApplyFilter(*it,
				  kdTree,
				  viewSpaceFilterSize,
				  spatialFilterSize,
				  newPvs[i]
				  );
	}
	
	// now replace all pvss
	for (i = 0, it = mViewCells.begin(); it != it_end; ++ it, ++ i) {
	  
	  ObjectPvs &pvs = (*it)->GetPvs();
	  pvs.Clear();
	  pvs = newPvs[i];
	  newPvs[i].Clear();
	}

	delete [] newPvs;
}


void
ViewCellsManager::ApplySpatialFilter(
									 KdTree *kdTree,
									 const float spatialFilterSize,
									 ObjectPvs &pvs
									 )
{
	// now compute a new Pvs by including also objects intersecting the 
	// extended boxes of visible objects
	Intersectable::NewMail();

	ObjectPvsIterator pit = pvs.GetIterator();

	while (pit.HasMoreEntries())
		pit.Next()->Mail();

	ObjectPvs nPvs;
	int nPvsSize = 0;

	ObjectPvsIterator pit2 = pvs.GetIterator();

	while (pit2.HasMoreEntries())
	{		
		// now go through the pvs again
		Intersectable *object = pit2.Next();

		//	Vector3 center = object->GetBox().Center();
		//	AxisAlignedBox3 box(center - Vector3(spatialFilterSize/2),
		//						center + Vector3(spatialFilterSize/2));

		AxisAlignedBox3 box = object->GetBox();
		box.Enlarge(Vector3(spatialFilterSize/2));

		ObjectContainer objects;

		// $$ warning collect objects takes only unmailed ones!
		kdTree->CollectObjects(box, objects);
		//	cout<<"collected objects="<<objects.size()<<endl;
		ObjectContainer::const_iterator noi = objects.begin();
		for (; noi != objects.end(); ++ noi) 
		{
			Intersectable *o = *noi;
			cout<<"w";
			// $$ JB warning: pdfs are not correct at this point!	  
			nPvs.AddSample(o, Limits::Small);
			nPvsSize ++;
		}
	}

	// cout<<"nPvs size = "<<nPvsSize<<endl;
	pvs.MergeInPlace(nPvs);
}


void ViewCellsManager::MergeViewCellsRecursivly(ObjectPvs &pvs, 
												const ViewCellContainer &viewCells) const
{
	MergeViewCellsRecursivly(pvs, viewCells, 0, (int)viewCells.size() - 1);
}


void ViewCellsManager::MergeViewCellsRecursivly(ObjectPvs &pvs, 
												const ViewCellContainer &viewCells, 
												const int leftIdx, 
												const int rightIdx) const
{
	if (leftIdx == rightIdx)
	{
		pvs = viewCells[leftIdx]->GetPvs();
	}
	else
	{
		const int midSplit = (leftIdx + rightIdx) / 2;
        
		ObjectPvs leftPvs, rightPvs;
		MergeViewCellsRecursivly(leftPvs, viewCells, leftIdx, midSplit);
		MergeViewCellsRecursivly(rightPvs, viewCells, midSplit, rightIdx);

        ObjectPvs::Merge(pvs, leftPvs, rightPvs);
	}
}


PvsFilterStatistics
ViewCellsManager::ApplyFilter2(ViewCell *viewCell,
							   const bool useViewSpaceFilter,
							   const float filterSize,
							   ObjectPvs &pvs,
							   vector<AxisAlignedBox3> *filteredBoxes
							   )
{
	pvs.Reserve(viewCell->GetFilteredPvsSize());

	PvsFilterStatistics stats;

	AxisAlignedBox3 vbox = GetViewCellBox(viewCell);
	const Vector3 center = vbox.Center();
	
	// copy the PVS
	if (!mUseKdPvs)
		Intersectable::NewMail();
	else
		KdNode::NewMail();

	ObjectPvs basePvs = viewCell->GetPvs();
	ObjectPvsIterator pit = basePvs.GetIterator();

	if (!mUseKdPvs)
	{	// first mark all objects from this pvs
		while (pit.HasMoreEntries()) 	
			pit.Next()->Mail();
	}

	int pvsSize = 0;
	int nPvsSize = 0;
	
	//Debug<<"f #s="<<samples<<"  pvs size = "<<basePvs.GetSize();
	//  cout<<"Filter size = "<<filterSize<<endl;
	//  cout<<"vbox = "<<vbox<<endl;
	//  cout<<"center = "<<center<<endl;


	// Minimal number of local samples to take into account
	// the local sampling density.
	// The size of the filter is a minimum of the conservative
	// local sampling density estimate (#rays intersecting teh viewcell and
	// the object)
	// and gobal estimate for the view cell
	// (total #rays intersecting the viewcell)
	const int minLocalSamples = 2;
	const float viewCellRadius = 0.5f * Magnitude(vbox.Diagonal());

	float samples = (float)basePvs.GetSamples();


	//////////
	//-- now compute the filter box around the current viewCell

	if (useViewSpaceFilter) 
	{
		// float radius = Max(viewCellRadius/100.0f, avgRadius - viewCellRadius);
		float radius = viewCellRadius / 100.0f;
		vbox.Enlarge(radius);
		cout<<"vbox = "<<vbox<<endl;

		ViewCellContainer viewCells;
		ComputeBoxIntersections(vbox, viewCells);

		ViewCellContainer::const_iterator it = viewCells.begin(), it_end = viewCells.end();

		for (int i = 0; it != it_end; ++ it, ++ i)
		{
			if ((*it) != viewCell) 
			{
				//cout<<"v"<<i<<" pvs="<<(*it)->GetPvs().mEntries.size()<<endl;
				basePvs.MergeInPlace((*it)->GetPvs());
			}

			// update samples and globalC
			samples = (float)pvs.GetSamples();
			//	cout<<"neighboring viewcells = "<<i-1<<endl;
			//	cout<<"Samples' = "<<samples<<endl;
		}
	}

	// Minimal number of samples so that filtering takes place
	const float MIN_SAMPLES = 50;

	if (samples > MIN_SAMPLES) 
	{
		float globalC = 2.0f * filterSize / sqrt(samples);

		ObjectContainer objects;
		PvsData pvsData;

		pit = basePvs.GetIterator();

		while (pit.HasMoreEntries()) 
		{		
			Intersectable *object = pit.Next(pvsData);

			// compute filter size based on the distance and the numebr of samples
			AxisAlignedBox3 box = object->GetBox();

			float distance = Distance(center, box.Center());
			float globalRadius = distance*globalC;

			int objectSamples = (int)pvsData.mSumPdf;
			float localRadius = MAX_FLOAT;

			localRadius = filterSize*0.5f*Magnitude(box.Diagonal())/
				sqrt((float)objectSamples);

			// cout<<"os="<<objectSamples<<" lr="<<localRadius<<" gr="<<globalRadius<<endl;

			// now compute the filter size
			float radius;

#if 0
			if (objectSamples <= 1) 
			{
				if (localRadius > globalRadius) 
				{
					radius = 0.5flRadius;
					stats.mLocalFilterCount++;
				} 
				else 
				{
					radius = globalRadius;
					stats.mGlobalFilterCount++;
				}
			} 
			else 
			{
				radius = localRadius;
				stats.mLocalFilterCount++;
			}
#else

			// radius = 0.5f*globalRadius + 0.5f*localRadius;
			radius = Min(globalRadius, localRadius);

			if (localRadius > globalRadius) 
				++ stats.mLocalFilterCount;
			else
				++ stats.mGlobalFilterCount;
#endif

			stats.mAvgFilterRadius += radius;

			// cout<<"box = "<<box<<endl;
			//	cout<<"distance = "<<distance<<endl;
			//	cout<<"radiues = "<<radius<<endl;

			box.Enlarge(Vector3(radius));

			if (filteredBoxes)
				filteredBoxes->push_back(box);

			objects.clear();

			// $$ warning collect objects takes only unmailed ones!
			if (mUseKdPvs) 
				GetPreprocessor()->mKdTree->CollectKdObjects(box, objects);
			else
				CollectObjects(box, objects);

			//	cout<<"collected objects="<<objects.size()<<endl;
			ObjectContainer::const_iterator noi = objects.begin();
			for (; noi != objects.end(); ++ noi) 
			{
				Intersectable *o = *noi;
				// $$ JB warning: pdfs are not correct at this point!	  
				pvs.AddSampleDirty(o, Limits::Small);
			}
		}
		
		stats.mAvgFilterRadius /= (stats.mLocalFilterCount + stats.mGlobalFilterCount);
	}

	//Debug << " nPvs size = " << pvs.GetSize() << endl;

	if (!mUseKdPvs)
	{
		PvsData pvsData;

		// copy the base pvs to the new pvs
		pit = basePvs.GetIterator();
		while (pit.HasMoreEntries()) 
		{		
			Intersectable *obj = pit.Next(pvsData);
			pvs.AddSampleDirty(obj, pvsData.mSumPdf);
		}
	}

	pvs.SimpleSort();
	viewCell->SetFilteredPvsSize(pvs.GetSize());

	// warning: not thread-safe!
	if (!mUseKdPvs)
		Intersectable::NewMail();

	return stats;
}



void ViewCellsManager::ExportColor(Exporter *exporter, 
								   ViewCell *vc, 
								   int colorCode) const
{
	const bool vcValid = CheckValidity(vc, mMinPvsSize, mMaxPvsSize);

	float importance = 0;
	static Material m;
	//cout << "color code: " << colorCode << endl;
		
	switch (colorCode)
	{
	case 0: // Random
		{
			if (vcValid)
			{
				m.mDiffuseColor.r = 0.2f + RandomValue(0.0f, 0.8f);
				m.mDiffuseColor.g = 0.2f + RandomValue(0.0f, 0.8f);
				m.mDiffuseColor.b = 0.2f + RandomValue(0.0f, 0.8f);
			}
			else
			{
				m.mDiffuseColor.r = 0.0f;
				m.mDiffuseColor.g = 1.0f;
				m.mDiffuseColor.b = 0.0f;
			}

			exporter->SetForcedMaterial(m);
			return;
		}
		
	case 1: // pvs
		{
			if (mCurrentViewCellsStats.maxPvs)
			{
				importance = //(float)mViewCellsTree->GetTrianglesInPvs(vc) / 700;
							 (float)mCurrentViewCellsStats.maxPvs;
			}
		}
		break;
	case 2: // merges
		{
            const int lSize = mViewCellsTree->GetNumInitialViewCells(vc);
			importance = (float)lSize / (float)mCurrentViewCellsStats.maxLeaves;
		}
		break;
	default:
		break;
	}

	// special color code for invalid view cells
	m.mDiffuseColor.r = importance;
	m.mDiffuseColor.b = 1.0f;//vcValid ? 0.0f : 1.0f;
	m.mDiffuseColor.g = 1.0f - importance;

	//Debug << "importance: " << importance << endl;
	exporter->SetForcedMaterial(m);
}


void ViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays, 
											  vector<MergeCandidate> &candidates)
{
	// implemented in subclasses
}


void ViewCellsManager::UpdatePvsForEvaluation()
{
	ObjectPvs objPvs;
	UpdatePvsForEvaluation(mViewCellsTree->GetRoot(), objPvs);
}


void ViewCellsManager::UpdatePvsForEvaluation(ViewCell *root, ObjectPvs &pvs)
{
	// terminate traversal
	if (root->IsLeaf())
	{ 
		// we assume that pvs is explicitly stored in leaves
		pvs = root->GetPvs();
		UpdateScalarPvsSize(root, pvs.EvalPvsCost(), pvs.GetSize());

		return;
	}

	////////////////
	//-- interior node => propagate pvs up the tree

	ViewCellInterior *interior = static_cast<ViewCellInterior *>(root);

	// reset interior pvs
	interior->GetPvs().Clear();

	// reset recursive pvs
	pvs.Clear();

	// pvss of child nodes
	vector<ObjectPvs> pvsList;
	pvsList.resize((int)interior->mChildren.size());

	ViewCellContainer::const_iterator vit, vit_end = interior->mChildren.end();
	
	int i = 0;

	////////
	//-- recursivly compute child pvss

	for (vit = interior->mChildren.begin(); vit != vit_end; ++ vit, ++ i)
	{
		UpdatePvsForEvaluation(*vit, pvsList[i]);
	}

#if 1
	Intersectable::NewMail();


	///////////
	//-- merge pvss

	PvsData pvsData;

	vector<ObjectPvs>::iterator oit = pvsList.begin();

	for (vit = interior->mChildren.begin(); vit != vit_end; ++ vit, ++ oit)
	{
		ObjectPvsIterator pit = (*oit).GetIterator();
		
		// add pvss to new pvs: use mailing to avoid adding entries two times.
		while (pit.HasMoreEntries())
		{		
			Intersectable *intersect = pit.Next(pvsData);

			if (!intersect->Mailed())
			{ 
				intersect->Mail();
				pvs.AddSampleDirty(intersect, pvsData.mSumPdf);
			}
		}
	}

	// store pvs in this node
	if (mViewCellsTree->ViewCellsStorage() == ViewCellsTree::PVS_IN_INTERIORS)
	{
		interior->SetPvs(pvs);
	}
	
	// set new pvs size
	UpdateScalarPvsSize(interior, pvs.EvalPvsCost(), pvs.GetSize());
	
#else 
	// really merge cells: slow but sumPdf is correct
	viewCellInterior->GetPvs().Merge(backVc->GetPvs());
	viewCellInterior->GetPvs().Merge(frontVc->GetPvs());
#endif
}



/*******************************************************************/
/*               BspViewCellsManager implementation                */
/*******************************************************************/


BspViewCellsManager::BspViewCellsManager(ViewCellsTree *vcTree, BspTree *bspTree):
ViewCellsManager(vcTree), mBspTree(bspTree)
{
	Environment::GetSingleton()->GetIntValue("BspTree.Construction.samples", mInitialSamples);

	mBspTree->SetViewCellsManager(this);
	mBspTree->SetViewCellsTree(mViewCellsTree);
}


bool BspViewCellsManager::ViewCellsConstructed() const
{
	return mBspTree->GetRoot() != NULL;
}


ViewCell *BspViewCellsManager::GenerateViewCell(Mesh *mesh) const
{
	return new BspViewCell(mesh);
}


int BspViewCellsManager::ConstructSubdivision(const ObjectContainer &objects,
											  const VssRayContainer &rays)
{
	// if view cells were already constructed, we can finish
	if (ViewCellsConstructed())
		return 0;

	int sampleContributions = 0;

	// construct view cells using the collected samples
	RayContainer constructionRays;
	VssRayContainer savedRays;

	// choose a a number of rays based on the ratio of cast rays / requested rays
	const int limit = min(mInitialSamples, (int)rays.size());
	VssRayContainer::const_iterator it, it_end = rays.end();

	const float prop = (float)limit / ((float)rays.size() + Limits::Small);

	for (it = rays.begin(); it != it_end; ++ it)
	{
		if (Random(1.0f) < prop)
			constructionRays.push_back(new Ray(*(*it)));
		else
			savedRays.push_back(*it);
	}

    if (!mUsePredefinedViewCells)
	{
		// no view cells loaded
		mBspTree->Construct(objects, constructionRays, &mViewSpaceBox);
		// collect final view cells
		mBspTree->CollectViewCells(mViewCells);
	}
	else
	{	
		// use predefined view cells geometry => 
		// contruct bsp hierarchy over them
		mBspTree->Construct(mViewCells);
	}

	// destroy rays created only for construction
	CLEAR_CONTAINER(constructionRays);

	Debug << mBspTree->GetStatistics() << endl;
	Debug << "\nView cells after construction:\n" << mCurrentViewCellsStats << endl;

	// recast rest of the rays
	if (SAMPLE_AFTER_SUBDIVISION)
		ComputeSampleContributions(savedRays, true, false);

	// real meshes are contructed at this stage
	if (0)
	{
		cout << "finalizing view cells ... ";
		FinalizeViewCells(true);
		cout << "finished" << endl;	
	}

	return sampleContributions;
}


void BspViewCellsManager::CollectViewCells()
{	
	if (!ViewCellsTreeConstructed())
	{	// view cells tree constructed	
		mBspTree->CollectViewCells(mViewCells);
	}
	else 
	{	// we can use the view cells tree hierarchy to get the right set
		mViewCellsTree->CollectBestViewCellSet(mViewCells, mNumActiveViewCells);
	}
}


float BspViewCellsManager::GetProbability(ViewCell *viewCell)
{
	if (1)
		return GetVolume(viewCell) / GetViewSpaceBox().GetVolume();
	else
		// compute view cell area as subsititute for probability
		return GetArea(viewCell) / GetAccVcArea();
}



int BspViewCellsManager::CastLineSegment(const Vector3 &origin,
										 const Vector3 &termination,
										 ViewCellContainer &viewcells)
{
	return mBspTree->CastLineSegment(origin, termination, viewcells);
}


bool BspViewCellsManager::LineSegmentIntersects(const Vector3 &origin, 
												const Vector3 &termination, 
												ViewCell *viewCell)
{
	return false;
}


void ViewCellsManager::ExportMergedViewCells(const ObjectContainer &objects)
{
	// save color code
	const int savedColorCode = mColorCode;

	Exporter *exporter;

	// export merged view cells using pvs color coding
	exporter = Exporter::GetExporter("merged_view_cells_pvs.wrl");
	cout << "exporting view cells after merge (pvs size) ... ";	

	if (exporter)
	{
		if (mExportGeometry)
		{
			exporter->ExportGeometry(objects);
		}

		exporter->SetFilled();
		mColorCode = 1;

		ExportViewCellsForViz(exporter, NULL,  mColorCode, GetClipPlane());

		delete exporter;
	}
	cout << "finished" << endl;
	
	mColorCode = savedColorCode;
}


int BspViewCellsManager::PostProcess(const ObjectContainer &objects,
									 const VssRayContainer &rays)
{
	if (!ViewCellsConstructed())
	{
		Debug << "view cells not constructed" << endl;
		return 0;
	}
	
	// view cells already finished before post processing step,
	// i.e., because they were loaded from disc
	if (mViewCellsFinished)
	{
		FinalizeViewCells(true);
		EvaluateViewCellsStats();

		return 0;
	}

	//////////////////
	//-- merge leaves of the view cell hierarchy	
	
	cout << "starting post processing using " << mPostProcessSamples << " samples ... ";
	long startTime = GetTime();
	
	VssRayContainer postProcessRays;
	GetRaySets(rays, mPostProcessSamples, postProcessRays);

	if (mMergeViewCells)
	{
		cout << "constructing visibility based merge tree" << endl;
		mViewCellsTree->ConstructMergeTree(rays, objects);
	}
	else
	{
		cout << "constructing spatial merge tree" << endl;
		ViewCell *root;
		// the spatial merge tree is difficult to build for 
		// this type of construction, as view cells cover several
		// leaves => create dummy tree which is only 2 levels deep
		if (mUsePredefinedViewCells) 
		{
			root = ConstructDummyMergeTree(mBspTree->GetRoot());
		}
		else
		{
			// create spatial merge hierarchy
			root = ConstructSpatialMergeTree(mBspTree->GetRoot());
		}
		
		mViewCellsTree->SetRoot(root);

		// recompute pvs in the whole hierarchy
		ObjectPvs pvs;
		UpdatePvsForEvaluation(root, pvs);
	}

	cout << "finished" << endl;
	cout << "merged view cells in "
		 << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;

	Debug << "Postprocessing: Merged view cells in "
		<< TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl << endl;

	
	////////////////////////
	//-- visualization and statistics after merge

	if (1)
	{
		char mstats[100];
		Environment::GetSingleton()->GetStringValue("ViewCells.mergeStats", mstats);
		mViewCellsTree->ExportStats(mstats);
	}

	// recompute view cells and stats
	ResetViewCells();
	Debug << "\nView cells after merge:\n" << mCurrentViewCellsStats << endl;

	//  visualization of the view cells
	if (1) ExportMergedViewCells(objects);

	// compute final meshes and volume / area
	if (1) FinalizeViewCells(true);
	
	return 0;
}


BspViewCellsManager::~BspViewCellsManager()
{
}


int BspViewCellsManager::GetType() const
{
	return BSP;
}


void BspViewCellsManager::Visualize(const ObjectContainer &objects,
									const VssRayContainer &sampleRays)
{
	if (!ViewCellsConstructed())
		return;
	
	const int savedColorCode = mColorCode;
	
	if (1) // export final view cells
	{
		mColorCode = 1; // 0 = pvs, 1 = random
		Exporter *exporter = Exporter::GetExporter("final_view_cells.wrl");
	
		cout << "exporting view cells after merge (pvs size) ... ";	

		if (exporter)
		{
			if (mExportGeometry)
			{
				exporter->ExportGeometry(objects);
			}

			ExportViewCellsForViz(exporter, NULL, mColorCode, GetClipPlane());
			delete exporter;
		}
		cout << "finished" << endl;
	}

	// reset color code
	mColorCode = savedColorCode;


	//////////////////
	//-- visualization of the BSP splits

	bool exportSplits = false;
	Environment::GetSingleton()->GetBoolValue("BspTree.Visualization.exportSplits", exportSplits);

	if (exportSplits)
	{
		cout << "exporting splits ... ";
	 	ExportSplits(objects);
		cout << "finished" << endl;
	}

	int leafOut;
	Environment::GetSingleton()->GetIntValue("ViewCells.Visualization.maxOutput", leafOut);
	const int raysOut = 100;
	ExportSingleViewCells(objects, leafOut, false, true, false, raysOut, "");
}


void BspViewCellsManager::ExportSplits(const ObjectContainer &objects)
{
	Exporter *exporter = Exporter::GetExporter("bsp_splits.x3d");

	if (exporter)
	{
		//exporter->SetFilled();
		if (mExportGeometry)
		{
			exporter->ExportGeometry(objects);
		}

		Material m;
		m.mDiffuseColor = RgbColor(1, 0, 0);
		exporter->SetForcedMaterial(m);
		exporter->SetWireframe();

		exporter->ExportBspSplits(*mBspTree, true);

		// NOTE: take forced material, else big scenes cannot be viewed
		m.mDiffuseColor = RgbColor(0, 1, 0);
		exporter->SetForcedMaterial(m);
		//exporter->ResetForcedMaterial();

		delete exporter;
	}
}


void BspViewCellsManager::ExportSingleViewCells(const ObjectContainer &objects,
												const int maxViewCells,
												const bool sortViewCells,
												const bool exportPvs,
												const bool exportRays,
												const int maxRays,
												const string &prefix,
												VssRayContainer *visRays)
{
	if (sortViewCells)
	{	// sort view cells to visualize the largest view cells
		sort(mViewCells.begin(), mViewCells.end(), LargerRenderCost);
	}

	//////////
	//-- export visualizations of some view cells

	ViewCell::NewMail();
	const int limit = min(maxViewCells, (int)mViewCells.size());
	
	for (int i = 0; i < limit; ++ i)
	{
		const int idx = sortViewCells ? (int)RandomValue(0, (float)mViewCells.size() - 0.5f) : i;
		ViewCell *vc = mViewCells[idx];

		if (vc->Mailed() || vc->GetId() == OUT_OF_BOUNDS_ID)
			continue;

		vc->Mail();

		ObjectPvs pvs;
		mViewCellsTree->GetPvs(vc, pvs);

		char s[64]; sprintf(s, "%sviewcell-%04d.wrl", prefix.c_str(), i);
		Exporter *exporter = Exporter::GetExporter(s);
		
		cout << "view cell " << idx << ": pvs cost=" << (int)mViewCellsTree->GetTrianglesInPvs(vc) << endl;

		if (exportRays)
		{
			////////////
			//-- export rays piercing this view cell

			// use rays stored with the view cells
			VssRayContainer vcRays, vcRays2, vcRays3;
            VssRayContainer collectRays;

			// collect initial view cells
			ViewCellContainer leaves;
			mViewCellsTree->CollectLeaves(vc, leaves);

			ViewCellContainer::const_iterator vit, vit_end = leaves.end();
       		for (vit = leaves.begin(); vit != vit_end; ++ vit)
			{	
				// prepare some rays for visualization
				VssRayContainer::const_iterator rit, rit_end = (*vit)->GetOrCreateRays()->end();
				for (rit = (*vit)->GetOrCreateRays()->begin(); rit != rit_end; ++ rit)
				{
					collectRays.push_back(*rit);
				}
			}

			const int raysOut = min((int)collectRays.size(), maxRays);

			// prepare some rays for visualization
			VssRayContainer::const_iterator rit, rit_end = collectRays.end();
			for (rit = collectRays.begin(); rit != rit_end; ++ rit)
			{
				const float p = RandomValue(0.0f, (float)collectRays.size());
				if (p < raysOut)
				{
					if ((*rit)->mFlags & VssRay::BorderSample)
					{
						vcRays.push_back(*rit);
					}
					else if ((*rit)->mFlags & VssRay::ReverseSample)
					{
						vcRays2.push_back(*rit);
					}
					else
					{
						vcRays3.push_back(*rit);
					}	
				}
			}

			exporter->ExportRays(vcRays, RgbColor(1, 0, 0));
			exporter->ExportRays(vcRays2, RgbColor(0, 1, 0));
			exporter->ExportRays(vcRays3, RgbColor(1, 1, 1));
		}
		
		////////////////
		//-- export view cell geometry

		exporter->SetWireframe();

		Material m;//= RandomMaterial();
		m.mDiffuseColor = RgbColor(0, 1, 0);
		exporter->SetForcedMaterial(m);

		ExportViewCellGeometry(exporter, vc, NULL, NULL);
		exporter->SetFilled();

		if (exportPvs)
		{
			Intersectable::NewMail();
			ObjectPvsIterator pit = pvs.GetIterator();

			while (pit.HasMoreEntries())
			{		
				Intersectable *intersect = pit.Next();

                // output PVS of view cell
				if (!intersect->Mailed())
				{
					intersect->Mail();

					m = RandomMaterial();
					exporter->SetForcedMaterial(m);
					exporter->ExportIntersectable(intersect);
				}
			}
			cout << endl;
		}
		
		DEL_PTR(exporter);
		cout << "finished" << endl;
	}
}


void BspViewCellsManager::TestSubdivision()
{
	ViewCellContainer leaves;
	mViewCellsTree->CollectLeaves(mViewCellsTree->GetRoot(), leaves);

	ViewCellContainer::const_iterator it, it_end = leaves.end();

	const float vol = mViewSpaceBox.GetVolume();
	float subdivVol = 0;
	float newVol = 0;

	for (it = leaves.begin(); it != it_end; ++ it)
	{
		BspNodeGeometry geom;
		mBspTree->ConstructGeometry(*it, geom);

		const float lVol = geom.GetVolume();
		newVol += lVol;
		subdivVol += (*it)->GetVolume();

		const float thres = 0.9f;
		if ((lVol < ((*it)->GetVolume() * thres)) ||
			(lVol * thres > ((*it)->GetVolume())))
			Debug << "warning: " << lVol << " " << (*it)->GetVolume() << endl;
	}
	
	Debug << "exact volume: " << vol << endl;
	Debug << "subdivision volume: " << subdivVol << endl;
	Debug << "new volume: " << newVol << endl;
}


void BspViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
												 ViewCell *vc,
												 const AxisAlignedBox3 *sceneBox,
												 const AxisAlignedPlane *clipPlane
												 ) const
{
	if (clipPlane)
	{
		const Plane3 plane = clipPlane->GetPlane();

		ViewCellContainer leaves;
		mViewCellsTree->CollectLeaves(vc, leaves);
		ViewCellContainer::const_iterator it, it_end = leaves.end();

		for (it = leaves.begin(); it != it_end; ++ it)
		{
			BspNodeGeometry geom;
			BspNodeGeometry front;
			BspNodeGeometry back;

			mBspTree->ConstructGeometry(*it, geom);

			const float eps = 0.0001f;
			const int cf = geom.Side(plane, eps);

			if (cf == -1)
			{
				exporter->ExportPolygons(geom.GetPolys());
			}
			else if (cf == 0)
			{
				geom.SplitGeometry(front,
								   back,
								   plane,
								   mViewSpaceBox, 
								   eps);

				if (back.Valid())
				{
					exporter->ExportPolygons(back.GetPolys());
				}			
			}
		}
	}
	else
	{
		// export mesh if available
		// TODO: some bug here?
		if (1 && vc->GetMesh())
		{
			exporter->ExportMesh(vc->GetMesh());
		}
		else
		{
			BspNodeGeometry geom;
			mBspTree->ConstructGeometry(vc, geom);
			exporter->ExportPolygons(geom.GetPolys());
		}
	}
}


void BspViewCellsManager::CreateMesh(ViewCell *vc)
{
	// note: should previous mesh be deleted (via mesh manager?)
	BspNodeGeometry geom;
	mBspTree->ConstructGeometry(vc, geom);

	Mesh *mesh = MeshManager::GetSingleton()->CreateResource();
	
	IncludeNodeGeomInMesh(geom, *mesh);
	mesh->ComputeBoundingBox();

	vc->SetMesh(mesh);
}


void BspViewCellsManager::Finalize(ViewCell *viewCell, 
								   const bool createMesh)
{
	float area = 0;
	float volume = 0;

	ViewCellContainer leaves;
	mViewCellsTree->CollectLeaves(viewCell, leaves);

	ViewCellContainer::const_iterator it, it_end = leaves.end();

    for (it = leaves.begin(); it != it_end; ++ it)
	{
		BspNodeGeometry geom;

		mBspTree->ConstructGeometry(*it, geom);

		const float lVol = geom.GetVolume();
		const float lArea = geom.GetArea();

		area += lArea;
		volume += lVol;
	
		CreateMesh(*it);
	}

	viewCell->SetVolume(volume);
	viewCell->SetArea(area);
}


ViewCell *BspViewCellsManager::GetViewCell(const Vector3 &point, const bool active) const
{
	if (!ViewCellsConstructed())
	{
		return NULL;
	}
	if (!mViewSpaceBox.IsInside(point))
	{
		return NULL;
	}
	return mBspTree->GetViewCell(point);
}


void BspViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays, 
												 vector<MergeCandidate> &candidates)
{
	cout << "collecting merge candidates ... " << endl;

	if (mUseRaysForMerge)
	{
		mBspTree->CollectMergeCandidates(rays, candidates);
	}
	else
	{
		vector<BspLeaf *> leaves;
		mBspTree->CollectLeaves(leaves);
		mBspTree->CollectMergeCandidates(leaves, candidates);
	}

	cout << "fininshed collecting candidates" << endl;
}



bool BspViewCellsManager::ExportViewCells(const string filename, 
										  const bool exportPvs, 
										  const ObjectContainer &objects)
{
	if (!ViewCellsConstructed() || !ViewCellsTreeConstructed())
	{
		return false;
	}

	cout << "exporting view cells to xml ... ";

	OUT_STREAM stream(filename.c_str());

	// we need unique ids for each view cell
	CreateUniqueViewCellIds();

	stream << "<?xml version=\"1.0\" encoding=\"UTF-8\"?>"<<endl;
	stream << "<VisibilitySolution>" << endl;

	if (exportPvs) 
	{
		//////////
		//-- export bounding boxes: they are used to identify the objects from the pvs and
		//-- assign them to the entities in the rendering engine

		stream << "<BoundingBoxes>" << endl;
		ObjectContainer::const_iterator oit, oit_end = objects.end();

		for (oit = objects.begin(); oit != oit_end; ++ oit)
		{
			const AxisAlignedBox3 box = (*oit)->GetBox();
			
			stream << "<BoundingBox" << " id=\"" << (*oit)->GetId() << "\""
				   << " min=\"" << box.Min().x << " " << box.Min().y << " " << box.Min().z << "\""
				   << " max=\"" << box.Max().x << " " << box.Max().y << " " << box.Max().z << "\" />" << endl;
		}

		stream << "</BoundingBoxes>" << endl;
	}

	///////////
	//-- export the view cells and the pvs

	const int numViewCells = mCurrentViewCellsStats.viewCells;
	stream << "<ViewCells number=\"" << numViewCells << "\" >" << endl;

	mViewCellsTree->Export(stream, exportPvs);
	
	stream << "</ViewCells>" << endl;

	/////////////
	//-- export the view space hierarchy
	stream << "<ViewSpaceHierarchy type=\"bsp\""
		   << " min=\"" << mViewSpaceBox.Min().x << " " << mViewSpaceBox.Min().y << " " << mViewSpaceBox.Min().z << "\""
		   << " max=\"" << mViewSpaceBox.Max().x << " " << mViewSpaceBox.Max().y << " " << mViewSpaceBox.Max().z << "\">" << endl;

	mBspTree->Export(stream);

	// end tags
	stream << "</ViewSpaceHierarchy>" << endl;
	stream << "</VisibilitySolution>" << endl;

	stream.close();
	cout << "finished" << endl;

	return true;
}


ViewCell *BspViewCellsManager::ConstructDummyMergeTree(BspNode *root)
{
	ViewCellInterior *vcRoot = new ViewCellInterior();
		
	// evaluate merge cost for priority traversal
	const float mergeCost =  -(float)root->mTimeStamp;
	vcRoot->SetMergeCost(mergeCost);

	float volume = 0;
	vector<BspLeaf *> leaves;
	mBspTree->CollectLeaves(leaves);
	vector<BspLeaf *>::const_iterator lit, lit_end = leaves.end();
	ViewCell::NewMail();

	for (lit = leaves.begin(); lit != lit_end; ++ lit)
	{
		BspLeaf *leaf = *lit;
		ViewCell *vc = leaf->GetViewCell();

		if (!vc->Mailed())
		{
			vc->Mail();
			vc->SetMergeCost(0.0f);
			vcRoot->SetupChildLink(vc);

			volume += vc->GetVolume();
			volume += vc->GetVolume();	
			vcRoot->SetVolume(volume);
		}
	}
	
	return vcRoot;
}


ViewCell *BspViewCellsManager::ConstructSpatialMergeTree(BspNode *root)
{
	// terminate recursion
	if (root->IsLeaf())
	{
		BspLeaf *leaf = static_cast<BspLeaf *>(root);
		leaf->GetViewCell()->SetMergeCost(0.0f);
		return leaf->GetViewCell();
	}
	
	BspInterior *interior = static_cast<BspInterior *>(root);
	ViewCellInterior *viewCellInterior = new ViewCellInterior();
		
	// evaluate merge cost for priority traversal
	const float mergeCost = -(float)root->mTimeStamp;
	viewCellInterior->SetMergeCost(mergeCost);

	float volume = 0;
	
	BspNode *front = interior->GetFront();
	BspNode *back = interior->GetBack();


	////////////
	//-- recursivly compute child hierarchies

	ViewCell *backVc = ConstructSpatialMergeTree(back);
	ViewCell *frontVc = ConstructSpatialMergeTree(front);

	viewCellInterior->SetupChildLink(backVc);
	viewCellInterior->SetupChildLink(frontVc);

	volume += backVc->GetVolume();
	volume += frontVc->GetVolume();	

	viewCellInterior->SetVolume(volume);

	return viewCellInterior;
}


/************************************************************************/
/*                   KdViewCellsManager implementation                  */
/************************************************************************/



KdViewCellsManager::KdViewCellsManager(ViewCellsTree *vcTree, KdTree *kdTree):
ViewCellsManager(vcTree), mKdTree(kdTree), mKdPvsDepth(100)
{
}


float KdViewCellsManager::GetProbability(ViewCell *viewCell)
{
	// compute view cell area / volume as subsititute for probability
	if (0)
		return GetArea(viewCell) / GetViewSpaceBox().SurfaceArea();
	else
		return GetVolume(viewCell) / GetViewSpaceBox().GetVolume();
}




void KdViewCellsManager::CollectViewCells()
{
	//mKdTree->CollectViewCells(mViewCells); TODO
}


int KdViewCellsManager::ConstructSubdivision(const ObjectContainer &objects,
								  const VssRayContainer &rays)
{
	// if view cells already constructed
	if (ViewCellsConstructed())
		return 0;

	mKdTree->Construct();

	mTotalAreaValid = false;
	// create the view cells
	mKdTree->CreateAndCollectViewCells(mViewCells);
	// cast rays
	ComputeSampleContributions(rays, true, false);

	EvaluateViewCellsStats();
	Debug << "\nView cells after construction:\n" << mCurrentViewCellsStats << endl;

	return 0;
}


bool KdViewCellsManager::ViewCellsConstructed() const
{
	return mKdTree->GetRoot() != NULL;
}


int KdViewCellsManager::PostProcess(const ObjectContainer &objects,
									const VssRayContainer &rays)
{
	return 0;
}


void KdViewCellsManager::ExportSingleViewCells(const ObjectContainer &objects,
											   const int maxViewCells,
											   const bool sortViewCells,
											   const bool exportPvs,
											   const bool exportRays,
											   const int maxRays,
											   const string &prefix,
											   VssRayContainer *visRays)
{
	// TODO
}


void KdViewCellsManager::Visualize(const ObjectContainer &objects,
								   const VssRayContainer &sampleRays)
{
	if (!ViewCellsConstructed())
		return;

	// using view cells instead of the kd PVS of objects
	const bool useViewCells = true;
	bool exportRays = false;

	int limit = min(mVisualizationSamples, (int)sampleRays.size());
	const int pvsOut = min((int)objects.size(), 10);
	VssRayContainer *rays = new VssRayContainer[pvsOut];

	if (useViewCells)
	{
		const int leafOut = 10;

		ViewCell::NewMail();

		//-- some rays for visualization
		const int raysOut = min((int)sampleRays.size(), mVisualizationSamples);
		Debug << "visualization using " << raysOut << " samples" << endl;

		//-- some random view cells and rays for visualization
		vector<KdLeaf *> kdLeaves;

		for (int i = 0; i < leafOut; ++ i)
			kdLeaves.push_back(static_cast<KdLeaf *>(mKdTree->GetRandomLeaf()));

		for (int i = 0; i < kdLeaves.size(); ++ i)
		{
			KdLeaf *leaf = kdLeaves[i];
			RayContainer vcRays;

			cout << "creating output for view cell " << i << " ... ";
#if 0
			// check whether we can add the current ray to the output rays
			for (int k = 0; k < raysOut; ++ k)
			{
				Ray *ray = sampleRays[k];

				for (int j = 0; j < (int)ray->bspIntersections.size(); ++ j)
				{
					BspLeaf *leaf2 = ray->bspIntersections[j].mLeaf;

					if (leaf->GetViewCell() == leaf2->GetViewCell())
					{
						vcRays.push_back(ray);
					}
				}
			}
#endif
			Intersectable::NewMail();

			ViewCell *vc = leaf->mViewCell;
			char str[64]; sprintf(str, "viewcell%04d.wrl", i);

			Exporter *exporter = Exporter::GetExporter(str);
			exporter->SetFilled();

			exporter->SetWireframe();
			//exporter->SetFilled();

			Material m;//= RandomMaterial();
			m.mDiffuseColor = RgbColor(1, 1, 0);
			exporter->SetForcedMaterial(m);

			AxisAlignedBox3 box = mKdTree->GetBox(leaf);
			exporter->ExportBox(box);

			// export rays piercing this view cell
			exporter->ExportRays(vcRays, 1000, RgbColor(0, 1, 0));

			m.mDiffuseColor = RgbColor(1, 0, 0);
			exporter->SetForcedMaterial(m);

			// exporter->SetWireframe();
			exporter->SetFilled();

			ObjectPvsIterator pit = vc->GetPvs().GetIterator();
			
			while (pit.HasMoreEntries())
			{		
				//-- output PVS of view cell
				Intersectable *intersect = pit.Next();

				if (!intersect->Mailed())
				{
					exporter->ExportIntersectable(intersect);
					intersect->Mail();
				}
			}

			DEL_PTR(exporter);
			cout << "finished" << endl;
		}

		DEL_PTR(rays);
	}
	else // using kd PVS of objects
	{
		for (int i = 0; i < limit; ++ i)
		{
			VssRay *ray = sampleRays[i];

			// check whether we can add this to the rays
			for (int j = 0; j < pvsOut; j++)
			{
				if (objects[j] == ray->mTerminationObject)
				{
					rays[j].push_back(ray);
				}
			}
		}

		if (exportRays)
		{
			Exporter *exporter = NULL;
			exporter = Exporter::GetExporter("sample-rays.x3d");
			exporter->SetWireframe();
			exporter->ExportKdTree(*mKdTree);

			for (int i = 0; i < pvsOut; i++)
				exporter->ExportRays(rays[i], RgbColor(1, 0, 0));

			exporter->SetFilled();
			delete exporter;
		}

		for (int k=0; k < pvsOut; k++)
		{
			Intersectable *object = objects[k];
			char str[64]; sprintf(str, "viewcell%04d.wrl", k);

			Exporter *exporter = Exporter::GetExporter(str);
			exporter->SetWireframe();

			// matt: we do not use kd pvs
#if 0
			KdPvsMap::iterator kit = object->mKdPvs.mEntries.begin();
			Intersectable::NewMail();

			// avoid adding the object to the list
			object->Mail();
			ObjectContainer visibleObjects;

			for (; kit != object->mKdPvs.mEntries.end(); i++)
			{
				KdNode *node = (*kit).first;
				exporter->ExportBox(mKdTree->GetBox(node));

				mKdTree->CollectObjects(node, visibleObjects);
			}

			exporter->ExportRays(rays[k],  RgbColor(0, 1, 0));
			exporter->SetFilled();

			for (int j = 0; j < visibleObjects.size(); j++)
				exporter->ExportIntersectable(visibleObjects[j]);

			Material m;
			m.mDiffuseColor = RgbColor(1, 0, 0);
			exporter->SetForcedMaterial(m);
			exporter->ExportIntersectable(object);
#endif
			delete exporter;
		}
	}
}


ViewCell *KdViewCellsManager::GenerateViewCell(Mesh *mesh) const
{
	return new KdViewCell(mesh);
}


void KdViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
												ViewCell *vc,
												const AxisAlignedBox3 *sceneBox,
												const AxisAlignedPlane *clipPlane
												) const
{
	ViewCellContainer leaves;
	mViewCellsTree->CollectLeaves(vc, leaves);
	ViewCellContainer::const_iterator it, it_end = leaves.end();

	for (it = leaves.begin(); it != it_end; ++ it)
	{
		KdViewCell *kdVc = static_cast<KdViewCell *>(*it);
		exporter->ExportBox(mKdTree->GetBox(kdVc->mLeaves[0]));
	}
}


int KdViewCellsManager::GetType() const
{
	return ViewCellsManager::KD;
}



KdNode *KdViewCellsManager::GetNodeForPvs(KdLeaf *leaf)
{
	KdNode *node = leaf;

	while (node->mParent && node->mDepth > mKdPvsDepth)
		node = node->mParent;

	return node;
}

int KdViewCellsManager::CastLineSegment(const Vector3 &origin,
										const Vector3 &termination,
										ViewCellContainer &viewcells)
{
	return mKdTree->CastLineSegment(origin, termination, viewcells);
}


bool KdViewCellsManager::LineSegmentIntersects(const Vector3 &origin, 
											   const Vector3 &termination, 
											   ViewCell *viewCell)
{
	return false;
}


void KdViewCellsManager::CreateMesh(ViewCell *vc)
{
	// TODO
}



void KdViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays, 
												vector<MergeCandidate> &candidates)
{
	// TODO
}



/**************************************************************************/
/*                   VspBspViewCellsManager implementation                */
/**************************************************************************/


VspBspViewCellsManager::VspBspViewCellsManager(ViewCellsTree *vcTree, VspBspTree *vspBspTree):
ViewCellsManager(vcTree), mVspBspTree(vspBspTree)
{
	Environment::GetSingleton()->GetIntValue("VspBspTree.Construction.samples", mInitialSamples);
	mVspBspTree->SetViewCellsManager(this);
	mVspBspTree->mViewCellsTree = mViewCellsTree;
}


VspBspViewCellsManager::~VspBspViewCellsManager()
{
}


float VspBspViewCellsManager::GetProbability(ViewCell *viewCell)
{
	if (0 && mVspBspTree->mUseAreaForPvs)
		return GetArea(viewCell) / GetAccVcArea();
	else
		return GetVolume(viewCell) / mViewSpaceBox.GetVolume();
}


void VspBspViewCellsManager::CollectViewCells()
{
	// view cells tree constructed?
	if (!ViewCellsTreeConstructed())
	{
		mVspBspTree->CollectViewCells(mViewCells, false);
	}
	else 
	{	
		// we can use the view cells tree hierarchy to get the right set
		mViewCellsTree->CollectBestViewCellSet(mViewCells, mNumActiveViewCells);
	}
}


void VspBspViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays, 
													vector<MergeCandidate> &candidates)
{	
	cout << "collecting merge candidates ... " << endl;

	if (mUseRaysForMerge)
	{
		mVspBspTree->CollectMergeCandidates(rays, candidates);
	}
	else
	{
		vector<BspLeaf *> leaves;
		mVspBspTree->CollectLeaves(leaves);
	
		mVspBspTree->CollectMergeCandidates(leaves, candidates);
	}

	cout << "fininshed collecting candidates" << endl;
}


bool VspBspViewCellsManager::ViewCellsConstructed() const
{
	return mVspBspTree->GetRoot() != NULL;
}


ViewCell *VspBspViewCellsManager::GenerateViewCell(Mesh *mesh) const
{
	return new BspViewCell(mesh);
}


int VspBspViewCellsManager::ConstructSubdivision(const ObjectContainer &objects,
												 const VssRayContainer &rays)
{
	mMaxPvsSize = (int)(mMaxPvsRatio * (float)objects.size());

	// if view cells were already constructed
	if (ViewCellsConstructed())
	{
		return 0;
	}

	int sampleContributions = 0;
	VssRayContainer sampleRays;

	const int limit = min(mInitialSamples, (int)rays.size());

	Debug << "samples used for vsp bsp subdivision: " << mInitialSamples 
		  << ", actual rays: " << (int)rays.size() << endl;

	VssRayContainer savedRays;

	if (SAMPLE_AFTER_SUBDIVISION)
	{
		VssRayContainer constructionRays;
		
		GetRaySets(rays, mInitialSamples, constructionRays, &savedRays);

		Debug << "rays used for initial construction: " << (int)constructionRays.size() << endl;
		Debug << "rays saved for later use: " << (int)savedRays.size() << endl;
	
		mVspBspTree->Construct(constructionRays, &mViewSpaceBox);
	}
	else
	{
		Debug << "rays used for initial construction: " << (int)rays.size() << endl;
		mVspBspTree->Construct(rays, &mViewSpaceBox);
	}

	// collapse invalid regions
	cout << "collapsing invalid tree regions ... ";
	long startTime = GetTime();

	const int collapsedLeaves = mVspBspTree->CollapseTree();
	Debug << "collapsed in " << TimeDiff(startTime, GetTime()) * 1e-3 
		  << " seconds" << endl;

    cout << "finished" << endl;

	/////////////////
	//-- stats after construction

	Debug << mVspBspTree->GetStatistics() << endl;

	ResetViewCells();
	Debug << "\nView cells after construction:\n" << mCurrentViewCellsStats << endl;


	//////////////////////
	//-- recast the rest of the rays

	startTime = GetTime();

	cout << "Computing remaining ray contributions ... ";

	if (SAMPLE_AFTER_SUBDIVISION)
		ComputeSampleContributions(savedRays, true, false);

	cout << "finished" << endl;

	Debug << "Computed remaining ray contribution in " << TimeDiff(startTime, GetTime()) * 1e-3
		  << " secs" << endl;

	cout << "construction finished" << endl;

	if (0)
	{	////////
		//-- real meshes are contructed at this stage

		cout << "finalizing view cells ... ";
		FinalizeViewCells(true);
		cout << "finished" << endl;
	}

	return sampleContributions;
}


void VspBspViewCellsManager::MergeViewCells(const VssRayContainer &rays,
											const ObjectContainer &objects)
{
    int vcSize = 0;
	int pvsSize = 0;

	//-- merge view cells
	cout << "starting merge using " << mPostProcessSamples << " samples ... " << endl;
	long startTime = GetTime();


	if (mMergeViewCells)
	{
		// TODO: should be done BEFORE the ray casting
		// compute tree by merging the nodes based on cost heuristics
		mViewCellsTree->ConstructMergeTree(rays, objects);
	}
	else
	{
		// compute tree by merging the nodes of the spatial hierarchy
		ViewCell *root = ConstructSpatialMergeTree(mVspBspTree->GetRoot());
		mViewCellsTree->SetRoot(root);

		// compute pvs
		ObjectPvs pvs;
		UpdatePvsForEvaluation(root, pvs);
	}

	if (1)
	{
		char mstats[100];
		ObjectPvs pvs;

		Environment::GetSingleton()->GetStringValue("ViewCells.mergeStats", mstats);
		mViewCellsTree->ExportStats(mstats);
	}

	cout << "merged view cells in "
		 << TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl;

	Debug << "Postprocessing: Merged view cells in "
		  << TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl << endl;
	

	//////////////////
	//-- stats and visualizations

	int savedColorCode = mColorCode;
	
	// get currently active view cell set
	ResetViewCells();
	Debug << "\nView cells after merge:\n" << mCurrentViewCellsStats << endl;
	
	if (mShowVisualization) // export merged view cells
	{
		mColorCode = 0;
		Exporter *exporter = Exporter::GetExporter("merged_view_cells.wrl");
		
		cout << "exporting view cells after merge ... ";

		if (exporter)
		{
			if (0)
				exporter->SetWireframe();
			else
				exporter->SetFilled();

			ExportViewCellsForViz(exporter, NULL, mColorCode, GetClipPlane());

			if (mExportGeometry)
			{
				Material m;
				m.mDiffuseColor = RgbColor(0, 1, 0);
				exporter->SetForcedMaterial(m);
				exporter->SetFilled();

				exporter->ExportGeometry(objects);
			}

			delete exporter;
		}
		cout << "finished" << endl;
	}

	mColorCode = savedColorCode;
}


void VspBspViewCellsManager::RefineViewCells(const VssRayContainer &rays,
											 const ObjectContainer &objects)
{
	mRenderer->RenderScene();

	SimulationStatistics ss;
	static_cast<RenderSimulator *>(mRenderer)->GetStatistics(ss);
    Debug << "render time before refine\n\n" << ss << endl;

	const long startTime = GetTime();
	cout << "Refining the merged view cells ... ";

	// refining the merged view cells
	const int refined = mViewCellsTree->RefineViewCells(rays, objects);

	//-- stats and visualizations
	cout << "finished" << endl;
	cout << "refined " << refined << " view cells in "
		 << TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl;

	Debug << "Postprocessing: refined " << refined << " view cells in "
		  << TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl << endl;
}


int VspBspViewCellsManager::PostProcess(const ObjectContainer &objects,
										const VssRayContainer &rays)
{
	if (!ViewCellsConstructed())
	{
		Debug << "postprocess error: no view cells constructed" << endl;
		return 0;
	}

	// view cells already finished before post processing step 
	// (i.e. because they were loaded)
	if (mViewCellsFinished)
	{
		FinalizeViewCells(true);
		EvaluateViewCellsStats();

		return 0;
	}

	// check if new view cells turned invalid
	int minPvs, maxPvs;

	if (0)
	{
		minPvs = mMinPvsSize;
		maxPvs = mMaxPvsSize;
	}
	else
	{
		// problem matt: why did I start here from zero?
		minPvs = 0;
		maxPvs = mMaxPvsSize;
	}

	Debug << "setting validity, min: " << minPvs << " max: " << maxPvs << endl;
	cout << "setting validity, min: " << minPvs << " max: " << maxPvs << endl;
	
	SetValidity(minPvs, maxPvs); 

	// update valid view space according to valid view cells
	if (0) mVspBspTree->ValidateTree();

	// area has to be recomputed
	mTotalAreaValid = false;
	VssRayContainer postProcessRays;
	GetRaySets(rays, mPostProcessSamples, postProcessRays);

	Debug << "post processing using " << (int)postProcessRays.size() << " samples" << endl;

	//////////
	//-- merge neighbouring view cells
	MergeViewCells(postProcessRays, objects);
	
	// refines the merged view cells
	if (0) RefineViewCells(postProcessRays, objects);


	///////////
	//-- render simulation after merge + refine

	cout << "\nview cells partition render time before compress" << endl << endl;;
	static_cast<RenderSimulator *>(mRenderer)->RenderScene();
	SimulationStatistics ss;
	static_cast<RenderSimulator *>(mRenderer)->GetStatistics(ss);
 	cout << ss << endl;
	
	if (0) CompressViewCells();
	
	// collapse sibling leaves that share the same view cell
	if (0) mVspBspTree->CollapseTree();

	// recompute view cell list and statistics
	ResetViewCells();

	// compute final meshes and volume / area
	if (1) FinalizeViewCells(true);

	return 0;
}


int VspBspViewCellsManager::GetType() const
{
	return VSP_BSP;
}


ViewCell *VspBspViewCellsManager::ConstructSpatialMergeTree(BspNode *root)
{
	// terminate recursion
	if (root->IsLeaf())
	{
		BspLeaf *leaf = static_cast<BspLeaf *>(root);
		leaf->GetViewCell()->SetMergeCost(0.0f);
		return leaf->GetViewCell();
	}
	
	
	BspInterior *interior = static_cast<BspInterior *>(root);
	ViewCellInterior *viewCellInterior = new ViewCellInterior();
		
	// evaluate merge cost for priority traversal
	float mergeCost = 1.0f / (float)root->mTimeStamp;
	viewCellInterior->SetMergeCost(mergeCost);

	float volume = 0;
	
	BspNode *front = interior->GetFront();
	BspNode *back = interior->GetBack();


	ObjectPvs frontPvs, backPvs;

	//-- recursivly compute child hierarchies
	ViewCell *backVc = ConstructSpatialMergeTree(back);
	ViewCell *frontVc = ConstructSpatialMergeTree(front);


	viewCellInterior->SetupChildLink(backVc);
	viewCellInterior->SetupChildLink(frontVc);

	volume += backVc->GetVolume();
	volume += frontVc->GetVolume();	

	viewCellInterior->SetVolume(volume);

	return viewCellInterior;
}


bool VspBspViewCellsManager::GetViewPoint(Vector3 &viewPoint) const
{
	if (!ViewCellsConstructed())
		return ViewCellsManager::GetViewPoint(viewPoint);

	// TODO: set reasonable limit
	const int limit = 20;

	for (int i = 0; i < limit; ++ i)
	{
		viewPoint = mViewSpaceBox.GetRandomPoint();
		if (mVspBspTree->ViewPointValid(viewPoint))
		{
			return true;
		}
	}

	Debug << "failed to find valid view point, taking " << viewPoint << endl;
	return false;
}


bool VspBspViewCellsManager::ViewPointValid(const Vector3 &viewPoint) const
{
	// $$JB -> implemented in viewcellsmanager (slower, but allows dynamic
	// validy update in preprocessor for all managers)
	return ViewCellsManager::ViewPointValid(viewPoint);

	//	return mViewSpaceBox.IsInside(viewPoint) &&
	//		   mVspBspTree->ViewPointValid(viewPoint);
}


void VspBspViewCellsManager::Visualize(const ObjectContainer &objects,
									   const VssRayContainer &sampleRays)
{
	if (!ViewCellsConstructed())
		return;

	VssRayContainer visRays;
	GetRaySets(sampleRays, mVisualizationSamples, visRays);
	
	if (1) 
	{	
		//////////////////
		//-- export final view cell partition

		Exporter *exporter = Exporter::GetExporter("final_view_cells.wrl");
		
		if (exporter)
		{
			cout << "exporting view cells after post process ... ";

			if (0)
			{	// export view space box
				exporter->SetWireframe();
				exporter->ExportBox(mViewSpaceBox);
				exporter->SetFilled();
			}

			Material m; 
			m.mDiffuseColor.r = 0.0f;
			m.mDiffuseColor.g = 0.5f;
			m.mDiffuseColor.b = 0.5f;

            exporter->SetForcedMaterial(m);

			if (1 && mExportGeometry)
			{
				exporter->ExportGeometry(objects);
			}

			if (0 && mExportRays)
			{
				exporter->ExportRays(visRays, RgbColor(1, 0, 0));
			}
			ExportViewCellsForViz(exporter, NULL, mColorCode, GetClipPlane());

			delete exporter;
			cout << "finished" << endl;
		}
	}

	////////////////
	//-- visualization of the BSP splits

	bool exportSplits = false;
	Environment::GetSingleton()->GetBoolValue("VspBspTree.Visualization.exportSplits", exportSplits);

	if (exportSplits)
	{
		cout << "exporting splits ... ";
	 	ExportSplits(objects, visRays);
		cout << "finished" << endl;
	}

	////////
	//-- export single view cells
	
	int leafOut;
	Environment::GetSingleton()->GetIntValue("ViewCells.Visualization.maxOutput", leafOut);
	const int raysOut = 100;
	
	ExportSingleViewCells(objects, leafOut, false, true, false, raysOut, "");
}


void VspBspViewCellsManager::ExportSplits(const ObjectContainer &objects,
										  const VssRayContainer &rays)
{
	Exporter *exporter = Exporter::GetExporter("bsp_splits.x3d");

	if (exporter)
	{
		Material m;
		m.mDiffuseColor = RgbColor(1, 0, 0);
		exporter->SetForcedMaterial(m);
		exporter->SetWireframe();

		exporter->ExportBspSplits(*mVspBspTree, true);

		// take forced material, else big scenes cannot be viewed
		m.mDiffuseColor = RgbColor(0, 1, 0);
		exporter->SetForcedMaterial(m);
		exporter->SetFilled();

		exporter->ResetForcedMaterial();

		// export rays
		if (mExportRays)
		{
			exporter->ExportRays(rays, RgbColor(1, 1, 0));
		}

		if (mExportGeometry)
		{
			exporter->ExportGeometry(objects);
		}
		delete exporter;
	}
}


void VspBspViewCellsManager::ExportSingleViewCells(const ObjectContainer &objects,
												   const int maxViewCells,
												   const bool sortViewCells,
												   const bool exportPvs,
												   const bool exportRays,
												   const int maxRays,
												   const string &prefix,
												   VssRayContainer *visRays)
{	
	if (sortViewCells)
	{
		// sort view cells to visualize the largest view cells
		sort(mViewCells.begin(), mViewCells.end(), LargerRenderCost);
	}

	//////////
	//-- export some view cells for visualization

	ViewCell::NewMail();
	const int limit = min(maxViewCells, (int)mViewCells.size());
	
	for (int i = 0; i < limit; ++ i)
	{
		cout << "creating output for view cell " << i << " ... ";

		ViewCell *vc = sortViewCells ? // largest view cell pvs first?
			mViewCells[(int)RandomValue(0, (float)mViewCells.size() - 0.5f)] : mViewCells[i];

		if (vc->Mailed() || vc->GetId() == OUT_OF_BOUNDS_ID)
			continue;

		vc->Mail();

		ObjectPvs pvs;
		mViewCellsTree->GetPvs(vc, pvs);

		char s[64]; sprintf(s, "%sviewcell%04d.wrl", prefix.c_str(), i);
		Exporter *exporter = Exporter::GetExporter(s);
		
		const float pvsCost = mViewCellsTree->GetTrianglesInPvs(vc);
		cout << "view cell " << vc->GetId() << ": pvs cost=" << pvsCost << endl;

		if (exportRays)
		{
			////////////
			//-- export rays piercing this view cell

			// take rays stored with the view cells during subdivision
			VssRayContainer vcRays;
            VssRayContainer collectRays;

			// collect initial view cells
			ViewCellContainer leaves;
			mViewCellsTree->CollectLeaves(vc, leaves);

			ViewCellContainer::const_iterator vit, vit_end = leaves.end();
       		for (vit = leaves.begin(); vit != vit_end; ++ vit)
			{	
				BspLeaf *vcLeaf = static_cast<BspViewCell *>(*vit)->mLeaves[0];
				VssRayContainer::const_iterator rit, rit_end = vcLeaf->mVssRays.end();

				for (rit = vcLeaf->mVssRays.begin(); rit != rit_end; ++ rit)
				{
					collectRays.push_back(*rit);
				}
			}

			const int raysOut = min((int)collectRays.size(), maxRays);
		
			// prepare some rays for visualization
			VssRayContainer::const_iterator rit, rit_end = collectRays.end();
			for (rit = collectRays.begin(); rit != rit_end; ++ rit)
			{
				const float p = RandomValue(0.0f, (float)collectRays.size());
			
				if (p < raysOut)
				{
					vcRays.push_back(*rit);
				}
			}

			exporter->ExportRays(vcRays, RgbColor(1, 1, 1));
		}
		
		////////////////
		//-- export view cell geometry

		exporter->SetWireframe();

		Material m;//= RandomMaterial();
		m.mDiffuseColor = RgbColor(0, 1, 0);
		exporter->SetForcedMaterial(m);

		ExportViewCellGeometry(exporter, vc, NULL, NULL);
		exporter->SetFilled();

		if (exportPvs)
		{
			Intersectable::NewMail();
			ObjectPvsIterator pit = pvs.GetIterator();

			cout << endl;

			// output PVS of view cell
			while (pit.HasMoreEntries())
			{
				Intersectable *intersect = pit.Next();		
				
				if (!intersect->Mailed())
				{
					intersect->Mail();

					m = RandomMaterial();
					exporter->SetForcedMaterial(m);
					exporter->ExportIntersectable(intersect);
				}
			}
			cout << endl;
		}
		
		DEL_PTR(exporter);
		cout << "finished" << endl;
	}
}


void VspBspViewCellsManager::TestFilter(const ObjectContainer &objects)
{
	Exporter *exporter = Exporter::GetExporter("filter.x3d");

	Vector3 bsize = mViewSpaceBox.Size();
	const Vector3 viewPoint(mViewSpaceBox.Center());
	float w = Magnitude(mViewSpaceBox.Size()) * mFilterWidth;
	const Vector3 width = Vector3(w);
	
	PrVs testPrVs;
	
	if (exporter)
	{
		ViewCellContainer viewCells;
	
        const AxisAlignedBox3 tbox = GetFilterBBox(viewPoint, mFilterWidth);

		GetPrVS(viewPoint, testPrVs, GetFilterWidth());

		exporter->SetWireframe();

		exporter->SetForcedMaterial(RgbColor(1,1,1));
		exporter->ExportBox(tbox);
		
		exporter->SetFilled();

		exporter->SetForcedMaterial(RgbColor(0,1,0));
		ExportViewCellGeometry(exporter, GetViewCell(viewPoint), NULL, NULL);

		//exporter->ResetForcedMaterial();
		exporter->SetForcedMaterial(RgbColor(0,0,1));
		ExportViewCellGeometry(exporter, testPrVs.mViewCell, NULL, NULL);

     	exporter->SetForcedMaterial(RgbColor(1,0,0));
		exporter->ExportGeometry(objects);

		delete exporter;
	}
}


int VspBspViewCellsManager::ComputeBoxIntersections(const AxisAlignedBox3 &box, 
													ViewCellContainer &viewCells) const
{
	return mVspBspTree->ComputeBoxIntersections(box, viewCells);
}


int VspBspViewCellsManager::CastLineSegment(const Vector3 &origin,
											const Vector3 &termination,
											ViewCellContainer &viewcells)
{
	return mVspBspTree->CastLineSegment(origin, termination, viewcells);
}


bool VspBspViewCellsManager::LineSegmentIntersects(const Vector3 &origin, 
												   const Vector3 &termination, 
												   ViewCell *viewCell)
{
	return false;
}


void VspBspViewCellsManager::VisualizeWithFromPointQueries()
{
	int numSamples;
	
	Environment::GetSingleton()->GetIntValue("RenderSampler.samples", numSamples);
	cout << "samples" << numSamples << endl;

	vector<RenderCostSample> samples;
  
	if (!mPreprocessor->GetRenderer())
		return;

	//start the view point queries
	long startTime = GetTime();
	cout << "starting sampling of render cost ... ";
	
	mPreprocessor->GetRenderer()->SampleRenderCost(numSamples, samples, true);

	cout << "finished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;


	// for each sample:
	//    find view cells associated with the samples
	//    store the sample pvs with the pvs associated with the view cell
	//
	// for each view cell:
	//    compute difference point sampled pvs - view cell pvs
	//    export geometry with color coded pvs difference
	
    std::map<ViewCell *, ObjectPvs> sampleMap;

	vector<RenderCostSample>::const_iterator rit, rit_end = samples.end();

	for (rit = samples.begin(); rit != rit_end; ++ rit)
	{
		RenderCostSample sample = *rit;
	
		ViewCell *vc = GetViewCell(sample.mPosition);

		std::map<ViewCell *, ObjectPvs>::iterator it = sampleMap.find(vc);

		if (it == sampleMap.end())
		{
			sampleMap[vc] = sample.mPvs;
		}
		else
		{
			(*it).second.MergeInPlace(sample.mPvs);
		}
	}

	// visualize the view cells
	std::map<ViewCell *, ObjectPvs>::const_iterator vit, vit_end = sampleMap.end();

	Material m;//= RandomMaterial();

	for (vit = sampleMap.begin(); vit != vit_end; ++ vit)
	{
		ViewCell *vc = (*vit).first;
		
		const int pvsVc = mViewCellsTree->GetPvsEntries(vc);
		const int pvsPtSamples = (*vit).second.GetSize();

        m.mDiffuseColor.r = (float) (pvsVc - pvsPtSamples);
		m.mDiffuseColor.b = 1.0f;
		//exporter->SetForcedMaterial(m);
		//ExportViewCellGeometry(exporter, vc, mClipPlaneForViz);

		/*	// counting the pvss
		for (rit = samples.begin(); rit != rit_end; ++ rit)
		{
			RenderCostSample sample = *rit;
			ViewCell *vc = GetViewCell(sample.mPosition);

			AxisAlignedBox3 box(sample.mPosition - Vector3(1, 1, 1), sample.mPosition + Vector3(1, 1, 1));
			Mesh *hMesh = CreateMeshFromBox(box);

			DEL_PTR(hMesh);
		}
		*/
	}
}


void VspBspViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
													ViewCell *vc,
													const AxisAlignedBox3 *sceneBox,
													const AxisAlignedPlane *clipPlane
													) const
{
	if (clipPlane)
	{
		const Plane3 plane = clipPlane->GetPlane();

		ViewCellContainer leaves;
		mViewCellsTree->CollectLeaves(vc, leaves);
		ViewCellContainer::const_iterator it, it_end = leaves.end();

		for (it = leaves.begin(); it != it_end; ++ it)
		{
			BspNodeGeometry geom;
			BspNodeGeometry front;
			BspNodeGeometry back;

			mVspBspTree->ConstructGeometry(*it, geom);

			const float eps = 0.0001f;
			const int cf = geom.Side(plane, eps);

			if (cf == -1)
			{
				exporter->ExportPolygons(geom.GetPolys());
			}
			else if (cf == 0)
			{
				geom.SplitGeometry(front,
								   back,
								   plane,
								   mViewSpaceBox, 
								   eps);

				if (back.Valid())
				{
					exporter->ExportPolygons(back.GetPolys());
				}			
			}
		}
	}
	else
	{
		// export mesh if available
		// TODO: some bug here?
		if (1 && vc->GetMesh())
		{
			exporter->ExportMesh(vc->GetMesh());
		}
		else
		{
			BspNodeGeometry geom;
			mVspBspTree->ConstructGeometry(vc, geom);
			exporter->ExportPolygons(geom.GetPolys());
		}
	}
}


int VspBspViewCellsManager::GetMaxTreeDiff(ViewCell *vc) const
{
	ViewCellContainer leaves;
	mViewCellsTree->CollectLeaves(vc, leaves);

	int maxDist = 0;
	
	// compute max height difference
	for (int i = 0; i < (int)leaves.size(); ++ i)
	{
		for (int j = 0; j < (int)leaves.size(); ++ j)
		{
			BspLeaf *leaf = static_cast<BspViewCell *>(leaves[i])->mLeaves[0];

			if (i != j)
			{
				BspLeaf *leaf2 =static_cast<BspViewCell *>(leaves[j])->mLeaves[0];
				const int dist = mVspBspTree->TreeDistance(leaf, leaf2);
				
				if (dist > maxDist)
					maxDist = dist;
			}
		}
	}

	return maxDist;
}


ViewCell *VspBspViewCellsManager::GetViewCell(const Vector3 &point, const bool active) const
{
	if (!ViewCellsConstructed())
		return NULL;

	if (!mViewSpaceBox.IsInside(point))
	  return NULL;

	return mVspBspTree->GetViewCell(point, active);
}


void VspBspViewCellsManager::CreateMesh(ViewCell *vc)
{
	BspNodeGeometry geom;
	mVspBspTree->ConstructGeometry(vc, geom);
	
	Mesh *mesh = MeshManager::GetSingleton()->CreateResource();
	
	IncludeNodeGeomInMesh(geom, *mesh);
	mesh->ComputeBoundingBox();

	vc->SetMesh(mesh);
}


int VspBspViewCellsManager::CastBeam(Beam &beam)
{
	return mVspBspTree->CastBeam(beam);
}


void VspBspViewCellsManager::Finalize(ViewCell *viewCell, 
									  const bool createMesh)
{
	float area = 0;
	float volume = 0;

	ViewCellContainer leaves;
	mViewCellsTree->CollectLeaves(viewCell, leaves);

	ViewCellContainer::const_iterator it, it_end = leaves.end();

    for (it = leaves.begin(); it != it_end; ++ it)
	{
		BspNodeGeometry geom;
		mVspBspTree->ConstructGeometry(*it, geom);

		const float lVol = geom.GetVolume();
		const float lArea = geom.GetArea();

		area += lArea;
		volume += lVol;

		if (createMesh)
			CreateMesh(*it);
	}

	viewCell->SetVolume(volume);
	viewCell->SetArea(area);
}


void VspBspViewCellsManager::TestSubdivision()
{
	ViewCellContainer leaves;
	mViewCellsTree->CollectLeaves(mViewCellsTree->GetRoot(), leaves);

	ViewCellContainer::const_iterator it, it_end = leaves.end();

	const float vol = mViewSpaceBox.GetVolume();
	float subdivVol = 0;
	float newVol = 0;

	for (it = leaves.begin(); it != it_end; ++ it)
	{
		BspNodeGeometry geom;
		mVspBspTree->ConstructGeometry(*it, geom);

		const float lVol = geom.GetVolume();
		
		newVol += lVol;
		subdivVol += (*it)->GetVolume();
		
		float thres = 0.9f;
		if ((lVol < ((*it)->GetVolume() * thres)) || (lVol * thres > ((*it)->GetVolume())))
			Debug << "warning: " << lVol << " " << (*it)->GetVolume() << endl;
	}
	
	Debug << "exact volume: " << vol << endl;
	Debug << "subdivision volume: " << subdivVol << endl;
	Debug << "new volume: " << newVol << endl;
}


void VspBspViewCellsManager::PrepareLoadedViewCells()
{
	// TODO: do I still need this here?
	if (0) mVspBspTree->RepairViewCellsLeafLists();
}



/************************************************************************/
/*                 VspOspViewCellsManager implementation                */
/************************************************************************/


VspOspViewCellsManager::VspOspViewCellsManager(ViewCellsTree *vcTree, 
											   const string &hierarchyType)
: ViewCellsManager(vcTree)
{
	Environment::GetSingleton()->GetIntValue("Hierarchy.Construction.samples", mInitialSamples);
	Environment::GetSingleton()->GetBoolValue("ViewCells.compressObjects", mCompressObjects);

	Debug << "compressing objects: " << mCompressObjects << endl;
	cout << "compressing objects: " << mCompressObjects << endl;

	mHierarchyManager = CreateHierarchyManager(hierarchyType);

	mHierarchyManager->SetViewCellsManager(this);
	mHierarchyManager->SetViewCellsTree(mViewCellsTree);
}


VspOspViewCellsManager::VspOspViewCellsManager(ViewCellsTree *vcTree, HierarchyManager *hm)
: ViewCellsManager(vcTree), mHierarchyManager(hm)
{
	Environment::GetSingleton()->GetIntValue("Hierarchy.Construction.samples", mInitialSamples);
	Environment::GetSingleton()->GetBoolValue("ViewCells.compressObjects", mCompressObjects);

	Debug << "compressing objects: " << mCompressObjects << endl;
	cout << "compressing objects: " << mCompressObjects << endl;

	mHierarchyManager->SetViewCellsManager(this);
	mHierarchyManager->SetViewCellsTree(mViewCellsTree);
}


Intersectable *VspOspViewCellsManager::GetIntersectable(const VssRay &ray, 
														const bool isTermination) const
{
	if (mUseKdPvs)
		return ViewCellsManager::GetIntersectable(ray, isTermination);
	else
		return mHierarchyManager->GetIntersectable(ray, isTermination);
}


HierarchyManager *VspOspViewCellsManager::CreateHierarchyManager(const string &hierarchyType)
{
	HierarchyManager *hierarchyManager;

	if (strcmp(hierarchyType.c_str(), "osp") == 0)
	{
		Debug << "hierarchy manager: osp" << endl;
		hierarchyManager = new HierarchyManager(HierarchyManager::KD_BASED_OBJ_SUBDIV);
	}
	else if (strcmp(hierarchyType.c_str(), "bvh") == 0)
	{
		Debug << "hierarchy manager: bvh" << endl;
		hierarchyManager = new HierarchyManager(HierarchyManager::BV_BASED_OBJ_SUBDIV);
	}
	else // only view space partition
	{
		Debug << "hierarchy manager: obj" << endl;
		hierarchyManager = new HierarchyManager(HierarchyManager::NO_OBJ_SUBDIV);
	}

	return hierarchyManager;
}


VspOspViewCellsManager::~VspOspViewCellsManager()
{
	DEL_PTR(mHierarchyManager);
}


float VspOspViewCellsManager::GetProbability(ViewCell *viewCell)
{
	return GetVolume(viewCell) / mViewSpaceBox.GetVolume();
}


void VspOspViewCellsManager::CollectViewCells()
{
	// view cells tree constructed
	if (!ViewCellsTreeConstructed())
	{
		mHierarchyManager->GetVspTree()->CollectViewCells(mViewCells, false);
	}
	else 
	{	// we can use the view cells tree hierarchy to get the right set
		mViewCellsTree->CollectBestViewCellSet(mViewCells, mNumActiveViewCells);
	}
}


bool VspOspViewCellsManager::ViewCellsConstructed() const
{
	return mHierarchyManager->GetVspTree()->GetRoot() != NULL;
}


ViewCell *VspOspViewCellsManager::GenerateViewCell(Mesh *mesh) const
{
	return new VspViewCell(mesh);
}


int VspOspViewCellsManager::ConstructSubdivision(const ObjectContainer &objects,
												 const VssRayContainer &rays)
{
	mMaxPvsSize = (int)(mMaxPvsRatio * (float)objects.size());

	// skip rest if view cells were already constructed
	if (ViewCellsConstructed())
		return 0;

	int sampleContributions = 0;
	VssRayContainer sampleRays;

	int limit = min (mInitialSamples, (int)rays.size());

	VssRayContainer constructionRays;
	VssRayContainer savedRays;

	Debug << "samples used for vsp bsp subdivision: " << mInitialSamples 
		  << ", actual rays: " << (int)rays.size() << endl;

	GetRaySets(rays, mInitialSamples, constructionRays, &savedRays);

	Debug << "initial rays used for construction: " << (int)constructionRays.size() << endl;
	Debug << "saved rays: " << (int)savedRays.size() << endl;

	mHierarchyManager->Construct(constructionRays, objects, &mViewSpaceBox);

#if TEST_EVALUATION
	VssRayContainer::const_iterator tit, tit_end = constructionRays.end();
	for (tit = constructionRays.begin(); tit != tit_end; ++ tit)
	{
		storedRays.push_back(new VssRay(*(*tit)));
	}
#endif

	/////////////////////////
	//-- print satistics for subdivision and view cells

	Debug << endl << endl << *mHierarchyManager << endl;

	ResetViewCells();
	//Debug << "\nView cells after construction:\n" << mCurrentViewCellsStats << endl;

	//////////////
	//-- recast rest of rays
	
	const long startTime = GetTime();
	cout << "Computing remaining ray contributions ... ";

	if (SAMPLE_AFTER_SUBDIVISION)
		ComputeSampleContributions(savedRays, true, false);

	Debug << "finished computing remaining ray contribution in " << TimeDiff(startTime, GetTime()) * 1e-3
		  << " secs" << endl;

	if (0)
	{	
		// real meshes are constructed at this stage
		cout << "finalizing view cells ... ";
        FinalizeViewCells(true);
		cout << "finished" << endl;
	}

	return sampleContributions;
}


int VspOspViewCellsManager::PostProcess(const ObjectContainer &objects,
										const VssRayContainer &rays)
{
	if (!ViewCellsConstructed())
	{
		Debug << "post process error: no view cells constructed" << endl;
		return 0;
	}

	// if view cells were already constructed before post processing step 
	// (e.g., because they were loaded), we are finished
	if (mViewCellsFinished)
	{
		FinalizeViewCells(true);
		EvaluateViewCellsStats();

		return 0;
	}

	// check if new view cells turned invalid
	int minPvs, maxPvs;

	if (0)
	{
		minPvs = mMinPvsSize;
		maxPvs = mMaxPvsSize;
	}
	else
	{
		// problem matt: why did I start here from zero?
		minPvs = 0;
		maxPvs = mMaxPvsSize;
	}

	Debug << "setting validity, min: " << minPvs << " max: " << maxPvs << endl;
	cout << "setting validity, min: " << minPvs << " max: " << maxPvs << endl;
	
	SetValidity(minPvs, maxPvs); 

	
	// area is not up to date, has to be recomputed
	mTotalAreaValid = false;
	VssRayContainer postProcessRays;
	GetRaySets(rays, mPostProcessSamples, postProcessRays);

	Debug << "post processing using " << (int)postProcessRays.size() << " samples" << endl;


	// compute tree by merging the nodes of the spatial hierarchy
	ViewCell *root = ConstructSpatialMergeTree(mHierarchyManager->GetVspTree()->GetRoot());
	mViewCellsTree->SetRoot(root);

	//////////////////////////
	//-- update pvs up to the root of the hierarchy

	ObjectPvs pvs;
	UpdatePvsForEvaluation(root, pvs);


	//////////////////////
	//-- render simulation after merge + refine

	cout << "\nview cells partition render time before compress" << endl << endl;
	static_cast<RenderSimulator *>(mRenderer)->RenderScene();
	SimulationStatistics ss;
	static_cast<RenderSimulator *>(mRenderer)->GetStatistics(ss);
	cout << ss << endl;
	

	mHierarchyManager->CreateUniqueObjectIds();

	///////////
	//-- compression

	if (0) CompressViewCells();

	/////////////
	//-- some tasks still to do on the view cells:
	//-- Compute meshes from view cell geometry, evaluate volume and / or area

	if (1) FinalizeViewCells(true);

	return 0;
}


int VspOspViewCellsManager::GetType() const
{
	return VSP_OSP;
}


ViewCell *VspOspViewCellsManager::ConstructSpatialMergeTree(VspNode *root)
{
	// terminate recursion
	if (root->IsLeaf())
	{
		VspLeaf *leaf = static_cast<VspLeaf *>(root);
		leaf->GetViewCell()->SetMergeCost(0.0f);
		return leaf->GetViewCell();
	}
	
	VspInterior *interior = static_cast<VspInterior *>(root);
	ViewCellInterior *viewCellInterior = new ViewCellInterior();
		
	// evaluate merge cost for priority traversal
	const float mergeCost = -(float)root->mTimeStamp;
	viewCellInterior->SetMergeCost(mergeCost);

	float volume = 0;
	
	VspNode *front = interior->GetFront();
	VspNode *back = interior->GetBack();

	ObjectPvs frontPvs, backPvs;

	/////////
	//-- recursivly compute child hierarchies

	ViewCell *backVc = ConstructSpatialMergeTree(back);
	ViewCell *frontVc = ConstructSpatialMergeTree(front);

	viewCellInterior->SetupChildLink(backVc);
	viewCellInterior->SetupChildLink(frontVc);

	volume += backVc->GetVolume();
	volume += frontVc->GetVolume();	

	viewCellInterior->SetVolume(volume);

	return viewCellInterior;
}


bool VspOspViewCellsManager::GetViewPoint(Vector3 &viewPoint) const
{
	if (!ViewCellsConstructed())
		return ViewCellsManager::GetViewPoint(viewPoint);

	// TODO: set reasonable limit
	const int limit = 20;

	for (int i = 0; i < limit; ++ i)
	{
		viewPoint = mViewSpaceBox.GetRandomPoint();

		if (mHierarchyManager->GetVspTree()->ViewPointValid(viewPoint))
		{
			return true;
		}
	}

	Debug << "failed to find valid view point, taking " << viewPoint << endl;
	return false;
}


void VspOspViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
													ViewCell *vc,
													const AxisAlignedBox3 *sceneBox,
													const AxisAlignedPlane *clipPlane
													) const
{
	Plane3 plane;
	if (clipPlane)
	{
		// arbitrary plane definition
		plane = clipPlane->GetPlane();
	}

	ViewCellContainer leaves;
	mViewCellsTree->CollectLeaves(vc, leaves);

	ViewCellContainer::const_iterator it, it_end = leaves.end();

	for (it = leaves.begin(); it != it_end; ++ it)
	{
		VspViewCell *vspVc = static_cast<VspViewCell *>(*it);
		VspLeaf *l = vspVc->mLeaves[0];

		const AxisAlignedBox3 box = 
			mHierarchyManager->GetVspTree()->GetBoundingBox(vspVc->mLeaves[0]);
		
		if (sceneBox && !Overlap(*sceneBox, box))
			continue;

		if (clipPlane)
		{
			if (box.Side(plane) == -1)
			{
				exporter->ExportBox(box);
			}
			else if (box.Side(plane) == 0)
			{
				// intersection
				AxisAlignedBox3 fbox, bbox;
				box.Split(clipPlane->mAxis, clipPlane->mPosition, fbox, bbox);
				exporter->ExportBox(bbox);
			}
		}
		else
		{
			exporter->ExportBox(box);
		}
	}
}


bool VspOspViewCellsManager::ViewPointValid(const Vector3 &viewPoint) const
{
  // $$JB -> implemented in viewcellsmanager (slower, but allows dynamic
  // validy update in preprocessor for all managers)
  return ViewCellsManager::ViewPointValid(viewPoint);

  //	return mViewSpaceBox.IsInside(viewPoint) &&
  //		   mVspTree->ViewPointValid(viewPoint);
}


float VspOspViewCellsManager::UpdateObjectCosts()
{
	float maxRenderCost = 0;

	cout << "updating object pvs cost ... ";
	const long startTime = GetTime();

	ViewCellContainer::const_iterator vit, vit_end = mViewCells.end();

	Intersectable::NewMail();

	const float invViewSpaceVol = 1.0f / GetViewSpaceBox().GetVolume();

	for (vit = mViewCells.begin(); vit != vit_end; ++ vit)
	{
		ViewCell *vc = *vit;

		ObjectPvsIterator pit = vc->GetPvs().GetIterator();

		// output PVS of view cell
		while (pit.HasMoreEntries())
		{		
			Intersectable *obj = pit.Next();
				
			BvhNode *node = static_cast<BvhNode *>(obj);
			
			// hack!!
			if (!node->IsLeaf())
			{
				cout << "error, can only process leaves" << endl;
				return 0;
			}
	
			if (!node->Mailed())
			{
				node->Mail();
				node->mRenderCost = 0;
			}

			const float rc = (float)((BvhLeaf *)node)->mObjects.size();

			node->mRenderCost += rc * vc->GetVolume() * invViewSpaceVol;

			if (node->mRenderCost > maxRenderCost)
				maxRenderCost = node->mRenderCost;
		}
	}

	cout << "finished in " << TimeDiff(startTime, GetTime()) * 1e-3f << " secs" << endl;

	return maxRenderCost;
}


void VspOspViewCellsManager::Visualize(const ObjectContainer &objects,
									   const VssRayContainer &sampleRays)
{
	if (!ViewCellsConstructed())
		return;

	VssRayContainer visRays;
	GetRaySets(sampleRays, mVisualizationSamples, visRays);

	////////////
	//-- export final view cells

	Exporter *exporter = Exporter::GetExporter("final_view_cells.wrl");

	Vector3 scale(0.9f, 0.9f, 0.9f);
	//Vector3 scale(1.0f, 1.0f, 1.0f);

	if (exporter)
	{
		// clamp to a scene boudning box
		if (CLAMP_TO_BOX)
			exporter->mClampToBox = true; 	
		
		const long starttime = GetTime();
		cout << "exporting final view cells (after initial construction + post process) ... " << endl;

		// matt: hack for clamping scene
		AxisAlignedBox3 bbox = mViewSpaceBox;
		bbox.Scale(scale);

		if (1 && mExportRays)
		{	
			exporter->ExportRays(visRays, RgbColor(0, 1, 0));
		}

		// hack color code
		const int savedColorCode = mColorCode;

		EvaluateViewCellsStats();
		const int colorCode = 0;

		const float maxRenderCost = -1;//UpdateObjectCosts();
		const bool exportBounds = false;

		//cout << "maxRenderCost: " << maxRenderCost << endl;
		if (1)
		mHierarchyManager->ExportObjectSpaceHierarchy(exporter, 
													  objects, 
													  CLAMP_TO_BOX ? &bbox : NULL, 
													  maxRenderCost, 
													  exportBounds);
		
		//ExportViewCellsForViz(exporter, CLAMP_TO_BOX ? &bbox : NULL, mColorCode, GetClipPlane());
		ExportViewCellsForViz(exporter, NULL, colorCode, GetClipPlane());
		
		delete exporter;

		cout << "finished in " << TimeDiff(starttime, GetTime()) * 1e-3f << " secs" << endl;
	}

	if (1)
	{
		exporter = Exporter::GetExporter("final_object_partition.wrl");

		if (exporter)
		{
			if (CLAMP_TO_BOX)
			{	
				exporter->mClampToBox = true; 	
			}

			const long starttime = GetTime();
			cout << "exporting final objects (after initial construction + post process) ... ";

			// matt: hack for clamping scene
			AxisAlignedBox3 bbox = mViewSpaceBox;
			bbox.Scale(scale);

			// hack color code (show pvs size)
			const int savedColorCode = mColorCode;

			EvaluateViewCellsStats();
			mColorCode = 1; // 0 = random, 1 = export pvs

			// don't visualize render cost
			const float maxRenderCost = -1;
			//const bool exportBounds = true;
			const bool exportBounds = false;

			mHierarchyManager->ExportObjectSpaceHierarchy(exporter, 
			                                              objects, 
														  CLAMP_TO_BOX ? &bbox : NULL, 
														  maxRenderCost, 
														  exportBounds);


			delete exporter;

			cout << "finished in " << TimeDiff(starttime, GetTime()) * 1e-3f << " secs" << endl;
			mColorCode = savedColorCode;
		}
	}

	// export some view cells
	int leafOut;
	Environment::GetSingleton()->GetIntValue("ViewCells.Visualization.maxOutput", leafOut);

	const bool sortViewCells = false;
	const bool exportPvs = true;
	const bool exportRays = true;
	const int raysOut = 100;

	ExportSingleViewCells(objects, 
						  leafOut, 
						  sortViewCells, 
						  exportPvs, 
						  exportRays, 
						  raysOut, 
						  "");
}


void VspOspViewCellsManager::ExportSingleViewCells(const ObjectContainer &objects,
												   const int maxViewCells,
												   const bool sortViewCells,
												   const bool exportPvs,
												   const bool exportRays,
												   const int maxRays,
												   const string &prefix,
												   VssRayContainer *visRays)
{
	if (sortViewCells)
	{
		// sort view cells to visualize the view cells with highest render cost
		sort(mViewCells.begin(), mViewCells.end(), LargerRenderCost);
	}

	ViewCell::NewMail();
	const int limit = min(maxViewCells, (int)mViewCells.size());
	
	cout << "\nExporting " << limit << " single view cells: " << endl;
	
	for (int i = 0; i < limit; ++ i)
	{
		cout << "creating output for view cell " << i << " ... ";
		
		// largest view cell pvs first of random view cell
		ViewCell *vc = sortViewCells ? 
			mViewCells[i] : mViewCells[(int)RandomValue(0, (float)mViewCells.size() - 1)];
		
		if (vc->Mailed()) // view cell already processed
			continue;

		vc->Mail();

		ObjectPvs pvs;
		mViewCellsTree->GetPvs(vc, pvs);

		char s[64]; sprintf(s, "%sviewcell%04d.wrl", prefix.c_str(), i);
		Exporter *exporter = Exporter::GetExporter(s);
		
		cout << "view cell " << vc->GetId() << ": pvs cost=" << mViewCellsTree->GetTrianglesInPvs(vc) << endl;

		if (exportPvs)
		{
			Material m;
			Intersectable::NewMail();
			
			ObjectPvsIterator pit = pvs.GetIterator();

			// output PVS of view cell
			while (pit.HasMoreEntries())
			{		
				Intersectable *intersect = pit.Next();
				
				if (!intersect->Mailed())
				{
					m = RandomMaterial();
					exporter->SetForcedMaterial(m);

					exporter->ExportIntersectable(intersect);
					intersect->Mail();
				}
			}
		}

		if (exportRays)
		{
			////////////
			//-- export the sample rays

			// output rays stored with the view cells during subdivision
			VssRayContainer vcRays;
			VssRayContainer collectRays;

			// collect intial view cells
			ViewCellContainer leaves;
			mViewCellsTree->CollectLeaves(vc, leaves);

			ViewCellContainer::const_iterator vit, vit_end = leaves.end();

			for (vit = leaves.begin(); vit != vit_end; ++ vit)
			{
				VspLeaf *vcLeaf = static_cast<VspViewCell *>(*vit)->mLeaves[0];
				VssRayContainer::const_iterator rit, rit_end = vcLeaf->mVssRays.end();

				for (rit = vcLeaf->mVssRays.begin(); rit != rit_end; ++ rit)
				{
					collectRays.push_back(*rit);
				}
			}

			const int raysOut = min((int)collectRays.size(), maxRays);

			VssRayContainer::const_iterator rit, rit_end = collectRays.end();

			for (rit = collectRays.begin(); rit != rit_end; ++ rit)
			{
				const float p = RandomValue(0.0f, (float)collectRays.size());

				if (p < raysOut)
					vcRays.push_back(*rit);
			}

			exporter->ExportRays(vcRays, RgbColor(1, 1, 1));
		}
		
	
		/////////////////
		//-- export view cell geometry

		exporter->SetWireframe();

		Material m;
		m.mDiffuseColor = RgbColor(0, 1, 0);
		exporter->SetForcedMaterial(m);

		ExportViewCellGeometry(exporter, vc, NULL, NULL);
		exporter->SetFilled();

		DEL_PTR(exporter);
		cout << "finished" << endl;
	}

	cout << endl;
}


int VspOspViewCellsManager::ComputeBoxIntersections(const AxisAlignedBox3 &box, 
													ViewCellContainer &viewCells) const
{
	return mHierarchyManager->GetVspTree()->ComputeBoxIntersections(box, viewCells);
}


int VspOspViewCellsManager::CastLineSegment(const Vector3 &origin,
											const Vector3 &termination,
											ViewCellContainer &viewcells)
{
	return mHierarchyManager->CastLineSegment(origin, termination, viewcells);
}


bool VspOspViewCellsManager::LineSegmentIntersects(const Vector3 &origin, 
												   const Vector3 &termination, 
												   ViewCell *viewCell)
{
	return false;
}


bool VspOspViewCellsManager::ExportViewCells(const string filename, 
											 const bool exportPvs, 
											 const ObjectContainer &objects)
{
	// no view cells were computed
	if (!ViewCellsConstructed() || !ViewCellsTreeConstructed())
		return false;

	if (strstr(filename.c_str(), ".bn"))
	{
		return ExportViewCellsBinary(filename, exportPvs, objects);
	}

	//cout << "exporting binary" << endl; string fname("test.vc"); return ExportViewCellsBinary(fname, exportPvs, objects);

	const long starttime = GetTime();
	cout << "exporting view cells to xml ... ";
	
	OUT_STREAM stream(filename.c_str());

	// we need unique ids for each view cell
	CreateUniqueViewCellIds();

	stream << "<?xml version=\"1.0\" encoding=\"UTF-8\"?>"<<endl;
	stream << "<VisibilitySolution>" << endl;

	if (exportPvs) 
	{
        ///////////////
		//-- export bounding boxes
		//-- we need the boxes to identify objects in the target engine

		if (mUseKdPvs)
		{
			stream << "<BoundingBoxes>" << endl;

			int id = 0;
			vector<KdIntersectable *>::const_iterator kit, kit_end = mPreprocessor->mKdTree->mKdIntersectables.end();
			
			for (kit = mPreprocessor->mKdTree->mKdIntersectables.begin(); kit != kit_end; ++ kit, ++ id)
			{
				Intersectable *obj = (*kit);
				const AxisAlignedBox3 box = obj->GetBox();

				// set kd node id
				obj->SetId(id);

				stream << "<BoundingBox" << " id=\"" << id << "\""
					   << " min=\"" << box.Min().x << " " << box.Min().y << " " << box.Min().z << "\""
				       << " max=\"" << box.Max().x << " " << box.Max().y << " " << box.Max().z << "\" />" << endl;
			}

			stream << "</BoundingBoxes>" << endl;
		}
		else
		{
			mHierarchyManager->ExportBoundingBoxes(stream, objects);
		}
	}


	//////////////////////////
	//-- export the view cells and the pvs

	const int numViewCells = mCurrentViewCellsStats.viewCells;

	stream << "<ViewCells number=\"" << numViewCells << "\" >" << endl;
	mViewCellsTree->Export(stream, exportPvs);
	stream << "</ViewCells>" << endl;


	/////////////////
	//-- export the view space hierarchy
	
	stream << "<ViewSpaceHierarchy type=\"vsp\""
		   << " min=\"" << mViewSpaceBox.Min().x << " " << mViewSpaceBox.Min().y << " " << mViewSpaceBox.Min().z << "\""
		   << " max=\"" << mViewSpaceBox.Max().x << " " << mViewSpaceBox.Max().y << " " << mViewSpaceBox.Max().z << "\">" << endl;

	mHierarchyManager->GetVspTree()->Export(stream);
	stream << "</ViewSpaceHierarchy>" << endl;

	/////////////////
	//-- export the object space hierarchy
	
	mHierarchyManager->ExportObjectSpaceHierarchy(stream);
	
	stream << "</VisibilitySolution>" << endl;
	stream.close();
	
	cout << "finished in " << TimeDiff(starttime, GetTime()) * 1e-3 << " secs" << endl;
	return true;
}


bool VspOspViewCellsManager::ExportViewCellsBinary(const string filename, 
												   const bool exportPvs, 
												   const ObjectContainer &objects)
{
	// no view cells constructed yet
	if (!ViewCellsConstructed() || !ViewCellsTreeConstructed())
		return false;

	const long starttime = GetTime();
	cout << "exporting view cells to binary format ... ";
	
	OUT_STREAM stream(filename.c_str());

	// we need unique ids for each view cell
	CreateUniqueViewCellIds();

	int numBoxes = mPreprocessor->mKdTree->mKdIntersectables.size();
	stream.write(reinterpret_cast<char *>(&numBoxes), sizeof(int));


    ///////////////
	//-- export bounding boxes

	// we use bounding box intersection to identify pvs objects in the target engine
	vector<KdIntersectable *>::const_iterator kit, kit_end = mPreprocessor->mKdTree->mKdIntersectables.end();

	int id = 0;

	for (kit = mPreprocessor->mKdTree->mKdIntersectables.begin(); kit != kit_end; ++ kit, ++ id)
	{
		Intersectable *obj = (*kit);
		// set the kd node id to identify the kd node as a pvs entry
		obj->SetId(id);

		const AxisAlignedBox3 &box = obj->GetBox();
		Vector3 bmin = box.Min();
		Vector3 bmax = box.Max();

		stream.write(reinterpret_cast<char *>(&bmin), sizeof(Vector3));
		stream.write(reinterpret_cast<char *>(&bmax), sizeof(Vector3));
		stream.write(reinterpret_cast<char *>(&id), sizeof(int));
	}

	cout << "written " << numBoxes << " kd nodes" << endl;

	///////////////
	//-- export the view cells and the pvs

	int numViewCells = mViewCells.size();
	stream.write(reinterpret_cast<char *>(&numViewCells), sizeof(int));

	Vector3 vmin = mViewSpaceBox.Min();
	Vector3 vmax = mViewSpaceBox.Max();

	stream.write(reinterpret_cast<char *>(&vmin), sizeof(Vector3));
	stream.write(reinterpret_cast<char *>(&vmax), sizeof(Vector3));


	//////////
	//-- export binary view cells

	mViewCellsTree->ExportBinary(stream);


	/////////
	//-- export the view space hierarchy
	
	mHierarchyManager->GetVspTree()->ExportBinary(stream);
	

	////////
	//-- export the object space hierarchy

	//mHierarchyManager->ExportObjectSpaceHierarchyBinary();
    
	stream.close();
	
	//mHierarchyManager->GetVspTree()->TestOutput("output.txt");

	cout << "finished in " << TimeDiff(starttime, GetTime()) * 1e-3 << " secs" << endl;
	return true;
}


ViewCell *VspOspViewCellsManager::GetViewCell(const Vector3 &point, 
											  const bool active) const
{
	if (!ViewCellsConstructed())
		return NULL;

	if (!mViewSpaceBox.IsInside(point))
		return NULL;

	return mHierarchyManager->GetVspTree()->GetViewCell(point, active);
}


void VspOspViewCellsManager::CreateMesh(ViewCell *vc)
{
	Mesh *mesh = MeshManager::GetSingleton()->CreateResource();
	
	ViewCellContainer leaves;
	mViewCellsTree->CollectLeaves(vc, leaves);

	ViewCellContainer::const_iterator it, it_end = leaves.end();

    for (it = leaves.begin(); it != it_end; ++ it)
	{
		VspLeaf *leaf = static_cast<VspViewCell *>(*it)->mLeaves[0];
		const AxisAlignedBox3 box = mHierarchyManager->GetVspTree()->GetBoundingBox(leaf);
        IncludeBoxInMesh(box, *mesh);
	}

	mesh->ComputeBoundingBox();

	vc->SetMesh(mesh);
}


int VspOspViewCellsManager::CastBeam(Beam &beam)
{
	// matt: TODO
	return 0;
}


void VspOspViewCellsManager::Finalize(ViewCell *viewCell, const bool createMesh)
{
	float area = 0;
	float volume = 0;

	ViewCellContainer leaves;
	mViewCellsTree->CollectLeaves(viewCell, leaves);

	ViewCellContainer::const_iterator it, it_end = leaves.end();

    for (it = leaves.begin(); it != it_end; ++ it)
	{
		VspLeaf *leaf = static_cast<VspViewCell *>(*it)->mLeaves[0];
		
		const AxisAlignedBox3 box = mHierarchyManager->GetVspTree()->GetBoundingBox(leaf);

		const float lVol = box.GetVolume();
		const float lArea = box.SurfaceArea();

		area += lArea;
		volume += lVol;

        CreateMesh(*it);
	}

	viewCell->SetVolume(volume);
	viewCell->SetArea(area);
}


void VspOspViewCellsManager::PrepareLoadedViewCells()
{
	// TODO
}


void VspOspViewCellsManager::PrintCompressionStats(HierarchyManager *hm, const int pvsEntries)
{
	const float mem = (float)pvsEntries * ObjectPvs::GetEntrySize();
		
	float fullmem = mem + 
			(hm->GetVspTree()->GetStatistics().Leaves() * 16 + 
			 hm->mBvHierarchy->GetStatistics().Leaves() * 16) / float(1024 * 1024);

	cout << "entries: " << pvsEntries << ", mem=" << mem << ", fullmem=" << fullmem <<endl;
	Debug << "entries: " << pvsEntries << ", mem=" << mem << ", fullmem=" << fullmem <<endl;
}


void VspOspViewCellsManager::CompressViewCells()
{
	if (!(ViewCellsTreeConstructed() && mCompressViewCells))
		return;


	////////////
	//-- compression

	int pvsEntries = mViewCellsTree->CountStoredPvsEntries(mViewCellsTree->GetRoot());

	cout << "before compression: " << endl;
	Debug << "before compression: " << endl;
	
	PrintCompressionStats(mHierarchyManager, pvsEntries);

	if (mCompressObjects)
	{
		cout << "compressing in the objects: " << endl;
		Debug << "compressing in the objects: " << endl;

		pvsEntries = mHierarchyManager->CompressObjectSpace();
	}
	else
	{
		cout << "compressing in the view space: " << endl;
		Debug << "compressing in the view space: " << endl;

		mViewCellsTree->SetViewCellsStorage(ViewCellsTree::COMPRESSED);
		pvsEntries = mViewCellsTree->CountStoredPvsEntries(mViewCellsTree->GetRoot());
	}

	PrintCompressionStats(mHierarchyManager, pvsEntries);
}


void VspOspViewCellsManager::CollectObjects(const AxisAlignedBox3 &box, 
											ObjectContainer &objects)
{
	mHierarchyManager->CollectObjects(box, objects);
}


void VspOspViewCellsManager::EvalViewCellPartition()
{
	int samplesPerPass;
	int castSamples = 0;
	int oldSamples = 0;
	int samplesForStats;
	char statsPrefix[100];
	char suffix[100];
	int splitsStepSize;

	Environment::GetSingleton()->GetIntValue("ViewCells.Evaluation.samplesPerPass", samplesPerPass);
	Environment::GetSingleton()->GetIntValue("ViewCells.Evaluation.samplesForStats", samplesForStats);
	Environment::GetSingleton()->GetIntValue("ViewCells.Evaluation.samples", mEvaluationSamples);
	Environment::GetSingleton()->GetStringValue("ViewCells.Evaluation.statsPrefix", statsPrefix);
	Environment::GetSingleton()->GetIntValue("ViewCells.Evaluation.stepSize", splitsStepSize);
	
	bool useHisto;
	int histoMem;

	Environment::GetSingleton()->GetBoolValue("ViewCells.Evaluation.histogram", useHisto);
	Environment::GetSingleton()->GetIntValue("ViewCells.Evaluation.histoMem", histoMem);

	Debug << "step size: " << splitsStepSize << endl;
	Debug << "view cell evaluation samples per pass: " << samplesPerPass << endl;
	Debug << "view cell evaluation samples: " << mEvaluationSamples << endl;
	Debug << "view cell stats prefix: " << statsPrefix << endl;

    cout << "reseting pvs ... ";
		
	// reset pvs and start over from zero
	mViewCellsTree->ResetPvs();
	
	cout << "finished" << endl;
    cout << "Evaluating view cell partition ... " << endl;

	int pass = 0;

	while (castSamples < mEvaluationSamples)
	{		
		///////////////
		//-- we have to use uniform sampling strategy for construction rays

		VssRayContainer evaluationSamples;
		const int samplingType = mEvaluationSamplingType;

		long startTime = GetTime();
		Real timeDiff;

		cout << "casting " << samplesPerPass << " samples ... ";
		Debug << "casting " << samplesPerPass << " samples ... ";
	
		// use mixed distributions
		CastEvaluationSamples(samplesPerPass, evaluationSamples);

		timeDiff = TimeDiff(startTime, GetTime());
		cout << "finished in " << timeDiff * 1e-3f << " secs" << endl;
		Debug << "finished in " << timeDiff * 1e-3f << " secs" << endl;
		
		// don't computed sample contributions 
		// because already accounted for inside the mixture distribution!
		
		castSamples += samplesPerPass;

		if ((castSamples >= samplesForStats + oldSamples) || 
			(castSamples >= mEvaluationSamples))
		{
			oldSamples += samplesForStats;

			///////////
			//-- output stats

			sprintf(suffix, "-%09d-eval.log", castSamples);
			const string filename = string(statsPrefix) + string(suffix);

			startTime = GetTime();
			
			cout << "compute new statistics ... " << endl;

			ofstream ofstr(filename.c_str());
			mHierarchyManager->EvaluateSubdivision(ofstr, splitsStepSize, false, useHisto, histoMem, pass);

			timeDiff = TimeDiff(startTime, GetTime());
			cout << "finished in " << timeDiff * 1e-3 << " secs" << endl;
			cout << "*************************************" << endl;

			Debug << "statistics computed in " << timeDiff * 1e-3 << " secs" << endl;

			++ pass;
		}

		disposeRays(evaluationSamples, NULL);
	}

	////////////
	//-- histogram

	const int numLeaves = mViewCellsTree->GetNumInitialViewCells(mViewCellsTree->GetRoot());
	int histoStepSize;

	Environment::GetSingleton()->GetBoolValue("ViewCells.Evaluation.histogram", useHisto);
	Environment::GetSingleton()->GetIntValue("ViewCells.Evaluation.histoStepSize", histoStepSize);

	if (useHisto)
	{
		// evaluate view cells in a histogram		
		char str[64];

		// hack: just show final view cells
		const int pass = (int)mViewCells.size();

		//for (int pass = histoStepSize; pass <= numLeaves; pass += histoStepSize)

		string filename;

		cout << "computing histogram for " << pass << " view cells" << endl;

		///////////////////
		//-- evaluate histogram for pvs size

		cout << "computing pvs histogram for " << pass << " view cells" << endl;

		sprintf(str, "-%09d-histo-pvs2.log", pass);
		filename = string(statsPrefix) + string(str);

		EvalViewCellHistogramForPvsSize(filename, pass);
	}
}


void VspOspViewCellsManager::FinalizeViewCells(const bool createMesh)
{	
	ViewCellsManager::FinalizeViewCells(createMesh);

	if (mHierarchyManager->mUseTraversalTree)
	{	// create a traversal tree for optimal view cell casting
		mHierarchyManager->CreateTraversalTree();
	}
}


#if TEST_PACKETS

float VspOspViewCellsManager::ComputeSampleContributions(const VssRayContainer &rays,
														 const bool addContributions,
														 const bool storeViewCells,
														 const bool useHitObjects)
{
	if (!ViewCellsConstructed()) 
		return 0;
	
	float sum = 0.0f;
	VssRayContainer::const_iterator it, it_end = rays.end();

	VssRayContainer tmpRays;	

	for (it = rays.begin(); it != it_end; ++ it) 
	{
		sum += ComputeSampleContribution(*(*it), addContributions, storeViewCells, useHitObjects);

		tmpRays.push_back(new VssRay(*(*it)));
		
		if (tmpRays.size() == 4)
		{
			// cast packets of 4 rays
			RayPacket packet(tmpRays);
			mHierarchyManager->CastLineSegment(packet);
		
			for (int i = 0; i < 4; ++ i)
			{
				ComputeSampleContribution(*tmpRays[i], addContributions, true, useHitObjects);
				// compare results
				cout << "ray " << i << ": " << (int)tmpRays[i]->mViewCells.size() << " " 
					 << (int)packet.mViewCells[i].size() << endl;
			}
			
			CLEAR_CONTAINER(tmpRays);
		}
	}
	
	CLEAR_CONTAINER(tmpRays);

	cout << "view cell cast time: " << viewCellCastTimer.TotalTime() << " s" << endl;
	Debug << "view cell cast time: " << viewCellCastTimer.TotalTime() << " s" << endl;

	cout << "pvs time: " << pvsTimer.TotalTime() << " s" << endl;
	Debug << "pvs time: " << pvsTimer.TotalTime() << " s" << endl;
	
	return sum;
}

#endif


ViewCellsManager *ViewCellsManager::LoadViewCellsBinary(const string &filename, 
														ObjectContainer &pvsObjects,
														bool finalizeViewCells,
														BoundingBoxConverter *bconverter)												 
{
	IN_STREAM stream(filename.c_str());

	if (!stream.is_open())
	{
		Debug << "View cells loading failed: could not open file" << endl;
		return NULL;
	}

	Debug << "loading boxes" << endl;

	const long startTime = GetTime();

	// load all the bounding boxes
	IndexedBoundingBoxContainer iboxes;
	ViewCellsManager::LoadIndexedBoundingBoxesBinary(stream, iboxes);

	pvsObjects.reserve(iboxes.size());

	if (bconverter)
	{
		// associate object ids with bounding boxes
		bconverter->IdentifyObjects(iboxes, pvsObjects);
	}


	ObjectContainer pvsLookup;
	pvsLookup.resize(iboxes.size());

	for (size_t i = 0; i < pvsLookup.size(); ++ i)
	{
		pvsLookup[i] = NULL;
	}

	for (size_t i = 0; i < pvsObjects.size(); ++ i)
	{
		pvsLookup[pvsObjects[i]->GetId()] = pvsObjects[i];
	}


	/////////////
	//-- load the view cells
	
	int numViewCells;
	stream.read(reinterpret_cast<char *>(&numViewCells), sizeof(int));

	Debug << "loading " << numViewCells << " view cells " << endl;

	Vector3 vmin, vmax;

	stream.read(reinterpret_cast<char *>(&vmin), sizeof(Vector3));
	stream.read(reinterpret_cast<char *>(&vmax), sizeof(Vector3));

	AxisAlignedBox3 viewSpaceBox(vmin, vmax);

	Debug << "view space box: " << viewSpaceBox << endl;

    ViewCellsTree *vcTree = new ViewCellsTree();

	if (!vcTree->ImportBinary(stream, pvsLookup))
	{
		Debug << "Error: loading view cells tree failed!" << endl;
		delete vcTree;
	
		return NULL;
	}

	Debug << "loading the view space partition tree" << endl;
	VspTree *vspTree = new VspTree(viewSpaceBox);

	if (!vspTree->ImportBinary(stream))
	{
		Debug << "Error: loading vsp tree failed!" << endl;
		delete vcTree; delete vspTree;

		return NULL;
	}


	HierarchyManager * hm = 
		new HierarchyManager(HierarchyManager::BV_BASED_OBJ_SUBDIV);

	hm->SetVspTree(vspTree);


	/////////
	//-- create view cells manager
	
	VspOspViewCellsManager *vm = new VspOspViewCellsManager(vcTree, hm);


	//////////////
	//-- do some more preparation

	vm->mViewSpaceBox = viewSpaceBox;
	vm->mViewCells.clear();

	ViewCellContainer viewCells;
	vcTree->CollectLeaves(vcTree->GetRoot(), viewCells);

	ViewCellContainer::const_iterator cit, cit_end = viewCells.end();

	for (cit = viewCells.begin(); cit != cit_end; ++ cit)
	{
		vm->mViewCells.push_back(*cit);
	}


	//////////////
	//-- associate view cells with vsp leaves

	vector<VspLeaf *> vspLeaves;
	vspTree->CollectLeaves(vspLeaves);

	vector<VspLeaf *>::const_iterator vit, vit_end = vspLeaves.end();
	cit = viewCells.begin();

	for (vit = vspLeaves.begin(); vit != vit_end; ++ vit, ++ cit)
	{
		VspLeaf *leaf = *vit;
		VspViewCell *vc = static_cast<VspViewCell *>(*cit);

		leaf->SetViewCell(vc);
		vc->mLeaves.push_back(leaf);
	}

	
	/*for (cit = viewCells.begin(); cit != cit_end; ++ cit)
	{
		Debug << "pvssize: " << (*cit)->GetPvs().GetSize();
	}*/


	vm->mViewCellsFinished = true;
	vm->mMaxPvsSize = (int)pvsObjects.size();

	if (finalizeViewCells)
	{
		// create the meshes and compute view cell volumes
		const bool createMeshes = true;
		vm->FinalizeViewCells(createMeshes);
	}

	Debug << (int)vm->mViewCells.size() << " view cells loaded in "
		  << TimeDiff(startTime, GetTime()) * 1e-6f << " secs" << endl;

	//vspTree->TestOutput("input.txt");

	return vm;
}

}