Index: /trunk/VUT/GtpVisibilityPreprocessor/scripts/Preprocessor.vcproj
===================================================================
--- /trunk/VUT/GtpVisibilityPreprocessor/scripts/Preprocessor.vcproj	(revision 577)
+++ /trunk/VUT/GtpVisibilityPreprocessor/scripts/Preprocessor.vcproj	(revision 580)
@@ -77,5 +77,6 @@
 				Name="VCLinkerTool"
 				AdditionalDependencies="xerces-c_2.lib zdll.lib zziplib.lib devil.lib qtmain.lib QtOpenGL4.lib QtCore4.lib QtGui4.lib Qt3Supportd4.lib QAxContainer.lib glut32.lib OpenGL32.Lib glu32.lib cg.lib cgGL.lib"
-				AdditionalLibraryDirectories="..\support\xercesc\lib\;..\support\zlib\lib\;..\support\devil\lib;&quot;$(QTDIR)\lib&quot;;..\include;..\src\GL;&quot;$(CG_LIB_PATH)&quot;"/>
+				AdditionalLibraryDirectories="..\support\xercesc\lib\;..\support\zlib\lib\;..\support\devil\lib;&quot;$(QTDIR)\lib&quot;;..\include;..\src\GL;&quot;$(CG_LIB_PATH)&quot;"
+				LargeAddressAware="2"/>
 			<Tool
 				Name="VCMIDLTool"/>
Index: /trunk/VUT/GtpVisibilityPreprocessor/scripts/default.env
===================================================================
--- /trunk/VUT/GtpVisibilityPreprocessor/scripts/default.env	(revision 579)
+++ /trunk/VUT/GtpVisibilityPreprocessor/scripts/default.env	(revision 580)
@@ -176,6 +176,6 @@
 	# samples used for view cell construction
 	Construction {
-		samples 1500000
-		samplesPerPass 100000
+		samples 1200000
+		samplesPerPass 300000
 	}
 
@@ -195,5 +195,4 @@
 	maxPvsRatio 1.0
 		
-	delayedConstruction false
 	pruneEmptyViewCells false
 	processOnlyValidViewCells false
@@ -202,4 +201,10 @@
 		# how much samples are used for post processing
 		samples 300000
+		renderCostWeight 0.5
+		maxCostRatio 0.1
+		minViewCells 110
+		avgCostMaxDeviation 0.8
+		maxMergesPerPass 500 
+		useRaysForMerge false
 	}
 
@@ -213,4 +218,5 @@
 		exportRays false
 		exportGeometry true
+		exportMergedViewCells false
 	}
 	
@@ -274,4 +280,5 @@
 		epsilon 0.005
 		randomize false
+		renderCostWeight 0.5
 	}
 
@@ -331,12 +338,4 @@
 		# x3d visualization of the split planes
 		exportSplits true
-		exportMergedViewCells false
-	}
-	
-	PostProcess {
-		maxCostRatio 0.1
-		minViewCells 110
-		useRaysForMerge false
-		exportMergeStats false
 	}
 }
Index: /trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.h
===================================================================
--- /trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.h	(revision 579)
+++ /trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.h	(revision 580)
@@ -21,5 +21,5 @@
 class ViewCellsStatistics;
 class ViewCellsManager;
-class BspMergeCandidate;
+class MergeCandidate;
 class Beam;
 
@@ -252,15 +252,4 @@
 	int TreeDistance(BspNode *n1, BspNode *n2) const;
 
-	/** Merges view cells according to some cost heuristics.
-	*/
-	int MergeViewCells(const VssRayContainer &rays, const ObjectContainer &objects);
-	
-	/** Refines view cells using shuffling, i.e., border leaves 
-		of two view cells are exchanged if the resulting view cells
-		are tested to be "better" than the old ones.
-		@returns number of refined view cells
-	*/
-	int RefineViewCells(const VssRayContainer &rays, const ObjectContainer &objects);
-
 	/** Collapses the tree with respect to the view cell partition.
 		@returns number of collapsed nodes
@@ -272,12 +261,4 @@
 	ViewCell *GetViewCell(const Vector3 &point);
 
-	/** Constructs bsp rays for post processing and visualization.
-	*/
-	void ConstructBspRays(vector<BspRay *> &bspRays,
-						  const VssRayContainer &rays);
-	
-	/** Merge view cells of leaves l1 and l2.
-	*/
-	bool MergeViewCells(BspLeaf *l1, BspLeaf *l2); //const;
 
 	/** Returns true if this view point is in a valid view space,
@@ -369,9 +350,4 @@
 	BspNode *CollapseTree(BspNode *node, int &collapsed);
 
-	/** Shuffles the leaves, i.e., tests if exchanging
-		the leaves helps in improving the view cells.
-	*/
-	bool ShuffleLeaves(BspLeaf *leaf1, BspLeaf *leaf2) const;
-
 	/** Helper function revalidating the view cell leaf list after merge.
 	*/
@@ -573,14 +549,8 @@
 
 
-	/** Collects candidates for the merge in the merge queue.
-		@param leaves the leaves to be merged
-		@returns number of leaves in queue
-	*/
-	int CollectMergeCandidates(const vector<BspLeaf *> leaves);
-	/** Collects candidates for the merge in the merge queue.
-		@returns number of leaves in queue
-	*/
-	int CollectMergeCandidates(const VssRayContainer &rays);
-
+
+
+
+	
 	/** Take 3 ray endpoints, where two are minimum and one a maximum
 		point or the other way round.
@@ -599,11 +569,16 @@
 	Plane3 ChooseCandidatePlane3(const RayInfoContainer &rays) const;
   
-	/** Shuffles, i.e. takes border leaf from view cell 1 and adds it 
-		to view cell 2.
-	*/
-	void ShuffleLeaf(BspLeaf *leaf, 
-					 BspViewCell *vc1, 
-					 BspViewCell *vc2) const;
-
+	/** Collects candidates for merging.
+		@param leaves the leaves to be merged
+		@returns number of leaves in queue
+	*/
+	int CollectMergeCandidates(const vector<BspLeaf *> leaves, vector<MergeCandidate> &candidates);
+
+	/** Collects candidates for the merge in the merge queue.
+		@returns number of leaves in queue
+	*/
+	int CollectMergeCandidates(const VssRayContainer &rays, vector<MergeCandidate> &candidates);
+	
+	
 	
 	/** Propagates valid flag up the tree.
@@ -620,11 +595,5 @@
 	float GetMemUsage() const;
 
-	/** Calculates cost for merge of view cell 1 and 2.
-	*/
-	float GetShuffledVcCost(BspLeaf *leaf, BspViewCell *vc1, BspViewCell *vc2) const;
-
-	void ExportMergedViewCells(ViewCellContainer &viewCells, 
-							   const ObjectContainer &objects,
-							   const int nViewCells);
+
 
 	/// Pointer to the root of the tree
@@ -658,5 +627,5 @@
 	float mTermMinAccRayLength;
 
-	ofstream mStats;
+	
 
 	//-- termination criteria for axis aligned split
@@ -701,8 +670,5 @@
 	/// maximal number of view cells
 	int mMaxViewCells;
-	/// minimal number of view cells
-	int mMergeMinViewCells;
-	/// maximal cost ratio for the merge
-	float mMergeMaxCostRatio;
+	
 
 	// if rays should be stored in leaves
@@ -716,16 +682,8 @@
 	vector<SortableEntry> *mSplitCandidates;
 
-
-	typedef priority_queue<BspMergeCandidate> MergeQueue;
-
-	MergeQueue mMergeQueue;
-
-	/// if rays should be used to collect merge candidates
-	bool mUseRaysForMerge;
-	
+	
+	float mRenderCostWeight;
 	/// View cell corresponding to the space outside the valid view space
 	BspViewCell *mOutOfBoundsCell;
-
-	int mCurrentViewCellsId;
 
 	/// maximal tree memory
@@ -733,13 +691,8 @@
 	/// the tree is out of memory
 	bool mOutOfMemory;
-	/// if merge visualization should be shown
-	bool mExportMergedViewCells;
-	/// if merge statistics should be exported
-	bool mExportMergeStats;
-
+	
+	
 private:
-	
-	ViewCellContainer mOldViewCells;
-	ViewCellContainer mNewViewCells;
+
 
 	static const float sLeastRaySplitsTable[5];
@@ -758,150 +711,6 @@
 };
 
-/**
-	Candidate for leaf merging based on priority.
-*/
-class BspMergeCandidate
-{  
-	friend class VspBspTree;
-
-public:
-
-	BspMergeCandidate(BspLeaf *l1, BspLeaf *l2);
-
-	/** If this merge pair is still valid.
-	*/
-	bool Valid() const;
-
-	/** Sets this merge candidate to be valid.
-	*/
-	void SetValid();
-
-	friend bool operator<(const BspMergeCandidate &leafa, const BspMergeCandidate &leafb)
-	{
-		return leafb.GetMergeCost() < leafa.GetMergeCost();
-	}
-
-	void SetLeaf1(BspLeaf *l);
-	void SetLeaf2(BspLeaf *l);
-
-	BspLeaf *GetLeaf1() const;
-	BspLeaf *GetLeaf2() const;
-
-	/** Merge cost of this candidate pair.
-	*/
-	float GetMergeCost() const;
-
-	/** Render cost of this candidate.
-	*/
-	float GetRenderCost() const;
-
-	/** returns increase in variance of this view cell.
-	*/
-	float GetVarianceIncr() const;
-
-	/** Returns cost of leaf 1.
-	*/
-	float GetLeaf1Cost() const;
-	
-	/** Returns cost of leaf 2.
-	*/
-	float GetLeaf2Cost() const;
-
-	/** Variance of leaf1
-	*/
-	float GetLeaf1Variance() const;
-
-	/** Variance of leaf2
-	*/
-	float GetLeaf2Variance() const;
-
-	/// overall cost used to normalize cost ratio
-	static float sOverallCost;
-	static float sExpectedCost;
-	static float sVariance;
-
-	static int sNumViewCells;
-
-	// weights between variance and render cost increase (must between zero and one)
-	static float sRenderCostWeight;
-
-	/// if area or volume should be used for the merge heuristics
-	static bool sUseArea;
-
-	/// pointer to view cells manager
-	static ViewCellsManager *sViewCellsManager;
-
-protected:
-
-	
-	/** Evaluates the merge costs of the leaves.
-	*/
-	void EvalMergeCost();
-
-	/** render cost of a view cell.
-	*/
-	float GetRenderCost(ViewCell *vc) const;
-	
-	int mLeaf1Id;
-	int mLeaf2Id;
-
-	/// render cost increase by this merge
-	float mRenderCost;
-	/// increase / decrease of variance
-	float mVarianceIncr;
-
-	BspLeaf *mLeaf1;
-	BspLeaf *mLeaf2;
-};
-
-
-class MergeStatistics: public StatisticsBase
-{
-public:
-	
-	int merged;
-	int siblings;
-	int candidates;
-	int nodes;
-
-	int accTreeDist;
-	int maxTreeDist;
-	
-	Real collectTime;
-	Real mergeTime;
-
-	Real overallCost;
-
-	// Constructor
-	MergeStatistics() 
-	{
-		Reset();
-	}
-	
-	double AvgTreeDist() const {return (double)accTreeDist / (double)merged;}; 
-
-	void Reset() 
-	{
-		nodes = 0;
-		merged = 0;
-		siblings = 0;
-		candidates = 0;
-	
-		accTreeDist = 0;
-		maxTreeDist = 0;
-
-		collectTime = 0;
-		mergeTime = 0;
-		overallCost = 0;
-	}
-
-	void Print(ostream &app) const;
-
-	friend ostream &operator<<(ostream &s, const MergeStatistics &stat) 
-	{
-		stat.Print(s);
-		return s;
-	} 
-};
+
+
 
 #endif
Index: /trunk/VUT/GtpVisibilityPreprocessor/src/VspKdTree.cpp
===================================================================
--- /trunk/VUT/GtpVisibilityPreprocessor/src/VspKdTree.cpp	(revision 556)
+++ /trunk/VUT/GtpVisibilityPreprocessor/src/VspKdTree.cpp	(revision 580)
@@ -30,6 +30,6 @@
 // Static variables
 int VspKdLeaf::sMailId = 0;
-int MergeCandidate::sMaxPvsSize = 150;
-float MergeCandidate::sOverallCost = Limits::Small;
+int VspKdMergeCandidate::sMaxPvsSize = 150;
+float VspKdMergeCandidate::sOverallCost = Limits::Small;
 #define USE_FIXEDPOINT_T 0
 
@@ -430,5 +430,5 @@
 	environment->GetFloatValue("VspKdTree.PostProcess.maxCostRatio", mMergeMaxCostRatio);
 	environment->GetIntValue("VspKdTree.PostProcess.maxPvsSize",
-							 MergeCandidate::sMaxPvsSize);
+							 VspKdMergeCandidate::sMaxPvsSize);
 
 	environment->GetBoolValue("VspKdTree.splitUseOnlyDrivingAxis", mOnlyDrivingAxis);
@@ -2173,5 +2173,5 @@
 	vc->SetArea(GetBBox(leaf).SurfaceArea());
 
-	vc->mLeaves.push_back(leaf);
+	vc->mLeaf = leaf;
 
 	for (it = leaf->GetRays().begin(); it != it_end; ++ it)
@@ -2200,5 +2200,6 @@
 	// if merge was unsuccessful
 	if (!vc) return false;
-
+// TODO
+#if VC_HISTORY
 	// set new size of view cell
 	vc->SetVolume(fVc->GetVolume() + bVc->GetVolume());
@@ -2223,5 +2224,5 @@
 		vc->mLeaves.push_back(*it);
 	}
-
+#endif
 	vc->Mail();
 
@@ -2235,5 +2236,5 @@
 void VspKdTree::CollectMergeCandidates()
 {
-	MergeCandidate::sOverallCost = 0;
+	VspKdMergeCandidate::sOverallCost = 0;
 	vector<VspKdLeaf *> leaves;
 
@@ -2256,5 +2257,5 @@
 		// no leaf is part of two merge candidates
 		leaf->Mail();
-		MergeCandidate::sOverallCost += 
+		VspKdMergeCandidate::sOverallCost += 
 			vc->GetVolume() * vc->GetPvs().GetSize();
 		vector<VspKdLeaf *> neighbors;
@@ -2266,5 +2267,5 @@
 		for (nit = neighbors.begin(); nit != nit_end; ++ nit)
 		{
-			mMergeQueue.push(MergeCandidate(leaf, *nit));
+			mMergeQueue.push(VspKdMergeCandidate(leaf, *nit));
 		}
 	}
@@ -2273,5 +2274,5 @@
 void VspKdTree::CollectMergeCandidates(const vector<VspKdRay *> &rays)
 {
-	MergeCandidate::sOverallCost = 0;
+	VspKdMergeCandidate::sOverallCost = 0;
 
 	vector<VspKdIntersection>::const_iterator iit;
@@ -2299,9 +2300,9 @@
 			leaf->Mail
 			// TODO: how to sort out doubles?
-			MergeCandidate mc = MergeCandidate(leaf, previousLeaf);
+			VspKdMergeCandidate mc = VspKdMergeCandidate(leaf, previousLeaf);
 			mMergeQueue.push(mc);
 
-			MergeCandidate::sOverallCost += mc.GetLeaf1Cost();
-			MergeCandidate::sOverallCost += mc.GetLeaf2Cost();
+			VspKdMergeCandidate::sOverallCost += mc.GetLeaf1Cost();
+			VspKdMergeCandidate::sOverallCost += mc.GetLeaf2Cost();
 
 			previousLeaf = leaf;
@@ -2321,9 +2322,9 @@
 	while (!mMergeQueue.empty() && (vcSize > mMergeMinViewCells) &&
 		   (mMergeQueue.top().GetMergeCost() < 
-		    mMergeMaxCostRatio * MergeCandidate::sOverallCost))
+		    mMergeMaxCostRatio * VspKdMergeCandidate::sOverallCost))
 	{
 		//Debug << "mergecost: " << mergeQueue.top().GetMergeCost() / 
-		//MergeCandidate::sOverallCost << " " << mMergeMaxCostRatio << endl;
-		MergeCandidate mc = mMergeQueue.top();
+		//VspKdMergeCandidate::sOverallCost << " " << mMergeMaxCostRatio << endl;
+		VspKdMergeCandidate mc = mMergeQueue.top();
 		mMergeQueue.pop();
 
@@ -2340,5 +2341,5 @@
 			-- vcSize;
 			// increase absolute merge cost
-			MergeCandidate::sOverallCost += mc.GetMergeCost();
+			VspKdMergeCandidate::sOverallCost += mc.GetMergeCost();
 		}
 		// merge candidate not valid, because one of the leaves was already
@@ -2378,5 +2379,5 @@
 
 			VspKdViewCell *viewCell = leaf->GetViewCell();
-
+#if VC_HISTORY
 			if (!viewCell->Mailed())
 			{
@@ -2386,4 +2387,5 @@
 
 			viewCell->mLeaves.push_back(leaf);
+#endif
 		}
 		else
