Changeset 485

Timestamp:

12/30/05 12:08:15 (18 years ago)

Author:

mattausch

Message:

changed castlinesegment of vspbpstree
changed rayinfo ray classification for bsp tree
implemented shuffling

Location:

trunk/VUT/GtpVisibilityPreprocessor

Files:

• scripts/default.env (modified) (7 diffs)
• src/Environment.cpp (modified) (7 diffs)
• src/Mesh.cpp (modified) (2 diffs)
• src/Plane3.h (modified) (1 diff)
• src/Pvs.h (modified) (5 diffs)
• src/Ray.cpp (modified) (5 diffs)
• src/RayInfo.cpp (modified) (1 diff)
• src/RssTree.cpp (modified) (5 diffs)
• src/ViewCell.cpp (modified) (1 diff)
• src/ViewCellBsp.cpp (modified) (6 diffs)
• src/ViewCellBsp.h (modified) (5 diffs)
• src/ViewCellsManager.cpp (modified) (67 diffs)
• src/ViewCellsManager.h (modified) (10 diffs)
• src/VspBspTree.cpp (modified) (29 diffs)
• src/VspBspTree.h (modified) (10 diffs)
• src/VspKdTree.cpp (modified) (14 diffs)
• src/VspKdTree.h (modified) (6 diffs)
• src/VssPreprocessor.cpp (modified) (1 diff)
• src/VssTree.cpp (modified) (1 diff)

trunk/VUT/GtpVisibilityPreprocessor/scripts/default.env

@@ -160 +160 @@
                 maxPvs 150
                 # how much samples are used for post processing
-                samples 10
+                samples 100000
         }
 
@@ -170 +170 @@
                 #colorCode MergedTreeDiff
                 colorCode Random
+                exportRays false
+                exportGeometry true
         }
         
 #       filename ../data/atlanta/atlanta_viewcells_large.x3d
-        filename ../data/vienna/viewcells-25-sel.x3d
+#       filename ../data/vienna/viewcells-25-sel.x3d
 #       filename ../data/vienna/viewcells-25.x3d
 #       filename ../data/vienna/viewcells-large-sel.x3d
@@ -196 +198 @@
         Termination {
                 maxDepth                40
-                minPvs                  1
+                minPvs                  50
                 minRays                 300
                 minSize                 0.1
                 maxCostRatio            0.9
-                missTolerance           6
-                maxRayContribution      0.3
-        }
-        
-        maxTotalMemory  400
-        maxStaticMemory 200
+                missTolerance           4
+                maxRayContribution      0.5
+        }
+        
+        maxTotalMemory  100
+        maxStaticMemory 50
 
         splitType       regular
         #splitType      heuristics
+        splitUseOnlyDrivingAxis true
         ct_div_ci       0.0
         
@@ -214 +217 @@
         PostProcess {
                 maxCostRatio 0.005
-                minViewCells 50
+                minViewCells 200
                 maxPvsSize   50000
         }
@@ -220 +223 @@
         
         Visualization {
-                exportRays true
-                exportGeometry true
         }
 }
@@ -272 +273 @@
         }
         
+        splitUseOnlyDrivingAxis false
+        
         Visualization {
                 # x3d visualization of the split planes
                 exportSplits true
-                exportRays true
-                exportGeometry true
         }
         
         PostProcess {
-                maxCostRatio 0.005
-                minViewCells 100
+                maxCostRatio 0.1
+                minViewCells 200
                 maxPvsSize   500
+                useRaysForMerge false
         }
 }
@@ -378 +380 @@
                 # x3d visualization of the split planes
                 exportSplits true
-                exportRays true
-                exportGeometry false
-        }
-}
+        }
+}

trunk/VUT/GtpVisibilityPreprocessor/src/Environment.cpp

@@ -1231 +1231 @@
                  "-view_cells_height=",
                  "5.0");
+
    RegisterOption("ViewCells.Visualization.colorCode",
                 optString,
@@ -1236 +1237 @@
                 "PVS");
 
+   RegisterOption("ViewCells.Visualization.exportRays",
+          optBool,
+          "-bsp_visualization.export_rays",
+          "false");
+   
+   RegisterOption("ViewCells.Visualization.exportGeometry",
+          optBool,
+          "-bsp_visualization.export_geometry",
+          "false");
+
   /************************************************************************************/
   /*                         Render simulation related options                        */
@@ -1374 +1385 @@
           "false");
 
-   RegisterOption("BspTree.Visualization.exportRays",
-          optBool,
-          "-bsp_visualization.export_rays",
-          "false");
-   
-   RegisterOption("BspTree.Visualization.exportGeometry",
-          optBool,
-          "-bsp_visualization.export_geometry",
-          "false");
 
    RegisterOption("BspTree.Factor.verticalSplits", optFloat, "-bsp_factor_vertical=", "1.0");
@@ -1456 +1458 @@
            "queries");
 
+  RegisterOption("VspKdTree.splitAxis", 
+           optString, 
+           "split=", 
+           "drivingAxis");
+
+  RegisterOption("VspKdTree.splitUseOnlyDrivingAxis", 
+          optBool, 
+          "vsp_kd_splitdriving=", 
+          "false");
+
         RegisterOption("VspKdTree.numberOfEndPointDomains", 
                 optInt, 
@@ -1505 +1517 @@
                 "vsp_kd_term_post_process_max_pvs_size=", 
                 "100");
-        
-        RegisterOption("VspKdTree.Visualization.exportRays",
-                optBool,
-                "-vsp_kd_visualization.export_rays",
-                "false");
-   
-        RegisterOption("VspKdTree.Visualization.exportGeometry",
-                optBool,
-                "-vsp_kd_visualization.export_geometry",
-                "false");
 
         RegisterOption("VspKdTree.Termination.missTolerance",
@@ -1719 +1721 @@
                 "-vsp_bsp_visualization.export_splits",
                 "false");
-
-        RegisterOption("VspBspTree.Visualization.exportRays",
-                optBool,
-                "-vsp_bsp_visualization.export_rays",
+        
+        RegisterOption("VspBspTree.splitUseOnlyDrivingAxis", 
+                optBool, 
+                "vsp_bsp_splitdriving=", 
                 "false");
-   
-        RegisterOption("VspBspTree.Visualization.exportGeometry",
-                optBool,
-                "-vsp_bsp_visualization.export_geometry",
-                "false");
-
-        
+
+
         RegisterOption("VspBspTree.Factor.leastRaySplits", optFloat, "-vsp_bsp_factor_least_ray_splits=", "1.0");
         RegisterOption("VspBspTree.Factor.balancedRays", optFloat, "-vsp_bsp_factor_balanced_rays=", "1.0");
@@ -1749 +1746 @@
                 "vsp_bsp_term_post_process_max_pvs_size=", 
                 "100");
+        
+        RegisterOption("VspBspTree.PostProcess.useRaysForMerge", 
+                optBool, 
+                "vsp_bsp_term_post_process_use_rays_for_merge=", 
+                "false");
         
         //////////////////////////////////////////////////////////////////////////////////

trunk/VUT/GtpVisibilityPreprocessor/src/Mesh.cpp

