#include "ViewCellsManager.h"
#include "RenderSimulator.h"
#include "Mesh.h"
#include "Triangle3.h"
#include "ViewCell.h"
#include "Environment.h"
#include "X3dParser.h"
#include "ViewCellBsp.h"
#include "KdTree.h"
#include "VspKdTree.h"
#include "Exporter.h"
#include "VspBspTree.h"


ViewCellsManager::ViewCellsManager():
mRenderSimulator(NULL),
mConstructionSamples(0),
mPostProcessSamples(0),
mVisualizationSamples(0),
mTotalAreaValid(false),
mTotalArea(0.0f)
{
	// post processing stuff
	environment->GetIntValue("ViewCells.PostProcessing.minPvsDif", mMinPvsDif);
	environment->GetIntValue("ViewCells.PostProcessing.minPvs", mMinPvs);
	environment->GetIntValue("ViewCells.PostProcessing.maxPvs", mMaxPvs);
}

ViewCellsManager::ViewCellsManager(int constructionSamples):
mConstructionSamples(constructionSamples),
mRenderSimulator(NULL),
mPostProcessSamples(0),
mVisualizationSamples(0)
{
	// post processing stuff
	environment->GetIntValue("ViewCells.PostProcessing.minPvsDif", mMinPvsDif);
	environment->GetIntValue("ViewCells.PostProcessing.minPvs", mMinPvs);
	environment->GetIntValue("ViewCells.PostProcessing.maxPvs", mMaxPvs);
}

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

	CLEAR_CONTAINER(mViewCells);
}

bool ViewCellsManager::LoadViewCells(const string filename)
{
	X3dParser parser;
	
	environment->GetFloatValue("ViewCells.height", parser.mViewCellHeight);
	
	bool success = parser.ParseFile(filename, *this);
	Debug << (int)mViewCells.size() << " view cells loaded" << endl;

	return success;
}

void ViewCellsManager::ComputeSampleContributions(const VssRayContainer &rays)
{
	// view cells not yet constructed
	if (!ViewCellsConstructed())
		return;
  
	VssRayContainer::const_iterator it, it_end = rays.end();
	
	for (it = rays.begin(); it != it_end; ++ it) 
	{
		ComputeSampleContributions(*(*it));
	}
}

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

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

	for (int i = 0; i < limit; ++ i)
	{
		Intersectable *object = objects[i];
		
		// extract the mesh instances
		if (object->Type() == Intersectable::MESH_INSTANCE)
		{
			MeshInstance *inst = dynamic_cast<MeshInstance *>(object);

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

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

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

	//--- extrude new vertices for top of prism
	Vector3 triNorm = baseTri.GetNormal();

	Triangle3 topTri;	

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

	return GenerateViewCell(mesh);
}

ViewCell *ViewCellsManager::MergeViewCells(ViewCell &front, ViewCell &back) const
{
	// generate merged view cell
	ViewCell *vc = GenerateViewCell();

	// merge pvs
	vc->GetPvs().Merge(front.GetPvs(), back.GetPvs());

	//-- merge ray sets
	stable_sort(front.mPiercingRays.begin(), front.mPiercingRays.end());
	stable_sort(back.mPiercingRays.begin(), back.mPiercingRays.end());

	std::merge(front.mPiercingRays.begin(), front.mPiercingRays.end(),
			   back.mPiercingRays.begin(), back.mPiercingRays.end(), 
			   vc->mPiercingRays.begin());

	return vc;
}


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


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

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

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

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

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

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

void
ViewCellsManager::GetPvsStatistics(PvsStatistics &stat)
{
  ViewCellContainer::const_iterator it = mViewCells.begin();
  stat.viewcells = 0;
  stat.minPvs = 100000000;
  stat.maxPvs = 0;
  stat.avgPvs = 0.0f;

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

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

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

void ViewCellsManager::ComputeSampleContributions(VssRay &ray)
{
	ViewCellContainer viewcells;
	
	CastLineSegment(ray.mOrigin,
					ray.mTermination,
					viewcells);
	
	ray.mPvsContribution = 0;
	ray.mRelativePvsContribution = 0.0f;
  
	ViewCellContainer::const_iterator it = viewcells.begin();
	
	for (; it != viewcells.end(); ++it) 
	{ 	
		ViewCell *viewcell = *it;
	
		// if ray not outside of view space
		float contribution;
		bool added = 
			viewcell->GetPvs().AddSample(ray.mTerminationObject,
										 contribution);
		
		if (added)
			++ ray.mPvsContribution;
		
		ray.mRelativePvsContribution += contribution;
	}
}


void ViewCellsManager::GetRaySets(const VssRayContainer &sourceRays,
								  VssRayContainer &constructionRays, 
								  VssRayContainer &savedRays) const
{
	const int limit = min(mConstructionSamples, (int)sourceRays.size());

	VssRayContainer::const_iterator it, it_end = sourceRays.end();
	
	const float prop = (float)limit / ((float)sourceRays.size() + Limits::Small);

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


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


float ViewCellsManager::GetArea(ViewCell *viewCell) const
{
	return 0.0f;
}


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)
        mTotalArea += GetArea(*it);
	
	mTotalAreaValid = true;

	return mTotalArea;
}

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


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

BspViewCellsManager::BspViewCellsManager(BspTree *bspTree, 
										 int constructionSamples):
ViewCellsManager(constructionSamples), 
mBspTree(bspTree)
{
}


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

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

int BspViewCellsManager::Construct(const ObjectContainer &objects, 
								   const VssRayContainer &rays,
								   AxisAlignedBox3 *sceneBbox)
{
	// 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(mConstructionSamples, (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);
		// collect final view cells
		mBspTree->CollectViewCells(mViewCells);
	} 
	else
	{
		mBspTree->Construct(mViewCells);
	}

	mBspTree->EvaluateViewCellsStats(mViewCellsStats);

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

	Debug << mBspTree->GetStatistics() << endl;
	
	// recast rest of the rays
	ComputeSampleContributions(savedRays);

	return sampleContributions;
}

