#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 "VspKdTree.h"
#include "Exporter.h"
#include "VspBspTree.h"
#include "ViewCellsParser.h"
#include "Beam.h"
#include "VssPreprocessor.h"
#include "RssPreprocessor.h"

#define SAMPLE_AFTER_SUBDIVISION 1
#define TEST_EMPTY_VIEW_CELLS 0



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

typedef priority_queue<ViewCell *, vector<ViewCell *>, myless<vector<ViewCell *>::value_type> > FilterQueue;



ViewCellsManager::ViewCellsManager():
mRenderer(NULL),
mInitialSamples(0),
mConstructionSamples(0),
mPostProcessSamples(0),
mVisualizationSamples(0),
mTotalAreaValid(false),
mTotalArea(0.0f),
mViewCellsFinished(false),
mMaxPvsSize(9999999),
mMinPvsSize(0), // one means only empty view cells are invalid
mMaxPvsRatio(1.0)
{
	mViewSpaceBox.Initialize();
	ParseEnvironment();

	mViewCellsTree = new ViewCellsTree(this);
}


void ViewCellsManager::ParseEnvironment()
{
	// visualization stuff
	environment->GetBoolValue("ViewCells.Visualization.exportRays", mExportRays);
	environment->GetBoolValue("ViewCells.Visualization.exportGeometry", mExportGeometry);
	environment->GetFloatValue("ViewCells.maxPvsRatio", mMaxPvsRatio);
	
	bool emptyViewCells = false;
	environment->GetBoolValue("ViewCells.pruneEmptyViewCells", emptyViewCells);
	mMinPvsSize = emptyViewCells ? 1 : 0;

	environment->GetBoolValue("ViewCells.processOnlyValidViewCells", mOnlyValidViewCells);

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

 	environment->GetIntValue("ViewCells.Visualization.samples", mVisualizationSamples);

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

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

	
	if (strcmp(buf, "box") == 0)
		mSamplingType = Preprocessor::SPATIAL_BOX_BASED_DISTRIBUTION;
	else if (strcmp(buf, "directional") == 0)
		mSamplingType = Preprocessor::DIRECTION_BASED_DISTRIBUTION;
	else 
	{
		Debug << "error! wrong sampling type" << endl;
		exit(0);
	}

	environment->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 options ****************" << endl;
	Debug << "color code: " << mColorCode << endl;

	Debug << "export rays: " << mExportRays << endl;
	Debug << "export geometry: " << mExportGeometry << endl;
	Debug << "max pvs ratio: " << mMaxPvsRatio << endl;
	
	Debug << "prune empty view cells: " << emptyViewCells << 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: " << 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 << "show visualization: " << mShowVisualization << endl;
	Debug << "filter width: " << mFilterWidth << endl;

	Debug << endl;
}


ViewCellsManager::~ViewCellsManager()
{
	DEL_PTR(mRenderer);

	if (!ViewCellsTreeConstructed())
		CLEAR_CONTAINER(mViewCells);
	else
		DEL_PTR(mViewCellsTree);

	CLEAR_CONTAINER(mMeshContainer);
}


void ViewCellsManager::CollectEmptyViewCells()
{
	mEmptyViewCells.clear();
	ViewCellContainer leaves;
	mViewCellsTree->CollectLeaves(mViewCellsTree->GetRoot(), leaves);

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

	cout << "collecting empty view cells" << endl;
	
	for (it = leaves.begin(); it != it_end; ++ it)
	{
		if ((*it)->GetPvs().Empty())
		{
			mEmptyViewCells.push_back(*it);
		}
	}
	Debug << "empty view cells found: " << (int)mEmptyViewCells.size() << endl;
}


void ViewCellsManager::TestEmptyViewCells(const ObjectContainer &obj)
{
	ViewCellContainer::const_iterator it, it_end = mEmptyViewCells.end();

	char buf[50];
	int i = 0;
	for (it = mEmptyViewCells.begin(); it != it_end; ++ it)
	{
		if (!(*it)->GetPvs().Empty())
		{
			sprintf(buf, "empty-viewcells-%09d.x3d", i/*(*it)->GetId()*/);
			Exporter *exporter = Exporter::GetExporter(buf);
			
			if (exporter && i < 20)
			{
				Ray *pray = (*it)->mPiercingRays[0];
				Debug << "view cell " << (*it)->GetId() << " not empty, pvs: " << (*it)->GetPvs().GetSize() << " " << (int)pray->intersections.size() << endl;

				exporter->ExportRays((*it)->mPiercingRays);
							
				exporter->SetFilled();
				exporter->SetForcedMaterial(RgbColor(0,0,1));

				for (int j = 0; j < (int)pray->intersections.size(); ++ j)
				{
					if (pray->intersections[j].mObject)
						exporter->ExportIntersectable(pray->intersections[j].mObject);
				}

				//exporter->SetWireframe();
				exporter->SetForcedMaterial(RgbColor(0,1,0));
				exporter->ExportGeometry(obj);

				exporter->SetFilled();

				exporter->SetForcedMaterial(RgbColor(1,0,0));
				ExportViewCellGeometry(exporter, *it);

				delete exporter;		
			}

		
			++ i;
		}
	}
	Debug << "\nSampled " << i << " new view cells (" << " of " << (int)mEmptyViewCells.size() << ")" << endl << endl;
}


int ViewCellsManager::CastPassSamples(const int samplesPerPass, 
									  const int sampleType, 
									  VssRayContainer &passSamples) const
{
	SimpleRayContainer simpleRays;

	preprocessor->GenerateRays(samplesPerPass,
							   sampleType,
							   simpleRays);

	// shoot simple ray and add it to importance samples
	preprocessor->CastRays(simpleRays, passSamples);

	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)
		{
			//(*it)->Unref();
			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;

	cout << "view cell construction: casting " << mInitialSamples << " initial samples ... ";
	//-- construction rays => we use uniform samples for this
	CastPassSamples(mInitialSamples, 
					mSamplingType,
					initialSamples);
	
	cout << "finished" << endl;

	
	// construct view cells
	const int numInitialSamples = 
		ConstructSubdivision(preprocessor->mObjects, initialSamples);

	numSamples += numInitialSamples;

	// rays can be passed or deleted
	disposeRays(initialSamples, outRays);
	
	cout << "testing filter ... ";

	TestFilter(preprocessor->mObjects);

	cout << "finished" << endl;

	// -- stats after contruction
	ResetViewCells();

  	Debug << "\nView cells after initial sampling:\n" << mCurrentViewCellsStats << endl;

	if (1) // export initial view cells
	{
		cout << "exporting initial view cells (=leaves) ... ";
		Exporter *exporter = Exporter::GetExporter("view_cells.x3d");

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

			ExportViewCellsForViz(exporter);

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

	//-- guided rays are used for further sampling
	const int n = mConstructionSamples; //+initialSamples;

	// should we use directional samples?
	bool dirSamples = (mSamplingType == Preprocessor::DIRECTION_BASED_DISTRIBUTION);

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

		const int samplingType = mSamplingType;
			/*dirSamples ? 
						Preprocessor::DIRECTION_BASED_DISTRIBUTION :
				 		Preprocessor::SPATIAL_BOX_BASED_DISTRIBUTION;*/

		if (0)
			dirSamples = !dirSamples; // toggle sampling method

		numSamples += CastPassSamples(mSamplesPerPass, 
									  samplingType,
									  constructionSamples);

		cout << "finished" << endl;

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

		// TODO: leak?
		if (SAMPLE_AFTER_SUBDIVISION)
			ComputeSampleContributions(constructionSamples, true, false);
		cout << "finished" << endl;


		disposeRays(constructionSamples, outRays);

		cout << "total samples: " << numSamples << endl;
	}
	

	//-- post processing
	VssRayContainer postProcessSamples;

	//-- construction rays 
	CastPassSamples(mPostProcessSamples,
					mSamplingType, 
					postProcessSamples);


	// stats before post processing (i.e., merge)
	EvaluateViewCellsStats();
	Debug << "\noriginal view cell partition before post process:\n" << mCurrentViewCellsStats << endl;

	mRenderer->RenderScene();
	SimulationStatistics ss;
	dynamic_cast<RenderSimulator *>(mRenderer)->GetStatistics(ss);

    Debug << ss << endl;



	cout << "starting post processing and visualization" << endl;


	// store view cells for postprocessing
	const bool storeViewCells = true;


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

	// merge the view cells
	PostProcess(preprocessor->mObjects, postProcessSamples);

	// only for testing
	if (TEST_EMPTY_VIEW_CELLS)
		CollectEmptyViewCells();


	//-- visualization
	if (mShowVisualization)
	{
		VssRayContainer visualizationSamples;

		//-- construction rays => we use uniform samples for this
		CastPassSamples(mVisualizationSamples,
					    Preprocessor::DIRECTION_BASED_DISTRIBUTION, 
						visualizationSamples);

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

		// different visualizations
		Visualize(preprocessor->mObjects, visualizationSamples);

		disposeRays(visualizationSamples, outRays);
	}

	if (mEvaluateViewCells)
	{
		EvalViewCellPartition(preprocessor);
	}
	
	if (0)
	{
		ViewCellContainer leaves;
		mViewCellsTree->CollectLeaves(mViewCellsTree->GetRoot(), leaves);
		mViewCellsTree->ResetPvs();
		VssRayContainer dummyRays;
		CastPassSamples(mInitialSamples, mSamplingType, dummyRays);
	
		//ComputeSampleContributions(initialSamples, true, false);
		ComputeSampleContributions(dummyRays, true, false);

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

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

		mViewCellsTree->ExportStats("dummy.log");
	}

	return numSamples;
}


