Changeset 580

Timestamp:

02/01/06 19:29:59 (18 years ago)

Author:

mattausch

Message:

implemented variance
started implementing merge history

Location:

trunk/VUT/GtpVisibilityPreprocessor

Files:

• scripts/Preprocessor.vcproj (modified) (1 diff)
• scripts/default.env (modified) (6 diffs)
• src/Environment.cpp (modified) (3 diffs)
• src/KdTree.cpp (modified) (1 diff)
• src/RenderSimulator.cpp (modified) (1 diff)
• src/ViewCell.cpp (modified) (6 diffs)
• src/ViewCell.h (modified) (9 diffs)
• src/ViewCellBsp.cpp (modified) (3 diffs)
• src/ViewCellsManager.cpp (modified) (39 diffs)
• src/ViewCellsManager.h (modified) (12 diffs)
• src/ViewCellsParser.cpp (modified) (2 diffs)
• src/VspBspTree.cpp (modified) (40 diffs)
• src/VspBspTree.h (modified) (12 diffs)
• src/VspKdTree.cpp (modified) (29 diffs)
• src/VspKdTree.h (modified) (3 diffs)
• src/X3dExporter.cpp (modified) (2 diffs)

trunk/VUT/GtpVisibilityPreprocessor/scripts/Preprocessor.vcproj

@@ -77 +77 @@
                                 Name="VCLinkerTool"
                                 AdditionalDependencies="xerces-c_2.lib zdll.lib zziplib.lib devil.lib qtmain.lib QtOpenGL4.lib QtCore4.lib QtGui4.lib Qt3Supportd4.lib QAxContainer.lib glut32.lib OpenGL32.Lib glu32.lib cg.lib cgGL.lib"
-                                AdditionalLibraryDirectories="..\support\xercesc\lib\;..\support\zlib\lib\;..\support\devil\lib;"$(QTDIR)\lib";..\include;..\src\GL;"$(CG_LIB_PATH)""/>
+                                AdditionalLibraryDirectories="..\support\xercesc\lib\;..\support\zlib\lib\;..\support\devil\lib;"$(QTDIR)\lib";..\include;..\src\GL;"$(CG_LIB_PATH)""
+                                LargeAddressAware="2"/>
                         <Tool
                                 Name="VCMIDLTool"/>

trunk/VUT/GtpVisibilityPreprocessor/scripts/default.env

@@ -176 +176 @@
         # samples used for view cell construction
         Construction {
-                samples 1500000
-                samplesPerPass 100000
+                samples 1200000
+                samplesPerPass 300000
         }
 
@@ -195 +195 @@
         maxPvsRatio 1.0
                 
-        delayedConstruction false
         pruneEmptyViewCells false
         processOnlyValidViewCells false
@@ -202 +201 @@
                 # how much samples are used for post processing
                 samples 300000
+                renderCostWeight 0.5
+                maxCostRatio 0.1
+                minViewCells 110
+                avgCostMaxDeviation 0.8
+                maxMergesPerPass 500 
+                useRaysForMerge false
         }
 
@@ -213 +218 @@
                 exportRays false
                 exportGeometry true
+                exportMergedViewCells false
         }
         
@@ -274 +280 @@
                 epsilon 0.005
                 randomize false
+                renderCostWeight 0.5
         }
 
@@ -331 +338 @@
                 # x3d visualization of the split planes
                 exportSplits true
-                exportMergedViewCells false
-        }
-        
-        PostProcess {
-                maxCostRatio 0.1
-                minViewCells 110
-                useRaysForMerge false
-                exportMergeStats false
         }
 }

trunk/VUT/GtpVisibilityPreprocessor/src/Environment.cpp

@@ -1283 +1283 @@
                 "false");
         
+        
+        RegisterOption("ViewCells.PostProcess.maxCostRatio",
+                        optFloat,
+                        "-view_cells_post_process_max_cost_ratio=",
+                        "0.9");
+
+        
+        RegisterOption("ViewCells.PostProcess.renderCostWeight",
+                        optFloat,
+                        "-view_cells_post_process_render_cost_weight",
+                        "0.5");
+
+        
+        RegisterOption("ViewCells.PostProcess.avgCostMaxDeviation",
+                        optFloat,
+                        "-vsp_bsp_avgcost_max_deviations",
+                        "0.5");
+
+        RegisterOption("ViewCells.PostProcess.maxMergesPerPass", 
+                optInt, 
+                "vsp_bsp_term_max_merges_per_pass=", 
+                "500");
+
+        RegisterOption("ViewCells.PostProcess.minViewCells", 
+                optInt, 
+                "vsp_bsp_term_post_process_min_view_cells=", 
+                "1000");
+
+        RegisterOption("ViewCells.PostProcess.useRaysForMerge", 
+                optBool,
+                "view_cells_post_process_use_rays_for_merge=", 
+                "false");
+
+        RegisterOption("ViewCells.Visualization.exportMergedViewCells",
+                optBool, 
+                "view_cells_viz_export_merged_viewcells=", 
+                "false");
+
+
         /************************************************************************************/
         /*                         Render simulation related options                        */
@@ -1834 +1873 @@
         RegisterOption("VspBspTree.Factor.pvs", optFloat, "-vsp_bsp_factor_pvs=", "1.0");
 
-        RegisterOption("VspBspTree.PostProcess.maxCostRatio",
+
+        RegisterOption("VspBspTree.Construction.renderCostWeight",
                         optFloat,
-                        "-vsp_bsp_post_process_max_cost_ratio=",
-                        "0.9");
-
-        RegisterOption("VspBspTree.PostProcess.minViewCells", 
-                optInt, 
-                "vsp_bsp_term_post_process_min_view_cells=", 
-                "1000");
-
-        RegisterOption("VspBspTree.PostProcess.useRaysForMerge", 
-                optBool, 
-                "vsp_bsp_term_post_process_use_rays_for_merge=", 
-                "false");
+                        "-vsp_bsp_post_process_render_cost_weight",
+                        "0.5");
+
 
         RegisterOption("VspBspTree.Construction.randomize", 
@@ -1865 +1896 @@
                 "8.0");
 
-        RegisterOption("VspBspTree.Visualization.exportMergedViewCells",
-                optBool, 
-                "vsp_bsp_viz_export_merged_viewcells=", 
-                "false");
-
-        RegisterOption("VspBspTree.PostProcess.exportMergeStats",
-                optBool, 
-                "vsp_bsp_viz_export_merge_stats=", 
-                "false");
+        
+        
 
         //////////////////////////////////////////////////////////////////////////////////

trunk/VUT/GtpVisibilityPreprocessor/src/KdTree.cpp

@@ -888 +888 @@
           leaf->mViewCell = viewCell;
           // push back pointer to this leaf
