#include "ViewCell.h"
#include "Mesh.h"
#include "Intersectable.h"
#include "MeshKdTree.h"
#include "Triangle3.h"
#include "common.h"
#include "Environment.h"
#include "ViewCellsManager.h"
#include "Exporter.h"

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



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


typedef priority_queue<ViewCell *, vector<ViewCell *>, myless<vector<ViewCell *>::value_type> > TraversalQueue;

int ViewCell::sMailId = 21843194198;
int ViewCell::sReservedMailboxes = 1;

//int upperPvsLimit = 120;
//int lowerPvsLimit = 5;

float MergeCandidate::sRenderCostWeight = 0;


// pvs penalty can be different from pvs size
inline float EvalPvsPenalty(const int pvs, 
							const int lower,
							const int upper)
{
	// clamp to minmax values
	if (pvs < lower)
		return (float)lower;
	if (pvs > upper)
		return (float)upper;

	return (float)pvs;
}


int ComputeMergedPvsSize(const ObjectPvs &pvs1, const ObjectPvs &pvs2)
{
	int pvs = pvs1.GetSize();

	// compute new pvs size
	ObjectPvsMap::const_iterator it, it_end =  pvs1.mEntries.end();

	Intersectable::NewMail();

	for (it = pvs1.mEntries.begin(); it != it_end; ++ it)
	{
		(*it).first->Mail();
	}

	it_end = pvs2.mEntries.end();

	for (it = pvs2.mEntries.begin(); it != it_end; ++ it)
	{
		Intersectable *obj = (*it).first;
		if (!obj->Mailed())
			++ pvs;
	}

	return pvs;
}


ViewCell::ViewCell(): 
MeshInstance(NULL), 
mPiercingRays(0),
mArea(-1),
mVolume(-1),
mValid(true),
mParent(NULL),
mTimeStamp(0)
{
}

ViewCell::ViewCell(Mesh *mesh): 
MeshInstance(mesh), 
mPiercingRays(0),
mArea(-1),
mVolume(-1),
mValid(true),
mParent(NULL),
mTimeStamp(0)
{
}


const ObjectPvs &ViewCell::GetPvs() const
{
	return mPvs;
}

ObjectPvs &ViewCell::GetPvs()
{
	return mPvs;
}


int ViewCell::Type() const 
{ 
	return VIEW_CELL; 
}


float ViewCell::GetVolume() const
{
	return mVolume;
}


void ViewCell::SetVolume(float volume) 
{
	mVolume = volume;
}


void ViewCell::SetMesh(Mesh *mesh)
{
	mMesh = mesh;
}


void ViewCell::UpdateViewCellsStats(ViewCellsStatistics &vcStat)
{
	++ vcStat.viewCells;
		
	const int pvsSize = mPvs.GetSize();

	vcStat.pvs += pvsSize;

	if (pvsSize == 0)
		++ vcStat.emptyPvs;

	if (pvsSize > vcStat.maxPvs)
		vcStat.maxPvs = pvsSize;

	if (pvsSize < vcStat.minPvs)
		vcStat.minPvs = pvsSize;

	if (!mValid)
		++ vcStat.invalid;
}


float ViewCell::GetArea() const
{
	return mArea;
}


void ViewCell::SetArea(float area) 
{
	mArea = area;
}


void ViewCell::SetValid(const bool valid)
{
	mValid = valid;
}


bool ViewCell::GetValid() const
{
	return mValid;
}


/*bool ViewCell::IsLeaf() const
{
	return true;
}*/


void ViewCell::SetParent(ViewCellInterior *parent)
{
	mParent = parent;
}


bool ViewCell::IsRoot() const
{
	return !mParent;
}


ViewCellInterior *ViewCell::GetParent() const
{
	return mParent;
}


void ViewCell::SetTimeStamp(const int timeStamp)
{
	mTimeStamp = timeStamp;
}


int ViewCell::GetTimeStamp() const
{
	return mTimeStamp;
}



/************************************************************************/
/*                class ViewCellInterior implementation                 */
/************************************************************************/


ViewCellInterior::ViewCellInterior()
{
}


ViewCellInterior::~ViewCellInterior()
{
	ViewCellContainer::const_iterator it, it_end = mChildren.end();

	for (it = mChildren.begin(); it != it_end; ++ it)
		delete (*it);
}


ViewCellInterior::ViewCellInterior(Mesh *mesh): 
ViewCell(mesh)
{
}


bool ViewCellInterior::IsLeaf() const
{
	return false;
}


void ViewCellInterior::SetupChildLink(ViewCell *l)
{
    mChildren.push_back(l);
    l->mParent = this;
}



/************************************************************************/
/*                class ViewCellsStatistics implementation              */
/************************************************************************/