void ViewCellsManager::EvalViewCellPartition(Preprocessor *preprocessor)
{
	int samplesPerPass;
	int numSamples;
	int castSamples = 0;

	char s[64]; 

	environment->GetIntValue("ViewCells.Evaluation.samplesPerPass", samplesPerPass);
	environment->GetIntValue("ViewCells.Evaluation.samples", numSamples);

	char statsPrefix[100];
	environment->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;

	//VssRayContainer outRays;
	// should directional sampling be used?
	bool dirSamples = mSamplingType == Preprocessor::DIRECTION_BASED_DISTRIBUTION;

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

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

	bool startFromZero = true;

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

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

	while (castSamples < numSamples)
	{
		VssRayContainer evaluationSamples;

		const int samplingType = mSamplingType;
		/*	dirSamples ? 
						Preprocessor::DIRECTION_BASED_DISTRIBUTION :
				 		Preprocessor::SPATIAL_BOX_BASED_DISTRIBUTION;
		*/
		//-- construction rays => we use uniform samples for this
		CastPassSamples(samplesPerPass, samplingType, evaluationSamples);
		
		castSamples += samplesPerPass;

		cout << "casting " << (int)evaluationSamples.size() << " samples " << endl;

		ComputeSampleContributions(evaluationSamples, true, false);

		cout << "compute new statistics ... ";

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

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

		// output stats
		sprintf(s, "-%09d-eval.log", castSamples);
		string fileName = string(statsPrefix) + string(s);

		mViewCellsTree->ExportStats(fileName);

		cout << "finished" << endl;
	
		disposeRays(evaluationSamples, NULL);
	}

	// find empty view cells bug
	if (TEST_EMPTY_VIEW_CELLS)
		TestEmptyViewCells(preprocessor->mObjects);
}

/*
int ViewCellsManager::ConstructLocalMergeTree(vector<LocalMergeCandidate> candidates)
											 
{
	while(!candidates.empty())
	{
		MergeCandidate mc = candidates.back();
		candidates.pop_back();
		EvalMergeCost(mc);
		mergeQueue.push(mc);
	}

	ViewCell::NewMail();

	
	long startTime = GetTime();

	mergeStats.candidates = (int)mMergeQueue.size();

	// passes are needed for statistics, because we don't want to record
	// every merge
	int pass = 0;
	int mergedPerPass = 0;
	float realExpectedCost = mExpectedCost;
	float realAvgRenderCost = mAvgRenderCost;
	int realNumActiveViewCells = mNumActiveViewCells;
	
	 reset.

	int numMergedViewCells = 0;

	environment->GetIntValue("ViewCells.PostProcess.maxMergesPerPass", maxMergesPerPass);
	environment->GetFloatValue("ViewCells.PostProcess.avgCostMaxDeviation", avgCostMaxDeviation);

	cout << "actual merge starts now ... " << endl;

	//-- use priority queue to merge leaf pairs

	//const float maxAvgCost = 350;
	while (!mMergeQueue.empty())//NumActiveViewCells > mMergeMinViewCells))
	{
		//-- reset merge queue if the ratio of current expected cost / real expected cost
		//   too small or after a given number of merges
		if ((mergedPerPass > maxMergesPerPass) ||
			(avgCostMaxDeviation > mAvgRenderCost / realAvgRenderCost))
		{
			// adjust render cost
			++ pass;

			mergedPerPass = 0;
			mExpectedCost = realExpectedCost;
					
			
		
			// refines the view cells
			// then priorities are recomputed
			// and the candidates are put back into merge queue
			if (mRefineViewCells)
				RefineViewCells(rays, objects);
			else
				ResetMergeQueue();

			Debug << "Values after reset: "  
				  << " erc: " << mExpectedCost 
				  << " avg: " << mAvgRenderCost 
				  << " dev: " << mDeviation << endl;

			if (mExportMergedViewCells)
			{
				ExportMergedViewCells(activeViewCells, objects, numMergedViewCells);
			}
		}


		MergeCandidate mc = mMergeQueue.top();
		mMergeQueue.pop();
	
		// both view cells equal
		// NOTE: do I really still need this? probably cannot happen!!
		if (mc.mLeftViewCell == mc.mRightViewCell)
			continue;

		if (mc.IsValid())
		{
			ViewCell::NewMail();

			//-- update statistical values
			-- realNumActiveViewCells;
			++ mergeStats.merged;
			++ mergedPerPass;

			const float renderCostIncr = mc.GetRenderCost();
			const float mergeCostIncr = mc.GetMergeCost();

			totalRenderCost += renderCostIncr;
			mDeviation += mc.GetDeviationIncr();
			
			
			// merge the view cells of leaf1 and leaf2
			int pvsDiff;
			ViewCellInterior *mergedVc = 
				MergeViewCells(mc.mLeftViewCell, mc.mRightViewCell, pvsDiff);


			// total render cost and deviation has changed
			// real expected cost will be larger than expected cost used for the
			// cost heuristics, but cannot recompute costs on each increase of the 
			// expected cost
			totalPvs += pvsDiff;
			realExpectedCost = totalRenderCost / (float)realNumActiveViewCells;
			realAvgRenderCost = (float)totalPvs / (float)realNumActiveViewCells;
	
			// set merge cost to this node
			mergedVc->SetMergeCost(totalRenderCost);

			//if (mViewCellsManager->EqualToSpatialNode(mergedVc))
			//	++ mergeStats.siblings;
			mergedVc->SetCost(realExpectedCost);

			if ((mergeStats.merged % statsOut) == 0)
				cout << "merged " << mergeStats.merged << " view cells" << endl;

		}
		else
		{ 
			// merge candidate not valid, because one of the leaves was already
			// merged with another one => validate and reinsert into queue
			if (ValidateMergeCandidate(mc))
			{
				EvalMergeCost(mc);
				mMergeQueue.push(mc);
			}
		}
		
	}

	
	// adjust stats and reset queue one final time
	mExpectedCost = realExpectedCost;
	mAvgRenderCost = realAvgRenderCost;
	mNumActiveViewCells = realNumActiveViewCells;

	UpdateActiveViewCells(activeViewCells);

	
	// refine view cells and reset costs
	if (mRefineViewCells)
		RefineViewCells(rays, objects);
	else
		ResetMergeQueue();

	// create a root node if the merge was not done till root level,
	// else take the single node as new root
	if ((int)activeViewCells.size() > 1)
	{
		Debug << "creating root of view cell hierarchy for " 
			  << (int)activeViewCells.size() << " view cells" << endl;
		
		ViewCellInterior *root = mViewCellsManager->MergeViewCells(activeViewCells);
		root->SetMergeCost(totalRenderCost);
		// $$JB keep this 0 temporarilly
		root->SetCost(0.0f);

		mRoot = root;
	}
	else if ((int)activeViewCells.size() == 1)
	{
		Debug << "setting root of the merge history" << endl;
		mRoot = activeViewCells[0];
	}

	//-- empty merge queue just in case
	while (!mMergeQueue.empty())
	{
		mMergeQueue.pop();
	}

	// TODO delete because makes no sense here
	mergeStats.expectedRenderCost = realExpectedCost;
	mergeStats.deviation = mDeviation;

	// we want to optimize this heuristics
	mergeStats.heuristics = 
		mDeviation * (1.0f - mRenderCostWeight) + 
		mExpectedCost * mRenderCostWeight;

	mergeStats.mergeTime = TimeDiff(startTime, GetTime());
	mergeStats.Stop();
	Debug << mergeStats << endl << endl;

	// assign colors for the view cells so that at least one is always consistent
	AssignRandomColors();
	
	//TODO: should return sample contributions?
	return mergeStats.merged;
}
*/

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

  if ((vc->GetPvs().GetSize() > maxPvsSize) ||
	  (vc->GetPvs().GetSize() < minPvsSize))
	{
	  return false;
	}

  return true;
}


