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();
 }
+
