Index: trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.cpp
===================================================================
--- trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.cpp	(revision 484)
+++ trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.cpp	(revision 485)
@@ -33,5 +33,5 @@
 int VspBspTree::sFrontAndBackId = 0;
 
-float BspMergeCandidate::sOverallCost = Limits::Small;
+float BspMergeCandidate::sOverallCost = 0;
 
 /****************************************************************/
@@ -44,9 +44,7 @@
 mCostNormalizer(Limits::Small),
 mViewCellsManager(NULL),
-mStoreRays(true),
+mStoreRays(false),
 mOnlyDrivingAxis(false)
 {
-	mRootCell = new BspViewCell();
-
 	Randomize(); // initialise random generator for heuristics
 
@@ -82,4 +80,6 @@
 	environment->GetFloatValue("VspBspTree.PostProcess.maxCostRatio", mMergeMaxCostRatio);
 
+	environment->GetBoolValue("VspBspTree.splitUseOnlyDrivingAxis", mOnlyDrivingAxis);
+	environment->GetBoolValue("VspBspTree.PostProcess.useRaysForMerge", mUseRaysForMerge);
 
 	//-- debug output
@@ -137,5 +137,4 @@
 {
 	DEL_PTR(mRoot);
-	DEL_PTR(mRootCell);
 	DEL_PTR(mSplitCandidates);
 }
@@ -216,5 +215,5 @@
 		{
 			mBox.Include(object->GetBox()); // add to BSP tree aabb
-			AddMeshToPolygons(mesh, polys, mRootCell);
+			AddMeshToPolygons(mesh, polys, NULL);
 		}
 	}
@@ -360,5 +359,5 @@
 		 (data.mPvs <= mTermMinPvs)   ||
 		 (data.mArea <= mTermMinArea) ||
-		 (mStat.nodes / 2 + 1 >= mMaxViewCells) ||
+		 (mStat.Leaves() >= mMaxViewCells) ||
 		// (data.GetAvgRayContribution() >= mTermMaxRayContribution) ||
 		 (data.mDepth >= mTermMaxDepth));
@@ -400,5 +399,5 @@
 		BspViewCell *viewCell = new BspViewCell();
 		leaf->SetViewCell(viewCell);
-
+		
 		if (mStoreRays)
 		{
@@ -410,9 +409,10 @@
 		viewCell->mLeaves.push_back(leaf);
 		viewCell->SetArea(tData.mArea);
+		leaf->mArea = tData.mArea;
 
 		//-- update pvs
 		int conSamp = 0, sampCon = 0;
 		AddToPvs(leaf, *tData.mRays, conSamp, sampCon);
-
+	
 		mStat.contributingSamples += conSamp;
 		mStat.sampleContributions += sampCon;
@@ -1065,5 +1065,4 @@
 			// add the termination object
 			AddObjToPvs(ray->mTerminationObject, cf, frontPvs, backPvs);
-
 			// add the source object
 			AddObjToPvs(ray->mOriginObject, cf, frontPvs, backPvs);
@@ -1081,7 +1080,7 @@
 				if (cf == 1)
 					pFront += len;
-				if (cf == -1)
+				else if (cf == -1)
 					pBack += len;
-				if (cf == 0)
+				else if (cf == 0)
 				{
 					// use length of rays to approximate volume
@@ -1231,7 +1230,8 @@
 		mStat.maxDepth = data.mDepth;
 
+	if (data.mPvs > mStat.maxPvs)
+		mStat.maxPvs = data.mPvs;
 	if (data.mDepth < mStat.minDepth)
 		mStat.minDepth = data.mDepth;
-
 	if (data.mDepth >= mTermMaxDepth)
 		++ mStat.maxDepthNodes;
@@ -1436,5 +1436,5 @@
 		float t;
 
-			// get classification and receive new t
+		// get classification and receive new t
 		const int cf = bRay.ComputeRayIntersection(plane, t);
 
@@ -1448,19 +1448,23 @@
 			break;
 		case 0:
-			//-- split ray
-			//--  look if start point behind or in front of plane
-			if (plane.Side(bRay.ExtrapOrigin()) <= 0)
 			{
-				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()));
+				//-- split ray
+				//-- test if start point behind or in front of plane
+				const int side = plane.Side(bRay.ExtrapOrigin());
+
+				if (side <= 0)
+				{
+					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()));
+				}
 			}
 			break;
 		default:
