Changeset 580 for trunk/VUT/GtpVisibilityPreprocessor/src/ViewCell.cpp

Timestamp:

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

Author:

mattausch

Message:

implemented variance
started implementing merge history

File:

• trunk/VUT/GtpVisibilityPreprocessor/src/ViewCell.cpp (modified) (6 diffs)

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";
+}