Index: trunk/VUT/GtpVisibilityPreprocessor/src/VspKdTree.cpp
===================================================================
--- trunk/VUT/GtpVisibilityPreprocessor/src/VspKdTree.cpp	(revision 453)
+++ trunk/VUT/GtpVisibilityPreprocessor/src/VspKdTree.cpp	(revision 462)
@@ -25,9 +25,12 @@
 #include "Ray.h"
 #include "RayInfo.h"
+#include "ViewCell.h"
 #include "ViewCellsManager.h"
-#include "ViewCell.h"
+#include "ViewCellBsp.h"
 
 // Static variables
-int VspKdTreeLeaf::mailID = 0;
+int VspKdLeaf::sMailId = 0;
+int MergeCandidate::sMaxPvsSize = 150;
+
 
 #define USE_FIXEDPOINT_T 0
@@ -70,31 +73,31 @@
 
 /**************************************************************/
-/*                class VspKdTreeNode implementation          */
+/*                class VspKdNode implementation          */
 /**************************************************************/
 
 // Inline constructor
-VspKdTreeNode::VspKdTreeNode(VspKdTreeInterior *p):
+VspKdNode::VspKdNode(VspKdInterior *p):
 mParent(p), mAxis(-1), mDepth(p ? p->mDepth + 1 : 0) 
 {}
 
-VspKdTreeNode::~VspKdTreeNode() 
+VspKdNode::~VspKdNode() 
 {};
 
-inline VspKdTreeInterior *VspKdTreeNode::GetParent() const
+inline VspKdInterior *VspKdNode::GetParent() const
 {
 	return mParent;
 }
 
-inline void VspKdTreeNode::SetParent(VspKdTreeInterior *p)
+inline void VspKdNode::SetParent(VspKdInterior *p)
 {
 	mParent = p;
 }
 
-bool VspKdTreeNode::IsLeaf() const 
+bool VspKdNode::IsLeaf() const 
 { 
 	return mAxis == -1; 
 }
   
-int VspKdTreeNode::GetAccessTime() 
+int VspKdNode::GetAccessTime() 
 {
 	return 0x7FFFFFF;
@@ -102,18 +105,18 @@
 
 /**************************************************************/
-/*                VspKdTreeInterior implementation            */
+/*                VspKdInterior implementation            */
 /**************************************************************/
 
-VspKdTreeInterior::VspKdTreeInterior(VspKdTreeInterior *p):
-VspKdTreeNode(p), mBack(NULL), mFront(NULL), mAccesses(0), mLastAccessTime(-1)
-{
-}
-
-int VspKdTreeInterior::GetAccessTime()
+VspKdInterior::VspKdInterior(VspKdInterior *p):
+VspKdNode(p), mBack(NULL), mFront(NULL), mAccesses(0), mLastAccessTime(-1)
+{
+}
+
+int VspKdInterior::GetAccessTime()
 {
 	return mLastAccessTime;
 }
 
-void VspKdTreeInterior::SetupChildLinks(VspKdTreeNode *b, VspKdTreeNode *f) 
+void VspKdInterior::SetupChildLinks(VspKdNode *b, VspKdNode *f) 
 {
 	mBack = b;
@@ -123,6 +126,6 @@
 }
 
-void VspKdTreeInterior::ReplaceChildLink(VspKdTreeNode *oldChild, 
-										 VspKdTreeNode *newChild)
+void VspKdInterior::ReplaceChildLink(VspKdNode *oldChild, 
+										 VspKdNode *newChild)
 {
 	if (mBack == oldChild)
@@ -132,10 +135,10 @@
 }
 
-int VspKdTreeInterior::Type() const  
+int VspKdInterior::Type() const  
 { 
 	return EInterior; 
 }
   
-VspKdTreeInterior::~VspKdTreeInterior()
+VspKdInterior::~VspKdInterior()
 {
 	DEL_PTR(mBack);
@@ -143,5 +146,5 @@
 }
   
-void VspKdTreeInterior::Print(ostream &s) const 
+void VspKdInterior::Print(ostream &s) const 
 {
 	switch (mAxis)
@@ -161,15 +164,15 @@
 }
 	
-int VspKdTreeInterior::ComputeRayIntersection(const RayInfo &rayData, float &t) 
+int VspKdInterior::ComputeRayIntersection(const RayInfo &rayData, float &t) 
 {
 	return rayData.ComputeRayIntersection(mAxis, mPosition, t);
 }
 
-VspKdTreeNode *VspKdTreeInterior::GetBack() const
+VspKdNode *VspKdInterior::GetBack() const
 {
 	return mBack;
 }
 
-VspKdTreeNode *VspKdTreeInterior::GetFront() const
+VspKdNode *VspKdInterior::GetFront() const
 {
 	return mFront;
@@ -178,26 +181,29 @@
 
 /**************************************************************/
-/*              class VspKdTreeLeaf implementation            */
+/*              class VspKdLeaf implementation            */
 /**************************************************************/
-VspKdTreeLeaf::VspKdTreeLeaf(VspKdTreeInterior *p,	const int nRays):
-VspKdTreeNode(p), mRays(), mPvsSize(0), mValidPvs(false), mViewCell(NULL)
+
+
+VspKdLeaf::VspKdLeaf(VspKdInterior *p,	const int nRays):
+VspKdNode(p), mRays(), mPvsSize(0), mValidPvs(false), mViewCell(NULL)
 {
 	mRays.reserve(nRays);
 }
 
-VspKdTreeLeaf::~VspKdTreeLeaf() 
-{}
-
-int VspKdTreeLeaf::Type() const  
+VspKdLeaf::~VspKdLeaf() 
+{
+}
+
+int VspKdLeaf::Type() const  
 { 
 	return ELeaf; 
 }
 
-void VspKdTreeLeaf::Print(ostream &s) const 
+void VspKdLeaf::Print(ostream &s) const 
 {
 	s << endl << "L: r = " << (int)mRays.size() << endl;
 };
 
-void VspKdTreeLeaf::AddRay(const RayInfo &data) 
+void VspKdLeaf::AddRay(const RayInfo &data) 
 {
 	mValidPvs = false;
@@ -206,50 +212,55 @@
 }
 
-int VspKdTreeLeaf::GetPvsSize() const 
+int VspKdLeaf::GetPvsSize() const 
 {
 	return mPvsSize;
 }
 
-void VspKdTreeLeaf::SetPvsSize(const int s) 
+void VspKdLeaf::SetPvsSize(const int s) 
 {
 	mPvsSize = s;
 }
 
-void VspKdTreeLeaf::Mail()
+void VspKdLeaf::Mail()
 { 
-	mMailbox = mailID; 
-}
-
-void VspKdTreeLeaf::NewMail() 
+	mMailbox = sMailId; 
+}
+
+void VspKdLeaf::NewMail() 
 { 
-	++ mailID; 
-}
-
-bool VspKdTreeLeaf::Mailed() const 
+	++ sMailId; 
+}
+
+bool VspKdLeaf::Mailed() const 
 { 
-	return mMailbox == mailID; 
-}
-
-bool VspKdTreeLeaf::Mailed(const int mail) 
-{
-	return mMailbox >= mailID + mail;
-}
-
-float VspKdTreeLeaf::GetAvgRayContribution() const 
+	return mMailbox == sMailId; 
+}
+
+bool VspKdLeaf::Mailed(const int mail) const
+{
+	return mMailbox == mail;
+}
+
+int VspKdLeaf::GetMailbox() const
+{
+	return mMailbox;
+}
+
+float VspKdLeaf::GetAvgRayContribution() const 
 {
 	return GetPvsSize() / ((float)mRays.size() + Limits::Small);
 }
 