@@ -2468,5 +2470,5 @@
 	while (!mMergeQueue.empty())
 	{
-		MergeCandidate mc = mMergeQueue.top();
+		VspKdMergeCandidate mc = mMergeQueue.top();
 		mMergeQueue.pop();
 
@@ -2501,5 +2503,5 @@
 
 
-float GetShuffledVcCost(VspKdLeaf *leaf, VspKdViewCell *vc1, VspKdViewCell *vc2)
+float EvalShuffleCost(VspKdLeaf *leaf, VspKdViewCell *vc1, VspKdViewCell *vc2)
 {
 	const int pvs1 = SubtractedPvsSize(vc1->GetPvs(), *leaf->mPvs);
@@ -2521,4 +2523,6 @@
 {
 	// compute new pvs and area
+	//	TODO
+#if VC_HISTORY
 	vc1->GetPvs().SubtractPvs(*leaf->mPvs);
 	vc2->GetPvs().AddPvs(*leaf->mPvs);
@@ -2537,4 +2541,5 @@
 
 	leaf->SetViewCell(vc2);  // finally change view cell
+#endif
 }
 
@@ -2554,10 +2559,11 @@
 
 	// the view cell should not be empty after the shuffle
-	if (vc1->mLeaves.size() > 1)
-		shuffledCost1 = GetShuffledVcCost(leaf1, vc1, vc2);
+//todo
+	/*	if (vc1->mLeaves.size() > 1)
+		shuffledCost1 = EvalShuffleCost(leaf1, vc1, vc2);
 	if (vc2->mLeaves.size() > 1)
-		shuffledCost2 = GetShuffledVcCost(leaf2, vc2, vc1);
-
-	// shuffling unsuccessful
+		shuffledCost2 = EvalShuffleCost(leaf2, vc2, vc1);
+
+*/	// shuffling unsuccessful
 	if ((oldCost <= shuffledCost1) && (oldCost <= shuffledCost2))
 		return false;
@@ -2581,9 +2587,9 @@
 
 /*********************************************************************/
-/*                MergeCandidate implementation                      */
+/*                VspKdMergeCandidate implementation                      */
 /*********************************************************************/
 
 
-MergeCandidate::MergeCandidate(VspKdLeaf *l1, VspKdLeaf *l2):
+VspKdMergeCandidate::VspKdMergeCandidate(VspKdLeaf *l1, VspKdLeaf *l2):
 mMergeCost(0),
 mLeaf1(l1),
@@ -2595,5 +2601,5 @@
 }
 
-float MergeCandidate::GetLeaf1Cost() const
+float VspKdMergeCandidate::GetLeaf1Cost() const
 {
 	VspKdViewCell *vc = mLeaf1->GetViewCell();
@@ -2601,5 +2607,5 @@
 }
 
-float MergeCandidate::GetLeaf2Cost() const
+float VspKdMergeCandidate::GetLeaf2Cost() const
 {
 	VspKdViewCell *vc = mLeaf2->GetViewCell();
@@ -2607,5 +2613,5 @@
 }
 
-void MergeCandidate::EvalMergeCost()
+void VspKdMergeCandidate::EvalMergeCost()
 {
 	//-- compute pvs difference
@@ -2630,10 +2636,10 @@
 }
 
-void MergeCandidate::SetLeaf1(VspKdLeaf *l)
+void VspKdMergeCandidate::SetLeaf1(VspKdLeaf *l)
 {
 	mLeaf1 = l;
 }
 
-void MergeCandidate::SetLeaf2(VspKdLeaf *l)
+void VspKdMergeCandidate::SetLeaf2(VspKdLeaf *l)
 {
 	mLeaf2 = l;
@@ -2641,5 +2647,5 @@
 
 
-VspKdLeaf *MergeCandidate::GetLeaf1()
+VspKdLeaf *VspKdMergeCandidate::GetLeaf1()
 {
 	return mLeaf1;
@@ -2647,5 +2653,5 @@
 
 
-VspKdLeaf *MergeCandidate::GetLeaf2()
+VspKdLeaf *VspKdMergeCandidate::GetLeaf2()
 {
 	return mLeaf2;
@@ -2653,5 +2659,5 @@
 
 
-bool MergeCandidate::Valid() const
+bool VspKdMergeCandidate::Valid() const
 {
 	return
@@ -2661,5 +2667,5 @@
 
 
-float MergeCandidate::GetMergeCost() const
+float VspKdMergeCandidate::GetMergeCost() const
 {
 	return mMergeCost;
@@ -2667,5 +2673,5 @@
 
 
-void MergeCandidate::SetValid()
+void VspKdMergeCandidate::SetValid()
 {
 	mLeaf1Id = mLeaf1->GetViewCell()->mMailbox;
Index: /trunk/VUT/GtpVisibilityPreprocessor/src/ViewCell.cpp
===================================================================
--- /trunk/VUT/GtpVisibilityPreprocessor/src/ViewCell.cpp	(revision 564)
+++ /trunk/VUT/GtpVisibilityPreprocessor/src/ViewCell.cpp	(revision 580)
@@ -4,6 +4,79 @@
 #include "MeshKdTree.h"
 #include "Triangle3.h"
+#include "common.h"
+#include "Environment.h"
+#include "ViewCellsManager.h"
+#include "Exporter.h"
+
 #include <time.h>
 #include <iomanip>
+#include <stack>
+
+
+
+template <typename T> class myless
+{
+public:
+	
+	//bool operator() (HierarchyNode *v1, HierarchyNode *v2) const
+	bool operator() (T v1, T v2) const
+	{
+		return (v1->GetTimeStamp() > v2->GetTimeStamp());
+	}
+};
+
+
+typedef priority_queue<ViewCell *, vector<ViewCell *>, myless<vector<ViewCell *>::value_type> > TraversalQueue;
+
+int ViewCell::sMailId = 21843194198;
+int ViewCell::sReservedMailboxes = 1;
+
+//int upperPvsLimit = 120;
+//int lowerPvsLimit = 5;
+
+float MergeCandidate::sRenderCostWeight = 0;
+
+
+// pvs penalty can be different from pvs size
+inline 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 ComputeMergedPvsSize(const ObjectPvs &pvs1, const ObjectPvs &pvs2)
+{
+	int pvs = pvs1.GetSize();
+
+	// compute new pvs size
+	ObjectPvsMap::const_iterator it, it_end =  pvs1.mEntries.end();
+
+	Intersectable::NewMail();
+
+	for (it = pvs1.mEntries.begin(); it != it_end; ++ it)
+	{
+		(*it).first->Mail();
+	}
+
+	it_end = pvs2.mEntries.end();
+
+	for (it = pvs2.mEntries.begin(); it != it_end; ++ it)
+	{
+		Intersectable *obj = (*it).first;
+		if (!obj->Mailed())
+			++ pvs;
+	}
+
+	return pvs;
+}
+
 
 ViewCell::ViewCell(): 
@@ -12,5 +85,7 @@
 mArea(-1),
 mVolume(-1),
-mValid(true)
+mValid(true),
+mParent(NULL),
+mTimeStamp(0)
 {
 }
@@ -21,5 +96,7 @@
 mArea(-1),
 mVolume(-1),
-mValid(true)
+mValid(true),
+mParent(NULL),
+mTimeStamp(0)
 {
 }
@@ -43,10 +120,4 @@
 
 
-void ViewCell::AddPassingRay(const Ray &ray, const int contributions)
-{
-	mPassingRays.AddRay(ray, contributions);
-}
-
-
 float ViewCell::GetVolume() const
 {
@@ -113,8 +184,86 @@
 
 
+/*bool ViewCell::IsLeaf() const
+{
+	return true;
+}*/
+
+
+void ViewCell::SetParent(ViewCellInterior *parent)
+{
+	mParent = parent;
+}
+
+
+bool ViewCell::IsRoot() const
+{
+	return !mParent;
+}
+
+
+ViewCellInterior *ViewCell::GetParent() const
+{
+	return mParent;
+}
+
+
+void ViewCell::SetTimeStamp(const int timeStamp)
+{
+	mTimeStamp = timeStamp;
+}
+
+
+int ViewCell::GetTimeStamp() const
+{
+	return mTimeStamp;
+}
+
+
+/************************************************************************/
+/*                class ViewCellInterior implementation                 */
+/************************************************************************/
+
+
+ViewCellInterior::ViewCellInterior()
+{
+}
+
+
+ViewCellInterior::~ViewCellInterior()
+{
+	ViewCellContainer::const_iterator it, it_end = mChildren.end();
+
+	for (it = mChildren.begin(); it != it_end; ++ it)
+		delete (*it);
+}
+
+
+ViewCellInterior::ViewCellInterior(Mesh *mesh): 
+ViewCell(mesh)
+{
+}
+
+
+bool ViewCellInterior::IsLeaf() const
+{
+	return false;
+}
+
+
+void ViewCellInterior::SetupChildLink(ViewCell *l)
+{
+    mChildren.push_back(l);
+    l->mParent = this;
+}
+
+
+
 /************************************************************************/
 /*                class ViewCellsStatistics implementation              */
 /************************************************************************/
 
+
+
+
 void ViewCellsStatistics::Print(ostream &app) const
 {
@@ -145,2 +294,1059 @@
 	app << "========== End of View Cells Statistics ==========\n";
 }
+
+
+/*************************************************************************/
+/*                    class ViewCellsTree implementation                 */
+/*************************************************************************/
+
+
+ViewCellsTree::ViewCellsTree(ViewCellsManager *vcm):
+mRoot(NULL),
+mUseAreaForPvs(false),
+mViewCellsManager(vcm)
+{
+	environment->GetBoolValue("ViewCells.Visualization.exportMergedViewCells", mExportMergedViewCells);
+
+	//-- merge options
+	environment->GetFloatValue("ViewCells.PostProcess.renderCostWeight", mRenderCostWeight);
+	environment->GetIntValue("ViewCells.PostProcess.minViewCells", mMergeMinViewCells);
+	environment->GetFloatValue("ViewCells.PostProcess.maxCostRatio", mMergeMaxCostRatio);
+	
+	MergeCandidate::sRenderCostWeight = mRenderCostWeight;
+
+	mStats.open("mergeStats.log");
+}
+
+
+int ViewCellsTree::GetSize(ViewCell *vc) const
+{
+	int vcSize = 0;
+
+	stack<ViewCell *> tstack;
+
+	tstack.push(vc);
+
+	while (!tstack.empty())
+	{
+		ViewCell *vc = tstack.top();
+		tstack.pop();
+
+		if (vc->IsLeaf())
+		{
+			++ vcSize;
+		}
+		else
+		{
+			ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
+			ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
+			for (it = interior->mChildren.begin(); it != it_end; ++ it)
+				tstack.push(*it);
+			
+		}
+	}
+
+	return vcSize;
+}
+
+
+void ViewCellsTree::CollectLeaves(ViewCell *vc, ViewCellContainer &leaves) const
+{
+	stack<ViewCell *> tstack;
+
+	tstack.push(vc);
+
+	while (!tstack.empty())
+	{
+		ViewCell *vc = tstack.top();
+		tstack.pop();
+
+		if (vc->IsLeaf())
+		{
+			leaves.push_back(vc);
+		}
+		else
+		{
+			ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
+			ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
+			for (it = interior->mChildren.begin(); it != it_end; ++ it)
+				tstack.push(*it);
+			
+		}
+	}
+}
+
+
+ViewCellsTree::~ViewCellsTree()
+{
+	DEL_PTR(mRoot);
+}
+
+
+int ViewCellsTree::ConstructMergeTree(const VssRayContainer &rays, 
+									  const ObjectContainer &objects)
+{
+	// number of view cells equals the number of leaves 
+	// (without the invalid ones )
+	//mNumViewCells = mBspStats.Leaves();//- mBspStats.invalidLeaves;
+	mNumViewCells = (int)mViewCellsManager->GetViewCells().size();
+
+	float variance = 0;
+	int totalPvs = 0;
+	float totalCost = 0;
+
+	//-- compute statistics values of initial view cells
+	mViewCellsManager->EvaluateRenderStatistics(totalCost,
+												mExpectedCost,
+												mDeviation,
+												variance,
+												totalPvs,
+												mAvgRenderCost);
+
+
+	//-- fill merge queue
+	vector<MergeCandidate> candidates;
+
+	mViewCellsManager->CollectMergeCandidates(rays, candidates);
+	while(!candidates.empty())
+	{
+		MergeCandidate mc = candidates.back();
+		candidates.pop_back();
+		EvalMergeCost(mc);
+		mMergeQueue.push(mc);
+	}
+
+	Debug << "************************* merge ***********************************" << endl;  
+	Debug << "deviation: " << mDeviation << endl;
+	Debug << "avg render cost: " << mAvgRenderCost << endl;
+	Debug << "expected cost: " <<mExpectedCost << endl;
+
+
+	ViewCellsManager::PvsStatistics pvsStats;
+	mViewCellsManager->GetPvsStatistics(pvsStats);
+
+	static float expectedValue = pvsStats.avgPvs;
+	
+	// the current view cells are kept in this container
+	// we start with the current view cells from the
+	// view cell manager. They will change with
+	// subsequent merges
+	ViewCellContainer &viewCells = mViewCellsManager->GetViewCells();
+
+
+	ViewCell::NewMail();
+
+	MergeStatistics mergeStats;
+	mergeStats.Start();
+	
+	long startTime = GetTime();
+
+	mergeStats.collectTime = TimeDiff(startTime, GetTime());
+	mergeStats.candidates = (int)mMergeQueue.size();
+	startTime = GetTime();
+
+	// frequency stats are updated
+	const int statsOut = 100;
+
+	// passes are needed for statistics, because we don't want to record
+	// every merge
+	int pass = 0;
+	int mergedPerPass = 0;
+	float realExpectedCost = mExpectedCost;
+	float realAvgRenderCost = mAvgRenderCost;
+	int realNumViewCells = mNumViewCells;
+	
+	// maximal ratio of old expected render cost to expected render
+	// when the the render queue has to be reset.
+	float avgCostMaxDeviation;
+	int maxMergesPerPass;
+	int numActiveViewCells = 0;
+
+	environment->GetIntValue("ViewCells.PostProcess.maxMergesPerPass", maxMergesPerPass);
+	environment->GetFloatValue("ViewCells.PostProcess.avgCostMaxDeviation", avgCostMaxDeviation);
+
+	cout << "actual merge starts now ... " << endl;
+	
+	//ResetMergeQueue();
+
+	//-- use priority queue to merge leaf pairs
+
+	while (!mMergeQueue.empty() && (realNumViewCells > mMergeMinViewCells) &&
+		   (mMergeQueue.top().GetRenderCost() < mMergeMaxCostRatio * totalCost))
+	{
+		//-- reset merge queue if the ratio of current expected cost / real expected cost
+		//   too small or after a given number of merges
+		if(0)
+		if ((mergedPerPass > maxMergesPerPass) ||
+			(avgCostMaxDeviation > mAvgRenderCost / realAvgRenderCost))
+		{
+			Debug << "************ reset queue *****************\n"
+				  << "ratios: " << avgCostMaxDeviation 
+				  << " real avg render cost " << realAvgRenderCost << " average render cost " << mAvgRenderCost
+				  << " merged per pass : " << mergedPerPass << " of maximal " << maxMergesPerPass << endl;
+
+			Debug << "Values before reset: "  
+				  << " erc: " << mExpectedCost 
+				  << " avgrc: " << mAvgRenderCost
+				  << " dev: " << mDeviation << endl;
+	
+			// adjust render cost
+			++ pass;
+
+			mergedPerPass = 0;
+			mExpectedCost = realExpectedCost;
+			mAvgRenderCost = realAvgRenderCost;
+			mNumViewCells = realNumViewCells;
+			
+			const int numActiveViewCells = UpdateMergedViewCells(viewCells);
+
+		    ResetMergeQueue();
+
+			
+			Debug << "Values after reset: "  
+				  << " erc: " << mExpectedCost 
+				  << " avg: " << mAvgRenderCost 
+				  << " dev: " << mDeviation << endl;
+
+			if (mExportMergedViewCells)
+			{
+				ExportMergedViewCells(viewCells, objects, numActiveViewCells);
+			}
+		}
+
+#ifdef _DEBUG
+		Debug << "abs mergecost: " << mMergeQueue.top().GetMergeCost() << 
+			  << " rel mergecost: " << mMergeQueue.top().GetRenderCost() / mExpectedCost << 
+			  << " max ratio: " << mMergeMaxCostRatio << endl
+			  << " expected value: " << realExpectedCost << endl;
+#endif
+
+	
+		MergeCandidate mc = mMergeQueue.top();
+		mMergeQueue.pop();
+	
+		// both view cells equal!
+		if (mc.mLeftViewCell == mc.mRightViewCell)
+			continue;
+
+		if (mc.IsValid())
+		{
+			ViewCell::NewMail();
+						
+			-- realNumViewCells;
+			++ mergeStats.merged;
+			++ mergedPerPass;
+
+
+			//-- update statistical values
+
+			// total render cost and deviation has changed
+			// real expected cost will be larger than expected cost used for the
+			// cost heuristics, but cannot recompute costs on each increase of the 
+			// expected cost
+
+			totalCost += mc.GetRenderCost();
+			mDeviation += mc.GetDeviationIncr();
+						
+			realExpectedCost = totalCost / (float)realNumViewCells;
+			
+			const float currentMergeCost = mc.GetMergeCost();
+
+			// merge the view cells of leaf1 and leaf2
+			int pvsDiff;
+			ViewCellInterior *mergedVc = 
+				MergeViewCells(mc.mLeftViewCell, mc.mRightViewCell, pvsDiff);
+
+			totalPvs += pvsDiff;
+			// set timestamp
+			mergedVc->SetTimeStamp(mergeStats.merged);
+
+			realAvgRenderCost = (float)totalPvs / (float)realNumViewCells;
+#if VC_HISTORY
+			if (mc.mLeftViewCell->IsSibling(mc.mRightViewCell))
+				++ mergeStats.siblings;
+#endif
+			if (((mergeStats.merged % statsOut) == 0) || 
+				(realNumViewCells == mMergeMinViewCells))
+			{
+				cout << "merged " << mergeStats.merged << " view cells" << endl;
+
+				mStats 
+					<< "#Pass\n" << pass << endl
+					<< "#Merged\n" << mergeStats.merged << endl 
+					<< "#Viewcells\n" << realNumViewCells << endl 
+					<< "#CurrentCost\n" << currentMergeCost << endl
+					<< "#RelativeCost\n" << currentMergeCost / mOverallCost << endl
+					<< "#CurrentPvs\n" << mc.GetLeftViewCell()->GetPvs().GetSize() << endl
+					<< "#MergedSiblings\n" << mergeStats.siblings << endl
+					<< "#AvgTreeDist\n" << mergeStats.AvgTreeDist() << endl
+					<< "#UsedExpectedCost\n" << mExpectedCost << endl
+					<< "#RealExpectedCost\n" << realExpectedCost << endl
+					<< "#RealAvgRenderCost\n" << realAvgRenderCost << endl
+					<< "#AvgRenderCost\n" << mAvgRenderCost << endl
+					<< "#expectedCostRatio\n" << mExpectedCost / realExpectedCost << endl
+					<< "#Deviation\n" << mDeviation / (float)realNumViewCells << endl
+					<< "#TotalDeviation\n" << mDeviation<< endl;
+			}
+		}
+		else
+		{ 
+			// merge candidate not valid, because one of the leaves was already
+			// merged with another one => validate and reinsert into queue
+			SetMergeCandidateValid(mc);
+			mMergeQueue.push(mc);
+		}
+	}
+
+	// adjust stats and reset queue one final time
+	mExpectedCost = realExpectedCost;
+	mAvgRenderCost = realAvgRenderCost;
+	mNumViewCells = realNumViewCells;
+
+	UpdateMergedViewCells(viewCells);
+	ResetMergeQueue();
+
+
+	// create a root node if the merge was not done till root level,
+	// else take the single node as new root
+	if ((int)viewCells.size() > 1)
+	{
+		ViewCellInterior *root = new ViewCellInterior();
+
+		ViewCellContainer::const_iterator it, it_end = viewCells.end();
+		for (it = viewCells.begin(); it != it_end; ++ it)
+			root->SetupChildLink(*it);
+
+		mRoot = root;
+	}
+	else if ((int)viewCells.size() == 1)
+	{
+		mRoot = viewCells[0];
+	}
+
+	mergeStats.expectedRenderCost = realExpectedCost;
+	mergeStats.deviation = mDeviation;
+
+	// we want to optimize this heuristics
+	mergeStats.heuristics = 
+		mDeviation * (1.0f - mRenderCostWeight) + 
+		mExpectedCost * mRenderCostWeight;
+
+	mergeStats.mergeTime = TimeDiff(startTime, GetTime());
+	mergeStats.Stop();
+
+	Debug << mergeStats << endl << endl;
+
+
+	//TODO: should return sample contributions?
+	return mergeStats.merged;
+}
+
+
+void ViewCellsTree::ResetMergeQueue()
+{
+	cout << "reset merge queue ... ";
+	
+	vector<MergeCandidate> buf;
+	buf.reserve(mMergeQueue.size());
+			
+	
+	// store merge candidates in intermediate buffer
+	while (!mMergeQueue.empty())
+	{
+		MergeCandidate mc = mMergeQueue.top();
+		mMergeQueue.pop();
+		
+		// recalculate cost
+		SetMergeCandidateValid(mc);
+		buf.push_back(mc);				
+	}
+
+	vector<MergeCandidate>::const_iterator bit, bit_end = buf.end();
+
+	// reinsert back into queue
+	for (bit = buf.begin(); bit != bit_end; ++ bit)
+	{      
+		mMergeQueue.push(*bit);	
+	}
+
+	cout << "finished" << endl;
+}
+
+
+int ViewCellsTree::UpdateMergedViewCells(ViewCellContainer &viewCells)
+{
+	int numActiveViewCells = 0;
+
+	// find all already merged view cells and remove them from view cells
+	int i = 0;
+
+	while (1)
+	{
+		while (!viewCells.empty() && (!viewCells.back()->GetParent()))
+		{
+			viewCells.pop_back();
+		}
+
+		// all merged view cells have been found
+		if (i >= viewCells.size()) 
+			break;
+
+		// already merged view cell, put it to end of vector
+		if (!viewCells[i]->IsRoot())
+			swap(viewCells[i], viewCells.back());
+		
+		++ i;
+	}
+
+	// add new view cells to container only if they don't have been 
+	// merged in the mean time
+	while (!mActiveViewCells.empty())
+	{
+		if (!mActiveViewCells.back()->GetParent())
+		{
+			viewCells.push_back(mActiveViewCells.back());
+			++ numActiveViewCells;
+		}
+
+		mActiveViewCells.pop_back();
+	}
+
+	// update standard deviation
+	ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
+	
+	mDeviation = 0;
+
+	for (vit = viewCells.begin(); vit != vit_end; ++ vit)
+	{
+		int lower = mViewCellsManager->GetMinPvsSize();
+		int upper = mViewCellsManager->GetMaxPvsSize();
+		float penalty = EvalPvsPenalty((*vit)->GetPvs().GetSize(), lower, upper);
+		
+		mDeviation += fabs(mAvgRenderCost - penalty);
+	}
+
+	mDeviation /= (float)viewCells.size();
+
+	// clear the view cells which were merged
+	mInactiveViewCells.clear();
+	// remove the new view cells
+	mActiveViewCells.clear();
+
+	return numActiveViewCells;
+}
+
+
+void ViewCellsTree::ExportMergedViewCells(ViewCellContainer &viewCells, 
+										  const ObjectContainer &objects,
+										  const int numActiveViewCells)
+{
+	
+
+	char s[64];
+
+	sprintf(s, "merged_viewcells%07d.x3d", (int)viewCells.size());
+	Exporter *exporter = Exporter::GetExporter(s);
+
+	if (exporter)
+	{
+		cout << "exporting " << (int)viewCells.size() << " merged view cells ... ";
+		exporter->ExportGeometry(objects);
+		//Debug << "vc size " << (int)viewCells.size() << " merge queue size: " << (int)mMergeQueue.size() << endl;
+		ViewCellContainer::const_iterator it, it_end = viewCells.end();
+
+		int i = 0;
+		for (it = viewCells.begin(); it != it_end; ++ it)
+		{
+			Material m;
+			// assign special material to new view cells
+			// new view cells are on the back of container
+			if (i ++ >= (viewCells.size() - numActiveViewCells))
+			{
+				//m = RandomMaterial();
+				m.mDiffuseColor.r = RandomValue(0.5f, 1.0f);
+				m.mDiffuseColor.g = RandomValue(0.5f, 1.0f);
+				m.mDiffuseColor.b = RandomValue(0.5f, 1.0f);
+			}
+			else
+			{
+				float col = RandomValue(0.1f, 0.4f);
+				m.mDiffuseColor.r = col;
+				m.mDiffuseColor.g = col;
+				m.mDiffuseColor.b = col;
+			}
+
+			exporter->SetForcedMaterial(m);
+			mViewCellsManager->ExportViewCellGeometry(exporter, *it);
+		}
+		delete exporter;
+		cout << "finished" << endl;
+	}
+}
+
+
+// TODO: should be done in view cells manager
+ViewCellInterior *ViewCellsTree::MergeViewCells(ViewCell *l, ViewCell *r, int &pvsDiff) //const
+{
+	ViewCellInterior *vc = mViewCellsManager->MergeViewCells(*l, *r);
+
+	// if merge was unsuccessful
+	if (!vc) return NULL;
+
+	// set new size of view cell
+	if (mUseAreaForPvs)
+		vc->SetArea(l->GetArea() + l->GetArea());
+	else
+		vc->SetVolume(r->GetVolume() + r->GetVolume());
+	
+	// important so other merge candidates sharing this view cell
+	// are notified that the merge cost must be updated!!
+	vc->Mail();
+
+	const int pvs1 = l->GetPvs().GetSize();
+	const int pvs2 = r->GetPvs().GetSize();
+
+
+	//-- clean up old view cells
+	if (0 && !mExportMergedViewCells)
+	{
+		DEL_PTR(l);
+		DEL_PTR(r);
+	}
+	else 
+	{
+		mInactiveViewCells.push_back(l);
+		mInactiveViewCells.push_back(r);
+		
+		mActiveViewCells.push_back(vc);
+	}
+
+	pvsDiff = vc->GetPvs().GetSize() - pvs1 - pvs2;
+
+	return vc;
+}
+
+
+
+
+int ViewCellsTree::RefineViewCells(const VssRayContainer &rays, const ObjectContainer &objects)
+{
+	Debug << "refining " << (int)mMergeQueue.size() << " candidates " << endl;
+	
+	// Use priority queue of remaining leaf pairs 
+	// The 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.
+	//
+	// repeat the merging test numPasses times. For example, it could be
+	// that a shuffle only makes sense if another pair was shuffled before.
+	// Therefore we keep two queues and shift the merge candidates between
+	// those two queues until numPasses is reached
+	
+	queue<MergeCandidate> queue1;
+	queue<MergeCandidate> queue2;
+
+	queue<MergeCandidate> *shuffleQueue = &queue1;
+	queue<MergeCandidate> *backQueue = &queue2;
+
+	while (!mMergeQueue.empty())
+	{
+		MergeCandidate mc = mMergeQueue.top();
+		shuffleQueue->push(mc);
+		mMergeQueue.pop();
+	}
+
+	const int numPasses = 5;
+	int pass = 0;
+	int passShuffled = 0;
+	int shuffled = 0;
+	int shuffledViewCells = 0;
+
+	ViewCell::NewMail();
+	
+	do
+	{
+		passShuffled = 0;
+		while (!shuffleQueue->empty())
+		{
+			MergeCandidate mc = shuffleQueue->front();
+			shuffleQueue->pop();
+
+			// both view cells equal or already shuffled
+			if ((mc.GetLeftViewCell() == mc.GetRightViewCell()) || 
+				(GetSize(mc.GetLeftViewCell()) == 1) || 
+				(GetSize(mc.GetRightViewCell()) == 1))
+			{			
+				continue;
+			}
+
+			// candidate for shuffling
+			const bool wasShuffled = 
+				ShuffleLeaves(mc.GetLeftViewCell(), mc.GetRightViewCell());
+		
+			// shuffled or put into other queue for further refine
+			if (wasShuffled)
+			{
+				++ passShuffled;
+
+				if (!mc.GetLeftViewCell()->Mailed())
+				{
+					mc.GetLeftViewCell()->Mail();
+					++ shuffledViewCells;
+				}
+				if (!mc.GetRightViewCell()->Mailed())
+				{
+					mc.GetRightViewCell()->Mail();
+					++ shuffledViewCells;
+				}
+			}
+			else
+			{
+				backQueue->push(mc);
+			}
+		}
+
+		// now the back queue is the current shuffle queue
+		swap(shuffleQueue, backQueue);
+		shuffled += passShuffled;
+		Debug << "shuffled in pass: " << passShuffled << endl;
+	}
+	while (((++ pass) < numPasses) && passShuffled);
+
+	while (!shuffleQueue->empty())
+	{
+		shuffleQueue->pop();
+	}
+
+	return shuffledViewCells;
+}
+
+
+
+
+inline int AddedPvsSize(ObjectPvs pvs1, const ObjectPvs &pvs2)
+{
+	return pvs1.AddPvs(pvs2);
+}
+
+
+// recomputes pvs size minus pvs of leaf l
+#if 0
+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();
+}
+#endif
+
+
+// computes pvs1 minus pvs2
+inline int SubtractedPvsSize(ObjectPvs pvs1, const ObjectPvs &pvs2)
+{
+	return pvs1.SubtractPvs(pvs2);
+}
+
+
+float ViewCellsTree::EvalShuffleCost(ViewCell *leaf, 
+									 ViewCell *vc1, 
+									 ViewCell *vc2) const
+{
+	//const int pvs1 = SubtractedPvsSize(vc1, leaf, *leaf->mPvs);
+	const int pvs1 = SubtractedPvsSize(vc1->GetPvs(), leaf->GetPvs());
+	const int pvs2 = AddedPvsSize(vc2->GetPvs(), leaf->GetPvs());
+
+	const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize();
+	const int upperPvsLimit = mViewCellsManager->GetMaxPvsSize();
+
+	const float pvsPenalty1 = 
+		EvalPvsPenalty(pvs1, lowerPvsLimit, upperPvsLimit);
+
+	const float pvsPenalty2 =
+		EvalPvsPenalty(pvs2, lowerPvsLimit, upperPvsLimit);
+
+
+	// don't shuffle leaves with pvs > max
+	if (0 && (pvs1 + pvs2 > mViewCellsManager->GetMaxPvsSize()))
+	{
+		return 1e20f;
+	}
+
+	float p1, p2;
+
+    if (mUseAreaForPvs)
+	{
+		p1 = vc1->GetArea() - leaf->GetArea();
+		p2 = vc2->GetArea() + leaf->GetArea();
+	}
+	else
+	{
+		p1 = vc1->GetVolume() - leaf->GetVolume();
+		p2 = vc2->GetVolume() + leaf->GetVolume();
+	}
+
+	const float renderCost1 = pvsPenalty1 * p1;
+	const float renderCost2 = pvsPenalty2 * p2;
+
+	float dev1, dev2;
+
+	if (1)
+	{
+		dev1 = fabs(mAvgRenderCost - pvsPenalty1);
+		dev2 = fabs(mAvgRenderCost - pvsPenalty2);
+	}
+	else
+	{
+		dev1 = fabs(mExpectedCost - renderCost1);
+		dev2 = fabs(mExpectedCost - renderCost2);
+	}
+	
+	return mRenderCostWeight * (renderCost1 + renderCost2) +
+		  (1.0f - mRenderCostWeight) * (dev1 + dev2) / (float)mNumViewCells;
+}
+
+
+void ViewCellsTree::ShuffleLeaf(ViewCell *leaf,
+								ViewCell *vc1, 
+								ViewCell *vc2) const
+{
+	// compute new pvs and area
+	vc1->GetPvs().SubtractPvs(leaf->GetPvs());
+	vc2->GetPvs().AddPvs(leaf->GetPvs());
+	
+	if (mUseAreaForPvs)
+	{
+		vc1->SetArea(vc1->GetArea() - leaf->GetArea());
+		vc2->SetArea(vc2->GetArea() + leaf->GetArea());
+	}
+	else
+	{
+		vc1->SetVolume(vc1->GetVolume() - leaf->GetVolume());
+		vc2->SetVolume(vc2->GetVolume() + leaf->GetVolume());
+	}
+
+	// TODO
+#if VC_HISTORY
+	/// 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
+#endif
+}
+
+
+bool ViewCellsTree::ShuffleLeaves(ViewCell *l, ViewCell *r) const
+{
+	float cost1, cost2;
+
+	//-- first test if shuffling would decrease cost
+	cost1 = GetCostHeuristics(l);
+	cost2 = GetCostHeuristics(r);
+
+	const float oldCost = cost1 + cost2;
+	
+	float shuffledCost1 = Limits::Infinity;
+	float shuffledCost2 = Limits::Infinity;
+
+	// the view cell should not be empty after the shuffle
+#if VC_HISTORY
+	shuffledCost1 = EvalShuffleCost(l, vc1, vc2);
+	/shuffledCost2 = EvalShuffleCost(r, vc2, vc1);
+
+	// if cost of shuffle is less than old cost => shuffle
+	if ((oldCost <= shuffledCost1) && (oldCost <= shuffledCost2))
+		return false;
+	
+	
+	if (shuffledCost1 < shuffledCost2)
+	{
+		ShuffleLeaf(leaf1, vc1, vc2);
+		leaf1->Mail();
+	}
+	else
+	{
+		ShuffleLeaf(leaf2, vc2, vc1);
+		leaf2->Mail();
+	}
+#endif
+	return true;
+}
+
+
+float ViewCellsTree::GetVariance(ViewCell *vc) const
+{
+	const int upper = mViewCellsManager->GetMaxPvsSize();
+	const int lower = mViewCellsManager->GetMinPvsSize();
+
+	if (1)
+	{
+		const float penalty = EvalPvsPenalty(vc->GetPvs().GetSize(), lower, upper);
+		return (mAvgRenderCost - penalty) * (mAvgRenderCost - penalty) / (float)mNumViewCells;
+	}
+
+    const float leafCost = GetRenderCost(vc);
+	return (mExpectedCost - leafCost) * (mExpectedCost - leafCost);
+}
+
+
+float ViewCellsTree::GetDeviation(ViewCell *vc) const
+{
+	const int upper = mViewCellsManager->GetMaxPvsSize();
+	const int lower = mViewCellsManager->GetMinPvsSize();
+
+	if (1)
+	{
+		const float penalty = EvalPvsPenalty(vc->GetPvs().GetSize(), lower, upper);
+		return fabs(mAvgRenderCost - penalty) / (float)mNumViewCells;
+	}
+
+    const float renderCost = GetRenderCost(vc);
+	return fabs(mExpectedCost - renderCost);
+}
+
+
+
+float ViewCellsTree::GetRenderCost(ViewCell *vc) const
+{
+	if (mUseAreaForPvs)
+		return vc->GetPvs().GetSize() * vc->GetArea();
+
+	return vc->GetPvs().GetSize() * vc->GetVolume();
+}
+
+
+float ViewCellsTree::GetCostHeuristics(ViewCell *vc) const
+{
+	return GetRenderCost(vc) * mRenderCostWeight + 
+		   GetDeviation(vc) * (1.0f - mRenderCostWeight);
+}
+
+
+void ViewCellsTree::SetMergeCandidateValid(MergeCandidate &mc) const
+{
+	while (mc.mLeftViewCell->mParent)
+	{
+		mc.mLeftViewCell = mc.mLeftViewCell->mParent;
+	}
+
+	while (mc.mRightViewCell->mParent)
+	{
+		mc.mRightViewCell = mc.mRightViewCell->mParent;
+	}
+
+	EvalMergeCost(mc);
+}
+
+
+void ViewCellsTree::EvalMergeCost(MergeCandidate &mc) const
+{
+	//-- compute pvs difference
+	const int newPvs = 
+		ComputeMergedPvsSize(mc.mLeftViewCell->GetPvs(), 
+							 mc.mRightViewCell->GetPvs());
+			
+	const float newPenalty = 
+		EvalPvsPenalty(newPvs,
+					   mViewCellsManager->GetMinPvsSize(),
+					   mViewCellsManager->GetMaxPvsSize());
+
+	ViewCell *vc1 = mc.mLeftViewCell;
+	ViewCell *vc2 = mc.mRightViewCell;
+
+	//-- compute ratio of old cost
+	//   (i.e., added size of left and right view cell times pvs size)
+	//   to new rendering cost (i.e, size of merged view cell times pvs size)
+	const float oldCost = GetRenderCost(vc1) + GetRenderCost(vc2);
+
+    const float newCost = mUseAreaForPvs ? 
+		(float)newPenalty * (vc1->GetArea() + vc2->GetArea()) :
+		(float)newPenalty * (vc1->GetVolume() + vc2->GetVolume());
+
+
+	// strong penalty if pvs size too large
+	if (0 && (newPvs > mViewCellsManager->GetMaxPvsSize()))
+	{
+		mc.mRenderCost = 1e20f;
+	}
+	else
+	{
+		mc.mRenderCost = (newCost - oldCost) / 
+			mViewCellsManager->GetViewSpaceBox().GetVolume();
+	}	
+	
+
+	//-- merge cost also takes deviation into account
+	float newDev, oldDev;
+
+	if (1)
+		newDev = fabs(mAvgRenderCost - newPenalty) / (float)mNumViewCells;
+	else
+		newDev = fabs(mExpectedCost - newCost) / (float)mNumViewCells;
+	
+	oldDev = GetDeviation(vc1) + GetDeviation(vc2);
+
+	// compute deviation increase
+	mc.mDeviationIncr = newDev - oldDev;
+	
+	//Debug << "render cost: " << mc.mRenderCost * mRenderCostWeight << endl;
+	//Debug << "standard deviation: " << mc.mDeviationIncr * mRenderCostWeight << endl;
+}
+
+
+void ViewCellsTree::CompressViewCellsPvs()
+{
+	stack<ViewCell *> tstack;
+
+
+}
+
+
+void  ViewCellsTree::CollectBestViewCellSet(ViewCellContainer &viewCells, const int numViewCells)
+{
+	TraversalQueue tqueue;
+
+	while (!tqueue.empty())
+	{
+		ViewCell *vc = tqueue.top();
+
+		tqueue.pop();
+	}
+}
+
+
+/**************************************************************************/
+/*                     MergeCandidate implementation                      */
+/**************************************************************************/
+
+
+MergeCandidate::MergeCandidate(ViewCell *l, ViewCell *r):
+mRenderCost(0),
+mDeviationIncr(0),
+mLeftViewCell(l),
+mRightViewCell(r)
+{
+	//EvalMergeCost();
+}
+
+
+void MergeCandidate::SetRightViewCell(ViewCell *v)
+{
+	mRightViewCell = v;
+}
+
+
+void MergeCandidate::SetLeftViewCell(ViewCell *v)
+{
+	mLeftViewCell = v;
+}
+
+
+ViewCell *MergeCandidate::GetRightViewCell() const
+{
+	return mRightViewCell;
+}
+
+
+ViewCell *MergeCandidate::GetLeftViewCell() const
+{
+	return mLeftViewCell;
+}
+
+
+ViewCell *MergeCandidate::GetInitialRightViewCell() const
+{
+	return mInitialRightViewCell;
+}
+
+
+ViewCell *MergeCandidate::GetInitialLeftViewCell() const
+{
+	return mInitialLeftViewCell;
+}
+
+
+bool MergeCandidate::IsValid() const
+{
+	return !(mLeftViewCell->mParent && mRightViewCell->mParent);
+}
+
+
+float MergeCandidate::GetRenderCost() const
+{
+	return mRenderCost;
+}
+
+
+float MergeCandidate::GetDeviationIncr() const
+{
+	return mDeviationIncr;
+}
+
+
+float MergeCandidate::GetMergeCost() const
+{
+	return mRenderCost * sRenderCostWeight + 
+		   mDeviationIncr * (1.0f - sRenderCostWeight);
+}
+
+
+/************************************************************************/
+/*                    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 << "#OVERALLCOST ( overall merge cost )\n" << overallCost << "\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 << "#EXPECTEDCOST ( expected render cost )\n" << expectedRenderCost << "\n";
+
+	app << "#DEVIATION ( deviation )\n" << deviation << "\n";
+
+	app << "#HEURISTICS ( heuristics )\n" << heuristics << "\n";
+	
+
+	app << "===== END OF BspTree statistics ==========\n";
+}
Index: /trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellsManager.h
===================================================================
--- /trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellsManager.h	(revision 579)
+++ /trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellsManager.h	(revision 580)
@@ -27,4 +27,6 @@
 class Beam;
 class Preprocessor;
+class ViewCellsTree;
+class MergeCandidate;
 
 struct BspRay;
@@ -133,9 +135,9 @@
 		@returns new view cell based on the merging.
 	*/
-	ViewCell *MergeViewCells(ViewCell &front, ViewCell &back) const;
+	ViewCellInterior *MergeViewCells(ViewCell &front, ViewCell &back) const;
 	
 	/** Generates view cell of type specified by this manager
 	*/
-	virtual ViewCell *GenerateViewCell(Mesh *mesh = NULL) const;
+	virtual ViewCell *GenerateViewCell(Mesh *mesh = NULL) const = 0;
 
 	/** Adds a new view cell to the list of predefined view cells.
@@ -206,5 +208,5 @@
 	virtual float GetRendercost(ViewCell *viewCell, float objRendercost) const = 0;
 
-	/** Returns vector of loaded / generated view cells.
+	/** Returns container of loaded / generated view cells.
 	*/
 	ViewCellContainer &GetViewCells();
@@ -311,5 +313,5 @@
 	/** Exports view cell geometry.
 	*/
-	virtual void ExportVcGeometry(Exporter *exporter, ViewCell *vc) const = 0;
+	virtual void ExportViewCellGeometry(Exporter *exporter, ViewCell *vc) const = 0;
 
 	virtual void FinalizeViewCells(const bool createMesh);
@@ -325,7 +327,18 @@
 	/** Evaluates statistics values on view cells.
 	*/
-	void EvaluateRenderStatistics(float &totalRenderCost, 
-								  float &expectedRenderCost, 
-								  float &variance);
+	void EvaluateRenderStatistics(float &totalRenderCost,
+								  float &expectedRenderCost,
+								  float &deviation,
+								  float &variance,
+								  int &totalPvs,
+								  float &avgRenderCost);
+
+
+	/** Returns hierarchy of the view cells.
+	*/
+	ViewCellsTree *GetViewCellsTree();
+
+	virtual void CollectMergeCandidates(const VssRayContainer &rays, vector<MergeCandidate> &candidates) = 0;
+
 
 protected:
@@ -392,4 +405,6 @@
 	/// Loaded view cells
 	ViewCellContainer mViewCells;
+
+	ViewCellsTree *mViewCellsTree;
 
 	/// maximum number of samples taken for construction of the view cells
@@ -417,4 +432,8 @@
 	bool mOnlyValidViewCells;
 
+	/// if rays should be used to collect merge candidates
+	bool mUseRaysForMerge;
+	
+
 	//-- visualization options
 	
@@ -472,5 +491,7 @@
 	void CreateMesh(ViewCell *vc);
 
-	void ExportVcGeometry(Exporter *exporter, ViewCell *vc) const;
+	void ExportViewCellGeometry(Exporter *exporter, ViewCell *vc) const;
+	
+	void CollectMergeCandidates(const VssRayContainer &rays, vector<MergeCandidate> &candidates);
 
 protected:
@@ -529,4 +550,5 @@
 	bool ViewCellsConstructed() const;
 
+	ViewCell *GenerateViewCell(Mesh *mesh) const;
 
 	/** Prints out statistics of this approach.
@@ -540,9 +562,14 @@
 	void CreateMesh(ViewCell *vc);
 
-	void ExportVcGeometry(Exporter *exporter, ViewCell *vc) const;
+	void ExportViewCellGeometry(Exporter *exporter, ViewCell *vc) const;
+
+	void CollectMergeCandidates(const VssRayContainer &rays, vector<MergeCandidate> &candidates);
 
 protected:
 
+	/** Collects view cells from a hierarchy.
+	*/
 	void CollectViewCells();
+
 	KdNode *GetNodeForPvs(KdLeaf *leaf);
 
@@ -598,5 +625,7 @@
 	void CreateMesh(ViewCell *vc);
 
-	void ExportVcGeometry(Exporter *exporter, ViewCell *vc) const;
+	void ExportViewCellGeometry(Exporter *exporter, ViewCell *vc) const;
+
+	void CollectMergeCandidates(const VssRayContainer &rays, vector<MergeCandidate> &candidates);
 
 protected:
@@ -664,9 +693,11 @@
 	int CastBeam(Beam &beam);
 
-	void ExportVcGeometry(Exporter *exporter, ViewCell *vc) const;
+	void ExportViewCellGeometry(Exporter *exporter, ViewCell *vc) const;
 
 	//float GetVolume(ViewCell *viewCell) const;
 
 	void Finalize(ViewCell *viewCell, const bool createMesh);
+
+	void CollectMergeCandidates(const VssRayContainer &rays, vector<MergeCandidate> &candidates);
 
 protected:
Index: /trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.cpp
===================================================================
--- /trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.cpp	(revision 579)
+++ /trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.cpp	(revision 580)
@@ -25,11 +25,8 @@
 const float VspBspTree::sLeastRaySplitsTable[] = {0, 0, 1, 1, 0};
 /** Evaluates split plane classification with respect to the plane's
-	contribution for balanced rays.
+	contribution for  balanced rays.
 */
 const float VspBspTree::sBalancedRaysTable[] = {1, -1, 0, 0, 0};
 
-ViewCellsManager *BspMergeCandidate::sViewCellsManager = NULL;
-//int BspMergeCandidate::sMaxPvsSize = 0;
-//int BspMergeCandidate::sMinPvsSize = 0;
 
 int VspBspTree::sFrontId = 0;
@@ -37,13 +34,4 @@
 int VspBspTree::sFrontAndBackId = 0;
 
-float BspMergeCandidate::sOverallCost = 0;
-float BspMergeCandidate::sExpectedCost = 0;
-float BspMergeCandidate::sVariance = 0;
-float BspMergeCandidate::sRenderCostWeight = 0.5f;
-bool BspMergeCandidate::sUseArea = false;
-int BspMergeCandidate::sNumViewCells = 0;
-
-//int upperPvsLimit = 120;
-//int lowerPvsLimit = 5;
 
 
@@ -64,17 +52,4 @@
 
 
-// penalty for pvs durint merge
-inline float EvalPvsPenaltyForMerge(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;
-}
 
 
@@ -90,5 +65,6 @@
 mViewCellsManager(NULL),
 mOutOfBoundsCell(NULL),
-mStoreRays(false)
+mStoreRays(false),
+mRenderCostWeight(0.5)
 {
 	bool randomize = false;
@@ -126,11 +102,5 @@
 	// if only the driving axis is used for axis aligned split
 	environment->GetBoolValue("VspBspTree.splitUseOnlyDrivingAxis", mOnlyDrivingAxis);
-
-	//-- merge options
-	environment->GetIntValue("VspBspTree.PostProcess.minViewCells", mMergeMinViewCells);
-	environment->GetFloatValue("VspBspTree.PostProcess.maxCostRatio", mMergeMaxCostRatio);
-	environment->GetBoolValue("VspBspTree.PostProcess.useRaysForMerge", mUseRaysForMerge);
-
-
+	
 	//-- termination criteria for axis aligned split
 	environment->GetFloatValue("VspBspTree.Termination.AxisAligned.maxRayContribution", 
@@ -142,11 +112,11 @@
 	environment->GetFloatValue("VspBspTree.maxStaticMemory", mMaxMemory);
 
-	environment->GetBoolValue("VspBspTree.Visualization.exportMergedViewCells", mExportMergedViewCells);
-	environment->GetBoolValue("VspBspTree.PostProcess.exportMergeStats", mExportMergeStats);
-	
-
-	mStats.open("bspStats.log");
+	environment->GetFloatValue("VspBspTree.Construction.renderCostWeight", mRenderCostWeight);
+
+
+
 
 	//-- debug output
+
 	Debug << "******* VSP BSP options ******** " << endl;
     Debug << "max depth: " << mTermMaxDepth << endl;
@@ -162,6 +132,7 @@
 	Debug << "max plane candidates: " << mMaxRayCandidates << endl;
 	Debug << "randomize: " << randomize << endl;
-	Debug << "minimum view cells: " << mMergeMinViewCells << endl;
+//	Debug << "minimum view cells: " << mMergeMinViewCells << endl;
 	Debug << "using area for pvs: " << mUseAreaForPvs << endl;
+	Debug << "render cost weight: " << mRenderCostWeight << endl;
 	Debug << "Split plane strategy: ";
 
@@ -195,4 +166,5 @@
 	Debug << endl;
 }
+
 
 BspViewCell *VspBspTree::GetOutOfBoundsCell()
@@ -249,4 +221,5 @@
 	return (int)mesh->mFaces.size();
 }
+
 
 int VspBspTree::AddToPolygonSoup(const ViewCellContainer &viewCells,
@@ -273,4 +246,5 @@
 	return polysSize;
 }
+
 
 int VspBspTree::AddToPolygonSoup(const ObjectContainer &objects,
@@ -310,4 +284,5 @@
 }
 
+
 void VspBspTree::Construct(const VssRayContainer &sampleRays,
 						   AxisAlignedBox3 *forcedBoundingBox)
@@ -366,4 +341,5 @@
 	
 	Debug << "maximal pvs (i.e., pvs still considered as valid) : " << mViewCellsManager->GetMaxPvsSize() << endl;
+
 	//-- store rays
 	for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
@@ -572,5 +548,5 @@
 		}
 		
-        viewCell->mLeaves.push_back(leaf);
+        viewCell->mLeaf = leaf;
 
 		if (mUseAreaForPvs)
@@ -589,6 +565,4 @@
 	return newNode;
 }
-
-
 
 
@@ -752,4 +726,5 @@
 }
 
+
 void VspBspTree::SortSplitCandidates(const RayInfoContainer &rays, const int axis)
 {
@@ -780,4 +755,5 @@
 	stable_sort(mSplitCandidates->begin(), mSplitCandidates->end());
 }
+
 
 float VspBspTree::BestCostRatioHeuristics(const RayInfoContainer &rays,
@@ -1035,4 +1011,401 @@
 
 
+bool VspBspTree::SelectPlane(Plane3 &bestPlane,
+							 BspLeaf *leaf,
+							 VspBspTraversalData &data,
+							 VspBspTraversalData &frontData,
+							 VspBspTraversalData &backData)
+{
+	// simplest strategy: just take next polygon
+	if (mSplitPlaneStrategy & RANDOM_POLYGON)
+	{
+        if (!data.mPolygons->empty())
+		{
+			const int randIdx = 
+				(int)RandomValue(0, (Real)((int)data.mPolygons->size() - 1));
+			Polygon3 *nextPoly = (*data.mPolygons)[randIdx];
+
+			bestPlane = nextPoly->GetSupportingPlane();
+			return true;
+		}
+	}
+
+	//-- use heuristics to find appropriate plane
+
+	// intermediate plane
+	Plane3 plane;
+	float lowestCost = MAX_FLOAT;
+	
+	// decides if the first few splits should be only axisAligned
+	const bool onlyAxisAligned  = 
+		(mSplitPlaneStrategy & AXIS_ALIGNED) &&
+		((int)data.mRays->size() > mTermMinRaysForAxisAligned) &&
+		((int)data.GetAvgRayContribution() < mTermMaxRayContriForAxisAligned);
+	
+	const int limit = onlyAxisAligned ? 0 : 
+		Min((int)data.mPolygons->size(), mMaxPolyCandidates);
+
+	float candidateCost;
+
+	int maxIdx = (int)data.mPolygons->size();
+
+	for (int i = 0; i < limit; ++ i)
+	{
+		// the already taken candidates are stored behind maxIdx
+		// => assure that no index is taken twice
+		const int candidateIdx = (int)RandomValue(0, (Real)(-- maxIdx));
+		Polygon3 *poly = (*data.mPolygons)[candidateIdx];
+
+		// swap candidate to the end to avoid testing same plane
+		std::swap((*data.mPolygons)[maxIdx], (*data.mPolygons)[candidateIdx]);
+		//Polygon3 *poly = (*data.mPolygons)[(int)RandomValue(0, (int)polys.size() - 1)];
+
+		// evaluate current candidate
+		BspNodeGeometry fGeom, bGeom;
+		float fArea, bArea;
+		plane = poly->GetSupportingPlane();
+		candidateCost = EvalSplitPlaneCost(plane, data, fGeom, bGeom, fArea, bArea);
+		
+		if (candidateCost < lowestCost)
+		{
+			bestPlane = plane;
+			lowestCost = candidateCost;
+		}
+	}
+
+	//-- evaluate axis aligned splits
+	int axis;
+	BspNodeGeometry *fGeom, *bGeom;
+	float pFront, pBack;
+
+	candidateCost = SelectAxisAlignedPlane(plane, data, axis,
+										   &fGeom, &bGeom, 
+										   pFront, pBack,
+										   data.mIsKdNode);	 
+
+	bool isAxisAlignedSplit = false;
+
+	if (candidateCost < lowestCost)
+	{	
+		bestPlane = plane;
+		lowestCost = candidateCost;
+
+		// assign already computed values
+		// we can do this because we always save the
+		// computed values from the axis aligned splits		
+		frontData.mGeometry = fGeom;
+		backData.mGeometry = bGeom;
+	
+		frontData.mProbability = pFront;
+		backData.mProbability = pBack;
+		
+		//! error also computed if cost ratio is missed
+		++ mBspStats.splits[axis];
+		isAxisAlignedSplit = true;
+	}
+	else
+	{
+		DEL_PTR(fGeom);
+		DEL_PTR(bGeom);
+	}
+
+	frontData.mIsKdNode = backData.mIsKdNode = (data.mIsKdNode && isAxisAlignedSplit);
+
+#ifdef _DEBUG
+	Debug << "plane lowest cost: " << lowestCost << endl;
+#endif
+
+	// cost ratio miss
+	if (lowestCost > mTermMaxCostRatio)
+		return false;
+
+	return true;
+}
+
+
+Plane3 VspBspTree::ChooseCandidatePlane(const RayInfoContainer &rays) const
+{
+	const int candidateIdx = (int)RandomValue(0, (Real)((int)rays.size() - 1));
+
+	const Vector3 minPt = rays[candidateIdx].ExtrapOrigin();
+	const Vector3 maxPt = rays[candidateIdx].ExtrapTermination();
+
+	const Vector3 pt = (maxPt + minPt) * 0.5;
+	const Vector3 normal = Normalize(rays[candidateIdx].mRay->GetDir());
+
+	return Plane3(normal, pt);
+}
+
+
+Plane3 VspBspTree::ChooseCandidatePlane2(const RayInfoContainer &rays) const
+{
+	Vector3 pt[3];
+
+	int idx[3];
+	int cmaxT = 0;
+	int cminT = 0;
+	bool chooseMin = false;
+
+	for (int j = 0; j < 3; ++ j)
+	{
+		idx[j] = (int)RandomValue(0, (Real)((int)rays.size() * 2 - 1));
+
+		if (idx[j] >= (int)rays.size())
+		{
+			idx[j] -= (int)rays.size();
+
+			chooseMin = (cminT < 2);
+		}
+		else
+			chooseMin = (cmaxT < 2);
+
+		RayInfo rayInf = rays[idx[j]];
+		pt[j] = chooseMin ? rayInf.ExtrapOrigin() : rayInf.ExtrapTermination();
+	}
+
+	return Plane3(pt[0], pt[1], pt[2]);
+}
+
+
+Plane3 VspBspTree::ChooseCandidatePlane3(const RayInfoContainer &rays) const
+{
+	Vector3 pt[3];
+
+	int idx1 = (int)RandomValue(0, (Real)((int)rays.size() - 1));
+	int idx2 = (int)RandomValue(0, (Real)((int)rays.size() - 1));
+
+	// check if rays different
+	if (idx1 == idx2)
+		idx2 = (idx2 + 1) % (int)rays.size();
+
+	const RayInfo ray1 = rays[idx1];
+	const RayInfo ray2 = rays[idx2];
+
+	// normal vector of the plane parallel to both lines
+	const Vector3 norm = Normalize(CrossProd(ray1.mRay->GetDir(), ray2.mRay->GetDir()));
+
+	// vector from line 1 to line 2
+	const Vector3 vd = ray2.ExtrapOrigin() - ray1.ExtrapOrigin();
+
+	// project vector on normal to get distance
+	const float dist = DotProd(vd, norm);
+
+	// point on plane lies halfway between the two planes
+	const Vector3 planePt = ray1.ExtrapOrigin() + norm * dist * 0.5;
+
+	return Plane3(norm, planePt);
+}
+
+
+inline void VspBspTree::GenerateUniqueIdsForPvs()
+{
+	Intersectable::NewMail(); sBackId = Intersectable::sMailId;
+	Intersectable::NewMail(); sFrontId = Intersectable::sMailId;
+	Intersectable::NewMail(); sFrontAndBackId = Intersectable::sMailId;
+}
+
+
+float VspBspTree::EvalSplitPlaneCost(const Plane3 &candidatePlane,
+									 const VspBspTraversalData &data,
+									 BspNodeGeometry &geomFront,
+									 BspNodeGeometry &geomBack,
+									 float &pFront,
+									 float &pBack) const
+{
+	float cost = 0;
+
+	float sumBalancedRays = 0;
+	float sumRaySplits = 0;
+
+	int pvsFront = 0;
+	int pvsBack = 0;
+
+	// probability that view point lies in back / front node
+	float pOverall = 0;
+	pFront = 0;
+	pBack = 0;
+
+	int raysFront = 0;
+	int raysBack = 0;
+	int totalPvs = 0;
+
+	int limit;
+	bool useRand;
+
+	// choose test rays randomly if too much
+	if ((int)data.mRays->size() > mMaxTests)
+	{
+		useRand = true;
+		limit = mMaxTests;
+	}
+	else
+	{
+		useRand = false;
+		limit = (int)data.mRays->size();
+	}
+	
+	for (int i = 0; i < limit; ++ i)
+	{
+		const int testIdx = useRand ? 
+			(int)RandomValue(0, (Real)((int)data.mRays->size() - 1)) : i;
+		RayInfo rayInf = (*data.mRays)[testIdx];
+
+		float t;
+		VssRay *ray = rayInf.mRay;
+		const int cf = rayInf.ComputeRayIntersection(candidatePlane, t);
+
+        if (0)
+		{
+			if (cf >= 0)
+				++ raysFront;
+			if (cf <= 0)
+				++ raysBack;
+		}
+
+		if (mSplitPlaneStrategy & LEAST_RAY_SPLITS)
+		{
+			sumBalancedRays += cf;
+		}
+
+		if (mSplitPlaneStrategy & BALANCED_RAYS)
+		{
+			if (cf == 0)
+				++ sumRaySplits;
+		}
+
+		if (mSplitPlaneStrategy & PVS)
+		{
+			// find front and back pvs for origing and termination object
+			AddObjToPvs(ray->mTerminationObject, cf, pvsFront, pvsBack, totalPvs);
+			AddObjToPvs(ray->mOriginObject, cf, pvsFront, pvsBack, totalPvs);
+		}
+	}
+
+	const float raysSize = (float)data.mRays->size() + Limits::Small;
+
+	if (mSplitPlaneStrategy & PVS)
+	{
+		// create unique ids for pvs heuristics
+		GenerateUniqueIdsForPvs();
+
+		// construct child geometry with regard to the candidate split plane
+		data.mGeometry->SplitGeometry(geomFront,
+									  geomBack,
+									  candidatePlane,
+									  mBox,
+									  mEpsilon);
+
+		pOverall = data.mProbability;
+
+		if (!mUseAreaForPvs) // use front and back cell areas to approximate volume
+		{
+			pFront = geomFront.GetVolume();
+			pBack = pOverall - geomFront.GetVolume();
+		}
+		else
+		{
+			pFront = geomFront.GetArea();
+			pBack = geomBack.GetArea();
+		}
+	}
+
+
+	if (mSplitPlaneStrategy & LEAST_RAY_SPLITS)
+		cost += mLeastRaySplitsFactor * sumRaySplits / raysSize;
+
+	if (mSplitPlaneStrategy & BALANCED_RAYS)
+		cost += mBalancedRaysFactor * fabs(sumBalancedRays) / raysSize;
+
+	// -- pvs rendering heuristics
+	if (mSplitPlaneStrategy & PVS)
+	{
+		const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize();
+		const int upperPvsLimit = mViewCellsManager->GetMaxPvsSize();
+
+		// only render cost heuristics or combined with standard deviation
+		if (1)
+		{
+			const float penaltyOld = EvalPvsPenalty(totalPvs, lowerPvsLimit, upperPvsLimit);
+         	const float penaltyFront = EvalPvsPenalty(pvsFront, lowerPvsLimit, upperPvsLimit);
+			const float penaltyBack = EvalPvsPenalty(pvsBack, lowerPvsLimit, upperPvsLimit);
+			
+			const float oldRenderCost = pOverall * (float)penaltyOld + Limits::Small;
+			const float newRenderCost = penaltyFront * pFront + penaltyBack * pBack;
+
+			float oldCost, newCost;
+
+			if (1)
+			{
+				oldCost = oldRenderCost;
+				newCost = newRenderCost;
+			}
+			else
+			{
+				// standard deviation is difference of back and front pvs
+				const float expectedCost = 0.5f * (penaltyFront + penaltyBack);
+
+				const float newDeviation = 0.5f * 
+					fabs(penaltyFront - expectedCost) + fabs(penaltyBack - expectedCost);
+
+                const float oldDeviation = penaltyOld + Limits::Small;
+
+				newCost = mRenderCostWeight * newRenderCost + (1.0f - mRenderCostWeight) * newDeviation;
+				oldCost = mRenderCostWeight * oldRenderCost + (1.0f - mRenderCostWeight) * oldDeviation;
+			}
+
+			cost += mPvsFactor * newCost / oldCost;
+		}
+		else
+		{
+			//-- compute weighted sum of expected render cost and standard deviation
+			
+			//-- first compute expected render cost		
+			const float penaltyOld = EvalPvsPenalty(totalPvs, lowerPvsLimit, upperPvsLimit);
+         	const float penaltyFront = EvalPvsPenalty(pvsFront, lowerPvsLimit, upperPvsLimit);
+			const float penaltyBack = EvalPvsPenalty(pvsBack, lowerPvsLimit, upperPvsLimit);
+			
+			const float renderCostFront = penaltyFront * pFront;
+			const float renderCostBack = penaltyBack * pBack;
+
+			const float oldRenderCost = pOverall * (float)penaltyOld + Limits::Small;
+			const float newRenderCost = renderCostFront + renderCostBack;
+
+
+			//-- compute standard deviation
+			const float expectedCost = 0.5f * (renderCostBack + renderCostFront);
+
+			const float devFront = fabs(renderCostFront - expectedCost);
+			
+			const float devBack = fabs(renderCostBack - expectedCost);
+
+			const float newDev = 0.5f * (devFront + devBack);
+			const float oldDev = oldRenderCost * oldRenderCost;
+
+			const float newCost = newRenderCost * mRenderCostWeight + newDev * (1.0f - mRenderCostWeight);
+			const float oldCost = oldRenderCost * mRenderCostWeight + oldDev * (1.0f - mRenderCostWeight);
+
+			cost += mPvsFactor * newCost / oldCost;
+
+			// also try to equalize render differences between front and back pvs
+			//const float oldCost = pOverall + Limits::Small;
+			//float newCost = (float)abs(pvsFront - pvsBack);
+			
+		}
+	}
+
+#ifdef _DEBUG
+  	Debug << "totalpvs: " << data.mPvs << " ptotal: " << pOverall
+  		  << " frontpvs: " << pvsFront << " pFront: " << pFront
+  		  << " backpvs: " << pvsBack << " pBack: " << pBack << endl << endl;
+#endif
+
+	// normalize cost by sum of linear factors
+	if(0)
+		return cost / (float)mCostNormalizer;
+	else
+		return cost;
+}
+
+
 float VspBspTree::EvalAxisAlignedSplitCost(const VspBspTraversalData &data,
 										   const AxisAlignedBox3 &box,
@@ -1110,353 +1483,4 @@
 
 	return  (mCtDivCi + newCost) / oldCost;
-}
-
-
-
-bool VspBspTree::SelectPlane(Plane3 &bestPlane,
-							 BspLeaf *leaf,
-							 VspBspTraversalData &data,
-							 VspBspTraversalData &frontData,
-							 VspBspTraversalData &backData)
-{
-	// simplest strategy: just take next polygon
-	if (mSplitPlaneStrategy & RANDOM_POLYGON)
-	{
-        if (!data.mPolygons->empty())
-		{
-			const int randIdx = 
-				(int)RandomValue(0, (Real)((int)data.mPolygons->size() - 1));
-			Polygon3 *nextPoly = (*data.mPolygons)[randIdx];
-
-			bestPlane = nextPoly->GetSupportingPlane();
-			return true;
-		}
-	}
-
-	//-- use heuristics to find appropriate plane
-
-	// intermediate plane
-	Plane3 plane;
-	float lowestCost = MAX_FLOAT;
-	
-	// decides if the first few splits should be only axisAligned
-	const bool onlyAxisAligned  = 
-		(mSplitPlaneStrategy & AXIS_ALIGNED) &&
-		((int)data.mRays->size() > mTermMinRaysForAxisAligned) &&
-		((int)data.GetAvgRayContribution() < mTermMaxRayContriForAxisAligned);
-	
-	const int limit = onlyAxisAligned ? 0 : 
-		Min((int)data.mPolygons->size(), mMaxPolyCandidates);
-
-	float candidateCost;
-
-	int maxIdx = (int)data.mPolygons->size();
-
-	for (int i = 0; i < limit; ++ i)
-	{
-		// the already taken candidates are stored behind maxIdx
-		// => assure that no index is taken twice
-		const int candidateIdx = (int)RandomValue(0, (Real)(-- maxIdx));
-		Polygon3 *poly = (*data.mPolygons)[candidateIdx];
-
-		// swap candidate to the end to avoid testing same plane
-		std::swap((*data.mPolygons)[maxIdx], (*data.mPolygons)[candidateIdx]);
-		//Polygon3 *poly = (*data.mPolygons)[(int)RandomValue(0, (int)polys.size() - 1)];
-
-		// evaluate current candidate
-		BspNodeGeometry fGeom, bGeom;
-		float fArea, bArea;
-		plane = poly->GetSupportingPlane();
-		candidateCost = EvalSplitPlaneCost(plane, data, fGeom, bGeom, fArea, bArea);
-		
-		if (candidateCost < lowestCost)
-		{
-			bestPlane = plane;
-			lowestCost = candidateCost;
-		}
-	}
-
-	//-- evaluate axis aligned splits
-	int axis;
-	BspNodeGeometry *fGeom, *bGeom;
-	float pFront, pBack;
-
-	candidateCost = SelectAxisAlignedPlane(plane, data, axis,
-										   &fGeom, &bGeom, 
-										   pFront, pBack,
-										   data.mIsKdNode);	 
-
-	bool isAxisAlignedSplit = false;
-
-	if (candidateCost < lowestCost)
-	{	
-		bestPlane = plane;
-		lowestCost = candidateCost;
-
-		// assign already computed values
-		// we can do this because we always save the
-		// computed values from the axis aligned splits		
-		frontData.mGeometry = fGeom;
-		backData.mGeometry = bGeom;
-	
-		frontData.mProbability = pFront;
-		backData.mProbability = pBack;
-		
-		//! error also computed if cost ratio is missed
-		++ mBspStats.splits[axis];
-		isAxisAlignedSplit = true;
-	}
-	else
-	{
-		DEL_PTR(fGeom);
-		DEL_PTR(bGeom);
-	}
-
-	frontData.mIsKdNode = backData.mIsKdNode = (data.mIsKdNode && isAxisAlignedSplit);
-
-#ifdef _DEBUG
-	Debug << "plane lowest cost: " << lowestCost << endl;
-#endif
-
-	// cost ratio miss
-	if (lowestCost > mTermMaxCostRatio)
-		return false;
-
-	return true;
-}
-
-
-Plane3 VspBspTree::ChooseCandidatePlane(const RayInfoContainer &rays) const
-{
-	const int candidateIdx = (int)RandomValue(0, (Real)((int)rays.size() - 1));
-
-	const Vector3 minPt = rays[candidateIdx].ExtrapOrigin();
-	const Vector3 maxPt = rays[candidateIdx].ExtrapTermination();
-
-	const Vector3 pt = (maxPt + minPt) * 0.5;
-	const Vector3 normal = Normalize(rays[candidateIdx].mRay->GetDir());
-
-	return Plane3(normal, pt);
-}
-
-
-Plane3 VspBspTree::ChooseCandidatePlane2(const RayInfoContainer &rays) const
-{
-	Vector3 pt[3];
-
-	int idx[3];
-	int cmaxT = 0;
-	int cminT = 0;
-	bool chooseMin = false;
-
-	for (int j = 0; j < 3; ++ j)
-	{
-		idx[j] = (int)RandomValue(0, (Real)((int)rays.size() * 2 - 1));
-
-		if (idx[j] >= (int)rays.size())
-		{
-			idx[j] -= (int)rays.size();
-
-			chooseMin = (cminT < 2);
-		}
-		else
-			chooseMin = (cmaxT < 2);
-
-		RayInfo rayInf = rays[idx[j]];
-		pt[j] = chooseMin ? rayInf.ExtrapOrigin() : rayInf.ExtrapTermination();
-	}
-
-	return Plane3(pt[0], pt[1], pt[2]);
-}
-
-Plane3 VspBspTree::ChooseCandidatePlane3(const RayInfoContainer &rays) const
-{
-	Vector3 pt[3];
-
-	int idx1 = (int)RandomValue(0, (Real)((int)rays.size() - 1));
-	int idx2 = (int)RandomValue(0, (Real)((int)rays.size() - 1));
-
-	// check if rays different
-	if (idx1 == idx2)
-		idx2 = (idx2 + 1) % (int)rays.size();
-
-	const RayInfo ray1 = rays[idx1];
-	const RayInfo ray2 = rays[idx2];
-
-	// normal vector of the plane parallel to both lines
-	const Vector3 norm = Normalize(CrossProd(ray1.mRay->GetDir(), ray2.mRay->GetDir()));
-
-	// vector from line 1 to line 2
-	const Vector3 vd = ray2.ExtrapOrigin() - ray1.ExtrapOrigin();
-
-	// project vector on normal to get distance
-	const float dist = DotProd(vd, norm);
-
-	// point on plane lies halfway between the two planes
-	const Vector3 planePt = ray1.ExtrapOrigin() + norm * dist * 0.5;
-
-	return Plane3(norm, planePt);
-}
-
-
-inline void VspBspTree::GenerateUniqueIdsForPvs()
-{
-	Intersectable::NewMail(); sBackId = ViewCell::sMailId;
-	Intersectable::NewMail(); sFrontId = ViewCell::sMailId;
-	Intersectable::NewMail(); sFrontAndBackId = ViewCell::sMailId;
-}
-
-
-float VspBspTree::EvalSplitPlaneCost(const Plane3 &candidatePlane,
-									 const VspBspTraversalData &data,
-									 BspNodeGeometry &geomFront,
-									 BspNodeGeometry &geomBack,
-									 float &pFront,
-									 float &pBack) const
-{
-	float cost = 0;
-
-	float sumBalancedRays = 0;
-	float sumRaySplits = 0;
-
-	int pvsFront = 0;
-	int pvsBack = 0;
-
-	// probability that view point lies in back / front node
-	float pOverall = 0;
-	pFront = 0;
-	pBack = 0;
-
-	int raysFront = 0;
-	int raysBack = 0;
-	int totalPvs = 0;
-
-	int limit;
-	bool useRand;
-
-	// choose test rays randomly if too much
-	if ((int)data.mRays->size() > mMaxTests)
-	{
-		useRand = true;
-		limit = mMaxTests;
-	}
-	else
-	{
-		useRand = false;
-		limit = (int)data.mRays->size();
-	}
-	
-	for (int i = 0; i < limit; ++ i)
-	{
-		const int testIdx = useRand ? 
-			(int)RandomValue(0, (Real)((int)data.mRays->size() - 1)) : i;
-		RayInfo rayInf = (*data.mRays)[testIdx];
-
-		float t;
-		VssRay *ray = rayInf.mRay;
-		const int cf = rayInf.ComputeRayIntersection(candidatePlane, t);
-
-        if (0)
-		{
-			if (cf >= 0)
-				++ raysFront;
-			if (cf <= 0)
-				++ raysBack;
-		}
-
-		if (mSplitPlaneStrategy & LEAST_RAY_SPLITS)
-		{
-			sumBalancedRays += cf;
-		}
-
-		if (mSplitPlaneStrategy & BALANCED_RAYS)
-		{
-			if (cf == 0)
-				++ sumRaySplits;
-		}
-
-		if (mSplitPlaneStrategy & PVS)
-		{
-			// find front and back pvs for origing and termination object
-			AddObjToPvs(ray->mTerminationObject, cf, pvsFront, pvsBack, totalPvs);
-			AddObjToPvs(ray->mOriginObject, cf, pvsFront, pvsBack, totalPvs);
-		}
-	}
-
-	const float raysSize = (float)data.mRays->size() + Limits::Small;
-
-	if (mSplitPlaneStrategy & PVS)
-	{
-		// create unique ids for pvs heuristics
-		GenerateUniqueIdsForPvs();
-
-		// construct child geometry with regard to the candidate split plane
-		data.mGeometry->SplitGeometry(geomFront,
-									  geomBack,
-									  candidatePlane,
-									  mBox,
-									  mEpsilon);
-
-		pOverall = data.mProbability;
-
-		if (!mUseAreaForPvs) // use front and back cell areas to approximate volume
-		{
-			pFront = geomFront.GetVolume();
-			pBack = pOverall - geomFront.GetVolume();
-		}
-		else
-		{
-			pFront = geomFront.GetArea();
-			pBack = geomBack.GetArea();
-		}
-	}
-
-
-	if (mSplitPlaneStrategy & LEAST_RAY_SPLITS)
-		cost += mLeastRaySplitsFactor * sumRaySplits / raysSize;
-
-	if (mSplitPlaneStrategy & BALANCED_RAYS)
-		cost += mBalancedRaysFactor * fabs(sumBalancedRays) / raysSize;
-
-	// pvs criterium
-	if (mSplitPlaneStrategy & PVS)
-	{
-		if (1)
-		{
-			const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize();
-			const int upperPvsLimit = mViewCellsManager->GetMaxPvsSize();
-			
-			const float penaltyOld = EvalPvsPenalty(totalPvs, lowerPvsLimit, upperPvsLimit);
-            
-			const float penaltyFront = EvalPvsPenalty(pvsFront, lowerPvsLimit, upperPvsLimit);
-			const float penaltyBack = EvalPvsPenalty(pvsBack, lowerPvsLimit, upperPvsLimit);
-			
-			const float oldCost = pOverall * (float)penaltyOld + Limits::Small;
-			cost += mPvsFactor * (penaltyFront * pFront + penaltyBack * pBack) / oldCost;
-
-		}
-		else
-		{
-			// try to equalize render differences
-			//const float oldCost = pOverall * (float)totalPvs + Limits::Small;
-			//float newCost = fabs(pvsFront * pFront - pvsBack * pBack);
-			const float oldCost = pOverall + Limits::Small;
-			float newCost = (float)abs(pvsFront - pvsBack);
-
-			cost += mPvsFactor * newCost / oldCost;
-		}
-	}
-
-#ifdef _DEBUG
-  	Debug << "totalpvs: " << data.mPvs << " ptotal: " << pOverall
-  		  << " frontpvs: " << pvsFront << " pFront: " << pFront
-  		  << " backpvs: " << pvsBack << " pBack: " << pBack << endl << endl;
-#endif
-
-	// normalize cost by sum of linear factors
-	if(0)
-		return cost / (float)mCostNormalizer;
-	else
-		return cost;
 }
 
@@ -1731,9 +1755,13 @@
 			{
 				BspViewCell *viewCell = dynamic_cast<BspLeaf *>(node)->GetViewCell();
-			
-				vector<BspLeaf *>::const_iterator it, it_end = viewCell->mLeaves.end();
-				for (it = viewCell->mLeaves.begin();it != it_end; ++ it)
+	
+				ViewCellContainer leaves;
+				mViewCellsManager->GetViewCellsTree()->CollectLeaves(viewCell, leaves);
+
+				ViewCellContainer::const_iterator it, it_end = leaves.end();
+
+				for (it = leaves.begin(); it != it_end; ++ it)
 				{
-					BspLeaf *l = *it;
+					BspLeaf *l = dynamic_cast<BspViewCell *>(*it)->mLeaf;
 					l->SetViewCell(GetOrCreateOutOfBoundsCell());
 					++ mBspStats.invalidLeaves;
@@ -2024,9 +2052,14 @@
 								   BspNodeGeometry &vcGeom) const
 {
-	vector<BspLeaf *> leaves = vc->mLeaves;
-	vector<BspLeaf *>::const_iterator it, it_end = leaves.end();
+	ViewCellContainer leaves;
+	mViewCellsManager->GetViewCellsTree()->CollectLeaves(vc, leaves);
+
+	ViewCellContainer::const_iterator it, it_end = leaves.end();
 
 	for (it = leaves.begin(); it != it_end; ++ it)
-		ConstructGeometry(*it, vcGeom);
+	{
+		BspLeaf *l = dynamic_cast<BspViewCell *>(*it)->mLeaf;
+		ConstructGeometry(l, vcGeom);
+	}
 }
 
@@ -2456,4 +2489,5 @@
 }
 
+
 BspNode *VspBspTree::CollapseTree(BspNode *node, int &collapsed)
 {
@@ -2499,10 +2533,11 @@
 {
 	int collapsed = 0;
-	
+	//TODO
+#if VC_HISTORY
 	(void)CollapseTree(mRoot, collapsed);
 
 	// revalidate leaves
 	RepairViewCellsLeafLists();
-
+#endif
 	return collapsed;
 }
@@ -2527,5 +2562,6 @@
 
 			BspViewCell *viewCell = leaf->GetViewCell();
-
+	// TODO
+#if VC_HISTORY
 			if (!viewCell->Mailed())
 			{
@@ -2533,6 +2569,8 @@
 				viewCell->Mail();
 			}
-
+	
 			viewCell->mLeaves.push_back(leaf);
+// TODO
+#endif
 		}
 		else
@@ -2631,69 +2669,4 @@
 
 
-bool VspBspTree::MergeViewCells(BspLeaf *l1, BspLeaf *l2) //const
-{
-	//-- change pointer to view cells of all leaves associated
-	//-- with the previous view cells
-	BspViewCell *fVc = l1->GetViewCell();
-	BspViewCell *bVc = l2->GetViewCell();
-
-	BspViewCell *vc = dynamic_cast<BspViewCell *>(
-		mViewCellsManager->MergeViewCells(*fVc, *bVc));
-
-	// if merge was unsuccessful
-	if (!vc) return false;
-
-	// set new size of view cell
-	if (mUseAreaForPvs)
-		vc->SetArea(fVc->GetArea() + bVc->GetArea());
-	else
-		vc->SetVolume(fVc->GetVolume() + bVc->GetVolume());
-	
-	vector<BspLeaf *> fLeaves = fVc->mLeaves;
-	vector<BspLeaf *> bLeaves = bVc->mLeaves;
-
-	vector<BspLeaf *>::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->mLeaves.push_back(*it);
-	}
-
-	for (it = bLeaves.begin(); it != bLeaves.end(); ++ it)
-	{
-		(*it)->SetViewCell(vc);
-		vc->mLeaves.push_back(*it);
-	}
-
-	// important so other merge candidates sharing this view cell
-	// are notified that the merge cost must be updated!!
-	vc->Mail();
-
-	//-- clean up old view cells
-	if (mExportMergedViewCells)
-	{
-		DEL_PTR(fVc);
-		DEL_PTR(bVc);
-	}
-	else 
-	{
-		// old view cells container needed for visualization
-		//fVc->mMailbox = -1;
-		//bVc->mMailbox = -1;
-		fVc->SetId(-2);
-		bVc->SetId(-2);
-
-		mOldViewCells.push_back(fVc);
-		mOldViewCells.push_back(bVc);
-		
-		mNewViewCells.push_back(vc);
-	}
-
-	return true;
-}
-
-
 void VspBspTree::SetViewCellsManager(ViewCellsManager *vcm)
 {
@@ -2702,5 +2675,6 @@
 
 
-int VspBspTree::CollectMergeCandidates(const vector<BspLeaf *> leaves)
+int VspBspTree::CollectMergeCandidates(const vector<BspLeaf *> leaves,
+									   vector<MergeCandidate> &candidates)
 {
 	BspLeaf::NewMail();
@@ -2708,5 +2682,5 @@
 	vector<BspLeaf *>::const_iterator it, it_end = leaves.end();
 
-	int candidates = 0;
+	int numCandidates = 0;
 
 	// find merge candidates and push them into queue
@@ -2714,10 +2688,4 @@
 	{
 		BspLeaf *leaf = *it;
-		
-		/// create leaf pvs (needed for post processing)
-		leaf->mPvs = new ObjectPvs(leaf->GetViewCell()->GetPvs());
-
-		//const float rc = leaf->mProbability * (float)leaf->mPvs->GetSize();
-		//BspMergeCandidate::sOverallCost += rc;
 		
 		// the same leaves must not be part of two merge candidates
@@ -2733,12 +2701,11 @@
 			if ((*nit)->GetViewCell() != leaf->GetViewCell())
 			{
-				BspMergeCandidate mc(leaf, *nit);
-				mc.EvalMergeCost();
-
-				mMergeQueue.push(mc);
-				++ candidates;
-				if ((candidates % 1000) == 0)
+				MergeCandidate mc(leaf->GetViewCell(), (*nit)->GetViewCell());
+				candidates.push_back(mc);
+
+				++ numCandidates;
+				if ((numCandidates % 1000) == 0)
 				{
-					cout << "collected " << candidates << " merge candidates" << endl;
+					cout << "collected " << numCandidates << " merge candidates" << endl;
 				}
 			}
@@ -2746,8 +2713,7 @@
 	}
 
-	Debug << "mergequeue: " << (int)mMergeQueue.size() << endl;
-	Debug << "leaves in queue: " << candidates << endl;
-	Debug << "overall cost: " << BspMergeCandidate::sOverallCost << endl;
-
+	Debug << "merge queue: " << (int)candidates.size() << endl;
+	Debug << "leaves in queue: " << numCandidates << endl;
+	
 
 	return (int)leaves.size();
@@ -2755,5 +2721,6 @@
 
 
-int VspBspTree::CollectMergeCandidates(const VssRayContainer &rays)
+int VspBspTree::CollectMergeCandidates(const VssRayContainer &rays, 
+									   vector<MergeCandidate> &candidates)
 {
 	ViewCell::NewMail();
@@ -2775,20 +2742,8 @@
 		if (ray->mViewCells.size() < 2)
 			continue;
-	  
+//TODO viewcellhierarchy
 		iit = ray->mViewCells.begin();
 		BspViewCell *bspVc = dynamic_cast<BspViewCell *>(*(iit ++));
-		BspLeaf *leaf = bspVc->mLeaves[0];
-		
-		// create leaf pvs (needed for post processing)
-		if (!leaf->mPvs)
-		{
-			leaf->mPvs = 
-				new ObjectPvs(leaf->GetViewCell()->GetPvs());
-
-			//BspMergeCandidate::sOverallCost += 
-			//	leaf->mProbability * leaf->mPvs->GetSize();
-			
-			++ numLeaves;
-		}
+		BspLeaf *leaf = bspVc->mLeaf;
 		
 		// traverse intersections 
@@ -2799,5 +2754,5 @@
 			BspLeaf *prevLeaf = leaf;
 			bspVc = dynamic_cast<BspViewCell *>(*iit);
-            leaf = bspVc->mLeaves[0];
+            leaf = bspVc->mLeaf;
 
 			// view space not valid or same view cell
@@ -2806,17 +2761,5 @@
 				continue;
 
-            // create leaf pvs (needed for post processing)
-			if (!leaf->mPvs)
-			{
-				leaf->mPvs = 
-					new ObjectPvs(leaf->GetViewCell()->GetPvs());
-				
-				//BspMergeCandidate::sOverallCost += 
-				//	leaf->mProbability * leaf->mPvs->GetSize();
-
-				++ numLeaves;
-			}
-		
-			vector<BspLeaf *> &neighbors = neighborMap[leaf];
+           	vector<BspLeaf *> &neighbors = neighborMap[leaf];
 			
 			bool found = false;
@@ -2843,12 +2786,11 @@
 				prevLeaf->Mail();
 		
-				BspMergeCandidate mc(leaf, prevLeaf);
-				mc.EvalMergeCost();
-
-				mMergeQueue.push(mc);
-
-				if (((int)mMergeQueue.size() % 1000) == 0)
+				MergeCandidate mc(leaf->GetViewCell(), prevLeaf->GetViewCell());
+				
+				candidates.push_back(mc);
+
+				if (((int)candidates.size() % 1000) == 0)
 				{
-					cout << "collected " << (int)mMergeQueue.size() << " merge candidates" << endl;
+					cout << "collected " << (int)candidates.size() << " merge candidates" << endl;
 				}
 			}
@@ -2857,7 +2799,7 @@
 
 	Debug << "neighbormap size: " << (int)neighborMap.size() << endl;
-	Debug << "mergequeue: " << (int)mMergeQueue.size() << endl;
+	Debug << "merge queue: " << (int)candidates.size() << endl;
 	Debug << "leaves in queue: " << numLeaves << endl;
-	Debug << "overall cost: " << BspMergeCandidate::sOverallCost << endl;
+
 
 	//-- collect the leaves which haven't been found by ray casting
@@ -2868,5 +2810,5 @@
 		CollectLeaves(leaves, true);
 		Debug << "found " << (int)leaves.size() << " new leaves" << endl << endl;
-		CollectMergeCandidates(leaves);
+		CollectMergeCandidates(leaves, candidates);
 	}
 
@@ -2875,391 +2817,4 @@
 
 
-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);
-	}
-}
-
-
-#if 1
-int VspBspTree::MergeViewCells(const VssRayContainer &rays, const ObjectContainer &objects)
-{
-	BspMergeCandidate::sViewCellsManager = mViewCellsManager;
-	BspMergeCandidate::sUseArea = mUseAreaForPvs;
-
-
-	//-- compute statistics values of initial view cells
-	mViewCellsManager->EvaluateRenderStatistics(BspMergeCandidate::sOverallCost, 
-												BspMergeCandidate::sExpectedCost,
-												BspMergeCandidate::sVariance);
-
-
-	//BspMergeCandidate::sExpectedCost = 
-	//	BspMergeCandidate::sOverallCost / BspMergeCandidate::sNumViewCells;
-
-
-	ViewCellsManager::PvsStatistics pvsStats;
-	mViewCellsManager->GetPvsStatistics(pvsStats);
-
-	static float expectedValue = pvsStats.avgPvs;
-	
-	// the current view cells are kept in this container
-	ViewCellContainer viewCells;
-	if (mExportMergedViewCells)
-	{
-		ViewCell::NewMail();
-		CollectViewCells(mRoot, true, viewCells, true);
-	}
-
-
-	ViewCell::NewMail();
-
-	MergeStatistics mergeStats;
-	mergeStats.Start();
-	
-	long startTime = GetTime();
-
-	cout << "collecting merge candidates ... " << endl;
-	
-	if (mUseRaysForMerge)
-	{
-		mergeStats.nodes = CollectMergeCandidates(rays);
-	}
-	else
-	{
-		vector<BspLeaf *> leaves;
-		CollectLeaves(leaves);
-		mergeStats.nodes = CollectMergeCandidates(leaves);
-	}
-	
-	cout << "fininshed collecting candidates" << endl;
-
-	mergeStats.collectTime = TimeDiff(startTime, GetTime());
-	mergeStats.candidates = (int)mMergeQueue.size();
-	startTime = GetTime();
-
-	// frequency stats are updated
-	const int statsOut = 100;
-
-	// number of view cells withouth the invalid ones
-	BspMergeCandidate::sNumViewCells = mBspStats.Leaves() - mBspStats.invalidLeaves;
-
-	// passes are needed for statistics, because we don't want to record
-	// every merge
-	const int maxMergesPerPass = 100;
-	int pass = 0;
-
-	// maximal ratio of old expected render cost to expected render
-	// when the the render queue has to be reset.
-	const float ercMaxRatio = 0.7f;
-	
-	cout << "actual merge starts now ... " << endl;
-
-	
-	
-	//-- use priority queue to merge leaf pairs
-
-
-	while (!mMergeQueue.empty() && 
-		   (BspMergeCandidate::sNumViewCells > mMergeMinViewCells) &&
-		   (mMergeQueue.top().GetMergeCost() < mMergeMaxCostRatio * BspMergeCandidate::sOverallCost))
-	{
-
-		int mergedPerPass = 0;
-		const float oldExpectedCost = BspMergeCandidate::sExpectedCost;
-		
-//#ifdef _DEBUG
-		Debug << "abs mergecost: " << mMergeQueue.top().GetMergeCost() << " rel mergecost: "
-			  << mMergeQueue.top().GetMergeCost() / BspMergeCandidate::sOverallCost 
-			  << " max ratio: " << mMergeMaxCostRatio << endl
-			  << " expected value: " << oldExpectedCost << endl;
-//#endif
-
-		while (!mMergeQueue.empty() && 
-			   (BspMergeCandidate::sNumViewCells > mMergeMinViewCells) &&
-			   (ercMaxRatio > oldExpectedCost / BspMergeCandidate::sExpectedCost) &&
-			   (mMergeQueue.top().GetMergeCost() < mMergeMaxCostRatio * BspMergeCandidate::sOverallCost) &&
-			   (maxMergesPerPass < mergedPerPass));
-		{
-				Debug << "erc max ratio" << ercMaxRatio << endl;
-
-				BspMergeCandidate mc = mMergeQueue.top();
-				mMergeQueue.pop();
-
-				// both view cells equal!
-				if (mc.GetLeaf1()->GetViewCell() == mc.GetLeaf2()->GetViewCell())
-					continue;
-
-				if (mc.Valid())
-				{
-					ViewCell::NewMail();
-					const float currentMergeCost = mc.GetMergeCost();
-
-					MergeViewCells(mc.GetLeaf1(), mc.GetLeaf2());
-					
-					-- BspMergeCandidate::sNumViewCells;
-					++ mergeStats.merged;
-					++ mergedPerPass;
-
-					// increase absolute merge cost
-					BspMergeCandidate::sOverallCost += mc.GetRenderCost();
-					BspMergeCandidate::sVariance = mc.GetVarianceIncr();
-
-					BspMergeCandidate::sExpectedCost = 
-						BspMergeCandidate::sOverallCost / (float)BspMergeCandidate::sNumViewCells;
-
-					// stats
-					if (mc.GetLeaf1()->IsSibling(mc.GetLeaf2()))
-						++ mergeStats.siblings;
-
-					if (0)
-					{
-						const int dist = 
-							TreeDistance(mc.GetLeaf1(), mc.GetLeaf2());
-						if (dist > mergeStats.maxTreeDist)
-							mergeStats.maxTreeDist = dist;
-						mergeStats.accTreeDist += dist;
-					}
-
-					if ((mergeStats.merged % statsOut) == 0)
-					{
-						cout << "merged " << mergeStats.merged << " view cells" << endl;
-
-						mStats 
-							<< "#Pass\n" << pass << endl
-							<< "#Merged\n" << mergeStats.merged << endl 
-							<< "#Viewcells\n" << BspMergeCandidate::sNumViewCells << endl 
-							<< "#OverallCost\n" << BspMergeCandidate::sOverallCost << endl
-							<< "#CurrentCost\n" << currentMergeCost << endl
-							<< "#RelativeCost\n" << currentMergeCost / BspMergeCandidate::sOverallCost << endl
-							<< "#CurrentPvs\n" << mc.GetLeaf1()->GetViewCell()->GetPvs().GetSize() << endl
-							<< "#MergedSiblings\n" << mergeStats.siblings << endl
-							<< "#AvgTreeDist\n" << mergeStats.AvgTreeDist() << endl
-							<< "#ExpectedCost\n" << BspMergeCandidate::sExpectedCost << endl
-							<< "#RatioExpectedCost\n" << oldExpectedCost / BspMergeCandidate::sExpectedCost << endl
-							<< "#variance\n" << BspMergeCandidate::sVariance << endl;
-
-						if (mExportMergedViewCells)
-							ExportMergedViewCells(viewCells, objects, BspMergeCandidate::sNumViewCells);
-					}
-				}
-				else
-				{ 
-
-					// merge candidate not valid, because one of the leaves was already
-					// merged with another one => validate and reinsert into queue
-					mc.SetValid();
-					mMergeQueue.push(mc);
-				}
-		}
-	
-
-		++ pass;
-	}
-
-	mergeStats.overallCost = BspMergeCandidate::sOverallCost;
-
-	mergeStats.mergeTime = TimeDiff(startTime, GetTime());
-	mergeStats.Stop();
-
-	Debug << mergeStats << endl << endl;
-	
-	// delete the view cells which were already merged
-	CLEAR_CONTAINER(mOldViewCells);
-	
-
-	//TODO: should return sample contributions?
-	return mergeStats.merged;
-}
-
-#else
-
-int VspBspTree::MergeViewCells(const VssRayContainer &rays, const ObjectContainer &objects)
-{
-	BspMergeCandidate::sViewCellsManager = mViewCellsManager;
-	BspMergeCandidate::sUseArea = mUseAreaForPvs;
-
-	ViewCellsManager::PvsStatistics pvsStats;
-	mViewCellsManager->GetPvsStatistics(pvsStats);
-
-	static float expectedValue = pvsStats.avgPvs;
-	// the current view cells are kept in this container
-	ViewCellContainer viewCells;
-	if (mExportMergedViewCells)
-	{
-		ViewCell::NewMail();
-		CollectViewCells(mRoot, true, viewCells, true);
-	}
-	ViewCell::NewMail();
-
-	MergeStatistics mergeStats;
-	mergeStats.Start();
-	
-	//BspMergeCandidate::sOverallCost = mBox.SurfaceArea() * mBspStats.maxPvs;
-	long startTime = GetTime();
-
-	cout << "collecting merge candidates ... " << endl;
-	
-	if (mUseRaysForMerge)
-	{
-		mergeStats.nodes = CollectMergeCandidates(rays);
-	}
-	else
-	{
-		vector<BspLeaf *> leaves;
-		CollectLeaves(leaves);
-		mergeStats.nodes = CollectMergeCandidates(leaves);
-	}
-	
-	cout << "fininshed collecting candidates" << endl;
-
-	mergeStats.collectTime = TimeDiff(startTime, GetTime());
-	mergeStats.candidates = (int)mMergeQueue.size();
-	startTime = GetTime();
-
-	
-	// number of view cells withouth the invalid ones
-	int nViewCells = mBspStats.Leaves() - mBspStats.invalidLeaves;
-	BspMergeCandidate::sExpectedCost = BspMergeCandidate::sOverallCost / (float)nViewCells;
-
-	// passes are needed for statistics, because we don't want to record
-	// every merge
-	const int mergesPerPass = 100;
-	
-	int nextPass = 0;
-    int pass = 0;
-	
-	
-	Debug << "stats: " << nextStats << " " << statsIncr << endl;
-	cout << "actual merge starts now ... " << endl;
-
-	//-- use priority queue to merge leaf pairs
-	while (!mMergeQueue.empty() && (nViewCells > mMergeMinViewCells) &&
-		   (mMergeQueue.top().GetMergeCost() <
-		    mMergeMaxCostRatio * BspMergeCandidate::sOverallCost))
-	{
-#ifdef _DEBUG
-		Debug << "abs mergecost: " << mMergeQueue.top().GetMergeCost() << " rel mergecost: "
-			  << mMergeQueue.top().GetMergeCost() / BspMergeCandidate::sOverallCost 
-			  << " max ratio: " << mMergeMaxCostRatio << endl;
-#endif
-
-		BspMergeCandidate mc = mMergeQueue.top();
-		mMergeQueue.pop();
-
-
-		// both view cells equal!
-		if (mc.GetLeaf1()->GetViewCell() == mc.GetLeaf2()->GetViewCell())
-			continue;
-
-		if (mc.Valid())
-		{
-			ViewCell::NewMail();
-			const float mergeCost = mc.GetMergeCost();
-
-			MergeViewCells(mc.GetLeaf1(), mc.GetLeaf2());
-					
-			// increase absolute merge cost
-			BspMergeCandidate::sOverallCost += mc.GetMergeCost();
-			
-
-			-- nViewCells;
-			++ mergeStats.merged;
-
-			if ((mergeStats.merged % 500) == 0)
-				cout << "merged " << mergeStats.merged << " view cells" << endl;
-
-			// stats and visualizations
-			if (mExportMergeStats)
-			{
-				if (mc.GetLeaf1()->IsSibling(mc.GetLeaf2()))
-					++ mergeStats.siblings;
-
-				if (0)
-				const int dist = 
-					TreeDistance(mc.GetLeaf1(), mc.GetLeaf2());
-				if (dist > mergeStats.maxTreeDist)
-					mergeStats.maxTreeDist = dist;
-				mergeStats.accTreeDist += dist;
-
-				if ((mergeStats.merged == nextPass) || (nViewCells == mMergeMinViewCells))
-				{
-					nextPass += mergesPerPass;
-
-					mStats 
-						<< "#Pass\n" << pass ++ << endl
-						<< "#Merged\n" << mergeStats.merged << endl 
-						<< "#Viewcells\n" << nViewCells << endl 
-						<< "#OverallCost\n" << BspMergeCandidate::sOverallCost << endl
-						<< "#CurrentCost\n" << mergeCost << endl
-						<< "#RelativeCost\n" << mergeCost / BspMergeCandidate::sOverallCost << endl
-						<< "#CurrentPvs\n" << mc.GetLeaf1()->GetViewCell()->GetPvs().GetSize() << endl
-						<< "#MergedSiblings\n" << mergeStats.siblings << endl
-						<< "#AvgTreeDist\n" << mergeStats.AvgTreeDist() << endl;
-
-						if (mExportMergedViewCells)
-							ExportMergedViewCells(viewCells, objects, nViewCells);
-				}
-			}
-		}
-		// 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.overallCost = BspMergeCandidate::sOverallCost;
-
-	mergeStats.mergeTime = TimeDiff(startTime, GetTime());
-	mergeStats.Stop();
-
-	Debug << mergeStats << endl << endl;
-	
-	// delete the view cells which were already merged
-	CLEAR_CONTAINER(mOldViewCells);
-	
-
-	//TODO: should return sample contributions?
-	return mergeStats.merged;
-}
-#endif
 
 
@@ -3297,326 +2852,4 @@
 
 
-void VspBspTree::ExportMergedViewCells(ViewCellContainer &viewCells, 
-									   const ObjectContainer &objects,
-									   const int nViewCells)
-{
-	ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
-					
-	// find all already merged view cells and remove them from view cells
-	int i = 0;
-
-	while (1)
-	{
-		//while (!viewCells.empty() && (viewCells.back()->mMailbox == -1))
-		while (!viewCells.empty() && (viewCells.back()->GetId() == -2))
-		{
-			//DEL_PTR(viewCells.back());
-			viewCells.pop_back();
-		}
-		// all merged view cells have been found
-		if (i >= viewCells.size()) 
-			break;
-
-		// already merged view cell, put it to end of vector
-		//if (viewCells[i]->mMailbox == -1)
-		if (viewCells[i]->GetId() == -2)
-			swap(viewCells[i], viewCells.back());
-		
-		++ i;
-	}
-
-	int newVcSize = 0;
-	// add new view cells to container only if they don't have been 
-	// merged in the mean time
-	while (!mNewViewCells.empty())
-	{
-		if (mNewViewCells.back()->GetId() != -2)
-		{
-			viewCells.push_back(mNewViewCells.back());
-			++ newVcSize;
-		}
-
-		mNewViewCells.pop_back();
-	}
-
-	char s[64];
-	sprintf(s, "merged_viewcells%07d.x3d", nViewCells);
-	Exporter *exporter = Exporter::GetExporter(s);
-
-	if (exporter)
-	{
-		cout << "exporting " << nViewCells << " merged view cells ... ";
-		exporter->ExportGeometry(objects);
-		//Debug << "vc size " << (int)viewCells.size() << " merge queue size: " << (int)mMergeQueue.size() << endl;
-		ViewCellContainer::const_iterator it, it_end = viewCells.end();
-
-		int i = 0;
-		for (it = viewCells.begin(); it != it_end; ++ it)
-		{
-			Material m;
-			// assign special material to new view cells
-			// new view cells are on the back of container
-			if (i ++ >= (viewCells.size() - newVcSize))
-			{
-				//m = RandomMaterial();
-				m.mDiffuseColor.r = RandomValue(0.5f, 1.0f);
-				m.mDiffuseColor.g = RandomValue(0.5f, 1.0f);
-				m.mDiffuseColor.b = RandomValue(0.5f, 1.0f);
-			}
-			else
-			{
-				float col = RandomValue(0.1f, 0.4f);
-				m.mDiffuseColor.r = col;
-				m.mDiffuseColor.g = col;
-				m.mDiffuseColor.b = col;
-			}
-
-			exporter->SetForcedMaterial(m);
-			mViewCellsManager->ExportVcGeometry(exporter, *it);
-		}
-		delete exporter;
-		cout << "finished" << endl;
-	}
-
-	// delete the view cells which were merged
-	CLEAR_CONTAINER(mOldViewCells);
-	// remove the new view cells
-	mNewViewCells.clear();
-}
-
-
-int VspBspTree::RefineViewCells(const VssRayContainer &rays, const ObjectContainer &objects)
-{
-	Debug << "refining " << (int)mMergeQueue.size() << " candidates " << endl;
-	
-	BspLeaf::NewMail();
-
-	// Use priority queue of remaining leaf pairs 
-	// The 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.
-	//
-	// repeat the merging test numPasses times. For example, it could be
-	// that a shuffle only makes sense if another pair was shuffled before.
-	// Therefore we keep two queues and shift the merge candidates between
-	// those two queues until numPasses is reached
-	
-	queue<BspMergeCandidate> queue1;
-	queue<BspMergeCandidate> queue2;
-
-	queue<BspMergeCandidate> *shuffleQueue = &queue1;
-	queue<BspMergeCandidate> *backQueue = &queue2;
-
-	while (!mMergeQueue.empty())
-	{
-		BspMergeCandidate mc = mMergeQueue.top();
-		shuffleQueue->push(mc);
-		mMergeQueue.pop();
-	}
-
-	const int numPasses = 5;
-	int pass = 0;
-	int passShuffled = 0;
-	int shuffled = 0;
-
-	BspLeaf::NewMail();
-
-	do
-	{
-		passShuffled = 0;
-		while (!shuffleQueue->empty())
-		{
-			BspMergeCandidate mc = shuffleQueue->front();
-			shuffleQueue->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());
-		
-			if (wasShuffled)
-				++ passShuffled;
-			else
-				backQueue->push(mc);
-		}
-
-		// now the back queue is the current shuffle queue
-		swap(shuffleQueue, backQueue);
-		shuffled += passShuffled;
-		Debug << "shuffled in pass: " << passShuffled << endl;
-	}
-	while (((++ pass) < numPasses) && passShuffled);
-
-	while (!shuffleQueue->empty())
-	{
-		shuffleQueue->pop();
-	}
-
-	return shuffled;
-}
-
-
-inline int AddedPvsSize(ObjectPvs pvs1, const ObjectPvs &pvs2)
-{
-	return pvs1.AddPvs(pvs2);
-}
-
-
-// recomputes pvs size minus pvs of leaf l
-#if 0
-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();
-}
-#endif
-
-// computes pvs1 minus pvs2
-inline int SubtractedPvsSize(ObjectPvs pvs1, const ObjectPvs &pvs2)
-{
-	return pvs1.SubtractPvs(pvs2);
-}
-
-
-float VspBspTree::GetShuffledVcCost(BspLeaf *leaf, BspViewCell *vc1, BspViewCell *vc2) const
-{
-	//const int pvs1 = SubtractedPvsSize(vc1, leaf, *leaf->mPvs);
-	const int pvs1 = SubtractedPvsSize(vc1->GetPvs(), *leaf->mPvs);
-	const int pvs2 = AddedPvsSize(vc2->GetPvs(), *leaf->mPvs);
-
-	// don't shuffle leaves with pvs > max
-	if (pvs1 + pvs2 > mViewCellsManager->GetMaxPvsSize())
-		return 1e15f;
-
-#if 1
-	float p1, p2;
-
-    if (mUseAreaForPvs)
-	{
-		p1 = vc1->GetArea() - leaf->mProbability;
-		p2 = vc2->GetArea() + leaf->mProbability;
-	}
-	else
-	{
-		p1 = vc1->GetVolume() - leaf->mProbability;
-		p2 = vc2->GetVolume() + leaf->mProbability;
-	}
-
-	const float cost1 = pvs1 * p1;
-	const float cost2 = pvs2 * p2;
-#else
-	const float cost1 = pvs1;
-	const float cost2 = pvs2;
-#endif
-
-	return cost1 + cost2;
-}
-
-
-void VspBspTree::ShuffleLeaf(BspLeaf *leaf, 
-							 BspViewCell *vc1, 
-							 BspViewCell *vc2) const
-{
-	// compute new pvs and area
-	vc1->GetPvs().SubtractPvs(*leaf->mPvs);
-	vc2->GetPvs().AddPvs(*leaf->mPvs);
-	
-	if (mUseAreaForPvs)
-	{
-		vc1->SetArea(vc1->GetArea() - leaf->mProbability);
-		vc2->SetArea(vc2->GetArea() + leaf->mProbability);
-	}
-	else
-	{
-		vc1->SetVolume(vc1->GetVolume() - leaf->mProbability);
-		vc2->SetVolume(vc2->GetVolume() + leaf->mProbability);
-	}
-
-	/// 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
-}
-
-
-bool VspBspTree::ShuffleLeaves(BspLeaf *leaf1, BspLeaf *leaf2) const
-{
-	BspViewCell *vc1 = leaf1->GetViewCell();
-	BspViewCell *vc2 = leaf2->GetViewCell();
-
-	float cost1, cost2;
-
-#if 1
-	if (mUseAreaForPvs)
-	{
-		cost1 = vc1->GetPvs().GetSize() * vc1->GetArea();
-		cost2 = vc2->GetPvs().GetSize() * vc2->GetArea();
-	}
-	else
-	{
-		cost1 = vc1->GetPvs().GetSize() * vc1->GetVolume();
-		cost2 = vc2->GetPvs().GetSize() * vc2->GetVolume();
-	}
-#else
-	cost1 = vc1->GetPvs().GetSize(); 
-	cost2 = vc2->GetPvs().GetSize(); 
-#endif
-
-	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)
-	{
-		ShuffleLeaf(leaf1, vc1, vc2);
-		leaf1->Mail();
-	}
-	else
-	{
-		ShuffleLeaf(leaf2, vc2, vc1);
-		leaf2->Mail();
-	}
-
-	return true;
-}
-
-
 bool VspBspTree::ViewPointValid(const Vector3 &viewPoint) const
 {
@@ -3713,224 +2946,2 @@
 	}
 }
