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

#include "ViewCell.h"
#include "Plane3.h"
#include "VspOspTree.h"
#include "Mesh.h"
#include "common.h"
#include "Environment.h"
#include "Polygon3.h"
#include "Ray.h"
#include "AxisAlignedBox3.h"
#include "Exporter.h"
#include "Plane3.h"
#include "ViewCellsManager.h"
#include "Beam.h"
#include "KdTree.h"


namespace GtpVisibilityPreprocessor {

#define USE_FIXEDPOINT_T 0


//-- static members

int VspTree::sFrontId = 0;
int VspTree::sBackId = 0;
int VspTree::sFrontAndBackId = 0;



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

	return (float)pvs;
}


int VspNode::sMailId = 1;



void VspTreeStatistics::Print(ostream &app) const
{
#if TODO
	app << "===== BspTree 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 << "#N_POLYSPLITS ( Number of polygon splits )\n" << polySplits << "\n";

	app << "#AXIS_ALIGNED_SPLITS (number of axis aligned splits)\n" << splits[0] + splits[1] + splits[2] << endl;

	app << "#N_SPLITS ( Number of splits in axes x y z)\n";

	for (int i = 0; i < 3; ++ i)
		app << splits[i] << " ";
	app << endl;

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

	app << "#N_PMINPVSLEAVES  ( Percentage of leaves with mininimal PVS )\n" 
		<< minPvsNodes * 100 / (double)Leaves() << endl;

	app << "#N_PMINRAYSLEAVES  ( Percentage of leaves with minimal number of rays)\n" 
		<< minRaysNodes * 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_PMAXRAYCONTRIBLEAVES  ( Percentage of leaves with maximal ray contribution )\n" 
		<<	maxRayContribNodes * 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_INPUTPOLYGONS (number of input polygons )\n" << polys << endl;

	app << "#N_INVALIDLEAVES (number of invalid leaves )\n" << invalidLeaves << endl;

	app << "#N_RAYS (number of rays / leaf)\n" << AvgRays() << endl;
	//app << "#N_PVS: " << pvs << endl;

	app << "#N_ROUTPUT_INPUT_POLYGONS ( ratio polygons after subdivision / input polygons )\n" <<
		 (polys + polySplits) / (double)polys << endl;
	
	app << "===== END OF BspTree statistics ==========\n";
#endif
}


/******************************************************************/
/*                  class VspNode implementation                  */
/******************************************************************/


VspNode::VspNode(): 
mParent(NULL), mTreeValid(true), mTimeStamp(0)
{}


VspNode::VspNode(VspInterior *parent): 
mParent(parent), mTreeValid(true)
{}


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


VspInterior *VspNode::GetParent() 
{ 
	return mParent; 
}


void VspNode::SetParent(VspInterior *parent)
{
	mParent = parent;
}


bool VspNode::IsSibling(VspNode *n) const
{
	return  ((this != n) && mParent && 
			 (mParent->GetFront() == n) || (mParent->GetBack() == n));
}


int VspNode::GetDepth() const
{
	int depth = 0;
	VspNode *p = mParent;
	
	while (p)
	{
		p = p->mParent;
		++ depth;
	}

	return depth;
}


bool VspNode::TreeValid() const
{
	return mTreeValid;
}


void VspNode::SetTreeValid(const bool v)
{
	mTreeValid = v;
}


/****************************************************************/
/*              class VspInterior implementation                */
/****************************************************************/


VspInterior::VspInterior(const AxisAlignedPlane &plane): 
mPlane(plane), mFront(NULL), mBack(NULL)
{}


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


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


VspNode *VspInterior::GetBack() 
{
	return mBack;
}


VspNode *VspInterior::GetFront() 
{
	return mFront;
}


AxisAlignedPlane VspInterior::GetPlane() const
{
	return mPlane;
}


float VspInterior::GetPosition() const
{
	return mPlane.mPosition;
}


int VspInterior::GetAxis() const
{
	return mPlane.mAxis;
}


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


void VspInterior::SetupChildLinks(VspNode *b, VspNode *f) 
{
    mBack = b;
    mFront = f;
}


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


void VspInterior::SetBoundingBox(const AxisAlignedBox3 &box)
{
	mBoundingBox = box;
}


int VspInterior::Type() const
{
	return Interior;
}

/****************************************************************/
/*                  class VspLeaf implementation                */
/****************************************************************/


VspLeaf::VspLeaf(): mViewCell(NULL), mPvs(NULL)
{
}


VspLeaf::~VspLeaf()
{
	DEL_PTR(mPvs);
}


int VspLeaf::Type() const
{
	return Leaf;
}


VspLeaf::VspLeaf(ViewCellLeaf *viewCell): 
mViewCell(viewCell)
{
}


VspLeaf::VspLeaf(VspInterior *parent): 
VspNode(parent), mViewCell(NULL), mPvs(NULL)
{}



VspLeaf::VspLeaf(VspInterior *parent, ViewCellLeaf *viewCell): 
VspNode(parent), mViewCell(viewCell), mPvs(NULL)
{
}

ViewCellLeaf *VspLeaf::GetViewCell() const
{
	return mViewCell;
}

void VspLeaf::SetViewCell(ViewCellLeaf *viewCell)
{
	mViewCell = viewCell;
}


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


/******************************************************************************/
/*                       class VspTree implementation                      */
/******************************************************************************/


VspTree::VspTree():
mRoot(NULL),
mOutOfBoundsCell(NULL),
mStoreRays(false),
mUseRandomAxis(false),
mTimeStamp(1)
{
	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("VspTree.Termination.maxDepth", mTermMaxDepth);
	Environment::GetSingleton()->GetIntValue("VspTree.Termination.minPvs", mTermMinPvs);
	Environment::GetSingleton()->GetIntValue("VspTree.Termination.minRays", mTermMinRays);
	Environment::GetSingleton()->GetFloatValue("VspTree.Termination.minProbability", mTermMinProbability);
	Environment::GetSingleton()->GetFloatValue("VspTree.Termination.maxRayContribution", mTermMaxRayContribution);
	Environment::GetSingleton()->GetFloatValue("VspTree.Termination.maxCostRatio", mTermMaxCostRatio);
	Environment::GetSingleton()->GetIntValue("VspTree.Termination.missTolerance", mTermMissTolerance);
	Environment::GetSingleton()->GetIntValue("VspTree.Termination.maxViewCells", mMaxViewCells);

	//-- max cost ratio for early tree termination
	Environment::GetSingleton()->GetFloatValue("VspTree.Termination.maxCostRatio", mTermMaxCostRatio);

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

	// HACK//mTermMinPolygons = 25;

	//-- factors for bsp tree split plane heuristics
	Environment::GetSingleton()->GetFloatValue("VspTree.Termination.ct_div_ci", mCtDivCi);

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

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

	Environment::GetSingleton()->GetBoolValue("VspTree.useCostHeuristics", mUseCostHeuristics);
	Environment::GetSingleton()->GetBoolValue("VspTree.simulateOctree", mCirculatingAxis);
	Environment::GetSingleton()->GetBoolValue("VspTree.useRandomAxis", mUseRandomAxis);
	Environment::GetSingleton()->GetIntValue("VspTree.nodePriorityQueueType", mNodePriorityQueueType);
	
	char subdivisionStatsLog[100];
	Environment::GetSingleton()->GetStringValue("VspTree.subdivisionStats", subdivisionStatsLog);
	mSubdivisionStats.open(subdivisionStatsLog);

	Environment::GetSingleton()->GetFloatValue("VspTree.Construction.minBand", mMinBand);
	Environment::GetSingleton()->GetFloatValue("VspTree.Construction.maxBand", mMaxBand);
	

	//-- debug output

	Debug << "******* VSP BSP options ******** " << endl;
    Debug << "max depth: " << mTermMaxDepth << endl;
	Debug << "min PVS: " << mTermMinPvs << endl;
	Debug << "min probabiliy: " << mTermMinProbability << endl;
	Debug << "min rays: " << mTermMinRays << endl;
	Debug << "max ray contri: " << mTermMaxRayContribution << endl;
	Debug << "max cost ratio: " << mTermMaxCostRatio << endl;
	Debug << "miss tolerance: " << mTermMissTolerance << endl;
	Debug << "max view cells: " << mMaxViewCells << 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 << "use random axis: " << mUseRandomAxis << endl;
	Debug << "priority queue type: " << mNodePriorityQueueType << endl;
	Debug << "circulating axis: " << mCirculatingAxis << endl;
	Debug << "minband: " << mMinBand << endl;
	Debug << "maxband: " << mMaxBand << endl;
	

	mSplitCandidates = new vector<SortableEntry>;

	Debug << endl;
}


