#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 "VspOspTree.h"
#include "Exporter.h"
#include "VspBspTree.h"
#include "ViewCellsParser.h"
#include "Beam.h"
#include "VssPreprocessor.h"
#include "RssPreprocessor.h"
#include "BoundingBoxConverter.h"
#include "GlRenderer.h"
#include "ResourceManager.h"
#include "KdIntersectable.h"

// should not count origin object for sampling because it disturbs heuristics
#define SAMPLE_ORIGIN_OBJECTS 0

namespace GtpVisibilityPreprocessor {


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


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


ViewCellsManager::ViewCellsManager():
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),
mViewCellPvsIsUpdated(false),
mPreprocessor(NULL),
mStoreKdPvs(false)
{
	mViewSpaceBox.Initialize();
	ParseEnvironment();

	mViewCellsTree = new ViewCellsTree(this);
}


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

	// HACK
	if (0)
		mMinPvsSize = mPruneEmptyViewCells ? 1 : 0;
	else
		mMinPvsSize = 0;

	Environment::GetSingleton()->GetBoolValue("ViewCells.processOnlyValidViewCells", mOnlyValidViewCells);

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

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

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

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


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

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

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

	Environment::GetSingleton()->GetStringValue("ViewCells.renderCostEvaluationType", buf);
	
	if (strcmp(buf, "perobject") == 0)
	{
		mRenderCostEvaluationType = ViewCellsManager::PER_OBJECT;
	}
	else if (strcmp(buf, "directional") == 0)
	{
		mRenderCostEvaluationType = ViewCellsManager::PER_TRIANGLE;
	}
	else 
	{
		Debug << "error! wrong sampling type" << endl;
		exit(0);
	}

    Environment::GetSingleton()->GetStringValue("ViewCells.Visualization.colorCode", buf);

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



	Debug << "************ View Cells 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: " << mPruneEmptyViewCells << endl;
	
	Debug << "process only valid view cells: " << mOnlyValidViewCells << endl;
	Debug << "construction samples: " << mConstructionSamples << endl;
	Debug << "post process samples: " << mPostProcessSamples << endl;
	Debug << "post process use rays for merge: " << mUseRaysForMerge << endl;
	Debug << "visualization samples: " << mVisualizationSamples << endl;
	Debug << "construction samples per pass: " << mSamplesPerPass << endl;
	Debug << "export to file: " << mExportViewCells << endl;
	
	Debug << "active view cells: " << mNumActiveViewCells << endl;
	Debug << "post process compress: " << mCompressViewCells << endl;
	Debug << "visualization use clipPlane: " << mUseClipPlaneForViz << endl; 
	Debug << "post process merge: " << mMergeViewCells << endl;
	Debug << "evaluate view cells: " << mEvaluateViewCells << endl;
	Debug << "sampling type: " << mSamplingType << endl;
	Debug << "render cost evaluation type: " << mRenderCostEvaluationType << endl;
	Debug << "evaluation sampling type: " << mEvaluationSamplingType << endl;
	Debug << "show visualization: " << mShowVisualization << endl;
	Debug << "filter width: " << mFilterWidth << endl;
	Debug << "sample after subdivision: " << SAMPLE_AFTER_SUBDIVISION << endl;

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

	Debug << endl;
}


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

	DEL_PTR(mViewCellsTree);
}


AxisAlignedBox3 ViewCellsManager::GetViewCellBox(ViewCell *vc)
{
  Mesh *m = vc->GetMesh();
  
  if (m) {
	m->ComputeBoundingBox();
	return m->mBox;
  }

  AxisAlignedBox3 box;
  
  box.Initialize();
  
  if (!vc->IsLeaf()) {
	ViewCellInterior *vci = (ViewCellInterior *) vc;
	
	ViewCellContainer::iterator it = vci->mChildren.begin();
	for (; it != vci->mChildren.end(); ++it) {
	  box.Include(GetViewCellBox(*it));
	}
  }
  
  return box;
}

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