-			Debug << "Should not come here 4" << endl;
+			Debug << "Should not come here" << endl;
 			break;
 		}
@@ -1497,11 +1501,11 @@
 }
 
+
 void VspBspTree::ConstructGeometry(BspNode *n,
 								   BspNodeGeometry &cell) const
 {
-	PolygonContainer polys;
-	ConstructGeometry(n, polys);
-	cell.mPolys = polys;
-}
+	ConstructGeometry(n, cell.mPolys);
+}
+
 
 void VspBspTree::ConstructGeometry(BspNode *n,
@@ -1588,8 +1592,9 @@
 }
 
-void VspBspTree::ConstructGeometry(BspViewCell *vc, PolygonContainer &vcGeom) const
+
+void VspBspTree::ConstructGeometry(BspViewCell *vc, 
+								   PolygonContainer &vcGeom) const
 {
 	vector<BspLeaf *> leaves = vc->mLeaves;
-
 	vector<BspLeaf *>::const_iterator it, it_end = leaves.end();
 
@@ -1598,9 +1603,9 @@
 }
 
+
 int VspBspTree::FindNeighbors(BspNode *n, vector<BspLeaf *> &neighbors,
 						   const bool onlyUnmailed) const
 {
 	PolygonContainer cell;
-
 	ConstructGeometry(n, cell);
 
@@ -1794,8 +1799,4 @@
 }
 
-BspViewCell *VspBspTree::GetRootCell() const
-{
-	return mRootCell;
-}
 
 int VspBspTree::SplitPolygons(const Plane3 &plane,
@@ -1858,4 +1859,5 @@
 	BspNode *farChild = NULL;
 
+	float t;
 	while (1)
 	{
@@ -1865,16 +1867,18 @@
 
 			Plane3 splitPlane = in->GetPlane();
+			
 			const int entSide = splitPlane.Side(entp);
 			const int extSide = splitPlane.Side(extp);
 
-			if (entSide < 0)
+			if (entSide < 0) 
 			{
 				node = in->GetBack();
-
-				if (extSide <= 0) // plane does not split ray => no far child
+				// plane does not split ray => no far child
+				if (extSide <= 0) 
 					continue;
 
 				farChild = in->GetFront(); // plane splits ray
-			} else if (entSide > 0)
+			} 
+			else if (entSide > 0)
 			{
 				node = in->GetFront();
@@ -1885,21 +1889,21 @@
 				farChild = in->GetBack(); // plane splits ray
 			}
-			else // ray and plane are coincident
-			{
-				// WHAT TO DO IN THIS CASE ?
-				//break;
-				node = in->GetFront();
-				continue;
+			else // ray end point on plane
+			{	// NOTE: what to do if ray is coincident with plane?
+				if (extSide < 0)
+					node = in->GetBack();
+				else if (extSide > 0)
+					node = in->GetFront();
+
+				continue; // no far child
 			}
 
 			// push data for far child
-			tStack.push(BspRayTraversalData(farChild, extp, maxt));
+			tStack.push(BspRayTraversalData(farChild, extp));
 
 			// find intersection of ray segment with plane
-			float t;
 			extp = splitPlane.FindIntersection(origin, extp, &t);
-			maxt *= t;
-
-		} else
+		} 
+		else
 		{
 			// reached leaf => intersection with view cell
@@ -1918,20 +1922,18 @@
 
 			entp = extp;
-			mint = maxt; // NOTE: need this?
-
-
+			
 			BspRayTraversalData &s = tStack.top();
 
 			node = s.mNode;
 			extp = s.mExitPoint;
-			maxt = s.mMaxT;
 
 			tStack.pop();
 		}
 	}
