#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"



ViewCellsManager::ViewCellsManager():
mRenderSimulator(NULL),
mConstructionSamples(0),
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(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);
}

void ViewCellsManager::InitRenderSimulator()
{
	float objRenderCost = 0, vcOverhead = 0, moveSpeed = 0;

	environment->GetFloatValue("Simulation.objRenderCost",objRenderCost);
	environment->GetFloatValue("Simulation.vcOverhead", vcOverhead);
	environment->GetFloatValue("Simulation.moveSpeed", moveSpeed);

	mRenderSimulator->SetObjectRenderCost(objRenderCost);
	mRenderSimulator->SetVcOverhead(vcOverhead);
	mRenderSimulator->SetMoveSpeed(moveSpeed);
}

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 RayContainer &rays, 
												  const bool castRays,
												  int &sampleContributions,
												  int &contributingSamples)
{
	// view cells not yet constructed
	if (!ViewCellsConstructed())
		return;

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

    for (it = rays.begin(); it != it_end; ++ it)
	{
		sampleContributions +=ComputeSampleContributions(*(*it), castRays);
		contributingSamples += sampleContributions > 0;
	}
}

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

SimulationStatistics ViewCellsManager::SimulateRendering() const
{
	if (!ViewCellsConstructed())
		return SimulationStatistics();

	return mRenderSimulator->SimulateRendering();
}

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


void ViewCellsManager::SetVisualizationSamples(const int visSamples)
{
	int 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;
}

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

BspViewCellsManager::BspViewCellsManager(BspTree *bspTree, int constructionSamples):
ViewCellsManager(constructionSamples), 
mBspTree(bspTree)
{
   mRenderSimulator = new BspRenderSimulator(bspTree);
   InitRenderSimulator();
}

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;

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

	int sampleContributions = 0;
	
	RayContainer sampleRays;

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

    for (int i = 0; i < limit; ++ i)
		sampleRays.push_back(new Ray(*rays[i]));

	if (mViewCells.empty()) // no view cells loaded
		mBspTree->Construct(objects, sampleRays);
	else
		mBspTree->Construct(mViewCells);

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

	return sampleContributions;
}

int BspViewCellsManager::ComputeSampleContributions(Ray &ray, const bool castRay)
{
	// view cells not yet constructed
	if (!ViewCellsConstructed())
		return 0;

	int contributingSamples = 0;

	if (castRay)
		mBspTree->CastRay(ray);
	
	//if (mBspTree->bspIntersections.empty()) return 0;

	Intersectable *tObject = 
		!ray.intersections.empty() ? ray.intersections[0].mObject : NULL;

	Intersectable *sObject = ray.sourceObject.mObject;

	if (sObject || tObject)
	{
		// object can be seen from the view cell => add to view cell pvs
		for (int j = 0; j < (int)ray.bspIntersections.size(); ++ j)
		{ 	
			BspLeaf *leaf = ray.bspIntersections[j].mLeaf;
		
			// if ray not in unbounded space
			if (leaf->GetViewCell() != mBspTree->GetRootCell())
			{
				if (sObject)
				{
					contributingSamples += 
						leaf->GetViewCell()->GetPvs().AddSample(sObject);
				}

				if (tObject)
				{
					contributingSamples += 
						leaf->GetViewCell()->GetPvs().AddSample(tObject);
				}
			}
		}
	}

	// rays passing through this viewcell
	if (0)
		for (int j = 1; j < ((int)ray.bspIntersections.size() - 1); ++ j) 
		{
			BspLeaf *leaf = ray.bspIntersections[j].mLeaf;

			if (leaf->GetViewCell() != mBspTree->GetRootCell())
				leaf->GetViewCell()->
					AddPassingRay(ray, contributingSamples ? 1 : 0);
		}

	return contributingSamples;
}

