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

Revision 2117, 60.2 KB checked in by mattausch, 17 years ago (diff)

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