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

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