#include "Plane3.h"
#include "ViewCellBsp.h"
#include "Mesh.h"
#include "common.h"
#include "ViewCell.h"
#include "Environment.h"
#include "Polygon3.h"
#include "Ray.h"
#include "AxisAlignedBox3.h"
#include <stack>
#include <time.h>
#include <iomanip>
#include "Exporter.h"

#define INITIAL_COST 999999// unreachable high initial cost for heuristic evaluation

int BspTree::sTermMaxPolygons = 10;
int BspTree::sTermMaxDepth = 20;
int BspTree::sSplitPlaneStrategy = NEXT_POLYGON; 
int BspTree::sMaxCandidates = 10;
int BspTree::sConstructionMethod = VIEW_CELLS;

/** Evaluates split plane classification with respect to the plane's 
	contribution for a balanced tree.
*/
int BspTree::sLeastSplitsTable[4] = {0, 0, 1, 0};
/** Evaluates split plane classification with respect to the plane's 
	contribution for a minimum number splits in the tree.
*/
int BspTree::sBalancedTreeTable[4] = {-1, 1, 0, 0};

/****************************************************************/
/*                  class BspNode implementation                */
/****************************************************************/

BspNode::BspNode(): mParent(NULL)
{}

BspNode::BspNode(BspInterior *parent): mParent(parent)
{}


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

BspInterior *BspNode::GetParent() 
{ 
	return mParent; 
}

void BspNode::SetParent(BspInterior *parent)
{
	mParent = parent;
}

PolygonContainer *BspNode::GetPolygons()
{
	return &mPolygons;
}

void BspNode::AddPolygons(PolygonContainer *polys)
{
	while (!polys->empty())
	{
		mPolygons.push_back(polys->back());
		polys->pop_back();
	}
}


/****************************************************************/
/*              class BspInterior implementation                */
/****************************************************************/


BspInterior::BspInterior(const Plane3 &plane): 
mPlane(plane), mFront(NULL), mBack(NULL)
{}

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

BspNode *BspInterior::GetBack() 
{
	return mBack;
}

BspNode *BspInterior::GetFront() 
{
	return mFront;
}

Plane3 *BspInterior::GetPlane()
{
	return &mPlane;
}

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

void BspInterior::SetupChildLinks(BspNode *b, BspNode *f) 
{
    mBack = b;
    mFront = f;
}

void BspInterior::ProcessPolygon(Polygon3 *poly, bool storePolys)
{
	if (storePolys) 
		mPolygons.push_back(poly);
	else
		delete poly;
}

void BspInterior::SplitPolygons(PolygonContainer *polys, 
								PolygonContainer *frontPolys, 
								PolygonContainer *backPolys, 
								int &splits, bool storePolys)
{
	while (!polys->empty())
	{
		Polygon3 *poly = polys->back();
		polys->pop_back();

		// test if split is neccessary
		int result = poly->ClassifyPlane(mPlane);

		Polygon3 *front_piece = NULL;
		Polygon3 *back_piece = NULL;

		switch (result)
		{
			case Polygon3::COINCIDENT:
				// discard polygons or saves them in node
				ProcessPolygon(poly, storePolys);
				break;
			case Polygon3::FRONT_SIDE:
				frontPolys->push_back(poly);
				break;
			case Polygon3::BACK_SIDE:
				backPolys->push_back(poly);
				break;
			case Polygon3::SPLIT:
				front_piece = new Polygon3();
				back_piece = new Polygon3();

				//-- split polygon
				poly->Split(&mPlane, front_piece, back_piece, splits);

				frontPolys->push_back(front_piece);
				backPolys->push_back(back_piece);

#ifdef _DEBUG
				Debug << "split " << *poly << endl << *front_piece << endl << *back_piece << endl;
#endif
				// save or discard polygons
				ProcessPolygon(poly, storePolys);
				
				break;
			default:
                Debug << "SHOULD NEVER COME HERE\n";
				break;
		}
	}

	// contains nothing
	delete polys;
}