float BspViewCellsManager::GetArea(ViewCell *viewCell) const
{
	PolygonContainer geom;

	// compute view cell area
	mBspTree->ConstructGeometry(dynamic_cast<BspViewCell *>(viewCell), geom);
	
	const float area = Polygon3::GetArea(geom);
	CLEAR_CONTAINER(geom);

	return area;
}


float BspViewCellsManager::GetProbability(ViewCell *viewCell)
{
	// compute view cell area as subsititute for probability
#if 0
	return GetArea(viewCell) / mBspTree->GetBoundingBox().SurfaceArea();
#else
	return GetArea(viewCell) / GetAccVcArea();
#endif
}


float BspViewCellsManager::GetRendercost(ViewCell *viewCell, float objRendercost) const
{
	return viewCell->GetPvs().GetSize() * objRendercost;
}


AxisAlignedBox3 BspViewCellsManager::GetSceneBbox() const
{
	return mBspTree->GetBoundingBox();
}


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 (mBspRays.empty())
		ConstructBspRays(rays, mConstructionSamples);
	
	if (!ViewCellsConstructed())
	{
		Debug << "view cells not constructed" << endl;
		return 0;
	}

	//-- post processing of bsp view cells
    int vcSize = 0;
	int pvsSize = 0;

	Debug << "original view cell partition:\n" << mViewCellsStats << endl;
		
	if (1) // export view cells
	{
		cout << "exporting initial view cells (=leaves) ... ";
		Exporter *exporter = Exporter::GetExporter("view_cells.x3d");
	
		if (exporter)
		{
			//exporter->SetWireframe();
			exporter->SetFilled();
			exporter->ExportBspViewCellPartition(*mBspTree, 
				mViewCellsStats.maxPvs);
				
			if (0)
			{
				Material m;
				m.mDiffuseColor = RgbColor(0, 1, 0);
				exporter->SetForcedMaterial(m);
				exporter->SetWireframe();

				exporter->ExportGeometry(objects);
			}

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

	cout << "starting post processing using " << mPostProcessSamples << " samples ... ";
		
	long startTime = GetTime();


	// $$JB we do not have connectivity information from the ray in the moment
	// perhaps we could recast the rays or rember the cells traversed inside the
	// vssray (which would on other hand create some overhead)
	//-- merge or subdivide view cells
	int merged = 0;

	vector<BspIntersection>::const_iterator iit;

	for (int i = 0; i < (int)mBspRays.size(); ++ i)
	{  
		BspRay *ray = mBspRays[i];
	  
		// traverse leaves stored in the rays and compare and merge consecutive
		// leaves (i.e., the neighbors in the tree)
		if (ray->intersections.size() < 2)
			continue;
	  
		iit = ray->intersections.begin();

		BspLeaf *previousLeaf = (*iit).mLeaf;
		++ iit;
		
		for (; iit != ray->intersections.end(); ++ iit)
		{
			BspLeaf *leaf = (*iit).mLeaf;

			if (ShouldMerge(leaf, previousLeaf))
			{			
				MergeBspLeafViewCells(leaf, previousLeaf);

				++ merged;
			}
		
			previousLeaf = leaf;
		}
	}

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

	Debug << "Postprocessing: Merged " << merged << " view cells in "
		  << TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl << endl;
	
	// reset view cells and stats
	mViewCells.clear();
	mBspTree->CollectViewCells(mViewCells);
	mViewCellsStats.Reset();
	mBspTree->EvaluateViewCellsStats(mViewCellsStats);

	return merged;
}


BspViewCellsManager::~BspViewCellsManager()
{
	CLEAR_CONTAINER(mBspRays);
}


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


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

	if (mBspRays.empty())
		ConstructBspRays(sampleRays, mConstructionSamples);
	
	if (1) // export view cells
	{
		cout << "exporting view cells after merge ... ";
		Exporter *exporter = Exporter::GetExporter("merged_view_cells.x3d");

		if (exporter)
		{
			exporter->ExportBspViewCellPartition(*mBspTree, 
				mViewCellsStats.maxPvs);
			delete exporter;
		}
		
		cout << "finished" << endl;
	}	

	//-- visualization of the BSP splits
	bool exportSplits = false;
	environment->GetBoolValue("BspTree.Visualization.exportSplits", exportSplits);
	
	if (exportSplits)
	{
		cout << "exporting splits ... ";
	 	ExportSplits(objects);
		cout << "finished" << endl;
	}

	ExportBspPvs(objects);
}


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


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

	if (exporter) 
	{	
		Material m; 
		m.mDiffuseColor = RgbColor(1, 0, 0);
		exporter->SetForcedMaterial(m);
		exporter->SetWireframe();
		
		exporter->ExportBspSplits(*mBspTree, 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 (0)
		{
			VssRayContainer outRays;
		
			int raysSize = min((int)mBspRays.size(), mVisualizationSamples);

			for (int i = 0; i < raysSize; ++ i)
				// only rays piercing geometry
				outRays.push_back(mBspRays[i]->vssRay);
						
			// export rays 
			exporter->ExportRays(outRays, RgbColor(1, 1, 0));
		}

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

		delete exporter;
	}
}


