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

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