VspViewCell *VspTree::GetOutOfBoundsCell()
{
	return mOutOfBoundsCell;
}


VspViewCell *VspTree::GetOrCreateOutOfBoundsCell()
{
	if (!mOutOfBoundsCell)
	{
		mOutOfBoundsCell = new VspViewCell();
		mOutOfBoundsCell->SetId(-1);
		mOutOfBoundsCell->SetValid(false);
	}

	return mOutOfBoundsCell;
}


const VspTreeStatistics &VspTree::GetStatistics() const
{
	return mVspStats;
}


VspTree::~VspTree()
{
	DEL_PTR(mRoot);
	DEL_PTR(mSplitCandidates);
}


void VspTree::PrepareConstruction(const VssRayContainer &sampleRays,
								  AxisAlignedBox3 *forcedBoundingBox) 
{
	mVspStats.nodes = 1;
	mBoundingBox.Initialize(); 	// initialise vsp tree bounding box

	if (forcedBoundingBox)
		mBoundingBox = *forcedBoundingBox;
	
	VssRayContainer::const_iterator rit, rit_end = sampleRays.end();

	Intersectable::NewMail();

	//-- compute bounding box
	for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
	{
		VssRay *ray = *rit;

		// compute bounding box of view space
		if (!forcedBoundingBox)
		{
			mBoundingBox.Include(ray->GetTermination());
			mBoundingBox.Include(ray->GetOrigin());
		}
	}

	mTermMinProbability *= mBoundingBox.GetVolume();
	mGlobalCostMisses = 0;
}


void VspTree::AddSubdivisionStats(const int viewCells,
								  const float renderCostDecr,
								  const float splitCandidateCost,
								  const float totalRenderCost,
									 const float avgRenderCost)
{
	mSubdivisionStats 
			<< "#ViewCells\n" << viewCells << endl
			<< "#RenderCostDecrease\n" << renderCostDecr << endl 
			<< "#SplitCandidateCost\n" << splitCandidateCost << endl
			<< "#TotalRenderCost\n" << totalRenderCost << endl
			<< "#AvgRenderCost\n" << avgRenderCost << endl;
}


// TODO: return memory usage in MB
float VspTree::GetMemUsage() const
{
	return (float)
		 (sizeof(VspTree) + 
		  mVspStats.Leaves() * sizeof(VspLeaf) + 
		  mCreatedViewCells * sizeof(VspViewCell) +
		  mVspStats.pvs * sizeof(ObjectPvsData) +
		  mVspStats.Interior() * sizeof(VspInterior) +
		  mVspStats.accumRays * sizeof(RayInfo)) / (1024.0f * 1024.0f);
}


bool VspTree::LocalTerminationCriteriaMet(const VspTraversalData &data) const
{
	return
		(((int)data.mRays->size() <= mTermMinRays) ||
		 (data.mPvs <= mTermMinPvs)   ||
		 (data.mProbability <= mTermMinProbability) ||
		 (data.GetAvgRayContribution() > mTermMaxRayContribution) ||
		 (data.mDepth >= mTermMaxDepth));
}


bool VspTree::GlobalTerminationCriteriaMet(const VspTraversalData &data) const
{
	return
		(mOutOfMemory || 
		(mVspStats.Leaves() >= mMaxViewCells) || 
		(mGlobalCostMisses >= mTermGlobalCostMissTolerance));
}


VspNode *VspTree::Subdivide(SplitQueue &tQueue,
							VspSplitCandidate &splitCandidate,
							const bool globalCriteriaMet)
{
	VspTraversalData &tData = splitCandidate.mParentData;

	VspNode *newNode = tData.mNode;

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

		//-- continue subdivision
		
		// create new interior node and two leaf node
		const AxisAlignedPlane splitPlane = splitCandidate.mSplitPlane;
		newNode = SubdivideNode(splitPlane, tData, tFrontData, tBackData);
	
		const int maxCostMisses = splitCandidate.mMaxCostMisses;


		// how often was max cost ratio missed in this branch?
		tFrontData.mMaxCostMisses = maxCostMisses;
		tBackData.mMaxCostMisses = maxCostMisses;
			
		//-- statistics
		if (1)
		{
			const float cFront = (float)tFrontData.mPvs * tFrontData.mProbability;
			const float cBack = (float)tBackData.mPvs * tBackData.mProbability;
			const float cData = (float)tData.mPvs * tData.mProbability;
	
			const float costDecr = 
				(cFront + cBack - cData) / mBoundingBox.GetVolume();

			mTotalCost += costDecr;
			mTotalPvsSize += tFrontData.mPvs + tBackData.mPvs - tData.mPvs;

			AddSubdivisionStats(mVspStats.Leaves(),
								-costDecr,
								splitCandidate.GetPriority(),
								mTotalCost,
								(float)mTotalPvsSize / (float)mVspStats.Leaves());
		}

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

		EvalSplitCandidate(tFrontData, *frontCandidate);
		EvalSplitCandidate(tBackData, *backCandidate);

		tQueue.push(frontCandidate);
		tQueue.push(backCandidate);

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


	//-- terminate traversal and create new view cell
	if (newNode->IsLeaf())
	{
		VspLeaf *leaf = dynamic_cast<VspLeaf *>(newNode);
	
		VspViewCell *viewCell = new VspViewCell();
        leaf->SetViewCell(viewCell);
		
		//-- update pvs
		int conSamp = 0;
		float sampCon = 0.0f;
		AddToPvs(leaf, *tData.mRays, sampCon, conSamp);

		// update scalar pvs size value
		mViewCellsManager->SetScalarPvsSize(viewCell, viewCell->GetPvs().GetSize());

		mVspStats.contributingSamples += conSamp;
		mVspStats.sampleContributions +=(int) sampCon;

		//-- store additional info
		if (mStoreRays)
		{
			RayInfoContainer::const_iterator it, it_end = tData.mRays->end();
			for (it = tData.mRays->begin(); it != it_end; ++ it)
			{
				(*it).mRay->Ref();			
				leaf->mVssRays.push_back((*it).mRay);
			}
		}
		
		viewCell->mLeaf = leaf;

		viewCell->SetVolume(tData.mProbability);
        leaf->mProbability = tData.mProbability;

		// finally evaluate stats until this leaf
		EvaluateLeafStats(tData);
	}

	//-- cleanup
	tData.Clear();
	
	return newNode;
}


void VspTree::EvalSplitCandidate(VspTraversalData &tData,
								 VspSplitCandidate &splitData)
{
	float frontProb;
	float backtProb;
	
	VspLeaf *leaf = dynamic_cast<VspLeaf *>(tData.mNode);
	
	// compute locally best split plane
	const bool success = 
		SelectPlane(tData, splitData.mSplitPlane,
					frontProb, backtProb);

	//TODO
	// compute global decrease in render cost
	splitData.mPriority = EvalRenderCostDecrease(splitData.mSplitPlane, tData);
	splitData.mParentData = tData;
	splitData.mMaxCostMisses = success ? tData.mMaxCostMisses : tData.mMaxCostMisses + 1;
}


VspInterior *VspTree::SubdivideNode(const AxisAlignedPlane &splitPlane,
									VspTraversalData &tData,
									VspTraversalData &frontData,
									VspTraversalData &backData)
{
	VspLeaf *leaf = dynamic_cast<VspLeaf *>(tData.mNode);
	
	//-- the front and back traversal data is filled with the new values
	frontData.mDepth = tData.mDepth + 1;
	frontData.mRays = new RayInfoContainer();
	
	backData.mDepth = tData.mDepth + 1;
	backData.mRays = new RayInfoContainer();
	
	//-- subdivide rays
	SplitRays(splitPlane,
			  *tData.mRays,
			  *frontData.mRays,
			  *backData.mRays);

	//-- compute pvs
	frontData.mPvs = ComputePvsSize(*frontData.mRays);
	backData.mPvs = ComputePvsSize(*backData.mRays);

	// split front and back node geometry and compute area
	tData.mBoundingBox.Split(splitPlane.mAxis, splitPlane.mPosition, 
							 frontData.mBoundingBox, backData.mBoundingBox);


	frontData.mProbability = frontData.mBoundingBox.GetVolume();
	backData.mProbability = tData.mProbability - frontData.mProbability;

	
    ///////////////////////////////////////////
	// subdivide further

	// store maximal and minimal depth
	if (tData.mDepth > mVspStats.maxDepth)
	{
		Debug << "max depth increases to " << tData.mDepth << " at " << mVspStats.Leaves() << " leaves" << endl;
		mVspStats.maxDepth = tData.mDepth;
	}

	mVspStats.nodes += 2;

    
	VspInterior *interior = new VspInterior(splitPlane);

#ifdef _DEBUG
	Debug << interior << endl;
#endif


	//-- create front and back leaf

	VspInterior *parent = leaf->GetParent();

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

	// and setup child links
	interior->SetupChildLinks(new VspLeaf(interior), new VspLeaf(interior));
	// add bounding box
	interior->SetBoundingBox(tData.mBoundingBox);

	frontData.mNode = interior->GetFront();
	backData.mNode = interior->GetBack();

	interior->mTimeStamp = mTimeStamp ++;
	
	return interior;
}