-          viewCell->mLeaves.push_back(leaf);
+          viewCell->mLeaf = leaf;
       vc.push_back(viewCell);
     } else {

trunk/VUT/GtpVisibilityPreprocessor/src/RenderSimulator.cpp

@@ -94 +94 @@
                 ViewCell *vc = *it;
 
-                const bool valid = !vc->GetValid();
+                const bool valid = vc->GetValid();
         
 

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCell.cpp

@@ -4 +4 @@
 #include "MeshKdTree.h"
 #include "Triangle3.h"
+#include "common.h"
+#include "Environment.h"
+#include "ViewCellsManager.h"
+#include "Exporter.h"
+
 #include <time.h>
 #include <iomanip>
+#include <stack>
+
+
+
+template <typename T> class myless
+{
+public:
+        
+        //bool operator() (HierarchyNode *v1, HierarchyNode *v2) const
+        bool operator() (T v1, T v2) const
+        {
+                return (v1->GetTimeStamp() > v2->GetTimeStamp());
+        }
+};
+
+
+typedef priority_queue<ViewCell *, vector<ViewCell *>, myless<vector<ViewCell *>::value_type> > TraversalQueue;
+
+int ViewCell::sMailId = 21843194198;
+int ViewCell::sReservedMailboxes = 1;
+
+//int upperPvsLimit = 120;
+//int lowerPvsLimit = 5;
+
+float MergeCandidate::sRenderCostWeight = 0;
+
+
+// pvs penalty can be different from pvs size
+inline float EvalPvsPenalty(const int pvs, 
+                                                        const int lower,
+                                                        const int upper)
+{
+        // clamp to minmax values
+        if (pvs < lower)
+                return (float)lower;
+        if (pvs > upper)
+                return (float)upper;
+
+        return (float)pvs;
+}
+
+
+int ComputeMergedPvsSize(const ObjectPvs &pvs1, const ObjectPvs &pvs2)
+{
+        int pvs = pvs1.GetSize();
+
+        // compute new pvs size
+        ObjectPvsMap::const_iterator it, it_end =  pvs1.mEntries.end();
+
+        Intersectable::NewMail();
+
+        for (it = pvs1.mEntries.begin(); it != it_end; ++ it)
+        {
+                (*it).first->Mail();
+        }
+
+        it_end = pvs2.mEntries.end();
+
+        for (it = pvs2.mEntries.begin(); it != it_end; ++ it)
+        {
+                Intersectable *obj = (*it).first;
+                if (!obj->Mailed())
+                        ++ pvs;
+        }
+
+        return pvs;
+}
+
 
 ViewCell::ViewCell(): 
@@ -12 +85 @@
 mArea(-1),
 mVolume(-1),
-mValid(true)
+mValid(true),
+mParent(NULL),
+mTimeStamp(0)
 {
 }
@@ -21 +96 @@
 mArea(-1),
 mVolume(-1),
-mValid(true)
+mValid(true),
+mParent(NULL),
+mTimeStamp(0)
 {
 }
@@ -43 +120 @@
 
 
-void ViewCell::AddPassingRay(const Ray &ray, const int contributions)
-{
-        mPassingRays.AddRay(ray, contributions);
-}
-
-
 float ViewCell::GetVolume() const
 {
@@ -113 +184 @@
 
 
+/*bool ViewCell::IsLeaf() const
+{
+        return true;
+}*/
+
+
+void ViewCell::SetParent(ViewCellInterior *parent)
+{
+        mParent = parent;
+}
+
+
+bool ViewCell::IsRoot() const
+{
+        return !mParent;
+}
+
+
+ViewCellInterior *ViewCell::GetParent() const
+{
+        return mParent;
+}
+
+
+void ViewCell::SetTimeStamp(const int timeStamp)
+{
+        mTimeStamp = timeStamp;
+}
+
+
+int ViewCell::GetTimeStamp() const
+{
+        return mTimeStamp;
+}
+
+
+/************************************************************************/
+/*                class ViewCellInterior implementation                 */
+/************************************************************************/
+
+
+ViewCellInterior::ViewCellInterior()
+{
+}
+
+
+ViewCellInterior::~ViewCellInterior()
+{
+        ViewCellContainer::const_iterator it, it_end = mChildren.end();
+
+        for (it = mChildren.begin(); it != it_end; ++ it)
+                delete (*it);
+}
+
+
+ViewCellInterior::ViewCellInterior(Mesh *mesh): 
+ViewCell(mesh)
+{
+}
+
+
+bool ViewCellInterior::IsLeaf() const
+{
+        return false;
+}
+
+
+void ViewCellInterior::SetupChildLink(ViewCell *l)
+{
+    mChildren.push_back(l);
+    l->mParent = this;
+}
+
+
+
 /************************************************************************/
 /*                class ViewCellsStatistics implementation              */
 /************************************************************************/
 
+
+
+
 void ViewCellsStatistics::Print(ostream &app) const
 {
@@ -145 +294 @@
         app << "========== End of View Cells Statistics ==========\n";
 }
+
+
+/*************************************************************************/
+/*                    class ViewCellsTree implementation                 */
+/*************************************************************************/
+
+
+ViewCellsTree::ViewCellsTree(ViewCellsManager *vcm):
+mRoot(NULL),
+mUseAreaForPvs(false),
+mViewCellsManager(vcm)
+{
+        environment->GetBoolValue("ViewCells.Visualization.exportMergedViewCells", mExportMergedViewCells);
+
+        //-- merge options
+        environment->GetFloatValue("ViewCells.PostProcess.renderCostWeight", mRenderCostWeight);
+        environment->GetIntValue("ViewCells.PostProcess.minViewCells", mMergeMinViewCells);
+        environment->GetFloatValue("ViewCells.PostProcess.maxCostRatio", mMergeMaxCostRatio);
+        
+        MergeCandidate::sRenderCostWeight = mRenderCostWeight;
+
+        mStats.open("mergeStats.log");
+}
+
+
+int ViewCellsTree::GetSize(ViewCell *vc) const
+{
+        int vcSize = 0;
+
+        stack<ViewCell *> tstack;
+
+        tstack.push(vc);
+
+        while (!tstack.empty())
+        {
+                ViewCell *vc = tstack.top();
+                tstack.pop();
+
+                if (vc->IsLeaf())
+                {
+                        ++ vcSize;
+                }
+                else
+                {
+                        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
+                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
+                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
+                                tstack.push(*it);
+                        
+                }
+        }
+
+        return vcSize;
+}
+
+
+void ViewCellsTree::CollectLeaves(ViewCell *vc, ViewCellContainer &leaves) const
+{
+        stack<ViewCell *> tstack;
+
+        tstack.push(vc);
+
+        while (!tstack.empty())
+        {
+                ViewCell *vc = tstack.top();
+                tstack.pop();
+
+                if (vc->IsLeaf())
+                {
+                        leaves.push_back(vc);
+                }
+                else
+                {
+                        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
+                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
+                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
+                                tstack.push(*it);
+                        
+                }
+        }
+}
+
+
+ViewCellsTree::~ViewCellsTree()
+{
+        DEL_PTR(mRoot);
+}
+
+
+int ViewCellsTree::ConstructMergeTree(const VssRayContainer &rays, 
+                                                                          const ObjectContainer &objects)
+{
+        // number of view cells equals the number of leaves 
+        // (without the invalid ones )
+        //mNumViewCells = mBspStats.Leaves();//- mBspStats.invalidLeaves;
+        mNumViewCells = (int)mViewCellsManager->GetViewCells().size();
+
+        float variance = 0;
+        int totalPvs = 0;
+        float totalCost = 0;
+
+        //-- compute statistics values of initial view cells
+        mViewCellsManager->EvaluateRenderStatistics(totalCost,
+                                                                                                mExpectedCost,
+                                                                                                mDeviation,
+                                                                                                variance,
+                                                                                                totalPvs,
+                                                                                                mAvgRenderCost);
+
+
+        //-- fill merge queue
+        vector<MergeCandidate> candidates;
+
+        mViewCellsManager->CollectMergeCandidates(rays, candidates);
+        while(!candidates.empty())
+        {
+                MergeCandidate mc = candidates.back();
+                candidates.pop_back();
+                EvalMergeCost(mc);
+                mMergeQueue.push(mc);
+        }
+
+        Debug << "************************* merge ***********************************" << endl;  
+        Debug << "deviation: " << mDeviation << endl;
+        Debug << "avg render cost: " << mAvgRenderCost << endl;
+        Debug << "expected cost: " <<mExpectedCost << endl;
+
+
+        ViewCellsManager::PvsStatistics pvsStats;
+        mViewCellsManager->GetPvsStatistics(pvsStats);
+
+        static float expectedValue = pvsStats.avgPvs;
+        
+        // the current view cells are kept in this container
+        // we start with the current view cells from the
+        // view cell manager. They will change with
+        // subsequent merges
+        ViewCellContainer &viewCells = mViewCellsManager->GetViewCells();
+
+
+        ViewCell::NewMail();
+
+        MergeStatistics mergeStats;
+        mergeStats.Start();
+        
+        long startTime = GetTime();
+
+        mergeStats.collectTime = TimeDiff(startTime, GetTime());
+        mergeStats.candidates = (int)mMergeQueue.size();
+        startTime = GetTime();
+
+        // frequency stats are updated
+        const int statsOut = 100;
+
+        // passes are needed for statistics, because we don't want to record
+        // every merge
+        int pass = 0;
+        int mergedPerPass = 0;
+        float realExpectedCost = mExpectedCost;
+        float realAvgRenderCost = mAvgRenderCost;
+        int realNumViewCells = mNumViewCells;
+        
+        // maximal ratio of old expected render cost to expected render
+        // when the the render queue has to be reset.
+        float avgCostMaxDeviation;
+        int maxMergesPerPass;
+        int numActiveViewCells = 0;
+
+        environment->GetIntValue("ViewCells.PostProcess.maxMergesPerPass", maxMergesPerPass);
+        environment->GetFloatValue("ViewCells.PostProcess.avgCostMaxDeviation", avgCostMaxDeviation);
+
+        cout << "actual merge starts now ... " << endl;
+        
+        //ResetMergeQueue();
+
+        //-- use priority queue to merge leaf pairs
+
+        while (!mMergeQueue.empty() && (realNumViewCells > mMergeMinViewCells) &&
+                   (mMergeQueue.top().GetRenderCost() < mMergeMaxCostRatio * totalCost))
+        {
+                //-- reset merge queue if the ratio of current expected cost / real expected cost
+                //   too small or after a given number of merges
+                if(0)
+                if ((mergedPerPass > maxMergesPerPass) ||
+                        (avgCostMaxDeviation > mAvgRenderCost / realAvgRenderCost))
+                {
+                        Debug << "************ reset queue *****************\n"
+                                  << "ratios: " << avgCostMaxDeviation 
+                                  << " real avg render cost " << realAvgRenderCost << " average render cost " << mAvgRenderCost
+                                  << " merged per pass : " << mergedPerPass << " of maximal " << maxMergesPerPass << endl;
+
+                        Debug << "Values before reset: "  
+                                  << " erc: " << mExpectedCost 
+                                  << " avgrc: " << mAvgRenderCost
+                                  << " dev: " << mDeviation << endl;
+        
+                        // adjust render cost
+                        ++ pass;
+
+                        mergedPerPass = 0;
+                        mExpectedCost = realExpectedCost;
+                        mAvgRenderCost = realAvgRenderCost;
+                        mNumViewCells = realNumViewCells;
+                        
+                        const int numActiveViewCells = UpdateMergedViewCells(viewCells);
+
+                    ResetMergeQueue();
+
+                        
+                        Debug << "Values after reset: "  
+                                  << " erc: " << mExpectedCost 
+                                  << " avg: " << mAvgRenderCost 
+                                  << " dev: " << mDeviation << endl;
+
+                        if (mExportMergedViewCells)
+                        {
+                                ExportMergedViewCells(viewCells, objects, numActiveViewCells);
+                        }
+                }
+
+#ifdef _DEBUG
+                Debug << "abs mergecost: " << mMergeQueue.top().GetMergeCost() << 
+                          << " rel mergecost: " << mMergeQueue.top().GetRenderCost() / mExpectedCost << 
+                          << " max ratio: " << mMergeMaxCostRatio << endl
+                          << " expected value: " << realExpectedCost << endl;
+#endif
+
+        
+                MergeCandidate mc = mMergeQueue.top();
+                mMergeQueue.pop();
+        
+                // both view cells equal!
+                if (mc.mLeftViewCell == mc.mRightViewCell)
+                        continue;
+
+                if (mc.IsValid())
+                {
+                        ViewCell::NewMail();
+                                                
+                        -- realNumViewCells;
+                        ++ mergeStats.merged;
+                        ++ mergedPerPass;
+
+
+                        //-- update statistical values
+
+                        // total render cost and deviation has changed
+                        // real expected cost will be larger than expected cost used for the
+                        // cost heuristics, but cannot recompute costs on each increase of the 
+                        // expected cost
+
+                        totalCost += mc.GetRenderCost();
+                        mDeviation += mc.GetDeviationIncr();
+                                                
+                        realExpectedCost = totalCost / (float)realNumViewCells;
+                        
+                        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);
+
+                        realAvgRenderCost = (float)totalPvs / (float)realNumViewCells;
+#if VC_HISTORY
+                        if (mc.mLeftViewCell->IsSibling(mc.mRightViewCell))
+                                ++ mergeStats.siblings;
+#endif
+                        if (((mergeStats.merged % statsOut) == 0) || 
+                                (realNumViewCells == mMergeMinViewCells))
+                        {
+                                cout << "merged " << mergeStats.merged << " view cells" << endl;
+
+                                mStats 
+                                        << "#Pass\n" << pass << endl
+                                        << "#Merged\n" << mergeStats.merged << endl 
+                                        << "#Viewcells\n" << realNumViewCells << 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)realNumViewCells << endl
+                                        << "#TotalDeviation\n" << mDeviation<< endl;
+                        }
+                }
+                else
+                { 
+                        // merge candidate not valid, because one of the leaves was already
+                        // merged with another one => validate and reinsert into queue
+                        SetMergeCandidateValid(mc);
+                        mMergeQueue.push(mc);
+                }
+        }
+
+        // adjust stats and reset queue one final time
+        mExpectedCost = realExpectedCost;
+        mAvgRenderCost = realAvgRenderCost;
+        mNumViewCells = realNumViewCells;
+
+        UpdateMergedViewCells(viewCells);
+        ResetMergeQueue();
+
+
+        // create a root node if the merge was not done till root level,
+        // else take the single node as new root
+        if ((int)viewCells.size() > 1)
+        {
+                ViewCellInterior *root = new ViewCellInterior();
+
+                ViewCellContainer::const_iterator it, it_end = viewCells.end();
+                for (it = viewCells.begin(); it != it_end; ++ it)
+                        root->SetupChildLink(*it);
+
+                mRoot = root;
+        }
+        else if ((int)viewCells.size() == 1)
+        {
+                mRoot = viewCells[0];
+        }
+
+        mergeStats.expectedRenderCost = realExpectedCost;
+        mergeStats.deviation = mDeviation;
+
+        // we want to optimize this heuristics
+        mergeStats.heuristics = 
+                mDeviation * (1.0f - mRenderCostWeight) + 
+                mExpectedCost * mRenderCostWeight;
+
+        mergeStats.mergeTime = TimeDiff(startTime, GetTime());
+        mergeStats.Stop();
+
+        Debug << mergeStats << endl << endl;
+
+
+        //TODO: should return sample contributions?
+        return mergeStats.merged;
+}
+
+
+void ViewCellsTree::ResetMergeQueue()
+{
+        cout << "reset merge queue ... ";
+        
+        vector<MergeCandidate> buf;
+        buf.reserve(mMergeQueue.size());
+                        
+        
+        // store merge candidates in intermediate buffer
+        while (!mMergeQueue.empty())
+        {
+                MergeCandidate mc = mMergeQueue.top();
+                mMergeQueue.pop();
+                
+                // recalculate cost
+                SetMergeCandidateValid(mc);
+                buf.push_back(mc);                              
+        }
+
+        vector<MergeCandidate>::const_iterator bit, bit_end = buf.end();
+
+        // reinsert back into queue
+        for (bit = buf.begin(); bit != bit_end; ++ bit)
+        {      
+                mMergeQueue.push(*bit); 
+        }
+
+        cout << "finished" << endl;
+}
+
+
+int ViewCellsTree::UpdateMergedViewCells(ViewCellContainer &viewCells)
+{
+        int numActiveViewCells = 0;
+
+        // find all already merged view cells and remove them from view cells
+        int i = 0;
+
+        while (1)
+        {
+                while (!viewCells.empty() && (!viewCells.back()->GetParent()))
+                {
+                        viewCells.pop_back();
+                }
+
+                // all merged view cells have been found
+                if (i >= viewCells.size()) 
+                        break;
+
+                // already merged view cell, put it to end of vector
+                if (!viewCells[i]->IsRoot())
+                        swap(viewCells[i], viewCells.back());
+                
+                ++ i;
+        }
+
+        // add new view cells to container only if they don't have been 
+        // merged in the mean time
+        while (!mActiveViewCells.empty())
+        {
+                if (!mActiveViewCells.back()->GetParent())
+                {
+                        viewCells.push_back(mActiveViewCells.back());
+                        ++ numActiveViewCells;
+                }
+
+                mActiveViewCells.pop_back();
+        }
+
+        // update standard deviation
+        ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
+        
+        mDeviation = 0;
+
+        for (vit = viewCells.begin(); vit != vit_end; ++ vit)
+        {
+                int lower = mViewCellsManager->GetMinPvsSize();
+                int upper = mViewCellsManager->GetMaxPvsSize();
+                float penalty = EvalPvsPenalty((*vit)->GetPvs().GetSize(), lower, upper);
+                
+                mDeviation += fabs(mAvgRenderCost - penalty);
+        }
+
+        mDeviation /= (float)viewCells.size();
+
+        // clear the view cells which were merged
+        mInactiveViewCells.clear();
+        // remove the new view cells
+        mActiveViewCells.clear();
+
+        return numActiveViewCells;
+}
+
+
+void ViewCellsTree::ExportMergedViewCells(ViewCellContainer &viewCells, 
+                                                                                  const ObjectContainer &objects,
+                                                                                  const int numActiveViewCells)
+{
+        
+
+        char s[64];
+
+        sprintf(s, "merged_viewcells%07d.x3d", (int)viewCells.size());
+        Exporter *exporter = Exporter::GetExporter(s);
+
+        if (exporter)
+        {
+                cout << "exporting " << (int)viewCells.size() << " merged view cells ... ";
+                exporter->ExportGeometry(objects);
+                //Debug << "vc size " << (int)viewCells.size() << " merge queue size: " << (int)mMergeQueue.size() << endl;
+                ViewCellContainer::const_iterator it, it_end = viewCells.end();
+
+                int i = 0;
+                for (it = viewCells.begin(); it != it_end; ++ it)
+                {
+                        Material m;
+                        // assign special material to new view cells
+                        // new view cells are on the back of container
+                        if (i ++ >= (viewCells.size() - numActiveViewCells))
+                        {
+                                //m = RandomMaterial();
+                                m.mDiffuseColor.r = RandomValue(0.5f, 1.0f);
+                                m.mDiffuseColor.g = RandomValue(0.5f, 1.0f);
+                                m.mDiffuseColor.b = RandomValue(0.5f, 1.0f);
+                        }
+                        else
+                        {
+                                float col = RandomValue(0.1f, 0.4f);
+                                m.mDiffuseColor.r = col;
+                                m.mDiffuseColor.g = col;
+                                m.mDiffuseColor.b = col;
+                        }
+
+                        exporter->SetForcedMaterial(m);
+                        mViewCellsManager->ExportViewCellGeometry(exporter, *it);
+                }
+                delete exporter;
+                cout << "finished" << endl;
+        }
+}
+
+
+// TODO: should be done in view cells manager
+ViewCellInterior *ViewCellsTree::MergeViewCells(ViewCell *l, ViewCell *r, int &pvsDiff) //const
+{
+        ViewCellInterior *vc = mViewCellsManager->MergeViewCells(*l, *r);
+
+        // if merge was unsuccessful
+        if (!vc) return NULL;
+
+        // set new size of view cell
+        if (mUseAreaForPvs)
+                vc->SetArea(l->GetArea() + l->GetArea());
+        else
+                vc->SetVolume(r->GetVolume() + r->GetVolume());
+        
+        // important so other merge candidates sharing this view cell
+        // are notified that the merge cost must be updated!!
+        vc->Mail();
+
+        const int pvs1 = l->GetPvs().GetSize();
+        const int pvs2 = r->GetPvs().GetSize();
+
+
+        //-- clean up old view cells
+        if (0 && !mExportMergedViewCells)
+        {
+                DEL_PTR(l);
+                DEL_PTR(r);
+        }
+        else 
+        {
+                mInactiveViewCells.push_back(l);
+                mInactiveViewCells.push_back(r);
+                
+                mActiveViewCells.push_back(vc);
+        }
+
+        pvsDiff = vc->GetPvs().GetSize() - pvs1 - pvs2;
+
+        return vc;
+}
+
+
+
+
+int ViewCellsTree::RefineViewCells(const VssRayContainer &rays, const ObjectContainer &objects)
+{
+        Debug << "refining " << (int)mMergeQueue.size() << " candidates " << endl;
+        
+        // Use priority queue of remaining leaf pairs 
+        // The candidates either share the same view cells or
+        // are border leaves which share a boundary.
+        // We test if they can be shuffled, i.e.,
+        // either one leaf is made part of one view cell or the other
+        // leaf is made part of the other view cell. It is tested if the
+        // remaining view cells are "better" than the old ones.
+        //
+        // repeat the merging test numPasses times. For example, it could be
+        // that a shuffle only makes sense if another pair was shuffled before.
+        // Therefore we keep two queues and shift the merge candidates between
+        // those two queues until numPasses is reached
+        
+        queue<MergeCandidate> queue1;
+        queue<MergeCandidate> queue2;
+
+        queue<MergeCandidate> *shuffleQueue = &queue1;
+        queue<MergeCandidate> *backQueue = &queue2;
+
+        while (!mMergeQueue.empty())
+        {
+                MergeCandidate mc = mMergeQueue.top();
+                shuffleQueue->push(mc);
+                mMergeQueue.pop();
+        }
+
+        const int numPasses = 5;
+        int pass = 0;
+        int passShuffled = 0;
+        int shuffled = 0;
+        int shuffledViewCells = 0;
+
+        ViewCell::NewMail();
+        
+        do
+        {
+                passShuffled = 0;
+                while (!shuffleQueue->empty())
+                {
+                        MergeCandidate mc = shuffleQueue->front();
+                        shuffleQueue->pop();
+
+                        // both view cells equal or already shuffled
+                        if ((mc.GetLeftViewCell() == mc.GetRightViewCell()) || 
+                                (GetSize(mc.GetLeftViewCell()) == 1) || 
+                                (GetSize(mc.GetRightViewCell()) == 1))
+                        {                       
+                                continue;
+                        }
+
+                        // candidate for shuffling
+                        const bool wasShuffled = 
+                                ShuffleLeaves(mc.GetLeftViewCell(), mc.GetRightViewCell());
+                
+                        // shuffled or put into other queue for further refine
+                        if (wasShuffled)
+                        {
+                                ++ passShuffled;
+
+                                if (!mc.GetLeftViewCell()->Mailed())
+                                {
+                                        mc.GetLeftViewCell()->Mail();
+                                        ++ shuffledViewCells;
+                                }
+                                if (!mc.GetRightViewCell()->Mailed())
+                                {
+                                        mc.GetRightViewCell()->Mail();
+                                        ++ shuffledViewCells;
+                                }
+                        }
+                        else
+                        {
+                                backQueue->push(mc);
+                        }
+                }
+
+                // now the back queue is the current shuffle queue
+                swap(shuffleQueue, backQueue);
+                shuffled += passShuffled;
+                Debug << "shuffled in pass: " << passShuffled << endl;
+        }
+        while (((++ pass) < numPasses) && passShuffled);
+
+        while (!shuffleQueue->empty())
+        {
+                shuffleQueue->pop();
+        }
+
+        return shuffledViewCells;
+}
+
+
+
+
+inline int AddedPvsSize(ObjectPvs pvs1, const ObjectPvs &pvs2)
+{
+        return pvs1.AddPvs(pvs2);
+}
+
+
+// recomputes pvs size minus pvs of leaf l
+#if 0
+inline int SubtractedPvsSize(BspViewCell *vc, BspLeaf *l, const ObjectPvs &pvs2)
+{
+        ObjectPvs pvs;
+        vector<BspLeaf *>::const_iterator it, it_end = vc->mLeaves.end();
+        for (it = vc->mLeaves.begin(); it != vc->mLeaves.end(); ++ it)
+                if (*it != l)
+                        pvs.AddPvs(*(*it)->mPvs);
+        return pvs.GetSize();
+}
+#endif
+
+
+// computes pvs1 minus pvs2
+inline int SubtractedPvsSize(ObjectPvs pvs1, const ObjectPvs &pvs2)
+{
+        return pvs1.SubtractPvs(pvs2);
+}
+
+
+float ViewCellsTree::EvalShuffleCost(ViewCell *leaf, 
+                                                                         ViewCell *vc1, 
+                                                                         ViewCell *vc2) const
+{
+        //const int pvs1 = SubtractedPvsSize(vc1, leaf, *leaf->mPvs);
+        const int pvs1 = SubtractedPvsSize(vc1->GetPvs(), leaf->GetPvs());
+        const int pvs2 = AddedPvsSize(vc2->GetPvs(), leaf->GetPvs());
+
+        const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize();
+        const int upperPvsLimit = mViewCellsManager->GetMaxPvsSize();
+
+        const float pvsPenalty1 = 
+                EvalPvsPenalty(pvs1, lowerPvsLimit, upperPvsLimit);
+
+        const float pvsPenalty2 =
+                EvalPvsPenalty(pvs2, lowerPvsLimit, upperPvsLimit);
+
+
+        // don't shuffle leaves with pvs > max
+        if (0 && (pvs1 + pvs2 > mViewCellsManager->GetMaxPvsSize()))
+        {
+                return 1e20f;
+        }
+
+        float p1, p2;
+
+    if (mUseAreaForPvs)
+        {
+                p1 = vc1->GetArea() - leaf->GetArea();
+                p2 = vc2->GetArea() + leaf->GetArea();
+        }
+        else
+        {
+                p1 = vc1->GetVolume() - leaf->GetVolume();
+                p2 = vc2->GetVolume() + leaf->GetVolume();
+        }
+
+        const float renderCost1 = pvsPenalty1 * p1;
+        const float renderCost2 = pvsPenalty2 * p2;
+
+        float dev1, dev2;
+
+        if (1)
+        {
+                dev1 = fabs(mAvgRenderCost - pvsPenalty1);
+                dev2 = fabs(mAvgRenderCost - pvsPenalty2);
+        }
+        else
+        {
+                dev1 = fabs(mExpectedCost - renderCost1);
+                dev2 = fabs(mExpectedCost - renderCost2);
+        }
+        
+        return mRenderCostWeight * (renderCost1 + renderCost2) +
+                  (1.0f - mRenderCostWeight) * (dev1 + dev2) / (float)mNumViewCells;
+}
+
+
+void ViewCellsTree::ShuffleLeaf(ViewCell *leaf,
+                                                                ViewCell *vc1, 
+                                                                ViewCell *vc2) const
+{
+        // compute new pvs and area
+        vc1->GetPvs().SubtractPvs(leaf->GetPvs());
+        vc2->GetPvs().AddPvs(leaf->GetPvs());
+        
+        if (mUseAreaForPvs)
+        {
+                vc1->SetArea(vc1->GetArea() - leaf->GetArea());
+                vc2->SetArea(vc2->GetArea() + leaf->GetArea());
+        }
+        else
+        {
+                vc1->SetVolume(vc1->GetVolume() - leaf->GetVolume());
+                vc2->SetVolume(vc2->GetVolume() + leaf->GetVolume());
+        }
+
+        // TODO
+#if VC_HISTORY
+        /// add to second view cell
+        vc2->mLeaves.push_back(leaf);
+
+        // erase leaf from old view cell
+        vector<BspLeaf *>::iterator it = vc1->mLeaves.begin();
+
+        for (; *it != leaf; ++ it);
+        vc1->mLeaves.erase(it);
+
+        /*vc1->GetPvs().mEntries.clear();
+        for (; it != vc1->mLeaves.end(); ++ it)
+        {
+                if (*it == leaf)
+                        vc1->mLeaves.erase(it);
+                else
+                        vc1->GetPvs().AddPvs(*(*it)->mPvs);
+        }*/
+
+        leaf->SetViewCell(vc2); // finally change view cell
+#endif
+}
+
+
+bool ViewCellsTree::ShuffleLeaves(ViewCell *l, ViewCell *r) const
+{
+        float cost1, cost2;
+
+        //-- first test if shuffling would decrease cost
+        cost1 = GetCostHeuristics(l);
+        cost2 = GetCostHeuristics(r);
+
+        const float oldCost = cost1 + cost2;
+        
+        float shuffledCost1 = Limits::Infinity;
+        float shuffledCost2 = Limits::Infinity;
+
+        // the view cell should not be empty after the shuffle
+#if VC_HISTORY
+        shuffledCost1 = EvalShuffleCost(l, vc1, vc2);
+        /shuffledCost2 = EvalShuffleCost(r, vc2, vc1);
+
+        // if cost of shuffle is less than old cost => shuffle
+        if ((oldCost <= shuffledCost1) && (oldCost <= shuffledCost2))
+                return false;
+        
+        
+        if (shuffledCost1 < shuffledCost2)
+        {
+                ShuffleLeaf(leaf1, vc1, vc2);
+                leaf1->Mail();
+        }
+        else
+        {
+                ShuffleLeaf(leaf2, vc2, vc1);
+                leaf2->Mail();
+        }
+#endif
+        return true;
+}
+
+
+float ViewCellsTree::GetVariance(ViewCell *vc) const
+{
+        const int upper = mViewCellsManager->GetMaxPvsSize();
+        const int lower = mViewCellsManager->GetMinPvsSize();
+
+        if (1)
+        {
+                const float penalty = EvalPvsPenalty(vc->GetPvs().GetSize(), lower, upper);
+                return (mAvgRenderCost - penalty) * (mAvgRenderCost - penalty) / (float)mNumViewCells;
+        }
+
+    const float leafCost = GetRenderCost(vc);
+        return (mExpectedCost - leafCost) * (mExpectedCost - leafCost);
+}
+
+
+float ViewCellsTree::GetDeviation(ViewCell *vc) const
+{
+        const int upper = mViewCellsManager->GetMaxPvsSize();
+        const int lower = mViewCellsManager->GetMinPvsSize();
+
+        if (1)
+        {
+                const float penalty = EvalPvsPenalty(vc->GetPvs().GetSize(), lower, upper);
+                return fabs(mAvgRenderCost - penalty) / (float)mNumViewCells;
+        }
+
+    const float renderCost = GetRenderCost(vc);
+        return fabs(mExpectedCost - renderCost);
+}
+
+
+
+float ViewCellsTree::GetRenderCost(ViewCell *vc) const
+{
+        if (mUseAreaForPvs)
+                return vc->GetPvs().GetSize() * vc->GetArea();
+
+        return vc->GetPvs().GetSize() * vc->GetVolume();
+}
+
+
+float ViewCellsTree::GetCostHeuristics(ViewCell *vc) const
+{
+        return GetRenderCost(vc) * mRenderCostWeight + 
+                   GetDeviation(vc) * (1.0f - mRenderCostWeight);
+}
+
+
+void ViewCellsTree::SetMergeCandidateValid(MergeCandidate &mc) const
+{
+        while (mc.mLeftViewCell->mParent)
+        {
+                mc.mLeftViewCell = mc.mLeftViewCell->mParent;
+        }
+
+        while (mc.mRightViewCell->mParent)
+        {
+                mc.mRightViewCell = mc.mRightViewCell->mParent;
+        }
+
+        EvalMergeCost(mc);
+}
+
+
+void ViewCellsTree::EvalMergeCost(MergeCandidate &mc) const
+{
+        //-- compute pvs difference
+        const int newPvs = 
+                ComputeMergedPvsSize(mc.mLeftViewCell->GetPvs(), 
+                                                         mc.mRightViewCell->GetPvs());
+                        
+        const float newPenalty = 
+                EvalPvsPenalty(newPvs,
+                                           mViewCellsManager->GetMinPvsSize(),
+                                           mViewCellsManager->GetMaxPvsSize());
+
+        ViewCell *vc1 = mc.mLeftViewCell;
+        ViewCell *vc2 = mc.mRightViewCell;
+
+        //-- compute ratio of old cost
+        //   (i.e., added size of left and right view cell times pvs size)
+        //   to new rendering cost (i.e, size of merged view cell times pvs size)
+        const float oldCost = GetRenderCost(vc1) + GetRenderCost(vc2);
+
+    const float newCost = mUseAreaForPvs ? 
+                (float)newPenalty * (vc1->GetArea() + vc2->GetArea()) :
+                (float)newPenalty * (vc1->GetVolume() + vc2->GetVolume());
+
+
+        // strong penalty if pvs size too large
+        if (0 && (newPvs > mViewCellsManager->GetMaxPvsSize()))
+        {
+                mc.mRenderCost = 1e20f;
+        }
+        else
+        {
+                mc.mRenderCost = (newCost - oldCost) / 
+                        mViewCellsManager->GetViewSpaceBox().GetVolume();
+        }       
+        
+
+        //-- merge cost also takes deviation into account
+        float newDev, oldDev;
+
+        if (1)
+                newDev = fabs(mAvgRenderCost - newPenalty) / (float)mNumViewCells;
+        else
+                newDev = fabs(mExpectedCost - newCost) / (float)mNumViewCells;
+        
+        oldDev = GetDeviation(vc1) + GetDeviation(vc2);
+
+        // compute deviation increase
+        mc.mDeviationIncr = newDev - oldDev;
+        
+        //Debug << "render cost: " << mc.mRenderCost * mRenderCostWeight << endl;
+        //Debug << "standard deviation: " << mc.mDeviationIncr * mRenderCostWeight << endl;
+}
+
+
+void ViewCellsTree::CompressViewCellsPvs()
+{
+        stack<ViewCell *> tstack;
+
+
+}
+
+
+void  ViewCellsTree::CollectBestViewCellSet(ViewCellContainer &viewCells, const int numViewCells)
+{
+        TraversalQueue tqueue;
+
+        while (!tqueue.empty())
+        {
+                ViewCell *vc = tqueue.top();
+
+                tqueue.pop();
+        }
+}
+
+
+/**************************************************************************/
+/*                     MergeCandidate implementation                      */
+/**************************************************************************/
+
+
+MergeCandidate::MergeCandidate(ViewCell *l, ViewCell *r):
+mRenderCost(0),
+mDeviationIncr(0),
+mLeftViewCell(l),
+mRightViewCell(r)
+{
+        //EvalMergeCost();
+}
+
+
+void MergeCandidate::SetRightViewCell(ViewCell *v)
+{
+        mRightViewCell = v;
+}
+
+
+void MergeCandidate::SetLeftViewCell(ViewCell *v)
+{
+        mLeftViewCell = v;
+}
+
+
+ViewCell *MergeCandidate::GetRightViewCell() const
+{
+        return mRightViewCell;
+}
+
+
+ViewCell *MergeCandidate::GetLeftViewCell() const
+{
+        return mLeftViewCell;
+}
+
+
+ViewCell *MergeCandidate::GetInitialRightViewCell() const
+{
+        return mInitialRightViewCell;
+}
+
+
+ViewCell *MergeCandidate::GetInitialLeftViewCell() const
+{
+        return mInitialLeftViewCell;
+}
+
+
+bool MergeCandidate::IsValid() const
+{
+        return !(mLeftViewCell->mParent && mRightViewCell->mParent);
+}
+
+
+float MergeCandidate::GetRenderCost() const
+{
+        return mRenderCost;
+}
+
+
+float MergeCandidate::GetDeviationIncr() const
+{
+        return mDeviationIncr;
+}
+
+
+float MergeCandidate::GetMergeCost() const
+{
+        return mRenderCost * sRenderCostWeight + 
+                   mDeviationIncr * (1.0f - sRenderCostWeight);
+}
+
+
+/************************************************************************/
+/*                    MergeStatistics implementation                    */
+/************************************************************************/
+
+
+void MergeStatistics::Print(ostream &app) const
+{
+        app << "===== Merge statistics ===============\n";
+
+        app << setprecision(4);
+
+        app << "#N_CTIME ( Overall time [s] )\n" << Time() << " \n";
+
+        app << "#N_CCTIME ( Collect candidates time [s] )\n" << collectTime * 1e-3f << " \n";
+
+        app << "#N_MTIME ( Merge time [s] )\n" << mergeTime * 1e-3f << " \n";
+
+        app << "#N_NODES ( Number of nodes before merge )\n" << nodes << "\n";
+
+        app << "#N_CANDIDATES ( Number of merge candidates )\n" << candidates << "\n";
+
+        app << "#N_MERGEDSIBLINGS ( Number of merged siblings )\n" << siblings << "\n";
+
+        app << "#OVERALLCOST ( overall merge cost )\n" << overallCost << "\n";
+
+        app << "#N_MERGEDNODES ( Number of merged nodes )\n" << merged << "\n";
+
+        app << "#MAX_TREEDIST ( Maximal distance in tree of merged leaves )\n" << maxTreeDist << "\n";
+
+        app << "#AVG_TREEDIST ( Average distance in tree of merged leaves )\n" << AvgTreeDist() << "\n";
+
+        app << "#EXPECTEDCOST ( expected render cost )\n" << expectedRenderCost << "\n";
+
+        app << "#DEVIATION ( deviation )\n" << deviation << "\n";
+
+        app << "#HEURISTICS ( heuristics )\n" << heuristics << "\n";
+        
+
+        app << "===== END OF BspTree statistics ==========\n";
+}

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCell.h