void BspViewCellsManager::ExportBspPvs(const ObjectContainer &objects)
{
	bool exportRays = false;
	bool exportGeometry = false;

	environment->GetBoolValue("VspBspTree.Visualization.exportRays", exportRays);
	environment->GetBoolValue("VspBspTree.Visualization.exportGeometry", exportGeometry);

	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;

	if (1)
	{
		//-- some random view cells and rays for output
		vector<BspLeaf *> vspBspLeaves;

		for (int i = 0; i < leafOut; ++ i)
			vspBspLeaves.push_back(mBspTree->GetRandomLeaf());	
		
		for (int i = 0; i < (int)vspBspLeaves.size(); ++ i)
		{
			VssRayContainer vcRays;
			cout << "creating output for view cell " << i << " ... ";

			// 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 (vspBspLeaves[i]->GetViewCell() == leaf->GetViewCell()) 
					{
						vcRays.push_back(ray->vssRay);
					}
				}
			}

			Intersectable::NewMail();

			BspViewCell *vc = dynamic_cast<BspViewCell *>
				(vspBspLeaves[i]->GetViewCell());

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

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

			ObjectPvsMap::iterator it = vc->GetPvs().mEntries.begin();

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

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

			if (vc->GetMesh())
				exporter->ExportViewCell(vc);
			else
			{
				PolygonContainer vcGeom;

				// export view cell geometry
				mBspTree->ConstructGeometry(vc, vcGeom);
				exporter->ExportPolygons(vcGeom);
				CLEAR_CONTAINER(vcGeom);
			}

			Debug << i << ": pvs size=" << (int)vc->GetPvs().GetSize() 
					<< ", piercing rays=" << (int)vcRays.size() << endl;

			// export rays piercing this view cell
			if (exportRays)
			{
				//exporter->ExportRays(vcRays, RgbColor(1, 0, 0));
				exporter->ExportRays(vspBspLeaves[i]->mVssRays, RgbColor(1, 1, 1));
			}

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

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

			// output PVS of view cell
			for (; it != vc->GetPvs().mEntries.end(); ++ it) 
			{
				Intersectable *intersect = (*it).first;
				if (!intersect->Mailed())
				{
					exporter->ExportIntersectable(intersect);
					intersect->Mail();
				}			
			}
			Debug << "here1 exportgeom: " << exportGeometry << endl;
			// output rest of the objects
			if (exportGeometry)
			{
				Material m;//= RandomMaterial();
				m.mDiffuseColor = RgbColor(0, 0, 1);
				exporter->SetForcedMaterial(m);

				for (int j = 0; j < objects.size(); ++ j)
					if (!objects[j]->Mailed())
					{
						exporter->SetForcedMaterial(m);
						exporter->ExportIntersectable(objects[j]);
						objects[j]->Mail();
					}
			}
			DEL_PTR(exporter);
			cout << "finished" << endl;
		}
	}
	else
	{
		ViewCellContainer viewCells;

		mBspTree->CollectViewCells(viewCells);
		stable_sort(viewCells.begin(), viewCells.end(), vc_gt);

		int limit = min(leafOut, (int)viewCells.size()); 
		
		for (int i = 0; i < limit; ++ i)
		{
			cout << "creating output for view cell " << i << " ... ";
			VssRayContainer vcRays;
            Intersectable::NewMail();
			BspViewCell *vc = dynamic_cast<BspViewCell *>(viewCells[i]);

			cout << "creating output for view cell " << i << " ... ";

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

			if (vc->GetMesh())
				exporter->ExportViewCell(vc);
			else
			{
				PolygonContainer vcGeom;
				// export view cell
				mBspTree->ConstructGeometry(vc, vcGeom);
				exporter->ExportPolygons(vcGeom);
				CLEAR_CONTAINER(vcGeom);
			}

			
			Debug << i << ": pvs size=" << (int)vc->GetPvs().GetSize() 
				  << ", piercing rays=" << (int)vcRays.size() << endl;

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

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


bool BspViewCellsManager::MergeBspLeafViewCells(BspLeaf *front, BspLeaf *back) const
{
	BspViewCell *viewCell = 
		dynamic_cast<BspViewCell *>(MergeViewCells(*front->GetViewCell(), *back->GetViewCell()));
	
	if (!viewCell)
		return false;

	//-- change pointer to view cells of all leaves associated with the previous view cells
	BspViewCell *fVc = front->GetViewCell();
	BspViewCell *bVc = back->GetViewCell();

	vector<BspLeaf *> fLeaves = fVc->mLeaves;
	vector<BspLeaf *> bLeaves = bVc->mLeaves;

	vector<BspLeaf *>::const_iterator it;
	
	for (it = fLeaves.begin(); it != fLeaves.end(); ++ it)
	{
		(*it)->SetViewCell(viewCell);
		viewCell->mLeaves.push_back(*it);
	}
	for (it = bLeaves.begin(); it != bLeaves.end(); ++ it)
	{
		(*it)->SetViewCell(viewCell);
		viewCell->mLeaves.push_back(*it);
	}
	
	DEL_PTR(fVc);
	DEL_PTR(bVc);

	return true;
}

bool BspViewCellsManager::ShouldMerge(BspLeaf *front, BspLeaf *back) const
{
	ViewCell *fvc = front->GetViewCell();
	ViewCell *bvc = back->GetViewCell();

	if ((fvc == mBspTree->GetRootCell()) || (bvc == mBspTree->GetRootCell()) || (fvc == bvc))
		return false;

	int fdiff = fvc->GetPvs().Diff(bvc->GetPvs());

	if (fvc->GetPvs().GetSize() + fdiff < mMaxPvs)
	{
		if ((fvc->GetPvs().GetSize() < mMinPvs) ||	
			(bvc->GetPvs().GetSize() < mMinPvs) ||
			((fdiff < mMinPvsDif) && (bvc->GetPvs().Diff(fvc->GetPvs()) < mMinPvsDif)))
		{
			return true;
		}
	}
	
	return false;
}


void BspViewCellsManager::ConstructBspRays(const VssRayContainer &rays,
										   const int numSamples)
{
	VssRayContainer::const_iterator it, it_end = rays.end();

	for (it = rays.begin(); it != rays.end() && mBspRays.size() < numSamples; ++ it)
	{
		VssRay *vssRay = *it;
		BspRay *ray = new BspRay(vssRay);

		ViewCellContainer viewCells;

		CastLineSegment(vssRay->mTermination, vssRay->mOrigin, viewCells);

		ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
		
		for (vit = viewCells.begin(); vit != vit_end; ++ vit)
		{
			BspViewCell *vc = dynamic_cast<BspViewCell *>(*vit);
			ray->intersections.push_back(BspIntersection(0, vc->mLeaves[0]));
		}

		mBspRays.push_back(ray);
	}
}


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

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

float KdViewCellsManager::GetProbability(ViewCell *viewCell)
{
	// compute view cell area as subsititute for probability
	AxisAlignedBox3 box = mKdTree->GetBox(mKdTree->GetRoot());
#if 0
	return GetArea(viewCell) / box.SurfaceArea();
#else
	return GetArea(viewCell) / GetAccVcArea();
#endif
}


float KdViewCellsManager::GetRendercost(ViewCell *viewCell, float objRendercost) const
{
	return viewCell->GetPvs().GetSize() * objRendercost;
}

AxisAlignedBox3 KdViewCellsManager::GetSceneBbox() const
{
	return mKdTree->GetBox();
}

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

	mKdTree->Construct();

	// create the view cells
	mKdTree->CreateAndCollectViewCells(mViewCells);
	//mKdTree->EvaluateViewCellsStats(mViewCellsStats);

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

  //$$ JB
//#if 0

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

			Debug << i << ": pvs size=" << (int)vc->GetPvs().GetSize() 
				<< ", piercing rays=" << (int)vcRays.size() << endl;
			
			// 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;
		}
	}		
}


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



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

