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

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