source: trunk/VUT/GtpVisibilityPreprocessor/src/ViewCell.cpp @ 582

#include "ViewCell.h"
#include "Mesh.h"
#include "Intersectable.h"
#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(): 
MeshInstance(NULL), 
mPiercingRays(0),
mArea(-1),
mVolume(-1),
mValid(true),
mParent(NULL),
mTimeStamp(0)
{
}

ViewCell::ViewCell(Mesh *mesh): 
MeshInstance(mesh), 
mPiercingRays(0),
mArea(-1),
mVolume(-1),
mValid(true),
mParent(NULL),
mTimeStamp(0)
{
}


const ObjectPvs &ViewCell::GetPvs() const
{
        return mPvs;
}

ObjectPvs &ViewCell::GetPvs()
{
        return mPvs;
}


int ViewCell::Type() const 
{ 
        return VIEW_CELL; 
}


float ViewCell::GetVolume() const
{
        return mVolume;
}


void ViewCell::SetVolume(float volume) 
{
        mVolume = volume;
}


void ViewCell::SetMesh(Mesh *mesh)
{
        mMesh = mesh;
}


void ViewCell::UpdateViewCellsStats(ViewCellsStatistics &vcStat)
{
        ++ vcStat.viewCells;
                
        const int pvsSize = mPvs.GetSize();

        vcStat.pvs += pvsSize;

        if (pvsSize == 0)
                ++ vcStat.emptyPvs;

        if (pvsSize > vcStat.maxPvs)
                vcStat.maxPvs = pvsSize;

        if (pvsSize < vcStat.minPvs)
                vcStat.minPvs = pvsSize;

        if (!mValid)
                ++ vcStat.invalid;
}


float ViewCell::GetArea() const
{
        return mArea;
}


void ViewCell::SetArea(float area) 
{
        mArea = area;
}


void ViewCell::SetValid(const bool valid)
{
        mValid = valid;
}


bool ViewCell::GetValid() const
{
        return mValid;
}


