#include <stack>
#include <time.h>
#include <iomanip>

#include "ViewCell.h"
#include "Plane3.h"
#include "HierarchyManager.h"
#include "Mesh.h"
#include "common.h"
#include "Environment.h"
#include "Polygon3.h"
#include "Ray.h"
#include "AxisAlignedBox3.h"
#include "Exporter.h"
#include "Plane3.h"
#include "ViewCellsManager.h"
#include "Beam.h"
#include "KdTree.h"
#include "IntersectableWrapper.h"
#include "VspTree.h"
#include "OspTree.h"
#include "BvHierarchy.h"
#include "ViewCell.h"


namespace GtpVisibilityPreprocessor {


#define USE_FIXEDPOINT_T 0


/*******************************************************************/
/*              class HierarchyManager implementation              */
/*******************************************************************/


HierarchyManager::HierarchyManager(const int objectSpaceSubdivisionType):
mObjectSpaceSubdivisionType(objectSpaceSubdivisionType),
mOspTree(NULL), 
mBvHierarchy(NULL)
{
	switch(mObjectSpaceSubdivisionType)
	{
	case KD_BASED_OBJ_SUBDIV:
		mOspTree = new OspTree();
		mOspTree->mVspTree = mVspTree;
		mOspTree->mHierarchyManager = this;
		break;
	case BV_BASED_OBJ_SUBDIV:
        mBvHierarchy = new BvHierarchy();
		mBvHierarchy->mHierarchyManager = this;
		break;
	default:
		break;
	}

	// hierarchy manager links view space partition and object space partition
	mVspTree = new VspTree();
	mVspTree->mHierarchyManager = this;
	
	mViewSpaceSubdivisionType = KD_BASED_VIEWSPACE_SUBDIV;
	ParseEnvironment();
}


HierarchyManager::HierarchyManager(KdTree *kdTree): 
mObjectSpaceSubdivisionType(KD_BASED_OBJ_SUBDIV),
mBvHierarchy(NULL)
{
	mOspTree = new OspTree(*kdTree);
	mOspTree->mVspTree = mVspTree;

	mVspTree = new VspTree();
	mVspTree->mHierarchyManager = this;

	mViewSpaceSubdivisionType = KD_BASED_VIEWSPACE_SUBDIV;
	ParseEnvironment();
}


void HierarchySubdivisionStats::Print(ostream &app) const
{
	app << "#Pass\n" << 0 << endl
		<< "#Splits\n" << mNumSplits << endl 
		<< "#TotalRenderCost\n" << mTotalRenderCost << endl
		<< "#TotalEntriesInPvs\n" << mEntriesInPvs << endl
		<< "#Memory\n" << mMemoryCost << endl
		<< "#StepsView\n" << mViewSpaceSplits << endl
		<< "#StepsObject\n" << mObjectSpaceSplits << endl
		<< "#VspOspRatio\n" << VspOspRatio() << endl
		<< "#FullMem\n" << mFullMemory << endl
		<< "#RenderCostDecrease\n" << mRenderCostDecrease << endl
		<< "#Priority\n" << mPriority << endl
		<< "#FpsPerMb\n" << FpsPerMb() << endl
		<< endl;
}


void HierarchyManager::ParseEnvironment()
{
	Environment::GetSingleton()->GetFloatValue(
		"Hierarchy.Termination.minGlobalCostRatio", mTermMinGlobalCostRatio);
	Environment::GetSingleton()->GetIntValue(
		"Hierarchy.Termination.globalCostMissTolerance", mTermGlobalCostMissTolerance);

	Environment::GetSingleton()->GetBoolValue(
		"Hierarchy.Construction.startWithObjectSpace", mStartWithObjectSpace);

	Environment::GetSingleton()->GetIntValue(
		"Hierarchy.Termination.maxLeaves", mTermMaxLeaves);

	Environment::GetSingleton()->GetIntValue(
		"Hierarchy.Construction.type", mConstructionType);

	Environment::GetSingleton()->GetIntValue(
		"Hierarchy.Construction.minDepthForOsp", mMinDepthForObjectSpaceSubdivion);

	Environment::GetSingleton()->GetIntValue(
		"Hierarchy.Construction.minDepthForVsp", mMinDepthForViewSpaceSubdivion);
	
	Environment::GetSingleton()->GetBoolValue(
		"Hierarchy.Construction.repairQueue", mRepairQueue);

	Environment::GetSingleton()->GetBoolValue(
		"Hierarchy.Construction.useMultiLevel", mUseMultiLevelConstruction);

	Environment::GetSingleton()->GetIntValue(
		"Hierarchy.Construction.levels", mNumMultiLevels);

	Environment::GetSingleton()->GetIntValue(
		"Hierarchy.Construction.minStepsOfSameType", mMinStepsOfSameType);
	
	Environment::GetSingleton()->GetIntValue(
		"Hierarchy.Construction.maxStepsOfSameType", mMaxStepsOfSameType);

	char subdivisionStatsLog[100];
	Environment::GetSingleton()->GetStringValue("Hierarchy.subdivisionStats", subdivisionStatsLog);
	mSubdivisionStats.open(subdivisionStatsLog);

	Environment::GetSingleton()->GetBoolValue(
		"Hierarchy.Construction.recomputeSplitPlaneOnRepair", mRecomputeSplitPlaneOnRepair);

	Environment::GetSingleton()->GetBoolValue(
		"Hierarchy.Construction.considerMemory", mConsiderMemory);

	Environment::GetSingleton()->GetFloatValue(
		"Hierarchy.Termination.maxMemory", mTermMaxMemory);

	Environment::GetSingleton()->GetIntValue(
		"Hierarchy.Construction.maxRepairs", mMaxRepairs);

	// compare to bytes
	mTermMaxMemory *= (1024.0f * 1024.0f);

	Debug << "******** Hierarchy Manager Options ***********" << endl;
	Debug << "max leaves: " << mTermMaxLeaves << endl;
	Debug << "min global cost ratio: " << mTermMinGlobalCostRatio << endl;
	Debug << "global cost miss tolerance: " << mTermGlobalCostMissTolerance << endl;
	Debug << "min depth for object space subdivision: " << mMinDepthForObjectSpaceSubdivion << endl;
	Debug << "repair queue: " << mRepairQueue << endl;
	Debug << "number of multilevels: " << mNumMultiLevels << endl;
	Debug << "recompute split plane on repair: " << mRecomputeSplitPlaneOnRepair << endl;
	Debug << "minimal number of steps from same type: " << mMinStepsOfSameType << endl;
	Debug << "maximal allowed memory: " << mTermMaxMemory << endl;
	Debug << "consider memory: " << mConsiderMemory << endl;
	Debug << "min steps of same kind: " << mMinStepsOfSameType << endl;
	Debug << "max steps of same kind: " << mMaxStepsOfSameType << endl;
	Debug << "max repairs: " << mMaxRepairs << endl;

	switch (mConstructionType)
	{
	case 0:
		Debug << "construction type: sequential" << endl;
		break;
	case 1:
		Debug << "construction type: interleaved" << endl;
		break;
	case 2:
		Debug << "construction type: gradient" << endl;
		break;
	case 3:
		Debug << "construction type: multilevel" << endl;
		break;
	default:
		Debug << "construction type " << mConstructionType << " unknown" << endl;
		break;
	}

	//Debug << "min render cost " << mMinRenderCostDecrease << endl;
	Debug << endl;
}


HierarchyManager::~HierarchyManager()
{
	DEL_PTR(mOspTree);
	DEL_PTR(mVspTree);
	DEL_PTR(mBvHierarchy);
}


int HierarchyManager::GetObjectSpaceSubdivisionType() const
{
	return mObjectSpaceSubdivisionType;
}


int HierarchyManager::GetViewSpaceSubdivisionType() const
{
	return mViewSpaceSubdivisionType;
}


void HierarchyManager::SetViewCellsManager(ViewCellsManager *vcm)
{
	mVspTree->SetViewCellsManager(vcm);

	if (mOspTree)
	{
		mOspTree->SetViewCellsManager(vcm);
	}
	else if (mBvHierarchy)
	{
		mBvHierarchy->SetViewCellsManager(vcm);
	}
}


void HierarchyManager::SetViewCellsTree(ViewCellsTree *vcTree)
{
	mVspTree->SetViewCellsTree(vcTree);
}


VspTree *HierarchyManager::GetVspTree() 
{ 
	return mVspTree; 
}

/*
AxisAlignedBox3 HierarchyManager::GetViewSpaceBox() const
{
	return mVspTree->mBoundingBox;
}*/


AxisAlignedBox3 HierarchyManager::GetObjectSpaceBox() const
{
	switch (mObjectSpaceSubdivisionType)
	{
	case KD_BASED_OBJ_SUBDIV:
		return mOspTree->mBoundingBox;
	case BV_BASED_OBJ_SUBDIV:
		return mBvHierarchy->mBoundingBox;
	default:
		// hack: empty box
		return AxisAlignedBox3();
	}
}


SubdivisionCandidate *HierarchyManager::NextSubdivisionCandidate(SplitQueue &splitQueue)
{
	SubdivisionCandidate *splitCandidate = splitQueue.Top();
	splitQueue.Pop();

	// split was not reevaluated before => do it now
	if (splitCandidate->IsDirty())
		splitCandidate->EvalCandidate();

	return splitCandidate;
}


void HierarchyManager::EvalSubdivisionStats()
{
	// question: should I also add the mem usage of the hierarchies?
	const float objectSpaceMem = GetObjectSpaceMemUsage();
	const float viewSpaceMem = mVspTree->GetMemUsage();
		
	HierarchySubdivisionStats stats;

	stats.mNumSplits = mHierarchyStats.Leaves();
	stats.mTotalRenderCost = mHierarchyStats.mTotalCost;
	stats.mEntriesInPvs = mHierarchyStats.mPvsEntries;
	stats.mMemoryCost = mHierarchyStats.mMemory  / float(1024 * 1024);
	stats.mFullMemory = mHierarchyStats.mMemory  / float(1024 * 1024)
						+ objectSpaceMem + viewSpaceMem;
	stats.mViewSpaceSplits = mVspTree->mVspStats.Leaves();
	stats.mObjectSpaceSplits = GetObjectSpaceSubdivisionLeaves();
	stats.mRenderCostDecrease = mHierarchyStats.mRenderCostDecrease;
	stats.mPriority = mPriority;

	stats.Print(mSubdivisionStats);
}


void HierarchyManager::AddSubdivisionStats(const int splits,
										   const float renderCostDecr,
										   const float totalRenderCost,
										   const int pvsEntries,
										   const float memory,
										   const float renderCostPerStorage,
										   const float vspOspRatio)
{
	mSubdivisionStats
			<< "#Splits\n" << splits << endl
			<< "#RenderCostDecrease\n" << renderCostDecr << endl 
			<< "#TotalEntriesInPvs\n" << pvsEntries << endl
			<< "#TotalRenderCost\n" << totalRenderCost << endl
			<< "#Memory\n" << memory << endl
			<< "#FpsPerMb\n" << renderCostPerStorage << endl
			<< "#VspOspRatio\n" << vspOspRatio << endl
			<< endl;
}


bool HierarchyManager::GlobalTerminationCriteriaMet(SubdivisionCandidate *candidate) const
{
	const bool terminationCriteriaMet = 
		(0
		|| (mHierarchyStats.Leaves() >= mTermMaxLeaves) 
		|| (mHierarchyStats.mMemory >= mTermMaxMemory)
		|| candidate->GlobalTerminationCriteriaMet()
		//|| (mHierarchyStats.mRenderCostDecrease < mMinRenderCostDecrease)
		//|| (mHierarchyStats.mGlobalCostMisses >= mTermGlobalCostMissTolerance)
		);

#if GTP_DEBUG
	if (terminationCriteriaMet)
	{
		Debug << "hierarchy global termination criteria met:" << endl;
		Debug << "leaves: " << mHierarchyStats.Leaves() << " " << mTermMaxLeaves << endl;
		Debug << "cost misses: " << mHierarchyStats.mGlobalCostMisses << " " << mTermGlobalCostMissTolerance << endl;
		Debug << "memory: " << mHierarchyStats.mMemory << " " << mTermMaxMemory << endl;
	}
#endif

	return terminationCriteriaMet;
}


void HierarchyManager::Construct(const VssRayContainer &sampleRays,
								 const ObjectContainer &objects,
								 AxisAlignedBox3 *forcedViewSpace)
{
	mTimeStamp = 1;

	switch (mConstructionType)
	{
	case MULTILEVEL:
		ConstructMultiLevel(sampleRays, objects, forcedViewSpace);
		break;
	case INTERLEAVED:
	case SEQUENTIAL:
		ConstructInterleaved(sampleRays, objects, forcedViewSpace);
		break;
	case GRADIENT:
		ConstructInterleavedWithGradient(sampleRays, objects, forcedViewSpace);
		break;
	default:
		break;
	}

	// hack: should be different parameter name
	if (mUseMultiLevelConstruction)
	{
		cout << "starting optimizing multilevel ... " << endl;
		// try to optimize on the above hierarchy
		OptimizeMultiLevel(sampleRays, objects, forcedViewSpace);
		
		cout << "finished" << endl;
	}
}


void HierarchyManager::ConstructInterleavedWithGradient(const VssRayContainer &sampleRays,
														const ObjectContainer &objects,
														AxisAlignedBox3 *forcedViewSpace)
{
	mHierarchyStats.Reset();
	mHierarchyStats.Start();
	
	mHierarchyStats.mNodes = 2;

	// create first nodes
	mVspTree->Initialise(sampleRays, forcedViewSpace);
	InitialiseObjectSpaceSubdivision(objects);

	// hack: assume that object space can be seen from view space
	mHierarchyStats.mTotalCost = mInitialRenderCost = (float)objects.size();
	// only one entry for start
	mHierarchyStats.mPvsEntries = 1;
	mHierarchyStats.mMemory = (float)ObjectPvs::GetEntrySizeByte();

	EvalSubdivisionStats();
	Debug << "setting total cost to " << mHierarchyStats.mTotalCost << endl;

	const long startTime = GetTime();
	cout << "Constructing view space / object space tree ... \n";
	
	SplitQueue objectSpaceQueue;
	SplitQueue viewSpaceQueue;

	int vspSteps = 0, ospSteps = 0;

	// use sah for evaluating osp tree construction 
	// in the first iteration of the subdivision
	mSavedViewSpaceSubdivisionType = mViewSpaceSubdivisionType;
	mViewSpaceSubdivisionType = NO_VIEWSPACE_SUBDIV;
	mSavedObjectSpaceSubdivisionType = mObjectSpaceSubdivisionType;

	// number of initial splits
	const int minSteps = mMinStepsOfSameType;
	const int maxSteps = mMaxStepsOfSameType;

	SubdivisionCandidate *osc = 
		PrepareObjectSpaceSubdivision(sampleRays, objects);
	objectSpaceQueue.Push(osc);

	/////////////////////////
	// calulcate initial object space splits
	
	SubdivisionCandidateContainer dirtyList;

	// subdivide object space first
	// for first round, use sah splits. Once view space partition
	// has started, use render cost heuristics instead
	ospSteps = RunConstruction(objectSpaceQueue, 
							   dirtyList, 
							   NULL, 
							   minSteps, 
							   maxSteps);

	cout << "\n" << ospSteps << " object space partition steps taken" << endl;

	// create view space
	SubdivisionCandidate *vsc = PrepareViewSpaceSubdivision(sampleRays, objects);
	viewSpaceQueue.Push(vsc);

	dirtyList.clear();

	// view space subdivision started
	mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;

	if (1)
	{
		// rather also start with 100 view space splits to avoid initial bias.
		vspSteps = RunConstruction(viewSpaceQueue, dirtyList, NULL, minSteps, maxSteps);
		cout << "\n" << vspSteps << " view space partition steps taken" << endl;
		
		/// Repair split queue
		cout << "repairing queue ... " << endl;
		RepairQueue(dirtyList, objectSpaceQueue, true);
		cout << "repaired " << (int)dirtyList.size() << " candidates" << endl;

		dirtyList.clear();
	}
	else
	{
		// the priorities were calculated for driving sah.
		// => recalculate "real" priorities taking visibility into
		// account so we can compare to view space splits
		ResetQueue(objectSpaceQueue, false);
	}

	// This method subdivides view space / object space 
	// in order to converge to some optimal cost for this partition
	// start with object space partiton
	// then optimizate view space partition for the current osp
	// and vice versa until iteration depth is reached.

	bool lastSplitWasOsp = true;

	while (!(viewSpaceQueue.Empty() && objectSpaceQueue.Empty()))
	{
		// decide upon next split type
		const float vspPriority = viewSpaceQueue.Top() ? viewSpaceQueue.Top()->GetPriority() : -1e20f;
		const float ospPriority = objectSpaceQueue.Top() ? objectSpaceQueue.Top()->GetPriority() : -1e20f;
		
		cout << "new decicion, vsp: " << vspPriority << ", osp: " << ospPriority << endl;

		// should view or object space be subdivided further?
		if (ospPriority >= vspPriority)
		//if (!lastSplitWasOsp)
		{
			lastSplitWasOsp = true;
			cout << "osp" << endl;
			
			// dirtied view space candidates
			SubdivisionCandidateContainer dirtyVspList;

			// subdivide object space first for first round, 
			// use sah splits. Once view space partition
			// has started, use render cost heuristics instead
			const int ospSteps = RunConstruction(objectSpaceQueue, 
												 dirtyVspList, 
												 viewSpaceQueue.Top(), 
												 minSteps, 
												 maxSteps);

			cout << "\n" << ospSteps << " object space partition steps taken" << endl;
			Debug << "\n" << ospSteps << " object space partition steps taken" << endl;

			/// Repair split queue, i.e., affected view space candidates
			cout << "repairing queue ... " << endl;
			const int repaired = RepairQueue(dirtyVspList, viewSpaceQueue, true);
            
			cout << "\nrepaired " << repaired << " candidates from " << (int)dirtyVspList.size() << " dirtied candidates" << endl;
		}
		else
		{
			lastSplitWasOsp = false;
			cout << "vsp" << endl;
			
			/////////////////
			// subdivide view space with respect to the objects

			// dirtied object space candidates
			SubdivisionCandidateContainer dirtyOspList;

			// process view space candidates
			const int vspSteps = RunConstruction(viewSpaceQueue, 
												 dirtyOspList, 
												 objectSpaceQueue.Top(), 
												 minSteps, 
												 maxSteps);

			cout << "\n" << vspSteps << " view space partition steps taken" << endl;
			Debug << "\n" << vspSteps << " view space partition steps taken" << endl;

			// view space subdivision constructed
			mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;

			/// Repair split queue
			cout << "repairing queue ... " << endl;
			const int repaired = RepairQueue(dirtyOspList, objectSpaceQueue, true);

			cout << "\nrepaired " << repaired << " candidates from " << (int)dirtyOspList.size() << " dirtied candidates" << endl;
		}
	}

	cout << "\nfinished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;

	mHierarchyStats.Stop();
	mVspTree->mVspStats.Stop();

	FinishObjectSpaceSubdivision(objects, !mUseMultiLevelConstruction);
}


void HierarchyManager::ConstructInterleaved(const VssRayContainer &sampleRays,
											const ObjectContainer &objects,
											AxisAlignedBox3 *forcedViewSpace)
{
	mHierarchyStats.Reset();
	mHierarchyStats.Start();

	// two nodes for view space and object space
	mHierarchyStats.mNodes = 2; 
	mHierarchyStats.mPvsEntries = 1;
	mHierarchyStats.mMemory = (float)ObjectPvs::GetEntrySizeByte();
	mHierarchyStats.mTotalCost = (float)objects.size();

	mHierarchyStats.mRenderCostDecrease = 0;

	EvalSubdivisionStats();
	Debug << "setting total cost to " << mHierarchyStats.mTotalCost << endl;

	const long startTime = GetTime();
	cout << "Constructing view space / object space tree ... \n";
	
	// create only roots
	mVspTree->Initialise(sampleRays, forcedViewSpace);
	InitialiseObjectSpaceSubdivision(objects);

	// use objects for evaluating vsp tree construction in the 
	// first levels of the subdivision
	mSavedObjectSpaceSubdivisionType = mObjectSpaceSubdivisionType;
	mObjectSpaceSubdivisionType = NO_OBJ_SUBDIV;

	mSavedViewSpaceSubdivisionType = mViewSpaceSubdivisionType;
	mViewSpaceSubdivisionType = NO_VIEWSPACE_SUBDIV;

	// start view space subdivison immediately?
	if (StartViewSpaceSubdivision())
	{
		// prepare vsp tree for traversal
        mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
		SubdivisionCandidate *vspSc = 
			PrepareViewSpaceSubdivision(sampleRays, objects);

		mTQueue.Push(vspSc);
	}
	
	// start object space subdivision immediately?
	if (StartObjectSpaceSubdivision())
	{
		mObjectSpaceSubdivisionType = mSavedObjectSpaceSubdivisionType;
		SubdivisionCandidate *ospSc =
			PrepareObjectSpaceSubdivision(sampleRays, objects);
		mTQueue.Push(ospSc);
	}

	// begin subdivision
	RunConstruction(mRepairQueue, sampleRays, objects, forcedViewSpace);
	
	cout << "\nfinished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;

	mObjectSpaceSubdivisionType = mSavedObjectSpaceSubdivisionType;
	mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;

	mHierarchyStats.Stop();
	mVspTree->mVspStats.Stop();
	
	FinishObjectSpaceSubdivision(objects, !mUseMultiLevelConstruction);
}


SubdivisionCandidate *HierarchyManager::PrepareViewSpaceSubdivision(const VssRayContainer &sampleRays,
																	const ObjectContainer &objects)
{
	cout << "\npreparing view space hierarchy construction ... " << endl;

	// hack: reset global cost misses
	mHierarchyStats.mGlobalCostMisses = 0;

	RayInfoContainer *viewSpaceRays = new RayInfoContainer();
	SubdivisionCandidate *vsc = 
		mVspTree->PrepareConstruction(sampleRays, *viewSpaceRays);

	/////////
	//-- new stats

	mHierarchyStats.mTotalCost = mVspTree->mTotalCost;
	
	cout << "\nreseting cost for vsp, new total cost: " << mHierarchyStats.mTotalCost << endl;

	return vsc;
}


float HierarchyManager::GetObjectSpaceMemUsage() const
{
	if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
	{
		// TODO;
	}
	else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
	{
		return mBvHierarchy->GetMemUsage();
	}

	return -1;
}

void HierarchyManager::InitialiseObjectSpaceSubdivision(const ObjectContainer &objects)
{
	if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
	{
		// TODO;
	}
	else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
	{
		mBvHierarchy->Initialise(objects);
	}
}


SubdivisionCandidate *HierarchyManager::PrepareObjectSpaceSubdivision(const VssRayContainer &sampleRays,
																	  const ObjectContainer &objects)
{
	// hack: reset global cost misses
	mHierarchyStats.mGlobalCostMisses = 0;

	if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
	{
		return PrepareOspTree(sampleRays, objects);
	}
	else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
	{
		return PrepareBvHierarchy(sampleRays, objects);
	}
	
	return NULL;
}


SubdivisionCandidate *HierarchyManager::PrepareBvHierarchy(const VssRayContainer &sampleRays,
														   const ObjectContainer &objects)
{
	const long startTime = GetTime();

	cout << "preparing bv hierarchy construction ... " << endl;
	
	// compute first candidate
	SubdivisionCandidate *sc =
		mBvHierarchy->PrepareConstruction(sampleRays, objects);

	mHierarchyStats.mTotalCost = mBvHierarchy->mTotalCost;
	Debug << "\nreseting cost, new total cost: " << mHierarchyStats.mTotalCost << endl;

	cout << "finished bv hierarchy preparation in " 
		 << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
	 
	return sc;
}


SubdivisionCandidate *HierarchyManager::PrepareOspTree(const VssRayContainer &sampleRays,
													   const ObjectContainer &objects)
{
	cout << "starting osp tree construction ... " << endl;

	RayInfoContainer *objectSpaceRays = new RayInfoContainer();

	// start with one big kd cell - all objects can be seen from everywhere
	// note: only true for view space = object space

	// compute first candidate
	SubdivisionCandidate *osc =
		mOspTree->PrepareConstruction(sampleRays, objects, *objectSpaceRays);

	mHierarchyStats.mTotalCost = mOspTree->mTotalCost;
	Debug << "\nreseting cost for osp, new total cost: " << mHierarchyStats.mTotalCost << endl;
	
    return osc;
}


bool HierarchyManager::ApplySubdivisionCandidate(SubdivisionCandidate *sc, 
												 SplitQueue &splitQueue,
												 const bool repairQueue)
{
	const bool terminationCriteriaMet = GlobalTerminationCriteriaMet(sc);
	const bool success = sc->Apply(splitQueue, terminationCriteriaMet);

	if (sc->IsDirty())
		cerr << "Error: Should never come here!" << endl;

	if (!success) // split was not taken
	{
		return false;
	}

	//cout << "priority: " << sc->GetPriority() << " rc decr: " << sc->GetRenderCostDecrease() << " | ";
	///////////////
	//-- split was successful => update stats and queue

    // cost ratio of cost decrease / totalCost
	const float costRatio = sc->GetRenderCostDecrease() / mHierarchyStats.mTotalCost;
	//cout << "ratio: " << costRatio << " min ratio: " << mTermMinGlobalCostRatio << endl;
	
	if (costRatio < mTermMinGlobalCostRatio)
	{
		++ mHierarchyStats.mGlobalCostMisses;
	}
	
	cout << sc->Type() << " ";
		
	/////////////
	// update stats

	mHierarchyStats.mNodes += 2;
	mHierarchyStats.mTotalCost -= sc->GetRenderCostDecrease();

	const int pvsEntriesIncr = sc->GetPvsEntriesIncr();
	mHierarchyStats.mPvsEntries += pvsEntriesIncr;
	//cout << "pvs entries: " << pvsEntriesIncr << " " << mHierarchyStats.pvsEntries << endl;

	// memory size in byte
	mHierarchyStats.mMemory += (float)ObjectPvs::GetEntrySizeByte() * pvsEntriesIncr;
	mHierarchyStats.mRenderCostDecrease = sc->GetRenderCostDecrease();
	
	mPriority = sc->GetPriority();

	static float memoryCount = 0;

	if (mHierarchyStats.mMemory > memoryCount)
	{
		memoryCount += 100000;
		cout << "\nstorage cost: " << mHierarchyStats.mMemory / float(1024 * 1024) 
			 << " MB, steps: " << mHierarchyStats.Leaves() << endl;
	}

	// output stats
	EvalSubdivisionStats();
		
	if (repairQueue) 
	{
		// reevaluate candidates affected by the split for view space splits, 
		// this would be object space splits and other way round
		vector<SubdivisionCandidate *> dirtyList;
		sc->CollectDirtyCandidates(dirtyList, false);

		RepairQueue(dirtyList, splitQueue, mRecomputeSplitPlaneOnRepair);
	}

	return true;
}


int HierarchyManager::GetObjectSpaceSubdivisionDepth() const
{
	int maxDepth = 0;

	if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
	{
		maxDepth = mOspTree->mOspStats.maxDepth;
	}
	else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
	{
		maxDepth = mBvHierarchy->mBvhStats.maxDepth;
	}

	return maxDepth;
}


int HierarchyManager::GetObjectSpaceSubdivisionLeaves() const
{
	int maxLeaves= 0;

	if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
	{
		maxLeaves = mOspTree->mOspStats.Leaves();
	}
	else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
	{
		maxLeaves = mBvHierarchy->mBvhStats.Leaves();
	}

	return maxLeaves;
}


int HierarchyManager::GetObjectSpaceSubdivisionNodes() const
{
	int maxLeaves = 0;

	if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
	{
		maxLeaves = mOspTree->mOspStats.nodes;
	}
	else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
	{
		maxLeaves = mBvHierarchy->mBvhStats.nodes;
	}

	return maxLeaves;
}

bool HierarchyManager::StartObjectSpaceSubdivision() const
{
	// view space construction already started
	if (ObjectSpaceSubdivisionConstructed())
		return false;

	// start immediately with object space subdivision?
	if (mStartWithObjectSpace)
		return true;

	// is the queue empty again?
	if (ViewSpaceSubdivisionConstructed() && mTQueue.Empty())
		return true;

	// has the depth for subdivision been reached?
	return 
		((mConstructionType == INTERLEAVED) && 
		 (mMinStepsOfSameType <= mVspTree->mVspStats.nodes));
}


bool HierarchyManager::StartViewSpaceSubdivision() const
{
	// view space construction already started
	if (ViewSpaceSubdivisionConstructed())
		return false;

	// start immediately with view space subdivision?
	if (!mStartWithObjectSpace)
		return true;

	// is the queue empty again?
	if (ObjectSpaceSubdivisionConstructed() && mTQueue.Empty())
		return true;

	// has the depth for subdivision been reached?
	return 
		((mConstructionType == INTERLEAVED) && 
		 (mMinStepsOfSameType <= GetObjectSpaceSubdivisionLeaves()));
}


void HierarchyManager::RunConstruction(const bool repairQueue,
									   const VssRayContainer &sampleRays,
									   const ObjectContainer &objects,
									   AxisAlignedBox3 *forcedViewSpace)
{
	while (!FinishedConstruction())
	{
		SubdivisionCandidate *sc = NextSubdivisionCandidate(mTQueue);    
	
		///////////////////
		//-- subdivide leaf node

		ApplySubdivisionCandidate(sc, mTQueue, repairQueue);
				
		// we use objects for evaluating vsp tree construction until 
		// a certain depth once a certain depth existiert ...
		if (StartObjectSpaceSubdivision())
		{
			mObjectSpaceSubdivisionType = mSavedObjectSpaceSubdivisionType;

			cout << "\nstarting object space subdivision after " 
				 << mVspTree->mVspStats.nodes << " (" << mMinStepsOfSameType << ") steps, mem=" 
				 << mHierarchyStats.mMemory / float(1024 * 1024) << " MB" << endl;

			SubdivisionCandidate *ospSc = PrepareObjectSpaceSubdivision(sampleRays, objects);
			
			cout << "reseting queue ... ";
			ResetQueue(mTQueue, mRecomputeSplitPlaneOnRepair);
			cout << "finished" << endl;

			mTQueue.Push(ospSc);
		}

		if (StartViewSpaceSubdivision())
		{
			mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;

			cout << "\nstarting view space subdivision at " 
				 << GetObjectSpaceSubdivisionLeaves() << " (" 
				 << mMinStepsOfSameType << ") , mem=" 
				 << mHierarchyStats.mMemory / float(1024 * 1024) << " MB" << endl;

			SubdivisionCandidate *vspSc = PrepareViewSpaceSubdivision(sampleRays, objects);

			cout << "reseting queue ... ";
			ResetQueue(mTQueue, mRecomputeSplitPlaneOnRepair);
			cout << "finished" << endl;

			// push view space candidate			
			mTQueue.Push(vspSc);
		}

		DEL_PTR(sc);
	}
}


void HierarchyManager::RunConstruction(const bool repairQueue)
{
	// main loop
	while (!FinishedConstruction())
	{
		SubdivisionCandidate *sc = NextSubdivisionCandidate(mTQueue);    
		
		////////
		//-- subdivide leaf node of either type
        ApplySubdivisionCandidate(sc, mTQueue, repairQueue);
		
		DEL_PTR(sc);
	}
}


int HierarchyManager::RunConstruction(SplitQueue &splitQueue,
									  SubdivisionCandidateContainer &dirtyCandidates,
									  SubdivisionCandidate *oldCandidate,
									  const int minSteps,
									  const int maxSteps)
{
	if (minSteps >= maxSteps)
		cout << "error!! " << minSteps << " equal or larger maxSteps" << endl;

	int steps = 0;
	SubdivisionCandidate::NewMail();

	// main loop
	while (!splitQueue.Empty())
	{
		const float priority = splitQueue.Top()->GetPriority();
		const float threshold = oldCandidate ? oldCandidate->GetPriority() : 1e20f;

		// minimum slope reached
		if ((steps >= maxSteps) || ((priority < threshold) && !(steps < minSteps)))
		{
			cout << "\nbreaking on " << priority << " smaller than " << threshold << endl;
			break;
		}
		
		////////
		//-- subdivide leaf node of either type

		SubdivisionCandidate *sc = NextSubdivisionCandidate(splitQueue); 
			
		const bool repairQueue = false;
		const bool success = ApplySubdivisionCandidate(sc, splitQueue, repairQueue);

		if (success)
		{
			sc->CollectDirtyCandidates(dirtyCandidates, true);
			++ steps;
		}

		DEL_PTR(sc);
	}

	return steps;
}


SubdivisionCandidate *HierarchyManager::ResetObjectSpaceSubdivision(const VssRayContainer &sampleRays, 
																	const ObjectContainer &objects)
{	
	SubdivisionCandidate *firstCandidate;

	// object space partition constructed => reconstruct
	switch (mObjectSpaceSubdivisionType)
	{
	case BV_BASED_OBJ_SUBDIV:
		{
			cout << "\nreseting bv hierarchy" << endl;
			Debug << "old bv hierarchy:\n " << mBvHierarchy->mBvhStats << endl;
				
			// rather use this: remove previous nodes and add the two new ones
			//mHierarchyStats.mNodes -= mBvHierarchy->mBvhStats.nodes + 1;
			mHierarchyStats.mNodes = mVspTree->mVspStats.nodes;
			
			// create root
			mBvHierarchy->Initialise(objects);
	
			firstCandidate = mBvHierarchy->Reset(sampleRays, objects);

			mHierarchyStats.mTotalCost = mBvHierarchy->mTotalCost;
			
			//mHierarchyStats.mPvsEntries -= mBvHierarchy->mPvsEntries + 1;
			mHierarchyStats.mPvsEntries = mBvHierarchy->CountViewCells(objects);

			mHierarchyStats.mMemory = 
				(float)mHierarchyStats.mPvsEntries * ObjectPvs::GetEntrySizeByte();

			mHierarchyStats.mRenderCostDecrease = 0;

			// evaluate stats before first subdivision
			EvalSubdivisionStats();
			cout << "finished bv hierarchy preparation" << endl;
		}
		break;

	case KD_BASED_OBJ_SUBDIV:
		// TODO
	default:
		firstCandidate = NULL;
		break;
	}

	return firstCandidate;
}


SubdivisionCandidate *HierarchyManager::ResetViewSpaceSubdivision(const VssRayContainer &sampleRays, 
																  const ObjectContainer &objects,
																  AxisAlignedBox3 *forcedViewSpace)
{
	ViewCellsManager *vm = mVspTree->mViewCellsManager;

	// HACK: rather not destroy vsp tree
	DEL_PTR(mVspTree);
	mVspTree = new VspTree();

	mVspTree->mHierarchyManager = this;
	mVspTree->mViewCellsManager = vm;

	mVspTree->Initialise(sampleRays, forcedViewSpace);
	
	//-- reset stats
    mHierarchyStats.mNodes = GetObjectSpaceSubdivisionNodes();//-mVspTree->mVspStats.nodes + 1;
	
	SubdivisionCandidate *vsc = PrepareViewSpaceSubdivision(sampleRays, objects);
	
	mHierarchyStats.mPvsEntries = mVspTree->mPvsEntries;
	mHierarchyStats.mRenderCostDecrease = 0;

	mHierarchyStats.mMemory = (float)mHierarchyStats.mPvsEntries * ObjectPvs::GetEntrySizeByte();

	// evaluate new stats before first subdivsiion
	EvalSubdivisionStats();

	return vsc;
}


void HierarchyManager::ConstructMultiLevel(const VssRayContainer &sampleRays,											 
										   const ObjectContainer &objects,
										   AxisAlignedBox3 *forcedViewSpace)
{
	mHierarchyStats.Reset();
	mHierarchyStats.Start();
	mHierarchyStats.mNodes = 2;
	
	mHierarchyStats.mTotalCost = (float)objects.size();
	Debug << "setting total cost to " << mHierarchyStats.mTotalCost << endl;

	const long startTime = GetTime();
	cout << "Constructing view space / object space tree ... \n";
	
	// initialise view / object space
	mVspTree->Initialise(sampleRays, forcedViewSpace);
	InitialiseObjectSpaceSubdivision(objects);

	// use sah for evaluating osp tree construction 
	// in the first iteration of the subdivision

	mSavedViewSpaceSubdivisionType = mViewSpaceSubdivisionType;
	mViewSpaceSubdivisionType = NO_VIEWSPACE_SUBDIV;

	SubdivisionCandidate *osc = 
		PrepareObjectSpaceSubdivision(sampleRays, objects);
	mTQueue.Push(osc);

	//////////////////////////


	const int limit = mNumMultiLevels;
	int i = 0;

	// This method subdivides view space / object space 
	// in order to converge to some optimal cost for this partition
	// start with object space partiton
	// then optimizate view space partition for the current osp
	// and vice versa until iteration depth is reached.
	while (1)
	{
		char subdivisionStatsLog[100];
		sprintf(subdivisionStatsLog, "tests/i3d/subdivision-%04d.log", i);
		mSubdivisionStats.open(subdivisionStatsLog);

		// subdivide object space first
		osc = ResetObjectSpaceSubdivision(sampleRays, objects);
		mTQueue.Push(osc);

		// process object space candidates
		RunConstruction(false);

		// object space subdivision constructed
		mObjectSpaceSubdivisionType = mSavedObjectSpaceSubdivisionType;

		cout << "iteration " << i << " of " << limit << " finished" << endl;
		mSubdivisionStats.close();

		if ((i ++) >= limit)
			break;

		sprintf(subdivisionStatsLog, "tests/i3d/subdivision-%04d.log", i);
		mSubdivisionStats.open(subdivisionStatsLog);


		/////////////////
		// subdivide view space with respect to the objects

		SubdivisionCandidate *vspVc = 
			ResetViewSpaceSubdivision(sampleRays, objects, forcedViewSpace);
		mTQueue.Push(vspVc);

		// view space subdivision constructed
		mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
		
		// process view space candidates
		RunConstruction(false);

		cout << "iteration " << i << " of " << limit << " finished" << endl;
		mSubdivisionStats.close();

		if ((i ++) >= limit)
			break;
	}
	
	cout << "\nfinished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;

	mHierarchyStats.Stop();
	mVspTree->mVspStats.Stop();
	FinishObjectSpaceSubdivision(objects);
}


void HierarchyManager::OptimizeMultiLevel(const VssRayContainer &sampleRays,											 
										  const ObjectContainer &objects,
										  AxisAlignedBox3 *forcedViewSpace)
{
	const long startTime = GetTime();
	const int limit = mNumMultiLevels;

	// open up new subdivision
	mSubdivisionStats.close();

	int steps = 0;

	int maxViewSpaceLeaves = mVspTree->mVspStats.Leaves();
	int maxObjectSpaceLeaves;
	
	// set the number of leaves 'evaluated' from the previous methods
	// we go for the same numbers, but we try to optimize both subdivisions
	switch (mObjectSpaceSubdivisionType)
	{
	case BV_BASED_OBJ_SUBDIV:
		maxObjectSpaceLeaves = mBvHierarchy->mBvhStats.Leaves();
		break;
	case KD_BASED_OBJ_SUBDIV:
		maxObjectSpaceLeaves = mOspTree->mOspStats.Leaves();
	default:
		maxObjectSpaceLeaves = 0;
		break;
	}

	// This method subdivides view space / object space 
	// in order to converge to some optimal cost for this partition
	// start with object space partiton
	// then optimizate view space partition for the current osp
	// and vice versa until iteration depth is reached.
	while (1)
	{
		char subdivisionStatsLog[100];
		sprintf(subdivisionStatsLog, "tests/i3d/subdivision-%04d.log", steps);
		mSubdivisionStats.open(subdivisionStatsLog);

		// subdivide object space first
		SubdivisionCandidate *ospVc = 
			ResetObjectSpaceSubdivision(sampleRays, objects);
	
		// set the number of leaves 'evaluated' from the previous methods
		// we go for the same numbers, but we try to optimize both subdivisions
		mBvHierarchy->mTermMaxLeaves = maxObjectSpaceLeaves;
		mTQueue.Push(ospVc);

		// process object space candidates
		RunConstruction(false);

		cout << "iteration " << steps << " of " << limit << " finished" << endl;
		mSubdivisionStats.close();

		if ((++ steps) >= limit)
			break;

		sprintf(subdivisionStatsLog, "tests/i3d/subdivision-%04d.log", steps);
		mSubdivisionStats.open(subdivisionStatsLog);

		/////////////////
		// subdivide view space with respect to the objects

		SubdivisionCandidate *vspVc = 
			ResetViewSpaceSubdivision(sampleRays, objects, forcedViewSpace);

		mVspTree->mMaxViewCells = maxViewSpaceLeaves;
		mTQueue.Push(vspVc);

		// process view space candidates
		RunConstruction(false);

		cout << "iteration " << steps << " of " << limit << " finished" << endl;
		mSubdivisionStats.close();

		if ((++ steps) >= limit)
			break;
	}
	
	cout << "\nfinished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;

	mHierarchyStats.Stop();
	mVspTree->mVspStats.Stop();
	FinishObjectSpaceSubdivision(objects);
}



bool HierarchyManager::FinishedConstruction() const
{
	return mTQueue.Empty();
}


bool HierarchyManager::ObjectSpaceSubdivisionConstructed() const
{
	/*switch (mObjectSpaceSubdivisionType)
	{
	case KD_BASED_OBJ_SUBDIV:
		return mOspTree && mOspTree->GetRoot();
	case BV_BASED_OBJ_SUBDIV:
		return mBvHierarchy && mBvHierarchy->GetRoot();
	default:
		return false;
	}*/
	return mObjectSpaceSubdivisionType != NO_OBJ_SUBDIV;
}


bool HierarchyManager::ViewSpaceSubdivisionConstructed() const
{
	return mViewSpaceSubdivisionType != NO_VIEWSPACE_SUBDIV;
	//return mVspTree && mVspTree->GetRoot();
}


void HierarchyManager::CollectDirtyCandidates(const SubdivisionCandidateContainer &chosenCandidates, 
											  SubdivisionCandidateContainer &dirtyList)
{
	SubdivisionCandidateContainer::const_iterator sit, sit_end = chosenCandidates.end();
	SubdivisionCandidate::NewMail();

	for (sit = chosenCandidates.begin(); sit != sit_end; ++ sit)
	{
		(*sit)->CollectDirtyCandidates(dirtyList, true);
	}
}


int HierarchyManager::RepairQueue(const SubdivisionCandidateContainer &dirtyList,
								  SplitQueue &splitQueue,
								  const bool recomputeSplitPlaneOnRepair)
{
	// for each update of the view space partition:
	// the candidates from object space partition which
	// have been afected by the view space split (the kd split candidates
	// which saw the view cell which was split) must be reevaluated 
	// (maybe not locally, just reinsert them into the queue)
	//
	// vice versa for the view cells
	// for each update of the object space partition
	// reevaluate split candidate for view cells which saw the split kd cell
	// 
	// the priority queue update can be solved by implementing a binary heap
	// (explicit data structure, binary tree)
	// *) inserting and removal is efficient
	// *) search is not efficient => store queue position with each
	// split candidate

	int repaired = 0;

	// collect list of "dirty" candidates
	const long startTime = GetTime();
   	if (0) cout << "repairing " << (int)dirtyList.size() << " candidates ... ";

	const float prop = (float)mMaxRepairs / (float)dirtyList.size();

	///////////////////////////
	//-- reevaluate the dirty list

	SubdivisionCandidateContainer::const_iterator sit, sit_end = dirtyList.end();
	
	for (sit = dirtyList.begin(); sit != sit_end; ++ sit)
	{
		// only repair a certain number of candidates
		if ((mMaxRepairs < (int)dirtyList.size()) && (Random(1.0f) >= prop))
			continue;

		SubdivisionCandidate* sc = *sit;
		const float rcd = sc->GetRenderCostDecrease();
		
		// erase from queue
		splitQueue.Erase(sc);
		// reevaluate candidate
		sc->EvalCandidate(recomputeSplitPlaneOnRepair);
		 // reinsert
		splitQueue.Push(sc);
		
		++ repaired;
		cout << ".";

#ifdef GTP_DEBUG
		Debug << "candidate " << sc << " reevaluated\n" 
			  << "render cost decrease diff " <<  rcd - sc->GetRenderCostDecrease()
			  << " old: " << rcd << " new " << sc->GetRenderCostDecrease() << endl;
#endif	
	}

	const long endTime = GetTime();
	const Real timeDiff = TimeDiff(startTime, endTime);

	mHierarchyStats.mRepairTime += timeDiff;

	return repaired;
}


void HierarchyManager::ResetQueue(SplitQueue &splitQueue, const bool recomputeSplitPlane)
{
	SubdivisionCandidateContainer mCandidateBuffer;

	// remove from queue
	while (!splitQueue.Empty())
	{
		SubdivisionCandidate *candidate = NextSubdivisionCandidate(splitQueue);
		
		// reevaluate local split plane and priority
		candidate->EvalCandidate(recomputeSplitPlane);
		cout << ".";
		mCandidateBuffer.push_back(candidate);
	}

	// put back into queue
	SubdivisionCandidateContainer::const_iterator sit, sit_end = mCandidateBuffer.end();
    for (sit = mCandidateBuffer.begin(); sit != sit_end; ++ sit)
	{
		splitQueue.Push(*sit);
	}
}


void HierarchyManager::ExportObjectSpaceHierarchy(OUT_STREAM &stream)
{
	// the type of the view cells hierarchy
	switch (mObjectSpaceSubdivisionType)
	{
	case KD_BASED_OBJ_SUBDIV:
		stream << "<ObjectSpaceHierarchy type=\"osp\">" << endl;
		mOspTree->Export(stream);
		stream << endl << "</ObjectSpaceHierarchy>" << endl;
		break;		
	case BV_BASED_OBJ_SUBDIV:
		stream << "<ObjectSpaceHierarchy type=\"bvh\">" << endl;
		mBvHierarchy->Export(stream);
		stream << endl << "</ObjectSpaceHierarchy>" << endl;
		break;
	}
}


bool HierarchyManager::AddSampleToPvs(Intersectable *obj, 
									  const Vector3 &hitPoint,
									  ViewCell *vc,
									  const float pdf, 
									  float &contribution) const
{
	if (!obj) return false;

	switch (mObjectSpaceSubdivisionType)
	{
	case NO_OBJ_SUBDIV:
		{
			// potentially visible objects
			return vc->AddPvsSample(obj, pdf, contribution);
		}
	case KD_BASED_OBJ_SUBDIV:
		{
			// potentially visible kd cells
			KdLeaf *leaf = mOspTree->GetLeaf(hitPoint/*ray->mOriginNode*/);
			return mOspTree->AddLeafToPvs(leaf, vc, pdf, contribution);
		}
	case BV_BASED_OBJ_SUBDIV:
		{
			BvhLeaf *leaf = mBvHierarchy->GetLeaf(obj);
			BvhIntersectable *bvhObj = mBvHierarchy->GetOrCreateBvhIntersectable(leaf);
			
			return vc->AddPvsSample(bvhObj, pdf, contribution);
		}
	default:
		return false;
	}
}


void HierarchyManager::PrintHierarchyStatistics(ostream &stream) const
{
	stream << mHierarchyStats << endl;
	stream << "\nview space:" << endl << endl;
	stream << mVspTree->GetStatistics() << endl;
	stream << "\nobject space:" << endl << endl;

	switch (mObjectSpaceSubdivisionType)
	{
	case KD_BASED_OBJ_SUBDIV:
		{
			stream << mOspTree->GetStatistics() << endl;
			break;
		}
	case BV_BASED_OBJ_SUBDIV:
		{
			stream << mBvHierarchy->GetStatistics() << endl;
			break;
		}
	default:
		break;
	}
}


void HierarchyManager::ExportObjectSpaceHierarchy(Exporter *exporter,
												  const ObjectContainer &objects,
												  const AxisAlignedBox3 *bbox,
												  const bool exportBounds) const
{
	switch (mObjectSpaceSubdivisionType)
	{
	case KD_BASED_OBJ_SUBDIV:
		{
			ExportOspTree(exporter, objects);
			break;
		}
	case BV_BASED_OBJ_SUBDIV:
		{
			exporter->ExportBvHierarchy(*mBvHierarchy, 0, bbox, exportBounds);
			break;
		}
	default:
		break;
	}
}


void HierarchyManager::ExportOspTree(Exporter *exporter, 
									 const ObjectContainer &objects) const
{
	if (0) exporter->ExportGeometry(objects);
			
	exporter->SetWireframe();
	exporter->ExportOspTree(*mOspTree, 0);
}


Intersectable *HierarchyManager::GetIntersectable(Intersectable *obj,
												  const Vector3 &point) const
{
  
  if (!obj)
	return NULL;
  
  switch (mObjectSpaceSubdivisionType)
	{
	case HierarchyManager::KD_BASED_OBJ_SUBDIV:
	  {
		KdLeaf *leaf = mOspTree->GetLeaf(point, NULL);
		return mOspTree->GetOrCreateKdIntersectable(leaf);
	  }
	case HierarchyManager::BV_BASED_OBJ_SUBDIV:
	  {
		BvhLeaf *leaf = mBvHierarchy->GetLeaf(obj);
		return mBvHierarchy->GetOrCreateBvhIntersectable(leaf);
	  }
	default:
	  return obj;
	}
}

Intersectable *HierarchyManager::GetIntersectable(const VssRay &ray, 
												  const bool isTermination) const
{
  Intersectable *obj = NULL;
	Vector3 pt;
	KdNode *node;

	ray.GetSampleData(isTermination, pt, &obj, &node);
	
	if (!obj)
	  return NULL;

	switch (mObjectSpaceSubdivisionType)
	{
	case HierarchyManager::KD_BASED_OBJ_SUBDIV:
		{
		  KdLeaf *leaf = mOspTree->GetLeaf(pt, node);
			return mOspTree->GetOrCreateKdIntersectable(leaf);
		}
	case HierarchyManager::BV_BASED_OBJ_SUBDIV:
		{
			BvhLeaf *leaf = mBvHierarchy->GetLeaf(obj);
			return mBvHierarchy->GetOrCreateBvhIntersectable(leaf);
		}
	default:
	  break;
	}
	return obj;
}


void HierarchyStatistics::Print(ostream &app) const
{
	app << "=========== Hierarchy statistics ===============\n";

	app << setprecision(4);

	app << "#N_CTIME  ( Construction time [s] )\n" << Time() << " \n";
	
	app << "#N_RTIME  ( Repair time [s] )\n" << mRepairTime * 1e-3f << " \n";

	app << "#N_NODES ( Number of nodes )\n" << mNodes << "\n";

	app << "#N_INTERIORS ( Number of interior nodes )\n" << Interior() << "\n";

	app << "#N_LEAVES ( Number of leaves )\n" << Leaves() << "\n";

	app << "#N_PMAXDEPTH ( Maximal reached depth )\n" << mMaxDepth << endl;

	app << "#N_GLOBALCOSTMISSES ( Global cost misses )\n" << mGlobalCostMisses << endl;
	
	app << "========== END OF Hierarchy statistics ==========\n";
}


static void RemoveRayRefs(const ObjectContainer &objects)
{
	ObjectContainer::const_iterator oit, oit_end = objects.end();
	for (oit = objects.begin(); oit != oit_end; ++ oit)
	{
		(*oit)->DelRayRefs();
	}
}


void HierarchyManager::FinishObjectSpaceSubdivision(const ObjectContainer &objects, 
													const bool removeRayRefs) const
{
	switch (mObjectSpaceSubdivisionType)
	{
	case KD_BASED_OBJ_SUBDIV:
		{
			mOspTree->mOspStats.Stop();
			break;
		}
	case BV_BASED_OBJ_SUBDIV:
		{
			mBvHierarchy->mBvhStats.Stop();
			if (removeRayRefs)
				RemoveRayRefs(objects);
			break;
		}
	default:
		break;
	}
}


void HierarchyManager::ExportBoundingBoxes(OUT_STREAM &stream, const ObjectContainer &objects)
{
	stream << "<BoundingBoxes>" << endl;
	    
	if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
	{
		KdIntersectableMap::const_iterator kit, kit_end = mOspTree->mKdIntersectables.end();

		int id = 0;
		for (kit = mOspTree->mKdIntersectables.begin(); kit != kit_end; ++ kit, ++ id)
		{
			Intersectable *obj = (*kit).second;
			const AxisAlignedBox3 box = obj->GetBox();
		
			obj->SetId(id);

			stream << "<BoundingBox" << " id=\"" << id << "\""
				   << " min=\"" << box.Min().x << " " << box.Min().y << " " << box.Min().z << "\""
				   << " max=\"" << box.Max().x << " " << box.Max().y << " " << box.Max().z << "\" />" << endl;
		}
	}
	else
	{
		ObjectContainer::const_iterator oit, oit_end = objects.end();

		for (oit = objects.begin(); oit != oit_end; ++ oit)
		{
			const AxisAlignedBox3 box = (*oit)->GetBox();
		
			stream << "<BoundingBox" << " id=\"" << (*oit)->GetId() << "\""
				   << " min=\"" << box.Min().x << " " << box.Min().y << " " << box.Min().z << "\""
				   << " max=\"" << box.Max().x << " " << box.Max().y << " " << box.Max().z << "\" />" << endl;
		}
	}
		
	stream << "</BoundingBoxes>" << endl;
}


class HierarchyNodeWrapper;


template <typename T> class myless
{
public:
	bool operator() (T v1, T v2) const
	{
		return (v1->GetMergeCost() < v2->GetMergeCost());
	}
};


typedef priority_queue<HierarchyNodeWrapper *, vector<HierarchyNodeWrapper *>, 
					   myless<vector<HierarchyNodeWrapper *>::value_type> > HierarchyNodeQueue;

class HierarchyNodeWrapper
{
public:
	enum {VSP_NODE, BVH_NODE, VIEW_CELL};