bool ViewCellsManager::EqualToSpatialNode(ViewCell *viewCell) const 
{ 
	return false;
}


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().CountObjectsInPvs() << " " << (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;

	const long startTime = GetTime();

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

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

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

	return (int)passSamples.size();
}


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

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

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

		for (it = rays.begin(); it != it_end; ++ it)
		{
			//(*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)
{
	mPreprocessor = preprocessor;

	int numSamples = 0;

	SimpleRayContainer simpleRays;
	VssRayContainer initialSamples;

	cout << "view cell construction: casting " << mInitialSamples << " initial samples ... ";

	long startTime = GetTime();

	//-- construction rays => we use uniform samples for this
	CastPassSamples(mInitialSamples, mSamplingType,	initialSamples);
	
	cout << "finished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;

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

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

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

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

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


	// take post processing time
	startTime = GetTime();

	// -- stats after contruction
	ResetViewCells();
  	Debug << "\nView cells after initial sampling:\n" << mCurrentViewCellsStats << endl;


	if (0) // export initial view cells
	{
		const char filename[] = "view_cells.wrl";
		Exporter *exporter = Exporter::GetExporter(filename);

	
		if (exporter)
		{
			cout << "exporting initial view cells (=leaves) to " << filename << " ... ";
			if (mExportGeometry)
			{
				exporter->ExportGeometry(preprocessor->mObjects);
			}

			exporter->SetWireframe();
			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);

	//-- do some more sampling
	while (numSamples < n)
	{
		cout << "casting " << mSamplesPerPass << " samples of " << n << " ... ";
		Debug << "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

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

		cout << "finished" << endl;

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

		// computes sample contribution of cast rays 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;

	cout << "casting " << mPostProcessSamples << " post processing samples ... ";

	// cast post processing samples rays  (storing the view cells if wanted)
	CastPassSamples(mPostProcessSamples,
					mSamplingType, 
					postProcessSamples);

	cout << "finished" << endl;

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

	//-- post processing (e.g.,merging) of the view cells
	if (1) PostProcess(preprocessor->mObjects, postProcessSamples);

	cout << "time needed for post processing (merge) step: "
		 << TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl;

	Debug << "time needed for post processing (merge) step: "
		 << TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl;

	disposeRays(postProcessSamples, outRays);

	
	//return 1;
	// evaluation of the paritition, i.e., a number of new samples are cast
	if (mEvaluateViewCells)
	{
		EvalViewCellPartition();
	}


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

	return numSamples;
}


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

	ViewCellContainer viewCells;
	mViewCellsTree->CollectBestViewCellSet(viewCells, nViewCells);

	float maxRenderCost, minRenderCost;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

	outstream.close();
}



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

	ViewCellsManager *vm = NULL;

	if (parser.ParseViewCellsFile(filename, &vm, objects, bconverter))
	{
		long startTime = GetTime();

		//vm->PrepareLoadedViewCells();
		vm->ResetViewCells();

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

		// create the meshes and compute volumes
		if (finalizeViewCells)
		{
			vm->FinalizeViewCells(true);
			vm->mViewCellsTree->AssignRandomColors();
		}

		Debug << (int)vm->mViewCells.size() << " view cells loaded in "
			  << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
	}
	else
	{
		Debug << "Error: loading view cells failed!" << endl;
		DEL_PTR(vm);
	}

	return vm;
}


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

	cout << "exporting view cells to xml ... ";
	
	OUT_STREAM stream(filename.c_str());

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

	stream << "<?xml version=\"1.0\" encoding=\"UTF-8\"?>"<<endl;
	stream << "<VisibilitySolution>" << 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;

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

	ObjectContainer::const_iterator oit, oit_end = objects.end();

	for (oit = objects.begin(); oit != oit_end; ++ oit)
	{
			MeshInstance *mi = dynamic_cast<MeshInstance *>(*oit);
			const AxisAlignedBox3 box = mi->GetBox();

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

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

	//-- export the view cells and the pvs
	stream << "<HierarchyType name=\"vspBspTree\" />" << endl;

	const int numViewCells = mCurrentViewCellsStats.viewCells;

	stream << "<ViewCells number=\"" << numViewCells << "\" >" << endl;
	
	mViewCellsTree->Export(stream, exportPvs);

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


	//-- export the spatial hierarchy
	
	// the type of the view cells hierarchy
	stream << "<Hierarchy>" << endl;
	mVspBspTree->Export(stream);
	stream << endl << "</Hierarchy>" << endl;

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


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

	return true;
}


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

	ViewCellContainer viewCells;
	mViewCellsTree->CollectBestViewCellSet(viewCells, nViewCells);

	int maxPvs, maxVal, minVal;

	// sort by pvs size
	sort(viewCells.begin(), viewCells.end(), ViewCell::SmallerPvs);

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

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

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

	const int range = maxVal - minVal;
	int stepSize = range / intervals;

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

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

	int currentPvs = minVal;//(int)ceil(minRenderCost);

	
	int i = 0;
	int j = 0;

	float volSum = 0;
	int smallerSum = 0;

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

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

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

		outstream << "#Pass\n" << j << endl;
		outstream << "#Pvs\n" << currentPvs << endl;
		outstream << "#ViewCellsDif\n" << smallerDif << endl;
		outstream << "#ViewCellsSum\n" << smallerSum << endl;	
		outstream << "#VolumeDif\n" << volRatioDif << endl << endl;
		outstream << "#VolumeSum\n" << volRatioSum << endl << endl;
	
		//if ((i >= (int)viewCells.size()) || (currentPvs >= maxPvs))	break;

		//-- increase current pvs size to define next interval
		currentPvs += stepSize;
	}

	outstream.close();
}


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


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

	char s[64]; 

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

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

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

	// should directional sampling be used?
	bool dirSamples = (mEvaluationSamplingType == Preprocessor::DIRECTION_BASED_DISTRIBUTION);

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

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

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

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

	while (castSamples < numSamples)
	{
		VssRayContainer evaluationSamples;

		const int samplingType = mEvaluationSamplingType;
		/*	dirSamples ? 
						Preprocessor::DIRECTION_BASED_DISTRIBUTION :
				 		Preprocessor::SPATIAL_BOX_BASED_DISTRIBUTION;
		*/
		long startTime = GetTime();

		//-- construction rays => we use uniform samples for this
		cout << "casting " << samplesPerPass << " samples ... ";
		Debug << "casting " << samplesPerPass << " samples ... ";

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

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

		cout << "computing sample contributions of " << (int)evaluationSamples.size()  << " samples ... ";
		Debug << "computing sample contributions of " << (int)evaluationSamples.size()  << " samples ... ";

		startTime = GetTime();

		ComputeSampleContributions(evaluationSamples, true, false);

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

		startTime = GetTime();

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

		//-- propagate pvs or pvs size information
		ObjectPvs pvs;
		UpdatePvsForEvaluation(mViewCellsTree->GetRoot(), pvs);

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

		mViewCellsTree->ExportStats(fileName);

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

	//-- histogram

	bool useHisto;
	int histoStepSize;

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

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


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

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

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

			EvalViewCellHistogram(filename, pass);

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

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

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

			EvalViewCellHistogramForPvsSize(filename, pass);
		}
	}
}


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


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

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

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

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

	return bestViewCellIdx;
}


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


float ViewCellsManager::EvalRenderCost(Intersectable *obj) const
{
	switch (mRenderCostEvaluationType)
	{
	case PER_OBJECT:
		//cout << "perobject" << endl;
		return 1.0f;
	
	case PER_TRIANGLE:
		{//cout << "pertriangle" << endl;
			// HACK
			MeshInstance *mi = dynamic_cast<MeshInstance *>(obj);

			// HACK: assume meshes are triangles
			if (mi->GetMesh())
			{
				return (float)mi->GetMesh()->mFaces.size();
			}
		}
	default:
		cout << "default" << endl;
		return 1.0f;
	}

	// should not come here
	return 0.0f;
}


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

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

	const int n = min(mMaxFilterSize, (int)neighborhood.size());
	//-- use priority queue to merge leaf pairs

	//cout << "neighborhood: " << neighborhood.size() << endl;
	//const float maxAvgCost = 350;
	for (int nMergedViewCells = 0; nMergedViewCells < n; ++ nMergedViewCells)
	{
		const int bestViewCellIdx = GetBestViewCellIdx(root, neighborhood);
		
		ViewCell *bestViewCell = neighborhood[bestViewCellIdx];
	
		// remove from vector
		swap(neighborhood[bestViewCellIdx], neighborhood.back());
		neighborhood.pop_back();
	
		//		cout << "vc idx: " << bestViewCellIdx << endl;
		if (!bestViewCell || !root)
			cout << "warning!!" << endl;
		
		// create new root of the hierarchy
		root = MergeViewCells(root, bestViewCell);
	}

	return root;	
}


struct SortableViewCellEntry {

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

	float mValue;
	ViewCell *mViewCell;

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


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

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


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

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

	return true;
}


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


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


void ViewCellsManager::GetPrVS(const Vector3 &viewPoint,
							   PrVs &prvs,
							   const float filterWidth)
{

	

	
  ViewCell *currentViewCell = GetViewCell(viewPoint);

  if (mMaxFilterSize < 1) {
	prvs.mViewCell = currentViewCell;
	return;
  }
  
  const AxisAlignedBox3 box = GetFilterBBox(viewPoint, filterWidth);
  
  if (currentViewCell) {
	ViewCellContainer viewCells;
	ComputeBoxIntersections(box, viewCells);


	ViewCell *root = ConstructLocalMergeTree2(currentViewCell, viewCells);
	prvs.mViewCell = root;
	
  } else
	prvs.mViewCell = NULL;
  //prvs.mPvs = root->GetPvs();
}


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


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


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


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

