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

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