source: GTP/trunk/Lib/Vis/Preprocessing/src/ViewCell.cpp @ 1264

Revision 1264, 56.8 KB checked in by mattausch, 18 years ago (diff)
Line 
1#include <time.h>
2#include <iomanip>
3#include <stack>
4
5
6#include "ViewCell.h"
7#include "Mesh.h"
8#include "Intersectable.h"
9#include "KdTree.h"
10#include "Triangle3.h"
11#include "common.h"
12#include "Environment.h"
13#include "ViewCellsManager.h"
14#include "Exporter.h"
15
16
17namespace GtpVisibilityPreprocessor {
18
19
20
21template <typename T> class myless
22{
23public:
24        bool operator() (T v1, T v2) const
25        {
26                return (v1->GetMergeCost() < v2->GetMergeCost());
27        }
28};
29
30
31typedef priority_queue<ViewCell *, vector<ViewCell *>,
32                                           myless<vector<ViewCell *>::value_type> > TraversalQueue;
33
34int ViewCell::sMailId = 0;//21843194198;
35int ViewCell::sReservedMailboxes = 1;
36
37
38float MergeCandidate::sRenderCostWeight = 0;
39
40
41// pvs penalty can be different from pvs size
42inline static float EvalPvsPenalty(const int pvs,
43                                                                   const int lower,
44                                                                   const int upper)
45{
46        // clamp to minmax values
47        if (pvs < lower)
48                return (float)lower;
49        if (pvs > upper)
50                return (float)upper;
51
52        return (float)pvs;
53}
54
55/// Counts differences between pvss.
56inline int CountDiffPvs(ViewCell *vc)
57{
58        int count = 0;
59
60        ObjectPvsMap::const_iterator it, it_end = vc->GetPvs().mEntries.end();
61        for (it = vc->GetPvs().mEntries.begin(); it != it_end; ++ it)
62        {
63                if (!(*it).first->Mailed())
64                {
65                        (*it).first->Mail();
66                        ++ count;
67                }
68        }
69
70        return count;
71}
72
73
74/// Fast computation of merged pvs size
75static int ComputeMergedPvsSize(const ObjectPvs &pvs1, const ObjectPvs &pvs2)
76{
77        // add first pvs
78        int pvs = pvs1.GetSize();
79
80        ObjectPvsMap::const_iterator it, it_end =  pvs1.mEntries.end();
81
82        Intersectable::NewMail();
83
84        // mail all objects in first pvs
85        for (it = pvs1.mEntries.begin(); it != it_end; ++ it)
86        {
87                (*it).first->Mail();
88        }
89
90        it_end = pvs2.mEntries.end();
91
92        // look if the entries are also in second pvs
93        for (it = pvs2.mEntries.begin(); it != it_end; ++ it)
94        {
95                Intersectable *obj = (*it).first;
96                if (!obj->Mailed())
97                        ++ pvs;
98        }
99
100        return pvs;
101}
102
103
104ViewCell::ViewCell():
105MeshInstance(NULL),
106mPiercingRays(0),
107mArea(-1),
108mVolume(-1),
109mValid(true),
110mParent(NULL),
111mMergeCost(0),
112mPvsSize(0),
113mEntriesInPvs(0),
114mPvsSizeValid(false)
115{
116}
117
118ViewCell::ViewCell(Mesh *mesh):
119MeshInstance(mesh),
120mPiercingRays(0),
121mArea(-1),
122mVolume(-1),
123mValid(true),
124mParent(NULL),
125mMergeCost(0),
126mPvsSize(0),
127mPvsSizeValid(false)
128{
129}
130
131
132const ObjectPvs &ViewCell::GetPvs() const
133{
134        return mPvs;
135}
136
137
138ObjectPvs &ViewCell::GetPvs()
139{
140        return mPvs;
141}
142
143
144void ViewCell::SetPvs(const ObjectPvs &pvs)
145{
146        mPvs = pvs;
147}
148
149
150int ViewCell::Type() const
151{
152        return VIEW_CELL;
153}
154
155
156float ViewCell::GetVolume() const
157{
158        return mVolume;
159}
160
161
162void ViewCell::SetVolume(float volume)
163{
164        mVolume = volume;
165}
166
167
168void ViewCell::SetMesh(Mesh *mesh)
169{
170        mMesh = mesh;
171}
172
173
174float ViewCell::GetArea() const
175{
176        return mArea;
177}
178
179
180void ViewCell::SetArea(float area)
181{
182        mArea = area;
183}
184
185
186void ViewCell::SetColor(const RgbColor &color)
187{
188        mColor = color;
189}
190
191
192RgbColor ViewCell::GetColor() const
193{
194        return mColor;
195}
196
197
198void ViewCell::SetValid(const bool valid)
199{
200        mValid = valid;
201}
202
203
204bool ViewCell::GetValid() const
205{
206        return mValid;
207}
208
209
210void ViewCell::SetParent(ViewCellInterior *parent)
211{
212        mParent = parent;
213}
214
215
216bool ViewCell::IsRoot() const
217{
218        return !mParent;
219}
220
221
222ViewCellInterior *ViewCell::GetParent() const
223{
224        return mParent;
225}
226
227
228void ViewCell::SetMergeCost(const float mergeCost)
229{
230        mMergeCost = mergeCost;
231}
232
233
234float ViewCell::GetRenderCost() const
235{
236        //return (float)mPvs.GetSize() * GetVolume();
237        return (float)mPvsSize * GetVolume();
238}
239
240
241float ViewCell::GetMergeCost() const
242{
243        return mMergeCost;
244}
245
246
247bool ViewCell::AddPvsSample(Intersectable *sample,
248                                                        const float pdf,
249                                                        float &contribution)
250{
251        const bool result = mPvs.AddSample(sample, pdf, contribution);
252       
253        mPvsSizeValid = false; // have to recompute pvs size
254
255        return result;
256}
257
258
259
260/************************************************************************/
261/*                class ViewCellInterior implementation                 */
262/************************************************************************/
263
264
265ViewCellInterior::ViewCellInterior()
266{
267}
268
269
270ViewCellInterior::~ViewCellInterior()
271{
272        ViewCellContainer::const_iterator it, it_end = mChildren.end();
273
274        for (it = mChildren.begin(); it != it_end; ++ it)
275                delete (*it);
276}
277
278
279ViewCellInterior::ViewCellInterior(Mesh *mesh):
280ViewCell(mesh)
281{
282}
283
284
285bool ViewCellInterior::IsLeaf() const
286{
287        return false;
288}
289
290
291void ViewCellInterior::SetupChildLink(ViewCell *vc)
292{
293    mChildren.push_back(vc);
294    vc->SetParent(this);
295}
296
297
298void ViewCellInterior::RemoveChildLink(ViewCell *l)
299{
300        // erase leaf from old view cell
301        ViewCellContainer::iterator it = mChildren.begin();
302
303        for (; (*it) != l; ++ it);
304        if (it == mChildren.end())
305                Debug << "error" << endl;
306        else
307                mChildren.erase(it);
308}
309
310
311/************************************************************************/
312/*                class ViewCellsStatistics implementation              */
313/************************************************************************/
314
315
316
317
318void ViewCellsStatistics::Print(ostream &app) const
319{
320        app << "=========== View Cells Statistics ===============\n";
321
322        app << setprecision(4);
323
324        //app << "#N_CTIME  ( Construction time [s] )\n" << Time() << " \n";
325
326        app << "#N_OVERALLPVS ( objects in PVS )\n" << pvsSize << endl;
327
328        app << "#N_PMAXPVS ( largest PVS )\n" << maxPvs << endl;
329
330        app << "#N_PMINPVS ( smallest PVS )\n" << minPvs << endl;
331
332        app << "#N_PAVGPVS ( average PVS )\n" << AvgPvs() << endl;
333
334        app << "#N_PEMPTYPVS ( view cells with empty PVS )\n" << emptyPvs << endl;
335
336        app << "#N_VIEWCELLS ( number of view cells)\n" << viewCells << endl;
337
338        app << "#N_AVGLEAVES (average number of leaves per view cell )\n" << AvgLeaves() << endl;
339
340        app << "#N_MAXLEAVES ( maximal number of leaves per view cell )\n" << maxLeaves << endl;
341       
342        app << "#N_INVALID ( number of invalid view cells )\n" << invalid << endl;
343
344        app << "========== End of View Cells Statistics ==========\n";
345}
346
347
348/*************************************************************************/
349/*                    class ViewCellsTree implementation                 */
350/*************************************************************************/
351
352
353ViewCellsTree::ViewCellsTree(ViewCellsManager *vcm):
354mRoot(NULL),
355mUseAreaForPvs(false),
356mViewCellsManager(vcm),
357#if 0
358mViewCellsStorage(PVS_IN_INTERIORS)
359#else
360mViewCellsStorage(PVS_IN_LEAVES)
361#endif
362{
363        ReadEnvironment();
364        MergeCandidate::sRenderCostWeight = mRenderCostWeight;
365}
366
367
368ViewCellsTree::ViewCellsTree():
369mRoot(NULL),
370mUseAreaForPvs(false),
371mViewCellsManager(NULL),
372#if 0
373mViewCellsStorage(PVS_IN_INTERIORS)
374#else
375mViewCellsStorage(PVS_IN_LEAVES)
376#endif
377{
378        ReadEnvironment();
379        MergeCandidate::sRenderCostWeight = mRenderCostWeight;
380}
381
382
383void ViewCellsTree::ReadEnvironment()
384{
385        Environment::GetSingleton()->GetBoolValue("ViewCells.Visualization.exportMergedViewCells", mExportMergedViewCells);
386        Environment::GetSingleton()->GetFloatValue("ViewCells.maxStaticMemory", mMaxMemory);
387
388        //-- merge options
389        Environment::GetSingleton()->GetFloatValue("ViewCells.PostProcess.renderCostWeight", mRenderCostWeight);
390        Environment::GetSingleton()->GetIntValue("ViewCells.PostProcess.minViewCells", mMergeMinViewCells);
391        Environment::GetSingleton()->GetFloatValue("ViewCells.PostProcess.maxCostRatio", mMergeMaxCostRatio);
392        Environment::GetSingleton()->GetBoolValue("ViewCells.PostProcess.refine", mRefineViewCells);   
393
394        Environment::GetSingleton()->GetIntValue("ViewCells.PostProcess.maxMergesPerPass", mMaxMergesPerPass);
395        Environment::GetSingleton()->GetFloatValue("ViewCells.PostProcess.avgCostMaxDeviation", mAvgCostMaxDeviation);
396
397        Debug << "============= view cell tree options ================\n";
398        Debug << "minimum view cells: " << mMergeMinViewCells << endl;
399        Debug << "max cost ratio: " << mMergeMaxCostRatio << endl;
400        Debug << "max memory: " << mMaxMemory << endl;
401        Debug << "refining view cells: " << mRefineViewCells << endl;
402        Debug << "=========== end view cell tree options ===============\n";
403}
404
405
406// return memory usage in MB
407float ViewCellsTree::GetMemUsage() const
408{
409        // TODO
410        return 0;
411                /*(sizeof(ViewCellsTree) +
412                 mBspStats.Leaves() * sizeof(BspLeaf) +
413                 mBspStats.Interior() * sizeof(BspInterior) +
414                 mBspStats.accumRays * sizeof(RayInfo)) / (1024.0f * 1024.0f);*/
415}
416
417
418int ViewCellsTree::GetNumInitialViewCells(ViewCell *vc) const
419{
420        int vcSize = 0;
421
422        stack<ViewCell *> tstack;
423
424        tstack.push(vc);
425
426        while (!tstack.empty())
427        {
428                ViewCell *vc = tstack.top();
429                tstack.pop();
430
431                if (vc->IsLeaf())
432                {
433                        ++ vcSize;
434                }
435                else
436                {
437                        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
438
439                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
440                       
441                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
442                        {
443                                tstack.push(*it);
444                        }
445                       
446                }
447        }
448
449        return vcSize;
450}
451
452
453void ViewCellsTree::CollectLeaves(ViewCell *vc, ViewCellContainer &leaves) const
454{
455        stack<ViewCell *> tstack;
456
457        tstack.push(vc);
458
459        while (!tstack.empty())
460        {
461                ViewCell *vc = tstack.top();
462                tstack.pop();
463
464                if (vc->IsLeaf())
465                {
466                        leaves.push_back(vc);
467                }
468                else
469                {
470                        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
471                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
472
473                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
474                        {
475                                tstack.push(*it);
476                        }
477                       
478                }
479        }
480}
481
482
483ViewCellsTree::~ViewCellsTree()
484{
485        DEL_PTR(mRoot);
486}
487
488
489int ViewCellsTree::ConstructMergeTree(const VssRayContainer &rays,
490                                                                          const ObjectContainer &objects)
491{
492        mNumActiveViewCells = (int)mViewCellsManager->GetViewCells().size();
493
494        float variance = 0;
495        int totalPvs = 0;
496        float totalRenderCost = 0;
497
498        //-- compute statistics values of initial view cells
499        mViewCellsManager->EvaluateRenderStatistics(totalRenderCost,
500                                                                                                mExpectedCost,
501                                                                                                mDeviation,
502                                                                                                variance,
503                                                                                                totalPvs,
504                                                                                                mAvgRenderCost);
505
506
507        //-- fill merge queue
508        vector<MergeCandidate> candidates;
509
510        mViewCellsManager->CollectMergeCandidates(rays, candidates);
511
512        while(!candidates.empty())
513        {
514                MergeCandidate mc = candidates.back();
515                candidates.pop_back();
516                EvalMergeCost(mc);
517                mMergeQueue.push(mc);
518        }
519
520        Debug << "************************* merge ***********************************" << endl; 
521        Debug << "deviation: " << mDeviation << endl;
522        Debug << "avg render cost: " << mAvgRenderCost << endl;
523        Debug << "expected cost: " << mExpectedCost << endl;
524
525
526        ViewCellsManager::PvsStatistics pvsStats;
527        mViewCellsManager->GetPvsStatistics(pvsStats);
528
529        //static float expectedValue = pvsStats.avgPvs;
530       
531        //-- the current view cells are kept in this container
532        //-- we start with the current view cells from the view cell manager.
533        //-- The active view cells will change with subsequent merges
534       
535        // todo: should rather take initial view cells
536    ViewCellContainer &activeViewCells = mViewCellsManager->GetViewCells();
537       
538       
539        ViewCell::NewMail();
540
541        MergeStatistics mergeStats;
542        mergeStats.Start();
543       
544        long startTime = GetTime();
545
546        mergeStats.collectTime = TimeDiff(startTime, GetTime());
547        mergeStats.candidates = (int)mMergeQueue.size();
548        startTime = GetTime();
549
550        // frequency stats are updated
551        const int statsOut = 500;
552       
553        // passes are needed for statistics, because we don't want to record
554        // every merge
555        int pass = 0;
556        int mergedPerPass = 0;
557        float realExpectedCost = mExpectedCost;
558        float realAvgRenderCost = mAvgRenderCost;
559        int realNumActiveViewCells = mNumActiveViewCells;
560       
561        // maximal ratio of old expected render cost to expected render
562        // when the the render queue has to be reset.
563        int numMergedViewCells = 0;
564               
565
566        cout << "actual merge starts now ... " << endl;
567
568        //-- use priority queue to merge leaf pairs
569
570        while (!mMergeQueue.empty())
571        {
572                //-- reset merge queue if the ratio of current expected cost / real expected cost
573                //   too small or after a given number of merges
574                if ((mergedPerPass > mMaxMergesPerPass) ||
575                        (mAvgCostMaxDeviation > mAvgRenderCost / realAvgRenderCost))
576                {
577                        Debug << "************ reset queue *****************\n"
578                                  << "ratios: " << mAvgCostMaxDeviation
579                                  << " real avg render cost " << realAvgRenderCost << " average render cost " << mAvgRenderCost
580                                  << " merged per pass : " << mergedPerPass << " of maximal " << mMaxMergesPerPass << endl;
581
582                        Debug << "Values before reset: " 
583                                  << " erc: " << mExpectedCost
584                                  << " avgrc: " << mAvgRenderCost
585                                  << " dev: " << mDeviation << endl;
586       
587                        // adjust render cost
588                        ++ pass;
589
590                        mergedPerPass = 0;
591                        mExpectedCost = realExpectedCost;
592                        mAvgRenderCost = realAvgRenderCost;
593                        mNumActiveViewCells = realNumActiveViewCells;
594                       
595                        const int numMergedViewCells = UpdateActiveViewCells(activeViewCells);
596               
597                       
598                        //-- resets / refines the view cells
599                        //-- priorities are recomputed
600                        //-- the candidates are put back into merge queue
601                        if (mRefineViewCells)
602                                RefineViewCells(rays, objects);
603                        else
604                                ResetMergeQueue();
605
606                        Debug << "Values after reset: " 
607                                  << " erc: " << mExpectedCost
608                                  << " avg: " << mAvgRenderCost
609                                  << " dev: " << mDeviation << endl;
610
611                        if (mExportMergedViewCells)
612                        {
613                                ExportMergedViewCells(activeViewCells, objects, numMergedViewCells);
614                        }
615                }
616
617
618                MergeCandidate mc = mMergeQueue.top();
619                mMergeQueue.pop();
620       
621                // both view cells equal because of previous merges
622                // NOTE: do I really still need this? probably cannot happen!!
623                if (mc.mLeftViewCell == mc.mRightViewCell)
624                        continue;
625
626                if (mc.IsValid())
627                {
628                        ViewCell::NewMail();
629
630                        //-- update statistical values
631                        -- realNumActiveViewCells;
632                        ++ mergeStats.merged;
633                        ++ mergedPerPass;
634
635                        const float renderCostIncr = mc.GetRenderCost();
636                        const float mergeCostIncr = mc.GetMergeCost();
637
638                        totalRenderCost += renderCostIncr;
639                        mDeviation += mc.GetDeviationIncr();
640
641                                               
642                        //-- merge the view cells of leaf1 and leaf2
643                        int pvsDiff;
644                        ViewCellInterior *mergedVc =
645                                MergeViewCells(mc.mLeftViewCell, mc.mRightViewCell, pvsDiff);
646                       
647
648                        // total render cost and deviation has changed
649                        // real expected cost will be larger than expected cost used for the
650                        // cost heuristics, but cannot recompute costs on each increase of the
651                        // expected cost
652                        totalPvs += pvsDiff;
653                        realExpectedCost = totalRenderCost / (float)realNumActiveViewCells;
654                        realAvgRenderCost = (float)totalPvs / (float)realNumActiveViewCells;
655       
656                        // set merge cost to this node for priority traversal
657                        mergedVc->SetMergeCost(totalRenderCost);
658                       
659                        // HACK
660                        //mergedVc->SetMergeCost(1.0f / (float)realNumActiveViewCells);
661
662                        // check if "siblings (back and front node of the same parent)
663                        if (0 && mViewCellsManager->EqualToSpatialNode(mergedVc))
664                                ++ mergeStats.siblings;
665                        // set the coŽst for rendering a view cell
666                        mergedVc->SetCost(realExpectedCost);
667
668                        if ((mergeStats.merged % statsOut) == 0)
669                                cout << "merged " << mergeStats.merged << " view cells" << endl;
670
671                }
672                else
673                {
674                        // merge candidate not valid, because one of the leaves was already
675                        // merged with another one => validate and reinsert into queue
676                        if (ValidateMergeCandidate(mc))
677                        {
678                                EvalMergeCost(mc);
679                                mMergeQueue.push(mc);
680                        }
681                }
682               
683        }
684
685        // adjust stats and reset queue one final time
686        mExpectedCost = realExpectedCost;
687        mAvgRenderCost = realAvgRenderCost;
688        mNumActiveViewCells = realNumActiveViewCells;
689
690        UpdateActiveViewCells(activeViewCells);
691
692        // refine view cells and reset costs
693        if (mRefineViewCells)
694                RefineViewCells(rays, objects);
695        else
696                ResetMergeQueue();
697
698
699        // create a root node if the merge was not done till root level,
700        // else take the single node as new root
701        if ((int)activeViewCells.size() > 1)
702        {
703                Debug << "creating root of view cell hierarchy for "
704                          << (int)activeViewCells.size() << " view cells" << endl;
705               
706                ViewCellInterior *root = mViewCellsManager->MergeViewCells(activeViewCells);
707       
708                ViewCellContainer::const_iterator it, it_end = root->mChildren.end();
709
710                for (it = root->mChildren.begin(); it != it_end; ++ it)
711                        (*it)->SetParent(root);
712       
713                root->SetMergeCost(totalRenderCost);
714                // $$JB keep this 0 temporarilly
715                root->SetCost(0.0f);
716
717                mRoot = root;
718        }
719        // normal case
720        else if (!activeViewCells.empty())
721        {
722                Debug << "setting root of the merge history" << endl;
723                mRoot = activeViewCells[0];
724        }
725        else
726        {
727                Debug << "big error, root is NULL" << endl;
728        }
729       
730        //-- empty merge queue just in case
731        while (!mMergeQueue.empty())
732        {
733                mMergeQueue.pop();
734        }
735
736        // test if voluje is equal
737        Debug << "volume of the root view cell: " << mRoot->GetVolume() << " " << mViewCellsManager->GetViewSpaceBox().GetVolume() << endl;
738
739        //hack!!
740        //mRoot->GetPvs().Clear();
741       
742        // TODO: delete because makes no sense here
743        mergeStats.expectedRenderCost = realExpectedCost;
744        mergeStats.deviation = mDeviation;
745
746        // we want to optimize this heuristics
747        mergeStats.heuristics =
748                mDeviation * (1.0f - mRenderCostWeight) +
749                mExpectedCost * mRenderCostWeight;
750
751        mergeStats.mergeTime = TimeDiff(startTime, GetTime());
752        mergeStats.Stop();
753        Debug << mergeStats << endl << endl;
754
755        // assign colors for the view cells so that at least one is always consistent
756        AssignRandomColors();
757
758        //TODO: should return sample contributions?
759        return mergeStats.merged;
760}
761
762
763ViewCell *ViewCellsTree::GetRoot() const
764{
765        return mRoot;
766}
767
768
769void ViewCellsTree::ResetMergeQueue()
770{
771        cout << "reset merge queue ... ";
772       
773        vector<MergeCandidate> buf;
774        buf.reserve(mMergeQueue.size());
775                       
776       
777        // store merge candidates in intermediate buffer
778        while (!mMergeQueue.empty())
779        {
780                MergeCandidate mc = mMergeQueue.top();
781                mMergeQueue.pop();
782               
783                // recalculate cost
784                if (ValidateMergeCandidate(mc))
785                {
786                        EvalMergeCost(mc);
787                        buf.push_back(mc);                             
788                }
789        }
790
791        vector<MergeCandidate>::const_iterator bit, bit_end = buf.end();
792
793        // reinsert back into queue
794        for (bit = buf.begin(); bit != bit_end; ++ bit)
795        {     
796                mMergeQueue.push(*bit);
797        }
798
799        cout << "finished" << endl;
800}
801
802
803float ViewCellsTree::ComputeMergedPvsCost(const ObjectPvs &pvs1,
804                                                                                  const ObjectPvs &pvs2) const
805{
806        // computes render cost of merge
807        float renderCost = 0;
808
809        // compute new pvs size
810        ObjectPvsMap::const_iterator it, it_end =  pvs1.mEntries.end();
811
812        Intersectable::NewMail();
813
814        // first mail all objects in first pvs
815        for (it = pvs1.mEntries.begin(); it != it_end; ++ it)
816        {
817                Intersectable *obj = (*it).first;
818
819                obj->Mail();
820                renderCost += mViewCellsManager->EvalRenderCost(obj);
821        }
822
823        it_end = pvs2.mEntries.end();
824
825       
826        for (it = pvs2.mEntries.begin(); it != it_end; ++ it)
827        {
828                Intersectable *obj = (*it).first;
829
830                // test if object already considered   
831                if (!obj->Mailed())
832                {
833                        renderCost += mViewCellsManager->EvalRenderCost(obj);
834                }
835        }
836
837        return renderCost;
838}
839
840
841int ViewCellsTree::UpdateActiveViewCells(ViewCellContainer &viewCells)
842{
843        int numMergedViewCells = 0;
844
845        Debug << "updating active vc: " << (int)viewCells.size() << endl;
846       
847        // find all already merged view cells and remove them from the
848        // container view cells
849               
850        // sort out all view cells which are not active anymore, i.e., they
851        // were already part of a merge
852        int i = 0;
853
854        ViewCell::NewMail();
855
856        while (1)
857        {
858                // remove all merged view cells from end of the vector
859                while (!viewCells.empty() && (viewCells.back()->GetParent()))
860                {
861                        viewCells.pop_back();
862                }
863
864                // all merged view cells have been found
865                if (i >= (int)viewCells.size())
866                        break;
867
868                // already merged this view cell, put it to end of vector
869                if (viewCells[i]->GetParent())
870                        swap(viewCells[i], viewCells.back());
871               
872                // mail view cell that it has not been merged
873                viewCells[i]->Mail();
874
875                // increase loop counter
876                ++ i;
877        }
878
879
880        // add new view cells to container only if they don't have been
881        // merged in the mean time
882        ViewCellContainer::const_iterator ait, ait_end = mMergedViewCells.end();
883
884        for (ait = mMergedViewCells.begin(); ait != ait_end; ++ ait)
885        {
886                ViewCell *vc = mMergedViewCells.back();
887                if (!vc->GetParent() && !vc->Mailed())
888                {
889                        vc->Mail();
890                        viewCells.push_back(vc);
891                        ++ numMergedViewCells;
892                }
893        }
894
895        // dispose old merged view cells
896        mMergedViewCells.clear();
897
898        // update standard deviation
899        ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
900       
901        mDeviation = 0;
902
903        for (vit = viewCells.begin(); vit != vit_end; ++ vit)
904        {
905                const int lower = mViewCellsManager->GetMinPvsSize();
906                const int upper = mViewCellsManager->GetMaxPvsSize();
907
908                const float penalty = EvalPvsPenalty((*vit)->GetPvs().CountObjectsInPvs(), lower, upper);
909               
910                mDeviation += fabs(mAvgRenderCost - penalty);
911        }
912
913        mDeviation /= (float)viewCells.size();
914       
915        return numMergedViewCells;
916}
917
918
919void ViewCellsTree::ExportMergedViewCells(ViewCellContainer &viewCells,
920                                                                                  const ObjectContainer &objects,
921                                                                                  const int numMergedViewCells)
922{
923       
924
925        char s[64];
926
927        sprintf(s, "merged_viewcells%07d.x3d", (int)viewCells.size());
928        Exporter *exporter = Exporter::GetExporter(s);
929
930        if (exporter)
931        {
932                cout << "exporting " << (int)viewCells.size() << " merged view cells ... ";
933                exporter->ExportGeometry(objects);
934                //Debug << "vc size " << (int)viewCells.size() << " merge queue size: " << (int)mMergeQueue.size() << endl;
935                ViewCellContainer::const_iterator it, it_end = viewCells.end();
936
937                int i = 0;
938                for (it = viewCells.begin(); it != it_end; ++ it)
939                {
940                        Material m;
941                        // assign special material to new view cells
942                        // new view cells are on the back of container
943                        if (i ++ >= (viewCells.size() - numMergedViewCells))
944                        {
945                                //m = RandomMaterial();
946                                m.mDiffuseColor.r = RandomValue(0.5f, 1.0f);
947                                m.mDiffuseColor.g = RandomValue(0.5f, 1.0f);
948                                m.mDiffuseColor.b = RandomValue(0.5f, 1.0f);
949                        }
950                        else
951                        {
952                                float col = RandomValue(0.1f, 0.4f);
953                                m.mDiffuseColor.r = col;
954                                m.mDiffuseColor.g = col;
955                                m.mDiffuseColor.b = col;
956                        }
957
958                        exporter->SetForcedMaterial(m);
959                        mViewCellsManager->ExportViewCellGeometry(exporter, *it);
960                }
961                delete exporter;
962                cout << "finished" << endl;
963        }
964}
965
966
967// TODO: should be done in view cells manager
968ViewCellInterior *ViewCellsTree::MergeViewCells(ViewCell *left,
969                                                                                                ViewCell *right,
970                                                                                                int &pvsDiff) //const
971{
972        // create merged view cell
973        ViewCellInterior *vc =
974                mViewCellsManager->MergeViewCells(left, right);
975
976        // if merge was unsuccessful
977        if (!vc) return NULL;
978
979        // set to the new parent view cell
980        left->SetParent(vc);
981        right->SetParent(vc);
982
983       
984        if (mUseAreaForPvs)
985        {
986                // set new area of view cell
987                // not not correct, but costly to compute real area!!
988                vc->SetArea(left->GetArea() + right->GetArea());
989        }
990        else
991        {       // set new volume of view cell
992                vc->SetVolume(left->GetVolume() + right->GetVolume());
993        }
994
995       
996        // important so other merge candidates sharing this view cell
997        // are notified that the merge cost must be updated!!
998        vc->Mail();
999
1000        const int pvs1 = left->GetPvs().CountObjectsInPvs();
1001        const int pvs2 = right->GetPvs().CountObjectsInPvs();
1002
1003
1004        // the new view cells are stored in this container
1005        mMergedViewCells.push_back(vc);
1006
1007        pvsDiff = vc->GetPvs().CountObjectsInPvs() - pvs1 - pvs2;
1008
1009
1010        // don't store pvs in interior cells, just a scalar
1011        if (mViewCellsStorage == PVS_IN_LEAVES)
1012        {
1013                // set scalars
1014                mViewCellsManager->UpdateScalarPvsSize(left,
1015                        left->GetPvs().CountObjectsInPvs(),
1016                        left->GetPvs().GetSize());
1017                       
1018                // remove pvs, we don't store interior pvss
1019                if (!left->IsLeaf())
1020                {
1021                        left->GetPvs().Clear();
1022                }
1023
1024                // set scalars
1025                mViewCellsManager->UpdateScalarPvsSize(right,
1026                        right->GetPvs().CountObjectsInPvs(),
1027                        right->GetPvs().GetSize());
1028
1029                right->mPvsSizeValid = true;
1030               
1031                // remove pvs, we don't store interior pvss
1032                if (!right->IsLeaf())
1033                {
1034                        right->GetPvs().Clear();
1035                }
1036        }
1037
1038        return vc;
1039}
1040
1041
1042int ViewCellsTree::RefineViewCells(const VssRayContainer &rays,
1043                                                                   const ObjectContainer &objects)
1044{
1045        Debug << "refining " << (int)mMergeQueue.size() << " candidates " << endl;
1046
1047        // intermediate buffer for shuffled view cells
1048        vector<MergeCandidate> buf;
1049        buf.reserve(mMergeQueue.size());
1050                       
1051        // Use priority queue of remaining leaf pairs
1052        // The candidates either share the same view cells or
1053        // are border leaves which share a boundary.
1054        // We test if they can be shuffled, i.e.,
1055        // either one leaf is made part of one view cell or the other
1056        // leaf is made part of the other view cell. It is tested if the
1057        // remaining view cells are "better" than the old ones.
1058       
1059        const int numPasses = 3;
1060        int pass = 0;
1061        int passShuffled = 0;
1062        int shuffled = 0;
1063        int shuffledViewCells = 0;
1064
1065        ViewCell::NewMail();
1066       
1067        while (!mMergeQueue.empty())
1068        {
1069                MergeCandidate mc = mMergeQueue.top();
1070                mMergeQueue.pop();
1071
1072                // both view cells equal or already shuffled
1073                if ((mc.GetLeftViewCell() == mc.GetRightViewCell()) ||
1074                        mc.GetLeftViewCell()->IsLeaf() || mc.GetRightViewCell()->IsLeaf())
1075                {                       
1076                        continue;
1077                }
1078
1079                // candidate for shuffling
1080                const bool wasShuffled = ShuffleLeaves(mc);
1081               
1082                // shuffled or put into other queue for further refine
1083                if (wasShuffled)
1084                {
1085                        ++ passShuffled;
1086
1087                        if (!mc.GetLeftViewCell()->Mailed())
1088                        {
1089                                mc.GetLeftViewCell()->Mail();
1090                                ++ shuffledViewCells;
1091                        }
1092                        if (!mc.GetRightViewCell()->Mailed())
1093                        {
1094                                mc.GetRightViewCell()->Mail();
1095                                ++ shuffledViewCells;
1096                        }
1097                }
1098
1099                // put back into intermediate vector
1100                buf.push_back(mc);
1101        }
1102
1103
1104        //-- in the end, the candidates must be in the mergequeue again
1105        //   with the correct cost
1106
1107        cout << "reset merge queue ... ";
1108       
1109       
1110        vector<MergeCandidate>::const_iterator bit, bit_end = buf.end();
1111       
1112        for (bit = buf.begin(); bit != bit_end; ++ bit)
1113        {   
1114                MergeCandidate mc = *bit;
1115                // recalculate cost
1116                if (ValidateMergeCandidate(mc))
1117                {
1118                        EvalMergeCost(mc);
1119                        mMergeQueue.push(mc);   
1120                }
1121        }
1122
1123        cout << "finished" << endl;
1124
1125        return shuffledViewCells;
1126}
1127
1128
1129inline int AddedPvsSize(ObjectPvs pvs1, const ObjectPvs &pvs2)
1130{
1131        return pvs1.AddPvs(pvs2);
1132}
1133
1134
1135// recomputes pvs size minus pvs of leaf l
1136#if 0
1137inline int SubtractedPvsSize(BspViewCell *vc, BspLeaf *l, const ObjectPvs &pvs2)
1138{
1139        ObjectPvs pvs;
1140        vector<BspLeaf *>::const_iterator it, it_end = vc->mLeaves.end();
1141        for (it = vc->mLeaves.begin(); it != vc->mLeaves.end(); ++ it)
1142                if (*it != l)
1143                        pvs.AddPvs(*(*it)->mPvs);
1144        return pvs.GetSize();
1145}
1146#endif
1147
1148
1149// computes pvs1 minus pvs2
1150inline int SubtractedPvsSize(ObjectPvs pvs1, const ObjectPvs &pvs2)
1151{
1152        return pvs1.SubtractPvs(pvs2);
1153}
1154
1155
1156float ViewCellsTree::EvalShuffleCost(ViewCell *leaf,
1157                                                                         ViewCellInterior *vc1,
1158                                                                         ViewCellInterior *vc2) const
1159{
1160        //const int pvs1 = SubtractedPvsSize(vc1, leaf, *leaf->mPvs);
1161        const int pvs1 = SubtractedPvsSize(vc1->GetPvs(), leaf->GetPvs());
1162        const int pvs2 = AddedPvsSize(vc2->GetPvs(), leaf->GetPvs());
1163
1164        const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize();
1165        const int upperPvsLimit = mViewCellsManager->GetMaxPvsSize();
1166
1167        const float pvsPenalty1 =
1168                EvalPvsPenalty(pvs1, lowerPvsLimit, upperPvsLimit);
1169
1170        const float pvsPenalty2 =
1171                EvalPvsPenalty(pvs2, lowerPvsLimit, upperPvsLimit);
1172
1173
1174        // don't shuffle leaves with pvs > max
1175        if (0 && (pvs1 + pvs2 > mViewCellsManager->GetMaxPvsSize()))
1176        {
1177                return 1e20f;
1178        }
1179
1180        float p1, p2;
1181
1182    if (mUseAreaForPvs)
1183        {
1184                p1 = vc1->GetArea() - leaf->GetArea();
1185                p2 = vc2->GetArea() + leaf->GetArea();
1186        }
1187        else
1188        {
1189                p1 = vc1->GetVolume() - leaf->GetVolume();
1190                p2 = vc2->GetVolume() + leaf->GetVolume();
1191        }
1192
1193        const float renderCost1 = pvsPenalty1 * p1;
1194        const float renderCost2 = pvsPenalty2 * p2;
1195
1196        float dev1, dev2;
1197
1198        if (1)
1199        {
1200                dev1 = fabs(mAvgRenderCost - pvsPenalty1);
1201                dev2 = fabs(mAvgRenderCost - pvsPenalty2);
1202        }
1203        else
1204        {
1205                dev1 = fabs(mExpectedCost - renderCost1);
1206                dev2 = fabs(mExpectedCost - renderCost2);
1207        }
1208       
1209        return mRenderCostWeight * (renderCost1 + renderCost2) +
1210                  (1.0f - mRenderCostWeight) * (dev1 + dev2) / (float)mNumActiveViewCells;
1211}
1212
1213
1214void ViewCellsTree::ShuffleLeaf(ViewCell *leaf,
1215                                                                ViewCellInterior *vc1,
1216                                                                ViewCellInterior *vc2) const
1217{
1218        // compute new pvs and area
1219        // TODO change
1220        vc1->GetPvs().SubtractPvs(leaf->GetPvs());
1221        vc2->GetPvs().AddPvs(leaf->GetPvs());
1222       
1223        if (mUseAreaForPvs)
1224        {
1225                vc1->SetArea(vc1->GetArea() - leaf->GetArea());
1226                vc2->SetArea(vc2->GetArea() + leaf->GetArea());
1227        }
1228        else
1229        {
1230                vc1->SetVolume(vc1->GetVolume() - leaf->GetVolume());
1231                vc2->SetVolume(vc2->GetVolume() + leaf->GetVolume());
1232        }
1233
1234       
1235        ViewCellInterior *p = dynamic_cast<ViewCellInterior *>(leaf->GetParent());
1236
1237        p->RemoveChildLink(leaf);
1238        vc2->SetupChildLink(leaf);
1239}
1240
1241
1242bool ViewCellsTree::ShuffleLeaves(MergeCandidate &mc) const
1243{
1244        float cost1, cost2;
1245
1246        ViewCellInterior *vc1 = dynamic_cast<ViewCellInterior *>(mc.GetLeftViewCell());
1247        ViewCellInterior *vc2 = dynamic_cast<ViewCellInterior *>(mc.GetRightViewCell());
1248
1249        ViewCell *leaf1 = mc.GetInitialLeftViewCell();
1250        ViewCell *leaf2 = mc.GetInitialRightViewCell();
1251
1252        //-- first test if shuffling would decrease cost
1253        cost1 = GetCostHeuristics(vc1);
1254        cost2 = GetCostHeuristics(vc2);
1255
1256        const float oldCost = cost1 + cost2;
1257       
1258        float shuffledCost1 = Limits::Infinity;
1259        float shuffledCost2 = Limits::Infinity;
1260
1261        if (leaf1)
1262                shuffledCost1 = EvalShuffleCost(leaf1, vc1, vc2);       
1263        if (leaf2)
1264                shuffledCost2 = EvalShuffleCost(leaf2, vc2, vc1);
1265
1266        // if cost of shuffle is less than old cost => shuffle
1267        if ((oldCost <= shuffledCost1) && (oldCost <= shuffledCost2))
1268                return false;
1269       
1270        if (shuffledCost1 < shuffledCost2)
1271        {
1272                if (leaf1)
1273                        ShuffleLeaf(leaf1, vc1, vc2);
1274                mc.mInitialLeftViewCell = NULL;
1275        }
1276        else
1277        {
1278                if (leaf2)
1279                        ShuffleLeaf(leaf2, vc2, vc1);
1280                mc.mInitialRightViewCell = NULL;
1281        }
1282
1283        return true;
1284}
1285
1286
1287float ViewCellsTree::GetVariance(ViewCell *vc) const
1288{
1289        const int upper = mViewCellsManager->GetMaxPvsSize();
1290        const int lower = mViewCellsManager->GetMinPvsSize();
1291
1292        if (1)
1293        {
1294                const float penalty =
1295                        EvalPvsPenalty(vc->GetPvs().GetSize(), lower, upper);
1296
1297                return (mAvgRenderCost - penalty) * (mAvgRenderCost - penalty) /
1298                        (float)mNumActiveViewCells;
1299        }
1300
1301    const float leafCost = GetRenderCost(vc);
1302        return (mExpectedCost - leafCost) * (mExpectedCost - leafCost);
1303}
1304
1305
1306float ViewCellsTree::GetDeviation(ViewCell *vc) const
1307{
1308        const int upper = mViewCellsManager->GetMaxPvsSize();
1309        const int lower = mViewCellsManager->GetMinPvsSize();
1310
1311        if (1)
1312        {
1313                const float penalty = EvalPvsPenalty(vc->GetPvs().CountObjectsInPvs(), lower, upper);
1314                return fabs(mAvgRenderCost - penalty) / (float)mNumActiveViewCells;
1315        }
1316
1317    const float renderCost = GetRenderCost(vc);
1318        return fabs(mExpectedCost - renderCost);
1319}
1320
1321
1322float ViewCellsTree::GetRenderCost(ViewCell *vc) const
1323{
1324        if (mUseAreaForPvs)
1325        {
1326                return vc->GetPvs().CountObjectsInPvs() * vc->GetArea();
1327        }
1328
1329        return vc->GetPvs().CountObjectsInPvs() * vc->GetVolume();
1330}
1331
1332
1333float ViewCellsTree::GetCostHeuristics(ViewCell *vc) const
1334{
1335        return GetRenderCost(vc) * mRenderCostWeight +
1336                   GetDeviation(vc) * (1.0f - mRenderCostWeight);
1337}
1338
1339
1340bool ViewCellsTree::ValidateMergeCandidate(MergeCandidate &mc) const
1341{
1342        // propagate up so we have only the active view cells
1343        while (mc.mLeftViewCell->mParent)
1344        {
1345                mc.mLeftViewCell = mc.mLeftViewCell->mParent;
1346        }
1347
1348        while (mc.mRightViewCell->mParent)
1349        {
1350                mc.mRightViewCell = mc.mRightViewCell->mParent;
1351        }
1352
1353        // this view cell was already merged
1354        //return mc.mLeftViewCell && (mc.mLeftViewCell != mc.mRightViewCell);
1355        return mc.mLeftViewCell != mc.mRightViewCell;
1356}
1357
1358
1359void ViewCellsTree::EvalMergeCost(MergeCandidate &mc) const
1360{
1361        //-- compute pvs difference
1362        int newPvs;
1363        if (1) // not valid if not using const cost per object!!
1364                newPvs = ComputeMergedPvsSize(mc.mLeftViewCell->GetPvs(), mc.mRightViewCell->GetPvs());
1365        else
1366                newPvs = (int)ComputeMergedPvsCost(mc.mLeftViewCell->GetPvs(), mc.mRightViewCell->GetPvs());
1367
1368        const float newPenalty = EvalPvsPenalty(newPvs,
1369                                                                                        mViewCellsManager->GetMinPvsSize(),
1370                                                                                        mViewCellsManager->GetMaxPvsSize());
1371
1372        ViewCell *vc1 = mc.mLeftViewCell;
1373        ViewCell *vc2 = mc.mRightViewCell;
1374
1375        //-- compute ratio of old cost
1376        //   (i.e., added size of left and right view cell times pvs size)
1377        //   to new rendering cost (i.e, size of merged view cell times pvs size)
1378        const float oldCost = GetRenderCost(vc1) + GetRenderCost(vc2);
1379
1380    const float newCost = mUseAreaForPvs ?
1381                (float)newPenalty * (vc1->GetArea() + vc2->GetArea()) :
1382                (float)newPenalty * (vc1->GetVolume() + vc2->GetVolume());
1383
1384
1385        // strong penalty if pvs size too large
1386        if (0 && (newPvs > mViewCellsManager->GetMaxPvsSize()))
1387        {
1388                mc.mRenderCost = 1e20f;
1389        }
1390        else
1391        {
1392                mc.mRenderCost = (newCost - oldCost) /
1393                        mViewCellsManager->GetViewSpaceBox().GetVolume();
1394        }       
1395       
1396
1397        //-- merge cost also takes deviation into account
1398        float newDev, oldDev;
1399
1400        if (1)
1401                newDev = fabs(mAvgRenderCost - newPenalty) / (float)mNumActiveViewCells;
1402        else
1403                newDev = fabs(mExpectedCost - newCost) / (float)mNumActiveViewCells;
1404       
1405        oldDev = GetDeviation(vc1) + GetDeviation(vc2);
1406
1407        // compute deviation increase
1408        mc.mDeviationIncr = newDev - oldDev;
1409       
1410        //Debug << "render cost: " << mc.mRenderCost * mRenderCostWeight << endl;
1411        //Debug << "standard deviation: " << mc.mDeviationIncr * mRenderCostWeight << endl;
1412}
1413
1414
1415void ViewCellsTree::SetViewCellsStorage(int stype)
1416{
1417        if (mViewCellsStorage == stype)
1418                return;
1419
1420        // TODO
1421        switch (stype)
1422        {
1423        case COMPRESSED:
1424                CompressViewCellsPvs(mRoot);
1425                break;
1426        default:
1427                break;
1428        }
1429
1430        mViewCellsStorage = stype;
1431}
1432
1433
1434void ViewCellsTree::CompressViewCellsPvs(ViewCell *root)
1435{
1436        if (!root->IsLeaf())
1437        {
1438                ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(root);
1439
1440        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1441               
1442                // compress child sets first
1443                for (it = interior->mChildren.begin(); it != it_end; ++ it)
1444                {
1445                        CompressViewCellsPvs(*it);
1446                }
1447
1448                // compress root node
1449                PullUpVisibility(interior);
1450        }
1451}
1452
1453
1454void ViewCellsTree::UpdateStats(ofstream &stats,
1455                                                                const int pass,
1456                                                                const int viewCells,
1457                                                                const float renderCostDecrease,
1458                                                                const float totalRenderCost,
1459                                                                const int currentPvs,
1460                                                                const float expectedCost,
1461                                                                const float avgRenderCost,
1462                                                                const float deviation,
1463                                                                const int totalPvs,
1464                                                                const int entriesInPvs,
1465                                                                const int pvsSizeDecr,
1466                                                                const float volume)
1467{
1468         stats << "#Pass\n" << pass << endl
1469                //<< "#Merged\n" << mergeStats.merged << endl
1470                << "#ViewCells\n" << viewCells << endl
1471        << "#RenderCostDecrease\n" << renderCostDecrease << endl // TODO
1472                << "#TotalRenderCost\n" << totalRenderCost << endl
1473                << "#CurrentPvs\n" << currentPvs << endl
1474                << "#ExpectedCost\n" << expectedCost << endl
1475                << "#AvgRenderCost\n" << avgRenderCost << endl
1476                << "#Deviation\n" << deviation << endl
1477                << "#TotalPvs\n" << totalPvs << endl
1478                << "#TotalEntriesInPvs\n" << entriesInPvs << endl
1479                << "#PvsSizeDecrease\n" << pvsSizeDecr << endl // TODO
1480                << "#Volume\n" << volume << endl
1481                << endl;
1482}
1483
1484void ViewCellsTree::ExportStats(const string &mergeStats)
1485{
1486        TraversalQueue tqueue;
1487
1488        tqueue.push(mRoot);
1489        int numViewCells = 1;
1490       
1491        const AxisAlignedBox3 box = mViewCellsManager->GetViewSpaceBox();
1492        const float vol = box.GetVolume();
1493
1494        const int rootPvs = GetPvsSize(mRoot);
1495        const int rootEntries = GetPvsEntries(mRoot);
1496
1497        Debug << "******** Export stats **********" << endl;
1498        /*Debug << "vsb volume: " << vol << endl;
1499        Debug << "root volume: " << mRoot->GetVolume() << endl;
1500        Debug << "root pvs: " << rootPvs << endl;
1501        */
1502
1503        float totalRenderCost, avgRenderCost, expectedCost;
1504
1505        float deviation = 0;
1506        int totalPvs = rootPvs;
1507        int entriesInPvs = rootEntries;
1508
1509        totalRenderCost = avgRenderCost = expectedCost = (float)rootPvs;
1510
1511        ofstream stats;
1512        stats.open(mergeStats.c_str());
1513
1514        //-- first view cell
1515        UpdateStats(stats,
1516                                0, numViewCells, 0, totalRenderCost,
1517                                rootPvs, expectedCost, avgRenderCost, deviation,
1518                                totalPvs, entriesInPvs, 0, mRoot->GetVolume());
1519               
1520
1521        //-- go through tree in the order of render cost decrease
1522        //-- which is the same order as the view cells were merged
1523        //-- or the reverse order of subdivision for subdivision-only
1524        //-- view cell hierarchies.
1525
1526        while (!tqueue.empty())
1527        {
1528                ViewCell *vc = tqueue.top();
1529                tqueue.pop();
1530
1531                if (!vc->IsLeaf())
1532                {       
1533                        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
1534
1535                        const int parentPvs = GetPvsSize(interior);
1536                        const int parentPvsEntries = GetPvsEntries(interior);
1537            const float parentCost = (float)parentPvs * interior->GetVolume();
1538
1539                        float childCost = 0;
1540                        int childPvs = 0;
1541                        int childPvsEntries = 0;
1542
1543                        -- numViewCells;
1544
1545                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1546
1547                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
1548                        {
1549                                ViewCell *vc = *it;
1550
1551                                const int pvsSize = GetPvsSize(vc);
1552                                const int pvsEntries = GetPvsEntries(vc);
1553
1554                                childCost += (float) pvsSize * vc->GetVolume();
1555                                childPvs += pvsSize;
1556                                childPvsEntries += pvsEntries;
1557
1558                                tqueue.push(vc);
1559                                ++ numViewCells;
1560                        }
1561
1562
1563                        const float costDecr = (parentCost - childCost) / vol;
1564
1565                        totalRenderCost -= costDecr;
1566                        totalPvs += childPvs - parentPvs;
1567                        entriesInPvs += childPvsEntries - parentPvsEntries;
1568
1569                        expectedCost = totalRenderCost / (float)numViewCells;
1570                        avgRenderCost = (float)totalPvs / (float)numViewCells;
1571
1572                        UpdateStats(stats,
1573                                                0, numViewCells, costDecr, totalRenderCost,
1574                                                parentPvs, expectedCost, avgRenderCost, deviation,
1575                        totalPvs, entriesInPvs, childPvs - parentPvs,
1576                                                vc->GetVolume());
1577
1578                }
1579        }
1580
1581        stats.close();
1582}
1583
1584
1585void ViewCellsTree::SetRoot(ViewCell *root)
1586{
1587        mRoot = root;
1588}
1589
1590
1591void ViewCellsTree::CollectBestViewCellSet(ViewCellContainer &viewCells,
1592                                                                                   const int numViewCells)
1593{
1594        TraversalQueue tqueue;
1595        tqueue.push(mRoot);
1596       
1597        while (!tqueue.empty())
1598        {
1599                ViewCell *vc = tqueue.top();
1600                tqueue.pop();
1601
1602                // save the view cells if it is a leaf or if enough view cells have already been traversed
1603                // because of the priority queue, this will be the optimal set of v
1604                if (vc->IsLeaf() || ((viewCells.size() + tqueue.size() + 1) >= numViewCells))
1605                {
1606                        viewCells.push_back(vc);
1607                }
1608                else
1609                {       
1610                        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
1611
1612                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1613
1614                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
1615                        {
1616                                tqueue.push(*it);
1617                        }
1618                }
1619        }
1620}
1621       
1622
1623void ViewCellsTree::PullUpVisibility(ViewCellInterior *interior)
1624{
1625        Intersectable::NewMail((int)interior->mChildren.size());
1626
1627        ViewCellContainer::const_iterator cit, cit_end = interior->mChildren.end();
1628
1629        ObjectPvsMap::const_iterator oit;
1630
1631        // mail all objects in the leaf sets
1632        // we are interested in the objects which are present in all leaves
1633        // => count how often an object is part of a child set
1634        for (cit = interior->mChildren.begin(); cit != cit_end; ++ cit)
1635        {
1636                ViewCell *vc = *cit;
1637
1638                ObjectPvsMap::const_iterator oit_end = vc->GetPvs().mEntries.end();
1639
1640                for (oit = vc->GetPvs().mEntries.begin(); oit != oit_end; ++ oit)
1641                {
1642                        Intersectable *obj = (*oit).first;
1643                        if ((cit == interior->mChildren.begin()) && !obj->Mailed())
1644                                obj->Mail();
1645                       
1646                        int incm = obj->IncMail();
1647                }
1648        }
1649
1650        interior->GetPvs().Clear();
1651       
1652       
1653        // only the objects which are present in all leaf pvs
1654        // should remain in the parent pvs
1655        // these are the objects which have been mailed in all children
1656        for (cit = interior->mChildren.begin(); cit != cit_end; ++ cit)
1657        {
1658                ViewCell *vc = *cit;
1659
1660                ObjectPvsMap::const_iterator oit_end = vc->GetPvs().mEntries.end();
1661
1662                for (oit = vc->GetPvs().mEntries.begin(); oit != oit_end; ++ oit)
1663                {               
1664                        if ((*oit).first->Mailed((int)interior->mChildren.size()))
1665                        {       
1666                                interior->GetPvs().AddSample((*oit).first, (*oit).second.mSumPdf);
1667                        }
1668                }
1669        }
1670
1671
1672        // delete all the objects from the leaf sets which were moved to parent pvs
1673        ObjectPvsMap::const_iterator oit_end = interior->GetPvs().mEntries.end();
1674
1675        for (oit = interior->GetPvs().mEntries.begin(); oit != oit_end; ++ oit)
1676        {
1677                for (cit = interior->mChildren.begin(); cit != cit_end; ++ cit)
1678                {
1679                        if (!(*cit)->GetPvs().RemoveSample((*oit).first, Limits::Infinity))
1680                        {
1681                                Debug << "should not come here!" << endl;
1682                        }
1683                }
1684        }
1685}
1686
1687
1688// TODO matt: implement this function for different storing methods
1689void ViewCellsTree::GetPvs(ViewCell *vc, ObjectPvs &pvs) const
1690{
1691        // pvs is stored in each cell => just return pvs
1692        if (mViewCellsStorage == PVS_IN_INTERIORS)
1693        {
1694                pvs = vc->GetPvs();
1695                return;
1696        }
1697
1698
1699        //-- pvs is not stored with the interiors => reconstruct
1700        Intersectable::NewMail();
1701
1702        int pvsSize = 0;
1703        ViewCell *root = vc;
1704       
1705        // add pvs from this view cell to root
1706        while (root->GetParent())
1707        {
1708                root = root->GetParent();
1709                pvs.AddPvs(root->GetPvs());
1710        }
1711
1712        // add pvs from leaves
1713        stack<ViewCell *> tstack;
1714        tstack.push(vc);
1715
1716        while (!tstack.empty())
1717        {
1718                vc = tstack.top();
1719                tstack.pop();
1720
1721                // add newly found pvs to merged pvs
1722                pvs.AddPvs(vc->GetPvs());
1723
1724                if (!vc->IsLeaf()) // interior cells: go down to leaf level
1725                {
1726                        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
1727
1728                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1729
1730                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
1731                        {
1732                                tstack.push(*it);
1733                        }               
1734                }
1735        }
1736}
1737
1738
1739int ViewCellsTree::GetPvsSizeForLeafStorage(ViewCell *vc) const
1740{
1741        // pvs is always stored directly in leaves
1742        if (vc->IsLeaf())
1743        {
1744                return vc->GetPvs().CountObjectsInPvs();
1745        }
1746       
1747        // interior node
1748       
1749        // interior nodes: pvs is either stored as a scalar or
1750        // has to be reconstructed from the leaves
1751
1752        // the stored pvs size is the valid pvs size => just return scalar
1753        if (vc->mPvsSizeValid)
1754        {
1755                return vc->mPvsSize;
1756        }
1757       
1758        // if no valid pvs size stored as a scalar =>
1759        // compute current pvs size of interior from it's leaf nodes
1760        ViewCellContainer leaves;
1761        CollectLeaves(vc, leaves);
1762
1763        ViewCellContainer::const_iterator it, it_end = leaves.end();
1764
1765        Intersectable::NewMail();
1766        ObjectPvs newPvs;
1767
1768        // sum different intersectables
1769        for (it = leaves.begin(); it != it_end; ++ it)
1770        {
1771                ObjectPvsMap::iterator oit, oit_end = (*it)->GetPvs().mEntries.end();
1772
1773                for (oit = (*it)->GetPvs().mEntries.begin(); oit != oit_end; ++ oit)
1774                {
1775                        Intersectable *intersect = (*oit).first;
1776
1777                        if (!intersect->Mailed())
1778                        {
1779                                intersect->Mail();
1780                                newPvs.AddSample(intersect, (*oit).second.mSumPdf);
1781                        }
1782                }
1783        }
1784
1785        return newPvs.CountObjectsInPvs();
1786}
1787
1788
1789int ViewCellsTree::GetEntriesInPvsForLeafStorage(ViewCell *vc) const
1790{
1791        // pvs is always stored directly in leaves
1792        if (vc->IsLeaf())
1793        {
1794                return vc->GetPvs().GetSize();
1795        }
1796       
1797        // interior node
1798
1799        // interior nodes: pvs is either stored as a scalar or
1800        // has to be reconstructed from the leaves
1801
1802        // the stored pvs size is the valid pvs size => just return scalar
1803        if (vc->mPvsSizeValid)
1804        {
1805                return vc->mEntriesInPvs;
1806        }
1807       
1808        int pvsSize = 0;
1809
1810        // if no valid pvs size stored as a scalar =>
1811        // compute current pvs size of interior from it's leaf nodes
1812        ViewCellContainer leaves;
1813        CollectLeaves(vc, leaves);
1814
1815        ViewCellContainer::const_iterator it, it_end = leaves.end();
1816        Intersectable::NewMail();
1817
1818        // sum different intersectables
1819        for (it = leaves.begin(); it != it_end; ++ it)
1820        {
1821                ObjectPvsMap::iterator oit, oit_end = (*it)->GetPvs().mEntries.end();
1822
1823                for (oit = (*it)->GetPvs().mEntries.begin(); oit != oit_end; ++ oit)
1824                {
1825                        Intersectable *intersect = (*oit).first;
1826
1827                        if (!intersect->Mailed())
1828                        {
1829                                intersect->Mail();
1830                                ++ pvsSize;
1831                        }
1832                }
1833        }
1834
1835        return pvsSize;
1836}
1837
1838
1839int ViewCellsTree::GetPvsSizeForCompressedStorage(ViewCell *vc) const
1840{
1841        int pvsSize = 0;
1842
1843        //-- compressed pvs
1844
1845        // the stored pvs size is the valid pvs size => just return scalar
1846        if (vc->mPvsSizeValid)
1847        {
1848                pvsSize = vc->mPvsSize;
1849        }
1850
1851        // if no pvs size stored, compute new one
1852        ViewCell *root = vc;
1853       
1854        // also add pvs from this view cell to root
1855        while (root->GetParent())
1856        {
1857                root = root->GetParent();
1858       
1859                // matt: bug! must evaluate kd pvss also
1860                pvsSize += CountDiffPvs(root);
1861        }
1862
1863        stack<ViewCell *> tstack;
1864        tstack.push(vc);
1865
1866        while (!tstack.empty())
1867        {
1868                vc = tstack.top();
1869                tstack.pop();
1870                // matt: bug! must evaluate kd pvss also
1871                pvsSize += CountDiffPvs(vc);
1872
1873                if (!vc->IsLeaf())
1874                {
1875                        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
1876
1877                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1878
1879                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
1880                        {
1881                                tstack.push(*it);
1882                        }               
1883                }
1884        }
1885
1886        return pvsSize;
1887}
1888
1889
1890int ViewCellsTree::GetEntriesInPvsForCompressedStorage(ViewCell *vc) const
1891{
1892        int pvsSize = 0;
1893
1894        //-- compressed pvs
1895
1896        // the stored pvs size is the valid pvs size => just return scalar
1897        if (vc->mPvsSizeValid)
1898        {
1899                pvsSize = vc->mEntriesInPvs;
1900        }
1901
1902        // if no pvs size stored, compute new one
1903        ViewCell *root = vc;
1904       
1905        // also add pvs from this view cell to root
1906        while (root->GetParent())
1907        {
1908                root = root->GetParent();
1909                // count the pvs entries different from the already found ones 
1910                pvsSize += CountDiffPvs(root);
1911        }
1912
1913        stack<ViewCell *> tstack;
1914        tstack.push(vc);
1915
1916        while (!tstack.empty())
1917        {
1918                vc = tstack.top();
1919                tstack.pop();
1920       
1921                // count the pvs entries different from the already found ones 
1922                pvsSize += CountDiffPvs(vc);
1923
1924                if (!vc->IsLeaf())
1925                {
1926                        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
1927
1928                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1929
1930                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
1931                        {
1932                                tstack.push(*it);
1933                        }               
1934                }
1935        }
1936
1937        return pvsSize;
1938}
1939
1940
1941int ViewCellsTree::GetPvsSize(ViewCell *vc) const
1942{
1943        int pvsSize = 0;
1944
1945        Intersectable::NewMail();
1946
1947        ////////////////////////////////////////////////
1948        //  for interiors, pvs can be stored using different methods
1949        //
1950
1951        switch (mViewCellsStorage)
1952        {
1953        case PVS_IN_LEAVES: //-- store pvs only in leaves
1954                {                       
1955                        pvsSize = GetPvsSizeForLeafStorage(vc);                 
1956                        break;
1957                }
1958        case COMPRESSED:
1959                {
1960                        pvsSize = GetPvsSizeForCompressedStorage(vc);
1961                        break;
1962                }
1963        case PVS_IN_INTERIORS:
1964        default:
1965                // pvs is stored consistently in the tree up to the root
1966                // just return pvs size
1967                pvsSize = vc->GetPvs().CountObjectsInPvs();     
1968                break;
1969        }
1970
1971        return pvsSize; 
1972}
1973
1974
1975int ViewCellsTree::GetPvsEntries(ViewCell *vc) const
1976{
1977        int pvsSize = 0;
1978
1979        Intersectable::NewMail();
1980
1981        ////////////////////////////////////////////////
1982        // for interiors, pvs can be stored using different methods
1983       
1984        switch (mViewCellsStorage)
1985        {
1986        case PVS_IN_LEAVES: //-- store pvs only in leaves
1987                {                       
1988                        pvsSize = GetEntriesInPvsForLeafStorage(vc);
1989                        break;
1990                }
1991        case COMPRESSED:
1992                {
1993                        pvsSize = GetEntriesInPvsForCompressedStorage(vc);
1994                        break;
1995                }
1996        case PVS_IN_INTERIORS:
1997        default:
1998                // pvs is stored consistently in the tree up to the root
1999                // just return pvs size
2000                pvsSize = vc->GetPvs().GetSize();       
2001                break;
2002        }
2003
2004        return pvsSize; 
2005}
2006
2007
2008float ViewCellsTree::GetMemoryCost(ViewCell *vc) const
2009{
2010        const float entrySize =
2011                sizeof(PvsData) + sizeof(Intersectable *);
2012
2013        return (float)GetStoredPvsEntriesNum(vc) * entrySize;
2014}
2015
2016
2017int ViewCellsTree::GetStoredPvsEntriesNum(ViewCell *root) const
2018{
2019        int pvsSize = root->GetPvs().GetSize();
2020
2021        // recursivly count leaves
2022        if (!root->IsLeaf())
2023        {
2024                ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(root);
2025
2026                ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
2027
2028                for (it = interior->mChildren.begin(); it != it_end; ++ it)
2029                {
2030                        pvsSize += GetStoredPvsEntriesNum(*it);
2031                }
2032        }
2033
2034        return pvsSize;         
2035}
2036
2037
2038int ViewCellsTree::ViewCellsStorage() const
2039{
2040        return mViewCellsStorage;
2041}
2042
2043
2044ViewCell *ViewCellsTree::GetActiveViewCell(ViewCellLeaf *vc) const
2045{
2046        return vc->GetActiveViewCell();
2047}
2048
2049
2050void ViewCellsTree::PropagatePvs(ViewCell *vc)
2051{       
2052        ViewCell *viewCell = vc;
2053
2054        // propagate pvs up
2055        while (viewCell->GetParent())
2056        {
2057                viewCell->GetParent()->GetPvs().Merge(vc->GetPvs());
2058                viewCell = viewCell->GetParent();
2059        }
2060
2061        if (vc->IsLeaf())
2062                return;
2063
2064        // propagate pvs to the leaves
2065        stack<ViewCell *> tstack;
2066        tstack.push(vc);
2067
2068        while (!tstack.empty())
2069        {
2070                ViewCell *viewCell = tstack.top();
2071                tstack.pop();
2072
2073                if (viewCell != vc)
2074                {
2075                        viewCell->GetPvs().Merge(vc->GetPvs());
2076                }
2077
2078                if (!viewCell->IsLeaf())
2079                {
2080                        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(viewCell);
2081
2082                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
2083
2084                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
2085                        {
2086                                tstack.push(*it);
2087                        }
2088                }
2089        }
2090}
2091
2092
2093void ViewCellsTree::AssignRandomColors()
2094{
2095        TraversalQueue tqueue;
2096       
2097        tqueue.push(mRoot);
2098       
2099        mRoot->SetColor(RandomColor(0.3f, 1.0f));
2100       
2101        while (!tqueue.empty())
2102        {
2103                ViewCell *vc = tqueue.top();
2104                tqueue.pop();
2105
2106                // save the view cells if it is a leaf or if enough view cells have already been traversed
2107                // because of the priority queue, this will be the optimal set of v
2108                if (!vc->IsLeaf())
2109                {       
2110                        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
2111                 
2112                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
2113                 
2114                        float maxProbability = -1.0f;
2115                 
2116                        ViewCell *maxViewCell = NULL;
2117                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
2118                        {
2119                                ViewCell *v = *it;
2120                         
2121                                // set random color
2122                                v->SetColor(RandomColor(0.3f, 1.0f));
2123                         
2124                                if (v->GetVolume() > maxProbability)
2125                                {
2126                                        maxProbability = v->GetVolume();
2127                                        maxViewCell = v;
2128                                }
2129
2130                                if (maxViewCell)
2131                                {
2132                                        maxViewCell->SetColor(vc->GetColor());
2133                                }
2134                               
2135                                tqueue.push(v);
2136                        }
2137                }       
2138        }
2139}
2140
2141
2142/** Get costs resulting from each merge step.
2143*/
2144void
2145ViewCellsTree::GetCostFunction(vector<float> &costFunction)
2146{
2147        TraversalQueue tqueue;
2148        tqueue.push(mRoot);
2149       
2150        while (!tqueue.empty())
2151        {
2152                ViewCell *vc = tqueue.top();
2153                tqueue.pop();
2154                // save the view cells if it is a leaf or if enough view cells have already been traversed
2155                // because of the priority queue, this will be the optimal set of v
2156                if (!vc->IsLeaf()) {   
2157                        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
2158                        costFunction.push_back(interior->GetMergeCost());
2159
2160                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
2161
2162                        for (it = interior->mChildren.begin(); it != it_end; ++ it) {
2163                                tqueue.push(*it);
2164                        }
2165
2166                }
2167        }
2168}
2169
2170
2171void ViewCellsTree::UpdateViewCellsStats(ViewCell *vc,
2172                                                                                 ViewCellsStatistics &vcStat)
2173{
2174        ++ vcStat.viewCells;
2175               
2176        const int pvsSize = GetPvsSize(vc);
2177
2178        vcStat.pvsSize += pvsSize;
2179
2180        if (pvsSize == 0)
2181                ++ vcStat.emptyPvs;
2182
2183        if (pvsSize > vcStat.maxPvs)
2184                vcStat.maxPvs = pvsSize;
2185
2186        if (pvsSize < vcStat.minPvs)
2187                vcStat.minPvs = pvsSize;
2188
2189        if (!vc->GetValid())
2190                ++ vcStat.invalid;
2191}
2192
2193
2194bool ViewCellsTree::Export(OUT_STREAM &stream, const bool exportPvs)
2195{
2196        // export recursivly all view cells from the root
2197        ExportViewCell(mRoot, stream, exportPvs);
2198
2199        return true;
2200}
2201
2202
2203void ViewCellsTree::CreateUniqueViewCellsIds()
2204{
2205        stack<ViewCell *> tstack;
2206
2207        int currentId = 0;
2208
2209        tstack.push(mRoot);
2210
2211        while (!tstack.empty())
2212        {
2213                ViewCell *vc = tstack.top();
2214                tstack.pop();
2215
2216                vc->SetId(currentId ++);
2217
2218                if (!vc->IsLeaf())
2219                {
2220                        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
2221                       
2222                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
2223                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
2224                        {
2225                                tstack.push(*it);
2226                        }
2227                }
2228        }
2229}
2230
2231
2232void ViewCellsTree::ExportPvs(ViewCell *viewCell, OUT_STREAM &stream)
2233{
2234        ObjectPvsMap::iterator it, it_end = viewCell->GetPvs().mEntries.end();
2235
2236        for (it = viewCell->GetPvs().mEntries.begin(); it != it_end; ++ it)
2237        {
2238                stream << (*it).first->GetId() << " ";
2239        }
2240}
2241
2242
2243void ViewCellsTree::ExportViewCell(ViewCell *viewCell,
2244                                                                   OUT_STREAM &stream,
2245                                                                   const bool exportPvs)
2246{
2247        if (viewCell->IsLeaf())
2248        {
2249                stream << "<Leaf ";
2250                stream << "id=\"" << viewCell->GetId() << "\" ";
2251                stream << "active=\"" << dynamic_cast<ViewCellLeaf *>(viewCell)->GetActiveViewCell()->GetId() << "\" ";
2252                stream << "mergecost=\"" << viewCell->GetMergeCost() << "\" ";
2253                stream << "pvs=\"";
2254               
2255                //-- export pvs
2256                if (exportPvs)
2257                {
2258                        ExportPvs(viewCell, stream);
2259                }
2260
2261                stream << "\" />" << endl;
2262        }
2263        else
2264        {
2265                ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(viewCell);
2266       
2267                stream << "<Interior ";
2268                stream << "id=\"" << viewCell->GetId() << "\" ";
2269                stream << "mergecost=\"" << viewCell->GetMergeCost() << "\" ";
2270                stream << "pvs=\"";
2271
2272                //-- NOTE: do not export pvss for interior view cells because
2273                // they can be completely reconstructed from the leaf pvss
2274                if (0)
2275                        ExportPvs(viewCell, stream);
2276               
2277                stream << "\" >" << endl;
2278
2279                //-- recursivly export child view cells
2280                ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
2281
2282                for (it = interior->mChildren.begin(); it != it_end; ++ it)
2283                {
2284                        ExportViewCell(*it, stream, exportPvs);
2285                }
2286
2287                stream << "</Interior>" << endl;
2288        }
2289}
2290
2291
2292void ViewCellsTree::ResetPvs()
2293{
2294        stack<ViewCell *> tstack;
2295
2296        tstack.push(mRoot);
2297
2298        while (!tstack.empty())
2299        {
2300                ViewCell *vc = tstack.top();
2301                tstack.pop();
2302
2303                vc->GetPvs().Clear();
2304               
2305                if (!vc->IsLeaf())
2306                {
2307                        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
2308                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
2309
2310                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
2311                        {
2312                                tstack.push(*it);
2313                        }
2314                }
2315        }
2316}
2317
2318
2319void ViewCellsTree::SetActiveSetToLeaves()
2320{
2321        // todo
2322}
2323
2324/**************************************************************************/
2325/*                     MergeCandidate implementation                      */
2326/**************************************************************************/
2327
2328
2329MergeCandidate::MergeCandidate(ViewCell *l, ViewCell *r):
2330mRenderCost(0),
2331mDeviationIncr(0),
2332mLeftViewCell(l),
2333mRightViewCell(r),
2334mInitialLeftViewCell(l),
2335mInitialRightViewCell(r)
2336{
2337        //EvalMergeCost();
2338}
2339
2340
2341void MergeCandidate::SetRightViewCell(ViewCell *v)
2342{
2343        mRightViewCell = v;
2344}
2345
2346
2347void MergeCandidate::SetLeftViewCell(ViewCell *v)
2348{
2349        mLeftViewCell = v;
2350}
2351
2352
2353ViewCell *MergeCandidate::GetRightViewCell() const
2354{
2355        return mRightViewCell;
2356}
2357
2358
2359ViewCell *MergeCandidate::GetLeftViewCell() const
2360{
2361        return mLeftViewCell;
2362}
2363
2364
2365ViewCell *MergeCandidate::GetInitialRightViewCell() const
2366{
2367        return mInitialRightViewCell;
2368}
2369
2370
2371ViewCell *MergeCandidate::GetInitialLeftViewCell() const
2372{
2373        return mInitialLeftViewCell;
2374}
2375
2376
2377bool MergeCandidate::IsValid() const
2378{
2379        // if one has a parent, it was already merged
2380        return !(mLeftViewCell->GetParent() || mRightViewCell->GetParent());
2381}
2382
2383
2384float MergeCandidate::GetRenderCost() const
2385{
2386        return mRenderCost;
2387}
2388
2389
2390float MergeCandidate::GetDeviationIncr() const
2391{
2392        return mDeviationIncr;
2393}
2394
2395
2396float MergeCandidate::GetMergeCost() const
2397{
2398        return mRenderCost * sRenderCostWeight +
2399                   mDeviationIncr * (1.0f - sRenderCostWeight);
2400}
2401
2402
2403
2404
2405
2406
2407/************************************************************************/
2408/*                    MergeStatistics implementation                    */
2409/************************************************************************/
2410
2411
2412void MergeStatistics::Print(ostream &app) const
2413{
2414        app << "===== Merge statistics ===============\n";
2415
2416        app << setprecision(4);
2417
2418        app << "#N_CTIME ( Overall time [s] )\n" << Time() << " \n";
2419
2420        app << "#N_CCTIME ( Collect candidates time [s] )\n" << collectTime * 1e-3f << " \n";
2421
2422        app << "#N_MTIME ( Merge time [s] )\n" << mergeTime * 1e-3f << " \n";
2423
2424        app << "#N_NODES ( Number of nodes before merge )\n" << nodes << "\n";
2425
2426        app << "#N_CANDIDATES ( Number of merge candidates )\n" << candidates << "\n";
2427
2428        app << "#N_MERGEDSIBLINGS ( Number of merged siblings )\n" << siblings << "\n";
2429
2430        app << "#OVERALLCOST ( overall merge cost )\n" << overallCost << "\n";
2431
2432        app << "#N_MERGEDNODES ( Number of merged nodes )\n" << merged << "\n";
2433
2434        app << "#MAX_TREEDIST ( Maximal distance in tree of merged leaves )\n" << maxTreeDist << "\n";
2435
2436        app << "#AVG_TREEDIST ( Average distance in tree of merged leaves )\n" << AvgTreeDist() << "\n";
2437
2438        app << "#EXPECTEDCOST ( expected render cost )\n" << expectedRenderCost << "\n";
2439
2440        app << "#DEVIATION ( deviation )\n" << deviation << "\n";
2441
2442        app << "#HEURISTICS ( heuristics )\n" << heuristics << "\n";
2443       
2444
2445        app << "===== END OF BspTree statistics ==========\n";
2446}
2447
2448}
Note: See TracBrowser for help on using the repository browser.