+
 	return hits;
 }
 
-int VspBspTree::TreeDistance(BspNode *n1, BspNode *n2)
+int VspBspTree::TreeDistance(BspNode *n1, BspNode *n2) const
 {
 	std::deque<BspNode *> path1;
@@ -1997,4 +1999,7 @@
 		}
 	}
+
+	// revalidate leaves
+	RepairVcLeafLists();
 
 	return node;
@@ -2040,121 +2045,5 @@
 
 
-int VspBspTree::MergeLeaves()
-{
-	vector<BspLeaf *> leaves;
-	priority_queue<BspMergeCandidate> mergeQueue;
-
-	// collect the leaves, e.g., the "voxels" that will build the view cells
-	CollectLeaves(leaves);
-
-	int vcSize = (int)leaves.size();
-	int savedVcSize = vcSize;
-
-	BspLeaf::NewMail();
-
-	vector<BspLeaf *>::const_iterator it, it_end = leaves.end();
-
-	// find merge candidates and push them into queue
-	for (it = leaves.begin(); it != it_end; ++ it)
-	{
-		BspLeaf *leaf = *it;
-
-		// no leaf is part of two merge candidates
-		if (!leaf->Mailed())
-		{
-			leaf->Mail();
-
-			vector<BspLeaf *> neighbors;
-			FindNeighbors(leaf, neighbors, true);
-
-			vector<BspLeaf *>::const_iterator nit,
-				nit_end = neighbors.end();
-
-			for (nit = neighbors.begin(); nit != nit_end; ++ nit)
-			{
-				BspMergeCandidate mc = BspMergeCandidate(leaf, *nit);
-				mergeQueue.push(mc);
-
-				BspMergeCandidate::sOverallCost += mc.GetLeaf1Cost();
-				BspMergeCandidate::sOverallCost += mc.GetLeaf2Cost();
-			}
-		}
-	}
-
-	int merged = 0;
-	int mergedSiblings = 0;
-	int accTreeDist = 0;
-	int maxTreeDist = 0;
-	const bool mergeStats = true;
-
-
-	//-- use priority queue to merge leaf pairs
-	while (!mergeQueue.empty() && (vcSize > mMergeMinViewCells) &&
-		   (mergeQueue.top().GetMergeCost() <
-		    mMergeMaxCostRatio * BspMergeCandidate::sOverallCost))
-	{
-		//Debug << "mergecost: " << mergeQueue.top().GetMergeCost() / BspMergeCandidate::sOverallCost << " " << mMergeMaxCostRatio << endl;
-		BspMergeCandidate mc = mergeQueue.top();
-		mergeQueue.pop();
-
-		// both view cells equal!
-		if (mc.GetLeaf1()->GetViewCell() == mc.GetLeaf2()->GetViewCell())
-			continue;
-
-		if (mc.Valid())
-		{
-			ViewCell::NewMail();
-			MergeViewCells(mc.GetLeaf1(), mc.GetLeaf2());
-			-- vcSize;
-			// increase absolute merge cost
-			BspMergeCandidate::sOverallCost += mc.GetMergeCost();
-
-			//-- stats
-			++ merged;
-
-			if (mc.GetLeaf1()->IsSibling(mc.GetLeaf2()))
-				++ mergedSiblings;
-
-			if (mergeStats)
-			{
-				const int dist = TreeDistance(mc.GetLeaf1(), mc.GetLeaf2());
-
-				if (dist > maxTreeDist)
-					maxTreeDist = dist;
-
-				accTreeDist += dist;
-			}
-		}
-		// merge candidate not valid, because one of the leaves was already
-		// merged with another one
-		else
-		{
-			// validate and reinsert into queue
-			mc.SetValid();
-			mergeQueue.push(mc);
-			//Debug << "validate " << mc.GetMergeCost() << endl;
-		}
-	}
-
-	// collapse tree according to view cell partition
-	CollapseTree(mRoot);
-	// revalidate leaves
-	RepairVcLeafLists();
-
-	Debug << "Merged " << merged << " nodes of " << savedVcSize
-		  << " (merged " << mergedSiblings << " siblings)" << endl;
-
-	if (mergeStats)
-	{
-		Debug << "maximal tree distance: " << maxTreeDist << endl;
-		Debug << "Avg tree distance: " << (float)accTreeDist / (float)merged << endl;
-	}
-
-	//TODO: should return sample contributions
-	return merged;
-}
-
-
-bool VspBspTree::MergeViewCells(BspLeaf *l1, BspLeaf *l2)
+bool VspBspTree::MergeViewCells(BspLeaf *l1, BspLeaf *l2) const
 {
 	//-- change pointer to view cells of all leaves associated
@@ -2204,4 +2093,413 @@
 	mViewCellsManager = vcm;
 }
