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

#include "BvHierarchy.h"
#include "ViewCell.h"
#include "Plane3.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 "VspTree.h"
#include "HierarchyManager.h"


namespace GtpVisibilityPreprocessor {


#define PROBABILIY_IS_BV_VOLUME 1
#define USE_FIXEDPOINT_T 0
#define USE_VOLUMES_FOR_HEURISTICS 1

int BvhNode::sMailId = 10000; //2147483647;
int BvhNode::sReservedMailboxes = 1;

BvHierarchy *BvHierarchy::BvhSubdivisionCandidate::sBvHierarchy = NULL;


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


/***************************************************************/
/*              class BvhNode implementation                   */
/***************************************************************/

BvhNode::BvhNode(): 
mParent(NULL), 
mMailbox(0),
//mRenderCostDecr(0), 
//mMemoryIncr(0),
//mPvsEntriesIncr(0),
mTimeStamp(0)
{
	
}

BvhNode::BvhNode(const AxisAlignedBox3 &bbox):
mParent(NULL), 
mBoundingBox(bbox), 
mMailbox(0),
//mMemoryIncr(0),
//mRenderCostDecr(0), 
//mPvsEntriesIncr(0),
mTimeStamp(0)
{
}


BvhNode::BvhNode(const AxisAlignedBox3 &bbox, BvhInterior *parent):
mBoundingBox(bbox), 
mParent(parent), 
mMailbox(0),
//mMemoryIncr(0),
//mRenderCostDecr(0), 
//mPvsEntriesIncr(0),
mTimeStamp(0)
{
}


bool BvhNode::IsRoot() const
{
	return mParent == NULL;
}


BvhInterior *BvhNode::GetParent()
{
	return mParent;
}


void BvhNode::SetParent(BvhInterior *parent)
{
	mParent = parent;
}



/******************************************************************/
/*              class BvhInterior implementation                  */
/******************************************************************/


BvhLeaf::BvhLeaf(const AxisAlignedBox3 &bbox):
BvhNode(bbox), 
mSubdivisionCandidate(NULL)
{
	mActiveNode = this;
}


BvhLeaf::BvhLeaf(const AxisAlignedBox3 &bbox, BvhInterior *parent):
BvhNode(bbox, parent)
{
	mActiveNode = this;
}


BvhLeaf::BvhLeaf(const AxisAlignedBox3 &bbox, 
				 BvhInterior *parent, 
				 const int numObjects):
BvhNode(bbox, parent)
{
	mObjects.reserve(numObjects);
	mActiveNode = this;
}


bool BvhLeaf::IsLeaf() const 
{ 
	return true; 
}


BvhLeaf::~BvhLeaf() 
{ 
}


void BvhLeaf::CollectObjects(ObjectContainer &objects)
{
	ObjectContainer::const_iterator oit, oit_end = mObjects.end();
	for (oit = mObjects.begin(); oit != oit_end; ++ oit)
	{
		objects.push_back(*oit);
	}
}

/******************************************************************/
/*              class BvhInterior implementation                  */
/******************************************************************/


BvhInterior::BvhInterior(const AxisAlignedBox3 &bbox):
BvhNode(bbox), mFront(NULL), mBack(NULL)
{
}


BvhInterior::BvhInterior(const AxisAlignedBox3 &bbox, BvhInterior *parent):
BvhNode(bbox, parent), mFront(NULL), mBack(NULL)
{
}


void BvhInterior::ReplaceChildLink(BvhNode *oldChild, BvhNode *newChild) 
{
	if (mBack == oldChild)
		mBack = newChild;
	else
		mFront = newChild;
}


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


BvhInterior::~BvhInterior() 
{ 
	DEL_PTR(mFront); 
	DEL_PTR(mBack);
}


void BvhInterior::SetupChildLinks(BvhNode *front, BvhNode *back) 
{
    mBack = back;
    mFront = front;
}


void BvhInterior::CollectObjects(ObjectContainer &objects)
{
	mFront->CollectObjects(objects);
	mBack->CollectObjects(objects);
}


/*******************************************************************/
/*                  class BvHierarchy implementation               */
/*******************************************************************/


BvHierarchy::BvHierarchy():
mRoot(NULL),
mTimeStamp(1)
{
	ReadEnvironment();
	mSubdivisionCandidates = new SortableEntryContainer;
	for (int i = 0; i < 3; ++ i)
		mSortedObjects[i] = NULL;
}


BvHierarchy::~BvHierarchy()
{
	// delete bvh intersectables
	BvhIntersectableMap::iterator it, it_end = mBvhIntersectables.end();

	for (it = mBvhIntersectables.begin(); it != mBvhIntersectables.end(); ++ it)
	{
		DEL_PTR((*it).second);
	}

	// delete the local subdivision candidates
	DEL_PTR(mSubdivisionCandidates);

	// delete the presorted objects
	for (int i = 0; i < 3; ++ i)
	{
		DEL_PTR(mSortedObjects[i]);
	}
	
	// delete the tree
	DEL_PTR(mRoot);
}


void BvHierarchy::ReadEnvironment()
{
	bool randomize = false;
	Environment::GetSingleton()->GetBoolValue("VspTree.Construction.randomize", randomize);
	 
	// initialise random generator for heuristics
	if (randomize)
		Randomize();

	//////////////////////////////
	//-- termination criteria for autopartition

	Environment::GetSingleton()->GetIntValue("BvHierarchy.Termination.maxDepth", mTermMaxDepth);
	Environment::GetSingleton()->GetIntValue("BvHierarchy.Termination.maxLeaves", mTermMaxLeaves);
	Environment::GetSingleton()->GetIntValue("BvHierarchy.Termination.minObjects", mTermMinObjects);
	Environment::GetSingleton()->GetIntValue("BvHierarchy.Termination.minRays", mTermMinRays);
	Environment::GetSingleton()->GetFloatValue(
		"BvHierarchy.Termination.minProbability", mTermMinProbability);
    Environment::GetSingleton()->GetIntValue("BvHierarchy.Termination.missTolerance", mTermMissTolerance);


	//////////////////////////////
	//-- max cost ratio for early tree termination

	Environment::GetSingleton()->GetFloatValue("BvHierarchy.Termination.maxCostRatio", mTermMaxCostRatio);
	Environment::GetSingleton()->GetFloatValue("BvHierarchy.Termination.minGlobalCostRatio",
		mTermMinGlobalCostRatio);
	Environment::GetSingleton()->GetIntValue("BvHierarchy.Termination.globalCostMissTolerance", 
		mTermGlobalCostMissTolerance);


	//////////////////////////////
	//-- factors for subdivision heuristics

	// if only the driving axis is used for splits
	Environment::GetSingleton()->GetBoolValue("BvHierarchy.splitUseOnlyDrivingAxis", mOnlyDrivingAxis);
	Environment::GetSingleton()->GetFloatValue("BvHierarchy.maxStaticMemory", mMaxMemory);
	Environment::GetSingleton()->GetBoolValue("BvHierarchy.useCostHeuristics", mUseCostHeuristics);
	Environment::GetSingleton()->GetBoolValue("BvHierarchy.useSah", mUseSah);

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

	Environment::GetSingleton()->GetFloatValue(
		"BvHierarchy.Construction.renderCostDecreaseWeight", mRenderCostDecreaseWeight);
	Environment::GetSingleton()->GetBoolValue(
		"BvHierarchy.Construction.useGlobalSorting", mUseGlobalSorting);
	Environment::GetSingleton()->GetIntValue("BvHierarchy.minRaysForVisibility", mMinRaysForVisibility);
	Environment::GetSingleton()->GetIntValue("BvHierarchy.maxTests", mMaxTests);

	//mMemoryConst = (float)(sizeof(VspLeaf) + sizeof(VspViewCell));
	//mMemoryConst = (float)sizeof(BvhLeaf);
mMemoryConst = (float)sizeof(ObjectContainer);
	cout << "bvh memcost: " << mMemoryConst << endl;
	cout << "triangle: " << sizeof(TriangleIntersectable) << endl;
	cout << "triangle: " << sizeof(Intersectable) << endl;
	cout << "triangle: " << sizeof(ObjectContainer) << endl;
	cout << "triangle: " << sizeof(float) << endl;
	cout << "triangle: " << sizeof(int) << endl;

    mUseBboxAreaForSah = true;

	/////////////
	//-- debug output

	Debug << "******* Bvh hierarchy options ******** " << endl;
    Debug << "max depth: " << mTermMaxDepth << endl;
	Debug << "min probabiliy: " << mTermMinProbability<< endl;
	Debug << "min objects: " << mTermMinObjects << endl;
	Debug << "max cost ratio: " << mTermMaxCostRatio << endl;
	Debug << "miss tolerance: " << mTermMissTolerance << endl;
	Debug << "max leaves: " << mTermMaxLeaves << endl;
	Debug << "randomize: " << randomize << endl;
	Debug << "min global cost ratio: " << mTermMinGlobalCostRatio << endl;
	Debug << "global cost miss tolerance: " << mTermGlobalCostMissTolerance << endl;
	Debug << "only driving axis: " << mOnlyDrivingAxis << endl;
	Debug << "max memory: " << mMaxMemory << endl;
	Debug << "use cost heuristics: " << mUseCostHeuristics << endl;
	Debug << "use sah (surface area heuristics: " << mUseSah << endl;
	Debug << "subdivision stats log: " << subdivisionStatsLog << endl;
	Debug << "split borders: " << mSplitBorder << endl;
	Debug << "render cost decrease weight: " << mRenderCostDecreaseWeight << endl;
	Debug << "use global sort: " << mUseGlobalSorting << endl;
	Debug << "minimal rays for visibility: " << mMinRaysForVisibility << endl;
	Debug << "bvh mem const: " << mMemoryConst << endl;

	Debug << endl;
}


void BvHierarchy::AssociateObjectsWithLeaf(BvhLeaf *leaf)
{
	ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();

	for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit)
	{
		(*oit)->mBvhLeaf = leaf;
	}
}