@@ -271 +271 @@
 Mesh::GetRandomSurfacePoint(Vector3 &point, Vector3 &normal)
 {
-  int faceIndex = RandomValue(0, mFaces.size()-1);
+  int faceIndex = (int)RandomValue(0, (Real)((int)mFaces.size()-1));
   
   // assume the face is convex and generate a convex combination
@@ -298 +298 @@
 {
   Plane3 plane;
-  int faceIndex = RandomValue(0, mFaces.size()-1);
+  int faceIndex = (int)RandomValue(0, (Real)((int)mFaces.size()-1));
         int tries;
   for (tries = 0; tries < maxTries; tries++) {

trunk/VUT/GtpVisibilityPreprocessor/src/Plane3.h

@@ -76 +76 @@
       @returns -1 if coplanar, else parameter t
   */
-  float FindT(const Vector3 &a,
-                          const Vector3 &b) const 
+  float FindT(const Vector3 &a, const Vector3 &b) const 
   {       
           const Vector3 v = b - a; // line from A to B

trunk/VUT/GtpVisibilityPreprocessor/src/Pvs.h

@@ -72 +72 @@
   int AddSample(T sample);
 
+  /** Adds one pvs to another one.
+          @returns new pvs size
+  */
+  int AddPvs(const Pvs<T> &pvs);
+  /** Subtracts one pvs from another one.
+          @returns new pvs size
+  */
+  int SubtractPvs(const Pvs<T> &pvs);
   /** Returns PVS data, i.e., how often it was seen from the view cell, 
           and the object itsef.
@@ -80 +88 @@
   */
   void CollectEntries(std::vector<T> &entries);
+
+  /** Removes sample from PVS if reference count is zero.
+          @param visibleSampels number of references to be removed
+  */
+  bool RemoveSample(T sample, const int visibleSamples);
 
   /// Map of PVS entries
@@ -108 +121 @@
         // todo: copy all elements instead of inserting
         for (it = a.mEntries.begin(); it != a.mEntries.end(); ++ it)
-        {
                 mEntries.insert(*it);
-        }
-
+        
         for (it = b.mEntries.begin(); it != b.mEntries.end(); ++ it)
         {
@@ -135 +146 @@
 template <typename T>
 void Pvs<T>::GetData(const int index,
-               T &entry,
-               PvsData<T> &data)
+                                         T &entry,
+                                         PvsData<T> &data)
 {
   std::map<T, PvsData<T>, LtSample<T> >::iterator i = mEntries.begin();
@@ -170 +181 @@
 
 template <typename T>
+bool Pvs<T>::RemoveSample(T sample, const int visibleSamples)
+{
+        std::map<T, PvsData<T>, LtSample<T> >::
+                iterator it = mEntries.find(sample);
+
+        if (it == mEntries.end())
+                return false;
+
+        PvsData<T> *data = &(*it).second;
+  
+        data->mVisibleSamples -= visibleSamples;
+        if (data->mVisibleSamples <= 0)
+                mEntries.erase(it);
+
+        return true;
+}
+
+template <typename T>
+int Pvs<T>::AddPvs(const Pvs<T> &pvs)
+{
+        std::map<T, PvsData<T>, LtSample<T> >::
+                const_iterator it, it_end = pvs.mEntries.end();
+
+        float contri;
+        // output PVS of view cell
+        for (it = pvs.mEntries.begin(); it != it_end; ++ it) 
+                AddSample((*it).first, contri);
+
+        return GetSize();
+}
+ 
+template <typename T>
+int Pvs<T>::SubtractPvs(const Pvs<T> &pvs)
+{
+        std::map<T, PvsData<T>, LtSample<T> >::
+                const_iterator it, it_end = pvs.mEntries.end();
+
+        // output PVS of view cell
+        for (it = pvs.mEntries.begin(); it != it_end; ++ it) 
+                RemoveSample((*it).first, (*it).second.mVisibleSamples);
+
+        return GetSize();
+}
+
+template <typename T>
 void Pvs<T>::CollectEntries(std::vector<T> &entries)
 {
-        PvsMap<T>::const_iterator it, it_end = mEntries.end();
+        std::map<T, PvsData<T>, LtSample<T> >::
+                const_iterator it, it_end = mEntries.end();
 
         // output PVS of view cell

trunk/VUT/GtpVisibilityPreprocessor/src/Ray.cpp

@@ -50 +50 @@
 Ray::CorrectZeroComponents()
 {
-  const float eps = 1e-6;
+  const float eps = 1e-6f;
 
   // it does change the ray direction very slightly,
@@ -99 +99 @@
   }
   else
-    invDir.x = 1.0 / dir.x;
+    invDir.x = 1.0f / dir.x;
   
   if (fabs(dir.y) < eps) {
@@ -108 +108 @@
   }
   else
-    invDir.y = 1.0 / dir.y;
+    invDir.y = 1.0f / dir.y;
   
   if (fabs(dir.z) < eps) {
-    if (dir.z < 0.0)
+    if (dir.z < 0.0f)
       invDir.z = -invEps;
     else
@@ -117 +117 @@
   }
   else
-    invDir.z = 1.0 / dir.z;
+    invDir.z = 1.0f / dir.z;
 
   return;
@@ -165 +165 @@
   float x, y;
   dir.ExtractVerts(&x, &y, axis);
-  int ix = (x + 1.0f)*0.5f*Resolution;
-  int iy = (y + 1.0f)*0.5f*Resolution;
+  int ix = (int)((x + 1.0f)*0.5f*Resolution);
+  int iy = (int)((y + 1.0f)*0.5f*Resolution);
 
   return Resolution*(Resolution*axis + iy) + ix;

trunk/VUT/GtpVisibilityPreprocessor/src/RayInfo.cpp

@@ -133 +133 @@
 {       
         t = splitPlane.FindT(mRay->GetOrigin(), mRay->GetTermination());
+//      Debug << "t: " << t << " mint " << GetMinT() << " maxt " << GetMaxT() << 
+//      " orig: " << mRay->GetOrigin() << " term " << mRay->GetTermination() << endl;
 
-//      Debug << "t: " << t << " mint " << GetMinT() << " maxt " << GetMaxT() << " orig: " << mRay->GetOrigin() <<
-//              " term " << mRay->GetTermination() << endl;
-        if ((t < GetMinT()) || (t > GetMaxT()))
+        // NOTE: if plane equals end point of ray, the ray should be classified
+        // non-intersecting, otherwise polygon-plane intersections of bsp tree
+        // approaches are not eliminating any rays intersecting the polygon!
+
+        //if (t > GetMaxT())
+        if (t >= GetMaxT() - 1e-20)
                 return splitPlane.Side(ExtrapOrigin());
+        //if (t < GetMinT())
+        if (t <= GetMinT() + 1e-20)
+                return splitPlane.Side(ExtrapTermination());
 
         return 0;

trunk/VUT/GtpVisibilityPreprocessor/src/RssTree.cpp

@@ -824 +824 @@
   float sizeBox = maxBox - minBox;
         
-  float minBand = minBox + 0.1*(maxBox - minBox);
-  float maxBand = minBox + 0.9*(maxBox - minBox);
-        
-  float minRatio = 1e20;
+  float minBand = minBox + 0.1f*(maxBox - minBox);
+  float maxBand = minBox + 0.9f*(maxBox - minBox);
+        
+  float minRatio = 1e20f;
         
   Intersectable::NewMail();
@@ -1123 +1123 @@
   
   // update stats
-  stat.rayRefs -= leaf->rays.size();
+  stat.rayRefs -= (int)leaf->rays.size();
   stat.rayRefs += raysBack + raysFront;
 
@@ -1296 +1296 @@
         
                 if (removeAllScheduledRays) {
-                  int tail = leaf->rays.size()-1;
+                  int tail = (int)leaf->rays.size()-1;
 
                   for (int i=0; i < (int)(leaf->rays.size()); i++) {
@@ -2069 +2069 @@
         }
   }
-  return rays.size();
+  return (int)rays.size();
 }
 
@@ -2103 +2103 @@
   }
   
-  return rays.size();
-}
+  return (int)rays.size();
+}

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCell.cpp

@@ -105 +105 @@
         app << "#N_PAVGPVS ( average PVS )\n" << AvgPvs() << endl;
 
-        app << "#N_PEMPTYPVS ( view cells with PVS smaller 2 )\n" << emptyPvs << endl;
+        app << "#N_PEMPTYPVS ( view cells with empty PVS )\n" << emptyPvs << endl;
 
         app << "#N_VIEWCELLS ( number of view cells)\n" << viewCells << endl;

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp

@@ -144 +144 @@
 
 
-BspLeaf::BspLeaf(): mViewCell(NULL)
-{
+BspLeaf::BspLeaf(): mViewCell(NULL), mPvs(NULL)
+{
+}
+
+
+BspLeaf::~BspLeaf()
+{
+        DEL_PTR(mPvs);
 }
 
@@ -156 +162 @@
 
 BspLeaf::BspLeaf(BspInterior *parent): 
-BspNode(parent), mViewCell(NULL)
+BspNode(parent), mViewCell(NULL), mPvs(NULL)
 {}
 
@@ -162 +168 @@
 
 BspLeaf::BspLeaf(BspInterior *parent, BspViewCell *viewCell): 
-BspNode(parent), mViewCell(viewCell)
+BspNode(parent), mViewCell(viewCell), mPvs(NULL)
 {
 }
@@ -406 +412 @@
 {
         DEL_PTR(mRoot);
-        DEL_PTR(mRootCell);
+
+        // root cell not used
+        if (mGenerateViewCells)
+                DEL_PTR(mRootCell);
 }
 
@@ -795 +804 @@
                 // generate new view cell for each leaf
                 if (mGenerateViewCells)
-                {
                         viewCell = new BspViewCell();
-                }
                 else
-                {
                         // add view cell to leaf
                         viewCell = dynamic_cast<BspViewCell *>(tData.mViewCell);
-                }
-
+                
                 leaf->SetViewCell(viewCell);
                 viewCell->mLeaves.push_back(leaf);
@@ -1312 +1317 @@
         }
         
-        //-- choose candidate planes extracted from rays
-        //-- different methods are available
+        // choose candidate planes extracted from rays
         for (int i = 0; i < mMaxRayCandidates; ++ i)
         {

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.h

@@ -63 +63 @@
     BspRayTraversalData(BspNode *n, const Vector3 &extp, const float maxt):
     mNode(n), mExitPoint(extp), mMaxT(maxt) 
+        {}
+
+        BspRayTraversalData(BspNode *n, const Vector3 &extp):
+        mNode(n), mExitPoint(extp)
         {}
 };
@@ -122 +126 @@
         int sampleContributions;
         /// largest pvs
-        int largestPvs;
+        int maxPvs;
 
         // Constructor
@@ -156 +160 @@
                 contributingSamples = 0;
                 sampleContributions = 0;
+
+                maxPvs = 0;
         }
 
@@ -274 +280 @@
         BspLeaf(BspInterior *parent, BspViewCell *viewCell);
 
+        ~BspLeaf();
+
         /** @return true since it is an interior node 
         */
@@ -287 +295 @@
 
         VssRayContainer mVssRays;
+        
+        /// leaf pvs
+        ObjectPvs *mPvs;
+        /// leaf area
+        float mArea;
 
 protected:
-
+        
         /// if NULL this does not correspond to feasible viewcell
         BspViewCell *mViewCell;

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellsManager.cpp

@@ -40 +40 @@
         environment->GetIntValue("ViewCells.PostProcess.maxPvs", mMaxPvs);
 
+        environment->GetBoolValue("ViewCells.Visualization.exportRays", mExportRays);
+        environment->GetBoolValue("ViewCells.Visualization.exportGeometry", mExportGeometry);
+
         char buf[50];
         
@@ -56 +59 @@
 }
 
+
 ViewCellsManager::~ViewCellsManager()
 {
@@ -62 +66 @@
         CLEAR_CONTAINER(mViewCells);
 }
+
 
 bool ViewCellsManager::LoadViewCells(const string filename)
@@ -74 +79 @@
         return success;
 }
+
 
 void ViewCellsManager::ComputeSampleContributions(const VssRayContainer &rays)
@@ -82 +88 @@
   
         VssRayContainer::const_iterator it, it_end = rays.end();
-        
+        int i = 0;      
         for (it = rays.begin(); it != it_end; ++ it) 
-        {
+        {       if ((i ++) % 50000 == 0)
+                        cout << "Computed 50000 samples" << endl;
                 ComputeSampleContributions(*(*it));
         }
 }
+
 
 void ViewCellsManager::EvaluateViewCellsStats()
@@ -99 +107 @@
 }
 
+
 void ViewCellsManager::AddViewCell(ViewCell *viewCell)
 {
@@ -104 +113 @@
 }
 
+
 float ViewCellsManager::GetArea(ViewCell *viewCell) const
 {
@@ -114 +124 @@
         return viewCell->GetVolume();
 }
+
 
 void ViewCellsManager::DeriveViewCells(const ObjectContainer &objects, 
@@ -138 +149 @@
         }
 }
+
 
 ViewCell *ViewCellsManager::ExtrudeViewCell(const Triangle3 &baseTri, 
@@ -174 +186 @@
 }
 
+
 ViewCell *ViewCellsManager::MergeViewCells(ViewCell &front, ViewCell &back) const
 {
@@ -193 +206 @@
 }
 
+
 void ViewCellsManager::SetRenderer(Renderer *renderer)
 {
@@ -198 +212 @@
 }
 
+
 ViewCell *ViewCellsManager::GenerateViewCell(Mesh *mesh) const
 {
@@ -209 +224 @@
 }
 
+
 void ViewCellsManager::SetConstructionSamples(const int constructionSamples)
 {
@@ -214 +230 @@
 }
 
+
 void ViewCellsManager::SetPostProcessSamples(const int postProcessSamples)
 {
@@ -219 +236 @@
 }
 
+
 int ViewCellsManager::GetVisualizationSamples() const
 {
@@ -224 +242 @@
 }
 
+
 int ViewCellsManager::GetConstructionSamples() const
 {
@@ -229 +248 @@
 }
 
+
 int ViewCellsManager::GetPostProcessSamples() const
 {
@@ -234 +254 @@
 }
 
-void
-ViewCellsManager::GetPvsStatistics(PvsStatistics &stat)
+
+void ViewCellsManager::GetPvsStatistics(PvsStatistics &stat)
 {
   ViewCellContainer::const_iterator it = mViewCells.begin();
@@ -257 +277 @@
 }
 
+
 void ViewCellsManager::PrintPvsStatistics(ostream &s)
 {
@@ -267 +288 @@
 }
 
+
 ViewCellContainer &ViewCellsManager::GetViewCells()
 {
         return mViewCells;
 }
+
 
 void ViewCellsManager::ResetViewCells()
@@ -282 +305 @@
 }
 
+
 void ViewCellsManager::ComputeSampleContributions(VssRay &ray)
 {
         ViewCellContainer viewcells;
-        
+                
+        ray.mPvsContribution = 0;
+        ray.mRelativePvsContribution = 0.0f;
+
+        // matt TODO: remove this!!
         Ray hray(ray);
         float tmin = 0, tmax = 1.0;
-        // matt TODO: remove this!!
+        Debug << "here2" << endl;
         //hray.Init(ray.GetOrigin(), ray.GetDir(), Ray::LINE_SEGMENT);
-
         if (!GetSceneBbox().GetRaySegment(hray, tmin, tmax) || (tmin > tmax))
                 return;
@@ -300 +327 @@
                                         termination,
                                         viewcells);
-        
-        ray.mPvsContribution = 0;
-        ray.mRelativePvsContribution = 0.0f;
   
         ViewCellContainer::const_iterator it = viewcells.begin();
@@ -320 +344 @@
                 
                 ray.mRelativePvsContribution += contribution;
-        }
+        }Debug << "here5" << endl;
 }
 
 
 void ViewCellsManager::GetRaySets(const VssRayContainer &sourceRays,
-                                                                  VssRayContainer &constructionRays, 
-                                                                  VssRayContainer &savedRays) const
-{
-        const int limit = min(mConstructionSamples, (int)sourceRays.size());
+                                                                  const int maxSize,
+                                                                  VssRayContainer &usedRays, 
+                                                                  VssRayContainer *savedRays) const
+{
+        const int limit = min(maxSize, (int)sourceRays.size());
+        const float prop = (float)limit / ((float)sourceRays.size() + Limits::Small);
 
         VssRayContainer::const_iterator it, it_end = sourceRays.end();
-        
-        const float prop = (float)limit / ((float)sourceRays.size() + Limits::Small);
-
         for (it = sourceRays.begin(); it != it_end; ++ it)
         {
                 if (Random(1.0f) < prop)
-                        constructionRays.push_back(*it);
-                else
-                        savedRays.push_back(*it);
+                        usedRays.push_back(*it);
+                else if (savedRays)
+                        savedRays->push_back(*it);
         }
 }
@@ -378 +401 @@
         {
                 ExportColor(exporter, *it);
-                ExportGeometry(exporter, *it);
+                ExportVcGeometry(exporter, *it);
         }
 }
@@ -512 +535 @@
 
         EvaluateViewCellsStats();
-        Debug << "original view cell partition:\n" << mViewCellsStats << endl;
+        Debug << "\noriginal view cell partition:\n" << mViewCellsStats << endl;
 
         mRenderer->RenderScene();
