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

Revision 2227, 60.0 KB checked in by mattausch, 18 years ago (diff)

added render cost bound for objects, improved undersampling compensation

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