void ViewCellsStatistics::Print(ostream &app) const
{
	app << "=========== View Cells Statistics ===============\n";

	app << setprecision(4);

	//app << "#N_CTIME  ( Construction time [s] )\n" << Time() << " \n";

	app << "#N_OVERALLPVS ( objects in PVS )\n" << pvs << endl;

	app << "#N_PMAXPVS ( largest PVS )\n" << maxPvs << endl;

	app << "#N_PMINPVS ( smallest PVS )\n" << minPvs << endl;

	app << "#N_PAVGPVS ( average PVS )\n" << AvgPvs() << endl;

	app << "#N_PEMPTYPVS ( view cells with empty PVS )\n" << emptyPvs << endl;

	app << "#N_VIEWCELLS ( number of view cells)\n" << viewCells << endl;

	app << "#N_AVGLEAVES (average number of leaves per view cell )\n" << AvgLeaves() << endl;

	app << "#N_MAXLEAVES ( maximal number of leaves per view cell )\n" << maxLeaves << endl;
	
	app << "#N_INVALID ( number of invalid view cells )\n" << invalid << endl;

	app << "========== End of View Cells Statistics ==========\n";
}


/*************************************************************************/
/*                    class ViewCellsTree implementation                 */
/*************************************************************************/


ViewCellsTree::ViewCellsTree(ViewCellsManager *vcm):
mRoot(NULL),
mUseAreaForPvs(false),
mViewCellsManager(vcm)
{
	environment->GetBoolValue("ViewCells.Visualization.exportMergedViewCells", mExportMergedViewCells);
	environment->GetFloatValue("ViewCells.maxStaticMemory", mMaxMemory);

	//-- merge options
	environment->GetFloatValue("ViewCells.PostProcess.renderCostWeight", mRenderCostWeight);
	environment->GetIntValue("ViewCells.PostProcess.minViewCells", mMergeMinViewCells);
	environment->GetFloatValue("ViewCells.PostProcess.maxCostRatio", mMergeMaxCostRatio);
	

	Debug << "========= view cell tree options ================\n";
	Debug << "minimum view cells: " << mMergeMinViewCells << endl;
	Debug << "max cost ratio: " << mMergeMaxCostRatio << endl;
	Debug << "max memory: " << mMaxMemory << endl;

	MergeCandidate::sRenderCostWeight = mRenderCostWeight;

	mStats.open("mergeStats.log");
}


// return memory usage in MB
float ViewCellsTree::GetMemUsage() const
{
	return 0;
		/*(sizeof(ViewCellsTree) +
		 mBspStats.Leaves() * sizeof(BspLeaf) +
		 mBspStats.Interior() * sizeof(BspInterior) +
		 mBspStats.accumRays * sizeof(RayInfo)) / (1024.0f * 1024.0f);*/
}


int ViewCellsTree::GetSize(ViewCell *vc) const
{
	int vcSize = 0;

	stack<ViewCell *> tstack;

	tstack.push(vc);

	while (!tstack.empty())
	{
		ViewCell *vc = tstack.top();
		tstack.pop();

		if (vc->IsLeaf())
		{
			++ vcSize;
		}
		else
		{
			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);
			
		}
	}

	return vcSize;
}


void ViewCellsTree::CollectLeaves(ViewCell *vc, ViewCellContainer &leaves) const
{
	stack<ViewCell *> tstack;

	tstack.push(vc);

	while (!tstack.empty())
	{
		ViewCell *vc = tstack.top();
		tstack.pop();

		if (vc->IsLeaf())
		{
			leaves.push_back(vc);
		}
		else
		{
			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);
			
		}
	}
}


ViewCellsTree::~ViewCellsTree()
{
	DEL_PTR(mRoot);
}


