#include "SceneGraph.h"
#include "KdTree.h"
#include "SamplingPreprocessor.h"
#include "X3dExporter.h"
#include "Environment.h"
#include "MutualVisibility.h"
#include "Polygon3.h"
#include "ViewCell.h"
#include "RenderSimulator.h"

SamplingPreprocessor::SamplingPreprocessor(): mPass(0)
{
  // this should increase coherence of the samples
  environment->GetIntValue("Sampling.samplesPerPass", mSamplesPerPass);
  environment->GetIntValue("Sampling.totalSamples", mTotalSamples);
  environment->GetIntValue("BspTree.Construction.samples", mBspConstructionSamples);
  environment->GetIntValue("VspKdTree.Construction.samples", mVspConstructionSamples);
  environment->GetIntValue("ViewCells.PostProcessing.samples", mPostProcessSamples);
  environment->GetIntValue("BspTree.Visualization.samples", mVisualizationSamples);
 
  mKdPvsDepth = 100;
  mStats.open("stats.log");
}

SamplingPreprocessor::~SamplingPreprocessor()
{
	CLEAR_CONTAINER(mSampleRays);
	CLEAR_CONTAINER(mVspSampleRays);
}

void
SamplingPreprocessor::SetupRay(Ray &ray, 
															 const Vector3 &point, 
															 const Vector3 &direction,
															 const int type)
{
  ray.intersections.clear();
  ray.kdLeaves.clear();
  ray.testedObjects.clear();
  ray.bspIntersections.clear();
	ray.mFlags |= Ray::STORE_KDLEAVES | Ray::STORE_BSP_INTERSECTIONS;
  //  cout<<point<<" "<<direction<<endl;
  ray.Init(point, direction, type);
}

KdNode *
SamplingPreprocessor::GetNodeForPvs(KdLeaf *leaf)
{
  KdNode *node = leaf;
  while (node->mParent && node->mDepth > mKdPvsDepth)
    node = node->mParent;
  return node;
}

bool
SamplingPreprocessor::BuildBspTree()
{
	// delete old tree
	DEL_PTR(mBspTree);
	mBspTree = new BspTree(&mUnbounded);
	ObjectContainer objects;
	
	switch (BspTree::sConstructionMethod)
	{
	case BspTree::FROM_INPUT_VIEW_CELLS:
		mBspTree->SetGenerateViewCells(false);
		mBspTree->Construct(mViewCells);
		break;
	case BspTree::FROM_SCENE_GEOMETRY:
		DeleteViewCells(); // we generate new view cells
		mBspTree->SetGenerateViewCells(true);
		mSceneGraph->CollectObjects(&objects);
		mBspTree->Construct(objects);
		break;
	case BspTree::FROM_RAYS:
		DeleteViewCells(); // we generate new view cells
		mBspTree->SetGenerateViewCells(true);
		mBspTree->Construct(mSampleRays);
		break;
	default:
		Debug << "Error: Method not available\n";
		break;
	}
	
	
	return true;
}

int
SamplingPreprocessor::AddNodeSamples(const Ray &ray,
																		 Intersectable *sObject,
																		 Intersectable *tObject
																		 )
{
  int contributingSamples = 0;
  int j;
	int objects = 0;
	if (sObject)
		objects++;
	if (tObject)
		objects++;

	if (objects) {
		for (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);
		}
	}
	
	for (j=1; j < ((int)ray.kdLeaves.size() - 1); j++) {
		ray.kdLeaves[j]->AddPassingRay2(ray,
																		objects,
																		ray.kdLeaves.size()
																		);
  }
  
  return contributingSamples;
}


int SamplingPreprocessor::AddObjectSamples(Intersectable *obj, const Ray &ray)
{
	int contributingSamples = 0;
	int j;
 
	// object can be seen from the view cell => add to view cell pvs
	for (j=0; j < ray.bspIntersections.size(); ++ j)
	{ 	
		BspLeaf *leaf = ray.bspIntersections[j].mLeaf;
		// if ray not in unbounded space
		if (leaf->GetViewCell() != &mUnbounded)
			contributingSamples += 
				leaf->GetViewCell()->GetPvs().AddSample(obj);
	}
 
	// rays passing through this viewcell
	if (mPass > 1)
		for (j=1; j < ((int)ray.bspIntersections.size() - 1); ++ j) 
		{
			BspLeaf *leaf = ray.bspIntersections[j].mLeaf;

			if (leaf->GetViewCell() != &mUnbounded)
				leaf->GetViewCell()->
					AddPassingRay(ray, contributingSamples ? 1 : 0);
		}
 
	return contributingSamples;
}