VspKdViewCellsManager::VspKdViewCellsManager(VspKdTree *vspKdTree, 
											 int constructionSamples):
ViewCellsManager(constructionSamples), 
mVspKdTree(vspKdTree)
{
	mVspKdTree->SetViewCellsManager(this);
}

float VspKdViewCellsManager::GetProbability(ViewCell *viewCell)
{
	// volume or area substitutes for view point probability
	AxisAlignedBox3 box = mVspKdTree->GetBBox(mVspKdTree->GetRoot());

	return GetArea(viewCell) / box.SurfaceArea();
	//return GetArea(viewCell) / GetAccVcArea();
}


float VspKdViewCellsManager::GetRendercost(ViewCell *viewCell, float objRendercost) const
{
	return viewCell->GetPvs().GetSize() * objRendercost;
}


int VspKdViewCellsManager::Construct(const ObjectContainer &objects, 
									 const VssRayContainer &rays,
									 AxisAlignedBox3 *sceneBbox)
{
	// if view cells already constructed
	if (ViewCellsConstructed())
		return 0;
		
	VssRayContainer constructionRays;
	VssRayContainer savedRays;

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

	mVspKdTree->Construct(constructionRays, sceneBbox);
	mVspKdTree->CollectViewCells(mViewCells);
	//mVspBspTree->EvaluateViewCellsStats(mViewCellsStats);

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

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

	// recast rest of rays
	ComputeSampleContributions(savedRays);

	return merged;
}

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


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

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

	return 0;
}

