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

Revision 602, 39.6 KB checked in by mattausch, 18 years ago (diff)

found bug in Merge
Line 
1#include "ViewCell.h"
2#include "Mesh.h"
3#include "Intersectable.h"
4#include "MeshKdTree.h"
5#include "Triangle3.h"
6#include "common.h"
7#include "Environment.h"
8#include "ViewCellsManager.h"
9#include "Exporter.h"
10
11#include <time.h>
12#include <iomanip>
13#include <stack>
14
15
16
17template <typename T> class myless
18{
19public:
20       
21        //bool operator() (HierarchyNode *v1, HierarchyNode *v2) const
22        bool operator() (T v1, T v2) const
23        {
24                return (v1->GetMergeCost() < v2->GetMergeCost());
25        }
26};
27
28
29typedef priority_queue<ViewCell *, vector<ViewCell *>, myless<vector<ViewCell *>::value_type> > TraversalQueue;
30
31int ViewCell::sMailId = 21843194198;
32int ViewCell::sReservedMailboxes = 1;
33
34//int upperPvsLimit = 120;
35//int lowerPvsLimit = 5;
36
37float MergeCandidate::sRenderCostWeight = 0;
38
39
40// pvs penalty can be different from pvs size
41inline float EvalPvsPenalty(const int pvs,
42                                                        const int lower,
43                                                        const int upper)
44{
45        // clamp to minmax values
46        /*if (pvs < lower)
47                return (float)lower;
48        if (pvs > upper)
49                return (float)upper;
50*/
51        return (float)pvs;
52}
53
54
55
56
57inline int CountDiffPvs(ViewCell *vc)
58{
59        int count = 0;
60
61        ObjectPvsMap::const_iterator it, it_end = vc->GetPvs().mEntries.end();
62        for (it = vc->GetPvs().mEntries.begin(); it != it_end; ++ it)
63        {
64                if (!(*it).first->Mailed())
65                {
66                        (*it).first->Mail();
67                        ++ count;
68                }
69        }
70
71        return count;
72}
73
74
75int ComputeMergedPvsSize(const ObjectPvs &pvs1, const ObjectPvs &pvs2)
76{
77        int pvs = pvs1.GetSize();
78
79        // compute new pvs size
80        ObjectPvsMap::const_iterator it, it_end =  pvs1.mEntries.end();
81
82        Intersectable::NewMail();
83
84        for (it = pvs1.mEntries.begin(); it != it_end; ++ it)
85        {
86                (*it).first->Mail();
87        }
88
89        it_end = pvs2.mEntries.end();
90
91        for (it = pvs2.mEntries.begin(); it != it_end; ++ it)
92        {
93                Intersectable *obj = (*it).first;
94                if (!obj->Mailed())
95                        ++ pvs;
96        }
97
98        return pvs;
99}
100
101
102ViewCell::ViewCell():
103MeshInstance(NULL),
104mPiercingRays(0),
105mArea(-1),
106mVolume(-1),
107mValid(true),
108mParent(NULL),
109mMergeCost(0),
110mIsActive(false)
111{
112}
113
114ViewCell::ViewCell(Mesh *mesh):
115MeshInstance(mesh),
116mPiercingRays(0),
117mArea(-1),
118mVolume(-1),
119mValid(true),
120mParent(NULL),
121mMergeCost(0),
122mIsActive(false)
123{
124}
125
126
127const ObjectPvs &ViewCell::GetPvs() const
128{
129        return mPvs;
130}
131
132ObjectPvs &ViewCell::GetPvs()
133{
134        return mPvs;
135}
136
137
138int ViewCell::Type() const
139{
140        return VIEW_CELL;
141}
142
143
144float ViewCell::GetVolume() const
145{
146        return mVolume;
147}
148
149
150void ViewCell::SetVolume(float volume)
151{
152        mVolume = volume;
153}
154
155
156void ViewCell::SetMesh(Mesh *mesh)
157{
158        mMesh = mesh;
159}
160
161
162void ViewCell::UpdateViewCellsStats(ViewCellsStatistics &vcStat)
163{
164        ++ vcStat.viewCells;
165               
166        const int pvsSize = mPvs.GetSize();
167
168        vcStat.pvs += pvsSize;
169
170        if (pvsSize == 0)
171                ++ vcStat.emptyPvs;
172
173        if (pvsSize > vcStat.maxPvs)
174                vcStat.maxPvs = pvsSize;
175
176        if (pvsSize < vcStat.minPvs)
177                vcStat.minPvs = pvsSize;
178
179        if (!mValid)
180                ++ vcStat.invalid;
181}
182
183
184float ViewCell::GetArea() const
185{
186        return mArea;
187}
188
189
190void ViewCell::SetArea(float area)
191{
192        mArea = area;
193}
194
195
196void ViewCell::SetValid(const bool valid)
197{
198        mValid = valid;
199}
200
201
202bool ViewCell::GetValid() const
203{
204        return mValid;
205}
206
207
208/*bool ViewCell::IsLeaf() const
209{
210        return true;
211}*/
212
213
214void ViewCell::SetParent(ViewCellInterior *parent)
215{
216        mParent = parent;
217}
218
219
220bool ViewCell::IsRoot() const
221{
222        return !mParent;
223}
224
225
226ViewCellInterior *ViewCell::GetParent() const
227{
228        return mParent;
229}
230
231
232void ViewCell::SetMergeCost(const float mergeCost)
233{
234        mMergeCost = mergeCost;
235}
236
237
238float ViewCell::GetMergeCost() const
239{
240        return mMergeCost;
241}
242
243
244
245/************************************************************************/
246/*                class ViewCellInterior implementation                 */
247/************************************************************************/
248
249
250ViewCellInterior::ViewCellInterior()
251{
252}
253
254
255ViewCellInterior::~ViewCellInterior()
256{
257        ViewCellContainer::const_iterator it, it_end = mChildren.end();
258
259        for (it = mChildren.begin(); it != it_end; ++ it)
260                delete (*it);
261}
262
263
264ViewCellInterior::ViewCellInterior(Mesh *mesh):
265ViewCell(mesh)
266{
267}
268
269
270bool ViewCellInterior::IsLeaf() const
271{
272        return false;
273}
274
275
276void ViewCellInterior::SetupChildLink(ViewCell *l)
277{
278    mChildren.push_back(l);
279    l->mParent = this;
280}
281
282
283void ViewCellInterior::RemoveChildLink(ViewCell *l)
284{
285        // erase leaf from old view cell
286        ViewCellContainer::iterator it = mChildren.begin();
287
288        for (; (*it) != l; ++ it);
289        if (it == mChildren.end())
290                Debug << "error" << endl;
291        else
292                mChildren.erase(it);
293}
294
295/************************************************************************/
296/*                class ViewCellsStatistics implementation              */
297/************************************************************************/
298
299
300
301
302void ViewCellsStatistics::Print(ostream &app) const
303{
304        app << "=========== View Cells Statistics ===============\n";
305
306        app << setprecision(4);
307
308        //app << "#N_CTIME  ( Construction time [s] )\n" << Time() << " \n";
309
310        app << "#N_OVERALLPVS ( objects in PVS )\n" << pvs << endl;
311
312        app << "#N_PMAXPVS ( largest PVS )\n" << maxPvs << endl;
313
314        app << "#N_PMINPVS ( smallest PVS )\n" << minPvs << endl;
315
316        app << "#N_PAVGPVS ( average PVS )\n" << AvgPvs() << endl;
317
318        app << "#N_PEMPTYPVS ( view cells with empty PVS )\n" << emptyPvs << endl;
319
320        app << "#N_VIEWCELLS ( number of view cells)\n" << viewCells << endl;
321
322        app << "#N_AVGLEAVES (average number of leaves per view cell )\n" << AvgLeaves() << endl;
323
324        app << "#N_MAXLEAVES ( maximal number of leaves per view cell )\n" << maxLeaves << endl;
325       
326        app << "#N_INVALID ( number of invalid view cells )\n" << invalid << endl;
327
328        app << "========== End of View Cells Statistics ==========\n";
329}
330
331
332/*************************************************************************/
333/*                    class ViewCellsTree implementation                 */
334/*************************************************************************/
335
336
337ViewCellsTree::ViewCellsTree(ViewCellsManager *vcm):
338mRoot(NULL),
339mUseAreaForPvs(false),
340mViewCellsManager(vcm),
341mIsCompressed(false)
342{
343        environment->GetBoolValue("ViewCells.Visualization.exportMergedViewCells", mExportMergedViewCells);
344        environment->GetFloatValue("ViewCells.maxStaticMemory", mMaxMemory);
345
346        //-- merge options
347        environment->GetFloatValue("ViewCells.PostProcess.renderCostWeight", mRenderCostWeight);
348        environment->GetIntValue("ViewCells.PostProcess.minViewCells", mMergeMinViewCells);
349        environment->GetFloatValue("ViewCells.PostProcess.maxCostRatio", mMergeMaxCostRatio);
350        environment->GetBoolValue("ViewCells.PostProcess.refine", mRefineViewCells);   
351
352
353        Debug << "========= view cell tree options ================\n";
354        Debug << "minimum view cells: " << mMergeMinViewCells << endl;
355        Debug << "max cost ratio: " << mMergeMaxCostRatio << endl;
356        Debug << "max memory: " << mMaxMemory << endl;
357        Debug << "refining view cells: " << mRefineViewCells << endl;
358
359        MergeCandidate::sRenderCostWeight = mRenderCostWeight;
360
361        mStats.open("mergeStats.log");
362}
363
364
365// return memory usage in MB
366float ViewCellsTree::GetMemUsage() const
367{
368        return 0;
369                /*(sizeof(ViewCellsTree) +
370                 mBspStats.Leaves() * sizeof(BspLeaf) +
371                 mBspStats.Interior() * sizeof(BspInterior) +
372                 mBspStats.accumRays * sizeof(RayInfo)) / (1024.0f * 1024.0f);*/
373}
374
375
376int ViewCellsTree::GetSize(ViewCell *vc) const
377{
378        int vcSize = 0;
379
380        stack<ViewCell *> tstack;
381
382        tstack.push(vc);
383
384        while (!tstack.empty())
385        {
386                ViewCell *vc = tstack.top();
387                tstack.pop();
388
389                if (vc->IsLeaf())
390                {
391                        ++ vcSize;
392                }
393                else
394                {
395                        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
396                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
397                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
398                                tstack.push(*it);
399                       
400                }
401        }
402
403        return vcSize;
404}
405
406
407void ViewCellsTree::CollectLeaves(ViewCell *vc, ViewCellContainer &leaves) const
408{
409        stack<ViewCell *> tstack;
410
411        tstack.push(vc);
412
413        while (!tstack.empty())
414        {
415                ViewCell *vc = tstack.top();
416                tstack.pop();
417
418                if (vc->IsLeaf())
419                {
420                        leaves.push_back(vc);
421                }
422                else
423                {
424                        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
425                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
426                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
427                                tstack.push(*it);
428                       
429                }
430        }
431}
432
433
434ViewCellsTree::~ViewCellsTree()
435{
436        DEL_PTR(mRoot);
437}
438
439
440int ViewCellsTree::ConstructMergeTree(const VssRayContainer &rays,
441                                                                          const ObjectContainer &objects)
442{
443        mNumActiveViewCells = (int)mViewCellsManager->GetViewCells().size();
444
445        float variance = 0;
446        int totalPvs = 0;
447        float totalRenderCost = 0;
448
449        //-- compute statistics values of initial view cells
450        mViewCellsManager->EvaluateRenderStatistics(totalRenderCost,
451                                                                                                mExpectedCost,
452                                                                                                mDeviation,
453                                                                                                variance,
454                                                                                                totalPvs,
455                                                                                                mAvgRenderCost);
456
457
458        //-- fill merge queue
459        vector<MergeCandidate> candidates;
460
461        mViewCellsManager->CollectMergeCandidates(rays, candidates);
462        while(!candidates.empty())
463        {
464                MergeCandidate mc = candidates.back();
465                candidates.pop_back();
466                EvalMergeCost(mc);
467                mMergeQueue.push(mc);
468        }
469
470        Debug << "************************* merge ***********************************" << endl; 
471        Debug << "deviation: " << mDeviation << endl;
472        Debug << "avg render cost: " << mAvgRenderCost << endl;
473        Debug << "expected cost: " << mExpectedCost << endl;
474
475
476        ViewCellsManager::PvsStatistics pvsStats;
477        mViewCellsManager->GetPvsStatistics(pvsStats);
478
479        static float expectedValue = pvsStats.avgPvs;
480       
481        // the current view cells are kept in this container
482        // we start with the current view cells from the
483        // view cell manager. They will change with
484        // subsequent merges
485        ViewCellContainer &activeViewCells = mViewCellsManager->GetViewCells();
486
487
488        ViewCell::NewMail();
489
490        MergeStatistics mergeStats;
491        mergeStats.Start();
492       
493        long startTime = GetTime();
494
495        mergeStats.collectTime = TimeDiff(startTime, GetTime());
496        mergeStats.candidates = (int)mMergeQueue.size();
497        startTime = GetTime();
498
499        // frequency stats are updated
500        const int statsOut = 1;
501
502        // passes are needed for statistics, because we don't want to record
503        // every merge
504        int pass = 0;
505        int mergedPerPass = 0;
506        float realExpectedCost = mExpectedCost;
507        float realAvgRenderCost = mAvgRenderCost;
508        int realNumActiveViewCells = mNumActiveViewCells;
509       
510        // maximal ratio of old expected render cost to expected render
511        // when the the render queue has to be reset.
512        float avgCostMaxDeviation;
513        int maxMergesPerPass;
514        int numMergedViewCells = 0;
515
516        environment->GetIntValue("ViewCells.PostProcess.maxMergesPerPass", maxMergesPerPass);
517        environment->GetFloatValue("ViewCells.PostProcess.avgCostMaxDeviation", avgCostMaxDeviation);
518
519        cout << "actual merge starts now ... " << endl;
520       
521
522        //-- use priority queue to merge leaf pairs
523// HACK
524        //const float maxAvgCost = 350;
525        while (!mMergeQueue.empty())//NumActiveViewCells > mMergeMinViewCells))
526        {
527                //-- reset merge queue if the ratio of current expected cost / real expected cost
528                //   too small or after a given number of merges
529                if ((mergedPerPass > maxMergesPerPass) ||
530                        (avgCostMaxDeviation > mAvgRenderCost / realAvgRenderCost))
531                {
532                        Debug << "************ reset queue *****************\n"
533                                  << "ratios: " << avgCostMaxDeviation
534                                  << " real avg render cost " << realAvgRenderCost << " average render cost " << mAvgRenderCost
535                                  << " merged per pass : " << mergedPerPass << " of maximal " << maxMergesPerPass << endl;
536
537                        Debug << "Values before reset: " 
538                                  << " erc: " << mExpectedCost
539                                  << " avgrc: " << mAvgRenderCost
540                                  << " dev: " << mDeviation << endl;
541       
542                        // adjust render cost
543                        ++ pass;
544
545                        mergedPerPass = 0;
546                        mExpectedCost = realExpectedCost;
547                        mAvgRenderCost = realAvgRenderCost;
548                        mNumActiveViewCells = realNumActiveViewCells;
549                       
550                        const int numMergedViewCells = UpdateActiveViewCells(activeViewCells);
551               
552                        // refines the view cells
553                        // then priorities are recomputed
554                        // and the candidates are put back into merge queue
555                        if (mRefineViewCells)
556                                RefineViewCells(rays, objects);
557                        else
558                                ResetMergeQueue();
559
560                       
561                        Debug << "Values after reset: " 
562                                  << " erc: " << mExpectedCost
563                                  << " avg: " << mAvgRenderCost
564                                  << " dev: " << mDeviation << endl;
565
566                        if (mExportMergedViewCells)
567                        {
568                                ExportMergedViewCells(activeViewCells, objects, numMergedViewCells);
569                        }
570                }
571
572#ifdef _DEBUG
573                Debug << "abs mergecost: " << mMergeQueue.top().GetMergeCost() <<
574                          << " rel mergecost: " << mMergeQueue.top().GetRenderCost() / mExpectedCost <<
575                          << " max ratio: " << mMergeMaxCostRatio << endl
576                          << " expected value: " << realExpectedCost << endl;
577#endif
578
579       
580                MergeCandidate mc = mMergeQueue.top();
581                mMergeQueue.pop();
582       
583                // both view cells equal
584                // NOTE: do I really still need this? probably cannot happen!!
585                if (mc.mLeftViewCell == mc.mRightViewCell)
586                        continue;
587
588                if (mc.IsValid())
589                {
590                        ViewCell::NewMail();
591
592                        //-- update statistical values
593                        -- realNumActiveViewCells;
594                        ++ mergeStats.merged;
595                        ++ mergedPerPass;
596
597                        const float renderCostIncr = mc.GetRenderCost();
598                        const float mergeCostIncr = mc.GetMergeCost();
599
600                        totalRenderCost += renderCostIncr;
601                        mDeviation += mc.GetDeviationIncr();
602                       
603                       
604                        // merge the view cells of leaf1 and leaf2
605                        int pvsDiff;
606                        ViewCellInterior *mergedVc =
607                                MergeViewCells(mc.mLeftViewCell, mc.mRightViewCell, pvsDiff);
608
609
610                        // total render cost and deviation has changed
611                        // real expected cost will be larger than expected cost used for the
612                        // cost heuristics, but cannot recompute costs on each increase of the
613                        // expected cost
614                        totalPvs += pvsDiff;
615                        realExpectedCost = totalRenderCost / (float)realNumActiveViewCells;
616                        realAvgRenderCost = (float)totalPvs / (float)realNumActiveViewCells;
617       
618                        // set merge cost to this node
619                        mergedVc->SetMergeCost(totalRenderCost);
620
621#if VC_HISTORY
622                        if (mc.mLeftViewCell->IsSibling(mc.mRightViewCell))
623                                ++ mergeStats.siblings;
624#endif
625                //      if (((mergeStats.merged % statsOut) == 0) ||
626                //              (realNumActiveViewCells == mMergeMinViewCells))
627                //      {
628                                cout << "merged " << mergeStats.merged << " view cells" << endl;
629
630                                mStats
631                                        << "#Pass\n" << pass << endl
632                                        << "#Merged\n" << mergeStats.merged << endl
633                                        << "#Viewcells\n" << realNumActiveViewCells << endl
634                                        << "#RenderCostIncrease\n" << renderCostIncr << endl
635                                        << "#TotalRenderCost\n" << totalRenderCost << endl
636                                        << "#CurrentPvs\n" << mergedVc->GetPvs().GetSize() << endl
637                                        << "#ExpectedCost\n" << realExpectedCost / (float) realNumActiveViewCells << endl
638                                        << "#AvgRenderCost\n" << realAvgRenderCost << endl
639                                        << "#Deviation\n" << mDeviation << endl
640                                        << "#TotalPvs\n" << totalPvs << endl
641                                        << "#PvsSizeDecrease\n" << -pvsDiff << endl
642                                        <<  "#Volume\n" << mergedVc->GetVolume() << endl
643                                        << "#Dummy\n" << (float)mergedVc->GetPvs().GetSize() * mergedVc->GetVolume() / mViewCellsManager->GetViewSpaceBox().GetVolume() << endl;
644                //      }
645                }
646                else
647                {
648                        // merge candidate not valid, because one of the leaves was already
649                        // merged with another one => validate and reinsert into queue
650                        if (ValidateMergeCandidate(mc))
651                        {
652                                EvalMergeCost(mc);
653                                mMergeQueue.push(mc);
654                        }
655                }
656        }
657
658        // adjust stats and reset queue one final time
659        mExpectedCost = realExpectedCost;
660        mAvgRenderCost = realAvgRenderCost;
661        mNumActiveViewCells = realNumActiveViewCells;
662
663        UpdateActiveViewCells(activeViewCells);
664
665        // refine view cells and reset costs
666        if (mRefineViewCells)
667                RefineViewCells(rays, objects);
668        else
669                ResetMergeQueue();
670
671        // create a root node if the merge was not done till root level,
672        // else take the single node as new root
673        if ((int)activeViewCells.size() > 1)
674        {
675                Debug << "creating root of view cell hierarchy for "
676                          << (int)activeViewCells.size() << " view cells" << endl;
677                /*for (int i = 0;  i < activeViewCells.size(); ++ i){
678                        Debug << "parent " << activeViewCells[i]->GetParent() << endl;
679                        Debug << "viewcell " << activeViewCells[i] << endl;
680                }*/
681                ViewCellInterior *root = mViewCellsManager->MergeViewCells(activeViewCells);
682                root->SetMergeCost(totalRenderCost);
683                mRoot = root;
684        }
685        else if ((int)activeViewCells.size() == 1)
686        {
687                Debug << "setting root of the merge history" << endl;
688                mRoot = activeViewCells[0];
689        }
690
691
692        while (!mMergeQueue.empty())
693        {
694                mMergeQueue.pop();
695        }
696       
697       
698        // TODO delete because makes no sense here
699        mergeStats.expectedRenderCost = realExpectedCost;
700        mergeStats.deviation = mDeviation;
701
702        // we want to optimize this heuristics
703        mergeStats.heuristics =
704                mDeviation * (1.0f - mRenderCostWeight) +
705                mExpectedCost * mRenderCostWeight;
706
707        mergeStats.mergeTime = TimeDiff(startTime, GetTime());
708        mergeStats.Stop();
709
710        Debug << mergeStats << endl << endl;
711
712
713        //TODO: should return sample contributions?
714        return mergeStats.merged;
715}
716
717
718ViewCell *ViewCellsTree::GetRoot() const
719{
720        return mRoot;
721}
722
723
724void ViewCellsTree::ResetMergeQueue()
725{
726        cout << "reset merge queue ... ";
727       
728        vector<MergeCandidate> buf;
729        buf.reserve(mMergeQueue.size());
730                       
731       
732        // store merge candidates in intermediate buffer
733        while (!mMergeQueue.empty())
734        {
735                MergeCandidate mc = mMergeQueue.top();
736                mMergeQueue.pop();
737               
738                // recalculate cost
739                if (ValidateMergeCandidate(mc))
740                {
741                        EvalMergeCost(mc);
742                        buf.push_back(mc);                             
743                }
744        }
745
746        vector<MergeCandidate>::const_iterator bit, bit_end = buf.end();
747
748        // reinsert back into queue
749        for (bit = buf.begin(); bit != bit_end; ++ bit)
750        {     
751                mMergeQueue.push(*bit);
752        }
753
754        cout << "finished" << endl;
755}
756
757
758int ViewCellsTree::UpdateActiveViewCells(ViewCellContainer &viewCells)
759{
760        int numMergedViewCells = 0;
761
762        Debug << "updating active vc: " << (int)viewCells.size() << endl;
763        // find all already merged view cells and remove them from view cells
764               
765        // sort out all view cells which are not active anymore, i.e., they
766        // were already part of a merge
767        int i = 0;
768
769        ViewCell::NewMail();
770
771        while (1)
772        {
773                // remove all merged view cells from end of the vector
774                while (!viewCells.empty() && (viewCells.back()->GetParent()))
775                {
776                        viewCells.pop_back();
777                }
778
779                // all merged view cells have been found
780                if (i >= viewCells.size())
781                        break;
782
783                // already merged view cell, put it to end of vector
784                if (viewCells[i]->GetParent())
785                        swap(viewCells[i], viewCells.back());
786               
787                viewCells[i ++]->Mail();
788        }
789
790
791        // add new view cells to container only if they don't have been
792        // merged in the mean time
793        ViewCellContainer::const_iterator ait, ait_end = mMergedViewCells.end();
794        for (ait = mMergedViewCells.begin(); ait != ait_end; ++ ait)
795        {
796                ViewCell *vc = mMergedViewCells.back();
797                if (!vc->GetParent() && !vc->Mailed())
798                {
799                        vc->Mail();
800                        viewCells.push_back(vc);
801                        ++ numMergedViewCells;
802                }
803        }
804
805        mMergedViewCells.clear();
806
807        // update standard deviation
808        ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
809       
810        mDeviation = 0;
811
812        for (vit = viewCells.begin(); vit != vit_end; ++ vit)
813        {
814                int lower = mViewCellsManager->GetMinPvsSize();
815                int upper = mViewCellsManager->GetMaxPvsSize();
816                float penalty = EvalPvsPenalty((*vit)->GetPvs().GetSize(), lower, upper);
817               
818                mDeviation += fabs(mAvgRenderCost - penalty);
819        }
820
821        mDeviation /= (float)viewCells.size();
822       
823        return numMergedViewCells;
824}
825
826
827void ViewCellsTree::ExportMergedViewCells(ViewCellContainer &viewCells,
828                                                                                  const ObjectContainer &objects,
829                                                                                  const int numMergedViewCells)
830{
831       
832
833        char s[64];
834
835        sprintf(s, "merged_viewcells%07d.x3d", (int)viewCells.size());
836        Exporter *exporter = Exporter::GetExporter(s);
837
838        if (exporter)
839        {
840                cout << "exporting " << (int)viewCells.size() << " merged view cells ... ";
841                exporter->ExportGeometry(objects);
842                //Debug << "vc size " << (int)viewCells.size() << " merge queue size: " << (int)mMergeQueue.size() << endl;
843                ViewCellContainer::const_iterator it, it_end = viewCells.end();
844
845                int i = 0;
846                for (it = viewCells.begin(); it != it_end; ++ it)
847                {
848                        Material m;
849                        // assign special material to new view cells
850                        // new view cells are on the back of container
851                        if (i ++ >= (viewCells.size() - numMergedViewCells))
852                        {
853                                //m = RandomMaterial();
854                                m.mDiffuseColor.r = RandomValue(0.5f, 1.0f);
855                                m.mDiffuseColor.g = RandomValue(0.5f, 1.0f);
856                                m.mDiffuseColor.b = RandomValue(0.5f, 1.0f);
857                        }
858                        else
859                        {
860                                float col = RandomValue(0.1f, 0.4f);
861                                m.mDiffuseColor.r = col;
862                                m.mDiffuseColor.g = col;
863                                m.mDiffuseColor.b = col;
864                        }
865
866                        exporter->SetForcedMaterial(m);
867                        mViewCellsManager->ExportViewCellGeometry(exporter, *it);
868                }
869                delete exporter;
870                cout << "finished" << endl;
871        }
872}
873
874
875// TODO: should be done in view cells manager
876ViewCellInterior *ViewCellsTree::MergeViewCells(ViewCell *l,
877                                                                                                ViewCell *r,
878                                                                                                int &pvsDiff) //const
879{
880        ViewCellInterior *vc = mViewCellsManager->MergeViewCells(l, r);
881
882        // if merge was unsuccessful
883        if (!vc) return NULL;
884
885        // set new size of view cell
886        if (mUseAreaForPvs)
887                vc->SetArea(l->GetArea() + l->GetArea());
888        else
889        {
890                vc->SetVolume(r->GetVolume() + l->GetVolume());
891        }
892        // important so other merge candidates sharing this view cell
893        // are notified that the merge cost must be updated!!
894        vc->Mail();
895
896        const int pvs1 = l->GetPvs().GetSize();
897        const int pvs2 = r->GetPvs().GetSize();
898
899
900        // new view cells are stored in this vector
901        mMergedViewCells.push_back(vc);
902
903        pvsDiff = vc->GetPvs().GetSize() - pvs1 - pvs2;
904
905        return vc;
906}
907
908
909
910int ViewCellsTree::RefineViewCells(const VssRayContainer &rays,
911                                                                   const ObjectContainer &objects)
912{
913        Debug << "refining " << (int)mMergeQueue.size() << " candidates " << endl;
914
915        // intermediate buffer for shuffled view cells
916        vector<MergeCandidate> buf;
917        buf.reserve(mMergeQueue.size());
918                       
919        // Use priority queue of remaining leaf pairs
920        // The candidates either share the same view cells or
921        // are border leaves which share a boundary.
922        // We test if they can be shuffled, i.e.,
923        // either one leaf is made part of one view cell or the other
924        // leaf is made part of the other view cell. It is tested if the
925        // remaining view cells are "better" than the old ones.
926       
927        const int numPasses = 3;
928        int pass = 0;
929        int passShuffled = 0;
930        int shuffled = 0;
931        int shuffledViewCells = 0;
932
933        ViewCell::NewMail();
934       
935        while (!mMergeQueue.empty())
936        {
937                MergeCandidate mc = mMergeQueue.top();
938                mMergeQueue.pop();
939
940                // both view cells equal or already shuffled
941                if ((mc.GetLeftViewCell() == mc.GetRightViewCell()) ||
942                        mc.GetLeftViewCell()->IsLeaf() || mc.GetRightViewCell()->IsLeaf())
943                {                       
944                        continue;
945                }
946
947                // candidate for shuffling
948                const bool wasShuffled = ShuffleLeaves(mc);
949               
950                // shuffled or put into other queue for further refine
951                if (wasShuffled)
952                {
953                        ++ passShuffled;
954
955                        if (!mc.GetLeftViewCell()->Mailed())
956                        {
957                                mc.GetLeftViewCell()->Mail();
958                                ++ shuffledViewCells;
959                        }
960                        if (!mc.GetRightViewCell()->Mailed())
961                        {
962                                mc.GetRightViewCell()->Mail();
963                                ++ shuffledViewCells;
964                        }
965                }
966
967                // put back into intermediate vector
968                buf.push_back(mc);
969        }
970
971
972        //-- in the end, the candidates must be in the mergequeue again
973        //   with the correct cost
974
975        cout << "reset merge queue ... ";
976       
977       
978        vector<MergeCandidate>::const_iterator bit, bit_end = buf.end();
979       
980        for (bit = buf.begin(); bit != bit_end; ++ bit)
981        {   
982                MergeCandidate mc = *bit;
983                // recalculate cost
984                if (ValidateMergeCandidate(mc))
985                {
986                        EvalMergeCost(mc);
987                        mMergeQueue.push(mc);   
988                }
989        }
990
991        cout << "finished" << endl;
992
993        return shuffledViewCells;
994}
995
996
997
998
999inline int AddedPvsSize(ObjectPvs pvs1, const ObjectPvs &pvs2)
1000{
1001        return pvs1.AddPvs(pvs2);
1002}
1003
1004
1005// recomputes pvs size minus pvs of leaf l
1006#if 0
1007inline int SubtractedPvsSize(BspViewCell *vc, BspLeaf *l, const ObjectPvs &pvs2)
1008{
1009        ObjectPvs pvs;
1010        vector<BspLeaf *>::const_iterator it, it_end = vc->mLeaves.end();
1011        for (it = vc->mLeaves.begin(); it != vc->mLeaves.end(); ++ it)
1012                if (*it != l)
1013                        pvs.AddPvs(*(*it)->mPvs);
1014        return pvs.GetSize();
1015}
1016#endif
1017
1018
1019// computes pvs1 minus pvs2
1020inline int SubtractedPvsSize(ObjectPvs pvs1, const ObjectPvs &pvs2)
1021{
1022        return pvs1.SubtractPvs(pvs2);
1023}
1024
1025
1026float ViewCellsTree::EvalShuffleCost(ViewCell *leaf,
1027                                                                         ViewCellInterior *vc1,
1028                                                                         ViewCellInterior *vc2) const
1029{
1030        //const int pvs1 = SubtractedPvsSize(vc1, leaf, *leaf->mPvs);
1031        const int pvs1 = SubtractedPvsSize(vc1->GetPvs(), leaf->GetPvs());
1032        const int pvs2 = AddedPvsSize(vc2->GetPvs(), leaf->GetPvs());
1033
1034        const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize();
1035        const int upperPvsLimit = mViewCellsManager->GetMaxPvsSize();
1036
1037        const float pvsPenalty1 =
1038                EvalPvsPenalty(pvs1, lowerPvsLimit, upperPvsLimit);
1039
1040        const float pvsPenalty2 =
1041                EvalPvsPenalty(pvs2, lowerPvsLimit, upperPvsLimit);
1042
1043
1044        // don't shuffle leaves with pvs > max
1045        if (0 && (pvs1 + pvs2 > mViewCellsManager->GetMaxPvsSize()))
1046        {
1047                return 1e20f;
1048        }
1049
1050        float p1, p2;
1051
1052    if (mUseAreaForPvs)
1053        {
1054                p1 = vc1->GetArea() - leaf->GetArea();
1055                p2 = vc2->GetArea() + leaf->GetArea();
1056        }
1057        else
1058        {
1059                p1 = vc1->GetVolume() - leaf->GetVolume();
1060                p2 = vc2->GetVolume() + leaf->GetVolume();
1061        }
1062
1063        const float renderCost1 = pvsPenalty1 * p1;
1064        const float renderCost2 = pvsPenalty2 * p2;
1065
1066        float dev1, dev2;
1067
1068        if (1)
1069        {
1070                dev1 = fabs(mAvgRenderCost - pvsPenalty1);
1071                dev2 = fabs(mAvgRenderCost - pvsPenalty2);
1072        }
1073        else
1074        {
1075                dev1 = fabs(mExpectedCost - renderCost1);
1076                dev2 = fabs(mExpectedCost - renderCost2);
1077        }
1078       
1079        return mRenderCostWeight * (renderCost1 + renderCost2) +
1080                  (1.0f - mRenderCostWeight) * (dev1 + dev2) / (float)mNumActiveViewCells;
1081}
1082
1083
1084void ViewCellsTree::ShuffleLeaf(ViewCell *leaf,
1085                                                                ViewCellInterior *vc1,
1086                                                                ViewCellInterior *vc2) const
1087{
1088        // compute new pvs and area
1089        // TODO change
1090        vc1->GetPvs().SubtractPvs(leaf->GetPvs());
1091        vc2->GetPvs().AddPvs(leaf->GetPvs());
1092       
1093        if (mUseAreaForPvs)
1094        {
1095                vc1->SetArea(vc1->GetArea() - leaf->GetArea());
1096                vc2->SetArea(vc2->GetArea() + leaf->GetArea());
1097        }
1098        else
1099        {
1100                vc1->SetVolume(vc1->GetVolume() - leaf->GetVolume());
1101                vc2->SetVolume(vc2->GetVolume() + leaf->GetVolume());
1102        }
1103
1104       
1105        ViewCellInterior *p = dynamic_cast<ViewCellInterior *>(leaf->GetParent());
1106
1107        p->RemoveChildLink(leaf);
1108        vc2->SetupChildLink(leaf);
1109}
1110
1111
1112bool ViewCellsTree::ShuffleLeaves(MergeCandidate &mc) const
1113{
1114        float cost1, cost2;
1115
1116        ViewCellInterior *vc1 = dynamic_cast<ViewCellInterior *>(mc.GetLeftViewCell());
1117        ViewCellInterior *vc2 = dynamic_cast<ViewCellInterior *>(mc.GetRightViewCell());
1118
1119        ViewCell *leaf1 = mc.GetInitialLeftViewCell();
1120        ViewCell *leaf2 = mc.GetInitialRightViewCell();
1121
1122        //-- first test if shuffling would decrease cost
1123        cost1 = GetCostHeuristics(vc1);
1124        cost2 = GetCostHeuristics(vc2);
1125
1126        const float oldCost = cost1 + cost2;
1127       
1128        float shuffledCost1 = Limits::Infinity;
1129        float shuffledCost2 = Limits::Infinity;
1130
1131        if (leaf1)
1132                shuffledCost1 = EvalShuffleCost(leaf1, vc1, vc2);       
1133        if (leaf2)
1134                shuffledCost2 = EvalShuffleCost(leaf2, vc2, vc1);
1135
1136        // if cost of shuffle is less than old cost => shuffle
1137        if ((oldCost <= shuffledCost1) && (oldCost <= shuffledCost2))
1138                return false;
1139       
1140        if (shuffledCost1 < shuffledCost2)
1141        {
1142                if (leaf1)
1143                        ShuffleLeaf(leaf1, vc1, vc2);
1144                mc.mInitialLeftViewCell = NULL;
1145        }
1146        else
1147        {
1148                if (leaf2)
1149                        ShuffleLeaf(leaf2, vc2, vc1);
1150                mc.mInitialRightViewCell = NULL;
1151        }
1152
1153        return true;
1154}
1155
1156
1157float ViewCellsTree::GetVariance(ViewCell *vc) const
1158{
1159        const int upper = mViewCellsManager->GetMaxPvsSize();
1160        const int lower = mViewCellsManager->GetMinPvsSize();
1161
1162        if (1)
1163        {
1164                const float penalty = EvalPvsPenalty(vc->GetPvs().GetSize(), lower, upper);
1165                return (mAvgRenderCost - penalty) * (mAvgRenderCost - penalty) / (float)mNumActiveViewCells;
1166        }
1167
1168    const float leafCost = GetRenderCost(vc);
1169        return (mExpectedCost - leafCost) * (mExpectedCost - leafCost);
1170}
1171
1172
1173float ViewCellsTree::GetDeviation(ViewCell *vc) const
1174{
1175        const int upper = mViewCellsManager->GetMaxPvsSize();
1176        const int lower = mViewCellsManager->GetMinPvsSize();
1177
1178        if (1)
1179        {
1180                const float penalty = EvalPvsPenalty(vc->GetPvs().GetSize(), lower, upper);
1181                return fabs(mAvgRenderCost - penalty) / (float)mNumActiveViewCells;
1182        }
1183
1184    const float renderCost = GetRenderCost(vc);
1185        return fabs(mExpectedCost - renderCost);
1186}
1187
1188
1189
1190float ViewCellsTree::GetRenderCost(ViewCell *vc) const
1191{
1192        if (mUseAreaForPvs)
1193                return vc->GetPvs().GetSize() * vc->GetArea();
1194
1195        return vc->GetPvs().GetSize() * vc->GetVolume();
1196}
1197
1198
1199float ViewCellsTree::GetCostHeuristics(ViewCell *vc) const
1200{
1201        return GetRenderCost(vc) * mRenderCostWeight +
1202                   GetDeviation(vc) * (1.0f - mRenderCostWeight);
1203}
1204
1205
1206bool ViewCellsTree::ValidateMergeCandidate(MergeCandidate &mc) const
1207{
1208        while (mc.mLeftViewCell->mParent)
1209        {
1210                mc.mLeftViewCell = mc.mLeftViewCell->mParent;
1211        }
1212
1213        while (mc.mRightViewCell->mParent)
1214        {
1215                mc.mRightViewCell = mc.mRightViewCell->mParent;
1216        }
1217
1218        return mc.mLeftViewCell != mc.mRightViewCell;
1219}
1220
1221
1222void ViewCellsTree::EvalMergeCost(MergeCandidate &mc) const
1223{
1224        //-- compute pvs difference
1225        const int newPvs =
1226                ComputeMergedPvsSize(mc.mLeftViewCell->GetPvs(),
1227                                                         mc.mRightViewCell->GetPvs());
1228                       
1229        const float newPenalty =
1230                EvalPvsPenalty(newPvs,
1231                                           mViewCellsManager->GetMinPvsSize(),
1232                                           mViewCellsManager->GetMaxPvsSize());
1233
1234        ViewCell *vc1 = mc.mLeftViewCell;
1235        ViewCell *vc2 = mc.mRightViewCell;
1236
1237        //-- compute ratio of old cost
1238        //   (i.e., added size of left and right view cell times pvs size)
1239        //   to new rendering cost (i.e, size of merged view cell times pvs size)
1240        const float oldCost = GetRenderCost(vc1) + GetRenderCost(vc2);
1241
1242    const float newCost = mUseAreaForPvs ?
1243                (float)newPenalty * (vc1->GetArea() + vc2->GetArea()) :
1244                (float)newPenalty * (vc1->GetVolume() + vc2->GetVolume());
1245
1246
1247        // strong penalty if pvs size too large
1248        if (0 && (newPvs > mViewCellsManager->GetMaxPvsSize()))
1249        {
1250                mc.mRenderCost = 1e20f;
1251        }
1252        else
1253        {
1254                mc.mRenderCost = (newCost - oldCost) /
1255                        mViewCellsManager->GetViewSpaceBox().GetVolume();
1256        }       
1257       
1258
1259        //-- merge cost also takes deviation into account
1260        float newDev, oldDev;
1261
1262        if (1)
1263                newDev = fabs(mAvgRenderCost - newPenalty) / (float)mNumActiveViewCells;
1264        else
1265                newDev = fabs(mExpectedCost - newCost) / (float)mNumActiveViewCells;
1266       
1267        oldDev = GetDeviation(vc1) + GetDeviation(vc2);
1268
1269        // compute deviation increase
1270        mc.mDeviationIncr = newDev - oldDev;
1271       
1272        //Debug << "render cost: " << mc.mRenderCost * mRenderCostWeight << endl;
1273        //Debug << "standard deviation: " << mc.mDeviationIncr * mRenderCostWeight << endl;
1274}
1275
1276void ViewCellsTree::CompressViewCellsPvs()
1277{
1278        if (!mIsCompressed)
1279        {
1280                mIsCompressed = true;
1281                CompressViewCellsPvs(mRoot);
1282        }
1283}
1284
1285void ViewCellsTree::CompressViewCellsPvs(ViewCell *root)
1286{
1287        if (!root->IsLeaf())
1288        {
1289                ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(root);
1290
1291        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1292               
1293                // compress child sets first
1294                for (it = interior->mChildren.begin(); it != it_end; ++ it)
1295                {
1296                        CompressViewCellsPvs(*it);
1297                }
1298
1299                // compress root node
1300                PropagateUpVisibility(interior);
1301        }
1302}
1303
1304
1305void ViewCellsTree::CollectBestViewCellSet(ViewCellContainer &viewCells,
1306                                                                                   const int numViewCells)
1307{
1308        TraversalQueue tqueue;
1309        tqueue.push(mRoot);
1310       
1311        while (!tqueue.empty())
1312        {
1313                ViewCell *vc = tqueue.top();
1314               
1315                // save the view cells if it is a leaf or if enough view cells have already been traversed
1316                // because of the priority queue, this will be the optimal set of v
1317                if (vc->IsLeaf() || ((viewCells.size() + tqueue.size()) >= numViewCells))
1318                {
1319                        // todo: should be done with a function taking the active flag and some
1320                        // time stamp so I don't have to reset view cells, this also means that
1321                        // the leaf view cells can be set active fist
1322                        vc->mIsActive = true;
1323                        viewCells.push_back(vc);
1324                }
1325                else
1326                {       
1327                        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
1328
1329                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1330
1331                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
1332                        {
1333                                tqueue.push(*it);
1334                        }
1335                }
1336
1337                tqueue.pop();
1338        }
1339}
1340       
1341
1342void ViewCellsTree::PropagateUpVisibility(ViewCellInterior *interior)
1343{
1344        Intersectable::NewMail((int)interior->mChildren.size());
1345
1346        ViewCellContainer::const_iterator cit, cit_end = interior->mChildren.end();
1347
1348        ObjectPvsMap::const_iterator oit;
1349
1350        // mail all objects in the leaf sets
1351        // we are interested in the objects which are present in all leaves
1352        // => count how often an object is part of a child set
1353        for (cit = interior->mChildren.begin(); cit != cit_end; ++ cit)
1354        {
1355                ViewCell *vc = *cit;
1356
1357                ObjectPvsMap::const_iterator oit_end = vc->GetPvs().mEntries.end();
1358
1359                for (oit = vc->GetPvs().mEntries.begin(); oit != oit_end; ++ oit)
1360                {
1361                        Intersectable *obj = (*oit).first;
1362                        if ((cit == interior->mChildren.begin()) && !obj->Mailed())
1363                                obj->Mail();
1364                       
1365                        int incm = obj->IncMail();
1366                }
1367        }
1368
1369        interior->GetPvs().mEntries.clear();
1370       
1371       
1372        // only the objects which are present in all leaf pvs
1373        // should remain in the parent pvs
1374        // these are the objects which have been mailed in all children
1375        for (cit = interior->mChildren.begin(); cit != cit_end; ++ cit)
1376        {
1377                ViewCell *vc = *cit;
1378
1379                ObjectPvsMap::const_iterator oit_end = vc->GetPvs().mEntries.end();
1380
1381                for (oit = vc->GetPvs().mEntries.begin(); oit != oit_end; ++ oit)
1382                {               
1383                        if ((*oit).first->Mailed((int)interior->mChildren.size()))
1384                        {       
1385                                interior->GetPvs().AddSample((*oit).first, (*oit).second.mSumPdf);
1386                        }
1387                }
1388        }
1389
1390
1391
1392        // delete all the objects from the leaf sets which were moved to parent pvs
1393        ObjectPvsMap::const_iterator oit_end = interior->GetPvs().mEntries.end();
1394
1395        for (oit = interior->GetPvs().mEntries.begin(); oit != oit_end; ++ oit)
1396        {
1397                for (cit = interior->mChildren.begin(); cit != cit_end; ++ cit)
1398                {
1399                        if (!(*cit)->GetPvs().RemoveSample((*oit).first, Limits::Infinity))
1400                                Debug << "should not come here!" << endl;
1401                }
1402        }
1403
1404        int dummy = interior->GetPvs().GetSize();
1405
1406        for (cit = interior->mChildren.begin(); cit != cit_end; ++ cit)
1407        {
1408                dummy += (*cit)->GetPvs().GetSize();
1409        }
1410
1411}
1412
1413
1414
1415void ViewCellsTree::GetPvs(ViewCell *vc, ObjectPvs &pvs) const
1416{
1417        Intersectable::NewMail();
1418
1419        if (!mIsCompressed)
1420                pvs = vc->GetPvs();
1421
1422        int pvsSize = 0;
1423        ViewCell *root = vc;
1424       
1425        // also add pvs from this view cell to root
1426        while (root->GetParent())
1427        {
1428                root = root->GetParent();
1429                pvs.AddPvs(root->GetPvs());
1430        }
1431
1432        stack<ViewCell *> tstack;
1433        tstack.push(vc);
1434
1435        while (!tstack.empty())
1436        {
1437                vc = tstack.top();
1438                tstack.pop();
1439
1440                pvs.AddPvs(vc->GetPvs());
1441
1442                if (!vc->IsLeaf())
1443                {
1444                        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
1445
1446                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1447
1448                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
1449                        {
1450                                tstack.push(*it);
1451                        }               
1452                }
1453        }
1454}
1455
1456
1457int ViewCellsTree::GetPvsSize(ViewCell *vc) const
1458{
1459        Intersectable::NewMail();
1460
1461        if (!mIsCompressed)
1462                return vc->GetPvs().GetSize();
1463
1464        int pvsSize = 0;
1465        ViewCell *root = vc;
1466       
1467        // also add pvs from this view cell to root
1468        while (root->GetParent())
1469        {
1470                root = root->GetParent();
1471                pvsSize += CountDiffPvs(root);
1472        }
1473
1474        stack<ViewCell *> tstack;
1475        tstack.push(vc);
1476
1477        Debug << "current size: " << pvsSize << endl;
1478
1479        while (!tstack.empty())
1480        {
1481                vc = tstack.top();
1482                tstack.pop();
1483
1484                pvsSize += CountDiffPvs(vc);
1485
1486                if (!vc->IsLeaf())
1487                {
1488                        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
1489
1490                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1491
1492                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
1493                        {
1494                                tstack.push(*it);
1495                        }               
1496                }
1497        }
1498
1499        return pvsSize; 
1500
1501}
1502
1503
1504float ViewCellsTree::GetMemoryCost(ViewCell *vc) const
1505{
1506        const float entrySize =
1507                sizeof(PvsData<Intersectable *>) + sizeof(Intersectable *);
1508
1509        return (float)GetNumPvsEntries(vc) * entrySize;
1510}
1511
1512
1513int ViewCellsTree::GetNumPvsEntries(ViewCell *vc) const
1514{
1515        int pvsSize = 0;
1516        // only count leaves for uncompressed method for fairness
1517        if (mIsCompressed || vc->IsLeaf())
1518                pvsSize = vc->GetPvs().GetSize();
1519
1520        if (!vc->IsLeaf())
1521        {
1522                ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
1523
1524                ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1525
1526                for (it = interior->mChildren.begin(); it != it_end; ++ it)
1527                {
1528                        pvsSize += GetNumPvsEntries(*it);
1529                }
1530        }
1531
1532        return pvsSize;         
1533}
1534
1535
1536bool ViewCellsTree::IsCompressed() const
1537{
1538        return mIsCompressed;
1539}
1540
1541
1542ViewCell *ViewCellsTree::GetActiveViewCell(ViewCell *vc) const
1543{
1544        while (vc->GetParent() && !vc->mIsActive)
1545        {
1546                vc = vc->GetParent();
1547        }
1548
1549        return vc;
1550}
1551
1552
1553/**************************************************************************/
1554/*                     MergeCandidate implementation                      */
1555/**************************************************************************/
1556
1557
1558MergeCandidate::MergeCandidate(ViewCell *l, ViewCell *r):
1559mRenderCost(0),
1560mDeviationIncr(0),
1561mLeftViewCell(l),
1562mRightViewCell(r),
1563mInitialLeftViewCell(l),
1564mInitialRightViewCell(r)
1565{
1566        //EvalMergeCost();
1567}
1568
1569
1570void MergeCandidate::SetRightViewCell(ViewCell *v)
1571{
1572        mRightViewCell = v;
1573}
1574
1575
1576void MergeCandidate::SetLeftViewCell(ViewCell *v)
1577{
1578        mLeftViewCell = v;
1579}
1580
1581
1582ViewCell *MergeCandidate::GetRightViewCell() const
1583{
1584        return mRightViewCell;
1585}
1586
1587
1588ViewCell *MergeCandidate::GetLeftViewCell() const
1589{
1590        return mLeftViewCell;
1591}
1592
1593
1594ViewCell *MergeCandidate::GetInitialRightViewCell() const
1595{
1596        return mInitialRightViewCell;
1597}
1598
1599
1600ViewCell *MergeCandidate::GetInitialLeftViewCell() const
1601{
1602        return mInitialLeftViewCell;
1603}
1604
1605
1606bool MergeCandidate::IsValid() const
1607{
1608        return !(mLeftViewCell->mParent || mRightViewCell->mParent);
1609}
1610
1611
1612float MergeCandidate::GetRenderCost() const
1613{
1614        return mRenderCost;
1615}
1616
1617
1618float MergeCandidate::GetDeviationIncr() const
1619{
1620        return mDeviationIncr;
1621}
1622
1623
1624float MergeCandidate::GetMergeCost() const
1625{
1626        return mRenderCost * sRenderCostWeight +
1627                   mDeviationIncr * (1.0f - sRenderCostWeight);
1628}
1629
1630
1631/************************************************************************/
1632/*                    MergeStatistics implementation                    */
1633/************************************************************************/
1634
1635
1636void MergeStatistics::Print(ostream &app) const
1637{
1638        app << "===== Merge statistics ===============\n";
1639
1640        app << setprecision(4);
1641
1642        app << "#N_CTIME ( Overall time [s] )\n" << Time() << " \n";
1643
1644        app << "#N_CCTIME ( Collect candidates time [s] )\n" << collectTime * 1e-3f << " \n";
1645
1646        app << "#N_MTIME ( Merge time [s] )\n" << mergeTime * 1e-3f << " \n";
1647
1648        app << "#N_NODES ( Number of nodes before merge )\n" << nodes << "\n";
1649
1650        app << "#N_CANDIDATES ( Number of merge candidates )\n" << candidates << "\n";
1651
1652        app << "#N_MERGEDSIBLINGS ( Number of merged siblings )\n" << siblings << "\n";
1653
1654        app << "#OVERALLCOST ( overall merge cost )\n" << overallCost << "\n";
1655
1656        app << "#N_MERGEDNODES ( Number of merged nodes )\n" << merged << "\n";
1657
1658        app << "#MAX_TREEDIST ( Maximal distance in tree of merged leaves )\n" << maxTreeDist << "\n";
1659
1660        app << "#AVG_TREEDIST ( Average distance in tree of merged leaves )\n" << AvgTreeDist() << "\n";
1661
1662        app << "#EXPECTEDCOST ( expected render cost )\n" << expectedRenderCost << "\n";
1663
1664        app << "#DEVIATION ( deviation )\n" << deviation << "\n";
1665
1666        app << "#HEURISTICS ( heuristics )\n" << heuristics << "\n";
1667       
1668
1669        app << "===== END OF BspTree statistics ==========\n";
1670}
Note: See TracBrowser for help on using the repository browser.