@@ -531 +554 @@
                         ExportViewCells(exporter);
                                 
-                        if (0)
+                        if (mExportGeometry)
                         {
                                 Material m;
@@ -552 +575 @@
 
         // $$JB we do not have connectivity information from the ray in the moment
-        // perhaps we could recast the rays or rember the cells traversed inside the
+        // perhaps we could recast the rays or remember the cells traversed inside the
         // vssray (which would on other hand create some overhead)
         //-- merge or subdivide view cells
@@ -558 +581 @@
 
         vector<BspIntersection>::const_iterator iit;
-
-        if (mBspRays.empty())
-                ConstructBspRays(rays, mPostProcessSamples);
+        CLEAR_CONTAINER(mBspRays);
+        ConstructBspRays(rays, mPostProcessSamples);
         
         for (int i = 0; i < (int)mBspRays.size(); ++ i)
@@ -597 +619 @@
 
         Debug << "Postprocessing: Merged " << merged << " view cells in "
-                  << TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl << endl;
-        
+                  << TimeDiff(startTime, GetTime()) *1e-3 << " secs" 
+                  << "using " << (int)mBspRays.size() << " samples" << endl << endl;
+        
+        CLEAR_CONTAINER(mBspRays);
+
         // reset view cells and stats
         ResetViewCells();
@@ -623 +648 @@
         if (!ViewCellsConstructed())
                 return;
-
-        if (mBspRays.empty())
-                ConstructBspRays(sampleRays, mVisualizationSamples);
+        CLEAR_CONTAINER(mBspRays);
+        ConstructBspRays(sampleRays, mVisualizationSamples);
         
         if (1) // export view cells
@@ -697 +721 @@
                 }
 
-                if (0)
+                if (mExportGeometry)
                         exporter->ExportGeometry(objects);
 
@@ -707 +731 @@
 void BspViewCellsManager::ExportBspPvs(const ObjectContainer &objects)
 {
-        bool exportRays = false;
-        bool exportGeometry = false;
-
-        environment->GetBoolValue("VspBspTree.Visualization.exportRays", exportRays);
-        environment->GetBoolValue("VspBspTree.Visualization.exportRays", exportRays);
-
         const int leafOut = 10;
         
@@ -777 +795 @@
                 }
                         
-                        
                 Debug << i << ": pvs size=" << (int)vc->GetPvs().GetSize() 
-                          << ", piercing rays=" << (int)vcRays.size() << endl;
+                          << ", piercing rays=" << (int)vcRays.size()
+                          << ", leaves=" << (int)vc->mLeaves.size() << endl;
 
                         
@@ -951 +969 @@
 }
 
-void BspViewCellsManager::ExportGeometry(Exporter *exporter, 
+void BspViewCellsManager::ExportVcGeometry(Exporter *exporter, 
                                                                                  ViewCell *vc) const
 {
@@ -959 +977 @@
         {
                 PolygonContainer cell;
-                mBspTree->ConstructGeometry(dynamic_cast<BspViewCell *>(vc), cell);
-
+                mBspTree->ConstructGeometry(
+                        dynamic_cast<BspViewCell *>(vc), cell);
                 exporter->ExportPolygons(cell);
         }
@@ -1221 +1239 @@
 
 
-void KdViewCellsManager::ExportGeometry(Exporter *exporter, 
-                                                                                ViewCell *vc) const
-{
-        // TODO
+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));
 }
 
@@ -1297 +1319 @@
         VssRayContainer savedRays;
 
-        GetRaySets(rays, constructionRays, savedRays);
+        GetRaySets(rays, 
+                           mConstructionSamples, 
+                           constructionRays, 
+                           &savedRays);
         
         Debug << "constructing vsp kd tree using " 
@@ -1308 +1333 @@
         ExportLeaves(objects, rays);
 
-        mVspKdTree->CollectMergeCandidates();
         // finally merge kd leaf building blocks to view cells
-        const int merged = mVspKdTree->MergeLeaves();
+        const int merged = mVspKdTree->MergeViewCells(rays);
+
+        // collapse siblings belonging to the same view cell
+        mVspKdTree->CollapseTree(mVspKdTree->GetRoot());
+        
+        // collapse siblings belonging to the same view cell
+        mVspKdTree->RefineViewCells();
+
         // evaluale view cell stats
         ResetViewCells();
@@ -1316 +1347 @@
         Debug << "\nView cells after construction:\n" << mViewCellsStats << endl;
 
+        long startTime = GetTime();
         // recast rest of rays
         ComputeSampleContributions(savedRays);
+        
+        Debug << "Computed remaining ray contribution in " << TimeDiff(startTime, GetTime()) * 1e-3 
+                  << " secs" << endl;
 
         return merged;
