Changeset 600

Timestamp:

02/06/06 19:09:53 (18 years ago)

Author:

mattausch

Message:

 

Location:

trunk/VUT/GtpVisibilityPreprocessor

Files:

• scripts/default.env (modified) (9 diffs)
• src/ViewCell.cpp (modified) (13 diffs)
• src/ViewCell.h (modified) (3 diffs)
• src/ViewCellBsp.cpp (modified) (5 diffs)
• src/ViewCellsManager.cpp (modified) (13 diffs)
• src/ViewCellsManager.h (modified) (2 diffs)
• src/VspBspTree.cpp (modified) (25 diffs)
• src/VspBspTree.h (modified) (9 diffs)
• src/VssPreprocessor.cpp (modified) (4 diffs)

trunk/VUT/GtpVisibilityPreprocessor/scripts/default.env

@@ -13 +13 @@
 #;../data/vienna/vienna-plane.x3d
 #       filename ../data/vienna/viewcells-25-sel.x3d
-#       filename ../data/atlanta/atlanta2.x3d
+        filename ../data/atlanta/atlanta2.x3d
 #       filename ../data/soda/soda.dat
-        filename ../data/soda/soda5.dat
+#       filename ../data/soda/soda5.dat
 }
 
@@ -25 +25 @@
         type vss
 #       type rss
-        detectEmptyViewSpace true
+        detectEmptyViewSpace false
 }
 
@@ -36 +36 @@
         loadInitialSamples  false
         storeInitialSamples false
-        useViewSpaceBox true
+        useViewSpaceBox false
 #       testBeamSampling true
 }
@@ -176 +176 @@
         # samples used for view cell construction
         Construction {
-                samples 600000
-                samplesPerPass 200000
+                samples 2000000
+                samplesPerPass 500000
         }
 
         #number of active view cells
-        active 256
+        active 2048
         maxStaticMemory 40
 
-        exportToFile false
+        exportToFile true
         loadFromFile false
 
         #type kdTree
-        type vspKdTree
+        #type vspKdTree
         #type bspTree
         type vspBspTree
@@ -209 +209 @@
                 maxCostRatio 0.1
                 minViewCells 1
-                avgCostMaxDeviation 0.8
-                maxMergesPerPass 500 
+                avgCostMaxDeviation 0.01
+                maxMergesPerPass 500
                 useRaysForMerge false
                 refine false
                 compress false
-                merge false
+                merge true
         }
 
@@ -288 +288 @@
 VspBspTree {
         Construction {
-                samples 300000
+                samples 1000000
                 epsilon 0.005
                 randomize false
@@ -301 +301 @@
         # pvs                  = 1024
         
-        splitPlaneStrategy 1024
+        splitPlaneStrategy 1026
         
         # maximal candidates for split planes
-        maxPolyCandidates 0
+        maxPolyCandidates 200
 
         
@@ -322 +322 @@
         Termination {
                 # parameters used for autopartition
-                minRays                 -150
+                minRays                 500
                 minPolygons             -1
-                maxDepth                30
-                minPvs                  -10
-                #minProbability         0.0001
-                minProbability          -1
-#               maxRayContribution      0.3
-                maxRayContribution      2.3
-#               maxCostRatio            0.9
-                maxCostRatio            3.9
+                maxDepth                25
+                minPvs                  -1
+                minProbability          0.0000001
+                maxRayContribution      0.3
+                maxCostRatio            0.9
                 missTolerance           3
-
-                
-                maxViewCells            512
+                
+                maxViewCells            30000
                 
                 # used for pvs criterium
@@ -341 +337 @@
                 
                 AxisAligned {
-                        minRays                 1
+                        minRays                 20000
                         maxRayContribution      9.9
                 }
         }
         
-        splitUseOnlyDrivingAxis true
+        splitUseOnlyDrivingAxis false
         
         Visualization {
                 # x3d visualization of the split planes
-                exportSplits true
+                exportSplits false
         }
 }

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCell.cpp

@@ -22 +22 @@
         bool operator() (T v1, T v2) const
         {
-                return (v1->GetTimeStamp() < v2->GetTimeStamp());
+                return (v1->GetMergeCost() < v2->GetMergeCost());
         }
 };
@@ -107 +107 @@
 mValid(true),
 mParent(NULL),
-mTimeStamp(0),
+mMergeCost(0),
 mIsActive(false)
 {
@@ -119 +119 @@
 mValid(true),
 mParent(NULL),
-mTimeStamp(0),
+mMergeCost(0),
 mIsActive(false)
 {
@@ -230 +230 @@
 
 
-void ViewCell::SetTimeStamp(const int timeStamp)
-{
-        mTimeStamp = timeStamp;
-}
-
-
-int ViewCell::GetTimeStamp() const
-{
-        return mTimeStamp;
+void ViewCell::SetMergeCost(const float mergeCost)
+{
+        mMergeCost = mergeCost;
+}
+
+
+float ViewCell::GetMergeCost() const
+{
+        return mMergeCost;
 }
 
@@ -445 +445 @@
         float variance = 0;
         int totalPvs = 0;
-        float totalCost = 0;
+        float totalRenderCost = 0;
 
         //-- compute statistics values of initial view cells
-        mViewCellsManager->EvaluateRenderStatistics(totalCost,
+        mViewCellsManager->EvaluateRenderStatistics(totalRenderCost,
                                                                                                 mExpectedCost,
                                                                                                 mDeviation,
@@ -471 +471 @@
         Debug << "deviation: " << mDeviation << endl;
         Debug << "avg render cost: " << mAvgRenderCost << endl;
-        Debug << "expected cost: " <<mExpectedCost << endl;
+        Debug << "expected cost: " << mExpectedCost << endl;
 
 
@@ -498 +498 @@
 
         // frequency stats are updated
-        const int statsOut = 100;
+        const int statsOut = 1;
 
         // passes are needed for statistics, because we don't want to record
@@ -521 +521 @@
 
         //-- use priority queue to merge leaf pairs
-
-        while (!mMergeQueue.empty())// && (realNumActiveViewCells > mMergeMinViewCells))
+// HACK
+        //const float maxAvgCost = 350;
+        while (!mMergeQueue.empty())//NumActiveViewCells > mMergeMinViewCells))
         {
                 //-- reset merge queue if the ratio of current expected cost / real expected cost
@@ -588 +589 @@
                 {
                         ViewCell::NewMail();
-                                                
+
+                        //-- update statistical values
                         -- realNumActiveViewCells;
                         ++ mergeStats.merged;
                         ++ mergedPerPass;
 
-
-                        //-- update statistical values
+                        const float renderCostIncr = mc.GetRenderCost();
+                        const float mergeCostIncr = mc.GetMergeCost();
+
+                        totalRenderCost += renderCostIncr;
+                        mDeviation += mc.GetDeviationIncr();
+                        
+                        
+                        // merge the view cells of leaf1 and leaf2
+                        int pvsDiff;
+                        ViewCellInterior *mergedVc = 
+                                MergeViewCells(mc.mLeftViewCell, mc.mRightViewCell, pvsDiff);
+
 
                         // total render cost and deviation has changed
@@ -600 +612 @@
                         // cost heuristics, but cannot recompute costs on each increase of the 
                         // expected cost
-
-                        totalCost += mc.GetRenderCost();
-                        mDeviation += mc.GetDeviationIncr();
-                                                
-                        realExpectedCost = totalCost / (float)realNumActiveViewCells;
-                        
-                        const float currentMergeCost = mc.GetMergeCost();
-
-                        // merge the view cells of leaf1 and leaf2
-                        int pvsDiff;
-                        ViewCellInterior *mergedVc = 
-                                MergeViewCells(mc.mLeftViewCell, mc.mRightViewCell, pvsDiff);
-
                         totalPvs += pvsDiff;
-
-                        // set timestamp
-                        mergedVc->SetTimeStamp(mergeStats.merged);
-
+                        realExpectedCost = totalRenderCost / (float)realNumActiveViewCells;
                         realAvgRenderCost = (float)totalPvs / (float)realNumActiveViewCells;
+        
+                        // set merge cost to this node
+                        mergedVc->SetMergeCost(totalRenderCost);
+
 #if VC_HISTORY
                         if (mc.mLeftViewCell->IsSibling(mc.mRightViewCell))
@@ -632 +632 @@
                                         << "#Merged\n" << mergeStats.merged << endl 
                                         << "#Viewcells\n" << realNumActiveViewCells << endl 
-                                        << "#CurrentCost\n" << currentMergeCost << endl
-                                        << "#RelativeCost\n" << currentMergeCost / mOverallCost << endl
-                                        << "#CurrentPvs\n" << mc.GetLeftViewCell()->GetPvs().GetSize() << endl
-                                        << "#MergedSiblings\n" << mergeStats.siblings << endl
-                                        << "#AvgTreeDist\n" << mergeStats.AvgTreeDist() << endl
-                                        << "#UsedExpectedCost\n" << mExpectedCost << endl
-                                        << "#RealExpectedCost\n" << realExpectedCost << endl
-                                        << "#RealAvgRenderCost\n" << realAvgRenderCost << endl
-                                        << "#AvgRenderCost\n" << mAvgRenderCost << endl
-                                        << "#expectedCostRatio\n" << mExpectedCost / realExpectedCost << endl
-                                        << "#Deviation\n" << mDeviation / (float)realNumActiveViewCells << endl
-                                        << "#TotalDeviation\n" << mDeviation<< endl;
+                                        << "#RenderCostIncrease\n" << renderCostIncr << endl
+                                        << "#TotalRenderCost\n" << totalRenderCost << endl
+                                        << "#CurrentPvs\n" << mergedVc->GetPvs().GetSize() << endl
+                                        << "#ExpectedCost\n" << realExpectedCost << endl
+                                        << "#AvgRenderCost\n" << realAvgRenderCost << endl
+                                        << "#Deviation\n" << mDeviation << endl
+                                        << "#TotalPvs\n" << totalPvs << endl
+                                        << "#PvsSizeDecrease\n" << -pvsDiff << endl;
                         }
                 }
@@ -682 +678 @@
                 }*/
                 ViewCellInterior *root = mViewCellsManager->MergeViewCells(activeViewCells);
-
-                root->SetTimeStamp(mergeStats.merged + 1);
+                root->SetMergeCost(totalRenderCost);
                 mRoot = root;
         }
@@ -692 +687 @@
         }
 
+
+        while (!mMergeQueue.empty())
+        {
+                mMergeQueue.pop();
+        }
+        
+        
         // TODO delete because makes no sense here
         mergeStats.expectedRenderCost = realExpectedCost;

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCell.h

@@ -169 +169 @@
 
 
-        void SetTimeStamp(const int timeStamp);
-        int GetTimeStamp() const;
+        void SetMergeCost(const float mergeCost);
+        float GetMergeCost() const;
         static void NewMail(const int reserve = 1) {
                 sMailId += sReservedMailboxes;
@@ -201 +201 @@
         float mArea;
 
-        int mTimeStamp;
+        float mMergeCost;
 
         bool mValid;
@@ -265 +265 @@
 class ViewCellsTree
 {
+        friend class ViewCellsManager;
 public:
         ViewCellsTree(ViewCellsManager *vcm);

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp

@@ -414 +414 @@
                 << maxCostNodes * 100 / (double)Leaves() << endl;
 
-        app << "#N_PMINPROBABILITYAREALEAVES  ( Percentage of leaves with mininum probability )\n"
+        app << "#N_PMINPROBABILITYLEAVES  ( Percentage of leaves with mininum probability )\n"
                 << minProbabilityNodes * 100 / (double)Leaves() << endl;
 
@@ -864 +864 @@
 }
 
+
 bool BspTree::TerminationCriteriaMet(const BspTraversalData &data) const
 {
@@ -875 +876 @@
                  (data.GetAvgRayContribution() > mTermMaxRayContribution));
 }
+
 
 BspNode *BspTree::Subdivide(BspTraversalStack &tStack, BspTraversalData &tData)
@@ -1986 +1988 @@
 
         Intersectable::NewMail();
+        ViewCell::NewMail();
 
         Vector3 entp = origin;
@@ -2229 +2232 @@
 {
         ViewCellContainer leaves;
-        mViewCellsManager->GetViewCellsTree()->CollectLeaves(vc, leaves);
+        mViewCellsTree->CollectLeaves(vc, leaves);
 
         ViewCellContainer::const_iterator it, it_end = leaves.end();

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellsManager.cpp

@@ -58 +58 @@
         
         
-        environment->GetIntValue("ViewCells.active", mNumMergedViewCells);
+        environment->GetIntValue("ViewCells.active", mNumActiveViewCells);
         environment->GetBoolValue("ViewCells.PostProcess.compress", mCompressViewCells);
         environment->GetBoolValue("ViewCells.Visualization.useCuttingPlane", mUseCuttingPlaneForViz);
@@ -178 +178 @@
                                                 Preprocessor::SPATIAL_BOX_BASED_DISTRIBUTION;
 
+                if (0)
                 dirSamples = !dirSamples; // toggle sampling method
                 numSamples += CastPassSamples(mSamplesPerPass, 
@@ -692 +693 @@
         int axis = 0;
 
-        const float factor = 0.55;
+        const float factor = 0.35;
         Vector3 point = mViewSpaceBox.Min() +  mViewSpaceBox.Size() * factor;
 
@@ -1032 +1033 @@
                 if (exporter)
                 {
+                        
+                        if (0 && mExportRays)
+                                exporter->ExportRays(rays, RgbColor(1, 1, 1));
+
+                        
+                        if (mExportGeometry)
+                                exporter->ExportGeometry(objects);
+
                         //exporter->SetWireframe();
                         exporter->SetFilled();
                         ExportViewCellsForViz(exporter);
 
-                        if (0 && mExportRays)
-                                exporter->ExportRays(rays, RgbColor(1, 1, 1));
-
-                        if (mExportGeometry)
-                                exporter->ExportGeometry(objects);
 
                         delete exporter;
@@ -1063 +1067 @@
                 // we can use the view cells tree hierarchy to get the right set
                 mViewCellsTree->CollectBestViewCellSet(mViewCells, 
-                                                                                           mNumMergedViewCells);
+                                                                                           mNumActiveViewCells);
         }
 }
@@ -1113 +1117 @@
 
         //-- post processing of bsp view cells
+
     int vcSize = 0;
         int pvsSize = 0;
@@ -1124 +1129 @@
 
     Debug << ss << endl;
-
-        if (1) // export view cells
-        {
-                cout << "exporting initial view cells (=leaves) ... ";
-                Exporter *exporter = Exporter::GetExporter("view_cells.x3d");
-
-                if (exporter)
-                {
-                        //exporter->SetWireframe();
-                        exporter->SetFilled();
-                        ExportViewCellsForViz(exporter);
-
-                        if (mExportGeometry)
-                        {
-                                Material m;
-                                m.mDiffuseColor = RgbColor(0, 1, 0);
-                                exporter->SetForcedMaterial(m);
-                        
-                                exporter->SetWireframe();
-
-                                exporter->ExportGeometry(objects);
-                        }
-
-                        delete exporter;
-                }
-                cout << "finished" << endl;
-        }
 
         
@@ -1177 +1155 @@
         }
 
-        // reset view cells and stats
+    // reset view cells and stats
         ResetViewCells();
+
+        int savedColorCode  = mColorCode;
+
+        //BspLeaf::NewMail();
+        if (1) // export merged view cells
+        {
+                mColorCode = 0;
+                cout << "reseting view cells ... ";
+                ResetViewCells();
+                cout << "finished" << endl;
+
+                Exporter *exporter = Exporter::GetExporter("merged_view_cells.x3d");
+                Debug << "\nView cells after merge:\n" << mViewCellsStats << endl;
+
+                cout << "exporting view cells after merge ... ";
+
+                if (exporter)
+                {
+                        if (mExportGeometry)
+                                exporter->ExportGeometry(objects);
+
+                        //exporter->SetWireframe();
+                        exporter->SetFilled();
+                        ExportViewCellsForViz(exporter);
+
+
+                        delete exporter;
+                }
+                cout << "finished" << endl;
+        }
+
+        if (1) // export merged view cells
+        {
+                mColorCode = 1;
+
+                Exporter *exporter = Exporter::GetExporter("merged_view_cells_pvs.x3d");
+        
+                cout << "exporting view cells after merge (pvs size) ... ";     
+
+                if (exporter)
+                {
+                        //exporter->SetWireframe();
+                        
+                        if (mExportGeometry)
+                                exporter->ExportGeometry(objects);
+
+                        //exporter->SetWireframe();
+                        exporter->SetFilled();
+                        ExportViewCellsForViz(exporter);
+
+                        delete exporter;
+                }
+                cout << "finished" << endl;
+        }
+
+        mColorCode = savedColorCode;
+
         FinalizeViewCells(true);
         
-        // HACK: removes view cells in bsp leaves with active ones
-        if (0)
-                AddCurrentViewCellsToHierarchy();
-
         // write view cells to disc
         if (mExportViewCells)
@@ -1216 +1247 @@
                 return;
         
-        //BspLeaf::NewMail();
-        if (1) // export merged view cells
-        {
-
-                cout << "reseting view cells ... ";
-                ResetViewCells();
-
+        int savedColorCode = mColorCode;
+
+        
+        
+        if (1) // export final view cells
+        {
+                mColorCode = 1;
+
+                Exporter *exporter = Exporter::GetExporter("final_view_cells.x3d");
+        
+                cout << "exporting view cells after merge (pvs size) ... ";     
+
+                if (exporter)
+                {
+                        //exporter->SetWireframe();
+                        
+                        if (mExportGeometry)
+                                exporter->ExportGeometry(objects);
+
+                        //exporter->SetWireframe();
+                        exporter->SetFilled();
+                        ExportViewCellsForViz(exporter);
+
+                        delete exporter;
+                }
                 cout << "finished" << endl;
-
-                Exporter *exporter = Exporter::GetExporter("merged_view_cells.x3d");
-                Debug << "\nView cells after merge:\n" << mViewCellsStats << endl;
-
-                cout << "exporting view cells after merge ... ";
-
-                if (exporter)
-                {
-                        if (0)
-                                exporter->SetWireframe();
-                        else
-                                exporter->SetFilled();
-
-                        ExportViewCellsForViz(exporter);
-
-                        if (mExportGeometry)
-                        {
-                                Material m;
-                                m.mDiffuseColor = RgbColor(0, 1, 0);
-                                exporter->SetForcedMaterial(m);
-                                exporter->SetFilled();
-
-                                exporter->ExportGeometry(objects);
-                        }
-
-                        delete exporter;
-                }
-                cout << "finished" << endl;
-        }
+        }
+
+        mColorCode = savedColorCode;
 
         //-- visualization of the BSP splits
@@ -1265 +1288 @@
         }
 