-
-
-/**************************************************************************/
-/*                  BspMergeCandidate implementation                      */
-/**************************************************************************/
-
-
-BspMergeCandidate::BspMergeCandidate(BspLeaf *l1, BspLeaf *l2):
-mRenderCost(0),
-mVarianceIncr(0),
-mLeaf1(l1),
-mLeaf2(l2),
-mLeaf1Id(l1->GetViewCell()->mMailbox),
-mLeaf2Id(l2->GetViewCell()->mMailbox)
-{
-	//EvalMergeCost();
-}
-
-
-float BspMergeCandidate::GetRenderCost(ViewCell *vc) const
-{
-	if (sUseArea)
-		return vc->GetPvs().GetSize() * vc->GetArea();
-
-	return vc->GetPvs().GetSize() * vc->GetVolume();
-}
-
-
-float BspMergeCandidate::GetLeaf1Cost() const
-{
-	BspViewCell *vc = mLeaf1->GetViewCell();
-
-	return GetRenderCost(vc);
-}
-
-
-float BspMergeCandidate::GetLeaf2Cost() const
-{
-	BspViewCell *vc = mLeaf2->GetViewCell();
-
-	return GetRenderCost(vc);
-}
-
-
-int ComputeMergedPvsSize(const ObjectPvs &pvs1, const ObjectPvs &pvs2)
-{
-	int pvs = pvs1.GetSize();
-
-	// compute new pvs size
-	ObjectPvsMap::const_iterator it, it_end =  pvs1.mEntries.end();
-
-	Intersectable::NewMail();
-
-	for (it = pvs1.mEntries.begin(); it != it_end; ++ it)
-	{
-		(*it).first->Mail();
-	}
-
-	it_end = pvs2.mEntries.end();
-
-	for (it = pvs2.mEntries.begin(); it != it_end; ++ it)
-	{
-		Intersectable *obj = (*it).first;
-		if (!obj->Mailed())
-			++ pvs;
-	}
-
-	return pvs;
-}
-
-
-
-void BspMergeCandidate::EvalMergeCost()
-{
-	//-- compute pvs difference
-	BspViewCell *vc1 = mLeaf1->GetViewCell();
-	BspViewCell *vc2 = mLeaf2->GetViewCell();
-
-	const int newPvs = ComputeMergedPvsSize(vc1->GetPvs(), vc2->GetPvs());
-	const float newPenalty = 
-		EvalPvsPenalty(newPvs, 
-					   sViewCellsManager->GetMinPvsSize(),
-					   sViewCellsManager->GetMaxPvsSize());
-
-	//-- compute ratio of old cost
-	//   (i.e., added size of left and right view cell times pvs size)
-	//   to new rendering cost (i.e, size of merged view cell times pvs size)
-	const float oldCost = GetLeaf1Cost() + GetLeaf2Cost();
-
-    const float newCost = sUseArea ? 
-		(float)newPvs * (vc1->GetArea() + vc2->GetArea()) :
-		(float)newPvs * (vc1->GetVolume() + vc2->GetVolume());
-
-
-	if (newPvs > sViewCellsManager->GetMaxPvsSize()) // strong penalty if pvs size too large
-	{
-		mRenderCost = 1e15;
-	}
-	else
-	{
-		mRenderCost = newCost - oldCost;
-	}
-
-	// merge cost also takes variance into account
-
-	const float oldVar1 = GetLeaf1Variance();
-	const float oldVar2 = GetLeaf2Variance();
-
-	const float newVar = (sExpectedCost - mRenderCost) * (sExpectedCost - mRenderCost);
-
-	mVarianceIncr = (newVar - oldVar1 - oldVar2) / sNumViewCells;
-	//mMergeCost = mRenderCost + fabs(newPenalty - BspMergeCandidate::sExpectedCost) ;
-}
-
-
-void BspMergeCandidate::SetLeaf1(BspLeaf *l)
-{
-	mLeaf1 = l;
-}
-
-
-void BspMergeCandidate::SetLeaf2(BspLeaf *l)
-{
-	mLeaf2 = l;
-}
-
-
-BspLeaf *BspMergeCandidate::GetLeaf1() const
-{
-	return mLeaf1;
-}
-
-
-BspLeaf *BspMergeCandidate::GetLeaf2() const
-{
-	return mLeaf2;
-}
-
-
-bool BspMergeCandidate::Valid() const
-{
-	return
-		(mLeaf1->GetViewCell()->mMailbox == mLeaf1Id) &&
-		(mLeaf2->GetViewCell()->mMailbox == mLeaf2Id);
-}
-
-
-float BspMergeCandidate::GetMergeCost() const
-{
-	return mRenderCost * sRenderCostWeight + mVarianceIncr * (1.0f - sRenderCostWeight);
-}
-
-
-float BspMergeCandidate::GetRenderCost() const
-{
-	return mRenderCost;
-}
-
-
-float BspMergeCandidate::GetVarianceIncr() const
-{
-	return mVarianceIncr;
-}
-
-float BspMergeCandidate::GetLeaf1Variance() const
-{
-	const float leafCost = GetLeaf1Cost();
-	
-	return (sExpectedCost - leafCost) * (sExpectedCost - leafCost);
-}
-
-
-float BspMergeCandidate::GetLeaf2Variance() const
-{
-	const float leafCost = GetLeaf2Cost();
-	
-	return (sExpectedCost - leafCost) * (sExpectedCost - leafCost);
-}
-
-
-void BspMergeCandidate::SetValid()
-{
-	mLeaf1Id = mLeaf1->GetViewCell()->mMailbox;
-	mLeaf2Id = mLeaf2->GetViewCell()->mMailbox;
-
-	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 << "#OVERALLCOST ( overall merge cost )\n" << overallCost << "\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";
-}
Index: /trunk/VUT/GtpVisibilityPreprocessor/src/Environment.cpp
===================================================================
--- /trunk/VUT/GtpVisibilityPreprocessor/src/Environment.cpp	(revision 579)
+++ /trunk/VUT/GtpVisibilityPreprocessor/src/Environment.cpp	(revision 580)
@@ -1283,4 +1283,43 @@
 		"false");
 	