AxisAlignedBox3 ViewCellsManager::GetFilterBBox(const Vector3 &viewPoint, 
												const float width) const
{
	Vector3 min = viewPoint - width * 0.5f;
	Vector3 max = viewPoint + width * 0.5;

	return AxisAlignedBox3(min, max);
}


void ViewCellsManager::GetPrVS(const Vector3 &viewPoint, PrVs &prvs)
{
	const AxisAlignedBox3 box = GetFilterBBox(viewPoint, mFilterWidth);

	ViewCellContainer viewCells;
	ComputeBoxIntersections(box, viewCells);

		
}


bool ViewCellsManager::ViewCellsTreeConstructed() const
{
	return 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
										)
{
  sort(mViewCells.begin(), mViewCells.end(), ViewCell::SmallerPvs);

  int start = mViewCells.size()*minValid;
  int end = mViewCells.size()*maxValid;

  for (int i=0; i < mViewCells.size(); i++)
	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)
{
	X3dParser parser;

	environment->GetFloatValue("ViewCells.height", parser.mViewCellHeight);

	bool success = parser.ParseFile(filename, *this);
	Debug << (int)mViewCells.size() << " view cells loaded" << endl;

	return success;
}


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

	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 addRays,
											 const bool storeViewCells
											 )
{
  // view cells not yet constructed
  if (!ViewCellsConstructed())
	return 0.0f;

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

  float sum = 0.0f;
  for (it = rays.begin(); it != it_end; ++ it) 
  {
	  sum += ComputeSampleContributions(*(*it), addRays, storeViewCells);
	  //ComputeSampleContributions(*(*it), addRays);
	  //	sum += (*it)->mPvsContribution;
  }

  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,
												int &totalPvs,
												float &avgRenderCost)
{
	ViewCellContainer::const_iterator it, it_end = mViewCells.end();


	//-- compute expected value

	totalRenderCost = 0;
	totalPvs = 0;

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

	// normalize with view space box
	totalRenderCost /= mViewSpaceBox.GetVolume();
	expectedRenderCost = totalRenderCost / (float)mViewCells.size();
	avgRenderCost = totalPvs / (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().GetSize() * vc->GetVolume();
		float dev;

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

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

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



void ViewCellsManager::AddViewCell(ViewCell *viewCell)
{
	mViewCells.push_back(viewCell);
}


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


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


void ViewCellsManager::DeriveViewCells(const ObjectContainer &objects,
									   ViewCellContainer &viewCells,
									   const int maxViewCells) const
{
	// maximal max viewcells
	int limit = maxViewCells > 0 ?
		Min((int)objects.size(), maxViewCells) : (int)objects.size();

	for (int i = 0; i < limit; ++ i)
	{
		Intersectable *object = objects[i];

		// extract the mesh instances
		if (object->Type() == Intersectable::MESH_INSTANCE)
		{
			MeshInstance *inst = dynamic_cast<MeshInstance *>(object);

			ViewCell *viewCell = GenerateViewCell(inst->GetMesh());
			viewCells.push_back(viewCell);
		}
		//TODO: transformed meshes
	}
}


ViewCell *ViewCellsManager::ExtrudeViewCell(const Triangle3 &baseTri,
											const float height) const
{
	// one mesh per view cell
	Mesh *mesh = new Mesh();

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

	mesh->Preprocess();

	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 and a view cell mesh is created
	for (it = mViewCells.begin(); it != it_end; ++ it)
	{
		Finalize(*it, createMesh);
	}

	mTotalAreaValid = false;
}


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


ViewCellInterior *ViewCellsManager::MergeViewCells(ViewCell *left, ViewCell *right) const
{
	// generate parent view cell
	ViewCellInterior *vc = new ViewCellInterior();//GenerateViewCell();

	vc->GetPvs() = left->GetPvs();
	// merge pvs
	vc->GetPvs().Merge(right->GetPvs());

	//-- merge ray sets
	if (0)
	{
		stable_sort(left->mPiercingRays.begin(), left->mPiercingRays.end());
		stable_sort(right->mPiercingRays.begin(), right->mPiercingRays.end());

		std::merge(left->mPiercingRays.begin(), left->mPiercingRays.end(),
				   right->mPiercingRays.begin(), right->mPiercingRays.end(),
				   vc->mPiercingRays.begin());
	}


	vc->SetupChildLink(left);
	vc->SetupChildLink(right);


	return vc;
}


ViewCellInterior *ViewCellsManager::MergeViewCells(ViewCellContainer &children) const
{
	ViewCellInterior *vc = new ViewCellInterior();//GenerateViewCell();

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

	for (it = children.begin(); it != it_end; ++ it)
	{
		// merge pvs
		vc->GetPvs().Merge((*it)->GetPvs());

		vc->SetupChildLink(*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::GetPvsStatistics(PvsStatistics &stat)
{
  ViewCellContainer::const_iterator it = mViewCells.begin();
  stat.viewcells = 0;
  stat.minPvs = 100000000;
  stat.maxPvs = 0;
  stat.avgPvs = 0.0f;

  for (; it != mViewCells.end(); ++it) {
	ViewCell *viewcell = *it;
	int pvsSize = viewcell->GetPvs().GetSize();
	if ( pvsSize < stat.minPvs)
	  stat.minPvs = pvsSize;
	if (pvsSize > stat.maxPvs)
	  stat.maxPvs = pvsSize;
	stat.avgPvs += pvsSize;
	stat.viewcells++;
  }
  if (stat.viewcells)
	stat.avgPvs/=stat.viewcells;
}


void ViewCellsManager::PrintPvsStatistics(ostream &s)
{
  s<<"############# Viewcell PVS STAT ##################\n";
  PvsStatistics pvsStat;
  GetPvsStatistics(pvsStat);
  s<<"#AVG_PVS\n"<<pvsStat.avgPvs<<endl;
  s<<"#MAX_PVS\n"<<pvsStat.maxPvs<<endl;
  s<<"#MIN_PVS\n"<<pvsStat.minPvs<<endl;
}


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


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


void ViewCellsManager::SetViewSpaceBox(const AxisAlignedBox3 &box)
{
	mViewSpaceBox = box;

	CreateClipPlane();
	
	mTotalAreaValid = false;
}


void ViewCellsManager::CreateClipPlane()
{
	int axis = 0;
	float pos;

	environment->GetFloatValue("ViewCells.Visualization.clipPlanePos", pos);

	Vector3 point = mViewSpaceBox.Min() +  mViewSpaceBox.Size() * pos;

	if (mUseClipPlaneForViz)
        environment->GetIntValue("ViewCells.Visualization.clipPlaneAxis", axis);

	Vector3 normal(0,0,0);
	normal[axis] = 1;

	mClipPlane = Plane3(normal, point);
}


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


void ViewCellsManager::ResetViewCells()
{
	mViewCells.clear();
	
	CollectViewCells();
	
	mCurrentViewCellsStats.Reset();
	EvaluateViewCellsStats();

	// has to be recomputed
	mTotalAreaValid = false;
}


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


void
ViewCellsManager::AddSampleContributions(const VssRayContainer &rays)
{
  if (!ViewCellsConstructed())
	return;

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

  for (it = rays.begin(); it != it_end; ++ it) {
	AddSampleContributions(*(*it));
  }
}


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



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


void
ViewCellsManager::AddSampleContributions(VssRay &ray)
{
  // assumes viewcells have been stored...
  ViewCellContainer *viewcells = &ray.mViewCells;
  ViewCellContainer::const_iterator it;
  for (it = viewcells->begin(); it != viewcells->end(); ++it) {
	ViewCell *viewcell = *it;
	if (viewcell->GetValid()) {
	  // if ray not outside of view space
	  viewcell->GetPvs().AddSample(ray.mTerminationObject, ray.mPdf);
	}
  }
}


float ViewCellsManager::ComputeSampleContributions(VssRay &ray,
												   const bool addRays,
												   const bool storeViewCells)
{
	ViewCellContainer viewcells;

	ray.mPvsContribution = 0;
	ray.mRelativePvsContribution = 0.0f;

	static Ray hray;
	hray.Init(ray);
	//hray.mFlags |= Ray::CULL_BACKFACES;
	//Ray hray(ray);

	float tmin = 0, tmax = 1.0;

	if (!GetViewSpaceBox().GetRaySegment(hray, tmin, tmax) || (tmin > tmax))
		return 0;

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

	CastLineSegment(origin, termination, viewcells);

	// copy viewcells memory efficiently
	//const bool storeViewcells = !addRays;

	if (storeViewCells)
	{
		ray.mViewCells.reserve(viewcells.size());
		ray.mViewCells = viewcells;
	}

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

	for (; it != viewcells.end(); ++ it) 
	{
		ViewCell *viewcell = *it;

		if (viewcell->GetValid()) 
		{
			// HACK
			if (TEST_EMPTY_VIEW_CELLS)
				for (int i = 0; i < mEmptyViewCells.size(); ++i)
				{
					if (viewcell == mEmptyViewCells[i])
					{
						viewcell->mPiercingRays.push_back(new Ray(ray));
						Debug << "empty view cell ray found: " << ray.mOriginObject << ", " << ray.mTerminationObject << endl;
					}
				}

			// if ray not outside of view space
			float contribution;
			if (ray.mTerminationObject &&
				viewcell->GetPvs().GetSampleContribution(ray.mTerminationObject,
														 ray.mPdf,
														 contribution))
			{
				++ ray.mPvsContribution;
				ray.mRelativePvsContribution += contribution;
			}
			if (ray.mOriginObject && 
				viewcell->GetPvs().GetSampleContribution(ray.mOriginObject,
														 ray.mPdf,
														 contribution))
			{
				++ ray.mPvsContribution;
				ray.mRelativePvsContribution += contribution;
			}
		}
	}

	
	if (addRays)
	{
		for (it = viewcells.begin(); it != viewcells.end(); ++ it) 
		{
			ViewCell *viewcell = *it;
            
			if (viewcell->GetValid()) 
			{
				// if ray not outside of view space
				 if (ray.mTerminationObject)
					 viewcell->GetPvs().AddSample(ray.mTerminationObject, ray.mPdf);
				 if (ray.mOriginObject)
					 viewcell->GetPvs().AddSample(ray.mOriginObject, ray.mPdf);
			}
		}
	}

	return ray.mRelativePvsContribution;
}


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, float objRendercost) const
{
	return mViewCellsTree->GetPvsSize(viewCell) * objRendercost;
}


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
		for (int i = 0; i < (int)mViewCells.size(); ++ i)
			mViewCells[i]->SetId(i);
}


void ViewCellsManager::ExportViewCellsForViz(Exporter *exporter) const
{
	ViewCellContainer::const_iterator it, it_end = mViewCells.end();

	for (it = mViewCells.begin(); it != it_end; ++ it)
	{
		if (!mOnlyValidViewCells || (*it)->GetValid())
		{
			ExportColor(exporter, *it);		
			ExportViewCellGeometry(exporter, *it, 
				mUseClipPlaneForViz ? &mClipPlane : NULL);
		}
	}
}


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)
{
	return false;
}


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


void ViewCellsManager::SetViewCellsActive()
{
	++ ViewCell::sLastUpdated;
	ViewCellContainer::const_iterator it, it_end = mViewCells.end();
	for (it = mViewCells.begin(); it != it_end; ++ it)
	{
		(*it)->SetActive();
	}
}

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


BspViewCellsManager::BspViewCellsManager(BspTree *bspTree):
ViewCellsManager(), mBspTree(bspTree)
{
	environment->GetIntValue("BspTree.Construction.samples", mInitialSamples);
	mBspTree->SetViewCellsManager(this);
	mBspTree->mViewCellsTree = 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
	if (ViewCellsConstructed())
		return 0;

	int sampleContributions = 0;

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

	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 (mViewCells.empty())
	{
		// no view cells loaded
		mBspTree->Construct(objects, constructionRays, &mViewSpaceBox);
		// collect final view cells
		mBspTree->CollectViewCells(mViewCells);
	}
	else
	{
		mBspTree->Construct(mViewCells);
	}

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

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

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

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

	return sampleContributions;
}


void BspViewCellsManager::CollectViewCells()
{
	// view cells tree constructed
	if (!ViewCellsTreeConstructed())
	{		
		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)
{
	// compute view cell area as subsititute for probability
	if (1)
		return GetVolume(viewCell) / GetViewSpaceBox().GetVolume();
	else
		return GetArea(viewCell) / GetAccVcArea();
}



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


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)
	if (mViewCellsFinished)
	{
		FinalizeViewCells(true);
		EvaluateViewCellsStats();

		return 0;
	}

	//-- post processing of bsp view cells

    int vcSize = 0;
	int pvsSize = 0;

	//-- merge view cells
	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;
		// create spatial merge hierarchy
		mViewCellsTree->SetRoot(ConstructSpatialMergeTree(mBspTree->GetRoot()));
	}

	// export statistics after merge
	if (1)
	{
		char mstats[100];
		environment->GetStringValue("ViewCells.mergeStats", mstats);
		mViewCellsTree->ExportStats(mstats);
	}

	//-- stats and visualizations
	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
    // reset view cells and stats
	ResetViewCells();
	Debug << "\nView cells after merge:\n" << mCurrentViewCellsStats << endl;


	int savedColorCode  = mColorCode;
	
	//BspLeaf::NewMail();
	if (1) // export merged view cells
	{
		mColorCode = 0;
		
		Exporter *exporter = Exporter::GetExporter("merged_view_cells.x3d");
		

		cout << "exporting view cells after merge ... ";

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

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


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

	if (1) // export merged view cells
	{
		mColorCode = 1;

		Exporter *exporter = Exporter::GetExporter("merged_view_cells_pvs.x3d");
	
		cout << "exporting view cells after merge (pvs size) ... ";	

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

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

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

	
	// only for testing
	TestSubdivision();

	mColorCode = savedColorCode;

	FinalizeViewCells(true);
	
	// write view cells to disc
	if (mExportViewCells)
	{
		char buff[100];
		environment->GetStringValue("ViewCells.filename", buff);
		string vcFilename(buff);

		ExportViewCells(buff);
	}

	return 0;
}


BspViewCellsManager::~BspViewCellsManager()
{
}


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


void BspViewCellsManager::Visualize(const ObjectContainer &objects,
									const VssRayContainer &sampleRays)
{
	if (!ViewCellsConstructed())
		return;
	
	int savedColorCode = mColorCode;

	
	
	if (1) // export final view cells
	{
		mColorCode = 1;

		Exporter *exporter = Exporter::GetExporter("final_view_cells.x3d");
	
		cout << "exporting view cells after merge (pvs size) ... ";	

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

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

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

	mColorCode = savedColorCode;

	//-- visualization of the BSP splits
	bool exportSplits = false;
	environment->GetBoolValue("BspTree.Visualization.exportSplits", exportSplits);

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

	// export single view cells
	ExportBspPvs(objects);
}


inline bool vc_gt(ViewCell *a, ViewCell *b)
{
	return a->GetPvs().GetSize() > b->GetPvs().GetSize();
}


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::ExportBspPvs(const ObjectContainer &objects)
{
	const int leafOut = 10;

	ViewCell::NewMail();

	//-- some rays for output
	const int raysOut = min((int)mBspRays.size(), mVisualizationSamples);

	cout << "visualization using " << mVisualizationSamples << " samples" << endl;
	Debug << "\nOutput view cells: " << endl;

	// sort view cells to get largest view cells
	if (0)
		stable_sort(mViewCells.begin(), mViewCells.end(), vc_gt);

	int limit = min(leafOut, (int)mViewCells.size());

	for (int i = 0; i < limit; ++ i)
	{
		cout << "creating output for view cell " << i << " ... ";
		VssRayContainer vcRays;
		Intersectable::NewMail();
		ViewCell *vc;

		if (0)
			vc = mViewCells[i];
		else
			vc = mViewCells[Random((int)mViewCells.size())];

		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)
			{
				BspRay *ray = mBspRays[k];
				for	(int j = 0; j < (int)ray->intersections.size(); ++ j)
				{
					BspLeaf *leaf = ray->intersections[j].mLeaf;
					if (vc == leaf->GetViewCell())
						vcRays.push_back(ray->vssRay);
				}
			}
		}

		//bspLeaves[j]->Mail();
		char s[64]; sprintf(s, "bsp-pvs%04d.x3d", i);

		Exporter *exporter = Exporter::GetExporter(s);

		exporter->SetWireframe();

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

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

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

		ObjectPvsMap::const_iterator it,
			it_end = vc->GetPvs().mEntries.end();

		exporter->SetFilled();

		// output PVS of view cell
		for (it = vc->GetPvs().mEntries.begin(); it != it_end; ++ it)
		{
			Intersectable *intersect = (*it).first;

			if (!intersect->Mailed())
			{
				Material m = RandomMaterial();
				exporter->SetForcedMaterial(m);

				exporter->ExportIntersectable(intersect);
				intersect->Mail();
			}
		}

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

	Debug << endl;
}


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

	float importance = 0;
	static Material m;

	switch (mColorCode)
	{
	case 0: // Random
		{
			if (vcValid)
			{
				m.mDiffuseColor.r = 0.5f + RandomValue(0.0f, 0.5f);
				m.mDiffuseColor.g = 0.5f + RandomValue(0.0f, 0.5f);
				m.mDiffuseColor.b = 0.5f + RandomValue(0.0f, 0.5f);
			}
			else
			{
				m.mDiffuseColor.r = 0.0f;
				m.mDiffuseColor.g = 1.0f;
				m.mDiffuseColor.b = 0.0f;
			}

			exporter->SetForcedMaterial(m);
			return;
		}
		
	case 1: // pvs
		{
			importance = (float)vc->GetPvs().GetSize() /
				(float)mCurrentViewCellsStats.maxPvs;

		}
		break;
	case 2: // merges
		{
            int lSize = mViewCellsTree->GetSize(vc);
			importance = (float)lSize / (float)mCurrentViewCellsStats.maxLeaves;
		}
		//break;
	case 3: // merge tree differene
		{
			// TODO
			//importance = (float)GetMaxTreeDiff(vc) /
			//	(float)(mVspBspTree->GetStatistics().maxDepth * 2);

		}
		break;
	default:
		break;
	}

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

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


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;
		BspLeaf *leaf = dynamic_cast<BspViewCell *>(*it)->mLeaf;
		mBspTree->ConstructGeometry(leaf, geom);

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

		float thres = 0.9;
		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 Plane3 *clipPlane) const
{
	if (vc->GetMesh())
	{
		exporter->ExportMesh(vc->GetMesh());
		return;
	}

	BspNodeGeometry geom;
	mBspTree->ConstructGeometry(vc, geom);

	if (clipPlane)
	{
		const int cf = Polygon3::ClassifyPlane(geom.GetPolys(), *clipPlane, 0.0001f);

		if (cf == Polygon3::BACK_SIDE)
		{
			exporter->ExportPolygons(geom.GetPolys());
		}
		else if (cf == Polygon3::SPLIT)
		{
			BspNodeGeometry front;
			BspNodeGeometry back;

			geom.SplitGeometry(front,
							   back,
							   *clipPlane,
							   mViewSpaceBox, 
							   0.0001f);

			if (back.Valid())
				exporter->ExportPolygons(back.GetPolys());
		}
	}
	else
	{
		exporter->ExportPolygons(geom.GetPolys());
	}
}


void BspViewCellsManager::CreateMesh(ViewCell *vc)
{
	if (vc->GetMesh())
		delete vc->GetMesh();

	BspNodeGeometry geom;
	
	mBspTree->ConstructGeometry(vc, geom);

	Mesh *mesh = new Mesh();
	geom.AddToMesh(*mesh);
	vc->SetMesh(mesh);
	mMeshContainer.push_back(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;
		BspLeaf *leaf = dynamic_cast<BspViewCell *>(*it)->mLeaf;
		mBspTree->ConstructGeometry(leaf, geom);

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

		//(*it)->SetVolume(vol);
		//(*it)->SetArea(area);

		area += lArea;
		volume += lVol;

        CreateMesh(*it);
	}

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


ViewCell *BspViewCellsManager::GetViewCell(const Vector3 &point) const
{
	if (!mBspTree)
		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)
{
	cout << "exporting view cells to xml ... ";
	std::ofstream stream;

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


	stream.open(filename.c_str());
	stream << "<?xml version=\"1.0\" encoding=\"UTF-8\"?>"<<endl;
	stream << "<Visibility_Solution>" << endl;

	//-- the view space bounding box
	stream << "<ViewSpaceBox" 
		   << " min=\"" << mViewSpaceBox.Min().x << " " << mViewSpaceBox.Min().y << " " << mViewSpaceBox.Min().z << "\""
		   << " max=\"" << mViewSpaceBox.Max().x << " " << mViewSpaceBox.Max().y << " " << mViewSpaceBox.Max().z << "\" />" << endl;

	//-- the type of the view cells hierarchy
	//stream << "<Hierarchy name=\"bspTree\" />" << endl;
	stream << "<Hierarchy name=\"vspBspTree\" />" << endl; // write vsp bsp here because can use same tree and is bug free
	//-- load the view cells itself, i.e., the ids and the pvs
	stream << "<ViewCells>" << endl;

#if 0
	
	ViewCellContainer::const_iterator it, it_end = mViewCells.end();
		
	for (it = mViewCells.begin(); it != it_end; ++ it)
		ExportViewCell(*it, stream);
#else
	mViewCellsTree->Export(stream);
#endif

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

	//-- load the hierarchy
	stream << "<Hierarchy>" << endl;
	mBspTree->Export(stream);
	stream << endl << "</Hierarchy>" << endl;

	stream << "</Visibility_Solution>" << endl;
	stream.close();

	cout << "finished" << endl;

	return true;
}


void BspViewCellsManager::AddCurrentViewCellsToHierarchy()
{
	ViewCellContainer::const_iterator it, it_end = mViewCells.end();
	for (it = mViewCells.begin(); it != it_end; ++ it)
	{
		ViewCell *vc = *it;
		ViewCellContainer leaves;
		mViewCellsTree->CollectLeaves(vc, leaves);
		
		ViewCellContainer::const_iterator lit, lit_end = leaves.end();

		for (lit = leaves.begin(); lit != lit_end; ++ lit)
		{
			BspViewCell *bspVc = dynamic_cast<BspViewCell *>(*lit);
			bspVc->mLeaf->SetViewCell(vc);
		}
	}
}


ViewCell *BspViewCellsManager::ConstructSpatialMergeTree(BspNode *root)
{
	if (root->IsLeaf())
	{
		ViewCell *viewCell = dynamic_cast<BspLeaf *>(root)->GetViewCell();

		viewCell->SetMergeCost(0.0f);

		return viewCell;
	}
	
	BspInterior *interior = dynamic_cast<BspInterior *>(root);
	ViewCellInterior *viewCellInterior = new ViewCellInterior();
		
	float mergeCost = 1.0f / (float)root->mTimeStamp;
	//Debug << "timestamp: " << root->mTimeStamp;
	//Debug << "merge cost: " << mergeCost << endl;

	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(frontVc);
	viewCellInterior->SetupChildLink(backVc);


	viewCellInterior->GetPvs().Merge(backVc->GetPvs());
	viewCellInterior->GetPvs().Merge(frontVc->GetPvs());

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

	viewCellInterior->SetVolume(volume);

	return viewCellInterior;
}


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



KdViewCellsManager::KdViewCellsManager(KdTree *kdTree):
ViewCellsManager(), 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::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 output
		const int raysOut = min((int)sampleRays.size(), mVisualizationSamples);
		Debug << "visualization using " << raysOut << " samples" << endl;

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

		for (int i = 0; i < leafOut; ++ i)
			kdLeaves.push_back(dynamic_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;

			//bspLeaves[j]->Mail();
			char s[64]; sprintf(s, "kd-pvs%04d.x3d", i);

			Exporter *exporter = Exporter::GetExporter(s);
			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();

			ObjectPvsMap::iterator it, it_end = vc->GetPvs().mEntries.end();
			// output PVS of view cell
			for (it = vc->GetPvs().mEntries.begin(); it !=  it_end; ++ it)
			{
				Intersectable *intersect = (*it).first;
				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 (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 s[64];
			sprintf(s, "sample-pvs%04d.x3d", k);

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

			KdPvsMap::iterator i = object->mKdPvs.mEntries.begin();
			Intersectable::NewMail();

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

			for (; i != object->mKdPvs.mEntries.end(); i++)
			{
				KdNode *node = (*i).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);

			delete exporter;
		}
	}
}


void KdViewCellsManager::ExportColor(Exporter *exporter,
									 ViewCell *vc) const
{
	// TODO
}


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


void KdViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
												ViewCell *vc,
												const Plane3 *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 = dynamic_cast<KdViewCell *>(*it);
	
		exporter->ExportBox(mKdTree->GetBox(kdVc->mLeaf));
	}
}


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


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



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