int ViewCellsTree::ConstructMergeTree(const VssRayContainer &rays, 
									  const ObjectContainer &objects)
{
	mNumActiveViewCells = (int)mViewCellsManager->GetViewCells().size();

	float variance = 0;
	int totalPvs = 0;
	float totalCost = 0;

	//-- compute statistics values of initial view cells
	mViewCellsManager->EvaluateRenderStatistics(totalCost,
												mExpectedCost,
												mDeviation,
												variance,
												totalPvs,
												mAvgRenderCost);


	//-- fill merge queue
	vector<MergeCandidate> candidates;

	mViewCellsManager->CollectMergeCandidates(rays, candidates);
	while(!candidates.empty())
	{
		MergeCandidate mc = candidates.back();
		candidates.pop_back();
		EvalMergeCost(mc);
		mMergeQueue.push(mc);
	}

	Debug << "************************* merge ***********************************" << endl;  
	Debug << "deviation: " << mDeviation << endl;
	Debug << "avg render cost: " << mAvgRenderCost << endl;
	Debug << "expected cost: " <<mExpectedCost << endl;


	ViewCellsManager::PvsStatistics pvsStats;
	mViewCellsManager->GetPvsStatistics(pvsStats);

	static float expectedValue = pvsStats.avgPvs;
	
	// the current view cells are kept in this container
	// we start with the current view cells from the
	// view cell manager. They will change with
	// subsequent merges
	ViewCellContainer &activeViewCells = mViewCellsManager->GetViewCells();


	ViewCell::NewMail();

	MergeStatistics mergeStats;
	mergeStats.Start();
	
	long startTime = GetTime();

	mergeStats.collectTime = TimeDiff(startTime, GetTime());
	mergeStats.candidates = (int)mMergeQueue.size();
	startTime = GetTime();

	// frequency stats are updated
	const int statsOut = 100;

	// passes are needed for statistics, because we don't want to record
	// every merge
	int pass = 0;
	int mergedPerPass = 0;
	float realExpectedCost = mExpectedCost;
	float realAvgRenderCost = mAvgRenderCost;
	int realNumActiveViewCells = mNumActiveViewCells;
	
	// maximal ratio of old expected render cost to expected render
	// when the the render queue has to be reset.
	float avgCostMaxDeviation;
	int maxMergesPerPass;
	int numMergedViewCells = 0;

	environment->GetIntValue("ViewCells.PostProcess.maxMergesPerPass", maxMergesPerPass);
	environment->GetFloatValue("ViewCells.PostProcess.avgCostMaxDeviation", avgCostMaxDeviation);

	cout << "actual merge starts now ... " << endl;
	
	//ResetMergeQueue();

	//-- use priority queue to merge leaf pairs

	while (!mMergeQueue.empty())// && (realNumActiveViewCells > mMergeMinViewCells))
	{
		//-- reset merge queue if the ratio of current expected cost / real expected cost
		//   too small or after a given number of merges
		if ((mergedPerPass > maxMergesPerPass) ||
			(avgCostMaxDeviation > mAvgRenderCost / realAvgRenderCost))
		{
			Debug << "************ reset queue *****************\n"
				  << "ratios: " << avgCostMaxDeviation 
				  << " real avg render cost " << realAvgRenderCost << " average render cost " << mAvgRenderCost
				  << " merged per pass : " << mergedPerPass << " of maximal " << maxMergesPerPass << endl;

			Debug << "Values before reset: "  
				  << " erc: " << mExpectedCost 
				  << " avgrc: " << mAvgRenderCost
				  << " dev: " << mDeviation << endl;
	
			// adjust render cost
			++ pass;

			mergedPerPass = 0;
			mExpectedCost = realExpectedCost;
			mAvgRenderCost = realAvgRenderCost;
			mNumActiveViewCells = realNumActiveViewCells;
			
			const int numMergedViewCells = UpdateActiveViewCells(activeViewCells);
		
			// recompute priorities => reset render cost
		    ResetMergeQueue();

			
			Debug << "Values after reset: "  
				  << " erc: " << mExpectedCost 
				  << " avg: " << mAvgRenderCost 
				  << " dev: " << mDeviation << endl;

			if (mExportMergedViewCells)
			{
				ExportMergedViewCells(activeViewCells, objects, numMergedViewCells);
			}
		}

#ifdef _DEBUG
		Debug << "abs mergecost: " << mMergeQueue.top().GetMergeCost() << 
			  << " rel mergecost: " << mMergeQueue.top().GetRenderCost() / mExpectedCost << 
			  << " max ratio: " << mMergeMaxCostRatio << endl
			  << " expected value: " << realExpectedCost << endl;
#endif

	
		MergeCandidate mc = mMergeQueue.top();
		mMergeQueue.pop();
	
		// both view cells equal
		// NOTE: do I really still need this? probably cannot happen!!
		if (mc.mLeftViewCell == mc.mRightViewCell)
			continue;

		if (mc.IsValid())
		{
			ViewCell::NewMail();
						
			-- realNumActiveViewCells;
			++ mergeStats.merged;
			++ mergedPerPass;


			//-- update statistical values

			// total render cost and deviation has changed
			// real expected cost will be larger than expected cost used for the
			// cost heuristics, but cannot recompute costs on each increase of the 
			// expected cost

			totalCost += mc.GetRenderCost();
			mDeviation += mc.GetDeviationIncr();
						
			realExpectedCost = totalCost / (float)realNumActiveViewCells;
			
			const float currentMergeCost = mc.GetMergeCost();

			// merge the view cells of leaf1 and leaf2
			int pvsDiff;
			ViewCellInterior *mergedVc = 
				MergeViewCells(mc.mLeftViewCell, mc.mRightViewCell, pvsDiff);

			totalPvs += pvsDiff;

			// set timestamp
			mergedVc->SetTimeStamp(mergeStats.merged);

			realAvgRenderCost = (float)totalPvs / (float)realNumActiveViewCells;
#if VC_HISTORY
			if (mc.mLeftViewCell->IsSibling(mc.mRightViewCell))
				++ mergeStats.siblings;
#endif
			if (((mergeStats.merged % statsOut) == 0) || 
				(realNumActiveViewCells == mMergeMinViewCells))
			{
				cout << "merged " << mergeStats.merged << " view cells" << endl;

				mStats 
					<< "#Pass\n" << pass << endl
					<< "#Merged\n" << mergeStats.merged << endl 
					<< "#Viewcells\n" << realNumActiveViewCells << endl 
					<< "#CurrentCost\n" << currentMergeCost << endl
					<< "#RelativeCost\n" << currentMergeCost / mOverallCost << endl
					<< "#CurrentPvs\n" << mc.GetLeftViewCell()->GetPvs().GetSize() << endl
					<< "#MergedSiblings\n" << mergeStats.siblings << endl
					<< "#AvgTreeDist\n" << mergeStats.AvgTreeDist() << endl
					<< "#UsedExpectedCost\n" << mExpectedCost << endl
					<< "#RealExpectedCost\n" << realExpectedCost << endl
					<< "#RealAvgRenderCost\n" << realAvgRenderCost << endl
					<< "#AvgRenderCost\n" << mAvgRenderCost << endl
					<< "#expectedCostRatio\n" << mExpectedCost / realExpectedCost << endl
					<< "#Deviation\n" << mDeviation / (float)realNumActiveViewCells << endl
					<< "#TotalDeviation\n" << mDeviation<< endl;
			}
		}
		else
		{ 
			// merge candidate not valid, because one of the leaves was already
			// merged with another one => validate and reinsert into queue
			if (ValidateMergeCandidate(mc))
			{
				EvalMergeCost(mc);
				mMergeQueue.push(mc);
			}
		}
	}

	// adjust stats and reset queue one final time
	mExpectedCost = realExpectedCost;
	mAvgRenderCost = realAvgRenderCost;
	mNumActiveViewCells = realNumActiveViewCells;

	UpdateActiveViewCells(activeViewCells);
	ResetMergeQueue();

	// create a root node if the merge was not done till root level,
	// else take the single node as new root
	if ((int)activeViewCells.size() > 1)
	{
		Debug << "creating root of view cell hierarchy for " << (int)activeViewCells.size() << " view cells" << endl;
		for (int i = 0;  i < activeViewCells.size(); ++ i){
			Debug << "here233 " << activeViewCells[i]->GetParent() << endl;
			Debug << "here233 " << activeViewCells[i] << endl;
		}
		ViewCellInterior *root = mViewCellsManager->MergeViewCells(activeViewCells);

		root->SetTimeStamp(mergeStats.merged + 1);
		mRoot = root;
	}
	else if ((int)activeViewCells.size() == 1)
	{
		Debug << "setting root of the merge history" << endl;
		mRoot = activeViewCells[0];
	}

	// TODO delete because makes no sense here
	mergeStats.expectedRenderCost = realExpectedCost;
	mergeStats.deviation = mDeviation;

	// we want to optimize this heuristics
	mergeStats.heuristics = 
		mDeviation * (1.0f - mRenderCostWeight) + 
		mExpectedCost * mRenderCostWeight;

	mergeStats.mergeTime = TimeDiff(startTime, GetTime());
	mergeStats.Stop();

	Debug << mergeStats << endl << endl;


	//TODO: should return sample contributions?
	return mergeStats.merged;
}