@@ -16 +16 @@
 class VspKdLeaf;
 class KdLeaf;
+class ViewCellInterior;
+class MergeCandidate;
+class ViewCellsManager;
 
 /** Statistics for a view cell partition.
@@ -78 +81 @@
 };
 
+
 /**
         View cell with an optional mesh representation
 */
+
+
 class ViewCell: public MeshInstance
 {
@@ -93 +99 @@
         */
         virtual ~ViewCell() {}
+
         /** Returns Pvs.
         */
@@ -100 +107 @@
         int Type() const;
 
+        void SetParent(ViewCellInterior *parent);
+
         /** Adds a passing ray to the passing ray container.
         */
@@ -124 +133 @@
         virtual void UpdateViewCellsStats(ViewCellsStatistics &vcStat);
 
-        /// Ray set description of the rays passing through this node.
-        PassingRaySet mPassingRays;
+        /** if this view cell is the root of a view cell hierarchy
+        */
+        bool IsRoot() const;
+
+        /** Returns parent view cell.
+        */
+        ViewCellInterior *GetParent() const;
+
+        
+        /** Sets the mesh for this view cell.
+        */
+        void SetMesh(Mesh *mesh);
+
+        void SetValid(const bool valid);
+        bool GetValid() const;
+
+
+
+
+        /// parent view cell in the view cell hierarchy
+        ViewCellInterior *mParent;
 
         /// Rays piercing this view cell.
         RayContainer mPiercingRays;
 
-        /** Sets the mesh for this view cell.
-        */
-        void SetMesh(Mesh *mesh);
-
-        void SetValid(const bool valid);
-        bool GetValid() const;
+
+        /** if this is a view cell correspending to a leaf in a hierarchy.
+        */
+        virtual bool IsLeaf() const = 0;
 
   static bool SmallerPvs(const ViewCell *a,
@@ -142 +168 @@
   }
 
+
+        void SetTimeStamp(const int timeStamp);
+        int GetTimeStamp() const;
+        static void NewMail(const int reserve = 1) {
+                sMailId += sReservedMailboxes;
+                sReservedMailboxes = reserve;
+        }
+        void Mail() { mMailbox = sMailId; }
+        bool Mailed() const { return mMailbox == sMailId; }
+
+        void Mail(const int mailbox) { mMailbox = sMailId + mailbox; }
+        bool Mailed(const int mailbox) const { return mMailbox == sMailId + mailbox; }
+
+        int IncMail() { return ++mMailbox - sMailId; }
+
+
+                                                 
+        // last mail id -> warning not thread safe!
+        // both mailId and mailbox should be unique for each thread!!!
+        static int sMailId;
+        static int sReservedMailboxes;
+        
+
 protected:
 
@@ -150 +199 @@
         float mArea;
 
+        int mTimeStamp;
 
         bool mValid;
+};
+
+
+class ViewCellInterior: public ViewCell
+{
+public:
+        ViewCellInterior();
+        ~ViewCellInterior();
+
+        ViewCellInterior(Mesh *mesh);
+        
+
+        /** Sets pointer from parent to child and vice versa.
+        */
+        void SetupChildLink(ViewCell *l);
+        bool IsLeaf() const;
+
+        ViewCellContainer mChildren;
+
 };
 
@@ -158 +227 @@
 */
 template<typename T>
-class HierarchyViewCell: public ViewCell
+class ViewCellLeaf: public ViewCell
 {
 public:
-        HierarchyViewCell<T>(): mLeaves(0) {}
-        HierarchyViewCell<T>(Mesh *mesh):
-                ViewCell(mesh), mLeaves(0) {}
+
+        ViewCellLeaf<T>(): mLeaf(NULL) {}
+        ViewCellLeaf<T>(Mesh *mesh):
+                ViewCell(mesh), mLeaf(NULL) {}
 
         void UpdateViewCellsStats(ViewCellsStatistics &vcStat)
@@ -169 +239 @@
                 ViewCell::UpdateViewCellsStats(vcStat);
 
-                if ((int)mLeaves.size() > vcStat.maxLeaves)
-                        vcStat.maxLeaves = (int)mLeaves.size();
-                vcStat.leaves += (int)mLeaves.size();
-        }
-
-        /// Leaves of the hierarchy which are part of this view cell.
-        std::vector<T> mLeaves;
-};
-
-
-typedef HierarchyViewCell<BspLeaf *> BspViewCell;
-typedef HierarchyViewCell<KdLeaf *> KdViewCell;
-typedef HierarchyViewCell<VspKdLeaf *> VspKdViewCell;
-
+                //if ((int)mLeaves.size() > vcStat.maxLeaves)
+                //      vcStat.maxLeaves = (int)mLeaves.size();
+                //vcStat.leaves += (int)mLeaves.size();
+        }
+
+        bool IsLeaf() const
+        {
+                return true;
+        }
+
+        /// Leaf of some hierarchy which is part of this view cell.
+        T mLeaf;
+};
+
+
+typedef ViewCellLeaf<BspLeaf *> BspViewCell;
+typedef ViewCellLeaf<KdLeaf *> KdViewCell;
+typedef ViewCellLeaf<VspKdLeaf *> VspKdViewCell;
+
+
+
+class ViewCellsTree
+{
+public:
+        ViewCellsTree(ViewCellsManager *vcm);
+        ~ViewCellsTree();
+
+        /** Returns number of leaves this view cell consists of.
+        */
+        int GetSize(ViewCell *vc) const;
+
+        /** Collects leaves corresponding to a view cell.
+        */
+        void CollectLeaves(ViewCell *vc, ViewCellContainer &leaves) const;
+
+        /** Merges view cells according to some cost heuristics.
+        */
+        int ConstructMergeTree(const VssRayContainer &rays, const ObjectContainer &objects);
+        
+        /** Refines view cells using shuffling, i.e., border leaves 
+                of two view cells are exchanged if the resulting view cells
+                are tested to be "better" than the old ones.
+                @returns number of refined view cells
+        */
+        int RefineViewCells(const VssRayContainer &rays, const ObjectContainer &objects);
+
+        /** Compresses the pvs of the view cells.
+        */
+        void CompressViewCellsPvs();
+
+        /** Returns optimal set of view cells for a given number of view cells.
+        */
+        void CollectBestViewCellSet(ViewCellContainer &viewCells, const int numViewCells);
+
+protected:
+
+
+        //////////////////////////////////////////////////////////////
+        //                 merge options                            //
+        //////////////////////////////////////////////////////////////
+        
+
+        /** Returns cost of this leaf according to current heuristics.
+        */
+        float GetCostHeuristics(ViewCell *vc) const;
+
+        /** Returns cost of leaf.
+        */
+        float GetRenderCost(ViewCell *vc) const;
+
+        /** Evaluates the merge cost of this merge candidate pair.
+        */
+        void EvalMergeCost(MergeCandidate &mc) const;
+
+        /** Variance of leaf.
+        */
+        float GetVariance(ViewCell *vc) const;
+
+        /** Standard deviation of leaf.
+        */
+        float GetDeviation(ViewCell *vc) const;
+
+        /** Recalculates this merge candidate and sets valid.
+        */
+        void SetMergeCandidateValid(MergeCandidate &mc) const;
+
+        /** Merge view cells of leaves l1 and l2.
+                @returns difference in pvs size
+        */
+        ViewCellInterior *MergeViewCells(ViewCell *l, ViewCell *r, int &pvsDiff); //const;
+
+        /** Shuffles, i.e. takes border leaf from view cell 1 and adds it 
+                to view cell 2.
+        */
+        void ShuffleLeaf(ViewCell *leaf, ViewCell *vc1, ViewCell *vc2) const;   
+                
+        /** Shuffles the leaves, i.e., tests if exchanging
+                the leaves helps in improving the view cells.
+        */
+        bool ShuffleLeaves(ViewCell *l, ViewCell *r) const;
+
+        /** Calculates cost for merge of view cell 1 and 2.
+        */
+        float EvalShuffleCost(ViewCell *leaf, ViewCell *vc1, ViewCell *vc2) const;
+
+        /** Exports a snapshot of the merged view cells to disc.
+        */
+        void ExportMergedViewCells(ViewCellContainer &viewCells, 
+                                                           const ObjectContainer &objects,
+                                                           const int numNewViewCells);
+
+
+
+        /** merge queue must be reset after some time because expected value
+                may not be valid.
+        */
+        void ResetMergeQueue();
+
+        /** Updates the current top level of view cells.
+        */
+        int UpdateMergedViewCells(ViewCellContainer &viewCells);
+
+
+
+        ViewCellsManager *mViewCellsManager;
+        ViewCell *mRoot;
+
+        /// if merge visualization should be shown
+        bool mExportMergedViewCells;
+
+        
+                
+        ViewCellContainer mInactiveViewCells;
+        ViewCellContainer mActiveViewCells;
+
+        /// weights between variance and render cost increase (must be between zero and one)
+        float mRenderCostWeight;
+
+        /// overall cost used to normalize cost ratio
+        float mOverallCost;
+        float mExpectedCost;
+    float mDeviation;
+        float mAvgRenderCost;
+
+        int mUseAreaForPvs;
+
+        int mNumViewCells;
+
+        /// minimal number of view cells
+        int mMergeMinViewCells;
+        /// maximal cost ratio for the merge
+        float mMergeMaxCostRatio;
+
+        ofstream mStats;
+
+        typedef priority_queue<MergeCandidate> MergeQueue;
+
+        MergeQueue mMergeQueue;
+
+        
+
+};
+
+
+/**
+        Candidate for leaf merging based on priority.
+*/
+class MergeCandidate
+{  
+        friend class ViewCellsTree;
+
+public:
+
+        MergeCandidate(ViewCell *l, ViewCell *r);
+
+        /** If this merge pair is still valid.
+        */
+        bool IsValid() const;
+
+        
+        friend bool operator<(const MergeCandidate &leafa, const MergeCandidate &leafb)
+        {
+                return leafb.GetMergeCost() < leafa.GetMergeCost();
+        }
+
+        void SetLeftViewCell(ViewCell *l);
+        void SetRightViewCell(ViewCell *l);
+
+        ViewCell *GetLeftViewCell() const;
+        ViewCell *GetRightViewCell() const;
+
+        ViewCell *GetInitialLeftViewCell() const;
+        ViewCell *GetInitialRightViewCell() const;
+
+        /** Returns the increase of the standard deviation of this merge candidate.
+        */
+        float GetDeviationIncr() const;
+
+        /** Merge cost of this candidate pair.
+        */
+        float GetMergeCost() const;
+
+        /** Render cost of this candidate.
+        */
+        float GetRenderCost() const;
+        
+        static float sRenderCostWeight;
+
+protected:
+
+        /// render cost increase by this merge
+        float mRenderCost;
+        /// increase / decrease of standard deviation
+        float mDeviationIncr;
+
+        ViewCell *mLeftViewCell;
+        ViewCell *mRightViewCell;
+
+        ViewCell *mInitialLeftViewCell;
+        ViewCell *mInitialRightViewCell;
+};
+
+
+class MergeStatistics: public StatisticsBase
+{
+public:
+        
+        int merged;
+        int siblings;
+        int candidates;
+        int nodes;
+
+        int accTreeDist;
+        int maxTreeDist;
+        
+        Real collectTime;
+        Real mergeTime;
+
+        Real overallCost;
+
+        Real expectedRenderCost;
+        Real deviation;
+        Real heuristics;
+
+        // Constructor
+        MergeStatistics() 
+        {
+                Reset();
+        }
+        
+        double AvgTreeDist() const {return (double)accTreeDist / (double)merged;}; 
+
+        void Reset() 
+        {
+                nodes = 0;
+                merged = 0;
+                siblings = 0;
+                candidates = 0;
+        
+                accTreeDist = 0;
+                maxTreeDist = 0;
+
+                collectTime = 0;
+                mergeTime = 0;
+                overallCost = 0;
+
+                expectedRenderCost = 0;
+                deviation = 0;
+                heuristics = 0;
+
+        }
+
+        void Print(ostream &app) const;
+
+        friend ostream &operator<<(ostream &s, const MergeStatistics &stat) 
+        {
+                stat.Print(s);
+                return s;
+        } 
+};
 
 #endif

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp

@@ -208 +208 @@
 
 
-/******************************************************************/
-/*                    class BspTree implementation                */
-/******************************************************************/
+/*********************************************************************/
+/*                       class BspTree implementation                */
+/*********************************************************************/
 
 BspTree::BspTree():  
@@ -840 +840 @@
                 
                 leaf->SetViewCell(viewCell);
-                viewCell->mLeaves.push_back(leaf);
+                viewCell->mLeaf = leaf;
 
                 //-- add pvs
@@ -2208 +2208 @@
 void BspTree::ConstructGeometry(BspViewCell *vc, BspNodeGeometry &geom) const
 {
-        vector<BspLeaf *> leaves = vc->mLeaves;
+        // TODO
+/*      vector<BspLeaf *> leaves = vc->mLeaves;
 
         vector<BspLeaf *>::const_iterator it, it_end = leaves.end();
 
         for (it = leaves.begin(); it != it_end; ++ it)
-                ConstructGeometry(*it, geom);
+                ConstructGeometry(*it, geom);*/
 }
 

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellsManager.cpp

@@ -33 +33 @@
         mViewSpaceBox.Initialize();
         ParseEnvironment();
+
+        mViewCellsTree = new ViewCellsTree(this);
 }
 
@@ -53 +55 @@
 
         environment->GetBoolValue("ViewCells.exportToFile", mExportViewCells);
+
+        environment->GetBoolValue("ViewCells.PostProcess.useRaysForMerge", mUseRaysForMerge);
 
         mMinPvsSize = emptyViewCells ? 1 : 0;
@@ -75 +79 @@
 {
         DEL_PTR(mRenderer);
-        CLEAR_CONTAINER(mViewCells);
+        //CLEAR_CONTAINER(mViewCells);
+        DEL_PTR(mViewCellsTree);
+
         CLEAR_CONTAINER(mMeshContainer);
 }
@@ -302 +308 @@
 float ViewCellsManager::GetViewSpaceVolume()
 {
-        return mViewSpaceBox.GetVolume()*(2.0f*sqr(M_PI));
+        return mViewSpaceBox.GetVolume()*(2.0f*sqr((float)M_PI));
 }
 
@@ -356 +362 @@
 
 
-void ViewCellsManager::EvaluateRenderStatistics(float &totalRenderCost, 
+void ViewCellsManager::EvaluateRenderStatistics(float &totalRenderCost,
                                                                                                 float &expectedRenderCost, 
-                                                                                                float &variance)
+                                                                                                float &deviation,
+                                                                                                float &variance,
+                                                                                                int &totalPvs,
+                                                                                                float &avgRenderCost)
 {
         ViewCellContainer::const_iterator it, it_end = mViewCells.end();
 
+
         //-- compute expected value
 
         totalRenderCost = 0;
+        totalPvs = 0;
 
         for (it = mViewCells.begin(); it != it_end; ++ it)
         {
                 ViewCell *vc = *it;
-
                 totalRenderCost += vc->GetPvs().GetSize() * vc->GetVolume();
-        }
-
+                totalPvs += (int)vc->GetPvs().GetSize();
+        }
+
+        // normalize with view space box
+        totalRenderCost /= mViewSpaceBox.GetVolume();
         expectedRenderCost = totalRenderCost / (float)mViewCells.size();
-
-
-        //-- compute variance
-        
+        avgRenderCost = totalPvs / (float)mViewCells.size();
+
+
+        //-- compute standard defiation
         variance = 0;
+        deviation = 0;
 
         for (it = mViewCells.begin(); it != it_end; ++ it)
@@ -385 +399 @@
 
                 float renderCost = vc->GetPvs().GetSize() * vc->GetVolume();
-
-                const float var = (expectedRenderCost - renderCost) * (expectedRenderCost - renderCost);
-
-                variance += var;
-        }
-        
+                float dev;
+
+                if (1)
+                        dev = fabs(avgRenderCost - (float)vc->GetPvs().GetSize());
+                else
+                        dev = fabs(expectedRenderCost - renderCost);
+
+                deviation += dev;
+                variance += dev * dev;
+        }
+
         variance /= (float)mViewCells.size();
+        deviation /= (float)mViewCells.size();
 }
 
@@ -493 +513 @@
 
 
-ViewCell *ViewCellsManager::MergeViewCells(ViewCell &front, ViewCell &back) const
-{
-        // generate merged view cell
-        ViewCell *vc = GenerateViewCell();
+ViewCellInterior *ViewCellsManager::MergeViewCells(ViewCell &left, ViewCell &right) const
+{
+        // generate parent view cell
+        ViewCellInterior *vc = new ViewCellInterior();//GenerateViewCell();
 
         // merge pvs
-        vc->GetPvs().Merge(front.GetPvs(), back.GetPvs());
+        vc->GetPvs().Merge(left.GetPvs(), right.GetPvs());
 
         //-- merge ray sets
         if (0)
         {
-                stable_sort(front.mPiercingRays.begin(), front.mPiercingRays.end());
-                stable_sort(back.mPiercingRays.begin(), back.mPiercingRays.end());
-
-                std::merge(front.mPiercingRays.begin(), front.mPiercingRays.end(),
-                                   back.mPiercingRays.begin(), back.mPiercingRays.end(),
+                stable_sort(left.mPiercingRays.begin(), left.mPiercingRays.end());
+                stable_sort(right.mPiercingRays.begin(), right.mPiercingRays.end());
+
+                std::merge(left.mPiercingRays.begin(), left.mPiercingRays.end(),
+                                   right.mPiercingRays.begin(), right.mPiercingRays.end(),
                                    vc->mPiercingRays.begin());
         }
 
+
+        vc->SetupChildLink(&left);
+        vc->SetupChildLink(&right);
+
+
         return vc;
 }
@@ -522 +547 @@
 
 
-ViewCell *ViewCellsManager::GenerateViewCell(Mesh *mesh) const
-{
-        return new ViewCell(mesh);
+ViewCellsTree *ViewCellsManager::GetViewCellsTree()
+{
+        return mViewCellsTree;
 }
 
@@ -814 +839 @@
                 {
                         ExportColor(exporter, *it);
-                        ExportVcGeometry(exporter, *it);
+                        ExportViewCellGeometry(exporter, *it);
                 }
         }
@@ -1186 +1211 @@
 
                 Debug << i << ": pvs size=" << (int)vc->GetPvs().GetSize()
-                          << ", piercing rays=" << (int)vcRays.size()
-                          << ", leaves=" << (int)vc->mLeaves.size() << endl;
+                          << ", piercing rays=" << (int)vcRays.size() << endl;
+                         // << ", leaves=" << (int)vc->mLeaves.size() << endl;
 
 
                 // export rays piercing this view cell
-#if 0
                 exporter->ExportRays(vcRays, RgbColor(0, 1, 0));
-#else
-                vector<BspLeaf *>::const_iterator lit, lit_end = vc->mLeaves.end();
-                for (lit = vc->mLeaves.begin(); lit != lit_end; ++ lit)
-                        exporter->ExportRays((*lit)->mVssRays);
-#endif
+
                 m.mDiffuseColor = RgbColor(1, 0, 0);
                 exporter->SetForcedMaterial(m);
@@ -1249 +1269 @@
                 {
                         BspViewCell *vc = dynamic_cast<BspViewCell *>(*vit);
-                        ray->intersections.push_back(BspIntersection(0, vc->mLeaves[0]));
+                        ray->intersections.push_back(BspIntersection(0, vc->mLeaf));
                 }
 
@@ -1278 +1298 @@
         case 2: // merges
                 {
-                        BspViewCell *bspVc = dynamic_cast<BspViewCell *>(vc);
-
-                        importance = (float)bspVc->mLeaves.size() /
+                        importance = (float)mViewCellsTree->GetSize(vc) /
                                 (float)mViewCellsStats.maxLeaves;
                 }
@@ -1301 +1319 @@
 }
 
-void BspViewCellsManager::ExportVcGeometry(Exporter *exporter,
+void BspViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
                                                                                  ViewCell *vc) const
 {
@@ -1332 +1350 @@
   return mBspTree->GetViewCell(point);
 }
+
+
+void BspViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays, vector<MergeCandidate> &candidates)
+{
+        // TODO
+}
+
 
 /**********************************************************************/
@@ -1585 +1610 @@
 }
 