/**********************************************************************/
/*                   VspKdViewCellsManager implementation             */
/**********************************************************************/


VspKdViewCellsManager::VspKdViewCellsManager(VspKdTree *vspKdTree):
ViewCellsManager(), mVspKdTree(vspKdTree)
{
	environment->GetIntValue("VspKdTree.Construction.samples", mInitialSamples);
	mVspKdTree->SetViewCellsManager(this);
}

float VspKdViewCellsManager::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 VspKdViewCellsManager::CollectViewCells()
{
	mVspKdTree->CollectViewCells(mViewCells);
}


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

	VssRayContainer constructionRays;
	VssRayContainer savedRays;

	GetRaySets(rays,
			   mInitialSamples,
			   constructionRays,
			   &savedRays);

	Debug << "constructing vsp kd tree using "
		  << (int)constructionRays.size() << " samples" << endl;

	mVspKdTree->Construct(constructionRays, &mViewSpaceBox);
	Debug << mVspKdTree->GetStatistics() << endl;

	// export leaf building blocks
	ExportLeaves(objects, rays);

	// finally merge kd leaf building blocks to view cells
	const int merged = mVspKdTree->MergeViewCells(rays);

	// collapse siblings belonging to the same view cell
	mVspKdTree->RefineViewCells(rays);

	// collapse siblings belonging to the same view cell
	mVspKdTree->CollapseTree();

	// evaluale view cell stats
	ResetViewCells();

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

	long startTime = GetTime();

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

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

	return merged;
}

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