/****************************************************************/
/*                  class BspLeaf implementation                */
/****************************************************************/
BspLeaf::BspLeaf(): mViewCell(NULL)
{
}

BspLeaf::BspLeaf(ViewCell *viewCell): mViewCell(viewCell) 
{
}

BspLeaf::BspLeaf(BspInterior *parent): BspNode(parent), mViewCell(NULL)
{}

ViewCell *BspLeaf::GetViewCell()
{
	return mViewCell;
}

void BspLeaf::SetViewCell(ViewCell *viewCell)
{
	mViewCell = viewCell;
}

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

/****************************************************************/
/*                  class BspTree implementation                */
/****************************************************************/

BspTree::BspTree(): 
mTermMaxPolygons(0), 
mTermMaxDepth(0), 
mRoot(NULL), 
mIsIncremential(false),
mStorePolys(true)
{
	Randomize(); // initialise random generator for heuristics
}
 
const BspTreeStatistics &BspTree::GetStatistics() const 
{
	return mStat;
}

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

	app << setprecision(4);

	app << "#N_RAYS Number of rays )\n"
		<< rays << endl;
	app << "#N_DOMAINS  ( Number of query domains )\n"
		<< queryDomains <<endl;

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

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

	app << "#N_SPLITS ( Number of splits)\n" << splits << "\n";

	app << "#N_RAYREFS ( Number of rayRefs )\n" <<
	rayRefs << "\n";

	app << "#N_RAYRAYREFS  ( Number of rayRefs / ray )\n" <<
	rayRefs/(double)rays << "\n";

	app << "#N_LEAFRAYREFS  ( Number of rayRefs / leaf )\n" <<
	rayRefs/(double)Leaves() << "\n";

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

	app << "#N_NONEMPTYRAYREFS  ( Number of rayRefs in nonEmpty leaves / non empty leaf )\n" <<
	rayRefsNonZeroQuery/(double)(Leaves() - zeroQueryNodes) << "\n";

	app << "#N_LEAFDOMAINREFS  ( Number of query domain Refs / leaf )\n" <<
	objectRefs/(double)Leaves() << "\n";

	app << "#N_PEMPTYLEAVES  ( Percentage of leaves with zero query domains )\n"<<
	zeroQueryNodes*100/(double)Leaves() << endl;

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

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

	app << "#N_ADDED_RAYREFS  (Number of dynamically added ray references )\n"<<
	addedRayRefs<<endl;

	app << "#N_REMOVED_RAYREFS  (Number of dynamically removed ray references )\n"<<
	removedRayRefs<<endl;

	//  app << setprecision(4);

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

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

BspTree::~BspTree()
{
	std::stack<BspNode *> tStack;

	tStack.push(mRoot);

	while (!tStack.empty())
	{
		BspNode *node = tStack.top();

	    tStack.pop();
	
		/// if we stored the polygons
		CLEAR_CONTAINER(node->mPolygons);

		if (!node->IsLeaf())
		{
			BspInterior *interior = dynamic_cast<BspInterior *>(node);

			// push the children on the stack (there are always two children)
			tStack.push(interior->GetBack());
			tStack.push(interior->GetFront());
		}

		DEL_PTR(node);
	}
}