+	
+	RegisterOption("ViewCells.PostProcess.maxCostRatio",
+			optFloat,
+			"-view_cells_post_process_max_cost_ratio=",
+			"0.9");
+
+	
+	RegisterOption("ViewCells.PostProcess.renderCostWeight",
+			optFloat,
+			"-view_cells_post_process_render_cost_weight",
+			"0.5");
+
+	
+	RegisterOption("ViewCells.PostProcess.avgCostMaxDeviation",
+			optFloat,
+			"-vsp_bsp_avgcost_max_deviations",
+			"0.5");
+
+	RegisterOption("ViewCells.PostProcess.maxMergesPerPass", 
+		optInt, 
+		"vsp_bsp_term_max_merges_per_pass=", 
+		"500");
+
+	RegisterOption("ViewCells.PostProcess.minViewCells", 
+		optInt, 
+		"vsp_bsp_term_post_process_min_view_cells=", 
+		"1000");
+
+	RegisterOption("ViewCells.PostProcess.useRaysForMerge", 
+		optBool,
+		"view_cells_post_process_use_rays_for_merge=", 
+		"false");
+
+	RegisterOption("ViewCells.Visualization.exportMergedViewCells",
+		optBool, 
+		"view_cells_viz_export_merged_viewcells=", 
+		"false");
+
+
 	/************************************************************************************/
 	/*                         Render simulation related options                        */