static int CountRays(const ObjectContainer &objects)
{
	int nRays = 0;

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

	for (oit = objects.begin(); oit != oit_end; ++ oit)
	{
		nRays += (int)(*oit)->GetOrCreateRays()->size();
	}

	return nRays;
}
									

BvhInterior *BvHierarchy::SubdivideNode(const BvhSubdivisionCandidate &sc,
										BvhTraversalData &frontData,
										BvhTraversalData &backData)
{
	const BvhTraversalData &tData = sc.mParentData;
	BvhLeaf *leaf = tData.mNode;
	AxisAlignedBox3 parentBox = leaf->GetBoundingBox();

	// update stats: we have two new leaves
	mBvhStats.nodes += 2;

	if (tData.mDepth > mBvhStats.maxDepth)
	{
		mBvhStats.maxDepth = tData.mDepth;
	}

	// add the new nodes to the tree
	BvhInterior *node = new BvhInterior(parentBox, leaf->GetParent());
	

	//////////////////
	//-- create front and back leaf

	AxisAlignedBox3 fbox = EvalBoundingBox(sc.mFrontObjects, &parentBox);
	AxisAlignedBox3 bbox = EvalBoundingBox(sc.mBackObjects, &parentBox);

	BvhLeaf *back = new BvhLeaf(bbox, node, (int)sc.mBackObjects.size());
	BvhLeaf *front = new BvhLeaf(fbox, node, (int)sc.mFrontObjects.size());

	BvhInterior *parent = leaf->GetParent();

	// replace a link from node's parent
	if (parent)
	{
		parent->ReplaceChildLink(leaf, node);
		node->SetParent(parent);
	}
	else // no parent => this node is the root
	{
		mRoot = node;
	}

	// and setup child links
	node->SetupChildLinks(front, back);

	++ mBvhStats.splits;


	////////////////////////////////////////
	//-- fill  front and back traversal data with the new values

	frontData.mDepth = backData.mDepth = tData.mDepth + 1;

	frontData.mNode = front;
	backData.mNode = back;

	back->mObjects = sc.mBackObjects;
	front->mObjects = sc.mFrontObjects;

	// if the number of rays is too low, no assumptions can be made
	// (=> switch to surface area heuristics?)
	frontData.mNumRays = CountRays(sc.mFrontObjects);
	backData.mNumRays = CountRays(sc.mBackObjects);

	AssociateObjectsWithLeaf(back);
	AssociateObjectsWithLeaf(front);
   
#if PROBABILIY_IS_BV_VOLUME
	// volume of bvh (= probability that this bvh can be seen)
	frontData.mProbability = fbox.GetVolume();
	backData.mProbability = bbox.GetVolume();
#else
	// compute probability of this node being visible, 
	// i.e., volume of the view cells that can see this node
	frontData.mProbability = EvalViewCellsVolume(sc.mFrontObjects);
	backData.mProbability = EvalViewCellsVolume(sc.mBackObjects);
#endif

    // how often was max cost ratio missed in this branch?
	frontData.mMaxCostMisses = sc.GetMaxCostMisses();
	backData.mMaxCostMisses = sc.GetMaxCostMisses();
	
	// set the time stamp so the order of traversal can be reconstructed
	node->mTimeStamp = mHierarchyManager->mTimeStamp ++;
		
	// assign the objects in sorted order
	if (mUseGlobalSorting)
	{
		AssignSortedObjects(sc, frontData, backData);
	}
	
	// return the new interior node
	return node;
}


BvhNode *BvHierarchy::Subdivide(SplitQueue &tQueue,
								SubdivisionCandidate *splitCandidate,
								const bool globalCriteriaMet)
{
	BvhSubdivisionCandidate *sc = dynamic_cast<BvhSubdivisionCandidate *>(splitCandidate);
	BvhTraversalData &tData = sc->mParentData;

	BvhNode *currentNode = tData.mNode;

	if (!LocalTerminationCriteriaMet(tData) && !globalCriteriaMet)
	{	
		//////////////
		//-- continue subdivision

		BvhTraversalData tFrontData;
		BvhTraversalData tBackData;
			
		// create new interior node and two leaf node
		currentNode = SubdivideNode(*sc, tFrontData, tBackData);
	
		// decrease the weighted average cost of the subdivisoin
		mTotalCost -= sc->GetRenderCostDecrease();
		mPvsEntries += sc->GetPvsEntriesIncr();

		// subdivision statistics
		if (1) PrintSubdivisionStats(*sc);


		///////////////////////////
		//-- push the new split candidates on the queue
		
		BvhSubdivisionCandidate *frontCandidate = new BvhSubdivisionCandidate(tFrontData);
		BvhSubdivisionCandidate *backCandidate = new BvhSubdivisionCandidate(tBackData);

		EvalSubdivisionCandidate(*frontCandidate);
		EvalSubdivisionCandidate(*backCandidate);
	
		// cross reference
		tFrontData.mNode->SetSubdivisionCandidate(frontCandidate); 
		tBackData.mNode->SetSubdivisionCandidate(backCandidate);

		//cout << "f: " << frontCandidate->GetPriority() << " b: " << backCandidate->GetPriority() << endl;
		tQueue.Push(frontCandidate);
		tQueue.Push(backCandidate);
	}

	/////////////////////////////////
	//-- node is a leaf => terminate traversal

	if (currentNode->IsLeaf())
	{
		/////////////////////
		//-- store additional info
		EvaluateLeafStats(tData);
        
		const bool mStoreRays = true;
		if (mStoreRays)
		{
			BvhLeaf *leaf = dynamic_cast<BvhLeaf *>(currentNode);
		//	CollectRays(leaf->mObjects, leaf->mVssRays);
		}
		
		//////////////////////////////////////
		
		// this leaf is no candidate for splitting anymore
		// => detach subdivision candidate
		tData.mNode->SetSubdivisionCandidate(NULL); 
		// detach node so we don't delete it with the traversal data
		tData.mNode = NULL;
	}
	
	return currentNode;
}


void BvHierarchy::EvalSubdivisionCandidate(BvhSubdivisionCandidate &splitCandidate, 
										   bool computeSplitPlane)
{
	if (computeSplitPlane)
	{
		const bool sufficientSamples = 
			splitCandidate.mParentData.mNumRays > mMinRaysForVisibility;

		const bool useVisibiliyBasedHeuristics = 
			!mUseSah &&
			(mHierarchyManager->GetViewSpaceSubdivisionType() == 
			HierarchyManager::KD_BASED_VIEWSPACE_SUBDIV) &&
			sufficientSamples;

		// compute best object partition
		const float ratio =	SelectObjectPartition(splitCandidate.mParentData, 
												  splitCandidate.mFrontObjects, 
												  splitCandidate.mBackObjects,
												  useVisibiliyBasedHeuristics);
	
		// cost ratio violated?
		const bool maxCostRatioViolated = mTermMaxCostRatio < ratio;
		const int previousMisses = splitCandidate.mParentData.mMaxCostMisses;

		splitCandidate.SetMaxCostMisses(maxCostRatioViolated ? previousMisses + 1 : previousMisses);

	}

	BvhLeaf *leaf = splitCandidate.mParentData.mNode;

	const float oldProp = EvalViewCellsVolume(leaf->mObjects);
	const float oldRenderCost = EvalRenderCost(leaf->mObjects);
		
	// compute global decrease in render cost
	const float newRenderCost = EvalRenderCost(splitCandidate.mFrontObjects) +
								EvalRenderCost(splitCandidate.mBackObjects);

	const float renderCostDecr = oldRenderCost - newRenderCost;
	
	splitCandidate.SetRenderCostDecrease(renderCostDecr);

	// increase in pvs entries
	const int pvsEntriesIncr = EvalPvsEntriesIncr(splitCandidate);
	splitCandidate.SetPvsEntriesIncr(pvsEntriesIncr);

#ifdef GTP_DEBUG
	Debug << "old render cost: " << oldRenderCost << endl;
	Debug << "new render cost: " << newRenderCost << endl;
	Debug << "render cost decrease: " << renderCostDecr << endl;
#endif

	float priority;

	// surface area heuristics is used when there is no view space subdivision available. 
	// In order to have some prioritized traversal, use this formula instead
	if (mHierarchyManager->GetViewSpaceSubdivisionType() == 
		HierarchyManager::NO_VIEWSPACE_SUBDIV)
	{
		priority = EvalSahCost(leaf);
	}
	else
	{
		// take render cost of node into account 
		// otherwise danger of being stuck in a local minimum!
		const float factor = mRenderCostDecreaseWeight;

		if (1)
		{
			priority = factor * renderCostDecr + (1.0f - factor) * oldRenderCost;
			if (mHierarchyManager->mConsiderMemory2)
			{
				priority /= ((float)splitCandidate.GetPvsEntriesIncr() + mMemoryConst);
			}
		}
		else
		{
			if (!mHierarchyManager->mConsiderMemory2)
			{
				priority = factor * renderCostDecr + (1.0f - factor) * oldRenderCost;
			}
			else
			{
				const float ratio = 
					renderCostDecr / ((float)splitCandidate.GetPvsEntriesIncr() + mMemoryConst);

				priority = factor * ratio + (1.0f - factor) * oldRenderCost;
			}
		}
	}

  	// compute global decrease in render cost
	splitCandidate.SetPriority(priority);
}


