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

  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.leaves.clear();
  ray.meshes.clear();
  ray.viewCells.clear();

  //  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);
		
		mBspTree->CollectViewCells(mViewCells);
		break;
	case BspTree::FROM_RAYS:
		DeleteViewCells(); // we generate new view cells
		mBspTree->SetGenerateViewCells(true);
		mBspTree->Construct(mSampleRays);
		
		mBspTree->CollectViewCells(mViewCells);
		break;
	default:
		Debug << "Error: Method not available\n";
		break;
	}
	
	
	return true;
}

int
SamplingPreprocessor::AddNodeSamples(Intersectable *object,
																		 const Ray &ray
																		 )
{
  int contributingSamples = 0;
  int j;
  for (j=0; j < ray.leaves.size(); j++) {
    KdNode *node = GetNodeForPvs( ray.leaves[j] );
    contributingSamples += object->mKdPvs.AddSample(node);
  }
   
  if (mPass > 10)
    for (j=1; j < ((int)ray.leaves.size() - 1); j++) {
      ray.leaves[j]->AddPassingRay(ray, contributingSamples ? 1 : 0);
  }
  
  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.viewCells.size(); ++ j) 
	{ 	// if ray not in unbounded space
		if (ray.viewCells[j] != &mUnbounded)
			contributingSamples += ray.viewCells[j]->GetPvs().AddSample(obj);
	}
 
	// rays passing through this viewcell
	if (mPass > 1)
		for (j=1; j < ((int)ray.viewCells.size() - 1); ++ j) 
		{
			if (ray.viewCells[j] != &mUnbounded)
				ray.viewCells[j]->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,
															const bool reverseRay
															)
{
	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->GetId() > 2197) {
		object->Describe(cout)<<endl;
		cout<<ray<<endl;
	}

	if (mViewCellsType == BSP_VIEW_CELLS)
	{
		// cast ray to BSP tree to get intersection with view cells
		if (mBspTree)
		{
			mBspTree->CastRay(ray);
			
			if (!reverseRay)
				sampleContributions += AddObjectSamples(object, ray);
			
			if (!ray.intersections.empty()) // second intersection found
				{
					sampleContributions += 
						AddObjectSamples(ray.intersections[0].mObject, ray);
				}
		}
	}
	else
		{
			if (ray.leaves.size()) {
				if (!reverseRay)
					sampleContributions += AddNodeSamples(object, ray);
				
				if (ray.intersections.size()) {
					sampleContributions += AddNodeSamples(ray.intersections[0].mObject, ray);
				}
			} 
		} 	
	
	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, false);
		}
	}
	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];

  vector<Ray> vcRays[5];
  ViewCellContainer pvsViewCells;
  vector<Ray> viewCellRays; // used for BSP tree construction

  while (totalSamples < mTotalSamples) {
		int passContributingSamples = 0;
		int passSampleContributions = 0;
		int passSamples = 0;
		int index = 0;
		Real maxTime = 0;
		int maxTimeIdx = 0;
		int reverseSamples = 0;
		bool collectSamplesForBsp = 
			(mViewCellsType == BSP_VIEW_CELLS) &&
			(BspTree::sConstructionMethod == BspTree::FROM_RAYS) &&
			(totalSamples < mBspConstructionSamples);
			
		cout << "totalSamples: "  << totalSamples << endl;

		for (i = 0; i < objects.size(); i++) {
						
			KdNode *nodeToSample = NULL;
			Intersectable *object = objects[i];
		
			int pvsSize = 0;
			if (mViewCellsType == KD_VIEW_CELLS)
				pvsSize = object->mKdPvs.GetSize();
						
			
			if (0 && pvsSize && mPass == 1000 ) {
				VerifyVisibility(object);
			}
			
			int faceIndex = object->GetRandomSurfacePoint(point, normal);
			
			long samplesPerObjStart = GetTime();

			bool viewcellSample = true;
			int sampleContributions;
			bool debug = false; //(object->GetId() >= 2199);
			if (viewcellSample) {
				//mKdTree->GetRandomLeaf(Plane3(normal, point));

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

					nodeToSample = GetNodeToSample(object);

					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(object, ray, reverseSample);

					//-- 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 (mViewCellsType == BSP_VIEW_CELLS) 
					{
						// save rays for bsp tree construction
						if (collectSamplesForBsp)
						{
							// 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));
						}
						else
						{
							// construct BSP tree using the samples
							if (!mBspTree)
							{
								BuildBspTree();

								cout << "generated " << (int)mViewCells.size() << " view cells" << endl;

								passContributingSamples += mBspTree->GetStat().contributingSamples;
								passSampleContributions += mBspTree->GetStat().sampleContributions;

								BspTreeStatistics(Debug);	
								Export("vc_bsptree.x3d", false, false, true);
							}
								
							// some random view cells for output
							if (pvsViewCells.empty())
							{
								int vcPvsOut = Min((int)mViewCells.size(), 5);
							
								for (int j = 0; j < vcPvsOut; ++ j)
								{
									int idx = Random((int)mViewCells.size());
									Debug << "output view cell=" << idx << endl;
									pvsViewCells.push_back(mViewCells[Random((int)mViewCells.size())]);
								}
							}
							else
							{	
								// check whether we can add the current ray to the rays
								for (int k = 0; k < (int)ray.viewCells.size(); ++ k)
									for (int j = 0; j < (int)pvsViewCells.size(); ++ j) 
										if (pvsViewCells[j] == ray.viewCells[k]) 
											vcRays[j].push_back(ray);							
							}
						}
					}
		
				}
			} else {
				// edge samples
				// get random visible mesh
				//				object->GetRandomVisibleMesh(Plane3(normal, point));
			}
				
			// measure maximal time for samples per object
			Real t = TimeDiff(samplesPerObjStart, GetTime());

			if (t > maxTime)
			{
				maxTime = t;
				maxTimeIdx = i;
			}
	
			// CORR matt: must add all samples
			passSamples += mSamplesPerPass;
		}
	
		totalSamples += passSamples; 
		
		//    if (pass>10)
		//      HoleSamplingPass();
    
		mPass++;

		int pvsSize = 0;
        
		if (mViewCellsType == BSP_VIEW_CELLS) {
			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();
			}
		}

		Debug << "maximal time needed for pass: " << maxTime << " (object " << maxTimeIdx << ")" << endl;

		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 (mViewCellsType == KD_VIEW_CELLS)	
		cout << "#totalPvsSize=" << mKdTree->CollectLeafPvs() << endl;
  
  //  HoleSamplingPass();
  if (0) {
    Exporter *exporter = Exporter::GetExporter("ray-density.x3d");
    exporter->SetExportRayDensity(true);
    exporter->ExportKdTree(*mKdTree);

	if (mBspTree && (mViewCellsType == BSP_VIEW_CELLS))
		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) {
  if (mBspTree && (mViewCellsType == BSP_VIEW_CELLS))
  {
	  bool exportSplits = false;
	  environment->GetBoolValue("BspTree.exportSplits", exportSplits);

	  // export the bsp splits
	  if (exportSplits)
	  	  ExportSplits(objects);
	
	  Exporter *exporter = Exporter::GetExporter("viewCells.x3d");

	  if (exporter)
	  {
          //exporter->ExportLeavesGeometry(mBspTree, leaves);		

		  delete exporter;
	  }

	  for (int j = 0; j < pvsViewCells.size(); ++ j)
	  {
		  ViewCell *vc = pvsViewCells[j];

		  Intersectable::NewMail();
		  char s[64]; sprintf(s, "bsp-pvs%04d.x3d", j);

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

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

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

		  exporter->ExportViewCell(vc);

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

		  exporter->SetWireframe();

		  // export view cells
		  m.mDiffuseColor = RgbColor(1, 0, 1);
		  exporter->SetForcedMaterial(m);
		  exporter->ExportViewCells(mViewCells);
			
		  // export rays piercing this view cell
		  exporter->ExportRays(vcRays[j], 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())
				  {
					  //if (j == 2198)m.mDiffuseColor = RgbColor(1, 0, 1);
					  //else m.mDiffuseColor = RgbColor(1, 1, 0);
					  exporter->SetForcedMaterial(m);
					  exporter->ExportIntersectable(objects[j]);
					  objects[j]->Mail();
				  }
		  }
		  DEL_PTR(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;
    }
  }
  
  return true;
}


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

	if (exporter) 
	{	
		cout << "exporting splits ... ";

		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;

		cout << "finished" << endl;
	}
}