AxisAlignedBox3 VspKdViewCellsManager::GetSceneBbox() const
{
	return mVspKdTree->GetBBox(mVspKdTree->GetRoot());
}

void VspKdViewCellsManager::Visualize(const ObjectContainer &objects,
									  const VssRayContainer &sampleRays)
{
	bool exportRays = false;
	bool exportGeometry = false;

	environment->GetBoolValue("VspKdTree.Visualization.exportRays", exportRays);
	environment->GetBoolValue("VspKdTree.Visualization.exportGeometry", exportGeometry);

	if (!ViewCellsConstructed())
		return;

	//-- export tree leaves
	if (1)
	{
		Exporter *exporter = Exporter::GetExporter("vspkdtree.x3d"); 
		//exporter->SetWireframe();
		//exporter->ExportVspKdTree(*mVspKdTree, mVspKdTree->GetStatistics().maxPvsSize);
		exporter->ExportVspKdTree(*mVspKdTree);

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

		if (exportRays) 
		  {
			int raysSize = 2000;
			float prob = raysSize / (float)sampleRays.size();
		
			exporter->SetWireframe();
			
			VssRayContainer rays;
		
			for (int i = 0; i < sampleRays.size(); ++ i)
			{
				if (RandomValue(0,1) < prob)
					rays.push_back(sampleRays[i]);
			}

			exporter->ExportRays(rays, RgbColor(1, 0, 0));
		}

		delete exporter;
	}

	//-- export single leaves
	if (1)
	{
		vector<VspKdLeaf *> leafContainer;
		mVspKdTree->CollectLeaves(leafContainer);

		for (int i = 0; i < 10; ++ i)
		{
			char s[64];
			sprintf(s, "vsp_leaves%04d.x3d", i);
			Exporter *exporter = Exporter::GetExporter(s);

			// export geometry
			VspKdLeaf *leaf = leafContainer[(int)RandomValue(0.0, (Real)((int)leafContainer.size() - 1))]; 
			AxisAlignedBox3 box = mVspKdTree->GetBBox(leaf);

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

			//-- export stored rays
			VssRayContainer vssRays;
			leaf->GetRays(vssRays);

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

			for (it = vssRays.begin(); it != it_end; ++ it)
				rays.push_back(*it);
			
			exporter->ExportRays(rays, RgbColor(1, 0, 0));

			//-- export stored PVS
			ObjectContainer pvsObj;
			leaf->ExtractPvs(pvsObj);
				
			exporter->ExportGeometry(pvsObj);

			delete exporter;
		}			
	}

	//-- export final view cells
	Exporter *exporter = Exporter::GetExporter("vspkdtree_merged.x3d"); 
	exporter->SetWireframe();
	//exporter->ExportVspKdTreeViewCells(*mVspKdTree, vcStats.maxPvs);
	exporter->ExportVspKdTreeViewCells(*mVspKdTree);

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

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

	delete exporter;
}

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


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



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