void VspTree::AddToPvs(VspLeaf *leaf,
						  const RayInfoContainer &rays,
						  float &sampleContributions,
						  int &contributingSamples)
{
	sampleContributions = 0;
	contributingSamples = 0;
  
	RayInfoContainer::const_iterator it, it_end = rays.end();
  
	ViewCellLeaf *vc = leaf->GetViewCell();
  
	// add contributions from samples to the PVS
	for (it = rays.begin(); it != it_end; ++ it)
	{
		float sc = 0.0f;
		VssRay *ray = (*it).mRay;

		bool madeContrib = false;
		float contribution;

		if (ray->mTerminationObject) 
		{
			if (vc->AddPvsSample(ray->mTerminationObject, ray->mPdf, contribution))
				madeContrib = true;
			sc += contribution;
		}
	  
		if (ray->mOriginObject) 
		{
			if (vc->AddPvsSample(ray->mOriginObject, ray->mPdf, contribution))
				madeContrib = true;
			sc += contribution;
		}
	  
	  sampleContributions += sc;

	  if (madeContrib)
		  ++ contributingSamples;
		
	  //leaf->mVssRays.push_back(ray);
	}
}


void VspTree::SortSplitCandidates(const RayInfoContainer &rays, 
									 const int axis, 
									 float minBand, 
									 float maxBand)
{
	mSplitCandidates->clear();

	int requestedSize = 2 * (int)(rays.size());
	// creates a sorted split candidates array
	if (mSplitCandidates->capacity() > 500000 &&
		requestedSize < (int)(mSplitCandidates->capacity() / 10) )
	{
    	delete mSplitCandidates;
   		mSplitCandidates = new vector<SortableEntry>;
	}

	mSplitCandidates->reserve(requestedSize);

	float pos;

	// float values => don't compare with exact values
	if (0)
	{
		minBand += Limits::Small;
		maxBand -= Limits::Small;
	}

	// insert all queries
	for (RayInfoContainer::const_iterator ri = rays.begin(); ri < rays.end(); ++ ri)
	{
		const bool positive = (*ri).mRay->HasPosDir(axis);
				
		pos = (*ri).ExtrapOrigin(axis);
		// clamp to min / max band
		if (0) ClipValue(pos, minBand, maxBand);
		
		mSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMin : SortableEntry::ERayMax, 
									pos, (*ri).mRay));

		pos = (*ri).ExtrapTermination(axis);
		// clamp to min / max band
		if (0) ClipValue(pos, minBand, maxBand);

		mSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMax : SortableEntry::ERayMin, 
									pos, (*ri).mRay));
	}

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


float VspTree::BestCostRatioHeuristics(const RayInfoContainer &rays,
										  const AxisAlignedBox3 &box,
										  const int pvsSize,
										  const int axis,
                                          float &position)
{
	const float minBox = box.Min(axis);
	const float maxBox = box.Max(axis);

	const float sizeBox = maxBox - minBox;

	const float minBand = minBox + mMinBand * sizeBox;
	const float maxBand = minBox + mMaxBand * sizeBox;

	SortSplitCandidates(rays, axis, minBand, maxBand);

	// go through the lists, count the number of objects left and right
	// and evaluate the following cost funcion:
	// C = ct_div_ci  + (ql*rl + qr*rr)/queries

	int pvsl = 0;
	int pvsr = pvsSize;

	int pvsBack = pvsl;
	int pvsFront = pvsr;

	float sum = (float)pvsSize * sizeBox;
	float minSum = 1e20f;

	
	// if no border can be found, take mid split
	position = minBox + 0.5f * sizeBox;
	
	// the relative cost ratio
	float ratio = /*Limits::Infinity;*/99999999.0f;
	bool splitPlaneFound = false;

	Intersectable::NewMail();

   	RayInfoContainer::const_iterator ri, ri_end = rays.end();

	// set all object as belonging to the front pvs
	for(ri = rays.begin(); ri != ri_end; ++ ri)
	{
		Intersectable *oObject = (*ri).mRay->mOriginObject;
		Intersectable *tObject = (*ri).mRay->mTerminationObject;

		if (oObject)
		{
			if (!oObject->Mailed())
			{
				oObject->Mail();
				oObject->mCounter = 1;
			}
			else
			{
				++ oObject->mCounter;
			}
		}
		if (tObject)
		{
			if (!tObject->Mailed())
			{
				tObject->Mail();
				tObject->mCounter = 1;
			}
			else
			{
				++ tObject->mCounter;
			}
		}
	}

	Intersectable::NewMail();

	vector<SortableEntry>::const_iterator ci, ci_end = mSplitCandidates->end();

	for (ci = mSplitCandidates->begin(); ci != ci_end; ++ ci)
	{
		VssRay *ray;
		ray = (*ci).ray;
		
		Intersectable *oObject = ray->mOriginObject;
		Intersectable *tObject = ray->mTerminationObject;
		

		switch ((*ci).type)
		{
			case SortableEntry::ERayMin:
				{
					if (oObject && !oObject->Mailed())
					{
						oObject->Mail();
						++ pvsl;
					}
					if (tObject && !tObject->Mailed())
					{
						tObject->Mail();
						++ pvsl;
					}
					break;
				}
			case SortableEntry::ERayMax:
				{
					if (oObject)
					{
						if (-- oObject->mCounter == 0)
							-- pvsr;
					}

					if (tObject)
					{
						if (-- tObject->mCounter == 0)
							-- pvsr;
					}

					break;
				}
		}

		
		
		// Note: sufficient to compare size of bounding boxes of front and back side?
		if (((*ci).value >= minBand) && ((*ci).value <= maxBand))
		{
			sum = pvsl * ((*ci).value - minBox) + pvsr * (maxBox - (*ci).value);

			//Debug  << "pos=" << (*ci).value << "\t pvs=(" <<  pvsl << "," << pvsr << ")" << endl;
			//Debug << "cost= " << sum << endl;

			if (sum < minSum)
			{
				splitPlaneFound = true;

				minSum = sum;
				position = (*ci).value;
				
				pvsBack = pvsl;
				pvsFront = pvsr;
			}
		}
	}
	
	
	// -- compute cost
	const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize();
	const int upperPvsLimit = mViewCellsManager->GetMaxPvsSize();

	const float pOverall = sizeBox;

	const float pBack = position - minBox;
	const float pFront = maxBox - position;
	
	const float penaltyOld = EvalPvsPenalty(pvsSize, lowerPvsLimit, upperPvsLimit);
    const float penaltyFront = EvalPvsPenalty(pvsFront, lowerPvsLimit, upperPvsLimit);
	const float penaltyBack = EvalPvsPenalty(pvsBack, lowerPvsLimit, upperPvsLimit);
	
	const float oldRenderCost = penaltyOld * pOverall;
	const float newRenderCost = penaltyFront * pFront + penaltyBack * pBack;

	if (splitPlaneFound)
	{
		ratio = newRenderCost / (oldRenderCost + Limits::Small);
	}
	//if (axis != 1)
	//Debug << "axis=" << axis << " costRatio=" << ratio << " pos=" << position << " t=" << (position - minBox) / (maxBox - minBox)
	 //    <<"\t pb=(" << pvsBack << ")\t pf=(" << pvsFront << ")" << endl;

	return ratio;
}