ViewCell *ViewCellsTree::GetRoot()
{
	return mRoot;
}


void ViewCellsTree::ResetMergeQueue()
{
	cout << "reset merge queue ... ";
	
	vector<MergeCandidate> buf;
	buf.reserve(mMergeQueue.size());
			
	
	// store merge candidates in intermediate buffer
	while (!mMergeQueue.empty())
	{
		MergeCandidate mc = mMergeQueue.top();
		mMergeQueue.pop();
		
		// recalculate cost
		if (ValidateMergeCandidate(mc))
		{
			EvalMergeCost(mc);
			buf.push_back(mc);				
		}
	}

	vector<MergeCandidate>::const_iterator bit, bit_end = buf.end();

	// reinsert back into queue
	for (bit = buf.begin(); bit != bit_end; ++ bit)
	{      
		mMergeQueue.push(*bit);	
	}

	cout << "finished" << endl;
}


int ViewCellsTree::UpdateActiveViewCells(ViewCellContainer &viewCells)
{
	int numMergedViewCells = 0;

	Debug << "updating active vc: " << viewCells.size() << endl;
	// find all already merged view cells and remove them from view cells
		
	// sort out all view cells which are not active anymore, i.e., they
	// were already part of a merge
	int i = 0;

	ViewCell::NewMail();

	while (1)
	{
		// remove all merged view cells from end of the vector
		while (!viewCells.empty() && (viewCells.back()->GetParent()))
		{
			viewCells.pop_back();
		}

		// all merged view cells have been found
		if (i >= viewCells.size()) 
			break;

		// already merged view cell, put it to end of vector
		if (viewCells[i]->GetParent())
			swap(viewCells[i], viewCells.back());
		
		viewCells[i ++]->Mail();
	}


	// add new view cells to container only if they don't have been 
	// merged in the mean time
	ViewCellContainer::const_iterator ait, ait_end = mMergedViewCells.end();
	for (ait = mMergedViewCells.begin(); ait != ait_end; ++ ait)
	{
		ViewCell *vc = mMergedViewCells.back();
		if (!vc->GetParent() && !vc->Mailed())
		{
			vc->Mail();
			viewCells.push_back(vc);
			++ numMergedViewCells;
		}
	}

	mMergedViewCells.clear();

	// update standard deviation
	ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
	
	mDeviation = 0;

	for (vit = viewCells.begin(); vit != vit_end; ++ vit)
	{
		int lower = mViewCellsManager->GetMinPvsSize();
		int upper = mViewCellsManager->GetMaxPvsSize();
		float penalty = EvalPvsPenalty((*vit)->GetPvs().GetSize(), lower, upper);
		
		mDeviation += fabs(mAvgRenderCost - penalty);
	}

	mDeviation /= (float)viewCells.size();
	
	return numMergedViewCells;
}


