Changeset 462

Timestamp:

12/13/05 17:28:02 (19 years ago)

Author:

mattausch

Message:

worked on vsp kd view cells

Location:

trunk/VUT/GtpVisibilityPreprocessor

Files:

• scripts/default.env (modified) (4 diffs)
• src/Environment.cpp (modified) (1 diff)
• src/Exporter.h (modified) (1 diff)
• src/KdTree.cpp (modified) (1 diff)
• src/Preprocessor.cpp (modified) (1 diff)
• src/RenderSimulator.cpp (modified) (1 diff)
• src/RssPreprocessor.cpp (modified) (1 diff)
• src/SamplingPreprocessor.cpp (modified) (2 diffs)
• src/ViewCell.cpp (modified) (2 diffs)
• src/ViewCell.h (modified) (4 diffs)
• src/ViewCellBsp.cpp (modified) (5 diffs)
• src/ViewCellBsp.h (modified) (3 diffs)
• src/ViewCellsManager.cpp (modified) (18 diffs)
• src/ViewCellsManager.h (modified) (5 diffs)
• src/VspBspTree.cpp (modified) (3 diffs)
• src/VspBspTree.h (modified) (2 diffs)
• src/VspKdTree.cpp (modified) (64 diffs)
• src/VspKdTree.h (modified) (38 diffs)
• src/VssPreprocessor.cpp (modified) (1 diff)
• src/X3dExporter.cpp (modified) (5 diffs)
• src/X3dExporter.h (modified) (8 diffs)

trunk/VUT/GtpVisibilityPreprocessor/scripts/default.env

@@ -25 +25 @@
 
 VssPreprocessor {
-        samplesPerPass  10000
-        initialSamples 100000
-        vssSamples 300000
-        vssSamplesPerPass 10000
+        samplesPerPass  100000
+        initialSamples 1000000
+        vssSamples 3000000
+        vssSamplesPerPass 100000
         useImportanceSampling true
 }
@@ -153 +153 @@
         
         height 5.0
-        maxViewCells 0
+        maxViewCells 5000
         
         PostProcessing {
@@ -284 +284 @@
         Termination {
                 maxDepth                40
-                minPvs                  40
-                minRays                 100
+                minPvs                  90
+                minRays                 10
                 minSize                 0.1
                 maxCostRatio            999.0
@@ -297 +297 @@
         #splitType      heuristics
         ct_div_ci       0.0
+        
+        # maximal cost for merging a view cell
+        maxCostRatio 1.4
 }
 

trunk/VUT/GtpVisibilityPreprocessor/src/Environment.cpp

@@ -1395 +1395 @@
   RegisterOption("VspKdTree.Construction.samples",
                  optInt,
-                 "-vsp_construction_samples=",
+                 "-vsp_kd_construction_samples=",
                  "100000");
+
+  RegisterOption("VspKdTree.maxCostRatio",
+                 optFloat,
+                 "-vsp_kd_max_cost_ratio=",
+                 "1.5");
 
   RegisterOption("VspKdTree.Termination.maxDepth", 

trunk/VUT/GtpVisibilityPreprocessor/src/Exporter.h

@@ -119 +119 @@
                                  const Vector3 direction) = 0;
 
+  virtual bool 
+  ExportVspKdTreeViewCells(const VspKdTree &tree, const int maxPvs = 0) = 0;
+
   void SetExportRayDensity(const bool d) { mExportRayDensity = d; }
   

trunk/VUT/GtpVisibilityPreprocessor/src/KdTree.cpp

@@ -502 +502 @@
 int
 KdTree::CastRay(
-                                                                Ray &ray
-                                                                )
+                                Ray &ray
+                                )
 {
   int hits = 0;

trunk/VUT/GtpVisibilityPreprocessor/src/Preprocessor.cpp

@@ -23 +23 @@
 Preprocessor::~Preprocessor()
 {
+        DEL_PTR(mViewCellsManager);
+
         DEL_PTR(mBspTree);
         DEL_PTR(mKdTree);
         DEL_PTR(mVspKdTree);
         DEL_PTR(mVspBspTree);
-        DEL_PTR(mViewCellsManager);
 }
 

trunk/VUT/GtpVisibilityPreprocessor/src/RenderSimulator.cpp

@@ -239 +239 @@
 }
 
-/********************************************************/
-/*     class BspRenderSimulator implementation          */
-/********************************************************/
+/**********************************************************/
+/*       class BspRenderSimulator implementation          */
+/**********************************************************/
 
 VspBspRenderSimulator::VspBspRenderSimulator(VspBspTree *vspBspTree):

trunk/VUT/GtpVisibilityPreprocessor/src/RssPreprocessor.cpp

@@ -627 +627 @@
 
   //-- several visualizations and statistics
-  Debug << "===== Final view cells statistics ==========" << endl;
-
   mViewCellsManager->PrintStatistics(Debug);
 

trunk/VUT/GtpVisibilityPreprocessor/src/SamplingPreprocessor.cpp

@@ -398 +398 @@
         
         //-- several visualizations and statistics
-        Debug << "===== Final view cells statistics ==========" << endl;
-
         mViewCellsManager->PrintStatistics(Debug);
 
@@ -412 +410 @@
         
         mViewCellsManager->Visualize(objects, mSampleRays);     
-    
+   
         return true;
 }

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCell.cpp

@@ -4 +4 @@
 #include "MeshKdTree.h"
 #include "Triangle3.h"
+#include <time.h>
+#include <iomanip>
 
 ViewCell::ViewCell(): MeshInstance(NULL), mPiercingRays(0)
@@ -32 +34 @@
         mPassingRays.AddRay(ray, contributions);
 }
+
+/************************************************************************/
+/*                class ViewCellsStatistics implementation              */
+/************************************************************************/
+
+void ViewCellsStatistics::Print(ostream &app) const
+{
+        app << "=========== View Cells Statistics ===============\n";
+
+        app << setprecision(4);
+
+        //app << "#N_CTIME  ( Construction time [s] )\n" << Time() << " \n";
+
+        app << "#N_OVERALLPVS ( objects in PVS )\n" << pvs << endl;
+
+        app << "#N_PMAXPVS ( largest PVS )\n" << maxPvs << endl;
+
+        app << "#N_PMINPVS ( smallest PVS )\n" << minPvs << endl;
+
+        app << "#N_PAVGPVS ( average PVS )\n" << AvgPvs() << endl;
+
+        app << "#N_PEMPTYPVS ( view cells with PVS smaller 2 )\n" << emptyPvs << endl;
+
+        app << "#N_VIEWCELLS ( number of view cells)\n" << viewCells << endl;
+
+        app << "#N_AVGLEAVES (average number of leaves per view cell )\n" << AvgLeaves() << endl;
+
+        app << "#N_MAXLEAVES ( maximal number of leaves per view cell )\n" << maxLeaves << endl;
+        
+        app << "========== End of View Cells Statistics ==========\n";
+}

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCell.h

@@ -5 +5 @@
 #include "Containers.h"
 #include "Ray.h"
-
+#include "Statistics.h"
 //namespace GtpVisibilityPreprocessor {
   
@@ -13 +13 @@
 class BspLeaf;
 class VspKdTree;
-class VspKdTreeLeaf;
+class VspKdLeaf;
+
 
 /**
@@ -22 +23 @@
 public:
         ViewCell();
+        
         /** Constructor taking a mesh representing the shape of the viewcell.
         */
         ViewCell(Mesh *mesh);
+
+
+        virtual ~ViewCell() {}
         /** Returns Pvs. 
         */
@@ -67 +72 @@
         ViewCell(mesh), mVspKdLeaves(0) {}
 
-        float GetSize() {return 0;}
+        float GetSize() {return mSize;}
         void SetSize(float size) {mSize = size;}
 
         /// Leaves which hold this view cell.
-        vector<VspKdTreeLeaf *> mVspKdLeaves;
+        vector<VspKdLeaf *> mVspKdLeaves;
 
 protected:
         float mSize;
 };
+
+class ViewCellsStatistics: public StatisticsBase
+{
+public:
+
+        /// number of view cells
+        int viewCells;
+
+        /// size of the PVS
+        int pvs;
+  
+        /// largest PVS of all view cells
+        int maxPvs;
+
+        /// smallest PVS of all view cells
+        int minPvs;
+
+        /// view cells with empty PVS
+        int emptyPvs;
+
+        /// number of leaves covering the view space
+        int leaves;
+
+        /// largest number of leaves covered by one view cell  
+        int maxLeaves;
+
+    // Constructor
+        ViewCellsStatistics() 
+        {
+                Reset();
+        }
+
+        double AvgLeaves() const {return (double)leaves / (double)viewCells;};
+        double AvgPvs() const {return (double)pvs / (double)viewCells;};
+  
+        void Reset() 
+        {
+                viewCells = 0;  
+                pvs = 0;  
+                maxPvs = 0;
+
+                minPvs = 999999;
+                emptyPvs = 0;
+                leaves = 0;
+                maxLeaves = 0;
+        }
+
+        void Print(ostream &app) const;
+
+        friend ostream &operator<<(ostream &s, const ViewCellsStatistics &stat) 
+        {
+                stat.Print(s);
+                return s;
+        }  
+};
+
 #endif

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp

@@ -9 +9 @@
 #include "AxisAlignedBox3.h"
 #include <stack>
-#include <time.h>
-#include <iomanip>
+
 #include "Exporter.h"
 #include "Plane3.h"
@@ -1907 +1906 @@
 }
 
-void BspTree::EvaluateViewCellsStats(BspViewCellsStatistics &stat) const
-{
-        stat.Reset();
+void BspTree::EvaluateViewCellsStats(ViewCellsStatistics &vcStat) const
+{
+        vcStat.Reset();
 
         stack<BspNode *> nodeStack;
@@ -1926 +1925 @@
                 if (node->IsLeaf()) 
                 {
-                        ++ stat.bspLeaves;
+                        ++ vcStat.leaves;
 
                         BspViewCell *viewCell = dynamic_cast<BspLeaf *>(node)->mViewCell;
@@ -1934 +1933 @@
                                 viewCell->Mail();
                                 
-                                ++ stat.viewCells;
+                                ++ vcStat.viewCells;
                                 const int pvsSize = viewCell->GetPvs().GetSize();
 
-                stat.pvs += pvsSize;
+                vcStat.pvs += pvsSize;
 
                                 if (pvsSize < 1)
-                                        ++ stat.emptyPvs;
-
-                                if (pvsSize > stat.maxPvs)
-                                        stat.maxPvs = pvsSize;
-
-                                if (pvsSize < stat.minPvs)
-                                        stat.minPvs = pvsSize;
-
-                                if ((int)viewCell->mBspLeaves.size() > stat.maxBspLeaves)
-                                        stat.maxBspLeaves = (int)viewCell->mBspLeaves.size();           
+                                        ++ vcStat.emptyPvs;
+
+                                if (pvsSize > vcStat.maxPvs)
+                                        vcStat.maxPvs = pvsSize;
+
+                                if (pvsSize < vcStat.minPvs)
+                                        vcStat.minPvs = pvsSize;
+
+                                if ((int)viewCell->mBspLeaves.size() > vcStat.maxLeaves)
+                                        vcStat.maxLeaves = (int)viewCell->mBspLeaves.size();            
                         }
                 }
@@ -2412 +2411 @@
 }
 
-void BspViewCellsStatistics::Print(ostream &app) const
-{
-        app << "===== BspViewCells statistics ===============\n";
-
-        app << setprecision(4);
-
-        //app << "#N_CTIME  ( Construction time [s] )\n" << Time() << " \n";
-
-        app << "#N_OVERALLPVS ( objects in PVS )\n" << pvs << endl;
-
-        app << "#N_PMAXPVS ( largest PVS )\n" << maxPvs << endl;
-
-        app << "#N_PMINPVS ( smallest PVS )\n" << minPvs << endl;
-
-        app << "#N_PAVGPVS ( average PVS )\n" << AvgPvs() << endl;
-
-        app << "#N_PEMPTYPVS ( view cells with PVS smaller 2 )\n" << emptyPvs << endl;
-
-        app << "#N_VIEWCELLS ( number of view cells)\n" << viewCells << endl;
-
-        app << "#N_AVGBSPLEAVES (average number of BSP leaves per view cell )\n" << AvgBspLeaves() << endl;
-
-        app << "#N_MAXBSPLEAVES ( maximal number of BSP leaves per view cell )\n" << maxBspLeaves << endl;
-        
-        app << "===== END OF BspViewCells statistics ==========\n";
-}
 
 /*************************************************************/

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.h

@@ -18 +18 @@
 class AxisAlignedBox3;
 class Ray;
+class ViewCellsStatistics;
 
 class BspNodeGeometry
@@ -157 +158 @@
 };
 