/*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
{
        app << "=========== View Cells Statistics ===============\n";

        app << setprecision(4);

        //app << "#N_CTIME  ( Construction time [s] )\n" << Time() << " \n";

        app << "#N_OVERALLPVS ( objects in PVS )\n" << pvs << endl;

        app << "#N_PMAXPVS ( largest PVS )\n" << maxPvs << endl;

        app << "#N_PMINPVS ( smallest PVS )\n" << minPvs << endl;

        app << "#N_PAVGPVS ( average PVS )\n" << AvgPvs() << endl;

        app << "#N_PEMPTYPVS ( view cells with empty PVS )\n" << emptyPvs << endl;

        app << "#N_VIEWCELLS ( number of view cells)\n" << viewCells << endl;

        app << "#N_AVGLEAVES (average number of leaves per view cell )\n" << AvgLeaves() << endl;

        app << "#N_MAXLEAVES ( maximal number of leaves per view cell )\n" << maxLeaves << endl;
        
        app << "#N_INVALID ( number of invalid view cells )\n" << invalid << endl;

        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);
        environment->GetFloatValue("ViewCells.maxStaticMemory", mMaxMemory);

        //-- merge options
        environment->GetFloatValue("ViewCells.PostProcess.renderCostWeight", mRenderCostWeight);
        environment->GetIntValue("ViewCells.PostProcess.minViewCells", mMergeMinViewCells);
        environment->GetFloatValue("ViewCells.PostProcess.maxCostRatio", mMergeMaxCostRatio);
        

        Debug << "========= view cell tree options ================\n";
        Debug << "minimum view cells: " << mMergeMinViewCells << endl;
        Debug << "max cost ratio: " << mMergeMaxCostRatio << endl;
        Debug << "max memory: " << mMaxMemory << endl;

        MergeCandidate::sRenderCostWeight = mRenderCostWeight;

        mStats.open("mergeStats.log");
}


// return memory usage in MB
float ViewCellsTree::GetMemUsage() const
{
        return 0;
                /*(sizeof(ViewCellsTree) +
                 mBspStats.Leaves() * sizeof(BspLeaf) +
                 mBspStats.Interior() * sizeof(BspInterior) +
                 mBspStats.accumRays * sizeof(RayInfo)) / (1024.0f * 1024.0f);*/
}


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)
{
        mNumActiveViewCells = (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 &activeViewCells = 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 realNumActiveViewCells = mNumActiveViewCells;
        
        // maximal ratio of old expected render cost to expected render
        // when the the render queue has to be reset.
        float avgCostMaxDeviation;
        int maxMergesPerPass;
        int numMergedViewCells = 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())// && (realNumActiveViewCells > mMergeMinViewCells))
        {
                //-- reset merge queue if the ratio of current expected cost / real expected cost
                //   too small or after a given number of merges
                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;
                        mNumActiveViewCells = realNumActiveViewCells;
                        
                        const int numMergedViewCells = UpdateActiveViewCells(activeViewCells);
                
                        // recompute priorities => reset render cost
                    ResetMergeQueue();

                        
                        Debug << "Values after reset: "  
                                  << " erc: " << mExpectedCost 
                                  << " avg: " << mAvgRenderCost 
                                  << " dev: " << mDeviation << endl;

                        if (mExportMergedViewCells)
                        {
                                ExportMergedViewCells(activeViewCells, objects, numMergedViewCells);
                        }
                }

#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
                // NOTE: do I really still need this? probably cannot happen!!
                if (mc.mLeftViewCell == mc.mRightViewCell)
                        continue;

                if (mc.IsValid())
                {
                        ViewCell::NewMail();
                                                
                        -- realNumActiveViewCells;
                        ++ 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)realNumActiveViewCells;
                        
                        const float currentMergeCost = mc.GetMergeCost();

                        // merge the view cells of leaf1 and leaf2
                        int pvsDiff;
                        ViewCellInterior *mergedVc = 
                                MergeViewCells(mc.mLeftViewCell, mc.mRightViewCell, pvsDiff);

                        totalPvs += pvsDiff;

                        // set timestamp
                        mergedVc->SetTimeStamp(mergeStats.merged);

                        realAvgRenderCost = (float)totalPvs / (float)realNumActiveViewCells;
#if VC_HISTORY
                        if (mc.mLeftViewCell->IsSibling(mc.mRightViewCell))
                                ++ mergeStats.siblings;
#endif
                        if (((mergeStats.merged % statsOut) == 0) || 
                                (realNumActiveViewCells == mMergeMinViewCells))
                        {
                                cout << "merged " << mergeStats.merged << " view cells" << endl;

                                mStats 
                                        << "#Pass\n" << pass << endl
                                        << "#Merged\n" << mergeStats.merged << endl 
                                        << "#Viewcells\n" << realNumActiveViewCells << endl 
                                        << "#CurrentCost\n" << currentMergeCost << endl
                                        << "#RelativeCost\n" << currentMergeCost / mOverallCost << endl
                                        << "#CurrentPvs\n" << mc.GetLeftViewCell()->GetPvs().GetSize() << endl
                                        << "#MergedSiblings\n" << mergeStats.siblings << endl
                                        << "#AvgTreeDist\n" << mergeStats.AvgTreeDist() << endl
                                        << "#UsedExpectedCost\n" << mExpectedCost << endl
                                        << "#RealExpectedCost\n" << realExpectedCost << endl
                                        << "#RealAvgRenderCost\n" << realAvgRenderCost << endl
                                        << "#AvgRenderCost\n" << mAvgRenderCost << endl
                                        << "#expectedCostRatio\n" << mExpectedCost / realExpectedCost << endl
                                        << "#Deviation\n" << mDeviation / (float)realNumActiveViewCells << endl
                                        << "#TotalDeviation\n" << mDeviation<< endl;
                        }
                }
                else
                { 
                        // merge candidate not valid, because one of the leaves was already
                        // merged with another one => validate and reinsert into queue
                        if (ValidateMergeCandidate(mc))
                        {
                                EvalMergeCost(mc);
                                mMergeQueue.push(mc);
                        }
                }
        }

        // adjust stats and reset queue one final time
        mExpectedCost = realExpectedCost;
        mAvgRenderCost = realAvgRenderCost;
        mNumActiveViewCells = realNumActiveViewCells;

        UpdateActiveViewCells(activeViewCells);
        ResetMergeQueue();

        // create a root node if the merge was not done till root level,
        // else take the single node as new root
        if ((int)activeViewCells.size() > 1)
        {
                Debug << "creating root of view cell hierarchy for " << (int)activeViewCells.size() << " view cells" << endl;
                for (int i = 0;  i < activeViewCells.size(); ++ i){
                        Debug << "here233 " << activeViewCells[i]->GetParent() << endl;
                        Debug << "here233 " << activeViewCells[i] << endl;
                }
                ViewCellInterior *root = mViewCellsManager->MergeViewCells(activeViewCells);

                root->SetTimeStamp(mergeStats.merged + 1);
                mRoot = root;
        }
        else if ((int)activeViewCells.size() == 1)
        {
                Debug << "setting root of the merge history" << endl;
                mRoot = activeViewCells[0];
        }

        // TODO delete because makes no sense here
        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;
}