void
ViewCellsManager::SetValidityPercentage(
										const float minValid,
										const float maxValid
										)
{
	sort(mViewCells.begin(), mViewCells.end(), ViewCell::SmallerPvs);

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

	for (int i = 0; i < (int)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::GetSingleton()->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 += ComputeSampleContribution(*(*it), addRays, storeViewCells);
  }

  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().CountObjectsInPvs() * vc->GetVolume();
		totalPvs += (int)vc->GetPvs().CountObjectsInPvs();
	}

	// 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().CountObjectsInPvs() * vc->GetVolume();
		float dev;

		if (1)
			dev = fabs(avgRenderCost - (float)vc->GetPvs().CountObjectsInPvs());
		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::DeriveViewCellsFromObjects(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);
		}
		else if (object->Type() == Intersectable::TRANSFORMED_MESH_INSTANCE)
		{
			TransformedMeshInstance *mi = dynamic_cast<TransformedMeshInstance *>(object);

			Mesh *mesh = MeshManager::GetSingleton()->CreateResource();
			
			// transform mesh
			mi->GetTransformedMesh(*mesh);
			
			// create bb + kd tree
			mesh->Preprocess();

			ViewCell *viewCell = GenerateViewCell(mi->GetMesh());
			viewCells.push_back(viewCell);

			break;
		}
	}
}


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

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


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

	vc->GetPvs().Clear();
	vc->GetPvs() = left->GetPvs();

	// merge pvs of right cell
	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());
	}

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

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

	return vc;
}


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

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

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

	return vc;
}


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


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


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


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


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


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


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


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


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


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

	mViewCellPvsIsUpdated = true;

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

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

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


void ViewCellsManager::GetPvsStatistics(PvsStatistics &stat)
{
  // update pvs of view cells tree if necessary
  UpdatePvs();
  
  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;

	  //	  bool mCountKdPvs = false;
	  const int pvsSize = mViewCellsTree->GetPvsSize(viewcell);


	  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;
	
	// hack: create clip plane relative to new view space box
	CreateClipPlane();
	// the total area of the view space has changed
	mTotalAreaValid = false;
}


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

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

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

	if (mUseClipPlaneForViz)
        Environment::GetSingleton()->GetIntValue("ViewCells.Visualization.clipPlaneAxis", axis);

	mClipPlane = AxisAlignedPlane(axis, point[axis]);
}


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


void ViewCellsManager::ResetViewCells()
{
	// recollect view cells
	mViewCells.clear();
	CollectViewCells();
	
	
	// stats are computed once more
	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::ComputeSampleContribution(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);

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

	if (storeViewCells)
	{	// copy viewcells memory efficiently
		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())
		{
			// if ray not outside of view space
			float contribution;
			if (ray.mTerminationObject) {
			  if (viewcell->GetPvs().GetSampleContribution(ray.mTerminationObject,
														   ray.mPdf,
														   contribution))
			  {
				++ ray.mPvsContribution;
			  	  ray.mRelativePvsContribution += contribution;
			  }
			}
			// for directional sampling it is important to count only contributions
			// made in one direction!!!
			// the other contributions of this sample will be counted for the oposite ray!
#if SAMPLE_ORIGIN_OBJECTS
			if (ray.mOriginObject && 
				viewcell->GetPvs().GetSampleContribution(ray.mOriginObject,
														 ray.mPdf,
														 contribution))
			{
				++ ray.mPvsContribution;
				ray.mRelativePvsContribution += contribution;
			}
#endif
		}
	}

	// if addrays is true, sampled entities are stored in the pvs
	if (addRays)
	{
		for (it = viewcells.begin(); it != viewcells.end(); ++ it) 
		{
			ViewCell *viewcell = *it;
            
			if (viewcell->GetValid())
			{
				// if ray not outside of view space

				// add new object to the pvs
				if (ray.mTerminationObject)
				{
					viewcell->GetPvs().AddSample(ray.mTerminationObject, ray.mPdf);
				}				
#if SAMPLE_ORIGIN_OBJECTS
				 if (ray.mOriginObject)
				 {
					 viewcell->GetPvs().AddSample(ray.mOriginObject, ray.mPdf);
				 }
#endif
			}
		}
	}

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


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

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

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

	mTotalAreaValid = true;

	return mTotalArea;
}


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


void ViewCellsManager::CreateUniqueViewCellIds()
{
	if (ViewCellsTreeConstructed())
		mViewCellsTree->CreateUniqueViewCellsIds();
	else
		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, 
									   const bool exportPvs, 
									   const ObjectContainer &objects)
{
	return false;
}


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


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

	for (it = mViewCells.begin(); it != it_end; ++ it)
	{
		ViewCellContainer leaves;
		mViewCellsTree->CollectLeaves(*it, leaves);

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


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


static const bool USE_ASCII = true;


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

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

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

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

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

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

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

	return true;
}


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

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

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

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

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

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

		while (1)
		{
			boxesIn.read(reinterpret_cast<char *>(&id), sizeof(Vector3));
			boxesIn.read(reinterpret_cast<char *>(&bmin), sizeof(Vector3));
			boxesIn.read(reinterpret_cast<char *>(&bmax), sizeof(Vector3));
			
			if (boxesIn.eof())
				break;

			
			AxisAlignedBox3 box(bmin, bmax);
			MeshInstance *mi = new MeshInstance(NULL);

			// HACK: set bounding box to new box
			//mi->mBox = box;
			//boxes.push_back(mi);
			boxes.push_back(IndexedBoundingBox(id, box));
		}

		boxesIn.close();
	}

	return true;
}


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


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


void ViewCellsManager::UpdateScalarPvsSize(ViewCell *vc, 
										   const int pvsSize, 
										   const int entriesInPvs) const
{
	vc->mPvsSize = pvsSize;
	vc->mEntriesInPvs = entriesInPvs;

	vc->mPvsSizeValid = true;
}


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

  // get all viewcells intersecting the viewSpaceFilterBox
  // and compute the pvs union
  
  //Vector3 center = viewCell->GetBox().Center();
  //  Vector3 center = m->mBox.Center();
  
  //  AxisAlignedBox3 box(center - Vector3(viewSpaceFilterSize/2),
  //					  center + Vector3(viewSpaceFilterSize/2));
	if (!ViewCellsConstructed())
		return;

  	if (viewSpaceFilterSize >= 0.0f) {

  bool usePrVS = false;

  if (!usePrVS) {
	AxisAlignedBox3 box = GetViewCellBox(viewCell);
	box.Enlarge(Vector3(viewSpaceFilterSize/2));
	
	ViewCellContainer viewCells;
	ComputeBoxIntersections(box, viewCells);
	
  //  cout<<"box="<<box<<endl;
	ViewCellContainer::const_iterator it = viewCells.begin(), it_end = viewCells.end();
	
	int i;
	for (i=0; it != it_end; ++ it, ++ i) {
	  	//cout<<"v"<<i<<" pvs="<<(*it)->GetPvs().mEntries.size()<<endl;
	  pvs.Merge((*it)->GetPvs());
	}
  } else {
	PrVs prvs;
	AxisAlignedBox3 box = GetViewCellBox(viewCell);

	//  mViewCellsManager->SetMaxFilterSize(1);
	GetPrVS(box.Center(), prvs, viewSpaceFilterSize);
	pvs = prvs.mViewCell->GetPvs();
	DeleteLocalMergeTree(prvs.mViewCell);
  }
  } else
	pvs = viewCell->GetPvs();
   
  if (spatialFilterSize >=0.0f)
	ApplySpatialFilter(kdTree, spatialFilterSize, pvs);
  
}



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

	if (!ViewCellsConstructed())
		return;

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

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

  float viewSpaceFilterSize = Magnitude(mViewSpaceBox.Size())*relViewSpaceFilterSize;
  float spatialFilterSize = Magnitude(kdTree->GetBox().Size())*relSpatialFilterSize;
  
  int i;
  for (i=0, it = mViewCells.begin(); it != it_end; ++ it, ++ i) {
	ApplyFilter(*it,
				kdTree,
				viewSpaceFilterSize,
				spatialFilterSize,
				newPvs[i]
				);
  }

  // now replace all pvss
  for (i = 0, it = mViewCells.begin(); it != it_end; ++ it, ++ i) {
	    
	ObjectPvs &pvs = (*it)->GetPvs();
	pvs.Clear();
	pvs = newPvs[i];
	newPvs[i].Clear();
  }
  
  delete [] newPvs;
}




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

  Intersectable::NewMail();
  
 ObjectPvsMap::const_iterator oi;
  
  for (oi = pvs.mEntries.begin(); oi != pvs.mEntries.end(); ++ oi) 
  {
	  Intersectable *object = (*oi).first;
      object->Mail();
  }

  ObjectPvs nPvs;
  int nPvsSize = 0;
  // now go through the pvs again
  for (oi = pvs.mEntries.begin(); oi != pvs.mEntries.end(); ++oi) {
	Intersectable *object = (*oi).first;

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

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

	ObjectContainer objects;

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


void ViewCellsManager::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
		{
			if (mCurrentViewCellsStats.maxPvs)
			{
				importance = 
					(float)mViewCellsTree->GetPvsSize(vc) / 
					(float)mCurrentViewCellsStats.maxPvs;
			}
		}
		break;
	case 2: // merges
		{
            const int lSize = mViewCellsTree->GetNumInitialViewCells(vc);
			importance = (float)lSize / (float)mCurrentViewCellsStats.maxLeaves;
		}
		break;
#if 0
	case 3: // merge tree differene
		{
			importance = (float)GetMaxTreeDiff(vc) /
				(float)(mVspBspTree->GetStatistics().maxDepth * 2);

		}
		break;
#endif
	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 ViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays, 
											  vector<MergeCandidate> &candidates)
{
	// implemented in subclasses
}