@@ -1355 +1390 @@
                                                                                  const VssRayContainer &sampleRays)
 {
-        bool exportRays = false;
-        bool exportGeometry = false;
-
-        environment->GetBoolValue("VspKdTree.Visualization.exportRays", exportRays);
-        environment->GetBoolValue("VspKdTree.Visualization.exportGeometry", exportGeometry);
-
         if (!ViewCellsConstructed())
                 return;
@@ -1373 +1402 @@
         exporter->ExportVspKdTree(*mVspKdTree);
 
-        if (exportGeometry) 
+        if (mExportGeometry) 
                 exporter->ExportGeometry(objects);
 
-        if (exportRays) 
+        if (mExportRays) 
         {
                 const float prob = (float)mVisualizationSamples 
@@ -1400 +1429 @@
                                                                           const VssRayContainer &sampleRays)
 {
-        bool exportRays = false;
-        bool exportGeometry = false;
-
-        environment->GetBoolValue("VspKdTree.Visualization.exportRays", exportRays);
-        environment->GetBoolValue("VspKdTree.Visualization.exportGeometry", exportGeometry);
-
         if (!ViewCellsConstructed())
                 return;
@@ -1429 +1452 @@
                 exporter->SetWireframe();
 
-                ExportGeometry(exporter, vc);
+                ExportVcGeometry(exporter, vc);
 
                 //-- export stored rays
-                if (exportRays)
+                if (mExportRays)
                 {
                         vector<VspKdLeaf *>::const_iterator it, 
@@ -1454 +1477 @@
                                 for (it = vssRays.begin(); it != it_end; ++ it)
                                 {
-                                        if (RandomValue(0, 1) < prop)
+                                        if (Random(1) < prop)
                                                 if ((*it)->mTerminationObject == NULL)
                                                         castRays.push_back(*it);
@@ -1497 +1520 @@
         Exporter *exporter = Exporter::GetExporter("vspkdtree_merged.x3d"); 
         
-        /*if (exportGeometry) exporter->SetWireframe();
-        else exporter->SetFilled();*/
+        //if (exportGeometry) exporter->SetWireframe();
+        //else exporter->SetFilled();
 
         ExportViewCells(exporter);
 
-        if (exportGeometry) 
+        if (mExportGeometry) 
         {
                 exporter->SetFilled();
@@ -1508 +1531 @@
         }
 
-        if (exportRays) 
+        if (mExportRays) 
         {
                 const float prob = (float)mVisualizationSamples 
@@ -1566 +1589 @@
                 }
                 break;
-        case 3: // merge tree differene
+        case 3: // merged tree depth difference
                 {
                         //importance = (float)GetMaxTreeDiff(vc) / 
@@ -1585 +1608 @@
 
 
-void VspKdViewCellsManager::ExportGeometry(Exporter *exporter, 
+void VspKdViewCellsManager::ExportVcGeometry(Exporter *exporter, 
                                                                                    ViewCell *vc) const
 {
         VspKdViewCell *kdVc = dynamic_cast<VspKdViewCell *>(vc);
-
         vector<VspKdLeaf *>::const_iterator it, it_end = kdVc->mLeaves.end();
 
         for (it = kdVc->mLeaves.begin(); it != it_end; ++ it)
-        {
                 exporter->ExportBox(mVspKdTree->GetBBox(*it));
-        }
 }
 
@@ -1615 +1635 @@
 VspBspViewCellsManager::~VspBspViewCellsManager()
 {
-        CLEAR_CONTAINER(mBspRays);
 }
 
@@ -1672 +1691 @@
         VssRayContainer savedRays;
 
-        GetRaySets(rays, constructionRays, savedRays);
-        
+        GetRaySets(rays, mConstructionSamples, constructionRays, &savedRays);
+        
+        Debug << "construction rays: " << (int)savedRays.size() << endl;
+        Debug << "saved rays: " << (int)constructionRays.size() << endl;
+
         mVspBspTree->Construct(constructionRays, sceneBbox);
         Debug << mVspBspTree->GetStatistics() << endl;
@@ -1680 +1702 @@
 
         Debug << "\nView cells after construction:\n" << mViewCellsStats << endl;
+        
+        long startTime = GetTime();
         // recast rest of rays
         ComputeSampleContributions(savedRays);
-
+        
+        Debug << "Computed remaining ray contribution in " << TimeDiff(startTime, GetTime()) * 1e-3 
+                  << " secs" << endl;
+
+        cout << "construction finished" << endl;
         return sampleContributions;
 }
 
-
-void VspBspViewCellsManager::ConstructBspRays(const VssRayContainer &rays,
-                                                                                          const int numSamples)
-{
-        VssRayContainer::const_iterator it, it_end = rays.end();
-
-        for (it = rays.begin(); it != rays.end() && mBspRays.size() < numSamples; ++ it)
-        {
-                VssRay *vssRay = *it;
-                
-                Ray hray(*vssRay);
-                float tmin = 0, tmax = 1.0;
-        
-                //hray.Init(ray.GetOrigin(), ray.GetDir(), Ray::LINE_SEGMENT);
-
-                if (!GetSceneBbox().GetRaySegment(hray, tmin, tmax) || (tmin > tmax))
+// matt TODO: remove
+int VspBspViewCellsManager::MergeViewCells(const VssRayContainer &rays) const
+{
+        vector<BspIntersection>::const_iterator iit;
+        vector<BspRay *>bspRays;
+        int merged = 0;
+
+        mVspBspTree->ConstructBspRays(bspRays, rays);
+
+        for (int i = 0; i < (int)bspRays.size(); ++ i)
+        {
+                BspRay *ray = bspRays[i];
+          
+                // traverse leaves stored in the rays and compare and merge consecutive
+                // leaves (i.e., the neighbors in the tree)
+                if (ray->intersections.size() < 2)
                         continue;
-
-                Vector3 origin = hray.Extrap(tmin);
-                Vector3 termination = hray.Extrap(tmax);
-        
-                BspRay *ray = new BspRay(vssRay);
-
-                ViewCellContainer viewCells;
-
-                // cast line segment and store intersections with the rays
-                CastLineSegment(origin, termination, viewCells);
-
-                ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
-                
-                for (vit = viewCells.begin(); vit != vit_end; ++ vit)
-                {
-                        BspViewCell *vc = dynamic_cast<BspViewCell *>(*vit);
-                        ray->intersections.push_back(BspIntersection(0, vc->mLeaves[0]));
-                }
-
-                mBspRays.push_back(ray);
-        }
-}
-
+          
+                iit = ray->intersections.begin();
+
+                BspLeaf *previousLeaf = (*iit).mLeaf;
+                ++ iit;
+                
+                for (; iit != ray->intersections.end(); ++ iit)
+                {
+                        BspLeaf *leaf = (*iit).mLeaf;
+
+                        if (ShouldMerge(leaf, previousLeaf))
+                        {                       
+                                mVspBspTree->MergeViewCells(leaf, previousLeaf);
+                                ++ merged;
+                        }
+                        previousLeaf = leaf;
+                }
+        }
+        CLEAR_CONTAINER(bspRays);
+
+        return merged;
+}
+        
 
 int VspBspViewCellsManager::PostProcess(const ObjectContainer &objects, 
@@ -1740 +1768 @@
         int pvsSize = 0;
 
+        VssRayContainer postProcessRays;
+        GetRaySets(rays, mPostProcessSamples, postProcessRays);
+
+        Debug << "post processing using " << (int)postProcessRays.size() << " samples" << endl;
         EvaluateViewCellsStats();
-        Debug << "original view cell partition:\n" << mViewCellsStats << endl;
+        Debug << "\noriginal view cell partition:\n" << mViewCellsStats << endl << endl;
 
         mRenderer->RenderScene();
@@ -1759 +1791 @@
                         ExportViewCells(exporter);
 
-                        bool exportGeometry = false;
-                        environment->GetBoolValue("VspBspTree.Visualization.exportGeometry", exportGeometry);
-
-                        if (exportGeometry)
+                        if (mExportGeometry)
                         {
                                 Material m;
@@ -1777 +1806 @@
         }
 
-        cout << "starting post processing using " << mPostProcessSamples << " samples ... ";
-                
-        long startTime = GetTime();
-
-
-        // $$JB we do not have connectivity information from the ray in the moment
-        // perhaps we could recast the rays or rember the cells traversed inside the
-        // vssray (which would on other hand create some overhead)
         //-- merge or subdivide view cells
         int merged = 0;
-
-        vector<BspIntersection>::const_iterator iit;
-
-        // matt TODO: remove
-        if (0)
-        {
-                if (mBspRays.empty())
-                        ConstructBspRays(rays, mPostProcessSamples);
-
-                for (int i = 0; i < (int)mBspRays.size(); ++ i)
-                {
-                        BspRay *ray = mBspRays[i];
-          
-                        // traverse leaves stored in the rays and compare and merge consecutive
-                        // leaves (i.e., the neighbors in the tree)
-                        if (ray->intersections.size() < 2)
-                                continue;
-          
-                        iit = ray->intersections.begin();
-
-                        BspLeaf *previousLeaf = (*iit).mLeaf;
-                        ++ iit;
-                
-                        for (; iit != ray->intersections.end(); ++ iit)
-                        {
-                                BspLeaf *leaf = (*iit).mLeaf;
-
-                                if (ShouldMerge(leaf, previousLeaf))
-                                {                       
-                                        MergeVspBspLeafViewCells(leaf, previousLeaf);
-                                        ++ merged;
-                                }
-                                previousLeaf = leaf;
-                        }
-                }
-        }
-        else
-        {
-                merged = mVspBspTree->MergeLeaves();
-        }
+        
+        cout << "starting merge using " << mPostProcessSamples << " samples ... ";
+        long startTime = GetTime();
+
+        merged = mVspBspTree->MergeViewCells(postProcessRays);
 
         //-- stats and visualizations
@@ -1836 +1822 @@
                   << TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl << endl;
         
+        ResetViewCells();
+        //BspLeaf::NewMail();
+        if (1) // export merged view cells
+        {
+                Exporter *exporter = Exporter::GetExporter("merged_view_cells.x3d");
+                Debug << "\nView cells after merge:\n" << mViewCellsStats << endl;
+
+                cout << "exporting view cells after merge ... ";
+
+                if (exporter)
+                {
+                        //exporter->SetWireframe();
+                        exporter->SetFilled();
+                        ExportViewCells(exporter);
+
+                        if (mExportGeometry)
+                        {
+                                Material m;
+                                m.mDiffuseColor = RgbColor(0, 1, 0);
+                                exporter->SetForcedMaterial(m);
+                                exporter->SetFilled();
+
+                                exporter->ExportGeometry(objects);
+                        }
+
+                        delete exporter;
+                }
+                cout << "finished" << endl;
+        }
+
+        Debug << "render time before refine:" << endl;
+        mRenderer->RenderScene();
+        dynamic_cast<RenderSimulator *>(mRenderer)->GetStatistics(ss);
+    Debug << ss << endl;
+
+        cout << "Refining the view cells ... ";
+        startTime = GetTime();
+
+        // refining the merged view cells
+        const int refined = mVspBspTree->RefineViewCells(rays);
+
+        //-- stats and visualizations
+        cout << "finished" << endl;
+        cout << "refined " << refined << " view cells in "
+                 << TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl;
+
+        Debug << "Postprocessing: refined " << refined << " view cells in "
+                  << TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl << endl;
+        
+        // collapse sibling leaves that share the same view cell
+        mVspBspTree->CollapseTree(mVspBspTree->GetRoot());
         // reset view cells and stats
         ResetViewCells();
@@ -1854 +1891 @@
                 return;
 
-#if 1
-        if (mBspRays.empty())
-                ConstructBspRays(sampleRays, mVisualizationSamples);
-#endif
+        VssRayContainer visRays;
+        
+        GetRaySets(sampleRays, mVisualizationSamples, visRays);
 
         if (1) // export view cells
         {
                 cout << "exporting view cells after post process ... ";
-                Exporter *exporter = Exporter::GetExporter("merged_view_cells.x3d");
+                Exporter *exporter = Exporter::GetExporter("final_view_cells.x3d");
 
                 if (exporter)
                 {
+                        if (mExportGeometry)
+                                exporter->ExportGeometry(objects);
                         ExportViewCells(exporter);
                         delete exporter;
@@ -1880 +1918 @@
         {
                 cout << "exporting splits ... ";
-                ExportSplits(objects);
+                ExportSplits(objects, visRays);
                 cout << "finished" << endl;
         }
 
-        ExportBspPvs(objects);
-}
-        
-
-void VspBspViewCellsManager::ExportSplits(const ObjectContainer &objects)
+        // export single view cells
+        ExportBspPvs(objects, visRays);
+}
+        
+
+void VspBspViewCellsManager::ExportSplits(const ObjectContainer &objects,
+                                                                                  const VssRayContainer &rays)
 {
         Exporter *exporter = Exporter::GetExporter("bsp_splits.x3d");
-
-        bool exportRays = false;
-        bool exportGeometry = false;
-
-        environment->GetBoolValue("VspBspTree.Visualization.exportRays", exportRays);
-        environment->GetBoolValue("VspBspTree.Visualization.exportGeometry", exportGeometry);
 
         if (exporter) 
@@ -1915 +1949 @@
                 
                 // export rays
-                if (exportRays)
-                {
-                        VssRayContainer outRays;
-                
-                        int raysSize = min((int)mBspRays.size(), mVisualizationSamples);
-
-                        for (int i = 0; i < raysSize; ++ i)
-                                // only rays piercing geometry
-                                outRays.push_back(mBspRays[i]->vssRay);
-                                                
-                        // export rays 
-                        exporter->ExportRays(outRays, RgbColor(1, 1, 0));
-                }
-
-                if (exportGeometry)
+                if (mExportRays)
+                        exporter->ExportRays(rays, RgbColor(1, 1, 0));
+        
+                if (mExportGeometry)
                         exporter->ExportGeometry(objects);
 
@@ -1936 +1959 @@
 }
 
-void VspBspViewCellsManager::ExportBspPvs(const ObjectContainer &objects)
-{
-        bool exportRays = false;
-        bool exportGeometry = false;
-
-        environment->GetBoolValue("VspBspTree.Visualization.exportRays", exportRays);
-        environment->GetBoolValue("VspBspTree.Visualization.exportGeometry", exportGeometry);
-
+void VspBspViewCellsManager::ExportBspPvs(const ObjectContainer &objects,
+                                                                                  const VssRayContainer &rays)
+{
         const int leafOut = 10;
         
         ViewCell::NewMail();
-
-        //-- some rays for output
-        const int raysOut = min((int)mBspRays.size(), mVisualizationSamples);
         
         cout << "visualization using " << mVisualizationSamples << " samples" << endl;
         Debug << "\nOutput view cells: " << endl;
         
-        // sort view cells to get largest view cells
+        // sort view cells to visualize the largest view cells
 #if 0
         stable_sort(mViewCells.begin(), mViewCells.end(), vc_gt);
@@ -1960 +1975 @@
         int limit = min(leafOut, (int)mViewCells.size()); 
 
+#if 1
+        //-- some rays for output
+        vector<BspRay *> bspRays;
+        mVspBspTree->ConstructBspRays(bspRays, rays);
+
+        const int raysOut = min((int)bspRays.size(), mVisualizationSamples);
+#endif
+
         for (int i = 0; i < limit; ++ i)
         {
                 cout << "creating output for view cell " << i << " ... ";
+                
                 VssRayContainer vcRays;
-           Intersectable::NewMail();
+                Intersectable::NewMail();
 #if 0
                 BspViewCell *vc = dynamic_cast<BspViewCell *>(mViewCells[i]);
 #else
-                BspViewCell *vc = dynamic_cast<BspViewCell *>(mViewCells[Random((int)mViewCells.size())]);
+                BspViewCell *vc = dynamic_cast<BspViewCell *>
+                        (mViewCells[Random((int)mViewCells.size())]);
 #endif
-                cout << "creating output for view cell " << i << " ... ";
 
 #if 1
@@ -1976 +2000 @@
                 for (int k = 0; k < raysOut; ++ k) 
                 {
-                        BspRay *ray = mBspRays[k];
+                        BspRay *ray = bspRays[k];
                         for     (int j = 0; j < (int)ray->intersections.size(); ++ j)
                         {
@@ -1987 +2011 @@
                 //bspLeaves[j]->Mail();
                 char s[64]; sprintf(s, "bsp-pvs%04d.x3d", i);
-
                 Exporter *exporter = Exporter::GetExporter(s);
-                        
                 exporter->SetWireframe();
 
@@ -1996 +2018 @@
                 exporter->SetForcedMaterial(m);
 
-                if (vc->GetMesh())
-                        exporter->ExportViewCell(vc);
-                else
-                {
-                        PolygonContainer vcGeom;
-                        // export view cell
-                        mVspBspTree->ConstructGeometry(vc, vcGeom);
-                        exporter->ExportPolygons(vcGeom);
-                        CLEAR_CONTAINER(vcGeom);
-                }
+                ExportVcGeometry(exporter, vc); 
                         
-                        
+                                
                 Debug << i << ": pvs size=" << (int)vc->GetPvs().GetSize() 
-                          << ", piercing rays=" << (int)vcRays.size() << endl;
-
-                        
-                // export rays piercing this view cell
+                          << ", piercing rays=" << (int)vcRays.size()
+                          << ", leaves=" << (int)vc->mLeaves.size() << endl;
+                
+                //-- export rays piercing this view cell
 #if 1
                 exporter->ExportRays(vcRays, RgbColor(0, 1, 0));
@@ -2049 +2062 @@
         }
 
+#if 1
+        CLEAR_CONTAINER(bspRays);
+#endif
         Debug << endl;
 }
 
-
-bool VspBspViewCellsManager::MergeVspBspLeafViewCells(BspLeaf *front, 
-                                                                                                          BspLeaf *back) const
-{
-        BspViewCell *viewCell = 
-                dynamic_cast<BspViewCell *>(MergeViewCells(*front->GetViewCell(), 
-                                                                                                   *back->GetViewCell()));
-        
-        if (!viewCell)
-                return false;
-
-        // change view cells of all leaves
-        // associated with the previous view cells
-        BspViewCell *fVc = front->GetViewCell();
-        BspViewCell *bVc = back->GetViewCell();
-
-        vector<BspLeaf *> fLeaves = fVc->mLeaves;
-        vector<BspLeaf *> bLeaves = bVc->mLeaves;
-
-        vector<BspLeaf *>::const_iterator it;
-        
-        for (it = fLeaves.begin(); it != fLeaves.end(); ++ it)
-        {
-                (*it)->SetViewCell(viewCell);
-                viewCell->mLeaves.push_back(*it);
-        }
-        for (it = bLeaves.begin(); it != bLeaves.end(); ++ it)
-        {
-                (*it)->SetViewCell(viewCell);
-                viewCell->mLeaves.push_back(*it);
-        }
-        
-        DEL_PTR(fVc);
-        DEL_PTR(bVc);
-
-        return true;
-}
 
 bool VspBspViewCellsManager::ShouldMerge(BspLeaf *front, BspLeaf *back) const
@@ -2095 +2074 @@
         ViewCell *bvc = back->GetViewCell();
 
-        if ((fvc == mVspBspTree->GetRootCell()) || 
-                (bvc == mVspBspTree->GetRootCell()) || 
-                (fvc == bvc))
+        if (fvc == bvc)
                 return false;
 
@@ -2106 +2083 @@
                 if ((fvc->GetPvs().GetSize() < mMinPvs) ||      
                         (bvc->GetPvs().GetSize() < mMinPvs) ||
-                        ((fdiff < mMinPvsDif) && (bvc->GetPvs().Diff(fvc->GetPvs()) < mMinPvsDif)))
+                        ((fdiff < mMinPvsDif) && 
+                         (bvc->GetPvs().Diff(fvc->GetPvs()) < mMinPvsDif)))
                 {
                         return true;
@@ -2167 +2145 @@
 
 
-void VspBspViewCellsManager::ExportGeometry(Exporter *exporter, 
-                                                                                        ViewCell *vc) const
-{
-        if (vc->GetMesh())
-                exporter->ExportViewCell(vc);
-        else
-        {
-                PolygonContainer cell;
-                mVspBspTree->
-                        ConstructGeometry(dynamic_cast<BspViewCell *>(vc), cell);
-
-                exporter->ExportPolygons(cell);
-        }
+void VspBspViewCellsManager::ExportVcGeometry(Exporter *exporter, 
+                                                                                          ViewCell *vc) const
+{
+#if 1
+        BspNodeGeometry geom;
+        mVspBspTree->
+                ConstructGeometry(dynamic_cast<BspViewCell *>(vc), geom.mPolys);
+        exporter->ExportPolygons(geom.mPolys);
+#else
+        
+        Material m2;
+        m2.mDiffuseColor.b = 0.3f + Random(0.7f);
+        m2.mDiffuseColor.r = 0.0f;//0.3f + Random(0.7f);
+        m2.mDiffuseColor.g = 0.3f + Random(0.7f);
+        Material m;
+        m.mDiffuseColor.b = 0.0f;
+        m.mDiffuseColor.r = 1.0f;
+        m.mDiffuseColor.g = 0.0f;
+
+        BspViewCell *bspVc = dynamic_cast<BspViewCell *>(vc);
+        vector<BspLeaf *>::const_iterator it, it_end = bspVc->mLeaves.end();
+
+        for (it = bspVc->mLeaves.begin(); it != it_end; ++ it)
+        {
+                if ((*it)->Mailed())
+                        exporter->SetForcedMaterial(m);
+                else
+                        exporter->SetForcedMaterial(m2);
+                        //exporter->ResetForcedMaterial();
+                BspNodeGeometry geom;
+                mVspBspTree->ConstructGeometry(*it, geom);
+                exporter->ExportPolygons(geom.mPolys);
+        }
+#endif
 }
 

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellsManager.h

@@ -186 +186 @@
         ViewCellContainer &GetViewCells();
 
-        /** Helper function used to split ray set into one used for view cell
-                construction and one cast after construction.
+        /** Helper function used to split ray sets uniformly 
+                into one that is currently used and the other that 
+                is saved for later processing.
+                @param sourceRays the input ray set
+                @param maxSize the maximal number of rays that will be used
+                @param usedRays returns the used ray set
+                @param savedRays if not null, returns the saved ray set
         */
         void GetRaySets(const VssRayContainer &sourceRays,
-                                        VssRayContainer &constructionRays, 
-                                        VssRayContainer &savedRays) const;
-
+                                        const int maxSize,
+                                        VssRayContainer &usedRays, 
+                                        VssRayContainer *savedRays = NULL) const;
+        
         /** Returns accumulated area of all view cells.
         */
@@ -242 +248 @@
         /** Exports view cell geometry.
         */
-        virtual void ExportGeometry(Exporter *exporter, ViewCell *vc) const = 0;
+        virtual void ExportVcGeometry(Exporter *exporter, ViewCell *vc) const = 0;
 
         /// the view cell corresponding to unbounded space
@@ -266 +272 @@
         float mTotalArea;
 
-        // visualization color code
+        //-- visualization options
+        
+        /// color code for view cells
         int mColorCode;
+        bool mExportGeometry;
+        bool mExportRays;
 
         ViewCellsStatistics mViewCellsStats;
@@ -281 +291 @@
 
 public:
-
+        /** Constructor taking the bsp tree and the number of samples
+                used to construct the bsp tree.
+        */
         BspViewCellsManager(BspTree *tree, int constructionSamples);
 
@@ -330 +342 @@
 
         void ExportColor(Exporter *exporter, ViewCell *vc) const;
-        void ExportGeometry(Exporter *exporter, ViewCell *vc) const;
+        void ExportVcGeometry(Exporter *exporter, ViewCell *vc) const;
 
         /// the BSP tree.
@@ -393 +405 @@
 
         void ExportColor(Exporter *exporter, ViewCell *vc) const;
-        void ExportGeometry(Exporter *exporter, ViewCell *vc) const;
+        void ExportVcGeometry(Exporter *exporter, ViewCell *vc) const;
 
         /// the BSP tree.
@@ -450 +462 @@
 
         void ExportColor(Exporter *exporter, ViewCell *vc) const;
-        void ExportGeometry(Exporter *exporter, ViewCell *vc) const;
+        void ExportVcGeometry(Exporter *exporter, ViewCell *vc) const;
 
 
@@ -499 +511 @@
 
 protected:
-
-        /** Constructs bsp rays for post processing and visualization.
-        */
-        void ConstructBspRays(const VssRayContainer &rays, const int numSamples);
-
-        /** Merges view cells front and back leaf view cell.
-        */
-        bool MergeVspBspLeafViewCells(BspLeaf *front, BspLeaf *back) const;
+        /** DEPRECATED
+        */
+        int MergeViewCells(const VssRayContainer &rays) const;
 
         /** Returns true if front and back leaf should be merged.
@@ -513 +520 @@
 
         void CollectViewCells();
-
-        void ExportColor(Exporter *exporter, ViewCell *vc) const;
-        void ExportGeometry(Exporter *exporter, ViewCell *vc) const;
 
         /** Returns maximal depth difference of view cell 
@@ -521 +525 @@
         */
         int GetMaxTreeDiff(ViewCell *vc) const;
+        
+
+        void ExportColor(Exporter *exporter, ViewCell *vc) const;
+        void ExportVcGeometry(Exporter *exporter, ViewCell *vc) const;
+
 
         /// the view space partition BSP tree.
         VspBspTree *mVspBspTree;
 
-        /// helper array of rays
-        vector<BspRay *> mBspRays;
-
 private:
 
         /** Exports visualization of the BSP splits.
         */
-        void ExportSplits(const ObjectContainer &objects);
+        void ExportSplits(const ObjectContainer &objects, 
+                                          const VssRayContainer &rays);
 
         /** Exports visualization of the BSP PVS.
         */
-        void ExportBspPvs(const ObjectContainer &objects);
+        void ExportBspPvs(const ObjectContainer &objects,
+                                          const VssRayContainer &rays);
 
 };

trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.cpp

@@ -33 +33 @@
 int VspBspTree::sFrontAndBackId = 0;
 
-float BspMergeCandidate::sOverallCost = Limits::Small;
+float BspMergeCandidate::sOverallCost = 0;
 
 /****************************************************************/
@@ -44 +44 @@
 mCostNormalizer(Limits::Small),
 mViewCellsManager(NULL),
-mStoreRays(true),
+mStoreRays(false),
 mOnlyDrivingAxis(false)
 {
-        mRootCell = new BspViewCell();
-
         Randomize(); // initialise random generator for heuristics
 
@@ -82 +80 @@
         environment->GetFloatValue("VspBspTree.PostProcess.maxCostRatio", mMergeMaxCostRatio);
 
+        environment->GetBoolValue("VspBspTree.splitUseOnlyDrivingAxis", mOnlyDrivingAxis);
+        environment->GetBoolValue("VspBspTree.PostProcess.useRaysForMerge", mUseRaysForMerge);
 
         //-- debug output
@@ -137 +137 @@
 {
         DEL_PTR(mRoot);
-        DEL_PTR(mRootCell);
         DEL_PTR(mSplitCandidates);
 }
@@ -216 +215 @@
                 {
                         mBox.Include(object->GetBox()); // add to BSP tree aabb
-                        AddMeshToPolygons(mesh, polys, mRootCell);
+                        AddMeshToPolygons(mesh, polys, NULL);
                 }
         }
@@ -360 +359 @@
                  (data.mPvs <= mTermMinPvs)   ||
                  (data.mArea <= mTermMinArea) ||
-                 (mStat.nodes / 2 + 1 >= mMaxViewCells) ||
+                 (mStat.Leaves() >= mMaxViewCells) ||
                 // (data.GetAvgRayContribution() >= mTermMaxRayContribution) ||
                  (data.mDepth >= mTermMaxDepth));
@@ -400 +399 @@
                 BspViewCell *viewCell = new BspViewCell();
                 leaf->SetViewCell(viewCell);
-
+                
                 if (mStoreRays)
                 {
@@ -410 +409 @@
                 viewCell->mLeaves.push_back(leaf);
                 viewCell->SetArea(tData.mArea);
+                leaf->mArea = tData.mArea;
 
                 //-- update pvs
                 int conSamp = 0, sampCon = 0;
                 AddToPvs(leaf, *tData.mRays, conSamp, sampCon);
-
+        
                 mStat.contributingSamples += conSamp;
                 mStat.sampleContributions += sampCon;
@@ -1065 +1065 @@
                         // add the termination object
                         AddObjToPvs(ray->mTerminationObject, cf, frontPvs, backPvs);
-
                         // add the source object
                         AddObjToPvs(ray->mOriginObject, cf, frontPvs, backPvs);
@@ -1081 +1080 @@
                                 if (cf == 1)
                                         pFront += len;
-                                if (cf == -1)
+                                else if (cf == -1)
                                         pBack += len;
-                                if (cf == 0)
+                                else if (cf == 0)
                                 {
                                         // use length of rays to approximate volume
@@ -1231 +1230 @@
                 mStat.maxDepth = data.mDepth;
 
+        if (data.mPvs > mStat.maxPvs)
+                mStat.maxPvs = data.mPvs;
         if (data.mDepth < mStat.minDepth)
                 mStat.minDepth = data.mDepth;
-
         if (data.mDepth >= mTermMaxDepth)
                 ++ mStat.maxDepthNodes;
@@ -1436 +1436 @@
                 float t;
 
-                        // get classification and receive new t
+                // get classification and receive new t
                 const int cf = bRay.ComputeRayIntersection(plane, t);
 
@@ -1448 +1448 @@
                         break;
                 case 0:
-                        //-- split ray
-                        //--  look if start point behind or in front of plane
-                        if (plane.Side(bRay.ExtrapOrigin()) <= 0)
                         {
-                                backRays.push_back(RayInfo(ray, bRay.GetMinT(), t));
-                                frontRays.push_back(RayInfo(ray, t, bRay.GetMaxT()));
-                        }
-                        else
-                        {
-                                frontRays.push_back(RayInfo(ray, bRay.GetMinT(), t));
-                                backRays.push_back(RayInfo(ray, t, bRay.GetMaxT()));
+                                //-- split ray
+                                //-- test if start point behind or in front of plane
+                                const int side = plane.Side(bRay.ExtrapOrigin());
+
+                                if (side <= 0)
+                                {
+                                        backRays.push_back(RayInfo(ray, bRay.GetMinT(), t));
+                                        frontRays.push_back(RayInfo(ray, t, bRay.GetMaxT()));
+                                }
+                                else
+                                {
+                                        frontRays.push_back(RayInfo(ray, bRay.GetMinT(), t));
+                                        backRays.push_back(RayInfo(ray, t, bRay.GetMaxT()));
+                                }
                         }
                         break;
                 default:
-                        Debug << "Should not come here 4" << endl;
+                        Debug << "Should not come here" << endl;
                         break;
                 }
@@ -1497 +1501 @@
 }
 
+
 void VspBspTree::ConstructGeometry(BspNode *n,
                                                                    BspNodeGeometry &cell) const
 {
-        PolygonContainer polys;
-        ConstructGeometry(n, polys);
-        cell.mPolys = polys;
-}
+        ConstructGeometry(n, cell.mPolys);
+}
+
 
 void VspBspTree::ConstructGeometry(BspNode *n,
@@ -1588 +1592 @@
 }
 
-void VspBspTree::ConstructGeometry(BspViewCell *vc, PolygonContainer &vcGeom) const
+
+void VspBspTree::ConstructGeometry(BspViewCell *vc, 
+                                                                   PolygonContainer &vcGeom) const
 {
         vector<BspLeaf *> leaves = vc->mLeaves;
-
         vector<BspLeaf *>::const_iterator it, it_end = leaves.end();
 
@@ -1598 +1603 @@
 }
 
+
 int VspBspTree::FindNeighbors(BspNode *n, vector<BspLeaf *> &neighbors,
                                                    const bool onlyUnmailed) const
 {
         PolygonContainer cell;
-
         ConstructGeometry(n, cell);
 
@@ -1794 +1799 @@
 }
 
-BspViewCell *VspBspTree::GetRootCell() const
-{
-        return mRootCell;
-}
 
 int VspBspTree::SplitPolygons(const Plane3 &plane,
@@ -1858 +1859 @@
         BspNode *farChild = NULL;
 
+        float t;
         while (1)
         {
@@ -1865 +1867 @@
 
                         Plane3 splitPlane = in->GetPlane();
+                        
                         const int entSide = splitPlane.Side(entp);
                         const int extSide = splitPlane.Side(extp);
 
-                        if (entSide < 0)
+                        if (entSide < 0) 
                         {
                                 node = in->GetBack();
-
-                                if (extSide <= 0) // plane does not split ray => no far child
+                                // plane does not split ray => no far child
+                                if (extSide <= 0) 
                                         continue;
 
                                 farChild = in->GetFront(); // plane splits ray
-                        } else if (entSide > 0)
+                        } 
+                        else if (entSide > 0)
                         {
                                 node = in->GetFront();
@@ -1885 +1889 @@
                                 farChild = in->GetBack(); // plane splits ray
                         }
-                        else // ray and plane are coincident
-                        {
-                                // WHAT TO DO IN THIS CASE ?
-                                //break;
-                                node = in->GetFront();
-                                continue;
+                        else // ray end point on plane
+                        {       // NOTE: what to do if ray is coincident with plane?
+                                if (extSide < 0)
+                                        node = in->GetBack();
+                                else if (extSide > 0)
+                                        node = in->GetFront();
+
+                                continue; // no far child
                         }
 
                         // push data for far child
-                        tStack.push(BspRayTraversalData(farChild, extp, maxt));
+                        tStack.push(BspRayTraversalData(farChild, extp));
 
                         // find intersection of ray segment with plane
-                        float t;
                         extp = splitPlane.FindIntersection(origin, extp, &t);
-                        maxt *= t;
-
-                } else
+                } 
+                else
                 {
                         // reached leaf => intersection with view cell
@@ -1918 +1922 @@
 
                         entp = extp;
-                        mint = maxt; // NOTE: need this?
-
-
+                        
                         BspRayTraversalData &s = tStack.top();
 
                         node = s.mNode;
                         extp = s.mExitPoint;
-                        maxt = s.mMaxT;
 
                         tStack.pop();
                 }
         }
+
         return hits;
 }
 
-int VspBspTree::TreeDistance(BspNode *n1, BspNode *n2)
+int VspBspTree::TreeDistance(BspNode *n1, BspNode *n2) const
 {
         std::deque<BspNode *> path1;
@@ -1997 +1999 @@
                 }
         }
+
+        // revalidate leaves
+        RepairVcLeafLists();
 
         return node;
@@ -2040 +2045 @@
 
 
-int VspBspTree::MergeLeaves()
-{
-        vector<BspLeaf *> leaves;
-        priority_queue<BspMergeCandidate> mergeQueue;
-
-        // collect the leaves, e.g., the "voxels" that will build the view cells
-        CollectLeaves(leaves);
-
-        int vcSize = (int)leaves.size();
-        int savedVcSize = vcSize;
-
-        BspLeaf::NewMail();
-
-        vector<BspLeaf *>::const_iterator it, it_end = leaves.end();
-
-        // find merge candidates and push them into queue
-        for (it = leaves.begin(); it != it_end; ++ it)
-        {
-                BspLeaf *leaf = *it;
-
-                // no leaf is part of two merge candidates
-                if (!leaf->Mailed())
-                {
-                        leaf->Mail();
-
-                        vector<BspLeaf *> neighbors;
-                        FindNeighbors(leaf, neighbors, true);
-
-                        vector<BspLeaf *>::const_iterator nit,
-                                nit_end = neighbors.end();
-
-                        for (nit = neighbors.begin(); nit != nit_end; ++ nit)
-                        {
-                                BspMergeCandidate mc = BspMergeCandidate(leaf, *nit);
-                                mergeQueue.push(mc);
-
-                                BspMergeCandidate::sOverallCost += mc.GetLeaf1Cost();
-                                BspMergeCandidate::sOverallCost += mc.GetLeaf2Cost();
-                        }
-                }
-        }
-
-        int merged = 0;
-        int mergedSiblings = 0;
-        int accTreeDist = 0;
-        int maxTreeDist = 0;
-        const bool mergeStats = true;
-
-
-        //-- use priority queue to merge leaf pairs
-        while (!mergeQueue.empty() && (vcSize > mMergeMinViewCells) &&
-                   (mergeQueue.top().GetMergeCost() <
-                    mMergeMaxCostRatio * BspMergeCandidate::sOverallCost))
-        {
-                //Debug << "mergecost: " << mergeQueue.top().GetMergeCost() / BspMergeCandidate::sOverallCost << " " << mMergeMaxCostRatio << endl;
-                BspMergeCandidate mc = mergeQueue.top();
-                mergeQueue.pop();
-
-                // both view cells equal!
-                if (mc.GetLeaf1()->GetViewCell() == mc.GetLeaf2()->GetViewCell())
-                        continue;
-
-                if (mc.Valid())
-                {
-                        ViewCell::NewMail();
-                        MergeViewCells(mc.GetLeaf1(), mc.GetLeaf2());
-                        -- vcSize;
-                        // increase absolute merge cost
-                        BspMergeCandidate::sOverallCost += mc.GetMergeCost();
-
-                        //-- stats
-                        ++ merged;
-
-                        if (mc.GetLeaf1()->IsSibling(mc.GetLeaf2()))
-                                ++ mergedSiblings;
-
-                        if (mergeStats)
-                        {
-                                const int dist = TreeDistance(mc.GetLeaf1(), mc.GetLeaf2());
-
-                                if (dist > maxTreeDist)
-                                        maxTreeDist = dist;
-
-                                accTreeDist += dist;
-                        }
-                }
-                // merge candidate not valid, because one of the leaves was already
-                // merged with another one
-                else
-                {
-                        // validate and reinsert into queue
-                        mc.SetValid();
-                        mergeQueue.push(mc);
-                        //Debug << "validate " << mc.GetMergeCost() << endl;
-                }
-        }
-
-        // collapse tree according to view cell partition
-        CollapseTree(mRoot);
-        // revalidate leaves
-        RepairVcLeafLists();
-
-        Debug << "Merged " << merged << " nodes of " << savedVcSize
-                  << " (merged " << mergedSiblings << " siblings)" << endl;
-
-        if (mergeStats)
-        {
-                Debug << "maximal tree distance: " << maxTreeDist << endl;
-                Debug << "Avg tree distance: " << (float)accTreeDist / (float)merged << endl;
-        }
-
-        //TODO: should return sample contributions
-        return merged;
-}
-
-
-bool VspBspTree::MergeViewCells(BspLeaf *l1, BspLeaf *l2)
+bool VspBspTree::MergeViewCells(BspLeaf *l1, BspLeaf *l2) const
 {
         //-- change pointer to view cells of all leaves associated
@@ -2204 +2093 @@
         mViewCellsManager = vcm;
 }
+
+
+int VspBspTree::CollectMergeCandidates()
+{
+        vector<BspLeaf *> leaves;
+
+        // collect the leaves, e.g., the "voxels" that will build the view cells
+        CollectLeaves(leaves);
+        BspLeaf::NewMail();
+
+        vector<BspLeaf *>::const_iterator it, it_end = leaves.end();
+
+        // find merge candidates and push them into queue
+        for (it = leaves.begin(); it != it_end; ++ it)
+        {
+                BspLeaf *leaf = *it;
+                
+                /// create leaf pvs (needed for post processing
+                leaf->mPvs = new ObjectPvs(leaf->GetViewCell()->GetPvs());
+
+                BspMergeCandidate::sOverallCost += 
+                        leaf->mArea * leaf->mPvs->GetSize();
+
+                // the same leaves must not be part of two merge candidates
+                leaf->Mail();
+                vector<BspLeaf *> neighbors;
+                FindNeighbors(leaf, neighbors, true);
+
+                vector<BspLeaf *>::const_iterator nit, nit_end = neighbors.end();
+
+                // TODO: test if at least one ray goes from one leaf to the other
+                for (nit = neighbors.begin(); nit != nit_end; ++ nit)
+                {                       
+                        mMergeQueue.push(BspMergeCandidate(leaf, *nit));
+                }
+        }
+
+        return (int)leaves.size();
+}
+
+
+int VspBspTree::CollectMergeCandidates(const VssRayContainer &rays)
+{
+        vector<BspRay *> bspRays;
+
+        ConstructBspRays(bspRays, rays);
+        map<BspLeaf *, vector<BspLeaf*> > neighborMap;
+
+        vector<BspIntersection>::const_iterator iit;
+
+        int leaves = 0;
+        
+        BspLeaf::NewMail();
+
+        for (int i = 0; i < (int)bspRays.size(); ++ i)
+        {  
+                BspRay *ray = bspRays[i];
+          
+                // traverse leaves stored in the rays and compare and 
+                // merge consecutive leaves (i.e., the neighbors in the tree)
+                if (ray->intersections.size() < 2)
+                        continue;
+          
+                iit = ray->intersections.begin();
+                BspLeaf *prevLeaf = (*(iit ++)).mLeaf;
+                
+                // create leaf pvs (needed for post processing)
+                if (!prevLeaf->mPvs)
+                {
+                        prevLeaf->mPvs = 
+                                new ObjectPvs(prevLeaf->GetViewCell()->GetPvs());
+
+                        BspMergeCandidate::sOverallCost += 
+                                prevLeaf->mArea * prevLeaf->mPvs->GetSize();
+                        
+                        ++ leaves;
+                }
+                
+                // traverse intersections 
+                // consecutive leaves are neighbors => 
+                // add them to queue
+                for (; iit != ray->intersections.end(); ++ iit)
+                {
+            BspLeaf *leaf = (*iit).mLeaf;
+            
+                        if (!leaf->mPvs)
+                        {
+                                leaf->mPvs = 
+                                        new ObjectPvs(leaf->GetViewCell()->GetPvs());
+                                
+                                BspMergeCandidate::sOverallCost += 
+                                        leaf->mArea * leaf->mPvs->GetSize();
+
+                                ++ leaves;
+                        }
+                
+                        vector<BspLeaf *> &neighbors = neighborMap[leaf];
+                        
+                        bool found = false;
+
+                        // both leaves inserted in queue already =>
+                        // look if double pair already exists
+                        if (leaf->Mailed() && prevLeaf->Mailed())
+                        {
+                                vector<BspLeaf *>::const_iterator it, it_end = neighbors.end();
+                                
+                for (it = neighbors.begin(); !found && (it != it_end); ++ it)
+                                        if (*it == prevLeaf)
+                                                found = true; // already in queue
+                        }
+                        
+                        if (!found)
+                        {
+                                // this pair is not in map already
+                                // => insert into the neighbor map and the queue
+                                neighbors.push_back(prevLeaf);
+                                neighborMap[prevLeaf].push_back(leaf);
+
+                                leaf->Mail();
+                                prevLeaf->Mail();
+
+                                mMergeQueue.push(BspMergeCandidate(leaf, prevLeaf));
+                        }
+
+                        prevLeaf = leaf;
+        }
+        }
+        Debug << "neighbormap size: " << (int)neighborMap.size() << endl;
+        Debug << "mergequeue: " << (int)mMergeQueue.size() << endl;
+        Debug << "leaves in queue: " << leaves << endl;
+        Debug << "overall cost: " << BspMergeCandidate::sOverallCost << endl;
+
+        CLEAR_CONTAINER(bspRays);
+
+        return leaves;
+}
+
+
+void VspBspTree::ConstructBspRays(vector<BspRay *> &bspRays,
+                                                                  const VssRayContainer &rays)
+{
+        VssRayContainer::const_iterator it, it_end = rays.end();
+
+        for (it = rays.begin(); it != rays.end(); ++ it)
+        {
+                VssRay *vssRay = *it;
+                BspRay *ray = new BspRay(vssRay);
+
+                ViewCellContainer viewCells;
+
+                Ray hray(*vssRay);
+                float tmin = 0, tmax = 1.0;
+                // matt TODO: remove this!!
+                //hray.Init(ray.GetOrigin(), ray.GetDir(), Ray::LINE_SEGMENT);
+                if (!mBox.GetRaySegment(hray, tmin, tmax) || (tmin > tmax))
+                        continue;
+
+                Vector3 origin = hray.Extrap(tmin);
+                Vector3 termination = hray.Extrap(tmax);
+        
+                // cast line segment to get intersections with bsp leaves
+                CastLineSegment(origin, termination, viewCells);
+
+                ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
+                for (vit = viewCells.begin(); vit != vit_end; ++ vit)
+                {
+                        BspViewCell *vc = dynamic_cast<BspViewCell *>(*vit);
+                        vector<BspLeaf *>::const_iterator it, it_end = vc->mLeaves.end();
+                        //NOTE: not sorted!
+                        for (it = vc->mLeaves.begin(); it != it_end; ++ it)
+                                ray->intersections.push_back(BspIntersection(0, *it));
+                }
+
+                bspRays.push_back(ray);
+        }
+}
+
+
+int VspBspTree::MergeViewCells(const VssRayContainer &rays)
+{
+        MergeStatistics mergeStats;
+        mergeStats.Start();
+        // TODO: REMOVE LATER for performance!
+        const bool showMergeStats = true;
+        //BspMergeCandidate::sOverallCost = mBox.SurfaceArea() * mStat.maxPvs;
+        long startTime = GetTime();
+
+        if (mUseRaysForMerge)
+                mergeStats.nodes = CollectMergeCandidates(rays);
+        else
+                mergeStats.nodes = CollectMergeCandidates();
+
+        mergeStats.collectTime = TimeDiff(startTime, GetTime());
+        mergeStats.candidates = (int)mMergeQueue.size();
+        startTime = GetTime();
+
+        int nViewCells = /*mergeStats.nodes*/ mStat.Leaves();
+
+        
+        //-- use priority queue to merge leaf pairs
+        while (!mMergeQueue.empty() && (nViewCells > mMergeMinViewCells) &&
+                   (mMergeQueue.top().GetMergeCost() <
+                    mMergeMaxCostRatio * BspMergeCandidate::sOverallCost))
+        {
+                //Debug << "abs mergecost: " << mMergeQueue.top().GetMergeCost() << " rel mergecost: "
+                //        << mMergeQueue.top().GetMergeCost() / BspMergeCandidate::sOverallCost 
+                //        << " max ratio: " << mMergeMaxCostRatio << endl;
+                BspMergeCandidate mc = mMergeQueue.top();
+                mMergeQueue.pop();
+
+                // both view cells equal!
+                if (mc.GetLeaf1()->GetViewCell() == mc.GetLeaf2()->GetViewCell())
+                        continue;
+
+                if (mc.Valid())
+                {
+                        ViewCell::NewMail();
+                        MergeViewCells(mc.GetLeaf1(), mc.GetLeaf2());
+                        -- nViewCells;
+                        
+                        ++ mergeStats.merged;
+                        
+                        // increase absolute merge cost
+                        BspMergeCandidate::sOverallCost += mc.GetMergeCost();
+
+                        if (showMergeStats)
+                        {
+                                if (mc.GetLeaf1()->IsSibling(mc.GetLeaf2()))
+                                        ++ mergeStats.siblings;
+
+                                const int dist = 
+                                        TreeDistance(mc.GetLeaf1(), mc.GetLeaf2());
+                                if (dist > mergeStats.maxTreeDist)
+                                        mergeStats.maxTreeDist = dist;
+                                mergeStats.accTreeDist += dist;
+                        }
+                }
+                // merge candidate not valid, because one of the leaves was already
+                // merged with another one => validate and reinsert into queue
+                else
+                { 
+                        mc.SetValid();
+                        mMergeQueue.push(mc);
+                }
+        }
+
+        mergeStats.mergeTime = TimeDiff(startTime, GetTime());
+        mergeStats.Stop();
+
+        if (showMergeStats)
+                Debug << mergeStats << endl << endl;
+        
+        //TODO: should return sample contributions?
+        return mergeStats.merged;
+}
+
+
+int VspBspTree::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())
+        {
+                BspMergeCandidate 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 = 
+                        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(BspViewCell *vc, BspLeaf *l, const ObjectPvs &pvs2)
+{
+        ObjectPvs pvs;
+        vector<BspLeaf *>::const_iterator it, it_end = vc->mLeaves.end();
+        for (it = vc->mLeaves.begin(); it != vc->mLeaves.end(); ++ it)
+                if (*it != l)
+                        pvs.AddPvs(*(*it)->mPvs);
+        return pvs.GetSize();
+}*/
+
+inline int SubtractedPvsSize(ObjectPvs pvs1, const ObjectPvs &pvs2)
+{
+        return pvs1.SubtractPvs(pvs2);
+}
+
+
+float GetShuffledVcCost(BspLeaf *leaf, BspViewCell *vc1, BspViewCell *vc2)
+{
+        //const int pvs1 = SubtractedPvsSize(vc1, leaf, *leaf->mPvs);
+        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;
+}
+
+
+void VspBspTree::ShuffleLeaf(BspLeaf *leaf, 
+                                                         BspViewCell *vc1, 
+                                                         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);
+        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<BspLeaf *>::iterator it = vc1->mLeaves.begin();
+
+        for (; *it != leaf; ++ it);
+        vc1->mLeaves.erase(it);
+
+        /*vc1->GetPvs().mEntries.clear();
+        for (; it != vc1->mLeaves.end(); ++ it)
+        {
+                if (*it == leaf)
+                        vc1->mLeaves.erase(it);
+                else
+                        vc1->GetPvs().AddPvs(*(*it)->mPvs);
+        }*/
+
+        leaf->SetViewCell(vc2);         // finally change view cell
+        
+        //Debug << "new pvs: " << vc1->GetPvs().GetSize() + vc2->GetPvs().GetSize() 
+        //        << " (" << vc1->GetPvs().GetSize() << ", " << vc2->GetPvs().GetSize() << ")" << endl;
+
+}
+
+
+bool VspBspTree::ShuffleLeaves(BspLeaf *leaf1, BspLeaf *leaf2) const
+{
+        BspViewCell *vc1 = leaf1->GetViewCell();
+        BspViewCell *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)
+        {
+                //Debug << "old cost: " << oldCost << ", new cost: " << shuffledCost1 << endl;
+                ShuffleLeaf(leaf1, vc1, vc2);
+                leaf1->Mail();
+        }
+        else
+        {
+                //Debug << "old cost: " << oldCost << ", new cost: " << shuffledCost2 << endl;
+                ShuffleLeaf(leaf2, vc2, vc1);
+                leaf2->Mail();
+        }
+
+        return true;
+}
+
 
 /************************************************************************/
@@ -2220 +2518 @@
 }
 