+        // export single view cells
         ExportBspPvs(objects);
 }
@@ -1406 +1430 @@
                                                                           ViewCell *vc) const
 {
-                const bool vcValid = CheckValidity(vc, mMinPvsSize, mMaxPvsSize);
+        const bool vcValid = CheckValidity(vc, mMinPvsSize, mMaxPvsSize);
+
+        float importance = 0;
+        static Material m;
+
+        switch (mColorCode)
+        {
+        case 0: // Random
+                {
+                        if (vcValid)
+                        {
+                                m.mDiffuseColor.r = 0.5f + RandomValue(0.0f, 0.5f);
+                                m.mDiffuseColor.g = 0.5f + RandomValue(0.0f, 0.5f);
+                                m.mDiffuseColor.b = 0.5f + RandomValue(0.0f, 0.5f);
+                        }
+                        else
+                        {
+                                m.mDiffuseColor.r = 0.0f;
+                                m.mDiffuseColor.g = 1.0f;
+                                m.mDiffuseColor.b = 0.0f;
+                        }
+
+                        exporter->SetForcedMaterial(m);
+                        return;
+                }
+                
+        case 1: // pvs
+                {
+                        importance = (float)vc->GetPvs().GetSize() /
+                                (float)mViewCellsStats.maxPvs;
+
+                }
+                break;
+        case 2: // merges
+                {
+            int lSize = mViewCellsTree->GetSize(vc);
+                        importance = (float)lSize / (float)mViewCellsStats.maxLeaves;
+                }
+                //break;
+        case 3: // merge tree differene
+                {
+                        // TODO
+                        //importance = (float)GetMaxTreeDiff(vc) /
+                        //      (float)(mVspBspTree->GetStatistics().maxDepth * 2);
+
+                }
+                break;
+        default:
+                break;
+        }
+
+        // special color code for invalid view cells
+        m.mDiffuseColor.r = importance;
+        m.mDiffuseColor.g = 1.0f - m.mDiffuseColor.r;
+        m.mDiffuseColor.b = vcValid ? 1.0f : 0.0f;
+
+        //Debug << "importance: " << importance << endl;
+        exporter->SetForcedMaterial(m);
+}
+
+
+void BspViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
+                                                                                                 ViewCell *vc,
+                                                                                                 const Plane3 *cuttingPlane) const
+{
+        if (vc->GetMesh())
+        {
+                exporter->ExportMesh(vc->GetMesh());
+                return;
+        }
+
+        BspNodeGeometry geom;
+        mBspTree->ConstructGeometry(vc, geom);
+
+
+        if (cuttingPlane)
+        {
+                BspNodeGeometry front;
+                BspNodeGeometry back;
+
+                geom.SplitGeometry(front,
+                                                   back,
+                                                   *cuttingPlane,
+                                                   mViewSpaceBox, 
+                                                   0.0001f);
+
+                if ((int)back.mPolys.size() >= 3)
+                        exporter->ExportPolygons(back.mPolys);
+        }
+        else
+        {
+                
+                exporter->ExportPolygons(geom.mPolys);
+        }
+}
+
+
+void BspViewCellsManager::CreateMesh(ViewCell *vc)
+{
+        if (vc->GetMesh())
+                delete vc->GetMesh();
+
+        BspNodeGeometry geom;
+        
+        mBspTree->ConstructGeometry(vc, geom);
+
+        Mesh *mesh = new Mesh();
+        geom.AddToMesh(*mesh);
+        vc->SetMesh(mesh);
+        mMeshContainer.push_back(mesh);
+}
+
+
+void BspViewCellsManager::Finalize(ViewCell *viewCell, 
+                                                                   const bool createMesh)
+{
+        CreateMesh(viewCell);
+
+        float area = 0;
+        float volume = 0;
+
+        ViewCellContainer leaves;
+        mViewCellsTree->CollectLeaves(viewCell, leaves);
+
+        ViewCellContainer::const_iterator it, it_end = leaves.end();
+
+        for (it = leaves.begin(); it != it_end; ++ it)
+        {
+                BspNodeGeometry geom;
+                BspLeaf *leaf = dynamic_cast<BspViewCell *>(*it)->mLeaf;
+                mBspTree->ConstructGeometry(leaf, geom);
+
+                area += geom.GetArea();
+                volume += geom.GetVolume();
+        }
+
+        viewCell->SetVolume(volume);
+        viewCell->SetArea(area);
+}
+
+
+ViewCell *BspViewCellsManager::GetViewCell(const Vector3 &point) const
+{
+        if (!mBspTree)
+                return NULL;
+
+        if (!mViewSpaceBox.IsInside(point))
+                return NULL;
+        
+        return mBspTree->GetViewCell(point);
+}
+
+
+void BspViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays, 
+                                                                                                 vector<MergeCandidate> &candidates)
+{
+        cout << "collecting merge candidates ... " << endl;
+
+        if (mUseRaysForMerge)
+        {
+                mBspTree->CollectMergeCandidates(rays, candidates);
+        }
+        else
+        {
+                vector<BspLeaf *> leaves;
+                mBspTree->CollectLeaves(leaves);
+                mBspTree->CollectMergeCandidates(leaves, candidates);
+        }
+
+        cout << "fininshed collecting candidates" << endl;
+}
+
+
+
+bool BspViewCellsManager::ExportViewCells(const string filename)
+{
+        cout << "exporting view cells to xml ... ";
+        std::ofstream stream;
+
+        // for output we need unique ids for each view cell
+        CreateUniqueViewCellIds();
+
+
+        stream.open(filename.c_str());
+        stream << "<?xml version=\"1.0\" encoding=\"UTF-8\"?>"<<endl;
+        stream << "<Visibility_Solution>" << endl;
+
+        //-- the view space bounding box
+        stream << "<ViewSpaceBox" 
+                   << " min=\"" << mViewSpaceBox.Min().x << " " << mViewSpaceBox.Min().y << " " << mViewSpaceBox.Min().z << "\""
+                   << " max=\"" << mViewSpaceBox.Max().x << " " << mViewSpaceBox.Max().y << " " << mViewSpaceBox.Max().z << "\" />" << endl;
+
+        //-- the type of the view cells hierarchy
+        //stream << "<Hierarchy name=\"bspTree\" />" << endl;
+        stream << "<Hierarchy name=\"vspBspTree\" />" << endl; // write vsp bsp here because can use same tree and is bug free
+        //-- load the view cells itself, i.e., the ids and the pvs
+        stream << "<ViewCells>" << endl;
+        ViewCellContainer::const_iterator it, it_end = mViewCells.end();
+        for (it = mViewCells.begin(); it != it_end; ++ it)
+                ExportViewCell(*it, stream);
+
+        stream << "</ViewCells>" << endl;
+
+        //-- load the hierarchy
+        stream << "<Hierarchy>" << endl;
+        mBspTree->Export(stream);
+        stream << endl << "</Hierarchy>" << endl;
+
+        stream << "</Visibility_Solution>" << endl;
+        stream.close();
+
+        cout << "finished" << endl;
+
+        return true;
+}
+
+
+void BspViewCellsManager::AddCurrentViewCellsToHierarchy()
+{
+        ViewCellContainer::const_iterator it, it_end = mViewCells.end();
+        for (it = mViewCells.begin(); it != it_end; ++ it)
+        {
+                ViewCell *vc = *it;
+                ViewCellContainer leaves;
+                mViewCellsTree->CollectLeaves(vc, leaves);
+                
+                ViewCellContainer::const_iterator lit, lit_end = leaves.end();
+
+                for (lit = leaves.begin(); lit != lit_end; ++ lit)
+                {
+                        BspViewCell *bspVc = dynamic_cast<BspViewCell *>(*lit);
+                        bspVc->mLeaf->SetViewCell(vc);
+                }
+        }
+}
+
+/************************************************************************/
+/*                   KdViewCellsManager implementation                  */
+/************************************************************************/
+
+
+
+KdViewCellsManager::KdViewCellsManager(KdTree *kdTree):
+ViewCellsManager(), mKdTree(kdTree), mKdPvsDepth(100)
+{
+}
+
+float KdViewCellsManager::GetProbability(ViewCell *viewCell)
+{
+        // compute view cell area / volume as subsititute for probability
+#if 0
+        return GetArea(viewCell) / GetViewSpaceBox().SurfaceArea();
+#endif
+#if 1
+        return GetArea(viewCell) / GetAccVcArea();
+#endif
+#if 0
+        return GetVolume(viewCell) / GetViewSpaceBox().GetVolume();
+#endif
+}
+
+
+float KdViewCellsManager::GetRendercost(ViewCell *viewCell, float objRendercost) const
+{
+        return viewCell->GetPvs().GetSize() * objRendercost;
+}
+
+
+void KdViewCellsManager::CollectViewCells()
+{
+        //mKdTree->CollectViewCells(mViewCells); TODO
+}
+
+
+int KdViewCellsManager::ConstructSubdivision(const ObjectContainer &objects,
+                                                                  const VssRayContainer &rays)
+{
+        // if view cells already constructed
+        if (ViewCellsConstructed())
+                return 0;
+
+        mKdTree->Construct();
+
+        mTotalAreaValid = false;
+        // create the view cells
+        mKdTree->CreateAndCollectViewCells(mViewCells);
+
+        // cast rays
+        ComputeSampleContributions(rays, true, false);
+
+        EvaluateViewCellsStats();
+        Debug << "\nView cells after construction:\n" << mViewCellsStats << endl;
+
+        return 0;
+}
+
+
+bool KdViewCellsManager::ViewCellsConstructed() const
+{
+        return mKdTree->GetRoot() != NULL;
+}
+
+int KdViewCellsManager::PostProcess(const ObjectContainer &objects,
+                                                                        const VssRayContainer &rays)
+{
+        return 0;
+}
+
+void KdViewCellsManager::Visualize(const ObjectContainer &objects,
+                                                                   const VssRayContainer &sampleRays)
+{
+        if (!ViewCellsConstructed())
+                return;
+
+        // using view cells instead of the kd PVS of objects
+        const bool useViewCells = true;
+        bool exportRays = false;
+
+        int limit = min(mVisualizationSamples, (int)sampleRays.size());
+        const int pvsOut = min((int)objects.size(), 10);
+        VssRayContainer *rays = new VssRayContainer[pvsOut];
+
+        if (useViewCells)
+        {
+                const int leafOut = 10;
+
+                ViewCell::NewMail();
+
+                //-- some rays for output
+                const int raysOut = min((int)sampleRays.size(), mVisualizationSamples);
+                Debug << "visualization using " << raysOut << " samples" << endl;
+
+                //-- some random view cells and rays for output
+                vector<KdLeaf *> kdLeaves;
+
+                for (int i = 0; i < leafOut; ++ i)
+                        kdLeaves.push_back(dynamic_cast<KdLeaf *>(mKdTree->GetRandomLeaf()));
+
+                for (int i = 0; i < kdLeaves.size(); ++ i)
+                {
+                        KdLeaf *leaf = kdLeaves[i];
+                        RayContainer vcRays;
+
+                        cout << "creating output for view cell " << i << " ... ";
+#if 0
+                        // check whether we can add the current ray to the output rays
+                        for (int k = 0; k < raysOut; ++ k)
+                        {
+                                Ray *ray = sampleRays[k];
+
+                                for (int j = 0; j < (int)ray->bspIntersections.size(); ++ j)
+                                {
+                                        BspLeaf *leaf2 = ray->bspIntersections[j].mLeaf;
+
+                                        if (leaf->GetViewCell() == leaf2->GetViewCell())
+                                        {
+                                                vcRays.push_back(ray);
+                                        }
+                                }
+                        }
+#endif
+                        Intersectable::NewMail();
+
+                        ViewCell *vc = leaf->mViewCell;
+
+                        //bspLeaves[j]->Mail();
+                        char s[64]; sprintf(s, "kd-pvs%04d.x3d", i);
+
+                        Exporter *exporter = Exporter::GetExporter(s);
+                        exporter->SetFilled();
+
+                        exporter->SetWireframe();
+                        //exporter->SetFilled();
+
+                        Material m;//= RandomMaterial();
+                        m.mDiffuseColor = RgbColor(1, 1, 0);
+                        exporter->SetForcedMaterial(m);
+
+                        AxisAlignedBox3 box = mKdTree->GetBox(leaf);
+                        exporter->ExportBox(box);
+
+                        Debug << i << ": pvs size=" << (int)vc->GetPvs().GetSize()
+                                << ", piercing rays=" << (int)vcRays.size() << endl;
+
+                        // export rays piercing this view cell
+                        exporter->ExportRays(vcRays, 1000, RgbColor(0, 1, 0));
+
+                        m.mDiffuseColor = RgbColor(1, 0, 0);
+                        exporter->SetForcedMaterial(m);
+
+                        // exporter->SetWireframe();
+                        exporter->SetFilled();
+
+                        ObjectPvsMap::iterator it, it_end = vc->GetPvs().mEntries.end();
+                        // output PVS of view cell
+                        for (it = vc->GetPvs().mEntries.begin(); it !=  it_end; ++ it)
+                        {
+                                Intersectable *intersect = (*it).first;
+                                if (!intersect->Mailed())
+                                {
+                                        exporter->ExportIntersectable(intersect);
+                                        intersect->Mail();
+                                }
+                        }
+
+                        DEL_PTR(exporter);
+                        cout << "finished" << endl;
+                }
+
+                DEL_PTR(rays);
+        }
+        else // using kd PVS of objects
+        {
+                for (int i = 0; i < limit; ++ i)
+                {
+                        VssRay *ray = sampleRays[i];
+
+                        // check whether we can add this to the rays
+                        for (int j = 0; j < pvsOut; j++)
+                        {
+                                if (objects[j] == ray->mTerminationObject)
+                                {
+                                        rays[j].push_back(ray);
+                                }
+                        }
+                }
+
+                if (exportRays)
+                {
+                        Exporter *exporter = NULL;
+                        exporter = Exporter::GetExporter("sample-rays.x3d");
+                        exporter->SetWireframe();
+                        exporter->ExportKdTree(*mKdTree);
+
+                        for (i=0; i < pvsOut; i++)
+                                exporter->ExportRays(rays[i], RgbColor(1, 0, 0));
+
+                        exporter->SetFilled();
+
+                        delete exporter;
+                }
+
+                for (int k=0; k < pvsOut; k++)
+                {
+                        Intersectable *object = objects[k];
+                        char s[64];
+                        sprintf(s, "sample-pvs%04d.x3d", k);
+
+                        Exporter *exporter = Exporter::GetExporter(s);
+                        exporter->SetWireframe();
+
+                        KdPvsMap::iterator i = object->mKdPvs.mEntries.begin();
+                        Intersectable::NewMail();
+
+                        // avoid adding the object to the list
+                        object->Mail();
+                        ObjectContainer visibleObjects;
+
+                        for (; i != object->mKdPvs.mEntries.end(); i++)
+                        {
+                                KdNode *node = (*i).first;
+                                exporter->ExportBox(mKdTree->GetBox(node));
+
+                                mKdTree->CollectObjects(node, visibleObjects);
+                        }
+
+                        exporter->ExportRays(rays[k],  RgbColor(0, 1, 0));
+                        exporter->SetFilled();
+
+                        for (int j = 0; j < visibleObjects.size(); j++)
+                                exporter->ExportIntersectable(visibleObjects[j]);
+
+                        Material m;
+                        m.mDiffuseColor = RgbColor(1, 0, 0);
+                        exporter->SetForcedMaterial(m);
+                        exporter->ExportIntersectable(object);
+
+                        delete exporter;
+                }
+        }
+}
+
+
+void KdViewCellsManager::ExportColor(Exporter *exporter,
+                                                                         ViewCell *vc) const
+{
+        // TODO
+}
+
+ViewCell *KdViewCellsManager::GenerateViewCell(Mesh *mesh) const
+{
+        return new KdViewCell(mesh);
+}
+
+
+void KdViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
+                                                                                                ViewCell *vc,
+                                                                                                const Plane3 *cuttingPlane) const
+{
+        ViewCellContainer leaves;
+
+        mViewCellsTree->CollectLeaves(vc, leaves);
+        ViewCellContainer::const_iterator it, it_end = leaves.end();
+
+        for (it = leaves.begin(); it != it_end; ++ it)
+        {
+                KdViewCell *kdVc = dynamic_cast<KdViewCell *>(*it);
+        
+                exporter->ExportBox(mKdTree->GetBox(kdVc->mLeaf));
+        }
+}
+
+
+int KdViewCellsManager::GetType() const
+{
+        return ViewCellsManager::KD;
+}
+
+
+
+KdNode *KdViewCellsManager::GetNodeForPvs(KdLeaf *leaf)
+{
+        KdNode *node = leaf;
+
+        while (node->mParent && node->mDepth > mKdPvsDepth)
+                node = node->mParent;
+        return node;
+}
+
+int KdViewCellsManager::CastLineSegment(const Vector3 &origin,
+                                                                                const Vector3 &termination,
+                                                                                ViewCellContainer &viewcells)
+{
+        return mKdTree->CastLineSegment(origin, termination, viewcells);
+}
+
+
+void KdViewCellsManager::CreateMesh(ViewCell *vc)
+{
+        // TODO
+}
+
+
+
+void KdViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays, 
+                                                                                                vector<MergeCandidate> &candidates)
+{
+        // TODO
+}
+
+
+/**********************************************************************/
+/*                   VspKdViewCellsManager implementation             */
+/**********************************************************************/
+
+
+VspKdViewCellsManager::VspKdViewCellsManager(VspKdTree *vspKdTree):
+ViewCellsManager(), mVspKdTree(vspKdTree)
+{
+        environment->GetIntValue("VspKdTree.Construction.samples", mInitialSamples);
+        mVspKdTree->SetViewCellsManager(this);
+}
+
+float VspKdViewCellsManager::GetProbability(ViewCell *viewCell)
+{
+        // volume or area substitutes for view point probability
+#if 0
+        return GetArea(viewCell) / GetViewSpaceBox().SurfaceArea();
+#else
+        return GetArea(viewCell) / GetAccVcArea();
+#endif
+}
+
+
+float VspKdViewCellsManager::GetRendercost(ViewCell *viewCell, float objRendercost) const
+{
+        return viewCell->GetPvs().GetSize() * objRendercost;
+}
+
+
+void VspKdViewCellsManager::CollectViewCells()
+{
+        mVspKdTree->CollectViewCells(mViewCells);
+}
+
+
+int VspKdViewCellsManager::ConstructSubdivision(const ObjectContainer &objects,
+                                                                                                const VssRayContainer &rays)
+{
+        // if view cells already constructed
+        if (ViewCellsConstructed())
+                return 0;
+
+        VssRayContainer constructionRays;
+        VssRayContainer savedRays;
+
+        GetRaySets(rays,
+                           mInitialSamples,
+                           constructionRays,
+                           &savedRays);
+
+        Debug << "constructing vsp kd tree using "
+                  << (int)constructionRays.size() << " samples" << endl;
+
+        mVspKdTree->Construct(constructionRays, &mViewSpaceBox);
+        Debug << mVspKdTree->GetStatistics() << endl;
+
+        // export leaf building blocks
+        ExportLeaves(objects, rays);
+
+        // finally merge kd leaf building blocks to view cells
+        const int merged = mVspKdTree->MergeViewCells(rays);
+
+        // collapse siblings belonging to the same view cell
+        mVspKdTree->RefineViewCells(rays);
+
+        // collapse siblings belonging to the same view cell
+        mVspKdTree->CollapseTree();
+
+        // evaluale view cell stats
+        ResetViewCells();
+
+        Debug << "\nView cells after construction:\n" << mViewCellsStats << endl;
+
+        long startTime = GetTime();
+        // recast rest of rays
+        ComputeSampleContributions(savedRays, true, false);
+
+        Debug << "Computed remaining ray contribution in " << TimeDiff(startTime, GetTime()) * 1e-3
+                  << " secs" << endl;
+
+        return merged;
+}
+
+bool VspKdViewCellsManager::ViewCellsConstructed() const
+{
+        return mVspKdTree->GetRoot() != NULL;
+}
+
+
+ViewCell *VspKdViewCellsManager::GenerateViewCell(Mesh *mesh) const
+{
+        return new VspKdViewCell(mesh);
+}
+
+int VspKdViewCellsManager::PostProcess(const ObjectContainer &objects,
+                                                                           const VssRayContainer &rays)
+{
+        if (!ViewCellsConstructed())
+                return 0;
+
+        // recalculate stats
+        EvaluateViewCellsStats();
+
+        return 0;
+}
+
+
+void VspKdViewCellsManager::ExportLeaves(const ObjectContainer &objects,
+                                                                                 const VssRayContainer &sampleRays)
+{
+        if (!ViewCellsConstructed())
+                return;
+
+        //-- export leaf building blocks
+        Exporter *exporter = Exporter::GetExporter("vspkdtree.x3d");
+        if (!exporter)
+                return;
+
+        if (mExportGeometry)
+                exporter->ExportGeometry(objects);
+        
+        //exporter->SetWireframe();
+        //exporter->ExportVspKdTree(*mVspKdTree, mVspKdTree->GetStatistics().maxPvsSize);
+        exporter->ExportVspKdTree(*mVspKdTree);
+
+        if (mExportRays)
+        {
+                const float prob = (float)mVisualizationSamples
+                        / ((float)sampleRays.size() + Limits::Small);
+
+                exporter->SetWireframe();
+
+                //-- collect uniformly distributed rays
+                VssRayContainer rays;
+
+                for (int i = 0; i < sampleRays.size(); ++ i)
+                {
+                        if (RandomValue(0,1) < prob)
+                                rays.push_back(sampleRays[i]);
+                }
+                exporter->ExportRays(rays, RgbColor(1, 0, 0));
+        }
+
+        delete exporter;
+}
+
+void VspKdViewCellsManager::Visualize(const ObjectContainer &objects,
+                                                                          const VssRayContainer &sampleRays)
+{
+        if (!ViewCellsConstructed())
+                return;
+
+        //-- export single view cells
+        for (int i = 0; i < 10; ++ i)
+        {
+                char s[64];
+                sprintf(s, "vsp_viewcell%04d.x3d", i);
+                Exporter *exporter = Exporter::GetExporter(s);
+                const int idx =
+                        (int)RandomValue(0.0, (Real)((int)mViewCells.size() - 1));
+
+                VspKdViewCell *vc = dynamic_cast<VspKdViewCell *>(mViewCells[idx]);
+
+                cout << "Output view cell " << i << " with pvs size " << vc->GetPvs().GetSize() << endl;
+                Debug << "Output view cell " << i << " with pvs size " << vc->GetPvs().GetSize() << endl;
+                //-- export geometry
+                Material m;
+                m.mDiffuseColor = RgbColor(0, 1, 1);
+
+                exporter->SetForcedMaterial(m);
+                exporter->SetWireframe();
+
+                ExportViewCellGeometry(exporter, vc);
+
+                //-- export stored rays
+                
+                if (mExportRays)
+                {
+                        ViewCellContainer leaves;
+                        mViewCellsTree->CollectLeaves(vc, leaves);
+
+                        ViewCellContainer::const_iterator it,
+                                it_end = leaves.end();
+
+                        for (it = leaves.begin(); it != it_end; ++ it)
+                        {
+                                VspKdViewCell *vspKdVc = dynamic_cast<VspKdViewCell *>(*it);
+                                VspKdLeaf *leaf = vspKdVc->mLeaf;
+                                AxisAlignedBox3 box = mVspKdTree->GetBBox(leaf);
+
+                                VssRayContainer vssRays;
+
+                                VssRayContainer castRays;
+                                VssRayContainer initRays;
+
+                                leaf->GetRays(vssRays);
+
+                                VssRayContainer::const_iterator it, it_end = vssRays.end();
+                                const float prop = 200.0f / (float)vssRays.size();
+
+                                for (it = vssRays.begin(); it != it_end; ++ it)
+                                {
+                                        if (Random(1) < prop)
+                                                if ((*it)->mTerminationObject == NULL)
+                                                        castRays.push_back(*it);
+                                                else
+                                                        initRays.push_back(*it);
+                                }
+
+                                exporter->ExportRays(castRays, RgbColor(1, 0, 0));
+                                exporter->ExportRays(initRays, RgbColor(0, 1, 0));
+                        }
+                }
+        
+                //-- output PVS of view cell
+                m.mDiffuseColor = RgbColor(1, 0, 0);
+                exporter->SetForcedMaterial(m);
+
+                Intersectable::NewMail();
+
+                ObjectPvsMap::const_iterator it,
+                        it_end = vc->GetPvs().mEntries.end();
+
+                exporter->SetFilled();
+
+                for (it = vc->GetPvs().mEntries.begin(); it != it_end; ++ it)
+                {
+                        Intersectable *intersect = (*it).first;
+
+                        if (!intersect->Mailed())
+                        {
+                                Material m = RandomMaterial();
+                                exporter->SetForcedMaterial(m);
+
+                                exporter->ExportIntersectable(intersect);
+                                intersect->Mail();
+                        }
+                }
+
+                delete exporter;
+        }
+
+        //-- export final view cells
+        Exporter *exporter = Exporter::GetExporter("vspkdtree_merged.x3d");
+
+        //if (exportGeometry) exporter->SetWireframe();
+        //else exporter->SetFilled();
+
+        ExportViewCellsForViz(exporter);
+
+        if (mExportGeometry)
+        {
+                exporter->SetFilled();
+                exporter->ExportGeometry(objects);
+        }
+
+        if (mExportRays)
+        {
+                const float prob = (float)mVisualizationSamples
+                        / ((float)sampleRays.size() + Limits::Small);
+
+                exporter->SetWireframe();
+
+                VssRayContainer rays;
+
+                for (int i = 0; i < sampleRays.size(); ++ i)
+                {
+                  if (RandomValue(0,1) < prob)
+                        rays.push_back(sampleRays[i]);
+                }
+                exporter->ExportRays(rays, RgbColor(1, 0, 0));
+        }
+
+        delete exporter;
+}
+
+int VspKdViewCellsManager::GetType() const
+{
+        return VSP_KD;
+}
+
+
+int VspKdViewCellsManager::CastLineSegment(const Vector3 &origin,
+                                                                                   const Vector3 &termination,
+                                                                                   ViewCellContainer &viewcells)
+{
+        return mVspKdTree->CastLineSegment(origin, termination, viewcells);
+}
+
+
+void VspKdViewCellsManager::ExportColor(Exporter *exporter,
+                                                                                ViewCell *vc) const
+{
+        if (mColorCode == 0) // Random color
+                return;
+
+        float importance = 0;
+
+        switch (mColorCode)
+        {
+        case 1: // pvs
+                {
+                        importance = (float)vc->GetPvs().GetSize() /
+                                (float)mViewCellsStats.maxPvs;
+                }
+                break;
+        case 2: // merged leaves
+                {
+                int lSize = mViewCellsTree->GetSize(vc);
+                        importance = (float)lSize /
+                                (float)mViewCellsStats.maxLeaves;
+                }
+                break;
+        case 3: // merged tree depth difference
+                {
+                        //importance = (float)GetMaxTreeDiff(vc) /
+                        //      (float)(mVspBspTree->GetStatistics().maxDepth * 2);
+                }
+                break;
+        default:
+                break;
+        }
+
+        Material m;
+        m.mDiffuseColor.b = 1.0f;
+        m.mDiffuseColor.r = importance;
+        m.mDiffuseColor.g = 1.0f - m.mDiffuseColor.r;
+        //Debug << "importance: " << importance << endl;
+        exporter->SetForcedMaterial(m);
+}
+
+
+void VspKdViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
+                                                                                                   ViewCell *vc,
+                                                                                                   const Plane3 *cuttingPlane) const
+{
+        VspKdViewCell *kdVc = dynamic_cast<VspKdViewCell *>(vc);
+
+        Mesh m;
+
+        ViewCellContainer leaves;
+        mViewCellsTree->CollectLeaves(vc, leaves);
+
+        ViewCellContainer::const_iterator it, it_end = leaves.end();
+
+        for (it = leaves.begin(); it != it_end; ++ it)
+        {
+                VspKdLeaf *l = dynamic_cast<VspKdViewCell *>(*it)->mLeaf;
+                mVspKdTree->GetBBox(l).AddBoxToMesh(&m);
+        }
+
+        exporter->ExportMesh(&m);
+}
+
+
+void VspKdViewCellsManager::CreateMesh(ViewCell *vc)
+{
+        //TODO
+}
+
+
+void VspKdViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays, 
+                                                                                                   vector<MergeCandidate> &candidates)
+{
+        // TODO
+}
+
+
+/**************************************************************************/
+/*                   VspBspViewCellsManager implementation                */
+/**************************************************************************/
+
+
+VspBspViewCellsManager::VspBspViewCellsManager(VspBspTree *vspBspTree):
+ViewCellsManager(), mVspBspTree(vspBspTree)
+{
+        environment->GetIntValue("VspBspTree.Construction.samples", mInitialSamples);
+        mVspBspTree->SetViewCellsManager(this);
+        mVspBspTree->mViewCellsTree = mViewCellsTree;
+}
+
+
+VspBspViewCellsManager::~VspBspViewCellsManager()
+{
+}
+
+
+float VspBspViewCellsManager::GetProbability(ViewCell *viewCell)
+{
+        if (0 && mVspBspTree->mUseAreaForPvs)
+                return GetArea(viewCell) / GetAccVcArea();
+        else
+                return GetVolume(viewCell) / mViewSpaceBox.GetVolume();
+}
+
+
+void VspBspViewCellsManager::CollectViewCells()
+{
+        // view cells tree constructed
+        if (!ViewCellsTreeConstructed())
+        {
+                mVspBspTree->CollectViewCells(mViewCells, false);
+        }
+        else 
+        {
+                // we can use the view cells tree hierarchy to get the right set
+                mViewCellsTree->CollectBestViewCellSet(mViewCells, mNumActiveViewCells);
+        }
+
+}
+
+
+float VspBspViewCellsManager::GetRendercost(ViewCell *viewCell,
+                                                                                        float objRendercost) const
+{
+        return viewCell->GetPvs().GetSize() * objRendercost;
+}
+
+
+bool VspBspViewCellsManager::ViewCellsConstructed() const
+{
+        return mVspBspTree->GetRoot() != NULL;
+}
+
+
+ViewCell *VspBspViewCellsManager::GenerateViewCell(Mesh *mesh) const
+{
+        return new BspViewCell(mesh);
+}
+
+
+/*void VspBspViewCellsManager::CollectNodes(ViewCell *vc, vector<BspNode *>nodes)
+{
+        void ViewCellsTree::CollectLeaves(ViewCell *vc, vector<BspNode *> &nodes) const
+        
+        if (vc->IsLeaf())
+        {
+                BspViewCell *bvc = dynamic_cast<BspViewCell *>(vc);
+                nodes->push_back(bvc->mLeaf);
+        }
+        else
+        {
+                ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
+
+                for (it = interior->mChildren.begin; it != it_end; ++ it)
+                {
+                        vector<BspNode *> mynodes;
+                        CollectNodes(*it, mynodes);
+
+                        if (mynodes[0]->GetParent() && (mynodes[0]->GetParent() == mynodes[1]->GetParent()))
+                        {
+                                nodes.push_back(nodes[0]->GetParent());
+                        }
+
+                }
+        }
+}*/
+
+
+int VspBspViewCellsManager::ConstructSubdivision(const ObjectContainer &objects,
+                                                                                                 const VssRayContainer &rays)
+{
+        // if view cells were already constructed
+        if (ViewCellsConstructed())
+                return 0;
+
+        Debug << "Constructing bsp view cells" << endl;
+
+        int sampleContributions = 0;
+
+        VssRayContainer sampleRays;
+
+        int limit = min (mInitialSamples, (int)rays.size());
+
+        VssRayContainer constructionRays;
+        VssRayContainer savedRays;
+
+        Debug << "samples used for subdivision: " << mInitialSamples 
+                  << " rays: " << (int)rays.size() << endl;
+
+        GetRaySets(rays, mInitialSamples, constructionRays, &savedRays);
+
+        Debug << "initial rays: " << (int)constructionRays.size() << endl;
+        Debug << "saved rays: " << (int)savedRays.size() << endl;
+
+        mMaxPvsSize = (int)(mMaxPvsRatio * (float)objects.size());
+
+        mVspBspTree->Construct(constructionRays, &mViewSpaceBox);
+
+        Debug << mVspBspTree->GetStatistics() << endl;
+
+        // collapse invalid regions
+        cout << "collapsing invalid tree regions ... ";
+        long startTime = GetTime();
+        int collapsedLeaves = mVspBspTree->CollapseTree();
+        Debug << "collapsed in " << TimeDiff(startTime, GetTime()) * 1e-3 
+                  << " seconds" << endl;
+
+    cout << "finished" << endl;
+
+        cout << "reseting view cell stats ... ";
+        ResetViewCells();
+        cout << "finished" << endl;
+
+        Debug << "\nView cells after construction:\n" << mViewCellsStats << endl;
+
+        if (1) // export initial view cells
+        {
+                cout << "exporting initial view cells (=leaves) ... ";
+                Exporter *exporter = Exporter::GetExporter("view_cells.x3d");
+
+                if (exporter)
+                {
+                        if (0 && mExportRays)
+                                exporter->ExportRays(rays, RgbColor(1, 1, 1));
+
+                        if (mExportGeometry)
+                                exporter->ExportGeometry(objects);
+
+                        //exporter->SetWireframe();
+                        exporter->SetFilled();
+                        ExportViewCellsForViz(exporter);
+
+                        delete exporter;
+                }
+                cout << "finished" << endl;
+        }
+
+        startTime = GetTime();
+
+        // reset view cells and stats
+        ResetViewCells();
+
+        cout << "Computing remaining ray contributions ... ";
+        // recast rest of rays
+        ComputeSampleContributions(savedRays, true, false);
+        cout << "finished" << endl;
+
+        Debug << "Computed remaining ray contribution in " << TimeDiff(startTime, GetTime()) * 1e-3
+                  << " secs" << endl;
+
+        cout << "construction finished" << endl;
+
+        return sampleContributions;
+}
+
+
+void VspBspViewCellsManager::MergeViewCells(const VssRayContainer &rays,
+                                                                                        const ObjectContainer &objects)
+{
+        //-- post processing of bsp view cells
+    int vcSize = 0;
+        int pvsSize = 0;
+
+        mRenderer->RenderScene();
+        SimulationStatistics ss;
+        dynamic_cast<RenderSimulator *>(mRenderer)->GetStatistics(ss);
+    Debug << ss << endl;
+
+        //-- merge or subdivide view cells
+        int merged = 0;
+        if (mMergeViewCells)
+        {
+                cout << "starting merge using " << mPostProcessSamples << " samples ... " << endl;
+                long startTime = GetTime();
+
+        
+                // TODO: should be done BEFORE the ray casting
+                merged = mViewCellsTree->ConstructMergeTree(rays, objects);
+
+                //-- stats and visualizations
+                cout << "finished merging" << endl;
+                cout << "merged " << merged << " view cells in "
+                         << TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl;
+
+                Debug << "Postprocessing: Merged " << merged << " view cells in "
+                          << TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl << endl;
+        }
+
+        int savedColorCode = mColorCode;
+        
+        //BspLeaf::NewMail();
+        if (1) // export merged view cells
+        {
+                mColorCode = 0;
+                cout << "reseting view cells ... ";
+                ResetViewCells();
+
+                cout << "finished" << endl;
+
+                Exporter *exporter = Exporter::GetExporter("merged_view_cells.x3d");
+                Debug << "\nView cells after merge:\n" << mViewCellsStats << endl;
+
+                cout << "exporting view cells after merge ... ";
+
+                if (exporter)
+                {
+                        if (0)
+                                exporter->SetWireframe();
+                        else
+                                exporter->SetFilled();
+
+                        ExportViewCellsForViz(exporter);
+
+                        if (mExportGeometry)
+                        {
+                                Material m;
+                                m.mDiffuseColor = RgbColor(0, 1, 0);
+                                exporter->SetForcedMaterial(m);
+                                exporter->SetFilled();
+
+                                exporter->ExportGeometry(objects);
+                        }
+
+                        delete exporter;
+                }
+                cout << "finished" << endl;
+        }
+
+        if (1) // export merged view cells
+        {
+                mColorCode = 1;
+
+                Exporter *exporter = Exporter::GetExporter("merged_view_cells_pvs.x3d");
+        
+                cout << "exporting view cells after merge (pvs size) ... ";     
+
+                if (exporter)
+                {
+                        if (0)
+                                exporter->SetWireframe();
+                        else
+                                exporter->SetFilled();
+
+                        ExportViewCellsForViz(exporter);
+
+                        if (mExportGeometry)
+                        {
+                                Material m;
+                                m.mDiffuseColor = RgbColor(0, 1, 0);
+                                exporter->SetForcedMaterial(m);
+                                exporter->SetFilled();
+
+                                exporter->ExportGeometry(objects);
+                        }
+
+                        delete exporter;
+                }
+                cout << "finished" << endl;
+        }
+
+        mColorCode = savedColorCode;
+
+}
+
+
+void VspBspViewCellsManager::RefineViewCells(const VssRayContainer &rays,
+                                                                                         const ObjectContainer &objects)
+{
+        Debug << "render time before refine:" << endl;
+        mRenderer->RenderScene();
+        SimulationStatistics ss;
+        dynamic_cast<RenderSimulator *>(mRenderer)->GetStatistics(ss);
+    Debug << ss << endl;
+
+        cout << "Refining the merged view cells ... ";
+        long startTime = GetTime();
+
+        // refining the merged view cells
+        const int refined = mViewCellsTree->RefineViewCells(rays, objects);
+
+        //-- stats and visualizations
+        cout << "finished" << endl;
+        cout << "refined " << refined << " view cells in "
+                 << TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl;
+
+        Debug << "Postprocessing: refined " << refined << " view cells in "
+                  << TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl << endl;
+}
+
+
+int VspBspViewCellsManager::PostProcess(const ObjectContainer &objects,
+                                                                                const VssRayContainer &rays)
+{
+        if (!ViewCellsConstructed())
+        {
+                Debug << "postprocess error: no view cells constructed" << endl;
+                return 0;
+        }
+
+
+        // view cells already finished before post processing step (i.e. because they were loaded)
+        if (mViewCellsFinished)
+        {
+                FinalizeViewCells(true);
+                EvaluateViewCellsStats();
+
+                return 0;
+        }
+
+
+        // check if new view cells turned invalid
+        SetValidity(mMinPvsSize, mMaxPvsSize); 
+        // update valid view space according to valid view cells
+        mVspBspTree->ValidateTree();
+
+        // recompute view cell statistics
+        mViewCellsStats.Reset();
+        EvaluateViewCellsStats();
+
+        // has to be recomputed
+        mTotalAreaValid = false;
+
+
+        VssRayContainer postProcessRays;
+        GetRaySets(rays, mPostProcessSamples, postProcessRays);
+
+        Debug << "post processing using " << (int)postProcessRays.size() << " samples" << endl;
+
+        Debug << "\nview cell partition after sampling:\n" << mViewCellsStats << endl << endl;
+
+        // should maybe be done here to allow merge working with area or volume
+        // and to correct the rendering statistics
+        if (0)
+        {
+                FinalizeViewCells(false);
+        }
+
+        //-- merge the individual view cells
+        MergeViewCells(postProcessRays, objects);
+        
+
+        //-- refines the merged view cells
+        if (0)
+                RefineViewCells(postProcessRays, objects);
+
+        
+        if (1)
+        {               
+                float totalCost, erc, var, dev, avg;
+                int totalpvs;
+
+                mViewCellsStats.Reset();
+
+        EvaluateRenderStatistics(totalCost, erc, dev, var, totalpvs, avg);
+                
+                Debug << "statistics after merge "  
+                          << " erc: " << erc 
+                          << " dev: " << dev
+                          << " totalpvs: " << totalpvs 
+                          << " avg: " << avg << endl;
+        }
+
+        //-- render simulation after merge
+  cout << "\nevaluating bsp view cells render time before compress ... ";
+  dynamic_cast<RenderSimulator *>(mRenderer)->RenderScene();
+  SimulationStatistics ss;
+  dynamic_cast<RenderSimulator *>(mRenderer)->GetStatistics(ss);
+  
+  cout << " finished" << endl;
+  cout << ss << endl;
+  Debug << ss << endl;
+
+
+
+        //-- compression
+
+        if (ViewCellsTreeConstructed() && mCompressViewCells)
+        {
+                int pvsEntries = mViewCellsTree->GetNumPvsEntries(mViewCellsTree->GetRoot());
+                Debug << "number of entries before compress: " << pvsEntries << endl;
+
+                mViewCellsTree->CompressViewCellsPvs();
+
+                pvsEntries = mViewCellsTree->GetNumPvsEntries(mViewCellsTree->GetRoot());
+                Debug << "number of entries after compress: " << pvsEntries << endl;
+        }
+
+
+        //-- export refined (shuffled) view cells
+        if (0)
+        {
+                cout << "exporting shuffled view cells ... ";
+
+                Exporter *exporter = Exporter::GetExporter("shuffled_view_cells.x3d");
+                if (exporter)
+                {
+                        if (1)
+                        {
+                                exporter->SetWireframe();
+                                exporter->ExportBox(mViewSpaceBox);
+                                exporter->SetFilled();
+                        }
+
+                        if (mExportGeometry)
+                        {
+                                exporter->ExportGeometry(objects);
+                        }
+
+                        ViewCellContainer::const_iterator vit, vit_end = mViewCells.end();
+
+                        Material vm, lm;
+
+                        for (vit = mViewCells.begin(); vit != mViewCells.end(); ++ vit)
+                        {
+                                ViewCell *vc = *vit;
+
+                                vm = RandomMaterial();
+
+                                lm = vm;
+
+                                vm.mDiffuseColor.r -= 0.45f;
+                                vm.mDiffuseColor.g -= 0.45f;
+                                vm.mDiffuseColor.b -= 0.45f;
+
+
+                                ViewCellContainer leaves;
+                                mViewCellsTree->CollectLeaves(vc, leaves);
+
+                                ViewCellContainer::const_iterator lit, lit_end = leaves.end();
+
+                                for (lit = leaves.begin(); lit != lit_end; ++ lit)
+                                {
+                                        BspLeaf *leaf = dynamic_cast<BspViewCell *>(*lit)->mLeaf;
+
+                                        if (leaf->Mailed())
+                                                exporter->SetForcedMaterial(lm);
+                                        else
+                                                exporter->SetForcedMaterial(vm);
+
+                                        BspNodeGeometry geom;
+                                        mVspBspTree->ConstructGeometry(leaf, geom);
+                                        exporter->ExportPolygons(geom.mPolys);
+                                }
+                        }
+
+                        delete exporter;
+                }
+
+
+                cout << "finished" << endl;
+        }
+
+        // collapse sibling leaves that share the same view cell
+        if (0)
+                mVspBspTree->CollapseTree();
+
+        // recompute view cell list and statistics
+        ResetViewCells();
+
+        // real meshes are only contructed only at this stage
+        FinalizeViewCells(true);
+
+        // write view cells to disc
+        if (mExportViewCells)
+        {
+                char buff[100];
+                environment->GetStringValue("ViewCells.filename", buff);
+                string vcFilename(buff);
+
+                ExportViewCells(buff);
+        }
+
+        return 0;
+}
+
+
+int VspBspViewCellsManager::GetType() const
+{
+        return VSP_BSP;
+}
+
+
+bool VspBspViewCellsManager::GetViewPoint(Vector3 &viewPoint) const
+{
+        if (!ViewCellsConstructed())
+                return ViewCellsManager::GetViewPoint(viewPoint);
+
+        // TODO: set reasonable limit
+        const int limit = 20;
+
+        for (int i = 0; i < limit; ++ i)
+        {
+                viewPoint = mViewSpaceBox.GetRandomPoint();
+                if (mVspBspTree->ViewPointValid(viewPoint))
+                {
+                        return true;
+                }
+        }
+        Debug << "failed to find valid view point, taking " << viewPoint << endl;
+        return false;
+}
+
+
+bool VspBspViewCellsManager::ViewPointValid(const Vector3 &viewPoint) const
+{
+  // $$JB -> implemented in viewcellsmanager (slower, but allows dynamic
+  // validy update in preprocessor for all managers)
+  return ViewCellsManager::ViewPointValid(viewPoint);
+
+  //    return mViewSpaceBox.IsInside(viewPoint) &&
+  //               mVspBspTree->ViewPointValid(viewPoint);
+}
+
+
+void VspBspViewCellsManager::Visualize(const ObjectContainer &objects,
+                                                                           const VssRayContainer &sampleRays)
+{
+        if (!ViewCellsConstructed())
+                return;
+
+        VssRayContainer visRays;
+        GetRaySets(sampleRays, mVisualizationSamples, visRays);
+
+        
+        if (1) // export view cells
+        {// hack pvs
+                int savedColorCode = mColorCode;
+                mColorCode = 1;
+                Exporter *exporter = Exporter::GetExporter("final_view_cells.x3d");
+                
+                if (exporter)
+                {
+                        cout << "exporting view cells after post process ... ";
+
+                        if (0)
+                        {
+                                exporter->SetWireframe();
+                                exporter->ExportBox(mViewSpaceBox);
+                                exporter->SetFilled();
+                        }
+
+                        if (mExportGeometry)
+                        {
+                                exporter->ExportGeometry(objects);
+                        }
+
+                        // export rays
+                        if (mExportRays)
+                        {
+                                exporter->ExportRays(visRays, RgbColor(0, 1, 0));
+                        }
+
+                        ExportViewCellsForViz(exporter);
+                        delete exporter;
+                        cout << "finished" << endl;
+                }
+
+                mColorCode = savedColorCode;
+        }
+
+        if (0)
+        {
+                cout << "exporting depth map ... ";
+
+                Exporter *exporter = Exporter::GetExporter("depth_map.x3d");
+                if (exporter)
+                {
+                        if (1)
+                        {
+                                exporter->SetWireframe();
+                                exporter->ExportBox(mViewSpaceBox);
+                                exporter->SetFilled();
+                        }
+
+                        if (mExportGeometry)
+                        {
+                                exporter->ExportGeometry(objects);
+                        }
+
+                        const int maxDepth = mVspBspTree->mBspStats.maxDepth;
+
+                        ViewCellContainer::const_iterator vit, vit_end = mViewCells.end();
+
+                        for (vit = mViewCells.begin(); vit != mViewCells.end(); ++ vit)
+                        {
+                                ViewCell *vc = *vit;
+
+                                ViewCellContainer leaves;
+                                mViewCellsTree->CollectLeaves(vc, leaves);
+
+                                ViewCellContainer::const_iterator lit, lit_end = leaves.end();
+
+                                for (lit = leaves.begin(); lit != lit_end; ++ lit)
+                                {
+                                        BspLeaf *leaf = dynamic_cast<BspViewCell *>(*lit)->mLeaf;
+
+                                        Material m; 
+
+                                        float relDepth = (float)leaf->GetDepth() / (float)maxDepth;
+                                        m.mDiffuseColor.r = relDepth;
+                                        m.mDiffuseColor.g = 0.0f;
+                                        m.mDiffuseColor.b = 1.0f - relDepth;
+
+                    exporter->SetForcedMaterial(m);
+                                
+
+                                        BspNodeGeometry geom;
+                                        mVspBspTree->ConstructGeometry(leaf, geom);
+                                        exporter->ExportPolygons(geom.mPolys);
+                                }
+                        }
+
+                        delete exporter;
+                }
+
+
+                cout << "finished" << endl;
+        }
+
+        //-- visualization of the BSP splits
+        bool exportSplits = false;
+        environment->GetBoolValue("VspBspTree.Visualization.exportSplits", exportSplits);
+
+        if (exportSplits)
+        {
+                cout << "exporting splits ... ";
+                ExportSplits(objects, visRays);
+                cout << "finished" << endl;
+        }
+
+        //-- export single view cells
+        ExportBspPvs(objects, visRays);
+}
+
+
+void VspBspViewCellsManager::ExportSplits(const ObjectContainer &objects,
+                                                                                  const VssRayContainer &rays)
+{
+        Exporter *exporter = Exporter::GetExporter("bsp_splits.x3d");
+
+        if (exporter)
+        {
+                Material m;
+                m.mDiffuseColor = RgbColor(1, 0, 0);
+                exporter->SetForcedMaterial(m);
+                exporter->SetWireframe();
+
+                exporter->ExportBspSplits(*mVspBspTree, true);
+
+                // take forced material, else big scenes cannot be viewed
+                m.mDiffuseColor = RgbColor(0, 1, 0);
+                exporter->SetForcedMaterial(m);
+                exporter->SetFilled();
+
+                exporter->ResetForcedMaterial();
+
+                // export rays
+                if (mExportRays)
+                        exporter->ExportRays(rays, RgbColor(1, 1, 0));
+
+                if (mExportGeometry)
+                        exporter->ExportGeometry(objects);
+
+                delete exporter;
+        }
+}
+
+
+void VspBspViewCellsManager::ExportBspPvs(const ObjectContainer &objects,
+                                                                                  const VssRayContainer &rays)
+{
+        const int leafOut = 10;
+
+        ViewCell::NewMail();
+
+        cout << "visualization using " << mVisualizationSamples << " samples" << endl;
+        Debug << "\nOutput view cells: " << endl;
+
+        // sort view cells to visualize the largest view cells
+        if (0)
+                stable_sort(mViewCells.begin(), mViewCells.end(), vc_gt);
+
+        int limit = min(leafOut, (int)mViewCells.size());
+
+        int raysOut;
+
+        //-- some rays for output
+        if (1)
+                raysOut = min((int)rays.size(), mVisualizationSamples);
+
+        for (int i = 0; i < limit; ++ i)
+        {
+                cout << "creating output for view cell " << i << " ... ";
+
+                VssRayContainer vcRays;
+                Intersectable::NewMail();
+                ViewCell *vc;
+        
+                if (0) // largest view cell pvs first
+                        vc = mViewCells[i];
+                else
+                        vc = mViewCells[Random((int)mViewCells.size())];
+
+                vector<ViewCell *> leaves;
+                mViewCellsTree->CollectLeaves(vc, leaves);
+
+        if (1)
+                {
+                        // check whether we can add the current ray to the output rays
+                        for (int k = 0; k < raysOut; ++ k)
+                        {
+                                VssRay *ray = rays[k];
+                                for     (int j = 0; j < (int)ray->mViewCells.size(); ++ j)
+                                {
+                                        ViewCell *rayvc = ray->mViewCells[j];
+
+                                        if (leaves[0] == rayvc)
+                                                vcRays.push_back(ray);
+                                }
+                        }
+                }
+
+                //bspLeaves[j]->Mail();
+                char s[64]; sprintf(s, "bsp-pvs%04d.x3d", i);
+                Exporter *exporter = Exporter::GetExporter(s);
+                exporter->SetWireframe();
+
+                Material m;//= RandomMaterial();
+                m.mDiffuseColor = RgbColor(0, 1, 0);
+                exporter->SetForcedMaterial(m);
+
+                ExportViewCellGeometry(exporter, vc);
+
+
+                Debug << i << ": pvs size=" << (int)mViewCellsTree->GetPvsSize(vc)
+                          << ", piercing rays=" << (int)vcRays.size() << endl;
+                        //  << ", leaves=" << (int)vc->mLeaves.size() << endl;
+
+                
+                //-- export rays piercing this view cell
+                if (1)
+                {
+                        exporter->ExportRays(vcRays, RgbColor(1, 1, 1));
+                }
+                else
+                {
+
+                        ViewCellContainer leaves;
+                        mViewCellsTree->CollectLeaves(vc, leaves);
+
+                        ViewCellContainer::const_iterator lit, lit_end = leaves.end();
+
+                        for (lit = leaves.begin(); lit != lit_end; ++ lit)
+                        {
+                                BspLeaf *l = dynamic_cast<BspViewCell *>(*lit)->mLeaf;
+                                exporter->ExportRays(l->mVssRays);
+                        }
+                }
+
+        
+                m.mDiffuseColor = RgbColor(1, 0, 0);
+                exporter->SetForcedMaterial(m);
+
+                ObjectPvsMap::const_iterator it,
+                        it_end = vc->GetPvs().mEntries.end();
+
+                exporter->SetFilled();
+
+        
+                // output PVS of view cell
+                for (it = vc->GetPvs().mEntries.begin(); it != it_end; ++ it)
+                {
+                
+                        Intersectable *intersect = (*it).first;
+
+                        if (!intersect->Mailed())
+                        {
+                                Material m = RandomMaterial();
+                                exporter->SetForcedMaterial(m);
+
+                                exporter->ExportIntersectable(intersect);
+                                intersect->Mail();
+                        }
+                }
+
+                
+                DEL_PTR(exporter);
+                cout << "finished" << endl;
+        }
+
+        Debug << endl;
+}
+
+
+int VspBspViewCellsManager::CastLineSegment(const Vector3 &origin,
+                                                                                        const Vector3 &termination,
+                                                                                        ViewCellContainer &viewcells)
+{
+        return mVspBspTree->CastLineSegment(origin, termination, viewcells);
+}
+
+
+void VspBspViewCellsManager::ExportColor(Exporter *exporter,
+                                                                                 ViewCell *vc) const
+{
+        const bool vcValid = CheckValidity(vc, mMinPvsSize, mMaxPvsSize);
 
         float importance = 0;
@@ -1442 +3213 @@
                 {
             int lSize = mViewCellsTree->GetSize(vc);
-        
-                        importance = (float)lSize / (float)mViewCellsStats.maxLeaves;
-                }
-                //break;
-        case 3: // merge tree differene
-                {
-                        // TODO
-                        //importance = (float)GetMaxTreeDiff(vc) /
-                        //      (float)(mVspBspTree->GetStatistics().maxDepth * 2);
-
-                }
-                break;
-        default:
-                break;
-        }
-
-        // special color code for invalid view cells
-        m.mDiffuseColor.r = importance;
-        m.mDiffuseColor.g = 1.0f - m.mDiffuseColor.r;
-        m.mDiffuseColor.b = vcValid ? 1.0f : 0.0f;
-
-        //Debug << "importance: " << importance << endl;
-        exporter->SetForcedMaterial(m);
-}
-
-
-void BspViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
-                                                                                                 ViewCell *vc,
-                                                                                                 const Plane3 *cuttingPlane) const
-{
-        if (vc->GetMesh())
-        {
-                exporter->ExportMesh(vc->GetMesh());
-        
-                return;
-        }
-
-        BspNodeGeometry geom;
-        mBspTree->ConstructGeometry(vc, geom);
-
-
-        if (cuttingPlane)
-        {
-                BspNodeGeometry front;
-                BspNodeGeometry back;
-
-                geom.SplitGeometry(front,
-                                                   back,
-                                                   *cuttingPlane,
-                                                   mViewSpaceBox, 
-                                                   0.0001);
-
-                exporter->ExportPolygons(back.mPolys);
-        }
-        else
-        {
-                exporter->ExportPolygons(geom.mPolys);
-        }
-}
-
-
-void BspViewCellsManager::CreateMesh(ViewCell *vc)
-{
-        if (vc->GetMesh())
-                delete vc->GetMesh();
-
-        BspNodeGeometry geom;
-        
-        mBspTree->ConstructGeometry(vc, geom);
-
-        Mesh *mesh = new Mesh();
-        geom.AddToMesh(*mesh);
-        vc->SetMesh(mesh);
-        mMeshContainer.push_back(mesh);
-}
-
-
-void BspViewCellsManager::Finalize(ViewCell *viewCell, 
-                                                                   const bool createMesh)
-{
-        CreateMesh(viewCell);
-
-        float area = 0;
-        float volume = 0;
-
-        ViewCellContainer leaves;
-        mViewCellsTree->CollectLeaves(viewCell, leaves);
-
-        ViewCellContainer::const_iterator it, it_end = leaves.end();
-
-        for (it = leaves.begin(); it != it_end; ++ it)
-        {
-                BspNodeGeometry geom;
-                BspLeaf *leaf = dynamic_cast<BspViewCell *>(*it)->mLeaf;
-                mBspTree->ConstructGeometry(leaf, geom);
-
-                area += geom.GetArea();
-                volume += geom.GetVolume();
-        }
-
-        viewCell->SetVolume(volume);
-        viewCell->SetArea(area);
-}
-
-
-ViewCell *BspViewCellsManager::GetViewCell(const Vector3 &point) const
-{
-        if (!mBspTree)
-                return NULL;
-
-        if (!mViewSpaceBox.IsInside(point))
-                return NULL;
-        
-        return mBspTree->GetViewCell(point);
-}
-
-
-void BspViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays, 
-                                                                                                 vector<MergeCandidate> &candidates)
-{
-        cout << "collecting merge candidates ... " << endl;
-
-        if (mUseRaysForMerge)
-        {
-                mBspTree->CollectMergeCandidates(rays, candidates);
-        }
-        else
-        {
-                vector<BspLeaf *> leaves;
-                mBspTree->CollectLeaves(leaves);
-                mBspTree->CollectMergeCandidates(leaves, candidates);
-        }
-
-        cout << "fininshed collecting candidates" << endl;
-}
-
-
-
-bool BspViewCellsManager::ExportViewCells(const string filename)
-{
-        cout << "exporting view cells to xml ... ";
-        std::ofstream stream;
-
-        // for output we need unique ids for each view cell
-        CreateUniqueViewCellIds();
-
-
-        stream.open(filename.c_str());
-        stream << "<?xml version=\"1.0\" encoding=\"UTF-8\"?>"<<endl;
-        stream << "<Visibility_Solution>" << endl;
-
-        //-- the view space bounding box
-        stream << "<ViewSpaceBox" 
-                   << " min=\"" << mViewSpaceBox.Min().x << " " << mViewSpaceBox.Min().y << " " << mViewSpaceBox.Min().z << "\""
-                   << " max=\"" << mViewSpaceBox.Max().x << " " << mViewSpaceBox.Max().y << " " << mViewSpaceBox.Max().z << "\" />" << endl;
-
-        //-- the type of the view cells hierarchy
-        //stream << "<Hierarchy name=\"bspTree\" />" << endl;
-        stream << "<Hierarchy name=\"vspBspTree\" />" << endl; // write vsp bsp here because can use same tree and is bug free
-        //-- load the view cells itself, i.e., the ids and the pvs
-        stream << "<ViewCells>" << endl;
-        ViewCellContainer::const_iterator it, it_end = mViewCells.end();
-        for (it = mViewCells.begin(); it != it_end; ++ it)
-                ExportViewCell(*it, stream);
-
-        stream << "</ViewCells>" << endl;
-
-        //-- load the hierarchy
-        stream << "<Hierarchy>" << endl;
-        mBspTree->Export(stream);
-        stream << endl << "</Hierarchy>" << endl;
-
-        stream << "</Visibility_Solution>" << endl;
-        stream.close();
-
-        cout << "finished" << endl;
-
-        return true;
-}
-
-
-void BspViewCellsManager::AddCurrentViewCellsToHierarchy()
-{
-        ViewCellContainer::const_iterator it, it_end = mViewCells.end();
-        for (it = mViewCells.begin(); it != it_end; ++ it)
-        {
-                ViewCell *vc = *it;
-                ViewCellContainer leaves;
-                mViewCellsTree->CollectLeaves(vc, leaves);
-                
-                ViewCellContainer::const_iterator lit, lit_end = leaves.end();
-
-                for (lit = leaves.begin(); lit != lit_end; ++ lit)
-                {
-                        BspViewCell *bspVc = dynamic_cast<BspViewCell *>(*lit);
-                        bspVc->mLeaf->SetViewCell(vc);
-                }
-        }
-}
-
-/************************************************************************/
-/*                   KdViewCellsManager implementation                  */
-/************************************************************************/
-
-
-
-KdViewCellsManager::KdViewCellsManager(KdTree *kdTree):
-ViewCellsManager(), mKdTree(kdTree), mKdPvsDepth(100)
-{
-}
-
-float KdViewCellsManager::GetProbability(ViewCell *viewCell)
-{
-        // compute view cell area / volume as subsititute for probability
-#if 0
-        return GetArea(viewCell) / GetViewSpaceBox().SurfaceArea();
-#endif
-#if 1
-        return GetArea(viewCell) / GetAccVcArea();
-#endif
-#if 0
-        return GetVolume(viewCell) / GetViewSpaceBox().GetVolume();
-#endif
-}
-
-
-float KdViewCellsManager::GetRendercost(ViewCell *viewCell, float objRendercost) const
-{
-        return viewCell->GetPvs().GetSize() * objRendercost;
-}
-
-
-void KdViewCellsManager::CollectViewCells()
-{
-        //mKdTree->CollectViewCells(mViewCells); TODO
-}
-
-
-int KdViewCellsManager::ConstructSubdivision(const ObjectContainer &objects,
-                                                                  const VssRayContainer &rays)
-{
-        // if view cells already constructed
-        if (ViewCellsConstructed())
-                return 0;
-
-        mKdTree->Construct();
-
-        mTotalAreaValid = false;
-        // create the view cells
-        mKdTree->CreateAndCollectViewCells(mViewCells);
-
-        // cast rays
-        ComputeSampleContributions(rays, true, false);
-
-        EvaluateViewCellsStats();
-        Debug << "\nView cells after construction:\n" << mViewCellsStats << endl;
-
-        return 0;
-}
-
-
-bool KdViewCellsManager::ViewCellsConstructed() const
-{
-        return mKdTree->GetRoot() != NULL;
-}
-
-int KdViewCellsManager::PostProcess(const ObjectContainer &objects,
-                                                                        const VssRayContainer &rays)
-{
-        return 0;
-}
-
-void KdViewCellsManager::Visualize(const ObjectContainer &objects,
-                                                                   const VssRayContainer &sampleRays)
-{
-        if (!ViewCellsConstructed())
-                return;
-
-        // using view cells instead of the kd PVS of objects
-        const bool useViewCells = true;
-        bool exportRays = false;
-
-        int limit = min(mVisualizationSamples, (int)sampleRays.size());
-        const int pvsOut = min((int)objects.size(), 10);
-        VssRayContainer *rays = new VssRayContainer[pvsOut];
-
-        if (useViewCells)
-        {
-                const int leafOut = 10;
-
-                ViewCell::NewMail();
-
-                //-- some rays for output
-                const int raysOut = min((int)sampleRays.size(), mVisualizationSamples);
-                Debug << "visualization using " << raysOut << " samples" << endl;
-
-                //-- some random view cells and rays for output
-                vector<KdLeaf *> kdLeaves;
-
-                for (int i = 0; i < leafOut; ++ i)
-                        kdLeaves.push_back(dynamic_cast<KdLeaf *>(mKdTree->GetRandomLeaf()));
-
-                for (int i = 0; i < kdLeaves.size(); ++ i)
-                {
-                        KdLeaf *leaf = kdLeaves[i];
-                        RayContainer vcRays;
-
-                        cout << "creating output for view cell " << i << " ... ";
-#if 0
-                        // check whether we can add the current ray to the output rays
-                        for (int k = 0; k < raysOut; ++ k)
-                        {
-                                Ray *ray = sampleRays[k];
-
-                                for (int j = 0; j < (int)ray->bspIntersections.size(); ++ j)
-                                {
-                                        BspLeaf *leaf2 = ray->bspIntersections[j].mLeaf;
-
-                                        if (leaf->GetViewCell() == leaf2->GetViewCell())
-                                        {
-                                                vcRays.push_back(ray);
-                                        }
-                                }
-                        }
-#endif
-                        Intersectable::NewMail();
-
-                        ViewCell *vc = leaf->mViewCell;
-
-                        //bspLeaves[j]->Mail();
-                        char s[64]; sprintf(s, "kd-pvs%04d.x3d", i);
-
-                        Exporter *exporter = Exporter::GetExporter(s);
-                        exporter->SetFilled();
-
-                        exporter->SetWireframe();
-                        //exporter->SetFilled();
-
-                        Material m;//= RandomMaterial();
-                        m.mDiffuseColor = RgbColor(1, 1, 0);
-                        exporter->SetForcedMaterial(m);
-
-                        AxisAlignedBox3 box = mKdTree->GetBox(leaf);
-                        exporter->ExportBox(box);
-
-                        Debug << i << ": pvs size=" << (int)vc->GetPvs().GetSize()
-                                << ", piercing rays=" << (int)vcRays.size() << endl;
-
-                        // export rays piercing this view cell
-                        exporter->ExportRays(vcRays, 1000, RgbColor(0, 1, 0));
-
-                        m.mDiffuseColor = RgbColor(1, 0, 0);
-                        exporter->SetForcedMaterial(m);
-
-                        // exporter->SetWireframe();
-                        exporter->SetFilled();
-
-                        ObjectPvsMap::iterator it, it_end = vc->GetPvs().mEntries.end();
-                        // output PVS of view cell
-                        for (it = vc->GetPvs().mEntries.begin(); it !=  it_end; ++ it)
-                        {
-                                Intersectable *intersect = (*it).first;
-                                if (!intersect->Mailed())
-                                {
-                                        exporter->ExportIntersectable(intersect);
-                                        intersect->Mail();
-                                }
-                        }
-
-                        DEL_PTR(exporter);
-                        cout << "finished" << endl;
-                }
-
-                DEL_PTR(rays);
-        }
-        else // using kd PVS of objects
-        {
-                for (int i = 0; i < limit; ++ i)
-                {
-                        VssRay *ray = sampleRays[i];
-
-                        // check whether we can add this to the rays
-                        for (int j = 0; j < pvsOut; j++)
-                        {
-                                if (objects[j] == ray->mTerminationObject)
-                                {
-                                        rays[j].push_back(ray);
-                                }
-                        }
-                }
-
-                if (exportRays)
-                {
-                        Exporter *exporter = NULL;
-                        exporter = Exporter::GetExporter("sample-rays.x3d");
-                        exporter->SetWireframe();
-                        exporter->ExportKdTree(*mKdTree);
-
-                        for (i=0; i < pvsOut; i++)
-                                exporter->ExportRays(rays[i], RgbColor(1, 0, 0));
-
-                        exporter->SetFilled();
-
-                        delete exporter;
-                }
-
-                for (int k=0; k < pvsOut; k++)
-                {
-                        Intersectable *object = objects[k];
-                        char s[64];
-                        sprintf(s, "sample-pvs%04d.x3d", k);
-
-                        Exporter *exporter = Exporter::GetExporter(s);
-                        exporter->SetWireframe();
-
-                        KdPvsMap::iterator i = object->mKdPvs.mEntries.begin();
-                        Intersectable::NewMail();
-
-                        // avoid adding the object to the list
-                        object->Mail();
-                        ObjectContainer visibleObjects;
-
-                        for (; i != object->mKdPvs.mEntries.end(); i++)
-                        {
-                                KdNode *node = (*i).first;
-                                exporter->ExportBox(mKdTree->GetBox(node));
-
-                                mKdTree->CollectObjects(node, visibleObjects);
-                        }
-
-                        exporter->ExportRays(rays[k],  RgbColor(0, 1, 0));
-                        exporter->SetFilled();
-
-                        for (int j = 0; j < visibleObjects.size(); j++)
-                                exporter->ExportIntersectable(visibleObjects[j]);
-
-                        Material m;
-                        m.mDiffuseColor = RgbColor(1, 0, 0);
-                        exporter->SetForcedMaterial(m);
-                        exporter->ExportIntersectable(object);
-
-                        delete exporter;
-                }
-        }
-}
-
-
-void KdViewCellsManager::ExportColor(Exporter *exporter,
-                                                                         ViewCell *vc) const
-{
-        // TODO
-}
-
-ViewCell *KdViewCellsManager::GenerateViewCell(Mesh *mesh) const
-{
-        return new KdViewCell(mesh);
-}
-
-
-void KdViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
-                                                                                                ViewCell *vc,
-                                                                                                const Plane3 *cuttingPlane) const
-{
-        ViewCellContainer leaves;
-
-        mViewCellsTree->CollectLeaves(vc, leaves);
-        ViewCellContainer::const_iterator it, it_end = leaves.end();
-
-        for (it = leaves.begin(); it != it_end; ++ it)
-        {
-                KdViewCell *kdVc = dynamic_cast<KdViewCell *>(*it);
-        
-                exporter->ExportBox(mKdTree->GetBox(kdVc->mLeaf));
-        }
-}
-
-
-int KdViewCellsManager::GetType() const
-{
-        return ViewCellsManager::KD;
-}
-
-
-
-KdNode *KdViewCellsManager::GetNodeForPvs(KdLeaf *leaf)
-{
-        KdNode *node = leaf;
-
-        while (node->mParent && node->mDepth > mKdPvsDepth)
-                node = node->mParent;
-        return node;
-}
-
-int KdViewCellsManager::CastLineSegment(const Vector3 &origin,
-                                                                                const Vector3 &termination,
-                                                                                ViewCellContainer &viewcells)
-{
-        return mKdTree->CastLineSegment(origin, termination, viewcells);
-}
-
-
-void KdViewCellsManager::CreateMesh(ViewCell *vc)
-{
-        // TODO
-}
-
-
-
-void KdViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays, 
-                                                                                                vector<MergeCandidate> &candidates)
-{
-        // TODO
-}
-
-
-/**********************************************************************/
-/*                   VspKdViewCellsManager implementation             */
-/**********************************************************************/
-
-
-VspKdViewCellsManager::VspKdViewCellsManager(VspKdTree *vspKdTree):
-ViewCellsManager(), mVspKdTree(vspKdTree)
-{
-        environment->GetIntValue("VspKdTree.Construction.samples", mInitialSamples);
-        mVspKdTree->SetViewCellsManager(this);
-}
-
-float VspKdViewCellsManager::GetProbability(ViewCell *viewCell)
-{
-        // volume or area substitutes for view point probability
-#if 0
-        return GetArea(viewCell) / GetViewSpaceBox().SurfaceArea();
-#else
-        return GetArea(viewCell) / GetAccVcArea();
-#endif
-}
-
-
-float VspKdViewCellsManager::GetRendercost(ViewCell *viewCell, float objRendercost) const
-{
-        return viewCell->GetPvs().GetSize() * objRendercost;
-}
-
-
-void VspKdViewCellsManager::CollectViewCells()
-{
-        mVspKdTree->CollectViewCells(mViewCells);
-}
-
-
-int VspKdViewCellsManager::ConstructSubdivision(const ObjectContainer &objects,
-                                                                                                const VssRayContainer &rays)
-{
-        // if view cells already constructed
-        if (ViewCellsConstructed())
-                return 0;
-
-        VssRayContainer constructionRays;
-        VssRayContainer savedRays;
-
-        GetRaySets(rays,
-                           mInitialSamples,
-                           constructionRays,
-                           &savedRays);
-
-        Debug << "constructing vsp kd tree using "
-                  << (int)constructionRays.size() << " samples" << endl;
-
-        mVspKdTree->Construct(constructionRays, &mViewSpaceBox);
-        Debug << mVspKdTree->GetStatistics() << endl;
-
-        // export leaf building blocks
-        ExportLeaves(objects, rays);
-
-        // finally merge kd leaf building blocks to view cells
-        const int merged = mVspKdTree->MergeViewCells(rays);
-
-        // collapse siblings belonging to the same view cell
-        mVspKdTree->RefineViewCells(rays);
-
-        // collapse siblings belonging to the same view cell
-        mVspKdTree->CollapseTree();
-
-        // evaluale view cell stats
-        ResetViewCells();
-
-        Debug << "\nView cells after construction:\n" << mViewCellsStats << endl;
-
-        long startTime = GetTime();
-        // recast rest of rays
-        ComputeSampleContributions(savedRays, true, false);
-
-        Debug << "Computed remaining ray contribution in " << TimeDiff(startTime, GetTime()) * 1e-3
-                  << " secs" << endl;
-
-        return merged;
-}
-
-bool VspKdViewCellsManager::ViewCellsConstructed() const
-{
-        return mVspKdTree->GetRoot() != NULL;
-}
-
-
-ViewCell *VspKdViewCellsManager::GenerateViewCell(Mesh *mesh) const
-{
-        return new VspKdViewCell(mesh);
-}
-
-int VspKdViewCellsManager::PostProcess(const ObjectContainer &objects,
-                                                                           const VssRayContainer &rays)
-{
-        if (!ViewCellsConstructed())
-                return 0;
-
-        // recalculate stats
-        EvaluateViewCellsStats();
-
-        return 0;
-}
-
-
-void VspKdViewCellsManager::ExportLeaves(const ObjectContainer &objects,
-                                                                                 const VssRayContainer &sampleRays)
-{
-        if (!ViewCellsConstructed())
-                return;
-
-        //-- export leaf building blocks
-        Exporter *exporter = Exporter::GetExporter("vspkdtree.x3d");
-        if (!exporter)
-                return;
-
-        if (mExportGeometry)
-                exporter->ExportGeometry(objects);
-        
-        //exporter->SetWireframe();
-        //exporter->ExportVspKdTree(*mVspKdTree, mVspKdTree->GetStatistics().maxPvsSize);
-        exporter->ExportVspKdTree(*mVspKdTree);
-
-        if (mExportRays)
-        {
-                const float prob = (float)mVisualizationSamples
-                        / ((float)sampleRays.size() + Limits::Small);
-
-                exporter->SetWireframe();
-
-                //-- collect uniformly distributed rays
-                VssRayContainer rays;
-
-                for (int i = 0; i < sampleRays.size(); ++ i)
-                {
-                        if (RandomValue(0,1) < prob)
-                                rays.push_back(sampleRays[i]);
-                }
-                exporter->ExportRays(rays, RgbColor(1, 0, 0));
-        }
-
-        delete exporter;
-}
-
-void VspKdViewCellsManager::Visualize(const ObjectContainer &objects,
-                                                                          const VssRayContainer &sampleRays)
-{
-        if (!ViewCellsConstructed())
-                return;
-
-        //-- export single view cells
-        for (int i = 0; i < 10; ++ i)
-        {
-                char s[64];
-                sprintf(s, "vsp_viewcell%04d.x3d", i);
-                Exporter *exporter = Exporter::GetExporter(s);
-                const int idx =
-                        (int)RandomValue(0.0, (Real)((int)mViewCells.size() - 1));
-
-                VspKdViewCell *vc = dynamic_cast<VspKdViewCell *>(mViewCells[idx]);
-
-                cout << "Output view cell " << i << " with pvs size " << vc->GetPvs().GetSize() << endl;
-                Debug << "Output view cell " << i << " with pvs size " << vc->GetPvs().GetSize() << endl;
-                //-- export geometry
-                Material m;
-                m.mDiffuseColor = RgbColor(0, 1, 1);
-
-                exporter->SetForcedMaterial(m);
-                exporter->SetWireframe();
-
-                ExportViewCellGeometry(exporter, vc);
-
-                //-- export stored rays
-                
-                if (mExportRays)
-                {
-                        ViewCellContainer leaves;
-                        mViewCellsTree->CollectLeaves(vc, leaves);
-
-                        ViewCellContainer::const_iterator it,
-                                it_end = leaves.end();
-
-                        for (it = leaves.begin(); it != it_end; ++ it)
-                        {
-                                VspKdViewCell *vspKdVc = dynamic_cast<VspKdViewCell *>(*it);
-                                VspKdLeaf *leaf = vspKdVc->mLeaf;
-                                AxisAlignedBox3 box = mVspKdTree->GetBBox(leaf);
-
-                                VssRayContainer vssRays;
-
-                                VssRayContainer castRays;
-                                VssRayContainer initRays;
-
-                                leaf->GetRays(vssRays);
-
-                                VssRayContainer::const_iterator it, it_end = vssRays.end();
-                                const float prop = 200.0f / (float)vssRays.size();
-
-                                for (it = vssRays.begin(); it != it_end; ++ it)
-                                {
-                                        if (Random(1) < prop)
-                                                if ((*it)->mTerminationObject == NULL)
-                                                        castRays.push_back(*it);
-                                                else
-                                                        initRays.push_back(*it);
-                                }
-
-                                exporter->ExportRays(castRays, RgbColor(1, 0, 0));
-                                exporter->ExportRays(initRays, RgbColor(0, 1, 0));
-                        }
-                }
-        
-                //-- output PVS of view cell
-                m.mDiffuseColor = RgbColor(1, 0, 0);
-                exporter->SetForcedMaterial(m);
-
-                Intersectable::NewMail();
-
-                ObjectPvsMap::const_iterator it,
-                        it_end = vc->GetPvs().mEntries.end();
-
-                exporter->SetFilled();
-
-                for (it = vc->GetPvs().mEntries.begin(); it != it_end; ++ it)
-                {
-                        Intersectable *intersect = (*it).first;
-
-                        if (!intersect->Mailed())
-                        {
-                                Material m = RandomMaterial();
-                                exporter->SetForcedMaterial(m);
-
-                                exporter->ExportIntersectable(intersect);
-                                intersect->Mail();
-                        }
-                }
-
-                delete exporter;
-        }
-
-        //-- export final view cells
-        Exporter *exporter = Exporter::GetExporter("vspkdtree_merged.x3d");
-
-        //if (exportGeometry) exporter->SetWireframe();
-        //else exporter->SetFilled();
-
-        ExportViewCellsForViz(exporter);
-
-        if (mExportGeometry)
-        {
-                exporter->SetFilled();
-                exporter->ExportGeometry(objects);
-        }
-
-        if (mExportRays)
-        {
-                const float prob = (float)mVisualizationSamples
-                        / ((float)sampleRays.size() + Limits::Small);
-
-                exporter->SetWireframe();
-
-                VssRayContainer rays;
-
-                for (int i = 0; i < sampleRays.size(); ++ i)
-                {
-                  if (RandomValue(0,1) < prob)
-                        rays.push_back(sampleRays[i]);
-                }
-                exporter->ExportRays(rays, RgbColor(1, 0, 0));
-        }
-
-        delete exporter;
-}
-
-int VspKdViewCellsManager::GetType() const
-{
-        return VSP_KD;
-}
-
-
-int VspKdViewCellsManager::CastLineSegment(const Vector3 &origin,
-                                                                                   const Vector3 &termination,
-                                                                                   ViewCellContainer &viewcells)
-{
-        return mVspKdTree->CastLineSegment(origin, termination, viewcells);
-}
-
-
-void VspKdViewCellsManager::ExportColor(Exporter *exporter,
-                                                                                ViewCell *vc) const
-{
-        if (mColorCode == 0) // Random color
-                return;
-
-        float importance = 0;
-
-        switch (mColorCode)
-        {
-        case 1: // pvs
-                {
-                        importance = (float)vc->GetPvs().GetSize() /
-                                (float)mViewCellsStats.maxPvs;
-                }
-                break;
-        case 2: // merged leaves
-                {
-                int lSize = mViewCellsTree->GetSize(vc);
-                        importance = (float)lSize /
-                                (float)mViewCellsStats.maxLeaves;
-                }
-                break;
-        case 3: // merged tree depth difference
-                {
-                        //importance = (float)GetMaxTreeDiff(vc) /
-                        //      (float)(mVspBspTree->GetStatistics().maxDepth * 2);
-                }
-                break;
-        default:
-                break;
-        }
-
-        Material m;
-        m.mDiffuseColor.b = 1.0f;
-        m.mDiffuseColor.r = importance;
-        m.mDiffuseColor.g = 1.0f - m.mDiffuseColor.r;
-        //Debug << "importance: " << importance << endl;
-        exporter->SetForcedMaterial(m);
-}
-
-
-void VspKdViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
-                                                                                                   ViewCell *vc,
-                                                                                                   const Plane3 *cuttingPlane) const
-{
-        VspKdViewCell *kdVc = dynamic_cast<VspKdViewCell *>(vc);
-
-        Mesh m;
-
-        ViewCellContainer leaves;
-        mViewCellsTree->CollectLeaves(vc, leaves);
-
-        ViewCellContainer::const_iterator it, it_end = leaves.end();
-
-        for (it = leaves.begin(); it != it_end; ++ it)
-        {
-                VspKdLeaf *l = dynamic_cast<VspKdViewCell *>(*it)->mLeaf;
-                mVspKdTree->GetBBox(l).AddBoxToMesh(&m);
-        }
-
-        exporter->ExportMesh(&m);
-}
-
-
-void VspKdViewCellsManager::CreateMesh(ViewCell *vc)
-{
-        //TODO
-}
-
-
-void VspKdViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays, 
-                                                                                                   vector<MergeCandidate> &candidates)
-{
-        // TODO
-}
-
-
-/**************************************************************************/
-/*                   VspBspViewCellsManager implementation                */
-/**************************************************************************/
-
-
-VspBspViewCellsManager::VspBspViewCellsManager(VspBspTree *vspBspTree):
-ViewCellsManager(), mVspBspTree(vspBspTree)
-{
-        environment->GetIntValue("VspBspTree.Construction.samples", mInitialSamples);
-        mVspBspTree->SetViewCellsManager(this);
-        mVspBspTree->mViewCellsTree = mViewCellsTree;
-}
-
-
-VspBspViewCellsManager::~VspBspViewCellsManager()
-{
-}
-
-
-float VspBspViewCellsManager::GetProbability(ViewCell *viewCell)
-{
-        if (0 && mVspBspTree->mUseAreaForPvs)
-                return GetArea(viewCell) / GetAccVcArea();
-        else
-                return GetVolume(viewCell) / mViewSpaceBox.GetVolume();
-}
-
-
-void VspBspViewCellsManager::CollectViewCells()
-{
-        // view cells tree constructed
-        if (!ViewCellsTreeConstructed())
-        {
-                mVspBspTree->CollectViewCells(mViewCells, false);
-        }
-        else 
-        {
-                // we can use the view cells tree hierarchy to get the right set
-                mViewCellsTree->CollectBestViewCellSet(mViewCells, mNumMergedViewCells);
-        }
-
-}
-
-
-float VspBspViewCellsManager::GetRendercost(ViewCell *viewCell,
-                                                                                        float objRendercost) const
-{
-        return viewCell->GetPvs().GetSize() * objRendercost;
-}
-
-
-bool VspBspViewCellsManager::ViewCellsConstructed() const
-{
-        return mVspBspTree->GetRoot() != NULL;
-}
-
-
-ViewCell *VspBspViewCellsManager::GenerateViewCell(Mesh *mesh) const
-{
-        return new BspViewCell(mesh);
-}
-
-
-int VspBspViewCellsManager::ConstructSubdivision(const ObjectContainer &objects,
-                                                                          const VssRayContainer &rays)
-{
-        // if view cells were already constructed
-        if (ViewCellsConstructed())
-                return 0;
-
-        Debug << "Constructing bsp view cells" << endl;
-
-        int sampleContributions = 0;
-
-        VssRayContainer sampleRays;
-
-        int limit = min (mInitialSamples, (int)rays.size());
-
-        VssRayContainer constructionRays;
-        VssRayContainer savedRays;
-
-        Debug << "samples used for subdivision: " << mInitialSamples 
-                  << " rays: " << (int)rays.size() << endl;
-
-        GetRaySets(rays, mInitialSamples, constructionRays, &savedRays);
-
-        Debug << "initial rays: " << (int)constructionRays.size() << endl;
-        Debug << "saved rays: " << (int)savedRays.size() << endl;
-
-        mMaxPvsSize = (int)(mMaxPvsRatio * (float)objects.size());
-
-        mVspBspTree->Construct(constructionRays, &mViewSpaceBox);
-
-        Debug << mVspBspTree->GetStatistics() << endl;
-
-        // collapse invalid regions
-        cout << "collapsing invalid tree regions ... ";
-        long startTime = GetTime();
-        int collapsedLeaves = mVspBspTree->CollapseTree();
-        Debug << "collapsed in " << TimeDiff(startTime, GetTime()) * 1e-3 
-                  << " seconds" << endl;
-
-    cout << "finished" << endl;
-
-        cout << "reseting view cell stats ... ";
-        ResetViewCells();
-        cout << "finished" << endl;
-
-        Debug << "\nView cells after construction:\n" << mViewCellsStats << endl;
-
-        if (1) // export initial view cells
-        {
-                cout << "exporting initial view cells (=leaves) ... ";
-                Exporter *exporter = Exporter::GetExporter("view_cells.x3d");
-
-                if (exporter)
-                {
-                        if (0 && mExportRays)
-                                exporter->ExportRays(rays, RgbColor(1, 1, 1));
-
-                        if (mExportGeometry)
-                                exporter->ExportGeometry(objects);
-
-                        //exporter->SetWireframe();
-                        exporter->SetFilled();
-                        ExportViewCellsForViz(exporter);
-
-                        delete exporter;
-                }
-                cout << "finished" << endl;
-        }
-
-        startTime = GetTime();
-
-        // reset view cells and stats
-        ResetViewCells();
-
-        cout << "Computing remaining ray contributions ... ";
-        // recast rest of rays
-        ComputeSampleContributions(savedRays, true, false);
-        cout << "finished" << endl;
-
-        Debug << "Computed remaining ray contribution in " << TimeDiff(startTime, GetTime()) * 1e-3
-                  << " secs" << endl;
-
-        cout << "construction finished" << endl;
-
-        return sampleContributions;
-}
-
-
-void VspBspViewCellsManager::MergeViewCells(const VssRayContainer &rays,
-                                                                                        const ObjectContainer &objects)
-{
-        //-- post processing of bsp view cells
-    int vcSize = 0;
-        int pvsSize = 0;
-
-        mRenderer->RenderScene();
-        SimulationStatistics ss;
-        dynamic_cast<RenderSimulator *>(mRenderer)->GetStatistics(ss);
-    Debug << ss << endl;
-
-        //-- merge or subdivide view cells
-        int merged = 0;
-        if (mMergeViewCells)
-        {
-                cout << "starting merge using " << mPostProcessSamples << " samples ... " << endl;
-                long startTime = GetTime();
-
-        
-                // TODO: should be done BEFORE the ray casting
-                merged = mViewCellsTree->ConstructMergeTree(rays, objects);
-
-                //-- stats and visualizations
-                cout << "finished merging" << endl;
-                cout << "merged " << merged << " view cells in "
-                         << TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl;
-
-                Debug << "Postprocessing: Merged " << merged << " view cells in "
-                          << TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl << endl;
-        }
-
-        //BspLeaf::NewMail();
-        if (1) // export merged view cells
-        {
-                cout << "reseting view cells ... ";
-                ResetViewCells();
-
-                cout << "finished" << endl;
-
-                Exporter *exporter = Exporter::GetExporter("merged_view_cells.x3d");
-                Debug << "\nView cells after merge:\n" << mViewCellsStats << endl;
-
-                cout << "exporting view cells after merge ... ";
-
-                if (exporter)
-                {
-                        if (mExportGeometry)
-                        {
-                                Material m;
-                                m.mDiffuseColor = RgbColor(0, 1, 0);
-                                exporter->SetForcedMaterial(m);
-                                exporter->SetFilled();
-
-                                exporter->ExportGeometry(objects);
-                        }
-
-                        if (0)
-                                exporter->SetWireframe();
-                        else
-                                exporter->SetFilled();
-
-                        ExportViewCellsForViz(exporter);
-
-                        delete exporter;
-                }
-                cout << "finished" << endl;
-        }
-}
-
-
-void VspBspViewCellsManager::RefineViewCells(const VssRayContainer &rays,
-                                                                                         const ObjectContainer &objects)
-{
-        Debug << "render time before refine:" << endl;
-        mRenderer->RenderScene();
-        SimulationStatistics ss;
-        dynamic_cast<RenderSimulator *>(mRenderer)->GetStatistics(ss);
-    Debug << ss << endl;
-
-        cout << "Refining the merged view cells ... ";
-        long startTime = GetTime();
-
-        // refining the merged view cells
-        const int refined = mViewCellsTree->RefineViewCells(rays, objects);
-
-        //-- stats and visualizations
-        cout << "finished" << endl;
-        cout << "refined " << refined << " view cells in "
-                 << TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl;
-
-        Debug << "Postprocessing: refined " << refined << " view cells in "
-                  << TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl << endl;
-}
-
-
-int VspBspViewCellsManager::PostProcess(const ObjectContainer &objects,
-                                                                                const VssRayContainer &rays)
-{
-        if (!ViewCellsConstructed())
-        {
-                Debug << "postprocess error: no view cells constructed" << endl;
-                return 0;
-        }
-
-
-        // view cells already finished before post processing step (i.e. because they were loaded)
-        if (mViewCellsFinished)
-        {
-                FinalizeViewCells(true);
-                EvaluateViewCellsStats();
-
-                return 0;
-        }
-
-
-        // check if new view cells turned invalid
-        SetValidity(mMinPvsSize, mMaxPvsSize); 
-        // update valid view space according to valid view cells
-        mVspBspTree->ValidateTree();
-
-        // recompute view cell statistics
-        mViewCellsStats.Reset();
-        EvaluateViewCellsStats();
-
-        // has to be recomputed
-        mTotalAreaValid = false;
-
-
-        VssRayContainer postProcessRays;
-        GetRaySets(rays, mPostProcessSamples, postProcessRays);
-
-        Debug << "post processing using " << (int)postProcessRays.size() << " samples" << endl;
-
-        Debug << "\nview cell partition after sampling:\n" << mViewCellsStats << endl << endl;
-
-        // should maybe be done here to allow merge working with area or volume
-        // and to correct the rendering statistics
-        if (0)
-        {
-                FinalizeViewCells(false);
-        }
-
-        //-- merge the individual view cells
-        MergeViewCells(postProcessRays, objects);
-        
-
-        //-- refines the merged view cells
-        if (0)
-                RefineViewCells(postProcessRays, objects);
-
-        //-- compression
-
-        if (ViewCellsTreeConstructed() && mCompressViewCells)
-        {
-                int pvsEntries = mViewCellsTree->GetNumPvsEntries(mViewCellsTree->GetRoot());
-                Debug << "number of entries before compress: " << pvsEntries << endl;
-
-                mViewCellsTree->CompressViewCellsPvs();
-
-                pvsEntries = mViewCellsTree->GetNumPvsEntries(mViewCellsTree->GetRoot());
-                Debug << "number of entries after compress: " << pvsEntries << endl;
-        }
-
-        if (1)
-        {               
-                float totalCost, erc, var, dev, avg;
-                int totalpvs;
-
-                mViewCellsStats.Reset();
-
-        EvaluateRenderStatistics(totalCost, erc, dev, var, totalpvs, avg);
-                
-                Debug << "statistics after merge "  
-                          << " erc: " << erc 
-                          << " dev: " << dev
-                          << " totalpvs: " << totalpvs 
-                          << " avg: " << avg << endl;
-        }
-
-
-        //-- export refined (shuffled) view cells
-        if (0)
-        {
-                cout << "exporting shuffled view cells ... ";
-
-                Exporter *exporter = Exporter::GetExporter("shuffled_view_cells.x3d");
-                if (exporter)
-                {
-                        if (1)
-                        {
-                                exporter->SetWireframe();
-                                exporter->ExportBox(mViewSpaceBox);
-                                exporter->SetFilled();
-                        }
-
-                        if (mExportGeometry)
-                        {
-                                exporter->ExportGeometry(objects);
-                        }
-
-                        ViewCellContainer::const_iterator vit, vit_end = mViewCells.end();
-
-                        Material vm, lm;
-
-                        for (vit = mViewCells.begin(); vit != mViewCells.end(); ++ vit)
-                        {
-                                ViewCell *vc = *vit;
-
-                                vm = RandomMaterial();
-
-                                lm = vm;
-
-                                vm.mDiffuseColor.r -= 0.45f;
-                                vm.mDiffuseColor.g -= 0.45f;
-                                vm.mDiffuseColor.b -= 0.45f;
-
-
-                                ViewCellContainer leaves;
-                                mViewCellsTree->CollectLeaves(vc, leaves);
-
-                                ViewCellContainer::const_iterator lit, lit_end = leaves.end();
-
-                                for (lit = leaves.begin(); lit != lit_end; ++ lit)
-                                {
-                                        BspLeaf *leaf = dynamic_cast<BspViewCell *>(*lit)->mLeaf;
-
-                                        if (leaf->Mailed())
-                                                exporter->SetForcedMaterial(lm);
-                                        else
-                                                exporter->SetForcedMaterial(vm);
-
-                                        BspNodeGeometry geom;
-                                        mVspBspTree->ConstructGeometry(leaf, geom);
-                                        exporter->ExportPolygons(geom.mPolys);
-                                }
-                        }
-
-                        delete exporter;
-                }
-
-
-                cout << "finished" << endl;
-        }
-
-        // collapse sibling leaves that share the same view cell
-        if (0)
-                mVspBspTree->CollapseTree();
-
-        // recompute view cell list and statistics
-        ResetViewCells();
-
-        // real meshes are only contructed only at this stage
-        FinalizeViewCells(true);
-
-        // write view cells to disc
-        if (mExportViewCells)
-        {
-                char buff[100];
-                environment->GetStringValue("ViewCells.filename", buff);
-                string vcFilename(buff);
-
-                ExportViewCells(buff);
-        }
-
-        return 0;
-}
-
-
-int VspBspViewCellsManager::GetType() const
-{
-        return VSP_BSP;
-}
-
-
-bool VspBspViewCellsManager::GetViewPoint(Vector3 &viewPoint) const
-{
-        if (!ViewCellsConstructed())
-                return ViewCellsManager::GetViewPoint(viewPoint);
-
-        // TODO: set reasonable limit
-        const int limit = 20;
-
-        for (int i = 0; i < limit; ++ i)
-        {
-                viewPoint = mViewSpaceBox.GetRandomPoint();
-                if (mVspBspTree->ViewPointValid(viewPoint))
-                {
-                        return true;
-                }
-        }
-        Debug << "failed to find valid view point, taking " << viewPoint << endl;
-        return false;
-}
-
-
-bool VspBspViewCellsManager::ViewPointValid(const Vector3 &viewPoint) const
-{
-  // $$JB -> implemented in viewcellsmanager (slower, but allows dynamic
-  // validy update in preprocessor for all managers)
-  return ViewCellsManager::ViewPointValid(viewPoint);
-
-  //    return mViewSpaceBox.IsInside(viewPoint) &&
-  //               mVspBspTree->ViewPointValid(viewPoint);
-}
-
-
-void VspBspViewCellsManager::Visualize(const ObjectContainer &objects,
-                                                                           const VssRayContainer &sampleRays)
-{
-        if (!ViewCellsConstructed())
-                return;
-
-        VssRayContainer visRays;
-        GetRaySets(sampleRays, mVisualizationSamples, visRays);
-
-        if (1) // export view cells
-        {
-                Exporter *exporter = Exporter::GetExporter("final_view_cells.x3d");
-
-                if (exporter)
-                {
-                        cout << "exporting view cells after post process ... ";
-
-                        if (1)
-                        {
-                                exporter->SetWireframe();
-                                exporter->ExportBox(mViewSpaceBox);
-                                exporter->SetFilled();
-                        }
-
-                        if (mExportGeometry)
-                        {
-                                exporter->ExportGeometry(objects);
-                        }
-
-                        // export rays
-                        if (mExportRays)
-                        {
-                                exporter->ExportRays(visRays, RgbColor(0, 1, 0));
-                        }
-
-                        ExportViewCellsForViz(exporter);
-                        delete exporter;
-                        cout << "finished" << endl;
-                }
-        }
-
-        if (1)
-        {
-                cout << "exporting depth map ... ";
-
-                Exporter *exporter = Exporter::GetExporter("depth_map.x3d");
-                if (exporter)
-                {
-                        if (1)
-                        {
-                                exporter->SetWireframe();
-                                exporter->ExportBox(mViewSpaceBox);
-                                exporter->SetFilled();
-                        }
-
-                        if (mExportGeometry)
-                        {
-                                exporter->ExportGeometry(objects);
-                        }
-
-                        const int maxDepth = mVspBspTree->mBspStats.maxDepth;
-
-                        ViewCellContainer::const_iterator vit, vit_end = mViewCells.end();
-
-                        for (vit = mViewCells.begin(); vit != mViewCells.end(); ++ vit)
-                        {
-                                ViewCell *vc = *vit;
-
-                                ViewCellContainer leaves;
-                                mViewCellsTree->CollectLeaves(vc, leaves);
-
-                                ViewCellContainer::const_iterator lit, lit_end = leaves.end();
-
-                                for (lit = leaves.begin(); lit != lit_end; ++ lit)
-                                {
-                                        BspLeaf *leaf = dynamic_cast<BspViewCell *>(*lit)->mLeaf;
-
-                                        Material m; 
-
-                                        float relDepth = (float)leaf->GetDepth() / (float)maxDepth;
-                                        m.mDiffuseColor.r = relDepth;
-                                        m.mDiffuseColor.g = 0.0f;
-                                        m.mDiffuseColor.b = 1.0f - relDepth;
-
-                    exporter->SetForcedMaterial(m);
-                                
-
-                                        BspNodeGeometry geom;
-                                        mVspBspTree->ConstructGeometry(leaf, geom);
-                                        exporter->ExportPolygons(geom.mPolys);
-                                }
-                        }
-
-                        delete exporter;
-                }
-
-
-                cout << "finished" << endl;
-        }
-
-        //-- visualization of the BSP splits
-        bool exportSplits = false;
-        environment->GetBoolValue("VspBspTree.Visualization.exportSplits", exportSplits);
-
-        if (exportSplits)
-        {
-                cout << "exporting splits ... ";
-                ExportSplits(objects, visRays);
-                cout << "finished" << endl;
-        }
-
-        //-- export single view cells
-        ExportBspPvs(objects, visRays);
-}
-
-
-void VspBspViewCellsManager::ExportSplits(const ObjectContainer &objects,
-                                                                                  const VssRayContainer &rays)
-{
-        Exporter *exporter = Exporter::GetExporter("bsp_splits.x3d");
-
-        if (exporter)
-        {
-                Material m;
-                m.mDiffuseColor = RgbColor(1, 0, 0);
-                exporter->SetForcedMaterial(m);
-                exporter->SetWireframe();
-
-                exporter->ExportBspSplits(*mVspBspTree, true);
-
-                // take forced material, else big scenes cannot be viewed
-                m.mDiffuseColor = RgbColor(0, 1, 0);
-                exporter->SetForcedMaterial(m);
-                exporter->SetFilled();
-
-                exporter->ResetForcedMaterial();
-
-                // export rays
-                if (mExportRays)
-                        exporter->ExportRays(rays, RgbColor(1, 1, 0));
-
-                if (mExportGeometry)
-                        exporter->ExportGeometry(objects);
-
-                delete exporter;
-        }
-}
-
-
-void VspBspViewCellsManager::ExportBspPvs(const ObjectContainer &objects,
-                                                                                  const VssRayContainer &rays)
-{
-        const int leafOut = 10;
-
-        ViewCell::NewMail();
-
-        cout << "visualization using " << mVisualizationSamples << " samples" << endl;
-        Debug << "\nOutput view cells: " << endl;
-
-        // sort view cells to visualize the largest view cells
-        if (0)
-                stable_sort(mViewCells.begin(), mViewCells.end(), vc_gt);
-
-        int limit = min(leafOut, (int)mViewCells.size());
-
-        int raysOut;
-
-        //-- some rays for output
-        if (1)
-                raysOut = min((int)rays.size(), mVisualizationSamples);
-
-        for (int i = 0; i < limit; ++ i)
-        {
-                cout << "creating output for view cell " << i << " ... ";
-
-                VssRayContainer vcRays;
-                Intersectable::NewMail();
-                ViewCell *vc;
-        
-                if (0) // largest view cell pvs first
-                        vc = mViewCells[i];
-                else
-                        vc = mViewCells[Random((int)mViewCells.size())];
-
-                vector<ViewCell *> leaves;
-                mViewCellsTree->CollectLeaves(vc, leaves);
-
-        if (1)
-                {
-                        // check whether we can add the current ray to the output rays
-                        for (int k = 0; k < raysOut; ++ k)
-                        {
-                                VssRay *ray = rays[k];
-                                for     (int j = 0; j < (int)ray->mViewCells.size(); ++ j)
-                                {
-                                        ViewCell *rayvc = ray->mViewCells[j];
-
-                                        if (leaves[0] == rayvc)
-                                                vcRays.push_back(ray);
-                                }
-                        }
-                }
-
-                //bspLeaves[j]->Mail();
-                char s[64]; sprintf(s, "bsp-pvs%04d.x3d", i);
-                Exporter *exporter = Exporter::GetExporter(s);
-                exporter->SetWireframe();
-
-                Material m;//= RandomMaterial();
-                m.mDiffuseColor = RgbColor(0, 1, 0);
-                exporter->SetForcedMaterial(m);
-
-                ExportViewCellGeometry(exporter, vc);
-
-
-                Debug << i << ": pvs size=" << (int)mViewCellsTree->GetPvsSize(vc)
-                          << ", piercing rays=" << (int)vcRays.size() << endl;
-                        //  << ", leaves=" << (int)vc->mLeaves.size() << endl;
-
-                
-                //-- export rays piercing this view cell
-                if (1)
-                {
-                        exporter->ExportRays(vcRays, RgbColor(1, 1, 1));
-                }
-                else
-                {
-
-                        ViewCellContainer leaves;
-                        mViewCellsTree->CollectLeaves(vc, leaves);
-
-                        ViewCellContainer::const_iterator lit, lit_end = leaves.end();
-
-                        for (lit = leaves.begin(); lit != lit_end; ++ lit)
-                        {
-                                BspLeaf *l = dynamic_cast<BspViewCell *>(*lit)->mLeaf;
-                                exporter->ExportRays(l->mVssRays);
-                        }
-                }
-
-        
-                m.mDiffuseColor = RgbColor(1, 0, 0);
-                exporter->SetForcedMaterial(m);
-
-                ObjectPvsMap::const_iterator it,
-                        it_end = vc->GetPvs().mEntries.end();
-
-                exporter->SetFilled();
-
-        
-                // output PVS of view cell
-                for (it = vc->GetPvs().mEntries.begin(); it != it_end; ++ it)
-                {
-                
-                        Intersectable *intersect = (*it).first;
-
-                        if (!intersect->Mailed())
-                        {
-                                Material m = RandomMaterial();
-                                exporter->SetForcedMaterial(m);
-
-                                exporter->ExportIntersectable(intersect);
-                                intersect->Mail();
-                        }
-                }
-
-                
-                DEL_PTR(exporter);
-                cout << "finished" << endl;
-        }
-
-        Debug << endl;
-}
-
-
-int VspBspViewCellsManager::CastLineSegment(const Vector3 &origin,
-                                                                                        const Vector3 &termination,
-                                                                                        ViewCellContainer &viewcells)
-{
-        return mVspBspTree->CastLineSegment(origin, termination, viewcells);
-}
-
-
-void VspBspViewCellsManager::ExportColor(Exporter *exporter,
-                                                                                 ViewCell *vc) const
-{
-        const bool vcValid = CheckValidity(vc, mMinPvsSize, mMaxPvsSize);
-
-        float importance = 0;
-        static Material m;
-
-        switch (mColorCode)
-        {
-        case 0: // Random
-                {
-                        if (vcValid)
-                        {
-                                m.mDiffuseColor.r = 0.5f + RandomValue(0.0f, 0.5f);
-                                m.mDiffuseColor.g = 0.5f + RandomValue(0.0f, 0.5f);
-                                m.mDiffuseColor.b = 0.5f + RandomValue(0.f, 0.5f);
-                        }
-                        else
-                        {
-                                m.mDiffuseColor.r = 0.0f;
-                                m.mDiffuseColor.g = 1.0f;
-                                m.mDiffuseColor.b = 0.0f;
-                        }
-
-                        exporter->SetForcedMaterial(m);
-                        return;
-                }
-                
-        case 1: // pvs
-                {
-                        importance = (float)vc->GetPvs().GetSize() /
-                                (float)mViewCellsStats.maxPvs;
-
-                }
-                break;
-        case 2: // merges
-                {
-            int lSize = mViewCellsTree->GetSize(vc);
-        
                         importance = (float)lSize / (float)mViewCellsStats.maxLeaves;
                 }
@@ -3164 +3271 @@
                                                            *cuttingPlane,
                                                            mViewSpaceBox, 
-                                                           0.0001);
-
-                        exporter->ExportPolygons(back.mPolys);
+                                                           0.0001f);
+
+                        if ((int)back.mPolys.size() >= 3)
+                                exporter->ExportPolygons(back.mPolys);
                 }
         }

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellsManager.h