void ViewCellsManager::SetStoreKdPvs(const bool storeKdPvs)
{
	mStoreKdPvs = storeKdPvs;
}


bool ViewCellsManager::GetStoreKdPVs() const
{
	return mStoreKdPvs;
}


void ViewCellsManager::UpdatePvsForEvaluation(ViewCell *root, ObjectPvs &pvs)
{
	// terminate traversal
	if (root->IsLeaf())
	{ 
		// we assume that pvs is explicitly stored in leaves
		pvs = root->GetPvs();
		UpdateScalarPvsSize(root, pvs.CountObjectsInPvs(), pvs.GetSize());
		
		return;
	}
	
	//-- interior node => propagate pvs up
	ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(root);
	interior->GetPvs().Clear();
	pvs.Clear();
	vector<ObjectPvs> pvsList;

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

	for (vit = interior->mChildren.begin(); vit != vit_end; ++ vit)
	{
		ObjectPvs objPvs;
		
		//-- recursivly compute child pvss
		UpdatePvsForEvaluation(*vit, objPvs);

		// store pvs in vector
		pvsList.push_back(objPvs);
	}

#if 1
	Intersectable::NewMail();

	//-- faster way of computing pvs:
	//   construct merged pvs by adding 
	//   and only those of the next pvs which were not mailed.
	//   note: sumpdf is not correct!!
	vector<ObjectPvs>::iterator oit = pvsList.begin();

	for (vit = interior->mChildren.begin(); vit != vit_end; ++ vit, ++ oit)
	{
	    ObjectPvsMap::iterator pit, pit_end = (*oit).mEntries.end();
	
		for (pit = (*oit).mEntries.begin(); pit != pit_end; ++ pit)
		{
			Intersectable *intersect = (*pit).first;

			if (!intersect->Mailed())
			{
				pvs.AddSample(intersect, (*pit).second.mSumPdf);
				intersect->Mail();
			}
		}
	}

	// store pvs in this node
	if (mViewCellsTree->ViewCellsStorage() == ViewCellsTree::PVS_IN_INTERIORS)
	{
		interior->SetPvs(pvs);
	}
	
	// set new pvs size
	UpdateScalarPvsSize(interior, pvs.CountObjectsInPvs(), pvs.GetSize());
	

#else // really merge cells: slow put sumPdf is correct
	viewCellInterior->GetPvs().Merge(backVc->GetPvs());
	viewCellInterior->GetPvs().Merge(frontVc->GetPvs());
#endif
}



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


BspViewCellsManager::BspViewCellsManager(BspTree *bspTree):
ViewCellsManager(), mBspTree(bspTree)
{
	Environment::GetSingleton()->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);

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

	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
		ViewCell *root = ConstructSpatialMergeTree(mBspTree->GetRoot());
		mViewCellsTree->SetRoot(root);

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

	// export statistics after merge
	if (1)
	{
		char mstats[100];
		Environment::GetSingleton()->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;

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

		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 using pvs color coding
	{
		mColorCode = 1;

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

		if (exporter)
		{
			//exporter->SetWireframe();
			//exporter->SetForcedMaterial(RandomMaterial());

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

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

			delete exporter;
		}
		cout << "finished" << endl;
	}
	
	// only for debugging purpose: test if the subdivision is valid
	if (0) TestSubdivision();

	mColorCode = savedColorCode;

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

	// write view cells to disc
	if (mExportViewCells)
	{
		char filename[100];
		Environment::GetSingleton()->GetStringValue("ViewCells.filename", filename);
		ExportViewCells(filename, mExportPvs, objects);
	}
	
	// export bounding boxes
	if (0 && mExportBboxesForPvs)
	{
		char filename[100];
		Environment::GetSingleton()->GetStringValue("ViewCells.boxesFilename", filename);
		ExportBoundingBoxes(filename, objects);
	}


	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; // hack color code
		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->SetFilled();
			const bool b = mUseClipPlaneForViz;
			mUseClipPlaneForViz = false;

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

	mColorCode = savedColorCode;

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

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

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


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 in order to find the largest view cells
	if (0)
		stable_sort(mViewCells.begin(), mViewCells.end(), ViewCell::SmallerPvs);

	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::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.9f;
		if ((lVol < ((*it)->GetVolume() * thres)) ||
			(lVol * thres > ((*it)->GetVolume())))
			Debug << "warning: " << lVol << " " << (*it)->GetVolume() << endl;
	}
	
	Debug << "exact volume: " << vol << endl;
	Debug << "subdivision volume: " << subdivVol << endl;
	Debug << "new volume: " << newVol << endl;
}


void BspViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
												 ViewCell *vc,
												 const AxisAlignedPlane *clipPlane) const
{
	// export mesh if available
	if (vc->GetMesh())
	{
		exporter->ExportMesh(vc->GetMesh());
		return;
	}
	// otherwise construct from leaves
	if (clipPlane)
	{
		const Plane3 plane = clipPlane->GetPlane();

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

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

			BspNodeGeometry front;
			BspNodeGeometry back;

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

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

			if (cf == -1)
			{
				exporter->ExportPolygons(geom.GetPolys());
			}
			else if (cf == 0)
			{
				geom.SplitGeometry(front,
								   back,
								   plane,
								   mViewSpaceBox, 
								   eps);
	
				//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;
		mBspTree->ConstructGeometry(vc, geom);
			
		exporter->ExportPolygons(geom.GetPolys());
	}
}


void BspViewCellsManager::CreateMesh(ViewCell *vc)
{
	// delete previous mesh
	///DEL_PTR(vc->GetMesh());
	BspNodeGeometry geom;
	mBspTree->ConstructGeometry(vc, geom);

	Mesh *mesh = MeshManager::GetSingleton()->CreateResource();

	IncludeNodeGeomInMesh(geom, *mesh);
	vc->SetMesh(mesh);
}


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

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

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

    for (it = leaves.begin(); it != it_end; ++ it)
	{
		BspNodeGeometry geom;
		BspLeaf *leaf = dynamic_cast<BspViewCell *>(*it)->mLeaf;
		mBspTree->ConstructGeometry(leaf, geom);

		const float lVol = geom.GetVolume();
		const 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 bool active) const
{
	if (!ViewCellsConstructed())
		return NULL;

	if (!mViewSpaceBox.IsInside(point))
		return NULL;
	
	return mBspTree->GetViewCell(point);
}


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

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

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



bool BspViewCellsManager::ExportViewCells(const string filename, 
										  const bool exportPvs, 
										  const ObjectContainer &objects)
{
#if TODO
	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 << "<VisibilitySolution>" << 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
	
	// NOTE: load in vsp bsp here because bsp and vsp bsp can use same tree and vsp bsp is bug free
	stream << "<Hierarchy name=\"vspBspTree\" >" << endl; 
	
	//-- load the view cells itself, i.e., the ids and the pvs
	stream << "<ViewCells>" << endl;

	mViewCellsTree->Export(stream, exportPvs);

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

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

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

	cout << "finished" << endl;
#endif
	return true;
}


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

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


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


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

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

	viewCellInterior->SetVolume(volume);

	return viewCellInterior;
}


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



KdViewCellsManager::KdViewCellsManager(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;
		}
	}
}


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


void KdViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
												ViewCell *vc,
												const AxisAlignedPlane *clipPlane) const
{
	ViewCellContainer leaves;

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

	for (it = leaves.begin(); it != it_end; ++ it)
	{
		KdViewCell *kdVc = 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
}




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


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


VspBspViewCellsManager::~VspBspViewCellsManager()
{
}


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


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


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

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

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


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


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


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

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

	int sampleContributions = 0;

	VssRayContainer sampleRays;

	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;

	long startTime;

	if (1)
	{
		mVspBspTree->Construct(constructionRays, &mViewSpaceBox);
	}
	else
	{
		mVspBspTree->Construct(rays, &mViewSpaceBox);
	}

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

    cout << "finished" << endl;

	//-- stats after construction

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

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


	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;

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

	return sampleContributions;
}


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

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


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

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

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

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

	//-- 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.wrl");
		
		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 (0) 
	{
		mColorCode = 1; // export merged view cells using pvs coding
		Exporter *exporter = Exporter::GetExporter("merged_view_cells_pvs.wrl");

		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
	int minPvs, maxPvs;

	if (0)
	{
		minPvs = mMinPvsSize;
		maxPvs = mMaxPvsSize;
	}
	else
	{
		minPvs = mPruneEmptyViewCells ? 1 : 0;
		maxPvs = mMaxPvsSize;
	}

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

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

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

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


	// 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 debugging purpose: test if the subdivision is valid
	if (0) 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->GetStoredPvsEntriesNum(mViewCellsTree->GetRoot());
		Debug << "number of entries before compress: " << pvsEntries << endl;

		mViewCellsTree->SetViewCellsStorage(ViewCellsTree::COMPRESSED);

		pvsEntries = mViewCellsTree->GetStoredPvsEntriesNum(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();

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

	// write view cells to disc
	if (mExportViewCells)
	{
		char filename[100];
		Environment::GetSingleton()->GetStringValue("ViewCells.filename", filename);
		ExportViewCells(filename, mExportPvs, objects);
	}

	
	// export bounding boxes
	if (mExportBboxesForPvs)
	{
		char filename[100];
		Environment::GetSingleton()->GetStringValue("ViewCells.boxesFilename", filename);
	
		ExportBoundingBoxes(filename, objects);
	}

	return 0;
}


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


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

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


	ObjectPvs frontPvs, backPvs;

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


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

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

	viewCellInterior->SetVolume(volume);

	return viewCellInterior;
}


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

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

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

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


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

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


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

	VssRayContainer visRays;
	GetRaySets(sampleRays, mVisualizationSamples, visRays);

	//-- export final view cell partition

	if (0) 
	{	
		// hack pvs
		//const int savedColorCode = mColorCode;
		//mColorCode = 1;
	
		Exporter *exporter = Exporter::GetExporter("final_view_cells.wrl");
		
		if (exporter)
		{
			cout << "exporting view cells after post process ... ";

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

			Material m; 

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

            exporter->SetForcedMaterial(m);

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

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

			//exporter->SetFilled();

			// HACK: export without clip plane
			const bool b = mUseClipPlaneForViz;
			//mUseClipPlaneForViz = false;

			ExportViewCellsForViz(exporter);
			
			mUseClipPlaneForViz = b;
			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->GetStatistics().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::GetSingleton()->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)
{
	int leafOut;
	Environment::GetSingleton()->GetIntValue("ViewCells.Visualization.maxOutput", leafOut);

	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(), ViewCell::SmallerPvs);
		stable_sort(mViewCells.begin(), mViewCells.end(), ViewCell::LargerRenderCost);
	}

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

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

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

		//-- export the sample rays
		if (mExportRays)
		{
			// output rays stored with the view cells during subdivision
			if (1)
			{
				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);
				}

				//Debug << "#rays: " << (int)vcRays.size() << endl;

				//-- export rays piercing this view cell
				exporter->ExportRays(vcRays, RgbColor(1, 1, 1));
			}
		
			// associate new rays with output view cell
			if (0)
			{
				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));
			}

		}
		

		//-- export view cell geometry
		exporter->SetWireframe();

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

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


		//-- export pvs
		if (1)
		{
			ObjectPvsMap::const_iterator oit,
				oit_end = pvs.mEntries.end();

			Intersectable::NewMail();

			// output PVS of view cell
			for (oit = pvs.mEntries.begin(); oit != oit_end; ++ oit)
			{		
				Intersectable *intersect = (*oit).first;

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

					exporter->ExportIntersectable(intersect);
					intersect->Mail();
				}
			}
		}
		
		if (0)
		{   // export scene geometry
			m.mDiffuseColor = RgbColor(1, 0, 0);
			exporter->SetForcedMaterial(m);

			exporter->ExportGeometry(objects);
		}

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

	Debug << endl;
}


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

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

		GetPrVS(viewPoint, testPrVs, GetFilterWidth());

		exporter->SetWireframe();

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

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

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

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

		delete exporter;
	}
}


int VspBspViewCellsManager::ComputeBoxIntersections(const AxisAlignedBox3 &box, 
													ViewCellContainer &viewCells) const
{
	return mVspBspTree->ComputeBoxIntersections(box, viewCells);
}


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


