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

Revision 585, 38.7 KB checked in by mattausch, 18 years ago (diff)

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