Index: trunk/VUT/GtpVisibilityPreprocessor/scripts/default.env
===================================================================
--- trunk/VUT/GtpVisibilityPreprocessor/scripts/default.env	(revision 485)
+++ trunk/VUT/GtpVisibilityPreprocessor/scripts/default.env	(revision 486)
@@ -146,7 +146,7 @@
 	loadFromFile false
 	#type kdTree
-	type vspKdTree
+	#type vspKdTree
 	#type bspTree
-	#type vspBspTree
+	type vspBspTree
 	
 	#type sceneDependent
@@ -217,5 +217,5 @@
 	PostProcess {
 		maxCostRatio 0.005
-		minViewCells 200
+		minViewCells 100
 		maxPvsSize   50000
 	}
@@ -230,4 +230,5 @@
 		samples 300000
 		epsilon 0.005
+		randomize true
 	}
 
@@ -282,5 +283,5 @@
 	PostProcess {
 		maxCostRatio 0.1
-		minViewCells 200
+		minViewCells 100
 		maxPvsSize   500
 		useRaysForMerge false
Index: trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.h
===================================================================
--- trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.h	(revision 485)
+++ trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.h	(revision 486)
@@ -529,4 +529,7 @@
 	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, 
Index: trunk/VUT/GtpVisibilityPreprocessor/src/VspKdTree.cpp
===================================================================
--- trunk/VUT/GtpVisibilityPreprocessor/src/VspKdTree.cpp	(revision 485)
+++ trunk/VUT/GtpVisibilityPreprocessor/src/VspKdTree.cpp	(revision 486)
@@ -179,7 +179,7 @@
 
 
-/**************************************************************/
-/*              class VspKdLeaf implementation            */
-/**************************************************************/
+/*******************************************************************/
+/*                   class VspKdLeaf implementation                */
+/*******************************************************************/
 
 
@@ -2351,8 +2351,136 @@
 
 
-void VspKdTree::RefineViewCells()
-{
-	//TODO
-}
+int VspKdTree::RefineViewCells(const VssRayContainer &rays)
+{
+	int shuffled = 0;
+
+	Debug << "refining " << (int)mMergeQueue.size() << " candidates " << endl;
+	BspLeaf::NewMail();
+
+	// Use priority queue of remaining leaf pairs 
+	// These candidates either share the same view cells or
+	// are border leaves which share a boundary.
+	// We test if they can be shuffled, i.e.,
+	// either one leaf is made part of one view cell or the other
+	// leaf is made part of the other view cell. It is tested if the
+	// remaining view cells are "better" than the old ones.
+	while (!mMergeQueue.empty())
+	{
+		MergeCandidate mc = mMergeQueue.top();
+		mMergeQueue.pop();
+
+		// both view cells equal or already shuffled
+		if ((mc.GetLeaf1()->GetViewCell() == mc.GetLeaf2()->GetViewCell()) ||
+			(mc.GetLeaf1()->Mailed()) || (mc.GetLeaf2()->Mailed()))
+			continue;
+		
+		// candidate for shuffling
+		const bool wasShuffled = false;
+			//ShuffleLeaves(mc.GetLeaf1(), mc.GetLeaf2());
+		
+		//-- stats
+		if (wasShuffled)
+			++ shuffled;
+	}
+
+	return shuffled;
+}
+
+
+inline int AddedPvsSize(ObjectPvs pvs1, const ObjectPvs &pvs2)
+{
+	return pvs1.AddPvs(pvs2);
+}
+
+
+inline int SubtractedPvsSize(ObjectPvs pvs1, const ObjectPvs &pvs2)
+{
+	return pvs1.SubtractPvs(pvs2);
+}
+
+
+float GetShuffledVcCost(VspKdLeaf *leaf, VspKdViewCell *vc1, VspKdViewCell *vc2)
+{
+#if 0 // TODO
+	const int pvs1 = SubtractedPvsSize(vc1->GetPvs(), *leaf->mPvs);
+	const int pvs2 = AddedPvsSize(vc2->GetPvs(), *leaf->mPvs);
+
+	const float area1 = vc1->GetArea() - leaf->mArea;
+	const float area2 = vc2->GetArea() + leaf->mArea;
+
+	const float cost1 = pvs1 * area1;
+	const float cost2 = pvs2 * area2;
+
+	return cost1 + cost2;
+#else
+	return -1;
+#endif
+}
+
+
+void VspKdTree::ShuffleLeaf(VspKdLeaf *leaf, 
+							VspKdViewCell *vc1, 
+							VspKdViewCell *vc2) const
+{
+#if 0 // TODO
+	// compute new pvs and area
+	vc1->GetPvs().SubtractPvs(*leaf->mPvs);
+	vc2->GetPvs().AddPvs(*leaf->mPvs);
+	
+	vc1->SetArea(vc1->GetArea() - leaf->mArea);
+	vc2->SetArea(vc2->GetArea() + leaf->mArea);
+
+	/// add to second view cell
+	vc2->mLeaves.push_back(leaf);
+
+	// erase leaf from old view cell
+	vector<VspKdLeaf *>::iterator it = vc1->mLeaves.begin();
+
+	for (; *it != leaf; ++ it);
+	vc1->mLeaves.erase(it);
+
+	leaf->SetViewCell(vc2);  // finally change view cell
+#endif
+}
+
+
+bool VspKdTree::ShuffleLeaves(VspKdLeaf *leaf1, VspKdLeaf *leaf2) const
+{
+	VspKdViewCell *vc1 = leaf1->GetViewCell();
+	VspKdViewCell *vc2 = leaf2->GetViewCell();
+
+	const float cost1 = vc1->GetPvs().GetSize() * vc1->GetArea();
+	const float cost2 = vc2->GetPvs().GetSize() * vc2->GetArea();
+
+	const float oldCost = cost1 + cost2;
+	
+	float shuffledCost1 = Limits::Infinity;
+	float shuffledCost2 = Limits::Infinity;
+
+	// the view cell should not be empty after the shuffle
+	if (vc1->mLeaves.size() > 1)
+		shuffledCost1 = GetShuffledVcCost(leaf1, vc1, vc2);
+	if (vc2->mLeaves.size() > 1)
+		shuffledCost2 = GetShuffledVcCost(leaf2, vc2, vc1);
+
+	// shuffling unsuccessful
+	if ((oldCost <= shuffledCost1) && (oldCost <= shuffledCost2))
+		return false;
+	
+	if (shuffledCost1 < shuffledCost2)
+	{
+		ShuffleLeaf(leaf1, vc1, vc2);
+		leaf1->Mail();
+	}
+	else
+	{
+		ShuffleLeaf(leaf2, vc2, vc1);
+		leaf2->Mail();
+	}
+
+	return true;
+}
+
+
 
 
Index: trunk/VUT/GtpVisibilityPreprocessor/src/AxisAlignedBox3.h
===================================================================
--- trunk/VUT/GtpVisibilityPreprocessor/src/AxisAlignedBox3.h	(revision 482)
+++ trunk/VUT/GtpVisibilityPreprocessor/src/AxisAlignedBox3.h	(revision 486)
@@ -9,5 +9,5 @@
 class Ray;
 class Polygon3;
-
+class Mesh;
 // --------------------------------------------------------
 // CAABox class.
@@ -329,4 +329,8 @@
 						   const AxisAlignedBox3 &neighbour) const;
 