void BspTree::InsertViewCell(ViewCell *viewCell)
{	
	std::stack<BspTraversalData> tStack;
		Debug << "getting polygons" << endl; Debug.flush();
	PolygonContainer *polys = new PolygonContainer();

	// extract polygons that guide the split process
	AddMesh2Polygons(viewCell->GetMesh(), *polys);
	mBox.Include(viewCell->GetBox()); // add to BSP aabb

	 // traverse tree or create new one
	BspNode *firstNode = mRoot ? mRoot : new BspLeaf();

	tStack.push(BspTraversalData(firstNode, NULL, polys, 0));

	Debug << "starting traversal" << endl; Debug.flush();
	while (!tStack.empty())
	{
		Debug << "new traversal step" << endl; Debug.flush();
		
		// filter polygons donw the tree
		BspTraversalData tData = tStack.top();
	    tStack.pop();
			
		Debug << "popped stack" << endl; Debug.flush();
		if (!tData.mNode)
			Debug << "ERROR NO NODE\n"; Debug.flush();
		if (!tData.mNode->IsLeaf())
		{
			Debug << "no leaf" << endl; Debug.flush();
			BspInterior *interior = dynamic_cast<BspInterior *>(tData.mNode);

			//-- filter view cell polygons down the tree until a leaf is reached
			PolygonContainer *frontPolys = new PolygonContainer();
			PolygonContainer *backPolys = new PolygonContainer();

			int splits = 0;
		
			if ((int)tData.mPolygons->size() > 0)
			{
				Debug << "traversing down tree" << endl; Debug.flush();
				// split viecell polygons with respect to split plane
				interior->SplitPolygons(tData.mPolygons, frontPolys, backPolys, splits, mStorePolys);
				Debug << "polygon splitted" << endl; Debug.flush();
				//Debug << "Reached level " << tData.mDepth << " bk: " << backPolys->size() << " frnt: " << frontPolys->size() << endl;
				mStat.splits += splits;

				// push the children on the stack
				tStack.push(BspTraversalData(interior->GetFront(), interior->GetParent(), 
							frontPolys, tData.mDepth + 1));
			
				tStack.push(BspTraversalData(interior->GetBack(), interior->GetParent(), 
							backPolys, tData.mDepth + 1));
			
			}
			else
			{
				Debug << "deleting data" << endl; Debug.flush();
				DEL_PTR(tData.mPolygons);
				Debug << "deleted data" << endl; Debug.flush();
			}
		}
		else // reached leaf => subdivide current viewcell
		{
			Debug << "reached leaf" << endl; Debug.flush();
			BspNode *root = Subdivide(tStack, tData, viewCell);		

            // tree empty => new root
			if (!mRoot)
				mRoot = root;		
			Debug << "subdivision done" << endl; Debug.flush();
		}
		Debug << "ended one traversal step" << endl; Debug.flush();
	}
	Debug << "ended traversal" << endl; Debug.flush();
}

void BspTree::InitTree(int maxPolygons, int maxDepth)
{
	mTermMaxPolygons = maxPolygons;
	mTermMaxDepth = maxDepth;
	mStat.nodes = 1;
	
	mBox.Initialize(); 	// initialise bsp tree bounding box
}



void BspTree::AddMesh2Polygons(Mesh *mesh, PolygonContainer &polys)
{
	FaceContainer::const_iterator fi;
	
	// copy the face data to polygons
	for (fi = mesh->mFaces.begin(); fi != mesh->mFaces.end(); ++ fi)
	{
		Polygon3 *poly = new Polygon3((*fi), mesh);
		polys.push_back(poly);
	}
}

void BspTree::Copy2PolygonSoup(const ViewCellContainer &viewCells, PolygonContainer &polys, int maxObjects)
{
	int limit = (maxObjects > 0) ? Min((int)viewCells.size(), maxObjects) : (int)viewCells.size();
  
	for (int i = 0; i < limit; ++i)
	{
		if (viewCells[i]->GetMesh()) // copy the mesh data to polygons
		{
			mBox.Include(viewCells[i]->GetBox()); // add to BSP tree aabb
			AddMesh2Polygons(viewCells[i]->GetMesh(), polys);
		}
	}
}

void BspTree::Copy2PolygonSoup(const ObjectContainer &objects, PolygonContainer &polys, int maxObjects)
{
	int limit = (maxObjects > 0) ? Min((int)objects.size(), maxObjects) : (int)objects.size();
  
	for (int i = 0; i < limit; ++i)
	{
		Intersectable *object = objects[i];//*it;
		Mesh *mesh = NULL;

		switch (object->Type()) // extract the meshes
		{
		case Intersectable::MESH_INSTANCE:
			mesh = dynamic_cast<MeshInstance *>(object)->GetMesh();
			break;
		case Intersectable::VIEWCELL:
			mesh = dynamic_cast<ViewCell *>(object)->GetMesh();
			break;
			// TODO: handle transformed mesh instances
		default:
			break;
		}
		
        if (mesh) // copy the mesh data to polygons
		{
			mBox.Include(object->GetBox()); // add to BSP tree aabb
			AddMesh2Polygons(mesh, polys);
		}
	}

	Debug << "Number of polygons: " << (int)polys.size() << ", BSP root box: " << mBox << endl;
}