VspBspViewCellsManager::VspBspViewCellsManager(VspBspTree *vspBspTree, 
											   int constructionSamples):
ViewCellsManager(constructionSamples), 
mVspBspTree(vspBspTree)
{
}


VspBspViewCellsManager::~VspBspViewCellsManager()
{
	CLEAR_CONTAINER(mBspRays);
}


float VspBspViewCellsManager::GetProbability(ViewCell *viewCell)
{
#if 0
	return GetArea(viewCell) / mVspBspTree->GetBbox().SurfaceArea();
#else
	return GetArea(viewCell) / GetAccVcArea();
#endif
}


float VspBspViewCellsManager::GetArea(ViewCell *viewCell) const
{
	PolygonContainer geom;

	// compute view cell area
	mVspBspTree->ConstructGeometry(dynamic_cast<BspViewCell *>(viewCell), geom);
	
	const float area = Polygon3::GetArea(geom);
	CLEAR_CONTAINER(geom);

	return area;
}


float VspBspViewCellsManager::GetRendercost(ViewCell *viewCell, 
											float objRendercost) const
{
	return viewCell->GetPvs().GetSize() * objRendercost;
}


AxisAlignedBox3 VspBspViewCellsManager::GetSceneBbox() const
{
	return mVspBspTree->GetBoundingBox();
}


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


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

int VspBspViewCellsManager::Construct(const ObjectContainer &objects, 
									  const VssRayContainer &rays,
									  AxisAlignedBox3 *sceneBbox)
{
	// if view cells were already constructed
	if (ViewCellsConstructed())
		return 0;

	int sampleContributions = 0;
	
	VssRayContainer constructionRays;
	VssRayContainer savedRays;

	GetRaySets(rays, constructionRays, savedRays);
	
	mVspBspTree->Construct(constructionRays);
	mVspBspTree->CollectViewCells(mViewCells);
	mVspBspTree->EvaluateViewCellsStats(mViewCellsStats);
	
	Debug << mVspBspTree->GetStatistics() << endl;
	
	// recast rest of rays
	ComputeSampleContributions(savedRays);

	return sampleContributions;
}


void VspBspViewCellsManager::ConstructBspRays(const VssRayContainer &rays,
											  const int numSamples)
{
	VssRayContainer::const_iterator it, it_end = rays.end();

	for (it = rays.begin(); it != rays.end() && mBspRays.size() < numSamples; ++ it)
	{
		VssRay *vssRay = *it;
		BspRay *ray = new BspRay(vssRay);

		ViewCellContainer viewCells;

		CastLineSegment(vssRay->mTermination, vssRay->mOrigin, viewCells);

		ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
		
		for (vit = viewCells.begin(); vit != vit_end; ++ vit)
		{
			BspViewCell *vc = dynamic_cast<BspViewCell *>(*vit);
			ray->intersections.push_back(BspIntersection(0, vc->mLeaves[0]));
		}

		mBspRays.push_back(ray);
	}
}