void ViewCellsTree::ExportMergedViewCells(ViewCellContainer &viewCells, 
										  const ObjectContainer &objects,
										  const int numMergedViewCells)
{
	

	char s[64];

	sprintf(s, "merged_viewcells%07d.x3d", (int)viewCells.size());
	Exporter *exporter = Exporter::GetExporter(s);

	if (exporter)
	{
		cout << "exporting " << (int)viewCells.size() << " merged view cells ... ";
		exporter->ExportGeometry(objects);
		//Debug << "vc size " << (int)viewCells.size() << " merge queue size: " << (int)mMergeQueue.size() << endl;
		ViewCellContainer::const_iterator it, it_end = viewCells.end();

		int i = 0;
		for (it = viewCells.begin(); it != it_end; ++ it)
		{
			Material m;
			// assign special material to new view cells
			// new view cells are on the back of container
			if (i ++ >= (viewCells.size() - numMergedViewCells))
			{
				//m = RandomMaterial();
				m.mDiffuseColor.r = RandomValue(0.5f, 1.0f);
				m.mDiffuseColor.g = RandomValue(0.5f, 1.0f);
				m.mDiffuseColor.b = RandomValue(0.5f, 1.0f);
			}
			else
			{
				float col = RandomValue(0.1f, 0.4f);
				m.mDiffuseColor.r = col;
				m.mDiffuseColor.g = col;
				m.mDiffuseColor.b = col;
			}

			exporter->SetForcedMaterial(m);
			mViewCellsManager->ExportViewCellGeometry(exporter, *it);
		}
		delete exporter;
		cout << "finished" << endl;
	}
}


// TODO: should be done in view cells manager
ViewCellInterior *ViewCellsTree::MergeViewCells(ViewCell *l, ViewCell *r, int &pvsDiff) //const
{
	ViewCellInterior *vc = mViewCellsManager->MergeViewCells(l, r);

	// if merge was unsuccessful
	if (!vc) return NULL;

	// set new size of view cell
	if (mUseAreaForPvs)
		vc->SetArea(l->GetArea() + l->GetArea());
	else
		vc->SetVolume(r->GetVolume() + r->GetVolume());
	
	// important so other merge candidates sharing this view cell
	// are notified that the merge cost must be updated!!
	vc->Mail();

	const int pvs1 = l->GetPvs().GetSize();
	const int pvs2 = r->GetPvs().GetSize();


	// new view cells are stored in this vector
	mMergedViewCells.push_back(vc);

	pvsDiff = vc->GetPvs().GetSize() - pvs1 - pvs2;

	return vc;
}




int ViewCellsTree::RefineViewCells(const VssRayContainer &rays, const ObjectContainer &objects)
{
	Debug << "refining " << (int)mMergeQueue.size() << " candidates " << endl;
	
	// Use priority queue of remaining leaf pairs 
	// The candidates either share the same view cells or
	// are border leaves which share a boundary.
	// We test if they can be shuffled, i.e.,
	// either one leaf is made part of one view cell or the other
	// leaf is made part of the other view cell. It is tested if the
	// remaining view cells are "better" than the old ones.
	//
	// repeat the merging test numPasses times. For example, it could be
	// that a shuffle only makes sense if another pair was shuffled before.
	// Therefore we keep two queues and shift the merge candidates between
	// those two queues until numPasses is reached
	
	queue<MergeCandidate> queue1;
	queue<MergeCandidate> queue2;

	queue<MergeCandidate> *shuffleQueue = &queue1;
	queue<MergeCandidate> *backQueue = &queue2;

	while (!mMergeQueue.empty())
	{
		MergeCandidate mc = mMergeQueue.top();
		shuffleQueue->push(mc);
		mMergeQueue.pop();
	}

	const int numPasses = 5;
	int pass = 0;
	int passShuffled = 0;
	int shuffled = 0;
	int shuffledViewCells = 0;

	ViewCell::NewMail();
	
	do
	{
		passShuffled = 0;
		while (!shuffleQueue->empty())
		{
			MergeCandidate mc = shuffleQueue->front();
			shuffleQueue->pop();

			// both view cells equal or already shuffled
			if ((mc.GetLeftViewCell() == mc.GetRightViewCell()) || 
				(GetSize(mc.GetLeftViewCell()) == 1) || 
				(GetSize(mc.GetRightViewCell()) == 1))
			{			
				continue;
			}

			// candidate for shuffling
			const bool wasShuffled = 
				ShuffleLeaves(mc.GetLeftViewCell(), mc.GetRightViewCell());
		
			// shuffled or put into other queue for further refine
			if (wasShuffled)
			{
				++ passShuffled;

				if (!mc.GetLeftViewCell()->Mailed())
				{
					mc.GetLeftViewCell()->Mail();
					++ shuffledViewCells;
				}
				if (!mc.GetRightViewCell()->Mailed())
				{
					mc.GetRightViewCell()->Mail();
					++ shuffledViewCells;
				}
			}
			else
			{
				backQueue->push(mc);
			}
		}

		// now the back queue is the current shuffle queue
		swap(shuffleQueue, backQueue);
		shuffled += passShuffled;
		Debug << "shuffled in pass: " << passShuffled << endl;
	}
	while (((++ pass) < numPasses) && passShuffled);

	while (!shuffleQueue->empty())
	{
		shuffleQueue->pop();
	}

	return shuffledViewCells;
}