@@ -1834,18 +1873,10 @@
 	RegisterOption("VspBspTree.Factor.pvs", optFloat, "-vsp_bsp_factor_pvs=", "1.0");
 
-	RegisterOption("VspBspTree.PostProcess.maxCostRatio",
+
+	RegisterOption("VspBspTree.Construction.renderCostWeight",
 			optFloat,
-			"-vsp_bsp_post_process_max_cost_ratio=",
-			"0.9");
-
-	RegisterOption("VspBspTree.PostProcess.minViewCells", 
-		optInt, 
-		"vsp_bsp_term_post_process_min_view_cells=", 
-		"1000");
-
-	RegisterOption("VspBspTree.PostProcess.useRaysForMerge", 
-		optBool, 
-		"vsp_bsp_term_post_process_use_rays_for_merge=", 
-		"false");
+			"-vsp_bsp_post_process_render_cost_weight",
+			"0.5");
+
 
 	RegisterOption("VspBspTree.Construction.randomize", 
@@ -1865,13 +1896,6 @@
 		"8.0");
 
-	RegisterOption("VspBspTree.Visualization.exportMergedViewCells",
-		optBool, 
-		"vsp_bsp_viz_export_merged_viewcells=", 
-		"false");
-
-	RegisterOption("VspBspTree.PostProcess.exportMergeStats",
-		optBool, 
-		"vsp_bsp_viz_export_merge_stats=", 
-		"false");
+	
+	
 
 	//////////////////////////////////////////////////////////////////////////////////