int VspBspViewCellsManager::PostProcess(const ObjectContainer &objects, 
										const VssRayContainer &rays)
{
	if (mBspRays.empty())
		ConstructBspRays(rays, mConstructionSamples);
	
	if (!ViewCellsConstructed())
	{
		Debug << "view cells not constructed" << endl;
		return 0;
	}

	//-- post processing of bsp view cells
    int vcSize = 0;
	int pvsSize = 0;

	Debug << "original view cell partition:\n" << mViewCellsStats << endl;
		
	if (1) // export view cells
	{
		cout << "exporting initial view cells (=leaves) ... ";
		Exporter *exporter = Exporter::GetExporter("view_cells.x3d");
	
		if (exporter)
		{
			//exporter->SetWireframe();
			exporter->SetFilled();
			exporter->ExportBspViewCellPartition(*mVspBspTree, mViewCellsStats.maxPvs);
				
			if (0)
			{
				Material m;
				m.mDiffuseColor = RgbColor(0, 1, 0);
				exporter->SetForcedMaterial(m);
				exporter->SetWireframe();

				exporter->ExportGeometry(objects);
			}

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

	cout << "starting post processing using " << mPostProcessSamples << " samples ... ";
		
	long startTime = GetTime();


	// $$JB we do not have connectivity information from the ray in the moment
	// perhaps we could recast the rays or rember the cells traversed inside the
	// vssray (which would on other hand create some overhead)
	//-- merge or subdivide view cells
	int merged = 0;

	vector<BspIntersection>::const_iterator iit;

	for (int i = 0; i < (int)mBspRays.size(); ++ i)
	{  
		BspRay *ray = mBspRays[i];
	  
		// traverse leaves stored in the rays and compare and merge consecutive
		// leaves (i.e., the neighbors in the tree)
		if (ray->intersections.size() < 2)
			continue;
	  
		iit = ray->intersections.begin();

		BspLeaf *previousLeaf = (*iit).mLeaf;
		++ iit;
		
		for (; iit != ray->intersections.end(); ++ iit)
		{
			BspLeaf *leaf = (*iit).mLeaf;

			if (ShouldMerge(leaf, previousLeaf))
			{			
				MergeVspBspLeafViewCells(leaf, previousLeaf);

				++ merged;
			}
		
			previousLeaf = leaf;
		}
	}

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

	Debug << "Postprocessing: Merged " << merged << " view cells in "
		  << TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl << endl;
	
	// reset view cells and stats
	mViewCells.clear();
	mVspBspTree->CollectViewCells(mViewCells);
	mViewCellsStats.Reset();
	mVspBspTree->EvaluateViewCellsStats(mViewCellsStats);

	return merged;
}

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


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

	if (mBspRays.empty())
		ConstructBspRays(sampleRays, mConstructionSamples);
	
	if (1) // export view cells
	{
		cout << "exporting view cells after merge ... ";
		Exporter *exporter = Exporter::GetExporter("merged_view_cells.x3d");

		if (exporter)
		{
			exporter->ExportBspViewCellPartition(*mVspBspTree, mViewCellsStats.maxPvs);
			delete exporter;
		}
		
		cout << "finished" << endl;
	}	

	//-- visualization of the BSP splits
	bool exportSplits = false;
	environment->GetBoolValue("BspTree.Visualization.exportSplits", exportSplits);
	
	if (exportSplits)
	{
		cout << "exporting splits ... ";
	 	ExportSplits(objects);
		cout << "finished" << endl;
	}

	ExportBspPvs(objects);
}


void VspBspViewCellsManager::ExportSplits(const ObjectContainer &objects)
{
	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 (0)
		{
			VssRayContainer outRays;
		
			int raysSize = min((int)mBspRays.size(), mVisualizationSamples);

			for (int i = 0; i < raysSize; ++ i)
				// only rays piercing geometry
				outRays.push_back(mBspRays[i]->vssRay);
						
			// export rays 
			exporter->ExportRays(outRays, RgbColor(1, 1, 0));
		}

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

		delete exporter;
	}
}