int BvHierarchy::EvalPvsEntriesIncr(BvhSubdivisionCandidate &splitCandidate) const
{
	const int oldPvsSize = CountViewCells(splitCandidate.mParentData.mNode->mObjects);
	
	const int fPvsSize = CountViewCells(splitCandidate.mFrontObjects);
	const int bPvsSize = CountViewCells(splitCandidate.mBackObjects);

	return fPvsSize + bPvsSize - oldPvsSize;
}


inline bool BvHierarchy::LocalTerminationCriteriaMet(const BvhTraversalData &data) const
{
	const bool terminationCriteriaMet =
			(0
			|| ((int)data.mNode->mObjects.size() <= 1)//mTermMinObjects)
			//|| (data.mProbability <= mTermMinProbability)
			//|| (data.mNumRays <= mTermMinRays)
		 );

#ifdef _DEBUG
	if (terminationCriteriaMet)
	{
		cout << "bvh local termination criteria met:" << endl;
		cout << "objects: " << data.mNode->mObjects.size() << " " << mTermMinObjects << endl;
	}
#endif
	return terminationCriteriaMet; 
}


inline bool BvHierarchy::GlobalTerminationCriteriaMet(const BvhTraversalData &data) const
{
	// note: tracking for global cost termination 
	// does not make much sense for interleaved vsp / osp partition
	// as it is the responsibility of the hierarchy manager

	const bool terminationCriteriaMet =
		(0
		|| (mBvhStats.Leaves() >= mTermMaxLeaves)
		//|| (mBvhStats.mGlobalCostMisses >= mTermGlobalCostMissTolerance)
		//|| mOutOfMemory 
		);

#ifdef GTP_DEBUG
	if (terminationCriteriaMet)
	{
		Debug << "bvh global termination criteria met:" << endl;
		Debug << "cost misses: " << mBvhStats.mGlobalCostMisses << " " << mTermGlobalCostMissTolerance << endl;
		Debug << "leaves: " << mBvhStats.Leaves() << " " << mTermMaxLeaves << endl;
	}
#endif
	return terminationCriteriaMet; 
}


void BvHierarchy::EvaluateLeafStats(const BvhTraversalData &data)
{
	// the node became a leaf -> evaluate stats for leafs
	BvhLeaf *leaf = data.mNode;
	
	++ mCreatedLeaves;

	
	if (data.mProbability <= mTermMinProbability)
	{
		++ mBvhStats.minProbabilityNodes;
	}

	////////////////////////////////////////////
	// depth related stuff

	if (data.mDepth < mBvhStats.minDepth)
	{
		mBvhStats.minDepth = data.mDepth;
	}

	if (data.mDepth >= mTermMaxDepth)
	{
        ++ mBvhStats.maxDepthNodes;
	}

	// accumulate depth to compute average depth
	mBvhStats.accumDepth += data.mDepth;


	////////////////////////////////////////////
	// objects related stuff

	// note: the sum should alwaysbe total number of objects for bvh
	mBvhStats.objectRefs += (int)leaf->mObjects.size();

	if ((int)leaf->mObjects.size() <= mTermMinObjects)
	{
	     ++ mBvhStats.minObjectsNodes;
	}

	if (leaf->mObjects.empty())
	{
		++ mBvhStats.emptyNodes;
	}

	if ((int)leaf->mObjects.size() > mBvhStats.maxObjectRefs)
	{
		mBvhStats.maxObjectRefs = (int)leaf->mObjects.size();
	}

	if ((int)leaf->mObjects.size() < mBvhStats.minObjectRefs)
	{
		mBvhStats.minObjectRefs = (int)leaf->mObjects.size();
	}

	////////////////////////////////////////////
	// ray related stuff

	// note: this number should always accumulate to the total number of rays
	mBvhStats.rayRefs += data.mNumRays;
	
	if (data.mNumRays <= mTermMinRays)
	{
	     ++ mBvhStats.minRaysNodes;
	}

	if (data.mNumRays > mBvhStats.maxRayRefs)
	{
		mBvhStats.maxRayRefs = data.mNumRays;
	}

	if (data.mNumRays < mBvhStats.minRayRefs)
	{
		mBvhStats.minRayRefs = data.mNumRays;
	}

#ifdef _DEBUG
	cout << "depth: " << data.mDepth << " objects: " << (int)leaf->mObjects.size() 
		 << " rays: " << data.mNumRays << " rays / objects " 
		 << (float)data.mNumRays / (float)leaf->mObjects.size() << endl;
#endif
}


#if 0

/// compute object boundaries using spatial mid split
float BvHierarchy::EvalLocalObjectPartition(const BvhTraversalData &tData,
											const int axis,
											ObjectContainer &objectsFront,
											ObjectContainer &objectsBack)
{
	const float maxBox = tData.mBoundingBox.Max(axis);
	const float minBox = tData.mBoundingBox.Min(axis);

	float midPoint = (maxBox + minBox) * 0.5f;

	ObjectContainer::const_iterator oit, oit_end = tData.mNode->mObjects.end();
	
	for (oit = tData.mNode->mObjects.begin(); oit != oit_end; ++ oit)
	{
		Intersectable *obj = *oit;
		const AxisAlignedBox3 box = obj->GetBox();

		const float objMid = (box.Max(axis) + box.Min(axis)) * 0.5f;

		// object mailed => belongs to back objects
		if (objMid < midPoint) 
		{
			objectsBack.push_back(obj);
		}
		else
		{
			objectsFront.push_back(obj);
		}
	}

	const float oldRenderCost = EvalRenderCost(tData.mNode->mObjects);
	const float newRenderCost = EvalRenderCost(objectsFront) * EvalRenderCost(objectsBack);

	const float ratio = newRenderCost / oldRenderCost;
	return ratio;
}

#else

/// compute object partition by getting balanced objects on the left and right side
float BvHierarchy::EvalLocalObjectPartition(const BvhTraversalData &tData,
											const int axis,
											ObjectContainer &objectsFront,
											ObjectContainer &objectsBack)
{
	PrepareLocalSubdivisionCandidates(tData, axis);
	
	SortableEntryContainer::const_iterator cit, cit_end = mSubdivisionCandidates->end();

	int i = 0;
	const int border = (int)tData.mNode->mObjects.size() / 2;

    for (cit = mSubdivisionCandidates->begin(); cit != cit_end; ++ cit, ++ i)
	{
		Intersectable *obj = (*cit).mObject;

		// object mailed => belongs to back objects
		if (i < border) 
		{
			objectsBack.push_back(obj);
		}
		else
		{
			objectsFront.push_back(obj);
		}
	}

#if 1
	const float cost = (tData.mNode->GetBoundingBox().Size().DrivingAxis() == axis) ? -1.0f : 0.0f;
#else
	const float oldRenderCost = EvalRenderCost(tData.mNode->mObjects);
	const float newRenderCost = EvalRenderCost(objectsFront) * EvalRenderCost(objectsBack);

	const float cost = newRenderCost / oldRenderCost;
#endif

	return cost;
}
#endif

#if 1

float BvHierarchy::EvalSah(const BvhTraversalData &tData,
						   const int axis,
						   ObjectContainer &objectsFront,
						   ObjectContainer &objectsBack)
{
	// go through the lists, count the number of objects left and right
	// and evaluate the following cost funcion:
	// C = ct_div_ci  + (ol + or) / queries
	PrepareLocalSubdivisionCandidates(tData, axis);

	const float totalRenderCost = EvalAbsCost(tData.mNode->mObjects);
	float objectsLeft = 0, objectsRight = totalRenderCost;
  
	const AxisAlignedBox3 nodeBbox = tData.mNode->GetBoundingBox();
	const float boxArea = nodeBbox.SurfaceArea();

	float minSum = 1e20f;
  
	float minBorder = nodeBbox.Max(axis);
	float maxBorder = nodeBbox.Min(axis);

	float areaLeft = 0, areaRight = 0;

	SortableEntryContainer::const_iterator currentPos =
		mSubdivisionCandidates->begin();
	
	vector<float> bordersRight;

	// we keep track of both borders of the bounding boxes =>
	// store the events in descending order

	bordersRight.resize(mSubdivisionCandidates->size());

	SortableEntryContainer::reverse_iterator rcit = 
		mSubdivisionCandidates->rbegin(), rcit_end = 
		mSubdivisionCandidates->rend();

	vector<float>::reverse_iterator rbit = bordersRight.rbegin();

	for (; rcit != rcit_end; ++ rcit, ++ rbit) 
	{
		Intersectable *obj = (*rcit).mObject;
		const AxisAlignedBox3 obox = obj->GetBox();

		if (obox.Min(axis) < minBorder)
		{
			minBorder = obox.Min(axis);
		}

		(*rbit) = minBorder;
	}

	// temporary surface areas
	float al = 0;
	float ar = boxArea;

	vector<float>::const_iterator bit = bordersRight.begin();
	SortableEntryContainer::const_iterator cit, cit_end = mSubdivisionCandidates->end();

	for (cit = mSubdivisionCandidates->begin(); cit != cit_end; ++ cit, ++ bit) 
	{
		Intersectable *obj = (*cit).mObject;

		const float renderCost = mViewCellsManager->EvalRenderCost(obj);
		
		objectsLeft += renderCost;
		objectsRight -= renderCost;

		const AxisAlignedBox3 obox = obj->GetBox();

		// the borders of the bounding boxes have changed
		if (obox.Max(axis) > maxBorder)
		{
			maxBorder = obox.Max(axis);
		}

		minBorder = (*bit);

		AxisAlignedBox3 lbox = nodeBbox;
		AxisAlignedBox3 rbox = nodeBbox;

		lbox.SetMax(axis, maxBorder);
		rbox.SetMin(axis, minBorder);

		al = lbox.SurfaceArea();
		ar = rbox.SurfaceArea();

		const bool noValidSplit = ((objectsLeft <= Limits::Small) || (objectsRight <= Limits::Small));
		const float sum =  noValidSplit ? 1e25 : objectsLeft * al + objectsRight * ar;
      
		/*cout << "pos=" << (*cit).mPos << "\t q=(" << objectsLeft << "," << objectsRight <<")\t r=(" 
			 << lbox.SurfaceArea() << "," << rbox.SurfaceArea() << ")" << endl;
		cout << "minborder: " << minBorder << " maxborder: " << maxBorder << endl;
	    cout << "cost= " << sum << endl;*/
	
		if (sum < minSum) 
		{	
			minSum = sum;
			areaLeft = al;
			areaRight = ar;

			// objects belong to left side now
			for (; currentPos != (cit + 1); ++ currentPos);
		}
	}

	////////////
	//-- assign object to front and back volume

	// belongs to back bv
	for (cit = mSubdivisionCandidates->begin(); cit != currentPos; ++ cit)
		objectsBack.push_back((*cit).mObject);
	
	// belongs to front bv
	for (cit = currentPos; cit != cit_end; ++ cit)
		objectsFront.push_back((*cit).mObject);

	float newCost = minSum / boxArea;
	float ratio = newCost / totalRenderCost;
  
#ifdef GTP_DEBUG
	cout << "\n\nobjects=(" << (int)objectsBack.size() << "," << (int)objectsFront.size() << " of " 
		 << (int)tData.mNode->mObjects.size() << ")\t area=(" 
		 << areaLeft << ", " << areaRight << ", " << boxArea << ")" << endl
		 << "cost= " << newCost << " oldCost=" << totalRenderCost / boxArea << endl;
#endif

	return ratio;
}