Index: /trunk/VUT/GtpVisibilityPreprocessor/src/KdTree.cpp
===================================================================
--- /trunk/VUT/GtpVisibilityPreprocessor/src/KdTree.cpp	(revision 556)
+++ /trunk/VUT/GtpVisibilityPreprocessor/src/KdTree.cpp	(revision 580)
@@ -888,5 +888,5 @@
 	  leaf->mViewCell = viewCell;
 	  // push back pointer to this leaf
-	  viewCell->mLeaves.push_back(leaf);
+	  viewCell->mLeaf = leaf;
       vc.push_back(viewCell);
     } else {
Index: /trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp
===================================================================
--- /trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp	(revision 574)
+++ /trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp	(revision 580)
@@ -208,7 +208,7 @@
 
 
-/******************************************************************/
-/*                    class BspTree implementation                */
-/******************************************************************/
+/*********************************************************************/
+/*                       class BspTree implementation                */
+/*********************************************************************/
 
 BspTree::BspTree():  
@@ -840,5 +840,5 @@
 		
 		leaf->SetViewCell(viewCell);
-		viewCell->mLeaves.push_back(leaf);
+		viewCell->mLeaf = leaf;
 
 		//-- add pvs
@@ -2208,10 +2208,11 @@
 void BspTree::ConstructGeometry(BspViewCell *vc, BspNodeGeometry &geom) const
 {
-	vector<BspLeaf *> leaves = vc->mLeaves;
+	// TODO
+/*	vector<BspLeaf *> leaves = vc->mLeaves;
 
 	vector<BspLeaf *>::const_iterator it, it_end = leaves.end();
 
 	for (it = leaves.begin(); it != it_end; ++ it)
-		ConstructGeometry(*it, geom);
+		ConstructGeometry(*it, geom);*/
 }
 
Index: /trunk/VUT/GtpVisibilityPreprocessor/src/ViewCell.h
===================================================================
--- /trunk/VUT/GtpVisibilityPreprocessor/src/ViewCell.h	(revision 569)
+++ /trunk/VUT/GtpVisibilityPreprocessor/src/ViewCell.h	(revision 580)
@@ -16,4 +16,7 @@
 class VspKdLeaf;
 class KdLeaf;
+class ViewCellInterior;
+class MergeCandidate;
+class ViewCellsManager;
 
 /** Statistics for a view cell partition.
@@ -78,7 +81,10 @@
 };
 
+
 /**
 	View cell with an optional mesh representation
 */
+
+
 class ViewCell: public MeshInstance
 {
@@ -93,4 +99,5 @@
 	*/
 	virtual ~ViewCell() {}
+
 	/** Returns Pvs.
 	*/
@@ -100,4 +107,6 @@
 	int Type() const;
 
+	void SetParent(ViewCellInterior *parent);
+
 	/** Adds a passing ray to the passing ray container.
 	*/
@@ -124,16 +133,33 @@
 	virtual void UpdateViewCellsStats(ViewCellsStatistics &vcStat);
 
-	/// Ray set description of the rays passing through this node.
-	PassingRaySet mPassingRays;
+	/** if this view cell is the root of a view cell hierarchy
+	*/
+	bool IsRoot() const;
+
+	/** Returns parent view cell.
+	*/
+	ViewCellInterior *GetParent() const;
+
+	
+	/** Sets the mesh for this view cell.
+	*/
+	void SetMesh(Mesh *mesh);
+
+	void SetValid(const bool valid);
+	bool GetValid() const;
+
+
+
+
+	/// parent view cell in the view cell hierarchy
+	ViewCellInterior *mParent;
 
 	/// Rays piercing this view cell.
 	RayContainer mPiercingRays;
 
-	/** Sets the mesh for this view cell.
-	*/
-	void SetMesh(Mesh *mesh);
-
-	void SetValid(const bool valid);
-	bool GetValid() const;
+
+	/** if this is a view cell correspending to a leaf in a hierarchy.
+	*/
+	virtual bool IsLeaf() const = 0;
 
   static bool SmallerPvs(const ViewCell *a,
@@ -142,4 +168,27 @@
   }
 
+
+	void SetTimeStamp(const int timeStamp);
+	int GetTimeStamp() const;
+	static void NewMail(const int reserve = 1) {
+		sMailId += sReservedMailboxes;
+		sReservedMailboxes = reserve;
+	}
+	void Mail() { mMailbox = sMailId; }
+	bool Mailed() const { return mMailbox == sMailId; }
+
+	void Mail(const int mailbox) { mMailbox = sMailId + mailbox; }
+	bool Mailed(const int mailbox) const { return mMailbox == sMailId + mailbox; }
+
+	int IncMail() { return ++mMailbox - sMailId; }
+
+
+						 
+	// last mail id -> warning not thread safe!
+	// both mailId and mailbox should be unique for each thread!!!
+	static int sMailId;
+	static int sReservedMailboxes;
+	
+
 protected:
 
@@ -150,6 +199,26 @@
 	float mArea;
 
+	int mTimeStamp;
 
 	bool mValid;
+};
+
+
+class ViewCellInterior: public ViewCell
+{
+public:
+	ViewCellInterior();
+	~ViewCellInterior();
+
+	ViewCellInterior(Mesh *mesh);
+	
+
+	/** Sets pointer from parent to child and vice versa.
+	*/
+	void SetupChildLink(ViewCell *l);
+	bool IsLeaf() const;
+
+	ViewCellContainer mChildren;
+
 };
 
@@ -158,10 +227,11 @@
 */
 template<typename T>
-class HierarchyViewCell: public ViewCell
+class ViewCellLeaf: public ViewCell
 {
 public:
-	HierarchyViewCell<T>(): mLeaves(0) {}
-	HierarchyViewCell<T>(Mesh *mesh):
-		ViewCell(mesh), mLeaves(0) {}
+
+	ViewCellLeaf<T>(): mLeaf(NULL) {}
+	ViewCellLeaf<T>(Mesh *mesh):
+		ViewCell(mesh), mLeaf(NULL) {}
 
 	void UpdateViewCellsStats(ViewCellsStatistics &vcStat)
@@ -169,18 +239,284 @@
 		ViewCell::UpdateViewCellsStats(vcStat);
 
-		if ((int)mLeaves.size() > vcStat.maxLeaves)
-			vcStat.maxLeaves = (int)mLeaves.size();
-		vcStat.leaves += (int)mLeaves.size();
-	}
-
-	/// Leaves of the hierarchy which are part of this view cell.
-	std::vector<T> mLeaves;
-};
-
-
-typedef HierarchyViewCell<BspLeaf *> BspViewCell;
-typedef HierarchyViewCell<KdLeaf *> KdViewCell;
-typedef HierarchyViewCell<VspKdLeaf *> VspKdViewCell;
-
+		//if ((int)mLeaves.size() > vcStat.maxLeaves)
+		//	vcStat.maxLeaves = (int)mLeaves.size();
+		//vcStat.leaves += (int)mLeaves.size();
+	}
+
+	bool IsLeaf() const
+	{
+		return true;
+	}
+
+	/// Leaf of some hierarchy which is part of this view cell.
+	T mLeaf;
+};
+
+
+typedef ViewCellLeaf<BspLeaf *> BspViewCell;
+typedef ViewCellLeaf<KdLeaf *> KdViewCell;
+typedef ViewCellLeaf<VspKdLeaf *> VspKdViewCell;
+
+
+
+class ViewCellsTree
+{
+public:
+	ViewCellsTree(ViewCellsManager *vcm);
+	~ViewCellsTree();
+
+	/** Returns number of leaves this view cell consists of.
+	*/
+	int GetSize(ViewCell *vc) const;
+
+	/** Collects leaves corresponding to a view cell.
+	*/
+	void CollectLeaves(ViewCell *vc, ViewCellContainer &leaves) const;
+
+	/** Merges view cells according to some cost heuristics.
+	*/
+	int ConstructMergeTree(const VssRayContainer &rays, const ObjectContainer &objects);
+	
+	/** Refines view cells using shuffling, i.e., border leaves 
+		of two view cells are exchanged if the resulting view cells
+		are tested to be "better" than the old ones.
+		@returns number of refined view cells
+	*/
+	int RefineViewCells(const VssRayContainer &rays, const ObjectContainer &objects);
+
+	/** Compresses the pvs of the view cells.
+	*/
+	void CompressViewCellsPvs();
+
+	/** Returns optimal set of view cells for a given number of view cells.
+	*/
+	void CollectBestViewCellSet(ViewCellContainer &viewCells, const int numViewCells);
+
+protected:
+
+
+	//////////////////////////////////////////////////////////////
+	//                 merge options                            //
+	//////////////////////////////////////////////////////////////
+	
+
+	/** Returns cost of this leaf according to current heuristics.
+	*/
+	float GetCostHeuristics(ViewCell *vc) const;
+
+	/** Returns cost of leaf.
+	*/
+	float GetRenderCost(ViewCell *vc) const;
+
+	/** Evaluates the merge cost of this merge candidate pair.
+	*/
+	void EvalMergeCost(MergeCandidate &mc) const;
+
+	/** Variance of leaf.
+	*/
+	float GetVariance(ViewCell *vc) const;
+
+	/** Standard deviation of leaf.
+	*/
+	float GetDeviation(ViewCell *vc) const;
+
+	/** Recalculates this merge candidate and sets valid.
+	*/
+	void SetMergeCandidateValid(MergeCandidate &mc) const;
+
+	/** Merge view cells of leaves l1 and l2.
+		@returns difference in pvs size
+	*/
+	ViewCellInterior *MergeViewCells(ViewCell *l, ViewCell *r, int &pvsDiff); //const;
+
+	/** Shuffles, i.e. takes border leaf from view cell 1 and adds it 
+		to view cell 2.
+	*/
+	void ShuffleLeaf(ViewCell *leaf, ViewCell *vc1, ViewCell *vc2) const;	
+		
+	/** Shuffles the leaves, i.e., tests if exchanging
+		the leaves helps in improving the view cells.
+	*/
+	bool ShuffleLeaves(ViewCell *l, ViewCell *r) const;
+
+	/** Calculates cost for merge of view cell 1 and 2.
+	*/
+	float EvalShuffleCost(ViewCell *leaf, ViewCell *vc1, ViewCell *vc2) const;
+
+	/** Exports a snapshot of the merged view cells to disc.
+	*/
+	void ExportMergedViewCells(ViewCellContainer &viewCells, 
+							   const ObjectContainer &objects,
+							   const int numNewViewCells);
+
+
+
+	/** merge queue must be reset after some time because expected value
+		may not be valid.
+	*/
+	void ResetMergeQueue();
+
+	/** Updates the current top level of view cells.
+	*/
+	int UpdateMergedViewCells(ViewCellContainer &viewCells);
+
+
+
+	ViewCellsManager *mViewCellsManager;
+	ViewCell *mRoot;
+
+	/// if merge visualization should be shown
+	bool mExportMergedViewCells;
+
+	
+		
+	ViewCellContainer mInactiveViewCells;
+	ViewCellContainer mActiveViewCells;
+
+	/// weights between variance and render cost increase (must be between zero and one)
+	float mRenderCostWeight;
+
+	/// overall cost used to normalize cost ratio
+	float mOverallCost;
+	float mExpectedCost;
+    float mDeviation;
+	float mAvgRenderCost;
+
+	int mUseAreaForPvs;
+
+	int mNumViewCells;
+
+	/// minimal number of view cells
+	int mMergeMinViewCells;
+	/// maximal cost ratio for the merge
+	float mMergeMaxCostRatio;
+
+	ofstream mStats;
+
+	typedef priority_queue<MergeCandidate> MergeQueue;
+
+	MergeQueue mMergeQueue;
+
+	
+
+};
+
+
+/**
+	Candidate for leaf merging based on priority.
+*/
+class MergeCandidate
+{  
+	friend class ViewCellsTree;
+
+public:
+
+	MergeCandidate(ViewCell *l, ViewCell *r);
+
+	/** If this merge pair is still valid.
+	*/
+	bool IsValid() const;
+
+	
+	friend bool operator<(const MergeCandidate &leafa, const MergeCandidate &leafb)
+	{
+		return leafb.GetMergeCost() < leafa.GetMergeCost();
+	}
+
+	void SetLeftViewCell(ViewCell *l);
+	void SetRightViewCell(ViewCell *l);
+
+	ViewCell *GetLeftViewCell() const;
+	ViewCell *GetRightViewCell() const;
+
+	ViewCell *GetInitialLeftViewCell() const;
+	ViewCell *GetInitialRightViewCell() const;
+
+	/** Returns the increase of the standard deviation of this merge candidate.
+	*/
+	float GetDeviationIncr() const;
+
+	/** Merge cost of this candidate pair.
+	*/
+	float GetMergeCost() const;
+
+	/** Render cost of this candidate.
+	*/
+	float GetRenderCost() const;
+	
+	static float sRenderCostWeight;
+
+protected:
+
+	/// render cost increase by this merge
+	float mRenderCost;
+	/// increase / decrease of standard deviation
+	float mDeviationIncr;
+
+	ViewCell *mLeftViewCell;
+	ViewCell *mRightViewCell;
+
+	ViewCell *mInitialLeftViewCell;
+	ViewCell *mInitialRightViewCell;
+};
+
+
+class MergeStatistics: public StatisticsBase
+{
+public:
+	
+	int merged;
+	int siblings;
+	int candidates;
+	int nodes;
+
+	int accTreeDist;
+	int maxTreeDist;
+	
+	Real collectTime;
+	Real mergeTime;
+
+	Real overallCost;
+
+	Real expectedRenderCost;
+	Real deviation;
+	Real heuristics;
+
+	// Constructor
+	MergeStatistics() 
+	{
+		Reset();
+	}
+	
+	double AvgTreeDist() const {return (double)accTreeDist / (double)merged;}; 
+
+	void Reset() 
+	{
+		nodes = 0;
+		merged = 0;
+		siblings = 0;
+		candidates = 0;
+	
+		accTreeDist = 0;
+		maxTreeDist = 0;
+
+		collectTime = 0;
+		mergeTime = 0;
+		overallCost = 0;
+
+		expectedRenderCost = 0;
+		deviation = 0;
+		heuristics = 0;
+
+	}
+
+	void Print(ostream &app) const;
+
+	friend ostream &operator<<(ostream &s, const MergeStatistics &stat) 
+	{
+		stat.Print(s);
+		return s;
+	} 
+};
 
 #endif
