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

Revision 604, 40.2 KB checked in by mattausch, 18 years ago (diff)

fixed statistics
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        mStats << "#Pass\n" << pass << endl
523                << "#Merged\n" << mergeStats.merged << endl
524                << "#Viewcells\n" << realNumActiveViewCells << endl
525                << "#RenderCostIncrease\n" << 0 << endl
526                << "#TotalRenderCost\n" << totalRenderCost << endl
527                << "#CurrentPvs\n" << 0 << endl
528                << "#ExpectedCost\n" << realExpectedCost << endl
529                << "#AvgRenderCost\n" << realAvgRenderCost << endl
530                << "#Deviation\n" << mDeviation << endl
531                << "#TotalPvs\n" << totalPvs << endl
532                << "#PvsSizeDecrease\n" << 0 << endl
533                << "#Volume\n" << 0 << endl
534                << "#Dummy\n" << 0 << endl;
535
536        //-- use priority queue to merge leaf pairs
537// HACK
538        //const float maxAvgCost = 350;
539        while (!mMergeQueue.empty())//NumActiveViewCells > mMergeMinViewCells))
540        {
541                //-- reset merge queue if the ratio of current expected cost / real expected cost
542                //   too small or after a given number of merges
543                if ((mergedPerPass > maxMergesPerPass) ||
544                        (avgCostMaxDeviation > mAvgRenderCost / realAvgRenderCost))
545                {
546                        Debug << "************ reset queue *****************\n"
547                                  << "ratios: " << avgCostMaxDeviation
548                                  << " real avg render cost " << realAvgRenderCost << " average render cost " << mAvgRenderCost
549                                  << " merged per pass : " << mergedPerPass << " of maximal " << maxMergesPerPass << endl;
550
551                        Debug << "Values before reset: " 
552                                  << " erc: " << mExpectedCost
553                                  << " avgrc: " << mAvgRenderCost
554                                  << " dev: " << mDeviation << endl;
555       
556                        // adjust render cost
557                        ++ pass;
558
559                        mergedPerPass = 0;
560                        mExpectedCost = realExpectedCost;
561                        mAvgRenderCost = realAvgRenderCost;
562                        mNumActiveViewCells = realNumActiveViewCells;
563                       
564                        const int numMergedViewCells = UpdateActiveViewCells(activeViewCells);
565               
566                        // refines the view cells
567                        // then priorities are recomputed
568                        // and the candidates are put back into merge queue
569                        if (mRefineViewCells)
570                                RefineViewCells(rays, objects);
571                        else
572                                ResetMergeQueue();
573
574                       
575                        Debug << "Values after reset: " 
576                                  << " erc: " << mExpectedCost
577                                  << " avg: " << mAvgRenderCost
578                                  << " dev: " << mDeviation << endl;
579
580                        if (mExportMergedViewCells)
581                        {
582                                ExportMergedViewCells(activeViewCells, objects, numMergedViewCells);
583                        }
584                }
585
586#ifdef _DEBUG
587                Debug << "abs mergecost: " << mMergeQueue.top().GetMergeCost() <<
588                          << " rel mergecost: " << mMergeQueue.top().GetRenderCost() / mExpectedCost <<
589                          << " max ratio: " << mMergeMaxCostRatio << endl
590                          << " expected value: " << realExpectedCost << endl;
591#endif
592
593       
594                MergeCandidate mc = mMergeQueue.top();
595                mMergeQueue.pop();
596       
597                // both view cells equal
598                // NOTE: do I really still need this? probably cannot happen!!
599                if (mc.mLeftViewCell == mc.mRightViewCell)
600                        continue;
601
602                if (mc.IsValid())
603                {
604                        ViewCell::NewMail();
605
606                        //-- update statistical values
607                        -- realNumActiveViewCells;
608                        ++ mergeStats.merged;
609                        ++ mergedPerPass;
610
611                        const float renderCostIncr = mc.GetRenderCost();
612                        const float mergeCostIncr = mc.GetMergeCost();
613
614                        totalRenderCost += renderCostIncr;
615                        mDeviation += mc.GetDeviationIncr();
616                       
617                       
618                        // merge the view cells of leaf1 and leaf2
619                        int pvsDiff;
620                        ViewCellInterior *mergedVc =
621                                MergeViewCells(mc.mLeftViewCell, mc.mRightViewCell, pvsDiff);
622
623
624                        // total render cost and deviation has changed
625                        // real expected cost will be larger than expected cost used for the
626                        // cost heuristics, but cannot recompute costs on each increase of the
627                        // expected cost
628                        totalPvs += pvsDiff;
629                        realExpectedCost = totalRenderCost / (float)realNumActiveViewCells;
630                        realAvgRenderCost = (float)totalPvs / (float)realNumActiveViewCells;
631       
632                        // set merge cost to this node
633                        mergedVc->SetMergeCost(totalRenderCost);
634
635#if VC_HISTORY
636                        if (mc.mLeftViewCell->IsSibling(mc.mRightViewCell))
637                                ++ mergeStats.siblings;
638#endif
639                //      if (((mergeStats.merged % statsOut) == 0) ||
640                //              (realNumActiveViewCells == mMergeMinViewCells))
641                //      {
642                                cout << "merged " << mergeStats.merged << " view cells" << endl;
643
644                                mStats
645                                        << "#Pass\n" << pass << endl
646                                        << "#Merged\n" << mergeStats.merged << endl
647                                        << "#Viewcells\n" << realNumActiveViewCells << endl
648                                        << "#RenderCostIncrease\n" << renderCostIncr << endl
649                                        << "#TotalRenderCost\n" << totalRenderCost << endl
650                                        << "#CurrentPvs\n" << mergedVc->GetPvs().GetSize() << endl
651                                        << "#ExpectedCost\n" << realExpectedCost / (float) realNumActiveViewCells << endl
652                                        << "#AvgRenderCost\n" << realAvgRenderCost << endl
653                                        << "#Deviation\n" << mDeviation << endl
654                                        << "#TotalPvs\n" << totalPvs << endl
655                                        << "#PvsSizeDecrease\n" << -pvsDiff << endl
656                                        <<  "#Volume\n" << mergedVc->GetVolume() << endl
657                                        << "#Dummy\n" << (float)mergedVc->GetPvs().GetSize() * mergedVc->GetVolume() / mViewCellsManager->GetViewSpaceBox().GetVolume() << endl;
658                //      }
659                }
660                else
661                {
662                        // merge candidate not valid, because one of the leaves was already
663                        // merged with another one => validate and reinsert into queue
664                        if (ValidateMergeCandidate(mc))
665                        {
666                                EvalMergeCost(mc);
667                                mMergeQueue.push(mc);
668                        }
669                }
670        }
671
672        // adjust stats and reset queue one final time
673        mExpectedCost = realExpectedCost;
674        mAvgRenderCost = realAvgRenderCost;
675        mNumActiveViewCells = realNumActiveViewCells;
676
677        UpdateActiveViewCells(activeViewCells);
678
679        // refine view cells and reset costs
680        if (mRefineViewCells)
681                RefineViewCells(rays, objects);
682        else
683                ResetMergeQueue();
684
685        // create a root node if the merge was not done till root level,
686        // else take the single node as new root
687        if ((int)activeViewCells.size() > 1)
688        {
689                Debug << "creating root of view cell hierarchy for "
690                          << (int)activeViewCells.size() << " view cells" << endl;
691                /*for (int i = 0;  i < activeViewCells.size(); ++ i){
692                        Debug << "parent " << activeViewCells[i]->GetParent() << endl;
693                        Debug << "viewcell " << activeViewCells[i] << endl;
694                }*/
695                ViewCellInterior *root = mViewCellsManager->MergeViewCells(activeViewCells);
696                root->SetMergeCost(totalRenderCost);
697                mRoot = root;
698        }
699        else if ((int)activeViewCells.size() == 1)
700        {
701                Debug << "setting root of the merge history" << endl;
702                mRoot = activeViewCells[0];
703        }
704
705
706        while (!mMergeQueue.empty())
707        {
708                mMergeQueue.pop();
709        }
710       
711       
712        // TODO delete because makes no sense here
713        mergeStats.expectedRenderCost = realExpectedCost;
714        mergeStats.deviation = mDeviation;
715
716        // we want to optimize this heuristics
717        mergeStats.heuristics =
718                mDeviation * (1.0f - mRenderCostWeight) +
719                mExpectedCost * mRenderCostWeight;
720
721        mergeStats.mergeTime = TimeDiff(startTime, GetTime());
722        mergeStats.Stop();
723
724        Debug << mergeStats << endl << endl;
725
726
727        //TODO: should return sample contributions?
728        return mergeStats.merged;
729}
730
731
732ViewCell *ViewCellsTree::GetRoot() const
733{
734        return mRoot;
735}
736
737
738void ViewCellsTree::ResetMergeQueue()
739{
740        cout << "reset merge queue ... ";
741       
742        vector<MergeCandidate> buf;
743        buf.reserve(mMergeQueue.size());
744                       
745       
746        // store merge candidates in intermediate buffer
747        while (!mMergeQueue.empty())
748        {
749                MergeCandidate mc = mMergeQueue.top();
750                mMergeQueue.pop();
751               
752                // recalculate cost
753                if (ValidateMergeCandidate(mc))
754                {
755                        EvalMergeCost(mc);
756                        buf.push_back(mc);                             
757                }
758        }
759
760        vector<MergeCandidate>::const_iterator bit, bit_end = buf.end();
761
762        // reinsert back into queue
763        for (bit = buf.begin(); bit != bit_end; ++ bit)
764        {     
765                mMergeQueue.push(*bit);
766        }
767
768        cout << "finished" << endl;
769}
770
771
772int ViewCellsTree::UpdateActiveViewCells(ViewCellContainer &viewCells)
773{
774        int numMergedViewCells = 0;
775
776        Debug << "updating active vc: " << (int)viewCells.size() << endl;
777        // find all already merged view cells and remove them from view cells
778               
779        // sort out all view cells which are not active anymore, i.e., they
780        // were already part of a merge
781        int i = 0;
782
783        ViewCell::NewMail();
784
785        while (1)
786        {
787                // remove all merged view cells from end of the vector
788                while (!viewCells.empty() && (viewCells.back()->GetParent()))
789                {
790                        viewCells.pop_back();
791                }
792
793                // all merged view cells have been found
794                if (i >= viewCells.size())
795                        break;
796
797                // already merged view cell, put it to end of vector
798                if (viewCells[i]->GetParent())
799                        swap(viewCells[i], viewCells.back());
800               
801                viewCells[i ++]->Mail();
802        }
803
804
805        // add new view cells to container only if they don't have been
806        // merged in the mean time
807        ViewCellContainer::const_iterator ait, ait_end = mMergedViewCells.end();
808        for (ait = mMergedViewCells.begin(); ait != ait_end; ++ ait)
809        {
810                ViewCell *vc = mMergedViewCells.back();
811                if (!vc->GetParent() && !vc->Mailed())
812                {
813                        vc->Mail();
814                        viewCells.push_back(vc);
815                        ++ numMergedViewCells;
816                }
817        }
818
819        mMergedViewCells.clear();
820
821        // update standard deviation
822        ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
823       
824        mDeviation = 0;
825
826        for (vit = viewCells.begin(); vit != vit_end; ++ vit)
827        {
828                int lower = mViewCellsManager->GetMinPvsSize();
829                int upper = mViewCellsManager->GetMaxPvsSize();
830                float penalty = EvalPvsPenalty((*vit)->GetPvs().GetSize(), lower, upper);
831               
832                mDeviation += fabs(mAvgRenderCost - penalty);
833        }
834
835        mDeviation /= (float)viewCells.size();
836       
837        return numMergedViewCells;
838}
839
840
841void ViewCellsTree::ExportMergedViewCells(ViewCellContainer &viewCells,
842                                                                                  const ObjectContainer &objects,
843                                                                                  const int numMergedViewCells)
844{
845       
846
847        char s[64];
848
849        sprintf(s, "merged_viewcells%07d.x3d", (int)viewCells.size());
850        Exporter *exporter = Exporter::GetExporter(s);
851
852        if (exporter)
853        {
854                cout << "exporting " << (int)viewCells.size() << " merged view cells ... ";
855                exporter->ExportGeometry(objects);
856                //Debug << "vc size " << (int)viewCells.size() << " merge queue size: " << (int)mMergeQueue.size() << endl;
857                ViewCellContainer::const_iterator it, it_end = viewCells.end();
858
859                int i = 0;
860                for (it = viewCells.begin(); it != it_end; ++ it)
861                {
862                        Material m;
863                        // assign special material to new view cells
864                        // new view cells are on the back of container
865                        if (i ++ >= (viewCells.size() - numMergedViewCells))
866                        {
867                                //m = RandomMaterial();
868                                m.mDiffuseColor.r = RandomValue(0.5f, 1.0f);
869                                m.mDiffuseColor.g = RandomValue(0.5f, 1.0f);
870                                m.mDiffuseColor.b = RandomValue(0.5f, 1.0f);
871                        }
872                        else
873                        {
874                                float col = RandomValue(0.1f, 0.4f);
875                                m.mDiffuseColor.r = col;
876                                m.mDiffuseColor.g = col;
877                                m.mDiffuseColor.b = col;
878                        }
879
880                        exporter->SetForcedMaterial(m);
881                        mViewCellsManager->ExportViewCellGeometry(exporter, *it);
882                }
883                delete exporter;
884                cout << "finished" << endl;
885        }
886}
887
888
889// TODO: should be done in view cells manager
890ViewCellInterior *ViewCellsTree::MergeViewCells(ViewCell *l,
891                                                                                                ViewCell *r,
892                                                                                                int &pvsDiff) //const
893{
894        ViewCellInterior *vc = mViewCellsManager->MergeViewCells(l, r);
895
896        // if merge was unsuccessful
897        if (!vc) return NULL;
898
899        // set new size of view cell
900        if (mUseAreaForPvs)
901                vc->SetArea(l->GetArea() + l->GetArea());
902        else
903        {
904                vc->SetVolume(r->GetVolume() + l->GetVolume());
905        }
906        // important so other merge candidates sharing this view cell
907        // are notified that the merge cost must be updated!!
908        vc->Mail();
909
910        const int pvs1 = l->GetPvs().GetSize();
911        const int pvs2 = r->GetPvs().GetSize();
912
913
914        // new view cells are stored in this vector
915        mMergedViewCells.push_back(vc);
916
917        pvsDiff = vc->GetPvs().GetSize() - pvs1 - pvs2;
918
919        return vc;
920}
921
922
923
924int ViewCellsTree::RefineViewCells(const VssRayContainer &rays,
925                                                                   const ObjectContainer &objects)
926{
927        Debug << "refining " << (int)mMergeQueue.size() << " candidates " << endl;
928
929        // intermediate buffer for shuffled view cells
930        vector<MergeCandidate> buf;
931        buf.reserve(mMergeQueue.size());
932                       
933        // Use priority queue of remaining leaf pairs
934        // The candidates either share the same view cells or
935        // are border leaves which share a boundary.
936        // We test if they can be shuffled, i.e.,
937        // either one leaf is made part of one view cell or the other
938        // leaf is made part of the other view cell. It is tested if the
939        // remaining view cells are "better" than the old ones.
940       
941        const int numPasses = 3;
942        int pass = 0;
943        int passShuffled = 0;
944        int shuffled = 0;
945        int shuffledViewCells = 0;
946
947        ViewCell::NewMail();
948       
949        while (!mMergeQueue.empty())
950        {
951                MergeCandidate mc = mMergeQueue.top();
952                mMergeQueue.pop();
953
954                // both view cells equal or already shuffled
955                if ((mc.GetLeftViewCell() == mc.GetRightViewCell()) ||
956                        mc.GetLeftViewCell()->IsLeaf() || mc.GetRightViewCell()->IsLeaf())
957                {                       
958                        continue;
959                }
960
961                // candidate for shuffling
962                const bool wasShuffled = ShuffleLeaves(mc);
963               
964                // shuffled or put into other queue for further refine
965                if (wasShuffled)
966                {
967                        ++ passShuffled;
968
969                        if (!mc.GetLeftViewCell()->Mailed())
970                        {
971                                mc.GetLeftViewCell()->Mail();
972                                ++ shuffledViewCells;
973                        }
974                        if (!mc.GetRightViewCell()->Mailed())
975                        {
976                                mc.GetRightViewCell()->Mail();
977                                ++ shuffledViewCells;
978                        }
979                }
980
981                // put back into intermediate vector
982                buf.push_back(mc);
983        }
984
985
986        //-- in the end, the candidates must be in the mergequeue again
987        //   with the correct cost
988
989        cout << "reset merge queue ... ";
990       
991       
992        vector<MergeCandidate>::const_iterator bit, bit_end = buf.end();
993       
994        for (bit = buf.begin(); bit != bit_end; ++ bit)
995        {   
996                MergeCandidate mc = *bit;
997                // recalculate cost
998                if (ValidateMergeCandidate(mc))
999                {
1000                        EvalMergeCost(mc);
1001                        mMergeQueue.push(mc);   
1002                }
1003        }
1004
1005        cout << "finished" << endl;
1006
1007        return shuffledViewCells;
1008}
1009
1010
1011
1012
1013inline int AddedPvsSize(ObjectPvs pvs1, const ObjectPvs &pvs2)
1014{
1015        return pvs1.AddPvs(pvs2);
1016}
1017
1018
1019// recomputes pvs size minus pvs of leaf l
1020#if 0
1021inline int SubtractedPvsSize(BspViewCell *vc, BspLeaf *l, const ObjectPvs &pvs2)
1022{
1023        ObjectPvs pvs;
1024        vector<BspLeaf *>::const_iterator it, it_end = vc->mLeaves.end();
1025        for (it = vc->mLeaves.begin(); it != vc->mLeaves.end(); ++ it)
1026                if (*it != l)
1027                        pvs.AddPvs(*(*it)->mPvs);
1028        return pvs.GetSize();
1029}
1030#endif
1031
1032
1033// computes pvs1 minus pvs2
1034inline int SubtractedPvsSize(ObjectPvs pvs1, const ObjectPvs &pvs2)
1035{
1036        return pvs1.SubtractPvs(pvs2);
1037}
1038
1039
1040float ViewCellsTree::EvalShuffleCost(ViewCell *leaf,
1041                                                                         ViewCellInterior *vc1,
1042                                                                         ViewCellInterior *vc2) const
1043{
1044        //const int pvs1 = SubtractedPvsSize(vc1, leaf, *leaf->mPvs);
1045        const int pvs1 = SubtractedPvsSize(vc1->GetPvs(), leaf->GetPvs());
1046        const int pvs2 = AddedPvsSize(vc2->GetPvs(), leaf->GetPvs());
1047
1048        const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize();
1049        const int upperPvsLimit = mViewCellsManager->GetMaxPvsSize();
1050
1051        const float pvsPenalty1 =
1052                EvalPvsPenalty(pvs1, lowerPvsLimit, upperPvsLimit);
1053
1054        const float pvsPenalty2 =
1055                EvalPvsPenalty(pvs2, lowerPvsLimit, upperPvsLimit);
1056
1057
1058        // don't shuffle leaves with pvs > max
1059        if (0 && (pvs1 + pvs2 > mViewCellsManager->GetMaxPvsSize()))
1060        {
1061                return 1e20f;
1062        }
1063
1064        float p1, p2;
1065
1066    if (mUseAreaForPvs)
1067        {
1068                p1 = vc1->GetArea() - leaf->GetArea();
1069                p2 = vc2->GetArea() + leaf->GetArea();
1070        }
1071        else
1072        {
1073                p1 = vc1->GetVolume() - leaf->GetVolume();
1074                p2 = vc2->GetVolume() + leaf->GetVolume();
1075        }
1076
1077        const float renderCost1 = pvsPenalty1 * p1;
1078        const float renderCost2 = pvsPenalty2 * p2;
1079
1080        float dev1, dev2;
1081
1082        if (1)
1083        {
1084                dev1 = fabs(mAvgRenderCost - pvsPenalty1);
1085                dev2 = fabs(mAvgRenderCost - pvsPenalty2);
1086        }
1087        else
1088        {
1089                dev1 = fabs(mExpectedCost - renderCost1);
1090                dev2 = fabs(mExpectedCost - renderCost2);
1091        }
1092       
1093        return mRenderCostWeight * (renderCost1 + renderCost2) +
1094                  (1.0f - mRenderCostWeight) * (dev1 + dev2) / (float)mNumActiveViewCells;
1095}
1096
1097
1098void ViewCellsTree::ShuffleLeaf(ViewCell *leaf,
1099                                                                ViewCellInterior *vc1,
1100                                                                ViewCellInterior *vc2) const
1101{
1102        // compute new pvs and area
1103        // TODO change
1104        vc1->GetPvs().SubtractPvs(leaf->GetPvs());
1105        vc2->GetPvs().AddPvs(leaf->GetPvs());
1106       
1107        if (mUseAreaForPvs)
1108        {
1109                vc1->SetArea(vc1->GetArea() - leaf->GetArea());
1110                vc2->SetArea(vc2->GetArea() + leaf->GetArea());
1111        }
1112        else
1113        {
1114                vc1->SetVolume(vc1->GetVolume() - leaf->GetVolume());
1115                vc2->SetVolume(vc2->GetVolume() + leaf->GetVolume());
1116        }
1117
1118       
1119        ViewCellInterior *p = dynamic_cast<ViewCellInterior *>(leaf->GetParent());
1120
1121        p->RemoveChildLink(leaf);
1122        vc2->SetupChildLink(leaf);
1123}
1124
1125
1126bool ViewCellsTree::ShuffleLeaves(MergeCandidate &mc) const
1127{
1128        float cost1, cost2;
1129
1130        ViewCellInterior *vc1 = dynamic_cast<ViewCellInterior *>(mc.GetLeftViewCell());
1131        ViewCellInterior *vc2 = dynamic_cast<ViewCellInterior *>(mc.GetRightViewCell());
1132
1133        ViewCell *leaf1 = mc.GetInitialLeftViewCell();
1134        ViewCell *leaf2 = mc.GetInitialRightViewCell();
1135
1136        //-- first test if shuffling would decrease cost
1137        cost1 = GetCostHeuristics(vc1);
1138        cost2 = GetCostHeuristics(vc2);
1139
1140        const float oldCost = cost1 + cost2;
1141       
1142        float shuffledCost1 = Limits::Infinity;
1143        float shuffledCost2 = Limits::Infinity;
1144
1145        if (leaf1)
1146                shuffledCost1 = EvalShuffleCost(leaf1, vc1, vc2);       
1147        if (leaf2)
1148                shuffledCost2 = EvalShuffleCost(leaf2, vc2, vc1);
1149
1150        // if cost of shuffle is less than old cost => shuffle
1151        if ((oldCost <= shuffledCost1) && (oldCost <= shuffledCost2))
1152                return false;
1153       
1154        if (shuffledCost1 < shuffledCost2)
1155        {
1156                if (leaf1)
1157                        ShuffleLeaf(leaf1, vc1, vc2);
1158                mc.mInitialLeftViewCell = NULL;
1159        }
1160        else
1161        {
1162                if (leaf2)
1163                        ShuffleLeaf(leaf2, vc2, vc1);
1164                mc.mInitialRightViewCell = NULL;
1165        }
1166
1167        return true;
1168}
1169
1170
1171float ViewCellsTree::GetVariance(ViewCell *vc) const
1172{
1173        const int upper = mViewCellsManager->GetMaxPvsSize();
1174        const int lower = mViewCellsManager->GetMinPvsSize();
1175
1176        if (1)
1177        {
1178                const float penalty = EvalPvsPenalty(vc->GetPvs().GetSize(), lower, upper);
1179                return (mAvgRenderCost - penalty) * (mAvgRenderCost - penalty) / (float)mNumActiveViewCells;
1180        }
1181
1182    const float leafCost = GetRenderCost(vc);
1183        return (mExpectedCost - leafCost) * (mExpectedCost - leafCost);
1184}
1185
1186
1187float ViewCellsTree::GetDeviation(ViewCell *vc) const
1188{
1189        const int upper = mViewCellsManager->GetMaxPvsSize();
1190        const int lower = mViewCellsManager->GetMinPvsSize();
1191
1192        if (1)
1193        {
1194                const float penalty = EvalPvsPenalty(vc->GetPvs().GetSize(), lower, upper);
1195                return fabs(mAvgRenderCost - penalty) / (float)mNumActiveViewCells;
1196        }
1197
1198    const float renderCost = GetRenderCost(vc);
1199        return fabs(mExpectedCost - renderCost);
1200}
1201
1202
1203
1204float ViewCellsTree::GetRenderCost(ViewCell *vc) const
1205{
1206        if (mUseAreaForPvs)
1207                return vc->GetPvs().GetSize() * vc->GetArea();
1208
1209        return vc->GetPvs().GetSize() * vc->GetVolume();
1210}
1211
1212
1213float ViewCellsTree::GetCostHeuristics(ViewCell *vc) const
1214{
1215        return GetRenderCost(vc) * mRenderCostWeight +
1216                   GetDeviation(vc) * (1.0f - mRenderCostWeight);
1217}
1218
1219
1220bool ViewCellsTree::ValidateMergeCandidate(MergeCandidate &mc) const
1221{
1222        while (mc.mLeftViewCell->mParent)
1223        {
1224                mc.mLeftViewCell = mc.mLeftViewCell->mParent;
1225        }
1226
1227        while (mc.mRightViewCell->mParent)
1228        {
1229                mc.mRightViewCell = mc.mRightViewCell->mParent;
1230        }
1231
1232        return mc.mLeftViewCell != mc.mRightViewCell;
1233}
1234
1235
1236void ViewCellsTree::EvalMergeCost(MergeCandidate &mc) const
1237{
1238        //-- compute pvs difference
1239        const int newPvs =
1240                ComputeMergedPvsSize(mc.mLeftViewCell->GetPvs(),
1241                                                         mc.mRightViewCell->GetPvs());
1242                       
1243        const float newPenalty =
1244                EvalPvsPenalty(newPvs,
1245                                           mViewCellsManager->GetMinPvsSize(),
1246                                           mViewCellsManager->GetMaxPvsSize());
1247
1248        ViewCell *vc1 = mc.mLeftViewCell;
1249        ViewCell *vc2 = mc.mRightViewCell;
1250
1251        //-- compute ratio of old cost
1252        //   (i.e., added size of left and right view cell times pvs size)
1253        //   to new rendering cost (i.e, size of merged view cell times pvs size)
1254        const float oldCost = GetRenderCost(vc1) + GetRenderCost(vc2);
1255
1256    const float newCost = mUseAreaForPvs ?
1257                (float)newPenalty * (vc1->GetArea() + vc2->GetArea()) :
1258                (float)newPenalty * (vc1->GetVolume() + vc2->GetVolume());
1259
1260
1261        // strong penalty if pvs size too large
1262        if (0 && (newPvs > mViewCellsManager->GetMaxPvsSize()))
1263        {
1264                mc.mRenderCost = 1e20f;
1265        }
1266        else
1267        {
1268                mc.mRenderCost = (newCost - oldCost) /
1269                        mViewCellsManager->GetViewSpaceBox().GetVolume();
1270        }       
1271       
1272
1273        //-- merge cost also takes deviation into account
1274        float newDev, oldDev;
1275
1276        if (1)
1277                newDev = fabs(mAvgRenderCost - newPenalty) / (float)mNumActiveViewCells;
1278        else
1279                newDev = fabs(mExpectedCost - newCost) / (float)mNumActiveViewCells;
1280       
1281        oldDev = GetDeviation(vc1) + GetDeviation(vc2);
1282
1283        // compute deviation increase
1284        mc.mDeviationIncr = newDev - oldDev;
1285       
1286        //Debug << "render cost: " << mc.mRenderCost * mRenderCostWeight << endl;
1287        //Debug << "standard deviation: " << mc.mDeviationIncr * mRenderCostWeight << endl;
1288}
1289
1290void ViewCellsTree::CompressViewCellsPvs()
1291{
1292        if (!mIsCompressed)
1293        {
1294                mIsCompressed = true;
1295                CompressViewCellsPvs(mRoot);
1296        }
1297}
1298
1299void ViewCellsTree::CompressViewCellsPvs(ViewCell *root)
1300{
1301        if (!root->IsLeaf())
1302        {
1303                ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(root);
1304
1305        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1306               
1307                // compress child sets first
1308                for (it = interior->mChildren.begin(); it != it_end; ++ it)
1309                {
1310                        CompressViewCellsPvs(*it);
1311                }
1312
1313                // compress root node
1314                PropagateUpVisibility(interior);
1315        }
1316}
1317
1318
1319void ViewCellsTree::CollectBestViewCellSet(ViewCellContainer &viewCells,
1320                                                                                   const int numViewCells)
1321{
1322        TraversalQueue tqueue;
1323        tqueue.push(mRoot);
1324       
1325        while (!tqueue.empty())
1326        {
1327                ViewCell *vc = tqueue.top();
1328               
1329                // save the view cells if it is a leaf or if enough view cells have already been traversed
1330                // because of the priority queue, this will be the optimal set of v
1331                if (vc->IsLeaf() || ((viewCells.size() + tqueue.size()) >= numViewCells))
1332                {
1333                        // todo: should be done with a function taking the active flag and some
1334                        // time stamp so I don't have to reset view cells, this also means that
1335                        // the leaf view cells can be set active fist
1336                        vc->mIsActive = true;
1337                        viewCells.push_back(vc);
1338                }
1339                else
1340                {       
1341                        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
1342
1343                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1344
1345                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
1346                        {
1347                                tqueue.push(*it);
1348                        }
1349                }
1350
1351                tqueue.pop();
1352        }
1353}
1354       
1355
1356void ViewCellsTree::PropagateUpVisibility(ViewCellInterior *interior)
1357{
1358        Intersectable::NewMail((int)interior->mChildren.size());
1359
1360        ViewCellContainer::const_iterator cit, cit_end = interior->mChildren.end();
1361
1362        ObjectPvsMap::const_iterator oit;
1363
1364        // mail all objects in the leaf sets
1365        // we are interested in the objects which are present in all leaves
1366        // => count how often an object is part of a child set
1367        for (cit = interior->mChildren.begin(); cit != cit_end; ++ cit)
1368        {
1369                ViewCell *vc = *cit;
1370
1371                ObjectPvsMap::const_iterator oit_end = vc->GetPvs().mEntries.end();
1372
1373                for (oit = vc->GetPvs().mEntries.begin(); oit != oit_end; ++ oit)
1374                {
1375                        Intersectable *obj = (*oit).first;
1376                        if ((cit == interior->mChildren.begin()) && !obj->Mailed())
1377                                obj->Mail();
1378                       
1379                        int incm = obj->IncMail();
1380                }
1381        }
1382
1383        interior->GetPvs().mEntries.clear();
1384       
1385       
1386        // only the objects which are present in all leaf pvs
1387        // should remain in the parent pvs
1388        // these are the objects which have been mailed in all children
1389        for (cit = interior->mChildren.begin(); cit != cit_end; ++ cit)
1390        {
1391                ViewCell *vc = *cit;
1392
1393                ObjectPvsMap::const_iterator oit_end = vc->GetPvs().mEntries.end();
1394
1395                for (oit = vc->GetPvs().mEntries.begin(); oit != oit_end; ++ oit)
1396                {               
1397                        if ((*oit).first->Mailed((int)interior->mChildren.size()))
1398                        {       
1399                                interior->GetPvs().AddSample((*oit).first, (*oit).second.mSumPdf);
1400                        }
1401                }
1402        }
1403
1404
1405
1406        // delete all the objects from the leaf sets which were moved to parent pvs
1407        ObjectPvsMap::const_iterator oit_end = interior->GetPvs().mEntries.end();
1408
1409        for (oit = interior->GetPvs().mEntries.begin(); oit != oit_end; ++ oit)
1410        {
1411                for (cit = interior->mChildren.begin(); cit != cit_end; ++ cit)
1412                {
1413                        if (!(*cit)->GetPvs().RemoveSample((*oit).first, Limits::Infinity))
1414                                Debug << "should not come here!" << endl;
1415                }
1416        }
1417
1418        int dummy = interior->GetPvs().GetSize();
1419
1420        for (cit = interior->mChildren.begin(); cit != cit_end; ++ cit)
1421        {
1422                dummy += (*cit)->GetPvs().GetSize();
1423        }
1424
1425}
1426
1427
1428
1429void ViewCellsTree::GetPvs(ViewCell *vc, ObjectPvs &pvs) const
1430{
1431        Intersectable::NewMail();
1432
1433        if (!mIsCompressed)
1434                pvs = vc->GetPvs();
1435
1436        int pvsSize = 0;
1437        ViewCell *root = vc;
1438       
1439        // also add pvs from this view cell to root
1440        while (root->GetParent())
1441        {
1442                root = root->GetParent();
1443                pvs.AddPvs(root->GetPvs());
1444        }
1445
1446        stack<ViewCell *> tstack;
1447        tstack.push(vc);
1448
1449        while (!tstack.empty())
1450        {
1451                vc = tstack.top();
1452                tstack.pop();
1453
1454                pvs.AddPvs(vc->GetPvs());
1455
1456                if (!vc->IsLeaf())
1457                {
1458                        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
1459
1460                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1461
1462                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
1463                        {
1464                                tstack.push(*it);
1465                        }               
1466                }
1467        }
1468}
1469
1470
1471int ViewCellsTree::GetPvsSize(ViewCell *vc) const
1472{
1473        Intersectable::NewMail();
1474
1475        if (!mIsCompressed)
1476                return vc->GetPvs().GetSize();
1477
1478        int pvsSize = 0;
1479        ViewCell *root = vc;
1480       
1481        // also add pvs from this view cell to root
1482        while (root->GetParent())
1483        {
1484                root = root->GetParent();
1485                pvsSize += CountDiffPvs(root);
1486        }
1487
1488        stack<ViewCell *> tstack;
1489        tstack.push(vc);
1490
1491        Debug << "current size: " << pvsSize << endl;
1492
1493        while (!tstack.empty())
1494        {
1495                vc = tstack.top();
1496                tstack.pop();
1497
1498                pvsSize += CountDiffPvs(vc);
1499
1500                if (!vc->IsLeaf())
1501                {
1502                        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
1503
1504                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1505
1506                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
1507                        {
1508                                tstack.push(*it);
1509                        }               
1510                }
1511        }
1512
1513        return pvsSize; 
1514
1515}
1516
1517
1518float ViewCellsTree::GetMemoryCost(ViewCell *vc) const
1519{
1520        const float entrySize =
1521                sizeof(PvsData<Intersectable *>) + sizeof(Intersectable *);
1522
1523        return (float)GetNumPvsEntries(vc) * entrySize;
1524}
1525
1526
1527int ViewCellsTree::GetNumPvsEntries(ViewCell *vc) const
1528{
1529        int pvsSize = 0;
1530        // only count leaves for uncompressed method for fairness
1531        if (mIsCompressed || vc->IsLeaf())
1532                pvsSize = vc->GetPvs().GetSize();
1533
1534        if (!vc->IsLeaf())
1535        {
1536                ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
1537
1538                ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1539
1540                for (it = interior->mChildren.begin(); it != it_end; ++ it)
1541                {
1542                        pvsSize += GetNumPvsEntries(*it);
1543                }
1544        }
1545
1546        return pvsSize;         
1547}
1548
1549
1550bool ViewCellsTree::IsCompressed() const
1551{
1552        return mIsCompressed;
1553}
1554
1555
1556ViewCell *ViewCellsTree::GetActiveViewCell(ViewCell *vc) const
1557{
1558        while (vc->GetParent() && !vc->mIsActive)
1559        {
1560                vc = vc->GetParent();
1561        }
1562
1563        return vc;
1564}
1565
1566
1567/**************************************************************************/
1568/*                     MergeCandidate implementation                      */
1569/**************************************************************************/
1570
1571
1572MergeCandidate::MergeCandidate(ViewCell *l, ViewCell *r):
1573mRenderCost(0),
1574mDeviationIncr(0),
1575mLeftViewCell(l),
1576mRightViewCell(r),
1577mInitialLeftViewCell(l),
1578mInitialRightViewCell(r)
1579{
1580        //EvalMergeCost();
1581}
1582
1583
1584void MergeCandidate::SetRightViewCell(ViewCell *v)
1585{
1586        mRightViewCell = v;
1587}
1588
1589
1590void MergeCandidate::SetLeftViewCell(ViewCell *v)
1591{
1592        mLeftViewCell = v;
1593}
1594
1595
1596ViewCell *MergeCandidate::GetRightViewCell() const
1597{
1598        return mRightViewCell;
1599}
1600
1601
1602ViewCell *MergeCandidate::GetLeftViewCell() const
1603{
1604        return mLeftViewCell;
1605}
1606
1607
1608ViewCell *MergeCandidate::GetInitialRightViewCell() const
1609{
1610        return mInitialRightViewCell;
1611}
1612
1613
1614ViewCell *MergeCandidate::GetInitialLeftViewCell() const
1615{
1616        return mInitialLeftViewCell;
1617}
1618
1619
1620bool MergeCandidate::IsValid() const
1621{
1622        return !(mLeftViewCell->mParent || mRightViewCell->mParent);
1623}
1624
1625
1626float MergeCandidate::GetRenderCost() const
1627{
1628        return mRenderCost;
1629}
1630
1631
1632float MergeCandidate::GetDeviationIncr() const
1633{
1634        return mDeviationIncr;
1635}
1636
1637
1638float MergeCandidate::GetMergeCost() const
1639{
1640        return mRenderCost * sRenderCostWeight +
1641                   mDeviationIncr * (1.0f - sRenderCostWeight);
1642}
1643
1644
1645/************************************************************************/
1646/*                    MergeStatistics implementation                    */
1647/************************************************************************/
1648
1649
1650void MergeStatistics::Print(ostream &app) const
1651{
1652        app << "===== Merge statistics ===============\n";
1653
1654        app << setprecision(4);
1655
1656        app << "#N_CTIME ( Overall time [s] )\n" << Time() << " \n";
1657
1658        app << "#N_CCTIME ( Collect candidates time [s] )\n" << collectTime * 1e-3f << " \n";
1659
1660        app << "#N_MTIME ( Merge time [s] )\n" << mergeTime * 1e-3f << " \n";
1661
1662        app << "#N_NODES ( Number of nodes before merge )\n" << nodes << "\n";
1663
1664        app << "#N_CANDIDATES ( Number of merge candidates )\n" << candidates << "\n";
1665
1666        app << "#N_MERGEDSIBLINGS ( Number of merged siblings )\n" << siblings << "\n";
1667
1668        app << "#OVERALLCOST ( overall merge cost )\n" << overallCost << "\n";
1669
1670        app << "#N_MERGEDNODES ( Number of merged nodes )\n" << merged << "\n";
1671
1672        app << "#MAX_TREEDIST ( Maximal distance in tree of merged leaves )\n" << maxTreeDist << "\n";
1673
1674        app << "#AVG_TREEDIST ( Average distance in tree of merged leaves )\n" << AvgTreeDist() << "\n";
1675
1676        app << "#EXPECTEDCOST ( expected render cost )\n" << expectedRenderCost << "\n";
1677
1678        app << "#DEVIATION ( deviation )\n" << deviation << "\n";
1679
1680        app << "#HEURISTICS ( heuristics )\n" << heuristics << "\n";
1681       
1682
1683        app << "===== END OF BspTree statistics ==========\n";
1684}
Note: See TracBrowser for help on using the repository browser.