-
-void KdViewCellsManager::ExportVcGeometry(Exporter *exporter,
-                                                                                  ViewCell *vc) const
-{
-        KdViewCell *kdVc = dynamic_cast<KdViewCell *>(vc);
-        vector<KdLeaf *>::const_iterator it, it_end = kdVc->mLeaves.end();
-
-        for (it = kdVc->mLeaves.begin(); it != it_end; ++ it)
-                exporter->ExportBox(mKdTree->GetBox(*it));
+ViewCell *KdViewCellsManager::GenerateViewCell(Mesh *mesh) const
+{
+        return new KdViewCell(mesh);
+}
+
+
+void KdViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
+                                                                                                ViewCell *vc) 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));
+        }
 }
 
@@ -1625 +1661 @@
         // TODO
 }
+
+
+
+void KdViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays, 
+                                                                                                vector<MergeCandidate> &candidates)
+{
+        // TODO
+}
+
 
 /**********************************************************************/
@@ -1798 +1843 @@
                 exporter->SetWireframe();
 
-                ExportVcGeometry(exporter, vc);
+                ExportViewCellGeometry(exporter, vc);
 
                 //-- export stored rays
+                
                 if (mExportRays)
                 {
-                        vector<VspKdLeaf *>::const_iterator it,
-                                it_end = vc->mLeaves.end();
-
-                        for (it = vc->mLeaves.begin(); it != it_end; ++ it)
+                        ViewCellContainer leaves;
+                        mViewCellsTree->CollectLeaves(vc, leaves);
+
+                        ViewCellContainer::const_iterator it,
+                                it_end = leaves.end();
+
+                        for (it = leaves.begin(); it != it_end; ++ it)
                         {
-                                VspKdLeaf *leaf = *it;
+                                VspKdViewCell *vspKdVc = dynamic_cast<VspKdViewCell *>(*it);
+                                VspKdLeaf *leaf = vspKdVc->mLeaf;
                                 AxisAlignedBox3 box = mVspKdTree->GetBBox(leaf);
 
@@ -1834 +1884 @@
                         }
                 }
-
+        
                 //-- output PVS of view cell
                 m.mDiffuseColor = RgbColor(1, 0, 0);
@@ -1927 +1977 @@
                 }
                 break;
-        case 2: // merges
-                {
-            VspKdViewCell *vspKdVc = dynamic_cast<VspKdViewCell *>(vc);
-
-                        importance = (float)vspKdVc->mLeaves.size() /
+        case 2: // merged leaves
+                {
+                int lSize = mViewCellsTree->GetSize(vc);
+                        importance = (float)lSize /
                                 (float)mViewCellsStats.maxLeaves;
                 }
@@ -1954 +2003 @@
 
 
-void VspKdViewCellsManager::ExportVcGeometry(Exporter *exporter,
+void VspKdViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
                                                                                    ViewCell *vc) const
 {
         VspKdViewCell *kdVc = dynamic_cast<VspKdViewCell *>(vc);
-        vector<VspKdLeaf *>::const_iterator it, it_end = kdVc->mLeaves.end();
 
         Mesh m;
-        for (it = kdVc->mLeaves.begin(); it != it_end; ++ it)
-        {
-                mVspKdTree->GetBBox(*it).AddBoxToMesh(&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);
         }
 
@@ -1975 +2030 @@
 }
 
+
+void VspKdViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays, vector<MergeCandidate> &candidates)
+{
+        // TODO
+}
 
 
@@ -2131 +2191 @@
         long startTime = GetTime();
 
+        
         // TODO: should be done BEFORE the ray casting
-        merged = mVspBspTree->MergeViewCells(rays, objects);
+        merged = mViewCellsTree->ConstructMergeTree(rays, objects);
 
         //-- stats and visualizations
@@ -2194 +2255 @@
 
         // refining the merged view cells
-        const int refined = mVspBspTree->RefineViewCells(rays, objects);
+        const int refined = mViewCellsTree->RefineViewCells(rays, objects);
 
         //-- stats and visualizations
@@ -2234 +2295 @@
         mViewCellsStats.Reset();
         EvaluateViewCellsStats();
+
         // has to be recomputed
         mTotalAreaValid = false;
@@ -2254 +2316 @@
         //-- merge the individual view cells
         MergeViewCells(postProcessRays, objects);
+
         //-- refines the merged view cells
         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;
+        }
+
 
         //-- export shuffled view cells
@@ -2293 +2373 @@
                                 vm.mDiffuseColor.b -= 0.45f;
 