Index: /trunk/VUT/GtpVisibilityPreprocessor/src/RenderSimulator.cpp
===================================================================
--- /trunk/VUT/GtpVisibilityPreprocessor/src/RenderSimulator.cpp	(revision 574)
+++ /trunk/VUT/GtpVisibilityPreprocessor/src/RenderSimulator.cpp	(revision 580)
@@ -94,5 +94,5 @@
 		ViewCell *vc = *it;
 
-		const bool valid = !vc->GetValid();
+		const bool valid = vc->GetValid();
 	
 
Index: /trunk/VUT/GtpVisibilityPreprocessor/src/X3dExporter.cpp
===================================================================
--- /trunk/VUT/GtpVisibilityPreprocessor/src/X3dExporter.cpp	(revision 564)
+++ /trunk/VUT/GtpVisibilityPreprocessor/src/X3dExporter.cpp	(revision 580)
@@ -850,5 +850,5 @@
 		{
 			ViewCell *vc = dynamic_cast<BspLeaf *>(node)->GetViewCell();
-     
+#if 0     
 			// set the mesh material according to the ray density
 			if (vc->mPassingRays.mRays) 
@@ -860,6 +860,9 @@
 				mForcedMaterial.mDiffuseColor.g = 1.0f - mForcedMaterial.mDiffuseColor.r;
 				ExportViewCell(vc);
+
 			}