-float VspKdTreeLeaf::GetSqrRayContribution() const 
+float VspKdLeaf::GetSqrRayContribution() const 
 {
 	return sqr(GetAvgRayContribution());
 }
 
-RayInfoContainer &VspKdTreeLeaf::GetRays()
+RayInfoContainer &VspKdLeaf::GetRays()
 {
 	return mRays;
 }
 
-void VspKdTreeLeaf::ExtractPvs(ObjectContainer &objects) const
+void VspKdLeaf::ExtractPvs(ObjectContainer &objects) const
 {
 	RayInfoContainer::const_iterator it, it_end = mRays.end();
@@ -264,5 +275,5 @@
 }
 
-void VspKdTreeLeaf::GetRays(VssRayContainer &rays)
+void VspKdLeaf::GetRays(VssRayContainer &rays)
 {
 	RayInfoContainer::const_iterator it, it_end = mRays.end();
@@ -272,147 +283,16 @@
 }
 
-ViewCell *VspKdTreeLeaf::GetViewCell()
+VspKdViewCell *VspKdLeaf::GetViewCell()
 {
 	return mViewCell;
 }
 
-/*********************************************************/
-/*            class VspKdTree implementation             */
-/*********************************************************/
-
-
-VspKdTree::VspKdTree(): mOnlyDrivingAxis(true)
-{	  
-	environment->GetIntValue("VspKdTree.Termination.maxDepth", mTermMaxDepth);
-	environment->GetIntValue("VspKdTree.Termination.minPvs", mTermMinPvs);
-	environment->GetIntValue("VspKdTree.Termination.minRays", mTermMinRays);
-	environment->GetFloatValue("VspKdTree.Termination.maxRayContribution", mTermMaxRayContribution);
-	environment->GetFloatValue("VspKdTree.Termination.maxCostRatio", mTermMaxCostRatio);
-	environment->GetFloatValue("VspKdTree.Termination.minSize", mTermMinSize);
-
-	mTermMinSize = sqr(mTermMinSize);
-
-	environment->GetFloatValue("VspKdTree.epsilon", mEpsilon);
-	environment->GetFloatValue("VspKdTree.ct_div_ci", mCtDivCi);
-	
-	environment->GetFloatValue("VspKdTree.maxTotalMemory", mMaxTotalMemory);
-	environment->GetFloatValue("VspKdTree.maxStaticMemory", mMaxStaticMemory);
-    
-	environment->GetIntValue("VspKdTree.accessTimeThreshold", mAccessTimeThreshold);
-	environment->GetIntValue("VspKdTree.minCollapseDepth", mMinCollapseDepth);
-
-	// split type
-	char sname[128];
-	environment->GetStringValue("VspKdTree.splitType", sname);
-	string name(sname);
-		
-	Debug << "======= vsp kd tree options ========" << endl;
-	Debug << "max depth: "<< mTermMaxDepth << endl;
-	Debug << "min pvs: "<< mTermMinPvs << endl;
-	Debug << "min rays: "<< mTermMinRays << endl;
-	Debug << "max ray contribution: "<< mTermMaxRayContribution << endl;
-	Debug << "max cost ratio: "<< mTermMaxCostRatio << endl;
-	Debug << "min size: "<<mTermMinSize << endl;
-
-	if (name.compare("regular") == 0)
-	{
-		Debug << "using regular split" << endl;
-		splitType = ESplitRegular;
-	}
-	else
-	{
-		if (name.compare("heuristic") == 0)
-		{
-			Debug << "using heuristic split" << endl;
-			splitType = ESplitHeuristic;
-		}
-		else 
-		{
-			cerr << "Invalid VspKdTree split type " << name << endl;
-			exit(1);
-		}
-	}
-
-	mRoot = NULL;
-
-	mSplitCandidates = new vector<SortableEntry>;
-}
-
-
-VspKdTree::~VspKdTree()
-{
-	DEL_PTR(mRoot);
-	DEL_PTR(mSplitCandidates);
-}
-
-void VspKdStatistics::Print(ostream &app) const
-{
-	app << "===== VspKdTree statistics ===============\n";
-
-	app << "#N_RAYS ( Number of rays )\n"
-		<< rays << endl;
-  
-	app << "#N_INITPVS ( Initial PVS size )\n"
-		<< initialPvsSize << 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 in axes x y z dx dy dz \n";
-  
-	for (int i=0; i<7; i++)
-		app << splits[i] <<" ";
-	app << endl;
-
-	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_MAXRAYREFS  ( Max number of rayRefs / leaf )\n" <<
-		maxRayRefs << "\n";
-
-  //  app << setprecision(4);
-
-	app << "#N_PMAXDEPTHLEAVES ( Percentage of leaves at maxdepth )\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_PMINSIZELEAVES  ( Percentage of leaves with minSize )\n"<<
-		minSizeNodes * 100 / (double)Leaves() << endl;
-
-	app << "#N_PMAXRAYCONTRIBLEAVES  ( Percentage of leaves with maximal ray contribution )\n" <<
-		maxRayContribNodes * 100 / (double)Leaves() << 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_MAXPVS ( Maximal PVS size / leaf)\n"
-		<< maxPvsSize << endl;
-
-	app << "#N_CTIME  ( Construction time [s] )\n"
-		<< Time() << " \n";
-
-	app << "===== END OF VspKdTree statistics ==========\n";
-}
-
-
-void
-VspKdTreeLeaf::UpdatePvsSize()
+void VspKdLeaf::SetViewCell(VspKdViewCell *viewCell)
+{
+	mViewCell = viewCell;
+}
+
+
+void VspKdLeaf::UpdatePvsSize()
 {
 	if (!mValidPvs) 
@@ -449,8 +329,180 @@
 }
 