void BspTree::Construct(const ViewCellContainer &viewCells)
{
	//-- Construct tree using the given viewcells
	
	/* for this type of construction we filter all viewcells down the 
	 * tree. If there is no polygon left, the last split plane
	 * decides inside or outside of the viewcell.
    */
	InitTree(sTermMaxPolygons, sTermMaxDepth);

    bool savedStorePolys = mStorePolys;

	// tree is completely constructed once before 
	// view cells are inserted one after another => 
	// global tree optimization possible
	if (!mIsIncremential)
	{
		// copy view cell meshes into one big polygon soup
		PolygonContainer *polys = new PolygonContainer();
		Copy2PolygonSoup(viewCells, *polys, sMaxCandidates);

		// polygons are stored only during view cell insertion
		mStorePolys = false;

		// construct tree from viewcell polygons
		Construct(polys);
		//Export("bsp.x3d");
	}
	
	//-- insert all viewcells
	ViewCellContainer::const_iterator it;

	mStorePolys = savedStorePolys;

	int counter = 0;

	Debug << "\n**** Started view cells insertion ****\n\n";
	for (it = viewCells.begin(); it != viewCells.end(); ++ it)
	{
		Debug << "*** Inserting view cell " << counter << " ***" << endl;
		InsertViewCell(*it);
		Debug << "*** view cell " << ++ counter << " inserted ***" << endl;
	}
	Debug << "**** finished view cells insertion ****" << endl; Debug.flush();
}


void BspTree::Construct(const ObjectContainer &objects, ViewCellContainer *viewCells)
{
	// take termination criteria from globals
	InitTree(sTermMaxPolygons, sTermMaxDepth);
	
	PolygonContainer *polys = new PolygonContainer();
	
	// copy mesh instance polygons into one big polygon soup
	Copy2PolygonSoup(objects, *polys, sMaxCandidates);

	// construct tree from polygon soup
	Construct(polys);

	// TODO: generate view cells
}

void BspTree::Construct(const RayContainer &rays, ViewCellContainer *viewCells)
{
	// TODO
}

void BspTree::Construct(PolygonContainer *polys)
{
	std::stack<BspTraversalData> tStack;
	
	BspTraversalData tData(new BspLeaf(), NULL, polys, 0);

	tStack.push(tData);

	Debug << "**** Contructing tree using objects ****\n";
	while (!tStack.empty()) 
	{
		tData = tStack.top();
	    tStack.pop();
	
		// subdivide leaf node
		BspNode *root = Subdivide(tStack, tData);

		// empty tree => new root corresponding to unbounded space
		if (!mRoot) 
			mRoot = root;
	}

	Debug << "**** tree construction finished ****\n";
}