	virtual float GetMergeCost() const = 0;
	virtual int Type() const  = 0;
	virtual bool IsLeaf() const = 0;

	virtual void PushChildren(HierarchyNodeQueue &tQueue) = 0;
};


class VspNodeWrapper: public HierarchyNodeWrapper
{
public:
	VspNodeWrapper(VspNode *node): mNode(node) {}

	int Type() const { return VSP_NODE; }

	float GetMergeCost() const { return (float) -mNode->mTimeStamp; };

	bool IsLeaf() const { return mNode->IsLeaf(); }

	void PushChildren(HierarchyNodeQueue &tQueue)
	{
		if (!mNode->IsLeaf())
		{
			VspInterior *interior = dynamic_cast<VspInterior *>(mNode);

			tQueue.push(new VspNodeWrapper(interior->GetFront()));
			tQueue.push(new VspNodeWrapper(interior->GetBack()));
		}
	}

	VspNode *mNode;
};


class BvhNodeWrapper: public HierarchyNodeWrapper
{
public:
	BvhNodeWrapper(BvhNode *node): mNode(node) {}
	
	int Type()  const { return BVH_NODE; }

	float GetMergeCost() const { return (float)-mNode->mTimeStamp; };

	bool IsLeaf() const { return mNode->IsLeaf(); }