inline int AddedPvsSize(ObjectPvs pvs1, const ObjectPvs &pvs2)
{
	return pvs1.AddPvs(pvs2);
}


// recomputes pvs size minus pvs of leaf l
#if 0
inline int SubtractedPvsSize(BspViewCell *vc, BspLeaf *l, const ObjectPvs &pvs2)
{
	ObjectPvs pvs;
	vector<BspLeaf *>::const_iterator it, it_end = vc->mLeaves.end();
	for (it = vc->mLeaves.begin(); it != vc->mLeaves.end(); ++ it)
		if (*it != l)
			pvs.AddPvs(*(*it)->mPvs);
	return pvs.GetSize();
}
#endif


// computes pvs1 minus pvs2
inline int SubtractedPvsSize(ObjectPvs pvs1, const ObjectPvs &pvs2)
{
	return pvs1.SubtractPvs(pvs2);
}


float ViewCellsTree::EvalShuffleCost(ViewCell *leaf, 
									 ViewCell *vc1, 
									 ViewCell *vc2) const
{
	//const int pvs1 = SubtractedPvsSize(vc1, leaf, *leaf->mPvs);
	const int pvs1 = SubtractedPvsSize(vc1->GetPvs(), leaf->GetPvs());
	const int pvs2 = AddedPvsSize(vc2->GetPvs(), leaf->GetPvs());

	const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize();
	const int upperPvsLimit = mViewCellsManager->GetMaxPvsSize();

	const float pvsPenalty1 = 
		EvalPvsPenalty(pvs1, lowerPvsLimit, upperPvsLimit);

	const float pvsPenalty2 =
		EvalPvsPenalty(pvs2, lowerPvsLimit, upperPvsLimit);


	// don't shuffle leaves with pvs > max
	if (0 && (pvs1 + pvs2 > mViewCellsManager->GetMaxPvsSize()))
	{
		return 1e20f;
	}

	float p1, p2;

    if (mUseAreaForPvs)
	{
		p1 = vc1->GetArea() - leaf->GetArea();
		p2 = vc2->GetArea() + leaf->GetArea();
	}
	else
	{
		p1 = vc1->GetVolume() - leaf->GetVolume();
		p2 = vc2->GetVolume() + leaf->GetVolume();
	}

	const float renderCost1 = pvsPenalty1 * p1;
	const float renderCost2 = pvsPenalty2 * p2;

	float dev1, dev2;

	if (1)
	{
		dev1 = fabs(mAvgRenderCost - pvsPenalty1);
		dev2 = fabs(mAvgRenderCost - pvsPenalty2);
	}
	else
	{
		dev1 = fabs(mExpectedCost - renderCost1);
		dev2 = fabs(mExpectedCost - renderCost2);
	}
	
	return mRenderCostWeight * (renderCost1 + renderCost2) +
		  (1.0f - mRenderCostWeight) * (dev1 + dev2) / (float)mNumActiveViewCells;
}


void ViewCellsTree::ShuffleLeaf(ViewCell *leaf,
								ViewCell *vc1, 
								ViewCell *vc2) const
{
	// compute new pvs and area
	vc1->GetPvs().SubtractPvs(leaf->GetPvs());
	vc2->GetPvs().AddPvs(leaf->GetPvs());
	
	if (mUseAreaForPvs)
	{
		vc1->SetArea(vc1->GetArea() - leaf->GetArea());
		vc2->SetArea(vc2->GetArea() + leaf->GetArea());
	}
	else
	{
		vc1->SetVolume(vc1->GetVolume() - leaf->GetVolume());
		vc2->SetVolume(vc2->GetVolume() + leaf->GetVolume());
	}

	// TODO
#if VC_HISTORY
	/// add to second view cell
	vc2->mLeaves.push_back(leaf);

	// erase leaf from old view cell
	vector<BspLeaf *>::iterator it = vc1->mLeaves.begin();

	for (; *it != leaf; ++ it);
	vc1->mLeaves.erase(it);

	/*vc1->GetPvs().mEntries.clear();
	for (; it != vc1->mLeaves.end(); ++ it)
	{
		if (*it == leaf)
			vc1->mLeaves.erase(it);
		else
			vc1->GetPvs().AddPvs(*(*it)->mPvs);
	}*/

	leaf->SetViewCell(vc2); // finally change view cell
#endif
}


bool ViewCellsTree::ShuffleLeaves(ViewCell *l, ViewCell *r) const
{
	float cost1, cost2;

	//-- first test if shuffling would decrease cost
	cost1 = GetCostHeuristics(l);
	cost2 = GetCostHeuristics(r);

	const float oldCost = cost1 + cost2;
	
	float shuffledCost1 = Limits::Infinity;
	float shuffledCost2 = Limits::Infinity;

	// the view cell should not be empty after the shuffle
#if VC_HISTORY
	shuffledCost1 = EvalShuffleCost(l, vc1, vc2);
	/shuffledCost2 = EvalShuffleCost(r, vc2, vc1);

	// if cost of shuffle is less than old cost => shuffle
	if ((oldCost <= shuffledCost1) && (oldCost <= shuffledCost2))
		return false;
	
	
	if (shuffledCost1 < shuffledCost2)
	{
		ShuffleLeaf(leaf1, vc1, vc2);
		leaf1->Mail();
	}
	else
	{
		ShuffleLeaf(leaf2, vc2, vc1);
		leaf2->Mail();
	}
#endif
	return true;
}


