#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"


namespace GtpVisibilityPreprocessor {


#define USE_FIXEDPOINT_T 0

static float debugVol = 0;

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


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



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


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

BvhNode::BvhNode(): mParent(NULL)
{
}

BvhNode::BvhNode(const AxisAlignedBox3 &bbox):
mParent(NULL), mBoundingBox(bbox)
{
}


BvhNode::BvhNode(const AxisAlignedBox3 &bbox, BvhInterior *parent):
mBoundingBox(bbox), mParent(parent)
{
}


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)
{
}


BvhLeaf::BvhLeaf(const AxisAlignedBox3 &bbox, BvhInterior *parent):
BvhNode(bbox, parent)
{
}


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


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


BvhLeaf::~BvhLeaf() 
{ 
}


/******************************************************************/
/*              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;
}



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


BvHierarchy::BvHierarchy():
mRoot(NULL),
mTimeStamp(1)
{
	ReadEnvironment();
	mSubdivisionCandidates = new vector<SortableEntry>;
}


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

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

	DEL_PTR(mSubdivisionCandidates);

	mSubdivisionStats.close();
}


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

	//-- 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()->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 bsp tree split plane heuristics
	Environment::GetSingleton()->GetFloatValue("BvHierarchy.Termination.ct_div_ci", mCtDivCi);

	//-- partition criteria
	Environment::GetSingleton()->GetFloatValue("BvHierarchy.Construction.epsilon", mEpsilon);

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


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

	Environment::GetSingleton()->GetFloatValue("BvHierarchy.Construction.splitBorder", mSplitBorder);
	Environment::GetSingleton()->GetFloatValue(
		"BvHierarchy.Construction.renderCostDecreaseWeight", mRenderCostDecreaseWeight);
	

	//-- 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 << "subdivision stats log: " << subdivisionStatsLog << endl;
	
	Debug << "split borders: " << mSplitBorder << endl;
	Debug << "render cost decrease weight: " << mRenderCostDecreaseWeight << endl;
	Debug << endl;
}


void AssociateObjectsWithLeaf(BvhLeaf *leaf)
{
	ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
	for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit)
	{
		(*oit)->mBvhLeaf = leaf;
	}
}


BvhInterior *BvHierarchy::SubdivideNode(const ObjectContainer &frontObjects,
										const ObjectContainer &backObjects,
										const BvhTraversalData &tData,
										BvhTraversalData &frontData,
										BvhTraversalData &backData)
{
	BvhLeaf *leaf = tData.mNode;
	
	// two new leaves
    mBvhStats.nodes += 2;

	// add the new nodes to the tree
	BvhInterior *node = new BvhInterior(tData.mBoundingBox, leaf->GetParent());
	//cout << "bbox: " << tData.mBoundingBox << endl;


	//-- the front and back traversal data is filled with the new values

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

	frontData.mBoundingBox = ComputeBoundingBox(frontObjects, &(tData.mBoundingBox));
	backData.mBoundingBox = ComputeBoundingBox(backObjects, &(tData.mBoundingBox));
	
	/////////////
	//-- create front and back leaf

	BvhLeaf *back = 
		new BvhLeaf(backData.mBoundingBox, node, (int)backObjects.size());
	BvhLeaf *front = 
		new BvhLeaf(frontData.mBoundingBox, node, (int)frontObjects.size());

	BvhInterior *parent = leaf->GetParent();


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

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

	++ mBvhStats.splits;


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

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

	back->mObjects = backObjects;
	front->mObjects = frontObjects;

	AssociateObjectsWithLeaf(back);
	AssociateObjectsWithLeaf(front);
   
	// compute probability, i.e., volume of seen view cells
	frontData.mProbability = EvalViewCellsVolume(frontObjects);
	backData.mProbability = EvalViewCellsVolume(backObjects);

	return node;
}


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

	BvhNode *newNode = tData.mNode;

	if (!LocalTerminationCriteriaMet(tData) && !globalCriteriaMet)
	{	
		BvhTraversalData tFrontData;
		BvhTraversalData tBackData;

		//-- continue subdivision
		
		// create new interior node and two leaf node
		newNode = SubdivideNode(sc->mFrontObjects,
								sc->mBackObjects,
								tData, 
								tFrontData, 
								tBackData);
	
		const int maxCostMisses = sc->mMaxCostMisses;

        // how often was max cost ratio missed in this branch?
		tFrontData.mMaxCostMisses = maxCostMisses;
		tBackData.mMaxCostMisses = maxCostMisses;
		
		// decrease the weighted average cost of the subdivisoin
		mTotalCost -= sc->GetRenderCostDecrease();

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

		tQueue.Push(frontCandidate);
		tQueue.Push(backCandidate);

		// delete old leaf node
		DEL_PTR(tData.mNode);
	}


	//-- terminate traversal
	if (newNode->IsLeaf())
	{
		EvaluateLeafStats(tData);
        
		const bool mStoreRays= true;

		//-- store additional info
		if (mStoreRays)
		{
			BvhLeaf *leaf = dynamic_cast<BvhLeaf *>(newNode);
			CollectRays(leaf->mObjects, leaf->mVssRays);
		}
	}
	
	tData.Clear(); // cleanup
	
	return newNode;
}


void BvHierarchy::EvalSubdivisionCandidate(BvhSubdivisionCandidate &splitCandidate)
{
	// compute best object partition
	const float ratio =	SelectObjectPartition(
							splitCandidate.mParentData, 
							splitCandidate.mFrontObjects, 
							splitCandidate.mBackObjects);
	
	BvhLeaf *leaf = splitCandidate.mParentData.mNode;

	// cost ratio violated?
	const bool maxCostRatioViolated = ratio < mTermMaxCostRatio;

	splitCandidate.mMaxCostMisses = maxCostRatioViolated ? 
		splitCandidate.mParentData.mMaxCostMisses : 
		splitCandidate.mParentData.mMaxCostMisses + 1;

	const float viewSpaceVol = mVspTree->GetBoundingBox().GetVolume();
	const float oldRenderCost = 
		splitCandidate.mParentData.mProbability * (float)leaf->mObjects.size() / viewSpaceVol;

	// compute global decrease in render cost
	float newRenderCost = EvalRenderCost(splitCandidate.mParentData,
									     splitCandidate.mFrontObjects, 
										 splitCandidate.mBackObjects);

	newRenderCost /=  viewSpaceVol;

	const float renderCostDecr = oldRenderCost - newRenderCost;

	//Debug << "render cost decr: " << renderCostDecr << endl;
	splitCandidate.SetRenderCostDecrease(renderCostDecr);

#if 0
	const float priority = (float)-data.mDepth;
#else	
	// take render cost of node into account 
	// otherwise danger of being stuck in a local minimum!!
	const float factor = mRenderCostDecreaseWeight;
	const float priority = factor * renderCostDecr + (1.0f - factor) * oldRenderCost;

#endif

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


inline bool BvHierarchy::LocalTerminationCriteriaMet(const BvhTraversalData &data) const
{
	// matt: TODO
	return ( 0
		|| (data.mNode->mObjects.size() < mTermMinObjects)
		|| (data.mProbability <= mTermMinProbability)
		|| (data.mDepth >= mTermMaxDepth)
		 );
}


inline bool BvHierarchy::GlobalTerminationCriteriaMet(const BvhTraversalData &data) const
{
	// matt: TODO
	return (0
		|| (mBvhStats.Leaves() >= mTermMaxLeaves)
		|| (mGlobalCostMisses >= mTermGlobalCostMissTolerance)
		//|| mOutOfMemory 
		);
}


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

	if (data.mDepth >= mTermMaxDepth)
	{
        ++ mBvhStats.maxDepthNodes;
		//Debug << "new max depth: " << mVspStats.maxDepthNodes << endl;
	}

	if (data.mDepth < mTermMaxDepth)
	{
        ++ mBvhStats.minDepthNodes;
	}

	if (data.mProbability <= mTermMinProbability)
		++ mBvhStats.minProbabilityNodes;
	
	// accumulate depth to compute average depth
	mBvhStats.accumDepth += data.mDepth;
 
	if ((int)(leaf->mObjects.size()) < mTermMinObjects)
	     ++ mBvhStats.minObjectsNodes;
 
	if ((int)(leaf->mObjects.size()) > mBvhStats.maxObjectRefs)
		mBvhStats.maxObjectRefs = (int)leaf->mObjects.size();
}


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;
		AxisAlignedBox3 box = obj->GetBox();

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

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

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

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


float BvHierarchy::EvalLocalCostHeuristics(const BvhTraversalData &tData,
										   const int axis,
										   ObjectContainer &objectsFront,
										   ObjectContainer &objectsBack)
{
	// prepare the heuristics by setting mailboxes and counters.
	const float totalVol = PrepareHeuristics(tData, axis);

	// go through the lists, count the number of objects left and right
	// and evaluate the cost funcion

	// local helper variables
	float volLeft = 0;
	float volRight = totalVol;

	int nObjectsLeft = 0;

	const int nTotalObjects = (int)tData.mNode->mObjects.size();
	const float viewSpaceVol = mVspTree->GetBoundingBox().GetVolume();

	vector<SortableEntry>::const_iterator currentPos =
		mSubdivisionCandidates->begin();

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

	float volBack = volLeft;
	float volFront = volRight;

	float newRenderCost = nTotalObjects * totalVol;


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

	vector<SortableEntry>::const_iterator cit, 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);

		++ nObjectsLeft;
		
		const int nObjectsRight = nTotalObjects - nObjectsLeft;

		// the heuristics
	    const float sum = volLeft * (float)nObjectsLeft + 
						  volRight * (float)nObjectsRight;

		if (sum < newRenderCost)
		{
			newRenderCost = sum;

			volBack = volLeft;
			volFront = volRight;

			// objects belongs 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);

	tData.mNode->mObjects.end();

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

	Debug << "\n§§§§ eval local cost §§§§" << 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;

	return ratio;
}


void BvHierarchy::SortSubdivisionCandidates(const BvhTraversalData &tData,
											const int axis)											
{
	mSubdivisionCandidates->clear();

	//RayInfoContainer *rays = tData.mRays;
	BvhLeaf *leaf = tData.mNode;

	// compute requested size
	const int requestedSize = (int)leaf->mObjects.size() * 2;
	
	// creates a sorted split candidates array
	if (mSubdivisionCandidates->capacity() > 500000 &&
		requestedSize < (int)(mSubdivisionCandidates->capacity() / 10) )
	{
    	delete mSubdivisionCandidates;
   		mSubdivisionCandidates = new vector<SortableEntry>;
	}

	mSubdivisionCandidates->reserve(requestedSize);

	//-- insert object queries
	//-- These queries can induce a change in pvs size.
	//-- Note that they cannot induce a change in view cell volume, as
	//-- there is no ray associated with these events!!

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

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

		mSubdivisionCandidates->push_back(SortableEntry(object, midPt));
	}

	stable_sort(mSubdivisionCandidates->begin(), mSubdivisionCandidates->end());
}


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


float BvHierarchy::PrepareHeuristics(const BvhTraversalData &tData, const int axis)
{	
	//-- sort so we can use a sweep from right to left
	SortSubdivisionCandidates(tData, axis);

	float vol = 0;
	BvhLeaf *leaf = tData.mNode;

	// collect and mark the view cells as belonging to front pvs
	ViewCellContainer viewCells;
	CollectViewCells(tData.mNode->mObjects, viewCells, true);

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

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

	// mail view cells on the left side
	ViewCell::NewMail();
	
	// mail the objects on the left side
	Intersectable::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);


	/// 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;

		const float vol = viewCell->GetVolume();

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

			// we now see view cell from both nodes 
			// => add volume to left node
			volLeft += vol;
			//volRight -= 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)
{
	ObjectContainer nFrontObjects[3];
	ObjectContainer nBackObjects[3];

	float nCostRatio[3];

	// create bounding box of node geometry
	AxisAlignedBox3 box = tData.mBoundingBox;
		
	int sAxis = 0;
	int bestAxis = -1;

	if (mOnlyDrivingAxis)
	{
		sAxis = box.Size().DrivingAxis();
	}
	
	// -- evaluate split cost for all three axis
	
	for (int axis = 0; axis < 3; ++ axis)
	{
		if (!mOnlyDrivingAxis || (axis == sAxis))
		{
			if (mUseCostHeuristics)
			{
				//-- partition objects using heuristics
				nCostRatio[axis] =
					EvalLocalCostHeuristics(
											tData,
											axis,
											nFrontObjects[axis],
											nBackObjects[axis]);
			}
			else
			{
				nCostRatio[axis] =
					EvalLocalObjectPartition(
											 tData,
											 axis,
											 nFrontObjects[axis],
											 nBackObjects[axis]);
			}

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

	//-- assign values

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

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


void BvHierarchy::AssociateObjectsWithRays(const VssRayContainer &rays)
{

	VssRayContainer::const_iterator rit, rit_end = rays.end();

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

		if (ray->mTerminationObject)
		{
			ray->mTerminationObject->mVssRays.push_back(ray);
		}

		if (0 && ray->mOriginObject)
		{
			ray->mOriginObject->mVssRays.push_back(ray);
		}
	}
}


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

	mSubdivisionStats 
			<< "#Leaves\n" << mBvhStats.Leaves()
			<< "#RenderCostDecrease\n" << costDecr << endl 
			<< "#TotalRenderCost\n" << mTotalCost << endl;
			//<< "#AvgRenderCost\n" << avgRenderCost << 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->mVssRays.end();

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

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


float BvHierarchy::EvalRenderCost(const BvhTraversalData &tData,
								  const ObjectContainer &objectsFront,
								  const ObjectContainer &objectsBack) const
{
	BvhLeaf *leaf = tData.mNode;

	// probability that view point lies in a view cell which sees this node
	const float pFront = EvalViewCellsVolume(objectsFront);
	const float pBack = EvalViewCellsVolume(objectsBack);
		
	const int totalObjects = (int)leaf->mObjects.size();
	const int nObjectsFront = (int)objectsFront.size();
	const int nObjectsBack = (int)objectsBack.size();

	//-- pvs rendering heuristics
	const float newRenderCost = nObjectsFront * pFront + 
								nObjectsBack * pBack;

	const float viewSpaceVol = mVspTree->GetBoundingBox().GetVolume();
	Debug << "\n***** eval render cost *********\n" 
		  << "back p: " << pBack / viewSpaceVol << " front p " << pFront / viewSpaceVol << endl
		  << "new rc: " << newRenderCost / viewSpaceVol << endl;
		 

	return newRenderCost;
}


AxisAlignedBox3 BvHierarchy::ComputeBoundingBox(const ObjectContainer &objects,
												const AxisAlignedBox3 *parentBox)
{
	if (parentBox && objects.empty())
		return *parentBox;

	AxisAlignedBox3 box;
	box.Initialize();

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

	//-- compute bounding box
	for (oit = objects.begin(); oit != oit_end; ++ oit)
	{
		Intersectable *obj = *oit;

		// compute bounding box of view space
		box.Include(obj->GetBox());
	}

	return box;
}


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

	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
{
	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)
	{
		CollectViewCells(*oit, viewCells, true, setCounter);
	}
}


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

	for (rit = obj->mVssRays.begin(); rit < rit_end; ++ rit)
	{
		VssRay *ray = (*rit);
		ViewCellContainer tmpViewCells;
	
		mVspTree->GetViewCells(*ray, tmpViewCells);

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

		for (vit = tmpViewCells.begin(); vit != vit_end; ++ vit)
		{
			VspViewCell *vc = dynamic_cast<VspViewCell *>(*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;
			}
		}
	}
}


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

	// 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->mLeaf;
		dirtyList.push_back(leaf->GetSubdivisionCandidate());
	}
}


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->mBvhLeaf)
	{
		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(BvhNode *node)
{
	// search nodes
	std::map<BvhNode *, 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;
}


/*
int BvHierarchy::UpdateViewCellsPvs(BvhLeaf *leaf, 
								const RayInfoContainer &rays) const

{
	MailablePvsData::NewMail();
	
	ViewCellContainer touchedViewCells;
	CollectTouchedViewCells(rays, touchedViewCells);

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

	for (oit = leaf->mObjects.begin(); oit < oit_end; ++ oit)
	{
		Intersectable *obj = *oit;
		ViewCellContainer::const_iterator vit, vit_end = touchedViewCells.end();

		// traverse through view cells and classify them according
		// to them being seen from to back / front / front and back node
		for (vit = touchedViewCells.begin(); vit != vit_end; ++ vit)
		{
			ViewCell *vc = *vit;
			float contri;
			AddViewCellToObjectPvs(obj, vc, contri, true);
		}
	}

	return 0;
}


int BvHierarchy::RemoveParentViewCellsPvs(BvhLeaf *leaf, 
									  const RayInfoContainer &rays
									  ) const

{
	MailablePvsData::NewMail();
	
	ViewCellContainer touchedViewCells;
	CollectTouchedViewCells(rays, touchedViewCells);

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

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

		// traverse through view cells and classify them according
		// to them being seen from to back / front / front and back node
        ViewCellContainer::const_iterator vit, vit_end = touchedViewCells.end();

		for (vit = touchedViewCells.begin(); vit != vit_end; ++ vit)
		{
			ViewCell *vc = *vit;
			
			MailablePvsData *vdata = obj->mViewCellPvs.Find(vc);

			if (vdata && !vdata->Mailed())
			{
				vdata->Mail();
				obj->mViewCellPvs.RemoveSample(vc, 1);
			}
		}
	}

	return 0;
}
*/

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;
	CollectViewCells(objects, viewCells);

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

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

	return vol;
}