ViewCell *VspKdViewCellsManager::GenerateViewCell(Mesh *mesh) const
{
	return new VspKdViewCell(mesh);
}

int VspKdViewCellsManager::PostProcess(const ObjectContainer &objects,
									   const VssRayContainer &rays)
{
	if (!ViewCellsConstructed())
		return 0;

	// recalculate stats
	EvaluateViewCellsStats();

	return 0;
}


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

	//-- export leaf building blocks
	Exporter *exporter = Exporter::GetExporter("vspkdtree.x3d");
	if (!exporter)
		return;

	if (mExportGeometry)
		exporter->ExportGeometry(objects);
	
	//exporter->SetWireframe();
	//exporter->ExportVspKdTree(*mVspKdTree, mVspKdTree->GetStatistics().maxPvsSize);
	exporter->ExportVspKdTree(*mVspKdTree);

	if (mExportRays)
	{
		const float prob = (float)mVisualizationSamples
			/ ((float)sampleRays.size() + Limits::Small);

		exporter->SetWireframe();

		//-- collect uniformly distributed rays
		VssRayContainer rays;

		for (int i = 0; i < sampleRays.size(); ++ i)
		{
			if (RandomValue(0,1) < prob)
				rays.push_back(sampleRays[i]);
		}
		exporter->ExportRays(rays, RgbColor(1, 0, 0));
	}

	delete exporter;
}

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

	//-- export single view cells
	for (int i = 0; i < 10; ++ i)
	{
		char s[64];
		sprintf(s, "vsp_viewcell%04d.x3d", i);
		Exporter *exporter = Exporter::GetExporter(s);
		const int idx =
			(int)RandomValue(0.0, (Real)((int)mViewCells.size() - 1));

		VspKdViewCell *vc = dynamic_cast<VspKdViewCell *>(mViewCells[idx]);

		//-- export geometry
		Material m;
		m.mDiffuseColor = RgbColor(0, 1, 1);

		exporter->SetForcedMaterial(m);
		exporter->SetWireframe();

		ExportViewCellGeometry(exporter, vc);

		//-- export stored rays
		
		if (mExportRays)
		{
			ViewCellContainer leaves;
			mViewCellsTree->CollectLeaves(vc, leaves);

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

			for (it = leaves.begin(); it != it_end; ++ it)
			{
				VspKdViewCell *vspKdVc = dynamic_cast<VspKdViewCell *>(*it);
				VspKdLeaf *leaf = vspKdVc->mLeaf;
				AxisAlignedBox3 box = mVspKdTree->GetBBox(leaf);

				VssRayContainer vssRays;

				VssRayContainer castRays;
				VssRayContainer initRays;

				leaf->GetRays(vssRays);

				VssRayContainer::const_iterator it, it_end = vssRays.end();
				const float prop = 200.0f / (float)vssRays.size();

				for (it = vssRays.begin(); it != it_end; ++ it)
				{
					if (Random(1) < prop)
						if ((*it)->mTerminationObject == NULL)
							castRays.push_back(*it);
						else
							initRays.push_back(*it);
				}

				exporter->ExportRays(castRays, RgbColor(1, 0, 0));
				exporter->ExportRays(initRays, RgbColor(0, 1, 0));
			}
		}
	
		//-- output PVS of view cell
		m.mDiffuseColor = RgbColor(1, 0, 0);
		exporter->SetForcedMaterial(m);

		Intersectable::NewMail();

		ObjectPvsMap::const_iterator it,
			it_end = vc->GetPvs().mEntries.end();

		exporter->SetFilled();

		for (it = vc->GetPvs().mEntries.begin(); it != it_end; ++ it)
		{
			Intersectable *intersect = (*it).first;

			if (!intersect->Mailed())
			{
				Material m = RandomMaterial();
				exporter->SetForcedMaterial(m);

				exporter->ExportIntersectable(intersect);
				intersect->Mail();
			}
		}

		delete exporter;
	}

	//-- export final view cells
	Exporter *exporter = Exporter::GetExporter("vspkdtree_merged.x3d");

	//if (exportGeometry) exporter->SetWireframe();
	//else exporter->SetFilled();

	ExportViewCellsForViz(exporter);

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

	if (mExportRays)
	{
		const float prob = (float)mVisualizationSamples
			/ ((float)sampleRays.size() + Limits::Small);

		exporter->SetWireframe();

		VssRayContainer rays;

		for (int i = 0; i < sampleRays.size(); ++ i)
		{
		  if (RandomValue(0,1) < prob)
			rays.push_back(sampleRays[i]);
		}
		exporter->ExportRays(rays, RgbColor(1, 0, 0));
	}

	delete exporter;
}