float ViewCellsTree::GetVariance(ViewCell *vc) const
{
	const int upper = mViewCellsManager->GetMaxPvsSize();
	const int lower = mViewCellsManager->GetMinPvsSize();

	if (1)
	{
		const float penalty = EvalPvsPenalty(vc->GetPvs().GetSize(), lower, upper);
		return (mAvgRenderCost - penalty) * (mAvgRenderCost - penalty) / (float)mNumActiveViewCells;
	}

    const float leafCost = GetRenderCost(vc);
	return (mExpectedCost - leafCost) * (mExpectedCost - leafCost);
}


float ViewCellsTree::GetDeviation(ViewCell *vc) const
{
	const int upper = mViewCellsManager->GetMaxPvsSize();
	const int lower = mViewCellsManager->GetMinPvsSize();

	if (1)
	{
		const float penalty = EvalPvsPenalty(vc->GetPvs().GetSize(), lower, upper);
		return fabs(mAvgRenderCost - penalty) / (float)mNumActiveViewCells;
	}

    const float renderCost = GetRenderCost(vc);
	return fabs(mExpectedCost - renderCost);
}



float ViewCellsTree::GetRenderCost(ViewCell *vc) const
{
	if (mUseAreaForPvs)
		return vc->GetPvs().GetSize() * vc->GetArea();

	return vc->GetPvs().GetSize() * vc->GetVolume();
}


float ViewCellsTree::GetCostHeuristics(ViewCell *vc) const
{
	return GetRenderCost(vc) * mRenderCostWeight + 
		   GetDeviation(vc) * (1.0f - mRenderCostWeight);
}


bool ViewCellsTree::ValidateMergeCandidate(MergeCandidate &mc) const
{
	while (mc.mLeftViewCell->mParent)
	{
		mc.mLeftViewCell = mc.mLeftViewCell->mParent;
	}

	while (mc.mRightViewCell->mParent)
	{
		mc.mRightViewCell = mc.mRightViewCell->mParent;
	}

	return mc.mLeftViewCell != mc.mRightViewCell;
}


void ViewCellsTree::EvalMergeCost(MergeCandidate &mc) const
{
	//-- compute pvs difference
	const int newPvs = 
		ComputeMergedPvsSize(mc.mLeftViewCell->GetPvs(), 
							 mc.mRightViewCell->GetPvs());
			
	const float newPenalty = 
		EvalPvsPenalty(newPvs,
					   mViewCellsManager->GetMinPvsSize(),
					   mViewCellsManager->GetMaxPvsSize());

	ViewCell *vc1 = mc.mLeftViewCell;
	ViewCell *vc2 = mc.mRightViewCell;

	//-- compute ratio of old cost
	//   (i.e., added size of left and right view cell times pvs size)
	//   to new rendering cost (i.e, size of merged view cell times pvs size)
	const float oldCost = GetRenderCost(vc1) + GetRenderCost(vc2);

    const float newCost = mUseAreaForPvs ? 
		(float)newPenalty * (vc1->GetArea() + vc2->GetArea()) :
		(float)newPenalty * (vc1->GetVolume() + vc2->GetVolume());


	// strong penalty if pvs size too large
	if (0 && (newPvs > mViewCellsManager->GetMaxPvsSize()))
	{
		mc.mRenderCost = 1e20f;
	}
	else
	{
		mc.mRenderCost = (newCost - oldCost) / 
			mViewCellsManager->GetViewSpaceBox().GetVolume();
	}	
	

	//-- merge cost also takes deviation into account
	float newDev, oldDev;

	if (1)
		newDev = fabs(mAvgRenderCost - newPenalty) / (float)mNumActiveViewCells;
	else
		newDev = fabs(mExpectedCost - newCost) / (float)mNumActiveViewCells;
	
	oldDev = GetDeviation(vc1) + GetDeviation(vc2);

	// compute deviation increase
	mc.mDeviationIncr = newDev - oldDev;
	
	//Debug << "render cost: " << mc.mRenderCost * mRenderCostWeight << endl;
	//Debug << "standard deviation: " << mc.mDeviationIncr * mRenderCostWeight << endl;
}


void ViewCellsTree::CompressViewCellsPvs()
{
	stack<ViewCell *> tstack;
	
	while (!tstack.empty())
	{
		ViewCell *viewCell = tstack.top();
		tstack.pop();

		if (!viewCell->IsLeaf())
		{
		
			ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(viewCell);
			Debug << "compressing " << interior->GetPvs().GetSize() << endl;
			ComputeCommonPvs(interior);
			Debug << "compressed " << interior->GetPvs().GetSize() << endl;
		}
	}
}