#else

float BvHierarchy::EvalSah(const BvhTraversalData &tData,
						   const int axis,
						   ObjectContainer &objectsFront,
						   ObjectContainer &objectsBack)
{
	// go through the lists, count the number of objects left and right
	// and evaluate the following cost funcion:
	// C = ct_div_ci  + (ol + or) / queries
	PrepareLocalSubdivisionCandidates(tData, axis);

	const float totalRenderCost = EvalAbsCost(tData.mNode->mObjects);
	float objectsLeft = 0, objectsRight = totalRenderCost;
  
	const AxisAlignedBox3 nodeBbox = tData.mNode->GetBoundingBox();

	const float minBox = nodeBbox.Min(axis);
	const float maxBox = nodeBbox.Max(axis);
	const float boxArea = nodeBbox.SurfaceArea();

	float minSum = 1e20f;
  
	Vector3 minBorder = nodeBbox.Max();
	Vector3 maxBorder = nodeBbox.Min();

	float areaLeft = 0, areaRight = 0;

	SortableEntryContainer::const_iterator currentPos =
		mSubdivisionCandidates->begin();
	
	vector<Vector3> bordersRight;

	// we keep track of both borders of the bounding boxes =>
	// store the events in descending order
	bordersRight.resize(mSubdivisionCandidates->size());

	SortableEntryContainer::reverse_iterator rcit = 
		mSubdivisionCandidates->rbegin(), rcit_end = 
		mSubdivisionCandidates->rend();

	vector<Vector3>::reverse_iterator rbit = bordersRight.rbegin();

	for (; rcit != rcit_end; ++ rcit, ++ rbit) 
	{
		Intersectable *obj = (*rcit).mObject;
		const AxisAlignedBox3 obox = obj->GetBox();

		for (int i = 0; i < 3; ++ i)
		{
			if (obox.Min(i) < minBorder[i])
			{
				minBorder[i] = obox.Min(i);
			}
		}

		(*rbit) = minBorder;
	}

	// temporary surface areas
	float al = 0;
	float ar = boxArea;

	vector<Vector3>::const_iterator bit = bordersRight.begin();
	SortableEntryContainer::const_iterator cit, cit_end =
		mSubdivisionCandidates->end();

	for (cit = mSubdivisionCandidates->begin(); cit != cit_end; ++ cit, ++ bit) 
	{
		Intersectable *obj = (*cit).mObject;

		const float renderCost = mViewCellsManager->EvalRenderCost(obj);
		
		objectsLeft += renderCost;
		objectsRight -= renderCost;

		const AxisAlignedBox3 obox = obj->GetBox();

		AxisAlignedBox3 lbox = nodeBbox;
		AxisAlignedBox3 rbox = nodeBbox;
	
		// the borders of the left bounding box have changed
		for (int i = 0; i < 3; ++ i)
		{
			if (obox.Max(i) > maxBorder[i])
			{
				maxBorder[i] = obox.Max(i);
			}
		}

		minBorder = (*bit);

		lbox.SetMax(maxBorder);
		rbox.SetMin(minBorder);

		al = lbox.SurfaceArea();
		ar = rbox.SurfaceArea();
	
		const bool noValidSplit = ((objectsLeft <= Limits::Small) || (objectsRight <= Limits::Small));
		const float sum =  noValidSplit ? 1e25 : objectsLeft * al + objectsRight * ar;
      
		/*cout << "pos=" << (*cit).mPos << "\t q=(" << objectsLeft << "," << objectsRight <<")\t r=(" 
			 << lbox.SurfaceArea() << "," << rbox.SurfaceArea() << ")" << endl;
		cout << "minborder: " << minBorder << " maxborder: " << maxBorder << endl;
	    cout << "cost= " << sum << endl;*/
	
		if (sum < minSum) 
		{	
			minSum = sum;
			areaLeft = al;
			areaRight = ar;

			// objects belong to left side now
			for (; currentPos != (cit + 1); ++ currentPos);
		}
	}

	/////////////
	//-- assign object to front and back volume

	// belongs to back bv
	for (cit = mSubdivisionCandidates->begin(); cit != currentPos; ++ cit)
		objectsBack.push_back((*cit).mObject);
	
	// belongs to front bv
	for (cit = currentPos; cit != cit_end; ++ cit)
		objectsFront.push_back((*cit).mObject);

	float newCost = minSum / boxArea;
	float ratio = newCost / totalRenderCost;
  
#ifdef GTP_DEBUG
	cout << "\n\nobjects=(" << (int)objectsBack.size() << "," << (int)objectsFront.size() << " of " 
		 << (int)tData.mNode->mObjects.size() << ")\t area=(" 
		 << areaLeft << ", " << areaRight << ", " << boxArea << ")" << endl
		 << "cost= " << newCost << " oldCost=" << totalRenderCost / boxArea << endl;
#endif

	return ratio;
}

#endif

static bool PrepareOutput(const int axis,
						  const int leaves,
						  ofstream &sumStats, 
						  ofstream &vollStats, 
						  ofstream &volrStats)
{
	if ((axis == 0) && (leaves > 0) && (leaves < 90))
	{
		char str[64]; 	
		sprintf(str, "tmp/bvh_heur_sum-%04d.log", leaves);
		sumStats.open(str);
		sprintf(str, "tmp/bvh_heur_voll-%04d.log", leaves);
		vollStats.open(str);
		sprintf(str, "tmp/bvh_heur_volr-%04d.log", leaves);
		volrStats.open(str);
	}

	return sumStats.is_open() && vollStats.is_open() && volrStats.is_open();
}


static void PrintHeuristics(const float objectsRight,
							const float sum,
							const float volLeft,
							const float volRight,
							const float viewSpaceVol,
							ofstream &sumStats, 
							ofstream &vollStats, 
							ofstream &volrStats)
{
	sumStats
		<< "#Position\n" << objectsRight << endl
		<< "#Sum\n" << sum / viewSpaceVol << endl
		<< "#Vol\n" << (volLeft +  volRight) / viewSpaceVol << endl;

	vollStats
		<< "#Position\n" << objectsRight << endl
		<< "#Vol\n" << volLeft / viewSpaceVol << endl;

	volrStats
		<< "#Position\n" << objectsRight << endl
		<< "#Vol\n" << volRight / viewSpaceVol << endl;
}