int VspKdViewCellsManager::GetType() const
{
	return VSP_KD;
}


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


void VspKdViewCellsManager::ExportColor(Exporter *exporter,
										ViewCell *vc) const
{
	if (mColorCode == 0) // Random color
		return;

	float importance = 0;

	switch (mColorCode)
	{
	case 1: // pvs
		{
			importance = (float)vc->GetPvs().GetSize() /
				(float)mCurrentViewCellsStats.maxPvs;
		}
		break;
	case 2: // merged leaves
		{
        	int lSize = mViewCellsTree->GetSize(vc);
			importance = (float)lSize /
				(float)mCurrentViewCellsStats.maxLeaves;
		}
		break;
	case 3: // merged tree depth difference
		{
			//importance = (float)GetMaxTreeDiff(vc) /
			//	(float)(mVspBspTree->GetStatistics().maxDepth * 2);
		}
		break;
	default:
		break;
	}

	Material m;
	m.mDiffuseColor.b = 1.0f;
	m.mDiffuseColor.r = importance;
	m.mDiffuseColor.g = 1.0f - m.mDiffuseColor.r;
	//Debug << "importance: " << importance << endl;
	exporter->SetForcedMaterial(m);
}


void VspKdViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
												   ViewCell *vc,
												   const Plane3 *clipPlane) const
{
	VspKdViewCell *kdVc = dynamic_cast<VspKdViewCell *>(vc);

	Mesh m;

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

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

	for (it = leaves.begin(); it != it_end; ++ it)
	{
		VspKdLeaf *l = dynamic_cast<VspKdViewCell *>(*it)->mLeaf;
		mVspKdTree->GetBBox(l).AddBoxToMesh(&m);
	}

	exporter->ExportMesh(&m);
}


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


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


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


VspBspViewCellsManager::VspBspViewCellsManager(VspBspTree *vspBspTree):
ViewCellsManager(), mVspBspTree(vspBspTree)
{
	environment->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);
	}
}


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)
{
	// 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: " << (int)constructionRays.size() << endl;
	Debug << "saved rays: " << (int)savedRays.size() << endl;

	mMaxPvsSize = (int)(mMaxPvsRatio * (float)objects.size());

	//TODO: remove
	if (1)
		mVspBspTree->Construct(constructionRays, &mViewSpaceBox);
	else
		mVspBspTree->Construct(rays, &mViewSpaceBox);

	// collapse invalid regions
	cout << "collapsing invalid tree regions ... ";
	long startTime = GetTime();
	int collapsedLeaves = mVspBspTree->CollapseTree();
	Debug << "collapsed in " << TimeDiff(startTime, GetTime()) * 1e-3 
		  << " seconds" << endl;

    cout << "finished" << endl;

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

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


	startTime = GetTime();

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

	// recast rest of rays
	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;

	return sampleContributions;
}


void VspBspViewCellsManager::MergeViewCells(const VssRayContainer &rays,
											const ObjectContainer &objects)
{
	//-- post processing of bsp view cells
    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
		mViewCellsTree->ConstructMergeTree(rays, objects);
	}
	else
	{
		mViewCellsTree->SetRoot(ConstructSpatialMergeTree(mVspBspTree->GetRoot()));
	}

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

	//-- stats and visualizations
	cout << "finished merging" << 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;
	

	int savedColorCode = mColorCode;
	
	// get currently active view cell set
	ResetViewCells();
	Debug << "\nView cells after merge:\n" << mCurrentViewCellsStats << endl;

	//BspLeaf::NewMail();
	if (1) // export merged view cells
	{
		mColorCode = 0;
		Exporter *exporter = Exporter::GetExporter("merged_view_cells.x3d");
		
		cout << "exporting view cells after merge ... ";

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

			ExportViewCellsForViz(exporter);

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

				exporter->ExportGeometry(objects);
			}

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

	if (1) // export merged view cells using pvs coding
	{
		mColorCode = 1;

		Exporter *exporter = Exporter::GetExporter("merged_view_cells_pvs.x3d");
	
		cout << "exporting view cells after merge (pvs size) ... ";	

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

			ExportViewCellsForViz(exporter);

			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;

}