+float BspMergeCandidate::GetCost(ViewCell *vc) const
+{
+        return vc->GetPvs().GetSize() * vc->GetArea();
+}
+
 float BspMergeCandidate::GetLeaf1Cost() const
 {
         BspViewCell *vc = mLeaf1->GetViewCell();
-        return vc->GetPvs().GetSize() * vc->GetArea();
+        return GetCost(vc);
 }
 
@@ -2229 +2532 @@
 {
         BspViewCell *vc = mLeaf2->GetViewCell();
-        return vc->GetPvs().GetSize() * vc->GetVolume();
+        return GetCost(vc);
 }
 
@@ -2239 +2542 @@
 
         const int diff1 = vc1->GetPvs().Diff(vc2->GetPvs());
-        const int vcPvs = diff1 + vc1->GetPvs().GetSize();
+        const int newPvs = diff1 + vc1->GetPvs().GetSize();
 
         //-- compute ratio of old cost
@@ -2247 +2550 @@
 
         const float newCost =
-                (float)vcPvs * (vc1->GetArea() + vc2->GetArea());
+                (float)newPvs * (vc1->GetArea() + vc2->GetArea());
 
         mMergeCost = newCost - oldCost;
-
 //      if (vcPvs > sMaxPvsSize) // strong penalty if pvs size too large
 //              mMergeCost += 1.0;