+
+
+int VspBspTree::CollectMergeCandidates()
+{
+	vector<BspLeaf *> leaves;
+
+	// collect the leaves, e.g., the "voxels" that will build the view cells
+	CollectLeaves(leaves);
+	BspLeaf::NewMail();
+
+	vector<BspLeaf *>::const_iterator it, it_end = leaves.end();
+
+	// find merge candidates and push them into queue
+	for (it = leaves.begin(); it != it_end; ++ it)
+	{
+		BspLeaf *leaf = *it;
+		
+		/// create leaf pvs (needed for post processing
+		leaf->mPvs = new ObjectPvs(leaf->GetViewCell()->GetPvs());
+
+		BspMergeCandidate::sOverallCost += 
+			leaf->mArea * leaf->mPvs->GetSize();
+
+		// the same leaves must not be part of two merge candidates
+		leaf->Mail();
+		vector<BspLeaf *> neighbors;
+		FindNeighbors(leaf, neighbors, true);
+
+		vector<BspLeaf *>::const_iterator nit, nit_end = neighbors.end();
+
+		// TODO: test if at least one ray goes from one leaf to the other
+		for (nit = neighbors.begin(); nit != nit_end; ++ nit)
+		{			
+			mMergeQueue.push(BspMergeCandidate(leaf, *nit));
+		}
+	}
+
+	return (int)leaves.size();
+}
+
+
+int VspBspTree::CollectMergeCandidates(const VssRayContainer &rays)
+{
+	vector<BspRay *> bspRays;
+
+	ConstructBspRays(bspRays, rays);
+	map<BspLeaf *, vector<BspLeaf*> > neighborMap;
+
+	vector<BspIntersection>::const_iterator iit;
+
+	int leaves = 0;
+	
+	BspLeaf::NewMail();
+
+	for (int i = 0; i < (int)bspRays.size(); ++ i)
+	{  
+		BspRay *ray = bspRays[i];
+	  
+		// traverse leaves stored in the rays and compare and 
+		// merge consecutive leaves (i.e., the neighbors in the tree)
+		if (ray->intersections.size() < 2)
+			continue;
+	  
+		iit = ray->intersections.begin();
+		BspLeaf *prevLeaf = (*(iit ++)).mLeaf;
+		
+		// create leaf pvs (needed for post processing)
+		if (!prevLeaf->mPvs)
+		{
+			prevLeaf->mPvs = 
+				new ObjectPvs(prevLeaf->GetViewCell()->GetPvs());
+
+			BspMergeCandidate::sOverallCost += 
+				prevLeaf->mArea * prevLeaf->mPvs->GetSize();
+			
+			++ leaves;
+		}
+		
+		// traverse intersections 
+		// consecutive leaves are neighbors => 
+		// add them to queue
+		for (; iit != ray->intersections.end(); ++ iit)
+		{
+            BspLeaf *leaf = (*iit).mLeaf;
+            
+			if (!leaf->mPvs)
+			{
+				leaf->mPvs = 
+					new ObjectPvs(leaf->GetViewCell()->GetPvs());
+				
+				BspMergeCandidate::sOverallCost += 
+					leaf->mArea * leaf->mPvs->GetSize();
+
+				++ leaves;
+			}
+		
+			vector<BspLeaf *> &neighbors = neighborMap[leaf];
+			
+			bool found = false;
+
+			// both leaves inserted in queue already =>
+			// look if double pair already exists
+			if (leaf->Mailed() && prevLeaf->Mailed())
+			{
+				vector<BspLeaf *>::const_iterator it, it_end = neighbors.end();
+				
+                for (it = neighbors.begin(); !found && (it != it_end); ++ it)
+					if (*it == prevLeaf)
+						found = true; // already in queue
+			}
+			
+			if (!found)
+			{
+				// this pair is not in map already
+				// => insert into the neighbor map and the queue
+				neighbors.push_back(prevLeaf);
+				neighborMap[prevLeaf].push_back(leaf);
+
+				leaf->Mail();
+				prevLeaf->Mail();
+
+				mMergeQueue.push(BspMergeCandidate(leaf, prevLeaf));
+			}
+
+			prevLeaf = leaf;
+        }
+	}
+	Debug << "neighbormap size: " << (int)neighborMap.size() << endl;
+	Debug << "mergequeue: " << (int)mMergeQueue.size() << endl;
+	Debug << "leaves in queue: " << leaves << endl;
+	Debug << "overall cost: " << BspMergeCandidate::sOverallCost << endl;
+
+	CLEAR_CONTAINER(bspRays);
+
+	return leaves;
+}
+
+
+void VspBspTree::ConstructBspRays(vector<BspRay *> &bspRays,
+								  const VssRayContainer &rays)
+{
+	VssRayContainer::const_iterator it, it_end = rays.end();
+
+	for (it = rays.begin(); it != rays.end(); ++ it)
+	{
+		VssRay *vssRay = *it;
+		BspRay *ray = new BspRay(vssRay);
+
+		ViewCellContainer viewCells;
+
+		Ray hray(*vssRay);
+		float tmin = 0, tmax = 1.0;
+		// matt TODO: remove this!!
+		//hray.Init(ray.GetOrigin(), ray.GetDir(), Ray::LINE_SEGMENT);
+		if (!mBox.GetRaySegment(hray, tmin, tmax) || (tmin > tmax))
+			continue;
+
+		Vector3 origin = hray.Extrap(tmin);
+		Vector3 termination = hray.Extrap(tmax);
+	
+		// cast line segment to get intersections with bsp leaves
+		CastLineSegment(origin, termination, viewCells);
+
+		ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
+		for (vit = viewCells.begin(); vit != vit_end; ++ vit)
+		{
+			BspViewCell *vc = dynamic_cast<BspViewCell *>(*vit);
+			vector<BspLeaf *>::const_iterator it, it_end = vc->mLeaves.end();
+			//NOTE: not sorted!
+			for (it = vc->mLeaves.begin(); it != it_end; ++ it)
+				ray->intersections.push_back(BspIntersection(0, *it));
+		}
+
+		bspRays.push_back(ray);
+	}
+}
+
+
+int VspBspTree::MergeViewCells(const VssRayContainer &rays)
+{
+	MergeStatistics mergeStats;
+	mergeStats.Start();
+	// TODO: REMOVE LATER for performance!
+	const bool showMergeStats = true;
+	//BspMergeCandidate::sOverallCost = mBox.SurfaceArea() * mStat.maxPvs;
+	long startTime = GetTime();
+
+	if (mUseRaysForMerge)
+		mergeStats.nodes = CollectMergeCandidates(rays);
+	else
+		mergeStats.nodes = CollectMergeCandidates();
+
+	mergeStats.collectTime = TimeDiff(startTime, GetTime());
+	mergeStats.candidates = (int)mMergeQueue.size();
+	startTime = GetTime();
+
+	int nViewCells = /*mergeStats.nodes*/ mStat.Leaves();
+
+	
+	//-- use priority queue to merge leaf pairs
+	while (!mMergeQueue.empty() && (nViewCells > mMergeMinViewCells) &&
+		   (mMergeQueue.top().GetMergeCost() <
+		    mMergeMaxCostRatio * BspMergeCandidate::sOverallCost))
+	{
+		//Debug << "abs mergecost: " << mMergeQueue.top().GetMergeCost() << " rel mergecost: "
+		//	  << mMergeQueue.top().GetMergeCost() / BspMergeCandidate::sOverallCost 
+		//	  << " max ratio: " << mMergeMaxCostRatio << endl;
+		BspMergeCandidate mc = mMergeQueue.top();
+		mMergeQueue.pop();
+
+		// both view cells equal!
+		if (mc.GetLeaf1()->GetViewCell() == mc.GetLeaf2()->GetViewCell())
+			continue;
+
+		if (mc.Valid())
+		{
+			ViewCell::NewMail();
+			MergeViewCells(mc.GetLeaf1(), mc.GetLeaf2());
+			-- nViewCells;
+			
+			++ mergeStats.merged;
+			
+			// increase absolute merge cost
+			BspMergeCandidate::sOverallCost += mc.GetMergeCost();
+
+			if (showMergeStats)
+			{
+				if (mc.GetLeaf1()->IsSibling(mc.GetLeaf2()))
+					++ mergeStats.siblings;
+
+				const int dist = 
+					TreeDistance(mc.GetLeaf1(), mc.GetLeaf2());
+				if (dist > mergeStats.maxTreeDist)
+					mergeStats.maxTreeDist = dist;
+				mergeStats.accTreeDist += dist;
+			}
+		}
+		// merge candidate not valid, because one of the leaves was already
+		// merged with another one => validate and reinsert into queue
+		else
+		{ 
+			mc.SetValid();
+			mMergeQueue.push(mc);
+		}
+	}
+
+	mergeStats.mergeTime = TimeDiff(startTime, GetTime());
+	mergeStats.Stop();
+
+	if (showMergeStats)
+		Debug << mergeStats << endl << endl;
+	
+	//TODO: should return sample contributions?
+	return mergeStats.merged;
+}
+
+
+int VspBspTree::RefineViewCells(const VssRayContainer &rays)
+{
+	int shuffled = 0;
+
+	Debug << "refining " << (int)mMergeQueue.size() << " candidates " << endl;
+	BspLeaf::NewMail();
+
+	// Use priority queue of remaining leaf pairs 
+	// These candidates either share the same view cells or
+	// are border leaves which share a boundary.
+	// We test if they can be shuffled, i.e.,
+	// either one leaf is made part of one view cell or the other
+	// leaf is made part of the other view cell. It is tested if the
+	// remaining view cells are "better" than the old ones.
+	while (!mMergeQueue.empty())
+	{
+		BspMergeCandidate mc = mMergeQueue.top();
+		mMergeQueue.pop();
+
+		// both view cells equal or already shuffled
+		if ((mc.GetLeaf1()->GetViewCell() == mc.GetLeaf2()->GetViewCell()) ||
+			(mc.GetLeaf1()->Mailed()) || (mc.GetLeaf2()->Mailed()))
+			continue;
+		
+		// candidate for shuffling
+		const bool wasShuffled = 
+			ShuffleLeaves(mc.GetLeaf1(), mc.GetLeaf2());
+		
+		//-- stats
+		if (wasShuffled)
+			++ shuffled;
+	}
+
+	return shuffled;
+}
+
+
+inline int AddedPvsSize(ObjectPvs pvs1, const ObjectPvs &pvs2)
+{
+	return pvs1.AddPvs(pvs2);
+}
+
+/*inline int SubtractedPvsSize(BspViewCell *vc, BspLeaf *l, const ObjectPvs &pvs2)
+{
+	ObjectPvs pvs;
+	vector<BspLeaf *>::const_iterator it, it_end = vc->mLeaves.end();
+	for (it = vc->mLeaves.begin(); it != vc->mLeaves.end(); ++ it)
+		if (*it != l)
+			pvs.AddPvs(*(*it)->mPvs);
+	return pvs.GetSize();
+}*/
+
+inline int SubtractedPvsSize(ObjectPvs pvs1, const ObjectPvs &pvs2)
+{
+	return pvs1.SubtractPvs(pvs2);
+}
+
+
+float GetShuffledVcCost(BspLeaf *leaf, BspViewCell *vc1, BspViewCell *vc2)
+{
+	//const int pvs1 = SubtractedPvsSize(vc1, leaf, *leaf->mPvs);
+	const int pvs1 = SubtractedPvsSize(vc1->GetPvs(), *leaf->mPvs);
+	const int pvs2 = AddedPvsSize(vc2->GetPvs(), *leaf->mPvs);
+
+	const float area1 = vc1->GetArea() - leaf->mArea;
+	const float area2 = vc2->GetArea() + leaf->mArea;
+
+	const float cost1 = pvs1 * area1;
+	const float cost2 = pvs2 * area2;
+
+	return cost1 + cost2;
+}
+
+
+void VspBspTree::ShuffleLeaf(BspLeaf *leaf, 
+							 BspViewCell *vc1, 
+							 BspViewCell *vc2) const
+{
+	//Debug << "old pvs: " << vc1->GetPvs().GetSize() + vc2->GetPvs().GetSize() 
+	//	  << " (" << vc1->GetPvs().GetSize() << ", " << vc2->GetPvs().GetSize() << ")" << endl;
+	// compute new pvs and area
+	vc1->GetPvs().SubtractPvs(*leaf->mPvs);
+	vc2->GetPvs().AddPvs(*leaf->mPvs);
+	
+	vc1->SetArea(vc1->GetArea() - leaf->mArea);
+	vc2->SetArea(vc2->GetArea() + leaf->mArea);
+
+	/// add to second view cell
+	vc2->mLeaves.push_back(leaf);
+
+	// erase leaf from old view cell
+	vector<BspLeaf *>::iterator it = vc1->mLeaves.begin();
+
+	for (; *it != leaf; ++ it);
+	vc1->mLeaves.erase(it);
+
+	/*vc1->GetPvs().mEntries.clear();
+	for (; it != vc1->mLeaves.end(); ++ it)
+	{
+		if (*it == leaf)
+			vc1->mLeaves.erase(it);
+		else
+			vc1->GetPvs().AddPvs(*(*it)->mPvs);
+	}*/
+
+	leaf->SetViewCell(vc2); 	// finally change view cell
+	
+	//Debug << "new pvs: " << vc1->GetPvs().GetSize() + vc2->GetPvs().GetSize() 
+	//	  << " (" << vc1->GetPvs().GetSize() << ", " << vc2->GetPvs().GetSize() << ")" << endl;
+
+}
+
+
+bool VspBspTree::ShuffleLeaves(BspLeaf *leaf1, BspLeaf *leaf2) const
+{
+	BspViewCell *vc1 = leaf1->GetViewCell();
+	BspViewCell *vc2 = leaf2->GetViewCell();
+
+	const float cost1 = vc1->GetPvs().GetSize() * vc1->GetArea();
+	const float cost2 = vc2->GetPvs().GetSize() * vc2->GetArea();
+
+	const float oldCost = cost1 + cost2;
+	
+	float shuffledCost1 = Limits::Infinity;
+	float shuffledCost2 = Limits::Infinity;
+
+	// the view cell should not be empty after the shuffle
+	if (vc1->mLeaves.size() > 1)
+		shuffledCost1 = GetShuffledVcCost(leaf1, vc1, vc2);
+	if (vc2->mLeaves.size() > 1)
+		shuffledCost2 = GetShuffledVcCost(leaf2, vc2, vc1);
+
+	// shuffling unsuccessful
+	if ((oldCost <= shuffledCost1) && (oldCost <= shuffledCost2))
+		return false;
+	
+	if (shuffledCost1 < shuffledCost2)
+	{
+		//Debug << "old cost: " << oldCost << ", new cost: " << shuffledCost1 << endl;
+		ShuffleLeaf(leaf1, vc1, vc2);
+		leaf1->Mail();
+	}
+	else
+	{
+		//Debug << "old cost: " << oldCost << ", new cost: " << shuffledCost2 << endl;
+		ShuffleLeaf(leaf2, vc2, vc1);
+		leaf2->Mail();
+	}
+
+	return true;
+}
+
 
 /************************************************************************/
