source: GTP/trunk/Lib/Vis/Preprocessing/src/ViewCell.cpp @ 2124

Revision 2124, 60.2 KB checked in by mattausch, 17 years ago (diff)
RevLine 
[1010]1#include <time.h>
2#include <iomanip>
3#include <stack>
4
5
[235]6#include "ViewCell.h"
7#include "Mesh.h"
[308]8#include "Intersectable.h"
[1121]9#include "KdTree.h"
[235]10#include "Triangle3.h"
[580]11#include "common.h"
12#include "Environment.h"
13#include "ViewCellsManager.h"
14#include "Exporter.h"
[1614]15#include "BvHierarchy.h"
[580]16
[235]17
[1614]18
[863]19namespace GtpVisibilityPreprocessor {
[580]20
21
[955]22
[580]23template <typename T> class myless
24{
25public:
26        bool operator() (T v1, T v2) const
27        {
[600]28                return (v1->GetMergeCost() < v2->GetMergeCost());
[580]29        }
30};
31
32
[1121]33typedef priority_queue<ViewCell *, vector<ViewCell *>,
34                                           myless<vector<ViewCell *>::value_type> > TraversalQueue;
[580]35
[1867]36  int ViewCell::sMailId = 10000;//2147483647;
37  int ViewCell::sReservedMailboxes = 1;
[580]38
[882]39
[580]40float MergeCandidate::sRenderCostWeight = 0;
41
42
43// pvs penalty can be different from pvs size
[1709]44inline static float EvalPvsPenalty(const float pvs,
45                                                                   const float lower,
46                                                                   const float upper)
[580]47{
48        // clamp to minmax values
[728]49        if (pvs < lower)
[580]50                return (float)lower;
51        if (pvs > upper)
52                return (float)upper;
[752]53
[580]54        return (float)pvs;
55}
56
[1586]57/** Counts contribution of the view cell to the pvs.
58*/
59inline int CountPvsContribution(ViewCell *vc)
[585]60{
61        int count = 0;
62
[1742]63        ObjectPvsIterator pit = vc->GetPvs().GetIterator();
64
65        while (pit.HasMoreEntries())
[585]66        {
[2117]67                Intersectable *obj = pit.Next();
[1742]68
[2117]69                if (!obj->Mailed())
[585]70                {
[2117]71                        obj->Mail();
[585]72                        ++ count;
73                }
74        }
75
76        return count;
77}
78
[1233]79
[729]80/// Fast computation of merged pvs size
[1742]81static float ComputeMergedPvsCost(const ObjectPvs &pvs1,
82                                                                  const ObjectPvs &pvs2)
[580]83{
[729]84        // add first pvs
[1709]85        float pvs = (float)pvs1.GetSize();
[580]86
87        Intersectable::NewMail();
88
[729]89        // mail all objects in first pvs
[1742]90        ObjectPvsIterator pit = pvs1.GetIterator();
91
92        while (pit.HasMoreEntries())
[580]93        {
[2117]94                pit.Next()->Mail();
[580]95        }
96
[1742]97        pit = pvs2.GetIterator();
[580]98
[1742]99        while (pit.HasMoreEntries())
[580]100        {
[2117]101                if (!pit.Next()->Mailed())
[580]102                        ++ pvs;
103        }
104
105        return pvs;
106}
107
108
[478]109ViewCell::ViewCell():
110MeshInstance(NULL),
[551]111mArea(-1),
112mVolume(-1),
[580]113mValid(true),
114mParent(NULL),
[600]115mMergeCost(0),
[1709]116mPvsCost(0),
[1160]117mEntriesInPvs(0),
[1877]118mPvsSizeValid(false),
119mFilteredPvsSize(0)
[265]120{
[1570]121        mId = -100;
[265]122}
[235]123
[478]124ViewCell::ViewCell(Mesh *mesh):
125MeshInstance(mesh),
[551]126mArea(-1),
127mVolume(-1),
[580]128mValid(true),
129mParent(NULL),
[600]130mMergeCost(0),
[1709]131mPvsCost(0),
[1877]132mPvsSizeValid(false),
133mFilteredPvsSize(0)
[1297]134//mMailbox(0)
[372]135{
[1570]136        mId = -100;
[372]137}
138
[503]139
[1551]140ViewCell::~ViewCell()
141{
142}
143
144
[469]145const ObjectPvs &ViewCell::GetPvs() const
[419]146{
[2015]147  return mPvs;
[419]148}
149
[752]150
[469]151ObjectPvs &ViewCell::GetPvs()
[372]152{
[2015]153  return mPvs;
[372]154}
155
[503]156
[880]157void ViewCell::SetPvs(const ObjectPvs &pvs)
158{
159        mPvs = pvs;
160}
161
162
[235]163int ViewCell::Type() const
164{
[308]165        return VIEW_CELL;
[235]166}
167
[503]168
[469]169float ViewCell::GetVolume() const
170{
171        return mVolume;
172}
173
[478]174
[469]175void ViewCell::SetVolume(float volume)
176{
177        mVolume = volume;
178}
179
[503]180
181void ViewCell::SetMesh(Mesh *mesh)
182{
183        mMesh = mesh;
184}
185
186
[478]187float ViewCell::GetArea() const
188{
189        return mArea;
190}
191
192
193void ViewCell::SetArea(float area)
194{
195        mArea = area;
196}
197
198
[752]199void ViewCell::SetColor(const RgbColor &color)
200{
201        mColor = color;
202}
203
204
205RgbColor ViewCell::GetColor() const
206{
207        return mColor;
208}
209
210
[547]211void ViewCell::SetValid(const bool valid)
212{
[564]213        mValid = valid;
[547]214}
215
216
217bool ViewCell::GetValid() const
218{
219        return mValid;
220}
221
222
[580]223void ViewCell::SetParent(ViewCellInterior *parent)
224{
225        mParent = parent;
226}
227
228
229bool ViewCell::IsRoot() const
230{
231        return !mParent;
232}
233
234
235ViewCellInterior *ViewCell::GetParent() const
236{
237        return mParent;
238}
239
240
[600]241void ViewCell::SetMergeCost(const float mergeCost)
[580]242{
[600]243        mMergeCost = mergeCost;
[580]244}
245
246
[728]247float ViewCell::GetRenderCost() const
248{
[1709]249        return mPvsCost * GetVolume();
[728]250}
251
252
[600]253float ViewCell::GetMergeCost() const
[580]254{
[600]255        return mMergeCost;
[580]256}
257
[1002]258
259bool ViewCell::AddPvsSample(Intersectable *sample,
260                                                        const float pdf,
261                                                        float &contribution)
[1772]262{
[2124]263        const bool result = mPvs.AddSample(sample, pdf);
[1586]264        // have to recompute pvs size
265        mPvsSizeValid = false;
[1002]266
267        return result;
268}
269
270
[1133]271
[462]272/************************************************************************/
[580]273/*                class ViewCellInterior implementation                 */
274/************************************************************************/
275
276
277ViewCellInterior::ViewCellInterior()
278{
279}
280
281
282ViewCellInterior::~ViewCellInterior()
283{
284        ViewCellContainer::const_iterator it, it_end = mChildren.end();
285
286        for (it = mChildren.begin(); it != it_end; ++ it)
[1545]287        {
[580]288                delete (*it);
[1545]289        }
[580]290}
291
292
293ViewCellInterior::ViewCellInterior(Mesh *mesh):
294ViewCell(mesh)
295{
296}
297
298
299bool ViewCellInterior::IsLeaf() const
300{
301        return false;
302}
303
304
[650]305void ViewCellInterior::SetupChildLink(ViewCell *vc)
[580]306{
[650]307    mChildren.push_back(vc);
[1002]308    vc->SetParent(this);
[580]309}
310
311
[586]312void ViewCellInterior::RemoveChildLink(ViewCell *l)
313{
314        // erase leaf from old view cell
315        ViewCellContainer::iterator it = mChildren.begin();
[580]316
[586]317        for (; (*it) != l; ++ it);
318        if (it == mChildren.end())
319                Debug << "error" << endl;
320        else
321                mChildren.erase(it);
322}
323
[703]324
[1286]325void ViewCellInterior::ReplaceChildLink(ViewCell *prev, ViewCell *cur)
326{
327        // erase leaf from old view cell
328        ViewCellContainer::iterator it = mChildren.begin();
329
330        for (; (*it) != prev; ++ it);
331        if (it == mChildren.end())
332        {
333                Debug << "error: child link not found" << endl;
334        }
335        else
336        {
337                (*it) = cur;
338        }
339}
340
341
[1551]342
[580]343/************************************************************************/
[462]344/*                class ViewCellsStatistics implementation              */
345/************************************************************************/
346
[580]347
[463]348void ViewCellsStatistics::Print(ostream &app) const
349{
350        app << "=========== View Cells Statistics ===============\n";
351
352        app << setprecision(4);
353
354        //app << "#N_CTIME  ( Construction time [s] )\n" << Time() << " \n";
355
[1709]356        app << "#N_OVERALLPVS ( cost of the PVS )\n" << pvsCost << endl;
[463]357
[1709]358        //app << "#N_PVSENTRIES ( entries in the PVS)\n" << pvsEntries << endl;
359
[463]360        app << "#N_PMAXPVS ( largest PVS )\n" << maxPvs << endl;
361
362        app << "#N_PMINPVS ( smallest PVS )\n" << minPvs << endl;
363
364        app << "#N_PAVGPVS ( average PVS )\n" << AvgPvs() << endl;
365
[485]366        app << "#N_PEMPTYPVS ( view cells with empty PVS )\n" << emptyPvs << endl;
[463]367
368        app << "#N_VIEWCELLS ( number of view cells)\n" << viewCells << endl;
369
370        app << "#N_AVGLEAVES (average number of leaves per view cell )\n" << AvgLeaves() << endl;
371
372        app << "#N_MAXLEAVES ( maximal number of leaves per view cell )\n" << maxLeaves << endl;
373       
[564]374        app << "#N_INVALID ( number of invalid view cells )\n" << invalid << endl;
375
[463]376        app << "========== End of View Cells Statistics ==========\n";
[580]377}
378
379
380/*************************************************************************/
381/*                    class ViewCellsTree implementation                 */
382/*************************************************************************/
383
384
[1004]385ViewCellsTree::ViewCellsTree(ViewCellsManager *vcm):
[580]386mRoot(NULL),
387mUseAreaForPvs(false),
[584]388mViewCellsManager(vcm),
[752]389#if 0
390mViewCellsStorage(PVS_IN_INTERIORS)
391#else
392mViewCellsStorage(PVS_IN_LEAVES)
393#endif
[580]394{
[1264]395        ReadEnvironment();
396        MergeCandidate::sRenderCostWeight = mRenderCostWeight;
397}
398
399
400ViewCellsTree::ViewCellsTree():
401mRoot(NULL),
402mUseAreaForPvs(false),
403mViewCellsManager(NULL),
404#if 0
405mViewCellsStorage(PVS_IN_INTERIORS)
406#else
407mViewCellsStorage(PVS_IN_LEAVES)
408#endif
409{
410        ReadEnvironment();
411        MergeCandidate::sRenderCostWeight = mRenderCostWeight;
412}
413
414
415void ViewCellsTree::ReadEnvironment()
416{
[1004]417        Environment::GetSingleton()->GetBoolValue("ViewCells.Visualization.exportMergedViewCells", mExportMergedViewCells);
418        Environment::GetSingleton()->GetFloatValue("ViewCells.maxStaticMemory", mMaxMemory);
[580]419
420        //-- merge options
[1004]421        Environment::GetSingleton()->GetFloatValue("ViewCells.PostProcess.renderCostWeight", mRenderCostWeight);
422        Environment::GetSingleton()->GetIntValue("ViewCells.PostProcess.minViewCells", mMergeMinViewCells);
423        Environment::GetSingleton()->GetFloatValue("ViewCells.PostProcess.maxCostRatio", mMergeMaxCostRatio);
424        Environment::GetSingleton()->GetBoolValue("ViewCells.PostProcess.refine", mRefineViewCells);   
[582]425
[1004]426        Environment::GetSingleton()->GetIntValue("ViewCells.PostProcess.maxMergesPerPass", mMaxMergesPerPass);
427        Environment::GetSingleton()->GetFloatValue("ViewCells.PostProcess.avgCostMaxDeviation", mAvgCostMaxDeviation);
[586]428
[938]429        Debug << "============= view cell tree options ================\n";
[582]430        Debug << "minimum view cells: " << mMergeMinViewCells << endl;
431        Debug << "max cost ratio: " << mMergeMaxCostRatio << endl;
432        Debug << "max memory: " << mMaxMemory << endl;
[586]433        Debug << "refining view cells: " << mRefineViewCells << endl;
[1027]434        Debug << "=========== end view cell tree options ===============\n";
[580]435}
436
437
[582]438// return memory usage in MB
439float ViewCellsTree::GetMemUsage() const
440{
[752]441        // TODO
[582]442        return 0;
443                /*(sizeof(ViewCellsTree) +
444                 mBspStats.Leaves() * sizeof(BspLeaf) +
445                 mBspStats.Interior() * sizeof(BspInterior) +
446                 mBspStats.accumRays * sizeof(RayInfo)) / (1024.0f * 1024.0f);*/
447}
448
449
[736]450int ViewCellsTree::GetNumInitialViewCells(ViewCell *vc) const
[580]451{
452        int vcSize = 0;
453
454        stack<ViewCell *> tstack;
455
456        tstack.push(vc);
457
458        while (!tstack.empty())
459        {
460                ViewCell *vc = tstack.top();
461                tstack.pop();
462
463                if (vc->IsLeaf())
464                {
465                        ++ vcSize;
466                }
467                else
468                {
[2017]469                        ViewCellInterior *interior = static_cast<ViewCellInterior *>(vc);
[1233]470
[580]471                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
[1233]472                       
[580]473                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
[1233]474                        {
[580]475                                tstack.push(*it);
[1233]476                        }
[580]477                       
478                }
479        }
480
481        return vcSize;
482}
483
484
485void ViewCellsTree::CollectLeaves(ViewCell *vc, ViewCellContainer &leaves) const
486{
487        stack<ViewCell *> tstack;
488
489        tstack.push(vc);
490
491        while (!tstack.empty())
492        {
493                ViewCell *vc = tstack.top();
494                tstack.pop();
495
496                if (vc->IsLeaf())
497                {
498                        leaves.push_back(vc);
499                }
500                else
501                {
[2017]502                        ViewCellInterior *interior = static_cast<ViewCellInterior *>(vc);
[580]503                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
[664]504
[580]505                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
[664]506                        {
[580]507                                tstack.push(*it);
[664]508                        }
[580]509                }
510        }
511}
512
513
514ViewCellsTree::~ViewCellsTree()
[2003]515{
[580]516        DEL_PTR(mRoot);
517}
518
519
520int ViewCellsTree::ConstructMergeTree(const VssRayContainer &rays,
521                                                                          const ObjectContainer &objects)
522{
[582]523        mNumActiveViewCells = (int)mViewCellsManager->GetViewCells().size();
[580]524
525        float variance = 0;
[1709]526        float totalPvs = 0;
[600]527        float totalRenderCost = 0;
[580]528
[1786]529        //////////////////
[580]530        //-- compute statistics values of initial view cells
[1786]531
[600]532        mViewCellsManager->EvaluateRenderStatistics(totalRenderCost,
[580]533                                                                                                mExpectedCost,
534                                                                                                mDeviation,
535                                                                                                variance,
536                                                                                                totalPvs,
537                                                                                                mAvgRenderCost);
538
[1786]539        /////////////
[580]540        //-- fill merge queue
541        vector<MergeCandidate> candidates;
542
543        mViewCellsManager->CollectMergeCandidates(rays, candidates);
[703]544
[580]545        while(!candidates.empty())
546        {
547                MergeCandidate mc = candidates.back();
548                candidates.pop_back();
549                EvalMergeCost(mc);
550                mMergeQueue.push(mc);
551        }
552
553        Debug << "************************* merge ***********************************" << endl; 
554        Debug << "deviation: " << mDeviation << endl;
555        Debug << "avg render cost: " << mAvgRenderCost << endl;
[600]556        Debug << "expected cost: " << mExpectedCost << endl;
[580]557
558
559        ViewCellsManager::PvsStatistics pvsStats;
560        mViewCellsManager->GetPvsStatistics(pvsStats);
561
[605]562        //static float expectedValue = pvsStats.avgPvs;
[580]563       
[881]564        //-- the current view cells are kept in this container
565        //-- we start with the current view cells from the view cell manager.
566        //-- The active view cells will change with subsequent merges
[752]567       
[720]568        // todo: should rather take initial view cells
569    ViewCellContainer &activeViewCells = mViewCellsManager->GetViewCells();
570       
[752]571       
[580]572        ViewCell::NewMail();
573
574        MergeStatistics mergeStats;
575        mergeStats.Start();
576       
577        long startTime = GetTime();
578
579        mergeStats.collectTime = TimeDiff(startTime, GetTime());
580        mergeStats.candidates = (int)mMergeQueue.size();
581        startTime = GetTime();
582
583        // frequency stats are updated
[650]584        const int statsOut = 500;
[734]585       
[580]586        // passes are needed for statistics, because we don't want to record
587        // every merge
588        int pass = 0;
589        int mergedPerPass = 0;
590        float realExpectedCost = mExpectedCost;
591        float realAvgRenderCost = mAvgRenderCost;
[582]592        int realNumActiveViewCells = mNumActiveViewCells;
[580]593       
594        // maximal ratio of old expected render cost to expected render
595        // when the the render queue has to be reset.
[582]596        int numMergedViewCells = 0;
[938]597               
[580]598
599        cout << "actual merge starts now ... " << endl;
[604]600
[580]601        //-- use priority queue to merge leaf pairs
[612]602
[881]603        while (!mMergeQueue.empty())
[580]604        {
605                //-- reset merge queue if the ratio of current expected cost / real expected cost
606                //   too small or after a given number of merges
[938]607                if ((mergedPerPass > mMaxMergesPerPass) ||
608                        (mAvgCostMaxDeviation > mAvgRenderCost / realAvgRenderCost))
[580]609                {
610                        Debug << "************ reset queue *****************\n"
[938]611                                  << "ratios: " << mAvgCostMaxDeviation
[580]612                                  << " real avg render cost " << realAvgRenderCost << " average render cost " << mAvgRenderCost
[938]613                                  << " merged per pass : " << mergedPerPass << " of maximal " << mMaxMergesPerPass << endl;
[580]614
615                        Debug << "Values before reset: " 
616                                  << " erc: " << mExpectedCost
617                                  << " avgrc: " << mAvgRenderCost
618                                  << " dev: " << mDeviation << endl;
619       
620                        // adjust render cost
621                        ++ pass;
622
623                        mergedPerPass = 0;
624                        mExpectedCost = realExpectedCost;
625                        mAvgRenderCost = realAvgRenderCost;
[582]626                        mNumActiveViewCells = realNumActiveViewCells;
[580]627                       
[582]628                        const int numMergedViewCells = UpdateActiveViewCells(activeViewCells);
629               
[1603]630                        /////////////////
631                        //-- reset / refine the view cells
[720]632                        //-- priorities are recomputed
633                        //-- the candidates are put back into merge queue
[1603]634
[586]635                        if (mRefineViewCells)
636                                RefineViewCells(rays, objects);
637                        else
638                                ResetMergeQueue();
[580]639
640                        Debug << "Values after reset: " 
641                                  << " erc: " << mExpectedCost
642                                  << " avg: " << mAvgRenderCost
643                                  << " dev: " << mDeviation << endl;
644
645                        if (mExportMergedViewCells)
646                        {
[582]647                                ExportMergedViewCells(activeViewCells, objects, numMergedViewCells);
[580]648                        }
649                }
650
651
652                MergeCandidate mc = mMergeQueue.top();
653                mMergeQueue.pop();
654       
[710]655                // both view cells equal because of previous merges
[582]656                // NOTE: do I really still need this? probably cannot happen!!
[580]657                if (mc.mLeftViewCell == mc.mRightViewCell)
658                        continue;
659
660                if (mc.IsValid())
661                {
662                        ViewCell::NewMail();
[600]663
664                        //-- update statistical values
[582]665                        -- realNumActiveViewCells;
[580]666                        ++ mergeStats.merged;
667                        ++ mergedPerPass;
668
[600]669                        const float renderCostIncr = mc.GetRenderCost();
670                        const float mergeCostIncr = mc.GetMergeCost();
[580]671
[600]672                        totalRenderCost += renderCostIncr;
[580]673                        mDeviation += mc.GetDeviationIncr();
[710]674
675                                               
676                        //-- merge the view cells of leaf1 and leaf2
[1709]677                        float pvsDiff;
[580]678                        ViewCellInterior *mergedVc =
[1709]679                                MergeViewCells(mc.mLeftViewCell, mc.mRightViewCell, pvsDiff);   
[580]680
[600]681                        // total render cost and deviation has changed
682                        // real expected cost will be larger than expected cost used for the
683                        // cost heuristics, but cannot recompute costs on each increase of the
684                        // expected cost
[580]685                        totalPvs += pvsDiff;
[600]686                        realExpectedCost = totalRenderCost / (float)realNumActiveViewCells;
687                        realAvgRenderCost = (float)totalPvs / (float)realNumActiveViewCells;
688       
[801]689                        // set merge cost to this node for priority traversal
[837]690                        mergedVc->SetMergeCost(totalRenderCost);
691                       
692                        // check if "siblings (back and front node of the same parent)
[1706]693                        if (0) ++ mergeStats.siblings;
694
695                        // set the cost for rendering a view cell
[608]696                        mergedVc->SetCost(realExpectedCost);
[607]697
[650]698                        if ((mergeStats.merged % statsOut) == 0)
[580]699                                cout << "merged " << mergeStats.merged << " view cells" << endl;
700
701                }
702                else
703                {
704                        // merge candidate not valid, because one of the leaves was already
705                        // merged with another one => validate and reinsert into queue
[582]706                        if (ValidateMergeCandidate(mc))
707                        {
708                                EvalMergeCost(mc);
709                                mMergeQueue.push(mc);
710                        }
[580]711                }
[612]712               
[580]713        }
714
715        // adjust stats and reset queue one final time
716        mExpectedCost = realExpectedCost;
717        mAvgRenderCost = realAvgRenderCost;
[582]718        mNumActiveViewCells = realNumActiveViewCells;
[580]719
[582]720        UpdateActiveViewCells(activeViewCells);
[580]721
[586]722        // refine view cells and reset costs
723        if (mRefineViewCells)
724                RefineViewCells(rays, objects);
725        else
726                ResetMergeQueue();
727
[708]728
[580]729        // create a root node if the merge was not done till root level,
730        // else take the single node as new root
[582]731        if ((int)activeViewCells.size() > 1)
[580]732        {
[587]733                Debug << "creating root of view cell hierarchy for "
734                          << (int)activeViewCells.size() << " view cells" << endl;
[612]735               
[582]736                ViewCellInterior *root = mViewCellsManager->MergeViewCells(activeViewCells);
[710]737       
738                ViewCellContainer::const_iterator it, it_end = root->mChildren.end();
739
740                for (it = root->mChildren.begin(); it != it_end; ++ it)
741                        (*it)->SetParent(root);
742       
[600]743                root->SetMergeCost(totalRenderCost);
[608]744                // $$JB keep this 0 temporarilly
745                root->SetCost(0.0f);
[612]746
[580]747                mRoot = root;
748        }
[710]749        // normal case
750        else if (!activeViewCells.empty())
[580]751        {
[582]752                Debug << "setting root of the merge history" << endl;
753                mRoot = activeViewCells[0];
[580]754        }
[752]755        else
756        {
757                Debug << "big error, root is NULL" << endl;
758        }
[708]759       
[644]760        //-- empty merge queue just in case
[600]761        while (!mMergeQueue.empty())
762        {
763                mMergeQueue.pop();
764        }
[837]765
[1706]766        // test if computed volumes are correct
767        Debug << "volume of the root view cell: " << mRoot->GetVolume()
768                  << " " << mViewCellsManager->GetViewSpaceBox().GetVolume() << endl;
[837]769       
770        // TODO: delete because makes no sense here
[580]771        mergeStats.expectedRenderCost = realExpectedCost;
772        mergeStats.deviation = mDeviation;
773
774        // we want to optimize this heuristics
775        mergeStats.heuristics =
776                mDeviation * (1.0f - mRenderCostWeight) +
777                mExpectedCost * mRenderCostWeight;
778
779        mergeStats.mergeTime = TimeDiff(startTime, GetTime());
780        mergeStats.Stop();
781        Debug << mergeStats << endl << endl;
782
[608]783        // assign colors for the view cells so that at least one is always consistent
784        AssignRandomColors();
[708]785
[580]786        //TODO: should return sample contributions?
787        return mergeStats.merged;
788}
789
790
[584]791ViewCell *ViewCellsTree::GetRoot() const
[581]792{
793        return mRoot;
794}
795
796
[580]797void ViewCellsTree::ResetMergeQueue()
798{
799        cout << "reset merge queue ... ";
800       
801        vector<MergeCandidate> buf;
802        buf.reserve(mMergeQueue.size());
803                       
804       
805        // store merge candidates in intermediate buffer
806        while (!mMergeQueue.empty())
807        {
808                MergeCandidate mc = mMergeQueue.top();
809                mMergeQueue.pop();
810               
811                // recalculate cost
[582]812                if (ValidateMergeCandidate(mc))
813                {
814                        EvalMergeCost(mc);
815                        buf.push_back(mc);                             
816                }
[580]817        }
818
819        vector<MergeCandidate>::const_iterator bit, bit_end = buf.end();
820
821        // reinsert back into queue
822        for (bit = buf.begin(); bit != bit_end; ++ bit)
823        {     
824                mMergeQueue.push(*bit);
825        }
826
827        cout << "finished" << endl;
828}
829
830
[1002]831float ViewCellsTree::ComputeMergedPvsCost(const ObjectPvs &pvs1,
832                                                                                  const ObjectPvs &pvs2) const
833{
834        // computes render cost of merge
835        float renderCost = 0;
836
837        // compute new pvs size
838        Intersectable::NewMail();
839
[1742]840        ObjectPvsIterator pit = pvs1.GetIterator();
841
[1002]842        // first mail all objects in first pvs
[1742]843        while (pit.HasMoreEntries())
[1002]844        {
[2117]845                Intersectable *obj = pit.Next();
[1002]846
847                obj->Mail();
848                renderCost += mViewCellsManager->EvalRenderCost(obj);
849        }
850
[1742]851        ObjectPvsIterator pit2 = pvs2.GetIterator();
[1002]852
[1742]853        while (pit2.HasMoreEntries())
[1002]854        {
[2117]855                Intersectable *obj = pit2.Next();
856               
[1002]857                // test if object already considered   
858                if (!obj->Mailed())
859                {
860                        renderCost += mViewCellsManager->EvalRenderCost(obj);
861                }
862        }
863
864        return renderCost;
865}
866
867
[582]868int ViewCellsTree::UpdateActiveViewCells(ViewCellContainer &viewCells)
[580]869{
[582]870        int numMergedViewCells = 0;
[580]871
[584]872        Debug << "updating active vc: " << (int)viewCells.size() << endl;
[1141]873       
874        // find all already merged view cells and remove them from the
875        // container view cells
[582]876               
877        // sort out all view cells which are not active anymore, i.e., they
878        // were already part of a merge
[580]879        int i = 0;
880
[582]881        ViewCell::NewMail();
882
[580]883        while (1)
884        {
[582]885                // remove all merged view cells from end of the vector
886                while (!viewCells.empty() && (viewCells.back()->GetParent()))
[580]887                {
888                        viewCells.pop_back();
889                }
890
891                // all merged view cells have been found
[710]892                if (i >= (int)viewCells.size())
[580]893                        break;
894
[710]895                // already merged this view cell, put it to end of vector
[582]896                if (viewCells[i]->GetParent())
[580]897                        swap(viewCells[i], viewCells.back());
898               
[752]899                // mail view cell that it has not been merged
[710]900                viewCells[i]->Mail();
901
902                // increase loop counter
903                ++ i;
[580]904        }
905
[582]906
[580]907        // add new view cells to container only if they don't have been
908        // merged in the mean time
[582]909        ViewCellContainer::const_iterator ait, ait_end = mMergedViewCells.end();
[752]910
[582]911        for (ait = mMergedViewCells.begin(); ait != ait_end; ++ ait)
[580]912        {
[582]913                ViewCell *vc = mMergedViewCells.back();
914                if (!vc->GetParent() && !vc->Mailed())
[580]915                {
[582]916                        vc->Mail();
917                        viewCells.push_back(vc);
918                        ++ numMergedViewCells;
[580]919                }
920        }
921
[752]922        // dispose old merged view cells
[582]923        mMergedViewCells.clear();
924
[580]925        // update standard deviation
926        ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
927       
928        mDeviation = 0;
929
930        for (vit = viewCells.begin(); vit != vit_end; ++ vit)
931        {
[1709]932                const float lower = (float)mViewCellsManager->GetMinPvsSize();
933                const float upper = (float)mViewCellsManager->GetMaxPvsSize();
[752]934
[1707]935                const float penalty = EvalPvsPenalty((*vit)->GetPvs().EvalPvsCost(), lower, upper);
[580]936               
937                mDeviation += fabs(mAvgRenderCost - penalty);
938        }
939
940        mDeviation /= (float)viewCells.size();
[582]941       
942        return numMergedViewCells;
[580]943}
944
945
946void ViewCellsTree::ExportMergedViewCells(ViewCellContainer &viewCells,
947                                                                                  const ObjectContainer &objects,
[582]948                                                                                  const int numMergedViewCells)
[580]949{
950       
951
952        char s[64];
953
954        sprintf(s, "merged_viewcells%07d.x3d", (int)viewCells.size());
955        Exporter *exporter = Exporter::GetExporter(s);
956
957        if (exporter)
958        {
959                cout << "exporting " << (int)viewCells.size() << " merged view cells ... ";
960                exporter->ExportGeometry(objects);
961                //Debug << "vc size " << (int)viewCells.size() << " merge queue size: " << (int)mMergeQueue.size() << endl;
962                ViewCellContainer::const_iterator it, it_end = viewCells.end();
963
964                int i = 0;
965                for (it = viewCells.begin(); it != it_end; ++ it)
966                {
967                        Material m;
968                        // assign special material to new view cells
969                        // new view cells are on the back of container
[582]970                        if (i ++ >= (viewCells.size() - numMergedViewCells))
[580]971                        {
972                                //m = RandomMaterial();
973                                m.mDiffuseColor.r = RandomValue(0.5f, 1.0f);
974                                m.mDiffuseColor.g = RandomValue(0.5f, 1.0f);
975                                m.mDiffuseColor.b = RandomValue(0.5f, 1.0f);
976                        }
977                        else
978                        {
979                                float col = RandomValue(0.1f, 0.4f);
980                                m.mDiffuseColor.r = col;
981                                m.mDiffuseColor.g = col;
982                                m.mDiffuseColor.b = col;
983                        }
984
985                        exporter->SetForcedMaterial(m);
[1416]986                        mViewCellsManager->ExportViewCellGeometry(exporter, *it, NULL, NULL);
[580]987                }
[1416]988
[580]989                delete exporter;
990                cout << "finished" << endl;
991        }
992}
993
994
995// TODO: should be done in view cells manager
[1141]996ViewCellInterior *ViewCellsTree::MergeViewCells(ViewCell *left,
997                                                                                                ViewCell *right,
[1709]998                                                                                                float &pvsDiff) //const
[580]999{
[1141]1000        // create merged view cell
1001        ViewCellInterior *vc =
1002                mViewCellsManager->MergeViewCells(left, right);
[580]1003
1004        // if merge was unsuccessful
1005        if (!vc) return NULL;
1006
[752]1007        // set to the new parent view cell
[1141]1008        left->SetParent(vc);
1009        right->SetParent(vc);
[710]1010
[1141]1011       
[580]1012        if (mUseAreaForPvs)
[710]1013        {
[1141]1014                // set new area of view cell
1015                // not not correct, but costly to compute real area!!
1016                vc->SetArea(left->GetArea() + right->GetArea());
[710]1017        }
[580]1018        else
[1141]1019        {       // set new volume of view cell
1020                vc->SetVolume(left->GetVolume() + right->GetVolume());
[602]1021        }
[710]1022
1023       
[580]1024        // important so other merge candidates sharing this view cell
1025        // are notified that the merge cost must be updated!!
1026        vc->Mail();
1027
[1707]1028        const float pvs1 = left->GetPvs().EvalPvsCost();
1029        const float pvs2 = right->GetPvs().EvalPvsCost();
[580]1030
1031
[1141]1032        // the new view cells are stored in this container
[582]1033        mMergedViewCells.push_back(vc);
[580]1034
[1707]1035        pvsDiff = vc->GetPvs().EvalPvsCost() - pvs1 - pvs2;
[580]1036
[752]1037
[1141]1038        // don't store pvs in interior cells, just a scalar
[752]1039        if (mViewCellsStorage == PVS_IN_LEAVES)
1040        {
[1168]1041                // set scalars
1042                mViewCellsManager->UpdateScalarPvsSize(left,
[1707]1043                                left->GetPvs().EvalPvsCost(),
[1586]1044                                left->GetPvs().GetSize());
[1168]1045                       
[1141]1046                // remove pvs, we don't store interior pvss
1047                if (!left->IsLeaf())
1048                {
1049                        left->GetPvs().Clear();
1050                }
1051
[1168]1052                // set scalars
1053                mViewCellsManager->UpdateScalarPvsSize(right,
[1707]1054                        right->GetPvs().EvalPvsCost(),
[1168]1055                        right->GetPvs().GetSize());
1056
[1141]1057                right->mPvsSizeValid = true;
[752]1058               
[1141]1059                // remove pvs, we don't store interior pvss
1060                if (!right->IsLeaf())
1061                {
1062                        right->GetPvs().Clear();
1063                }
1064        }
[752]1065
[580]1066        return vc;
1067}
1068
1069
[586]1070int ViewCellsTree::RefineViewCells(const VssRayContainer &rays,
1071                                                                   const ObjectContainer &objects)
[580]1072{
1073        Debug << "refining " << (int)mMergeQueue.size() << " candidates " << endl;
[586]1074
1075        // intermediate buffer for shuffled view cells
1076        vector<MergeCandidate> buf;
1077        buf.reserve(mMergeQueue.size());
1078                       
[580]1079        // Use priority queue of remaining leaf pairs
1080        // The candidates either share the same view cells or
1081        // are border leaves which share a boundary.
1082        // We test if they can be shuffled, i.e.,
1083        // either one leaf is made part of one view cell or the other
1084        // leaf is made part of the other view cell. It is tested if the
1085        // remaining view cells are "better" than the old ones.
1086       
[586]1087        const int numPasses = 3;
[580]1088        int pass = 0;
1089        int passShuffled = 0;
1090        int shuffled = 0;
1091        int shuffledViewCells = 0;
1092
1093        ViewCell::NewMail();
1094       
[586]1095        while (!mMergeQueue.empty())
[580]1096        {
[586]1097                MergeCandidate mc = mMergeQueue.top();
1098                mMergeQueue.pop();
[580]1099
[586]1100                // both view cells equal or already shuffled
1101                if ((mc.GetLeftViewCell() == mc.GetRightViewCell()) ||
1102                        mc.GetLeftViewCell()->IsLeaf() || mc.GetRightViewCell()->IsLeaf())
1103                {                       
1104                        continue;
1105                }
[580]1106
[586]1107                // candidate for shuffling
1108                const bool wasShuffled = ShuffleLeaves(mc);
[580]1109               
[586]1110                // shuffled or put into other queue for further refine
1111                if (wasShuffled)
1112                {
1113                        ++ passShuffled;
1114
1115                        if (!mc.GetLeftViewCell()->Mailed())
[580]1116                        {
[586]1117                                mc.GetLeftViewCell()->Mail();
1118                                ++ shuffledViewCells;
[580]1119                        }
[586]1120                        if (!mc.GetRightViewCell()->Mailed())
[580]1121                        {
[586]1122                                mc.GetRightViewCell()->Mail();
1123                                ++ shuffledViewCells;
[580]1124                        }
1125                }
1126
[586]1127                // put back into intermediate vector
1128                buf.push_back(mc);
[580]1129        }
1130
[586]1131
1132        //-- in the end, the candidates must be in the mergequeue again
1133        //   with the correct cost
1134
1135        cout << "reset merge queue ... ";
1136       
1137       
1138        vector<MergeCandidate>::const_iterator bit, bit_end = buf.end();
1139       
1140        for (bit = buf.begin(); bit != bit_end; ++ bit)
1141        {   
1142                MergeCandidate mc = *bit;
1143                // recalculate cost
1144                if (ValidateMergeCandidate(mc))
1145                {
1146                        EvalMergeCost(mc);
1147                        mMergeQueue.push(mc);   
1148                }
[580]1149        }
1150
[586]1151        cout << "finished" << endl;
1152
[580]1153        return shuffledViewCells;
1154}
1155
1156
[2100]1157inline int AddedPvsSize(const ObjectPvs &pvs1, const ObjectPvs &pvs2)
[580]1158{
[1740]1159        ObjectPvs interPvs;
1160        ObjectPvs::Merge(interPvs, pvs1, pvs2);
1161
1162        return (int)interPvs.GetSize();
[580]1163}
1164
1165
1166// recomputes pvs size minus pvs of leaf l
1167#if 0
1168inline int SubtractedPvsSize(BspViewCell *vc, BspLeaf *l, const ObjectPvs &pvs2)
1169{
1170        ObjectPvs pvs;
1171        vector<BspLeaf *>::const_iterator it, it_end = vc->mLeaves.end();
1172        for (it = vc->mLeaves.begin(); it != vc->mLeaves.end(); ++ it)
1173                if (*it != l)
1174                        pvs.AddPvs(*(*it)->mPvs);
1175        return pvs.GetSize();
1176}
1177#endif
1178
1179
1180// computes pvs1 minus pvs2
1181inline int SubtractedPvsSize(ObjectPvs pvs1, const ObjectPvs &pvs2)
1182{
1183        return pvs1.SubtractPvs(pvs2);
1184}
1185
1186
1187float ViewCellsTree::EvalShuffleCost(ViewCell *leaf,
[586]1188                                                                         ViewCellInterior *vc1,
1189                                                                         ViewCellInterior *vc2) const
[580]1190{
1191        //const int pvs1 = SubtractedPvsSize(vc1, leaf, *leaf->mPvs);
[1709]1192        const float pvs1 = (float)SubtractedPvsSize(vc1->GetPvs(), leaf->GetPvs());
1193        const float pvs2 = (float)AddedPvsSize(vc2->GetPvs(), leaf->GetPvs());
[580]1194
[1709]1195        const float lowerPvsLimit = (float)mViewCellsManager->GetMinPvsSize();
1196        const float upperPvsLimit = (float)mViewCellsManager->GetMaxPvsSize();
[580]1197
1198        const float pvsPenalty1 =
1199                EvalPvsPenalty(pvs1, lowerPvsLimit, upperPvsLimit);
1200
1201        const float pvsPenalty2 =
1202                EvalPvsPenalty(pvs2, lowerPvsLimit, upperPvsLimit);
1203
1204
1205        // don't shuffle leaves with pvs > max
1206        if (0 && (pvs1 + pvs2 > mViewCellsManager->GetMaxPvsSize()))
1207        {
1208                return 1e20f;
1209        }
1210
1211        float p1, p2;
1212
1213    if (mUseAreaForPvs)
1214        {
1215                p1 = vc1->GetArea() - leaf->GetArea();
1216                p2 = vc2->GetArea() + leaf->GetArea();
1217        }
1218        else
1219        {
1220                p1 = vc1->GetVolume() - leaf->GetVolume();
1221                p2 = vc2->GetVolume() + leaf->GetVolume();
1222        }
1223
1224        const float renderCost1 = pvsPenalty1 * p1;
1225        const float renderCost2 = pvsPenalty2 * p2;
1226
1227        float dev1, dev2;
1228
1229        if (1)
1230        {
1231                dev1 = fabs(mAvgRenderCost - pvsPenalty1);
1232                dev2 = fabs(mAvgRenderCost - pvsPenalty2);
1233        }
1234        else
1235        {
1236                dev1 = fabs(mExpectedCost - renderCost1);
1237                dev2 = fabs(mExpectedCost - renderCost2);
1238        }
1239       
1240        return mRenderCostWeight * (renderCost1 + renderCost2) +
[582]1241                  (1.0f - mRenderCostWeight) * (dev1 + dev2) / (float)mNumActiveViewCells;
[580]1242}
1243
1244
1245void ViewCellsTree::ShuffleLeaf(ViewCell *leaf,
[586]1246                                                                ViewCellInterior *vc1,
1247                                                                ViewCellInterior *vc2) const
[580]1248{
1249        // compute new pvs and area
[586]1250        // TODO change
[580]1251        vc1->GetPvs().SubtractPvs(leaf->GetPvs());
1252       
[1740]1253        ObjectPvs interPvs;
1254        ObjectPvs::Merge(interPvs, vc2->GetPvs(), leaf->GetPvs());
1255        vc2->SetPvs(interPvs);
1256
[580]1257        if (mUseAreaForPvs)
1258        {
1259                vc1->SetArea(vc1->GetArea() - leaf->GetArea());
1260                vc2->SetArea(vc2->GetArea() + leaf->GetArea());
1261        }
1262        else
1263        {
1264                vc1->SetVolume(vc1->GetVolume() - leaf->GetVolume());
1265                vc2->SetVolume(vc2->GetVolume() + leaf->GetVolume());
1266        }
1267
[586]1268       
[2017]1269        ViewCellInterior *p = static_cast<ViewCellInterior *>(leaf->GetParent());
[580]1270
[586]1271        p->RemoveChildLink(leaf);
1272        vc2->SetupChildLink(leaf);
[580]1273}
1274
1275
[586]1276bool ViewCellsTree::ShuffleLeaves(MergeCandidate &mc) const
[580]1277{
1278        float cost1, cost2;
1279
[2017]1280        ViewCellInterior *vc1 = static_cast<ViewCellInterior *>(mc.GetLeftViewCell());
1281        ViewCellInterior *vc2 = static_cast<ViewCellInterior *>(mc.GetRightViewCell());
[586]1282
1283        ViewCell *leaf1 = mc.GetInitialLeftViewCell();
1284        ViewCell *leaf2 = mc.GetInitialRightViewCell();
1285
[580]1286        //-- first test if shuffling would decrease cost
[586]1287        cost1 = GetCostHeuristics(vc1);
1288        cost2 = GetCostHeuristics(vc2);
[580]1289
1290        const float oldCost = cost1 + cost2;
1291       
1292        float shuffledCost1 = Limits::Infinity;
1293        float shuffledCost2 = Limits::Infinity;
1294
[586]1295        if (leaf1)
1296                shuffledCost1 = EvalShuffleCost(leaf1, vc1, vc2);       
1297        if (leaf2)
1298                shuffledCost2 = EvalShuffleCost(leaf2, vc2, vc1);
[580]1299
1300        // if cost of shuffle is less than old cost => shuffle
1301        if ((oldCost <= shuffledCost1) && (oldCost <= shuffledCost2))
1302                return false;
1303       
1304        if (shuffledCost1 < shuffledCost2)
1305        {
[586]1306                if (leaf1)
1307                        ShuffleLeaf(leaf1, vc1, vc2);
1308                mc.mInitialLeftViewCell = NULL;
[580]1309        }
1310        else
1311        {
[586]1312                if (leaf2)
1313                        ShuffleLeaf(leaf2, vc2, vc1);
1314                mc.mInitialRightViewCell = NULL;
[580]1315        }
[586]1316
[580]1317        return true;
1318}
1319
1320
1321float ViewCellsTree::GetVariance(ViewCell *vc) const
1322{
[1709]1323        const float upper = (float)mViewCellsManager->GetMaxPvsSize();
1324        const float lower = (float)mViewCellsManager->GetMinPvsSize();
[580]1325
1326        if (1)
1327        {
[752]1328                const float penalty =
[1709]1329                        EvalPvsPenalty(GetPvsCost(vc), lower, upper);
[1141]1330
[752]1331                return (mAvgRenderCost - penalty) * (mAvgRenderCost - penalty) /
1332                        (float)mNumActiveViewCells;
[580]1333        }
1334
1335    const float leafCost = GetRenderCost(vc);
1336        return (mExpectedCost - leafCost) * (mExpectedCost - leafCost);
1337}
1338
1339
1340float ViewCellsTree::GetDeviation(ViewCell *vc) const
1341{
[1709]1342        const float upper = (float)mViewCellsManager->GetMaxPvsSize();
1343        const float lower = (float)mViewCellsManager->GetMinPvsSize();
[580]1344
1345        if (1)
1346        {
[1709]1347                const float penalty = EvalPvsPenalty(GetPvsCost(vc), lower, upper);
[582]1348                return fabs(mAvgRenderCost - penalty) / (float)mNumActiveViewCells;
[580]1349        }
1350
1351    const float renderCost = GetRenderCost(vc);
1352        return fabs(mExpectedCost - renderCost);
1353}
1354
1355
1356float ViewCellsTree::GetRenderCost(ViewCell *vc) const
1357{
1358        if (mUseAreaForPvs)
[1141]1359        {
[1707]1360                return vc->GetPvs().EvalPvsCost() * vc->GetArea();
[1141]1361        }
[580]1362
[1707]1363        return vc->GetPvs().EvalPvsCost() * vc->GetVolume();
[580]1364}
1365
1366
1367float ViewCellsTree::GetCostHeuristics(ViewCell *vc) const
1368{
1369        return GetRenderCost(vc) * mRenderCostWeight +
1370                   GetDeviation(vc) * (1.0f - mRenderCostWeight);
1371}
1372
1373
[582]1374bool ViewCellsTree::ValidateMergeCandidate(MergeCandidate &mc) const
[580]1375{
[752]1376        // propagate up so we have only the active view cells
[580]1377        while (mc.mLeftViewCell->mParent)
1378        {
1379                mc.mLeftViewCell = mc.mLeftViewCell->mParent;
1380        }
1381
1382        while (mc.mRightViewCell->mParent)
1383        {
1384                mc.mRightViewCell = mc.mRightViewCell->mParent;
1385        }
1386
[752]1387        // this view cell was already merged
1388        //return mc.mLeftViewCell && (mc.mLeftViewCell != mc.mRightViewCell);
[582]1389        return mc.mLeftViewCell != mc.mRightViewCell;
[580]1390}
1391
1392
1393void ViewCellsTree::EvalMergeCost(MergeCandidate &mc) const
1394{
[1586]1395        ///////////////////
[580]1396        //-- compute pvs difference
[1586]1397
[1709]1398        float newPvs;
[1586]1399       
[1709]1400        // not valid if not using const cost per object!!
1401        newPvs = ComputeMergedPvsCost(mc.mLeftViewCell->GetPvs(), mc.mRightViewCell->GetPvs());
[580]1402
[1709]1403
[1141]1404        const float newPenalty = EvalPvsPenalty(newPvs,
[1709]1405                                                                                        (float)mViewCellsManager->GetMinPvsSize(),
1406                                                                                        (float)mViewCellsManager->GetMaxPvsSize());
[729]1407
[580]1408        ViewCell *vc1 = mc.mLeftViewCell;
1409        ViewCell *vc2 = mc.mRightViewCell;
1410
1411        //-- compute ratio of old cost
[1586]1412        //-- (i.e., added size of left and right view cell times pvs size)
1413        //-- to new rendering cost (i.e, size of merged view cell times pvs size)
[580]1414        const float oldCost = GetRenderCost(vc1) + GetRenderCost(vc2);
1415
1416    const float newCost = mUseAreaForPvs ?
1417                (float)newPenalty * (vc1->GetArea() + vc2->GetArea()) :
1418                (float)newPenalty * (vc1->GetVolume() + vc2->GetVolume());
1419
1420
1421        // strong penalty if pvs size too large
1422        if (0 && (newPvs > mViewCellsManager->GetMaxPvsSize()))
1423        {
1424                mc.mRenderCost = 1e20f;
1425        }
1426        else
1427        {
1428                mc.mRenderCost = (newCost - oldCost) /
1429                        mViewCellsManager->GetViewSpaceBox().GetVolume();
1430        }       
1431       
[1586]1432        ///////////////////////////
1433        //-- merge cost also takes deviation into account
[580]1434
1435        float newDev, oldDev;
1436
1437        if (1)
[582]1438                newDev = fabs(mAvgRenderCost - newPenalty) / (float)mNumActiveViewCells;
[580]1439        else
[582]1440                newDev = fabs(mExpectedCost - newCost) / (float)mNumActiveViewCells;
[580]1441       
1442        oldDev = GetDeviation(vc1) + GetDeviation(vc2);
1443
1444        // compute deviation increase
1445        mc.mDeviationIncr = newDev - oldDev;
1446       
1447        //Debug << "render cost: " << mc.mRenderCost * mRenderCostWeight << endl;
1448        //Debug << "standard deviation: " << mc.mDeviationIncr * mRenderCostWeight << endl;
1449}
1450
[752]1451
1452void ViewCellsTree::SetViewCellsStorage(int stype)
[580]1453{
[752]1454        if (mViewCellsStorage == stype)
1455                return;
1456
1457        // TODO
1458        switch (stype)
[581]1459        {
[752]1460        case COMPRESSED:
[584]1461                CompressViewCellsPvs(mRoot);
[752]1462                break;
1463        default:
1464                break;
[584]1465        }
[752]1466
1467        mViewCellsStorage = stype;
[584]1468}
[580]1469
[752]1470
[584]1471void ViewCellsTree::CompressViewCellsPvs(ViewCell *root)
1472{
1473        if (!root->IsLeaf())
1474        {
[2017]1475                ViewCellInterior *interior = static_cast<ViewCellInterior *>(root);
[584]1476
1477        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
[585]1478               
[584]1479                // compress child sets first
1480                for (it = interior->mChildren.begin(); it != it_end; ++ it)
[581]1481                {
[584]1482                        CompressViewCellsPvs(*it);
[581]1483                }
[584]1484
[1842]1485                /*cout << "***************\nbefore pulling up:\n";
1486                for (it = interior->mChildren.begin(); it != it_end; ++ it)
1487                {
1488                        cout << "vc:\n" << (*it)->GetPvs() << endl;
1489                }*/
1490
[585]1491                // compress root node
[610]1492                PullUpVisibility(interior);
[1842]1493
1494                /*cout << "after pulling up:\n";
1495                cout << "interior:\n" << interior->GetPvs() << endl;
1496
1497                for (it = interior->mChildren.begin(); it != it_end; ++ it)
1498                {
1499                        cout << "vc:\n" << (*it)->GetPvs() << endl;
1500                }*/
[581]1501        }
[580]1502}
1503
1504
[1166]1505void ViewCellsTree::UpdateStats(ofstream &stats,
[1709]1506                                                                const ViewCellsTreeStats &vcStats)
[1166]1507{
[1709]1508         stats << "#Pass\n" << vcStats.mPass << endl
1509                   << "#Splits\n" << vcStats.mNumViewCells << endl
1510                   << "#RenderCostDecrease\n" << vcStats.mRenderCostDecrease << endl // TODO
1511                   << "#TotalRenderCost\n" << vcStats.mTotalRenderCost << endl
1512                   << "#CurrentPvs\n" << vcStats.mCurrentPvsCost << endl
1513                   << "#ExpectedCost\n" << vcStats.mExpectedCost << endl
1514                   << "#AvgRenderCost\n" << vcStats.mAvgRenderCost << endl
1515                   << "#Deviation\n" << vcStats.mDeviation << endl
1516                   << "#TotalPvs\n" << vcStats.mTotalPvsCost << endl
1517                   << "#TotalEntriesInPvs\n" << vcStats.mEntriesInPvs << endl
1518                   << "#Memory\n" << vcStats.mMemoryCost << endl
1519                   << "#PvsSizeDecrease\n" << vcStats.mPvsSizeDecr << endl
1520                   << "#Volume\n" << vcStats.mVolume << endl
[1653]1521                   << endl;
[1166]1522}
1523
[1489]1524
[660]1525void ViewCellsTree::ExportStats(const string &mergeStats)
[650]1526{
1527        TraversalQueue tqueue;
1528        tqueue.push(mRoot);
[1666]1529
[1709]1530        ViewCellsTreeStats vcStats;
1531        vcStats.Reset();
1532
[1695]1533        //cout << "exporting stats ... " << endl;
[1709]1534        vcStats.mNumViewCells = 1;
[650]1535       
1536        const AxisAlignedBox3 box = mViewCellsManager->GetViewSpaceBox();
1537        const float vol = box.GetVolume();
1538
[1709]1539        const float rootPvs = GetPvsCost(mRoot);
[1161]1540        const int rootEntries = GetPvsEntries(mRoot);
[1709]1541       
1542        vcStats.mTotalPvsCost = rootPvs;
1543        vcStats.mTotalRenderCost = rootPvs;
1544        vcStats.mAvgRenderCost = rootPvs;
1545        vcStats.mExpectedCost = rootPvs;
1546       
1547        vcStats.mEntriesInPvs = rootEntries;
[650]1548
1549        ofstream stats;
[660]1550        stats.open(mergeStats.c_str());
[650]1551
[1709]1552        vcStats.mMemoryCost = (float)vcStats.mEntriesInPvs * ObjectPvs::GetEntrySize();
[1653]1553
[1603]1554        /////////////
[752]1555        //-- first view cell
[1603]1556
[1709]1557        UpdateStats(stats, vcStats);
1558                               
[1166]1559               
[1161]1560        //-- go through tree in the order of render cost decrease
1561        //-- which is the same order as the view cells were merged
1562        //-- or the reverse order of subdivision for subdivision-only
1563        //-- view cell hierarchies.
[650]1564
1565        while (!tqueue.empty())
1566        {
1567                ViewCell *vc = tqueue.top();
1568                tqueue.pop();
1569
1570                if (!vc->IsLeaf())
1571                {       
[2017]1572                        ViewCellInterior *interior = static_cast<ViewCellInterior *>(vc);
[1166]1573
[1709]1574                        const float parentCost = GetPvsCost(interior);
[1166]1575                        const int parentPvsEntries = GetPvsEntries(interior);
[1709]1576            const float parentExpCost = (float)parentCost * interior->GetVolume();
[1166]1577
[1709]1578                        float childExpCost = 0;
[650]1579                        float childCost = 0;
[1166]1580                        int childPvsEntries = 0;
[650]1581
[1709]1582                        -- vcStats.mNumViewCells;
[650]1583
1584                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
[1179]1585
[650]1586                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
1587                        {
[1166]1588                                ViewCell *vc = *it;
[1168]1589
[1709]1590                                const float pvsCost = GetPvsCost(vc);
[1166]1591                                const int pvsEntries = GetPvsEntries(vc);
1592
[1709]1593                                childExpCost += childCost * vc->GetVolume();
1594                                childCost += pvsCost;
[1166]1595                                childPvsEntries += pvsEntries;
[650]1596
[1166]1597                                tqueue.push(vc);
[1709]1598                                ++ vcStats.mNumViewCells;
[650]1599                        }
1600
[1603]1601                        // update stats for this view cell
[1709]1602                        const float costDecr = (parentExpCost - childExpCost) / vol;
[650]1603
[1709]1604                        vcStats.mTotalRenderCost -= costDecr;
1605                        vcStats.mTotalPvsCost += childCost - parentCost;
1606                        vcStats.mEntriesInPvs += childPvsEntries - parentPvsEntries;
[1166]1607
[1709]1608                        vcStats.mExpectedCost = vcStats.mTotalRenderCost / (float)vcStats.mNumViewCells;
1609                        vcStats.mAvgRenderCost = vcStats.mTotalPvsCost / (float)vcStats.mNumViewCells;
[650]1610
[1709]1611                        vcStats.mMemoryCost = vcStats.mEntriesInPvs * ObjectPvs::GetEntrySize();
[1653]1612
[1709]1613                        UpdateStats(stats, vcStats);
[650]1614                }
1615        }
1616
1617        stats.close();
1618}
1619
1620
1621void ViewCellsTree::SetRoot(ViewCell *root)
1622{
1623        mRoot = root;
1624}
1625
[660]1626
[581]1627void ViewCellsTree::CollectBestViewCellSet(ViewCellContainer &viewCells,
1628                                                                                   const int numViewCells)
[580]1629{
1630        TraversalQueue tqueue;
[581]1631        tqueue.push(mRoot);
[582]1632       
[580]1633        while (!tqueue.empty())
1634        {
1635                ViewCell *vc = tqueue.top();
[650]1636                tqueue.pop();
1637
[582]1638                // save the view cells if it is a leaf or if enough view cells have already been traversed
1639                // because of the priority queue, this will be the optimal set of v
[650]1640                if (vc->IsLeaf() || ((viewCells.size() + tqueue.size() + 1) >= numViewCells))
[581]1641                {
1642                        viewCells.push_back(vc);
1643                }
[582]1644                else
1645                {       
[2017]1646                        ViewCellInterior *interior = static_cast<ViewCellInterior *>(vc);
[580]1647
[581]1648                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1649
1650                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
1651                        {
1652                                tqueue.push(*it);
1653                        }
1654                }
[580]1655        }
1656}
1657
[1742]1658
[610]1659void ViewCellsTree::PullUpVisibility(ViewCellInterior *interior)
[581]1660{
[1842]1661        const int mail = (int)interior->mChildren.size();
1662        Intersectable::NewMail(mail);
[580]1663
[581]1664        ViewCellContainer::const_iterator cit, cit_end = interior->mChildren.end();
1665
[1842]1666    // mail all objects in the leaf sets
[584]1667        // we are interested in the objects which are present in all leaves
1668        // => count how often an object is part of a child set
[581]1669        for (cit = interior->mChildren.begin(); cit != cit_end; ++ cit)
1670        {
1671                ViewCell *vc = *cit;
[1842]1672                ObjectPvsIterator pit = vc->GetPvs().GetIterator();
[581]1673
[1842]1674                while (pit.HasMoreEntries())
1675                {               
[2117]1676                        pit.Next()->Mail();
[1842]1677                }
1678        }
1679
1680        for (cit = interior->mChildren.begin(); cit != cit_end; ++ cit)
1681        {
1682                ViewCell *vc = *cit;
1683
[1742]1684                ObjectPvsIterator pit = vc->GetPvs().GetIterator();
[581]1685
[1742]1686                while (pit.HasMoreEntries())
1687                {               
[2117]1688                        pit.Next()->IncMail();
[581]1689                }
1690        }
1691
[1842]1692        // reset pvs
1693    interior->GetPvs().Clear(false);
[1742]1694               
[2117]1695        PvsData pvsData;
1696
[581]1697        // only the objects which are present in all leaf pvs
1698        // should remain in the parent pvs
[584]1699        // these are the objects which have been mailed in all children
[581]1700        for (cit = interior->mChildren.begin(); cit != cit_end; ++ cit)
1701        {
1702                ViewCell *vc = *cit;
[1742]1703               
1704                ObjectPvsIterator pit = vc->GetPvs().GetIterator();
[581]1705
[1742]1706                while (pit.HasMoreEntries())
1707                {               
[2117]1708                        Intersectable *obj = pit.Next(pvsData);
[581]1709
[2117]1710                        if (obj->Mailed(mail))
[581]1711                        {       
[2117]1712                                interior->GetPvs().AddSample(obj, pvsData.mSumPdf);
[581]1713                        }
1714                }
1715        }
1716
[1842]1717        // delete entries which are pulled up
1718        // note: could be inefficent, rather gather unmailed pvs and reassign
1719        for (cit = interior->mChildren.begin(); cit != cit_end; ++ cit)
1720        {
1721                ViewCell *vc = *cit;
1722                ObjectPvsIterator pit = vc->GetPvs().GetIterator();
[581]1723
[1842]1724                ObjectPvs newPvs;
[2117]1725               
[1842]1726                while (pit.HasMoreEntries())
1727                {               
[2117]1728                        Intersectable *obj = pit.Next(pvsData);
[1842]1729
1730                        if (!obj->Mailed(mail))
1731                        {
[2117]1732                                newPvs.AddSampleDirty(obj, pvsData.mSumPdf);
[1189]1733                        }
[581]1734                }
[1842]1735
1736                vc->SetPvs(newPvs);
[581]1737        }
1738}
1739
[1168]1740
[1166]1741// TODO matt: implement this function for different storing methods
[584]1742void ViewCellsTree::GetPvs(ViewCell *vc, ObjectPvs &pvs) const
1743{
[1161]1744        // pvs is stored in each cell => just return pvs
[752]1745        if (mViewCellsStorage == PVS_IN_INTERIORS)
[801]1746        {
[585]1747                pvs = vc->GetPvs();
[801]1748                return;
1749        }
[585]1750
[1713]1751        ////////////////
[1161]1752        //-- pvs is not stored with the interiors => reconstruct
[585]1753        ViewCell *root = vc;
1754       
[883]1755        // add pvs from this view cell to root
[585]1756        while (root->GetParent())
[584]1757        {
[585]1758                root = root->GetParent();
[1740]1759                pvs.MergeInPlace(root->GetPvs());
[585]1760        }
[584]1761
[883]1762        // add pvs from leaves
[585]1763        stack<ViewCell *> tstack;
1764        tstack.push(vc);
[584]1765
[585]1766        while (!tstack.empty())
1767        {
1768                vc = tstack.top();
1769                tstack.pop();
[1742]1770       
[1161]1771                // add newly found pvs to merged pvs
[1740]1772                pvs.MergeInPlace(vc->GetPvs());
[1750]1773               
[1161]1774                if (!vc->IsLeaf()) // interior cells: go down to leaf level
[584]1775                {
[2017]1776                        ViewCellInterior *interior = static_cast<ViewCellInterior *>(vc);
[584]1777                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1778
1779                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
1780                        {
[585]1781                                tstack.push(*it);
1782                        }               
[584]1783                }
1784        }
1785}
1786
1787
[1709]1788float ViewCellsTree::GetPvsCostForLeafStorage(ViewCell *vc) const
[584]1789{
[1166]1790        // pvs is always stored directly in leaves
1791        if (vc->IsLeaf())
1792        {
[1707]1793                return vc->GetPvs().EvalPvsCost();
[1166]1794        }
[1168]1795       
[1707]1796        // interior nodes: pvs is either stored as a
1797        // scalar or has to be reconstructed from the leaves
[1168]1798        // the stored pvs size is the valid pvs size => just return scalar
1799        if (vc->mPvsSizeValid)
[1166]1800        {
[1709]1801                return vc->mPvsCost;
[1168]1802        }
1803       
1804        // if no valid pvs size stored as a scalar =>
1805        // compute current pvs size of interior from it's leaf nodes
1806        ViewCellContainer leaves;
1807        CollectLeaves(vc, leaves);
[1121]1808
[1168]1809        ViewCellContainer::const_iterator it, it_end = leaves.end();
[1166]1810
[1168]1811        ObjectPvs newPvs;
[1166]1812
[1586]1813        // sum up uniquely found intersectables
[1168]1814        for (it = leaves.begin(); it != it_end; ++ it)
1815        {
[1763]1816                newPvs.MergeInPlace((*it)->GetPvs());
[1166]1817        }
1818
[1707]1819        return newPvs.EvalPvsCost();
[1166]1820}
1821
1822
1823int ViewCellsTree::GetEntriesInPvsForLeafStorage(ViewCell *vc) const
1824{
1825        // pvs is always stored directly in leaves
1826        if (vc->IsLeaf())
[752]1827        {
[1168]1828                return vc->GetPvs().GetSize();
[1166]1829        }
[1168]1830       
1831        // interior node
1832
1833        // interior nodes: pvs is either stored as a scalar or
1834        // has to be reconstructed from the leaves
1835
1836        // the stored pvs size is the valid pvs size => just return scalar
1837        if (vc->mPvsSizeValid)
[1166]1838        {
[1168]1839                return vc->mEntriesInPvs;
1840        }
1841       
1842        int pvsSize = 0;
[1161]1843
[1168]1844        // if no valid pvs size stored as a scalar =>
1845        // compute current pvs size of interior from it's leaf nodes
1846        ViewCellContainer leaves;
1847        CollectLeaves(vc, leaves);
[1161]1848
[1168]1849        ViewCellContainer::const_iterator it, it_end = leaves.end();
1850        Intersectable::NewMail();
[1161]1851
[1168]1852        // sum different intersectables
1853        for (it = leaves.begin(); it != it_end; ++ it)
1854        {
[1742]1855                ObjectPvsIterator oit = (*it)->GetPvs().GetIterator();
[1161]1856
[1742]1857                while (oit.HasMoreEntries())
[1166]1858                {
[2117]1859                        Intersectable *intersect = oit.Next();
[1168]1860
1861                        if (!intersect->Mailed())
1862                        {
1863                                intersect->Mail();
1864                                ++ pvsSize;
1865                        }
[1166]1866                }
1867        }
[1161]1868
[1166]1869        return pvsSize;
1870}
[1161]1871
1872
[1709]1873float ViewCellsTree::GetPvsCostForCompressedStorage(ViewCell *vc) const
[1166]1874{
[1709]1875        float pvsCost = 0;
[1166]1876
[1545]1877        /////////////
[1166]1878        //-- compressed pvs
1879
1880        // the stored pvs size is the valid pvs size => just return scalar
1881        if (vc->mPvsSizeValid)
1882        {
[1709]1883                pvsCost = vc->mPvsCost;
[1166]1884        }
1885
1886        // if no pvs size stored, compute new one
1887        ViewCell *root = vc;
1888       
1889        // also add pvs from this view cell to root
1890        while (root->GetParent())
1891        {
1892                root = root->GetParent();
1893       
1894                // matt: bug! must evaluate kd pvss also
[1709]1895                pvsCost += CountPvsContribution(root);
[1166]1896        }
1897
1898        stack<ViewCell *> tstack;
1899        tstack.push(vc);
1900
1901        while (!tstack.empty())
1902        {
1903                vc = tstack.top();
1904                tstack.pop();
[1709]1905
[1166]1906                // matt: bug! must evaluate kd pvss also
[1709]1907                pvsCost += CountPvsContribution(vc);
[1166]1908
1909                if (!vc->IsLeaf())
[1161]1910                {
[2017]1911                        ViewCellInterior *interior = static_cast<ViewCellInterior *>(vc);
[1166]1912                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1913
1914                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
[752]1915                        {
[1166]1916                                tstack.push(*it);
1917                        }               
1918                }
1919        }
[1161]1920
[1709]1921        return pvsCost;
[1166]1922}
1923
1924
1925int ViewCellsTree::GetEntriesInPvsForCompressedStorage(ViewCell *vc) const
1926{
1927        int pvsSize = 0;
1928
[1586]1929        /////////////////
[1166]1930        //-- compressed pvs
1931
1932        // the stored pvs size is the valid pvs size => just return scalar
1933        if (vc->mPvsSizeValid)
1934        {
1935                pvsSize = vc->mEntriesInPvs;
1936        }
1937
1938        // if no pvs size stored, compute new one
1939        ViewCell *root = vc;
[752]1940       
[1166]1941        // also add pvs from this view cell to root
1942        while (root->GetParent())
1943        {
1944                root = root->GetParent();
1945                // count the pvs entries different from the already found ones 
[1586]1946                pvsSize += CountPvsContribution(root);
[1166]1947        }
[585]1948
[1166]1949        stack<ViewCell *> tstack;
1950        tstack.push(vc);
[719]1951
[1166]1952        while (!tstack.empty())
1953        {
1954                vc = tstack.top();
1955                tstack.pop();
[1161]1956       
[1166]1957                // count the pvs entries different from the already found ones 
[1586]1958                pvsSize += CountPvsContribution(vc);
[752]1959
[1166]1960                if (!vc->IsLeaf())
1961                {
[2017]1962                        ViewCellInterior *interior = static_cast<ViewCellInterior *>(vc);
[1161]1963
[1166]1964                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
[1161]1965
[1166]1966                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
1967                        {
1968                                tstack.push(*it);
1969                        }               
1970                }
1971        }
1972
1973        return pvsSize;
1974}
1975
1976
[1709]1977float ViewCellsTree::GetPvsCost(ViewCell *vc) const
[1166]1978{
[1709]1979        float pvsCost = 0;
[1166]1980        Intersectable::NewMail();
1981
1982        ////////////////////////////////////////////////
[1311]1983        // for interiors, pvs can be stored using different methods
[1166]1984        //
1985
1986        switch (mViewCellsStorage)
1987        {
[1707]1988        case PVS_IN_LEAVES:
1989                // pvs is stored only in leaves
[1709]1990                pvsCost = GetPvsCostForLeafStorage(vc);                 
[1311]1991                break;
[1166]1992        case COMPRESSED:
[1709]1993                pvsCost = GetPvsCostForCompressedStorage(vc);
[1311]1994                break;
[1161]1995        case PVS_IN_INTERIORS:
1996        default:
[1742]1997                // pvs is stored consistently in the tree up
1998                //to the root just return pvs size
[1709]1999                pvsCost = vc->GetPvs().EvalPvsCost();   
[1161]2000                break;
2001        }
2002
[1709]2003        return pvsCost; 
[1161]2004}
2005
2006
2007int ViewCellsTree::GetPvsEntries(ViewCell *vc) const
2008{
2009        int pvsSize = 0;
2010
2011        Intersectable::NewMail();
2012
2013        ////////////////////////////////////////////////
2014        // for interiors, pvs can be stored using different methods
2015       
2016        switch (mViewCellsStorage)
2017        {
[1622]2018        case PVS_IN_LEAVES:
2019                {
2020                        //-- store pvs only in leaves
[1166]2021                        pvsSize = GetEntriesInPvsForLeafStorage(vc);
2022                        break;
[752]2023                }
2024        case COMPRESSED:
2025                {
[1166]2026                        pvsSize = GetEntriesInPvsForCompressedStorage(vc);
[752]2027                        break;
2028                }
2029        case PVS_IN_INTERIORS:
[997]2030        default:
[1161]2031                // pvs is stored consistently in the tree up to the root
2032                // just return pvs size
2033                pvsSize = vc->GetPvs().GetSize();       
2034                break;
[752]2035        }
[584]2036
2037        return pvsSize; 
2038}
2039
2040
2041float ViewCellsTree::GetMemoryCost(ViewCell *vc) const
2042{
[1667]2043        return (float)CountStoredPvsEntries(vc) * ObjectPvs::GetEntrySize();
[584]2044}
2045
[1586]2046//#if HAS_TO_BE_REDONE
2047int ViewCellsTree::CountStoredPvsEntries(ViewCell *root) const
[584]2048{
[1161]2049        int pvsSize = root->GetPvs().GetSize();
[584]2050
[1161]2051        // recursivly count leaves
2052        if (!root->IsLeaf())
[584]2053        {
[2017]2054                ViewCellInterior *interior = static_cast<ViewCellInterior *>(root);
[584]2055
2056                ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
2057
2058                for (it = interior->mChildren.begin(); it != it_end; ++ it)
2059                {
[1586]2060                        pvsSize += CountStoredPvsEntries(*it);
[584]2061                }
2062        }
2063
2064        return pvsSize;         
2065}
[1586]2066//#endif
[584]2067
[752]2068int ViewCellsTree::ViewCellsStorage() const
[584]2069{
[752]2070        return mViewCellsStorage;
[584]2071}
2072
2073
[881]2074ViewCell *ViewCellsTree::GetActiveViewCell(ViewCellLeaf *vc) const
[590]2075{
[881]2076        return vc->GetActiveViewCell();
[590]2077}
2078
2079
[1740]2080void ViewCellsTree::PropagatePvs(ViewCell *root)
[664]2081{       
[1740]2082        ViewCell *viewCell = root;
[664]2083
[660]2084        // propagate pvs up
[664]2085        while (viewCell->GetParent())
[610]2086        {
[1740]2087                ObjectPvs mergedPvs;
2088                viewCell->GetParent()->GetPvs().MergeInPlace(root->GetPvs());
2089
[664]2090                viewCell = viewCell->GetParent();
[610]2091        }
[651]2092
[1740]2093        if (root->IsLeaf())
[651]2094                return;
2095
[660]2096        // propagate pvs to the leaves
[651]2097        stack<ViewCell *> tstack;
[1740]2098        tstack.push(root);
[651]2099
2100        while (!tstack.empty())
2101        {
2102                ViewCell *viewCell = tstack.top();
2103                tstack.pop();
2104
[1740]2105                if (viewCell != root)
[651]2106                {
[1740]2107                        viewCell->GetPvs().MergeInPlace(root->GetPvs());
[651]2108                }
2109
2110                if (!viewCell->IsLeaf())
2111                {
[2017]2112                        ViewCellInterior *interior = static_cast<ViewCellInterior *>(viewCell);
[664]2113
[651]2114                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
2115
2116                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
2117                        {
2118                                tstack.push(*it);
2119                        }
2120                }
2121        }
[610]2122}
[605]2123
[610]2124
[650]2125void ViewCellsTree::AssignRandomColors()
[608]2126{
[675]2127        TraversalQueue tqueue;
2128        tqueue.push(mRoot);
[708]2129       
[675]2130        mRoot->SetColor(RandomColor(0.3f, 1.0f));
2131       
2132        while (!tqueue.empty())
[608]2133        {
[675]2134                ViewCell *vc = tqueue.top();
2135                tqueue.pop();
[650]2136
[1740]2137                // save the view cells if it is a leaf or if enough view cells
2138                // have already been traversed because of the priority queue,
2139                // this will be the optimal set of v
[675]2140                if (!vc->IsLeaf())
2141                {       
[2017]2142                        ViewCellInterior *interior = static_cast<ViewCellInterior *>(vc);
[675]2143                 
2144                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
2145                 
2146                        float maxProbability = -1.0f;
2147                 
2148                        ViewCell *maxViewCell = NULL;
2149                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
2150                        {
2151                                ViewCell *v = *it;
2152                         
2153                                // set random color
2154                                v->SetColor(RandomColor(0.3f, 1.0f));
2155                         
2156                                if (v->GetVolume() > maxProbability)
2157                                {
2158                                        maxProbability = v->GetVolume();
2159                                        maxViewCell = v;
2160                                }
2161
2162                                if (maxViewCell)
[708]2163                                {
[675]2164                                        maxViewCell->SetColor(vc->GetColor());
[708]2165                                }
[675]2166                               
2167                                tqueue.push(v);
2168                        }
2169                }       
[608]2170        }
2171}
2172
[675]2173
[1161]2174/** Get costs resulting from each merge step.
2175*/
[1603]2176void ViewCellsTree::GetCostFunction(vector<float> &costFunction)
[608]2177{
[1603]2178        TraversalQueue tqueue;
2179        tqueue.push(mRoot);
2180
2181        int numViewCells = 1;
2182
2183        const float vol = mViewCellsManager->GetViewSpaceBox().GetVolume();
[1709]2184        const float rootPvs = GetPvsCost(mRoot);
[1603]2185       
2186        float totalRenderCost;
2187
[1709]2188        float totalPvsCost = rootPvs;
[1603]2189        totalRenderCost = (float)rootPvs;
2190
2191        costFunction.push_back(totalRenderCost);
2192
2193        //-- go through tree in the order of render cost decrease
2194        //-- which is the same order as the view cells were merged
2195        //-- or the reverse order of subdivision for subdivision-only
2196        //-- view cell hierarchies.
2197
2198        while (!tqueue.empty())
[1161]2199        {
[1603]2200                ViewCell *vc = tqueue.top();
2201                tqueue.pop();
2202
2203                if (!vc->IsLeaf())
2204                {       
[2017]2205                        ViewCellInterior *interior = static_cast<ViewCellInterior *>(vc);
[1603]2206
[1709]2207                        const float parentCost = GetPvsCost(interior);
2208                        const float parentExpCost = parentCost * interior->GetVolume();
[1603]2209
2210                        -- numViewCells;
2211
[1709]2212                        float childExpCost = 0;
[1603]2213                        float childCost = 0;
2214                       
2215                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
2216
2217                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
2218                        {
2219                                ViewCell *vc = *it;
2220
[1709]2221                                const float pvsCost = GetPvsCost(vc);
[1603]2222                               
[1709]2223                                childExpCost += (float) pvsCost * vc->GetVolume();
2224                                childCost += pvsCost;
[1603]2225                               
2226                                tqueue.push(vc);
2227                                ++ numViewCells;
2228                        }
2229
2230                        // update stats for this view cell
[1709]2231                        const float costDecr = (parentExpCost - childExpCost) / vol;
[1603]2232                        totalRenderCost -= costDecr;
[1709]2233                       
2234                        costFunction.push_back(totalRenderCost);
[1161]2235                }
[608]2236        }
2237}
2238
2239
[1603]2240/** Get storage costs resulting from each merge step.
2241*/
2242void ViewCellsTree::GetStorageFunction(vector<int> &storageFunction)
2243{
2244        TraversalQueue tqueue;
2245        tqueue.push(mRoot);
2246
2247        int numViewCells = 1;
2248
2249        const float vol = mViewCellsManager->GetViewSpaceBox().GetVolume();
2250        const int rootEntries = GetPvsEntries(mRoot);
2251
2252        int entriesInPvs = rootEntries;
[2100]2253        // one entry into the pvs
2254    const int entryStorage = sizeof(PvsData) + sizeof(int);
[1603]2255
2256        storageFunction.push_back(rootEntries);
2257
2258        ////////////
2259        //-- go through tree in the order of render cost decrease
2260        //-- which is the same order as the view cells were merged
2261        //-- or the reverse order of subdivision for subdivision-only
2262        //-- view cell hierarchies.
2263
2264        while (!tqueue.empty())
2265        {
2266                ViewCell *vc = tqueue.top();
2267                tqueue.pop();
2268
2269                if (!vc->IsLeaf())
2270                {       
[2017]2271                        ViewCellInterior *interior = static_cast<ViewCellInterior *>(vc);
[1603]2272
[1709]2273                        const float parentPvsCost = GetPvsCost(interior);
[1603]2274                        const int parentPvsEntries = GetPvsEntries(interior);
[1709]2275            const float parentExpCost = (float)parentPvsCost * interior->GetVolume();
[1603]2276
[1709]2277                        float childExpCost = 0;
[1603]2278                        int childPvs = 0;
2279                        int childPvsEntries = 0;
2280
2281                        -- numViewCells;
2282
2283                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
2284
2285                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
2286                        {
2287                                ViewCell *vc = *it;
2288
2289                                const int pvsEntries = GetPvsEntries(vc);
2290                                childPvsEntries += pvsEntries;
2291
2292                                tqueue.push(vc);
2293                                ++ numViewCells;
2294                        }
2295
2296                        // update stats for this view cell
[1709]2297                        const float costDecr = (parentExpCost - childExpCost) / vol;
[1603]2298
2299                        entriesInPvs += childPvsEntries - parentPvsEntries;
2300
2301                        const int storageCost = entriesInPvs * entryStorage;
2302                        storageFunction.push_back(storageCost);
2303                }
2304        }
2305}
2306
2307
[1161]2308void ViewCellsTree::UpdateViewCellsStats(ViewCell *vc,
2309                                                                                 ViewCellsStatistics &vcStat)
[605]2310{
2311        ++ vcStat.viewCells;
2312               
[1709]2313        const float pvsCost = GetPvsCost(vc);
[605]2314
[1709]2315        vcStat.pvsCost += pvsCost;
[605]2316
[1709]2317        if (pvsCost < Limits::Small)
[605]2318                ++ vcStat.emptyPvs;
2319
[1709]2320        if (pvsCost > vcStat.maxPvs)
2321                vcStat.maxPvs = pvsCost;
[605]2322
[1709]2323        if (pvsCost < vcStat.minPvs)
2324                vcStat.minPvs = pvsCost;
[605]2325
2326        if (!vc->GetValid())
2327                ++ vcStat.invalid;
2328}
2329
[1161]2330
[1201]2331bool ViewCellsTree::Export(OUT_STREAM &stream, const bool exportPvs)
[610]2332{
[840]2333        // export recursivly all view cells from the root
[844]2334        ExportViewCell(mRoot, stream, exportPvs);
[605]2335
[610]2336        return true;
2337}
2338
2339
[651]2340void ViewCellsTree::CreateUniqueViewCellsIds()
[610]2341{
[651]2342        stack<ViewCell *> tstack;
[610]2343
[651]2344        int currentId = 0;
2345
2346        tstack.push(mRoot);
2347
2348        while (!tstack.empty())
[610]2349        {
[651]2350                ViewCell *vc = tstack.top();
2351                tstack.pop();
2352
[1551]2353                if (vc->GetId() != -1) // out of bounds
2354                        vc->SetId(currentId ++);
[651]2355
2356                if (!vc->IsLeaf())
2357                {
[2017]2358                        ViewCellInterior *interior = static_cast<ViewCellInterior *>(vc);
[1161]2359                       
[651]2360                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
2361                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
2362                        {
2363                                tstack.push(*it);
2364                        }
2365                }
[610]2366        }
[651]2367}
[610]2368
[1201]2369
2370void ViewCellsTree::ExportPvs(ViewCell *viewCell, OUT_STREAM &stream)
[651]2371{
[1742]2372        ObjectPvsIterator it = viewCell->GetPvs().GetIterator();
[651]2373
[1742]2374        while (it.HasMoreEntries())
[837]2375        {
[2117]2376                Intersectable *obj = it.Next();
[1742]2377
[2124]2378                // hack: just output all the "elementary" objects
[1843]2379                if (0 && (obj->Type() == Intersectable::BVH_INTERSECTABLE))
[1614]2380                {
2381                        ObjectContainer objects;
[2017]2382                        BvhNode *node = static_cast<BvhNode *>(obj);
[1614]2383                        node->CollectObjects(objects);
2384               
2385                        ObjectContainer::const_iterator oit, oit_end = objects.end();
2386                        for (oit = objects.begin(); oit != oit_end; ++ oit)
2387                        {
2388                                stream << (*oit)->GetId() << " ";
2389                        }
2390                }
2391                else
2392                {
[2117]2393                        stream << obj->GetId() << " ";
[1614]2394                }
[837]2395        }
2396}
2397
[1201]2398
2399void ViewCellsTree::ExportViewCell(ViewCell *viewCell,
2400                                                                   OUT_STREAM &stream,
2401                                                                   const bool exportPvs)
[837]2402{
[610]2403        if (viewCell->IsLeaf())
2404        {
2405                stream << "<Leaf ";
2406                stream << "id=\"" << viewCell->GetId() << "\" ";
[2017]2407                stream << "active=\"" << static_cast<ViewCellLeaf *>(viewCell)->GetActiveViewCell()->GetId() << "\" ";
[610]2408                stream << "mergecost=\"" << viewCell->GetMergeCost() << "\" ";
2409                stream << "pvs=\"";
[837]2410               
[1551]2411                //-- export pvs, i.e., the ids of the objects in the pvs
[844]2412                if (exportPvs)
[955]2413                {
[840]2414                        ExportPvs(viewCell, stream);
[955]2415                }
[651]2416                stream << "\" />" << endl;
[610]2417        }
2418        else
2419        {
[2017]2420                ViewCellInterior *interior = static_cast<ViewCellInterior *>(viewCell);
[610]2421       
2422                stream << "<Interior ";
2423                stream << "id=\"" << viewCell->GetId() << "\" ";
2424                stream << "mergecost=\"" << viewCell->GetMergeCost() << "\" ";
[870]2425                stream << "pvs=\"";
2426
[1551]2427                // NOTE: do not export pvss for interior view cells because
[870]2428                // they can be completely reconstructed from the leaf pvss
[1551]2429                // on the other hand: we could store a tag with the compression scheme,
2430        // then some scheme were pvs is in the interiors could be used
[1890]2431                if (exportPvs)
2432                {
2433                        ExportPvs(viewCell, stream);
2434                }
2435
[651]2436                stream << "\" >" << endl;
2437
[837]2438                //-- recursivly export child view cells
[610]2439                ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
2440
2441                for (it = interior->mChildren.begin(); it != it_end; ++ it)
2442                {
[844]2443                        ExportViewCell(*it, stream, exportPvs);
[610]2444                }
2445
2446                stream << "</Interior>" << endl;
2447        }
2448}
2449
2450
[660]2451void ViewCellsTree::ResetPvs()
2452{
2453        stack<ViewCell *> tstack;
[610]2454
[660]2455        tstack.push(mRoot);
2456
2457        while (!tstack.empty())
2458        {
2459                ViewCell *vc = tstack.top();
2460                tstack.pop();
2461
[1189]2462                vc->GetPvs().Clear();
[666]2463               
[660]2464                if (!vc->IsLeaf())
2465                {
[2017]2466                        ViewCellInterior *interior = static_cast<ViewCellInterior *>(vc);
[660]2467                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
[666]2468
[660]2469                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
2470                        {
2471                                tstack.push(*it);
2472                        }
2473                }
2474        }
2475}
2476
2477
[1551]2478void ViewCellsTree::SetViewCellsManager(ViewCellsManager *vcm)
2479{
2480        mViewCellsManager = vcm;
2481}
2482
2483
[660]2484void ViewCellsTree::SetActiveSetToLeaves()
2485{
[752]2486        // todo
[660]2487}
2488
[1603]2489
[1842]2490
[580]2491/**************************************************************************/
2492/*                     MergeCandidate implementation                      */
2493/**************************************************************************/
2494
2495
2496MergeCandidate::MergeCandidate(ViewCell *l, ViewCell *r):
2497mRenderCost(0),
2498mDeviationIncr(0),
2499mLeftViewCell(l),
[586]2500mRightViewCell(r),
2501mInitialLeftViewCell(l),
2502mInitialRightViewCell(r)
[580]2503{
2504        //EvalMergeCost();
2505}
2506
2507
2508void MergeCandidate::SetRightViewCell(ViewCell *v)
2509{
2510        mRightViewCell = v;
2511}
2512
2513
2514void MergeCandidate::SetLeftViewCell(ViewCell *v)
2515{
2516        mLeftViewCell = v;
2517}
2518
2519
2520ViewCell *MergeCandidate::GetRightViewCell() const
2521{
2522        return mRightViewCell;
2523}
2524
2525
2526ViewCell *MergeCandidate::GetLeftViewCell() const
2527{
2528        return mLeftViewCell;
2529}
2530
2531
2532ViewCell *MergeCandidate::GetInitialRightViewCell() const
2533{
2534        return mInitialRightViewCell;
2535}
2536
2537
2538ViewCell *MergeCandidate::GetInitialLeftViewCell() const
2539{
2540        return mInitialLeftViewCell;
2541}
2542
2543
2544bool MergeCandidate::IsValid() const
2545{
[752]2546        // if one has a parent, it was already merged
[1002]2547        return !(mLeftViewCell->GetParent() || mRightViewCell->GetParent());
[580]2548}
2549
2550
2551float MergeCandidate::GetRenderCost() const
2552{
2553        return mRenderCost;
2554}
2555
2556
2557float MergeCandidate::GetDeviationIncr() const
2558{
2559        return mDeviationIncr;
2560}
2561
2562
2563float MergeCandidate::GetMergeCost() const
2564{
2565        return mRenderCost * sRenderCostWeight +
2566                   mDeviationIncr * (1.0f - sRenderCostWeight);
2567}
2568
2569
[605]2570
[580]2571/************************************************************************/
2572/*                    MergeStatistics implementation                    */
2573/************************************************************************/
2574
2575
2576void MergeStatistics::Print(ostream &app) const
2577{
2578        app << "===== Merge statistics ===============\n";
2579
2580        app << setprecision(4);
2581
2582        app << "#N_CTIME ( Overall time [s] )\n" << Time() << " \n";
2583
2584        app << "#N_CCTIME ( Collect candidates time [s] )\n" << collectTime * 1e-3f << " \n";
2585
2586        app << "#N_MTIME ( Merge time [s] )\n" << mergeTime * 1e-3f << " \n";
2587
2588        app << "#N_NODES ( Number of nodes before merge )\n" << nodes << "\n";
2589
2590        app << "#N_CANDIDATES ( Number of merge candidates )\n" << candidates << "\n";
2591
2592        app << "#N_MERGEDSIBLINGS ( Number of merged siblings )\n" << siblings << "\n";
2593
2594        app << "#OVERALLCOST ( overall merge cost )\n" << overallCost << "\n";
2595
2596        app << "#N_MERGEDNODES ( Number of merged nodes )\n" << merged << "\n";
2597
2598        app << "#MAX_TREEDIST ( Maximal distance in tree of merged leaves )\n" << maxTreeDist << "\n";
2599
2600        app << "#AVG_TREEDIST ( Average distance in tree of merged leaves )\n" << AvgTreeDist() << "\n";
2601
2602        app << "#EXPECTEDCOST ( expected render cost )\n" << expectedRenderCost << "\n";
2603
2604        app << "#DEVIATION ( deviation )\n" << deviation << "\n";
2605
2606        app << "#HEURISTICS ( heuristics )\n" << heuristics << "\n";
2607       
2608
2609        app << "===== END OF BspTree statistics ==========\n";
[608]2610}
[860]2611
[1742]2612
[1199]2613}
Note: See TracBrowser for help on using the repository browser.