Changeset 564

Timestamp:

01/23/06 02:56:48 (18 years ago)

Author:

mattausch

Message:

 

Location:

trunk/VUT/GtpVisibilityPreprocessor

Files:

• scripts/default.env (modified) (6 diffs)
• src/Environment.cpp (modified) (2 diffs)
• src/Ray.cpp (modified) (1 diff)
• src/RenderSimulator.cpp (modified) (4 diffs)
• src/RenderSimulator.h (modified) (2 diffs)
• src/ViewCell.cpp (modified) (3 diffs)
• src/ViewCell.h (modified) (2 diffs)
• src/ViewCellsManager.cpp (modified) (32 diffs)
• src/ViewCellsManager.h (modified) (2 diffs)
• src/VspBspTree.cpp (modified) (30 diffs)
• src/VspBspTree.h (modified) (6 diffs)
• src/VssPreprocessor.cpp (modified) (2 diffs)
• src/X3dExporter.cpp (modified) (1 diff)

trunk/VUT/GtpVisibilityPreprocessor/scripts/default.env

@@ -30 +30 @@
 VssPreprocessor {
         samplesPerPass  100000
-        initialSamples 1800000
+        initialSamples 1200000
         vssSamples 0
         vssSamplesPerPass 500000
@@ -172 +172 @@
 ViewCells {
         loadFromFile false
-        exportToFile true
+        exportToFile false
         #type kdTree
         #type vspKdTree
@@ -186 +186 @@
                 
         delayedConstruction false
-                
-                
+        pruneEmptyViewCells false
+        processOnlyValidViewCells false
+        
         PostProcess {
                 # how much samples are used for post processing
@@ -304 +305 @@
                 #maxAccRayLength        100
                 
-                maxViewCells            1000
+                maxViewCells            10000
                 
                 # used for pvs criterium
@@ -320 +321 @@
                 # x3d visualization of the split planes
                 exportSplits true
+                exportMergedViewCells false
         }
         
@@ -326 +328 @@
                 minViewCells 110
                 useRaysForMerge false
+                exportMergeStats false
         }
 }

trunk/VUT/GtpVisibilityPreprocessor/src/Environment.cpp

@@ -1266 +1266 @@
                 "false");
 
-
+        RegisterOption("ViewCells.pruneEmptyViewCells",
+                optBool,
+                "-view_cells_prune_empty_view_cells",
+                "false");
+
+        RegisterOption("ViewCells.processOnlyValidViewCells",
+                optBool,
+                "-view_cells_process_only_valid_view_cells",
+                "false");
+        
         /************************************************************************************/
         /*                         Render simulation related options                        */
@@ -1848 +1857 @@
                 "vsp_bsp_max_static_mem=", 
                 "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");
+
         //////////////////////////////////////////////////////////////////////////////////
 }

trunk/VUT/GtpVisibilityPreprocessor/src/Ray.cpp

@@ -234 +234 @@
   dir = vssRay.GetDir() / len;
   
+  intersections.clear();
   if (vssRay.mTerminationObject)
         intersections.push_back(Intersection(len, vssRay.mTerminationObject, 0));

trunk/VUT/GtpVisibilityPreprocessor/src/RenderSimulator.cpp

@@ -28 +28 @@
 
 RenderSimulator::RenderSimulator(ViewCellsManager *viewCellsManager):
-Renderer(NULL, viewCellsManager)
+Renderer(NULL, viewCellsManager),
+mObjRenderCost(0.0f), 
+mVcOverhead(0.0f), 
+mMoveSpeed(0.0f),
+mOnlyValid(false)
 {}
+
 
 RenderSimulator::RenderSimulator(ViewCellsManager *viewCellsManager,
@@ -38 +43 @@
 mObjRenderCost(objRenderCost), 
 mVcOverhead(vcOverhead), 
-mMoveSpeed(moveSpeed)
+mMoveSpeed(moveSpeed),
+mOnlyValid(false)
 {
 }
+
 
 void RenderSimulator::SetObjectRenderCost(const float objRenderCost)
@@ -46 +53 @@
         mObjRenderCost = objRenderCost;
 }
+
+
+void RenderSimulator::SetRenderOnlyValid(const bool renderOnlyValid)
+{
+        mOnlyValid = renderOnlyValid;
+}
+
 
 void RenderSimulator::SetVcOverhead(const float vcOverhead)