void VspBspViewCellsManager::VisualizeWithFromPointQueries()
{
	int numSamples;
	
	Environment::GetSingleton()->GetIntValue("RenderSampler.samples", numSamples);
	cout << "samples" << numSamples << endl;

	vector<RenderCostSample> samples;
  
	if (!mPreprocessor->GetRenderer())
		return;

	//start the view point queries
	long startTime = GetTime();
	cout << "starting sampling of render cost ... ";
	
	mPreprocessor->GetRenderer()->SampleRenderCost(numSamples, samples, true);

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


	// for each sample:
	//    find view cells associated with the samples
	//    store the sample pvs with the pvs associated with the view cell
	// for each view cell:
	//    compute difference point sampled pvs - view cell pvs
	//    export geometry with color coded pvs difference
	
    std::map<ViewCell *, ObjectPvs> sampleMap;

	vector<RenderCostSample>::const_iterator rit, rit_end = samples.end();

	for (rit = samples.begin(); rit != rit_end; ++ rit)
	{
		RenderCostSample sample = *rit;
	
		ViewCell *vc = GetViewCell(sample.mPosition);

		std::map<ViewCell *, ObjectPvs>::iterator it = sampleMap.find(vc);

		if (it == sampleMap.end())
		{
			sampleMap[vc] = sample.mPvs;
		}
		else
		{
			(*it).second.Merge(sample.mPvs);
		}
	}

	// visualize the view cells
	std::map<ViewCell *, ObjectPvs>::const_iterator vit, vit_end = sampleMap.end();

	Material m;//= RandomMaterial();

	for (vit = sampleMap.begin(); vit != vit_end; ++ vit)
	{
		ViewCell *vc = (*vit).first;
		
		const int pvsVc = mViewCellsTree->GetPvsEntries(vc);
		const int pvsPtSamples = (*vit).second.GetSize();

        m.mDiffuseColor.r = (float) (pvsVc - pvsPtSamples);
		m.mDiffuseColor.b = 1.0f;
		//exporter->SetForcedMaterial(m);

//		ExportViewCellGeometry(exporter, vc, mClipPlane);

/*	// counting the pvss
	for (rit = samples.begin(); rit != rit_end; ++ rit)
	{
		RenderCostSample sample = *rit;

		ViewCell *vc = GetViewCell(sample.mPosition);
		
		AxisAlignedBox3 box(sample.mPosition - Vector3(1, 1, 1), sample.mPosition + Vector3(1, 1, 1));
		Mesh *hMesh = CreateMeshFromBox(box);
		
		DEL_PTR(hMesh);

*/
	}
}


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

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

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

			BspNodeGeometry front;
			BspNodeGeometry back;

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

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

			if (cf == -1)
			{
				exporter->ExportPolygons(geom.GetPolys());
			}
			else if (cf == 0)
			{
				geom.SplitGeometry(front,
								   back,
								   plane,
								   mViewSpaceBox, 
								   eps);
	
				//Debug << "geo size: " << geom.Size() << endl;
				//Debug << "size b: " << back.Size() << " f: " << front.Size() << endl;

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


int VspBspViewCellsManager::GetMaxTreeDiff(ViewCell *vc) const
{
	ViewCellContainer leaves;
	mViewCellsTree->CollectLeaves(vc, leaves);

	int maxDist = 0;
	
	// compute max height difference
	for (int i = 0; i < (int)leaves.size(); ++ i)
	{
		for (int j = 0; j < (int)leaves.size(); ++ j)
		{
			BspLeaf *leaf = 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 bool active) const
{
	if (!ViewCellsConstructed())
		return NULL;

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

	return mVspBspTree->GetViewCell(point, active);
}


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

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

	vc->SetMesh(mesh);
}


int VspBspViewCellsManager::CastBeam(Beam &beam)
{
	return mVspBspTree->CastBeam(beam);
}


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

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

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

    for (it = leaves.begin(); it != it_end; ++ it)
	{
		BspNodeGeometry geom;
		BspLeaf *leaf = dynamic_cast<BspViewCell *>(*it)->mLeaf;
		mVspBspTree->ConstructGeometry(leaf, geom);

		const float lVol = geom.GetVolume();
		const 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.9f;
		if ((lVol < ((*it)->GetVolume() * thres)) || (lVol * thres > ((*it)->GetVolume())))
			Debug << "warning: " << lVol << " " << (*it)->GetVolume() << endl;
	}
	
	Debug << "exact volume: " << vol << endl;
	Debug << "subdivision volume: " << subdivVol << endl;
	Debug << "new volume: " << newVol << endl;
}


void VspBspViewCellsManager::PrepareLoadedViewCells()
{
	// TODO: do I still need this here?
	if (0)
		mVspBspTree->RepairViewCellsLeafLists();
}



/**************************************************************************/
/*                   VspOspViewCellsManager implementation                */
/**************************************************************************/


VspOspViewCellsManager::VspOspViewCellsManager(VspTree *vspTree, OspTree *ospTree):
ViewCellsManager(), mVspTree(vspTree), mOspTree(ospTree)
{
	mHierarchyManager = new HierarchyManager(*vspTree, *ospTree);
	Environment::GetSingleton()->GetIntValue("VspTree.Construction.samples", mInitialSamples);

	mVspTree->SetViewCellsManager(this);
	mOspTree->SetViewCellsManager(this);

	mVspTree->SetViewCellsTree(mViewCellsTree);
}


VspOspViewCellsManager::~VspOspViewCellsManager()
{
	DEL_PTR(mHierarchyManager);
}


float VspOspViewCellsManager::GetProbability(ViewCell *viewCell)
{
	return GetVolume(viewCell) / mViewSpaceBox.GetVolume();
}


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


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


ViewCell *VspOspViewCellsManager::GenerateViewCell(Mesh *mesh) const
{
	return new VspViewCell(mesh);
}


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

	// skip rest if view cells were already constructed
	if (ViewCellsConstructed())
		return 0;

	int sampleContributions = 0;

	VssRayContainer sampleRays;

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

	VssRayContainer constructionRays;
	VssRayContainer savedRays;

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

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

	Debug << "initial rays: " << (int)constructionRays.size() << endl;
	Debug << "saved rays: " << (int)savedRays.size() << endl;

	long startTime;

	//mHierarchyManager->Construct(constructionRays, objects, &mViewSpaceBox);
	mHierarchyManager->Construct2(constructionRays, objects, &mViewSpaceBox);

	VssRayContainer::const_iterator vit, vit_end = constructionRays.end();

	for (vit = constructionRays.begin(); vit != vit_end; ++ vit)
	{
		storedRays.push_back(new VssRay(*(*vit)));
	}

	// print subdivision statistics
	Debug << mVspTree->GetStatistics() << endl;
	Debug << mOspTree->GetStatistics() << endl;

	OUT_STREAM stream("osptree.xml.zip");
	mOspTree->Export(stream);

	// print view cell statistics
	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;

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

	return sampleContributions;
}


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


	// take this step only if 
	// view cells already constructed before post processing step 
	// (e.g., because they were loaded)
	if (mViewCellsFinished)
	{
		FinalizeViewCells(true);
		EvaluateViewCellsStats();

		return 0;
	}

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

	if (0)
	{
		minPvs = mMinPvsSize;
		maxPvs = mMaxPvsSize;
	}
	else
	{
		minPvs = mPruneEmptyViewCells ? 1 : 0;
		maxPvs = mMaxPvsSize;
	}

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

	
	// area 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);
		
	// compute tree by merging the nodes of the spatial hierarchy
	ViewCell *root = ConstructSpatialMergeTree(mVspTree->GetRoot());
	mViewCellsTree->SetRoot(root);

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

	
	//-- 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->GetStoredPvsEntriesNum(mViewCellsTree->GetRoot());
		Debug << "number of entries before compress: " << pvsEntries << endl;

		mViewCellsTree->SetViewCellsStorage(ViewCellsTree::COMPRESSED);

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

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

	// write view cells to disc
	if (mExportViewCells)
	{
		char filename[100];
		Environment::GetSingleton()->GetStringValue("ViewCells.filename", filename);
		ExportViewCells(filename, mExportPvs, objects);
	}


	return 0;
}


