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

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