float VspTree::SelectPlane(const VspTraversalData &tData,
						   AxisAlignedPlane &plane,
						   float &pFront,
						   float &pBack)
{
	float nPosition[3];
	float nCostRatio[3];
	float nProbFront[3];
	float nProbBack[3];

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


	// if we use some kind of specialised fixed axis
    const bool useSpecialAxis = 
		mOnlyDrivingAxis || mUseRandomAxis || mCirculatingAxis;

	if (mUseRandomAxis)
		sAxis = Random(3);
	else if (mCirculatingAxis)
		sAxis = (tData.mAxis + 1) % 3;
	else if (mOnlyDrivingAxis)
		sAxis = box.Size().DrivingAxis();


	for (int axis = 0; axis < 3 ; ++ axis)
	{
		if (!useSpecialAxis || (axis == sAxis))
		{
			//-- place split plane using heuristics

			if (mUseCostHeuristics)
			{
				nCostRatio[axis] =
					BestCostRatioHeuristics(*tData.mRays,
										    box,
											tData.mPvs,
											axis,
											nPosition[axis]);			
			}
			else //-- split plane position is spatial median
			{
				nPosition[axis] = (box.Min()[axis] + box.Max()[axis]) * 0.5f;

				nCostRatio[axis] = EvalSplitCost(tData,
												 box,
												 axis,
												 nPosition[axis],
												 nProbFront[axis], 
												 nProbBack[axis]);
			}
						
			if (bestAxis == -1)
			{
				bestAxis = axis;
			}
			else if (nCostRatio[axis] < nCostRatio[bestAxis])
			{
				bestAxis = axis;
			} 
		}
	}

	//-- assign values
	plane.mAxis = bestAxis;
	pFront = nProbFront[bestAxis];
	pBack = nProbBack[bestAxis];

	//-- split plane position
    plane.mPosition = nPosition[bestAxis];

	return nCostRatio[bestAxis];
}


inline void VspTree::GenerateUniqueIdsForPvs()
{
	Intersectable::NewMail(); sBackId = Intersectable::sMailId;
	Intersectable::NewMail(); sFrontId = Intersectable::sMailId;
	Intersectable::NewMail(); sFrontAndBackId = Intersectable::sMailId;
}


float VspTree::EvalRenderCostDecrease(const AxisAlignedPlane &candidatePlane,
									  const VspTraversalData &data) const
{
	float pvsFront = 0;
	float pvsBack = 0;
	float totalPvs = 0;

	// probability that view point lies in back / front node
	float pOverall = data.mProbability;
	float pFront = 0;
	float pBack = 0;


	// create unique ids for pvs heuristics
	GenerateUniqueIdsForPvs();
	
	RayInfoContainer::const_iterator rit, rit_end = data.mRays->end();

	for (rit = data.mRays->begin(); rit != rit_end; ++ rit)
	{
		RayInfo rayInf = *rit;

		float t;
		VssRay *ray = rayInf.mRay;
		const int cf = 
			rayInf.ComputeRayIntersection(candidatePlane.mAxis, 
										  candidatePlane.mPosition, t);

		// find front and back pvs for origing and termination object
		AddObjToPvs(ray->mTerminationObject, cf, pvsFront, pvsBack, totalPvs);
		AddObjToPvs(ray->mOriginObject, cf, pvsFront, pvsBack, totalPvs);
	}

	AxisAlignedBox3 frontBox;
	AxisAlignedBox3 backBox;

	data.mBoundingBox.Split(candidatePlane.mAxis, candidatePlane.mPosition, frontBox, backBox);

	pFront = frontBox.GetVolume();
	pBack = pOverall - pFront;
		

	//-- pvs rendering heuristics
	const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize();
	const int upperPvsLimit = mViewCellsManager->GetMaxPvsSize();

	//-- only render cost heuristics or combined with standard deviation
	const float penaltyOld = EvalPvsPenalty((int)totalPvs, lowerPvsLimit, upperPvsLimit);
    const float penaltyFront = EvalPvsPenalty((int)pvsFront, lowerPvsLimit, upperPvsLimit);
	const float penaltyBack = EvalPvsPenalty((int)pvsBack, lowerPvsLimit, upperPvsLimit);
			
	const float oldRenderCost = pOverall * penaltyOld;
	const float newRenderCost = penaltyFront * pFront + penaltyBack * pBack;

	//Debug << "decrease: " << oldRenderCost - newRenderCost << endl;
	const float renderCostDecrease = (oldRenderCost - newRenderCost) / mBoundingBox.GetVolume();
	

#if 1
	// take render cost of node into account 
	// otherwise danger of being stuck in a local minimum!!
	const float normalizedOldRenderCost = oldRenderCost / mBoundingBox.GetVolume();
	return 0.99f * renderCostDecrease + 0.01f * normalizedOldRenderCost;
#else
	return renderCostDecrease;
#endif
}


float VspTree::EvalSplitCost(const VspTraversalData &data,
							 const AxisAlignedBox3 &box,
							 const int axis,
							 const float &position,										  
							 float &pFront,
							 float &pBack) const
{
	float pvsTotal = 0;
	float pvsFront = 0;
	float pvsBack = 0;
	
	// create unique ids for pvs heuristics
	GenerateUniqueIdsForPvs();

	const int pvsSize = data.mPvs;

	RayInfoContainer::const_iterator rit, rit_end = data.mRays->end();

	// this is the main ray classification loop!
	for(rit = data.mRays->begin(); rit != rit_end; ++ rit)
	{
		// determine the side of this ray with respect to the plane
		float t;
		const int side = (*rit).ComputeRayIntersection(axis, position, t);
	
		AddObjToPvs((*rit).mRay->mTerminationObject, side, pvsFront, pvsBack, pvsTotal);
		AddObjToPvs((*rit).mRay->mOriginObject, side, pvsFront, pvsBack, pvsTotal);
	}

	//-- pvs heuristics
	float pOverall;

	//-- compute heurstics
	//-- we take simplified computation for mid split
		
	pOverall = data.mProbability;
	pBack = pFront = pOverall * 0.5f;
	
	
#ifdef _DEBUG
	Debug << axis << " " << pvsSize << " " << pvsBack << " " << pvsFront << endl;
	Debug << pFront << " " << pBack << " " << pOverall << endl;
#endif

	
	const float newCost = pvsBack * pBack + pvsFront * pFront;
	const float oldCost = (float)pvsSize * pOverall + Limits::Small;

	return  (mCtDivCi + newCost) / oldCost;
}


void VspTree::AddObjToPvs(Intersectable *obj,
							 const int cf,
							 float &frontPvs,
							 float &backPvs,
							 float &totalPvs) const
{
	if (!obj)
		return;

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

	// new object
	if ((obj->mMailbox != sFrontId) &&
		(obj->mMailbox != sBackId) &&
		(obj->mMailbox != sFrontAndBackId))
	{
		totalPvs += renderCost;
	}

	// TODO: does this really belong to no pvs?
	//if (cf == Ray::COINCIDENT) return;

	// object belongs to both PVS
	if (cf >= 0)
	{
		if ((obj->mMailbox != sFrontId) &&
			(obj->mMailbox != sFrontAndBackId))
		{
			frontPvs += renderCost;
		
			if (obj->mMailbox == sBackId)
				obj->mMailbox = sFrontAndBackId;
			else
				obj->mMailbox = sFrontId;
		}
	}

	if (cf <= 0)
	{
		if ((obj->mMailbox != sBackId) &&
			(obj->mMailbox != sFrontAndBackId))
		{
			backPvs += renderCost;
		
			if (obj->mMailbox == sFrontId)
				obj->mMailbox = sFrontAndBackId;
			else
				obj->mMailbox = sBackId;
		}
	}
}