-                                vector<BspLeaf *>::const_iterator lit, lit_end = vc->mLeaves.end();
-
-                                for (lit = vc->mLeaves.begin(); lit != lit_end; ++ lit)
+
+                                ViewCellContainer leaves;
+                                mViewCellsTree->CollectLeaves(vc, leaves);
+
+                                ViewCellContainer::const_iterator lit, lit_end = leaves.end();
+
+                                for (lit = leaves.begin(); lit != lit_end; ++ lit)
                                 {
-                                        BspLeaf *leaf = *lit;
+                                        BspLeaf *leaf = dynamic_cast<BspViewCell *>(*lit)->mLeaf;
 
                                         if (leaf->Mailed())
@@ -2391 +2475 @@
         if (1) // export view cells
         {
-                cout << "exporting view cells after post process ... ";
                 Exporter *exporter = Exporter::GetExporter("final_view_cells.x3d");
 
                 if (exporter)
                 {
+                        cout << "exporting view cells after post process ... ";
+
                         if (1)
                         {
@@ -2416 +2501 @@
                         ExportViewCellsForViz(exporter);
                         delete exporter;
+                        cout << "finished" << endl;
                 }
         }
@@ -2446 +2532 @@
                                 BspViewCell *vc = dynamic_cast<BspViewCell *>(*vit);
 
-                                vector<BspLeaf *>::const_iterator lit, lit_end = vc->mLeaves.end();
-
-                                for (lit = vc->mLeaves.begin(); lit != lit_end; ++ lit)
+                                ViewCellContainer leaves;
+                                mViewCellsTree->CollectLeaves(vc, leaves);
+
+                                ViewCellContainer::const_iterator lit, lit_end = leaves.end();
+
+                                for (lit = leaves.begin(); lit != lit_end; ++ lit)
                                 {
-                                        BspLeaf *leaf = *lit;
+                                        BspLeaf *leaf = dynamic_cast<BspViewCell *>(*lit)->mLeaf;
 
                                         Material m; 
@@ -2573 +2662 @@
                                 {
                                         BspViewCell *bspVc = dynamic_cast<BspViewCell *>(ray->mViewCells[j]);
-                                        BspLeaf *leaf = bspVc->mLeaves[0];
+                                        BspLeaf *leaf = bspVc->mLeaf;
                                         if (vc == bspVc)
                                                 vcRays.push_back(ray);
@@ -2589 +2678 @@
                 exporter->SetForcedMaterial(m);
 
-                ExportVcGeometry(exporter, vc);
+                ExportViewCellGeometry(exporter, vc);
 
 
                 Debug << i << ": pvs size=" << (int)vc->GetPvs().GetSize()
-                          << ", piercing rays=" << (int)vcRays.size()
-                          << ", leaves=" << (int)vc->mLeaves.size() << endl;
+                          << ", piercing rays=" << (int)vcRays.size() << endl;
+                        //  << ", leaves=" << (int)vc->mLeaves.size() << endl;
 
                 
@@ -2604 +2693 @@
                 else
                 {
-                        vector<BspLeaf *>::const_iterator lit, lit_end = vc->mLeaves.end();
-
-                        for (lit = vc->mLeaves.begin(); lit != lit_end; ++ lit)
-                                exporter->ExportRays((*lit)->mVssRays);
+
+                        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);
+                        }
                 }
 
@@ -2686 +2782 @@
         case 2: // merges
                 {
-            BspViewCell *bspVc = dynamic_cast<BspViewCell *>(vc);
-
-                        importance = (float)bspVc->mLeaves.size() /
-                                (float)mViewCellsStats.maxLeaves;
+            int lSize = mViewCellsTree->GetSize(vc);
+        
+                        importance = (float)lSize / (float)mViewCellsStats.maxLeaves;
                 }
                 break;
@@ -2713 +2808 @@
 
 
-void VspBspViewCellsManager::ExportVcGeometry(Exporter *exporter,
+void VspBspViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
                                                                                           ViewCell *vc) const
 {
@@ -2731 +2826 @@
 int VspBspViewCellsManager::GetMaxTreeDiff(ViewCell *vc) const
 {
-        BspViewCell *bspVc = dynamic_cast<BspViewCell *>(vc);
+        ViewCellContainer leaves;
+        mViewCellsTree->CollectLeaves(vc, leaves);
+
 
         int maxDist = 0;
+        
         // compute max height difference
-        for (int i = 0; i < (int)bspVc->mLeaves.size(); ++ i)
-                for (int j = 0; j < (int)bspVc->mLeaves.size(); ++ j)
-        {
-                BspLeaf *leaf = bspVc->mLeaves[i];
+        for (int i = 0; i < (int)leaves.size(); ++ i)
+                for (int j = 0; j < (int)leaves.size(); ++ j)
+        {
+                BspLeaf *leaf = dynamic_cast<BspViewCell *>(leaves[i])->mLeaf;
 
                 if (i != j)
                 {
-                        BspLeaf *leaf2 = bspVc->mLeaves[j];
+                        BspLeaf *leaf2 =dynamic_cast<BspViewCell *>(leaves[j])->mLeaf;
                         int dist = mVspBspTree->TreeDistance(leaf, leaf2);
                         if (dist > maxDist)
@@ -2748 +2846 @@
                 }
         }
+
         return maxDist;
 }
@@ -2871 +2970 @@
         CreateMesh(vc);
 
-        vector<BspLeaf *>::const_iterator it, it_end = vc->mLeaves.end();
-
         float area = 0;
         float volume = 0;
 
-        for (it = vc->mLeaves.begin(); it != it_end; ++ it)
+        ViewCellContainer leaves;
+        mViewCellsTree->CollectLeaves(vc, leaves);
+
+        ViewCellContainer::const_iterator it, it_end = leaves.end();
+
+        for (it = leaves.begin(); it != it_end; ++ it)
         {
                 BspNodeGeometry geom;
-                BspLeaf *leaf = *it;
+                BspLeaf *leaf = dynamic_cast<BspViewCell *>(*it)->mLeaf;
                 mVspBspTree->ConstructGeometry(leaf, geom);
 
@@ -2898 +3000 @@
 
 
-//////////////////////////////////77
+
+void VspBspViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays, 
+                                                                                                        vector<MergeCandidate> &candidates)
+{       
+        cout << "collecting merge candidates ... " << endl;
+
+        if (mUseRaysForMerge)
+        {
+                mVspBspTree->CollectMergeCandidates(rays, candidates);
+        }
+        else
+        {
+                vector<BspLeaf *> leaves;
+                mVspBspTree->CollectLeaves(leaves);
+                mVspBspTree->CollectMergeCandidates(leaves, candidates);
+        }
+
+        cout << "fininshed collecting candidates" << endl;
+}
+
+
+
+//////////////////////////////////
 ViewCellsManager *ViewCellsManagerFactory::Create(const string mName)
 {
@@ -2904 +3028 @@
         return NULL;// new VspBspViewCellsManager();
 }
+

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellsManager.h

@@ -27 +27 @@
 class Beam;
 class Preprocessor;
+class ViewCellsTree;
+class MergeCandidate;
 
 struct BspRay;
@@ -133 +135 @@
                 @returns new view cell based on the merging.
         */
-        ViewCell *MergeViewCells(ViewCell &front, ViewCell &back) const;
+        ViewCellInterior *MergeViewCells(ViewCell &front, ViewCell &back) const;
         
         /** Generates view cell of type specified by this manager
         */
-        virtual ViewCell *GenerateViewCell(Mesh *mesh = NULL) const;
+        virtual ViewCell *GenerateViewCell(Mesh *mesh = NULL) const = 0;
 
         /** Adds a new view cell to the list of predefined view cells.
@@ -206 +208 @@
         virtual float GetRendercost(ViewCell *viewCell, float objRendercost) const = 0;
 
-        /** Returns vector of loaded / generated view cells.
+        /** Returns container of loaded / generated view cells.
         */
         ViewCellContainer &GetViewCells();
@@ -311 +313 @@
         /** Exports view cell geometry.
         */
-        virtual void ExportVcGeometry(Exporter *exporter, ViewCell *vc) const = 0;
+        virtual void ExportViewCellGeometry(Exporter *exporter, ViewCell *vc) const = 0;
 
         virtual void FinalizeViewCells(const bool createMesh);
@@ -325 +327 @@
         /** Evaluates statistics values on view cells.
         */
-        void EvaluateRenderStatistics(float &totalRenderCost, 
-                                                                  float &expectedRenderCost, 
-                                                                  float &variance);
+        void EvaluateRenderStatistics(float &totalRenderCost,
+                                                                  float &expectedRenderCost,
+                                                                  float &deviation,
+                                                                  float &variance,
+                                                                  int &totalPvs,
+                                                                  float &avgRenderCost);
+
+
+        /** Returns hierarchy of the view cells.
+        */
+        ViewCellsTree *GetViewCellsTree();
+
+        virtual void CollectMergeCandidates(const VssRayContainer &rays, vector<MergeCandidate> &candidates) = 0;
+
 
 protected:
@@ -392 +405 @@
         /// Loaded view cells
         ViewCellContainer mViewCells;
+
+        ViewCellsTree *mViewCellsTree;
 
         /// maximum number of samples taken for construction of the view cells
@@ -417 +432 @@
         bool mOnlyValidViewCells;
 
+        /// if rays should be used to collect merge candidates
+        bool mUseRaysForMerge;
+        
+
         //-- visualization options
         
@@ -472 +491 @@
         void CreateMesh(ViewCell *vc);
 
-        void ExportVcGeometry(Exporter *exporter, ViewCell *vc) const;
+        void ExportViewCellGeometry(Exporter *exporter, ViewCell *vc) const;
+        
+        void CollectMergeCandidates(const VssRayContainer &rays, vector<MergeCandidate> &candidates);
 
 protected:
@@ -529 +550 @@
         bool ViewCellsConstructed() const;
 
+        ViewCell *GenerateViewCell(Mesh *mesh) const;
 
         /** Prints out statistics of this approach.
@@ -540 +562 @@
         void CreateMesh(ViewCell *vc);
 
-        void ExportVcGeometry(Exporter *exporter, ViewCell *vc) const;
+        void ExportViewCellGeometry(Exporter *exporter, ViewCell *vc) const;
+
+        void CollectMergeCandidates(const VssRayContainer &rays, vector<MergeCandidate> &candidates);
 
 protected:
 
+        /** Collects view cells from a hierarchy.
+        */
         void CollectViewCells();
+
         KdNode *GetNodeForPvs(KdLeaf *leaf);
 
@@ -598 +625 @@
         void CreateMesh(ViewCell *vc);
 
-        void ExportVcGeometry(Exporter *exporter, ViewCell *vc) const;
+        void ExportViewCellGeometry(Exporter *exporter, ViewCell *vc) const;
+
+        void CollectMergeCandidates(const VssRayContainer &rays, vector<MergeCandidate> &candidates);
 
 protected:
@@ -664 +693 @@
         int CastBeam(Beam &beam);
 
-        void ExportVcGeometry(Exporter *exporter, ViewCell *vc) const;
+        void ExportViewCellGeometry(Exporter *exporter, ViewCell *vc) const;
 
         //float GetVolume(ViewCell *viewCell) const;
 
         void Finalize(ViewCell *viewCell, const bool createMesh);
+
+        void CollectMergeCandidates(const VssRayContainer &rays, vector<MergeCandidate> &candidates);
 
 protected:

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellsParser.cpp

@@ -356 +356 @@
         {
                 // TODO: get view cell with specified id
-                ViewCell dummyVc;
+                BspViewCell dummyVc;
                 dummyVc.SetId(viewCellId);
 
@@ -363 +363 @@
                         
                 BspViewCell *viewCell = dynamic_cast<BspViewCell *>(*vit);
+
                 if (viewCell->GetId() == viewCellId)
                 {

trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.cpp

@@ -25 +25 @@
 const float VspBspTree::sLeastRaySplitsTable[] = {0, 0, 1, 1, 0};
 /** Evaluates split plane classification with respect to the plane's
-        contribution for balanced rays.
+        contribution for  balanced rays.
 */
 const float VspBspTree::sBalancedRaysTable[] = {1, -1, 0, 0, 0};
 
-ViewCellsManager *BspMergeCandidate::sViewCellsManager = NULL;
-//int BspMergeCandidate::sMaxPvsSize = 0;
-//int BspMergeCandidate::sMinPvsSize = 0;
 
 int VspBspTree::sFrontId = 0;
@@ -37 +34 @@
 int VspBspTree::sFrontAndBackId = 0;
 
-float BspMergeCandidate::sOverallCost = 0;
-float BspMergeCandidate::sExpectedCost = 0;
-float BspMergeCandidate::sVariance = 0;
-float BspMergeCandidate::sRenderCostWeight = 0.5f;
-bool BspMergeCandidate::sUseArea = false;
-int BspMergeCandidate::sNumViewCells = 0;
-
-//int upperPvsLimit = 120;
-//int lowerPvsLimit = 5;
 
 
@@ -64 +52 @@
 
 
-// penalty for pvs durint merge
-inline float EvalPvsPenaltyForMerge(const int pvs, 
-                                                                        const int lower,
-                                                                        const int upper)
-{
-        // clamp to minmax values
-        if (pvs < lower)
-                return (float)lower;
-        if (pvs > upper)
-                return (float)upper;
-
-        return (float)pvs;
-}
 
 
@@ -90 +65 @@
 mViewCellsManager(NULL),
 mOutOfBoundsCell(NULL),
-mStoreRays(false)
+mStoreRays(false),
+mRenderCostWeight(0.5)
 {
         bool randomize = false;
@@ -126 +102 @@
         // if only the driving axis is used for axis aligned split
         environment->GetBoolValue("VspBspTree.splitUseOnlyDrivingAxis", mOnlyDrivingAxis);
-
-        //-- merge options
-        environment->GetIntValue("VspBspTree.PostProcess.minViewCells", mMergeMinViewCells);
-        environment->GetFloatValue("VspBspTree.PostProcess.maxCostRatio", mMergeMaxCostRatio);
-        environment->GetBoolValue("VspBspTree.PostProcess.useRaysForMerge", mUseRaysForMerge);
-
-
+        
         //-- termination criteria for axis aligned split
         environment->GetFloatValue("VspBspTree.Termination.AxisAligned.maxRayContribution", 
@@ -142 +112 @@
         environment->GetFloatValue("VspBspTree.maxStaticMemory", mMaxMemory);
 
-        environment->GetBoolValue("VspBspTree.Visualization.exportMergedViewCells", mExportMergedViewCells);
-        environment->GetBoolValue("VspBspTree.PostProcess.exportMergeStats", mExportMergeStats);
-        
-
-        mStats.open("bspStats.log");
+        environment->GetFloatValue("VspBspTree.Construction.renderCostWeight", mRenderCostWeight);
+
+
+
 
         //-- debug output
+
         Debug << "******* VSP BSP options ******** " << endl;
     Debug << "max depth: " << mTermMaxDepth << endl;
@@ -162 +132 @@
         Debug << "max plane candidates: " << mMaxRayCandidates << endl;
         Debug << "randomize: " << randomize << endl;
-        Debug << "minimum view cells: " << mMergeMinViewCells << endl;
+//      Debug << "minimum view cells: " << mMergeMinViewCells << endl;
         Debug << "using area for pvs: " << mUseAreaForPvs << endl;
+        Debug << "render cost weight: " << mRenderCostWeight << endl;
         Debug << "Split plane strategy: ";
 
@@ -195 +166 @@
         Debug << endl;
 }
+
 
 BspViewCell *VspBspTree::GetOutOfBoundsCell()
@@ -249 +221 @@
         return (int)mesh->mFaces.size();
 }
+
 
 int VspBspTree::AddToPolygonSoup(const ViewCellContainer &viewCells,
@@ -273 +246 @@
         return polysSize;
 }
+
 
 int VspBspTree::AddToPolygonSoup(const ObjectContainer &objects,
@@ -310 +284 @@
 }
 
+
 void VspBspTree::Construct(const VssRayContainer &sampleRays,
                                                    AxisAlignedBox3 *forcedBoundingBox)
@@ -366 +341 @@
         
         Debug << "maximal pvs (i.e., pvs still considered as valid) : " << mViewCellsManager->GetMaxPvsSize() << endl;
+
         //-- store rays
         for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
@@ -572 +548 @@
                 }
                 
-        viewCell->mLeaves.push_back(leaf);
+        viewCell->mLeaf = leaf;
 
                 if (mUseAreaForPvs)
@@ -589 +565 @@
         return newNode;
 }
-
-
 
 
@@ -752 +726 @@
 }
 
+
 void VspBspTree::SortSplitCandidates(const RayInfoContainer &rays, const int axis)
 {
@@ -780 +755 @@
         stable_sort(mSplitCandidates->begin(), mSplitCandidates->end());
 }
+
 
 float VspBspTree::BestCostRatioHeuristics(const RayInfoContainer &rays,
@@ -1035 +1011 @@
 
 
+bool VspBspTree::SelectPlane(Plane3 &bestPlane,
+                                                         BspLeaf *leaf,
+                                                         VspBspTraversalData &data,
+                                                         VspBspTraversalData &frontData,
+                                                         VspBspTraversalData &backData)
+{
+        // simplest strategy: just take next polygon
+        if (mSplitPlaneStrategy & RANDOM_POLYGON)
+        {
+        if (!data.mPolygons->empty())
+                {
+                        const int randIdx = 
+                                (int)RandomValue(0, (Real)((int)data.mPolygons->size() - 1));
+                        Polygon3 *nextPoly = (*data.mPolygons)[randIdx];
+
+                        bestPlane = nextPoly->GetSupportingPlane();
+                        return true;
+                }
+        }
+
+        //-- use heuristics to find appropriate plane
+
+        // intermediate plane
+        Plane3 plane;
+        float lowestCost = MAX_FLOAT;
+        
+        // decides if the first few splits should be only axisAligned
+        const bool onlyAxisAligned  = 
+                (mSplitPlaneStrategy & AXIS_ALIGNED) &&
+                ((int)data.mRays->size() > mTermMinRaysForAxisAligned) &&
+                ((int)data.GetAvgRayContribution() < mTermMaxRayContriForAxisAligned);
+        
+        const int limit = onlyAxisAligned ? 0 : 
+                Min((int)data.mPolygons->size(), mMaxPolyCandidates);
+
+        float candidateCost;
+
+        int maxIdx = (int)data.mPolygons->size();
+
+        for (int i = 0; i < limit; ++ i)
+        {
+                // the already taken candidates are stored behind maxIdx
+                // => assure that no index is taken twice
+                const int candidateIdx = (int)RandomValue(0, (Real)(-- maxIdx));
+                Polygon3 *poly = (*data.mPolygons)[candidateIdx];
+
+                // swap candidate to the end to avoid testing same plane
+                std::swap((*data.mPolygons)[maxIdx], (*data.mPolygons)[candidateIdx]);
+                //Polygon3 *poly = (*data.mPolygons)[(int)RandomValue(0, (int)polys.size() - 1)];
+
+                // evaluate current candidate
+                BspNodeGeometry fGeom, bGeom;
+                float fArea, bArea;
+                plane = poly->GetSupportingPlane();
+                candidateCost = EvalSplitPlaneCost(plane, data, fGeom, bGeom, fArea, bArea);
+                
+                if (candidateCost < lowestCost)
+                {
+                        bestPlane = plane;
+                        lowestCost = candidateCost;
+                }
+        }
+
+        //-- evaluate axis aligned splits
+        int axis;
+        BspNodeGeometry *fGeom, *bGeom;
+        float pFront, pBack;
+
+        candidateCost = SelectAxisAlignedPlane(plane, data, axis,
+                                                                                   &fGeom, &bGeom, 
+                                                                                   pFront, pBack,
+                                                                                   data.mIsKdNode);      
+
+        bool isAxisAlignedSplit = false;
+
+        if (candidateCost < lowestCost)
+        {       
+                bestPlane = plane;
+                lowestCost = candidateCost;
+
+                // assign already computed values
+                // we can do this because we always save the
+                // computed values from the axis aligned splits         
+                frontData.mGeometry = fGeom;
+                backData.mGeometry = bGeom;
+        
+                frontData.mProbability = pFront;
+                backData.mProbability = pBack;
+                
+                //! error also computed if cost ratio is missed
+                ++ mBspStats.splits[axis];
+                isAxisAlignedSplit = true;
+        }
+        else
+        {
+                DEL_PTR(fGeom);
+                DEL_PTR(bGeom);
+        }
+
+        frontData.mIsKdNode = backData.mIsKdNode = (data.mIsKdNode && isAxisAlignedSplit);
+
+#ifdef _DEBUG
+        Debug << "plane lowest cost: " << lowestCost << endl;
+#endif
+
+        // cost ratio miss
+        if (lowestCost > mTermMaxCostRatio)
+                return false;
+
+        return true;
+}
+
+
+Plane3 VspBspTree::ChooseCandidatePlane(const RayInfoContainer &rays) const
+{
+        const int candidateIdx = (int)RandomValue(0, (Real)((int)rays.size() - 1));
+
+        const Vector3 minPt = rays[candidateIdx].ExtrapOrigin();
+        const Vector3 maxPt = rays[candidateIdx].ExtrapTermination();
+
+        const Vector3 pt = (maxPt + minPt) * 0.5;
+        const Vector3 normal = Normalize(rays[candidateIdx].mRay->GetDir());
+
+        return Plane3(normal, pt);
+}
+
+
+Plane3 VspBspTree::ChooseCandidatePlane2(const RayInfoContainer &rays) const
+{
+        Vector3 pt[3];
+
+        int idx[3];
+        int cmaxT = 0;
+        int cminT = 0;
+        bool chooseMin = false;
+
+        for (int j = 0; j < 3; ++ j)
+        {
+                idx[j] = (int)RandomValue(0, (Real)((int)rays.size() * 2 - 1));
+
+                if (idx[j] >= (int)rays.size())
+                {
+                        idx[j] -= (int)rays.size();
+
+                        chooseMin = (cminT < 2);
+                }
+                else
+                        chooseMin = (cmaxT < 2);
+
+                RayInfo rayInf = rays[idx[j]];
+                pt[j] = chooseMin ? rayInf.ExtrapOrigin() : rayInf.ExtrapTermination();
+        }
+
+        return Plane3(pt[0], pt[1], pt[2]);
+}
+
+
+Plane3 VspBspTree::ChooseCandidatePlane3(const RayInfoContainer &rays) const
+{
+        Vector3 pt[3];
+
+        int idx1 = (int)RandomValue(0, (Real)((int)rays.size() - 1));
+        int idx2 = (int)RandomValue(0, (Real)((int)rays.size() - 1));
+
+        // check if rays different
+        if (idx1 == idx2)
+                idx2 = (idx2 + 1) % (int)rays.size();
+
+        const RayInfo ray1 = rays[idx1];
+        const RayInfo ray2 = rays[idx2];
+
+        // normal vector of the plane parallel to both lines
+        const Vector3 norm = Normalize(CrossProd(ray1.mRay->GetDir(), ray2.mRay->GetDir()));
+
+        // vector from line 1 to line 2
+        const Vector3 vd = ray2.ExtrapOrigin() - ray1.ExtrapOrigin();
+
+        // project vector on normal to get distance
+        const float dist = DotProd(vd, norm);
+
+        // point on plane lies halfway between the two planes
+        const Vector3 planePt = ray1.ExtrapOrigin() + norm * dist * 0.5;
+
+        return Plane3(norm, planePt);
+}
+
+
+inline void VspBspTree::GenerateUniqueIdsForPvs()
+{
+        Intersectable::NewMail(); sBackId = Intersectable::sMailId;
+        Intersectable::NewMail(); sFrontId = Intersectable::sMailId;
+        Intersectable::NewMail(); sFrontAndBackId = Intersectable::sMailId;
+}
+
+
+float VspBspTree::EvalSplitPlaneCost(const Plane3 &candidatePlane,
+                                                                         const VspBspTraversalData &data,
+                                                                         BspNodeGeometry &geomFront,
+                                                                         BspNodeGeometry &geomBack,
+                                                                         float &pFront,
+                                                                         float &pBack) const
+{
+        float cost = 0;
+
+        float sumBalancedRays = 0;
+        float sumRaySplits = 0;
+
+        int pvsFront = 0;
+        int pvsBack = 0;
+
+        // probability that view point lies in back / front node
+        float pOverall = 0;
+        pFront = 0;
+        pBack = 0;
+
+        int raysFront = 0;
+        int raysBack = 0;
+        int totalPvs = 0;
+
+        int limit;
+        bool useRand;
+
+        // choose test rays randomly if too much
+        if ((int)data.mRays->size() > mMaxTests)
+        {
+                useRand = true;
+                limit = mMaxTests;
+        }
+        else
+        {
+                useRand = false;
+                limit = (int)data.mRays->size();
+        }
+        
+        for (int i = 0; i < limit; ++ i)
+        {
+                const int testIdx = useRand ? 
+                        (int)RandomValue(0, (Real)((int)data.mRays->size() - 1)) : i;
+                RayInfo rayInf = (*data.mRays)[testIdx];
+
+                float t;
+                VssRay *ray = rayInf.mRay;
+                const int cf = rayInf.ComputeRayIntersection(candidatePlane, t);
+
+        if (0)
+                {
+                        if (cf >= 0)
+                                ++ raysFront;
+                        if (cf <= 0)
+                                ++ raysBack;
+                }
+
+                if (mSplitPlaneStrategy & LEAST_RAY_SPLITS)
+                {
+                        sumBalancedRays += cf;
+                }
+
+                if (mSplitPlaneStrategy & BALANCED_RAYS)
+                {
+                        if (cf == 0)
+                                ++ sumRaySplits;
+                }
+
+                if (mSplitPlaneStrategy & PVS)
+                {
+                        // find front and back pvs for origing and termination object
+                        AddObjToPvs(ray->mTerminationObject, cf, pvsFront, pvsBack, totalPvs);
+                        AddObjToPvs(ray->mOriginObject, cf, pvsFront, pvsBack, totalPvs);
+                }
+        }
+
+        const float raysSize = (float)data.mRays->size() + Limits::Small;
+
+        if (mSplitPlaneStrategy & PVS)
+        {
+                // create unique ids for pvs heuristics
+                GenerateUniqueIdsForPvs();
+
+                // construct child geometry with regard to the candidate split plane
+                data.mGeometry->SplitGeometry(geomFront,
+                                                                          geomBack,
+                                                                          candidatePlane,
+                                                                          mBox,
+                                                                          mEpsilon);
+
+                pOverall = data.mProbability;
+
+                if (!mUseAreaForPvs) // use front and back cell areas to approximate volume
+                {
+                        pFront = geomFront.GetVolume();
+                        pBack = pOverall - geomFront.GetVolume();
+                }
+                else
+                {
+                        pFront = geomFront.GetArea();
+                        pBack = geomBack.GetArea();
+                }
+        }
+
+
+        if (mSplitPlaneStrategy & LEAST_RAY_SPLITS)
+                cost += mLeastRaySplitsFactor * sumRaySplits / raysSize;
+
+        if (mSplitPlaneStrategy & BALANCED_RAYS)
+                cost += mBalancedRaysFactor * fabs(sumBalancedRays) / raysSize;
+
+        // -- pvs rendering heuristics
+        if (mSplitPlaneStrategy & PVS)
+        {
+                const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize();
+                const int upperPvsLimit = mViewCellsManager->GetMaxPvsSize();
+
+                // only render cost heuristics or combined with standard deviation
+                if (1)
+                {
+                        const float penaltyOld = EvalPvsPenalty(totalPvs, lowerPvsLimit, upperPvsLimit);
+                const float penaltyFront = EvalPvsPenalty(pvsFront, lowerPvsLimit, upperPvsLimit);
+                        const float penaltyBack = EvalPvsPenalty(pvsBack, lowerPvsLimit, upperPvsLimit);
+                        
+                        const float oldRenderCost = pOverall * (float)penaltyOld + Limits::Small;
+                        const float newRenderCost = penaltyFront * pFront + penaltyBack * pBack;
+
+                        float oldCost, newCost;
+
+                        if (1)
+                        {
+                                oldCost = oldRenderCost;
+                                newCost = newRenderCost;
+                        }
+                        else
+                        {
+                                // standard deviation is difference of back and front pvs
+                                const float expectedCost = 0.5f * (penaltyFront + penaltyBack);
+
+                                const float newDeviation = 0.5f * 
+                                        fabs(penaltyFront - expectedCost) + fabs(penaltyBack - expectedCost);
+
+                const float oldDeviation = penaltyOld + Limits::Small;
+
+                                newCost = mRenderCostWeight * newRenderCost + (1.0f - mRenderCostWeight) * newDeviation;
+                                oldCost = mRenderCostWeight * oldRenderCost + (1.0f - mRenderCostWeight) * oldDeviation;
+                        }
+
+                        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);
+                        
+                }
+        }
+
+#ifdef _DEBUG
+        Debug << "totalpvs: " << data.mPvs << " ptotal: " << pOverall
+                  << " frontpvs: " << pvsFront << " pFront: " << pFront
+                  << " backpvs: " << pvsBack << " pBack: " << pBack << endl << endl;
+#endif
+
+        // normalize cost by sum of linear factors
+        if(0)
+                return cost / (float)mCostNormalizer;
+        else
+                return cost;
+}
+
+
 float VspBspTree::EvalAxisAlignedSplitCost(const VspBspTraversalData &data,
                                                                                    const AxisAlignedBox3 &box,
@@ -1110 +1483 @@
 
         return  (mCtDivCi + newCost) / oldCost;
-}
-
-
-
-bool VspBspTree::SelectPlane(Plane3 &bestPlane,
-                                                         BspLeaf *leaf,
-                                                         VspBspTraversalData &data,
-                                                         VspBspTraversalData &frontData,
-                                                         VspBspTraversalData &backData)
-{
-        // simplest strategy: just take next polygon
-        if (mSplitPlaneStrategy & RANDOM_POLYGON)
-        {
-        if (!data.mPolygons->empty())
-                {
-                        const int randIdx = 
-                                (int)RandomValue(0, (Real)((int)data.mPolygons->size() - 1));
-                        Polygon3 *nextPoly = (*data.mPolygons)[randIdx];
-
-                        bestPlane = nextPoly->GetSupportingPlane();
-                        return true;
-                }
-        }
-
-        //-- use heuristics to find appropriate plane
-
-        // intermediate plane
-        Plane3 plane;
-        float lowestCost = MAX_FLOAT;
-        
-        // decides if the first few splits should be only axisAligned
-        const bool onlyAxisAligned  = 
-                (mSplitPlaneStrategy & AXIS_ALIGNED) &&
-                ((int)data.mRays->size() > mTermMinRaysForAxisAligned) &&
-                ((int)data.GetAvgRayContribution() < mTermMaxRayContriForAxisAligned);
-        
-        const int limit = onlyAxisAligned ? 0 : 
-                Min((int)data.mPolygons->size(), mMaxPolyCandidates);
-
-        float candidateCost;
-
-        int maxIdx = (int)data.mPolygons->size();
-
-        for (int i = 0; i < limit; ++ i)
-        {
-                // the already taken candidates are stored behind maxIdx
-                // => assure that no index is taken twice
-                const int candidateIdx = (int)RandomValue(0, (Real)(-- maxIdx));
-                Polygon3 *poly = (*data.mPolygons)[candidateIdx];
-
-                // swap candidate to the end to avoid testing same plane
-                std::swap((*data.mPolygons)[maxIdx], (*data.mPolygons)[candidateIdx]);
-                //Polygon3 *poly = (*data.mPolygons)[(int)RandomValue(0, (int)polys.size() - 1)];
-
-                // evaluate current candidate
-                BspNodeGeometry fGeom, bGeom;
-                float fArea, bArea;
-                plane = poly->GetSupportingPlane();
-                candidateCost = EvalSplitPlaneCost(plane, data, fGeom, bGeom, fArea, bArea);
-                
-                if (candidateCost < lowestCost)
-                {
-                        bestPlane = plane;
-                        lowestCost = candidateCost;
-                }
-        }
-
-        //-- evaluate axis aligned splits
-        int axis;
-        BspNodeGeometry *fGeom, *bGeom;
-        float pFront, pBack;
-
-        candidateCost = SelectAxisAlignedPlane(plane, data, axis,
-                                                                                   &fGeom, &bGeom, 
-                                                                                   pFront, pBack,
-                                                                                   data.mIsKdNode);      
-
-        bool isAxisAlignedSplit = false;
-
-        if (candidateCost < lowestCost)
-        {       
-                bestPlane = plane;
-                lowestCost = candidateCost;
-
-                // assign already computed values
-                // we can do this because we always save the
-                // computed values from the axis aligned splits         
-                frontData.mGeometry = fGeom;
-                backData.mGeometry = bGeom;
-        
-                frontData.mProbability = pFront;
-                backData.mProbability = pBack;
-                
-                //! error also computed if cost ratio is missed
-                ++ mBspStats.splits[axis];
-                isAxisAlignedSplit = true;
-        }
-        else
-        {
-                DEL_PTR(fGeom);
-                DEL_PTR(bGeom);
-        }
-
-        frontData.mIsKdNode = backData.mIsKdNode = (data.mIsKdNode && isAxisAlignedSplit);
-
-#ifdef _DEBUG
-        Debug << "plane lowest cost: " << lowestCost << endl;
-#endif
-
-        // cost ratio miss
-        if (lowestCost > mTermMaxCostRatio)
-                return false;
-
-        return true;
-}
-
-
-Plane3 VspBspTree::ChooseCandidatePlane(const RayInfoContainer &rays) const
-{
-        const int candidateIdx = (int)RandomValue(0, (Real)((int)rays.size() - 1));
-
-        const Vector3 minPt = rays[candidateIdx].ExtrapOrigin();
-        const Vector3 maxPt = rays[candidateIdx].ExtrapTermination();
-
-        const Vector3 pt = (maxPt + minPt) * 0.5;
-        const Vector3 normal = Normalize(rays[candidateIdx].mRay->GetDir());
-
-        return Plane3(normal, pt);
-}
-
-
-Plane3 VspBspTree::ChooseCandidatePlane2(const RayInfoContainer &rays) const
-{
-        Vector3 pt[3];
-
-        int idx[3];
-        int cmaxT = 0;
-        int cminT = 0;
-        bool chooseMin = false;
-
-        for (int j = 0; j < 3; ++ j)
-        {
-                idx[j] = (int)RandomValue(0, (Real)((int)rays.size() * 2 - 1));
-
-                if (idx[j] >= (int)rays.size())
-                {
-                        idx[j] -= (int)rays.size();
-
-                        chooseMin = (cminT < 2);
-                }
-                else
-                        chooseMin = (cmaxT < 2);
-
-                RayInfo rayInf = rays[idx[j]];
-                pt[j] = chooseMin ? rayInf.ExtrapOrigin() : rayInf.ExtrapTermination();
-        }
-
-        return Plane3(pt[0], pt[1], pt[2]);
-}
-
-Plane3 VspBspTree::ChooseCandidatePlane3(const RayInfoContainer &rays) const
-{
-        Vector3 pt[3];
-
-        int idx1 = (int)RandomValue(0, (Real)((int)rays.size() - 1));
-        int idx2 = (int)RandomValue(0, (Real)((int)rays.size() - 1));
-
-        // check if rays different
-        if (idx1 == idx2)
-                idx2 = (idx2 + 1) % (int)rays.size();
-
-        const RayInfo ray1 = rays[idx1];
-        const RayInfo ray2 = rays[idx2];
-
-        // normal vector of the plane parallel to both lines
-        const Vector3 norm = Normalize(CrossProd(ray1.mRay->GetDir(), ray2.mRay->GetDir()));
-
-        // vector from line 1 to line 2
-        const Vector3 vd = ray2.ExtrapOrigin() - ray1.ExtrapOrigin();
-
-        // project vector on normal to get distance
-        const float dist = DotProd(vd, norm);
-
-        // point on plane lies halfway between the two planes
-        const Vector3 planePt = ray1.ExtrapOrigin() + norm * dist * 0.5;
-
-        return Plane3(norm, planePt);
-}
-
-
-inline void VspBspTree::GenerateUniqueIdsForPvs()
-{
-        Intersectable::NewMail(); sBackId = ViewCell::sMailId;
-        Intersectable::NewMail(); sFrontId = ViewCell::sMailId;
-        Intersectable::NewMail(); sFrontAndBackId = ViewCell::sMailId;
-}
-
-
-float VspBspTree::EvalSplitPlaneCost(const Plane3 &candidatePlane,
-                                                                         const VspBspTraversalData &data,
-                                                                         BspNodeGeometry &geomFront,
-                                                                         BspNodeGeometry &geomBack,
-                                                                         float &pFront,
-                                                                         float &pBack) const
-{
-        float cost = 0;
-
-        float sumBalancedRays = 0;
-        float sumRaySplits = 0;
-
-        int pvsFront = 0;
-        int pvsBack = 0;
-
-        // probability that view point lies in back / front node
-        float pOverall = 0;
-        pFront = 0;
-        pBack = 0;
-
-        int raysFront = 0;
-        int raysBack = 0;
-        int totalPvs = 0;
-
-        int limit;
-        bool useRand;
-
-        // choose test rays randomly if too much
-        if ((int)data.mRays->size() > mMaxTests)
-        {
-                useRand = true;
-                limit = mMaxTests;
-        }
-        else
-        {
-                useRand = false;
-                limit = (int)data.mRays->size();
-        }
-        
-        for (int i = 0; i < limit; ++ i)
-        {
-                const int testIdx = useRand ? 
-                        (int)RandomValue(0, (Real)((int)data.mRays->size() - 1)) : i;
-                RayInfo rayInf = (*data.mRays)[testIdx];
-
-                float t;
-                VssRay *ray = rayInf.mRay;
-                const int cf = rayInf.ComputeRayIntersection(candidatePlane, t);
-
-        if (0)
-                {
-                        if (cf >= 0)
-                                ++ raysFront;
-                        if (cf <= 0)
-                                ++ raysBack;
-                }
-
-                if (mSplitPlaneStrategy & LEAST_RAY_SPLITS)
-                {
-                        sumBalancedRays += cf;
-                }
-
-                if (mSplitPlaneStrategy & BALANCED_RAYS)
-                {
-                        if (cf == 0)
-                                ++ sumRaySplits;
-                }
-
-                if (mSplitPlaneStrategy & PVS)
-                {
-                        // find front and back pvs for origing and termination object
-                        AddObjToPvs(ray->mTerminationObject, cf, pvsFront, pvsBack, totalPvs);
-                        AddObjToPvs(ray->mOriginObject, cf, pvsFront, pvsBack, totalPvs);
-                }
-        }
-
-        const float raysSize = (float)data.mRays->size() + Limits::Small;
-
-        if (mSplitPlaneStrategy & PVS)
-        {
-                // create unique ids for pvs heuristics
-                GenerateUniqueIdsForPvs();
-
-                // construct child geometry with regard to the candidate split plane
-                data.mGeometry->SplitGeometry(geomFront,
-                                                                          geomBack,
-                                                                          candidatePlane,
-                                                                          mBox,
-                                                                          mEpsilon);
-
-                pOverall = data.mProbability;
-
-                if (!mUseAreaForPvs) // use front and back cell areas to approximate volume
-                {
-                        pFront = geomFront.GetVolume();
-                        pBack = pOverall - geomFront.GetVolume();
-                }
-                else
-                {
-                        pFront = geomFront.GetArea();
-                        pBack = geomBack.GetArea();
-                }
-        }
-
-
-        if (mSplitPlaneStrategy & LEAST_RAY_SPLITS)
-                cost += mLeastRaySplitsFactor * sumRaySplits / raysSize;
-
-        if (mSplitPlaneStrategy & BALANCED_RAYS)
-                cost += mBalancedRaysFactor * fabs(sumBalancedRays) / raysSize;
-
-        // pvs criterium
-        if (mSplitPlaneStrategy & PVS)
-        {
-                if (1)
-                {
-                        const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize();
-                        const int upperPvsLimit = mViewCellsManager->GetMaxPvsSize();
-                        
-                        const float penaltyOld = EvalPvsPenalty(totalPvs, lowerPvsLimit, upperPvsLimit);
-            
-                        const float penaltyFront = EvalPvsPenalty(pvsFront, lowerPvsLimit, upperPvsLimit);
-                        const float penaltyBack = EvalPvsPenalty(pvsBack, lowerPvsLimit, upperPvsLimit);
-                        
-                        const float oldCost = pOverall * (float)penaltyOld + Limits::Small;
-                        cost += mPvsFactor * (penaltyFront * pFront + penaltyBack * pBack) / oldCost;
-
-                }
-                else
-                {
-                        // try to equalize render differences
-                        //const float oldCost = pOverall * (float)totalPvs + Limits::Small;
-                        //float newCost = fabs(pvsFront * pFront - pvsBack * pBack);
-                        const float oldCost = pOverall + Limits::Small;
-                        float newCost = (float)abs(pvsFront - pvsBack);
-
-                        cost += mPvsFactor * newCost / oldCost;
-                }
-        }
-
-#ifdef _DEBUG
-        Debug << "totalpvs: " << data.mPvs << " ptotal: " << pOverall
-                  << " frontpvs: " << pvsFront << " pFront: " << pFront
-                  << " backpvs: " << pvsBack << " pBack: " << pBack << endl << endl;
-#endif
-
-        // normalize cost by sum of linear factors
-        if(0)
-                return cost / (float)mCostNormalizer;
-        else
-                return cost;
 }
 
@@ -1731 +1755 @@
                         {
                                 BspViewCell *viewCell = dynamic_cast<BspLeaf *>(node)->GetViewCell();
-                        
-                                vector<BspLeaf *>::const_iterator it, it_end = viewCell->mLeaves.end();
-                                for (it = viewCell->mLeaves.begin();it != it_end; ++ it)
+        
+                                ViewCellContainer leaves;
+                                mViewCellsManager->GetViewCellsTree()->CollectLeaves(viewCell, leaves);
+
+                                ViewCellContainer::const_iterator it, it_end = leaves.end();
+
+                                for (it = leaves.begin(); it != it_end; ++ it)
                                 {
-                                        BspLeaf *l = *it;
+                                        BspLeaf *l = dynamic_cast<BspViewCell *>(*it)->mLeaf;
                                         l->SetViewCell(GetOrCreateOutOfBoundsCell());
                                         ++ mBspStats.invalidLeaves;
@@ -2024 +2052 @@
                                                                    BspNodeGeometry &vcGeom) const
 {
-        vector<BspLeaf *> leaves = vc->mLeaves;
-        vector<BspLeaf *>::const_iterator it, it_end = leaves.end();
+        ViewCellContainer leaves;
+        mViewCellsManager->GetViewCellsTree()->CollectLeaves(vc, leaves);
+
+        ViewCellContainer::const_iterator it, it_end = leaves.end();
 
         for (it = leaves.begin(); it != it_end; ++ it)
-                ConstructGeometry(*it, vcGeom);
+        {
+                BspLeaf *l = dynamic_cast<BspViewCell *>(*it)->mLeaf;
+                ConstructGeometry(l, vcGeom);
+        }
 }
 
@@ -2456 +2489 @@
 }
 
+
 BspNode *VspBspTree::CollapseTree(BspNode *node, int &collapsed)
 {
@@ -2499 +2533 @@
 {
         int collapsed = 0;
-        
+        //TODO
+#if VC_HISTORY
         (void)CollapseTree(mRoot, collapsed);
 
         // revalidate leaves
         RepairViewCellsLeafLists();
-
+#endif
         return collapsed;
 }
@@ -2527 +2562 @@
 
                         BspViewCell *viewCell = leaf->GetViewCell();
-
+        // TODO
+#if VC_HISTORY
                         if (!viewCell->Mailed())
                         {
@@ -2533 +2569 @@
                                 viewCell->Mail();
                         }
-
+        
                         viewCell->mLeaves.push_back(leaf);
+// TODO
+#endif
                 }
                 else
@@ -2631 +2669 @@
 
 
-bool VspBspTree::MergeViewCells(BspLeaf *l1, BspLeaf *l2) //const
-{
-        //-- change pointer to view cells of all leaves associated
-        //-- with the previous view cells
-        BspViewCell *fVc = l1->GetViewCell();
-        BspViewCell *bVc = l2->GetViewCell();
-
-        BspViewCell *vc = dynamic_cast<BspViewCell *>(
-                mViewCellsManager->MergeViewCells(*fVc, *bVc));
-
-        // if merge was unsuccessful
-        if (!vc) return false;
-
-        // set new size of view cell
-        if (mUseAreaForPvs)
-                vc->SetArea(fVc->GetArea() + bVc->GetArea());
-        else
-                vc->SetVolume(fVc->GetVolume() + bVc->GetVolume());
-        
-        vector<BspLeaf *> fLeaves = fVc->mLeaves;
-        vector<BspLeaf *> bLeaves = bVc->mLeaves;
-
-        vector<BspLeaf *>::const_iterator it;
-
-        //-- change view cells of all the other leaves the view cell belongs to
-        for (it = fLeaves.begin(); it != fLeaves.end(); ++ it)
-        {
-                (*it)->SetViewCell(vc);
-                vc->mLeaves.push_back(*it);
-        }
-
-        for (it = bLeaves.begin(); it != bLeaves.end(); ++ it)
-        {
-                (*it)->SetViewCell(vc);
-                vc->mLeaves.push_back(*it);
-        }
-
-        // important so other merge candidates sharing this view cell
-        // are notified that the merge cost must be updated!!
-        vc->Mail();
-
-        //-- clean up old view cells
-        if (mExportMergedViewCells)
-        {
-                DEL_PTR(fVc);
-                DEL_PTR(bVc);
-        }
-        else 
-        {
-                // old view cells container needed for visualization
-                //fVc->mMailbox = -1;
-                //bVc->mMailbox = -1;
-                fVc->SetId(-2);
-                bVc->SetId(-2);
-
-                mOldViewCells.push_back(fVc);
-                mOldViewCells.push_back(bVc);
-                
-                mNewViewCells.push_back(vc);
-        }
-
-        return true;
-}
-
-
 void VspBspTree::SetViewCellsManager(ViewCellsManager *vcm)
 {
@@ -2702 +2675 @@
 
 
-int VspBspTree::CollectMergeCandidates(const vector<BspLeaf *> leaves)
+int VspBspTree::CollectMergeCandidates(const vector<BspLeaf *> leaves,
+                                                                           vector<MergeCandidate> &candidates)
 {
         BspLeaf::NewMail();
@@ -2708 +2682 @@
         vector<BspLeaf *>::const_iterator it, it_end = leaves.end();
 
-        int candidates = 0;
+        int numCandidates = 0;
 
         // find merge candidates and push them into queue
@@ -2714 +2688 @@
         {
                 BspLeaf *leaf = *it;
-                
-                /// create leaf pvs (needed for post processing)
-                leaf->mPvs = new ObjectPvs(leaf->GetViewCell()->GetPvs());
-
-                //const float rc = leaf->mProbability * (float)leaf->mPvs->GetSize();
-                //BspMergeCandidate::sOverallCost += rc;
                 
                 // the same leaves must not be part of two merge candidates
@@ -2733 +2701 @@
                         if ((*nit)->GetViewCell() != leaf->GetViewCell())
                         {
-                                BspMergeCandidate mc(leaf, *nit);
-                                mc.EvalMergeCost();
-
-                                mMergeQueue.push(mc);
-                                ++ candidates;
-                                if ((candidates % 1000) == 0)
+                                MergeCandidate mc(leaf->GetViewCell(), (*nit)->GetViewCell());
+                                candidates.push_back(mc);
+
+                                ++ numCandidates;
+                                if ((numCandidates % 1000) == 0)
                                 {
-                                        cout << "collected " << candidates << " merge candidates" << endl;
+                                        cout << "collected " << numCandidates << " merge candidates" << endl;
                                 }
                         }
@@ -2746 +2713 @@
         }
 
-        Debug << "mergequeue: " << (int)mMergeQueue.size() << endl;
-        Debug << "leaves in queue: " << candidates << endl;
-        Debug << "overall cost: " << BspMergeCandidate::sOverallCost << endl;
-
+        Debug << "merge queue: " << (int)candidates.size() << endl;
+        Debug << "leaves in queue: " << numCandidates << endl;
+        
 
         return (int)leaves.size();
@@ -2755 +2721 @@
 
 
-int VspBspTree::CollectMergeCandidates(const VssRayContainer &rays)
+int VspBspTree::CollectMergeCandidates(const VssRayContainer &rays, 
+                                                                           vector<MergeCandidate> &candidates)
 {
         ViewCell::NewMail();
@@ -2775 +2742 @@
                 if (ray->mViewCells.size() < 2)
                         continue;
-          
+//TODO viewcellhierarchy
                 iit = ray->mViewCells.begin();
                 BspViewCell *bspVc = dynamic_cast<BspViewCell *>(*(iit ++));
-                BspLeaf *leaf = bspVc->mLeaves[0];
-                
-                // create leaf pvs (needed for post processing)
-                if (!leaf->mPvs)
-                {
-                        leaf->mPvs = 
-                                new ObjectPvs(leaf->GetViewCell()->GetPvs());
-
-                        //BspMergeCandidate::sOverallCost += 
-                        //      leaf->mProbability * leaf->mPvs->GetSize();
-                        
-                        ++ numLeaves;
-                }
+                BspLeaf *leaf = bspVc->mLeaf;
                 
                 // traverse intersections 
@@ -2799 +2754 @@
                         BspLeaf *prevLeaf = leaf;
                         bspVc = dynamic_cast<BspViewCell *>(*iit);
-            leaf = bspVc->mLeaves[0];
+            leaf = bspVc->mLeaf;
 
                         // view space not valid or same view cell
@@ -2806 +2761 @@
                                 continue;
 
-            // create leaf pvs (needed for post processing)
-                        if (!leaf->mPvs)
-                        {
-                                leaf->mPvs = 
-                                        new ObjectPvs(leaf->GetViewCell()->GetPvs());
-                                
-                                //BspMergeCandidate::sOverallCost += 
-                                //      leaf->mProbability * leaf->mPvs->GetSize();
-
-                                ++ numLeaves;
-                        }
-                
-                        vector<BspLeaf *> &neighbors = neighborMap[leaf];
+                vector<BspLeaf *> &neighbors = neighborMap[leaf];
                         
                         bool found = false;
@@ -2843 +2786 @@
                                 prevLeaf->Mail();
                 
-                                BspMergeCandidate mc(leaf, prevLeaf);
-                                mc.EvalMergeCost();
-
-                                mMergeQueue.push(mc);
-
-                                if (((int)mMergeQueue.size() % 1000) == 0)
+                                MergeCandidate mc(leaf->GetViewCell(), prevLeaf->GetViewCell());
+                                
+                                candidates.push_back(mc);
+
+                                if (((int)candidates.size() % 1000) == 0)
                                 {
-                                        cout << "collected " << (int)mMergeQueue.size() << " merge candidates" << endl;
+                                        cout << "collected " << (int)candidates.size() << " merge candidates" << endl;
                                 }
                         }
@@ -2857 +2799 @@
 
         Debug << "neighbormap size: " << (int)neighborMap.size() << endl;
-        Debug << "mergequeue: " << (int)mMergeQueue.size() << endl;
+        Debug << "merge queue: " << (int)candidates.size() << endl;
         Debug << "leaves in queue: " << numLeaves << endl;
-        Debug << "overall cost: " << BspMergeCandidate::sOverallCost << endl;
+
 
         //-- collect the leaves which haven't been found by ray casting
@@ -2868 +2810 @@
                 CollectLeaves(leaves, true);
                 Debug << "found " << (int)leaves.size() << " new leaves" << endl << endl;
-                CollectMergeCandidates(leaves);
+                CollectMergeCandidates(leaves, candidates);
         }
 
@@ -2875 +2817 @@
 
 
-void VspBspTree::ConstructBspRays(vector<BspRay *> &bspRays,
-                                                                  const VssRayContainer &rays)
-{
-        VssRayContainer::const_iterator it, it_end = rays.end();
-
-        for (it = rays.begin(); it != rays.end(); ++ it)
-        {
-                VssRay *vssRay = *it;
-                BspRay *ray = new BspRay(vssRay);
-
-                ViewCellContainer viewCells;
-
-                Ray hray(*vssRay);
-                float tmin = 0, tmax = 1.0;
-                // matt TODO: remove this!!
-                //hray.Init(ray.GetOrigin(), ray.GetDir(), Ray::LINE_SEGMENT);
-                if (!mBox.GetRaySegment(hray, tmin, tmax) || (tmin > tmax))
-                        continue;
-
-                Vector3 origin = hray.Extrap(tmin);
-                Vector3 termination = hray.Extrap(tmax);
-        
-                // cast line segment to get intersections with bsp leaves
-                CastLineSegment(origin, termination, viewCells);
-
-                ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
-                for (vit = viewCells.begin(); vit != vit_end; ++ vit)
-                {
-                        BspViewCell *vc = dynamic_cast<BspViewCell *>(*vit);
-                        vector<BspLeaf *>::const_iterator it, it_end = vc->mLeaves.end();
-                        //NOTE: not sorted!
-                        for (it = vc->mLeaves.begin(); it != it_end; ++ it)
-                        {
-                                ray->intersections.push_back(BspIntersection(0, *it));
-                        }
-                }
-
-                bspRays.push_back(ray);
-        }
-}
-
-
-#if 1
-int VspBspTree::MergeViewCells(const VssRayContainer &rays, const ObjectContainer &objects)
-{
-        BspMergeCandidate::sViewCellsManager = mViewCellsManager;
-        BspMergeCandidate::sUseArea = mUseAreaForPvs;
-
-
-        //-- compute statistics values of initial view cells
-        mViewCellsManager->EvaluateRenderStatistics(BspMergeCandidate::sOverallCost, 
-                                                                                                BspMergeCandidate::sExpectedCost,
-                                                                                                BspMergeCandidate::sVariance);
-
-
-        //BspMergeCandidate::sExpectedCost = 
-        //      BspMergeCandidate::sOverallCost / BspMergeCandidate::sNumViewCells;
-
-
-        ViewCellsManager::PvsStatistics pvsStats;
-        mViewCellsManager->GetPvsStatistics(pvsStats);
-
-        static float expectedValue = pvsStats.avgPvs;
-        
-        // the current view cells are kept in this container
-        ViewCellContainer viewCells;
-        if (mExportMergedViewCells)
-        {
-                ViewCell::NewMail();
-                CollectViewCells(mRoot, true, viewCells, true);
-        }
-
-
-        ViewCell::NewMail();
-
-        MergeStatistics mergeStats;
-        mergeStats.Start();
-        
-        long startTime = GetTime();
-
-        cout << "collecting merge candidates ... " << endl;
-        
-        if (mUseRaysForMerge)
-        {
-                mergeStats.nodes = CollectMergeCandidates(rays);
-        }
-        else
-        {
-                vector<BspLeaf *> leaves;
-                CollectLeaves(leaves);
-                mergeStats.nodes = CollectMergeCandidates(leaves);
-        }
-        
-        cout << "fininshed collecting candidates" << endl;
-
-        mergeStats.collectTime = TimeDiff(startTime, GetTime());
-        mergeStats.candidates = (int)mMergeQueue.size();
-        startTime = GetTime();
-
-        // frequency stats are updated
-        const int statsOut = 100;
-
-        // number of view cells withouth the invalid ones
-        BspMergeCandidate::sNumViewCells = mBspStats.Leaves() - mBspStats.invalidLeaves;
-
-        // passes are needed for statistics, because we don't want to record
-        // every merge
-        const int maxMergesPerPass = 100;
-        int pass = 0;
-
-        // maximal ratio of old expected render cost to expected render
-        // when the the render queue has to be reset.
-        const float ercMaxRatio = 0.7f;
-        
-        cout << "actual merge starts now ... " << endl;
-
-        
-        
-        //-- use priority queue to merge leaf pairs
-
-
-        while (!mMergeQueue.empty() && 
-                   (BspMergeCandidate::sNumViewCells > mMergeMinViewCells) &&
-                   (mMergeQueue.top().GetMergeCost() < mMergeMaxCostRatio * BspMergeCandidate::sOverallCost))
-        {
-
-                int mergedPerPass = 0;
-                const float oldExpectedCost = BspMergeCandidate::sExpectedCost;
-                
-//#ifdef _DEBUG
-                Debug << "abs mergecost: " << mMergeQueue.top().GetMergeCost() << " rel mergecost: "
-                          << mMergeQueue.top().GetMergeCost() / BspMergeCandidate::sOverallCost 
-                          << " max ratio: " << mMergeMaxCostRatio << endl
-                          << " expected value: " << oldExpectedCost << endl;
-//#endif
-
-                while (!mMergeQueue.empty() && 
-                           (BspMergeCandidate::sNumViewCells > mMergeMinViewCells) &&
-                           (ercMaxRatio > oldExpectedCost / BspMergeCandidate::sExpectedCost) &&
-                           (mMergeQueue.top().GetMergeCost() < mMergeMaxCostRatio * BspMergeCandidate::sOverallCost) &&
-                           (maxMergesPerPass < mergedPerPass));
-                {
-                                Debug << "erc max ratio" << ercMaxRatio << endl;
-
-                                BspMergeCandidate mc = mMergeQueue.top();
-                                mMergeQueue.pop();
-
-                                // both view cells equal!
-                                if (mc.GetLeaf1()->GetViewCell() == mc.GetLeaf2()->GetViewCell())
-                                        continue;
-
-                                if (mc.Valid())
-                                {
-                                        ViewCell::NewMail();
-                                        const float currentMergeCost = mc.GetMergeCost();
-
-                                        MergeViewCells(mc.GetLeaf1(), mc.GetLeaf2());
-                                        
-                                        -- BspMergeCandidate::sNumViewCells;
-                                        ++ mergeStats.merged;
-                                        ++ mergedPerPass;
-
-                                        // increase absolute merge cost
-                                        BspMergeCandidate::sOverallCost += mc.GetRenderCost();
-                                        BspMergeCandidate::sVariance = mc.GetVarianceIncr();
-
-                                        BspMergeCandidate::sExpectedCost = 
-                                                BspMergeCandidate::sOverallCost / (float)BspMergeCandidate::sNumViewCells;
-
-                                        // stats
-                                        if (mc.GetLeaf1()->IsSibling(mc.GetLeaf2()))
-                                                ++ mergeStats.siblings;
-
-                                        if (0)
-                                        {
-                                                const int dist = 
-                                                        TreeDistance(mc.GetLeaf1(), mc.GetLeaf2());
-                                                if (dist > mergeStats.maxTreeDist)
-                                                        mergeStats.maxTreeDist = dist;
-                                                mergeStats.accTreeDist += dist;
-                                        }
-
-                                        if ((mergeStats.merged % statsOut) == 0)
-                                        {
-                                                cout << "merged " << mergeStats.merged << " view cells" << endl;
-
-                                                mStats 
-                                                        << "#Pass\n" << pass << endl
-                                                        << "#Merged\n" << mergeStats.merged << endl 
-                                                        << "#Viewcells\n" << BspMergeCandidate::sNumViewCells << endl 
-                                                        << "#OverallCost\n" << BspMergeCandidate::sOverallCost << endl
-                                                        << "#CurrentCost\n" << currentMergeCost << endl
-                                                        << "#RelativeCost\n" << currentMergeCost / BspMergeCandidate::sOverallCost << endl
-                                                        << "#CurrentPvs\n" << mc.GetLeaf1()->GetViewCell()->GetPvs().GetSize() << endl
-                                                        << "#MergedSiblings\n" << mergeStats.siblings << endl
-                                                        << "#AvgTreeDist\n" << mergeStats.AvgTreeDist() << endl
-                                                        << "#ExpectedCost\n" << BspMergeCandidate::sExpectedCost << endl
-                                                        << "#RatioExpectedCost\n" << oldExpectedCost / BspMergeCandidate::sExpectedCost << endl
-                                                        << "#variance\n" << BspMergeCandidate::sVariance << endl;
-
-                                                if (mExportMergedViewCells)
-                                                        ExportMergedViewCells(viewCells, objects, BspMergeCandidate::sNumViewCells);
-                                        }
-                                }
-                                else
-                                { 
-
-                                        // merge candidate not valid, because one of the leaves was already
-                                        // merged with another one => validate and reinsert into queue
-                                        mc.SetValid();
-                                        mMergeQueue.push(mc);
-                                }
-                }
-        
-
-                ++ pass;
-        }
-
-        mergeStats.overallCost = BspMergeCandidate::sOverallCost;
-
-        mergeStats.mergeTime = TimeDiff(startTime, GetTime());
-        mergeStats.Stop();
-
-        Debug << mergeStats << endl << endl;
-        
-        // delete the view cells which were already merged
-        CLEAR_CONTAINER(mOldViewCells);
-        
-
-        //TODO: should return sample contributions?
-        return mergeStats.merged;
-}
-
-#else
-
-int VspBspTree::MergeViewCells(const VssRayContainer &rays, const ObjectContainer &objects)
-{
-        BspMergeCandidate::sViewCellsManager = mViewCellsManager;
-        BspMergeCandidate::sUseArea = mUseAreaForPvs;
-
-        ViewCellsManager::PvsStatistics pvsStats;
-        mViewCellsManager->GetPvsStatistics(pvsStats);
-
-        static float expectedValue = pvsStats.avgPvs;
-        // the current view cells are kept in this container
-        ViewCellContainer viewCells;
-        if (mExportMergedViewCells)
-        {
-                ViewCell::NewMail();
-                CollectViewCells(mRoot, true, viewCells, true);
-        }
-        ViewCell::NewMail();
-
-        MergeStatistics mergeStats;
-        mergeStats.Start();
-        
-        //BspMergeCandidate::sOverallCost = mBox.SurfaceArea() * mBspStats.maxPvs;
-        long startTime = GetTime();
-
-        cout << "collecting merge candidates ... " << endl;
-        
-        if (mUseRaysForMerge)
-        {
-                mergeStats.nodes = CollectMergeCandidates(rays);
-        }
-        else
-        {
-                vector<BspLeaf *> leaves;
-                CollectLeaves(leaves);
-                mergeStats.nodes = CollectMergeCandidates(leaves);
-        }
-        
-        cout << "fininshed collecting candidates" << endl;
-
-        mergeStats.collectTime = TimeDiff(startTime, GetTime());
-        mergeStats.candidates = (int)mMergeQueue.size();
-        startTime = GetTime();
-
-        
-        // number of view cells withouth the invalid ones
-        int nViewCells = mBspStats.Leaves() - mBspStats.invalidLeaves;
-        BspMergeCandidate::sExpectedCost = BspMergeCandidate::sOverallCost / (float)nViewCells;
-
-        // passes are needed for statistics, because we don't want to record
-        // every merge
-        const int mergesPerPass = 100;
-        
-        int nextPass = 0;
-    int pass = 0;
-        
-        
-        Debug << "stats: " << nextStats << " " << statsIncr << endl;
-        cout << "actual merge starts now ... " << endl;
-
-        //-- use priority queue to merge leaf pairs
-        while (!mMergeQueue.empty() && (nViewCells > mMergeMinViewCells) &&
-                   (mMergeQueue.top().GetMergeCost() <
-                    mMergeMaxCostRatio * BspMergeCandidate::sOverallCost))
-        {
-#ifdef _DEBUG
-                Debug << "abs mergecost: " << mMergeQueue.top().GetMergeCost() << " rel mergecost: "
-                          << mMergeQueue.top().GetMergeCost() / BspMergeCandidate::sOverallCost 
-                          << " max ratio: " << mMergeMaxCostRatio << endl;
-#endif
-
-                BspMergeCandidate mc = mMergeQueue.top();
-                mMergeQueue.pop();
-
-
-                // both view cells equal!
-                if (mc.GetLeaf1()->GetViewCell() == mc.GetLeaf2()->GetViewCell())
-                        continue;
-
-                if (mc.Valid())
-                {
-                        ViewCell::NewMail();
-                        const float mergeCost = mc.GetMergeCost();
-
-                        MergeViewCells(mc.GetLeaf1(), mc.GetLeaf2());
-                                        
-                        // increase absolute merge cost
-                        BspMergeCandidate::sOverallCost += mc.GetMergeCost();
-                        
-
-                        -- nViewCells;
-                        ++ mergeStats.merged;
-
-                        if ((mergeStats.merged % 500) == 0)
-                                cout << "merged " << mergeStats.merged << " view cells" << endl;
-
-                        // stats and visualizations
-                        if (mExportMergeStats)
-                        {
-                                if (mc.GetLeaf1()->IsSibling(mc.GetLeaf2()))
-                                        ++ mergeStats.siblings;
-
-                                if (0)
-                                const int dist = 
-                                        TreeDistance(mc.GetLeaf1(), mc.GetLeaf2());
-                                if (dist > mergeStats.maxTreeDist)
-                                        mergeStats.maxTreeDist = dist;
-                                mergeStats.accTreeDist += dist;
-
-                                if ((mergeStats.merged == nextPass) || (nViewCells == mMergeMinViewCells))
-                                {
-                                        nextPass += mergesPerPass;
-
-                                        mStats 
-                                                << "#Pass\n" << pass ++ << endl
-                                                << "#Merged\n" << mergeStats.merged << endl 
-                                                << "#Viewcells\n" << nViewCells << endl 
-                                                << "#OverallCost\n" << BspMergeCandidate::sOverallCost << endl
-                                                << "#CurrentCost\n" << mergeCost << endl
-                                                << "#RelativeCost\n" << mergeCost / BspMergeCandidate::sOverallCost << endl
-                                                << "#CurrentPvs\n" << mc.GetLeaf1()->GetViewCell()->GetPvs().GetSize() << endl
-                                                << "#MergedSiblings\n" << mergeStats.siblings << endl
-                                                << "#AvgTreeDist\n" << mergeStats.AvgTreeDist() << endl;
-
-                                                if (mExportMergedViewCells)
-                                                        ExportMergedViewCells(viewCells, objects, nViewCells);
-                                }
-                        }
-                }
-                // merge candidate not valid, because one of the leaves was already
-                // merged with another one => validate and reinsert into queue
-                else
-                { 
-                        mc.SetValid();
-                        mMergeQueue.push(mc);
-                }
-        }
-
-        mergeStats.overallCost = BspMergeCandidate::sOverallCost;
-
-        mergeStats.mergeTime = TimeDiff(startTime, GetTime());
-        mergeStats.Stop();
-
-        Debug << mergeStats << endl << endl;
-        
-        // delete the view cells which were already merged
-        CLEAR_CONTAINER(mOldViewCells);
-        
-
-        //TODO: should return sample contributions?
-        return mergeStats.merged;
-}
-#endif
 
 
@@ -3297 +2852 @@
 
 
-void VspBspTree::ExportMergedViewCells(ViewCellContainer &viewCells, 
-                                                                           const ObjectContainer &objects,
-                                                                           const int nViewCells)
-{
-        ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
-                                        
-        // find all already merged view cells and remove them from view cells
-        int i = 0;
-
-        while (1)
-        {
-                //while (!viewCells.empty() && (viewCells.back()->mMailbox == -1))
-                while (!viewCells.empty() && (viewCells.back()->GetId() == -2))
-                {
-                        //DEL_PTR(viewCells.back());
-                        viewCells.pop_back();
-                }
-                // all merged view cells have been found
-                if (i >= viewCells.size()) 
-                        break;
-
-                // already merged view cell, put it to end of vector
-                //if (viewCells[i]->mMailbox == -1)
-                if (viewCells[i]->GetId() == -2)
-                        swap(viewCells[i], viewCells.back());
-                
-                ++ i;
-        }
-
-        int newVcSize = 0;
-        // add new view cells to container only if they don't have been 
-        // merged in the mean time
-        while (!mNewViewCells.empty())
-        {
-                if (mNewViewCells.back()->GetId() != -2)
-                {
-                        viewCells.push_back(mNewViewCells.back());
-                        ++ newVcSize;
-                }
-
-                mNewViewCells.pop_back();
-        }
-
-        char s[64];
-        sprintf(s, "merged_viewcells%07d.x3d", nViewCells);
-        Exporter *exporter = Exporter::GetExporter(s);
-
-        if (exporter)
-        {
-                cout << "exporting " << nViewCells << " merged view cells ... ";
-                exporter->ExportGeometry(objects);
-                //Debug << "vc size " << (int)viewCells.size() << " merge queue size: " << (int)mMergeQueue.size() << endl;
-                ViewCellContainer::const_iterator it, it_end = viewCells.end();
-
-                int i = 0;
-                for (it = viewCells.begin(); it != it_end; ++ it)
-                {
-                        Material m;
-                        // assign special material to new view cells
-                        // new view cells are on the back of container
-                        if (i ++ >= (viewCells.size() - newVcSize))
-                        {
-                                //m = RandomMaterial();
-                                m.mDiffuseColor.r = RandomValue(0.5f, 1.0f);
-                                m.mDiffuseColor.g = RandomValue(0.5f, 1.0f);
-                                m.mDiffuseColor.b = RandomValue(0.5f, 1.0f);
-                        }
-                        else
-                        {
-                                float col = RandomValue(0.1f, 0.4f);
-                                m.mDiffuseColor.r = col;
-                                m.mDiffuseColor.g = col;
-                                m.mDiffuseColor.b = col;
-                        }
-
-                        exporter->SetForcedMaterial(m);
-                        mViewCellsManager->ExportVcGeometry(exporter, *it);
-                }
-                delete exporter;
-                cout << "finished" << endl;
-        }
-
-        // delete the view cells which were merged
-        CLEAR_CONTAINER(mOldViewCells);
-        // remove the new view cells
-        mNewViewCells.clear();
-}
-
-
-int VspBspTree::RefineViewCells(const VssRayContainer &rays, const ObjectContainer &objects)
-{
-        Debug << "refining " << (int)mMergeQueue.size() << " candidates " << endl;
-        
-        BspLeaf::NewMail();
-
-        // Use priority queue of remaining leaf pairs 
-        // The candidates either share the same view cells or
-        // are border leaves which share a boundary.
-        // We test if they can be shuffled, i.e.,
-        // either one leaf is made part of one view cell or the other
-        // leaf is made part of the other view cell. It is tested if the
-        // remaining view cells are "better" than the old ones.
-        //
-        // repeat the merging test numPasses times. For example, it could be
-        // that a shuffle only makes sense if another pair was shuffled before.
-        // Therefore we keep two queues and shift the merge candidates between
-        // those two queues until numPasses is reached
-        
-        queue<BspMergeCandidate> queue1;
-        queue<BspMergeCandidate> queue2;
-
-        queue<BspMergeCandidate> *shuffleQueue = &queue1;
-        queue<BspMergeCandidate> *backQueue = &queue2;
-
-        while (!mMergeQueue.empty())
-        {
-                BspMergeCandidate mc = mMergeQueue.top();
-                shuffleQueue->push(mc);
-                mMergeQueue.pop();
-        }
-
-        const int numPasses = 5;
-        int pass = 0;
-        int passShuffled = 0;
-        int shuffled = 0;
-
-        BspLeaf::NewMail();
-
-        do
-        {
-                passShuffled = 0;
-                while (!shuffleQueue->empty())
-                {
-                        BspMergeCandidate mc = shuffleQueue->front();
-                        shuffleQueue->pop();
-
-                        // both view cells equal or already shuffled
-                        if ((mc.GetLeaf1()->GetViewCell() == mc.GetLeaf2()->GetViewCell()))// ||
-                        //      (mc.GetLeaf1()->Mailed()) || (mc.GetLeaf2()->Mailed()))
-                                continue;
-                
-                        // candidate for shuffling
-                        const bool wasShuffled = 
-                                ShuffleLeaves(mc.GetLeaf1(), mc.GetLeaf2());
-                
-                        if (wasShuffled)
-                                ++ passShuffled;
-                        else
-                                backQueue->push(mc);
-                }
-
-                // now the back queue is the current shuffle queue
-                swap(shuffleQueue, backQueue);
-                shuffled += passShuffled;
-                Debug << "shuffled in pass: " << passShuffled << endl;
-        }
-        while (((++ pass) < numPasses) && passShuffled);
-
-        while (!shuffleQueue->empty())
-        {
-                shuffleQueue->pop();
-        }
-
-        return shuffled;
-}
-
-
-inline int AddedPvsSize(ObjectPvs pvs1, const ObjectPvs &pvs2)
-{
-        return pvs1.AddPvs(pvs2);
-}
-
-
-// recomputes pvs size minus pvs of leaf l
-#if 0
-inline int SubtractedPvsSize(BspViewCell *vc, BspLeaf *l, const ObjectPvs &pvs2)
-{
-        ObjectPvs pvs;
-        vector<BspLeaf *>::const_iterator it, it_end = vc->mLeaves.end();
-        for (it = vc->mLeaves.begin(); it != vc->mLeaves.end(); ++ it)
-                if (*it != l)
-                        pvs.AddPvs(*(*it)->mPvs);
-        return pvs.GetSize();
-}
-#endif
-
-// computes pvs1 minus pvs2
-inline int SubtractedPvsSize(ObjectPvs pvs1, const ObjectPvs &pvs2)
-{
-        return pvs1.SubtractPvs(pvs2);
-}
-
-
-float VspBspTree::GetShuffledVcCost(BspLeaf *leaf, BspViewCell *vc1, BspViewCell *vc2) const
-{
-        //const int pvs1 = SubtractedPvsSize(vc1, leaf, *leaf->mPvs);
-        const int pvs1 = SubtractedPvsSize(vc1->GetPvs(), *leaf->mPvs);
-        const int pvs2 = AddedPvsSize(vc2->GetPvs(), *leaf->mPvs);
-
-        // don't shuffle leaves with pvs > max
-        if (pvs1 + pvs2 > mViewCellsManager->GetMaxPvsSize())
-                return 1e15f;
-
-#if 1
-        float p1, p2;
-
-    if (mUseAreaForPvs)
-        {
-                p1 = vc1->GetArea() - leaf->mProbability;
-                p2 = vc2->GetArea() + leaf->mProbability;
-        }
-        else
-        {
-                p1 = vc1->GetVolume() - leaf->mProbability;
-                p2 = vc2->GetVolume() + leaf->mProbability;
-        }
-
-        const float cost1 = pvs1 * p1;
-        const float cost2 = pvs2 * p2;
-#else
-        const float cost1 = pvs1;
-        const float cost2 = pvs2;
-#endif
-
-        return cost1 + cost2;
-}
-
-
-void VspBspTree::ShuffleLeaf(BspLeaf *leaf, 
-                                                         BspViewCell *vc1, 
-                                                         BspViewCell *vc2) const
-{
-        // compute new pvs and area
-        vc1->GetPvs().SubtractPvs(*leaf->mPvs);
-        vc2->GetPvs().AddPvs(*leaf->mPvs);
-        
-        if (mUseAreaForPvs)
-        {
-                vc1->SetArea(vc1->GetArea() - leaf->mProbability);
-                vc2->SetArea(vc2->GetArea() + leaf->mProbability);
-        }
-        else
-        {
-                vc1->SetVolume(vc1->GetVolume() - leaf->mProbability);
-                vc2->SetVolume(vc2->GetVolume() + leaf->mProbability);
-        }
-
-        /// add to second view cell
-        vc2->mLeaves.push_back(leaf);
-
-        // erase leaf from old view cell
-        vector<BspLeaf *>::iterator it = vc1->mLeaves.begin();
-
-        for (; *it != leaf; ++ it);
-        vc1->mLeaves.erase(it);
-
-        /*vc1->GetPvs().mEntries.clear();
-        for (; it != vc1->mLeaves.end(); ++ it)
-        {
-                if (*it == leaf)
-                        vc1->mLeaves.erase(it);
-                else
-                        vc1->GetPvs().AddPvs(*(*it)->mPvs);
-        }*/
-
-        leaf->SetViewCell(vc2); // finally change view cell
-}
-
-
-bool VspBspTree::ShuffleLeaves(BspLeaf *leaf1, BspLeaf *leaf2) const
-{
-        BspViewCell *vc1 = leaf1->GetViewCell();
-        BspViewCell *vc2 = leaf2->GetViewCell();
-
-        float cost1, cost2;
-
-#if 1
-        if (mUseAreaForPvs)
-        {
-                cost1 = vc1->GetPvs().GetSize() * vc1->GetArea();
-                cost2 = vc2->GetPvs().GetSize() * vc2->GetArea();
-        }
-        else
-        {
-                cost1 = vc1->GetPvs().GetSize() * vc1->GetVolume();
-                cost2 = vc2->GetPvs().GetSize() * vc2->GetVolume();
-        }
-#else
-        cost1 = vc1->GetPvs().GetSize(); 
-        cost2 = vc2->GetPvs().GetSize(); 
-#endif
-
-        const float oldCost = cost1 + cost2;
-        
-        float shuffledCost1 = Limits::Infinity;
-        float shuffledCost2 = Limits::Infinity;
-
-        // the view cell should not be empty after the shuffle
-        if (vc1->mLeaves.size() > 1)
-                shuffledCost1 = GetShuffledVcCost(leaf1, vc1, vc2);
-        if (vc2->mLeaves.size() > 1)
-                shuffledCost2 = GetShuffledVcCost(leaf2, vc2, vc1);
-
-        // shuffling unsuccessful
-        if ((oldCost <= shuffledCost1) && (oldCost <= shuffledCost2))
-                return false;
-        
-        if (shuffledCost1 < shuffledCost2)
-        {
-                ShuffleLeaf(leaf1, vc1, vc2);
-                leaf1->Mail();
-        }
-        else
-        {
-                ShuffleLeaf(leaf2, vc2, vc1);
-                leaf2->Mail();
-        }
-
-        return true;
-}
-
-
 bool VspBspTree::ViewPointValid(const Vector3 &viewPoint) const
 {
@@ -3713 +2946 @@
         }
 }
-
-
-/**************************************************************************/
-/*                  BspMergeCandidate implementation                      */
-/**************************************************************************/
-
-
-BspMergeCandidate::BspMergeCandidate(BspLeaf *l1, BspLeaf *l2):
-mRenderCost(0),
-mVarianceIncr(0),
-mLeaf1(l1),
-mLeaf2(l2),
-mLeaf1Id(l1->GetViewCell()->mMailbox),
-mLeaf2Id(l2->GetViewCell()->mMailbox)
-{
-        //EvalMergeCost();
-}
-
-
-float BspMergeCandidate::GetRenderCost(ViewCell *vc) const
-{
-        if (sUseArea)
-                return vc->GetPvs().GetSize() * vc->GetArea();
-
-        return vc->GetPvs().GetSize() * vc->GetVolume();
-}
-
-
-float BspMergeCandidate::GetLeaf1Cost() const
-{
-        BspViewCell *vc = mLeaf1->GetViewCell();
-
-        return GetRenderCost(vc);
-}
-
-
-float BspMergeCandidate::GetLeaf2Cost() const
-{
-        BspViewCell *vc = mLeaf2->GetViewCell();
-
-        return GetRenderCost(vc);
-}
-
-
-int ComputeMergedPvsSize(const ObjectPvs &pvs1, const ObjectPvs &pvs2)
-{
-        int pvs = pvs1.GetSize();
-
-        // compute new pvs size
-        ObjectPvsMap::const_iterator it, it_end =  pvs1.mEntries.end();
-
-        Intersectable::NewMail();
-
-        for (it = pvs1.mEntries.begin(); it != it_end; ++ it)
-        {
-                (*it).first->Mail();
-        }
-
-        it_end = pvs2.mEntries.end();
-
-        for (it = pvs2.mEntries.begin(); it != it_end; ++ it)
-        {
-                Intersectable *obj = (*it).first;
-                if (!obj->Mailed())
-                        ++ pvs;
-        }
-
-        return pvs;
-}
-
-
-
-void BspMergeCandidate::EvalMergeCost()
-{
-        //-- compute pvs difference
-        BspViewCell *vc1 = mLeaf1->GetViewCell();
-        BspViewCell *vc2 = mLeaf2->GetViewCell();
-
-        const int newPvs = ComputeMergedPvsSize(vc1->GetPvs(), vc2->GetPvs());
-        const float newPenalty = 
-                EvalPvsPenalty(newPvs, 
-                                           sViewCellsManager->GetMinPvsSize(),
-                                           sViewCellsManager->GetMaxPvsSize());
-
-        //-- compute ratio of old cost
-        //   (i.e., added size of left and right view cell times pvs size)
-        //   to new rendering cost (i.e, size of merged view cell times pvs size)
-        const float oldCost = GetLeaf1Cost() + GetLeaf2Cost();
-
-    const float newCost = sUseArea ? 
-                (float)newPvs * (vc1->GetArea() + vc2->GetArea()) :
-                (float)newPvs * (vc1->GetVolume() + vc2->GetVolume());
-
-
-        if (newPvs > sViewCellsManager->GetMaxPvsSize()) // strong penalty if pvs size too large
-        {
-                mRenderCost = 1e15;
-        }
-        else
-        {
-                mRenderCost = newCost - oldCost;
-        }
-
-        // merge cost also takes variance into account
-
-        const float oldVar1 = GetLeaf1Variance();
-        const float oldVar2 = GetLeaf2Variance();
-
-        const float newVar = (sExpectedCost - mRenderCost) * (sExpectedCost - mRenderCost);
-
-        mVarianceIncr = (newVar - oldVar1 - oldVar2) / sNumViewCells;
-        //mMergeCost = mRenderCost + fabs(newPenalty - BspMergeCandidate::sExpectedCost) ;
-}
-
-
-void BspMergeCandidate::SetLeaf1(BspLeaf *l)
-{
-        mLeaf1 = l;
-}
-
-
-void BspMergeCandidate::SetLeaf2(BspLeaf *l)
-{
-        mLeaf2 = l;
-}
-
-
-BspLeaf *BspMergeCandidate::GetLeaf1() const
-{
-        return mLeaf1;
-}
-
-
-BspLeaf *BspMergeCandidate::GetLeaf2() const
-{
-        return mLeaf2;
-}
-
-
-bool BspMergeCandidate::Valid() const
-{
-        return
-                (mLeaf1->GetViewCell()->mMailbox == mLeaf1Id) &&
-                (mLeaf2->GetViewCell()->mMailbox == mLeaf2Id);
-}
-
-
-float BspMergeCandidate::GetMergeCost() const
-{
-        return mRenderCost * sRenderCostWeight + mVarianceIncr * (1.0f - sRenderCostWeight);
-}
-
-
-float BspMergeCandidate::GetRenderCost() const
-{
-        return mRenderCost;
-}
-
-
-float BspMergeCandidate::GetVarianceIncr() const
-{
-        return mVarianceIncr;
-}
-
-float BspMergeCandidate::GetLeaf1Variance() const
-{
-        const float leafCost = GetLeaf1Cost();
-        
-        return (sExpectedCost - leafCost) * (sExpectedCost - leafCost);
-}
-
-
-float BspMergeCandidate::GetLeaf2Variance() const
-{
-        const float leafCost = GetLeaf2Cost();
-        
-        return (sExpectedCost - leafCost) * (sExpectedCost - leafCost);
-}
-
-
-void BspMergeCandidate::SetValid()
-{
-        mLeaf1Id = mLeaf1->GetViewCell()->mMailbox;
-        mLeaf2Id = mLeaf2->GetViewCell()->mMailbox;
-
-        EvalMergeCost();
-}
-
-
-/************************************************************************/
-/*                    MergeStatistics implementation                    */
-/************************************************************************/
-
-
-void MergeStatistics::Print(ostream &app) const
-{
-        app << "===== Merge statistics ===============\n";
-
-        app << setprecision(4);
-
-        app << "#N_CTIME ( Overall time [s] )\n" << Time() << " \n";
-
-        app << "#N_CCTIME ( Collect candidates time [s] )\n" << collectTime * 1e-3f << " \n";
-
-        app << "#N_MTIME ( Merge time [s] )\n" << mergeTime * 1e-3f << " \n";
-
-        app << "#N_NODES ( Number of nodes before merge )\n" << nodes << "\n";
-
-        app << "#N_CANDIDATES ( Number of merge candidates )\n" << candidates << "\n";
-
-        app << "#N_MERGEDSIBLINGS ( Number of merged siblings )\n" << siblings << "\n";
-
-        app << "#OVERALLCOST ( overall merge cost )\n" << overallCost << "\n";
-
-        app << "#N_MERGEDNODES ( Number of merged nodes )\n" << merged << "\n";
-
-        app << "#MAX_TREEDIST ( Maximal distance in tree of merged leaves )\n" << maxTreeDist << "\n";
-
-        app << "#AVG_TREEDIST ( Average distance in tree of merged leaves )\n" << AvgTreeDist() << "\n";
-
-        app << "===== END OF BspTree statistics ==========\n";
-}

trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.h

@@ -21 +21 @@
 class ViewCellsStatistics;
 class ViewCellsManager;
-class BspMergeCandidate;
+class MergeCandidate;
 class Beam;
 
@@ -252 +252 @@
         int TreeDistance(BspNode *n1, BspNode *n2) const;
 
-        /** Merges view cells according to some cost heuristics.
-        */
-        int MergeViewCells(const VssRayContainer &rays, const ObjectContainer &objects);
-        
-        /** Refines view cells using shuffling, i.e., border leaves 
-                of two view cells are exchanged if the resulting view cells
-                are tested to be "better" than the old ones.
-                @returns number of refined view cells
-        */
-        int RefineViewCells(const VssRayContainer &rays, const ObjectContainer &objects);
-
         /** Collapses the tree with respect to the view cell partition.
                 @returns number of collapsed nodes
@@ -272 +261 @@
         ViewCell *GetViewCell(const Vector3 &point);
 
-        /** Constructs bsp rays for post processing and visualization.
-        */
-        void ConstructBspRays(vector<BspRay *> &bspRays,
-                                                  const VssRayContainer &rays);
-        
-        /** Merge view cells of leaves l1 and l2.
-        */
-        bool MergeViewCells(BspLeaf *l1, BspLeaf *l2); //const;
 
         /** Returns true if this view point is in a valid view space,
@@ -369 +350 @@
         BspNode *CollapseTree(BspNode *node, int &collapsed);
 
-        /** Shuffles the leaves, i.e., tests if exchanging
-                the leaves helps in improving the view cells.
-        */
-        bool ShuffleLeaves(BspLeaf *leaf1, BspLeaf *leaf2) const;
-
         /** Helper function revalidating the view cell leaf list after merge.
         */
@@ -573 +549 @@
 
 
-        /** Collects candidates for the merge in the merge queue.
-                @param leaves the leaves to be merged
-                @returns number of leaves in queue
-        */
-        int CollectMergeCandidates(const vector<BspLeaf *> leaves);
-        /** Collects candidates for the merge in the merge queue.
-                @returns number of leaves in queue
-        */
-        int CollectMergeCandidates(const VssRayContainer &rays);
-
+
+
+
+        
         /** Take 3 ray endpoints, where two are minimum and one a maximum
                 point or the other way round.
@@ -599 +569 @@
         Plane3 ChooseCandidatePlane3(const RayInfoContainer &rays) const;
   
-        /** Shuffles, i.e. takes border leaf from view cell 1 and adds it 
-                to view cell 2.
-        */
-        void ShuffleLeaf(BspLeaf *leaf, 
-                                         BspViewCell *vc1, 
-                                         BspViewCell *vc2) const;
-
+        /** Collects candidates for merging.
+                @param leaves the leaves to be merged
+                @returns number of leaves in queue
+        */
+        int CollectMergeCandidates(const vector<BspLeaf *> leaves, vector<MergeCandidate> &candidates);
+
+        /** Collects candidates for the merge in the merge queue.
+                @returns number of leaves in queue
+        */
+        int CollectMergeCandidates(const VssRayContainer &rays, vector<MergeCandidate> &candidates);
+        
+        
         
         /** Propagates valid flag up the tree.
@@ -620 +595 @@
         float GetMemUsage() const;
 
-        /** Calculates cost for merge of view cell 1 and 2.
-        */
-        float GetShuffledVcCost(BspLeaf *leaf, BspViewCell *vc1, BspViewCell *vc2) const;
-
-        void ExportMergedViewCells(ViewCellContainer &viewCells, 
-                                                           const ObjectContainer &objects,
-                                                           const int nViewCells);
+
 
         /// Pointer to the root of the tree
@@ -658 +627 @@
         float mTermMinAccRayLength;
 
-        ofstream mStats;
+        
 
         //-- termination criteria for axis aligned split
@@ -701 +670 @@
         /// maximal number of view cells
         int mMaxViewCells;
-        /// minimal number of view cells
-        int mMergeMinViewCells;
-        /// maximal cost ratio for the merge
-        float mMergeMaxCostRatio;
+        
 
         // if rays should be stored in leaves
@@ -716 +682 @@
         vector<SortableEntry> *mSplitCandidates;
 
-
-        typedef priority_queue<BspMergeCandidate> MergeQueue;
-
-        MergeQueue mMergeQueue;
-
-        /// if rays should be used to collect merge candidates
-        bool mUseRaysForMerge;
-        
+        
+        float mRenderCostWeight;
         /// View cell corresponding to the space outside the valid view space
         BspViewCell *mOutOfBoundsCell;
-
-        int mCurrentViewCellsId;
 
         /// maximal tree memory
@@ -733 +691 @@
         /// the tree is out of memory
         bool mOutOfMemory;
-        /// if merge visualization should be shown
-        bool mExportMergedViewCells;
-        /// if merge statistics should be exported
-        bool mExportMergeStats;
-
+        
+        
 private:
-        
-        ViewCellContainer mOldViewCells;
-        ViewCellContainer mNewViewCells;
+
 
         static const float sLeastRaySplitsTable[5];
@@ -758 +711 @@
 };
 
-/**
-        Candidate for leaf merging based on priority.
-*/
-class BspMergeCandidate
-{  
-        friend class VspBspTree;
-
-public:
-
-        BspMergeCandidate(BspLeaf *l1, BspLeaf *l2);
-
-        /** If this merge pair is still valid.
-        */
-        bool Valid() const;
-
-        /** Sets this merge candidate to be valid.
-        */
-        void SetValid();
-
-        friend bool operator<(const BspMergeCandidate &leafa, const BspMergeCandidate &leafb)
-        {
-                return leafb.GetMergeCost() < leafa.GetMergeCost();
-        }
-
-        void SetLeaf1(BspLeaf *l);
-        void SetLeaf2(BspLeaf *l);
-
-        BspLeaf *GetLeaf1() const;
-        BspLeaf *GetLeaf2() const;
-
-        /** Merge cost of this candidate pair.
-        */
-        float GetMergeCost() const;
-
-        /** Render cost of this candidate.
-        */
-        float GetRenderCost() const;
-
-        /** returns increase in variance of this view cell.
-        */
-        float GetVarianceIncr() const;
-
-        /** Returns cost of leaf 1.
-        */
-        float GetLeaf1Cost() const;
-        
-        /** Returns cost of leaf 2.
-        */
-        float GetLeaf2Cost() const;
-
-        /** Variance of leaf1
-        */
-        float GetLeaf1Variance() const;
-
-        /** Variance of leaf2
-        */
-        float GetLeaf2Variance() const;
-
-        /// overall cost used to normalize cost ratio
-        static float sOverallCost;
-        static float sExpectedCost;
-        static float sVariance;
-
-        static int sNumViewCells;
-
-        // weights between variance and render cost increase (must between zero and one)
-        static float sRenderCostWeight;
-
-        /// if area or volume should be used for the merge heuristics
-        static bool sUseArea;
-
-        /// pointer to view cells manager
-        static ViewCellsManager *sViewCellsManager;
-
-protected:
-
-        
-        /** Evaluates the merge costs of the leaves.
-        */
-        void EvalMergeCost();
-
-        /** render cost of a view cell.
-        */
-        float GetRenderCost(ViewCell *vc) const;
-        
-        int mLeaf1Id;
-        int mLeaf2Id;
-
-        /// render cost increase by this merge
-        float mRenderCost;
-        /// increase / decrease of variance
-        float mVarianceIncr;
-
-        BspLeaf *mLeaf1;
-        BspLeaf *mLeaf2;
-};
-
-
-class MergeStatistics: public StatisticsBase
-{
-public:
-        
-        int merged;
-        int siblings;
-        int candidates;
-        int nodes;
-
-        int accTreeDist;
-        int maxTreeDist;
-        
-        Real collectTime;
-        Real mergeTime;
-
-        Real overallCost;
-
-        // Constructor
-        MergeStatistics() 
-        {
-                Reset();
-        }
-        
-        double AvgTreeDist() const {return (double)accTreeDist / (double)merged;}; 
-
-        void Reset() 
-        {
-                nodes = 0;
-                merged = 0;
-                siblings = 0;
-                candidates = 0;
-        
-                accTreeDist = 0;
-                maxTreeDist = 0;
-
-                collectTime = 0;
-                mergeTime = 0;
-                overallCost = 0;
-        }
-
-        void Print(ostream &app) const;
-
-        friend ostream &operator<<(ostream &s, const MergeStatistics &stat) 
-        {
-                stat.Print(s);
-                return s;
-        } 
-};
+
+
 
 #endif

trunk/VUT/GtpVisibilityPreprocessor/src/VspKdTree.cpp

@@ -30 +30 @@
 // Static variables
 int VspKdLeaf::sMailId = 0;
-int MergeCandidate::sMaxPvsSize = 150;
-float MergeCandidate::sOverallCost = Limits::Small;
+int VspKdMergeCandidate::sMaxPvsSize = 150;
+float VspKdMergeCandidate::sOverallCost = Limits::Small;
 #define USE_FIXEDPOINT_T 0
 
@@ -430 +430 @@
         environment->GetFloatValue("VspKdTree.PostProcess.maxCostRatio", mMergeMaxCostRatio);
         environment->GetIntValue("VspKdTree.PostProcess.maxPvsSize",
-                                                         MergeCandidate::sMaxPvsSize);
+                                                         VspKdMergeCandidate::sMaxPvsSize);
 
         environment->GetBoolValue("VspKdTree.splitUseOnlyDrivingAxis", mOnlyDrivingAxis);
@@ -2173 +2173 @@
         vc->SetArea(GetBBox(leaf).SurfaceArea());
 
-        vc->mLeaves.push_back(leaf);
+        vc->mLeaf = leaf;
 
         for (it = leaf->GetRays().begin(); it != it_end; ++ it)
@@ -2200 +2200 @@
         // if merge was unsuccessful
         if (!vc) return false;
-
+// TODO
+#if VC_HISTORY
         // set new size of view cell
         vc->SetVolume(fVc->GetVolume() + bVc->GetVolume());
@@ -2223 +2224 @@
                 vc->mLeaves.push_back(*it);
         }