BspNode * BspTree::Subdivide(BspTraversalStack &tStack, 
							 BspTraversalData &tData, 
							 ViewCell *viewCell)
{
	Debug << "subdividing" << endl; Debug.flush();
	PolygonContainer *backPolys = new PolygonContainer();
	PolygonContainer *frontPolys = new PolygonContainer();

	BspNode *node = SubdivideNode(dynamic_cast<BspLeaf *>(tData.mNode),
								  tData.mParent,
								  tData.mPolygons,
								  tData.mDepth,
								  frontPolys,
								  backPolys);

	if (!node->IsLeaf()) // node was subdivided
	{
		Debug << "node was subdivided" << endl; Debug.flush();
		BspInterior *interior = dynamic_cast<BspInterior *>(node);

		// push the children on the stack (there are always two children)
		tStack.push(BspTraversalData(interior->GetBack(), interior, backPolys, tData.mDepth + 1));
		tStack.push(BspTraversalData(interior->GetFront(), interior, frontPolys, tData.mDepth + 1));
	}
	else // traversal terminates
	{
		Debug << "eval stats" << endl; Debug.flush();
		EvaluateLeafStats(tData);

        BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);

		// add view cell if in negative halfspace (== inside object) 
		// or if there is still geometry left
		if (viewCell && 
			(!node->GetParent() || (node == node->GetParent()->GetBack()) || 
			 (tData.mPolygons->size() > 0)))
		{
			Debug << "** view cell inserted **\n";
			leaf->SetViewCell(viewCell);
		}

		Debug << "storing or deleting polygons: " << mStorePolys << endl; Debug.flush();
		// add or delete remaining polygons
		if (mStorePolys)
			leaf->AddPolygons(tData.mPolygons);
		else
			CLEAR_CONTAINER(*tData.mPolygons);

		DEL_PTR(tData.mPolygons);
		Debug << "deleted polygon container" << endl; Debug.flush();
	}

	return node;
}


BspNode *BspTree::SubdivideNode(BspLeaf *leaf, 
								BspInterior *parent, 
								PolygonContainer *polys, 
								const int depth, 
								PolygonContainer *frontPolys, 
								PolygonContainer *backPolys)
{
	if (leaf->GetViewCell() && (polys->size() == 0))
		Debug << "error: no distinct view cells!!!!!!!!!!!\n";
	
	// terminate traversal  
	if (//!leaf->GetViewCell() && 
		((polys->size() <= mTermMaxPolygons) || (depth >= mTermMaxDepth)))
	{Debug << "subdividing node termination" << endl; Debug.flush();
		return leaf;
	}

	 mStat.nodes += 2;

	// add the new nodes to the tree + select subdivision plane
	BspInterior *node = new BspInterior(SelectPlane(polys)); 

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

	// split polygon according to current plane
	int splits = 0;
		
	Debug << "splipoly" << endl; Debug.flush();
	node->SplitPolygons(polys, frontPolys, backPolys, splits, mStorePolys);
	
 	mStat.splits += splits;

	// two new leaves
	BspLeaf *back = new BspLeaf(node);
	BspLeaf *front = new BspLeaf(node);

	// replace a link from node's parent
	if (parent)
		parent->ReplaceChildLink(leaf, node);
	
	// and setup child links
	node->SetupChildLinks(back, front);
	
	DEL_PTR(leaf); // leaf not member of tree anymore
	
	return node;
}

Plane3 BspTree::SelectPlane(PolygonContainer *polys)  const
{
	if (polys->size() == 0)
	{
		Debug << "Warning: No split candidate available\n";
		return Plane3();
	}

	// simple strategy: just take next polygon
	if (sSplitPlaneStrategy == NEXT_POLYGON)
	{
		return polys->front()->GetSupportingPlane();
	}
	
	// use heuristics to find appropriate plane
	return SelectPlaneHeuristics(polys, sMaxCandidates);
}

Plane3 BspTree::SelectPlaneHeuristics(PolygonContainer *polygons, int maxTests) const
{
	int lowestCost = INITIAL_COST;
	Plane3 *bestPlane = NULL;
	
	int limit = Min((int)polygons->size(), maxTests);

	for (int i = 0; i < limit; ++i)
	{
		int candidateIdx = Random((int)polygons->size());
		Plane3 candidatePlane = (*polygons)[candidateIdx]->GetSupportingPlane();
		
		// evaluate current candidate
		int candidateCost = EvalSplitPlane(polygons, candidatePlane);
			
		if (candidateCost < lowestCost)
		{
			bestPlane = &candidatePlane;
			lowestCost = candidateCost;
			//Debug << "new plane cost " << lowestCost << endl;
		}
	}
		
	return *bestPlane;
}