void VspTree::CollectLeaves(vector<VspLeaf *> &leaves, 
							   const bool onlyUnmailed,
							   const int maxPvsSize) const
{
	stack<VspNode *> nodeStack;
	nodeStack.push(mRoot);

	while (!nodeStack.empty())
	{
		VspNode *node = nodeStack.top();
		nodeStack.pop();
		
		if (node->IsLeaf())
		{
			// test if this leaf is in valid view space
			VspLeaf *leaf = dynamic_cast<VspLeaf *>(node);
			if (leaf->TreeValid() && 
				(!onlyUnmailed || !leaf->Mailed()) &&
				((maxPvsSize < 0) || (leaf->GetViewCell()->GetPvs().GetSize() <= maxPvsSize)))
			{
				leaves.push_back(leaf);
			}
		}
		else
		{
			VspInterior *interior = dynamic_cast<VspInterior *>(node);

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


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


VspNode *VspTree::GetRoot() const
{
	return mRoot;
}


void VspTree::EvaluateLeafStats(const VspTraversalData &data)
{
	// the node became a leaf -> evaluate stats for leafs
	VspLeaf *leaf = dynamic_cast<VspLeaf *>(data.mNode);


	if (data.mPvs > mVspStats.maxPvs)
	{
		mVspStats.maxPvs = data.mPvs;
	}

	mVspStats.pvs += data.mPvs;

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

	// accumulate rays to compute rays /  leaf
	mVspStats.accumRays += (int)data.mRays->size();

	if (data.mPvs < mTermMinPvs)
		++ mVspStats.minPvsNodes;

	if ((int)data.mRays->size() < mTermMinRays)
		++ mVspStats.minRaysNodes;

	if (data.GetAvgRayContribution() > mTermMaxRayContribution)
		++ mVspStats.maxRayContribNodes;

	if (data.mProbability <= mTermMinProbability)
		++ mVspStats.minProbabilityNodes;
	
	// accumulate depth to compute average depth
	mVspStats.accumDepth += data.mDepth;

	++ mCreatedViewCells;

#ifdef _DEBUG
	Debug << "BSP stats: "
		  << "Depth: " << data.mDepth << " (max: " << mTermMaxDepth << "), "
		  << "PVS: " << data.mPvs << " (min: " << mTermMinPvs << "), "
	  //		  << "Area: " << data.mProbability << " (min: " << mTermMinProbability << "), "
		  << "#rays: " << (int)data.mRays->size() << " (max: " << mTermMinRays << "), "
		  << "#pvs: " << leaf->GetViewCell()->GetPvs().GetSize() << "=, "
		  << "#avg ray contrib (pvs): " << (float)data.mPvs / (float)data.mRays->size() << endl;
#endif
}


void VspTree::CollectViewCells(ViewCellContainer &viewCells, bool onlyValid) const
{
	ViewCell::NewMail();
	CollectViewCells(mRoot, onlyValid, viewCells, true);
}


void VspTree::CollapseViewCells()
{
// TODO
#if HAS_TO_BE_REDONE
	stack<VspNode *> nodeStack;

	if (!mRoot)
		return;

	nodeStack.push(mRoot);
	
	while (!nodeStack.empty()) 
	{
		VspNode *node = nodeStack.top();
		nodeStack.pop();
		
		if (node->IsLeaf())
        {
			BspViewCell *viewCell = dynamic_cast<VspLeaf *>(node)->GetViewCell();

			if (!viewCell->GetValid())
			{
				BspViewCell *viewCell = dynamic_cast<VspLeaf *>(node)->GetViewCell();
	
				ViewCellContainer leaves;
				mViewCellsTree->CollectLeaves(viewCell, leaves);

				ViewCellContainer::const_iterator it, it_end = leaves.end();

				for (it = leaves.begin(); it != it_end; ++ it)
				{
					VspLeaf *l = dynamic_cast<BspViewCell *>(*it)->mLeaf;
					l->SetViewCell(GetOrCreateOutOfBoundsCell());
					++ mVspStats.invalidLeaves;
				}

				// add to unbounded view cell
				GetOrCreateOutOfBoundsCell()->GetPvs().AddPvs(viewCell->GetPvs());
				DEL_PTR(viewCell);
			}
		}
		else
		{
			VspInterior *interior = dynamic_cast<VspInterior *>(node);
		
			nodeStack.push(interior->GetFront());
			nodeStack.push(interior->GetBack());
		}
	}

	Debug << "invalid leaves: " << mVspStats.invalidLeaves << endl;
#endif
}


void VspTree::CollectRays(VssRayContainer &rays)
{
	vector<VspLeaf *> leaves;

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

	for (lit = leaves.begin(); lit != lit_end; ++ lit)
	{
		VspLeaf *leaf = *lit;
		VssRayContainer::const_iterator rit, rit_end = leaf->mVssRays.end();

		for (rit = leaf->mVssRays.begin(); rit != rit_end; ++ rit)
			rays.push_back(*rit);
	}
}


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


void VspTree::ValidateTree()
{
	mVspStats.invalidLeaves = 0;

	stack<VspNode *> nodeStack;

	if (!mRoot)
		return;

	nodeStack.push(mRoot);

	while (!nodeStack.empty()) 
	{
		VspNode *node = nodeStack.top();
		nodeStack.pop();
		
		if (node->IsLeaf())
		{
			VspLeaf *leaf = dynamic_cast<VspLeaf *>(node);

			if (!leaf->GetViewCell()->GetValid())
				++ mVspStats.invalidLeaves;

			// validity flags don't match => repair
			if (leaf->GetViewCell()->GetValid() != leaf->TreeValid())
			{
				leaf->SetTreeValid(leaf->GetViewCell()->GetValid());
				PropagateUpValidity(leaf);
			}
		}
		else
		{
			VspInterior *interior = dynamic_cast<VspInterior *>(node);
		
			nodeStack.push(interior->GetFront());
			nodeStack.push(interior->GetBack());
		}
	}

	Debug << "invalid leaves: " << mVspStats.invalidLeaves << endl;
}



void VspTree::CollectViewCells(VspNode *root,
								  bool onlyValid,
								  ViewCellContainer &viewCells,
								  bool onlyUnmailed) const
{
	stack<VspNode *> nodeStack;

	if (!root)
		return;

	nodeStack.push(root);
	
	while (!nodeStack.empty()) 
	{
		VspNode *node = nodeStack.top();
		nodeStack.pop();
		
		if (node->IsLeaf())
		{
			if (!onlyValid || node->TreeValid())
			{
				ViewCellLeaf *leafVc = dynamic_cast<VspLeaf *>(node)->GetViewCell();

				ViewCell *viewCell = mViewCellsTree->GetActiveViewCell(leafVc);
						
				if (!onlyUnmailed || !viewCell->Mailed()) 
				{
					viewCell->Mail();
					viewCells.push_back(viewCell);
				}
			}
		}
		else
		{
			VspInterior *interior = dynamic_cast<VspInterior *>(node);
		
			nodeStack.push(interior->GetFront());
			nodeStack.push(interior->GetBack());
		}
	}
}


int VspTree::FindNeighbors(VspLeaf *n,
						   vector<VspLeaf *> &neighbors,
						   const bool onlyUnmailed) const
{
	stack<VspNode *> nodeStack;
	nodeStack.push(mRoot);

	const AxisAlignedBox3 box = GetBBox(n);

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

		if (node->IsLeaf())
		{
			VspLeaf *leaf = dynamic_cast<VspLeaf *>(node);

			if (leaf != n && (!onlyUnmailed || !leaf->Mailed()))
				neighbors.push_back(leaf);
		}
		else
		{
			VspInterior *interior = dynamic_cast<VspInterior *>(node);
			
			if (interior->GetPosition() > box.Max(interior->GetAxis()))
				nodeStack.push(interior->GetBack());
			else
			{
				if (interior->GetPosition() < box.Min(interior->GetAxis()))
					nodeStack.push(interior->GetFront());
				else
				{
					// random decision
					nodeStack.push(interior->GetBack());
					nodeStack.push(interior->GetFront());
				}
			}
		}
	}

	return (int)neighbors.size();
}


// Find random neighbor which was not mailed
VspLeaf *VspTree::GetRandomLeaf(const Plane3 &plane)
{
	stack<VspNode *> nodeStack;
	nodeStack.push(mRoot);
  
	int mask = rand();
  
	while (!nodeStack.empty()) 
	{
		VspNode *node = nodeStack.top();
		
		nodeStack.pop();
		
		if (node->IsLeaf()) 
		{
			return dynamic_cast<VspLeaf *>(node);
		} 
		else 
		{
			VspInterior *interior = dynamic_cast<VspInterior *>(node);
			VspNode *next;
			
			if (GetBBox(interior->GetBack()).Side(plane) < 0)
				next = interior->GetFront();
            else
				if (GetBBox(interior->GetFront()).Side(plane) < 0)
					next = interior->GetBack();
				else 
				{
					// random decision
					if (mask & 1)
						next = interior->GetBack();
					else
						next = interior->GetFront();
					mask = mask >> 1;
				}

				nodeStack.push(next);
		}
	}
  
	return NULL;
}


VspLeaf *VspTree::GetRandomLeaf(const bool onlyUnmailed)
{
	stack<VspNode *> nodeStack;

	nodeStack.push(mRoot);

	int mask = rand();

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

		if (node->IsLeaf())
		{
			if ( (!onlyUnmailed || !node->Mailed()) )
				return dynamic_cast<VspLeaf *>(node);
		}
		else
		{
			VspInterior *interior = dynamic_cast<VspInterior *>(node);

			// random decision
			if (mask & 1)
				nodeStack.push(interior->GetBack());
			else
				nodeStack.push(interior->GetFront());

			mask = mask >> 1;
		}
	}

	return NULL;
}


int VspTree::ComputePvsSize(const RayInfoContainer &rays) const
{
	int pvsSize = 0;

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

	Intersectable::NewMail();

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

		if (ray->mOriginObject)
		{
			if (!ray->mOriginObject->Mailed())
			{
				ray->mOriginObject->Mail();
				++ pvsSize;
			}
		}
		if (ray->mTerminationObject)
		{
			if (!ray->mTerminationObject->Mailed())
			{
				ray->mTerminationObject->Mail();
				++ pvsSize;
			}
		}
	}

	return pvsSize;
}