void ViewCellsTree::CollectBestViewCellSet(ViewCellContainer &viewCells, 
										   const int numViewCells)
{
	TraversalQueue tqueue;
	tqueue.push(mRoot);
	
	while (!tqueue.empty())
	{
		ViewCell *vc = tqueue.top();
		
		// 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 (vc->IsLeaf() || ((viewCells.size() + tqueue.size()) >= numViewCells))
		{
			viewCells.push_back(vc);
		}
		else 
		{	
			ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);

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

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

		tqueue.pop();
	}
}
	

void ViewCellsTree::ComputeCommonPvs(ViewCellInterior *interior)
{
	Intersectable::NewMail();

	ViewCellContainer::const_iterator cit, cit_end = interior->mChildren.end();

	ObjectPvsMap::const_iterator oit;

	// mail all objects in the leaf sets
	for (cit = interior->mChildren.begin(); cit != cit_end; ++ cit)
	{
		ViewCell *vc = *cit;

		ObjectPvsMap::const_iterator oit_end = vc->GetPvs().mEntries.end();

		for (oit = vc->GetPvs().mEntries.begin(); oit != oit_end; ++ oit)
		{
			if (!(*oit).first->Mailed())
				(*oit).first->Mail();
			
			(*oit).first->IncMail();
		}
	}

	interior->GetPvs().mEntries.clear();
    cit_end = interior->mChildren.end();
	
	// only the objects which are present in all leaf pvs 
	// should remain in the parent pvs

	for (cit = interior->mChildren.begin(); cit != cit_end; ++ cit)
	{
		ViewCell *vc = *cit;

		ObjectPvsMap::const_iterator oit_end = vc->GetPvs().mEntries.end();

		for (oit = vc->GetPvs().mEntries.begin(); oit != oit_end; ++ oit)
		{
			if ((*oit).first->Mailed((int)interior->mChildren.size()))
			{	
				interior->GetPvs().AddSample((*oit).first, (*oit).second.mSumPdf);
				//(*oit)->remove();
			}
		}
	}

	// delete all the objects from the leaf sets which were moved
	// to parent pvs
	ObjectPvsMap::const_iterator oit_end = interior->GetPvs().mEntries.end();

	for (oit = interior->GetPvs().mEntries.begin(); oit != oit_end; ++ oit)
	{
		for (cit = interior->mChildren.begin(); cit != cit_end; ++ cit)
		{
			(*cit)->GetPvs().RemoveSample((*oit).first, Limits::Infinity);
		}
	}
}


/**************************************************************************/
/*                     MergeCandidate implementation                      */
/**************************************************************************/


MergeCandidate::MergeCandidate(ViewCell *l, ViewCell *r):
mRenderCost(0),
mDeviationIncr(0),
mLeftViewCell(l),
mRightViewCell(r)
{
	//EvalMergeCost();
}


void MergeCandidate::SetRightViewCell(ViewCell *v)
{
	mRightViewCell = v;
}


void MergeCandidate::SetLeftViewCell(ViewCell *v)
{
	mLeftViewCell = v;
}


ViewCell *MergeCandidate::GetRightViewCell() const
{
	return mRightViewCell;
}


ViewCell *MergeCandidate::GetLeftViewCell() const
{
	return mLeftViewCell;
}


ViewCell *MergeCandidate::GetInitialRightViewCell() const
{
	return mInitialRightViewCell;
}


ViewCell *MergeCandidate::GetInitialLeftViewCell() const
{
	return mInitialLeftViewCell;
}


bool MergeCandidate::IsValid() const
{
	return !(mLeftViewCell->mParent || mRightViewCell->mParent);
}


float MergeCandidate::GetRenderCost() const
{
	return mRenderCost;
}


float MergeCandidate::GetDeviationIncr() const
{
	return mDeviationIncr;
}


float MergeCandidate::GetMergeCost() const
{
	return mRenderCost * sRenderCostWeight + 
		   mDeviationIncr * (1.0f - sRenderCostWeight);
}


/************************************************************************/
/*                    MergeStatistics implementation                    */
/************************************************************************/


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

	app << setprecision(4);

	app << "#N_CTIME ( Overall time [s] )\n" << Time() << " \n";

	app << "#N_CCTIME ( Collect candidates time [s] )\n" << collectTime * 1e-3f << " \n";

	app << "#N_MTIME ( Merge time [s] )\n" << mergeTime * 1e-3f << " \n";

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

	app << "#N_CANDIDATES ( Number of merge candidates )\n" << candidates << "\n";

	app << "#N_MERGEDSIBLINGS ( Number of merged siblings )\n" << siblings << "\n";

	app << "#OVERALLCOST ( overall merge cost )\n" << overallCost << "\n";

	app << "#N_MERGEDNODES ( Number of merged nodes )\n" << merged << "\n";

	app << "#MAX_TREEDIST ( Maximal distance in tree of merged leaves )\n" << maxTreeDist << "\n";

	app << "#AVG_TREEDIST ( Average distance in tree of merged leaves )\n" << AvgTreeDist() << "\n";

	app << "#EXPECTEDCOST ( expected render cost )\n" << expectedRenderCost << "\n";

	app << "#DEVIATION ( deviation )\n" << deviation << "\n";

	app << "#HEURISTICS ( heuristics )\n" << heuristics << "\n";
	

	app << "===== END OF BspTree statistics ==========\n";
}