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

Revision 2100, 60.8 KB checked in by mattausch, 17 years ago (diff)

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