@@ -2220,8 +2518,13 @@
 }
 
+float BspMergeCandidate::GetCost(ViewCell *vc) const
+{
+	return vc->GetPvs().GetSize() * vc->GetArea();
+}
+
 float BspMergeCandidate::GetLeaf1Cost() const
 {
 	BspViewCell *vc = mLeaf1->GetViewCell();
-	return vc->GetPvs().GetSize() * vc->GetArea();
+	return GetCost(vc);
 }
 
@@ -2229,5 +2532,5 @@
 {
 	BspViewCell *vc = mLeaf2->GetViewCell();
-	return vc->GetPvs().GetSize() * vc->GetVolume();
+	return GetCost(vc);
 }
 
@@ -2239,5 +2542,5 @@
 
 	const int diff1 = vc1->GetPvs().Diff(vc2->GetPvs());
-	const int vcPvs = diff1 + vc1->GetPvs().GetSize();
+	const int newPvs = diff1 + vc1->GetPvs().GetSize();
 
 	//-- compute ratio of old cost
@@ -2247,8 +2550,7 @@
 
 	const float newCost =
-		(float)vcPvs * (vc1->GetArea() + vc2->GetArea());
+		(float)newPvs * (vc1->GetArea() + vc2->GetArea());
 
 	mMergeCost = newCost - oldCost;
