#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():
mRenderer(NULL),
mConstructionSamples(0),
mPostProcessSamples(0),
mVisualizationSamples(0),
mTotalAreaValid(false),
mTotalArea(0.0f)
{
	mSceneBox.Initialize();
	ParseEnvironment();
}

ViewCellsManager::ViewCellsManager(int constructionSamples):
mConstructionSamples(constructionSamples),
mRenderer(NULL),
mPostProcessSamples(0),
mVisualizationSamples(0)
{
	mSceneBox.Initialize();
	ParseEnvironment();
}

void ViewCellsManager::ParseEnvironment()
{
	// visualization stuff
	environment->GetBoolValue("ViewCells.Visualization.exportRays", mExportRays);
	environment->GetBoolValue("ViewCells.Visualization.exportGeometry", mExportGeometry);

	char buf[50];

	environment->GetStringValue("ViewCells.Visualization.colorCode", buf);

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

	Debug << "colorCode: " << mColorCode << endl;
}


ViewCellsManager::~ViewCellsManager()
{
	DEL_PTR(mRenderer);
	CLEAR_CONTAINER(mViewCells);
	CLEAR_CONTAINER(mMeshContainer);
}


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


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

	return true;
}


bool ViewCellsManager::ViewPointValid(const Vector3 &viewPoint) const
{
	return mSceneBox.IsInside(viewPoint);
}


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::EvaluateViewCellsStats()
{
	mViewCellsStats.Reset();

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

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


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


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


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


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

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

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

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


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

	//-- construct prism

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

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

	Triangle3 topTri;

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

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

	mesh->Preprocess();

	return GenerateViewCell(mesh);
}


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


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


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::SetViewSpaceBox(const AxisAlignedBox3 &box)
{
	mSceneBox = box;
}


void ViewCellsManager::ResetViewCells()
{
	mViewCells.clear();

	CollectViewCells();
	mViewCellsStats.Reset();
	EvaluateViewCellsStats();

	mTotalAreaValid = false;
}


void ViewCellsManager::ComputeSampleContributions(VssRay &ray)
{



  ViewCellContainer viewcells;

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

  // matt TODO: remove this!!
  Ray hray(ray);
  float tmin = 0, tmax = 1.0;

  //hray.Init(ray.GetOrigin(), ray.GetDir(), Ray::LINE_SEGMENT);
  if (!GetSceneBbox().GetRaySegment(hray, tmin, tmax) || (tmin > tmax))
	return;

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

  CastLineSegment(origin,
				  termination,
				  viewcells);

  // copy viewcells memory efficiently
  const bool storeViewcells = false;
  if (storeViewcells) {
	ray.mViewCells.reserve(viewcells.size());
	ray.mViewCells = viewcells;
  }

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

  bool addInPlace = false;

  if (addInPlace) {
	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;
	}
  } else {
    for (; it != viewcells.end(); ++it) {
	  ViewCell *viewcell = *it;
	  // if ray not outside of view space
	  float contribution;
	  if (viewcell->GetPvs().GetSampleContribution(ray.mTerminationObject,
												   contribution
												   ))
		ray.mPvsContribution++;

	  ray.mRelativePvsContribution += contribution;
	}

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


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::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 << mViewCellsStats << endl;
}


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

	for (it = mViewCells.begin(); it != it_end; ++ it)
	{
		ExportColor(exporter, *it);
		ExportVcGeometry(exporter, *it);
	}
}



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

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

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

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

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

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

	// recast rest of the rays
	ComputeSampleContributions(savedRays);


	return sampleContributions;
}


void BspViewCellsManager::CollectViewCells()
{
	mBspTree->CollectViewCells(mViewCells);
}


