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

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