-class BspViewCellsStatistics: public StatisticsBase
-{
-public:
-
-        /// number of view cells
-        int viewCells;
-
-        /// size of the PVS
-        int pvs;
-  
-        /// largest PVS of all view cells
-        int maxPvs;
-
-        /// smallest PVS of all view cells
-        int minPvs;
-
-        /// view cells with empty PVS
-        int emptyPvs;
-
-        /// number of bsp leaves covering the view space
-        int bspLeaves;
-
-        /// largest number of leaves covered by one view cell  
-        int maxBspLeaves;
-
-    // Constructor
-        BspViewCellsStatistics() 
-        {
-                Reset();
-        }
-
-        double AvgBspLeaves() const {return (double)bspLeaves / (double)viewCells;};
-        double AvgPvs() const {return (double)pvs / (double)viewCells;};
-  
-        void Reset() 
-        {
-                viewCells = 0;  
-                pvs = 0;  
-                maxPvs = 0;
-
-                minPvs = 999999;
-                emptyPvs = 0;
-                bspLeaves = 0;
-                maxBspLeaves = 0;
-        }
-
-        void Print(ostream &app) const;
-
-        friend ostream &operator<<(ostream &s, const BspViewCellsStatistics &stat) 
-        {
-                stat.Print(s);
-                return s;
-        }  
-};
 
 /**
@@ -499 +446 @@
         /** Traverses tree and counts all view cells as well as their PVS size.
         */
-        void EvaluateViewCellsStats(BspViewCellsStatistics &stat) const;
+        void EvaluateViewCellsStats(ViewCellsStatistics &stat) const;
 
         /** Returns view cell corresponding to unbounded space.

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellsManager.cpp

@@ -154 +154 @@
 ViewCell *ViewCellsManager::MergeViewCells(ViewCell &front, ViewCell &back) const
 {
+        // generate merged view cell
         ViewCell *vc = GenerateViewCell();
+
         // merge pvs
         vc->GetPvs().Merge(front.GetPvs(), back.GetPvs());
 
-        // merge ray sets
+        //-- merge ray sets
         stable_sort(front.mPiercingRays.begin(), front.mPiercingRays.end());
         stable_sort(back.mPiercingRays.begin(), back.mPiercingRays.end());
@@ -223 +225 @@
    mRenderSimulator = new BspRenderSimulator(bspTree);
    InitRenderSimulator();
+}
+
+
+BspViewCellsManager::~BspViewCellsManager()
+{
+        ViewCellContainer vc;
+        mBspTree->CollectViewCells(vc);
+
+        CLEAR_CONTAINER(vc);
 }
 
@@ -336 +347 @@
         int pvsSize = 0;
 
-        BspViewCellsStatistics vcStats;
+        ViewCellsStatistics vcStats;
         mBspTree->EvaluateViewCellsStats(vcStats);
         Debug << "original view cell partition:\n" << vcStats << endl;
@@ -438 +449 @@
 
         //-- recount pvs
-        BspViewCellsStatistics vcStats;
+        ViewCellsStatistics vcStats;
         mBspTree->EvaluateViewCellsStats(vcStats);
 
@@ -721 +732 @@
                 return false;
 
-        // change view cells of all leaves associated with the
-        // previous view cells
-
+        //-- change pointer to view cells of all leaves associated with the previous view cells
         BspViewCell *fVc = front->GetViewCell();
         BspViewCell *bVc = back->GetViewCell();
@@ -774 +783 @@
 void BspViewCellsManager::PrintStatistics(ostream &s) const
 {
-        BspViewCellsStatistics vcStats;
+        ViewCellsStatistics vcStats;
         mBspTree->EvaluateViewCellsStats(vcStats);
         s << vcStats << endl;
@@ -973 +982 @@
 /**********************************************************************/
 
-VspKdViewCellsManager::VspKdViewCellsManager(VspKdTree *vspKdTree, int constructionSamples):
+VspKdViewCellsManager::VspKdViewCellsManager(VspKdTree *vspKdTree, 
+                                                                                         int constructionSamples):
 ViewCellsManager(constructionSamples), 
 mVspKdTree(vspKdTree)
 {
    mRenderSimulator = new VspKdRenderSimulator(vspKdTree);
+   mVspKdTree->SetViewCellsManager(this);
+
    InitRenderSimulator();
 }
+
+
+VspKdViewCellsManager::~VspKdViewCellsManager()
+{
+        ViewCellContainer vc;
+        mVspKdTree->CollectViewCells(vc);
+
+        CLEAR_CONTAINER(vc);
+}
+
 
 int VspKdViewCellsManager::Construct(const ObjectContainer &objects, 
@@ -1015 +1037 @@
                 return 0;
 
-        //if (castRay)
-                //mVspKdTree->CastRay(ray);
+        if (castRay)
+                mVspKdTree->CastRay(ray);
 
         int sampleContributions = 0;
 
         return sampleContributions;
+}
+
+ViewCell *VspKdViewCellsManager::GenerateViewCell(Mesh *mesh) const
+{
+        return new VspKdViewCell(mesh);
 }
 
@@ -1029 +1056 @@
                 return 0;
 
-        return 0;
+        return mVspKdTree->MergeLeaves();
 }
 
@@ -1043 +1070 @@
                 Exporter *exporter = Exporter::GetExporter("vspkdtree.x3d"); 
                 //exporter->SetWireframe();
-                exporter->ExportVspKdTree(*mVspKdTree, mVspKdTree->GetStatistics().maxPvsSize);
-
-                Debug << "average PVS size: " << mVspKdTree->GetAvgPvsSize() << endl;
+                //exporter->ExportVspKdTree(*mVspKdTree, mVspKdTree->GetStatistics().maxPvsSize);
+                exporter->ExportVspKdTree(*mVspKdTree);
 
                 if (0) 
@@ -1073 +1099 @@
         }
 
+        //-- export single leaves
         if (1)
         {
-                vector<VspKdTreeLeaf *> leafContainer;
-
+                vector<VspKdLeaf *> leafContainer;
                 mVspKdTree->CollectLeaves(leafContainer);
 
@@ -1086 +1112 @@
 
                         // export geometry
-                        VspKdTreeLeaf *leaf = leafContainer[Random((int)leafContainer.size())]; 
+                        VspKdLeaf *leaf = leafContainer[Random((int)leafContainer.size())]; 
                         AxisAlignedBox3 box = mVspKdTree->GetBBox(leaf);
 
@@ -1116 +1142 @@
                 }                       
         }
+
+        // evaluate maximal pvs
+        ViewCellsStatistics vcStats;
+        mVspKdTree->EvaluateViewCellsStats(vcStats);
+        
+        //-- export final view cells
+        Exporter *exporter = Exporter::GetExporter("vspkdtree_merged.x3d"); 
+        //exporter->SetWireframe();
+        //exporter->ExportVspKdTreeViewCells(*mVspKdTree, vcStats.maxPvs);
+        exporter->ExportVspKdTreeViewCells(*mVspKdTree);
+
+        Debug << "average PVS size: " << mVspKdTree->GetAvgPvsSize() << endl;
+
+        if (0) 
+                exporter->ExportGeometry(objects);
+
+        bool exportRays = false;
+
+        if (exportRays) 
+        {
+                int raysSize = 2000;
+                float prob = raysSize / (float)sampleRays.size();
+                
+                exporter->SetWireframe();
+                        
+                RayContainer rays;
+                
+                for (int i = 0; i < sampleRays.size(); ++ i)
+                {
+                        if (RandomValue(0,1) < prob)
+                                rays.push_back(sampleRays[i]);
+                }
+                exporter->ExportRays(rays, 1000, RgbColor(1, 0, 0));
+        }
+
+        delete exporter;
 }
 
@@ -1125 +1187 @@
 void VspKdViewCellsManager::PrintStatistics(ostream &s) const
 {
+        ViewCellsStatistics vcStats;
+
+        mVspKdTree->EvaluateViewCellsStats(vcStats);
+        Debug << vcStats << endl;
 }
 
@@ -1141 +1207 @@
 }
 
+
+
+VspBspViewCellsManager::~VspBspViewCellsManager()
+{
+        ViewCellContainer vc;
+        mVspBspTree->CollectViewCells(vc);
+
+        CLEAR_CONTAINER(vc);
+}
+
 bool VspBspViewCellsManager::ViewCellsConstructed() const
 {
         return mVspBspTree->GetRoot() != NULL;
 }
+
 
 ViewCell *VspBspViewCellsManager::GenerateViewCell(Mesh *mesh) const
@@ -1247 +1324 @@
 
         
-        BspViewCellsStatistics vcStats;
+        ViewCellsStatistics vcStats;
         mVspBspTree->EvaluateViewCellsStats(vcStats);
         Debug << "original view cell partition:\n" << vcStats << endl;
@@ -1340 +1417 @@
 
         //-- recount pvs
-        BspViewCellsStatistics vcStats;
+        ViewCellsStatistics vcStats;
         mVspBspTree->EvaluateViewCellsStats(vcStats);
 