ViewCell *ViewCellsTree::GetRoot()
{
        return mRoot;
}


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
                if (ValidateMergeCandidate(mc))
                {
                        EvalMergeCost(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::UpdateActiveViewCells(ViewCellContainer &viewCells)
{
        int numMergedViewCells = 0;

        Debug << "updating active vc: " << viewCells.size() << endl;
        // find all already merged view cells and remove them from view cells
                
        // sort out all view cells which are not active anymore, i.e., they
        // were already part of a merge
        int i = 0;

        ViewCell::NewMail();

        while (1)
        {
                // remove all merged view cells from end of the vector
                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]->GetParent())
                        swap(viewCells[i], viewCells.back());
                
                viewCells[i ++]->Mail();
        }


        // add new view cells to container only if they don't have been 
        // merged in the mean time
        ViewCellContainer::const_iterator ait, ait_end = mMergedViewCells.end();
        for (ait = mMergedViewCells.begin(); ait != ait_end; ++ ait)
        {
                ViewCell *vc = mMergedViewCells.back();
                if (!vc->GetParent() && !vc->Mailed())
                {
                        vc->Mail();
                        viewCells.push_back(vc);
                        ++ numMergedViewCells;
                }
        }

        mMergedViewCells.clear();

        // 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();
        
        return numMergedViewCells;
}


void ViewCellsTree::ExportMergedViewCells(ViewCellContainer &viewCells, 
                                                                                  const ObjectContainer &objects,
                                                                                  const int numMergedViewCells)
{
        

        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() - numMergedViewCells))
                        {
                                //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();


        // new view cells are stored in this vector
        mMergedViewCells.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)mNumActiveViewCells;
}


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)mNumActiveViewCells;
        }

    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)mNumActiveViewCells;
        }

    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);
}


bool ViewCellsTree::ValidateMergeCandidate(MergeCandidate &mc) const
{
        while (mc.mLeftViewCell->mParent)
        {
                mc.mLeftViewCell = mc.mLeftViewCell->mParent;
        }

        while (mc.mRightViewCell->mParent)
        {
                mc.mRightViewCell = mc.mRightViewCell->mParent;
        }

        return mc.mLeftViewCell != mc.mRightViewCell;
}


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)mNumActiveViewCells;
        else
                newDev = fabs(mExpectedCost - newCost) / (float)mNumActiveViewCells;
        
        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;
        
        while (!tstack.empty())
        {
                ViewCell *viewCell = tstack.top();
                tstack.pop();

                if (viewCell->IsLeaf())
                {
                        
                }
                else
                {
                        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(viewCell);                        
                        ComputeCommonPvs(interior);
                }
        }
}


void ViewCellsTree::CollectBestViewCellSet(ViewCellContainer &viewCells, 
                                                                                   const int numViewCells)
{
        TraversalQueue tqueue;
        tqueue.push(mRoot);
        
        while (!tqueue.empty())
        {
                ViewCell *vc = tqueue.top();
                
                // save the view cells if it is a leaf or if enough view cells have already been traversed
                // because of the priority queue, this will be the optimal set of v
                if (vc->IsLeaf() || ((viewCells.size() + tqueue.size()) >= numViewCells))
                {
                        viewCells.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)
                        {
                                tqueue.push(*it);
                        }
                }

                tqueue.pop();
        }
}
        

void ViewCellsTree::ComputeCommonPvs(ViewCellInterior *interior)
{
        Intersectable::NewMail();

        ViewCellContainer::const_iterator cit, cit_end = interior->mChildren.end();

        ObjectPvsMap::const_iterator oit;

        // mail all objects in the leaf sets
        for (cit = interior->mChildren.begin(); cit != cit_end; ++ cit)
        {
                ViewCell *vc = *cit;

                ObjectPvsMap::const_iterator oit_end = vc->GetPvs().mEntries.end();

                for (oit = vc->GetPvs().mEntries.begin(); oit != oit_end; ++ oit)
                {
                        if (!(*oit).first->Mailed())
                                (*oit).first->Mail();
                        
                        (*oit).first->IncMail();
                }
        }

        interior->GetPvs().mEntries.clear();
    cit_end = interior->mChildren.end();
        
        // only the objects which are present in all leaf pvs 
        // should remain in the parent pvs

        for (cit = interior->mChildren.begin(); cit != cit_end; ++ cit)
        {
                ViewCell *vc = *cit;

                ObjectPvsMap::const_iterator oit_end = vc->GetPvs().mEntries.end();

                for (oit = vc->GetPvs().mEntries.begin(); oit != oit_end; ++ oit)
                {
                        if ((*oit).first->Mailed((int)interior->mChildren.size()))
                        {       
                                interior->GetPvs().AddSample((*oit).first, (*oit).second.mSumPdf);
                                //(*oit)->remove();
                        }
                }
        }

        // delete all the objects from the leaf sets which were moved
        // to parent pvs
        ObjectPvsMap::const_iterator oit_end = interior->GetPvs().mEntries.end();

        for (oit = interior->GetPvs().mEntries.begin(); oit != oit_end; ++ oit)
        {
                for (cit = interior->mChildren.begin(); cit != cit_end; ++ cit)
                {
                        (*cit)->GetPvs().RemoveSample((*oit).first, Limits::Infinity);
                }
        }
}


/**************************************************************************/
/*                     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";
}