@@ -74 +88 @@
         {
                 ViewCell *vc = *it;
+
+                if (mOnlyValid && !vc->GetValid())
+                        continue;
 
                 // probability of view cell

trunk/VUT/GtpVisibilityPreprocessor/src/RenderSimulator.h

@@ -78 +78 @@
         bool RenderScene();
 
+        /** If only valid view space should be rendered.
+        */
+        void SetRenderOnlyValid(const bool onlyValid);
+
 protected:
 
@@ -95 +99 @@
         /// Simulation statistics
         SimulationStatistics mSimulationStatistics;
+
+        /// if only valid view space should be rendered
+        bool mOnlyValid;
 };
 

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCell.cpp

@@ -83 +83 @@
         if (pvsSize < vcStat.minPvs)
                 vcStat.minPvs = pvsSize;
+
+        if (!mValid)
+                ++ vcStat.invalid;
 }
 
@@ -100 +103 @@
 void ViewCell::SetValid(const bool valid)
 {
-        mValid = true;
+        mValid = valid;
 }
 
@@ -138 +141 @@
         app << "#N_MAXLEAVES ( maximal number of leaves per view cell )\n" << maxLeaves << endl;
         
+        app << "#N_INVALID ( number of invalid view cells )\n" << invalid << endl;
+
         app << "========== End of View Cells Statistics ==========\n";
 }

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCell.h

@@ -45 +45 @@
         int maxLeaves;
 
+        int invalid;
+
     // Constructor
         ViewCellsStatistics()
@@ -64 +66 @@
                 leaves = 0;
                 maxLeaves = 0;
+                invalid = 0;
         }
 

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellsManager.cpp

@@ -27 +27 @@
 mViewCellsFinished(false),
 mMaxPvsSize(9999999),