@@ -1628 +1705 @@
 void VspBspViewCellsManager::PrintStatistics(ostream &s) const
 {
-        BspViewCellsStatistics vcStats;
+        ViewCellsStatistics vcStats;
         mVspBspTree->EvaluateViewCellsStats(vcStats);
         s << vcStats << endl;

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellsManager.h

@@ -39 +39 @@
         ViewCellsManager();
 
-        ~ViewCellsManager();
+        virtual ~ViewCellsManager();
 
         /** Constructs view cell container with a given number of samples.
@@ -221 +221 @@
         void PrintStatistics(ostream &s) const;
 
+        ~BspViewCellsManager();
 protected:
 
@@ -303 +304 @@
         VspKdViewCellsManager(VspKdTree *vspKdTree, int constructionSamples);
 
+        ~VspKdViewCellsManager();
+
         int Construct(const ObjectContainer &objects, 
                                   const VssRayContainer &rays,
@@ -321 +324 @@
         virtual void PrintStatistics(ostream &s) const;
 
+        ViewCell *GenerateViewCell(Mesh *mesh) const;
+
 protected:
 
@@ -338 +343 @@
 
         VspBspViewCellsManager(VspBspTree *tree, int constructionSamples);
+
+        ~VspBspViewCellsManager();
 
         int Construct(const ObjectContainer &objects, 

trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.cpp

@@ -1220 +1220 @@
 }
 
-void VspBspTree::EvaluateViewCellsStats(BspViewCellsStatistics &stat) const
+void VspBspTree::EvaluateViewCellsStats(ViewCellsStatistics &stat) const
 {
         stat.Reset();
@@ -1239 +1239 @@
                 if (node->IsLeaf()) 
                 {
-                        ++ stat.bspLeaves;
+                        ++ stat.leaves;
 
                         BspViewCell *viewCell = dynamic_cast<BspLeaf *>(node)->GetViewCell();
@@ -1261 +1261 @@
                                         stat.minPvs = pvsSize;
 
-                                if ((int)viewCell->mBspLeaves.size() > stat.maxBspLeaves)
-                                        stat.maxBspLeaves = (int)viewCell->mBspLeaves.size();           
+                                if ((int)viewCell->mBspLeaves.size() > stat.maxLeaves)
+                                        stat.maxLeaves = (int)viewCell->mBspLeaves.size();              
                         }
                 }

trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.h

@@ -19 +19 @@
 class AxisAlignedBox3;
 class Ray;
+class ViewCellsStatistics;
 
 /*class BspNodeGeometry;
 class BspTreeStatistics;
-class BspViewCellsStatistics;
+class ViewCellsStatistics;
 class BspNode;
 class BspLeaf;
@@ -196 +197 @@
         /** Traverses tree and counts all view cells as well as their PVS size.
         */
-        void EvaluateViewCellsStats(BspViewCellsStatistics &stat) const;
+        void EvaluateViewCellsStats(ViewCellsStatistics &stat) const;
 
 

trunk/VUT/GtpVisibilityPreprocessor/src/VspKdTree.cpp

@@ -25 +25 @@
 #include "Ray.h"
 #include "RayInfo.h"
+#include "ViewCell.h"
 #include "ViewCellsManager.h"
-#include "ViewCell.h"
+#include "ViewCellBsp.h"
 
 // Static variables
-int VspKdTreeLeaf::mailID = 0;
+int VspKdLeaf::sMailId = 0;
+int MergeCandidate::sMaxPvsSize = 150;
+
 
 #define USE_FIXEDPOINT_T 0
@@ -70 +73 @@
 
 /**************************************************************/
-/*                class VspKdTreeNode implementation          */
+/*                class VspKdNode implementation          */
 /**************************************************************/
 
 // Inline constructor
-VspKdTreeNode::VspKdTreeNode(VspKdTreeInterior *p):
+VspKdNode::VspKdNode(VspKdInterior *p):
 mParent(p), mAxis(-1), mDepth(p ? p->mDepth + 1 : 0) 
 {}
 
-VspKdTreeNode::~VspKdTreeNode() 
+VspKdNode::~VspKdNode() 
 {};
 
-inline VspKdTreeInterior *VspKdTreeNode::GetParent() const
+inline VspKdInterior *VspKdNode::GetParent() const
 {
         return mParent;
 }
 
-inline void VspKdTreeNode::SetParent(VspKdTreeInterior *p)
+inline void VspKdNode::SetParent(VspKdInterior *p)
 {
         mParent = p;
 }
 
-bool VspKdTreeNode::IsLeaf() const 
+bool VspKdNode::IsLeaf() const 
 { 
         return mAxis == -1; 
 }
   
-int VspKdTreeNode::GetAccessTime() 
+int VspKdNode::GetAccessTime() 
 {
         return 0x7FFFFFF;
@@ -102 +105 @@
 
 /**************************************************************/
-/*                VspKdTreeInterior implementation            */
+/*                VspKdInterior implementation            */
 /**************************************************************/
 
-VspKdTreeInterior::VspKdTreeInterior(VspKdTreeInterior *p):
-VspKdTreeNode(p), mBack(NULL), mFront(NULL), mAccesses(0), mLastAccessTime(-1)
-{
-}
-
-int VspKdTreeInterior::GetAccessTime()
+VspKdInterior::VspKdInterior(VspKdInterior *p):
+VspKdNode(p), mBack(NULL), mFront(NULL), mAccesses(0), mLastAccessTime(-1)
+{
+}
+
+int VspKdInterior::GetAccessTime()
 {
         return mLastAccessTime;
 }
 
-void VspKdTreeInterior::SetupChildLinks(VspKdTreeNode *b, VspKdTreeNode *f) 
+void VspKdInterior::SetupChildLinks(VspKdNode *b, VspKdNode *f) 
 {
         mBack = b;
@@ -123 +126 @@
 }
 
-void VspKdTreeInterior::ReplaceChildLink(VspKdTreeNode *oldChild, 
-                                                                                 VspKdTreeNode *newChild)
+void VspKdInterior::ReplaceChildLink(VspKdNode *oldChild, 
+                                                                                 VspKdNode *newChild)
 {
         if (mBack == oldChild)
@@ -132 +135 @@
 }
 
-int VspKdTreeInterior::Type() const  
+int VspKdInterior::Type() const  
 { 
         return EInterior; 
 }
   
-VspKdTreeInterior::~VspKdTreeInterior()
+VspKdInterior::~VspKdInterior()
 {
         DEL_PTR(mBack);
@@ -143 +146 @@
 }
   
-void VspKdTreeInterior::Print(ostream &s) const 
+void VspKdInterior::Print(ostream &s) const 
 {
         switch (mAxis)
@@ -161 +164 @@
 }
         
-int VspKdTreeInterior::ComputeRayIntersection(const RayInfo &rayData, float &t) 
+int VspKdInterior::ComputeRayIntersection(const RayInfo &rayData, float &t) 
 {
         return rayData.ComputeRayIntersection(mAxis, mPosition, t);
 }
 
-VspKdTreeNode *VspKdTreeInterior::GetBack() const
+VspKdNode *VspKdInterior::GetBack() const
 {
         return mBack;
 }
 
-VspKdTreeNode *VspKdTreeInterior::GetFront() const
+VspKdNode *VspKdInterior::GetFront() const
 {
         return mFront;
@@ -178 +181 @@
 
 /**************************************************************/
-/*              class VspKdTreeLeaf implementation            */
+/*              class VspKdLeaf implementation            */
 /**************************************************************/
-VspKdTreeLeaf::VspKdTreeLeaf(VspKdTreeInterior *p,      const int nRays):
-VspKdTreeNode(p), mRays(), mPvsSize(0), mValidPvs(false), mViewCell(NULL)
+
+
+VspKdLeaf::VspKdLeaf(VspKdInterior *p,  const int nRays):
+VspKdNode(p), mRays(), mPvsSize(0), mValidPvs(false), mViewCell(NULL)
 {
         mRays.reserve(nRays);
 }
 
-VspKdTreeLeaf::~VspKdTreeLeaf() 
-{}
-
-int VspKdTreeLeaf::Type() const  
+VspKdLeaf::~VspKdLeaf() 
+{
+}
+
+int VspKdLeaf::Type() const  
 { 
         return ELeaf; 
 }
 
-void VspKdTreeLeaf::Print(ostream &s) const 
+void VspKdLeaf::Print(ostream &s) const 
 {
         s << endl << "L: r = " << (int)mRays.size() << endl;
 };
 
-void VspKdTreeLeaf::AddRay(const RayInfo &data) 
+void VspKdLeaf::AddRay(const RayInfo &data) 
 {
         mValidPvs = false;
@@ -206 +212 @@
 }
 
-int VspKdTreeLeaf::GetPvsSize() const 
+int VspKdLeaf::GetPvsSize() const 
 {
         return mPvsSize;
 }
 
-void VspKdTreeLeaf::SetPvsSize(const int s) 
+void VspKdLeaf::SetPvsSize(const int s) 
 {
         mPvsSize = s;
 }
 
-void VspKdTreeLeaf::Mail()
+void VspKdLeaf::Mail()
 { 
-        mMailbox = mailID; 
-}
-
-void VspKdTreeLeaf::NewMail() 
+        mMailbox = sMailId; 
+}
+
+void VspKdLeaf::NewMail() 
 { 
-        ++ mailID; 
-}
-
-bool VspKdTreeLeaf::Mailed() const 
+        ++ sMailId; 
+}
+
+bool VspKdLeaf::Mailed() const 
 { 
-        return mMailbox == mailID; 
-}
-
-bool VspKdTreeLeaf::Mailed(const int mail) 
-{
-        return mMailbox >= mailID + mail;
-}
-
-float VspKdTreeLeaf::GetAvgRayContribution() const 
+        return mMailbox == sMailId; 
+}
+
+bool VspKdLeaf::Mailed(const int mail) const
+{
+        return mMailbox == mail;
+}
+
+int VspKdLeaf::GetMailbox() const
+{
+        return mMailbox;
+}
+
+float VspKdLeaf::GetAvgRayContribution() const 
 {
         return GetPvsSize() / ((float)mRays.size() + Limits::Small);
 }
 
-float VspKdTreeLeaf::GetSqrRayContribution() const 
+float VspKdLeaf::GetSqrRayContribution() const 
 {
         return sqr(GetAvgRayContribution());
 }
 
-RayInfoContainer &VspKdTreeLeaf::GetRays()
+RayInfoContainer &VspKdLeaf::GetRays()
 {
         return mRays;
 }
 
-void VspKdTreeLeaf::ExtractPvs(ObjectContainer &objects) const
+void VspKdLeaf::ExtractPvs(ObjectContainer &objects) const
 {
         RayInfoContainer::const_iterator it, it_end = mRays.end();
@@ -264 +275 @@
 }
 
-void VspKdTreeLeaf::GetRays(VssRayContainer &rays)
+void VspKdLeaf::GetRays(VssRayContainer &rays)
 {
         RayInfoContainer::const_iterator it, it_end = mRays.end();
@@ -272 +283 @@
 }
 
-ViewCell *VspKdTreeLeaf::GetViewCell()
+VspKdViewCell *VspKdLeaf::GetViewCell()
 {
         return mViewCell;
 }
 
-/*********************************************************/
-/*            class VspKdTree implementation             */
-/*********************************************************/
-
-
-VspKdTree::VspKdTree(): mOnlyDrivingAxis(true)
-{         
-        environment->GetIntValue("VspKdTree.Termination.maxDepth", mTermMaxDepth);
-        environment->GetIntValue("VspKdTree.Termination.minPvs", mTermMinPvs);
-        environment->GetIntValue("VspKdTree.Termination.minRays", mTermMinRays);
-        environment->GetFloatValue("VspKdTree.Termination.maxRayContribution", mTermMaxRayContribution);
-        environment->GetFloatValue("VspKdTree.Termination.maxCostRatio", mTermMaxCostRatio);
-        environment->GetFloatValue("VspKdTree.Termination.minSize", mTermMinSize);
-
-        mTermMinSize = sqr(mTermMinSize);
-
-        environment->GetFloatValue("VspKdTree.epsilon", mEpsilon);
-        environment->GetFloatValue("VspKdTree.ct_div_ci", mCtDivCi);
-        
-        environment->GetFloatValue("VspKdTree.maxTotalMemory", mMaxTotalMemory);
-        environment->GetFloatValue("VspKdTree.maxStaticMemory", mMaxStaticMemory);
-    
-        environment->GetIntValue("VspKdTree.accessTimeThreshold", mAccessTimeThreshold);
-        environment->GetIntValue("VspKdTree.minCollapseDepth", mMinCollapseDepth);
-
-        // split type
-        char sname[128];
-        environment->GetStringValue("VspKdTree.splitType", sname);
-        string name(sname);
-                
-        Debug << "======= vsp kd tree options ========" << endl;
-        Debug << "max depth: "<< mTermMaxDepth << endl;
-        Debug << "min pvs: "<< mTermMinPvs << endl;
-        Debug << "min rays: "<< mTermMinRays << endl;
-        Debug << "max ray contribution: "<< mTermMaxRayContribution << endl;
-        Debug << "max cost ratio: "<< mTermMaxCostRatio << endl;
-        Debug << "min size: "<<mTermMinSize << endl;
-
-        if (name.compare("regular") == 0)
-        {
-                Debug << "using regular split" << endl;
-                splitType = ESplitRegular;
-        }
-        else
-        {
-                if (name.compare("heuristic") == 0)
-                {
-                        Debug << "using heuristic split" << endl;
-                        splitType = ESplitHeuristic;
-                }
-                else 
-                {
-                        cerr << "Invalid VspKdTree split type " << name << endl;
-                        exit(1);
-                }
-        }
-
-        mRoot = NULL;
-
-        mSplitCandidates = new vector<SortableEntry>;
-}
-
-
-VspKdTree::~VspKdTree()
-{
-        DEL_PTR(mRoot);
-        DEL_PTR(mSplitCandidates);
-}
-
-void VspKdStatistics::Print(ostream &app) const
-{
-        app << "===== VspKdTree statistics ===============\n";
-
-        app << "#N_RAYS ( Number of rays )\n"
-                << rays << endl;
-  
-        app << "#N_INITPVS ( Initial PVS size )\n"
-                << initialPvsSize << endl;
-  
-        app << "#N_NODES ( Number of nodes )\n" << nodes << "\n";
-
-        app << "#N_LEAVES ( Number of leaves )\n" << Leaves() << "\n";
-
-        app << "#N_SPLITS ( Number of splits in axes x y z dx dy dz \n";
-  
-        for (int i=0; i<7; i++)
-                app << splits[i] <<" ";
-        app << endl;
-
-        app << "#N_RAYREFS ( Number of rayRefs )\n" <<
-                rayRefs << "\n";
-
-        app << "#N_RAYRAYREFS  ( Number of rayRefs / ray )\n" <<
-                rayRefs / (double)rays << "\n";
-
-        app << "#N_LEAFRAYREFS  ( Number of rayRefs / leaf )\n" <<
-                rayRefs / (double)Leaves() << "\n";
-
-        app << "#N_MAXRAYREFS  ( Max number of rayRefs / leaf )\n" <<
-                maxRayRefs << "\n";
-
-  //  app << setprecision(4);
-
-        app << "#N_PMAXDEPTHLEAVES ( Percentage of leaves at maxdepth )\n" <<
-                maxDepthNodes * 100 / (double)Leaves() << endl;
-
-        app << "#N_PMINPVSLEAVES  ( Percentage of leaves with mininimal PVS )\n" <<
-                minPvsNodes * 100 / (double)Leaves() << endl;
-
-        app << "#N_PMINRAYSLEAVES  ( Percentage of leaves with minimal number of rays)\n" <<
-                minRaysNodes * 100 / (double)Leaves() << endl;
-
-        app << "#N_PMINSIZELEAVES  ( Percentage of leaves with minSize )\n"<<
-                minSizeNodes * 100 / (double)Leaves() << endl;
-
-        app << "#N_PMAXRAYCONTRIBLEAVES  ( Percentage of leaves with maximal ray contribution )\n" <<
-                maxRayContribNodes * 100 / (double)Leaves() << endl;
-
-        app << "#N_ADDED_RAYREFS  ( Number of dynamically added ray references )\n"<<
-                addedRayRefs << endl;
-
-        app << "#N_REMOVED_RAYREFS  ( Number of dynamically removed ray references )\n"<<
-                removedRayRefs << endl;
-
-        //  app << setprecision(4);
-
-        app << "#N_MAXPVS ( Maximal PVS size / leaf)\n"
-                << maxPvsSize << endl;
-
-        app << "#N_CTIME  ( Construction time [s] )\n"
-                << Time() << " \n";
-
-        app << "===== END OF VspKdTree statistics ==========\n";
-}
-
-
-void
-VspKdTreeLeaf::UpdatePvsSize()
+void VspKdLeaf::SetViewCell(VspKdViewCell *viewCell)
+{
+        mViewCell = viewCell;
+}
+
+
+void VspKdLeaf::UpdatePvsSize()
 {
         if (!mValidPvs) 
@@ -449 +329 @@
 }
 