+  /** Adds the box faces to the mesh.
+  */
+  void AddBoxToMesh(Mesh *mesh) const;
+
 #define __EXTENT_HACK
   // get the extent of face
Index: trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.cpp
===================================================================
--- trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.cpp	(revision 485)
+++ trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.cpp	(revision 486)
@@ -47,5 +47,8 @@
 mOnlyDrivingAxis(false)
 {
-	Randomize(); // initialise random generator for heuristics
+	bool randomize = false;
+	environment->GetBoolValue("VspBspTree.Construction.randomize", randomize);
+	if (randomize)
+		Randomize(); // initialise random generator for heuristics
 
 	//-- termination criteria for autopartition
@@ -96,4 +99,5 @@
 	Debug << "max polygon candidates: " << mMaxPolyCandidates << endl;
 	Debug << "max plane candidates: " << mMaxRayCandidates << endl;
+	Debug << "randomize: " << randomize << endl;
 
 	Debug << "Split plane strategy: ";
@@ -1904,7 +1908,9 @@
 			// find intersection of ray segment with plane
 			extp = splitPlane.FindIntersection(origin, extp, &t);
+			//cout << "x";
 		} 
 		else
 		{
+			//cout << "o";
 			// reached leaf => intersection with view cell
 			BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
@@ -1931,5 +1937,5 @@
 		}
 	}
-
+	//cout << "!!!!!!!!!!!" << endl;
 	return hits;
 }
@@ -2428,6 +2434,4 @@
 							 BspViewCell *vc2) const
 {
-	//Debug << "old pvs: " << vc1->GetPvs().GetSize() + vc2->GetPvs().GetSize() 
-	//	  << " (" << vc1->GetPvs().GetSize() << ", " << vc2->GetPvs().GetSize() << ")" << endl;
 	// compute new pvs and area
 	vc1->GetPvs().SubtractPvs(*leaf->mPvs);
@@ -2455,5 +2459,5 @@
 	}*/
 