float BvHierarchy::EvalLocalCostHeuristics(const BvhTraversalData &tData,
										   const int axis,
										   ObjectContainer &objectsFront,
										   ObjectContainer &objectsBack)
{
	///////////////////////////////////////////////////////
	//-- go through the lists, count the number of objects left 
	//-- and right and evaluate the cost funcion

	// prepare the heuristics by setting mailboxes and counters.
	const float totalVol = PrepareHeuristics(tData, axis);
	
	// local helper variables
	float volLeft = 0;
	float volRight = totalVol;
	
	const float nTotalObjects = EvalAbsCost(tData.mNode->mObjects);
	float nObjectsLeft = 0;
	float nObjectsRight = nTotalObjects;

	const float viewSpaceVol = mViewCellsManager->GetViewSpaceBox().GetVolume();

	SortableEntryContainer::const_iterator backObjectsStart = 
		mSubdivisionCandidates->begin();

	/////////////////////////////////
	//-- the parameters for the current optimum

	float volBack = volLeft;
	float volFront = volRight;
	float newRenderCost = nTotalObjects * totalVol;

#ifdef GTP_DEBUG
	ofstream sumStats;
	ofstream vollStats;
	ofstream volrStats;

	const bool printStats =
		PrepareOutput(axis, mBvhStats.Leaves(), sumStats, vollStats, volrStats);
#endif

	///////////////////////
	//-- the sweep heuristics
	//-- traverse through events and find best split plane

	SortableEntryContainer::const_iterator cit, 
		cit_end = cit_end = mSubdivisionCandidates->end();

	for (cit = mSubdivisionCandidates->begin(); cit != cit_end; ++ cit)
	{
		Intersectable *object = (*cit).mObject;
	
		// evaluate change in l and r volume
		// voll = view cells that see only left node (i.e., left pvs)
		// volr = view cells that see only right node (i.e., right pvs)
		EvalHeuristicsContribution(object, volLeft, volRight);

		const float rc = mViewCellsManager->EvalRenderCost(object);

		nObjectsLeft += rc;
		nObjectsRight -= rc;
		
		const bool noValidSplit = ((nObjectsLeft <= Limits::Small) || (nObjectsRight <= Limits::Small));

		// the heuristics
	    const float sum = noValidSplit ? 
			1e25 : volLeft * (float)nObjectsLeft + volRight * (float)nObjectsRight;

#ifdef GTP_DEBUG
		if (printStats)
		{
			PrintHeuristics(nObjectsRight, sum, volLeft, volRight, viewSpaceVol,
							sumStats, vollStats, volrStats);
		}
#endif

		if (sum < newRenderCost)
		{
			newRenderCost = sum;

			volBack = volLeft;
			volFront = volRight;

			// objects belongs to left side now
			for (; backObjectsStart != (cit + 1); ++ backObjectsStart);
		}
	}

	////////////////////////////////////////////
	//-- assign object to front and back volume

	// belongs to back bv
	for (cit = mSubdivisionCandidates->begin(); cit != backObjectsStart; ++ cit)
	{
		objectsBack.push_back((*cit).mObject);
	}
	// belongs to front bv
	for (cit = backObjectsStart; cit != cit_end; ++ cit)
	{
		objectsFront.push_back((*cit).mObject);
	}

	// render cost of the old parent
	const float oldRenderCost = (float)nTotalObjects * totalVol + Limits::Small;
	// the relative cost ratio
	const float ratio = newRenderCost / oldRenderCost;

#ifdef GTP_DEBUG
	Debug << "\n§§§§ bvh eval const decrease §§§§" << endl
		  << "back pvs: " << (int)objectsBack.size() << " front pvs: " 
		  << (int)objectsFront.size() << " total pvs: " << nTotalObjects << endl 
		  << "back p: " << volBack / viewSpaceVol << " front p " 
		  << volFront / viewSpaceVol << " p: " << totalVol / viewSpaceVol << endl
		  << "old rc: " << oldRenderCost / viewSpaceVol << " new rc: " 
		  << newRenderCost / viewSpaceVol << endl
		  << "render cost decrease: " 
		  << oldRenderCost / viewSpaceVol - newRenderCost / viewSpaceVol << endl;
#endif

	return ratio;
}


void BvHierarchy::PrepareLocalSubdivisionCandidates(const BvhTraversalData &tData,
													const int axis)											
{
	//-- insert object queries
	ObjectContainer *objects = mUseGlobalSorting ? 
		tData.mSortedObjects[axis] : &tData.mNode->mObjects;

	CreateLocalSubdivisionCandidates(*objects, &mSubdivisionCandidates, !mUseGlobalSorting, axis);
}


void BvHierarchy::CreateLocalSubdivisionCandidates(const ObjectContainer &objects, 
												  SortableEntryContainer **subdivisionCandidates, 
												  const bool sort,
												  const int axis)
{
	(*subdivisionCandidates)->clear();

	// compute requested size and look if subdivision candidate has to be recomputed
	const int requestedSize = (int)objects.size() * 2;
	
	// creates a sorted split candidates array
	if ((*subdivisionCandidates)->capacity() > 500000 &&
		requestedSize < (int)((*subdivisionCandidates)->capacity() / 10) )
	{
    	delete (*subdivisionCandidates);
   		(*subdivisionCandidates) = new SortableEntryContainer;
	}

	(*subdivisionCandidates)->reserve(requestedSize);

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

	for (oit = objects.begin(); oit < oit_end; ++ oit)
	{
		Intersectable *object = *oit;
		const AxisAlignedBox3 &box = object->GetBox();
		const float midPt = (box.Min(axis) + box.Max(axis)) * 0.5f;

		(*subdivisionCandidates)->push_back(SortableEntry(object, midPt));
	}

	if (sort)
	{	// no presorted candidate list
		stable_sort((*subdivisionCandidates)->begin(), (*subdivisionCandidates)->end());
	}
}


const BvhStatistics &BvHierarchy::GetStatistics() const
{
	return mBvhStats;
}


float BvHierarchy::PrepareHeuristics(const BvhTraversalData &tData, 
									 const int axis)
{	
	BvhLeaf *leaf = tData.mNode;
	float vol = 0;

    // sort so we can use a sweep from right to left
	PrepareLocalSubdivisionCandidates(tData, axis);
	
	VssRayContainer rays;
	rays.reserve(tData.mNumRays);
	CollectRays(tData.mNode->mObjects, rays);

	const float prop = (float)mMaxTests / (float)tData.mNumRays;

	VssRay::NewMail();

	// only use a subset of the rays
	VssRayContainer::const_iterator rit, rit_end = rays.end();

	for (rit = rays.begin(); rit != rit_end; ++ rit)
	{
		if ((mMaxTests >= tData.mNumRays) || (Random(1.0f) < prop))
		{
			(*rit)->Mail();
		}
	}
	
	// collect and mark the view cells as belonging to front pvs
	ViewCellContainer viewCells;
	CollectViewCells(tData.mNode->mObjects, viewCells, true, true);
			
	ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
	for (vit = viewCells.begin(); vit != vit_end; ++ vit)
	{
#if USE_VOLUMES_FOR_HEURISTICS
		const float volIncr = (*vit)->GetVolume();
#else
		const float volIncr = 1.0f;
#endif
		vol += volIncr;
	}

	// we will mail view cells switching to the back side
	ViewCell::NewMail();
	
	return vol;
}

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


void BvHierarchy::EvalHeuristicsContribution(Intersectable *obj,
											 float &volLeft, 
											 float &volRight)
{
	// collect all view cells associated with this objects 
	// (also multiple times, if they are pierced by several rays)
	ViewCellContainer viewCells;
	const bool useMailboxing = false;

	CollectViewCells(obj, viewCells, useMailboxing, true, true);

	// classify view cells and compute volume contri accordingly
	// possible view cell classifications:
	// view cell mailed => view cell can be seen from left child node
	// view cell counter > 0 view cell can be seen from right child node
	// combined: view cell volume belongs to both nodes
	ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
	
	for (vit = viewCells.begin(); vit != vit_end; ++ vit)
	{
		// view cells can also be seen from left child node
		ViewCell *viewCell = *vit;
#if USE_VOLUMES_FOR_HEURISTICS
		const float vol = viewCell->GetVolume();
#else
		const float vol = 1.0f;
#endif
		if (!viewCell->Mailed())
		{
			viewCell->Mail();
			// we now see view cell from both nodes 
			// => add volume to left node
			volLeft += vol;
		}

		// last reference into the right node
		if (-- viewCell->mCounter == 0)
		{	
			// view cell was previously seen from both nodes  =>
			// remove volume from right node
			volRight -= vol;
		}
	}
}


void BvHierarchy::SetViewCellsManager(ViewCellsManager *vcm)
{
	mViewCellsManager = vcm;
}


AxisAlignedBox3 BvHierarchy::GetBoundingBox() const
{
	return mBoundingBox;
}


float BvHierarchy::SelectObjectPartition(const BvhTraversalData &tData,
										 ObjectContainer &frontObjects,
										 ObjectContainer &backObjects,
										 bool useVisibilityBasedHeuristics)
{
	ObjectContainer nFrontObjects[3];
	ObjectContainer nBackObjects[3];
	float nCostRatio[3];

	int sAxis = 0;
	int bestAxis = -1;

	if (mOnlyDrivingAxis)
	{
		const AxisAlignedBox3 box = tData.mNode->GetBoundingBox();
		sAxis = box.Size().DrivingAxis();
	}
	
	////////////////////////////////////
	//-- evaluate split cost for all three axis
	
	for (int axis = 0; axis < 3; ++ axis)
	{
		if (!mOnlyDrivingAxis || (axis == sAxis))
		{
			if (mUseCostHeuristics)
			{
				//////////////////////////////////
                //-- split objects using heuristics
				
				if (useVisibilityBasedHeuristics)
				{
					//cout << "v rays: " << tData.mNumRays << " " << endl;
					///////////
					//-- heuristics using objects weighted by view cells volume
					nCostRatio[axis] =
						EvalLocalCostHeuristics(tData, 
												axis, 
												nFrontObjects[axis], 
												nBackObjects[axis]);
				}
				else
				{	//cout << "e rays: " << tData.mNumRays << " ";
					//////////////////
					//-- view cells not constructed yet	=> use surface area heuristic			
					nCostRatio[axis] = EvalSah(tData, 
											   axis, 
											   nFrontObjects[axis], 
											   nBackObjects[axis]);
				}
			}
			else
			{
				//-- split objects using some simple criteria
				nCostRatio[axis] =
					EvalLocalObjectPartition(tData, axis, nFrontObjects[axis], nBackObjects[axis]);
			}

			if ((bestAxis == -1) || (nCostRatio[axis] < nCostRatio[bestAxis]))
			{
				bestAxis = axis;
			}
		}
	}

    ////////////////
	//-- assign values

	frontObjects = nFrontObjects[bestAxis];
	backObjects = nBackObjects[bestAxis];

	//cout << "val: " << nCostRatio[bestAxis] << " axis: " << bestAxis << endl;
	return nCostRatio[bestAxis];
}