bool VspBspViewCellsManager::EqualToSpatialNode(ViewCell *viewCell) const
{
	return GetSpatialNode(viewCell) != NULL;
}


BspNode *VspBspViewCellsManager::GetSpatialNode(ViewCell *viewCell) const
{
	if (!viewCell->IsLeaf())
	{
		BspViewCell *bspVc = dynamic_cast<BspViewCell *>(viewCell);

		return bspVc->mLeaf;
 	}
	else
	{
		ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(viewCell);

		// cannot be node of binary tree
		if (interior->mChildren.size() != 2)
			return NULL;

		ViewCell *left = interior->mChildren[0];
		ViewCell *right = interior->mChildren[1];

		BspNode *leftNode = GetSpatialNode(left);
		BspNode *rightNode = GetSpatialNode(right);

		if (leftNode && rightNode && leftNode->IsSibling(rightNode))
		{
			return leftNode->GetParent(); 
		}
	}

	return NULL;
}


void VspBspViewCellsManager::RefineViewCells(const VssRayContainer &rays,
											 const ObjectContainer &objects)
{
	Debug << "render time before refine:" << endl;
	mRenderer->RenderScene();
	SimulationStatistics ss;
	dynamic_cast<RenderSimulator *>(mRenderer)->GetStatistics(ss);
    Debug << ss << endl;

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

	// 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
	SetValidity(mMinPvsSize, mMaxPvsSize); 
	// update valid view space according to valid view cells
	mVspBspTree->ValidateTree();

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

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


	// should maybe be done here to allow merge working with area or volume
	// and to correct the rendering statistics
	if (0)
	{
		FinalizeViewCells(false);
	}

	//-- merge the individual view cells
	MergeViewCells(postProcessRays, objects);
	
	// only for testing
	TestSubdivision();

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


	//-- render simulation after merge + refine
	
	cout << "\nevaluating bsp view cells render time before compress ... ";
	dynamic_cast<RenderSimulator *>(mRenderer)->RenderScene();
	SimulationStatistics ss;
	dynamic_cast<RenderSimulator *>(mRenderer)->GetStatistics(ss);
  

	cout << " finished" << endl;
	cout << ss << endl;
	Debug << ss << endl;


	//-- compression

	if (ViewCellsTreeConstructed() && mCompressViewCells)
	{
		int pvsEntries = mViewCellsTree->GetNumPvsEntries(mViewCellsTree->GetRoot());
		Debug << "number of entries before compress: " << pvsEntries << endl;

		mViewCellsTree->CompressViewCellsPvs();

		pvsEntries = mViewCellsTree->GetNumPvsEntries(mViewCellsTree->GetRoot());
		Debug << "number of entries after compress: " << pvsEntries << endl;
	}


	// collapse sibling leaves that share the same view cell
	if (0)
		mVspBspTree->CollapseTree();

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

	// real meshes are only contructed only at this stage
	FinalizeViewCells(true);

	// write view cells to disc
	if (mExportViewCells)
	{
		char buff[100];
		environment->GetStringValue("ViewCells.filename", buff);
		string vcFilename(buff);

		ExportViewCells(buff);
	}

	return 0;
}


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


ViewCell *VspBspViewCellsManager::ConstructSpatialMergeTree(BspNode *root)
{
	if (root->IsLeaf())
	{
		ViewCell *viewCell = dynamic_cast<BspLeaf *>(root)->GetViewCell();

		viewCell->SetMergeCost(0.0f);

		return viewCell;
	}
	
	BspInterior *interior = dynamic_cast<BspInterior *>(root);
	ViewCellInterior *viewCellInterior = new ViewCellInterior();
		
	float mergeCost = 1.0f / (float)root->mTimeStamp;
	//Debug << "timestamp: " << root->mTimeStamp;
	//Debug << "merge cost: " << mergeCost << endl;

	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(frontVc);
	viewCellInterior->SetupChildLink(backVc);


	viewCellInterior->GetPvs().Merge(backVc->GetPvs());
	viewCellInterior->GetPvs().Merge(frontVc->GetPvs());

	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 view cells
	{	// hack pvs
		int savedColorCode = mColorCode;
		mColorCode = 0;
		Exporter *exporter = Exporter::GetExporter("final_view_cells.x3d");
		
		if (exporter)
		{
			cout << "exporting view cells after post process ... ";

			if (0)
			{
				exporter->SetWireframe();
				exporter->ExportBox(mViewSpaceBox);
				exporter->SetFilled();
			}

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

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

			ExportViewCellsForViz(exporter);
			delete exporter;
			cout << "finished" << endl;
		}

		mColorCode = savedColorCode;
	}

	if (0)
	{
		cout << "exporting depth map ... ";

		Exporter *exporter = Exporter::GetExporter("depth_map.x3d");
		if (exporter)
		{
			if (1)
			{
				exporter->SetWireframe();
				exporter->ExportBox(mViewSpaceBox);
				exporter->SetFilled();
			}

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

			const int maxDepth = mVspBspTree->mBspStats.maxDepth;

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

			for (vit = mViewCells.begin(); vit != mViewCells.end(); ++ vit)
			{
				ViewCell *vc = *vit;

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

				ViewCellContainer::const_iterator lit, lit_end = leaves.end();

				for (lit = leaves.begin(); lit != lit_end; ++ lit)
				{
					BspLeaf *leaf = dynamic_cast<BspViewCell *>(*lit)->mLeaf;

					Material m; 

					float relDepth = (float)leaf->GetDepth() / (float)maxDepth;
					m.mDiffuseColor.r = relDepth;
					m.mDiffuseColor.g = 0.0f;
					m.mDiffuseColor.b = 1.0f - relDepth;

                    exporter->SetForcedMaterial(m);
				

					BspNodeGeometry geom;
					mVspBspTree->ConstructGeometry(leaf, geom);
					exporter->ExportPolygons(geom.GetPolys());
				}
			}

			delete exporter;
		}


		cout << "finished" << endl;
	}

	//-- visualization of the BSP splits
	bool exportSplits = false;
	environment->GetBoolValue("VspBspTree.Visualization.exportSplits", exportSplits);

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

	//-- export single view cells
	ExportBspPvs(objects, visRays);
}


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::ExportBspPvs(const ObjectContainer &objects,
										  const VssRayContainer &rays)
{
	const int leafOut = 20;

	ViewCell::NewMail();

	cout << "visualization using " << (int)rays.size() << " samples" << endl;
	Debug << "visualization using " << (int)rays.size() << " samples" << endl;
	Debug << "\nOutput view cells: " << endl;

	const bool sortViewCells = true;

	// sort view cells to visualize the largest view cells
	if (sortViewCells)
		stable_sort(mViewCells.begin(), mViewCells.end(), vc_gt);
	
	int limit = min(leafOut, (int)mViewCells.size());

	int raysOut = 0;

	//-- some rays for output
	for (int i = 0; i < limit; ++ i)
	{
		cout << "creating output for view cell " << i << " ... ";

		ViewCell *vc;
	
		if (sortViewCells) // largest view cell pvs first
			vc = mViewCells[i];
		else
			vc = mViewCells[(int)RandomValue(0, (float)mViewCells.size() - 1)];

		//bspLeaves[j]->Mail();
		char s[64]; sprintf(s, "bsp-pvs%04d.x3d", i);
		Exporter *exporter = Exporter::GetExporter(s);
		
		Debug << i << ": pvs size=" << (int)mViewCellsTree->GetPvsSize(vc) << endl;

		if (1 || mExportRays)
		{
			// output rays stored with the view cells during subdivision
			if (0)
			{
				VssRayContainer vcRays;
                VssRayContainer collectRays;

				raysOut = min((int)rays.size(), 100);

				// 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)
				{
					BspLeaf *vcLeaf = dynamic_cast<BspViewCell *>(*vit)->mLeaf;
				
					VssRayContainer::const_iterator rit, rit_end = vcLeaf->mVssRays.end();

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

				VssRayContainer::const_iterator rit, rit_end = collectRays.end();

				for (rit = collectRays.begin(); rit != rit_end; ++ rit)
				{
					float p = RandomValue(0.0f, (float)collectRays.size());
			
					if (p < raysOut)
						vcRays.push_back(*rit);
				}
				//-- export rays piercing this view cell
				exporter->ExportRays(vcRays, RgbColor(1, 1, 1));
			}
		
			// associate new rays with output view cell
			if (1)
			{
				VssRayContainer vcRays;
				raysOut = min((int)rays.size(), mVisualizationSamples);
				// check whether we can add the current ray to the output rays
				for (int k = 0; k < raysOut; ++ k)
				{
					VssRay *ray = rays[k];
					for	(int j = 0; j < (int)ray->mViewCells.size(); ++ j)
					{
						ViewCell *rayvc = ray->mViewCells[j];
	
						if (rayvc == vc)
							vcRays.push_back(ray);
					}
				}	
				
				//-- export rays piercing this view cell
				exporter->ExportRays(vcRays, RgbColor(1, 1, 0));
			}

		}
		

		exporter->SetWireframe();

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

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


		if (1)
		{
			ObjectPvsMap::const_iterator oit,
				oit_end = vc->GetPvs().mEntries.end();


			exporter->SetFilled();

			Intersectable::NewMail();
	
			// output PVS of view cell
			for (oit = vc->GetPvs().mEntries.begin(); oit != oit_end; ++ oit)
			{		
				Intersectable *intersect = (*oit).first;

				if (!intersect->Mailed())
				{
					m = RandomMaterial();
					exporter->SetForcedMaterial(m);

					exporter->ExportIntersectable(intersect);
					intersect->Mail();
				}
			}
		}
		else
		{
			m.mDiffuseColor = RgbColor(1, 0, 0);
			exporter->SetForcedMaterial(m);

			exporter->ExportGeometry(objects);
		}

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

	Debug << endl;
}


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


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

	float importance = 0;
	static Material m;

	switch (mColorCode)
	{
	case 0: // Random
		{
			if (vcValid)
			{
				m.mDiffuseColor.r = 0.5f + RandomValue(0.0f, 0.5f);
				m.mDiffuseColor.g = 0.5f + RandomValue(0.0f, 0.5f);
				m.mDiffuseColor.b = 0.5f + RandomValue(0.f, 0.5f);
			}
			else
			{
				m.mDiffuseColor.r = 0.0f;
				m.mDiffuseColor.g = 1.0f;
				m.mDiffuseColor.b = 0.0f;
			}

			exporter->SetForcedMaterial(m);
			return;
		}
		
	case 1: // pvs
		{
			importance = (float)vc->GetPvs().GetSize() /
				(float)mCurrentViewCellsStats.maxPvs;

		}
		break;
	case 2: // merges
		{
            int lSize = mViewCellsTree->GetSize(vc);
			importance = (float)lSize / (float)mCurrentViewCellsStats.maxLeaves;
		}
		break;
	case 3: // merge tree differene
		{
			importance = (float)GetMaxTreeDiff(vc) /
				(float)(mVspBspTree->GetStatistics().maxDepth * 2);

		}
		break;
	default:
		break;
	}

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

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


void VspBspViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
                                                    ViewCell *vc,
													const Plane3 *clipPlane) const
{
	if (vc->GetMesh())
	{
		exporter->ExportMesh(vc->GetMesh());
	
		return;
	}

	
	if (clipPlane)
	{
		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;

			BspLeaf *leaf = dynamic_cast<BspViewCell *>(*it)->mLeaf;
			mVspBspTree->ConstructGeometry(leaf, geom);

			const int cf = Polygon3::ClassifyPlane(geom.GetPolys(), *clipPlane, 0.00000001f);

			if (cf == Polygon3::BACK_SIDE)
			{
				exporter->ExportPolygons(geom.GetPolys());
			}
			else if (cf == Polygon3::SPLIT)
			{
				geom.SplitGeometry(front,
								   back,
								   *clipPlane,
								   mViewSpaceBox, 
								   0.00000001f);
	
				//Debug << "geo size: " << geom.Size() << endl;
				//Debug << "size b: " << back.Size() << " f: " << front.Size() << endl;
				if (back.Valid())
				{
					exporter->ExportPolygons(back.GetPolys());
				}
			
			}
		}
	}
	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 = dynamic_cast<BspViewCell *>(leaves[i])->mLeaf;

		if (i != j)
		{
			BspLeaf *leaf2 =dynamic_cast<BspViewCell *>(leaves[j])->mLeaf;
			int dist = mVspBspTree->TreeDistance(leaf, leaf2);
			if (dist > maxDist)
				maxDist = dist;
		}
	}

	return maxDist;
}