int BspTree::EvalSplitPlane(PolygonContainer *polygons, const Plane3 &candidatePlane) const
{
	PolygonContainer::const_iterator it;

	int sum = 0, sum2 = 0;

	for (it = polygons->begin(); it < polygons->end(); ++ it)
	{
		int classification = (*it)->ClassifyPlane(candidatePlane);
		
		if ((sSplitPlaneStrategy == BALANCED_TREE) || (sSplitPlaneStrategy == COMBINED))
		{
			sum += sBalancedTreeTable[classification];
		}
		
		if ((sSplitPlaneStrategy == LEAST_SPLITS) || (sSplitPlaneStrategy == COMBINED))
		{
			sum2 += sLeastSplitsTable[classification];
		}
	}

	// return linear combination of both sums
	return abs(sum) + abs(sum2);
}

void BspTree::ParseEnvironment()
{
	environment->GetIntValue("BspTree.Termination.maxDepth", sTermMaxDepth);
	environment->GetIntValue("BspTree.Termination.maxPolygons", sTermMaxPolygons);
	environment->GetIntValue("BspTree.maxCandidates", sMaxCandidates);

	//-- extract strategy to choose the next split plane
	char splitPlaneStrategyStr[60];

	environment->GetStringValue("BspTree.splitPlaneStrategy", splitPlaneStrategyStr);
	
	sSplitPlaneStrategy = BspTree::NEXT_POLYGON;
	
	if (strcmp(splitPlaneStrategyStr, "nextPolygon") == 0)
		sSplitPlaneStrategy = BspTree::NEXT_POLYGON;
	else if (strcmp(splitPlaneStrategyStr, "leastSplits") == 0)
		sSplitPlaneStrategy = BspTree::LEAST_SPLITS;
	else if (strcmp(splitPlaneStrategyStr, "balancedTree") == 0)
		sSplitPlaneStrategy = BspTree::BALANCED_TREE;
	else 
	{
		cerr << "Wrong BSP split plane strategy " << splitPlaneStrategyStr << endl;
		exit(1);
    }

	//-- parse BSP tree construction method
	char constructionMethodStr[64];
	
	environment->GetStringValue("BspTree.constructionMethod", constructionMethodStr);

	sConstructionMethod = BspTree::VIEW_CELLS;
	
	if (strcmp(constructionMethodStr, "viewCells") == 0)
		sConstructionMethod = BspTree::VIEW_CELLS;
	else if (strcmp(constructionMethodStr, "sceneGeometry") == 0)
		sConstructionMethod = BspTree::SCENE_GEOMETRY;
	else if (strcmp(constructionMethodStr, "rays") == 0)
		sConstructionMethod = BspTree::RAYS;
	else 
	{
		cerr << "Wrong bsp construction method " << constructionMethodStr << endl;
		exit(1);
    }

}

void BspTree::CollectLeaves(vector<BspLeaf *> &leaves)
{
	stack<BspNode *> nodeStack;
	nodeStack.push(mRoot);
 
	while (!nodeStack.empty()) 
	{
		BspNode *node = nodeStack.top();
    
		nodeStack.pop();
    
		if (node->IsLeaf()) 
		{
			BspLeaf *leaf = (BspLeaf *)node;
			
			leaves.push_back(leaf);
		} else 
		{
			BspInterior *interior = dynamic_cast<BspInterior *>(node);
			nodeStack.push(interior->GetBack());
			nodeStack.push(interior->GetFront());
		}
	}
}

int BspTree::CollectLeafPvs()
{
	int totalPvsSize = 0;
  
	stack<BspNode *> nodeStack;
  
	nodeStack.push(mRoot);
  
	while (!nodeStack.empty()) 
	{
		BspNode *node = nodeStack.top();
		
		nodeStack.pop();
		
		if (node->IsLeaf()) 
		{
			BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);

			ViewCell *viewcell = leaf->GetViewCell();
			
			if (!viewcell->Mailed()) 
			{
				viewcell->Mail(); // what does mail mean?
					
				// add this node to pvs of all nodes it can see
				BspPvsMap::iterator ni; 
	  
	/*			for (ni = object->mBspPvs.mEntries.begin(); ni != object->mKdPvs.mEntries.end(); ni++) 
				{
					BspNode *node = (*ni).first;
	    
					// $$ JB TEMPORARY solution -> should add object PVS or explictly computed
					// BSP tree PVS
	    			if (leaf->mBspPvs.AddNodeSample(node))
						totalPvsSize++;
				}*/
			}
		} else 
		{
			// traverse tree
			BspInterior *interior = (BspInterior *)node;
      
			nodeStack.push(interior->GetFront());
			nodeStack.push(interior->GetBack());
		}
	}

	return totalPvsSize;
}