-		} else 
+#endif
+		} 
+		else 
 		{
 			BspInterior *interior = (BspInterior *)node;
Index: /trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellsParser.cpp
===================================================================
--- /trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellsParser.cpp	(revision 577)
+++ /trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellsParser.cpp	(revision 580)
@@ -356,5 +356,5 @@
 	{
 		// TODO: get view cell with specified id
-		ViewCell dummyVc;
+		BspViewCell dummyVc;
 		dummyVc.SetId(viewCellId);
 
@@ -363,4 +363,5 @@
 			
 		BspViewCell *viewCell = dynamic_cast<BspViewCell *>(*vit);
+
 		if (viewCell->GetId() == viewCellId)
 		{
Index: /trunk/VUT/GtpVisibilityPreprocessor/src/VspKdTree.h
===================================================================
--- /trunk/VUT/GtpVisibilityPreprocessor/src/VspKdTree.h	(revision 517)
+++ /trunk/VUT/GtpVisibilityPreprocessor/src/VspKdTree.h	(revision 580)
@@ -43,9 +43,9 @@
 	Candidate for leaf merging based on priority.
 */
-class MergeCandidate
+class VspKdMergeCandidate
 {  
 public:
 
-	MergeCandidate(VspKdLeaf *l1, VspKdLeaf *l2);
+	VspKdMergeCandidate(VspKdLeaf *l1, VspKdLeaf *l2);
 
 	/** Computes PVS difference between the leaves.
@@ -61,5 +61,5 @@
 	void SetValid();
 
-	friend bool operator<(const MergeCandidate &leafa, const MergeCandidate &leafb)
+	friend bool operator<(const VspKdMergeCandidate &leafa, const VspKdMergeCandidate &leafb)
 	{
 		return leafb.GetMergeCost() < leafa.GetMergeCost();
@@ -850,5 +850,5 @@
 	ViewCellsManager *mViewCellsManager;
 
-	priority_queue<MergeCandidate> mMergeQueue;
+	priority_queue<VspKdMergeCandidate> mMergeQueue;
 
 
Index: /trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellsManager.cpp
===================================================================
--- /trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellsManager.cpp	(revision 579)
+++ /trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellsManager.cpp	(revision 580)
@@ -33,4 +33,6 @@
 	mViewSpaceBox.Initialize();
 	ParseEnvironment();
+
+	mViewCellsTree = new ViewCellsTree(this);
 }
 
@@ -53,4 +55,6 @@
 
 	environment->GetBoolValue("ViewCells.exportToFile", mExportViewCells);
+
+	environment->GetBoolValue("ViewCells.PostProcess.useRaysForMerge", mUseRaysForMerge);
 
 	mMinPvsSize = emptyViewCells ? 1 : 0;
@@ -75,5 +79,7 @@
 {
 	DEL_PTR(mRenderer);
-	CLEAR_CONTAINER(mViewCells);
+	//CLEAR_CONTAINER(mViewCells);
+	DEL_PTR(mViewCellsTree);
+
 	CLEAR_CONTAINER(mMeshContainer);
 }
@@ -302,5 +308,5 @@
 float ViewCellsManager::GetViewSpaceVolume()
 {
-	return mViewSpaceBox.GetVolume()*(2.0f*sqr(M_PI));
+	return mViewSpaceBox.GetVolume()*(2.0f*sqr((float)M_PI));
 }
 
@@ -356,27 +362,35 @@
 
 
-void ViewCellsManager::EvaluateRenderStatistics(float &totalRenderCost, 
+void ViewCellsManager::EvaluateRenderStatistics(float &totalRenderCost,
 												float &expectedRenderCost, 
-												float &variance)
+												float &deviation,
+												float &variance,
+												int &totalPvs,
+												float &avgRenderCost)
 {
 	ViewCellContainer::const_iterator it, it_end = mViewCells.end();
 
+
 	//-- compute expected value
 
 	totalRenderCost = 0;
+	totalPvs = 0;
 
 	for (it = mViewCells.begin(); it != it_end; ++ it)
 	{
 		ViewCell *vc = *it;
-
 		totalRenderCost += vc->GetPvs().GetSize() * vc->GetVolume();
-	}
-
+		totalPvs += (int)vc->GetPvs().GetSize();
+	}
+
+	// normalize with view space box
+	totalRenderCost /= mViewSpaceBox.GetVolume();
 	expectedRenderCost = totalRenderCost / (float)mViewCells.size();
-
-
-	//-- compute variance
-	
+	avgRenderCost = totalPvs / (float)mViewCells.size();
+
+
+	//-- compute standard defiation
 	variance = 0;
+	deviation = 0;
 
 	for (it = mViewCells.begin(); it != it_end; ++ it)
@@ -385,11 +399,17 @@
 
 		float renderCost = vc->GetPvs().GetSize() * vc->GetVolume();
-
-		const float var = (expectedRenderCost - renderCost) * (expectedRenderCost - renderCost);
-
-		variance += var;
-	}
-	
+		float dev;
+
+		if (1)
+			dev = fabs(avgRenderCost - (float)vc->GetPvs().GetSize());
+		else
+			dev = fabs(expectedRenderCost - renderCost);
+
+		deviation += dev;
+		variance += dev * dev;
+	}
+
 	variance /= (float)mViewCells.size();
+	deviation /= (float)mViewCells.size();
 }
 
@@ -493,23 +513,28 @@
 
 
-ViewCell *ViewCellsManager::MergeViewCells(ViewCell &front, ViewCell &back) const
-{
-	// generate merged view cell
-	ViewCell *vc = GenerateViewCell();
+ViewCellInterior *ViewCellsManager::MergeViewCells(ViewCell &left, ViewCell &right) const
+{
+	// generate parent view cell
+	ViewCellInterior *vc = new ViewCellInterior();//GenerateViewCell();
 
 	// merge pvs
-	vc->GetPvs().Merge(front.GetPvs(), back.GetPvs());
+	vc->GetPvs().Merge(left.GetPvs(), right.GetPvs());
 
 	//-- merge ray sets
 	if (0)
 	{
-		stable_sort(front.mPiercingRays.begin(), front.mPiercingRays.end());
-		stable_sort(back.mPiercingRays.begin(), back.mPiercingRays.end());
-
-		std::merge(front.mPiercingRays.begin(), front.mPiercingRays.end(),
-				   back.mPiercingRays.begin(), back.mPiercingRays.end(),
+		stable_sort(left.mPiercingRays.begin(), left.mPiercingRays.end());
+		stable_sort(right.mPiercingRays.begin(), right.mPiercingRays.end());
+
+		std::merge(left.mPiercingRays.begin(), left.mPiercingRays.end(),
+				   right.mPiercingRays.begin(), right.mPiercingRays.end(),
 				   vc->mPiercingRays.begin());
 	}
 
+
+	vc->SetupChildLink(&left);
+	vc->SetupChildLink(&right);
+
+
 	return vc;
 }
@@ -522,7 +547,7 @@
 
 
-ViewCell *ViewCellsManager::GenerateViewCell(Mesh *mesh) const
-{
-	return new ViewCell(mesh);
+ViewCellsTree *ViewCellsManager::GetViewCellsTree()
+{
+	return mViewCellsTree;
 }
 
@@ -814,5 +839,5 @@
 		{
 			ExportColor(exporter, *it);
-			ExportVcGeometry(exporter, *it);
+			ExportViewCellGeometry(exporter, *it);
 		}
 	}
@@ -1186,16 +1211,11 @@
 
 		Debug << i << ": pvs size=" << (int)vc->GetPvs().GetSize()
-			  << ", piercing rays=" << (int)vcRays.size()
-			  << ", leaves=" << (int)vc->mLeaves.size() << endl;
+			  << ", piercing rays=" << (int)vcRays.size() << endl;
+			 // << ", leaves=" << (int)vc->mLeaves.size() << endl;
 
 
 		// export rays piercing this view cell
-#if 0
 		exporter->ExportRays(vcRays, RgbColor(0, 1, 0));
-#else
-		vector<BspLeaf *>::const_iterator lit, lit_end = vc->mLeaves.end();
-		for (lit = vc->mLeaves.begin(); lit != lit_end; ++ lit)
-			exporter->ExportRays((*lit)->mVssRays);
-#endif
+
 		m.mDiffuseColor = RgbColor(1, 0, 0);
 		exporter->SetForcedMaterial(m);
@@ -1249,5 +1269,5 @@
 		{
 			BspViewCell *vc = dynamic_cast<BspViewCell *>(*vit);
-			ray->intersections.push_back(BspIntersection(0, vc->mLeaves[0]));
+			ray->intersections.push_back(BspIntersection(0, vc->mLeaf));
 		}
 
@@ -1278,7 +1298,5 @@
 	case 2: // merges
 		{
-			BspViewCell *bspVc = dynamic_cast<BspViewCell *>(vc);
-
-			importance = (float)bspVc->mLeaves.size() /
+			importance = (float)mViewCellsTree->GetSize(vc) /
 				(float)mViewCellsStats.maxLeaves;
 		}
@@ -1301,5 +1319,5 @@
 }
 
-void BspViewCellsManager::ExportVcGeometry(Exporter *exporter,
+void BspViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
 										 ViewCell *vc) const
 {
@@ -1332,4 +1350,11 @@
   return mBspTree->GetViewCell(point);
 }
+
+
+void BspViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays, vector<MergeCandidate> &candidates)
+{
+	// TODO
+}
+
 
 /**********************************************************************/
@@ -1585,13 +1610,24 @@
 }
 
-
-void KdViewCellsManager::ExportVcGeometry(Exporter *exporter,
-										  ViewCell *vc) const
-{
-	KdViewCell *kdVc = dynamic_cast<KdViewCell *>(vc);
-	vector<KdLeaf *>::const_iterator it, it_end = kdVc->mLeaves.end();
-
-	for (it = kdVc->mLeaves.begin(); it != it_end; ++ it)
-		exporter->ExportBox(mKdTree->GetBox(*it));
+ViewCell *KdViewCellsManager::GenerateViewCell(Mesh *mesh) const
+{
+	return new KdViewCell(mesh);
+}
+
+
+void KdViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
+												ViewCell *vc) const
+{
+	ViewCellContainer leaves;
+
+	mViewCellsTree->CollectLeaves(vc, leaves);
+	ViewCellContainer::const_iterator it, it_end = leaves.end();
+
+	for (it = leaves.begin(); it != it_end; ++ it)
+	{
+		KdViewCell *kdVc = dynamic_cast<KdViewCell *>(*it);
+	
+		exporter->ExportBox(mKdTree->GetBox(kdVc->mLeaf));
+	}
 }
 
@@ -1625,4 +1661,13 @@
 	// TODO
 }
+
+
+
+void KdViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays, 
+												vector<MergeCandidate> &candidates)
+{
+	// TODO
+}
+
 
 /**********************************************************************/
@@ -1798,15 +1843,20 @@
 		exporter->SetWireframe();
 
-		ExportVcGeometry(exporter, vc);
+		ExportViewCellGeometry(exporter, vc);
 
 		//-- export stored rays
+		
 		if (mExportRays)
 		{
-			vector<VspKdLeaf *>::const_iterator it,
-				it_end = vc->mLeaves.end();
-
-			for (it = vc->mLeaves.begin(); it != it_end; ++ it)
+			ViewCellContainer leaves;
+			mViewCellsTree->CollectLeaves(vc, leaves);
+
+			ViewCellContainer::const_iterator it,
+				it_end = leaves.end();
+
+			for (it = leaves.begin(); it != it_end; ++ it)
 			{
-				VspKdLeaf *leaf = *it;
+				VspKdViewCell *vspKdVc = dynamic_cast<VspKdViewCell *>(*it);
+				VspKdLeaf *leaf = vspKdVc->mLeaf;
 				AxisAlignedBox3 box = mVspKdTree->GetBBox(leaf);
 
@@ -1834,5 +1884,5 @@
 			}
 		}
-
+	
 		//-- output PVS of view cell
 		m.mDiffuseColor = RgbColor(1, 0, 0);
@@ -1927,9 +1977,8 @@
 		}
 		break;
-	case 2: // merges
-		{
-            VspKdViewCell *vspKdVc = dynamic_cast<VspKdViewCell *>(vc);
-
-			importance = (float)vspKdVc->mLeaves.size() /
+	case 2: // merged leaves
+		{
+        	int lSize = mViewCellsTree->GetSize(vc);
+			importance = (float)lSize /
 				(float)mViewCellsStats.maxLeaves;
 		}
@@ -1954,14 +2003,20 @@
 
 
-void VspKdViewCellsManager::ExportVcGeometry(Exporter *exporter,
+void VspKdViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
 										   ViewCell *vc) const
 {
 	VspKdViewCell *kdVc = dynamic_cast<VspKdViewCell *>(vc);
-	vector<VspKdLeaf *>::const_iterator it, it_end = kdVc->mLeaves.end();
 
 	Mesh m;
-	for (it = kdVc->mLeaves.begin(); it != it_end; ++ it)
-	{
-		mVspKdTree->GetBBox(*it).AddBoxToMesh(&m);
+
+	ViewCellContainer leaves;
+	mViewCellsTree->CollectLeaves(vc, leaves);
+
+	ViewCellContainer::const_iterator it, it_end = leaves.end();
+
+	for (it = leaves.begin(); it != it_end; ++ it)
+	{
+		VspKdLeaf *l = dynamic_cast<VspKdViewCell *>(*it)->mLeaf;
+		mVspKdTree->GetBBox(l).AddBoxToMesh(&m);
 	}
 
@@ -1975,4 +2030,9 @@
 }
 
+
+void VspKdViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays, vector<MergeCandidate> &candidates)
+{
+	// TODO
+}
 
 
@@ -2131,6 +2191,7 @@
 	long startTime = GetTime();
 
+	
 	// TODO: should be done BEFORE the ray casting
-	merged = mVspBspTree->MergeViewCells(rays, objects);
+	merged = mViewCellsTree->ConstructMergeTree(rays, objects);
 
 	//-- stats and visualizations
@@ -2194,5 +2255,5 @@
 
 	// refining the merged view cells
-	const int refined = mVspBspTree->RefineViewCells(rays, objects);
+	const int refined = mViewCellsTree->RefineViewCells(rays, objects);
 
 	//-- stats and visualizations
@@ -2234,4 +2295,5 @@
 	mViewCellsStats.Reset();
 	EvaluateViewCellsStats();
+
 	// has to be recomputed
 	mTotalAreaValid = false;
@@ -2254,6 +2316,24 @@
 	//-- merge the individual view cells
 	MergeViewCells(postProcessRays, objects);
+
 	//-- refines the merged view cells
 	RefineViewCells(postProcessRays, objects);
+
+	if (1)
+	{		
+		float totalCost, erc, var, dev, avg;
+		int totalpvs;
+
+		mViewCellsStats.Reset();
+
+        EvaluateRenderStatistics(totalCost, erc, dev, var, totalpvs, avg);
+		
+		Debug << "statistics after merge "  
+			  << " erc: " << erc 
+			  << " dev: " << dev
+			  << " totalpvs: " << totalpvs 
+			  << " avg: " << avg << endl;
+	}
+
 
 	//-- export shuffled view cells
@@ -2293,9 +2373,13 @@
 				vm.mDiffuseColor.b -= 0.45f;
 
-				vector<BspLeaf *>::const_iterator lit, lit_end = vc->mLeaves.end();
-
-				for (lit = vc->mLeaves.begin(); lit != lit_end; ++ lit)
+
+				ViewCellContainer leaves;
+				mViewCellsTree->CollectLeaves(vc, leaves);
+
+				ViewCellContainer::const_iterator lit, lit_end = leaves.end();
+
+				for (lit = leaves.begin(); lit != lit_end; ++ lit)
 				{
-					BspLeaf *leaf = *lit;
+					BspLeaf *leaf = dynamic_cast<BspViewCell *>(*lit)->mLeaf;
 
 					if (leaf->Mailed())
@@ -2391,9 +2475,10 @@
 	if (1) // export view cells
 	{
-		cout << "exporting view cells after post process ... ";
 		Exporter *exporter = Exporter::GetExporter("final_view_cells.x3d");
 
 		if (exporter)
 		{
+			cout << "exporting view cells after post process ... ";
+
 			if (1)
 			{
@@ -2416,4 +2501,5 @@
 			ExportViewCellsForViz(exporter);
 			delete exporter;
+			cout << "finished" << endl;
 		}
 	}
@@ -2446,9 +2532,12 @@
 				BspViewCell *vc = dynamic_cast<BspViewCell *>(*vit);
 
-				vector<BspLeaf *>::const_iterator lit, lit_end = vc->mLeaves.end();
-
-				for (lit = vc->mLeaves.begin(); lit != lit_end; ++ lit)
+				ViewCellContainer leaves;
+				mViewCellsTree->CollectLeaves(vc, leaves);
+
+				ViewCellContainer::const_iterator lit, lit_end = leaves.end();
+
+				for (lit = leaves.begin(); lit != lit_end; ++ lit)
 				{
-					BspLeaf *leaf = *lit;
+					BspLeaf *leaf = dynamic_cast<BspViewCell *>(*lit)->mLeaf;
 
 					Material m; 
@@ -2573,5 +2662,5 @@
 				{
 					BspViewCell *bspVc = dynamic_cast<BspViewCell *>(ray->mViewCells[j]);
-					BspLeaf *leaf = bspVc->mLeaves[0];
+					BspLeaf *leaf = bspVc->mLeaf;
 					if (vc == bspVc)
 						vcRays.push_back(ray);
@@ -2589,10 +2678,10 @@
 		exporter->SetForcedMaterial(m);
 
-		ExportVcGeometry(exporter, vc);
+		ExportViewCellGeometry(exporter, vc);
 
 
 		Debug << i << ": pvs size=" << (int)vc->GetPvs().GetSize()
-			  << ", piercing rays=" << (int)vcRays.size()
-			  << ", leaves=" << (int)vc->mLeaves.size() << endl;
+			  << ", piercing rays=" << (int)vcRays.size() << endl;
+			//  << ", leaves=" << (int)vc->mLeaves.size() << endl;
 
 		
@@ -2604,8 +2693,15 @@
 		else
 		{
-			vector<BspLeaf *>::const_iterator lit, lit_end = vc->mLeaves.end();
-
-			for (lit = vc->mLeaves.begin(); lit != lit_end; ++ lit)
-				exporter->ExportRays((*lit)->mVssRays);
+
+			ViewCellContainer leaves;
+			mViewCellsTree->CollectLeaves(vc, leaves);
+
+			ViewCellContainer::const_iterator lit, lit_end = leaves.end();
+
+			for (lit = leaves.begin(); lit != lit_end; ++ lit)
+			{
+				BspLeaf *l = dynamic_cast<BspViewCell *>(*lit)->mLeaf;
+				exporter->ExportRays(l->mVssRays);
+			}
 		}
 
@@ -2686,8 +2782,7 @@
 	case 2: // merges
 		{
-            BspViewCell *bspVc = dynamic_cast<BspViewCell *>(vc);
-
-			importance = (float)bspVc->mLeaves.size() /
-				(float)mViewCellsStats.maxLeaves;
+            int lSize = mViewCellsTree->GetSize(vc);
+	
+			importance = (float)lSize / (float)mViewCellsStats.maxLeaves;
 		}
 		break;
@@ -2713,5 +2808,5 @@
 
 
-void VspBspViewCellsManager::ExportVcGeometry(Exporter *exporter,
+void VspBspViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
 											  ViewCell *vc) const
 {
@@ -2731,16 +2826,19 @@
 int VspBspViewCellsManager::GetMaxTreeDiff(ViewCell *vc) const
 {
-	BspViewCell *bspVc = dynamic_cast<BspViewCell *>(vc);
+	ViewCellContainer leaves;
+	mViewCellsTree->CollectLeaves(vc, leaves);
+
 
 	int maxDist = 0;
+	
 	// compute max height difference
-	for (int i = 0; i < (int)bspVc->mLeaves.size(); ++ i)
-		for (int j = 0; j < (int)bspVc->mLeaves.size(); ++ j)
-	{
-		BspLeaf *leaf = bspVc->mLeaves[i];
+	for (int i = 0; i < (int)leaves.size(); ++ i)
+		for (int j = 0; j < (int)leaves.size(); ++ j)
+	{
+		BspLeaf *leaf = dynamic_cast<BspViewCell *>(leaves[i])->mLeaf;
 
 		if (i != j)
 		{
-			BspLeaf *leaf2 = bspVc->mLeaves[j];
+			BspLeaf *leaf2 =dynamic_cast<BspViewCell *>(leaves[j])->mLeaf;
 			int dist = mVspBspTree->TreeDistance(leaf, leaf2);
 			if (dist > maxDist)
@@ -2748,4 +2846,5 @@
 		}
 	}
+
 	return maxDist;
 }
@@ -2871,13 +2970,16 @@
 	CreateMesh(vc);
 
-	vector<BspLeaf *>::const_iterator it, it_end = vc->mLeaves.end();
-
 	float area = 0;
 	float volume = 0;
 
-	for (it = vc->mLeaves.begin(); it != it_end; ++ it)
+	ViewCellContainer leaves;
+	mViewCellsTree->CollectLeaves(vc, leaves);
+
+	ViewCellContainer::const_iterator it, it_end = leaves.end();
+
+	for (it = leaves.begin(); it != it_end; ++ it)
 	{
 		BspNodeGeometry geom;
-		BspLeaf *leaf = *it;
+		BspLeaf *leaf = dynamic_cast<BspViewCell *>(*it)->mLeaf;
 		mVspBspTree->ConstructGeometry(leaf, geom);
 
@@ -2898,5 +3000,27 @@
 
 
-//////////////////////////////////77
+
+void VspBspViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays, 
+													vector<MergeCandidate> &candidates)
+{	
+	cout << "collecting merge candidates ... " << endl;
+
+	if (mUseRaysForMerge)
+	{
+		mVspBspTree->CollectMergeCandidates(rays, candidates);
+	}
+	else
+	{
+		vector<BspLeaf *> leaves;
+		mVspBspTree->CollectLeaves(leaves);
+		mVspBspTree->CollectMergeCandidates(leaves, candidates);
+	}
+
+	cout << "fininshed collecting candidates" << endl;
+}
+
+
+
+//////////////////////////////////
 ViewCellsManager *ViewCellsManagerFactory::Create(const string mName)
 {
@@ -2904,2 +3028,3 @@
 	return NULL;// new VspBspViewCellsManager();
 }
+