float VspTree::GetEpsilon() const
{
	return mEpsilon;
}


int VspTree::CastLineSegment(const Vector3 &origin,
								const Vector3 &termination,
								ViewCellContainer &viewcells)
{
	int hits = 0;

	float mint = 0.0f, maxt = 1.0f;
	const Vector3 dir = termination - origin;

	stack<LineTraversalData> tStack;

	Intersectable::NewMail();
	ViewCell::NewMail();

	Vector3 entp = origin;
	Vector3 extp = termination;

	VspNode *node = mRoot;
	VspNode *farChild;

	float position;
	int axis;

	while (1)
	{
		if (!node->IsLeaf())
		{
			VspInterior *in = dynamic_cast<VspInterior *>(node);
			position = in->GetPosition();
			axis = in->GetAxis();

			if (entp[axis] <= position)
			{
				if (extp[axis] <= position)
				{
					node = in->GetBack();
					// cases N1,N2,N3,P5,Z2,Z3
					continue;
				} else
				{
					// case N4
					node = in->GetBack();
					farChild = in->GetFront();
				}
			}
			else
			{
				if (position <= extp[axis])
				{
					node = in->GetFront();
					// cases P1,P2,P3,N5,Z1
					continue;
				}
				else
				{
					node = in->GetFront();
					farChild = in->GetBack();
					// case P4
				}
			}

 			// $$ modification 3.5.2004 - hints from Kamil Ghais
			// case N4 or P4
			const float tdist = (position - origin[axis]) / dir[axis];
			tStack.push(LineTraversalData(farChild, extp, maxt)); //TODO

			extp = origin + dir * tdist;
			maxt = tdist;
		}
		else
		{
			// compute intersection with all objects in this leaf
			VspLeaf *leaf = dynamic_cast<VspLeaf *>(node);
			ViewCell *vc = leaf->GetViewCell();

			if (!vc->Mailed())
			{
				vc->Mail();
				viewcells.push_back(vc);
				++ hits;
			}
#if 0
			leaf->mRays.push_back(RayInfo(new VssRay(origin, termination, NULL, NULL, 0)));
#endif
			// get the next node from the stack
			if (tStack.empty())
				break;

			entp = extp;
			mint = maxt;
			
			LineTraversalData &s  = tStack.top();
			node = s.mNode;
			extp = s.mExitPoint;
			maxt = s.mMaxT;
			tStack.pop();
		}
	}

	return hits;
}


int VspTree::CastRay(Ray &ray)
{
	int hits = 0;

	stack<LineTraversalData> tStack;
	const Vector3 dir = ray.GetDir();

	float maxt, mint;

	if (!mBoundingBox.GetRaySegment(ray, mint, maxt))
		return 0;

	Intersectable::NewMail();
	ViewCell::NewMail();

	Vector3 entp = ray.Extrap(mint);
	Vector3 extp = ray.Extrap(maxt);

	const Vector3 origin = entp;

	VspNode *node = mRoot;
	VspNode *farChild = NULL;

	float position;
	int axis;

	while (1)
	{
		if (!node->IsLeaf())
		{
			VspInterior *in = dynamic_cast<VspInterior *>(node);
			position = in->GetPosition();
			axis = in->GetAxis();

			if (entp[axis] <= position)
			{
				if (extp[axis] <= position)
				{
					node = in->GetBack();
					// cases N1,N2,N3,P5,Z2,Z3
					continue;
				} 
				else
				{
					// case N4
					node = in->GetBack();
					farChild = in->GetFront();
				}
			}
			else
			{
				if (position <= extp[axis])
				{
					node = in->GetFront();
					// cases P1,P2,P3,N5,Z1
					continue;
				}
				else
				{
					node = in->GetFront();
					farChild = in->GetBack();
					// case P4
				}
			}

 			// $$ modification 3.5.2004 - hints from Kamil Ghais
			// case N4 or P4
			const float tdist = (position - origin[axis]) / dir[axis];
			tStack.push(LineTraversalData(farChild, extp, maxt)); //TODO
			extp = origin + dir * tdist;
			maxt = tdist;
		}
		else
		{
			// compute intersection with all objects in this leaf
			VspLeaf *leaf = dynamic_cast<VspLeaf *>(node);
			ViewCell *vc = leaf->GetViewCell();

			if (!vc->Mailed())
			{
				vc->Mail();
				// todo: add view cells to ray
				++ hits;
			}
#if 0
			leaf->mRays.push_back(RayInfo(new VssRay(origin, termination, NULL, NULL, 0)));
#endif
			// get the next node from the stack
			if (tStack.empty())
				break;

			entp = extp;
			mint = maxt;
			
			LineTraversalData &s  = tStack.top();
			node = s.mNode;
			extp = s.mExitPoint;
			maxt = s.mMaxT;
			tStack.pop();
		}
	}

	return hits;
}


VspNode *VspTree::CollapseTree(VspNode *node, int &collapsed)
{
// TODO
#if HAS_TO_BE_REDONE
	if (node->IsLeaf())
		return node;

	VspInterior *interior = dynamic_cast<VspInterior *>(node);

	VspNode *front = CollapseTree(interior->GetFront(), collapsed);
	VspNode *back = CollapseTree(interior->GetBack(), collapsed);

	if (front->IsLeaf() && back->IsLeaf())
	{
		VspLeaf *frontLeaf = dynamic_cast<VspLeaf *>(front);
		VspLeaf *backLeaf = dynamic_cast<VspLeaf *>(back);

		//-- collapse tree
		if (frontLeaf->GetViewCell() == backLeaf->GetViewCell())
		{
			BspViewCell *vc = frontLeaf->GetViewCell();

			VspLeaf *leaf = new VspLeaf(interior->GetParent(), vc);
			leaf->SetTreeValid(frontLeaf->TreeValid());

			// replace a link from node's parent
			if (leaf->GetParent())
				leaf->GetParent()->ReplaceChildLink(node, leaf);
			else
				mRoot = leaf;

			++ collapsed;
			delete interior;

			return leaf;
		}
	}
#endif
	return node;
}


int VspTree::CollapseTree()
{
	int collapsed = 0;

	(void)CollapseTree(mRoot, collapsed);
	// revalidate leaves
	RepairViewCellsLeafLists();

	return collapsed;
}


void VspTree::RepairViewCellsLeafLists()
{
// TODO
#if HAS_TO_BE_REDONE
	// list not valid anymore => clear
	stack<VspNode *> nodeStack;
	nodeStack.push(mRoot);

	ViewCell::NewMail();

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

		if (node->IsLeaf())
		{
			VspLeaf *leaf = dynamic_cast<VspLeaf *>(node);

			BspViewCell *viewCell = leaf->GetViewCell();

			if (!viewCell->Mailed())
			{
				viewCell->mLeaves.clear();
				viewCell->Mail();
			}
	
			viewCell->mLeaves.push_back(leaf);

		}
		else
		{
			VspInterior *interior = dynamic_cast<VspInterior *>(node);

			nodeStack.push(interior->GetFront());
			nodeStack.push(interior->GetBack());
		}
	}
// TODO
#endif
}



ViewCell *VspTree::GetViewCell(const Vector3 &point, const bool active)
{
	if (mRoot == NULL)
		return NULL;

	stack<VspNode *> nodeStack;
	nodeStack.push(mRoot);
  
	ViewCellLeaf *viewcell = NULL;
  
	while (!nodeStack.empty())  
	{
		VspNode *node = nodeStack.top();
		nodeStack.pop();
	
		if (node->IsLeaf()) 
		{
			viewcell = dynamic_cast<VspLeaf *>(node)->GetViewCell();
			break;
		} 
		else 	
		{	
			VspInterior *interior = dynamic_cast<VspInterior *>(node);
     
			// random decision
			if (interior->GetPosition() - point[interior->GetAxis()] < 0)
				nodeStack.push(interior->GetBack());
			else
				nodeStack.push(interior->GetFront());
		}
	}
  
	if (active)
		return mViewCellsTree->GetActiveViewCell(viewcell);
	else
		return viewcell;
}