-	leaf->SetViewCell(vc2); 	// finally change view cell
+	leaf->SetViewCell(vc2); // finally change view cell
 	
 	//Debug << "new pvs: " << vc1->GetPvs().GetSize() + vc2->GetPvs().GetSize() 
Index: trunk/VUT/GtpVisibilityPreprocessor/src/Environment.cpp
===================================================================
--- trunk/VUT/GtpVisibilityPreprocessor/src/Environment.cpp	(revision 485)
+++ trunk/VUT/GtpVisibilityPreprocessor/src/Environment.cpp	(revision 486)
@@ -1751,5 +1751,9 @@
 		"vsp_bsp_term_post_process_use_rays_for_merge=", 
 		"false");
-	
+
+	RegisterOption("VspBspTree.Construction.randomize", 
+		optBool, 
+		"vsp_bsp_construction_randomize=", 
+		"false");
 	//////////////////////////////////////////////////////////////////////////////////
 }
Index: trunk/VUT/GtpVisibilityPreprocessor/src/Exporter.h
===================================================================
--- trunk/VUT/GtpVisibilityPreprocessor/src/Exporter.h	(revision 482)
+++ trunk/VUT/GtpVisibilityPreprocessor/src/Exporter.h	(revision 486)
@@ -22,4 +22,5 @@
 class VspBspTree;
 class RssTree;
+class Mesh;
 
 class Exporter
@@ -109,4 +110,7 @@
   ExportGeometry(const ObjectContainer &objects) = 0;
 
