#include "SceneGraph.h"
#include "Exporter.h"
#include "UnigraphicsParser.h"
#include "X3dParser.h"
#include "Preprocessor.h"
#include "ViewCell.h"
#include "Environment.h"
#include "ViewCellsManager.h"
#include "ViewCellBsp.h"
#include "VspBspTree.h"
#include "RenderSimulator.h"
#include "GlRenderer.h"
#include "PlyParser.h"
#include "SamplingStrategy.h"
#include "VspTree.h"
#include "OspTree.h"
#include "ObjParser.h"
#include "BvHierarchy.h"
#include "HierarchyManager.h"
#include "VssRay.h"
#include "IntelRayCaster.h"
#include "InternalRayCaster.h"
#include "GlobalLinesRenderer.h"


#define DEBUG_RAYCAST 0
#define SHOW_RAYCAST_TIMING 1


namespace GtpVisibilityPreprocessor {

  const static bool ADDITIONAL_GEOMETRY_HACK = false;

  Preprocessor *preprocessor = NULL;
  
// HACK: Artificially modify scene to watch rendercost changes
static void AddGeometry(SceneGraph *scene)
{
	scene->GetRoot()->UpdateBox();

	AxisAlignedBox3 sceneBox = scene->GetBox();

	int n = 200;

	if (0)
	{
		// form grid of boxes
		for (int i = 0; i < n; ++ i)
		{
			for (int j = 0; j < n; ++ j)
			{
				const Vector3 scale2((float)j * 0.8f / n + 0.1f,  0.05f, (float)i * 0.8f  / (float)n + 0.1f);

				const Vector3 pt2 = sceneBox.Min() + scale2 * (sceneBox.Max() - sceneBox.Min());

				const Vector3 boxSize = sceneBox.Size() * Vector3(0.0025f, 0.01f, 0.0025f);
				AxisAlignedBox3 box(pt2, pt2 + boxSize);
				Mesh *mesh = CreateMeshFromBox(box);

				mesh->Preprocess();

				MeshInstance *mi = new MeshInstance(mesh);
				scene->GetRoot()->mGeometry.push_back(mi);
			}
		}

		for (int i = 0; i < n; ++ i)
		{
			for (int j = 0; j < n; ++ j)
			{
				const Vector3 scale2(0.15f, (float)j * 0.8f / n + 0.1f, (float)i * 0.8f  / (float)n + 0.1f);

				Vector3 pt2 = sceneBox.Min() + scale2 * (sceneBox.Max() - sceneBox.Min());

				Vector3 boxSize = sceneBox.Size() * Vector3(0.0025f, 0.01f, 0.0025f);
				AxisAlignedBox3 box(pt2, pt2 + boxSize);
				Mesh *mesh = CreateMeshFromBox(box);

				mesh->Preprocess();

				MeshInstance *mi = new MeshInstance(mesh);
				scene->GetRoot()->mGeometry.push_back(mi);
			}
		}

		for (int i = 0; i < n; ++ i)
		{
			const Vector3 scale2(2, 0.2f, (float)i * 0.8f  / (float)n + 0.1f);

			Vector3 pt2 = sceneBox.Min() + scale2 * (sceneBox.Max() - sceneBox.Min());
			Vector3 boxSize = sceneBox.Size() * Vector3(0.005f, 0.02f, 0.005f);

			AxisAlignedBox3 box(pt2 + 0.1f, pt2 + boxSize);
			Mesh *mesh = CreateMeshFromBox(box);

			mesh->Preprocess();

			MeshInstance *mi = new MeshInstance(mesh);
			scene->GetRoot()->mGeometry.push_back(mi);
		}

		scene->GetRoot()->UpdateBox();
	}

	if (1)
	{
		// plane separating view space regions
		const Vector3 scale(1.0f, 0.0, 0);

		Vector3 pt = sceneBox.Min() + scale * (sceneBox.Max() - sceneBox.Min());

		Plane3 cuttingPlane(Vector3(1, 0, 0), pt);
		Mesh *planeMesh = new Mesh();

		Polygon3 *poly = sceneBox.CrossSection(cuttingPlane);
		IncludePolyInMesh(*poly, *planeMesh);

		planeMesh->Preprocess();

		MeshInstance *planeMi = new MeshInstance(planeMesh);
		scene->GetRoot()->mGeometry.push_back(planeMi);
	}	
}


Preprocessor::Preprocessor():
mKdTree(NULL),
mBspTree(NULL),
mVspBspTree(NULL),
mViewCellsManager(NULL),
mRenderSimulator(NULL),
mPass(0),
mSceneGraph(NULL),
mRayCaster(NULL),
mStopComputation(false),
mThread(NULL),
mGlobalLinesRenderer(NULL)
{
	Environment::GetSingleton()->GetBoolValue("Preprocessor.useGlRenderer", mUseGlRenderer);
  
	// renderer will be constructed when the scene graph and viewcell manager will be known
	renderer = NULL;
	
	Environment::GetSingleton()->GetBoolValue("Preprocessor.useGlDebugger", mUseGlDebugger);
	Environment::GetSingleton()->GetBoolValue("Preprocessor.loadMeshes", mLoadMeshes);
	Environment::GetSingleton()->GetBoolValue("Preprocessor.quitOnFinish", mQuitOnFinish);
	Environment::GetSingleton()->GetBoolValue("Preprocessor.computeVisibility", mComputeVisibility);
	Environment::GetSingleton()->GetBoolValue("Preprocessor.detectEmptyViewSpace", mDetectEmptyViewSpace);
	Environment::GetSingleton()->GetBoolValue("Preprocessor.exportVisibility", mExportVisibility );
	
	char buffer[256];
	Environment::GetSingleton()->GetStringValue("Preprocessor.visibilityFile",  buffer);
	mVisibilityFileName = buffer;
	
	Environment::GetSingleton()->GetStringValue("Preprocessor.stats",  buffer);
	mStats.open(buffer);
		
	Environment::GetSingleton()->GetBoolValue("Preprocessor.applyVisibilityFilter", mApplyVisibilityFilter);
	Environment::GetSingleton()->GetBoolValue("Preprocessor.applyVisibilitySpatialFilter",
											  mApplyVisibilitySpatialFilter );
	Environment::GetSingleton()->GetFloatValue("Preprocessor.visibilityFilterWidth", mVisibilityFilterWidth);

	Environment::GetSingleton()->GetBoolValue("Preprocessor.exportObj", mExportObj);
	
	Environment::GetSingleton()->GetBoolValue("Preprocessor.useViewSpaceBox", mUseViewSpaceBox);

	Environment::GetSingleton()->GetBoolValue("Preprocessor.Export.rays", mExportRays);
	Environment::GetSingleton()->GetBoolValue("Preprocessor.Export.animation", mExportAnimation);
	Environment::GetSingleton()->GetIntValue("Preprocessor.Export.numRays", mExportNumRays);

	Environment::GetSingleton()->GetIntValue("Preprocessor.samplesPerPass", mSamplesPerPass);
	Environment::GetSingleton()->GetIntValue("Preprocessor.totalSamples", mTotalSamples);
	Environment::GetSingleton()->GetIntValue("Preprocessor.totalTime", mTotalTime);
	Environment::GetSingleton()->GetIntValue("Preprocessor.samplesPerEvaluation",
											 mSamplesPerEvaluation);

	Debug << "******* Preprocessor Options **********" << endl;
	Debug << "detect empty view space=" << mDetectEmptyViewSpace << endl;
	Debug << "load meshes: " << mLoadMeshes << endl;
	Debug << "load meshes: " << mLoadMeshes << endl;
	Debug << "export obj: " << mExportObj << endl;
	Debug << "use view space box: " << mUseViewSpaceBox << endl;

	cout << "samples per pass " << mSamplesPerPass << endl;
}


Preprocessor::~Preprocessor()
{
	cout << "cleaning up" << endl;

	cout << "Deleting view cells manager ... \n";
	DEL_PTR(mViewCellsManager);
	cout << "done.\n";

	
	cout << "Deleting bsp tree ... \n";
	DEL_PTR(mBspTree);
	cout << "done.\n";

	cout << "Deleting kd tree ...\n";
	DEL_PTR(mKdTree);
	cout << "done.\n";

	cout << "Deleting vspbsp tree ... \n";
	DEL_PTR(mVspBspTree);
	cout << "done.\n";

	cout << "Deleting scene graph ... \n";
	DEL_PTR(mSceneGraph);
	cout << "done.\n";

	cout << "deleting render simulator ... \n";
	DEL_PTR(mRenderSimulator);
	mRenderSimulator = NULL;
	cout << "deleting renderer ... \n";
	DEL_PTR(renderer);
	renderer = NULL;
	cout << "deleting ray caster ... \n";
	DEL_PTR(mRayCaster);

#ifdef USE_CG
	cout << "deleting global lines renderer ... \n";
	DEL_PTR(mGlobalLinesRenderer);
#endif
	cout << "finished" << endl;
}


GlRendererBuffer *Preprocessor::GetRenderer() 
{ 
	return renderer;
}


static int SplitFilenames(const string str, vector<string> &filenames)
{
	int pos = 0;

	while(1) {
		int npos = (int)str.find(';', pos);
		
		if (npos < 0 || npos - pos < 1)
			break;
		filenames.push_back(string(str, pos, npos - pos));
		pos = npos + 1;
	}
	
	filenames.push_back(string(str, pos, str.size() - pos));
	return (int)filenames.size();
}


void Preprocessor::SetThread(PreprocessorThread *t)
{
	mThread = t;
}


PreprocessorThread *Preprocessor::GetThread() const 
{
	return mThread;
}


bool Preprocessor::LoadBinaryObj(const string filename,
								 SceneGraphNode *root,
								 vector<FaceParentInfo> *parents)
{
	//ifstream samplesIn(filename, ios::binary);
	igzstream samplesIn(filename.c_str());
	
	if (!samplesIn.is_open())
		return false;

	cout << "binary obj dump available, loading " << filename.c_str() << endl;
	
	// table for vertices
	VertexContainer vertices; 
	
	if (parents)
		cout << "using face parents" << endl;
	else
		cout << "not using face parents" << endl;

	// read in triangle size
	int numTriangles;

	samplesIn.read(reinterpret_cast<char *>(&numTriangles), sizeof(int));
	root->mGeometry.reserve(numTriangles);
	cout << "loading " << numTriangles << " triangles (" 
		 << numTriangles * (sizeof(TriangleIntersectable) + sizeof(TriangleIntersectable *)) / (1024 * 1024) << " MB)" << endl;

	int i = 0;
	while (1)
	{
		Triangle3 tri;
		
		samplesIn.read(reinterpret_cast<char *>(tri.mVertices + 0), sizeof(Vector3));
		samplesIn.read(reinterpret_cast<char *>(tri.mVertices + 1), sizeof(Vector3));
		samplesIn.read(reinterpret_cast<char *>(tri.mVertices + 2), sizeof(Vector3));

		// end of file reached
		if (samplesIn.eof())
			break;

		TriangleIntersectable *obj = new TriangleIntersectable(tri);
		root->mGeometry.push_back(obj);
		
		i ++;
	
		if (i % 500000 == 499999)
			 cout<<"\r"<<i<<"/"<<numTriangles<<"\r";
	}
	
	if (i != numTriangles)
	{
		cout << "warning: triangle size does not match with loaded triangle size" << endl;
		return false;
	}

	cout << "loaded " << numTriangles << " triangles" << endl;

	return true;
}


bool Preprocessor::ExportBinaryObj(const string filename, SceneGraphNode *root)
{
	ogzstream samplesOut(filename.c_str());

	if (!samplesOut.is_open())
		return false;

	int numTriangles = (int)root->mGeometry.size();

	samplesOut.write(reinterpret_cast<char *>(&numTriangles), sizeof(int));

	ObjectContainer::const_iterator oit, oit_end = root->mGeometry.end();

	for (oit = root->mGeometry.begin(); oit != oit_end; ++ oit)
	{
		Intersectable *obj = *oit;

		if (obj->Type() == Intersectable::TRIANGLE_INTERSECTABLE)
		{
			Triangle3 tri = static_cast<TriangleIntersectable *>(obj)->GetItem();

			samplesOut.write(reinterpret_cast<char *>(tri.mVertices + 0), sizeof(Vector3));
			samplesOut.write(reinterpret_cast<char *>(tri.mVertices + 1), sizeof(Vector3));
			samplesOut.write(reinterpret_cast<char *>(tri.mVertices + 2), sizeof(Vector3));
		}
		else
		{
			cout << "not implemented intersectable type " << obj->Type() << endl;
		}
	}

	cout << "exported " << numTriangles << " triangles" << endl;

	return true;
}


bool Preprocessor::ExportObj(const string filename, const ObjectContainer &objects)
{
	ofstream samplesOut(filename.c_str());

	if (!samplesOut.is_open())
		return false;

	ObjectContainer::const_iterator oit, oit_end = objects.end();

	//AxisAlignedBox3 bbox = mSceneGraph->GetBox(); bbox.Enlarge(30.0);
	for (oit = objects.begin(); oit != oit_end; ++ oit)
	{
		Intersectable *obj = *oit;

		if (obj->Type() == Intersectable::TRIANGLE_INTERSECTABLE)
		{
			Triangle3 tri = static_cast<TriangleIntersectable *>(obj)->GetItem();
			//if (!(bbox.IsInside(tri.mVertices[0]) && bbox.IsInside(tri.mVertices[1]) && bbox.IsInside(tri.mVertices[2])))continue;
			
			samplesOut << "v " << tri.mVertices[0].x << " " << tri.mVertices[0].y << " " << tri.mVertices[0].z << endl;
			samplesOut << "v " << tri.mVertices[1].x << " " << tri.mVertices[1].y << " " << tri.mVertices[1].z << endl;
			samplesOut << "v " << tri.mVertices[2].x << " " << tri.mVertices[2].y << " " << tri.mVertices[2].z << endl;
			//}
		}
		else
		{
			cout << "not implemented intersectable type " << obj->Type() << endl;
		}
	}

	// write faces
	int i = 1;
	for (oit = objects.begin(); oit != oit_end; ++ oit)
	{
		Intersectable *obj = *oit;
		if (obj->Type() == Intersectable::TRIANGLE_INTERSECTABLE)
		{
			//Triangle3 tri = static_cast<TriangleIntersectable *>(obj)->GetItem();
			//if (!(bbox.IsInside(tri.mVertices[0]) && bbox.IsInside(tri.mVertices[1]) && bbox.IsInside(tri.mVertices[2]))) continue;
			
			Triangle3 tri = static_cast<TriangleIntersectable *>(obj)->GetItem();
			samplesOut << "f " << i << " " << i + 1 << " " << i + 2 << endl;
			i += 3;
		}
		else
		{
			cout << "not implemented intersectable type " << obj->Type() << endl;
		}
	}

	return true;

}

static string ReplaceSuffix(string filename, string a, string b)
{
	string result = filename;

	int pos = (int)filename.rfind(a, (int)filename.size() - 1);
	if (pos == filename.size() - a.size()) {
		result.replace(pos, a.size(), b);
	}
	return result;
}


Intersectable *Preprocessor::GetParentObject(const int index) const
{
	if (index < 0)
	{
		//cerr << "Warning: triangle index smaller zero! " << index << endl;
		return NULL;
	}
	
	if (!mFaceParents.empty())
	{
		if (index >= (int)mFaceParents.size())
		{
			cerr << "Warning: triangle index out of range! " << index << endl;
			return NULL;
		}
		else
		{
			return mFaceParents[index].mObject;
		}
	}
	else
	{
		  if (index >= (int)mObjects.size()) 
		  {
			  cerr<<"Warning: triangle  index out of range! " << index << endl;
			  return NULL;
		  }
		  else
		  {
			  return mObjects[index];
		  }
	}
}


Vector3 Preprocessor::GetParentNormal(const int index) const
{
	if (!mFaceParents.empty())
	{
		return mFaceParents[index].mObject->GetNormal(mFaceParents[index].mFaceIndex);
	}	
	else
	{
		return mObjects[index]->GetNormal(0);
	}
}


bool
Preprocessor::LoadScene(const string filename)
{
    // use leaf nodes of the original spatial hierarchy as occludees
	mSceneGraph = new SceneGraph;
  
	Parser *parser;
	vector<string> filenames;
	const int files = SplitFilenames(filename, filenames);
	cout << "number of input files: " << files << endl;
	bool result = false;
	bool isObj = false;

	// root for different files
	mSceneGraph->SetRoot(new SceneGraphNode());

	// intel ray caster can only trace triangles
	int rayCastMethod;
	Environment::GetSingleton()->GetIntValue("Preprocessor.rayCastMethod", rayCastMethod);
	vector<FaceParentInfo> *fi = 
	  ((rayCastMethod == RayCaster::INTEL_RAYCASTER) && mLoadMeshes) ?
	  &mFaceParents : NULL;
	
	if (files == 1) 
	  {
		if (strstr(filename.c_str(), ".x3d"))
		  {
			parser = new X3dParser;
			
			result = parser->ParseFile(filename, 
									   mSceneGraph->GetRoot(),
									   mLoadMeshes,
									   fi);
			delete parser;
		}
		else if (strstr(filename.c_str(), ".ply") || strstr(filename.c_str(), ".plb"))
		{
			parser = new PlyParser;

			result = parser->ParseFile(filename, 
									   mSceneGraph->GetRoot(),
									   mLoadMeshes,
									   fi);
			delete parser;
		}
		else if (strstr(filename.c_str(), ".obj"))
		{
			isObj = true;

			// hack: load binary dump
			const string bnFile = ReplaceSuffix(filename, ".obj", ".bn");
			
			if (!mLoadMeshes)
			{
				result = LoadBinaryObj(bnFile, mSceneGraph->GetRoot(), fi);
			}

			// parse obj
            if (!result)
			{
				cout << "no binary dump available or loading full meshes, parsing file" << endl;
				parser = new ObjParser;
		
				result = parser->ParseFile(filename, 
								   mSceneGraph->GetRoot(),
								   mLoadMeshes,
								   fi);
						
				cout << "loaded " << (int)mSceneGraph->GetRoot()->mGeometry.size() << " entities" << endl;
				// only works for triangles
				if (result && !mLoadMeshes)
				{
					cout << "exporting binary obj to " << bnFile << "... " << endl;
					ExportBinaryObj(bnFile, mSceneGraph->GetRoot());
					cout << "finished" << endl;
				}

				delete parser;
			}
			else if (0)
			{
				ExportBinaryObj("../data/test.bn", mSceneGraph->GetRoot());
			}
		}
		else 
		{
			parser = new UnigraphicsParser;
			result = parser->ParseFile(filename, 
									   mSceneGraph->GetRoot(),
									   mLoadMeshes,								  
									   fi);
			delete parser;
		}
		
		cout << filename << endl;
	} 
	else 
	{
		vector<string>::const_iterator fit, fit_end = filenames.end();
		
		for (fit = filenames.begin(); fit != fit_end; ++ fit) 
		{
			const string filename = *fit;

			cout << "parsing file " << filename.c_str() << endl;
			if (strstr(filename.c_str(), ".x3d"))
				parser = new X3dParser;
			else 
				parser = new UnigraphicsParser;

			SceneGraphNode *node = new SceneGraphNode();
			const bool success = 
				parser->ParseFile(filename, node, mLoadMeshes, fi);

			if (success) 
			{ 
				mSceneGraph->GetRoot()->mChildren.push_back(node);
				result = true; // at least one file parsed
			}

			// temporare hack
			//if (!strstr(filename.c_str(), "plane")) mSceneGraph->GetRoot()->UpdateBox();

			delete parser;
		}
	}
	
	if (result) 
	{ 
	  // HACK 
		if (ADDITIONAL_GEOMETRY_HACK)
			AddGeometry(mSceneGraph);

		mSceneGraph->AssignObjectIds();
 
		int intersectables, faces;
		mSceneGraph->GetStatistics(intersectables, faces);
 
		cout<<filename<<" parsed successfully."<<endl;
		cout<<"#NUM_OBJECTS (Total numner of objects)\n"<<intersectables<<endl;
		cout<<"#NUM_FACES (Total numner of faces)\n"<<faces<<endl;
		
		mObjects.reserve(intersectables);
		mSceneGraph->CollectObjects(&mObjects);
		
		// temp hack
		//ExportObj("cropped_vienna.obj", mObjects);
		mSceneGraph->GetRoot()->UpdateBox();
				
		cout << "finished loading" << endl;
	}

	return result;
}

bool
Preprocessor::ExportPreprocessedData(const string filename)
{
	mViewCellsManager->ExportViewCells(filename, true, mObjects);
	return true;
}


bool
Preprocessor::PostProcessVisibility()
{
  
  if (mApplyVisibilityFilter || mApplyVisibilitySpatialFilter) {
	cout<<"Applying visibility filter ...";
	cout<<"filter width = " << mVisibilityFilterWidth << endl;
	
	if (!mViewCellsManager)
	  return false;
	
	mViewCellsManager->ApplyFilter(mKdTree,
								   mApplyVisibilityFilter ? mVisibilityFilterWidth : -1.0f,
								   mApplyVisibilitySpatialFilter ? mVisibilityFilterWidth : -1.0f);
	cout << "done." << endl;
  }
  
  // export the preprocessed information to a file
  if (1 && mExportVisibility)
  {
	  ExportPreprocessedData(mVisibilityFileName);
  }

  return true;
}


bool
Preprocessor::BuildKdTree()
{
  mKdTree = new KdTree;

  // add mesh instances of the scene graph to the root of the tree
  KdLeaf *root = (KdLeaf *)mKdTree->GetRoot();
 	
  mSceneGraph->CollectObjects(&root->mObjects);
  
  const long startTime = GetTime();
  cout << "building kd tree ... " << endl;

  mKdTree->Construct();

  cout << "finished kd tree construction in " << TimeDiff(startTime, GetTime()) * 1e-3 
	   << " secs " << endl;

  return true;
}


void
Preprocessor::KdTreeStatistics(ostream &s)
{
  s<<mKdTree->GetStatistics();
}

void
Preprocessor::BspTreeStatistics(ostream &s)
{
	s << mBspTree->GetStatistics();
}

bool
Preprocessor::Export( const string filename,
					  const bool scene,
					  const bool kdtree
					  )
{
  Exporter *exporter = Exporter::GetExporter(filename);
	
  if (exporter) {
    if (2 && scene)
      exporter->ExportScene(mSceneGraph->GetRoot());

    if (1 && kdtree) {
      exporter->SetWireframe();
      exporter->ExportKdTree(*mKdTree);
    }

    delete exporter;
    return true;
  }

  return false;
}


bool Preprocessor::PrepareViewCells()
{
	///////
	//-- parse view cells construction method

	Environment::GetSingleton()->GetBoolValue("ViewCells.loadFromFile", mLoadViewCells);
	char buf[100];

	if (mLoadViewCells)
	{	
		Environment::GetSingleton()->GetStringValue("ViewCells.filename", buf);
		cout << "loading view cells from " << buf << endl<<flush;

		mViewCellsManager = ViewCellsManager::LoadViewCells(buf, &mObjects, true, NULL);

		cout << "view cells loaded." << endl<<flush;

		if (!mViewCellsManager)
		{
			return false;
		}
	}
	else
	{
		// parse type of view cell container
		Environment::GetSingleton()->GetStringValue("ViewCells.type", buf);		
		mViewCellsManager = CreateViewCellsManager(buf);

		// default view space is the extent of the scene
		AxisAlignedBox3 viewSpaceBox;

		if (mUseViewSpaceBox)
		{
			viewSpaceBox = mSceneGraph->GetBox();

			// use a small box outside of the scene
			viewSpaceBox.Scale(Vector3(0.15f, 0.3f, 0.5f));
			//viewSpaceBox.Translate(Vector3(Magnitude(mSceneGraph->GetBox().Size()) * 0.5f, 0, 0));
			viewSpaceBox.Translate(Vector3(Magnitude(mSceneGraph->GetBox().Size()) * 0.3f, 0, 0));
			mViewCellsManager->SetViewSpaceBox(viewSpaceBox);
		}
		else
		{
			viewSpaceBox = mSceneGraph->GetBox();
			mViewCellsManager->SetViewSpaceBox(viewSpaceBox);
		}

		bool loadVcGeometry;
		Environment::GetSingleton()->GetBoolValue("ViewCells.loadGeometry", loadVcGeometry);

		bool extrudeBaseTriangles;
		Environment::GetSingleton()->GetBoolValue("ViewCells.useBaseTrianglesAsGeometry", extrudeBaseTriangles);

		char vcGeomFilename[100];
		Environment::GetSingleton()->GetStringValue("ViewCells.geometryFilename", vcGeomFilename);

		// create view cells from specified geometry
		if (loadVcGeometry)
		{
			if (mViewCellsManager->GetType() == ViewCellsManager::BSP)
			{
				if (!mViewCellsManager->LoadViewCellsGeometry(vcGeomFilename, extrudeBaseTriangles))
				{
					cerr << "loading view cells geometry failed" << endl;
				}
			}
			else
			{
				cerr << "loading view cells geometry is not implemented for this manager" << endl;
			}
		}
	}

	////////
	//-- evaluation of render cost heuristics

	float objRenderCost = 0, vcOverhead = 0, moveSpeed = 0;

	Environment::GetSingleton()->GetFloatValue("Simulation.objRenderCost",objRenderCost);
	Environment::GetSingleton()->GetFloatValue("Simulation.vcOverhead", vcOverhead);
	Environment::GetSingleton()->GetFloatValue("Simulation.moveSpeed", moveSpeed);

	mRenderSimulator = 
		new RenderSimulator(mViewCellsManager, objRenderCost, vcOverhead, moveSpeed);

	mViewCellsManager->SetRenderer(mRenderSimulator);
	
	mViewCellsManager->SetPreprocessor(this);

	return true;
}

  
bool Preprocessor::ConstructViewCells()
{
	// construct view cells using it's own set of samples
	mViewCellsManager->Construct(this);

	// visualizations and statistics
	Debug << "finished view cells:" << endl;
	mViewCellsManager->PrintStatistics(Debug);

	return true;
}


ViewCellsManager *Preprocessor::CreateViewCellsManager(const char *name)
{
	ViewCellsTree *vcTree = new ViewCellsTree;

	if (strcmp(name, "kdTree") == 0)
	{
		mViewCellsManager = new KdViewCellsManager(vcTree, mKdTree);
	}
	else if (strcmp(name, "bspTree") == 0)
	{
		Debug << "view cell type: Bsp" << endl;

		mBspTree = new BspTree();
		mViewCellsManager = new BspViewCellsManager(vcTree, mBspTree);
	}
	else if (strcmp(name, "vspBspTree") == 0)
	{
		Debug << "view cell type: VspBsp" << endl;

		mVspBspTree = new VspBspTree();
		mViewCellsManager = new VspBspViewCellsManager(vcTree, mVspBspTree);
	}
	else if (strcmp(name, "vspOspTree") == 0)
	{
		Debug << "view cell type: VspOsp" << endl;
		char buf[100];		
		Environment::GetSingleton()->GetStringValue("Hierarchy.type", buf);	

		mViewCellsManager = new VspOspViewCellsManager(vcTree, buf);
	}
	else if (strcmp(name, "sceneDependent") == 0) //TODO
	{
		Debug << "view cell type: Bsp" << endl;
		
		mBspTree = new BspTree();
		mViewCellsManager = new BspViewCellsManager(vcTree, mBspTree);
	}
	else
	{
		cerr << "Wrong view cells type " << name << "!!!" << endl;
		exit(1);
	}

	return mViewCellsManager;
}


// use ascii format to store rays
#define USE_ASCII 0


static inline bool ilt(Intersectable *obj1, Intersectable *obj2)
{
	return obj1->mId < obj2->mId;
}


bool Preprocessor::LoadKdTree(const string filename)
{
	mKdTree = new KdTree();

	return mKdTree->LoadBinTree(filename.c_str(), mObjects);
}


bool Preprocessor::ExportKdTree(const string filename)
{
	return mKdTree->ExportBinTree(filename.c_str());
}


bool Preprocessor::LoadSamples(VssRayContainer &samples, 
							   ObjectContainer &objects) const
{
	std::stable_sort(objects.begin(), objects.end(), ilt);
	char fileName[100];
	Environment::GetSingleton()->GetStringValue("Preprocessor.samplesFilename", fileName);
	
    Vector3 origin, termination;
	// HACK: needed only for lower_bound algorithm to find the 
	// intersected objects
	MeshInstance sObj(NULL);
	MeshInstance tObj(NULL);

#if USE_ASCII
	ifstream samplesIn(fileName);
	if (!samplesIn.is_open())
		return false;

	string buf;
	while (!(getline(samplesIn, buf)).eof())
	{
		sscanf(buf.c_str(), "%f %f %f %f %f %f %d %d", 
			   &origin.x, &origin.y, &origin.z,
			   &termination.x, &termination.y, &termination.z, 
			   &(sObj.mId), &(tObj.mId));
		
		Intersectable *sourceObj = NULL;
		Intersectable *termObj = NULL;
		
		if (sObj.mId >= 0)
		{
			ObjectContainer::iterator oit =
				lower_bound(objects.begin(), objects.end(), &sObj, ilt);
			sourceObj = *oit;
		}
		
		if (tObj.mId >= 0)
		{
			ObjectContainer::iterator oit =
				lower_bound(objects.begin(), objects.end(), &tObj, ilt);
			termObj = *oit;
		}

		samples.push_back(new VssRay(origin, termination, sourceObj, termObj));
	}
#else
	ifstream samplesIn(fileName, ios::binary);
	if (!samplesIn.is_open())
		return false;

	while (1)
	{
		 samplesIn.read(reinterpret_cast<char *>(&origin), sizeof(Vector3));
		 samplesIn.read(reinterpret_cast<char *>(&termination), sizeof(Vector3));
		 samplesIn.read(reinterpret_cast<char *>(&(sObj.mId)), sizeof(int));
		 samplesIn.read(reinterpret_cast<char *>(&(tObj.mId)), sizeof(int));
		
		 if (samplesIn.eof())
			break;

		Intersectable *sourceObj = NULL;
		Intersectable *termObj = NULL;
		
		if (sObj.mId >= 0)
		{
			ObjectContainer::iterator oit =
				lower_bound(objects.begin(), objects.end(), &sObj, ilt);
			sourceObj = *oit;
		}
		
		if (tObj.mId >= 0)
		{
			ObjectContainer::iterator oit =
				lower_bound(objects.begin(), objects.end(), &tObj, ilt);
			termObj = *oit;
		}

		samples.push_back(new VssRay(origin, termination, sourceObj, termObj));
	}
#endif

	samplesIn.close();

	return true;
}


bool Preprocessor::ExportSamples(const VssRayContainer &samples) const
{
	char fileName[100];
	Environment::GetSingleton()->GetStringValue("Preprocessor.samplesFilename", fileName);
	

	VssRayContainer::const_iterator it, it_end = samples.end();
	
#if USE_ASCII
	ofstream samplesOut(fileName);
	if (!samplesOut.is_open())
		return false;

	for (it = samples.begin(); it != it_end; ++ it)
	{
		VssRay *ray = *it;
		int sourceid = ray->mOriginObject ? ray->mOriginObject->mId : -1;		
		int termid = ray->mTerminationObject ? ray->mTerminationObject->mId : -1;	

		samplesOut << ray->GetOrigin().x << " " << ray->GetOrigin().y << " " << ray->GetOrigin().z << " " 
				   << ray->GetTermination().x << " " << ray->GetTermination().y << " " << ray->GetTermination().z << " " 
				   << sourceid << " " << termid << "\n";
	}
#else
	ofstream samplesOut(fileName, ios::binary);
	if (!samplesOut.is_open())
		return false;

	for (it = samples.begin(); it != it_end; ++ it)
	{	
		VssRay *ray = *it;
		Vector3 origin(ray->GetOrigin());
		Vector3 termination(ray->GetTermination());
		
		int sourceid = ray->mOriginObject ? ray->mOriginObject->mId : -1;		
		int termid = ray->mTerminationObject ? ray->mTerminationObject->mId : -1;		

		samplesOut.write(reinterpret_cast<char *>(&origin), sizeof(Vector3));
		samplesOut.write(reinterpret_cast<char *>(&termination), sizeof(Vector3));
		samplesOut.write(reinterpret_cast<char *>(&sourceid), sizeof(int));
		samplesOut.write(reinterpret_cast<char *>(&termid), sizeof(int));
    }
#endif
	samplesOut.close();

	return true;
}


int
Preprocessor::GenerateRays(const int number,
						   SamplingStrategy &strategy,
						   SimpleRayContainer &rays)
{
  return strategy.GenerateSamples(number, rays);
}


int
Preprocessor::GenerateRays(const int number,
						   const int sampleType,
						   SimpleRayContainer &rays)
{
	const int startSize = (int)rays.size();
	SamplingStrategy *strategy = GenerateSamplingStrategy(sampleType);
	int castRays = 0;

	if (!strategy)
	{
		return 0;
	}

#if 1
	castRays = strategy->GenerateSamples(number, rays);
#else
	GenerateRayBundle(rays, newRay, 16, 0);
	castRays += 16;
#endif

	delete strategy;
	return castRays;
}


SamplingStrategy *Preprocessor::GenerateSamplingStrategy(const int strategyId)
{
	switch (strategyId)
	{
	case SamplingStrategy::OBJECT_BASED_DISTRIBUTION: 
		return new ObjectBasedDistribution(*this);
	case SamplingStrategy::OBJECT_DIRECTION_BASED_DISTRIBUTION:
		return new ObjectDirectionBasedDistribution(*this);
	case SamplingStrategy::DIRECTION_BASED_DISTRIBUTION:
		return new DirectionBasedDistribution(*this);
	case SamplingStrategy::DIRECTION_BOX_BASED_DISTRIBUTION: 
		return new DirectionBoxBasedDistribution(*this);
	case SamplingStrategy::SPATIAL_BOX_BASED_DISTRIBUTION:
		return new SpatialBoxBasedDistribution(*this);
	case SamplingStrategy::REVERSE_OBJECT_BASED_DISTRIBUTION:
		return new ReverseObjectBasedDistribution(*this);
	case SamplingStrategy::VIEWCELL_BORDER_BASED_DISTRIBUTION:
		return new ViewCellBorderBasedDistribution(*this);
	case SamplingStrategy::VIEWSPACE_BORDER_BASED_DISTRIBUTION:
		return new ViewSpaceBorderBasedDistribution(*this);
	case SamplingStrategy::REVERSE_VIEWSPACE_BORDER_BASED_DISTRIBUTION:
		return new ReverseViewSpaceBorderBasedDistribution(*this);
	case SamplingStrategy::GLOBAL_LINES_DISTRIBUTION:
		return new GlobalLinesDistribution(*this);
		
		//case OBJECTS_INTERIOR_DISTRIBUTION:
		//	return new ObjectsInteriorDistribution(*this);
	default: // no valid strategy
		Debug << "warning: no valid sampling strategy" << endl;
		return NULL;
	}

	return NULL; // should never come here
}


bool Preprocessor::LoadInternKdTree( const string internKdTree)
{
  bool mUseKdTree = true;
  
  if (!mUseKdTree) {
	// create just a dummy KdTree
	mKdTree = new KdTree;
	return true;
  }
  
  // always try to load the kd tree
  cout << "loading kd tree file " << internKdTree << " ... " << endl;
  
  if (!LoadKdTree(internKdTree)) {
	cout << "error loading kd tree with filename " 
		 << internKdTree << ", rebuilding it instead ... " << endl;
	// build new kd tree from scene geometry
	BuildKdTree();
	
	// export kd tree?
	const long startTime = GetTime();
	cout << "exporting kd tree ... ";
	
	if (!ExportKdTree(internKdTree))
	  {
		cout << " error exporting kd tree with filename " 
			 << internKdTree << endl;
	  }
	else
	  {
		cout << "finished in " 
			 << TimeDiff(startTime, GetTime()) * 1e-3 
			 << " secs" << endl;
	  }
  }
  
  KdTreeStatistics(cout);
  cout << mKdTree->GetBox() << endl;
  
  return true;
}


bool Preprocessor::InitRayCast(const string externKdTree, 
							   const string internKdTree)
{
	// always try to load the kd tree
/*	cout << "loading kd tree file " << internKdTree << " ... " << endl;

	if (!LoadKdTree(internKdTree))
	{
		cout << "error loading kd tree with filename " 
			 << internKdTree << ", rebuilding it instead ... " << endl;
		// build new kd tree from scene geometry
		BuildKdTree();

		// export kd tree?
		const long startTime = GetTime();
		cout << "exporting kd tree ... ";

		if (!ExportKdTree(internKdTree))
		{
			cout << " error exporting kd tree with filename " 
				 << internKdTree << endl;
		}
		else
		{
			cout << "finished in " 
				 << TimeDiff(startTime, GetTime()) * 1e-3 
				 << " secs" << endl;
		}
	}
	
	KdTreeStatistics(cout);
	cout << mKdTree->GetBox() << endl;
*/
	int rayCastMethod;
	Environment::GetSingleton()->
		GetIntValue("Preprocessor.rayCastMethod", rayCastMethod);

	if (rayCastMethod == 0)
	{
		cout << "ray cast method: internal" << endl;
		mRayCaster = new InternalRayCaster(*this);
	}
	else
	{
#ifdef GTP_INTERNAL
	  cout << "ray cast method: intel" << endl;
	  mRayCaster = new IntelRayCaster(*this, externKdTree);
#endif
	}
	
	// reserve constant block of rays
	cout << "======================" << endl;
	cout << "reserving " << 2 * mSamplesPerPass << " rays " << endl;
	mRayCaster->ReserveVssRayPool(2 * mSamplesPerPass);
	
	return true;
}


void
Preprocessor::CastRays(
					   SimpleRayContainer &rays,
					   VssRayContainer &vssRays,
					   const bool castDoubleRays,
					   const bool pruneInvalidRays
					   )
{

	const long t1 = GetTime();
	
	if ((int)rays.size() > 10000) {
	
		//mRayCaster->SortRays(rays);
		cout<<"Rays sorted in "<<TimeDiff(t1, GetTime())<<" ms."<<endl;

		if (0) {
			VssRayContainer tmpRays;
			int m = 890000;

			for (int i=m; i < m+20; i++) {
				tmpRays.push_back(new VssRay(rays[i].mOrigin,
					rays[i].mOrigin + 100.0f*rays[i].mDirection,
					NULL,
					NULL
					)
					);

			}
			ExportRays("sorted_rays.x3d", tmpRays, 200);
		}
	}

	SimpleRayContainer::const_iterator rit, rit_end = rays.end();
cout << "here1 " << vssRays.size()<<endl;
	SimpleRayContainer rayBucket;
	int i = 0;
	for (rit = rays.begin(); rit != rit_end; ++ rit, ++ i)
	{
		SimpleRay ray = *rit;
#ifdef USE_CG
		// HACK: global lines must be treated special
		if (ray.mDistribution == SamplingStrategy::HW_GLOBAL_LINES_DISTRIBUTION)
		{
			mGlobalLinesRenderer->CastGlobalLines(ray, vssRays);
			continue;
		}
#endif
		rayBucket.push_back(ray);

		// 16 rays gathered => do ray casting
		if ((int)rayBucket.size() >= 16)
		{
			mRayCaster->CastRays16(
								   rayBucket,				
								   vssRays,
								   mViewCellsManager->GetViewSpaceBox(),
								   castDoubleRays,
								   pruneInvalidRays);

			rayBucket.clear();
		}
	
		if ((int)rays.size() > 100000 && i % 100000 == 0)
			cout << "here2 " << vssRays.size()<<endl;
		  //cout<<"\r"<<i<<"/"<<(int)rays.size()<<"\r";
	}
    cout << "here3 " << vssRays.size()<<endl;
	// cast rest of rays
	SimpleRayContainer::const_iterator sit, sit_end = rayBucket.end();

	for (sit = rayBucket.begin(); sit != sit_end; ++ sit)
	{
		SimpleRay ray = *sit;

#ifdef USE_CG
		// HACK: global lines must be treated special
		if (ray.mDistribution == SamplingStrategy::HW_GLOBAL_LINES_DISTRIBUTION)
		{
			mGlobalLinesRenderer->CastGlobalLines(ray, vssRays);
			continue;
		}
#endif
		mRayCaster->CastRay(
							ray,
							vssRays,
							mViewCellsManager->GetViewSpaceBox(),
							castDoubleRays,
							pruneInvalidRays);
		
	}

	cout << "here5 " << vssRays.size()<<endl;

	int m = 850000;

	if (1 && (int)rays.size() > m + 50) {
	  VssRayContainer tmpRays;
	  	  
	  for (int i=m; i < m+20; i++) {
		  if (vssRays[i])
		  {cout<<"e";
		tmpRays.push_back(vssRays[i]);
		  }
		  else cout <<"d";
	  }
	  ExportRays("sorted_rays2.x3d", tmpRays, 200);
	}

	if ((int)rays.size() > 10000) 
	{
		cout << endl;
        long t2 = GetTime();

#if SHOW_RAYCAST_TIMING
		if (castDoubleRays)
			cout << 2 * rays.size() / (1e3f * TimeDiff(t1, t2)) << "M rays/s" << endl;
		else
			cout << rays.size() / (1e3f * TimeDiff(t1, t2)) << "M rays/s" << endl;
#endif
	}

	DeterminePvsObjects(vssRays);
}


bool Preprocessor::GenerateRayBundle(SimpleRayContainer &rayBundle,									
									 const SimpleRay &mainRay,
									 const int number,
									 const int pertubType) const
{
	rayBundle.push_back(mainRay);

	const float pertubOrigin = 0.0f;
	const float pertubDir = 0.2f;

	for (int i = 0; i < number - 1; ++ i)
	{
		Vector3 pertub;

		pertub.x = RandomValue(0.0f, pertubDir);
		pertub.y = RandomValue(0.0f, pertubDir);
		pertub.z = RandomValue(0.0f, pertubDir);

		const Vector3 newDir = mainRay.mDirection + pertub;
		//const Vector3 newDir = mainRay.mDirection;

		pertub.x = RandomValue(0.0f, pertubOrigin);
		pertub.y = RandomValue(0.0f, pertubOrigin);
		pertub.z = RandomValue(0.0f, pertubOrigin);

		const Vector3 newOrigin = mainRay.mOrigin + pertub;
		//const Vector3 newOrigin = mainRay.mOrigin;

		rayBundle.push_back(SimpleRay(newOrigin, newDir, 0, 1.0f));
	}

	return true;
}


void Preprocessor::SetupRay(Ray &ray,
							const Vector3 &point,
							const Vector3 &direction) const
{
	ray.Clear();
	// do not store anything else then intersections at the ray
	ray.Init(point, direction, Ray::LOCAL_RAY);	
}


void Preprocessor::EvalViewCellHistogram()
{
	char filename[256];
	Environment::GetSingleton()->GetStringValue("Preprocessor.histogram.file", filename);
  
	// mViewCellsManager->EvalViewCellHistogram(filename, 1000000);
	mViewCellsManager->EvalViewCellHistogramForPvsSize(filename, 1000000);
}


bool
Preprocessor::ExportRays(const char *filename,
						 const VssRayContainer &vssRays,
						 const int number,
						 const bool exportScene
						 )
{
  cout<<"Exporting vss rays..."<<endl<<flush;
  
  Exporter *exporter = NULL;
  exporter = Exporter::GetExporter(filename);

  if (0) {
	exporter->SetWireframe();
	exporter->ExportKdTree(*mKdTree);
  }
  
  exporter->SetFilled();
  // $$JB temporarily do not export the scene
  if (exportScene)
	exporter->ExportScene(mSceneGraph->GetRoot());

  exporter->SetWireframe();

  if (1) {
	exporter->SetForcedMaterial(RgbColor(1,0,1));
	exporter->ExportBox(mViewCellsManager->GetViewSpaceBox());
	exporter->ResetForcedMaterial();
  }
  
  VssRayContainer rays;
  vssRays.SelectRays(number, rays);
  exporter->ExportRays(rays, RgbColor(1, 0, 0));
  delete exporter;
  cout<<"done."<<endl<<flush;

  return true;
}

bool
Preprocessor::ExportRayAnimation(const char *filename,
								 const vector<VssRayContainer> &vssRays
								 )
{
  cout<<"Exporting vss rays..."<<endl<<flush;
	
  Exporter *exporter = NULL;
  exporter = Exporter::GetExporter(filename);
  if (0) {
	exporter->SetWireframe();
	exporter->ExportKdTree(*mKdTree);
  }
  exporter->SetFilled();
  // $$JB temporarily do not export the scene
  if (0)
	exporter->ExportScene(mSceneGraph->GetRoot());
  exporter->SetWireframe();

  if (1) {
	exporter->SetForcedMaterial(RgbColor(1,0,1));
	exporter->ExportBox(mViewCellsManager->GetViewSpaceBox());
	exporter->ResetForcedMaterial();
  }
  
  exporter->ExportRaySets(vssRays, RgbColor(1, 0, 0));
	
  delete exporter;

  cout<<"done."<<endl<<flush;

  return true;
}

void
Preprocessor::ComputeRenderError()
{
  // compute rendering error
	
  if (renderer && renderer->mPvsStatFrames) {
	//	emit EvalPvsStat();
	//	QMutex mutex;
	//	mutex.lock();
	//	renderer->mRenderingFinished.wait(&mutex);
	//	mutex.unlock();

	if (mViewCellsManager->GetViewCellPoints()->size()) {
	  
	  vector<ViewCellPoints *> *vcPoints = mViewCellsManager->GetViewCellPoints();
	  
	  vector<ViewCellPoints *>::const_iterator
		vit = vcPoints->begin(),
		vit_end = vcPoints->end();

	  SimpleRayContainer viewPoints;
	  
	  for (; vit != vit_end; ++ vit) {
		ViewCellPoints *vp = *vit;

		SimpleRayContainer::const_iterator rit = vp->second.begin(), rit_end = vp->second.end();
		for (; rit!=rit_end; ++rit)
		  viewPoints.push_back(*rit);
	  }

	  if (viewPoints.size() != renderer->mPvsErrorBuffer.size()) {
		renderer->mPvsErrorBuffer.resize(viewPoints.size());
		renderer->ClearErrorBuffer();
	  }

	  renderer->EvalPvsStat(viewPoints);
	} else
	  renderer->EvalPvsStat();

	mStats <<
	  "#AvgPvsRenderError\n" <<renderer->mPvsStat.GetAvgError()<<endl<<
	  "#AvgPixelError\n" <<renderer->GetAvgPixelError()<<endl<<
	  "#MaxPixelError\n" <<renderer->GetMaxPixelError()<<endl<<
	  "#MaxPvsRenderError\n" <<renderer->mPvsStat.GetMaxError()<<endl<<
	  "#ErrorFreeFrames\n" <<renderer->mPvsStat.GetErrorFreeFrames()<<endl<<
	  "#AvgRenderPvs\n" <<renderer->mPvsStat.GetAvgPvs()<<endl;
  }
}


Intersectable *Preprocessor::GetObjectById(const int id)
{
#if 1
	// create a dummy mesh instance to be able to use stl
	MeshInstance object(NULL);
	object.SetId(id);

	ObjectContainer::const_iterator oit =
		lower_bound(mObjects.begin(), mObjects.end(), &object, ilt);
				
	// objects sorted by id
	if ((oit != mObjects.end()) && ((*oit)->GetId() == object.GetId()))
	{
		return (*oit);
	}
	else
	{
		return NULL;
	}
#else
	return mObjects[id - 1];
#endif
}


void Preprocessor::PrepareHwGlobalLines()
{
	int texHeight, texWidth;
	float eps;
	int maxDepth;
	bool sampleReverse;

	Environment::GetSingleton()->GetIntValue("Preprocessor.HwGlobalLines.texHeight", texHeight);
	Environment::GetSingleton()->GetIntValue("Preprocessor.HwGlobalLines.texWidth", texWidth);
	Environment::GetSingleton()->GetFloatValue("Preprocessor.HwGlobalLines.stepSize", eps);
	Environment::GetSingleton()->GetIntValue("Preprocessor.HwGlobalLines.maxDepth", maxDepth);
	Environment::GetSingleton()->GetBoolValue("Preprocessor.HwGlobalLines.sampleReverse", sampleReverse);

	Debug << "****** hw global line options *******" << endl;
	Debug << "texWidth: " << texWidth << endl;
	Debug << "texHeight: " << texHeight << endl;
	Debug << "sampleReverse: " << sampleReverse << endl;
	Debug << "max depth: " << maxDepth << endl;
	Debug << "step size: " << eps << endl;
	Debug << endl;

#ifdef USE_CG
	globalLinesRenderer = mGlobalLinesRenderer = 
		new GlobalLinesRenderer(this,
								texHeight,
								texWidth,
								eps,
								maxDepth,
								sampleReverse);

	mGlobalLinesRenderer->InitGl();

#endif
}


void Preprocessor::DeterminePvsObjects(VssRayContainer &rays)
{
	mViewCellsManager->DeterminePvsObjects(rays, false);
}


}