SubdivisionCandidate *BvHierarchy::PrepareConstruction(const VssRayContainer &sampleRays,
													   const ObjectContainer &objects
													   //,AxisAlignedBox3 *forcedObjectSpace
													   )
{
	// note matt: we assume that we have objects sorted by their id

	// store pointer to this tree
	BvhSubdivisionCandidate::sBvHierarchy = this;
	mBvhStats.nodes = 1;

	// compute bounding box from objects
	mBoundingBox = ComputeBoundingBox(objects);

	mTermMinProbability *= mBoundingBox.GetVolume();
	mGlobalCostMisses = 0;
	
	//-- create new root

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

	// only rays intersecting objects in node are interesting
	AssociateObjectsWithRays(sampleRays);
	// associate root with current objects
	AssociateObjectsWithLeaf(bvhleaf);

	//-- add first candidate for object space partition
	
	// probabilty is voume of all "seen" view cells
#if 1
	const float prop = EvalViewCellsVolume(bvhleaf->mObjects);
#else
	const float prop = GetBoundingBox().GetVolume();
#endif

	// create bvh traversal data
	BvhTraversalData oData(bvhleaf, 0, mBoundingBox, prop);

	//-- first split candidate
	BvhSubdivisionCandidate *oSubdivisionCandidate = 
		new BvhSubdivisionCandidate(oData);

	//UpdateViewCellsPvs(kdleaf, rays);

	EvalSubdivisionCandidate(*oSubdivisionCandidate);

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

	PrintSubdivisionStats(*oSubdivisionCandidate);

	return oSubdivisionCandidate;
}


bool BvHierarchy::AddLeafToPvs(BvhLeaf *leaf, 
							   ViewCell *vc, 
							   const float pdf, 
							   float &contribution)
{
	// add kd intersecable to pvs
	BvhIntersectable *bvhObj = GetOrCreateBvhIntersectable(leaf);
	
	return vc->AddPvsSample(bvhObj, pdf, contribution);
}


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_PMINDEPTHLEAVES ( Percentage of leaves at minimum depth )\n" 
		<<	minDepthNodes * 100 / (double)Leaves() << endl;

	app << "#N_PMAXDEPTHLEAVES ( Percentage of leaves at maximum depth )\n" 
		<<	maxDepthNodes * 100 / (double)Leaves() << 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_PMINOBJECTSLEAVES  ( Percentage of leaves with mininum objects )\n"
		<< minObjectsNodes * 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_INVALIDLEAVES (number of invalid leaves )\n" << invalidLeaves << endl;

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

	//app << "#N_RAYS (number of rays / leaf)\n" << AvgRays() << endl;
	
	app << "========== END OF VspTree statistics ==========\n";
}


}