AxisAlignedBox3 BspTree::GetBoundingBox() const
{
	return mBox;
}

BspNode *BspTree::GetRoot() const
{
	return mRoot;
}

bool BspTree::StorePolys() const
{
	return mStorePolys;
}

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

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

	// store maximal depth
	if (data.mDepth > mStat.maxDepth)
		mStat.maxDepth = data.mDepth;

#ifdef _DEBUG
	Debug << "BSP Traversal data. Depth: " << data.mDepth << " (max: " << mTermMaxDepth<< "), #polygons: " << 
	  data.mPolygons->size() << " (max: " << mTermMaxPolygons << ")" << endl;
#endif
}

int BspTree::CastRay(Ray &ray)
{
	int hits = 0;
  
	stack<BspRayTraversalData> tStack;
  
	float maxt = 1e6;
	float mint = 0;

	Intersectable::NewMail();

	// test with tree bounding box
	if (!mBox.GetMinMaxT(ray, &mint, &maxt))
		return 0;

	if (mint < 0)
		mint = 0;
  
	maxt += Limits::Threshold;
  
	Vector3 entp = ray.Extrap(mint);
	Vector3 extp = ray.Extrap(maxt);
  
	BspNode *node = mRoot;
	BspNode *farChild;
	
	while (1)
	{
		if (!node->IsLeaf()) 
		{
			BspInterior *in = (BspInterior *) node;
			
			Plane3 *splitPlane = in->GetPlane();

			float t = 0;
			bool coplanar = false;
		
			int entSide = splitPlane->Side(entp);
			int extSide = splitPlane->Side(extp);

			Vector3 intersection;

			if (entSide < 0)
			{
				node = in->GetBack();

				if(extSide <= 0) 
					continue;
					
				farChild = in->GetFront(); // plane splits ray

			} else if (entSide > 0)
			{
				node = in->GetFront();

				if (extSide >= 0)
					continue;

				farChild = in->GetBack();	 // plane splits ray			
			}
			else // ray and plane are coincident // WHAT TO DO IN THIS CASE ?
			{
				node = in->GetFront();
				continue;
			}

			//-- split

			// push data for far child
			tStack.push(BspRayTraversalData(farChild, extp, maxt));

			// find intersection with plane between ray origin and exit point
			extp = splitPlane->FindIntersection(ray.GetLoc(), extp, &maxt);

		} else // compute intersections with objects in leaf
		{
			BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
			//ray.leaves.push_back(leaf);
      // TODO
   			/*ObjectContainer::const_iterator mi;
			for (mi = leaf->mObjects.begin(); mi != leaf->mObjects.end(); ++mi) 
			{
				Intersectable *object = *mi;
				if (!object->Mailed()) 
				{
					object->Mail();
					//ray.meshes.push_back(mesh);
					hits += object->CastRay(ray);
				}
			}*/

			if (hits && ray.GetType() == Ray::LOCAL_RAY)
				if (ray.intersections[0].mT <= maxt)
					break;
      
			// get the next node from the stack
			if (tStack.empty())
				break;
      
			entp = extp;
			mint = maxt;
			BspRayTraversalData &s  = tStack.top();

			node = s.mNode;
			extp = s.mExitPoint;
			maxt = s.mMaxT;

			tStack.pop();
		}
	}

	return hits;
}

bool BspTree::Export(const string filename)
{
	Exporter *exporter = Exporter::GetExporter(filename);

	if (exporter) 
	{
		exporter->ExportBspTree(*this);
		delete exporter;

		return true;
	}	

	return false;
}
//} // GtpVisibilityPreprocessor