-
-void
-VspKdTree::Construct(const VssRayContainer &rays,
-					 AxisAlignedBox3 *forcedBoundingBox)
+/*********************************************************/
+/*            class VspKdTree implementation             */
+/*********************************************************/
+
+
+
+VspKdTree::VspKdTree(): mOnlyDrivingAxis(true)
+{	  
+	environment->GetIntValue("VspKdTree.Termination.maxDepth", mTermMaxDepth);
+	environment->GetIntValue("VspKdTree.Termination.minPvs", mTermMinPvs);
+	environment->GetIntValue("VspKdTree.Termination.minRays", mTermMinRays);
+	environment->GetFloatValue("VspKdTree.Termination.maxRayContribution", mTermMaxRayContribution);
+	environment->GetFloatValue("VspKdTree.Termination.maxCostRatio", mTermMaxCostRatio);
+	environment->GetFloatValue("VspKdTree.Termination.minSize", mTermMinSize);
+
+	mTermMinSize = sqr(mTermMinSize);
+
+	environment->GetFloatValue("VspKdTree.epsilon", mEpsilon);
+	environment->GetFloatValue("VspKdTree.ct_div_ci", mCtDivCi);
+	
+	environment->GetFloatValue("VspKdTree.maxTotalMemory", mMaxTotalMemory);
+	environment->GetFloatValue("VspKdTree.maxStaticMemory", mMaxStaticMemory);
+    
+	environment->GetIntValue("VspKdTree.accessTimeThreshold", mAccessTimeThreshold);
+	environment->GetIntValue("VspKdTree.minCollapseDepth", mMinCollapseDepth);
+
+	environment->GetFloatValue("VspKdTree.maxCostRatio", mMaxCostRatio);
+	environment->GetIntValue("ViewCells.maxViewCells", mMaxViewCells);
+
+	MergeCandidate::sMaxPvsSize = 300; // TODO: add option
+
+	// split type
+	char sname[128];
+	environment->GetStringValue("VspKdTree.splitType", sname);
+	string name(sname);
+		
+	Debug << "======= vsp kd tree options ========" << endl;
+	Debug << "max depth: "<< mTermMaxDepth << endl;
+	Debug << "min pvs: "<< mTermMinPvs << endl;
+	Debug << "min rays: "<< mTermMinRays << endl;
+	Debug << "max ray contribution: "<< mTermMaxRayContribution << endl;
+	Debug << "max cost ratio: "<< mTermMaxCostRatio << endl;
+	Debug << "min size: "<<mTermMinSize << endl;
+
+	if (name.compare("regular") == 0)
+	{
+		Debug << "using regular split" << endl;
+		splitType = ESplitRegular;
+	}
+	else
+	{
+		if (name.compare("heuristic") == 0)
+		{
+			Debug << "using heuristic split" << endl;
+			splitType = ESplitHeuristic;
+		}
+		else 
+		{
+			cerr << "Invalid VspKdTree split type " << name << endl;
+			exit(1);
+		}
+	}
+
+	mRoot = NULL;
+
+	mSplitCandidates = new vector<SortableEntry>;
+}
+
+
+VspKdTree::~VspKdTree()
+{
+	DEL_PTR(mRoot);
+	DEL_PTR(mSplitCandidates);
+}
+
+void VspKdStatistics::Print(ostream &app) const
+{
+	app << "===== VspKdTree statistics ===============\n";
+
+	app << "#N_RAYS ( Number of rays )\n"
+		<< rays << endl;
+  
+	app << "#N_INITPVS ( Initial PVS size )\n"
+		<< initialPvsSize << 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 in axes x y z dx dy dz \n";
+  
+	for (int i=0; i<7; i++)
+		app << splits[i] <<" ";
+	app << endl;
+
+	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_MAXRAYREFS  ( Max number of rayRefs / leaf )\n" <<
+		maxRayRefs << "\n";
+
+  //  app << setprecision(4);
+
+	app << "#N_PMAXDEPTHLEAVES ( Percentage of leaves at maxdepth )\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_PMINSIZELEAVES  ( Percentage of leaves with minSize )\n"<<
+		minSizeNodes * 100 / (double)Leaves() << endl;
+
+	app << "#N_PMAXRAYCONTRIBLEAVES  ( Percentage of leaves with maximal ray contribution )\n" <<
+		maxRayContribNodes * 100 / (double)Leaves() << 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_( Maximal PVS size / leaf)\n"
+		<< maxPvsSize << endl;
+
+	app << "#N_CTIME  ( Construction time [s] )\n"
+		<< Time() << " \n";
+
+	app << "===== END OF VspKdTree statistics ==========\n";
+}
+
+
+void VspKdTree::CollectViewCells(ViewCellContainer &viewCells) const
+{
+	stack<VspKdNode *> nodeStack;
+	nodeStack.push(mRoot);
+
+	ViewCell::NewMail();
+
+	while (!nodeStack.empty()) 
+	{
+		VspKdNode *node = nodeStack.top();
+		nodeStack.pop();
+
+		if (node->IsLeaf()) 
+		{
+			ViewCell *viewCell = dynamic_cast<VspKdLeaf *>(node)->mViewCell;
+
+			if (!viewCell->Mailed()) 
+			{
+				viewCell->Mail();
+				viewCells.push_back(viewCell);
+			}
+		}
+		else 
+		{
+			VspKdInterior *interior = dynamic_cast<VspKdInterior *>(node);
+
+			nodeStack.push(interior->GetFront());
+			nodeStack.push(interior->GetBack());
+		}
+	}
+}
+
+void VspKdTree::Construct(const VssRayContainer &rays,
+						  AxisAlignedBox3 *forcedBoundingBox)
 {
 	mStat.Start();
@@ -459,8 +511,8 @@
 	DEL_PTR(mRoot);
 
-	mRoot = new VspKdTreeLeaf(NULL, (int)rays.size());
+	mRoot = new VspKdLeaf(NULL, (int)rays.size());
 
 	// first construct a leaf that will get subdivided
-	VspKdTreeLeaf *leaf = dynamic_cast<VspKdTreeLeaf *>(mRoot);
+	VspKdLeaf *leaf = dynamic_cast<VspKdLeaf *>(mRoot);
 	
 	mStat.nodes = 1;
@@ -523,7 +575,7 @@
 
 
-VspKdTreeNode *VspKdTree::Subdivide(const TraversalData &tdata)
-{
-	VspKdTreeNode *result = NULL;
+VspKdNode *VspKdTree::Subdivide(const TraversalData &tdata)
+{
+	VspKdNode *result = NULL;
 
 	priority_queue<TraversalData> tStack;
@@ -562,5 +614,5 @@
 		tStack.pop();    
 		
-		VspKdTreeNode *node = SubdivideNode((VspKdTreeLeaf *) data.mNode,
+		VspKdNode *node = SubdivideNode((VspKdLeaf *) data.mNode,
 											data.mBox, backBox,	frontBox);
 		if (result == NULL)
@@ -569,5 +621,5 @@
 		if (!node->IsLeaf()) 
 		{
-			VspKdTreeInterior *interior = dynamic_cast<VspKdTreeInterior *>(node);
+			VspKdInterior *interior = dynamic_cast<VspKdInterior *>(node);
 
 			// push the children on the stack
@@ -586,5 +638,5 @@
 
 // returns selected plane for subdivision
-int VspKdTree::SelectPlane(VspKdTreeLeaf *leaf,
+int VspKdTree::SelectPlane(VspKdLeaf *leaf,
 						   const AxisAlignedBox3 &box,
 						   float &position,
@@ -641,5 +693,5 @@
 
 							
-float VspKdTree::EvalCostRatio(VspKdTreeLeaf *leaf,
+float VspKdTree::EvalCostRatio(VspKdLeaf *leaf,
 							   const int axis,
 							   const float position,
@@ -711,5 +763,5 @@
 }
 
-float VspKdTree::BestCostRatioRegular(VspKdTreeLeaf *leaf,
+float VspKdTree::BestCostRatioRegular(VspKdLeaf *leaf,
 									  int &axis,
 									  float &position,
@@ -772,5 +824,5 @@
 }
 
-float VspKdTree::BestCostRatioHeuristic(VspKdTreeLeaf *leaf,
+float VspKdTree::BestCostRatioHeuristic(VspKdLeaf *leaf,
 										int &axis,
 										float &position,
@@ -895,5 +947,5 @@
 }
 
-void VspKdTree::SortSplitCandidates(VspKdTreeLeaf *node,
+void VspKdTree::SortSplitCandidates(VspKdLeaf *node,
 									const int axis)
 {
@@ -930,5 +982,5 @@
 {
 	// the node became a leaf -> evaluate stats for leafs
-	VspKdTreeLeaf *leaf = dynamic_cast<VspKdTreeLeaf *>(data.mNode);
+	VspKdLeaf *leaf = dynamic_cast<VspKdLeaf *>(data.mNode);
 
 	if (leaf->GetPvsSize() > mStat.maxPvsSize)
@@ -956,10 +1008,10 @@
 
 
-inline bool VspKdTree::TerminationCriteriaMet(const VspKdTreeLeaf *leaf, 
+inline bool VspKdTree::TerminationCriteriaMet(const VspKdLeaf *leaf, 
 											  const AxisAlignedBox3 &box) const
 {
 	return ((leaf->GetPvsSize() < mTermMinPvs) || 
 		    (leaf->mRays.size() < mTermMinRays) ||
-			(leaf->GetAvgRayContribution() > mTermMaxRayContribution ) ||
+			//(leaf->GetAvgRayContribution() > mTermMaxRayContribution ) ||
 			(leaf->mDepth >= mTermMaxDepth) || 
 			(SqrMagnitude(box.Size()) <= mTermMinSize));
@@ -967,5 +1019,5 @@
 
 
-VspKdTreeNode *VspKdTree::SubdivideNode(VspKdTreeLeaf *leaf,
+VspKdNode *VspKdTree::SubdivideNode(VspKdLeaf *leaf,
 										const AxisAlignedBox3 &box,
 										AxisAlignedBox3 &backBBox,
@@ -1005,5 +1057,5 @@
 
 	// add the new nodes to the tree
-	VspKdTreeInterior *node = new VspKdTreeInterior(leaf->mParent);
+	VspKdInterior *node = new VspKdInterior(leaf->mParent);
 
 	node->mAxis = axis;
@@ -1014,7 +1066,7 @@
 	frontBBox = box;
 
-	VspKdTreeLeaf *back = new VspKdTreeLeaf(node, raysBack);
+	VspKdLeaf *back = new VspKdLeaf(node, raysBack);
 	back->SetPvsSize(pvsBack);
-	VspKdTreeLeaf *front = new VspKdTreeLeaf(node, raysFront);
+	VspKdLeaf *front = new VspKdLeaf(node, raysFront);
 	front->SetPvsSize(pvsFront);
 
@@ -1025,5 +1077,5 @@
 	node->SetupChildLinks(back, front);
 	
-	if (axis <= VspKdTreeNode::SPLIT_Z) 
+	if (axis <= VspKdNode::SPLIT_Z) 
 	{
 		backBBox.SetMax(axis, position);
@@ -1110,5 +1162,5 @@
 int VspKdTree::ReleaseMemory(const int time)
 {
-	stack<VspKdTreeNode *> tstack;
+	stack<VspKdNode *> tstack;
 
 	// find a node in the tree which subtree will be collapsed
@@ -1120,10 +1172,10 @@
 	while (!tstack.empty())
 	{
-		VspKdTreeNode *node = tstack.top();
+		VspKdNode *node = tstack.top();
 		tstack.pop();
     
 		if (!node->IsLeaf()) 
 		{
-			VspKdTreeInterior *in = dynamic_cast<VspKdTreeInterior *>(node);
+			VspKdInterior *in = dynamic_cast<VspKdInterior *>(node);
 			// cout<<"depth="<<(int)in->depth<<" time="<<in->lastAccessTime<<endl;
 			if (in->mDepth >= mMinCollapseDepth && in->mLastAccessTime <= maxAccessTime) 
@@ -1156,8 +1208,8 @@
 
 
-VspKdTreeNode *VspKdTree::SubdivideLeaf(VspKdTreeLeaf *leaf,
+VspKdNode *VspKdTree::SubdivideLeaf(VspKdLeaf *leaf,
 										const float sizeThreshold)
 {
-	VspKdTreeNode *node = leaf;
+	VspKdNode *node = leaf;
 
 	AxisAlignedBox3 leafBBox = GetBBox(leaf);
@@ -1188,5 +1240,5 @@
 						   VssRayContainer &add)
 {
-	VspKdTreeLeaf::NewMail();
+	VspKdLeaf::NewMail();
 
 	// schedule rays for removal
@@ -1218,5 +1270,5 @@
 
 void VspKdTree::RemoveRay(VssRay *ray,
-						  vector<VspKdTreeLeaf *> *affectedLeaves,
+						  vector<VspKdLeaf *> *affectedLeaves,
 						  const bool removeAllScheduledRays)
 {
@@ -1243,5 +1295,5 @@
 			// remove the ray from the leaf
 			// find the ray in the leaf and swap it with the last ray...
-			VspKdTreeLeaf *leaf = (VspKdTreeLeaf *)data.mNode;
+			VspKdLeaf *leaf = (VspKdLeaf *)data.mNode;
       
 			if (!leaf->Mailed()) 
@@ -1329,5 +1381,5 @@
 			// remove the ray from the leaf
 			// find the ray in the leaf and swap it with the last ray
-			VspKdTreeLeaf *leaf = dynamic_cast<VspKdTreeLeaf *>(data.mNode);
+			VspKdLeaf *leaf = dynamic_cast<VspKdLeaf *>(data.mNode);
 
 			leaf->AddRay(data.mRayData);
@@ -1340,7 +1392,7 @@
 									 stack<RayTraversalData> &tstack)
 {
-	VspKdTreeInterior *in = dynamic_cast<VspKdTreeInterior *>(data.mNode);
-  
-	if (in->mAxis <= VspKdTreeNode::SPLIT_Z) 
+	VspKdInterior *in = dynamic_cast<VspKdInterior *>(data.mNode);
+  
+	if (in->mAxis <= VspKdNode::SPLIT_Z) 
 	{
 	    // determine the side of this ray with respect to the plane
@@ -1387,9 +1439,9 @@
 
 
-int VspKdTree::CollapseSubtree(VspKdTreeNode *sroot, const int time)
+int VspKdTree::CollapseSubtree(VspKdNode *sroot, const int time)
 {
 	// first count all rays in the subtree
 	// use mail 1 for this purpose
-	stack<VspKdTreeNode *> tstack;
+	stack<VspKdNode *> tstack;
 	
 	int rayCount = 0;
@@ -1413,9 +1465,9 @@
 		++ collapsedNodes;
 		
-		VspKdTreeNode *node = tstack.top();
+		VspKdNode *node = tstack.top();
 		tstack.pop();
 		if (node->IsLeaf()) 
 		{
-			VspKdTreeLeaf *leaf = (VspKdTreeLeaf *) node;
+			VspKdLeaf *leaf = (VspKdLeaf *) node;
 			
 			for(RayInfoContainer::iterator ri = leaf->mRays.begin();
@@ -1433,6 +1485,6 @@
 		else 
 		{
-			tstack.push(((VspKdTreeInterior *)node)->GetFront());
-			tstack.push(((VspKdTreeInterior *)node)->GetBack());
+			tstack.push(((VspKdInterior *)node)->GetFront());
+			tstack.push(((VspKdInterior *)node)->GetBack());
 		}
 	}
@@ -1441,5 +1493,5 @@
 
 	// create a new node that will hold the rays
-	VspKdTreeLeaf *newLeaf = new VspKdTreeLeaf(sroot->mParent, rayCount);
+	VspKdLeaf *newLeaf = new VspKdLeaf(sroot->mParent, rayCount);
 	
 	if (newLeaf->mParent)
@@ -1450,10 +1502,10 @@
 	while (!tstack.empty()) 
 	{
-		VspKdTreeNode *node = tstack.top();
+		VspKdNode *node = tstack.top();
 		tstack.pop();
 
 		if (node->IsLeaf()) 
 		{
-			VspKdTreeLeaf *leaf = dynamic_cast<VspKdTreeLeaf *>(node);
+			VspKdLeaf *leaf = dynamic_cast<VspKdLeaf *>(node);
 
 			for(RayInfoContainer::iterator ri = leaf->mRays.begin();
@@ -1476,6 +1528,6 @@
 		else 
 		{
-			VspKdTreeInterior *interior = 
-				dynamic_cast<VspKdTreeInterior *>(node);
+			VspKdInterior *interior = 
+				dynamic_cast<VspKdInterior *>(node);
 			tstack.push(interior->GetBack());
 			tstack.push(interior->GetFront());
@@ -1486,5 +1538,5 @@
 	DEL_PTR(sroot);
   
-	// for(VspKdTreeNode::SRayContainer::iterator ri = newleaf->mRays.begin();
+	// for(VspKdNode::SRayContainer::iterator ri = newleaf->mRays.begin();
     //      ri != newleaf->mRays.end(); ++ ri)
 	//     (*ri).ray->UnMail(2);
@@ -1510,7 +1562,7 @@
 
 
-int VspKdTree::GetPvsSize(VspKdTreeNode *node, const AxisAlignedBox3 &box) const
-{
-	stack<VspKdTreeNode *> tstack;
+int VspKdTree::GetPvsSize(VspKdNode *node, const AxisAlignedBox3 &box) const
+{
+	stack<VspKdNode *> tstack;
 	tstack.push(mRoot);
 
@@ -1520,10 +1572,10 @@
 	while (!tstack.empty()) 
 	{
-		VspKdTreeNode *node = tstack.top();
+		VspKdNode *node = tstack.top();
 		tstack.pop();
     
 	  if (node->IsLeaf()) 
 		{
-			VspKdTreeLeaf *leaf = (VspKdTreeLeaf *)node;
+			VspKdLeaf *leaf = (VspKdLeaf *)node;
 			for (RayInfoContainer::iterator ri = leaf->mRays.begin();
 				 ri != leaf->mRays.end(); ++ ri)
@@ -1552,5 +1604,5 @@
 		else 
 		{
-			VspKdTreeInterior *in = dynamic_cast<VspKdTreeInterior *>(node);
+			VspKdInterior *in = dynamic_cast<VspKdInterior *>(node);
 	
 			if (in->mAxis < 3) 
@@ -1578,5 +1630,5 @@
 											 float &avgRayContribution)
 {
-	stack<VspKdTreeNode *> tstack;
+	stack<VspKdNode *> tstack;
 	tstack.push(mRoot);
 	
@@ -1589,10 +1641,10 @@
 	while (!tstack.empty()) 
 	{
-		VspKdTreeNode *node = tstack.top();
+		VspKdNode *node = tstack.top();
 		tstack.pop();
 		if (node->IsLeaf()) 
 		{
 			leaves++;
-			VspKdTreeLeaf *leaf = (VspKdTreeLeaf *)node;
+			VspKdLeaf *leaf = (VspKdLeaf *)node;
 			float c = leaf->GetAvgRayContribution();
 
@@ -1605,5 +1657,5 @@
 		} 
 		else {
-			VspKdTreeInterior *in = (VspKdTreeInterior *)node;
+			VspKdInterior *in = (VspKdInterior *)node;
 			// both nodes for directional splits
 			tstack.push(in->GetFront());
@@ -1621,15 +1673,15 @@
 							SimpleRayContainer &rays)
 {
-	stack<VspKdTreeNode *> tstack;
+	stack<VspKdNode *> tstack;
 	tstack.push(mRoot);
 	
 	while (!tstack.empty()) 
 	{
-		VspKdTreeNode *node = tstack.top();
+		VspKdNode *node = tstack.top();
 		tstack.pop();
 		
 		if (node->IsLeaf()) 
 		{
-			VspKdTreeLeaf *leaf = dynamic_cast<VspKdTreeLeaf *>(node);
+			VspKdLeaf *leaf = dynamic_cast<VspKdLeaf *>(node);
 
 			float c = leaf->GetAvgRayContribution();
@@ -1649,6 +1701,6 @@
 		else 
 		{
-			VspKdTreeInterior *in = 
-				dynamic_cast<VspKdTreeInterior *>(node);
+			VspKdInterior *in = 
+				dynamic_cast<VspKdInterior *>(node);
 			// both nodes for directional splits
 			tstack.push(in->GetFront());
@@ -1663,5 +1715,5 @@
 float VspKdTree::GetAvgPvsSize()
 {
-	stack<VspKdTreeNode *> tstack;
+	stack<VspKdNode *> tstack;
 	tstack.push(mRoot);
 
@@ -1671,10 +1723,10 @@
 	while (!tstack.empty()) 
 	{
-		VspKdTreeNode *node = tstack.top();
+		VspKdNode *node = tstack.top();
 		tstack.pop();
 		
 		if (node->IsLeaf()) 
 		{
-			VspKdTreeLeaf *leaf = (VspKdTreeLeaf *)node;
+			VspKdLeaf *leaf = (VspKdLeaf *)node;
 			// update pvs size
 			leaf->UpdatePvsSize();
@@ -1684,5 +1736,5 @@
 		else 
 		{
-			VspKdTreeInterior *in = (VspKdTreeInterior *)node;
+			VspKdInterior *in = (VspKdInterior *)node;
 			// both nodes for directional splits
 			tstack.push(in->GetFront());
@@ -1694,10 +1746,10 @@
 }
 
-VspKdTreeNode *VspKdTree::GetRoot() const
+VspKdNode *VspKdTree::GetRoot() const
 {
 	return mRoot;
 }
 
-AxisAlignedBox3 VspKdTree::GetBBox(VspKdTreeNode *node) const
+AxisAlignedBox3 VspKdTree::GetBBox(VspKdNode *node) const
 {
 	if (node->mParent == NULL)
@@ -1705,5 +1757,5 @@
 
 	if (!node->IsLeaf())
-		return (dynamic_cast<VspKdTreeInterior *>(node))->mBox;
+		return (dynamic_cast<VspKdInterior *>(node))->mBox;
 
 	if (node->mParent->mAxis >= 3)
@@ -1740,6 +1792,6 @@
 	return 
 		(sizeof(VspKdTree) + 
-		 mStat.Leaves() * sizeof(VspKdTreeLeaf) +
-		 mStat.Interior() * sizeof(VspKdTreeInterior) +
+		 mStat.Leaves() * sizeof(VspKdLeaf) +
+		 mStat.Interior() * sizeof(VspKdInterior) +
 		 mStat.rayRefs * sizeof(RayInfo)) / (1024.0f * 1024.0f);
 }
@@ -1750,5 +1802,5 @@
 }
 
-int VspKdTree::ComputePvsSize(VspKdTreeNode *node, 
+int VspKdTree::ComputePvsSize(VspKdNode *node, 
 							  const RayInfoContainer &globalRays) const
 {
@@ -1766,12 +1818,12 @@
 }
 
-void VspKdTree::CollectLeaves(vector<VspKdTreeLeaf *> &leaves) const
-{
-	stack<VspKdTreeNode *> nodeStack;
+void VspKdTree::CollectLeaves(vector<VspKdLeaf *> &leaves) const
+{
+	stack<VspKdNode *> nodeStack;
 	nodeStack.push(mRoot);
 
 	while (!nodeStack.empty()) 
 	{
-		VspKdTreeNode *node = nodeStack.top();
+		VspKdNode *node = nodeStack.top();
 		
 		nodeStack.pop();
@@ -1779,10 +1831,10 @@
 		if (node->IsLeaf()) 
 		{
-			VspKdTreeLeaf *leaf = dynamic_cast<VspKdTreeLeaf *>(node);
+			VspKdLeaf *leaf = dynamic_cast<VspKdLeaf *>(node);
 			leaves.push_back(leaf);
 		} 
 		else 
 		{
-			VspKdTreeInterior *interior = dynamic_cast<VspKdTreeInterior *>(node);
+			VspKdInterior *interior = dynamic_cast<VspKdInterior *>(node);
 
 			nodeStack.push(interior->GetBack());
@@ -1792,9 +1844,9 @@
 }
 
-int VspKdTree::FindNeighbors(VspKdTreeLeaf *n,
-							 vector<VspKdTreeLeaf *> &neighbors,
+int VspKdTree::FindNeighbors(VspKdLeaf *n,
+							 vector<VspKdLeaf *> &neighbors,
 							 bool onlyUnmailed)
 {
-	stack<VspKdTreeNode *> nodeStack;
+	stack<VspKdNode *> nodeStack;
   
 	nodeStack.push(mRoot);
@@ -1804,10 +1856,10 @@
 	while (!nodeStack.empty()) 
 	{
-		VspKdTreeNode *node = nodeStack.top();
+		VspKdNode *node = nodeStack.top();
 		nodeStack.pop();
 
 		if (node->IsLeaf()) 
 		{
-			VspKdTreeLeaf *leaf = dynamic_cast<VspKdTreeLeaf *>(node);
+			VspKdLeaf *leaf = dynamic_cast<VspKdLeaf *>(node);
 
 			if (leaf != n && (!onlyUnmailed || !leaf->Mailed())) 
@@ -1816,5 +1868,5 @@
 		else 
 		{
-			VspKdTreeInterior *interior = dynamic_cast<VspKdTreeInterior *>(node);
+			VspKdInterior *interior = dynamic_cast<VspKdInterior *>(node);
 
 			if (interior->mPosition > box.Max(interior->mAxis))
@@ -1837,35 +1889,351 @@
 }
 
-void VspKdTree::MergeLeaves()
-{
-	vector<VspKdTreeLeaf *> leaves;
-	priority_queue<LeafPair> mergeCandidates;
-	vector<VspKdTreeLeaf *> neighbors;
-
+
+
+void VspKdTree::SetViewCellsManager(ViewCellsManager *vcm)
+{
+	mViewCellsManager = vcm;
+}
+
+
+int VspKdTree::CastRay(Ray &ray)
+{
+	int hits = 0;
+  
+	stack<RayTraversalData> tStack;
+  
+	float maxt = 1e6;
+	float mint = 0;
+
+	Intersectable::NewMail();
+
+	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);
+  
+	VspKdNode *node = mRoot;
+	VspKdNode *farChild;
+
+	float position;
+	int axis;
+  
+	while (1) 
+	{
+		if (!node->IsLeaf()) 
+		{
+			VspKdInterior *in = dynamic_cast<VspKdInterior *>(node);
+			position = in->mPosition;
+			axis = in->mAxis;
+
+			if (entp[axis] <= position) 
+			{
+				if (extp[axis] <= position) 
+				{
+					node = in->mBack;
+					// cases N1,N2,N3,P5,Z2,Z3
+					continue;
+				} else 
+				{
+					// case N4
+					node = in->mBack;
+					farChild = in->mFront;
+				}
+			}
+			else 
+			{
+				if (position <= extp[axis]) 
+				{
+					node = in->mFront;
+					// cases P1,P2,P3,N5,Z1
+					continue;
+				} 
+				else 
+				{
+					node = in->mFront;
+					farChild = in->mBack;
+					// case P4
+				}
+			}
+
+ 			// $$ modification 3.5.2004 - hints from Kamil Ghais
+			// case N4 or P4
+			float tdist = (position - ray.GetLoc(axis)) / ray.GetDir(axis);
+			//tStack.push(RayTraversalData(farChild, extp, maxt)); //TODO
+			extp = ray.GetLoc() + ray.GetDir()*tdist;
+			maxt = tdist;
+		} 
+		else 
+		{
+			// compute intersection with all objects in this leaf
+			/*KdLeaf *leaf = (KdLeaf *) node;
+			if (ray.mFlags & Ray::STORE_KDLEAVES)
+				ray.kdLeaves.push_back(leaf);
+			
+			ObjectContainer::const_iterator mi;
+			for ( mi = leaf->mObjects.begin(); mi != leaf->mObjects.end(); mi++) 
+			{
+				Intersectable *object = *mi;
+				if (!object->Mailed() ) 
+				{
+					object->Mail();
+					if (ray.mFlags & Ray::STORE_TESTED_OBJECTS)
+						ray.testedObjects.push_back(object);
+					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;
+			if (ray.GetType() == Ray::LINE_SEGMENT && mint > 1.0f)
+				break;
+			
+			RayTraversalData &s  = tStack.top();
+			node = s.mNode;
+			extp = s.mExitPoint;
+			maxt = s.mMaxT;
+			tStack.pop();
+			*/
+		}
+	}
+	
+	return hits;
+}
+
+
+void VspKdTree::GenerateViewCell(VspKdLeaf *leaf)
+{
+	RayInfoContainer::const_iterator it, it_end = leaf->GetRays().end();
+
+	VspKdViewCell *vc = dynamic_cast<VspKdViewCell *>(mViewCellsManager->GenerateViewCell());
+	leaf->SetViewCell(vc);
+
+	vc->SetSize(GetBBox(leaf).GetVolume());
+	vc->mVspKdLeaves.push_back(leaf);
+
+	for (it = leaf->GetRays().begin(); it != it_end; ++ it)
+	{
+		VssRay *ray = (*it).mRay;
+
+		if (ray->mTerminationObject)
+			vc->GetPvs().AddSample(ray->mTerminationObject);
+		
+		if (ray->mOriginObject)
+			vc->GetPvs().AddSample(ray->mOriginObject);
+	}
+}
+
+
+void VspKdTree::EvaluateViewCellsStats(ViewCellsStatistics &vcStat) const
+{
+	vcStat.Reset();
+
+	stack<VspKdNode *> nodeStack;
+	nodeStack.push(mRoot);
+
+	ViewCell::NewMail();
+
+	// exclude root cell
+	//mRootCell->Mail();
+
+	while (!nodeStack.empty()) 
+	{
+		VspKdNode *node = nodeStack.top();
+		nodeStack.pop();
+
+		if (node->IsLeaf()) 
+		{
+			++ vcStat.leaves;
+
+			VspKdViewCell *viewCell = dynamic_cast<VspKdLeaf *>(node)->mViewCell;
+
+			if (!viewCell->Mailed()) 
+			{
+				viewCell->Mail();
+				
+				++ vcStat.viewCells;
+				const int pvsSize = viewCell->GetPvs().GetSize();
+
+                vcStat.pvs += pvsSize;
+
+				if (pvsSize < 1)
+					++ vcStat.emptyPvs;
+
+				if (pvsSize > vcStat.maxPvs)
+					vcStat.maxPvs = pvsSize;
+
+				if (pvsSize < vcStat.minPvs)
+					vcStat.minPvs = pvsSize;
+
+				if ((int)viewCell->mVspKdLeaves.size() > vcStat.maxLeaves)
+					vcStat.maxLeaves = (int)viewCell->mVspKdLeaves.size();		
+			}
+		}
+		else 
+		{
+			VspKdInterior *interior = dynamic_cast<VspKdInterior *>(node);
+
+			nodeStack.push(interior->GetFront());
+			nodeStack.push(interior->GetBack());
+		}
+	}
+}
+
+
+bool VspKdTree::MergeViewCells(VspKdLeaf *l1, VspKdLeaf *l2)
+{
+	//-- change pointer to view cells of all leaves associated with the previous view cells
+	VspKdViewCell *fVc = l1->GetViewCell();
+	VspKdViewCell *bVc = l2->GetViewCell();
+
+	VspKdViewCell *vc = dynamic_cast<VspKdViewCell *>(
+		mViewCellsManager->MergeViewCells(*fVc, *bVc));
+
+	// if merge was unsuccessful
+	if (!vc) return false;
+
+	// set new size of view cell
+	vc->SetSize(fVc->GetSize() + bVc->GetSize());
+
+	vector<VspKdLeaf *> fLeaves = fVc->mVspKdLeaves;
+	vector<VspKdLeaf *> bLeaves = bVc->mVspKdLeaves;
+
+	vector<VspKdLeaf *>::const_iterator it;
+
+	//-- change view cells of all the other leaves the view cell belongs to
+	for (it = fLeaves.begin(); it != fLeaves.end(); ++ it)
+	{
+		(*it)->SetViewCell(vc);
+		vc->mVspKdLeaves.push_back(*it);
+	}
+
+	for (it = bLeaves.begin(); it != bLeaves.end(); ++ it)
+	{
+		(*it)->SetViewCell(vc);
+		vc->mVspKdLeaves.push_back(*it);
+	}
+
+	// clean up old view cells
+	DEL_PTR(fVc);
+	DEL_PTR(bVc);
+
+	return true;
+}
+
+
+
+int VspKdTree::MergeLeaves()
+{
+	vector<VspKdLeaf *> leaves;
+	priority_queue<MergeCandidate> mergeQueue;
+	
+	// collect the leaves, e.g., the "voxels" that will build the view cells
 	CollectLeaves(leaves);
 
-	VspKdTreeLeaf::NewMail();
-
-	vector<VspKdTreeLeaf *>::const_iterator it, it_end = leaves.end();
-
-
+	int vcSize = (int)leaves.size();
+
+	VspKdLeaf::NewMail();
+
+	vector<VspKdLeaf *>::const_iterator it, it_end = leaves.end();
+
+	// generate view cells
 	for (it = leaves.begin(); it != it_end; ++ it)
-	{
-		VspKdTreeLeaf *leaf = *it;
-
+		GenerateViewCell(*it);
+
+	// find merge candidates and push them into queue
+	for (it = leaves.begin(); it != it_end; ++ it)
+	{
+		VspKdLeaf *leaf = *it;
+		
+		// no leaf is part of two merge candidates
 		if (!leaf->Mailed())
 		{
+			leaf->Mail();
+
+			vector<VspKdLeaf *> neighbors;
 			FindNeighbors(leaf, neighbors, true);
 
-			vector<VspKdTreeLeaf *>::const_iterator nit, nit_end = neighbors.end();
-
-			for (nit = neighbors.begin(); nit != neighbors.end(); ++ nit)
-				mergeCandidates.push(LeafPair(leaf, *nit));
+			vector<VspKdLeaf *>::const_iterator nit, 
+				nit_end = neighbors.end();
+
+			for (nit = neighbors.begin(); nit != nit_end; ++ nit)
+				mergeQueue.push(MergeCandidate(leaf, *nit));
+		}
+	}
+
+	int merged = 0;
+
+	float savedMaxCostRatio = 0;
+
+	Debug << "merge cost " << mergeQueue.top().GetMergeCost() << " of " << mMaxCostRatio << endl;
+
+	// use priority queue to merge leaves
+	while (!mergeQueue.empty() && 
+		   ((mMaxViewCells < vcSize) ||
+		    (mergeQueue.top().GetMergeCost() < mMaxCostRatio)))
+	{
+		ViewCell::NewMail();
+
+		Debug << "=====================" << endl;
+		MergeCandidate mc = mergeQueue.top();
+		mergeQueue.pop();
+		
+		if (mc.GetLeaf1()->GetViewCell() == mc.GetLeaf2()->GetViewCell())
+		// both view cells the same!
+		{
+			Debug << "same view cell!!" << endl;
+			-- vcSize;
+
+			continue;
+		}
+
+		if (mc.Valid())
+		{
+			mc.GetLeaf1()->GetViewCell()->Mail();
+			mc.GetLeaf2()->GetViewCell()->Mail();
 			
-			leaf->Mail();
-		}
-	}
-}
-
+			Debug << "merging cells with cost " << mc.GetMergeCost() << " of " << mMaxCostRatio << endl;
+			savedMaxCostRatio = mc.GetMergeCost();
+
+			MergeViewCells(mc.GetLeaf1(), mc.GetLeaf2());
+			
+			++ merged;
+			-- vcSize;
+		}
+		// merge candidate not valid, because one of the leaves was already
+		// merged with another one
+		else 
+		{
+			Debug << "not valid " << mc.GetMergeCost() << endl;
+			
+			// validate and reinsert into queue
+			mc.SetValid();
+			Debug << "ag. valid " << mc.GetMergeCost() << endl;
+
+			mergeQueue.push(mc);
+		}
+	}
+
+	if (mergeQueue.empty())
+		Debug << "empty queue" << endl;
+	
+	Debug << "max cost ratio: " << savedMaxCostRatio << endl;
+
+	return merged;
+}
 
 
@@ -1875,27 +2243,88 @@
 
 
-MergeCandidate::MergeCandidate(VspKdTreeLeaf *l1, VspKdTreeLeaf *l2):
-mLeaf1(l1), mLeaf2(l2)
-{}
-
-float MergeCandidate::EvaluateMergeCost() const
-{
-	// pvs difference
-	VspKdViewCell *vc1 = dynamic_cast<VspKdViewCell *>(mLeaf1->GetViewCell());
-	VspKdViewCell *vc2 = dynamic_cast<VspKdViewCell *>(mLeaf2->GetViewCell());
+MergeCandidate::MergeCandidate(VspKdLeaf *l1, VspKdLeaf *l2):
+mMergeCost(0),
+mLeaf1(l1),
+mLeaf2(l2),
+mLeaf1Id(l1->GetViewCell()->mMailbox),
+mLeaf2Id(l2->GetViewCell()->mMailbox)
+{
+	EvalMergeCost();
+}
+
+
+void MergeCandidate::EvalMergeCost()
+{
+	// compute pvs differences
+	VspKdViewCell *vc1 = mLeaf1->GetViewCell();
+	VspKdViewCell *vc2 = mLeaf2->GetViewCell();
+	
+	//VspKdViewCell *vc1 = dynamic_cast<VspKdViewCell *>(mLeaf1->GetViewCell());
+	//VspKdViewCell *vc2 = dynamic_cast<VspKdViewCell *>(mLeaf2->GetViewCell());
 
 	const int diff1 = vc1->GetPvs().Diff(vc2->GetPvs());
-	
-	//const int diff2 = vc2->GetPvs().Diff(vc1->GetPvs());
-	//const float simDiff = (float)max(diff1, diff2);
-
+	const int vcPvs = diff1 + vc1->GetPvs().GetSize();
+
+	//-- compute ratio of old cost 
+	//-- (added size of left and right view cell times pvs size)
+	//-- to new rendering cost (size of merged view cell times pvs size)
 	const float oldCost = 
-		vc1->GetSize() * vc1->GetPvs().GetSize() + 
-		vc2->GetSize() * vc2->GetPvs().GetSize();
-
-	const float mergedPvsCost = 
-		(diff1 + vc1->GetPvs().GetSize()) *
-		(vc1->GetSize() + vc2->GetSize());
-
-	return mergedPvsCost / oldCost;
-}
+		(float)vc1->GetPvs().GetSize() * vc1->GetSize() + 
+		(float)vc2->GetPvs().GetSize() * vc2->GetSize();
+
+	const float newCost = 
+		(float)vcPvs * (vc1->GetSize() + vc2->GetSize());
+
+	mMergeCost = newCost / oldCost;
+
+	Debug << "******************************" << endl;
+	Debug << "pvs size: " << vcPvs << " max: " << sMaxPvsSize << endl;
+	if (vcPvs > sMaxPvsSize) // strong penalty if pvs size too large
+		mMergeCost += 1.0;
+
+	Debug << "old cost: " << oldCost << endl;
+	Debug << "new cost: " << newCost << endl;
+}
+
+void MergeCandidate::SetLeaf1(VspKdLeaf *l)
+{
+	mLeaf1 = l;
+}
+
+void MergeCandidate::SetLeaf2(VspKdLeaf *l)
+{
+	mLeaf2 = l;
+}
+
+VspKdLeaf *MergeCandidate::GetLeaf1()
+{
+	return mLeaf1;
+}
+
+VspKdLeaf *MergeCandidate::GetLeaf2()
+{
+	return mLeaf2;
+}
+
+bool MergeCandidate::Valid() const
+{	
+	//Debug << mLeaf1->GetViewCell()->mMailbox << " " << mLeaf1Id << endl;
+	//Debug << mLeaf2->GetViewCell()->mMailbox << " " << mLeaf2Id << endl;
+
+	return 
+		(mLeaf1->GetViewCell()->mMailbox == mLeaf1Id) && 
+		(mLeaf2->GetViewCell()->mMailbox == mLeaf2Id);
+}
+
+float MergeCandidate::GetMergeCost() const
+{
+	return mMergeCost;
+}
+
+void MergeCandidate::SetValid()
+{
+	mLeaf1Id = mLeaf1->GetViewCell()->mMailbox;
+	mLeaf2Id = mLeaf2->GetViewCell()->mMailbox;
+	
+	EvalMergeCost();
+}