int VspOspViewCellsManager::GetType() const
{
	return VSP_OSP;
}


ViewCell *VspOspViewCellsManager::ConstructSpatialMergeTree(VspNode *root)
{
	// terminate recursion
	if (root->IsLeaf())
	{
		VspLeaf *leaf = dynamic_cast<VspLeaf *>(root);
		leaf->GetViewCell()->SetMergeCost(0.0f);
		return leaf->GetViewCell();
	}
	
	VspInterior *interior = dynamic_cast<VspInterior *>(root);
	ViewCellInterior *viewCellInterior = new ViewCellInterior();
		
	// evaluate merge cost for priority traversal
	float mergeCost = 1.0f / (float)root->mTimeStamp;
	viewCellInterior->SetMergeCost(mergeCost);

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


	ObjectPvs frontPvs, backPvs;

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


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

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

	viewCellInterior->SetVolume(volume);

	return viewCellInterior;
}


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

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

	for (int i = 0; i < limit; ++ i)
	{
		viewPoint = mViewSpaceBox.GetRandomPoint();

		if (mVspTree->ViewPointValid(viewPoint))
		{
			return true;
		}
	}

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


void VspOspViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
													ViewCell *vc,
													const AxisAlignedPlane *clipPlane) const
{
	ViewCellContainer leaves;

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

	Plane3 plane;
	
	if (clipPlane)
		plane = clipPlane->GetPlane();

	for (it = leaves.begin(); it != it_end; ++ it)
	{
		VspViewCell *vspVc = dynamic_cast<VspViewCell *>(*it);
		VspLeaf *l = vspVc->mLeaf;

		const AxisAlignedBox3 box = mVspTree->GetBoundingBox(vspVc->mLeaf);
		
		if (clipPlane)
		{
			if (box.Side(plane) == -1)
			{
				exporter->ExportBox(box);
			}
			else if (box.Side(plane) == 0)
			{
				AxisAlignedBox3 fbox, bbox;
				box.Split(clipPlane->mAxis, clipPlane->mPosition, fbox, bbox);

				exporter->ExportBox(bbox);
			}
		}
		else
		{
			exporter->ExportBox(box);
		}
	}
}


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

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


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

	VssRayContainer visRays;
	GetRaySets(sampleRays, mVisualizationSamples, visRays);

	if (1) 
	{	
		//-- export final view cells

		// hack pvs
		const int savedColorCode = mColorCode;
		mColorCode = 0;
	
		Exporter *exporter = Exporter::GetExporter("final_view_cells.wrl");
		
		if (exporter)
		{
			cout << "exporting view cells after post process ... ";

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

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

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

			//exporter->SetFilled();

			// HACK: export without clip plane
			const bool b = mUseClipPlaneForViz;
			if (0) mUseClipPlaneForViz = false;

			ExportViewCellsForViz(exporter);
			
			mUseClipPlaneForViz = b;
			delete exporter;

			cout << "finished" << endl;
		}

		mColorCode = savedColorCode;
	}

	if (1 && mOspTree->GetRoot()) 
	{	
		//-- export final object partition
		Exporter *exporter = Exporter::GetExporter("final_object_partition.wrl");
		
		if (exporter)
		{
			cout << "exporting object space partition ... ";

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

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

			exporter->SetWireframe();
	
			const int savedColorCode = mColorCode;
			mColorCode = 0;
			const int maxPvs = 200;//mOspTree.GetStatistics().maxPvs;

			exporter->ExportOspTree(*mOspTree, mColorCode == 0 ? 0 : maxPvs);

			mColorCode = savedColorCode;

			delete exporter;

			cout << "finished" << endl;
		}
	}

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


void VspOspViewCellsManager::ExportPvs(const ObjectContainer &objects,
									   const VssRayContainer &rays)
{
	int leafOut;
	Environment::GetSingleton()->GetIntValue("ViewCells.Visualization.maxOutput", leafOut);

	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(), ViewCell::SmallerPvs);
		stable_sort(mViewCells.begin(), mViewCells.end(), ViewCell::LargerRenderCost);
	}

	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 // random view cell
			vc = mViewCells[(int)RandomValue(0, (float)mViewCells.size() - 1)];

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

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

		//-- export the sample rays
		if (1 || mExportRays)
		{
			// output rays stored with the view cells during subdivision
			if (1)
			{
				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)
				{
					VspLeaf *vcLeaf = dynamic_cast<VspViewCell *>(*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 (0)
			{
				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));
			}
		}

		//-- export view cell geometry

		exporter->SetWireframe();

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

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

		if (1)
		{	
			//-- export pvs
			
			Intersectable::NewMail();
			KdLeaf::NewMail();

			vector<KdLeaf *> kdLeaves;

			ObjectPvsMap::const_iterator oit, oit_end = pvs.mEntries.end();

			for (oit = pvs.mEntries.begin(); oit != oit_end; ++ oit)
			{	
				Intersectable *obj = (*oit).first;

				if (obj->Type() == Intersectable::KD_INTERSECTABLE)
				{
					m.mDiffuseColor = RgbColor(1, 1, 1);
					exporter->SetForcedMaterial(m);

					// export bounding box of node
					KdIntersectable *kdObj  = dynamic_cast<KdIntersectable *>(obj);
					AxisAlignedBox3 box = mOspTree->GetBoundingBox(kdObj->GetNode());
					
					exporter->SetWireframe();
					exporter->ExportBox(box);
					exporter->SetFilled();
				}

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

				// export pvs entry
				if (!obj->Mailed())
				{
					exporter->ExportIntersectable(obj);
					obj->Mail();
				}
			}		
		}
	
		DEL_PTR(exporter);
		cout << "finished" << endl;
	}

	Debug << endl;
}


int VspOspViewCellsManager::ComputeBoxIntersections(const AxisAlignedBox3 &box, 
													ViewCellContainer &viewCells) const
{
	return mVspTree->ComputeBoxIntersections(box, viewCells);
}


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


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

	cout << "exporting view cells to xml ... ";
	
	OUT_STREAM stream(filename.c_str());

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

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

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

	
	//-- export bounding boxes

	stream << "<BoundingBoxes>" << endl;

	ObjectContainer::const_iterator oit, oit_end = objects.end();

	for (oit = objects.begin(); oit != oit_end; ++ oit)
	{
			MeshInstance *mi = dynamic_cast<MeshInstance *>(*oit);
			const AxisAlignedBox3 box = mi->GetBox();

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

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


	//-- export the view cells and the pvs

	stream << "<Hierarchy name=\"vspTree\" />" << endl;
	const int numViewCells = mCurrentViewCellsStats.viewCells;

	stream << "<ViewCells number=\"" << numViewCells << "\" >" << endl;
	mViewCellsTree->Export(stream, exportPvs);
	stream << "</ViewCells>" << endl;


	//-- export the view space hierarchy
	
	// the type of the view space partition
	stream << "<ViewSpacePartition>" << endl;
	mVspTree->Export(stream);
	stream << endl << "</ViewSpacePartitioin>" << endl;

	
	//-- export the object space partition
	
	// the type of the view cells hierarchy
	stream << "<ObjectSpacePartition>" << endl;
	mOspTree->Export(stream);
	stream << endl << "</ObjectSpacePartition>" << endl;


	stream << "</VisibilitySolution>" << endl;
	stream.close();
	
	cout << "finished" << endl;

	return true;
}