ViewCell *VspBspViewCellsManager::GetViewCell(const Vector3 &point) const
{
	if (!mVspBspTree)
		return NULL;

	if (!mViewSpaceBox.IsInside(point))
	  return NULL;

	return mVspBspTree->GetViewCell(point);
}


void VspBspViewCellsManager::CreateMesh(ViewCell *vc)
{
	if (vc->GetMesh())
		delete vc->GetMesh();

	
	BspNodeGeometry geom;

	mVspBspTree->ConstructGeometry(vc, geom);
	
	Mesh *mesh = new Mesh();
	geom.AddToMesh(*mesh);
	vc->SetMesh(mesh);
	mMeshContainer.push_back(mesh);
}


ViewCellsManager *ViewCellsManager::LoadViewCells(const string filename, 
												  ObjectContainer *objects)
{
	ViewCellsParser parser;

	ViewCellsManager *vm = NULL;

	if (parser.ParseFile(filename, &vm, objects))
	{
		//vm->PrepareLoadedViewCells();
		vm->ResetViewCells();

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

		vm->FinalizeViewCells(true);

		vm->mViewCellsTree->AssignRandomColors();
		Debug << (int)vm->mViewCells.size() << " view cells loaded" << endl;
	}
	else
	{
		Debug << "failed loading view cells" << endl;
		DEL_PTR(vm);
	}


	return vm;
}


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


bool VspBspViewCellsManager::ExportViewCells(const string filename)
{
	cout << "exporting view cells to xml ... ";
	std::ofstream stream;

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

	stream.open(filename.c_str());
	stream << "<?xml version=\"1.0\" encoding=\"UTF-8\"?>"<<endl;
	stream << "<Visibility_Solution>" << endl;

	//-- the view space bounding box
	stream << "<ViewSpaceBox" 
		   << " min=\"" << mViewSpaceBox.Min().x << " " << mViewSpaceBox.Min().y << " " << mViewSpaceBox.Min().z << "\""
		   << " max=\"" << mViewSpaceBox.Max().x << " " << mViewSpaceBox.Max().y << " " << mViewSpaceBox.Max().z << "\" />" << endl;

	//-- the type of the view cells hierarchy
	stream << "<Hierarchy name=\"vspBspTree\" />" << endl;

	//-- load the view cells itself, i.e., the ids and the pvs
	stream << "<ViewCells>" << endl;
	
#if 0
	
	ViewCellContainer::const_iterator it, it_end = mViewCells.end();
		
	for (it = mViewCells.begin(); it != it_end; ++ it)
		ExportViewCell(*it, stream);
#else
	mViewCellsTree->Export(stream);
#endif

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

	//-- load the hierarchy
	stream << "<Hierarchy>" << endl;
	mVspBspTree->Export(stream);
	stream << endl << "</Hierarchy>" << endl;

	stream << "</Visibility_Solution>" << endl;
	stream.close();

	cout << "finished" << endl;

	return true;
}


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;
		BspLeaf *leaf = dynamic_cast<BspViewCell *>(*it)->mLeaf;
		mVspBspTree->ConstructGeometry(leaf, geom);

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

		//(*it)->SetVolume(vol);
		//(*it)->SetArea(area);

		area += lArea;
		volume += lVol;

        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;
		BspLeaf *leaf = dynamic_cast<BspViewCell *>(*it)->mLeaf;
		mVspBspTree->ConstructGeometry(leaf, geom);

		const float lVol = geom.GetVolume();
		
		newVol += lVol;
		subdivVol += (*it)->GetVolume();
		
		float thres = 0.9;
		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();
}


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

	if (exporter)
	{
		AxisAlignedBox3 testBox = mViewSpaceBox;
		Vector3 bsize = mViewSpaceBox.Size();

		testBox.Enlarge(Vector3(-bsize[0] * 0.3, 0, -bsize[2] * 0.4));
		
		ViewCellContainer viewCells;
        
		mVspBspTree->ComputeBoxIntersections(testBox, viewCells);
		cout << "view cells: " << viewCells.size() << endl;
		
		exporter->SetWireframe();

		exporter->SetForcedMaterial(RgbColor(1,1,1));
		exporter->ExportBox(testBox);
		
		exporter->SetFilled();
		exporter->ResetForcedMaterial();
        for (int i = 0; i < viewCells.size(); ++ i)
		{
			BspNodeGeometry geom;
				
			mVspBspTree->ConstructGeometry(viewCells[i], geom);
			exporter->ExportPolygons(geom.GetPolys());
		}		

		exporter->SetForcedMaterial(RgbColor(1,0,0));
		exporter->ExportGeometry(objects);

		delete exporter;
	}
}


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


void VspBspViewCellsManager::AddCurrentViewCellsToHierarchy()
{
	ViewCellContainer::const_iterator it, it_end = mViewCells.end();
	for (it = mViewCells.begin(); it != it_end; ++ it)
	{
	}
}

//////////////////////////////////
ViewCellsManager *ViewCellsManagerFactory::Create(const string mName)
{
	//TODO
	return NULL;// new VspBspViewCellsManager();
}