int BspViewCellsManager::PostProcess(const ObjectContainer &objects, 
									 const RayContainer &rays)
{
	if (!ViewCellsConstructed())
	{
		Debug << "view cells not constructed" << endl;
		return 0;
	}


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

	BspViewCellsStatistics stat;
	mBspTree->EvaluateViewCellsStats(stat);
	Debug << "original view cell partition:\n" << stat << endl;
		
	if (1) // export view cells
	{
		cout << "exporting initial view cells (=leaves) ... ";
		Exporter *exporter = Exporter::GetExporter("view_cells.x3d");
	
		if (exporter)
		{
			exporter->SetWireframe();
			exporter->ExportBspLeaves(*mBspTree, stat.maxPvs);
			//exporter->ExportBspViewCellPartition(*mBspTree, 0);
				
			if (0)
			{
				Material m;//= RandomMaterial();
				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();


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

	RayContainer::const_iterator rit, rit_end = rays.end();
	vector<Ray::BspIntersection>::const_iterator iit;

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

	for (int i = 0; i < limit; ++ i)
	{  
		Ray *ray = rays[i];

		// traverse leaves stored in the rays and compare and merge consecutive
		// leaves (i.e., the neighbors in the tree)
		if (ray->bspIntersections.size() < 2)
			continue;

		iit = ray->bspIntersections.begin();

		BspLeaf *previousLeaf = (*iit).mLeaf;
		++ iit;
		
		for (; iit != ray->bspIntersections.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;

	return merged;
}

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


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

	//-- recount pvs
	BspViewCellsStatistics vcStats;
	mBspTree->EvaluateViewCellsStats(vcStats);

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

		if (exporter)
		{
			exporter->ExportBspViewCellPartition(*mBspTree, vcStats.maxPvs);
			//exporter->ExportBspViewCellPartition(*mBspTree, 0);
			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, sampleRays);
		cout << "finished" << endl;
	}

	ExportBspPvs(objects, sampleRays);
}


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

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

			for (int i = 0; i < raysSize; ++ i)
			{
				// only rays piercing geometry
				if (!sampleRays[i]->intersections.empty())
					outRays.push_back(sampleRays[i]);
			}
			
			// export rays 
			exporter->ExportRays(outRays, 1000, RgbColor(1, 1, 0));
		}

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

		delete exporter;
	}
}

void BspViewCellsManager::ExportBspPvs(const ObjectContainer &objects,
									   const RayContainer &sampleRays)
{
	const int leafOut = 10;
	
	ViewCell::NewMail();

	//-- some rays for output
	const int raysOut = min((int)sampleRays.size(), mVisualizationSamples);
	cout << "visualization using " << mVisualizationSamples << " samples" << endl;
	vector<Ray *> vcRays[leafOut];

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

		for (int i = 0; i < leafOut; ++ i)
			bspLeaves.push_back(mBspTree->GetRandomLeaf());	
		
		for (int i = 0; i < bspLeaves.size(); ++ 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) 
			{
				Ray *ray = sampleRays[k];

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

					if (bspLeaves[i]->GetViewCell() == leaf->GetViewCell()) 
					{
						vcRays[i].push_back(ray);
					}
				}
			}

			Intersectable::NewMail();

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

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

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

			ViewCellPvsMap::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 cell;
				// export view cell geometry
				mBspTree->ConstructGeometry(vc, cell);
				exporter->ExportPolygons(cell);
				CLEAR_CONTAINER(cell);
			}

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

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

			m.mDiffuseColor = RgbColor(1, 0, 0);
			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();
				}			
			}
				
			// output rest of the objects
			if (0)
			{
				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 << " ... ";
			
            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) 
			{
				Ray *ray = sampleRays[k];

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

					if (vc == leaf->GetViewCell()) 
					{
						vcRays[i].push_back(ray);
					}
				}
			}

			//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 cell;
				// export view cell
				mBspTree->ConstructGeometry(vc, cell);
				exporter->ExportPolygons(cell);
				CLEAR_CONTAINER(cell);
			}

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

			
			// export rays piercing this view cell
			exporter->ExportRays(vcRays[i], 1000, RgbColor(0, 1, 0));
	
			m.mDiffuseColor = RgbColor(1, 0, 0);
			exporter->SetForcedMaterial(m);

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