bool VspTree::ViewPointValid(const Vector3 &viewPoint) const
{
	VspNode *node = mRoot;

	while (1)
	{
		// early exit
		if (node->TreeValid())
			return true;

		if (node->IsLeaf())
			return false;
			
		VspInterior *in = dynamic_cast<VspInterior *>(node);
					
		if (in->GetPosition() - viewPoint[in->GetAxis()] <= 0) 
		{
			node = in->GetBack();
		} 
		else
		{
			node = in->GetFront();
		}
	}

	// should never come here
	return false;
}


void VspTree::PropagateUpValidity(VspNode *node)
{
	const bool isValid = node->TreeValid();

	// propagative up invalid flag until only invalid nodes exist over this node
	if (!isValid)
	{
		while (!node->IsRoot() && node->GetParent()->TreeValid())
		{
			node = node->GetParent();
			node->SetTreeValid(false);
		}
	}
	else
	{
		// propagative up valid flag until one of the subtrees is invalid
		while (!node->IsRoot() && !node->TreeValid())
		{
            node = node->GetParent();
			VspInterior *interior = dynamic_cast<VspInterior *>(node);
			
			// the parent is valid iff both leaves are valid
			node->SetTreeValid(interior->GetBack()->TreeValid() && 
							   interior->GetFront()->TreeValid());
		}
	}
}

#if ZIPPED_VIEWCELLS
bool VspTree::Export(ogzstream &stream)
#else
bool VspTree::Export(ofstream &stream)
#endif
{
	ExportNode(mRoot, stream);

	return true;
}