int BvHierarchy::AssociateObjectsWithRays(const VssRayContainer &rays) const
{
	int nRays = 0;
	VssRayContainer::const_iterator rit, rit_end = rays.end();

	VssRay::NewMail();

    for (rit = rays.begin(); rit != rays.end(); ++ rit)
	{
		VssRay *ray = (*rit);

		if (ray->mTerminationObject)
		{
			ray->mTerminationObject->GetOrCreateRays()->push_back(ray);
			if (!ray->Mailed())
			{
				ray->Mail();
				++ nRays;
			}
		}
#if COUNT_ORIGIN_OBJECTS
		if (ray->mOriginObject)
		{
			ray->mOriginObject->GetOrCreateRays()->push_back(ray);

			if (!ray->Mailed())
			{
				ray->Mail();
				++ nRays;
			}
		}
#endif
	}

	return nRays;
}


void BvHierarchy::PrintSubdivisionStats(const SubdivisionCandidate &sc)
{
	const float costDecr = sc.GetRenderCostDecrease();	

	mSubdivisionStats 
			<< "#Leaves\n" << mBvhStats.Leaves() << endl
			<< "#RenderCostDecrease\n" << costDecr << endl 
			<< "#TotalRenderCost\n" << mTotalCost << endl
			<< "#EntriesInPvs\n" << mPvsEntries << endl;
}


void BvHierarchy::CollectRays(const ObjectContainer &objects,
							  VssRayContainer &rays) const
{
	VssRay::NewMail();
	ObjectContainer::const_iterator oit, oit_end = objects.end();

	// evaluate reverse pvs and view cell volume on left and right cell
	// note: should I take all leaf objects or rather the objects hit by rays?
	for (oit = objects.begin(); oit != oit_end; ++ oit)
	{
		Intersectable *obj = *oit;
		VssRayContainer::const_iterator rit, rit_end = obj->GetOrCreateRays()->end();

		for (rit = obj->GetOrCreateRays()->begin(); rit < rit_end; ++ rit)
		{
			VssRay *ray = (*rit);

			if (!ray->Mailed())
			{
				ray->Mail();
				rays.push_back(ray);
			}
		}
	}
}


float BvHierarchy::EvalAbsCost(const ObjectContainer &objects)// const
{
#if USE_BETTER_RENDERCOST_EST
	ObjectContainer::const_iterator oit, oit_end = objects.end();

	for (oit = objects.begin(); oit != oit_end; ++ oit)
	{
		objRenderCost += ViewCellsManager::GetRendercost(*oit);
	}
#else
	return (float)objects.size();
#endif
}


float BvHierarchy::EvalSahCost(BvhLeaf *leaf)
{
	////////////////
	//-- surface area heuristics
	if (leaf->mObjects.empty())
		return 0.0f;

	const AxisAlignedBox3 box = GetBoundingBox(leaf);
	const float area = box.SurfaceArea();
	const float viewSpaceArea = mViewCellsManager->GetViewSpaceBox().SurfaceArea();

	return EvalAbsCost(leaf->mObjects) * area / viewSpaceArea;
}


float BvHierarchy::EvalRenderCost(const ObjectContainer &objects) const
{	
	///////////////
	//-- render cost heuristics

	const float viewSpaceVol = mViewCellsManager->GetViewSpaceBox().GetVolume();

	// probability that view point lies in a view cell which sees this node
	const float p = EvalViewCellsVolume(objects) / viewSpaceVol;
    const float objRenderCost = EvalAbsCost(objects);
	
	return objRenderCost * p;
}


AxisAlignedBox3 BvHierarchy::EvalBoundingBox(const ObjectContainer &objects,
											 const AxisAlignedBox3 *parentBox) const
{
	// if there are no objects in this box, box size is set to parent box size. 
	// Question: Invalidate box instead?
	if (parentBox && objects.empty())
		return *parentBox;

	AxisAlignedBox3 box;
	box.Initialize();

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

	for (oit = objects.begin(); oit != oit_end; ++ oit)
	{
		Intersectable *obj = *oit;
		// grow bounding box to include all objects
		box.Include(obj->GetBox());
	}

	return box;
}


void BvHierarchy::CollectLeaves(BvhNode *root, vector<BvhLeaf *> &leaves) const
{
	stack<BvhNode *> nodeStack;
	nodeStack.push(root);

	while (!nodeStack.empty()) 
	{
		BvhNode *node = nodeStack.top();
		nodeStack.pop();

		if (node->IsLeaf()) 
		{
			BvhLeaf *leaf = (BvhLeaf *)node;
			leaves.push_back(leaf);
		}
		else 
		{
			BvhInterior *interior = (BvhInterior *)node;

			nodeStack.push(interior->GetBack());
			nodeStack.push(interior->GetFront());
		}
	}
}


AxisAlignedBox3 BvHierarchy::GetBoundingBox(BvhNode *node) const
{
	return node->GetBoundingBox();
}


void BvHierarchy::CollectViewCells(const ObjectContainer &objects, 
								   ViewCellContainer &viewCells,
								   const bool setCounter,
								   const bool onlyMailedRays) const
{
	ViewCell::NewMail();
	ObjectContainer::const_iterator oit, oit_end = objects.end();

	// loop through all object and collect view cell pvs of this node
	for (oit = objects.begin(); oit != oit_end; ++ oit)
	{
		// always use only mailed objects
		CollectViewCells(*oit, viewCells, true, setCounter, onlyMailedRays);
	}
}


void BvHierarchy::CollectViewCells(Intersectable *obj, 
								   ViewCellContainer &viewCells,
								   const bool useMailBoxing,
								   const bool setCounter,
								   const bool onlyMailedRays) const
{
	VssRayContainer::const_iterator rit, rit_end = obj->GetOrCreateRays()->end();

	for (rit = obj->GetOrCreateRays()->begin(); rit < rit_end; ++ rit)
	{
		VssRay *ray = (*rit);

		if (onlyMailedRays && !ray->Mailed())
			continue;

		ray->Mail();

		ViewCellContainer tmpViewCells;
		mHierarchyManager->mVspTree->GetViewCells(*ray, tmpViewCells);

		// matt: probably slow to allocate memory for view cells every time
		ViewCellContainer::const_iterator vit, vit_end = tmpViewCells.end();

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

			// store view cells
			if (!useMailBoxing || !vc->Mailed())
			{
				if (useMailBoxing)
				{
					vc->Mail();
					if (setCounter)
					{
						vc->mCounter = 0;
					}
				}
				viewCells.push_back(vc);
			}
			
			if (setCounter)
			{
				++ vc->mCounter;
			}
		}
	}
}


int BvHierarchy::CountViewCells(Intersectable *obj) const
{
	int result = 0;
	
	VssRayContainer::const_iterator rit, rit_end = obj->GetOrCreateRays()->end();

	for (rit = obj->GetOrCreateRays()->begin(); rit < rit_end; ++ rit)
	{
		VssRay *ray = (*rit);
		ViewCellContainer tmpViewCells;
	
		mHierarchyManager->mVspTree->GetViewCells(*ray, tmpViewCells);
		
		ViewCellContainer::const_iterator vit, vit_end = tmpViewCells.end();
		for (vit = tmpViewCells.begin(); vit != vit_end; ++ vit)
		{
			ViewCell *vc = *vit;

			// store view cells
			if (!vc->Mailed())
			{
				vc->Mail();
				++ result;
			}
		}
	}

	return result;
}


int BvHierarchy::CountViewCells(const ObjectContainer &objects) const
{
	int nViewCells = 0;
	ViewCell::NewMail();
	ObjectContainer::const_iterator oit, oit_end = objects.end();

	// loop through all object and collect view cell pvs of this node
	for (oit = objects.begin(); oit != oit_end; ++ oit)
	{
		nViewCells += CountViewCells(*oit);
	}

	return nViewCells;
}


void BvHierarchy::CollectDirtyCandidates(BvhSubdivisionCandidate *sc, 
										 vector<SubdivisionCandidate *> &dirtyList, 
										 const bool onlyUnmailed)
{
	BvhTraversalData &tData = sc->mParentData;
	BvhLeaf *node = tData.mNode;
	
	ViewCellContainer viewCells;
	ViewCell::NewMail();
	CollectViewCells(node->mObjects, viewCells, true, false);

	if (0) cout << "collected " << (int)viewCells.size() << " dirty candidates" << endl;
	
	// split candidates handling 
	// these view cells  are thrown into dirty list
	ViewCellContainer::const_iterator vit, vit_end = viewCells.end();

	for (vit = viewCells.begin(); vit != vit_end; ++ vit)
	{
        VspViewCell *vc = dynamic_cast<VspViewCell *>(*vit);
		VspLeaf *leaf = vc->mLeaves[0];
	
		SubdivisionCandidate *candidate = leaf->GetSubdivisionCandidate();
		
		// is this leaf still a split candidate?
		if (candidate && (!onlyUnmailed || !candidate->Mailed()))
		{
			candidate->Mail();
			candidate->SetDirty(true);
			dirtyList.push_back(candidate);
		}
	}
}