@@ -355 +355 @@
   
   void CollectViewCells(const int n) {
-        mNumMergedViewCells = n;
+        mNumActiveViewCells = n;
         mViewCells.clear();
         CollectViewCells();
@@ -454 +454 @@
         float mMaxPvsRatio;
 
-        int mNumMergedViewCells;
-
+        int mNumActiveViewCells;
         bool mCompressViewCells;
 

trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.cpp

@@ -86 +86 @@
         //-- max cost ratio for early tree termination
         environment->GetFloatValue("VspBspTree.Termination.maxCostRatio", mTermMaxCostRatio);
-
+mTermMinPolygons = 25;
         //-- factors for bsp tree split plane heuristics
         environment->GetFloatValue("VspBspTree.Factor.balancedRays", mBalancedRaysFactor);
@@ -116 +116 @@
 
 
+        mSubdivisionStats.open("subdivisionStats.log");
 
 
@@ -387 +388 @@
 
 // return memory usage in MB
-float VspBspTree::GetMemUsage(/*const VspBspTraversalStack &tstack*/) const
+float VspBspTree::GetMemUsage(/*const VspBspTraversalQueue &tstack*/) const
 {
         return
@@ -402 +403 @@
 void VspBspTree::Construct(const PolygonContainer &polys, RayInfoContainer *rays)
 {
-        VspBspTraversalStack tStack;
+        VspBspTraversalQueue tQueue;
 
         mRoot = new BspLeaf();
@@ -426 +427 @@
                 tData.mIsKdNode = false;
 
-        tStack.push(tData);
-
+        tQueue.push(tData);
+
+        mTotalCost = tData.GetCost() / mBox.GetVolume();
+
+        Debug << "total cost: " << mTotalCost << endl;
+        mSplits = 0;
+        
         mBspStats.Start();
         cout << "Contructing vsp bsp tree ... \n";
@@ -440 +446 @@
         int nleaves = 500;
 
-        while (!tStack.empty())
-        {
-                tData = tStack.top();
-            tStack.pop();               
+        while (!tQueue.empty())
+        {
+                tData = tQueue.top();
+            tQueue.pop();               
 
                 if (0 && !mOutOfMemory)
@@ -457 +463 @@
 
                 // subdivide leaf node
-                BspNode *r = Subdivide(tStack, tData);
+                BspNode *r = Subdivide(tQueue, tData);
 
                 if (r == mRoot)
@@ -489 +495 @@
                  (data.mProbability <= mTermMinProbability) ||
                  (mBspStats.Leaves() >= mMaxViewCells) ||
+#if 0
+                 (((int)data.mPolygons->size() <= mTermMinPolygons) && !data.mPolygons->empty())||
+#endif
                  (data.GetAvgRayContribution() > mTermMaxRayContribution) ||
                  (data.mDepth >= mTermMaxDepth));
@@ -494 +503 @@
 
 
-BspNode *VspBspTree::Subdivide(VspBspTraversalStack &tStack,
+BspNode *VspBspTree::Subdivide(VspBspTraversalQueue &tQueue,
                                                            VspBspTraversalData &tData)
 {
@@ -512 +521 @@
                 if (!newNode->IsLeaf()) //-- continue subdivision
                 {
+                        if (1)
+                        {
+                                float costDecr = 
+                                        (tFrontData.GetCost() + tBackData.GetCost() - tData.GetCost()) / mBox.GetVolume();
+                                mTotalCost += costDecr;
+
+                                mSubdivisionStats 
+                                                << "#Nodes\n" << ++ mSplits << endl
+                                                << "#RenderCostDecrease\n" << -costDecr << endl 
+                                                << "#TotalRenderCost\n" << mTotalCost << endl;
+                        }
+
                         // push the children on the stack
-                        tStack.push(tFrontData);
-                        tStack.push(tBackData);
+                        tQueue.push(tFrontData);
+                        tQueue.push(tBackData);
 
                         // delete old leaf node
@@ -1341 +1362 @@
                         float oldCost, newCost;
 
+                        // only render cost
                         if (1)
                         {
@@ -1346 +1368 @@
                                 newCost = newRenderCost;
                         }
-                        else
+                        else // also considering standard deviation
                         {
                                 // standard deviation is difference of back and front pvs
@@ -1361 +1383 @@
 
                         cost += mPvsFactor * newCost / oldCost;
-                }
-                else
-                {
-                        //-- compute weighted sum of expected render cost and standard deviation
-                        
-                        //-- first compute expected render cost         
-                        const float penaltyOld = EvalPvsPenalty(totalPvs, lowerPvsLimit, upperPvsLimit);
-                const float penaltyFront = EvalPvsPenalty(pvsFront, lowerPvsLimit, upperPvsLimit);
-                        const float penaltyBack = EvalPvsPenalty(pvsBack, lowerPvsLimit, upperPvsLimit);
-                        
-                        const float renderCostFront = penaltyFront * pFront;
-                        const float renderCostBack = penaltyBack * pBack;
-
-                        const float oldRenderCost = pOverall * (float)penaltyOld + Limits::Small;
-                        const float newRenderCost = renderCostFront + renderCostBack;
-
-
-                        //-- compute standard deviation
-                        const float expectedCost = 0.5f * (renderCostBack + renderCostFront);
-
-                        const float devFront = fabs(renderCostFront - expectedCost);
-                        
-                        const float devBack = fabs(renderCostBack - expectedCost);
-
-                        const float newDev = 0.5f * (devFront + devBack);
-                        const float oldDev = oldRenderCost * oldRenderCost;
-
-                        const float newCost = newRenderCost * mRenderCostWeight + newDev * (1.0f - mRenderCostWeight);
-                        const float oldCost = oldRenderCost * mRenderCostWeight + oldDev * (1.0f - mRenderCostWeight);
-
-                        cost += mPvsFactor * newCost / oldCost;
-
-                        // also try to equalize render differences between front and back pvs
-                        //const float oldCost = pOverall + Limits::Small;
-                        //float newCost = (float)abs(pvsFront - pvsBack);
-                        
                 }
         }
@@ -1404 +1390 @@
                   << " frontpvs: " << pvsFront << " pFront: " << pFront
                   << " backpvs: " << pvsBack << " pBack: " << pBack << endl << endl;
+        Debug << "cost: " << cost << endl;
 #endif
 
+        
         // normalize cost by sum of linear factors
         if(0)
@@ -1638 +1626 @@
         int hits = 0;
 
-        stack<BspRayTraversalData> tStack;
+        stack<BspRayTraversalData> tQueue;
 
         float maxt, mint;
@@ -1646 +1634 @@
 
         Intersectable::NewMail();
-
+        ViewCell::NewMail();
         Vector3 entp = ray.Extrap(mint);
         Vector3 extp = ray.Extrap(maxt);
@@ -1690 +1678 @@
 
                         // push data for far child
-                        tStack.push(BspRayTraversalData(farChild, extp, maxt));
+                        tQueue.push(BspRayTraversalData(farChild, extp, maxt));
 
                         // find intersection of ray segment with plane
@@ -1709 +1697 @@
 
                         //-- fetch the next far child from the stack
-                        if (tStack.empty())
+                        if (tQueue.empty())
                                 break;
 
@@ -1718 +1706 @@
                                 break;
 
-                        BspRayTraversalData &s = tStack.top();
+                        BspRayTraversalData &s = tQueue.top();
 
                         node = s.mNode;
@@ -1724 +1712 @@
                         maxt = s.mMaxT;
 
-                        tStack.pop();
+                        tQueue.pop();
                 }
         }
@@ -2204 +2192 @@
         return (int)neighbors.size();
 }
+
+
+
+int VspBspTree::FindApproximateNeighbors(BspNode *n, vector<BspLeaf *> &neighbors,
+                                                                                 const bool onlyUnmailed) const
+{
+        stack<bspNodePair> nodeStack;
+        
+        BspNodeGeometry nodeGeom;
+        ConstructGeometry(n, nodeGeom);
+        
+        // split planes from the root to this node
+        // needed to verify that we found neighbor leaf
+        // TODO: really needed?
+        vector<Plane3> halfSpaces;
+        ExtractHalfSpaces(n, halfSpaces);
+
+
+        BspNodeGeometry *rgeom = new BspNodeGeometry();
+        ConstructGeometry(mRoot, *rgeom);
+
+        nodeStack.push(bspNodePair(mRoot, rgeom));
+
+        while (!nodeStack.empty())
+        {
+                BspNode *node = nodeStack.top().first;
+                BspNodeGeometry *geom = nodeStack.top().second;
+        
+                nodeStack.pop();
+
+                if (node->IsLeaf())
+                {
+                        // test if this leaf is in valid view space
+                        if (node->TreeValid() &&
+                                (node != n) && 
+                                (!onlyUnmailed || !node->Mailed()))
+                        {
+                                bool isAdjacent = true;
+
+                                // neighbor was found
+                                if (isAdjacent)
+                                {       
+                                        neighbors.push_back(dynamic_cast<BspLeaf *>(node));
+                                }
+                        }
+                }
+                else
+                {
+                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
+
+                        const int cf = Polygon3::ClassifyPlane(nodeGeom.mPolys,
+                                                                                                   interior->GetPlane(),
+                                                                                                   mEpsilon);
+                        
+                        BspNode *front = interior->GetFront();
+                        BspNode *back = interior->GetBack();
+            
+                        BspNodeGeometry *fGeom = new BspNodeGeometry();
+                        BspNodeGeometry *bGeom = new BspNodeGeometry();
+
+                        geom->SplitGeometry(*fGeom,
+                                                                *bGeom,
+                                                                interior->GetPlane(),
+                                                                mBox,
+                                                                mEpsilon);
+                
+                        if (cf == Polygon3::FRONT_SIDE)
+                        {
+                                nodeStack.push(bspNodePair(interior->GetFront(), fGeom));
+                                DEL_PTR(bGeom);
+                        }
+                        else
+                        {
+                                if (cf == Polygon3::BACK_SIDE)
+                                {
+                                        nodeStack.push(bspNodePair(interior->GetBack(), bGeom));
+                                        DEL_PTR(fGeom);
+                                }
+                                else
+                                {       // random decision
+                                        nodeStack.push(bspNodePair(front, fGeom));
+                                        nodeStack.push(bspNodePair(back, bGeom));
+                                }
+                        }
+                }
+        
+                DEL_PTR(geom);
+        }
+
+        return (int)neighbors.size();
+}
+
 
 
@@ -2378 +2458 @@
 {
         int hits = 0;
-        stack<BspRayTraversalData> tStack;
+        stack<BspRayTraversalData> tQueue;
 
         float mint = 0.0f, maxt = 1.0f;
 
         Intersectable::NewMail();
+        ViewCell::NewMail();
 
         Vector3 entp = origin;
@@ -2431 +2512 @@
 
                         // push data for far child
-                        tStack.push(BspRayTraversalData(farChild, extp));
+                        tQueue.push(BspRayTraversalData(farChild, extp));
 
                         // find intersection of ray segment with plane
@@ -2450 +2531 @@
 
                         //-- fetch the next far child from the stack
-                        if (tStack.empty())
+                        if (tQueue.empty())
                                 break;
 
                         entp = extp;
                         
-                        BspRayTraversalData &s = tStack.top();
+                        BspRayTraversalData &s = tQueue.top();
 
                         node = s.mNode;
                         extp = s.mExitPoint;
 
-                        tStack.pop();
+                        tQueue.pop();
                 }
         }
@@ -2711 +2792 @@
                 vector<BspLeaf *> neighbors;
                 FindNeighbors(leaf, neighbors, true);
-
+                //FindApproximateNeighbors(leaf, neighbors, true);
                 vector<BspLeaf *>::const_iterator nit, nit_end = neighbors.end();
 

trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.h

@@ -24 +24 @@
 class Beam;
 class ViewCellsTree;
+
 
 struct BspRay;
@@ -123 +124 @@
                 float GetCost() const
                 {
-#if 0
+#if 1
                         return mPvs * mProbability;
 #endif
-#if 1
-                        return - mDepth;
+#if 0
+                        return (float) (-mDepth); // for regular grid
 #endif
 #if 0
@@ -154 +155 @@
     };
         
-        typedef std::priority_queue<VspBspTraversalData> VspBspTraversalStack;
-        //typedef std::stack<VspBspTraversalData> VspBspTraversalStack;
+        typedef std::priority_queue<VspBspTraversalData> VspBspTraversalQueue;
+        //typedef std::stack<VspBspTraversalData> VspBspTraversalQueue;
 
         /** Default constructor creating an empty tree.
@@ -292 +293 @@
 
         
+        int FindApproximateNeighbors(BspNode *n, 
+                                                             vector<BspLeaf *> &neighbors,
+                                                                 const bool onlyUnmailed) const;
+
         /** Checks if tree validity-flags are right 
                 with respect to view cell valitiy.
@@ -368 +373 @@
                 @returns new root of the subtree
         */
-        BspNode *Subdivide(VspBspTraversalStack &tStack, 
+        BspNode *Subdivide(VspBspTraversalQueue &tStack, 
                                            VspBspTraversalData &tData);
 
@@ -598 +603 @@
         /** Returns estimated memory usage of tree.
         */
-        //float GetMemUsage(const VspBspTraversalStack &tstack) const;
+        //float GetMemUsage(const VspBspTraversalQueue &tstack) const;
         float GetMemUsage() const;
 
@@ -633 +638 @@
         float mTermMinAccRayLength;
 
-        
+        //HACK
+        int mTermMinPolygons;
 
         //-- termination criteria for axis aligned split
@@ -677 +683 @@
         int mMaxViewCells;
         
+        ofstream  mSubdivisionStats;
 
         // if rays should be stored in leaves
@@ -698 +705 @@
         bool mOutOfMemory;
         
-        
+        float mTotalCost;
+        int mSplits;
+
+        ofstream mSubdivsionStats;
+
 private:
 

trunk/VUT/GtpVisibilityPreprocessor/src/VssPreprocessor.cpp

@@ -77 +77 @@
     int hits = 0;
   static Ray ray;
-  AxisAlignedBox3 box = mKdTree->GetBox();
+  AxisAlignedBox3 box =  mViewSpaceBox ? *mViewSpaceBox : mKdTree->GetBox();
 
   AxisAlignedBox3 sbox = box;
@@ -203 +203 @@
 {
   Vector3 point;
-  if (!use2dSampling) {
-        if (0) {
-          Vector3 normal;
-          int i = Random((int)mObjects.size());
-          Intersectable *object = mObjects[i];
-          object->GetRandomSurfacePoint(point, normal);
-        } else
-          point = mKdTree->GetBox().GetRandomPoint();
+  if (!use2dSampling) 
+  {
+          if (0) 
+          {
+                  Vector3 normal;
+                  int i = Random((int)mObjects.size());
+                  Intersectable *object = mObjects[i];
+                  object->GetRandomSurfacePoint(point, normal);
+          } 
+          else
+                  point = mKdTree->GetBox().GetRandomPoint();
         //        point = viewpoint + UniformRandomVector();
-
-  } else {
-        AxisAlignedBox3 box;
-
-        if (viewSpaceBox)
-          box =*viewSpaceBox;
-        else
-          box = mKdTree->GetBox();
-
-        point = box.GetRandomPoint();
-        point.y = viewpoint.y;
+  } 
+  else 
+  {
+          AxisAlignedBox3 box;
+
+          if (viewSpaceBox)
+                  box =*viewSpaceBox;
+          else
+                  box = mKdTree->GetBox();
+
+          point = box.GetRandomPoint();
+          point.y = viewpoint.y;
   }
 
@@ -528 +532 @@
   {
           if (0)
-                mViewSpaceBox = box;
+                  mViewSpaceBox = box;
           else
           {
@@ -536 +540 @@
                 Vector3 size = mViewSpaceBox->Size();
                 //size[1] *= 1.25;
-                Vector3 enlarge(size[0] * 0.1f, size[1] * 0.0f, size[2] * 0.1);
+                Vector3 enlarge(size[0] * 0.25f, size[1] * 0.0f, size[2] * 0.25f);
 
                 mViewSpaceBox->Enlarge(enlarge);