bool BspViewCellsManager::MergeBspLeafViewCells(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->mBspLeaves;
	vector<BspLeaf *> bLeaves = bVc->mBspLeaves;

	vector<BspLeaf *>::const_iterator it;
	
	for (it = fLeaves.begin(); it != fLeaves.end(); ++ it)
	{
		(*it)->SetViewCell(viewCell);
		viewCell->mBspLeaves.push_back(*it);
	}
	for (it = bLeaves.begin(); it != bLeaves.end(); ++ it)
	{
		(*it)->SetViewCell(viewCell);
		viewCell->mBspLeaves.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;
}



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

KdViewCellsManager::KdViewCellsManager(KdTree *kdTree):
ViewCellsManager(), 
mKdTree(kdTree), 
mKdPvsDepth(100)
{
   mRenderSimulator = new KdRenderSimulator(mKdTree);
   InitRenderSimulator();
}

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

	Debug << "Constructing bsp view cells" << endl;
	
	mKdTree->Construct();

	return 0;
}

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

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

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

	const int pvsOut = min((int)objects.size(), 10);

	int limit = min(mVisualizationSamples, (int)sampleRays.size());

	RayContainer *rays = new RayContainer[pvsOut];

	for  (int i = 0; i < limit; ++ i)
	{
		Ray *ray = sampleRays[i];

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

	bool exportRays = false;
	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], 1000, 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], 1000, 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;
	}
	DEL_PTR(rays);
}

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

int KdViewCellsManager::ComputeSampleContributions(Ray &ray, const bool castRay)
{
	// view cells not yet constructed
	if (!ViewCellsConstructed())
		return 0;

	if (castRay)
		mKdTree->CastRay(ray);

	if (ray.kdLeaves.empty())
		return 0;

	Intersectable *tObject =
		!ray.intersections.empty() ? ray.intersections[0].mObject : NULL;

	Intersectable *sObject =
		ray.sourceObject.mObject;

	int contributingSamples = 0;
	
	int objects = 0;

	if (sObject)
		objects++;
	if (tObject)
		objects++;

	for (int j = 1; j < ((int)ray.kdLeaves.size() - 1); ++ j) 
	{
		ray.kdLeaves[j]->AddPassingRay2(ray, objects,
										(int)ray.kdLeaves.size());
	}

	if (!objects)
		return 0;
	
	for (int j=0; j < ray.kdLeaves.size(); j++) 
	{
		KdNode *node = GetNodeForPvs(ray.kdLeaves[j]);

		if (sObject)
			contributingSamples += sObject->mKdPvs.AddSample(node);
		if (tObject)
			contributingSamples += tObject->mKdPvs.AddSample(node);
	}

	return contributingSamples;
}


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

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



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

VspKdViewCellsManager::VspKdViewCellsManager(VspKdTree *vspKdTree, int constructionSamples):
ViewCellsManager(constructionSamples), 
mVspKdTree(vspKdTree)
{
   mRenderSimulator = NULL; // TODO: new VspKdRenderSimulator(vspKdTree);
   InitRenderSimulator();
}

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

	mVspKdTree->Construct(rays, sceneBbox);
	return 0;
}

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

int VspKdViewCellsManager::ComputeSampleContributions(Ray &ray, const bool castRay)
{
	// view cells not yet constructed
	if (!ViewCellsConstructed())
		return 0;

	//if (castRay) // TODO

	int sampleContributions = 0;

/*
    for (int i = 0; i < (int)rays.size(); ++ i)
	{
		Ray *ray = rays[i];

		mBspTree->CastRay(*ray);
			
		Intersectable *term = 
			!ray->intersections.empty() ? ray->intersections[0].mObject : NULL
			;
		sampleContributions += 
			AddSampleContributions(*ray, ray->sourceObject.mObject, term);
			
	}
*/
	return sampleContributions;
}

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

	return 0;
}

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

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

		Debug << "average PVS size: " << mVspKdTree->GetAvgPvsSize() << endl;

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

		bool exportRays = true;

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

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

		delete exporter;
	}

	if (1)
	{
		vector<VspKdTreeLeaf *> 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
			VspKdTreeLeaf *leaf = leafContainer[Random((int)leafContainer.size())]; 
			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)
			{
				//if (!(*it)->mOriginObject && !(*it)->mTerminationObject)
					rays.push_back(*it);

				//if (!(*it)->mOriginObject && !(*it)->mTerminationObject)
				//	Debug << "ERR: " << (*it)->mOrigin << " " << (*it)->mTermination << endl;
			}

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

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

			delete exporter;
		}			
	}
}

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