-
-void
-VspKdTree::Construct(const VssRayContainer &rays,
-                                         AxisAlignedBox3 *forcedBoundingBox)
+/*********************************************************/
+/*            class VspKdTree implementation             */
+/*********************************************************/
+
+
+
+VspKdTree::VspKdTree(): mOnlyDrivingAxis(true)
+{         
+        environment->GetIntValue("VspKdTree.Termination.maxDepth", mTermMaxDepth);
+        environment->GetIntValue("VspKdTree.Termination.minPvs", mTermMinPvs);
+        environment->GetIntValue("VspKdTree.Termination.minRays", mTermMinRays);
+        environment->GetFloatValue("VspKdTree.Termination.maxRayContribution", mTermMaxRayContribution);
+        environment->GetFloatValue("VspKdTree.Termination.maxCostRatio", mTermMaxCostRatio);
+        environment->GetFloatValue("VspKdTree.Termination.minSize", mTermMinSize);
+
+        mTermMinSize = sqr(mTermMinSize);
+
+        environment->GetFloatValue("VspKdTree.epsilon", mEpsilon);
+        environment->GetFloatValue("VspKdTree.ct_div_ci", mCtDivCi);
+        
+        environment->GetFloatValue("VspKdTree.maxTotalMemory", mMaxTotalMemory);
+        environment->GetFloatValue("VspKdTree.maxStaticMemory", mMaxStaticMemory);
+    
+        environment->GetIntValue("VspKdTree.accessTimeThreshold", mAccessTimeThreshold);
+        environment->GetIntValue("VspKdTree.minCollapseDepth", mMinCollapseDepth);
+
+        environment->GetFloatValue("VspKdTree.maxCostRatio", mMaxCostRatio);
+        environment->GetIntValue("ViewCells.maxViewCells", mMaxViewCells);
+
+        MergeCandidate::sMaxPvsSize = 300; // TODO: add option
+
+        // split type
+        char sname[128];
+        environment->GetStringValue("VspKdTree.splitType", sname);
+        string name(sname);
+                
+        Debug << "======= vsp kd tree options ========" << endl;
+        Debug << "max depth: "<< mTermMaxDepth << endl;
+        Debug << "min pvs: "<< mTermMinPvs << endl;
+        Debug << "min rays: "<< mTermMinRays << endl;
+        Debug << "max ray contribution: "<< mTermMaxRayContribution << endl;
+        Debug << "max cost ratio: "<< mTermMaxCostRatio << endl;
+        Debug << "min size: "<<mTermMinSize << endl;
+
+        if (name.compare("regular") == 0)
+        {
+                Debug << "using regular split" << endl;
+                splitType = ESplitRegular;
+        }
+        else
+        {
+                if (name.compare("heuristic") == 0)
+                {
+                        Debug << "using heuristic split" << endl;
+                        splitType = ESplitHeuristic;
+                }
+                else 
+                {
+                        cerr << "Invalid VspKdTree split type " << name << endl;
+                        exit(1);
+                }
+        }
+
+        mRoot = NULL;
+
+        mSplitCandidates = new vector<SortableEntry>;
+}
+
+
+VspKdTree::~VspKdTree()
+{
+        DEL_PTR(mRoot);
+        DEL_PTR(mSplitCandidates);
+}
+
+void VspKdStatistics::Print(ostream &app) const
+{
+        app << "===== VspKdTree statistics ===============\n";
+
+        app << "#N_RAYS ( Number of rays )\n"
+                << rays << endl;
+  
+        app << "#N_INITPVS ( Initial PVS size )\n"
+                << initialPvsSize << endl;
+  
+        app << "#N_NODES ( Number of nodes )\n" << nodes << "\n";
+
+        app << "#N_LEAVES ( Number of leaves )\n" << Leaves() << "\n";
+
+        app << "#N_SPLITS ( Number of splits in axes x y z dx dy dz \n";
+  
+        for (int i=0; i<7; i++)
+                app << splits[i] <<" ";
+        app << endl;
+
+        app << "#N_RAYREFS ( Number of rayRefs )\n" <<
+                rayRefs << "\n";
+
+        app << "#N_RAYRAYREFS  ( Number of rayRefs / ray )\n" <<
+                rayRefs / (double)rays << "\n";
+
+        app << "#N_LEAFRAYREFS  ( Number of rayRefs / leaf )\n" <<
+                rayRefs / (double)Leaves() << "\n";
+
+        app << "#N_MAXRAYREFS  ( Max number of rayRefs / leaf )\n" <<
+                maxRayRefs << "\n";
+
+  //  app << setprecision(4);
+
+        app << "#N_PMAXDEPTHLEAVES ( Percentage of leaves at maxdepth )\n" <<
+                maxDepthNodes * 100 / (double)Leaves() << endl;
+
+        app << "#N_PMINPVSLEAVES  ( Percentage of leaves with mininimal PVS )\n" <<
+                minPvsNodes * 100 / (double)Leaves() << endl;
+
+        app << "#N_PMINRAYSLEAVES  ( Percentage of leaves with minimal number of rays)\n" <<
+                minRaysNodes * 100 / (double)Leaves() << endl;
+
+        app << "#N_PMINSIZELEAVES  ( Percentage of leaves with minSize )\n"<<
+                minSizeNodes * 100 / (double)Leaves() << endl;
+
+        app << "#N_PMAXRAYCONTRIBLEAVES  ( Percentage of leaves with maximal ray contribution )\n" <<
+                maxRayContribNodes * 100 / (double)Leaves() << endl;
+
+        app << "#N_ADDED_RAYREFS  ( Number of dynamically added ray references )\n"<<
+                addedRayRefs << endl;
+
+        app << "#N_REMOVED_RAYREFS  ( Number of dynamically removed ray references )\n"<<
+                removedRayRefs << endl;
+
+        //  app << setprecision(4);
+
+        app << "#N_( Maximal PVS size / leaf)\n"
+                << maxPvsSize << endl;
+
+        app << "#N_CTIME  ( Construction time [s] )\n"
+                << Time() << " \n";
+
+        app << "===== END OF VspKdTree statistics ==========\n";
+}
+
+
+void VspKdTree::CollectViewCells(ViewCellContainer &viewCells) const
+{
+        stack<VspKdNode *> nodeStack;
+        nodeStack.push(mRoot);
+
+        ViewCell::NewMail();
+
+        while (!nodeStack.empty()) 
+        {
+                VspKdNode *node = nodeStack.top();
+                nodeStack.pop();
+
+                if (node->IsLeaf()) 
+                {
+                        ViewCell *viewCell = dynamic_cast<VspKdLeaf *>(node)->mViewCell;
+
+                        if (!viewCell->Mailed()) 
+                        {
+                                viewCell->Mail();
+                                viewCells.push_back(viewCell);
+                        }
+                }
+                else 
+                {
+                        VspKdInterior *interior = dynamic_cast<VspKdInterior *>(node);
+
+                        nodeStack.push(interior->GetFront());
+                        nodeStack.push(interior->GetBack());
+                }
+        }
+}
+
+void VspKdTree::Construct(const VssRayContainer &rays,
+                                                  AxisAlignedBox3 *forcedBoundingBox)
 {
         mStat.Start();
@@ -459 +511 @@
         DEL_PTR(mRoot);
 
-        mRoot = new VspKdTreeLeaf(NULL, (int)rays.size());
+        mRoot = new VspKdLeaf(NULL, (int)rays.size());
 
         // first construct a leaf that will get subdivided
-        VspKdTreeLeaf *leaf = dynamic_cast<VspKdTreeLeaf *>(mRoot);
+        VspKdLeaf *leaf = dynamic_cast<VspKdLeaf *>(mRoot);
         
         mStat.nodes = 1;
@@ -523 +575 @@
 
 
-VspKdTreeNode *VspKdTree::Subdivide(const TraversalData &tdata)
-{
-        VspKdTreeNode *result = NULL;
+VspKdNode *VspKdTree::Subdivide(const TraversalData &tdata)
+{
+        VspKdNode *result = NULL;
 
         priority_queue<TraversalData> tStack;
@@ -562 +614 @@
                 tStack.pop();    
                 
-                VspKdTreeNode *node = SubdivideNode((VspKdTreeLeaf *) data.mNode,
+                VspKdNode *node = SubdivideNode((VspKdLeaf *) data.mNode,
                                                                                         data.mBox, backBox,     frontBox);
                 if (result == NULL)
@@ -569 +621 @@
                 if (!node->IsLeaf()) 
                 {
-                        VspKdTreeInterior *interior = dynamic_cast<VspKdTreeInterior *>(node);
+                        VspKdInterior *interior = dynamic_cast<VspKdInterior *>(node);
 
                         // push the children on the stack
@@ -586 +638 @@
 
 // returns selected plane for subdivision
-int VspKdTree::SelectPlane(VspKdTreeLeaf *leaf,
+int VspKdTree::SelectPlane(VspKdLeaf *leaf,
                                                    const AxisAlignedBox3 &box,
                                                    float &position,
@@ -641 +693 @@
 
                                                         
-float VspKdTree::EvalCostRatio(VspKdTreeLeaf *leaf,
+float VspKdTree::EvalCostRatio(VspKdLeaf *leaf,
                                                            const int axis,
                                                            const float position,
@@ -711 +763 @@
 }
 
-float VspKdTree::BestCostRatioRegular(VspKdTreeLeaf *leaf,
+float VspKdTree::BestCostRatioRegular(VspKdLeaf *leaf,
                                                                           int &axis,
                                                                           float &position,
@@ -772 +824 @@
 }
 
-float VspKdTree::BestCostRatioHeuristic(VspKdTreeLeaf *leaf,
+float VspKdTree::BestCostRatioHeuristic(VspKdLeaf *leaf,
                                                                                 int &axis,
                                                                                 float &position,
@@ -895 +947 @@
 }
 
-void VspKdTree::SortSplitCandidates(VspKdTreeLeaf *node,
+void VspKdTree::SortSplitCandidates(VspKdLeaf *node,
                                                                         const int axis)
 {
@@ -930 +982 @@
 {
         // the node became a leaf -> evaluate stats for leafs
-        VspKdTreeLeaf *leaf = dynamic_cast<VspKdTreeLeaf *>(data.mNode);
+        VspKdLeaf *leaf = dynamic_cast<VspKdLeaf *>(data.mNode);
 
         if (leaf->GetPvsSize() > mStat.maxPvsSize)
@@ -956 +1008 @@
 
 
-inline bool VspKdTree::TerminationCriteriaMet(const VspKdTreeLeaf *leaf, 
+inline bool VspKdTree::TerminationCriteriaMet(const VspKdLeaf *leaf, 
                                                                                           const AxisAlignedBox3 &box) const
 {
         return ((leaf->GetPvsSize() < mTermMinPvs) || 
                     (leaf->mRays.size() < mTermMinRays) ||
-                        (leaf->GetAvgRayContribution() > mTermMaxRayContribution ) ||
+                        //(leaf->GetAvgRayContribution() > mTermMaxRayContribution ) ||
                         (leaf->mDepth >= mTermMaxDepth) || 
                         (SqrMagnitude(box.Size()) <= mTermMinSize));
@@ -967 +1019 @@
 
 
-VspKdTreeNode *VspKdTree::SubdivideNode(VspKdTreeLeaf *leaf,
+VspKdNode *VspKdTree::SubdivideNode(VspKdLeaf *leaf,
                                                                                 const AxisAlignedBox3 &box,
                                                                                 AxisAlignedBox3 &backBBox,
@@ -1005 +1057 @@
 
         // add the new nodes to the tree
-        VspKdTreeInterior *node = new VspKdTreeInterior(leaf->mParent);
+        VspKdInterior *node = new VspKdInterior(leaf->mParent);
 
         node->mAxis = axis;
@@ -1014 +1066 @@
         frontBBox = box;
 
-        VspKdTreeLeaf *back = new VspKdTreeLeaf(node, raysBack);
+        VspKdLeaf *back = new VspKdLeaf(node, raysBack);
         back->SetPvsSize(pvsBack);
-        VspKdTreeLeaf *front = new VspKdTreeLeaf(node, raysFront);
+        VspKdLeaf *front = new VspKdLeaf(node, raysFront);
         front->SetPvsSize(pvsFront);
 
@@ -1025 +1077 @@
         node->SetupChildLinks(back, front);
         
-        if (axis <= VspKdTreeNode::SPLIT_Z) 
+        if (axis <= VspKdNode::SPLIT_Z) 
         {
                 backBBox.SetMax(axis, position);
@@ -1110 +1162 @@
 int VspKdTree::ReleaseMemory(const int time)
 {
-        stack<VspKdTreeNode *> tstack;
+        stack<VspKdNode *> tstack;
 
         // find a node in the tree which subtree will be collapsed
@@ -1120 +1172 @@
         while (!tstack.empty())
         {
-                VspKdTreeNode *node = tstack.top();
+                VspKdNode *node = tstack.top();
                 tstack.pop();
     
                 if (!node->IsLeaf()) 
                 {
-                        VspKdTreeInterior *in = dynamic_cast<VspKdTreeInterior *>(node);
+                        VspKdInterior *in = dynamic_cast<VspKdInterior *>(node);
                         // cout<<"depth="<<(int)in->depth<<" time="<<in->lastAccessTime<<endl;
                         if (in->mDepth >= mMinCollapseDepth && in->mLastAccessTime <= maxAccessTime) 
@@ -1156 +1208 @@
 
 
-VspKdTreeNode *VspKdTree::SubdivideLeaf(VspKdTreeLeaf *leaf,
+VspKdNode *VspKdTree::SubdivideLeaf(VspKdLeaf *leaf,
                                                                                 const float sizeThreshold)
 {
-        VspKdTreeNode *node = leaf;
+        VspKdNode *node = leaf;
 
         AxisAlignedBox3 leafBBox = GetBBox(leaf);
@@ -1188 +1240 @@
                                                    VssRayContainer &add)
 {
-        VspKdTreeLeaf::NewMail();
+        VspKdLeaf::NewMail();
 
         // schedule rays for removal
@@ -1218 +1270 @@
 
 void VspKdTree::RemoveRay(VssRay *ray,
-                                                  vector<VspKdTreeLeaf *> *affectedLeaves,
+                                                  vector<VspKdLeaf *> *affectedLeaves,
                                                   const bool removeAllScheduledRays)
 {
@@ -1243 +1295 @@
                         // remove the ray from the leaf
                         // find the ray in the leaf and swap it with the last ray...
-                        VspKdTreeLeaf *leaf = (VspKdTreeLeaf *)data.mNode;
+                        VspKdLeaf *leaf = (VspKdLeaf *)data.mNode;
       
                         if (!leaf->Mailed()) 
@@ -1329 +1381 @@
                         // remove the ray from the leaf
                         // find the ray in the leaf and swap it with the last ray
-                        VspKdTreeLeaf *leaf = dynamic_cast<VspKdTreeLeaf *>(data.mNode);
+                        VspKdLeaf *leaf = dynamic_cast<VspKdLeaf *>(data.mNode);
 
                         leaf->AddRay(data.mRayData);
@@ -1340 +1392 @@
                                                                          stack<RayTraversalData> &tstack)
 {
-        VspKdTreeInterior *in = dynamic_cast<VspKdTreeInterior *>(data.mNode);
-  
-        if (in->mAxis <= VspKdTreeNode::SPLIT_Z) 
+        VspKdInterior *in = dynamic_cast<VspKdInterior *>(data.mNode);
+  
+        if (in->mAxis <= VspKdNode::SPLIT_Z) 
         {
             // determine the side of this ray with respect to the plane
@@ -1387 +1439 @@
 
 
-int VspKdTree::CollapseSubtree(VspKdTreeNode *sroot, const int time)
+int VspKdTree::CollapseSubtree(VspKdNode *sroot, const int time)
 {
         // first count all rays in the subtree
         // use mail 1 for this purpose
-        stack<VspKdTreeNode *> tstack;
+        stack<VspKdNode *> tstack;
         
         int rayCount = 0;
@@ -1413 +1465 @@
                 ++ collapsedNodes;
                 
-                VspKdTreeNode *node = tstack.top();
+                VspKdNode *node = tstack.top();
                 tstack.pop();
                 if (node->IsLeaf()) 
                 {
-                        VspKdTreeLeaf *leaf = (VspKdTreeLeaf *) node;
+                        VspKdLeaf *leaf = (VspKdLeaf *) node;
                         
                         for(RayInfoContainer::iterator ri = leaf->mRays.begin();
@@ -1433 +1485 @@
                 else 
                 {
-                        tstack.push(((VspKdTreeInterior *)node)->GetFront());
-                        tstack.push(((VspKdTreeInterior *)node)->GetBack());
+                        tstack.push(((VspKdInterior *)node)->GetFront());
+                        tstack.push(((VspKdInterior *)node)->GetBack());
                 }
         }
@@ -1441 +1493 @@
 
         // create a new node that will hold the rays
-        VspKdTreeLeaf *newLeaf = new VspKdTreeLeaf(sroot->mParent, rayCount);
+        VspKdLeaf *newLeaf = new VspKdLeaf(sroot->mParent, rayCount);
         
         if (newLeaf->mParent)
@@ -1450 +1502 @@
         while (!tstack.empty()) 
         {
-                VspKdTreeNode *node = tstack.top();
+                VspKdNode *node = tstack.top();
                 tstack.pop();
 
                 if (node->IsLeaf()) 
                 {
-                        VspKdTreeLeaf *leaf = dynamic_cast<VspKdTreeLeaf *>(node);
+                        VspKdLeaf *leaf = dynamic_cast<VspKdLeaf *>(node);
 
                         for(RayInfoContainer::iterator ri = leaf->mRays.begin();
@@ -1476 +1528 @@
                 else 
                 {
-                        VspKdTreeInterior *interior = 
-                                dynamic_cast<VspKdTreeInterior *>(node);
+                        VspKdInterior *interior = 
+                                dynamic_cast<VspKdInterior *>(node);
                         tstack.push(interior->GetBack());
                         tstack.push(interior->GetFront());
@@ -1486 +1538 @@
         DEL_PTR(sroot);
   
-        // for(VspKdTreeNode::SRayContainer::iterator ri = newleaf->mRays.begin();
+        // for(VspKdNode::SRayContainer::iterator ri = newleaf->mRays.begin();
     //      ri != newleaf->mRays.end(); ++ ri)
         //     (*ri).ray->UnMail(2);
@@ -1510 +1562 @@
 
 
-int VspKdTree::GetPvsSize(VspKdTreeNode *node, const AxisAlignedBox3 &box) const
-{
-        stack<VspKdTreeNode *> tstack;
+int VspKdTree::GetPvsSize(VspKdNode *node, const AxisAlignedBox3 &box) const
+{
+        stack<VspKdNode *> tstack;
         tstack.push(mRoot);
 
@@ -1520 +1572 @@
         while (!tstack.empty()) 
         {
-                VspKdTreeNode *node = tstack.top();
+                VspKdNode *node = tstack.top();
                 tstack.pop();
     
           if (node->IsLeaf()) 
                 {
-                        VspKdTreeLeaf *leaf = (VspKdTreeLeaf *)node;
+                        VspKdLeaf *leaf = (VspKdLeaf *)node;
                         for (RayInfoContainer::iterator ri = leaf->mRays.begin();
                                  ri != leaf->mRays.end(); ++ ri)
@@ -1552 +1604 @@
                 else 
                 {
-                        VspKdTreeInterior *in = dynamic_cast<VspKdTreeInterior *>(node);
+                        VspKdInterior *in = dynamic_cast<VspKdInterior *>(node);
         
                         if (in->mAxis < 3) 
@@ -1578 +1630 @@
                                                                                          float &avgRayContribution)
 {
-        stack<VspKdTreeNode *> tstack;
+        stack<VspKdNode *> tstack;
         tstack.push(mRoot);
         
@@ -1589 +1641 @@
         while (!tstack.empty()) 
         {
-                VspKdTreeNode *node = tstack.top();
+                VspKdNode *node = tstack.top();
                 tstack.pop();
                 if (node->IsLeaf()) 
                 {
                         leaves++;
-                        VspKdTreeLeaf *leaf = (VspKdTreeLeaf *)node;
+                        VspKdLeaf *leaf = (VspKdLeaf *)node;
                         float c = leaf->GetAvgRayContribution();
 
@@ -1605 +1657 @@
                 } 
                 else {
-                        VspKdTreeInterior *in = (VspKdTreeInterior *)node;
+                        VspKdInterior *in = (VspKdInterior *)node;
                         // both nodes for directional splits
                         tstack.push(in->GetFront());
@@ -1621 +1673 @@
                                                         SimpleRayContainer &rays)
 {
-        stack<VspKdTreeNode *> tstack;
+        stack<VspKdNode *> tstack;
         tstack.push(mRoot);
         
         while (!tstack.empty()) 
         {
-                VspKdTreeNode *node = tstack.top();
+                VspKdNode *node = tstack.top();
                 tstack.pop();
                 
                 if (node->IsLeaf()) 
                 {
-                        VspKdTreeLeaf *leaf = dynamic_cast<VspKdTreeLeaf *>(node);
+                        VspKdLeaf *leaf = dynamic_cast<VspKdLeaf *>(node);
 
                         float c = leaf->GetAvgRayContribution();
@@ -1649 +1701 @@
                 else 
                 {
-                        VspKdTreeInterior *in = 
-                                dynamic_cast<VspKdTreeInterior *>(node);
+                        VspKdInterior *in = 
+                                dynamic_cast<VspKdInterior *>(node);
                         // both nodes for directional splits
                         tstack.push(in->GetFront());
@@ -1663 +1715 @@
 float VspKdTree::GetAvgPvsSize()
 {
-        stack<VspKdTreeNode *> tstack;
+        stack<VspKdNode *> tstack;
         tstack.push(mRoot);
 
@@ -1671 +1723 @@
         while (!tstack.empty()) 
         {
-                VspKdTreeNode *node = tstack.top();
+                VspKdNode *node = tstack.top();
                 tstack.pop();
                 
                 if (node->IsLeaf()) 
                 {
-                        VspKdTreeLeaf *leaf = (VspKdTreeLeaf *)node;
+                        VspKdLeaf *leaf = (VspKdLeaf *)node;
                         // update pvs size
                         leaf->UpdatePvsSize();
@@ -1684 +1736 @@
                 else 
                 {
-                        VspKdTreeInterior *in = (VspKdTreeInterior *)node;
+                        VspKdInterior *in = (VspKdInterior *)node;
                         // both nodes for directional splits
                         tstack.push(in->GetFront());
@@ -1694 +1746 @@
 }
 
-VspKdTreeNode *VspKdTree::GetRoot() const
+VspKdNode *VspKdTree::GetRoot() const
 {
         return mRoot;
 }
 
-AxisAlignedBox3 VspKdTree::GetBBox(VspKdTreeNode *node) const
+AxisAlignedBox3 VspKdTree::GetBBox(VspKdNode *node) const
 {
         if (node->mParent == NULL)
@@ -1705 +1757 @@
 
         if (!node->IsLeaf())
-                return (dynamic_cast<VspKdTreeInterior *>(node))->mBox;
+                return (dynamic_cast<VspKdInterior *>(node))->mBox;
 
         if (node->mParent->mAxis >= 3)
@@ -1740 +1792 @@
         return 
                 (sizeof(VspKdTree) + 
-                 mStat.Leaves() * sizeof(VspKdTreeLeaf) +
-                 mStat.Interior() * sizeof(VspKdTreeInterior) +
+                 mStat.Leaves() * sizeof(VspKdLeaf) +
+                 mStat.Interior() * sizeof(VspKdInterior) +
                  mStat.rayRefs * sizeof(RayInfo)) / (1024.0f * 1024.0f);
 }
@@ -1750 +1802 @@
 }
 
-int VspKdTree::ComputePvsSize(VspKdTreeNode *node, 
+int VspKdTree::ComputePvsSize(VspKdNode *node, 
                                                           const RayInfoContainer &globalRays) const
 {
@@ -1766 +1818 @@
 }
 
-void VspKdTree::CollectLeaves(vector<VspKdTreeLeaf *> &leaves) const
-{
-        stack<VspKdTreeNode *> nodeStack;
+void VspKdTree::CollectLeaves(vector<VspKdLeaf *> &leaves) const
+{
+        stack<VspKdNode *> nodeStack;
         nodeStack.push(mRoot);
 
         while (!nodeStack.empty()) 
         {
-                VspKdTreeNode *node = nodeStack.top();
+                VspKdNode *node = nodeStack.top();
                 
                 nodeStack.pop();
@@ -1779 +1831 @@
                 if (node->IsLeaf()) 
                 {
-                        VspKdTreeLeaf *leaf = dynamic_cast<VspKdTreeLeaf *>(node);
+                        VspKdLeaf *leaf = dynamic_cast<VspKdLeaf *>(node);
                         leaves.push_back(leaf);
                 } 
                 else 
                 {
-                        VspKdTreeInterior *interior = dynamic_cast<VspKdTreeInterior *>(node);
+                        VspKdInterior *interior = dynamic_cast<VspKdInterior *>(node);
 
                         nodeStack.push(interior->GetBack());
@@ -1792 +1844 @@
 }
 
-int VspKdTree::FindNeighbors(VspKdTreeLeaf *n,
-                                                         vector<VspKdTreeLeaf *> &neighbors,
+int VspKdTree::FindNeighbors(VspKdLeaf *n,
+                                                         vector<VspKdLeaf *> &neighbors,
                                                          bool onlyUnmailed)
 {
-        stack<VspKdTreeNode *> nodeStack;
+        stack<VspKdNode *> nodeStack;
   
         nodeStack.push(mRoot);
@@ -1804 +1856 @@
         while (!nodeStack.empty()) 
         {
-                VspKdTreeNode *node = nodeStack.top();
+                VspKdNode *node = nodeStack.top();
                 nodeStack.pop();
 
                 if (node->IsLeaf()) 
                 {
-                        VspKdTreeLeaf *leaf = dynamic_cast<VspKdTreeLeaf *>(node);
+                        VspKdLeaf *leaf = dynamic_cast<VspKdLeaf *>(node);
 
                         if (leaf != n && (!onlyUnmailed || !leaf->Mailed())) 
@@ -1816 +1868 @@
                 else 
                 {
-                        VspKdTreeInterior *interior = dynamic_cast<VspKdTreeInterior *>(node);
+                        VspKdInterior *interior = dynamic_cast<VspKdInterior *>(node);
 
                         if (interior->mPosition > box.Max(interior->mAxis))
@@ -1837 +1889 @@
 }
 
-void VspKdTree::MergeLeaves()
-{
-        vector<VspKdTreeLeaf *> leaves;
-        priority_queue<LeafPair> mergeCandidates;
-        vector<VspKdTreeLeaf *> neighbors;
-
+
+
+void VspKdTree::SetViewCellsManager(ViewCellsManager *vcm)
+{
+        mViewCellsManager = vcm;
+}
+
+
+int VspKdTree::CastRay(Ray &ray)
+{
+        int hits = 0;
+  
+        stack<RayTraversalData> tStack;
+  
+        float maxt = 1e6;
+        float mint = 0;
+
+        Intersectable::NewMail();
+
+        if (!mBox.GetMinMaxT(ray, &mint, &maxt))
+                return 0;
+
+        if (mint < 0)
+                mint = 0;
+  
+        maxt += Limits::Threshold;
+  
+        Vector3 entp = ray.Extrap(mint);
+        Vector3 extp = ray.Extrap(maxt);
+  
+        VspKdNode *node = mRoot;
+        VspKdNode *farChild;
+
+        float position;
+        int axis;
+  
+        while (1) 
+        {
+                if (!node->IsLeaf()) 
+                {
+                        VspKdInterior *in = dynamic_cast<VspKdInterior *>(node);
+                        position = in->mPosition;
+                        axis = in->mAxis;
+
+                        if (entp[axis] <= position) 
+                        {
+                                if (extp[axis] <= position) 
+                                {
+                                        node = in->mBack;
+                                        // cases N1,N2,N3,P5,Z2,Z3
+                                        continue;
+                                } else 
+                                {
+                                        // case N4
+                                        node = in->mBack;
+                                        farChild = in->mFront;
+                                }
+                        }
+                        else 
+                        {
+                                if (position <= extp[axis]) 
+                                {
+                                        node = in->mFront;
+                                        // cases P1,P2,P3,N5,Z1
+                                        continue;
+                                } 
+                                else 
+                                {
+                                        node = in->mFront;
+                                        farChild = in->mBack;
+                                        // case P4
+                                }
+                        }
+
+                        // $$ modification 3.5.2004 - hints from Kamil Ghais
+                        // case N4 or P4
+                        float tdist = (position - ray.GetLoc(axis)) / ray.GetDir(axis);
+                        //tStack.push(RayTraversalData(farChild, extp, maxt)); //TODO
+                        extp = ray.GetLoc() + ray.GetDir()*tdist;
+                        maxt = tdist;
+                } 
+                else 
+                {
+                        // compute intersection with all objects in this leaf
+                        /*KdLeaf *leaf = (KdLeaf *) node;
+                        if (ray.mFlags & Ray::STORE_KDLEAVES)
+                                ray.kdLeaves.push_back(leaf);
+                        
+                        ObjectContainer::const_iterator mi;
+                        for ( mi = leaf->mObjects.begin(); mi != leaf->mObjects.end(); mi++) 
+                        {
+                                Intersectable *object = *mi;
+                                if (!object->Mailed() ) 
+                                {
+                                        object->Mail();
+                                        if (ray.mFlags & Ray::STORE_TESTED_OBJECTS)
+                                                ray.testedObjects.push_back(object);
+                                        hits += object->CastRay(ray);
+                                }
+                        }
+                        
+                        if (hits && ray.GetType() == Ray::LOCAL_RAY)
+                                if (ray.intersections[0].mT <= maxt)
+                                        break;
+                        
+                        // get the next node from the stack
+                        if (tStack.empty())
+                                break;
+                        
+                        entp = extp;
+                        mint = maxt;
+                        if (ray.GetType() == Ray::LINE_SEGMENT && mint > 1.0f)
+                                break;
+                        
+                        RayTraversalData &s  = tStack.top();
+                        node = s.mNode;
+                        extp = s.mExitPoint;
+                        maxt = s.mMaxT;
+                        tStack.pop();
+                        */
+                }
+        }
+        
+        return hits;
+}
+
+
+void VspKdTree::GenerateViewCell(VspKdLeaf *leaf)
+{
+        RayInfoContainer::const_iterator it, it_end = leaf->GetRays().end();
+
+        VspKdViewCell *vc = dynamic_cast<VspKdViewCell *>(mViewCellsManager->GenerateViewCell());
+        leaf->SetViewCell(vc);
+
+        vc->SetSize(GetBBox(leaf).GetVolume());
+        vc->mVspKdLeaves.push_back(leaf);
+
+        for (it = leaf->GetRays().begin(); it != it_end; ++ it)
+        {
+                VssRay *ray = (*it).mRay;
+
+                if (ray->mTerminationObject)
+                        vc->GetPvs().AddSample(ray->mTerminationObject);
+                
+                if (ray->mOriginObject)
+                        vc->GetPvs().AddSample(ray->mOriginObject);
+        }
+}
+
+
+void VspKdTree::EvaluateViewCellsStats(ViewCellsStatistics &vcStat) const
+{
+        vcStat.Reset();
+
+        stack<VspKdNode *> nodeStack;
+        nodeStack.push(mRoot);
+
+        ViewCell::NewMail();
+
+        // exclude root cell
+        //mRootCell->Mail();
+
+        while (!nodeStack.empty()) 
+        {
+                VspKdNode *node = nodeStack.top();
+                nodeStack.pop();
+
+                if (node->IsLeaf()) 
+                {
+                        ++ vcStat.leaves;
+
+                        VspKdViewCell *viewCell = dynamic_cast<VspKdLeaf *>(node)->mViewCell;
+
+                        if (!viewCell->Mailed()) 
+                        {
+                                viewCell->Mail();
+                                
+                                ++ vcStat.viewCells;
+                                const int pvsSize = viewCell->GetPvs().GetSize();
+
+                vcStat.pvs += pvsSize;
+
+                                if (pvsSize < 1)
+                                        ++ vcStat.emptyPvs;
+
+                                if (pvsSize > vcStat.maxPvs)
+                                        vcStat.maxPvs = pvsSize;
+
+                                if (pvsSize < vcStat.minPvs)
+                                        vcStat.minPvs = pvsSize;
+
+                                if ((int)viewCell->mVspKdLeaves.size() > vcStat.maxLeaves)
+                                        vcStat.maxLeaves = (int)viewCell->mVspKdLeaves.size();          
+                        }
+                }
+                else 
+                {
+                        VspKdInterior *interior = dynamic_cast<VspKdInterior *>(node);
+
+                        nodeStack.push(interior->GetFront());
+                        nodeStack.push(interior->GetBack());
+                }
+        }
+}
+
+
+bool VspKdTree::MergeViewCells(VspKdLeaf *l1, VspKdLeaf *l2)
+{
+        //-- change pointer to view cells of all leaves associated with the previous view cells
+        VspKdViewCell *fVc = l1->GetViewCell();
+        VspKdViewCell *bVc = l2->GetViewCell();
+
+        VspKdViewCell *vc = dynamic_cast<VspKdViewCell *>(
+                mViewCellsManager->MergeViewCells(*fVc, *bVc));
+
+        // if merge was unsuccessful
+        if (!vc) return false;
+
+        // set new size of view cell
+        vc->SetSize(fVc->GetSize() + bVc->GetSize());
+
+        vector<VspKdLeaf *> fLeaves = fVc->mVspKdLeaves;
+        vector<VspKdLeaf *> bLeaves = bVc->mVspKdLeaves;
+
+        vector<VspKdLeaf *>::const_iterator it;
+
+        //-- change view cells of all the other leaves the view cell belongs to
+        for (it = fLeaves.begin(); it != fLeaves.end(); ++ it)
+        {
+                (*it)->SetViewCell(vc);
+                vc->mVspKdLeaves.push_back(*it);
+        }
+
+        for (it = bLeaves.begin(); it != bLeaves.end(); ++ it)
+        {
+                (*it)->SetViewCell(vc);
+                vc->mVspKdLeaves.push_back(*it);
+        }
+
+        // clean up old view cells
+        DEL_PTR(fVc);
+        DEL_PTR(bVc);
+
+        return true;
+}
+
+
+
+int VspKdTree::MergeLeaves()
+{
+        vector<VspKdLeaf *> leaves;
+        priority_queue<MergeCandidate> mergeQueue;
+        
+        // collect the leaves, e.g., the "voxels" that will build the view cells
         CollectLeaves(leaves);
 
-        VspKdTreeLeaf::NewMail();
-
-        vector<VspKdTreeLeaf *>::const_iterator it, it_end = leaves.end();
-
-
+        int vcSize = (int)leaves.size();
+
+        VspKdLeaf::NewMail();
+
+        vector<VspKdLeaf *>::const_iterator it, it_end = leaves.end();
+
+        // generate view cells
         for (it = leaves.begin(); it != it_end; ++ it)
-        {
-                VspKdTreeLeaf *leaf = *it;
-
+                GenerateViewCell(*it);
+
+        // find merge candidates and push them into queue
+        for (it = leaves.begin(); it != it_end; ++ it)
+        {
+                VspKdLeaf *leaf = *it;
+                
+                // no leaf is part of two merge candidates
                 if (!leaf->Mailed())
                 {
+                        leaf->Mail();
+
+                        vector<VspKdLeaf *> neighbors;
                         FindNeighbors(leaf, neighbors, true);
 
-                        vector<VspKdTreeLeaf *>::const_iterator nit, nit_end = neighbors.end();
-
-                        for (nit = neighbors.begin(); nit != neighbors.end(); ++ nit)
-                                mergeCandidates.push(LeafPair(leaf, *nit));
+                        vector<VspKdLeaf *>::const_iterator nit, 
+                                nit_end = neighbors.end();
+
+                        for (nit = neighbors.begin(); nit != nit_end; ++ nit)
+                                mergeQueue.push(MergeCandidate(leaf, *nit));
+                }
+        }
+
+        int merged = 0;
+
+        float savedMaxCostRatio = 0;
+
+        Debug << "merge cost " << mergeQueue.top().GetMergeCost() << " of " << mMaxCostRatio << endl;
+
+        // use priority queue to merge leaves
+        while (!mergeQueue.empty() && 
+                   ((mMaxViewCells < vcSize) ||
+                    (mergeQueue.top().GetMergeCost() < mMaxCostRatio)))
+        {
+                ViewCell::NewMail();
+
+                Debug << "=====================" << endl;
+                MergeCandidate mc = mergeQueue.top();
+                mergeQueue.pop();
+                
+                if (mc.GetLeaf1()->GetViewCell() == mc.GetLeaf2()->GetViewCell())
+                // both view cells the same!
+                {
+                        Debug << "same view cell!!" << endl;
+                        -- vcSize;
+
+                        continue;
+                }
+
+                if (mc.Valid())
+                {
+                        mc.GetLeaf1()->GetViewCell()->Mail();
+                        mc.GetLeaf2()->GetViewCell()->Mail();
                         
-                        leaf->Mail();
-                }
-        }
-}
-
+                        Debug << "merging cells with cost " << mc.GetMergeCost() << " of " << mMaxCostRatio << endl;
+                        savedMaxCostRatio = mc.GetMergeCost();
+
+                        MergeViewCells(mc.GetLeaf1(), mc.GetLeaf2());
+                        
+                        ++ merged;
+                        -- vcSize;
+                }
+                // merge candidate not valid, because one of the leaves was already
+                // merged with another one
+                else 
+                {
+                        Debug << "not valid " << mc.GetMergeCost() << endl;
+                        
+                        // validate and reinsert into queue
+                        mc.SetValid();
+                        Debug << "ag. valid " << mc.GetMergeCost() << endl;
+
+                        mergeQueue.push(mc);
+                }
+        }
+
+        if (mergeQueue.empty())
+                Debug << "empty queue" << endl;
+        
+        Debug << "max cost ratio: " << savedMaxCostRatio << endl;
+
+        return merged;
+}
 
 
@@ -1875 +2243 @@
 
 
-MergeCandidate::MergeCandidate(VspKdTreeLeaf *l1, VspKdTreeLeaf *l2):
-mLeaf1(l1), mLeaf2(l2)
-{}
-
-float MergeCandidate::EvaluateMergeCost() const
-{
-        // pvs difference
-        VspKdViewCell *vc1 = dynamic_cast<VspKdViewCell *>(mLeaf1->GetViewCell());
-        VspKdViewCell *vc2 = dynamic_cast<VspKdViewCell *>(mLeaf2->GetViewCell());
+MergeCandidate::MergeCandidate(VspKdLeaf *l1, VspKdLeaf *l2):
+mMergeCost(0),
+mLeaf1(l1),
+mLeaf2(l2),
+mLeaf1Id(l1->GetViewCell()->mMailbox),
+mLeaf2Id(l2->GetViewCell()->mMailbox)
+{
+        EvalMergeCost();
+}
+
+
+void MergeCandidate::EvalMergeCost()
+{
+        // compute pvs differences
+        VspKdViewCell *vc1 = mLeaf1->GetViewCell();
+        VspKdViewCell *vc2 = mLeaf2->GetViewCell();
+        
+        //VspKdViewCell *vc1 = dynamic_cast<VspKdViewCell *>(mLeaf1->GetViewCell());
+        //VspKdViewCell *vc2 = dynamic_cast<VspKdViewCell *>(mLeaf2->GetViewCell());
 
         const int diff1 = vc1->GetPvs().Diff(vc2->GetPvs());
-        
-        //const int diff2 = vc2->GetPvs().Diff(vc1->GetPvs());
-        //const float simDiff = (float)max(diff1, diff2);
-
+        const int vcPvs = diff1 + vc1->GetPvs().GetSize();
+
+        //-- compute ratio of old cost 
+        //-- (added size of left and right view cell times pvs size)
+        //-- to new rendering cost (size of merged view cell times pvs size)
         const float oldCost = 
-                vc1->GetSize() * vc1->GetPvs().GetSize() + 
-                vc2->GetSize() * vc2->GetPvs().GetSize();
-
-        const float mergedPvsCost = 
-                (diff1 + vc1->GetPvs().GetSize()) *
-                (vc1->GetSize() + vc2->GetSize());
-
-        return mergedPvsCost / oldCost;
-}
+                (float)vc1->GetPvs().GetSize() * vc1->GetSize() + 
+                (float)vc2->GetPvs().GetSize() * vc2->GetSize();
+
+        const float newCost = 
+                (float)vcPvs * (vc1->GetSize() + vc2->GetSize());
+
+        mMergeCost = newCost / oldCost;
+
+        Debug << "******************************" << endl;
+        Debug << "pvs size: " << vcPvs << " max: " << sMaxPvsSize << endl;
+        if (vcPvs > sMaxPvsSize) // strong penalty if pvs size too large
+                mMergeCost += 1.0;
+
+        Debug << "old cost: " << oldCost << endl;
+        Debug << "new cost: " << newCost << endl;
+}
+
+void MergeCandidate::SetLeaf1(VspKdLeaf *l)
+{
+        mLeaf1 = l;
+}
+
+void MergeCandidate::SetLeaf2(VspKdLeaf *l)
+{
+        mLeaf2 = l;
+}
+
+VspKdLeaf *MergeCandidate::GetLeaf1()
+{
+        return mLeaf1;
+}
+
+VspKdLeaf *MergeCandidate::GetLeaf2()
+{
+        return mLeaf2;
+}
+
+bool MergeCandidate::Valid() const
+{       
+        //Debug << mLeaf1->GetViewCell()->mMailbox << " " << mLeaf1Id << endl;
+        //Debug << mLeaf2->GetViewCell()->mMailbox << " " << mLeaf2Id << endl;
+
+        return 
+                (mLeaf1->GetViewCell()->mMailbox == mLeaf1Id) && 
+                (mLeaf2->GetViewCell()->mMailbox == mLeaf2Id);
+}
+
+float MergeCandidate::GetMergeCost() const
+{
+        return mMergeCost;
+}
+
+void MergeCandidate::SetValid()
+{
+        mLeaf1Id = mLeaf1->GetViewCell()->mMailbox;
+        mLeaf2Id = mLeaf2->GetViewCell()->mMailbox;
+        
+        EvalMergeCost();
+}

trunk/VUT/GtpVisibilityPreprocessor/src/VspKdTree.h

@@ -34 +34 @@
 #include "Containers.h"
 
-class VspKdTreeLeaf;
+class VspKdLeaf;
+class ViewCellsManager;
+class VspKdViewCell;
+class ViewCellsStatistics;
+
 
 /**
@@ -42 +46 @@
 {  
 public:
-        VspKdTreeLeaf *mLeaf1;
-        VspKdTreeLeaf *mLeaf2;
-
-        MergeCandidate(VspKdTreeLeaf *l1, VspKdTreeLeaf *l2);
+
+        MergeCandidate(VspKdLeaf *l1, VspKdLeaf *l2);
 
         /** Computes PVS difference between the leaves.
@@ -51 +53 @@
         //int ComputePvsDifference() const;
 
-        /** Evaluates the merge costs of this leaf.
-        */
-        float EvaluateMergeCost() const;
-
-        friend bool operator<(const MergeCandidate &leafa, const MergeCandidate &leafb) 
+        /** If this merge pair is still valid.
+        */
+        bool Valid() const;
+
+        /** Sets this merge candidate to be valid.
+        */
+        void SetValid();
+
+        friend bool operator<(const MergeCandidate &leafa, const MergeCandidate &leafb)
         {
-                return leafa.EvaluateMergeCost() < leafb.EvaluateMergeCost();
+                return leafb.GetMergeCost() < leafa.GetMergeCost();
         }
+
+        void SetLeaf1(VspKdLeaf *l);
+        void SetLeaf2(VspKdLeaf *l);
+
+        VspKdLeaf *GetLeaf1();
+        VspKdLeaf *GetLeaf2();
+
+        /** Merge cost of this candidate pair.
+        */
+        float GetMergeCost() const;
+
+        /// maximal pvs size
+        static int sMaxPvsSize;
+
+protected:
+        
+        /** Evaluates the merge costs of the leaves.
+        */
+        void EvalMergeCost();
+
+        int mLeaf1Id;
+        int mLeaf2Id;
+
+        float mMergeCost;
+        
+        VspKdLeaf *mLeaf1;
+        VspKdLeaf *mLeaf2;
 };
 
@@ -142 +175 @@
 
 
-class VspKdTreeInterior;
+class VspKdInterior;
 
 
 /** Abstract superclass of Vsp-Kd-Tree nodes.
 */
-class VspKdTreeNode
+class VspKdNode
 {
 public:
@@ -157 +190 @@
         /** Constructs new interior node from the parent node.
         */
-        inline VspKdTreeNode(VspKdTreeInterior *p);
+        inline VspKdNode(VspKdInterior *p);
 
         /** Destroys this node and the subtree.
         */
-        virtual ~VspKdTreeNode();
+        virtual ~VspKdNode();
 
         /** Type of the node (Einterior or ELeaf)
@@ -181 +214 @@
         /** Returns parent node.
         */
-        VspKdTreeInterior *GetParent() const;
+        VspKdInterior *GetParent() const;
 
         /** Sets parent node.
         */
-        void SetParent(VspKdTreeInterior *p);
+        void SetParent(VspKdInterior *p);
 
 protected:
@@ -192 +225 @@
   
         /// link to the parent
-        VspKdTreeInterior *mParent;
+        VspKdInterior *mParent;
 
         enum {SPLIT_X = 0, SPLIT_Y, SPLIT_Z, SPLIT_DIRX, SPLIT_DIRY, SPLIT_DIRZ};
@@ -206 +239 @@
 // KD-tree node - interior node
 // --------------------------------------------------------------
-class VspKdTreeInterior: public VspKdTreeNode
+class VspKdInterior: public VspKdNode
 {
 public:
@@ -213 +246 @@
         /** Constructs new interior node from parent node.
         */
-        VspKdTreeInterior(VspKdTreeInterior *p);
+        VspKdInterior(VspKdInterior *p);
                         
         virtual int GetAccessTime();
@@ -219 +252 @@
         virtual int Type() const;
   
-        virtual ~VspKdTreeInterior();
+        virtual ~VspKdInterior();
     
         virtual void Print(ostream &s) const;
@@ -225 +258 @@
         /** Returns back child.
         */
-        inline VspKdTreeNode *GetBack() const;
+        inline VspKdNode *GetBack() const;
         /** Returns front child.
         */
-        inline VspKdTreeNode *GetFront() const;
+        inline VspKdNode *GetFront() const;
 
 protected:
@@ -234 +267 @@
         /** Sets pointers to back child and front child.
         */
-        void SetupChildLinks(VspKdTreeNode *b, VspKdTreeNode *f);
+        void SetupChildLinks(VspKdNode *b, VspKdNode *f);
 
         /** Replaces the pointer to oldChild with a pointer to newChild.
         */
-        void ReplaceChildLink(VspKdTreeNode *oldChild, VspKdTreeNode *newChild);
+        void ReplaceChildLink(VspKdNode *oldChild, VspKdNode *newChild);
  
         /** Computes intersection of the ray with the node boundaries.
@@ -248 +281 @@
 
         // pointers to children
-        VspKdTreeNode *mBack;
-        VspKdTreeNode *mFront;
+        VspKdNode *mBack;
+        VspKdNode *mFront;
 
         // the bbox of the node
@@ -263 +296 @@
 // KD-tree node - leaf node
 // --------------------------------------------------------------
-class VspKdTreeLeaf: public VspKdTreeNode
+class VspKdLeaf: public VspKdNode
 {
 public:
@@ -272 +305 @@
                 @param nRays preallocates memory to store this number of rays
         */
-        VspKdTreeLeaf(VspKdTreeInterior *p,     const int nRays);
-        
-        virtual ~VspKdTreeLeaf();
+        VspKdLeaf(VspKdInterior *p,     const int nRays);
+        
+        virtual ~VspKdLeaf();
 
         virtual int Type() const;  
@@ -317 +350 @@
         bool Mailed() const;
   
-        bool Mailed(const int mail);
-
+        /** Returns true if mail equals the leaf mail box.
+        */
+        bool Mailed(const int mail) const;
+
+        void SetViewCell(VspKdViewCell *viewCell);
+
+        /** Returns mail box of this leaf.
+        */
+        int GetMailbox() const;
+
+        /** Returns view cell associated with this leaf.
+        */
+        VspKdViewCell *GetViewCell();
+
+        ////////////////////////////////////////////
+        
         static void NewMail();
 
-        static int mailID;
-
-        /** Returns view cell.
-        */
-        ViewCell *GetViewCell();
+        static int sMailId;
+
 
 protected:
@@ -337 +381 @@
   
         RayInfoContainer mRays;
+        
+        /// true if mPvsSize is valid => PVS does not have to be updated
         bool mValidPvs;
 
-        ViewCell *mViewCell;
+        /// the view cell associated with this leaf
+        VspKdViewCell *mViewCell;
+
 private:
+        /// stores PVS size so we have to evaluate PVS size only once
         int mPvsSize;
 };
@@ -380 +429 @@
         struct TraversalData
         {  
-                VspKdTreeNode *mNode;
+                VspKdNode *mNode;
                 AxisAlignedBox3 mBox;
                 int mDepth;
@@ -387 +436 @@
                 TraversalData() {}
 
-                TraversalData(VspKdTreeNode *n, const float p):
+                TraversalData(VspKdNode *n, const float p):
                 mNode(n)//, mPriority(p)
                 {}
 
-                TraversalData(VspKdTreeNode *n, const AxisAlignedBox3 &b, const int d):
+                TraversalData(VspKdNode *n,     const AxisAlignedBox3 &b, const int d):
                 mNode(n), mBox(b), mDepth(d) {}
     
@@ -406 +455 @@
                 {
                         // return a.node->queries.size() < b.node->queries.size();
-                        VspKdTreeLeaf *leafa = (VspKdTreeLeaf *) a.mNode;
-                        VspKdTreeLeaf *leafb = (VspKdTreeLeaf *) b.mNode;
+                        VspKdLeaf *leafa = (VspKdLeaf *) a.mNode;
+                        VspKdLeaf *leafb = (VspKdLeaf *) b.mNode;
 #if 0
                         return
@@ -446 +495 @@
   {
           RayInfo mRayData;
-          VspKdTreeNode *mNode;
+          VspKdNode *mNode;
       
           RayTraversalData() {}
           
-          RayTraversalData(VspKdTreeNode *n, const RayInfo &data):
+          RayTraversalData(VspKdNode *n, const RayInfo &data):
           mRayData(data), mNode(n) {}
   };
@@ -464 +513 @@
         /** Returns bounding box of the specified node.
         */
-        AxisAlignedBox3 GetBBox(VspKdTreeNode *node) const;
+        AxisAlignedBox3 GetBBox(VspKdNode *node) const;
 
         const VspKdStatistics &GetStatistics() const;
@@ -470 +519 @@
         /** Get the root of the tree.
         */
-        VspKdTreeNode *GetRoot() const;
+        VspKdNode *GetRoot() const;
 
         /** Returns average PVS size in tree.
@@ -484 +533 @@
         /** Collects leaves of this tree.
         */
-        void CollectLeaves(vector<VspKdTreeLeaf *> &leaves) const;
+        void CollectLeaves(vector<VspKdLeaf *> &leaves) const;
 
         /** Merges leaves of this tree according to some criteria.
         */
-        void MergeLeaves();
+        int MergeLeaves();
 
         /** Finds neighbours of this node.
@@ -495 +544 @@
                 @param onlyUnmailed if only unmailed neighbors are collected
         */
-        int FindNeighbors(VspKdTreeLeaf *n, 
-                                          vector<VspKdTreeLeaf *> &neighbors, 
+        int FindNeighbors(VspKdLeaf *n, 
+                                          vector<VspKdLeaf *> &neighbors, 
                                           bool onlyUnmailed);
+
+        
+        /** Sets pointer to view cells manager.
+        */
+        void SetViewCellsManager(ViewCellsManager *vcm);
+
+        /** A ray is cast possible intersecting the tree.
+                @param the ray that is cast.
+                @returns the number of intersections with objects stored in the tree.
+        */
+        int CastRay(Ray &ray);
+
+        /** Collects view cells generated by this tree.
+        */
+        void CollectViewCells(ViewCellContainer &viewCells) const;
+
+        /** Traverses tree and counts all view cells as well as their PVS size.
+        */
+        void EvaluateViewCellsStats(ViewCellsStatistics &stat) const;
 
 protected:
@@ -506 +574 @@
         virtual void AddRays(VssRayContainer &add);
 
-        VspKdTreeNode *Locate(const Vector3 &v);
-        
-        VspKdTreeNode *SubdivideNode(VspKdTreeLeaf *leaf,
+        VspKdNode *Locate(const Vector3 &v);
+        
+        VspKdNode *SubdivideNode(VspKdLeaf *leaf,
                                                                  const AxisAlignedBox3 &box,
                                                                  AxisAlignedBox3 &backBox,
                                                                  AxisAlignedBox3 &frontBox);
         
-        VspKdTreeNode *Subdivide(const TraversalData &tdata);
-        
-        int SelectPlane(VspKdTreeLeaf *leaf,
+        VspKdNode *Subdivide(const TraversalData &tdata);
+        
+        int SelectPlane(VspKdLeaf *leaf,
                                         const AxisAlignedBox3 &box,
                                         float &position,
@@ -523 +591 @@
                                         int &pvsFront);
 
-        void SortSplitCandidates(VspKdTreeLeaf *node,
+        void SortSplitCandidates(VspKdLeaf *node,
                                                          const int axis);       
   
-        float BestCostRatioHeuristic(VspKdTreeLeaf *node,
+        float BestCostRatioHeuristic(VspKdLeaf *node,
                                                                  int &axis,
                                                                  float &position,
@@ -534 +602 @@
                                                                  int &pvsFront);
 
-        float BestCostRatioRegular(VspKdTreeLeaf *node, 
+        float BestCostRatioRegular(VspKdLeaf *node, 
                                                            int &axis,
                                                            float &position,
@@ -542 +610 @@
                                                            int &pvsFront);
         
-        float EvalCostRatio(VspKdTreeLeaf *node,
+        float EvalCostRatio(VspKdLeaf *node,
                                                 const int axis,
                                                 const float position,
@@ -551 +619 @@
 
 
-        VspKdTreeNode * SubdivideLeaf(VspKdTreeLeaf *leaf,
+        VspKdNode * SubdivideLeaf(VspKdLeaf *leaf,
                                                                   const float SAThreshold);
 
         void RemoveRay(VssRay *ray,
-                                   vector<VspKdTreeLeaf *> *affectedLeaves,
+                                   vector<VspKdLeaf *> *affectedLeaves,
                                    const bool removeAllScheduledRays);
 
@@ -568 +636 @@
         int     GetRootPvsSize() const;
         
-        int     GetPvsSize(VspKdTreeNode *node, const AxisAlignedBox3 &box) const;
+        int     GetPvsSize(VspKdNode *node, const AxisAlignedBox3 &box) const;
 
         void GetRayContributionStatistics(float &minRayContribution,
@@ -580 +648 @@
                 @returns number of collapsed rays.
         */
-        int CollapseSubtree(VspKdTreeNode *sroot, const int time);
+        int CollapseSubtree(VspKdNode *sroot, const int time);
         
         int ReleaseMemory(const int time);
 
-        bool TerminationCriteriaMet(const VspKdTreeLeaf *leaf, 
+        bool TerminationCriteriaMet(const VspKdLeaf *leaf, 
                                                                 const AxisAlignedBox3 &box) const;
 
@@ -590 +658 @@
                 @returns PVS size of the intersection of this node bounding box with the rays.
         */
-        int ComputePvsSize(VspKdTreeNode *node, const RayInfoContainer &globalRays) const;
-
+        int ComputePvsSize(VspKdNode *node, 
+                                           const RayInfoContainer &globalRays) const;
+
+
+        /** Generates view cell for this leaf taking the ray contributions.
+        */
+        void GenerateViewCell(VspKdLeaf *leaf);
+
+        /** Merges view cells of the two leaves.
+        */
+        bool MergeViewCells(VspKdLeaf *l1, VspKdLeaf *l2);
+
+        
 protected:
         
@@ -597 +676 @@
         /////////////////////////////
         // The core pointer
-        VspKdTreeNode *mRoot;
+        VspKdNode *mRoot;
   
         /////////////////////////////
@@ -615 +694 @@
         
         // type of the splitting to use for the tree construction
-        enum {ESplitRegular, ESplitHeuristic };
+        enum {ESplitRegular, ESplitHeuristic};
         int splitType;
         
@@ -637 +716 @@
         vector<SortableEntry> *mSplitCandidates;
         
+        ViewCellsManager *mViewCellsManager;
+
+        /// maximal cost ratio of a merge
+        float mMaxCostRatio;
+
         /////////////////////////////
         // Construction parameters
@@ -658 +742 @@
         float mTermMaxRayContribution;
 
+        /// if only the "driving axis", i.e., the axis with the biggest extent
+        /// should be used for subdivision
         bool mOnlyDrivingAxis;
 
-        typedef std::pair<VspKdTreeLeaf *, VspKdTreeLeaf *> LeafPair;
+        /// maximal numbers of view cells
+        int mMaxViewCells;
 
         /////////////////////////////
@@ -667 +754 @@
 
 
-#endif // __LSDS_KDTREE_H__
-
+#endif // __VSP_KDTREE_H__
+

trunk/VUT/GtpVisibilityPreprocessor/src/VssPreprocessor.cpp

@@ -578 +578 @@
 
   //-- several visualizations and statistics
-  Debug << "===== Final view cells statistics ==========" << endl;
-
   mViewCellsManager->PrintStatistics(Debug);
 

trunk/VUT/GtpVisibilityPreprocessor/src/X3dExporter.cpp

@@ -593 +593 @@
 bool X3dExporter::ExportVspKdTree(const VspKdTree &tree, const int maxPvs)
 {
-        stack<VspKdTreeNode *> tStack;
+        stack<VspKdNode *> tStack;
 
         tStack.push(tree.GetRoot());
@@ -604 +604 @@
         while (!tStack.empty()) 
         {
-                VspKdTreeNode *node = tStack.top();
+                VspKdNode *node = tStack.top();
     
                 tStack.pop();
@@ -634 +634 @@
                         if (maxPvs > 0)
                         {
-                                VspKdTreeLeaf *leaf = dynamic_cast<VspKdTreeLeaf *>(node);
+                                VspKdLeaf *leaf = dynamic_cast<VspKdLeaf *>(node);
 
                                 mForcedMaterial.mDiffuseColor.b = 1.0f;
@@ -650 +650 @@
                 else  
                 {
-                        VspKdTreeInterior *interior = dynamic_cast<VspKdTreeInterior *>(node);
+                        VspKdInterior *interior = dynamic_cast<VspKdInterior *>(node);
                         tStack.push(interior->GetFront());
                         tStack.push(interior->GetBack());
@@ -658 +658 @@
         //ExportMesh(mesh);
         //DEL_PTR(mesh);
+
+        return true;
+}
+
+bool X3dExporter::ExportVspKdTreeViewCells(const VspKdTree &tree, const int maxPvs)
+{
+        ViewCellContainer vc;
+
+        //if (maxPvs > 0)
+        mUseForcedMaterial = true;
+
+        tree.CollectViewCells(vc);
+
+        ViewCellContainer::const_iterator it, it_end = vc.end();
+
+        for (it = vc.begin(); it != it_end; ++ it)
+        {
+                VspKdViewCell *viewCell = dynamic_cast<VspKdViewCell *>(*it);
+
+                if (maxPvs > 0)
+                {                       
+                        mForcedMaterial.mDiffuseColor.b = 1.0f;
+                        
+                        const float importance = (float)viewCell->GetPvs().GetSize() / (float)maxPvs;
+                        mForcedMaterial.mDiffuseColor.r = importance;
+                        mForcedMaterial.mDiffuseColor.g = 1.0f - mForcedMaterial.mDiffuseColor.r;
+                }
+                else 
+                        mForcedMaterial = RandomMaterial();
+
+                ExportVspKdTreeViewCell(tree, *viewCell);
+        }
+
+        return true;
+}
+
+bool X3dExporter::ExportVspKdTreeViewCell(const VspKdTree &tree, const VspKdViewCell &vc)
+{
+        vector<VspKdLeaf *>::const_iterator it, it_end = vc.mVspKdLeaves.end();
+
+        for (it = vc.mVspKdLeaves.begin(); it != it_end; ++ it)
+                ExportBox(tree.GetBBox(*it));
 
         return true;

trunk/VUT/GtpVisibilityPreprocessor/src/X3dExporter.h

@@ -21 +21 @@
 class VspBspTree;
 class BspNode;
+class VspKdViewCell;
+
 
 class X3dExporter : public Exporter
@@ -55 +57 @@
                                  );
 
-  bool 
+  bool
   ExportVspKdTree(const VspKdTree &tree, const int maxPvs);
 
@@ -61 +63 @@
 
   bool
-  ExportScene(SceneGraphNode *root) 
+  ExportScene(SceneGraphNode *root)
   {
     ExportSceneNode(root);
     return true;
   }
-  
-  virtual void 
+
+  virtual void
   ExportPolygon(Polygon3 *poly);
 
-  virtual void 
+  virtual void
   ExportPolygons(const PolygonContainer &polys);
 
@@ -85 +87 @@
   ExportMesh(Mesh *mesh);
 
-  virtual void 
+  virtual void
   ExportViewCell(ViewCell *viewCell);
 
-  virtual void 
+  virtual void
   ExportViewCells(const ViewCellContainer &viewCells);
 
-  virtual void 
+  virtual void
   ExportGeometry(const ObjectContainer &objects);
 
@@ -102 +104 @@
                          const RgbColor &color = RgbColor(1,1,1));
 
-  virtual void 
+  virtual void
   ExportBspSplitPlanes(const BspTree &tree);
-  
-  virtual void 
+
+  virtual void
   ExportBspSplits(const BspTree &tree, const bool exportDepth);
 
@@ -114 +116 @@
   ExportBspViewCellPartition(const BspTree &tree, const int maxPvs = 0);
 
-  virtual void 
+  virtual void
   ExportBspLeaves(const BspTree &tree, const int maxPvs = 0);
 
 
-  virtual void 
+  virtual void
   ExportBspSplits(const VspBspTree &tree, const bool exportDepth);
 
   virtual void
   ExportBspViewCellPartition(const VspBspTree &tree, const int maxPvs = 0);
+
+  virtual bool
+  ExportVspKdTreeViewCells(const VspKdTree &tree, const int maxPvs = 0);
 
 protected:
@@ -135 +140 @@
   bool
   ExportBspTreeRayDensity(const BspTree &tree);
-  
+
   void
   AddBoxToMesh(const AxisAlignedBox3 &box,
@@ -141 +146 @@
 
   void ExportBspNodeSplits(BspNode *root,
-                                                   const AxisAlignedBox3 &box, 
+                                                   const AxisAlignedBox3 &box,
                                                    const bool exportDepth,
+                                                   const bool epsilon);
 
+  bool ExportVspKdTreeViewCell(const VspKdTree &tree, const VspKdViewCell &vc);
 
-                                                   const bool epsilon);
 
   void ExportViewpoint(const Vector3 &point, const Vector3 &direction);
 
 };
- 
+