void VspBspViewCellsManager::ExportBspPvs(const ObjectContainer &objects)
{
	bool exportRays = false;
	bool exportGeometry = false;

	environment->GetBoolValue("VspBspTree.Visualization.exportRays", exportRays);
	environment->GetBoolValue("VspBspTree.Visualization.exportGeometry", exportGeometry);

	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;

	if (1)
	{
		//-- some random view cells and rays for output
		vector<BspLeaf *> vspBspLeaves;

		for (int i = 0; i < leafOut; ++ i)
			vspBspLeaves.push_back(mVspBspTree->GetRandomLeaf());	
		
		for (int i = 0; i < (int)vspBspLeaves.size(); ++ i)
		{
			VssRayContainer vcRays;
			cout << "creating output for view cell " << i << " ... ";

			// 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 (vspBspLeaves[i]->GetViewCell() == leaf->GetViewCell()) 
					{
						vcRays.push_back(ray->vssRay);
					}
				}
			}

			Intersectable::NewMail();

			BspViewCell *vc = dynamic_cast<BspViewCell *>
				(vspBspLeaves[i]->GetViewCell());

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

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

			ObjectPvsMap::iterator it = vc->GetPvs().mEntries.begin();

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

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

			if (vc->GetMesh())
				exporter->ExportViewCell(vc);
			else
			{
				PolygonContainer vcGeom;

				// export view cell geometry
				mVspBspTree->ConstructGeometry(vc, vcGeom);
				exporter->ExportPolygons(vcGeom);
				CLEAR_CONTAINER(vcGeom);
			}

			Debug << i << ": pvs size=" << (int)vc->GetPvs().GetSize() 
					<< ", piercing rays=" << (int)vcRays.size() << endl;

			// export rays piercing this view cell
			if (exportRays)
			{
				//exporter->ExportRays(vcRays, RgbColor(1, 0, 0));
				exporter->ExportRays(vspBspLeaves[i]->mVssRays, RgbColor(1, 1, 1));
			}

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

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

			// output PVS of view cell
			for (; it != vc->GetPvs().mEntries.end(); ++ it) 
			{
				Intersectable *intersect = (*it).first;
				if (!intersect->Mailed())
				{
					exporter->ExportIntersectable(intersect);
					intersect->Mail();
				}			
			}
			Debug << "here1 exportgeom: " << exportGeometry << endl;
			// output rest of the objects
			if (exportGeometry)
			{
				Material m;//= RandomMaterial();
				m.mDiffuseColor = RgbColor(0, 0, 1);
				exporter->SetForcedMaterial(m);

				for (int j = 0; j < objects.size(); ++ j)
					if (!objects[j]->Mailed())
					{
						exporter->SetForcedMaterial(m);
						exporter->ExportIntersectable(objects[j]);
						objects[j]->Mail();
					}
			}
			DEL_PTR(exporter);
			cout << "finished" << endl;
		}
	}
	else
	{
		ViewCellContainer viewCells;

		mVspBspTree->CollectViewCells(viewCells);
		stable_sort(viewCells.begin(), viewCells.end(), vc_gt);

		int limit = min(leafOut, (int)viewCells.size()); 
		
		for (int i = 0; i < limit; ++ i)
		{
			cout << "creating output for view cell " << i << " ... ";
			VssRayContainer vcRays;
            Intersectable::NewMail();
			BspViewCell *vc = dynamic_cast<BspViewCell *>(viewCells[i]);

			cout << "creating output for view cell " << i << " ... ";

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

			if (vc->GetMesh())
				exporter->ExportViewCell(vc);
			else
			{
				PolygonContainer vcGeom;
				// export view cell
				mVspBspTree->ConstructGeometry(vc, vcGeom);
				exporter->ExportPolygons(vcGeom);
				CLEAR_CONTAINER(vcGeom);
			}

			
			Debug << i << ": pvs size=" << (int)vc->GetPvs().GetSize() 
				  << ", piercing rays=" << (int)vcRays.size() << endl;

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

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


bool VspBspViewCellsManager::MergeVspBspLeafViewCells(BspLeaf *front, 
													  BspLeaf *back) const
{
	BspViewCell *viewCell = 
		dynamic_cast<BspViewCell *>(MergeViewCells(*front->GetViewCell(), 
												   *back->GetViewCell()));
	
	if (!viewCell)
		return false;

	// change view cells of all leaves
	// associated with the previous view cells
	BspViewCell *fVc = front->GetViewCell();
	BspViewCell *bVc = back->GetViewCell();

	vector<BspLeaf *> fLeaves = fVc->mLeaves;
	vector<BspLeaf *> bLeaves = bVc->mLeaves;

	vector<BspLeaf *>::const_iterator it;
	
	for (it = fLeaves.begin(); it != fLeaves.end(); ++ it)
	{
		(*it)->SetViewCell(viewCell);
		viewCell->mLeaves.push_back(*it);
	}
	for (it = bLeaves.begin(); it != bLeaves.end(); ++ it)
	{
		(*it)->SetViewCell(viewCell);
		viewCell->mLeaves.push_back(*it);
	}
	
	DEL_PTR(fVc);
	DEL_PTR(bVc);

	return true;
}

bool VspBspViewCellsManager::ShouldMerge(BspLeaf *front, BspLeaf *back) const
{
	ViewCell *fvc = front->GetViewCell();
	ViewCell *bvc = back->GetViewCell();

	if ((fvc == mVspBspTree->GetRootCell()) || 
		(bvc == mVspBspTree->GetRootCell()) || 
		(fvc == bvc))
		return false;

	const int fdiff = fvc->GetPvs().Diff(bvc->GetPvs());

	if (fvc->GetPvs().GetSize() + fdiff < mMaxPvs)
	{
		if ((fvc->GetPvs().GetSize() < mMinPvs) ||	
			(bvc->GetPvs().GetSize() < mMinPvs) ||
			((fdiff < mMinPvsDif) && (bvc->GetPvs().Diff(fvc->GetPvs()) < mMinPvsDif)))
		{
			return true;
		}
	}
	
	return false;
}


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