Index: trunk/VUT/GtpVisibilityPreprocessor/src/SamplingPreprocessor.cpp
===================================================================
--- trunk/VUT/GtpVisibilityPreprocessor/src/SamplingPreprocessor.cpp	(revision 361)
+++ trunk/VUT/GtpVisibilityPreprocessor/src/SamplingPreprocessor.cpp	(revision 362)
@@ -32,7 +32,7 @@
 {
   ray.intersections.clear();
-  ray.leaves.clear();
+  ray.kdLeaves.clear();
   ray.meshes.clear();
-  ray.viewCells.clear();
+  ray.bspLeaves.clear();
 
   //  cout<<point<<" "<<direction<<endl;
@@ -68,6 +68,4 @@
 		mSceneGraph->CollectObjects(&objects);
 		mBspTree->Construct(objects);
-		
-		mBspTree->CollectViewCells(mViewCells);
 		break;
 	case BspTree::FROM_RAYS:
@@ -75,6 +73,4 @@
 		mBspTree->SetGenerateViewCells(true);
 		mBspTree->Construct(mSampleRays);
-		
-		mBspTree->CollectViewCells(mViewCells);
 		break;
 	default:
@@ -94,12 +90,12 @@
   int contributingSamples = 0;
   int j;
-  for (j=0; j < ray.leaves.size(); j++) {
-    KdNode *node = GetNodeForPvs( ray.leaves[j] );
+  for (j=0; j < ray.kdLeaves.size(); j++) {
+    KdNode *node = GetNodeForPvs( ray.kdLeaves[j] );
     contributingSamples += object->mKdPvs.AddSample(node);
   }
    
   if (mPass > 10)
-    for (j=1; j < ((int)ray.leaves.size() - 1); j++) {
-      ray.leaves[j]->AddPassingRay(ray, contributingSamples ? 1 : 0);
+    for (j=1; j < ((int)ray.kdLeaves.size() - 1); j++) {
+      ray.kdLeaves[j]->AddPassingRay(ray, contributingSamples ? 1 : 0);
   }
   
@@ -114,16 +110,18 @@
  
 	// object can be seen from the view cell => add to view cell pvs
-	for (j=0; j < ray.viewCells.size(); ++ j) 
+	for (j=0; j < ray.bspLeaves.size(); ++ j) 
 	{ 	// if ray not in unbounded space
-		if (ray.viewCells[j] != &mUnbounded)
-			contributingSamples += ray.viewCells[j]->GetPvs().AddSample(obj);
+		if (ray.bspLeaves[j]->GetViewCell() != &mUnbounded)
+			contributingSamples += 
+				ray.bspLeaves[j]->GetViewCell()->GetPvs().AddSample(obj);
 	}
  
 	// rays passing through this viewcell
 	if (mPass > 1)
-		for (j=1; j < ((int)ray.viewCells.size() - 1); ++ j) 
-		{
-			if (ray.viewCells[j] != &mUnbounded)
-				ray.viewCells[j]->AddPassingRay(ray, contributingSamples ? 1 : 0);
+		for (j=1; j < ((int)ray.bspLeaves.size() - 1); ++ j) 
+		{
+			if (ray.bspLeaves[j]->GetViewCell() != &mUnbounded)
+				ray.bspLeaves[j]->GetViewCell()->
+					AddPassingRay(ray, contributingSamples ? 1 : 0);
 		}
  
@@ -183,5 +181,5 @@
 	else
 		{
-			if (ray.leaves.size()) {
+			if (ray.kdLeaves.size()) {
 				if (!reverseRay)
 					sampleContributions += AddNodeSamples(object, ray);
@@ -372,8 +370,4 @@
 
   vector<Ray> rays[10];
-
-  vector<Ray> vcRays[5];
-  ViewCellContainer pvsViewCells;
-  vector<Ray> viewCellRays; // used for BSP tree construction
 
   while (totalSamples < mTotalSamples) {
@@ -462,55 +456,13 @@
 					}
 					//-------------------
-
 					if (mViewCellsType == BSP_VIEW_CELLS) 
 					{
-						// save rays for bsp tree construction
-						if (collectSamplesForBsp)
-						{
-							// also add origin to sample in order to extract it as input polygons
-							MeshInstance *mi = dynamic_cast<MeshInstance *>(object);
-							ray.sourceObject = Ray::Intersection(0.0, mi, faceIndex);
-							
-                            mSampleRays.push_back(new Ray(ray));
-						}
-						else
-						{
-							// construct BSP tree using the samples
-							if (!mBspTree)
-							{
-								BuildBspTree();
-
-								cout << "generated " << (int)mViewCells.size() << " view cells" << endl;
-
-								passContributingSamples += mBspTree->GetStat().contributingSamples;
-								passSampleContributions += mBspTree->GetStat().sampleContributions;
-
-								BspTreeStatistics(Debug);	
-								Export("vc_bsptree.x3d", false, false, true);
-							}
-								
-							// some random view cells for output
-							if (pvsViewCells.empty())
-							{
-								int vcPvsOut = Min((int)mViewCells.size(), 5);
-							
-								for (int j = 0; j < vcPvsOut; ++ j)
-								{
-									int idx = Random((int)mViewCells.size());
-									Debug << "output view cell=" << idx << endl;
-									pvsViewCells.push_back(mViewCells[Random((int)mViewCells.size())]);
-								}
-							}
-							else
-							{	
-								// check whether we can add the current ray to the rays
-								for (int k = 0; k < (int)ray.viewCells.size(); ++ k)
-									for (int j = 0; j < (int)pvsViewCells.size(); ++ j) 
-										if (pvsViewCells[j] == ray.viewCells[k]) 
-											vcRays[j].push_back(ray);							
-							}
-						}
+						ProcessBspViewCells(collectSamplesForBsp,
+											ray,
+											object,
+											faceIndex,
+											passContributingSamples,
+											passSampleContributions);
 					}
-		
 				}
 			} else {
@@ -580,155 +532,63 @@
 		cout << "#totalPvsSize=" << mKdTree->CollectLeafPvs() << endl;
   
+	// merge or subdivide view cells
+	if (mBspTree)
+	{
+		int merged = PostprocessViewCells(mSampleRays);
+		Debug << "merged " << merged << " view cells" << endl;
+
+		ViewCellContainer vc;
+		mBspTree->CollectViewCells(vc);
+
+		ViewCellContainer::const_iterator it, it_end = vc.end();
+
+		int mergedPvs = 0;
+		for (it = vc.begin(); it != it_end; ++ it)
+			mergedPvs += (*it)->GetPvs().GetSize();
+
+		Debug << "merged pvs size: " << mergedPvs << endl;
+
+	}
+	
   //  HoleSamplingPass();
-  if (0) {
-    Exporter *exporter = Exporter::GetExporter("ray-density.x3d");
-    exporter->SetExportRayDensity(true);
-    exporter->ExportKdTree(*mKdTree);
-
+	if (0) {
+		Exporter *exporter = Exporter::GetExporter("ray-density.x3d"); 
+		exporter->SetExportRayDensity(true);
+		exporter->ExportKdTree(*mKdTree);
+
+		if (mBspTree && (mViewCellsType == BSP_VIEW_CELLS))
+			exporter->ExportBspTree(*mBspTree);
+
+		delete exporter;
+	}
+  
+	bool exportRays = false;
+	if (exportRays) {
+		Exporter *exporter = NULL;
+		exporter = Exporter::GetExporter("sample-rays.x3d");
+		exporter->SetWireframe();
+		exporter->ExportKdTree(*mKdTree);
+		exporter->ExportBspTree(*mBspTree);
+
+		for (i=0; i < pvsOut; i++) 
+		exporter->ExportRays(rays[i], 1000, RgbColor(1, 0, 0));
+		exporter->SetFilled();
+		  
+		delete exporter;
+	}
+
+	//-- several visualizations and statistics
+	if (1) {
 	if (mBspTree && (mViewCellsType == BSP_VIEW_CELLS))
-		exporter->ExportBspTree(*mBspTree);
-
-    delete exporter;
-  }
-  
-  bool exportRays = false;
-  if (exportRays) {
-    Exporter *exporter = NULL;
-    exporter = Exporter::GetExporter("sample-rays.x3d");
-    exporter->SetWireframe();
-    exporter->ExportKdTree(*mKdTree);
-	exporter->ExportBspTree(*mBspTree);
-
-    for (i=0; i < pvsOut; i++) 
-      exporter->ExportRays(rays[i], 1000, RgbColor(1, 0, 0));
-    exporter->SetFilled();
-	  
-    delete exporter;
-  }
-
-  //-- several visualizations and statistics
-  if (1) {
-  if (mBspTree && (mViewCellsType == BSP_VIEW_CELLS))
-  {
-	  bool exportSplits = false;
-	  environment->GetBoolValue("BspTree.exportSplits", exportSplits);
-
-	  // export the bsp splits
-	  if (exportSplits)
-	  	  ExportSplits(objects);
-	
-	  Exporter *exporter = Exporter::GetExporter("viewCells.x3d");
-
-	  // export leaves
-	  if (0 && exporter)
-	  {
-		  vector<BspLeaf *> leaves;
-		  mBspTree->CollectLeaves(leaves);
-		  vector<BspLeaf *> randLeaves;
-		  vector<BspLeaf *> neighbors;
-
-		  for (int k = 0; k < 1; ++ k) 
-		  {
-			  BspLeaf *leaf = leaves[Random((int)leaves.size())];
-			  randLeaves.push_back(leaf);
-			  mBspTree->FindNeighbors(leaf, neighbors, false);
-		  }	
-
-		  exporter->ExportLeavesGeometry(*mBspTree, randLeaves);
-		  exporter->SetWireframe();
-          exporter->ExportLeavesGeometry(*mBspTree, neighbors);	
-			
-          delete exporter;
-	  }
-
-	   vector<BspLeaf *> leaves;
-	   mBspTree->CollectLeaves(leaves);
-	   
-	   for (int k = 0; k < 100; ++ k) 
-	   {
-		   vector<BspLeaf *> randLeaves;
-		   vector<BspLeaf *> neighbors;
-		   
-		   char s[64]; sprintf(s, "bsp-vc%04d.x3d", k);
-		   Exporter *exporter = Exporter::GetExporter(s);
-
-		   BspLeaf *leaf = leaves[Random((int)leaves.size())];
-		   Debug << "\noutput leaf " << k << endl;
-		   randLeaves.push_back(leaf);
-		   mBspTree->FindNeighbors(leaf, neighbors, false);
-
-		   exporter->ExportLeavesGeometry(*mBspTree, randLeaves);
-		   exporter->SetWireframe();
-		   exporter->ExportLeavesGeometry(*mBspTree, neighbors);	
-			
-		   delete exporter;
-	   }	
-
-	  for (int j = 0; j < pvsViewCells.size(); ++ j)
-	  {
-		  ViewCell *vc = pvsViewCells[j];
-
-		  Intersectable::NewMail();
-		  char s[64]; sprintf(s, "bsp-pvs%04d.x3d", j);
-
-		  Exporter *exporter = Exporter::GetExporter(s);
-		  exporter->SetFilled();
-
-		  ViewCellPvsMap::iterator it = vc->GetPvs().mEntries.begin();
-
-		  Material m;//= RandomMaterial();
-		  m.mDiffuseColor = RgbColor(0, 1, 0);
-		  exporter->SetForcedMaterial(m);
-
-		  exporter->ExportViewCell(vc);
-
-		  Debug << j << ": pvs size=" << (int)vc->GetPvs().GetSize() 
-			    << ", piercing rays=" << (int)vcRays[j].size() << endl;
-
-		  exporter->SetWireframe();
-
-		  // export view cells
-		  m.mDiffuseColor = RgbColor(1, 0, 1);
-		  exporter->SetForcedMaterial(m);
-		  exporter->ExportViewCells(mViewCells);
-			
-		  // export rays piercing this view cell
-		  exporter->ExportRays(vcRays[j], 1000, RgbColor(0, 1, 0));
-
-		  m.mDiffuseColor = RgbColor(1, 0, 0);
-		  exporter->SetForcedMaterial(m);
-
-		  // output PVS of view cell
-		  for (; it != vc->GetPvs().mEntries.end(); ++ it) 
-		  {
-			  Intersectable *intersect = (*it).first;
-			  if (!intersect->Mailed())
-			  {
-				  exporter->ExportIntersectable(intersect);
-				  intersect->Mail();
-			  }			
-		  }
-		
-		  // output rest of the objects
-		  if (0)
-		  {
-			  Material m;//= RandomMaterial();
-			  m.mDiffuseColor = RgbColor(0, 0, 1);
-			  exporter->SetForcedMaterial(m);
-
-			  for (int j = 0; j < objects.size(); ++ j)
-				  if (!objects[j]->Mailed())
-				  {
-					  //if (j == 2198)m.mDiffuseColor = RgbColor(1, 0, 1);
-					  //else m.mDiffuseColor = RgbColor(1, 1, 0);
-					  exporter->SetForcedMaterial(m);
-					  exporter->ExportIntersectable(objects[j]);
-					  objects[j]->Mail();
-				  }
-		  }
-		  DEL_PTR(exporter);
-		}
-  }  
-
+	{
+		bool exportSplits = false;
+		environment->GetBoolValue("BspTree.exportSplits", exportSplits);
+
+		// export the bsp splits
+		if (exportSplits)
+	  		ExportSplits(objects);
+		
+		ExportBspPvs(objects);
+	}
    for (int k=0; k < pvsOut; k++) {
       Intersectable *object = objects[k];
@@ -772,4 +632,67 @@
 }
 
+bool SamplingPreprocessor::ProcessBspViewCells(bool collectSamplesForBsp,
+											   Ray &ray,
+											   Intersectable *object,
+											   int faceIndex,
+											   int &contributingSamples,
+											   int &sampleContributions)
+{
+	// save rays for bsp tree construction
+	if (collectSamplesForBsp)
+	{
+		// also add origin to sample in order to extract it as input polygons
+		MeshInstance *mi = dynamic_cast<MeshInstance *>(object);
+		ray.sourceObject = Ray::Intersection(0.0, mi, faceIndex);
+							
+        mSampleRays.push_back(new Ray(ray));
+		
+		return false;
+	}
+	
+	// construct BSP tree using the samples
+	if (!mBspTree)
+	{
+		BuildBspTree();
+		
+		contributingSamples += mBspTree->GetStat().contributingSamples;
+		sampleContributions += mBspTree->GetStat().sampleContributions;
+
+		BspTreeStatistics(Debug);	
+		if (0) Export("vc_bsptree.x3d", false, false, true);
+	}
+
+	return true;
+}
+
+// merge or subdivide view cells
+int SamplingPreprocessor::PostprocessViewCells(const RayContainer &rays)
+{
+	int merged = 0;
+	RayContainer::const_iterator rit, rit_end = rays.end();
+	vector<BspLeaf *>::const_iterator lit;
+if (0)
+	for (rit = rays.begin(); rit != rays.end(); ++ rit)
+	{  
+		// traverse leaves stored in the rays and compare and merge consecutive
+		// leaves (i.e., the neighbors in the tree)
+		lit = (*rit)->bspLeaves.begin();
+
+		BspLeaf *previousLeaf = *lit;
+		++ lit;
+		
+		for (; lit != (*rit)->bspLeaves.end(); ++ lit)
+		{
+			BspLeaf *leaf = *lit;
+			if (mBspTree->ShouldMerge(leaf, previousLeaf))
+			{			
+				mBspTree->MergeViewCells(leaf, previousLeaf);
+				++ merged;
+			}
+			previousLeaf = leaf;
+		}
+	}
+	return merged;
+}
 
 void SamplingPreprocessor::ExportSplits(const ObjectContainer &objects)
@@ -829,2 +752,120 @@
 	}
 }
+
+void SamplingPreprocessor::ExportBspPvs(const ObjectContainer &objects)
+{
+	//-- some random view cells and rays for output
+	const int leafOut = 10;
+
+	vector<Ray> vcRays[leafOut];
+	vector<BspLeaf *> bspLeaves;
+			
+	for (int i = 0; i < leafOut; ++ i)
+		bspLeaves.push_back(mBspTree->GetRandomLeaf());
+	
+	const int raysOut = min((int)mSampleRays.size(), 20000);
+
+	// check whether we can add the current ray to the output rays
+	for (int k = 0; k < raysOut; ++ k) 
+	{
+		Ray *ray = mSampleRays[k];
+
+		for (int j = 0; j < (int)ray->bspLeaves.size(); ++ j)
+		{
+			for (int i = 0; i < (int)bspLeaves.size(); ++ i)
+			{
+				if (bspLeaves[i] == ray->bspLeaves[j]) 
+				{
+					vcRays[i].push_back(*ray);
+				}
+			}
+		}
+	}
+
+	ViewCell::NewMail();
+
+	for (int i = 0; i < bspLeaves.size(); ++ i)
+	{
+		Intersectable::NewMail();
+
+		ViewCell *vc = bspLeaves[i]->GetViewCell();
+
+		//bspLeaves[j]->Mail();
+		char s[64]; sprintf(s, "bsp-pvs%04d.x3d", i);
+
+		Exporter *exporter = Exporter::GetExporter(s);
+		exporter->SetFilled();
+
+		ViewCellPvsMap::iterator it = vc->GetPvs().mEntries.begin();
+
+		Material m;//= RandomMaterial();
+		m.mDiffuseColor = RgbColor(0, 1, 0);
+		exporter->SetForcedMaterial(m);
+
+		exporter->SetWireframe();
+
+		if (vc->GetMesh())
+			exporter->ExportViewCell(vc);
+		else
+		{
+            PolygonContainer cell;
+
+			mBspTree->ConstructGeometry(bspLeaves[i], cell);
+			exporter->ExportPolygons(cell);
+			CLEAR_CONTAINER(cell);
+
+			/*vector<BspLeaf *> neighbors;
+			mBspTree->FindNeighbors(bspLeaves[j], neighbors);
+			for (int j = 0; j < (int)neighbors.size(); ++ j)
+			{	if (neighbors[j]->mViewCell == bspLeaves[j]->mViewCell)
+				{}}*/
+		}
+
+		Debug << i << ": pvs size=" << (int)vc->GetPvs().GetSize() 
+				<< ", piercing rays=" << (int)vcRays[i].size() << endl;
+
+		// export view cells
+		if (0)
+		{
+			m.mDiffuseColor = RgbColor(1, 0, 1);
+			exporter->SetForcedMaterial(m);
+			exporter->ExportViewCells(mViewCells);
+		}
+
+		// export rays piercing this view cell
+		exporter->ExportRays(vcRays[i], 1000, RgbColor(0, 1, 0));
+
+		m.mDiffuseColor = RgbColor(1, 0, 0);
+		exporter->SetForcedMaterial(m);
+
+		// output PVS of view cell
+		for (; it != vc->GetPvs().mEntries.end(); ++ it) 
+		{
+			Intersectable *intersect = (*it).first;
+			if (!intersect->Mailed())
+			{
+				exporter->ExportIntersectable(intersect);
+				intersect->Mail();
+			}			
+		}
+			
+		// output rest of the objects
+		if (0)
+		{
+			Material m;//= RandomMaterial();
+			m.mDiffuseColor = RgbColor(0, 0, 1);
+			exporter->SetForcedMaterial(m);
+
+			for (int j = 0; j < objects.size(); ++ j)
+				if (!objects[j]->Mailed())
+				{
+					//if (j == 2198)m.mDiffuseColor = RgbColor(1, 0, 1);
+					//else m.mDiffuseColor = RgbColor(1, 1, 0);
+					exporter->SetForcedMaterial(m);
+					exporter->ExportIntersectable(objects[j]);
+					objects[j]->Mail();
+				}
+		}
+		DEL_PTR(exporter);
+	}
+}