void
SamplingPreprocessor::HoleSamplingPass()
{
  vector<KdLeaf *> leaves;
  mKdTree->CollectLeaves(leaves);
  
  // go through all the leaves and evaluate their passing contribution
  for (int i=0 ; i < leaves.size(); i++) {
    KdLeaf *leaf = leaves[i];
    cout<<leaf->mPassingRays<<endl;
  }
}


int
SamplingPreprocessor::CastRay(Intersectable *object, Ray &ray)
{
	int sampleContributions = 0;

	long t1 = GetRealTime();
	// cast ray to KD tree to find intersection with other objects
	mKdTree->CastRay(ray);
	long t2 = GetRealTime();

	if (0 && object && object->GetId() > 2197) {
		object->Describe(cout)<<endl;
		cout<<ray<<endl;
	}

	switch(ViewCell::sHierarchy)
	{
	case ViewCell::BSP:
		
		//-- cast ray to BSP tree to get intersection with view cells
		if (!mBspTree)
			break;
		
		mBspTree->CastRay(ray);
			
		if (object)
			sampleContributions += AddObjectSamples(object, ray);
			
		if (!ray.intersections.empty()) // second intersection found
		{
			sampleContributions += 
				AddObjectSamples(ray.intersections[0].mObject, ray);
		}
		break;
	case ViewCell::KD:
		if (ray.kdLeaves.size()) 
		{
			Intersectable *terminator =
				ray.intersections.size() ? ray.intersections[0].mObject: NULL;

			sampleContributions += AddNodeSamples(ray,
																					object,
																					terminator);
		}
		break;
	case ViewCell::VSP:
		// TODO:
		break;
	default:
		Debug << "Should never come here" << endl;
		break;
	}

	return sampleContributions;
}

//  void
//  SamplingPreprocessor::AvsGenerateRandomRay(Ray &ray)
//  {
//    int objId = RandomValue(0, mObjects.size());
//    Intersectable *object = objects[objId];
//    object->GetRandomSurfacePoint(point, normal);
//    direction = UniformRandomVector(normal);
//    SetupRay(ray, point, direction);
//  }

//  void
//  SamplingPreprocessor::AvsHandleRay(Ray &ray)
//  {
//    int sampleContributions = 0;

//    mKdTree->CastRay(ray);
  
//    if (ray.leaves.size()) {
//      sampleContributions += AddNodeSamples(object, ray, pass);
    
//      if (ray.intersections.size()) {
//        sampleContributions += AddNodeSamples(ray.intersections[0].mObject, ray, pass);
//      }
//    }
//  }

//  void
//  SamplingPreprocessor::AvsBorderSampling(Ray &ray)
//  {
  

//  }

//  void
//  SamplingPreprocessor::AvsPass()
//  {
//    Ray ray;
//    while (1) {
//      AvsGenerateRay(ray);
//      HandleRay(ray);
//      while ( !mRayQueue.empty() ) {
//        Ray ray = mRayQueue.pop();
//        mRayQueue.pop();
//        AdaptiveBorderSampling(ray);
//      }
//    }
  
  

//  }


