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

SamplingPreprocessor::SamplingPreprocessor(): mPass(0), mSampleRays(NULL)
{
  // 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("ViewCells.PostProcessing.samples", mPostProcessSamples);
  mKdPvsDepth = 100;
  mStats.open("stats.log");

}

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

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

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

				sampleContributions += AddNodeSamples(ray,
																							object,
																							terminator);
			}
		}
	
	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);

  vector<Ray> 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 )
						rays[i].push_back(ray);
		
					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);
							}
						}
					}
					//-------------------
					if (ViewCell::sHierarchy == ViewCell::BSP) 
					{
						ProcessBspViewCells(ray,
											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++;

		int pvsSize = 0;
        
		if (ViewCell::sHierarchy == ViewCell::BSP) {
			for (i=0; i < mViewCells.size(); i++) {
				ViewCell *vc = mViewCells[i];
				pvsSize += vc->GetPvs().GetSize();
			}
		} else 	{
			for (i=0; i < objects.size(); i++) {
				Intersectable *object = objects[i];
				pvsSize += object->mKdPvs.GetSize();
			}
		}

		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="
				 << 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 << "#totalPvsSize=" << mKdTree->CollectLeafPvs() << endl;
  
	if (mBspTree)
	{
		//-- render simulation
		cout << "\nevaluating render time before merge ... ";
		Real rt = SimulateRendering();
		
		cout << "avg render time: " << rt * 1e-3 << endl;
		Debug << "avg render time: " << rt * 1e-3 << endl;

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

		BspViewCellsStatistics stat;
		
		Debug << "overall scene size: " << objects.size() << endl;
		mBspTree->EvaluateViewCellsStats(stat);
		
		Debug << "original view cell partition:\n" << stat << endl;
		
		if (1) // export view cells
		{
			cout << "exporting view cells ... ";
			Exporter *exporter = Exporter::GetExporter("view_cells.x3d");
			if (exporter)
			{
				exporter->ExportBspViewCellPartition(*mBspTree, stat.maxPvs);
				//exporter->ExportBspViewCellPartition(*mBspTree, 0);
				delete exporter;
			}
			cout << "finished" << endl;
		}

		cout << "starting post processing using " << (int)mSampleRays.size() << " 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 ... ";
			
		rt = SimulateRendering();

		cout << "render time: " << rt * 1e-3 << endl;
		Debug << "render time: " << rt * 1e-3 << 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.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::BSP))
			exporter->ExportBspTree(*mBspTree);

		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::ProcessBspViewCells(Ray &ray,
											   Intersectable *object,
											   int faceIndex,
											   int &contributingSamples,
											   int &sampleContributions)
{
	// save rays for bsp tree construction
	if (!mBspTree)
	{
		if ((BspTree::sConstructionMethod == BspTree::FROM_RAYS) &&
			((int)mSampleRays.size() < mBspConstructionSamples))
		{
			// also add origin to sample in order to extract it as input polygons
			MeshInstance *mi = dynamic_cast<MeshInstance *>(object);
			ray.sourceObject = Ray::Intersection(0.0, mi, faceIndex);
							
			mSampleRays.push_back(new Ray(ray));
			Debug << "abba " << mSampleRays.size() << endl;
		}
		else
		{
			// construct BSP tree using the samples
			cout << "building bsp tree from " << 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)
	{
		Debug << "police " << mSampleRays.size() << endl;
		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;

	for (rit = rays.begin(); rit != rays.end(); ++ rit)
	{  
		// traverse leaves stored in the rays and compare and merge consecutive
		// leaves (i.e., the neighbors in the tree)
		if ((*rit)->bspIntersections.empty())
			continue;

		iit = (*rit)->bspIntersections.begin();

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

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

void SamplingPreprocessor::ExportBspPvs(const ObjectContainer &objects)
{
	//-- some random view cells and rays for output
	const int leafOut = 10;

	vector<Ray> vcRays[leafOut];
	vector<BspLeaf *> bspLeaves;
			
	for (int i = 0; i < leafOut; ++ i)
		bspLeaves.push_back(mBspTree->GetRandomLeaf());
	
	const int raysOut = min((int)mSampleRays.size(), 20000);

	ViewCell::NewMail();

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

		ViewCell *vc = 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();

		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(bspLeaves[i]->GetViewCell(), cell);
			exporter->ExportPolygons(cell);
			CLEAR_CONTAINER(cell);
		}

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

		// export view cells
		if (0)
		{
			m.mDiffuseColor = RgbColor(1, 0, 1);
			exporter->SetForcedMaterial(m);
			exporter->ExportViewCells(mViewCells);
		}

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

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

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


Real SamplingPreprocessor::RenderPvs(ViewCell &viewCell, 
									 const float objRenderTime) const
{
	return viewCell.GetPvs().GetSize() * objRenderTime;
}

Real SamplingPreprocessor::SimulateRendering()
{
	Real renderTime = 0;

	// render time for 1 object of PVS
	const float objRt = 1.0f; 
	 // const overhead for crossing a view cell border
	const float vcOverhead = 0.01f;
	
	// total area of view cells
	float totalArea = 0;//= mKdTree->GetBox().SurfaceArea();

	ViewCellContainer viewCells;

	mBspTree->CollectViewCells(viewCells);

	ViewCellContainer::const_iterator it, it_end = viewCells.end();
	PolygonContainer::const_iterator pit;

	for (it = viewCells.begin(); it != it_end; ++ it)
	{
		// surface area substitute for probability
		PolygonContainer cell;
		float area = 0;

		mBspTree->ConstructGeometry(dynamic_cast<BspViewCell *>(*it), cell);

		for (pit = cell.begin(); pit != cell.end(); ++ pit)
			area += (*pit)->GetArea();
		
		renderTime += area * RenderPvs(*(*it), objRt);
		totalArea += area;
	}

	renderTime /= totalArea;

	Debug << "render time without overhead: " << renderTime * 1e-3 << endl;
	
	renderTime += (float)viewCells.size() * vcOverhead;

	return renderTime;
}