	void PushChildren(HierarchyNodeQueue &tQueue)
	{
		if (!mNode->IsLeaf())
		{
			BvhInterior *interior = dynamic_cast<BvhInterior *>(mNode);

			tQueue.push(new BvhNodeWrapper(interior->GetFront()));
			tQueue.push(new BvhNodeWrapper(interior->GetBack()));
		}
	}

	BvhNode *mNode;
};


class ViewCellWrapper: public HierarchyNodeWrapper
{
public:

	ViewCellWrapper(ViewCell *vc): mViewCell(vc) {}
	
	int Type()  const { return VIEW_CELL; }

	float GetMergeCost() const { return mViewCell->GetMergeCost(); };

	bool IsLeaf() const { return mViewCell->IsLeaf(); }

	void PushChildren(HierarchyNodeQueue &tQueue)
	{
		if (!mViewCell->IsLeaf())
		{
			ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(mViewCell);

			ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();

			for (it = interior->mChildren.begin(); it != it_end; ++ it)
			{
				tQueue.push(new ViewCellWrapper(*it));
			}
		}
	}

	ViewCell *mViewCell;
};


void HierarchyManager::CollectBestSet(const int maxSplits,
									  const float maxMemoryCost,
									  ViewCellContainer &viewCells,
									  vector<BvhNode *> &bvhNodes)
{
	HierarchyNodeQueue tqueue;
	//tqueue.push(new VspNodeWrapper(mVspTree->GetRoot()));
	tqueue.push(new ViewCellWrapper(mVspTree->mViewCellsTree->GetRoot()));
	tqueue.push(new BvhNodeWrapper(mBvHierarchy->GetRoot()));
	
	float memCost = 0;

	while (!tqueue.empty())
	{
		HierarchyNodeWrapper *nodeWrapper = tqueue.top();
		tqueue.pop();
		//cout << "priority: " << nodeWrapper->GetMergeCost() << endl;
		// save the view cells if it is a leaf or if enough view cells have already been traversed
		// because of the priority queue, this will be the optimal set of v
		if (nodeWrapper->IsLeaf() || 
			((viewCells.size() + bvhNodes.size() + tqueue.size() + 1) >= maxSplits) ||
			(memCost > maxMemoryCost)
			)
		{
			if (nodeWrapper->Type() == HierarchyNodeWrapper::VIEW_CELL)
			{
				//cout << "1";
				ViewCellWrapper *viewCellWrapper = dynamic_cast<ViewCellWrapper *>(nodeWrapper);
				viewCells.push_back(viewCellWrapper->mViewCell);
			}
			else
			{
				//cout << "0";
				BvhNodeWrapper *bvhNodeWrapper = dynamic_cast<BvhNodeWrapper *>(nodeWrapper);
				bvhNodes.push_back(bvhNodeWrapper->mNode);
			}
		}
		else 
		{	
			nodeWrapper->PushChildren(tqueue);
		}

		delete nodeWrapper;
	}
}


void HierarchyManager::ComputePvs(const ObjectPvs &pvs, float &rc, int &pvsEntries)
{
	BvhNode::NewMail();

	ObjectPvsIterator pit = pvs.GetIterator();

	while (pit.HasMoreEntries())
	{
		ObjectPvsEntry entry = pit.Next();

		BvhIntersectable *intersect = dynamic_cast<BvhIntersectable *>(entry.mObject);

		BvhLeaf *leaf = intersect->GetItem();
		BvhNode *activeNode = leaf->GetActiveNode();

		if (!activeNode->Mailed())
		{
			activeNode->Mail();

			ObjectContainer objects;
			activeNode->CollectObjects(objects);

			++ pvsEntries;
			rc += mBvHierarchy->EvalAbsCost(objects);
			//cout << " pvs: " << mBvHierarchy->EvalAbsCost(leaf->mObjects);
		}
	}
}


// TODO matt: implement this function for different storing methods
void HierarchyManager::GetPvsIncrementally(ViewCell *vc, ObjectPvs &pvs) const
{
	////////////////
	//-- pvs is not stored with the interiors => reconstruct
	ViewCell *root = vc;
	
	// add pvs from leaves
	stack<ViewCell *> tstack;
	tstack.push(vc);

	while (!tstack.empty())
	{
		vc = tstack.top();
		tstack.pop();
	
		// add newly found pvs to merged pvs: break here even for interior
		if (!vc->GetPvs().Empty())
		{
			pvs.MergeInPlace(vc->GetPvs());
		}
		else if (!vc->IsLeaf()) // interior cells: go down to leaf level
		{
			ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
			ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();

			for (it = interior->mChildren.begin(); it != it_end; ++ it)
			{
				tstack.push(*it);
			}		
		}
	}
}

int HierarchyManager::ExtractStatistics(const int maxSplits,
										const float maxMemoryCost,
										float &renderCost,
										float &memory,
										int &pvsEntries,
										int &viewSpaceSplits,
										int &objectSpaceSplits,
										const bool useFilter)
{
	ViewCellContainer viewCells;
	vector<BvhNode *> bvhNodes;

	// collect best set of view cells for this #splits
    CollectBestSet(maxSplits, maxMemoryCost, viewCells, bvhNodes);
	//cout << "here5 " << bvhNodes.size() << endl;
	vector<BvhNode *>::const_iterator bit, bit_end = bvhNodes.end();
	
	// set new nodes to be active
	for (bit = bvhNodes.begin(); bit != bit_end; ++ bit)
	{
		mBvHierarchy->SetActive(*bit);
	}

	ViewCellContainer::const_iterator vit, vit_end = viewCells.end();

	pvsEntries = 0;
	renderCost = 0.0f;

	ViewCell::NewMail();

	for (vit = viewCells.begin(); vit != vit_end; ++ vit)
	{
		ViewCell *vc = *vit;

		float rc = 0;
        ObjectPvs pvs;
		mVspTree->mViewCellsTree->GetPvs(vc, pvs);

		vc->SetPvs(pvs);

		vc->Mail();

		if (useFilter)
		{
			ObjectPvs filteredPvs;
			mVspTree->mViewCellsManager->ApplyFilter2(vc, false, 1.0f, filteredPvs);
			ComputePvs(filteredPvs, rc, pvsEntries);
		}
		else
		{
			ComputePvs(pvs, rc, pvsEntries);
		}

		rc *= vc->GetVolume();
		renderCost += rc;
	}

	renderCost /= mVspTree->mViewCellsManager->GetViewSpaceBox().GetVolume();
	memory = pvsEntries * ObjectPvs::GetEntrySize();

	viewSpaceSplits = (int)viewCells.size();
	objectSpaceSplits = (int)bvhNodes.size();
	//cout << "viewCells: " << (int)viewCells.size() << " nodes: " << (int)bvhNodes.size() << " rc: " << renderCost << " entries: " << pvsEntries << endl;

	// delete old "base" view cells if they are not leaves
	ViewCellContainer::const_iterator oit, oit_end = mOldViewCells.end();

	for (oit = mOldViewCells.begin(); oit != oit_end; ++ oit)
	{
		if (!(*oit)->Mailed() && !(*oit)->IsLeaf())
		{
			(*oit)->GetPvs().Clear();
		}
	}

	mOldViewCells = viewCells;

	return viewCells.size() + bvhNodes.size();
}


void HierarchyManager::ExportStats(ofstream &stats, 
								   SplitQueue &tQueue, 
								   const ObjectContainer &objects)
{
	HierarchySubdivisionStats subStats;
	subStats.Reset();

	/////////////
	//-- initial situation

	subStats.mNumSplits = 0;
	subStats.mTotalRenderCost = (float)objects.size();
	subStats.mEntriesInPvs = 1;
	subStats.mMemoryCost = (float)ObjectPvs::GetEntrySize();
	subStats.mFullMemory = subStats.mMemoryCost;
	subStats.mViewSpaceSplits = 0;
	subStats.mObjectSpaceSplits = 0;
	subStats.mRenderCostDecrease = 0;
	subStats.Print(stats);

	cout << "exporting vsposp stats ... " << endl;

	//-- go through tree in the order of render cost decrease
	//-- which is the same order as the view cells were merged
	//-- or the reverse order of subdivision for subdivision-only 
	//-- view cell hierarchies.
	
	while (!tQueue.Empty())
	{
		SubdivisionCandidate *nextCandidate = NextSubdivisionCandidate(tQueue);
		bool isLeaf;
		int timeStamp;
		float rcDecr; 
		int entriesIncr; 

        if (nextCandidate->Type() == SubdivisionCandidate::VIEW_SPACE)
		{
			timeStamp = (int)-nextCandidate->GetPriority();

			VspNode *newNode = mVspTree->SubdivideAndCopy(tQueue, nextCandidate);
			VspNode *oldNode = (VspNode *)nextCandidate->mEvaluationHack;
			
			isLeaf = newNode->IsLeaf();
			//subStats.mRenderCostDecrease = oldNode->mRenderCostDecr;
			//entriesIncr = oldNode->mPvsEntriesIncr;
		}
		else
		{
			timeStamp = (int)-nextCandidate->GetPriority();
			
			BvhNode *newNode = mBvHierarchy->SubdivideAndCopy(tQueue, nextCandidate);
			BvhNode *oldNode = (BvhNode *)nextCandidate->mEvaluationHack;
			
			isLeaf = newNode->IsLeaf();
			//subStats.mRenderCostDecrease = oldNode->mRenderCostDecr;
			//entriesIncr = oldNode->mPvsEntriesIncr;
		}		
				
		if (!isLeaf)
		{
			subStats.mTotalRenderCost -= subStats.mRenderCostDecrease;
			//subStats.mEntriesInPvs += entriesIncr;

			if (nextCandidate->Type() == SubdivisionCandidate::VIEW_SPACE)
			{
				++ subStats.mViewSpaceSplits;
				cout << "v";
				//cout << "vsp t: " << timeStamp << " rc: " << rcDecr << " pvs: " << entriesIncr << endl;
			}
			else
			{
				++ subStats.mObjectSpaceSplits;
				cout << "o";
				//"osp t: " << timeStamp << " rc: " << rcDecr << " pvs: " << entriesIncr << endl;
			}

			++ subStats.mNumSplits;

			if ((subStats.mNumSplits % 500) == 499)
				cout << subStats.mNumSplits << " steps taken" << endl;

			subStats.mMemoryCost = (float)subStats.mEntriesInPvs * (float)ObjectPvs::GetEntrySize();
			subStats.mFullMemory = subStats.mMemoryCost;

			subStats.Print(stats);
			
		}

		DEL_PTR(nextCandidate);
	}

	stats.close();
}


void HierarchyManager::EvaluateSubdivision(const VssRayContainer &sampleRays,
										   const ObjectContainer &objects,
										   const string &filename)
{
	VspTree *oldVspTree = mVspTree;
	ViewCellsManager *vm = mVspTree->mViewCellsManager;
	BvHierarchy *oldHierarchy = mBvHierarchy;

	mBvHierarchy = new BvHierarchy();
	mBvHierarchy->mHierarchyManager = this;
	mBvHierarchy->mViewCellsManager = vm;

	mVspTree = new VspTree();
	mVspTree->mHierarchyManager = this;
	mVspTree->mViewCellsManager = vm;

	// create first nodes
	mVspTree->Initialise(sampleRays, &oldVspTree->mBoundingBox);
	InitialiseObjectSpaceSubdivision(objects);

	const long startTime = GetTime();
	cout << "Constructing evaluation hierarchies ... \n";
	
	ofstream stats;
	stats.open(filename.c_str());
	SplitQueue tQueue;

	BvhNode *oldBvhRoot = oldHierarchy->GetRoot();
	VspNode *oldVspRoot = oldVspTree->GetRoot();

	RayInfoContainer *viewSpaceRays = new RayInfoContainer();
	
	SubdivisionCandidate *firstVsp = mVspTree->PrepareConstruction(sampleRays, *viewSpaceRays);
	SubdivisionCandidate *firstBvh = mBvHierarchy->PrepareConstruction(sampleRays, objects);

    firstVsp->mEvaluationHack = oldVspRoot;
	firstBvh->mEvaluationHack = oldBvhRoot;

	firstVsp->SetPriority((float)-oldVspRoot->mTimeStamp);
	firstBvh->SetPriority((float)-oldBvhRoot->mTimeStamp);

	tQueue.Push(firstVsp);
	tQueue.Push(firstBvh);

	ExportStats(stats, tQueue, objects);

	cout << "\nfinished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
	RemoveRayRefs(objects);

	// view cells needed only for evaluation
	ViewCellContainer viewCells;
	mVspTree->CollectViewCells(viewCells, false);
	
	// helper trees can be destroyed
	DEL_PTR(mVspTree);
	DEL_PTR(mBvHierarchy);

	CLEAR_CONTAINER(viewCells);

	// reset hierarchies
	mVspTree = oldVspTree;
	mBvHierarchy = oldHierarchy;

	// reinstall old bv refs
	vector<BvhLeaf *> leaves;
	mBvHierarchy->CollectLeaves(mBvHierarchy->GetRoot(), leaves);
	vector<BvhLeaf *>::const_iterator bit, bit_end = leaves.end();

	for (bit = leaves.begin(); bit != bit_end; ++ bit)
	{
		mBvHierarchy->AssociateObjectsWithLeaf(*bit);
	}
}


void HierarchyManager::EvaluateSubdivision2(ofstream &splitsStats,
											const int splitsStepSize,
											const bool useFilter)
{
	vector<HierarchySubdivisionStats> subStatsContainer;

	int splits = (1 + mHierarchyStats.Leaves() / splitsStepSize) * splitsStepSize;
	cout << "splits: " << splits << endl;

	while (1)
	{
		HierarchySubdivisionStats subStats;
		subStats.mNumSplits = ExtractStatistics(splits, 
												99999.0, 
												subStats.mTotalRenderCost, 
												subStats.mMemoryCost, 
												subStats.mEntriesInPvs,
												subStats.mViewSpaceSplits,
												subStats.mObjectSpaceSplits,
												useFilter);

		
		const float objectSpaceHierarchyMem = float(
											  subStats.mObjectSpaceSplits * sizeof(ObjectContainer)
											  //+ (subStats.mObjectSpaceSplits - 1) * sizeof(BvhInterior)
											  //+sizeof(BvHierarchy)
											  ) / float(1024 * 1024);

			
		const float viewSpaceHierarchyMem = float(
											subStats.mViewSpaceSplits * sizeof(ObjectPvs)
											//+ (subStats.mViewSpaceSplits - 1) * sizeof(VspInterior)
											+ sizeof(ObjectPvs)
											//+ sizeof(VspTree)
											)  / float(1024 * 1024);

		subStats.mFullMemory = subStats.mMemoryCost + objectSpaceHierarchyMem + viewSpaceHierarchyMem;
		
		subStatsContainer.push_back(subStats);
		
		if (splits == 0)
			break;

		splits -= splitsStepSize;

		cout << subStats.mNumSplits << " ";
	}

	vector<HierarchySubdivisionStats>::const_reverse_iterator hit, hit_end = subStatsContainer.rend();

	for (hit = subStatsContainer.rbegin(); hit != hit_end; ++ hit)
	{
		(*hit).Print(splitsStats);
	}

	// delete old "base" view cells: only pvss in the leaves are allowed
	ViewCellContainer::const_iterator oit, oit_end = mOldViewCells.end();
	for (oit = mOldViewCells.begin(); oit != oit_end; ++ oit)
	{
		if (!(*oit)->IsLeaf())
		{
			(*oit)->GetPvs().Clear();
		}
	}

	mOldViewCells.clear();

	cout << endl;
}


void HierarchyManager::CollectObjects(const AxisAlignedBox3 &box, ObjectContainer &objects)
{
	mBvHierarchy->CollectObjects(box, objects);
}

}