@@ -2294 +2596 @@
         EvalMergeCost();
 }
+
+
+/************************************************************************/
+/*                  MergeStatistics implementation                      */
+/************************************************************************/
+
+
+void MergeStatistics::Print(ostream &app) const
+{
+        app << "===== Merge statistics ===============\n";
+
+        app << setprecision(4);
+
+        app << "#N_CTIME ( Overall time [s] )\n" << Time() << " \n";
+
+        app << "#N_CCTIME ( Collect candidates time [s] )\n" << collectTime * 1e-3f << " \n";
+
+        app << "#N_MTIME ( Merge time [s] )\n" << mergeTime * 1e-3f << " \n";
+
+        app << "#N_NODES ( Number of nodes before merge )\n" << nodes << "\n";
+
+        app << "#N_CANDIDATES ( Number of merge candidates )\n" << candidates << "\n";
+
+        app << "#N_MERGEDSIBLINGS ( Number of merged siblings )\n" << siblings << "\n";
+        app << "#N_MERGEDNODES ( Number of merged nodes )\n" << merged << "\n";
+
+        app << "#MAX_TREEDIST ( Maximal distance in tree of merged leaves )\n" << maxTreeDist << "\n";
+
+        app << "#AVG_TREEDIST ( Average distance in tree of merged leaves )\n" << AvgTreeDist() << "\n";
+
+        app << "===== END OF BspTree statistics ==========\n";
+}

trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.h

@@ -21 +21 @@
 class ViewCellsStatistics;
 class ViewCellsManager;
+class BspMergeCandidate;
+struct BspRay;
 
 
@@ -222 +224 @@
         BspLeaf *GetRandomLeaf(const bool onlyUnmailed = false);
 
-        /** Returns view cell corresponding to unbounded space.
-        */
-        BspViewCell *GetRootCell() const;
-
         /** Returns epsilon of this tree.
         */
         float GetEpsilon() const;
 
-
+        /** Casts line segment into the tree.
+                @param origin the origin of the line segment
+                @param termination the end point of the line segment
+                @returns view cells intersecting the line segment.
+        */
     int CastLineSegment(const Vector3 &origin,
                                                 const Vector3 &termination,
                                                 ViewCellContainer &viewcells);
 
-        /** Merges leaves with similar PVS.
-        */
-        int MergeLeaves();
                 
         /** Sets pointer to view cells manager.
@@ -243 +242 @@
         void SetViewCellsManager(ViewCellsManager *vcm);
 
-        /** Helper function revalidating the view cell leaf list after merge.
-        */
-        void RepairVcLeafLists();
-
-        /** Collapses the tree with respect to the view cell partition.
-                @returns node of type leaf if the node could be collapsed, this node otherwise
+        /** Returns distance from node 1 to node 2.
+        */
+        int TreeDistance(BspNode *n1, BspNode *n2) const;
+
+        /** Merges view cells according to some cost heuristics.
+        */
+        int MergeViewCells(const VssRayContainer &rays);
+        
+        /** 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);
+
+        /** Collapses the tree with respect to the view cell partition,
+                i.e. leaves having the same view cell are collapsed.
+                @returns node of type leaf if the node could be collapsed, 
+                this node otherwise
         */
         BspNode *CollapseTree(BspNode *node);
-        
-
-        /** Returns distance from node 1 to node 2.
-        */
-        int TreeDistance(BspNode *n1, BspNode *n2);
+
+        /** Constructs bsp rays for post processing and visualization.
+        */
+        void ConstructBspRays(vector<BspRay *> &bspRays,
+                                                  const VssRayContainer &rays);
+
+        
+        /** Merge view cells of leaves l1 and l2.
+        */
+        bool MergeViewCells(BspLeaf *l1, BspLeaf *l2) const;
 
 protected:
@@ -286 +303 @@
         };
 