#if ZIPPED_VIEWCELLS
void VspTree::ExportNode(VspNode *node, ogzstream &stream)
#else
void VspTree::ExportNode(VspNode *node, ofstream &stream)
#endif
{
	if (node->IsLeaf())
	{
		VspLeaf *leaf = dynamic_cast<VspLeaf *>(node);
		ViewCell *viewCell = mViewCellsTree->GetActiveViewCell(leaf->GetViewCell());

		int id = -1;
		if (viewCell != mOutOfBoundsCell)
			id = viewCell->GetId();

		stream << "<Leaf viewCellId=\"" << id << "\" />" << endl;
	}
	else
	{	
		VspInterior *interior = dynamic_cast<VspInterior *>(node);
	
		AxisAlignedPlane plane = interior->GetPlane();
		stream << "<Interior plane=\"" << plane.mPosition << " " 
			   << plane.mAxis << "\">" << endl;

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

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


int VspTree::SplitRays(const AxisAlignedPlane &plane,
					   RayInfoContainer &rays,
					   RayInfoContainer &frontRays,
					   RayInfoContainer &backRays) const
{
	int splits = 0;

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

	for (rit = rays.begin(); rit != rit_end; ++ rit)
	{
		RayInfo bRay = *rit;
		
		VssRay *ray = bRay.mRay;
		float t;

		// get classification and receive new t
		//-- test if start point behind or in front of plane
		const int side = plane.ComputeRayIntersection(bRay, t);

		if (side == 0)
		{
			++ splits;

			if (ray->HasPosDir(plane.mAxis))
			{
				backRays.push_back(RayInfo(ray, bRay.GetMinT(), t));
				frontRays.push_back(RayInfo(ray, t, bRay.GetMaxT()));
			}
			else
			{
				frontRays.push_back(RayInfo(ray, bRay.GetMinT(), t));
				backRays.push_back(RayInfo(ray, t, bRay.GetMaxT()));
			}
		}
		else if (side == 1)
		{
			frontRays.push_back(bRay);
		}
		else
		{
			backRays.push_back(bRay);
		}

	}

	return splits;
}


AxisAlignedBox3 VspTree::GetBBox(VspNode *node) const
{
	if (!node->GetParent())
		return mBoundingBox;

	if (!node->IsLeaf())
	{
		return (dynamic_cast<VspInterior *>(node))->GetBoundingBox();		
	}

	VspInterior *parent = dynamic_cast<VspInterior *>(node->GetParent());

	AxisAlignedBox3 box(parent->GetBoundingBox());

	if (parent->GetFront() == node)
		box.SetMin(parent->GetAxis(), parent->GetPosition());
	else
		box.SetMax(parent->GetAxis(), parent->GetPosition());

	return box;
}




int VspTree::ComputeBoxIntersections(const AxisAlignedBox3 &box,
									 ViewCellContainer &viewCells) const
{
#if TODO
	stack<bspNodePair> nodeStack;
	BspNodeGeometry *rgeom = new BspNodeGeometry();

	ConstructGeometry(mRoot, *rgeom);

	nodeStack.push(bspNodePair(mRoot, rgeom));
  
	ViewCell::NewMail();

	while (!nodeStack.empty()) 
	{
		BspNode *node = nodeStack.top().first;
		BspNodeGeometry *geom = nodeStack.top().second;
		nodeStack.pop();

		const int side = geom->ComputeIntersection(box);
		
		switch (side)
		{
		case -1:
			// node geometry is contained in box
			CollectViewCells(node, true, viewCells, true);
			break;

		case 0:
			if (node->IsLeaf())
			{
				BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
			
				if (!leaf->GetViewCell()->Mailed() && leaf->TreeValid())
				{
					leaf->GetViewCell()->Mail();
					viewCells.push_back(leaf->GetViewCell());
				}
			}
			else 
			{
				BspInterior *interior = dynamic_cast<BspInterior *>(node);
			
				BspNode *first = interior->GetFront();
				BspNode *second = interior->GetBack();
            
				BspNodeGeometry *firstGeom = new BspNodeGeometry();
				BspNodeGeometry *secondGeom = new BspNodeGeometry();

				geom->SplitGeometry(*firstGeom,
									*secondGeom,
									interior->GetPlane(),
									mBox,
									//0.0000001f);
									mEpsilon);

				nodeStack.push(bspNodePair(first, firstGeom));
				nodeStack.push(bspNodePair(second, secondGeom));
			}
			
			break;
		default:
			// default: cull
			break;
		}
		DEL_PTR(geom);
	}

#endif
	return (int)viewCells.size();
}



/*****************************************************************/
/*                class OspTree implementation                   */
/*****************************************************************/


void OspTree::SplitObjects(const AxisAlignedPlane & splitPlane,
						   const ObjectContainer &objects,
						   ObjectContainer &back,
						   ObjectContainer &front)
{
	ObjectContainer::const_iterator oit, oit_end = objects.end();

    for (oit = objects.begin(); oit != oit_end; ++ oit) 
	{
		// determine the side of this ray with respect to the plane
		const AxisAlignedBox3 box = (*oit)->GetBox();

		if (box.Max(splitPlane.mAxis) >= splitPlane.mPosition)
            front.push_back(*oit);
    
		if (box.Min(splitPlane.mAxis) < splitPlane.mPosition)
			back.push_back(*oit);
#if TODO    
		mStat.objectRefs -= (int)objects.size();
		mStat.objectRefs += objectsBack + objectsFront;
#endif
	}
}


KdInterior *OspTree::SubdivideNode(KdLeaf *leaf,
								   const AxisAlignedPlane &splitPlane,
								   const AxisAlignedBox3 &box,
								   AxisAlignedBox3 &backBBox,
								   AxisAlignedBox3 &frontBBox)
{
#if TODO
    mSpatialStat.nodes += 2;
	mSpatialStat.splits[axis];
#endif

	// add the new nodes to the tree
	KdInterior *node = new KdInterior(leaf->mParent);

	const int axis = splitPlane.mAxis;
	const float position = splitPlane.mPosition;

	node->mAxis = axis;
	node->mPosition = position;
	node->mBox = box;

    backBBox = box;
	frontBBox = box;
  
	// first count ray sides
	int objectsBack = 0;
	int objectsFront = 0;
  
	backBBox.SetMax(axis, position);
	frontBBox.SetMin(axis, position);

	ObjectContainer::const_iterator mi, mi_end = leaf->mObjects.end();

	for ( mi = leaf->mObjects.begin(); mi != mi_end; ++ mi) 
	{
		// determine the side of this ray with respect to the plane
		const AxisAlignedBox3 box = (*mi)->GetBox();
		
		if (box.Max(axis) > position) 
			++ objectsFront;
    
		if (box.Min(axis) < position)
			++ objectsBack;
	}

	KdLeaf *back = new KdLeaf(node, objectsBack);
	KdLeaf *front = new KdLeaf(node, objectsFront);

	// replace a link from node's parent
	if (leaf->mParent)
		leaf->mParent->ReplaceChildLink(leaf, node);

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

	SplitObjects(splitPlane, leaf->mObjects, back->mObjects, front->mObjects);
  
	//delete leaf;
	return node;
}


KdNode *OspTree::Subdivide(SplitQueue &tQueue,
						   OspSplitCandidate &splitCandidate,
						   const bool globalCriteriaMet)
{
	OspTraversalData &tData = splitCandidate.mParentData;

	KdNode *newNode = tData.mNode;

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

		//-- continue subdivision
		
		// create new interior node and two leaf node
		const AxisAlignedPlane splitPlane = splitCandidate.mSplitPlane;
		newNode = SubdivideNode(dynamic_cast<KdLeaf *>(newNode), 
								splitPlane, 
								tData.mBoundingBox, 
								tFrontData.mBoundingBox, 
								tBackData.mBoundingBox);
	
		const int maxCostMisses = splitCandidate.mMaxCostMisses;

		// how often was max cost ratio missed in this branch?
		tFrontData.mMaxCostMisses = maxCostMisses;
		tBackData.mMaxCostMisses = maxCostMisses;
			
		//-- push the new split candidates on the queue
		OspSplitCandidate *frontCandidate = new OspSplitCandidate();
		OspSplitCandidate *backCandidate = new OspSplitCandidate();

		EvalSplitCandidate(tFrontData, *frontCandidate);
		EvalSplitCandidate(tBackData, *backCandidate);

		tQueue.push(frontCandidate);
		tQueue.push(backCandidate);

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


	//-- terminate traversal
	if (newNode->IsLeaf())
	{
		//KdLeaf *leaf = dynamic_cast<KdLeaf *>(newNode);
		EvaluateLeafStats(tData);		
	}

	//-- cleanup
	tData.Clear();
	
	return newNode;
}


void OspTree::EvalSplitCandidate(OspTraversalData &tData,
								 OspSplitCandidate &splitData)
{
	float frontProb;
	float backtProb;
	
	KdLeaf *leaf = dynamic_cast<KdLeaf *>(tData.mNode);

	// compute locally best split plane
	const bool success = false;
#if TODO
	SelectPlane(tData, splitData.mSplitPlane,
				frontData.mProbability, backData.mProbability);

	//TODO
	// compute global decrease in render cost
	splitData.mPriority = EvalRenderCostDecrease(splitData.mSplitPlane, tData);
	splitData.mParentData = tData;
	splitData.mMaxCostMisses = success ? tData.mMaxCostMisses : tData.mMaxCostMisses + 1;
#endif
}


bool OspTree::LocalTerminationCriteriaMet(const OspTraversalData &data) const
{
	// matt: TODO
	return true;
    /*		(((int)data.mRays->size() <= mTermMinRays) ||
		 (data.mPvs <= mTermMinPvs)   ||
		 (data.mProbability <= mTermMinProbability) ||
		 (data.GetAvgRayContribution() > mTermMaxRayContribution) ||
		 (data.mDepth >= mTermMaxDepth));*/
}


bool OspTree::GlobalTerminationCriteriaMet(const OspTraversalData &data) const
{
	// matt: TODO
	return true;
		/*(mOutOfMemory || 
		(mVspStats.Leaves() >= mMaxViewCells) || 
		(mGlobalCostMisses >= mTermGlobalCostMissTolerance));*/
}


void OspTree::EvaluateLeafStats(const OspTraversalData &data)
{
#if TODO
	// the node became a leaf -> evaluate stats for leafs
	VspLeaf *leaf = dynamic_cast<VspLeaf *>(data.mNode);

	if (data.mPvs > mVspStats.maxPvs)
	{
		mVspStats.maxPvs = data.mPvs;
	}

	mVspStats.pvs += data.mPvs;

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

	// accumulate rays to compute rays /  leaf
	mVspStats.accumRays += (int)data.mRays->size();

	if (data.mPvs < mTermMinPvs)
		++ mVspStats.minPvsNodes;

	if ((int)data.mRays->size() < mTermMinRays)
		++ mVspStats.minRaysNodes;

	if (data.GetAvgRayContribution() > mTermMaxRayContribution)
		++ mVspStats.maxRayContribNodes;

	if (data.mProbability <= mTermMinProbability)
		++ mVspStats.minProbabilityNodes;
	
	// accumulate depth to compute average depth
	mVspStats.accumDepth += data.mDepth;

	++ mCreatedViewCells;

#ifdef _DEBUG
	Debug << "BSP stats: "
		  << "Depth: " << data.mDepth << " (max: " << mTermMaxDepth << "), "
		  << "PVS: " << data.mPvs << " (min: " << mTermMinPvs << "), "
	  //		  << "Area: " << data.mProbability << " (min: " << mTermMinProbability << "), "
		  << "#rays: " << (int)data.mRays->size() << " (max: " << mTermMinRays << "), "
		  << "#pvs: " << leaf->GetViewCell()->GetPvs().GetSize() << "=, "
		  << "#avg ray contrib (pvs): " << (float)data.mPvs / (float)data.mRays->size() << endl;
#endif

#endif
}


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

HierarchyManager::HierarchyManager()
{
}


SplitCandidate *HierarchyManager::NextSplitCandidate()
{
	SplitCandidate *splitCandidate = mTQueue.top();
	mTQueue.pop();

	return splitCandidate;
}


void HierarchyManager::PrepareConstruction(const VssRayContainer &sampleRays,
										   AxisAlignedBox3 *forcedViewSpace,
										   RayInfoContainer &rays)
{
	VssRayContainer::const_iterator rit, rit_end = sampleRays.end();

	long startTime = GetTime();

	cout << "storing rays ... ";

	Intersectable::NewMail();

	mVspTree->PrepareConstruction(sampleRays, forcedViewSpace);

	//-- store rays
	for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
	{
		VssRay *ray = *rit;

		float minT, maxT;

		static Ray hray;
		hray.Init(*ray);

		// TODO: not very efficient to implictly cast between rays types
		if (mBoundingBox.GetRaySegment(hray, minT, maxT))
		{
			float len = ray->Length();

			if (!len)
				len = Limits::Small;

			rays.push_back(RayInfo(ray, minT / len, maxT / len));
		}
	}

	cout << "finished" << endl;

	//mOspTree->PrepareConstruction(sampleRays, forcedViewSpace, rays);
}


bool HierarchyManager::GlobalTerminationCriteriaMet(SplitCandidate *candidate) const
{
	if (candidate->Type() == SplitCandidate::VIEW_SPACE)
	{
		VspTree::VspSplitCandidate *sc = 
			dynamic_cast<VspTree::VspSplitCandidate *>(candidate);
		
		return mVspTree->GlobalTerminationCriteriaMet(sc->mParentData);
	}

	return true;
}


void HierarchyManager::Construct(const VssRayContainer &sampleRays,
								 const ObjectContainer &objects,
								 AxisAlignedBox3 *forcedViewSpace)
{
	RayInfoContainer *rays = new RayInfoContainer();
	
	// prepare vsp and osp trees for traversal
	PrepareConstruction(sampleRays, forcedViewSpace, *rays);

	mVspTree->mVspStats.Start();

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

	while (!FinishedConstruction())
	{
		SplitCandidate *splitCandidate = NextSplitCandidate();
	    
		const bool globalTerminationCriteriaMet = 
			GlobalTerminationCriteriaMet(splitCandidate);

		// cost ratio of cost decrease / totalCost
		const float costRatio = splitCandidate->GetPriority() / mTotalCost;
		//Debug << "cost ratio: " << costRatio << endl;

		if (costRatio < mTermMinGlobalCostRatio)
			++ mGlobalCostMisses;
	
		//-- subdivide leaf node
		//-- either a object space or view space split
		if (splitCandidate->Type() == SplitCandidate::VIEW_SPACE)
		{
			VspTree::VspSplitCandidate *sc = 
				dynamic_cast<VspTree::VspSplitCandidate *>(splitCandidate);

			VspNode *r = mVspTree->Subdivide(mTQueue, *sc, globalTerminationCriteriaMet);
		}
		else // object space split
		{
#if TODO
			KdNode *r = mKdtree->Subdivide(tOspQueue, dynamic_cast<OspSplitCandidate<(splitCandidate));
#endif
		}

		DEL_PTR(splitCandidate);
	}

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

	mVspTree->mVspStats.Stop();
}


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


}