float BspViewCellsManager::GetProbability(ViewCell *viewCell)
{
	// compute view cell area as subsititute for probability
#if 0
	return GetArea(viewCell) / GetSceneBbox().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 (!ViewCellsConstructed())
	{
		Debug << "view cells not constructed" << endl;
		return 0;
	}

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

	EvaluateViewCellsStats();
	Debug << "\noriginal view cell partition:\n" << mViewCellsStats << endl;

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

    Debug << ss << 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();
			ExportViewCells(exporter);

			if (mExportGeometry)
			{
				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 remember 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;
	CLEAR_CONTAINER(mBspRays);
	ConstructBspRays(rays, mPostProcessSamples);

	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"
		  << "using " << (int)mBspRays.size() << " samples" << endl << endl;

	CLEAR_CONTAINER(mBspRays);

	// reset view cells and stats
	ResetViewCells();

	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;
	CLEAR_CONTAINER(mBspRays);
	ConstructBspRays(sampleRays, mVisualizationSamples);

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

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

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

		exporter->SetFilled();

		// 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 (mExportGeometry)
			exporter->ExportGeometry(objects);

		delete exporter;
	}
}


void BspViewCellsManager::ExportBspPvs(const ObjectContainer &objects)
{
	const int leafOut = 10;

	ViewCell::NewMail();

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

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

	// sort view cells to get largest view cells
#if 0
	stable_sort(mViewCells.begin(), mViewCells.end(), vc_gt);
#endif
	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();
#if 0
		BspViewCell *vc = dynamic_cast<BspViewCell *>(mViewCells[i]);
#else
		BspViewCell *vc = dynamic_cast<BspViewCell *>(mViewCells[Random((int)mViewCells.size())]);
#endif
		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);
			}
		}
#endif
		//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
		{
			BspNodeGeometry vcGeom;

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

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


		// export rays piercing this view cell
#if 0
		exporter->ExportRays(vcRays, RgbColor(0, 1, 0));
#else
		vector<BspLeaf *>::const_iterator lit, lit_end = vc->mLeaves.end();
		for (lit = vc->mLeaves.begin(); lit != lit_end; ++ lit)
			exporter->ExportRays((*lit)->mVssRays);
#endif
		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;
}


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;

		// cast line segment to get intersections with bsp leaves
		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);
	}
}


void BspViewCellsManager::ExportColor(Exporter *exporter,
									  ViewCell *vc) const
{
	if (mColorCode == 0) // Random color
	{
		exporter->ResetForcedMaterial();
		return;
	}

	float importance = 0;

	switch (mColorCode)
	{
	case 1: // pvs
		{
			importance = (float)vc->GetPvs().GetSize() /
				(float)mViewCellsStats.maxPvs;
		}
		break;
	case 2: // merges
		{
			BspViewCell *bspVc = dynamic_cast<BspViewCell *>(vc);

			importance = (float)bspVc->mLeaves.size() /
				(float)mViewCellsStats.maxLeaves;
		}
		break;
	case 3: // merge tree differene
		{
			// TODO
		}
		break;
	default:
		break;
	}

	Material m;
	m.mDiffuseColor.b = 1.0f;
	m.mDiffuseColor.r = importance;
	m.mDiffuseColor.g = 1.0f - m.mDiffuseColor.r;

	exporter->SetForcedMaterial(m);
}

void BspViewCellsManager::ExportVcGeometry(Exporter *exporter,
										 ViewCell *vc) const
{
	if (vc->GetMesh())
		exporter->ExportViewCell(vc);
	else
	{
		BspNodeGeometry geom;
		mBspTree->ConstructGeometry(
			dynamic_cast<BspViewCell *>(vc), geom);
		exporter->ExportPolygons(geom.mPolys);
	}
}


void BspViewCellsManager::CreateMesh(ViewCell *vc)
{
}

ViewCell *
BspViewCellsManager::GetViewCell(const Vector3 &point)
{
  if (!mBspTree)
	return NULL;
  return mBspTree->GetViewCell(point);
}