BvhNode *BvHierarchy::GetRoot() const
{
	return mRoot;
}


bool BvHierarchy::IsObjectInLeaf(BvhLeaf *leaf, Intersectable *object) const
{
	ObjectContainer::const_iterator oit =
		lower_bound(leaf->mObjects.begin(), leaf->mObjects.end(), object, ilt);
				
	// objects sorted by id
	if ((oit != leaf->mObjects.end()) && ((*oit)->GetId() == object->GetId()))
	{
		return true;
	}
	else
	{
		return false;
	}
}


BvhLeaf *BvHierarchy::GetLeaf(Intersectable *object, BvhNode *node) const
{
	// rather use the simple version
	if (!object) 
		return NULL;
	
	return object->mBvhLeaf;
	
	///////////////////////////////////////
	// start from root of tree
	
	if (node == NULL)
		node = mRoot;
	
	vector<BvhLeaf *> leaves;

	stack<BvhNode *> nodeStack;
	nodeStack.push(node);
  
	BvhLeaf *leaf = NULL;
  
	while (!nodeStack.empty())  
	{
		BvhNode *node = nodeStack.top();
		nodeStack.pop();
	
		if (node->IsLeaf()) 
		{
			leaf = dynamic_cast<BvhLeaf *>(node);

			if (IsObjectInLeaf(leaf, object))
			{
				return leaf;
			}
		} 
		else 	
		{	
			// find point
			BvhInterior *interior = dynamic_cast<BvhInterior *>(node);
        
			if (interior->GetBack()->GetBoundingBox().Includes(object->GetBox()))
			{
				nodeStack.push(interior->GetBack());
			}
			
			// search both sides as we are using bounding volumes
			if (interior->GetFront()->GetBoundingBox().Includes(object->GetBox()))
			{
				nodeStack.push(interior->GetFront());
			}
		}
	}
  
	return leaf;
}


BvhIntersectable *BvHierarchy::GetOrCreateBvhIntersectable(BvhLeaf *node)
{
	// search nodes
	std::map<BvhLeaf *, BvhIntersectable *>::const_iterator 
		it = mBvhIntersectables.find(node);

	if (it != mBvhIntersectables.end()) 
	{
		return (*it).second;
	}

	// not in map => create new entry
	BvhIntersectable *bvhObj = new BvhIntersectable(node);
	mBvhIntersectables[node] = bvhObj;

	return bvhObj;
}


bool BvHierarchy::Export(OUT_STREAM &stream)
{
	ExportNode(mRoot, stream);

	return true;
}


void BvHierarchy::ExportObjects(BvhLeaf *leaf, OUT_STREAM &stream)
{
	ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
	for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit)
	{
		stream << (*oit)->GetId() << " ";
	}
}


void BvHierarchy::ExportNode(BvhNode *node, OUT_STREAM &stream)
{
	if (node->IsLeaf())
	{
		BvhLeaf *leaf = dynamic_cast<BvhLeaf *>(node);
		const AxisAlignedBox3 box = leaf->GetBoundingBox();
		stream << "<Leaf"
			   << " min=\"" << box.Min().x << " " << box.Min().y << " " << box.Min().z << "\""
			   << " max=\"" << box.Max().x << " " << box.Max().y << " " << box.Max().z << "\""
			   << " objects=\"";
		
		//-- export objects
		ExportObjects(leaf, stream);
		
		stream << "\" />" << endl;
	}
	else
	{	
		BvhInterior *interior = dynamic_cast<BvhInterior *>(node);
		const AxisAlignedBox3 box = interior->GetBoundingBox();

		stream << "<Interior"
			   << " min=\"" << box.Min().x << " " << box.Min().y << " " << box.Min().z << "\""
			   << " max=\"" << box.Max().x << " " << box.Max().y << " " << box.Max().z
			   << "\">" << endl;

		ExportNode(interior->GetBack(), stream);
		ExportNode(interior->GetFront(), stream);

		stream << "</Interior>" << endl;
	}
}


float BvHierarchy::EvalViewCellsVolume(const ObjectContainer &objects) const
{
	float vol = 0;

	ViewCellContainer viewCells;
	// here we have to account for all view cells that can 
	// be seen from the objects
	CollectViewCells(objects, viewCells, false, false);

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

	for (vit = viewCells.begin(); vit != vit_end; ++ vit)
	{
		vol += (*vit)->GetVolume();
	}

	return vol;
}


void BvHierarchy::Initialise(const ObjectContainer &objects)
{
	AxisAlignedBox3 box = EvalBoundingBox(objects);

	///////
	//-- create new root

	BvhLeaf *bvhleaf = new BvhLeaf(box, NULL, (int)objects.size());
	bvhleaf->mObjects = objects;
	mRoot = bvhleaf;

	// compute bounding box from objects
	mBoundingBox = mRoot->GetBoundingBox();

	// associate root with current objects
	AssociateObjectsWithLeaf(bvhleaf);
}


/*
Mesh *BvHierarchy::MergeLeafToMesh()
{
	vector<BvhLeaf *> leaves;
	CollectLeaves(leaves);

	vector<BvhLeaf *>::const_iterator lit, lit_end = leaves.end();

	for (lit = leaves.begin(); lit != lit_end; ++ lit)
	{
		Mesh *mesh = MergeLeafToMesh(*lit);
	}
}*/


SubdivisionCandidate *BvHierarchy::PrepareConstruction(const VssRayContainer &sampleRays,
													   const ObjectContainer &objects)
{
	///////////////////////////////////////
	//-- we assume that we have objects sorted by their id => 
	//-- we don't have to sort them here and an binary search 
	//-- for identifying if a object is in a leaf.
	
	mBvhStats.Reset();
	mBvhStats.Start();
	mBvhStats.nodes = 1;
		
	// store pointer to this tree
	BvhSubdivisionCandidate::sBvHierarchy = this;
	
	// root and bounding box was already constructed
	BvhLeaf *bvhLeaf = dynamic_cast<BvhLeaf *>(mRoot);

	// multiply termination criterium for comparison,
	// so it can be set between zero and one and
	// no division is necessary during traversal

#if PROBABILIY_IS_BV_VOLUME
	mTermMinProbability *= mBoundingBox.GetVolume();
	// probability that bounding volume is seen
	const float prop = GetBoundingBox().GetVolume();
#else
	mTermMinProbability *= mVspTree->GetBoundingBox().GetVolume();
	// probability that volume is "seen" from the view cells
	const float prop = EvalViewCellsVolume(objects);
#endif

	// only rays intersecting objects in node are interesting
	const int nRays = AssociateObjectsWithRays(sampleRays);
	//Debug << "using " << nRays << " of " << (int)sampleRays.size() << " rays" << endl;

	// create bvh traversal data
	BvhTraversalData oData(bvhLeaf, 0, prop, nRays);

	// create sorted object lists for the first data
	if (mUseGlobalSorting)
	{
		AssignInitialSortedObjectList(oData);
	}
	

	///////////////////
	//-- add first candidate for object space partition	

	BvhSubdivisionCandidate *oSubdivisionCandidate = new BvhSubdivisionCandidate(oData);

	// evaluate priority
	EvalSubdivisionCandidate(*oSubdivisionCandidate);
	bvhLeaf->SetSubdivisionCandidate(oSubdivisionCandidate);

	mTotalCost = EvalRenderCost(objects);
	mPvsEntries = CountViewCells(objects);

	PrintSubdivisionStats(*oSubdivisionCandidate);
	
	return oSubdivisionCandidate;
}


void BvHierarchy::AssignInitialSortedObjectList(BvhTraversalData &tData)
{
	// we sort the objects as a preprocess so they don't have
	// to be sorted for each split
	for (int i = 0; i < 3; ++ i)
	{
		// create new objects
		if (!mSortedObjects[i])
		{
			mSortedObjects[i] = new SortableEntryContainer();
			CreateLocalSubdivisionCandidates(tData.mNode->mObjects, &mSortedObjects[i], true, i);
		}

		// copy list into traversal data list
		tData.mSortedObjects[i] = new ObjectContainer();
		tData.mSortedObjects[i]->reserve((int)mSortedObjects[i]->size());

		SortableEntryContainer::const_iterator oit, oit_end = mSortedObjects[i]->end();

		for (oit = mSortedObjects[i]->begin(); oit != oit_end; ++ oit)
		{
			tData.mSortedObjects[i]->push_back((*oit).mObject);
		}
	}
}


void BvHierarchy::AssignSortedObjects(const BvhSubdivisionCandidate &sc,
									  BvhTraversalData &frontData,
									  BvhTraversalData &backData)
{
	Intersectable::NewMail();

	// we sorted the objects as a preprocess so they don't have
	// to be sorted for each split
	ObjectContainer::const_iterator fit, fit_end = sc.mFrontObjects.end();

	for (fit = sc.mFrontObjects.begin(); fit != fit_end; ++ fit)
	{
		(*fit)->Mail();
	}

	for (int i = 0; i < 3; ++ i)
	{
		frontData.mSortedObjects[i] = new ObjectContainer();
		backData.mSortedObjects[i] = new ObjectContainer();

		frontData.mSortedObjects[i]->reserve((int)sc.mFrontObjects.size());
		backData.mSortedObjects[i]->reserve((int)sc.mFrontObjects.size());

		ObjectContainer::const_iterator oit, oit_end = sc.mParentData.mSortedObjects[i]->end();

		for (oit = sc.mParentData.mSortedObjects[i]->begin(); oit != oit_end; ++ oit)
		{
			if ((*oit)->Mailed())
			{
				frontData.mSortedObjects[i]->push_back(*oit);
			}
			else
			{
				backData.mSortedObjects[i]->push_back(*oit);
			}
		}
	}
}