-mMinPvsSize(1), // only empty view cells are invalid
+mMinPvsSize(0), // one means only empty view cells are invalid
 mMaxPvsRatio(1.0)
 {
@@ -44 +44 @@
 mViewCellsFinished(false),
 mMaxPvsSize(9999999),
-mMinPvsSize(1), // only empty view cells are invalid
+mMinPvsSize(0), // one means only empty view cells are invalid
 mMaxPvsRatio(1.0)
 {
@@ -58 +58 @@
         environment->GetBoolValue("ViewCells.Visualization.exportGeometry", mExportGeometry);
         environment->GetFloatValue("ViewCells.maxPvsRatio", mMaxPvsRatio);
+        bool emptyViewCells = false;
+        environment->GetBoolValue("ViewCells.pruneEmptyViewCells", emptyViewCells);
+        environment->GetBoolValue("ViewCells.processOnlyValidViewCells", mOnlyValidViewCells);
+
+        mMinPvsSize = emptyViewCells ? 1 : 0;
 
         char buf[50];
-
         environment->GetStringValue("ViewCells.Visualization.colorCode", buf);
 
@@ -91 +95 @@
         preprocessor->GenerateVssRays(mConstructionSamples, vssRays);
         Construct(preprocessor->mObjects, vssRays);
-        
+
         // add rays to output rays
         while (!vssRays.empty)
@@ -116 +120 @@
 
 
-bool ViewCellsManager::CheckValidity(ViewCell *vc, 
-                                                                         int minPvsSize, 
+bool ViewCellsManager::CheckValidity(ViewCell *vc,
+                                                                         int minPvsSize,
                                                                          int maxPvsSize) const
 {
         if ((vc->GetPvs().GetSize() > mMaxPvsSize) ||
                 (vc->GetPvs().GetSize() < mMinPvsSize))
-        {       
+        {
                 return false;
         }
@@ -130 +134 @@
 
 
-void ViewCellsManager::SetValidity(ViewCell *vc, 
-                                                                   int minPvs, 
+void ViewCellsManager::SetValidity(ViewCell *vc,
+                                                                   int minPvs,
                                                                    int maxPvs) const
 {
@@ -179 +183 @@
   if (!ViewCellsConstructed())
         return 0.0f;
-  
+
   VssRayContainer::const_iterator it, it_end = rays.end();
 
@@ -309 +313 @@
 
         //-- merge ray sets
-        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(),
-                           vc->mPiercingRays.begin());
+        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(),
+                                   vc->mPiercingRays.begin());
+        }
 
         return vc;
@@ -429 +436 @@
 {
         mViewCells.clear();
-        
+
         CollectViewCells();
-        
+
         mViewCellsStats.Reset();
         EvaluateViewCellsStats();
@@ -449 +456 @@
   if (!ViewCellsConstructed())
         return;
-  
+
   VssRayContainer::const_iterator it, it_end = rays.end();
-  
+
   for (it = rays.begin(); it != it_end; ++ it) {
         AddSampleContributions(*(*it));
@@ -489 +496 @@
 {
   ViewCellContainer viewcells;
-  
+
   ray.mPvsContribution = 0;
   ray.mRelativePvsContribution = 0.0f;
-  
-  // matt TODO: remove this!!
-  Ray hray(ray);
-  float tmin = 0, tmax = 1.0;
-  
-  //hray.Init(ray.GetOrigin(), ray.GetDir(), Ray::LINE_SEGMENT);
-  if (!GetViewSpaceBox().GetRaySegment(hray, tmin, tmax) || (tmin > tmax))
-        return 0.0f;
-  
-  Vector3 origin = hray.Extrap(tmin);
-  Vector3 termination = hray.Extrap(tmax);
+
+ static Ray hray;
+        hray.Init(ray);
+        //hray.mFlags |= Ray::CULL_BACKFACES;
+        //Ray hray(ray);
+
+        float tmin = 0, tmax = 1.0;
+
+        if (!GetViewSpaceBox().GetRaySegment(hray, tmin, tmax) || (tmin > tmax))
+                return;
+
+        Vector3 origin = hray.Extrap(tmin);
+        Vector3 termination = hray.Extrap(tmax);
+
+        CastLineSegment(origin, termination, viewcells);
+        //Debug << "constribution: " << (int)viewcells.size() << endl;
+        // copy viewcells memory efficiently
+        const bool storeViewcells = false;
+        if (storeViewcells)
 
   CastLineSegment(origin,
                                   termination,
                                   viewcells);
-  
+
   //Debug << "constribution: " << (int)viewcells.size() << endl;
-  
+
   // copy viewcells memory efficiently
   const bool storeViewcells = !addRays;
-  
+
   if (storeViewcells)
-        {
+  {
           ray.mViewCells.reserve(viewcells.size());
           ray.mViewCells = viewcells;
-        }
-  
+          }
+
   ViewCellContainer::const_iterator it = viewcells.begin();
-  
-  
+
+
   for (; it != viewcells.end(); ++it) {
         ViewCell *viewcell = *it;
@@ -533 +548 @@
         ray.mRelativePvsContribution += contribution;
   }
-  
+
   if (addRays)
         for (it = viewcells.begin(); it != viewcells.end(); ++it) {
@@ -623 +638 @@
 
 
-bool ViewCellsManager::ExportViewCells(const string filename) 
-{ 
+bool ViewCellsManager::ExportViewCells(const string filename)
+{
         return false;
 }
@@ -1847 +1862 @@
 void VspBspViewCellsManager::CollectViewCells()
 {
-        mVspBspTree->CollectViewCells(mViewCells, false);
+        mVspBspTree->CollectViewCells(mViewCells, mOnlyValidViewCells);
 }
 
@@ -1894 +1909 @@
 
         mMaxPvsSize = (int)(mMaxPvsRatio * (float)objects.size());
-        
+
         mVspBspTree->Construct(constructionRays, &mViewSpaceBox);
 
@@ -1996 +2011 @@
                 if (exporter)
                 {
-                        if (1)
+                        if (0)
                                 exporter->SetWireframe();
                         else
@@ -2019 +2034 @@
 
 
-void VspBspViewCellsManager::RefineViewCells(const VssRayContainer &rays)
+void VspBspViewCellsManager::RefineViewCells(const VssRayContainer &rays,
+                                                                                         const ObjectContainer &objects)
 {
         Debug << "render time before refine:" << endl;
@@ -2031 +2047 @@
 
         // refining the merged view cells
-        const int refined = mVspBspTree->RefineViewCells(rays);
+        const int refined = mVspBspTree->RefineViewCells(rays, objects);
 
         //-- stats and visualizations
@@ -2052 +2068 @@
         }
 
-        
+
         // view cells already finished before post processing step (i.e. because they were loaded)
         if (mViewCellsFinished)
@@ -2060 +2076 @@
                 return 0;
         }
-        
+
 
         // check if new view cells turned invalid
@@ -2071 +2087 @@
 
         Debug << "post processing using " << (int)postProcessRays.size() << " samples" << endl;
-        
+
         Debug << "\nview cell partition after sampling:\n" << mViewCellsStats << endl << endl;
 
@@ -2084 +2100 @@
         MergeViewCells(postProcessRays, objects);
         //-- refines the merged view cells
-        RefineViewCells(postProcessRays);
+        RefineViewCells(postProcessRays, objects);
         // collapse sibling leaves that share the same view cell
         mVspBspTree->CollapseTree();
@@ -2174 +2190 @@
                                 exporter->ExportRays(visRays, RgbColor(0, 1, 0));
                         }
-                        
+
                         ExportViewCellsForViz(exporter);
                         delete exporter;
@@ -2211 +2227 @@
 
                                 lm = vm;
-                                        
+
                                 vm.mDiffuseColor.r -= 0.45f;
                                 vm.mDiffuseColor.g -= 0.45f;
@@ -2226 +2242 @@
                                         else
                                                 exporter->SetForcedMaterial(vm);
-                                        
+
                                         BspNodeGeometry geom;
                                         mVspBspTree->ConstructGeometry(leaf, geom);
@@ -2232 +2248 @@
                                 }
                         }
-                        
+
                         delete exporter;
                 }
@@ -2410 +2426 @@
                                                                                  ViewCell *vc) const
 {
-        if (CheckValidity(vc, mMinPvsSize, mMaxPvsSize) && (mColorCode == 0)) // Random color
+        const bool vcValid = CheckValidity(vc, mMinPvsSize, mMaxPvsSize);
+
+        float importance = 0;
+        static Material m;
+
+        switch (mColorCode)
+        {
+        case 0: // Random
+                {
+                        if (vcValid)
+                        {
+                                m = RandomMaterial();
+                        }
+                        else
+                        {
+                                m.mDiffuseColor.r = 0.0f;
+                                m.mDiffuseColor.g = 1.0f;
+                                m.mDiffuseColor.b = 0.0f;
+                        }
+                }
                 return;
-
-        float importance = 0;
-        Material m;
-        
-        switch (mColorCode)
-        {
         case 1: // pvs
                 {
@@ -2443 +2472 @@
         }
 
-        m.mDiffuseColor.b = CheckValidity(vc, mMinPvsSize, mMaxPvsSize) ? 1.0f : 0.0f;
+        // special color code for invalid view cells
         m.mDiffuseColor.r = importance;
         m.mDiffuseColor.g = 1.0f - m.mDiffuseColor.r;
+        m.mDiffuseColor.b = vcValid ? 1.0f : 0.0f;
 
         //Debug << "importance: " << importance << endl;
@@ -2515 +2545 @@
 {
         ViewCellsParser parser;
-        
+
         DEL_PTR(mVspBspTree);
         mVspBspTree = new VspBspTree();
-        
+
         bool success = parser.ParseFile(filename, mVspBspTree, this, objects);
         mVspBspTree->RepairViewCellsLeafLists();
         mVspBspTree->mBox = GetViewSpaceBox();
         ResetViewCells();
-        
+
         mViewCellsFinished = true;
         mMaxPvsSize = (int)objects->size();
 
         FinalizeViewCells(true);
-        
+
         Debug << (int)mViewCells.size() << " view cells loaded" << endl;
 
@@ -2543 +2573 @@
 bool VspBspViewCellsManager::ExportViewCells(const string filename)
 {
-        cout << "exporting view cells to xml ... "; 
+        cout << "exporting view cells to xml ... ";
         std::ofstream stream;
 
@@ -2552 +2582 @@
         stream << "<?xml version=\"1.0\" encoding=\"UTF-8\"?>"<<endl;
         stream << "<Visibility_Solution>" << endl;
-        
+
         //-- load the view cells itself, i.e., the ids and the pvs
         stream << "<ViewCells>" << endl;
@@ -2558 +2588 @@
         for (it = mViewCells.begin(); it != it_end; ++ it)
                 ExportViewCell(*it, stream);
-    
+
         stream << "</ViewCells>" << endl;
-        
+
         //-- load the hierarchy
         stream << "<BspTree>" << endl;
         mVspBspTree->Export(stream);
         stream << endl << "</BspTree>" << endl;
-        
+
         stream << "</Visibility_Solution>" << endl;
         stream.close();

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellsManager.h

@@ -363 +363 @@
         bool mExportViewCells;
 
+        bool mOnlyValidViewCells;
 
         //-- visualization options
@@ -625 +626 @@
                                                 const ObjectContainer &objects);
         
-        void RefineViewCells(const VssRayContainer &rays);
+        void RefineViewCells(const VssRayContainer &rays, const ObjectContainer &objects);
 
         void CollectViewCells();

trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.cpp

@@ -30 +30 @@
 
 int BspMergeCandidate::sMaxPvsSize = 0;
+//int BspMergeCandidate::sMinPvsSize = 0;
 
 int VspBspTree::sFrontId = 0;
@@ -66 +67 @@
         environment->GetFloatValue("VspBspTree.Termination.maxCostRatio", mTermMaxCostRatio);
         environment->GetIntValue("VspBspTree.Termination.missTolerance", mTermMissTolerance);
+        environment->GetIntValue("VspBspTree.Termination.maxViewCells", mMaxViewCells);
+        //-- max cost ratio for early tree termination
+        environment->GetFloatValue("VspBspTree.Termination.maxCostRatio", mTermMaxCostRatio);
 
         //-- factors for bsp tree split plane heuristics
@@ -72 +76 @@
         environment->GetFloatValue("VspBspTree.Termination.ct_div_ci", mCtDivCi);
 
-        //-- max cost ratio for early tree termination
-        environment->GetFloatValue("VspBspTree.Termination.maxCostRatio", mTermMaxCostRatio);
 
         //-- partition criteria
@@ -83 +85 @@
         environment->GetIntValue("VspBspTree.maxTests", mMaxTests);
 
-        // maximum and minimum number of view cells
-        environment->GetIntValue("VspBspTree.Termination.maxViewCells", mMaxViewCells);
-
+        // if only the driving axis is used for axis aligned split
         environment->GetBoolValue("VspBspTree.splitUseOnlyDrivingAxis", mOnlyDrivingAxis);
 
@@ -103 +103 @@
         environment->GetFloatValue("VspBspTree.maxStaticMemory", mMaxMemory);
 
-        
+        environment->GetBoolValue("VspBspTree.Visualization.exportMergedViewCells", mExportMergedViewCells);
+        environment->GetBoolValue("VspBspTree.PostProcess.exportMergeStats", mExportMergeStats);
+        
+
         mStats.open("bspStats.log");
 
@@ -123 +126 @@
         Debug << "using area for pvs: " << mUseAreaForPvs << endl;
         Debug << "Split plane strategy: ";
+
         if (mSplitPlaneStrategy & RANDOM_POLYGON)
         {
@@ -329 +333 @@
                 float minT, maxT;
 
-                //static Ray hray;
-                //hray.Init(ray.GetOrigin(), ray.GetDir(), Ray::LINE_SEGMENT);
+                static Ray hray;
+                hray.Init(*ray);
 
                 // TODO: not very efficient to implictly cast between rays types
-                if (mBox.GetRaySegment(*ray, minT, maxT))
+                if (mBox.GetRaySegment(hray, minT, maxT))
                 {
                         float len = ray->Length();
@@ -515 +519 @@
                                 leaf->mVssRays.push_back((*it).mRay);
                 }
-                
+                // should I check here?
                 if (0 && !mViewCellsManager->CheckValidity(viewCell, 0, mViewCellsManager->GetMaxPvsSize()))
                 {
@@ -1726 +1730 @@
                 if (node->IsLeaf())
                 {
-                        if (!onlyValid ||node->TreeValid())
+                        if (!onlyValid || node->TreeValid())
                         {
                                 ViewCell *viewCell = dynamic_cast<BspLeaf *>(node)->GetViewCell();
@@ -2572 +2576 @@
 
         // clean up old view cells
-        if (0)
+        if (mExportMergedViewCells)
         {
                 DEL_PTR(fVc);
@@ -2631 +2635 @@
                         if ((*nit)->GetViewCell() != leaf->GetViewCell())
                         {
-                                mMergeQueue.push(BspMergeCandidate(leaf, *nit));
+                                BspMergeCandidate mc(leaf, *nit);
+                                mc.EvalMergeCost();
+
+                                mMergeQueue.push(mc);
                                 ++ candidates;
                         }
@@ -2637 +2644 @@
         }
 
-        Debug << "found " << candidates << " new merge candidates" << endl;
+        Debug << "mergequeue: " << (int)mMergeQueue.size() << endl;
+        Debug << "leaves in queue: " << candidates << endl;
+        Debug << "overall cost: " << BspMergeCandidate::sOverallCost << endl;
+
 
         return (int)leaves.size();
@@ -2726 +2736 @@
                         if (!found)
                         {
-                                // this pair is not in map already
+                                // this pair is not in map yet
                                 // => insert into the neighbor map and the queue
                                 neighbors.push_back(prevLeaf);
@@ -2734 +2744 @@
                                 prevLeaf->Mail();
                 
-                                mMergeQueue.push(BspMergeCandidate(leaf, prevLeaf));
+                                BspMergeCandidate mc(leaf, prevLeaf);
+                                mc.EvalMergeCost();
+
+                                mMergeQueue.push(mc);
+
+                                if (((int)mMergeQueue.size() % 1000) == 0)
+                                {
+                                        cout << "collected " << (int)mMergeQueue.size() << " merge candidates" << endl;
+                                }
                         }
         }
         }
+
         Debug << "neighbormap size: " << (int)neighborMap.size() << endl;
         Debug << "mergequeue: " << (int)mMergeQueue.size() << endl;
@@ -2804 +2823 @@
 {
         BspMergeCandidate::sMaxPvsSize = mViewCellsManager->GetMaxPvsSize();
+        //BspMergeCandidate::sMinPvsSize = mViewCellsManager->GetMinPvsSize();
         BspMergeCandidate::sUseArea = mUseAreaForPvs;
 
         // the current view cells are kept in this container
         ViewCellContainer viewCells;
-        ViewCell::NewMail();
-        CollectViewCells(mRoot, true, viewCells, true);
+        if (mExportMergedViewCells)
+        {
+                ViewCell::NewMail();
+                CollectViewCells(mRoot, true, viewCells, true);
+        }
         ViewCell::NewMail();
 
         MergeStatistics mergeStats;
         mergeStats.Start();
-        // TODO: REMOVE LATER for performance!
-        const bool showMergeStats = false;
-
+        
         //BspMergeCandidate::sOverallCost = mBox.SurfaceArea() * mStat.maxPvs;
         long startTime = GetTime();
 
+        cout << "collecting merge candidates ... ";
+        
         if (mUseRaysForMerge)
         {
-                cout << "collecting merge candidates (rays) ... ";
                 mergeStats.nodes = CollectMergeCandidates(rays);
-                cout << "fininshed collecting candidates" << endl;
         }
         else
@@ -2832 +2853 @@
                 mergeStats.nodes = CollectMergeCandidates(leaves);
         }
-                
+        
+        cout << "fininshed collecting candidates" << endl;
 
         mergeStats.collectTime = TimeDiff(startTime, GetTime());
@@ -2840 +2862 @@
         // number of view cells withouth the invalid ones
         int nViewCells = mStat.Leaves() - mStat.invalidLeaves;
-        Debug << "number of view cells taken into account: " << nViewCells << endl;
+        
+        
         // pass is needed for statistics. the last n passes are
         // recorded
         const int maxPasses = 1000;
+        const int nextPass = 50;
+
         int pass = max(nViewCells - mMergeMinViewCells - maxPasses, 0);
-        const int nextPass = 50;
-
-        cout << "starting merge ... " << endl;
+        
+        cout << "actual merge starts now ... " << endl;
 
         //-- use priority queue to merge leaf pairs
@@ -2881 +2905 @@
                         ++ mergeStats.merged;
 
-                        if (showMergeStats)
+                        if ((mergeStats.merged % 500) == 0)
+                                cout << "merged " << mergeStats.merged << " view cells" << endl;
+
+                        // stats and visualizations
+                        if (mExportMergeStats)
                         {
                                 if (mc.GetLeaf1()->IsSibling(mc.GetLeaf2()))
@@ -2892 +2920 @@
                                 mergeStats.accTreeDist += dist;
 
-                                //Debug << "viewcells: " << nViewCells << " mergemin " << mMergeMinViewCells << endl;
                                 if ((mergeStats.merged == pass) || (nViewCells == mMergeMinViewCells))
                                 {
@@ -2903 +2930 @@
                                                 << "#CurrentCost\n" << mergeCost << endl
                                                 << "#RelativeCost\n" << mergeCost / BspMergeCandidate::sOverallCost << endl
-                                                << "#CurrentPvs\n" << mc.GetLeaf1()->GetViewCell()->GetPvs().GetSize() << endl;
-                                        
-                                        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();
-                                        }
-
-                                        // delete the view cells which were merged
-                                        CLEAR_CONTAINER(mOldViewCells);
-
-                                        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;
-                                        }
-                                        
+                                                << "#CurrentPvs\n" << mc.GetLeaf1()->GetViewCell()->GetPvs().GetSize() << endl
+                                                << "#MergedSiblings\n" << mergeStats.siblings << endl
+                                                << "#AvgTreeDist\n" << mergeStats.AvgTreeDist() << endl;
+
+                                                if (mExportMergedViewCells)
+                                                        ExportMergedViewCells(viewCells, objects, nViewCells);   
                                 }
                         }
-                        mNewViewCells.clear();
                 }
                 // merge candidate not valid, because one of the leaves was already
@@ -2998 +2948 @@
         }
 
-        // view cells which were merged and are not part of any leaf
-        CLEAR_CONTAINER(mOldViewCells);
-        
-        cout << "finished merge" << endl;
+        mergeStats.overallCost = BspMergeCandidate::sOverallCost;
+
         mergeStats.mergeTime = TimeDiff(startTime, GetTime());
         mergeStats.Stop();
 
-        if (showMergeStats)
-                Debug << mergeStats << endl << endl;
+        Debug << mergeStats << endl << endl;
+        
+        // delete the view cells which were already merged
+        CLEAR_CONTAINER(mOldViewCells);
         
 
@@ -3047 +2997 @@
 
 
-int VspBspTree::RefineViewCells(const VssRayContainer &rays)
+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)
 {
         int shuffled = 0;
@@ -3055 +3094 @@
 
         // Use priority queue of remaining leaf pairs 
-        // These candidates either share the same view cells or
+        // 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.,
@@ -3061 +3100 @@
         // 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;
+
+    Exporter *exporter = Exporter::GetExporter("neighors.x3d");
+
+        if (exporter)
+        {
+                cout << "exporting neighbors ... ";
+                exporter->ExportGeometry(objects);
+        }
+
+        // HACK for visualization
+        ViewCellContainer viewCells;
+        ViewCell::NewMail();
+        CollectViewCells(mRoot, true, viewCells, true);
+        for (int i = 0; i < viewCells.size(); ++i)
+                viewCells[i]->SetId((int)RandomValue(0, Real(256*256*256)));
+        
+        Material m;
+        m.mDiffuseColor.r = 0;
+        m.mDiffuseColor.g = 0;
+        m.mDiffuseColor.b = 0;
+
         while (!mMergeQueue.empty())
         {
                 BspMergeCandidate mc = mMergeQueue.top();
+                shuffleQueue->push(mc);
                 mMergeQueue.pop();
 
-                // both view cells equal or already shuffled
-                if ((mc.GetLeaf1()->GetViewCell() == mc.GetLeaf2()->GetViewCell()) ||
-                        (mc.GetLeaf1()->Mailed()) || (mc.GetLeaf2()->Mailed()))
-                        continue;
+                m = RandomMaterial();
+                // visualize neighbors
+                exporter->SetForcedMaterial(m);
                 
-                // candidate for shuffling
-                const bool wasShuffled = 
-                        ShuffleLeaves(mc.GetLeaf1(), mc.GetLeaf2());
+                BspNodeGeometry geom1, geom2;
+
+                ConstructGeometry(mc.GetLeaf1(), geom1);
+                ConstructGeometry(mc.GetLeaf1(), geom2);
+
+                //m.mDiffuseColor.r = (mc.GetLeaf1()->GetViewCell()->GetId() & 256)/ 255.0f;
+                //m.mDiffuseColor.g = ((mc.GetLeaf1()->GetViewCell()->GetId()>>8) & 256)/ 255.0f;
+                //m.mDiffuseColor.b = ((mc.GetLeaf1()->GetViewCell()->GetId()>>16) & 256)/ 255.0f;
+                exporter->SetForcedMaterial(m);
+
+                exporter->ExportPolygons(geom1.mPolys);
                 
-                //-- stats
-                if (wasShuffled)
-                        ++ shuffled;
+                //m.mDiffuseColor.r = (mc.GetLeaf2()->GetViewCell()->GetId() & 256)/ 255.0f;
+                //m.mDiffuseColor.g = ((mc.GetLeaf2()->GetViewCell()->GetId()>>8) & 256)/ 255.0f;
+                //m.mDiffuseColor.b = ((mc.GetLeaf2()->GetViewCell()->GetId()>>16) & 256)/ 255.0f;
+                //exporter->SetForcedMaterial(m);
+
+                exporter->ExportPolygons(geom2.mPolys);
+        }
+
+        if (exporter)
+        {
+                cout << "finished" << endl;
+                delete exporter;
+        }
+
+        const int numPasses = 5;
+        int pass = 0;
+        int passShuffled = 0;
+
+
+        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();
         }
 
@@ -3312 +3440 @@
 mLeaf2Id(l2->GetViewCell()->mMailbox)
 {
-        EvalMergeCost();
+        //EvalMergeCost();
 }
 
@@ -3336 +3464 @@
         BspViewCell *vc = mLeaf2->GetViewCell();
         return GetCost(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;
 }
 
@@ -3345 +3500 @@
         BspViewCell *vc2 = mLeaf2->GetViewCell();
 
-        const int diff1 = vc1->GetPvs().Diff(vc2->GetPvs());
-        const int newPvs = diff1 + vc1->GetPvs().GetSize();
+        //const int diff1 = vc1->GetPvs().Diff(vc2->GetPvs());
+        //const int newPvs = diff1 + vc1->GetPvs().GetSize();
+        const int newPvs = ComputeMergedPvsSize(vc1->GetPvs(), vc2->GetPvs());
 
         //-- compute ratio of old cost
@@ -3360 +3516 @@
         if (newPvs > sMaxPvsSize) // strong penalty if pvs size too large
         {
-                mMergeCost = 1e15f;
+                mMergeCost = 1e15;
         }
         else
@@ -3417 +3573 @@
 
 /************************************************************************/
-/*                  MergeStatistics implementation                      */
+/*                    MergeStatistics implementation                    */
 /************************************************************************/
 
@@ -3438 +3594 @@
 
         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";
 

trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.h

@@ -261 +261 @@
                 @returns number of refined view cells
         */
-        int RefineViewCells(const VssRayContainer &rays);
+        int RefineViewCells(const VssRayContainer &rays, const ObjectContainer &objects);
 
         /** Collapses the tree with respect to the view cell partition.
@@ -615 +615 @@
         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
@@ -722 +728 @@
         /// 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:
@@ -784 +794 @@
         /// maximal pvs size
         static int sMaxPvsSize;
+        /// minimal pvs size
+        //static int sMinPvsSize;
+
         /// overall cost used to normalize cost ratio
         static float sOverallCost;
@@ -823 +836 @@
         Real collectTime;
         Real mergeTime;
+
+        Real overallCost;
 
         // Constructor
@@ -844 +859 @@
                 collectTime = 0;
                 mergeTime = 0;
+                overallCost = 0;
         }
 

trunk/VUT/GtpVisibilityPreprocessor/src/VssPreprocessor.cpp

@@ -105 +105 @@
   if (!mDetectEmptyViewSpace)
         ray.mFlags &= ~Ray::CULL_BACKFACES;
-                                                           else
-                                                                 ray.mFlags |= Ray::CULL_BACKFACES;
+  else
+         ray.mFlags |= Ray::CULL_BACKFACES;
 
   if (mKdTree->CastRay(ray)) {
@@ -601 +601 @@
           
   }
-  
+ 
+
   cout << "#totalRayStackSize=" << (int)mVssRays.size() << endl << flush;
   Debug << (int)mVssRays.size() << " rays generated in " 

trunk/VUT/GtpVisibilityPreprocessor/src/X3dExporter.cpp

@@ -1254 +1254 @@
 
         // box should not never remove part of beam polygons
-        Vector3 bmin = beam.mBox.Min() - Vector3(zfar * 2.0);
-        Vector3 bmax = beam.mBox.Max() + Vector3(zfar * 2.0);
+        Vector3 bmin = beam.mBox.Min() - Vector3(zfar * 2.0f);
+        Vector3 bmax = beam.mBox.Max() + Vector3(zfar * 2.0f);
 
         AxisAlignedBox3 bbox(bmin, bmax);