int
SamplingPreprocessor::CastEdgeSamples(
																			Intersectable *object,
																			const Vector3 &point,
																			MeshInstance *mi,
																			const int samples
																			)
{
	Ray ray;
	int maxTries = samples*10;
	int i;
	int rays = 0;
	int edgeSamplesContributions = 0;
	for (i=0; i < maxTries && rays < samples; i++) {
		// pickup a random face of each mesh 
		Mesh *mesh = mi->GetMesh();
		int face = RandomValue(0, mesh->mFaces.size()-1);
		
		Polygon3 poly(mesh->mFaces[face], mesh);
		poly.Scale(1.001);
		// now extend a random edge of the face
		int edge = RandomValue(0, poly.mVertices.size()-1);
		float t = RandomValue(0.0f,1.0f);
		Vector3 target = t*poly.mVertices[edge] + (1.0f-t)*poly.mVertices[(edge + 1)%
																																		 poly.mVertices.size()];
		SetupRay(ray, point, target - point, Ray::LOCAL_RAY);
		if (!mesh->CastRay(ray, mi)) {
			// the rays which intersect the mesh have been discarded since they are not tangent
			// to the mesh
			rays++;
			edgeSamplesContributions += CastRay(object, ray);
		}
	}
	return edgeSamplesContributions;
}

KdNode *
SamplingPreprocessor::GetNodeToSample(Intersectable *object)
{
	int pvsSize = object->mKdPvs.GetSize();
	KdNode *nodeToSample = NULL;
	
	bool samplePvsBoundary = false;
	if (pvsSize && samplePvsBoundary) {
		// this samples the nodes from the boundary of the current PVS
		// mail all nodes from the pvs
		Intersectable::NewMail();
		KdPvsMap::iterator i = object->mKdPvs.mEntries.begin();
		
		for (; i != object->mKdPvs.mEntries.end(); i++) {
			KdNode *node = (*i).first;
			node->Mail();
		}
		
		int maxTries = 2*pvsSize;
		Debug << "Finding random neighbour" << endl;	
		for (int tries = 0; tries < 10; tries++) {
			int index = RandomValue(0, pvsSize - 1);
			KdPvsData data;
			KdNode *node;
			object->mKdPvs.GetData(index, node, data);
			nodeToSample = mKdTree->FindRandomNeighbor(node, true);
			if (nodeToSample)
				break;
		}
	} else {
		// just pickup a random node
		//		nodeToSample = mKdTree->GetRandomLeaf(Plane3(normal, point));
		nodeToSample = mKdTree->GetRandomLeaf();
	}
	return nodeToSample;
}

void
SamplingPreprocessor::VerifyVisibility(Intersectable *object)
{
	// mail all nodes from the pvs
	Intersectable::NewMail();
	KdPvsMap::iterator i = object->mKdPvs.mEntries.begin();
	for (; i != object->mKdPvs.mEntries.end(); i++) {
		KdNode *node = (*i).first;
		node->Mail();
	}
	Debug << "Get all neighbours from PVS" << endl;
	vector<KdNode *> invisibleNeighbors;
	// get all neighbors of all PVS nodes
	i = object->mKdPvs.mEntries.begin();
	for (; i != object->mKdPvs.mEntries.end(); i++) {
		KdNode *node = (*i).first;
		mKdTree->FindNeighbors(node, invisibleNeighbors, true);
		AxisAlignedBox3 box = object->GetBox();
		for (int j=0; j < invisibleNeighbors.size(); j++) {
			int visibility = ComputeBoxVisibility(mSceneGraph,
							      mKdTree,
							      box,
							      mKdTree->GetBox(invisibleNeighbors[j]),
							      1e-6f);
			//	      exit(0);
		}
		// now rank all the neighbors according to probability that a new
		// sample creates some contribution
	}
}