SubdivisionCandidate *BvHierarchy::Reset(const VssRayContainer &sampleRays, 
										 const ObjectContainer &objects)
{
	// reset stats
	mBvhStats.Reset();
	mBvhStats.Start();
	mBvhStats.nodes = 1;

	// reset root
	DEL_PTR(mRoot);
	
	BvhLeaf *bvhleaf = new BvhLeaf(mBoundingBox, NULL, (int)objects.size());
	bvhleaf->mObjects = objects;
	mRoot = bvhleaf;
	
#if PROBABILIY_IS_BV_VOLUME
	mTermMinProbability *= mBoundingBox.GetVolume();
	// probability that bounding volume is seen
	const float prop = GetBoundingBox().GetVolume();
#else
	mTermMinProbability *= mVspTree->GetBoundingBox().GetVolume();
	// probability that volume is "seen" from the view cells
	const float prop = EvalViewCellsVolume(objects);
#endif

	const int nRays = CountRays(objects);
	BvhLeaf *bvhLeaf = dynamic_cast<BvhLeaf *>(mRoot);

	// create bvh traversal data
	BvhTraversalData oData(bvhLeaf, 0, prop, nRays);

	AssignInitialSortedObjectList(oData);
	

	///////////////////
	//-- add first candidate for object space partition	

	BvhSubdivisionCandidate *oSubdivisionCandidate = 
		new BvhSubdivisionCandidate(oData);

	EvalSubdivisionCandidate(*oSubdivisionCandidate);
	bvhLeaf->SetSubdivisionCandidate(oSubdivisionCandidate);

	const float viewSpaceVol = mViewCellsManager->GetViewSpaceBox().GetVolume();
	mTotalCost = (float)objects.size() * prop / viewSpaceVol;

	PrintSubdivisionStats(*oSubdivisionCandidate);

	return oSubdivisionCandidate;
}


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

	app << setprecision(4);

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

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

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

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

	app << "#AXIS_ALIGNED_SPLITS (number of axis aligned splits)\n" << splits << endl;

	app << "#N_MAXCOSTNODES  ( Percentage of leaves with terminated because of max cost ratio )\n"
		<< maxCostNodes * 100 / (double)Leaves() << endl;

	app << "#N_PMINPROBABILITYLEAVES  ( Percentage of leaves with mininum probability )\n"
		<< minProbabilityNodes * 100 / (double)Leaves() << endl;


	//////////////////////////////////////////////////
	
	app << "#N_PMAXDEPTHLEAVES ( Percentage of leaves at maximum depth )\n" 
		<<	maxDepthNodes * 100 / (double)Leaves() << endl;
	
	app << "#N_PMAXDEPTH ( Maximal reached depth )\n" << maxDepth << endl;

	app << "#N_PMINDEPTH ( Minimal reached depth )\n" << minDepth << endl;

	app << "#AVGDEPTH ( average depth )\n" << AvgDepth() << endl;

	
	////////////////////////////////////////////////////////
	
	app << "#N_PMINOBJECTSLEAVES  ( Percentage of leaves with mininum objects )\n"
		<< minObjectsNodes * 100 / (double)Leaves() << endl;

	app << "#N_MAXOBJECTREFS  ( Max number of object refs / leaf )\n" << maxObjectRefs << "\n";

	app << "#N_MINOBJECTREFS  ( Min number of object refs / leaf )\n" << minObjectRefs << "\n";

	app << "#N_EMPTYLEAFS ( Empty leafs )\n" << emptyNodes << "\n";
	
	app << "#N_PAVGOBJECTSLEAVES  ( average object refs / leaf)\n" << AvgObjectRefs() << endl;


	////////////////////////////////////////////////////////
	
	app << "#N_PMINRAYSLEAVES  ( Percentage of leaves with mininum rays )\n"
		<< minRaysNodes * 100 / (double)Leaves() << endl;

	app << "#N_MAXRAYREFS  ( Max number of ray refs / leaf )\n" << maxRayRefs << "\n";

	app << "#N_MINRAYREFS  ( Min number of ray refs / leaf )\n" << minRayRefs << "\n";
	
	app << "#N_PAVGRAYLEAVES  ( average ray refs / leaf )\n" << AvgRayRefs() << endl;
	
	app << "#N_PAVGRAYCONTRIBLEAVES  ( Average ray contribution)\n" <<
		rayRefs / (double)objectRefs << endl;

	app << "#N_PMAXRAYCONTRIBLEAVES  ( Percentage of leaves with maximal ray contribution )\n"<<
		maxRayContriNodes * 100 / (double)Leaves() << endl;

	app << "#N_PGLOBALCOSTMISSES ( Global cost misses )\n" << mGlobalCostMisses << endl;

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


// TODO: return memory usage in MB
float BvHierarchy::GetMemUsage() const
{
	return (float)(sizeof(BvHierarchy)
				   + mBvhStats.Leaves() * sizeof(BvhLeaf) 
				   + mBvhStats.Interior() * sizeof(BvhInterior)
				   ) / float(1024 * 1024);
}


void BvHierarchy::SetActive(BvhNode *node) const
{
	vector<BvhLeaf *> leaves;

	// sets the pointers to the currently active view cells
	CollectLeaves(node, leaves);
	vector<BvhLeaf *>::const_iterator lit, lit_end = leaves.end();

	for (lit = leaves.begin(); lit != lit_end; ++ lit)
	{
		(*lit)->SetActiveNode(node);
	}
}


BvhNode *BvHierarchy::SubdivideAndCopy(SplitQueue &tQueue, 
									   SubdivisionCandidate *splitCandidate)
{
	BvhSubdivisionCandidate *sc = 
		dynamic_cast<BvhSubdivisionCandidate *>(splitCandidate);
	BvhTraversalData &tData = sc->mParentData;

	BvhNode *currentNode = tData.mNode;
	BvhNode *oldNode = (BvhNode *)splitCandidate->mEvaluationHack;

	if (!oldNode->IsLeaf())
	{	
		//////////////
		//-- continue subdivision

		BvhTraversalData tFrontData;
		BvhTraversalData tBackData;
			
		BvhInterior *oldInterior = dynamic_cast<BvhInterior *>(oldNode);
		
		sc->mFrontObjects.clear();
		sc->mBackObjects.clear();

		oldInterior->GetFront()->CollectObjects(sc->mFrontObjects);
		oldInterior->GetBack()->CollectObjects(sc->mBackObjects);
		
		// evaluate the changes in render cost and pvs entries
		EvalSubdivisionCandidate(*sc, false);

		// create new interior node and two leaf node
		currentNode = SubdivideNode(*sc, tFrontData, tBackData);
	
		//oldNode->mRenderCostDecr += sc->GetRenderCostDecrease();
		//oldNode->mPvsEntriesIncr += sc->GetPvsEntriesIncr();
		
		//oldNode->mRenderCostDecr = sc->GetRenderCostDecrease();
		//oldNode->mPvsEntriesIncr = sc->GetPvsEntriesIncr();
		
		///////////////////////////
		//-- push the new split candidates on the queue
		
		BvhSubdivisionCandidate *frontCandidate = new BvhSubdivisionCandidate(tFrontData);
		BvhSubdivisionCandidate *backCandidate = new BvhSubdivisionCandidate(tBackData);

		frontCandidate->SetPriority((float)-oldInterior->GetFront()->mTimeStamp);
		backCandidate->SetPriority((float)-oldInterior->GetBack()->mTimeStamp);

		frontCandidate->mEvaluationHack = oldInterior->GetFront();
		backCandidate->mEvaluationHack = oldInterior->GetBack();

		// cross reference
		tFrontData.mNode->SetSubdivisionCandidate(frontCandidate); 
		tBackData.mNode->SetSubdivisionCandidate(backCandidate);

		//cout << "f: " << frontCandidate->GetPriority() << " b: " << backCandidate->GetPriority() << endl;
		tQueue.Push(frontCandidate);
		tQueue.Push(backCandidate);
	}

	/////////////////////////////////
	//-- node is a leaf => terminate traversal

	if (currentNode->IsLeaf())
	{
		// this leaf is no candidate for splitting anymore
		// => detach subdivision candidate
		tData.mNode->SetSubdivisionCandidate(NULL); 
		// detach node so we don't delete it with the traversal data
		tData.mNode = NULL;
	}
	
	return currentNode;
}


void BvHierarchy::CollectObjects(const AxisAlignedBox3 &box, ObjectContainer &objects)
{
	stack<BvhNode *> nodeStack;

	nodeStack.push(mRoot);

	while (!nodeStack.empty()) 
	{
		BvhNode *node = nodeStack.top();

		nodeStack.pop();

		if (node->IsLeaf()) 
		{
			BvhLeaf *leaf = (BvhLeaf *)node;

			ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();

			for (oit = leaf->mObjects.begin(); oit != oit_end; ++oit) 
			{
				Intersectable *object = *oit;
				if (Overlap(box, object->GetBox())) 
				{
					object->Mail();
					objects.push_back(object);
				}
			}
		} 
		else 
		{
			BvhInterior *interior = (BvhInterior *)node;

			if (Overlap(box, interior->GetBoundingBox()))
				nodeStack.push(interior->GetFront());

			if (Overlap(box, interior->GetBoundingBox()))
				nodeStack.push(interior->GetBack());
		}
	}
}

}