-
 //	if (vcPvs > sMaxPvsSize) // strong penalty if pvs size too large
 //		mMergeCost += 1.0;
@@ -2294,2 +2596,34 @@
 	EvalMergeCost();
 }
+
+
+/************************************************************************/
+/*                  MergeStatistics implementation                      */
+/************************************************************************/
+
+
+void MergeStatistics::Print(ostream &app) const
+{
+	app << "===== Merge statistics ===============\n";
+
+	app << setprecision(4);
+
+	app << "#N_CTIME ( Overall time [s] )\n" << Time() << " \n";
+
+	app << "#N_CCTIME ( Collect candidates time [s] )\n" << collectTime * 1e-3f << " \n";
+
+	app << "#N_MTIME ( Merge time [s] )\n" << mergeTime * 1e-3f << " \n";
+
+	app << "#N_NODES ( Number of nodes before merge )\n" << nodes << "\n";
+
+	app << "#N_CANDIDATES ( Number of merge candidates )\n" << candidates << "\n";
+
+	app << "#N_MERGEDSIBLINGS ( Number of merged siblings )\n" << siblings << "\n";
+	app << "#N_MERGEDNODES ( Number of merged nodes )\n" << merged << "\n";
+
+	app << "#MAX_TREEDIST ( Maximal distance in tree of merged leaves )\n" << maxTreeDist << "\n";
+
+	app << "#AVG_TREEDIST ( Average distance in tree of merged leaves )\n" << AvgTreeDist() << "\n";
+
+	app << "===== END OF BspTree statistics ==========\n";
+}
