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

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