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

Revision 601, 39.6 KB checked in by mattausch, 18 years ago (diff)
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                vc->SetVolume(r->GetVolume() + r->GetVolume());
890       
891        // important so other merge candidates sharing this view cell
892        // are notified that the merge cost must be updated!!
893        vc->Mail();
894
895        const int pvs1 = l->GetPvs().GetSize();
896        const int pvs2 = r->GetPvs().GetSize();
897
898
899        // new view cells are stored in this vector
900        mMergedViewCells.push_back(vc);
901
902        pvsDiff = vc->GetPvs().GetSize() - pvs1 - pvs2;
903
904        return vc;
905}
906
907
908
909int ViewCellsTree::RefineViewCells(const VssRayContainer &rays,
910                                                                   const ObjectContainer &objects)
911{
912        Debug << "refining " << (int)mMergeQueue.size() << " candidates " << endl;
913
914        // intermediate buffer for shuffled view cells
915        vector<MergeCandidate> buf;
916        buf.reserve(mMergeQueue.size());
917                       
918        // Use priority queue of remaining leaf pairs
919        // The candidates either share the same view cells or
920        // are border leaves which share a boundary.
921        // We test if they can be shuffled, i.e.,
922        // either one leaf is made part of one view cell or the other
923        // leaf is made part of the other view cell. It is tested if the
924        // remaining view cells are "better" than the old ones.
925       
926        const int numPasses = 3;
927        int pass = 0;
928        int passShuffled = 0;
929        int shuffled = 0;
930        int shuffledViewCells = 0;
931
932        ViewCell::NewMail();
933       
934        while (!mMergeQueue.empty())
935        {
936                MergeCandidate mc = mMergeQueue.top();
937                mMergeQueue.pop();
938
939                // both view cells equal or already shuffled
940                if ((mc.GetLeftViewCell() == mc.GetRightViewCell()) ||
941                        mc.GetLeftViewCell()->IsLeaf() || mc.GetRightViewCell()->IsLeaf())
942                {                       
943                        continue;
944                }
945
946                // candidate for shuffling
947                const bool wasShuffled = ShuffleLeaves(mc);
948               
949                // shuffled or put into other queue for further refine
950                if (wasShuffled)
951                {
952                        ++ passShuffled;
953
954                        if (!mc.GetLeftViewCell()->Mailed())
955                        {
956                                mc.GetLeftViewCell()->Mail();
957                                ++ shuffledViewCells;
958                        }
959                        if (!mc.GetRightViewCell()->Mailed())
960                        {
961                                mc.GetRightViewCell()->Mail();
962                                ++ shuffledViewCells;
963                        }
964                }
965
966                // put back into intermediate vector
967                buf.push_back(mc);
968        }
969
970
971        //-- in the end, the candidates must be in the mergequeue again
972        //   with the correct cost
973
974        cout << "reset merge queue ... ";
975       
976       
977        vector<MergeCandidate>::const_iterator bit, bit_end = buf.end();
978       
979        for (bit = buf.begin(); bit != bit_end; ++ bit)
980        {   
981                MergeCandidate mc = *bit;
982                // recalculate cost
983                if (ValidateMergeCandidate(mc))
984                {
985                        EvalMergeCost(mc);
986                        mMergeQueue.push(mc);   
987                }
988        }
989
990        cout << "finished" << endl;
991
992        return shuffledViewCells;
993}
994
995
996
997
998inline int AddedPvsSize(ObjectPvs pvs1, const ObjectPvs &pvs2)
999{
1000        return pvs1.AddPvs(pvs2);
1001}
1002
1003
1004// recomputes pvs size minus pvs of leaf l
1005#if 0
1006inline int SubtractedPvsSize(BspViewCell *vc, BspLeaf *l, const ObjectPvs &pvs2)
1007{
1008        ObjectPvs pvs;
1009        vector<BspLeaf *>::const_iterator it, it_end = vc->mLeaves.end();
1010        for (it = vc->mLeaves.begin(); it != vc->mLeaves.end(); ++ it)
1011                if (*it != l)
1012                        pvs.AddPvs(*(*it)->mPvs);
1013        return pvs.GetSize();
1014}
1015#endif
1016
1017
1018// computes pvs1 minus pvs2
1019inline int SubtractedPvsSize(ObjectPvs pvs1, const ObjectPvs &pvs2)
1020{
1021        return pvs1.SubtractPvs(pvs2);
1022}
1023
1024
1025float ViewCellsTree::EvalShuffleCost(ViewCell *leaf,
1026                                                                         ViewCellInterior *vc1,
1027                                                                         ViewCellInterior *vc2) const
1028{
1029        //const int pvs1 = SubtractedPvsSize(vc1, leaf, *leaf->mPvs);
1030        const int pvs1 = SubtractedPvsSize(vc1->GetPvs(), leaf->GetPvs());
1031        const int pvs2 = AddedPvsSize(vc2->GetPvs(), leaf->GetPvs());
1032
1033        const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize();
1034        const int upperPvsLimit = mViewCellsManager->GetMaxPvsSize();
1035
1036        const float pvsPenalty1 =
1037                EvalPvsPenalty(pvs1, lowerPvsLimit, upperPvsLimit);
1038
1039        const float pvsPenalty2 =
1040                EvalPvsPenalty(pvs2, lowerPvsLimit, upperPvsLimit);
1041
1042
1043        // don't shuffle leaves with pvs > max
1044        if (0 && (pvs1 + pvs2 > mViewCellsManager->GetMaxPvsSize()))
1045        {
1046                return 1e20f;
1047        }
1048
1049        float p1, p2;
1050
1051    if (mUseAreaForPvs)
1052        {
1053                p1 = vc1->GetArea() - leaf->GetArea();
1054                p2 = vc2->GetArea() + leaf->GetArea();
1055        }
1056        else
1057        {
1058                p1 = vc1->GetVolume() - leaf->GetVolume();
1059                p2 = vc2->GetVolume() + leaf->GetVolume();
1060        }
1061
1062        const float renderCost1 = pvsPenalty1 * p1;
1063        const float renderCost2 = pvsPenalty2 * p2;
1064
1065        float dev1, dev2;
1066
1067        if (1)
1068        {
1069                dev1 = fabs(mAvgRenderCost - pvsPenalty1);
1070                dev2 = fabs(mAvgRenderCost - pvsPenalty2);
1071        }
1072        else
1073        {
1074                dev1 = fabs(mExpectedCost - renderCost1);
1075                dev2 = fabs(mExpectedCost - renderCost2);
1076        }
1077       
1078        return mRenderCostWeight * (renderCost1 + renderCost2) +
1079                  (1.0f - mRenderCostWeight) * (dev1 + dev2) / (float)mNumActiveViewCells;
1080}
1081
1082
1083void ViewCellsTree::ShuffleLeaf(ViewCell *leaf,
1084                                                                ViewCellInterior *vc1,
1085                                                                ViewCellInterior *vc2) const
1086{
1087        // compute new pvs and area
1088        // TODO change
1089        vc1->GetPvs().SubtractPvs(leaf->GetPvs());
1090        vc2->GetPvs().AddPvs(leaf->GetPvs());
1091       
1092        if (mUseAreaForPvs)
1093        {
1094                vc1->SetArea(vc1->GetArea() - leaf->GetArea());
1095                vc2->SetArea(vc2->GetArea() + leaf->GetArea());
1096        }
1097        else
1098        {
1099                vc1->SetVolume(vc1->GetVolume() - leaf->GetVolume());
1100                vc2->SetVolume(vc2->GetVolume() + leaf->GetVolume());
1101        }
1102
1103       
1104        ViewCellInterior *p = dynamic_cast<ViewCellInterior *>(leaf->GetParent());
1105
1106        p->RemoveChildLink(leaf);
1107        vc2->SetupChildLink(leaf);
1108}
1109
1110
1111bool ViewCellsTree::ShuffleLeaves(MergeCandidate &mc) const
1112{
1113        float cost1, cost2;
1114
1115        ViewCellInterior *vc1 = dynamic_cast<ViewCellInterior *>(mc.GetLeftViewCell());
1116        ViewCellInterior *vc2 = dynamic_cast<ViewCellInterior *>(mc.GetRightViewCell());
1117
1118        ViewCell *leaf1 = mc.GetInitialLeftViewCell();
1119        ViewCell *leaf2 = mc.GetInitialRightViewCell();
1120
1121        //-- first test if shuffling would decrease cost
1122        cost1 = GetCostHeuristics(vc1);
1123        cost2 = GetCostHeuristics(vc2);
1124
1125        const float oldCost = cost1 + cost2;
1126       
1127        float shuffledCost1 = Limits::Infinity;
1128        float shuffledCost2 = Limits::Infinity;
1129
1130        if (leaf1)
1131                shuffledCost1 = EvalShuffleCost(leaf1, vc1, vc2);       
1132        if (leaf2)
1133                shuffledCost2 = EvalShuffleCost(leaf2, vc2, vc1);
1134
1135        // if cost of shuffle is less than old cost => shuffle
1136        if ((oldCost <= shuffledCost1) && (oldCost <= shuffledCost2))
1137                return false;
1138       
1139        if (shuffledCost1 < shuffledCost2)
1140        {
1141                if (leaf1)
1142                        ShuffleLeaf(leaf1, vc1, vc2);
1143                mc.mInitialLeftViewCell = NULL;
1144        }
1145        else
1146        {
1147                if (leaf2)
1148                        ShuffleLeaf(leaf2, vc2, vc1);
1149                mc.mInitialRightViewCell = NULL;
1150        }
1151
1152        return true;
1153}
1154
1155
1156float ViewCellsTree::GetVariance(ViewCell *vc) const
1157{
1158        const int upper = mViewCellsManager->GetMaxPvsSize();
1159        const int lower = mViewCellsManager->GetMinPvsSize();
1160
1161        if (1)
1162        {
1163                const float penalty = EvalPvsPenalty(vc->GetPvs().GetSize(), lower, upper);
1164                return (mAvgRenderCost - penalty) * (mAvgRenderCost - penalty) / (float)mNumActiveViewCells;
1165        }
1166
1167    const float leafCost = GetRenderCost(vc);
1168        return (mExpectedCost - leafCost) * (mExpectedCost - leafCost);
1169}
1170
1171
1172float ViewCellsTree::GetDeviation(ViewCell *vc) const
1173{
1174        const int upper = mViewCellsManager->GetMaxPvsSize();
1175        const int lower = mViewCellsManager->GetMinPvsSize();
1176
1177        if (1)
1178        {
1179                const float penalty = EvalPvsPenalty(vc->GetPvs().GetSize(), lower, upper);
1180                return fabs(mAvgRenderCost - penalty) / (float)mNumActiveViewCells;
1181        }
1182
1183    const float renderCost = GetRenderCost(vc);
1184        return fabs(mExpectedCost - renderCost);
1185}
1186
1187
1188
1189float ViewCellsTree::GetRenderCost(ViewCell *vc) const
1190{
1191        if (mUseAreaForPvs)
1192                return vc->GetPvs().GetSize() * vc->GetArea();
1193
1194        return vc->GetPvs().GetSize() * vc->GetVolume();
1195}
1196
1197
1198float ViewCellsTree::GetCostHeuristics(ViewCell *vc) const
1199{
1200        return GetRenderCost(vc) * mRenderCostWeight +
1201                   GetDeviation(vc) * (1.0f - mRenderCostWeight);
1202}
1203
1204
1205bool ViewCellsTree::ValidateMergeCandidate(MergeCandidate &mc) const
1206{
1207        while (mc.mLeftViewCell->mParent)
1208        {
1209                mc.mLeftViewCell = mc.mLeftViewCell->mParent;
1210        }
1211
1212        while (mc.mRightViewCell->mParent)
1213        {
1214                mc.mRightViewCell = mc.mRightViewCell->mParent;
1215        }
1216
1217        return mc.mLeftViewCell != mc.mRightViewCell;
1218}
1219
1220
1221void ViewCellsTree::EvalMergeCost(MergeCandidate &mc) const
1222{
1223        //-- compute pvs difference
1224        const int newPvs =
1225                ComputeMergedPvsSize(mc.mLeftViewCell->GetPvs(),
1226                                                         mc.mRightViewCell->GetPvs());
1227                       
1228        const float newPenalty =
1229                EvalPvsPenalty(newPvs,
1230                                           mViewCellsManager->GetMinPvsSize(),
1231                                           mViewCellsManager->GetMaxPvsSize());
1232
1233        ViewCell *vc1 = mc.mLeftViewCell;
1234        ViewCell *vc2 = mc.mRightViewCell;
1235
1236        //-- compute ratio of old cost
1237        //   (i.e., added size of left and right view cell times pvs size)
1238        //   to new rendering cost (i.e, size of merged view cell times pvs size)
1239        const float oldCost = GetRenderCost(vc1) + GetRenderCost(vc2);
1240
1241    const float newCost = mUseAreaForPvs ?
1242                (float)newPenalty * (vc1->GetArea() + vc2->GetArea()) :
1243                (float)newPenalty * (vc1->GetVolume() + vc2->GetVolume());
1244
1245
1246        // strong penalty if pvs size too large
1247        if (0 && (newPvs > mViewCellsManager->GetMaxPvsSize()))
1248        {
1249                mc.mRenderCost = 1e20f;
1250        }
1251        else
1252        {
1253                mc.mRenderCost = (newCost - oldCost) /
1254                        mViewCellsManager->GetViewSpaceBox().GetVolume();
1255        }       
1256       
1257
1258        //-- merge cost also takes deviation into account
1259        float newDev, oldDev;
1260
1261        if (1)
1262                newDev = fabs(mAvgRenderCost - newPenalty) / (float)mNumActiveViewCells;
1263        else
1264                newDev = fabs(mExpectedCost - newCost) / (float)mNumActiveViewCells;
1265       
1266        oldDev = GetDeviation(vc1) + GetDeviation(vc2);
1267
1268        // compute deviation increase
1269        mc.mDeviationIncr = newDev - oldDev;
1270       
1271        //Debug << "render cost: " << mc.mRenderCost * mRenderCostWeight << endl;
1272        //Debug << "standard deviation: " << mc.mDeviationIncr * mRenderCostWeight << endl;
1273}
1274
1275void ViewCellsTree::CompressViewCellsPvs()
1276{
1277        if (!mIsCompressed)
1278        {
1279                mIsCompressed = true;
1280                CompressViewCellsPvs(mRoot);
1281        }
1282}
1283
1284void ViewCellsTree::CompressViewCellsPvs(ViewCell *root)
1285{
1286        if (!root->IsLeaf())
1287        {
1288                ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(root);
1289
1290        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1291               
1292                // compress child sets first
1293                for (it = interior->mChildren.begin(); it != it_end; ++ it)
1294                {
1295                        CompressViewCellsPvs(*it);
1296                }
1297
1298                // compress root node
1299                PropagateUpVisibility(interior);
1300        }
1301}
1302
1303
1304void ViewCellsTree::CollectBestViewCellSet(ViewCellContainer &viewCells,
1305                                                                                   const int numViewCells)
1306{
1307        TraversalQueue tqueue;
1308        tqueue.push(mRoot);
1309       
1310        while (!tqueue.empty())
1311        {
1312                ViewCell *vc = tqueue.top();
1313               
1314                // save the view cells if it is a leaf or if enough view cells have already been traversed
1315                // because of the priority queue, this will be the optimal set of v
1316                if (vc->IsLeaf() || ((viewCells.size() + tqueue.size()) >= numViewCells))
1317                {
1318                        // todo: should be done with a function taking the active flag and some
1319                        // time stamp so I don't have to reset view cells, this also means that
1320                        // the leaf view cells can be set active fist
1321                        vc->mIsActive = true;
1322                        viewCells.push_back(vc);
1323                }
1324                else
1325                {       
1326                        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
1327
1328                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1329
1330                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
1331                        {
1332                                tqueue.push(*it);
1333                        }
1334                }
1335
1336                tqueue.pop();
1337        }
1338}
1339       
1340
1341void ViewCellsTree::PropagateUpVisibility(ViewCellInterior *interior)
1342{
1343        Intersectable::NewMail((int)interior->mChildren.size());
1344
1345        ViewCellContainer::const_iterator cit, cit_end = interior->mChildren.end();
1346
1347        ObjectPvsMap::const_iterator oit;
1348
1349        // mail all objects in the leaf sets
1350        // we are interested in the objects which are present in all leaves
1351        // => count how often an object is part of a child set
1352        for (cit = interior->mChildren.begin(); cit != cit_end; ++ cit)
1353        {
1354                ViewCell *vc = *cit;
1355
1356                ObjectPvsMap::const_iterator oit_end = vc->GetPvs().mEntries.end();
1357
1358                for (oit = vc->GetPvs().mEntries.begin(); oit != oit_end; ++ oit)
1359                {
1360                        Intersectable *obj = (*oit).first;
1361                        if ((cit == interior->mChildren.begin()) && !obj->Mailed())
1362                                obj->Mail();
1363                       
1364                        int incm = obj->IncMail();
1365                }
1366        }
1367
1368        interior->GetPvs().mEntries.clear();
1369       
1370       
1371        // only the objects which are present in all leaf pvs
1372        // should remain in the parent pvs
1373        // these are the objects which have been mailed in all children
1374        for (cit = interior->mChildren.begin(); cit != cit_end; ++ cit)
1375        {
1376                ViewCell *vc = *cit;
1377
1378                ObjectPvsMap::const_iterator oit_end = vc->GetPvs().mEntries.end();
1379
1380                for (oit = vc->GetPvs().mEntries.begin(); oit != oit_end; ++ oit)
1381                {               
1382                        if ((*oit).first->Mailed((int)interior->mChildren.size()))
1383                        {       
1384                                interior->GetPvs().AddSample((*oit).first, (*oit).second.mSumPdf);
1385                        }
1386                }
1387        }
1388
1389
1390
1391        // delete all the objects from the leaf sets which were moved to parent pvs
1392        ObjectPvsMap::const_iterator oit_end = interior->GetPvs().mEntries.end();
1393
1394        for (oit = interior->GetPvs().mEntries.begin(); oit != oit_end; ++ oit)
1395        {
1396                for (cit = interior->mChildren.begin(); cit != cit_end; ++ cit)
1397                {
1398                        if (!(*cit)->GetPvs().RemoveSample((*oit).first, Limits::Infinity))
1399                                Debug << "should not come here!" << endl;
1400                }
1401        }
1402
1403        int dummy = interior->GetPvs().GetSize();
1404
1405        for (cit = interior->mChildren.begin(); cit != cit_end; ++ cit)
1406        {
1407                dummy += (*cit)->GetPvs().GetSize();
1408        }
1409
1410}
1411
1412
1413
1414void ViewCellsTree::GetPvs(ViewCell *vc, ObjectPvs &pvs) const
1415{
1416        Intersectable::NewMail();
1417
1418        if (!mIsCompressed)
1419                pvs = vc->GetPvs();
1420
1421        int pvsSize = 0;
1422        ViewCell *root = vc;
1423       
1424        // also add pvs from this view cell to root
1425        while (root->GetParent())
1426        {
1427                root = root->GetParent();
1428                pvs.AddPvs(root->GetPvs());
1429        }
1430
1431        stack<ViewCell *> tstack;
1432        tstack.push(vc);
1433
1434        while (!tstack.empty())
1435        {
1436                vc = tstack.top();
1437                tstack.pop();
1438
1439                pvs.AddPvs(vc->GetPvs());
1440
1441                if (!vc->IsLeaf())
1442                {
1443                        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
1444
1445                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1446
1447                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
1448                        {
1449                                tstack.push(*it);
1450                        }               
1451                }
1452        }
1453}
1454
1455
1456int ViewCellsTree::GetPvsSize(ViewCell *vc) const
1457{
1458        Intersectable::NewMail();
1459
1460        if (!mIsCompressed)
1461                return vc->GetPvs().GetSize();
1462
1463        int pvsSize = 0;
1464        ViewCell *root = vc;
1465       
1466        // also add pvs from this view cell to root
1467        while (root->GetParent())
1468        {
1469                root = root->GetParent();
1470                pvsSize += CountDiffPvs(root);
1471        }
1472
1473        stack<ViewCell *> tstack;
1474        tstack.push(vc);
1475
1476        Debug << "current size: " << pvsSize << endl;
1477
1478        while (!tstack.empty())
1479        {
1480                vc = tstack.top();
1481                tstack.pop();
1482
1483                pvsSize += CountDiffPvs(vc);
1484
1485                if (!vc->IsLeaf())
1486                {
1487                        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
1488
1489                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1490
1491                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
1492                        {
1493                                tstack.push(*it);
1494                        }               
1495                }
1496        }
1497
1498        return pvsSize; 
1499
1500}
1501
1502
1503float ViewCellsTree::GetMemoryCost(ViewCell *vc) const
1504{
1505        const float entrySize =
1506                sizeof(PvsData<Intersectable *>) + sizeof(Intersectable *);
1507
1508        return (float)GetNumPvsEntries(vc) * entrySize;
1509}
1510
1511
1512int ViewCellsTree::GetNumPvsEntries(ViewCell *vc) const
1513{
1514        int pvsSize = 0;
1515        // only count leaves for uncompressed method for fairness
1516        if (mIsCompressed || vc->IsLeaf())
1517                pvsSize = vc->GetPvs().GetSize();
1518
1519        if (!vc->IsLeaf())
1520        {
1521                ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
1522
1523                ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1524
1525                for (it = interior->mChildren.begin(); it != it_end; ++ it)
1526                {
1527                        pvsSize += GetNumPvsEntries(*it);
1528                }
1529        }
1530
1531        return pvsSize;         
1532}
1533
1534
1535bool ViewCellsTree::IsCompressed() const
1536{
1537        return mIsCompressed;
1538}
1539
1540
1541ViewCell *ViewCellsTree::GetActiveViewCell(ViewCell *vc) const
1542{
1543        while (vc->GetParent() && !vc->mIsActive)
1544        {
1545                vc = vc->GetParent();
1546        }
1547
1548        return vc;
1549}
1550
1551
1552/**************************************************************************/
1553/*                     MergeCandidate implementation                      */
1554/**************************************************************************/
1555
1556
1557MergeCandidate::MergeCandidate(ViewCell *l, ViewCell *r):
1558mRenderCost(0),
1559mDeviationIncr(0),
1560mLeftViewCell(l),
1561mRightViewCell(r),
1562mInitialLeftViewCell(l),
1563mInitialRightViewCell(r)
1564{
1565        //EvalMergeCost();
1566}
1567
1568
1569void MergeCandidate::SetRightViewCell(ViewCell *v)
1570{
1571        mRightViewCell = v;
1572}
1573
1574
1575void MergeCandidate::SetLeftViewCell(ViewCell *v)
1576{
1577        mLeftViewCell = v;
1578}
1579
1580
1581ViewCell *MergeCandidate::GetRightViewCell() const
1582{
1583        return mRightViewCell;
1584}
1585
1586
1587ViewCell *MergeCandidate::GetLeftViewCell() const
1588{
1589        return mLeftViewCell;
1590}
1591
1592
1593ViewCell *MergeCandidate::GetInitialRightViewCell() const
1594{
1595        return mInitialRightViewCell;
1596}
1597
1598
1599ViewCell *MergeCandidate::GetInitialLeftViewCell() const
1600{
1601        return mInitialLeftViewCell;
1602}
1603
1604
1605bool MergeCandidate::IsValid() const
1606{
1607        return !(mLeftViewCell->mParent || mRightViewCell->mParent);
1608}
1609
1610
1611float MergeCandidate::GetRenderCost() const
1612{
1613        return mRenderCost;
1614}
1615
1616
1617float MergeCandidate::GetDeviationIncr() const
1618{
1619        return mDeviationIncr;
1620}
1621
1622
1623float MergeCandidate::GetMergeCost() const
1624{
1625        return mRenderCost * sRenderCostWeight +
1626                   mDeviationIncr * (1.0f - sRenderCostWeight);
1627}
1628
1629
1630/************************************************************************/
1631/*                    MergeStatistics implementation                    */
1632/************************************************************************/
1633
1634
1635void MergeStatistics::Print(ostream &app) const
1636{
1637        app << "===== Merge statistics ===============\n";
1638
1639        app << setprecision(4);
1640
1641        app << "#N_CTIME ( Overall time [s] )\n" << Time() << " \n";
1642
1643        app << "#N_CCTIME ( Collect candidates time [s] )\n" << collectTime * 1e-3f << " \n";
1644
1645        app << "#N_MTIME ( Merge time [s] )\n" << mergeTime * 1e-3f << " \n";
1646
1647        app << "#N_NODES ( Number of nodes before merge )\n" << nodes << "\n";
1648
1649        app << "#N_CANDIDATES ( Number of merge candidates )\n" << candidates << "\n";
1650
1651        app << "#N_MERGEDSIBLINGS ( Number of merged siblings )\n" << siblings << "\n";
1652
1653        app << "#OVERALLCOST ( overall merge cost )\n" << overallCost << "\n";
1654
1655        app << "#N_MERGEDNODES ( Number of merged nodes )\n" << merged << "\n";
1656
1657        app << "#MAX_TREEDIST ( Maximal distance in tree of merged leaves )\n" << maxTreeDist << "\n";
1658
1659        app << "#AVG_TREEDIST ( Average distance in tree of merged leaves )\n" << AvgTreeDist() << "\n";
1660
1661        app << "#EXPECTEDCOST ( expected render cost )\n" << expectedRenderCost << "\n";
1662
1663        app << "#DEVIATION ( deviation )\n" << deviation << "\n";
1664
1665        app << "#HEURISTICS ( heuristics )\n" << heuristics << "\n";
1666       
1667
1668        app << "===== END OF BspTree statistics ==========\n";
1669}
Note: See TracBrowser for help on using the repository browser.