bool
SamplingPreprocessor::ComputeVisibility()
{
  
  // pickup an object
  ObjectContainer objects;
  
  mSceneGraph->CollectObjects(&objects);

  Vector3 point, normal, direction;
  Ray ray;

  long startTime = GetTime();
  
  int i;
  int totalSamples = 0;

  int pvsOut = Min((int)objects.size(), 10);
  int pvsSize = 0;

  RayContainer rays[10];

  while (totalSamples < mTotalSamples) {
		int passContributingSamples = 0;
		int passSampleContributions = 0;
		int passSamples = 0;
		int index = 0;
		
		int reverseSamples = 0;
		
			
		//cout << "totalSamples: "  << totalSamples << endl;

		for (i = 0; i < objects.size(); i++) {
						
			KdNode *nodeToSample = NULL;
			Intersectable *object = objects[i];
		
			int pvsSize = 0;
			if (ViewCell::sHierarchy == ViewCell::KD)
				pvsSize = object->mKdPvs.GetSize();
						
			
			if (0 && pvsSize && mPass == 1000 ) {
				VerifyVisibility(object);
			}
			
			int faceIndex = object->GetRandomSurfacePoint(point, normal);
			
			bool viewcellSample = true;
			int sampleContributions;
			bool debug = false; //(object->GetId() >= 2199);
			if (viewcellSample) {
				//mKdTree->GetRandomLeaf(Plane3(normal, point));

				nodeToSample = GetNodeToSample(object);

				for (int k=0; k < mSamplesPerPass; k++) {
					bool reverseSample = false;
					

					if (nodeToSample) {
						AxisAlignedBox3 box = mKdTree->GetBox(nodeToSample);
						Vector3 pointToSample = box.GetRandomPoint();
						//						pointToSample.y = 0.9*box.Min().y + 0.1*box.Max().y;
						if (object->GetRandomVisibleSurfacePoint( point, normal, pointToSample, 3 )) {
							direction = pointToSample - point;
						} else {
							reverseSamples++;
							reverseSample = true;
							direction = point - pointToSample;
							point = pointToSample;
						}
					}
					else {
						direction = UniformRandomVector(normal);
					}
					
					// construct a ray
					SetupRay(ray, point, direction, Ray::LOCAL_RAY);
					
					sampleContributions = CastRay(reverseSample ? NULL : object, ray);
					
					//-- CORR matt: put block inside loop
					if (sampleContributions) {
						passContributingSamples ++;
						passSampleContributions += sampleContributions;
					}

					if ( i < pvsOut ) {
						Ray *nray = new Ray(ray);
						rays[i].push_back(nray);
					}
		
					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) {
								Ray *nray = new Ray(ray);
								rays[j].push_back(nray);
							}
						}
					}
					//-------------------
					if (ViewCell::sHierarchy == ViewCell::BSP) 
					{
						ProcessBspViewCells(ray,
											reverseSample ? NULL : object,
											faceIndex,
											passContributingSamples,
											passSampleContributions);

						//mVspKdTree->Construct(mSampleRays, mBoundingBox);
					}
					else if (ViewCell::sHierarchy == ViewCell::VSP)
					{
						ProcessVspViewCells(ray,
											reverseSample ? NULL : object,
											faceIndex,
											passContributingSamples,
											passSampleContributions);
					}
				}
			} else {
				// edge samples
				// get random visible mesh
				//				object->GetRandomVisibleMesh(Plane3(normal, point));
			}
	
			// CORR matt: must add all samples
			passSamples += mSamplesPerPass;
		}
	
		totalSamples += passSamples; 
		
		//    if (pass>10)
		//      HoleSamplingPass();
    
		mPass++;
        
		if (ViewCell::sHierarchy == ViewCell::KD)
		{
			pvsSize = 0;

			for (i=0; i < objects.size(); i++) {
				Intersectable *object = objects[i];
				pvsSize += object->mKdPvs.GetSize();
			}
		}
		else
			pvsSize += passSampleContributions;
		
		float avgRayContrib = (passContributingSamples > 0) ? 
			passSampleContributions/(float)passContributingSamples : 0;

		cout << "#Pass " << mPass << " : t = " << TimeDiff(startTime, GetTime())*1e-3 << "s" << endl;
		cout << "#TotalSamples=" << totalSamples/1000 
				 << "k   #SampleContributions=" << passSampleContributions << " (" 
				 << 100*passContributingSamples/(float)passSamples<<"%)" << " avgPVS="
				 << (float)pvsSize /(float)objects.size() << endl 
				 << "avg ray contrib=" << avgRayContrib << endl
				 << "reverse samples [%]" << reverseSamples/(float)passSamples*100.0f << endl;

		mStats <<
			"#Pass\n" <<mPass<<endl<<
			"#Time\n" << TimeDiff(startTime, GetTime())*1e-3 << endl<<
			"#TotalSamples\n" << totalSamples<< endl<<
			"#SampleContributions\n" << passSampleContributions << endl << 
			"#PContributingSamples\n"<<100*passContributingSamples/(float)passSamples<<endl <<
			"#AvgPVS\n"<< pvsSize/(float)objects.size() << endl <<
			"#AvgRayContrib\n" << avgRayContrib << endl;
	}
	
	if (ViewCell::sHierarchy == ViewCell::KD)	
		cout << "#totalKdPvsSize=" << mKdTree->CollectLeafPvs() << endl;
  
	//-- render simulation
	cout << "\nevaluating bsp view cells render time before merge ... ";
	GetRenderSimulator()->SimulateRendering();
	
	cout << " finished" << endl;

	cout << GetRenderSimulator()->mStat << endl;
	Debug << GetRenderSimulator()->mStat << endl;


	if (mBspTree)
	{
		//-- post processing of bsp view cells
        int vcSize = 0;
		int pvsSize = 0;

		BspViewCellsStatistics stat;
		
		Debug << "overall scene size: " << (int)objects.size() << endl;
		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 (1) // export scene geometry
				{
					Material m;//= RandomMaterial();
					m.mDiffuseColor = RgbColor(0, 1, 0);
					exporter->SetForcedMaterial(m);
					exporter->SetWireframe();
	
					for (int j = 0; j < objects.size(); ++ j)
						exporter->ExportIntersectable(objects[j]);
				}
					
				delete exporter;
			}
			cout << "finished" << endl;
		}

		cout << "starting post processing using " << mPostProcessSamples << " samples ... ";
		
		long startTime = GetTime();
		int merged = PostprocessViewCells(mSampleRays);
		
		cout << "finished" << endl;
		cout << "merged " << merged << " view cells in "
			 << TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl;

		//-- recount pvs
		mBspTree->EvaluateViewCellsStats(stat);
		
		Debug << "after post processing:\n" << stat << endl;

		//-- render simulation
		cout << "\nevaluating render time after merge ... ";
			
		GetRenderSimulator()->SimulateRendering();
		cout << " finished" << endl;

		cout << GetRenderSimulator()->mStat << endl;
		Debug << GetRenderSimulator()->mStat << endl;

		if (1) // export view cells
		{
			cout << "exporting view cells after merge ... ";
			Exporter *exporter = Exporter::GetExporter("merged_view_cells.x3d");
			if (exporter)
			{
				exporter->ExportBspViewCellPartition(*mBspTree, stat.maxPvs);
				//exporter->ExportBspViewCellPartition(*mBspTree, 0);
				delete exporter;
			}

			cout << "finished" << endl;
		}

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

		// export the PVS of sample view cells
		if (1)
			ExportBspPvs(objects);
	}
	
  //  HoleSamplingPass();
	if (0) {
		Exporter *exporter = Exporter::GetExporter("ray-density.x3d"); 
		exporter->SetExportRayDensity(true);
		exporter->ExportKdTree(*mKdTree);

		if (mBspTree && (ViewCell::sHierarchy == ViewCell::VSP))
			exporter->ExportVspKdTree(*mVspKdTree);

		delete exporter;
	}
  
	bool exportRays = false;
	if (exportRays) {
		Exporter *exporter = NULL;
		exporter = Exporter::GetExporter("sample-rays.x3d");
		exporter->SetWireframe();
		exporter->ExportKdTree(*mKdTree);
		exporter->ExportBspTree(*mBspTree);

		for (i=0; i < pvsOut; i++) 
			exporter->ExportRays(rays[i], 1000, RgbColor(1, 0, 0));
		exporter->SetFilled();
		
		delete exporter;
	}

	//-- several visualizations and statistics
	if (1) {

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


void SamplingPreprocessor::ProcessVspViewCells(const Ray &ray,
                                               Intersectable *object,
											   const int faceIndex,
											   int &contributingSamples,
											   int &sampleContributions)
{
	// save rays for bsp tree construction
	if (!mVspKdTree)
	{
		if ((int)mVspSampleRays.size() < mVspConstructionSamples)
		{
			MeshInstance *mi = dynamic_cast<MeshInstance *>(object);
			
			VssRay *sRay = new VssRay(ray);
			mVspSampleRays.push_back(sRay);
		
			// also add origin to sample
			sRay->mOriginObject = object;
		}
		else
		{
			// construct VSP tree using the collected samples
			cout << "building VSP tree from " << (int)mVspSampleRays.size() << " samples " << endl;
			mVspKdTree->Construct(mVspSampleRays);
		
			// add contributions of saved samples to PVS
			//contributingSamples += mBspTree->GetStat().contributingSamples;
			//sampleContributions += mBspTree->GetStat().sampleContributions;

			Debug << mVspKdTree->GetStatistics();

			// throw away samples because BSP leaves not stored in order 
			// Need ordered rays for post processing => collect new rays
			//CLEAR_CONTAINER(mVspSampleRays);
		}
	}
	// save rays for post processing
	/*else if (((int)mVspSampleRays.size() < mPostProcessSamples) ||
			 ((int)mVspSampleRays.size() < mVisualizationSamples))
	{
		mVspSampleRays.push_back(new Ray(ray));
	}*/
}

void SamplingPreprocessor::ProcessBspViewCells(const Ray &ray,
                                               Intersectable *object,
											   const int faceIndex,
											   int &contributingSamples,
											   int &sampleContributions)
{
	// save rays for bsp tree construction
	if (!mBspTree)
	{
		if ((BspTree::sConstructionMethod == BspTree::FROM_RAYS) &&
			((int)mSampleRays.size() < mBspConstructionSamples))
		{
			MeshInstance *mi = dynamic_cast<MeshInstance *>(object);
			
			Ray *sRay = new Ray(ray);
			mSampleRays.push_back(sRay);
		
			// also add origin to sample
			sRay->sourceObject = Ray::Intersection(0.0, object, faceIndex);
		}
		else
		{
			// construct BSP tree using the collected samples
			cout << "building bsp tree from " << (int)mSampleRays.size() << " samples " << endl;
			BuildBspTree();
		
			// add contributions of saved samples to PVS
			contributingSamples += mBspTree->GetStat().contributingSamples;
			sampleContributions += mBspTree->GetStat().sampleContributions;

			BspTreeStatistics(Debug);

			if (0) Export("vc_bsptree.x3d", false, false, true);

			// throw away samples because BSP leaves not stored in order 
			// Need ordered rays for post processing => collect new rays
			CLEAR_CONTAINER(mSampleRays);
		}
	}
	// save rays for post processing
	else if (((int)mSampleRays.size() < mPostProcessSamples) ||
			 ((int)mSampleRays.size() < mVisualizationSamples))
	{
		mSampleRays.push_back(new Ray(ray));
	}
}

// merge or subdivide view cells
int SamplingPreprocessor::PostprocessViewCells(const RayContainer &rays)
{
	int merged = 0;

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

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

	for (int i = 0; i < limit; ++ i)
	{  
		Ray *ray = mSampleRays[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 (mBspTree->ShouldMerge(leaf, previousLeaf))
			{			
				mBspTree->MergeViewCells(leaf, previousLeaf);

				++ merged;
			}
		
			previousLeaf = leaf;
		}
	}

	return merged;
}

void SamplingPreprocessor::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)
		{
			RayContainer outRays;
		
			for (int i = 0; i < mSampleRays.size(); ++ i)
			{
				// only rays piercing geometry
				if (!mSampleRays[i]->intersections.empty())
					outRays.push_back(mSampleRays[i]);
			}
			if (BspTree::sConstructionMethod == BspTree::FROM_RAYS)
			{
				// export rays 
				exporter->ExportRays(outRays, 1000, RgbColor(1, 1, 0));
			}
		}

		// export scene geometry
		if (1)
		{
			Material m;//= RandomMaterial();
			m.mDiffuseColor = RgbColor(0, 1, 0);
			exporter->SetForcedMaterial(m);
            exporter->SetWireframe();

			for (int j = 0; j < objects.size(); ++ j)
				exporter->ExportIntersectable(objects[j]);
		}

		delete exporter;
	}
}

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

void SamplingPreprocessor::ExportBspPvs(const ObjectContainer &objects)
{
	const int leafOut = 10;
	
	ViewCell::NewMail();

	//-- some rays for output
	const int raysOut = min((int)mSampleRays.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 = mSampleRays[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 = mSampleRays[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;
		}
	}
}