-
+#endif
         vc->Mail();
 
@@ -2235 +2236 @@
 void VspKdTree::CollectMergeCandidates()
 {
-        MergeCandidate::sOverallCost = 0;
+        VspKdMergeCandidate::sOverallCost = 0;
         vector<VspKdLeaf *> leaves;
 
@@ -2256 +2257 @@
                 // no leaf is part of two merge candidates
                 leaf->Mail();
-                MergeCandidate::sOverallCost += 
+                VspKdMergeCandidate::sOverallCost += 
                         vc->GetVolume() * vc->GetPvs().GetSize();
                 vector<VspKdLeaf *> neighbors;
@@ -2266 +2267 @@
                 for (nit = neighbors.begin(); nit != nit_end; ++ nit)
                 {
-                        mMergeQueue.push(MergeCandidate(leaf, *nit));
+                        mMergeQueue.push(VspKdMergeCandidate(leaf, *nit));
                 }
         }
@@ -2273 +2274 @@
 void VspKdTree::CollectMergeCandidates(const vector<VspKdRay *> &rays)
 {
-        MergeCandidate::sOverallCost = 0;
+        VspKdMergeCandidate::sOverallCost = 0;
 
         vector<VspKdIntersection>::const_iterator iit;
@@ -2299 +2300 @@
                         leaf->Mail
                         // TODO: how to sort out doubles?
-                        MergeCandidate mc = MergeCandidate(leaf, previousLeaf);
+                        VspKdMergeCandidate mc = VspKdMergeCandidate(leaf, previousLeaf);
                         mMergeQueue.push(mc);
 
-                        MergeCandidate::sOverallCost += mc.GetLeaf1Cost();
-                        MergeCandidate::sOverallCost += mc.GetLeaf2Cost();
+                        VspKdMergeCandidate::sOverallCost += mc.GetLeaf1Cost();
+                        VspKdMergeCandidate::sOverallCost += mc.GetLeaf2Cost();
 
                         previousLeaf = leaf;
@@ -2321 +2322 @@
         while (!mMergeQueue.empty() && (vcSize > mMergeMinViewCells) &&
                    (mMergeQueue.top().GetMergeCost() < 
-                    mMergeMaxCostRatio * MergeCandidate::sOverallCost))
+                    mMergeMaxCostRatio * VspKdMergeCandidate::sOverallCost))
         {
                 //Debug << "mergecost: " << mergeQueue.top().GetMergeCost() / 
-                //MergeCandidate::sOverallCost << " " << mMergeMaxCostRatio << endl;
-                MergeCandidate mc = mMergeQueue.top();
+                //VspKdMergeCandidate::sOverallCost << " " << mMergeMaxCostRatio << endl;
+                VspKdMergeCandidate mc = mMergeQueue.top();
                 mMergeQueue.pop();
 
@@ -2340 +2341 @@
                         -- vcSize;
                         // increase absolute merge cost
-                        MergeCandidate::sOverallCost += mc.GetMergeCost();
+                        VspKdMergeCandidate::sOverallCost += mc.GetMergeCost();
                 }
                 // merge candidate not valid, because one of the leaves was already