ViewCell *VspOspViewCellsManager::GetViewCell(const Vector3 &point, 
											  const bool active) const
{
	if (!ViewCellsConstructed())
		return NULL;

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

	return mVspTree->GetViewCell(point, active);
}


void VspOspViewCellsManager::CreateMesh(ViewCell *vc)
{
	// matt: TODO
	Mesh *mesh = MeshManager::GetSingleton()->CreateResource();

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

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

    for (it = leaves.begin(); it != it_end; ++ it)
	{
		VspLeaf *leaf = dynamic_cast<VspViewCell *>(*it)->mLeaf;
		const AxisAlignedBox3 box = mVspTree->GetBoundingBox(leaf);

        IncludeBoxInMesh(box, *mesh);
	}

	vc->SetMesh(mesh);
}


int VspOspViewCellsManager::CastBeam(Beam &beam)
{
	// matt: TODO
	return 0;
}


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

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

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

    for (it = leaves.begin(); it != it_end; ++ it)
	{
		VspLeaf *leaf = dynamic_cast<VspViewCell *>(*it)->mLeaf;
		
		const AxisAlignedBox3 box = mVspTree->GetBoundingBox(leaf);

		const float lVol = box.GetVolume();
		const float lArea = box.SurfaceArea();

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

		area += lArea;
		volume += lVol;

        CreateMesh(*it);
	}

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

float VspOspViewCellsManager::ComputeSampleContribution(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);

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

	if (storeViewCells)
	{	// copy viewcells memory efficiently
		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())
		{
			// if ray not outside of view space
			float contribution;

			if (ray.mTerminationObject) 
			{
				// todo: maybe not correct for kd node pvs
				if (viewcell->GetPvs().GetSampleContribution(ray.mTerminationObject,
					ray.mPdf, contribution))
				{
					++ ray.mPvsContribution;
				}

				ray.mRelativePvsContribution += contribution;
			}

			// for directional sampling it is important to count only contributions
			// made in one direction!!!
			// the other contributions of this sample will be counted for the oposite ray!
#if SAMPLE_ORIGIN_OBJECTS
			if (ray.mOriginObject && 
				viewcell->GetPvs().GetSampleContribution(ray.mOriginObject,
														 ray.mPdf,
														 contribution))
			{
				++ ray.mPvsContribution;
				ray.mRelativePvsContribution += contribution;
			}
#endif
		}
	}

	// if addrays is true, sampled entities are stored in the pvs
	if (addRays)
	{
		for (it = viewcells.begin(); it != viewcells.end(); ++ it) 
		{
			ViewCell *viewcell = *it;
            
			if (viewcell->GetValid())
			{
				// if ray not outside of view space

				// add kd cell
				if (ray.mTerminationObject)
				{
					if (!mStoreKdPvs)
					{
						viewcell->AddPvsSample(ray.mTerminationObject, 
							ray.mPdf, ray.mRelativePvsContribution);
					}
					else
					{
						// get current leaf the point is located in
						KdLeaf *leaf = mOspTree->GetLeaf(ray.mTermination);
						KdIntersectable *entry = mOspTree->GetOrCreateKdIntersectable(leaf);

						viewcell->AddPvsSample(entry, ray.mPdf, ray.mRelativePvsContribution);
					}
				}
				
#if SAMPLE_ORIGIN_OBJECTS
				 if (ray.mOriginObject)
				 {
					 if (!mStoreKdPvs)
					 {
						 viewcell->AddPvsSample(ray.mOriginObject, ray.mPdf, ray.mPvsContribution);
					 }
					 else
					 {
						 /// get current leaf the point
						KdLeaf *leaf = mOspTree->GetLeaf(ray.mOrigin);
						KdIntersectable *entry = mOspTree->GetOrCreateKdIntersectable(leaf);

						viewcell->AddPvsSample(entry, ray.mPdf, ray.mRelativePvsContribution);
					 }
				 }
#endif
			}
		}
	}

	return ray.mRelativePvsContribution;
}


void VspOspViewCellsManager::PrepareLoadedViewCells()
{
	// TODO
}


ViewCellsManager *VspOspViewCellsManager::LoadViewCells(const string &filename, 
														ObjectContainer *objects,
														const bool finalizeViewCells,
														BoundingBoxConverter *bconverter)
												 
{
	ViewCellsManager *vm = 
		ViewCellsManager::LoadViewCells(filename, objects, finalizeViewCells, bconverter);

	mOspTree->InsertObjects(mOspTree->GetRoot(), *objects);

	return vm;
}


#if TEST_EVALUATION
void VspOspViewCellsManager::EvalViewCellPartition()
{
	int castSamples = (int)storedRays.size();

	char s[64]; 
	char statsPrefix[100];

	Environment::GetSingleton()->GetStringValue("ViewCells.Evaluation.statsPrefix", statsPrefix);

	Debug << "view cell stats prefix: " << statsPrefix << endl;

	// should directional sampling be used?
	bool dirSamples = (mEvaluationSamplingType == Preprocessor::DIRECTION_BASED_DISTRIBUTION);

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


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

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

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

	VssRayContainer evaluationSamples = storedRays;
	const int samplingType = mEvaluationSamplingType;
	
	cout << "computing sample contributions of " << (int)evaluationSamples.size()  << " samples ... ";

	ComputeSampleContributions(evaluationSamples, true, false);

	cout << "finished" << endl;
	
	cout << "compute new statistics ... ";
	Debug << "compute new statistics ... ";

	// propagate pvs or pvs size information
	ObjectPvs pvs;
	UpdatePvsForEvaluation(mViewCellsTree->GetRoot(), pvs);


//-- test render cost

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

ViewCellContainer leaves;

mViewCellsTree->CollectLeaves(mViewCellsTree->GetRoot(), leaves);
float rc = 0;
ViewCellContainer::const_iterator vit, vit_end = leaves.end();
for (vit = leaves.begin(); vit != vit_end; ++ vit)
{
	ViewCell *vc = *vit;
		int pvs = vc->GetPvs().CountObjectsInPvs();
	float vol = vc->GetVolume();
	rc += pvs * vol;

	}
	
	Debug << "\nhere295 " << rc / mVspTree->GetBoundingBox().GetVolume() << endl;

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

	disposeRays(evaluationSamples, NULL);
}
#endif
//////////////////////////////////
/*ViewCellsManager *ViewCellsManagerFactory::Create(const string mName)
{
	//TODO
	return NULL;// new VspBspViewCellsManager();
}*/


}