+  virtual void
+  ExportMesh(Mesh *mesh) = 0;
+
   virtual bool
   ExportRssTree2(const RssTree &tree,
Index: trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp
===================================================================
--- trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp	(revision 485)
+++ trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp	(revision 486)
@@ -197,4 +197,6 @@
 mGenerateViewCells(true)
 {
+	
+
 	Randomize(); // initialise random generator for heuristics
 
Index: trunk/VUT/GtpVisibilityPreprocessor/src/X3dExporter.h
===================================================================
--- trunk/VUT/GtpVisibilityPreprocessor/src/X3dExporter.h	(revision 482)
+++ trunk/VUT/GtpVisibilityPreprocessor/src/X3dExporter.h	(revision 486)
@@ -133,8 +133,4 @@
   ExportBspTreeRayDensity(const BspTree &tree);
 
-  void
-  AddBoxToMesh(const AxisAlignedBox3 &box,
-			   Mesh *mesh);
-
   void ExportBspNodeSplits(BspNode *root,
 						   const AxisAlignedBox3 &box,
Index: trunk/VUT/GtpVisibilityPreprocessor/src/X3dExporter.cpp
===================================================================
--- trunk/VUT/GtpVisibilityPreprocessor/src/X3dExporter.cpp	(revision 483)
+++ trunk/VUT/GtpVisibilityPreprocessor/src/X3dExporter.cpp	(revision 486)
@@ -678,26 +678,5 @@
 
 
-void
-X3dExporter::AddBoxToMesh(const AxisAlignedBox3 &box,
-													Mesh *mesh)
-{
-	// add 6 vertices of the box
-	int index = (int)mesh->mVertices.size();
-	
-	for (int i=0; i < 8; i++) {
-		Vector3 v;
-		box.GetVertex(i, v);
-		mesh->mVertices.push_back(v);
-	}
-	
-	mesh->AddFace(new Face(index + 0, index + 1, index + 3, index + 2) );
-	mesh->AddFace(new Face(index + 0, index + 2, index + 6, index + 4) );
-	mesh->AddFace(new Face(index + 4, index + 6, index + 7, index + 5) );
-	
-	mesh->AddFace(new Face(index + 3, index + 1, index + 5, index + 7) );
-	mesh->AddFace(new Face(index + 0, index + 4, index + 5, index + 1) );
-	mesh->AddFace(new Face(index + 2, index + 3, index + 7, index + 6) );
-
-}
+
 
 bool
@@ -726,5 +705,5 @@
 			AxisAlignedBox3 box;
 			box = tree.GetBBox(leaf);
-			AddBoxToMesh(box, mesh);
+			box.AddBoxToMesh(mesh);
 
 			if (tree.ValidLeaf(leaf)) {
@@ -829,5 +808,5 @@
 		box = tree.GetBBox(leaf);
 		Mesh *mesh = new Mesh;
-		AddBoxToMesh(box, mesh);
+		box.AddBoxToMesh(mesh);
 		
 		// get 4 corners of the ray directions
@@ -1226,5 +1205,5 @@
 		box = tree.GetShrankedBBox(leaf);
 		Mesh *mesh = new Mesh;
-		AddBoxToMesh(box, mesh);
+		box.AddBoxToMesh(mesh);
 		
 		// get 4 corners of the ray directions
Index: trunk/VUT/GtpVisibilityPreprocessor/src/VspKdTree.h
===================================================================
--- trunk/VUT/GtpVisibilityPreprocessor/src/VspKdTree.h	(revision 485)
+++ trunk/VUT/GtpVisibilityPreprocessor/src/VspKdTree.h	(revision 486)
@@ -603,7 +603,11 @@
 	*/
 	void CollectViewCells(ViewCellContainer &viewCells) const;
-	/** Refines view cells in a post processing step.
-	*/
-	void RefineViewCells();
+	
+	/** 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);
 
 	/** Collects candidates for the merge in the merge queue.
@@ -726,4 +730,15 @@
 	void RepairVcLeafLists();
 
+	/** Shuffles the leaves, i.e., tests if exchanging
+		the view cells the leaves belong to helps in improving the view cells.
+	*/
+	bool ShuffleLeaves(VspKdLeaf *leaf1, VspKdLeaf *leaf2) const;
+
+	/** Shuffles, i.e. takes border leaf from view cell 1 and adds it 
+		to view cell 2.
+	*/
+	void ShuffleLeaf(VspKdLeaf *leaf,
+					 VspKdViewCell *vc1, 
+					 VspKdViewCell *vc2) const;
 protected:
 	
Index: trunk/VUT/GtpVisibilityPreprocessor/src/AxisAlignedBox3.cpp
===================================================================
--- trunk/VUT/GtpVisibilityPreprocessor/src/AxisAlignedBox3.cpp	(revision 482)
+++ trunk/VUT/GtpVisibilityPreprocessor/src/AxisAlignedBox3.cpp	(revision 486)
@@ -7,4 +7,5 @@
 #include "Ray.h"
 #include "Polygon3.h"
+#include "Mesh.h"
 
 #define FATAL Debug
@@ -1865,2 +1866,24 @@
 }
 
+
+void AxisAlignedBox3::AddBoxToMesh(Mesh *mesh) const
+{
+	// add 6 vertices of the box
+	int index = (int)mesh->mVertices.size();
+	
+	for (int i=0; i < 8; i++) 
+	{
+		Vector3 v;
+		GetVertex(i, v);
+		mesh->mVertices.push_back(v);
+	}
+	
+	mesh->AddFace(new Face(index + 0, index + 1, index + 3, index + 2) );
+	mesh->AddFace(new Face(index + 0, index + 2, index + 6, index + 4) );
+	mesh->AddFace(new Face(index + 4, index + 6, index + 7, index + 5) );
+	
+	mesh->AddFace(new Face(index + 3, index + 1, index + 5, index + 7) );
+	mesh->AddFace(new Face(index + 0, index + 4, index + 5, index + 1) );
+	mesh->AddFace(new Face(index + 2, index + 3, index + 7, index + 6) );
+
+}
Index: trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellsManager.cpp
===================================================================
--- trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellsManager.cpp	(revision 485)
+++ trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellsManager.cpp	(revision 486)
@@ -90,7 +90,7 @@
 	int i = 0;	
 	for (it = rays.begin(); it != it_end; ++ it) 
-	{	if ((i ++) % 50000 == 0)
-			cout << "Computed 50000 samples" << endl;
+	{	Debug << "here " << i ++ << endl;
 		ComputeSampleContributions(*(*it));
+		Debug << "**" << endl;
 	}
 }
@@ -316,5 +316,5 @@
 	Ray hray(ray);
 	float tmin = 0, tmax = 1.0;
-	Debug << "here2" << endl;
+	
 	//hray.Init(ray.GetOrigin(), ray.GetDir(), Ray::LINE_SEGMENT);
 	if (!GetSceneBbox().GetRaySegment(hray, tmin, tmax) || (tmin > tmax))
@@ -344,5 +344,5 @@
 		
 		ray.mRelativePvsContribution += contribution;
-	}Debug << "here5" << endl;
+	}
 }
 
@@ -1340,5 +1340,5 @@
 	
 	// collapse siblings belonging to the same view cell
-	mVspKdTree->RefineViewCells();
+	mVspKdTree->RefineViewCells(rays);
 
 	// evaluale view cell stats
@@ -1614,6 +1614,11 @@
 	vector<VspKdLeaf *>::const_iterator it, it_end = kdVc->mLeaves.end();
 
+	Mesh m;
 	for (it = kdVc->mLeaves.begin(); it != it_end; ++ it)
-		exporter->ExportBox(mVspKdTree->GetBBox(*it));
+	{
+		mVspKdTree->GetBBox(*it).AddBoxToMesh(&m);
+	}
+
+	exporter->ExportMesh(&m);
 }
 