@@ -2378 +2379 @@
 
                         VspKdViewCell *viewCell = leaf->GetViewCell();
-
+#if VC_HISTORY
                         if (!viewCell->Mailed())
                         {
@@ -2386 +2387 @@
 
                         viewCell->mLeaves.push_back(leaf);
+#endif
                 }
                 else
@@ -2468 +2470 @@
         while (!mMergeQueue.empty())
         {
-                MergeCandidate mc = mMergeQueue.top();
+                VspKdMergeCandidate mc = mMergeQueue.top();
                 mMergeQueue.pop();
 
@@ -2501 +2503 @@
 
 
-float GetShuffledVcCost(VspKdLeaf *leaf, VspKdViewCell *vc1, VspKdViewCell *vc2)
+float EvalShuffleCost(VspKdLeaf *leaf, VspKdViewCell *vc1, VspKdViewCell *vc2)
 {
         const int pvs1 = SubtractedPvsSize(vc1->GetPvs(), *leaf->mPvs);
@@ -2521 +2523 @@
 {
         // compute new pvs and area
+        //      TODO
+#if VC_HISTORY
         vc1->GetPvs().SubtractPvs(*leaf->mPvs);
         vc2->GetPvs().AddPvs(*leaf->mPvs);
@@ -2537 +2541 @@
 
         leaf->SetViewCell(vc2);  // finally change view cell
+#endif
 }
 
@@ -2554 +2559 @@
 
         // the view cell should not be empty after the shuffle
-        if (vc1->mLeaves.size() > 1)
-                shuffledCost1 = GetShuffledVcCost(leaf1, vc1, vc2);
+//todo
+        /*      if (vc1->mLeaves.size() > 1)
+                shuffledCost1 = EvalShuffleCost(leaf1, vc1, vc2);
         if (vc2->mLeaves.size() > 1)
-                shuffledCost2 = GetShuffledVcCost(leaf2, vc2, vc1);
-
-        // shuffling unsuccessful
+                shuffledCost2 = EvalShuffleCost(leaf2, vc2, vc1);
+
+*/      // shuffling unsuccessful
         if ((oldCost <= shuffledCost1) && (oldCost <= shuffledCost2))
                 return false;
@@ -2581 +2587 @@
 
 /*********************************************************************/
-/*                MergeCandidate implementation                      */
+/*                VspKdMergeCandidate implementation                      */
 /*********************************************************************/
 
 
-MergeCandidate::MergeCandidate(VspKdLeaf *l1, VspKdLeaf *l2):
+VspKdMergeCandidate::VspKdMergeCandidate(VspKdLeaf *l1, VspKdLeaf *l2):
 mMergeCost(0),
 mLeaf1(l1),
@@ -2595 +2601 @@
 }
 
-float MergeCandidate::GetLeaf1Cost() const
+float VspKdMergeCandidate::GetLeaf1Cost() const
 {
         VspKdViewCell *vc = mLeaf1->GetViewCell();
@@ -2601 +2607 @@
 }
 
-float MergeCandidate::GetLeaf2Cost() const
+float VspKdMergeCandidate::GetLeaf2Cost() const
 {
         VspKdViewCell *vc = mLeaf2->GetViewCell();
@@ -2607 +2613 @@
 }
 
-void MergeCandidate::EvalMergeCost()
+void VspKdMergeCandidate::EvalMergeCost()
 {
         //-- compute pvs difference
@@ -2630 +2636 @@
 }
 
-void MergeCandidate::SetLeaf1(VspKdLeaf *l)
+void VspKdMergeCandidate::SetLeaf1(VspKdLeaf *l)
 {
         mLeaf1 = l;
 }
 
-void MergeCandidate::SetLeaf2(VspKdLeaf *l)
+void VspKdMergeCandidate::SetLeaf2(VspKdLeaf *l)
 {
         mLeaf2 = l;
@@ -2641 +2647 @@
 
 
-VspKdLeaf *MergeCandidate::GetLeaf1()
+VspKdLeaf *VspKdMergeCandidate::GetLeaf1()
 {
         return mLeaf1;
@@ -2647 +2653 @@
 
 
-VspKdLeaf *MergeCandidate::GetLeaf2()
+VspKdLeaf *VspKdMergeCandidate::GetLeaf2()
 {
         return mLeaf2;
@@ -2653 +2659 @@
 
 
-bool MergeCandidate::Valid() const
+bool VspKdMergeCandidate::Valid() const
 {
         return
@@ -2661 +2667 @@
 
 
-float MergeCandidate::GetMergeCost() const
+float VspKdMergeCandidate::GetMergeCost() const
 {
         return mMergeCost;
@@ -2667 +2673 @@
 
 
-void MergeCandidate::SetValid()
+void VspKdMergeCandidate::SetValid()
 {
         mLeaf1Id = mLeaf1->GetViewCell()->mMailbox;

trunk/VUT/GtpVisibilityPreprocessor/src/VspKdTree.h

@@ -43 +43 @@
         Candidate for leaf merging based on priority.
 */
-class MergeCandidate
+class VspKdMergeCandidate
 {  
 public:
 
-        MergeCandidate(VspKdLeaf *l1, VspKdLeaf *l2);
+        VspKdMergeCandidate(VspKdLeaf *l1, VspKdLeaf *l2);
 
         /** Computes PVS difference between the leaves.
@@ -61 +61 @@
         void SetValid();
 
-        friend bool operator<(const MergeCandidate &leafa, const MergeCandidate &leafb)
+        friend bool operator<(const VspKdMergeCandidate &leafa, const VspKdMergeCandidate &leafb)
         {
                 return leafb.GetMergeCost() < leafa.GetMergeCost();
@@ -850 +850 @@
         ViewCellsManager *mViewCellsManager;
 
-        priority_queue<MergeCandidate> mMergeQueue;
+        priority_queue<VspKdMergeCandidate> mMergeQueue;
 
 

trunk/VUT/GtpVisibilityPreprocessor/src/X3dExporter.cpp

@@ -850 +850 @@
                 {
                         ViewCell *vc = dynamic_cast<BspLeaf *>(node)->GetViewCell();
-     
+#if 0     
                         // set the mesh material according to the ray density
                         if (vc->mPassingRays.mRays) 
@@ -860 +860 @@
                                 mForcedMaterial.mDiffuseColor.g = 1.0f - mForcedMaterial.mDiffuseColor.r;
                                 ExportViewCell(vc);
+
                         }
-                } else 
+#endif
+                } 
+                else 
                 {
                         BspInterior *interior = (BspInterior *)node;