+        /** Shuffles the leaves, i.e., tests if exchanging
+                the leaves helps in improving the view cells.
+        */
+        bool ShuffleLeaves(BspLeaf *leaf1, BspLeaf *leaf2) const;
+
+        /** Helper function revalidating the view cell leaf list after merge.
+        */
+        void RepairVcLeafLists();
+
         /** Evaluates tree stats in the BSP tree leafs.
         */
@@ -478 +504 @@
 
 
+        /** Collects candidates for the merge in the merge queue.
+                @returns number of leaves in queue
+        */
+        int CollectMergeCandidates();
+        /** Collects candidates for the merge in the merge queue.
+                @returns number of leaves in queue
+        */
+        int CollectMergeCandidates(const VssRayContainer &rays);
+
         /** Take 3 ray endpoints, where two are minimum and one a maximum
                 point or the other way round.
@@ -484 +519 @@
 
         /** Take plane normal as plane normal and the midpoint of the ray.
-                PROBLEM: does not resemble any point where visibility is likely to change
+                PROBLEM: does not resemble any point where visibility is 
+                likely to change
         */
         Plane3 ChooseCandidatePlane2(const RayInfoContainer &rays) const;
 
-        /** Fit the plane between the two lines so that the plane has equal shortest 
-                distance to both lines.
+        /** Fit the plane between the two lines so that the plane 
+                has equal shortest distance to both lines.
         */
         Plane3 ChooseCandidatePlane3(const RayInfoContainer &rays) const;
   
-        /** Merge view cells of leaves l1 and l2.
-        */
-        bool MergeViewCells(BspLeaf *l1, BspLeaf *l2);
+        void ShuffleLeaf(BspLeaf *leaf, 
+                                         BspViewCell *vc1, 
+                                         BspViewCell *vc2) const;
 
         /// Pointer to the root of the tree
@@ -513 +549 @@
         /// box around the whole view domain
         AxisAlignedBox3 mBox;
-
-        /// view cell corresponding to unbounded space
-        BspViewCell *mRootCell;
 
         /// minimal number of rays before subdivision termination
@@ -574 +607 @@
         float mMergeMaxCostRatio;
 
-        ViewCellsManager *mViewCellsManager;
-
         // if rays should be stored in leaves
         bool mStoreRays;
+        
+        /// if only driving axis should be used for split
+        bool mOnlyDrivingAxis;
+
+        ViewCellsManager *mViewCellsManager;
 
         vector<SortableEntry> *mSplitCandidates;
 
-        bool mOnlyDrivingAxis;
-
+        typedef priority_queue<BspMergeCandidate> MergeQueue;
+        MergeQueue mMergeQueue;
+        
+        bool mUseRaysForMerge;
 
 private:
@@ -646 +684 @@
 
 protected:
-        
+
+        /** Cost of a view cell.
+        */
+        float GetCost(ViewCell *vc) const;
         /** Evaluates the merge costs of the leaves.
         */
@@ -661 +702 @@
 
 
+class MergeStatistics: public StatisticsBase
+{
+public:
+        
+        int merged;
+        int siblings;
+        int candidates;
+        int nodes;
+
+        int accTreeDist;
+        int maxTreeDist;
+        
+        Real collectTime;
+        Real mergeTime;
+
+        // Constructor
+        MergeStatistics() 
+        {
+                Reset();
+        }
+        
+        double AvgTreeDist() const {return (double)accTreeDist / (double)merged;}; 
+
+        void Reset() 
+        {
+                nodes = 0;
+                merged = 0;
+                siblings = 0;
+                candidates = 0;
+        
+                accTreeDist = 0;
+                maxTreeDist = 0;
+
+                collectTime = 0;
+                mergeTime = 0;
+        }
+
+        void Print(ostream &app) const;
+
+        friend ostream &operator<<(ostream &s, const MergeStatistics &stat) 
+        {
+                stat.Print(s);
+                return s;
+        } 
+};
+
 #endif

trunk/VUT/GtpVisibilityPreprocessor/src/VspKdTree.cpp

@@ -372 +372 @@
                                                          MergeCandidate::sMaxPvsSize);
 
-        // split type
-        char sname[128];
-        environment->GetStringValue("VspKdTree.splitType", sname);
-        string name(sname);
-
+        environment->GetBoolValue("VspKdTree.splitUseOnlyDrivingAxis", mOnlyDrivingAxis);
+
+        //-- output
         Debug << "======= vsp kd tree options ========" << endl;
         Debug << "max depth: "<< mTermMaxDepth << endl;
@@ -385 +383 @@
         Debug << "min size: " << mTermMinSize << endl;
 
+        Debug << "split type: ";
+
+        //-- split type
+        char sname[128];
+        environment->GetStringValue("VspKdTree.splitType", sname);
+        string name(sname);
+
         if (name.compare("regular") == 0)
         {
-                Debug << "using regular split" << endl;
+                Debug << "regular split" << endl;
                 splitType = ESplitRegular;
         }
@@ -394 +399 @@
                 if (name.compare("heuristic") == 0)
                 {
-                        Debug << "using heuristic split" << endl;
+                        Debug << "heuristic split" << endl;
                         splitType = ESplitHeuristic;
                 }
@@ -405 +410 @@
 
         mRoot = NULL;
-
         mSplitCandidates = new vector<SortableEntry>;
 }
@@ -1464 +1468 @@
         {
             // determine the side of this ray with respect to the plane
- float t;
- int side = in->ComputeRayIntersection(data.mRayData, t);
+                float t;
+                const int side = in->ComputeRayIntersection(data.mRayData, t);
 
                 if (side == 0)
@@ -2050 +2054 @@
                         }
 
-                        if (1) //matt TODO: REMOVE LATER
+                        if (0) //matt TODO: REMOVE LATER
                                 leaf->mRays.push_back(RayInfo(new VssRay(origin, termination, NULL, NULL, 0)));
 
@@ -2162 +2166 @@
         {
                 VspKdLeaf *leaf = *it;
-
+                ViewCell *vc = leaf->GetViewCell();
                 // no leaf is part of two merge candidates
-                if (!leaf->Mailed())
-                {
-                        leaf->Mail();
-
-                        vector<VspKdLeaf *> neighbors;
-                        FindNeighbors(leaf, neighbors, true);
-
-                        vector<VspKdLeaf *>::const_iterator nit,
-                                nit_end = neighbors.end();
-
-                        for (nit = neighbors.begin(); nit != nit_end; ++ nit)
-                        {
-                                // TODO: test if at least one ray goes from one leaf to the other
-                                MergeCandidate mc = MergeCandidate(leaf, *nit);
-                                mMergeQueue.push(mc);
-
-                                MergeCandidate::sOverallCost += mc.GetLeaf1Cost();
-                                MergeCandidate::sOverallCost += mc.GetLeaf2Cost();
-                        }
-                }
-        }
-}
-
-/*
+                leaf->Mail();
+                MergeCandidate::sOverallCost += 
+                        vc->GetVolume() * vc->GetPvs().GetSize();
+                vector<VspKdLeaf *> neighbors;
+                FindNeighbors(leaf, neighbors, true);
+
+                vector<VspKdLeaf *>::const_iterator nit,
+                        nit_end = neighbors.end();
+
+                for (nit = neighbors.begin(); nit != nit_end; ++ nit)
+                {
+                        mMergeQueue.push(MergeCandidate(leaf, *nit));
+                }
+        }
+}
+#if 0
 void VspKdTree::CollectMergeCandidates(const vector<VspKdRay *> &rays)
 {
@@ -2193 +2189 @@
 
         vector<VspKdIntersection>::const_iterator iit;
+        map<BspLeaf *, vector<BspLeaf*> candidateMap;
 
         for (int i = 0; i < (int)rays.size(); ++ i)
         {  
                 //VspKdLeaf::NewMail();
-
                 VspKdRay *ray = rays[i];
           
@@ -2214 +2210 @@
                 {
             BspLeaf *leaf = (*iit).mLeaf;
-                        
+                        leaf->Mail
                         // TODO: how to sort out doubles?
                         MergeCandidate mc = MergeCandidate(leaf, previousLeaf);
@@ -2226 +2222 @@
         }
 }
-*/
-
-int VspKdTree::MergeLeaves()
-{
+#endif
+
+int VspKdTree::MergeViewCells(const VssRayContainer &rays)
+{
+        CollectMergeCandidates();
+
         int merged = 0;
 
-        int vcSize = mStat.nodes / 2 + 1;
+        int vcSize = mStat.Leaves();
         // use priority queue to merge leaves
         while (!mMergeQueue.empty() && (vcSize > mMergeMinViewCells) &&
@@ -2238 +2236 @@
                     mMergeMaxCostRatio * MergeCandidate::sOverallCost))
         {
-                //Debug << "mergecost: " << mergeQueue.top().GetMergeCost() / MergeCandidate::sOverallCost << " " << mMergeMaxCostRatio << endl;
+                //Debug << "mergecost: " << mergeQueue.top().GetMergeCost() / 
+                //MergeCandidate::sOverallCost << " " << mMergeMaxCostRatio << endl;
                 MergeCandidate mc = mMergeQueue.top();
                 mMergeQueue.pop();
@@ -2267 +2266 @@
         }
 
-        // collapse siblings belonging to the same view cell
-        CollapseTree(mRoot);
-        // revalidate leaves
-        RepairVcLeafLists();
-
-        Debug << "merged " << merged << " of " << mStat.nodes / 2 + 1 << " leaves" << endl;
+        Debug << "merged " << merged << " of " << mStat.Leaves() << " leaves" << endl;
 
         //TODO: should return sample contributions
@@ -2350 +2344 @@
         }
 
+        // revalidate leaves
+        RepairVcLeafLists();
+
         return node;
 }
@@ -2356 +2353 @@
 void VspKdTree::RefineViewCells()
 {
+        //TODO
 }
 

trunk/VUT/GtpVisibilityPreprocessor/src/VspKdTree.h

@@ -285 +285 @@
         */
         void SetupChildLinks(VspKdNode *b, VspKdNode *f);
-
         /** Replaces the pointer to oldChild with a pointer to newChild.
         */
         void ReplaceChildLink(VspKdNode *oldChild, VspKdNode *newChild);
- 
         /** Computes intersection of the ray with the node boundaries.
         */
@@ -568 +566 @@
         */
         float GetMemUsage() const;
-        
+        //?
         float GetRayMemUsage() const;
 
@@ -575 +573 @@
         void CollectLeaves(vector<VspKdLeaf *> &leaves) const;
 
-        /** Merges leaves of this tree according to some criteria.
-        */
-        int MergeLeaves();
+        /** Merges view cells created with this tree according to 
+                some (global) cost heuristics.
+        */
+        int MergeViewCells(const VssRayContainer &rays);
 
         /** Finds neighbours of this node.
@@ -604 +603 @@
         */
         void CollectViewCells(ViewCellContainer &viewCells) const;
-
         /** Refines view cells in a post processing step.
         */
@@ -612 +610 @@
         */
         void CollectMergeCandidates();
+
+        /** Collapses the tree with respect to the view cell partition.
+                @returns node of type leaf if the node could be collapsed, this node otherwise
+        */
+        VspKdNode *CollapseTree(VspKdNode *node);
 
 protected:
@@ -718 +721 @@
         */
         bool MergeViewCells(VspKdLeaf *l1, VspKdLeaf *l2);
-
-        /** Collapses the tree with respect to the view cell partition.
-                @returns node of type leaf if the node could be collapsed, this node otherwise
-        */
-        VspKdNode *CollapseTree(VspKdNode *node);
         
         /** Helper function revalidating the view cell leaf list after merge.

trunk/VUT/GtpVisibilityPreprocessor/src/VssPreprocessor.cpp

@@ -558 +558 @@
 
         //-- several visualizations and statistics
-        Debug << "view cells after post processing: " << endl;
+        Debug << "\nview cells after post processing: " << endl;
         mViewCellsManager->PrintStatistics(Debug);
 

trunk/VUT/GtpVisibilityPreprocessor/src/VssTree.cpp

@@ -558 +558 @@
 #if 1
         float newCost = raysBack*pvsBack  + raysFront*pvsFront;
-        float oldCost = leaf->rays.size()*pvsSize;
+        float oldCost = (float)leaf->rays.size()*pvsSize;
         ratio = newCost/oldCost;
 #else