/**********************************************************************/
/*                   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) / GetSceneBbox().SurfaceArea();
#endif
#if 1
	return GetArea(viewCell) / GetAccVcArea();
#endif
#if 0
	return GetVolume(viewCell) / GetSceneBbox().GetVolume();
#endif
}


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


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

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

int KdViewCellsManager::Construct(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);

	EvaluateViewCellsStats();
	Debug << "\nView cells after construction:\n" << mViewCellsStats << 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);

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


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


void KdViewCellsManager::ExportVcGeometry(Exporter *exporter,
										  ViewCell *vc) const
{
	KdViewCell *kdVc = dynamic_cast<KdViewCell *>(vc);
	vector<KdLeaf *>::const_iterator it, it_end = kdVc->mLeaves.end();

	for (it = kdVc->mLeaves.begin(); it != it_end; ++ it)
		exporter->ExportBox(mKdTree->GetBox(*it));
}


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

/**********************************************************************/
/*                   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
#if 0
	return GetArea(viewCell) / GetSceneBbox().SurfaceArea();
#else
	return GetArea(viewCell) / GetAccVcArea();
#endif
}


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


void VspKdViewCellsManager::CollectViewCells()
{
	mVspKdTree->CollectViewCells(mViewCells);
}

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

	VssRayContainer constructionRays;
	VssRayContainer savedRays;

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

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

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

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

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

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

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

	// evaluale view cell stats
	ResetViewCells();

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

	long startTime = GetTime();
	// recast rest of rays
	ComputeSampleContributions(savedRays);

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

	return merged;
}

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


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

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

	// recalculate stats
	EvaluateViewCellsStats();

	return 0;
}


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


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

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

	//exporter->SetWireframe();
	//exporter->ExportVspKdTree(*mVspKdTree, mVspKdTree->GetStatistics().maxPvsSize);
	exporter->ExportVspKdTree(*mVspKdTree);

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

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

		exporter->SetWireframe();

		//-- collect uniformly distributed rays
		VssRayContainer rays;

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

	delete exporter;
}

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

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

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

		cout << "Output view cell " << i << " with pvs size " << vc->GetPvs().GetSize() << endl;
		Debug << "Output view cell " << i << " with pvs size " << vc->GetPvs().GetSize() << endl;
		//-- export geometry
		Material m;
		m.mDiffuseColor = RgbColor(0, 1, 1);

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

		ExportVcGeometry(exporter, vc);

		//-- export stored rays
		if (mExportRays)
		{
			vector<VspKdLeaf *>::const_iterator it,
				it_end = vc->mLeaves.end();

			for (it = vc->mLeaves.begin(); it != it_end; ++ it)
			{
				VspKdLeaf *leaf = *it;
				AxisAlignedBox3 box = mVspKdTree->GetBBox(leaf);

				VssRayContainer vssRays;

				VssRayContainer castRays;
				VssRayContainer initRays;

				leaf->GetRays(vssRays);

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

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

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

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

		Intersectable::NewMail();

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

		exporter->SetFilled();

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

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

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

		delete exporter;
	}

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

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

	ExportViewCells(exporter);

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

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

		exporter->SetWireframe();

		VssRayContainer rays;

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

	delete exporter;
}

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


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


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

	float importance = 0;

	switch (mColorCode)
	{
	case 1: // pvs
		{
			importance = (float)vc->GetPvs().GetSize() /
				(float)mViewCellsStats.maxPvs;
		}
		break;
	case 2: // merges
		{
            VspKdViewCell *vspKdVc = dynamic_cast<VspKdViewCell *>(vc);

			importance = (float)vspKdVc->mLeaves.size() /
				(float)mViewCellsStats.maxLeaves;
		}
		break;
	case 3: // merged tree depth difference
		{
			//importance = (float)GetMaxTreeDiff(vc) /
			//	(float)(mVspBspTree->GetStatistics().maxDepth * 2);
		}
		break;
	default:
		break;
	}

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


void VspKdViewCellsManager::ExportVcGeometry(Exporter *exporter,
										   ViewCell *vc) const
{
	VspKdViewCell *kdVc = dynamic_cast<VspKdViewCell *>(vc);
	vector<VspKdLeaf *>::const_iterator it, it_end = kdVc->mLeaves.end();

	Mesh m;
	for (it = kdVc->mLeaves.begin(); it != it_end; ++ it)
	{
		mVspKdTree->GetBBox(*it).AddBoxToMesh(&m);
	}

	exporter->ExportMesh(&m);
}


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

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


VspBspViewCellsManager::VspBspViewCellsManager(VspBspTree *vspBspTree,
											   int constructionSamples):
ViewCellsManager(constructionSamples),
mVspBspTree(vspBspTree)
{
	mVspBspTree->SetViewCellsManager(this);
}


VspBspViewCellsManager::~VspBspViewCellsManager()
{
}


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


void VspBspViewCellsManager::CollectViewCells()
{
	mVspBspTree->CollectViewCells(mViewCells);
}


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)
{
	// if view cells were already constructed
	if (ViewCellsConstructed())
		return 0;

	Debug << "Constructing bsp view cells" << endl;

	int sampleContributions = 0;

	VssRayContainer sampleRays;

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

	VssRayContainer constructionRays;
	VssRayContainer savedRays;

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

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

	mVspBspTree->Construct(constructionRays, &mSceneBox);

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

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

	cout << "reseting view cell stats ... ";
	ResetViewCells();
	cout << "finished" << endl;

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

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

		if (exporter)
		{
			//exporter->SetWireframe();
			exporter->SetFilled();
			ExportViewCells(exporter);

			if (0 && mExportRays)
				exporter->ExportRays(rays, RgbColor(1, 1, 1));

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

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

	startTime = GetTime();

	//-- merge the individual view cells: Should be done here because it makes
	MergeViewCells(rays, objects);
	//-- refines the merged view cells
	RefineViewCells(rays);
	// collapse sibling leaves that share the same view cell
	mVspBspTree->CollapseTree();

	// reset view cells and stats
	ResetViewCells();

	cout << "Computing remaining ray contributions ... ";
	// recast rest of rays
	ComputeSampleContributions(savedRays);
	cout << "finished" << endl;

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

	cout << "construction finished" << endl;

	return sampleContributions;
}


void VspBspViewCellsManager::MergeViewCells(const VssRayContainer &rays,
											const ObjectContainer &objects)
{
	//-- post processing of bsp view cells
    int vcSize = 0;
	int pvsSize = 0;

	VssRayContainer postProcessRays;
	GetRaySets(rays, mPostProcessSamples, postProcessRays);

	Debug << "post processing using " << (int)postProcessRays.size() << " samples" << endl;
	EvaluateViewCellsStats();
	Debug << "\noriginal view cell partition:\n" << mViewCellsStats << endl << endl;

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

	//-- merge or subdivide view cells
	int merged = 0;

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

	// TODO: should be done BEFORE the ray casting
	merged = mVspBspTree->MergeViewCells(postProcessRays);

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

	cout << "reseting view cell stats ... ";
	ResetViewCells();
	cout << "finished" << endl;

	//BspLeaf::NewMail();
	if (1) // export merged view cells
	{
		Exporter *exporter = Exporter::GetExporter("merged_view_cells.x3d");
		Debug << "\nView cells after merge:\n" << mViewCellsStats << endl;

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

		if (exporter)
		{
			//exporter->SetWireframe();
			exporter->SetFilled();
			ExportViewCells(exporter);

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

				exporter->ExportGeometry(objects);
			}

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


void VspBspViewCellsManager::RefineViewCells(const VssRayContainer &rays)
{
	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 = mVspBspTree->RefineViewCells(rays);

	//-- 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 << "view cells not constructed" << endl;
		return 0;
	}

	CreateViewCellsMeshes();

	return 0;
}


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


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 = mSceneBox.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
{
	return mSceneBox.IsInside(viewPoint) &&
		   mVspBspTree->ViewPointValid(viewPoint);
}


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

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

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

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

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

			ExportViewCells(exporter);
			delete exporter;
		}

		cout << "finished" << endl;
	}

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

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

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


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

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

		exporter->ExportBspSplits(*mVspBspTree, true);

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

		exporter->ResetForcedMaterial();

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

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

		delete exporter;
	}
}


void VspBspViewCellsManager::ExportBspPvs(const ObjectContainer &objects,
										  const VssRayContainer &rays)
{
	const int leafOut = 10;

	ViewCell::NewMail();

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

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

#if 1
	//-- some rays for output
	vector<BspRay *> bspRays;
	mVspBspTree->ConstructBspRays(bspRays, rays);

	const int raysOut = min((int)bspRays.size(), mVisualizationSamples);
#endif

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

		VssRayContainer vcRays;
		Intersectable::NewMail();
#if 0
		BspViewCell *vc = dynamic_cast<BspViewCell *>(mViewCells[i]);
#else
		BspViewCell *vc = dynamic_cast<BspViewCell *>
			(mViewCells[Random((int)mViewCells.size())]);
#endif

#if 1
		// check whether we can add the current ray to the output rays
		for (int k = 0; k < raysOut; ++ k)
		{
			BspRay *ray = bspRays[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);
			}
		}
#endif
		//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);

		ExportVcGeometry(exporter, vc);


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

		//-- export rays piercing this view cell
#if 1
		exporter->ExportRays(vcRays, RgbColor(1, 1, 1));
#endif
#if 0
		vector<BspLeaf *>::const_iterator lit, lit_end = vc->mLeaves.end();

		for (lit = vc->mLeaves.begin(); lit != lit_end; ++ lit)
			exporter->ExportRays((*lit)->mVssRays);
#endif
		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;
	}

#if 1
	CLEAR_CONTAINER(bspRays);
#endif
	Debug << endl;
}


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


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

	float importance = 0;

	switch (mColorCode)
	{
	case 1: // pvs
		{
			importance = (float)vc->GetPvs().GetSize() /
				(float)mViewCellsStats.maxPvs;
		}
		break;
	case 2: // merges
		{
            BspViewCell *bspVc = dynamic_cast<BspViewCell *>(vc);

			importance = (float)bspVc->mLeaves.size() /
				(float)mViewCellsStats.maxLeaves;
		}
		break;
	case 3: // merge tree differene
		{
			importance = (float)GetMaxTreeDiff(vc) /
				(float)(mVspBspTree->GetStatistics().maxDepth * 2);
		}
		break;
	default:
		break;
	}

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


void VspBspViewCellsManager::ExportVcGeometry(Exporter *exporter,
											  ViewCell *vc) const
{
#if 1
    if (vc->GetMesh())
	{
		exporter->ExportMesh(vc->GetMesh());
		return;
	}

	BspNodeGeometry geom;
	mVspBspTree->
		ConstructGeometry(dynamic_cast<BspViewCell *>(vc), geom);
	exporter->ExportPolygons(geom.mPolys);
#else

	Material m2;
	m2.mDiffuseColor.b = 0.3f + Random(0.7f);
	m2.mDiffuseColor.r = 0.0f;//0.3f + Random(0.7f);
	m2.mDiffuseColor.g = 0.3f + Random(0.7f);
	Material m;
	m.mDiffuseColor.b = 0.0f;
	m.mDiffuseColor.r = 1.0f;
	m.mDiffuseColor.g = 0.0f;

	BspViewCell *bspVc = dynamic_cast<BspViewCell *>(vc);
	vector<BspLeaf *>::const_iterator it, it_end = bspVc->mLeaves.end();

	for (it = bspVc->mLeaves.begin(); it != it_end; ++ it)
	{
		if ((*it)->Mailed())
			exporter->SetForcedMaterial(m);
		else
			exporter->SetForcedMaterial(m2);
			//exporter->ResetForcedMaterial();
		BspNodeGeometry geom;
		mVspBspTree->ConstructGeometry(*it, geom);
		exporter->ExportPolygons(geom.mPolys);
	}
#endif
}


int VspBspViewCellsManager::GetMaxTreeDiff(ViewCell *vc) const
{
	BspViewCell *bspVc = dynamic_cast<BspViewCell *>(vc);

	int maxDist = 0;
	// compute max height difference
	for (int i = 0; i < (int)bspVc->mLeaves.size(); ++ i)
		for (int j = 0; j < (int)bspVc->mLeaves.size(); ++ j)
	{
		BspLeaf *leaf = bspVc->mLeaves[i];

		if (i != j)
		{
			BspLeaf *leaf2 = bspVc->mLeaves[j];
			int dist = mVspBspTree->TreeDistance(leaf, leaf2);
			if (dist > maxDist)
				maxDist = dist;
		}
	}
	return maxDist;
}


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


void VspBspViewCellsManager::CreateMesh(ViewCell *vc)
{
	BspNodeGeometry geom;
	BspViewCell *bspVc = dynamic_cast<BspViewCell *>(vc);
	mVspBspTree->ConstructGeometry(bspVc, geom);

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