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

Revision 1758, 60.2 KB checked in by mattausch, 18 years ago (diff)

bvhnode is now derived from Intersectable
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        ViewCell *root = vc;
1730       
1731        // add pvs from this view cell to root
1732        while (root->GetParent())
1733        {
1734                root = root->GetParent();
1735                pvs.MergeInPlace(root->GetPvs());
1736        }
1737
1738        // add pvs from leaves
1739        stack<ViewCell *> tstack;
1740        tstack.push(vc);
1741
1742        while (!tstack.empty())
1743        {
1744                vc = tstack.top();
1745                tstack.pop();
1746       
1747                // add newly found pvs to merged pvs
1748                pvs.MergeInPlace(vc->GetPvs());
1749               
1750                if (!vc->IsLeaf()) // interior cells: go down to leaf level
1751                {
1752                        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
1753                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1754
1755                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
1756                        {
1757                                tstack.push(*it);
1758                        }               
1759                }
1760        }
1761}
1762
1763
1764float ViewCellsTree::GetPvsCostForLeafStorage(ViewCell *vc) const
1765{
1766        // pvs is always stored directly in leaves
1767        if (vc->IsLeaf())
1768        {
1769                return vc->GetPvs().EvalPvsCost();
1770        }
1771       
1772        // interior nodes: pvs is either stored as a
1773        // scalar or has to be reconstructed from the leaves
1774        // the stored pvs size is the valid pvs size => just return scalar
1775        if (vc->mPvsSizeValid)
1776        {
1777                return vc->mPvsCost;
1778        }
1779       
1780        // if no valid pvs size stored as a scalar =>
1781        // compute current pvs size of interior from it's leaf nodes
1782        ViewCellContainer leaves;
1783        CollectLeaves(vc, leaves);
1784
1785        ViewCellContainer::const_iterator it, it_end = leaves.end();
1786
1787        Intersectable::NewMail();
1788        ObjectPvs newPvs;
1789
1790        // sum up uniquely found intersectables
1791        for (it = leaves.begin(); it != it_end; ++ it)
1792        {
1793                ObjectPvsIterator oit = (*it)->GetPvs().GetIterator();
1794
1795                while (oit.HasMoreEntries())
1796                {
1797                        ObjectPvsEntry entry = oit.Next();
1798                        Intersectable *intersect = entry.mObject;
1799
1800                        if (!intersect->Mailed())
1801                        {
1802                                intersect->Mail();
1803                                newPvs.AddSample(intersect, entry.mData.mSumPdf);
1804                        }
1805                }
1806        }
1807
1808        return newPvs.EvalPvsCost();
1809}
1810
1811
1812int ViewCellsTree::GetEntriesInPvsForLeafStorage(ViewCell *vc) const
1813{
1814        // pvs is always stored directly in leaves
1815        if (vc->IsLeaf())
1816        {
1817                return vc->GetPvs().GetSize();
1818        }
1819       
1820        // interior node
1821
1822        // interior nodes: pvs is either stored as a scalar or
1823        // has to be reconstructed from the leaves
1824
1825        // the stored pvs size is the valid pvs size => just return scalar
1826        if (vc->mPvsSizeValid)
1827        {
1828                return vc->mEntriesInPvs;
1829        }
1830       
1831        int pvsSize = 0;
1832
1833        // if no valid pvs size stored as a scalar =>
1834        // compute current pvs size of interior from it's leaf nodes
1835        ViewCellContainer leaves;
1836        CollectLeaves(vc, leaves);
1837
1838        ViewCellContainer::const_iterator it, it_end = leaves.end();
1839        Intersectable::NewMail();
1840
1841        // sum different intersectables
1842        for (it = leaves.begin(); it != it_end; ++ it)
1843        {
1844                ObjectPvsIterator oit = (*it)->GetPvs().GetIterator();
1845
1846                while (oit.HasMoreEntries())
1847                {
1848                        ObjectPvsEntry entry = oit.Next();
1849                        Intersectable *intersect = entry.mObject;
1850
1851                        if (!intersect->Mailed())
1852                        {
1853                                intersect->Mail();
1854                                ++ pvsSize;
1855                        }
1856                }
1857        }
1858
1859        return pvsSize;
1860}
1861
1862
1863float ViewCellsTree::GetPvsCostForCompressedStorage(ViewCell *vc) const
1864{
1865        float pvsCost = 0;
1866
1867        /////////////
1868        //-- compressed pvs
1869
1870        // the stored pvs size is the valid pvs size => just return scalar
1871        if (vc->mPvsSizeValid)
1872        {
1873                pvsCost = vc->mPvsCost;
1874        }
1875
1876        // if no pvs size stored, compute new one
1877        ViewCell *root = vc;
1878       
1879        // also add pvs from this view cell to root
1880        while (root->GetParent())
1881        {
1882                root = root->GetParent();
1883       
1884                // matt: bug! must evaluate kd pvss also
1885                pvsCost += CountPvsContribution(root);
1886        }
1887
1888        stack<ViewCell *> tstack;
1889        tstack.push(vc);
1890
1891        while (!tstack.empty())
1892        {
1893                vc = tstack.top();
1894                tstack.pop();
1895
1896                // matt: bug! must evaluate kd pvss also
1897                pvsCost += CountPvsContribution(vc);
1898
1899                if (!vc->IsLeaf())
1900                {
1901                        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
1902                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1903
1904                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
1905                        {
1906                                tstack.push(*it);
1907                        }               
1908                }
1909        }
1910
1911        return pvsCost;
1912}
1913
1914
1915int ViewCellsTree::GetEntriesInPvsForCompressedStorage(ViewCell *vc) const
1916{
1917        int pvsSize = 0;
1918
1919        /////////////////
1920        //-- compressed pvs
1921
1922        // the stored pvs size is the valid pvs size => just return scalar
1923        if (vc->mPvsSizeValid)
1924        {
1925                pvsSize = vc->mEntriesInPvs;
1926        }
1927
1928        // if no pvs size stored, compute new one
1929        ViewCell *root = vc;
1930       
1931        // also add pvs from this view cell to root
1932        while (root->GetParent())
1933        {
1934                root = root->GetParent();
1935                // count the pvs entries different from the already found ones 
1936                pvsSize += CountPvsContribution(root);
1937        }
1938
1939        stack<ViewCell *> tstack;
1940        tstack.push(vc);
1941
1942        while (!tstack.empty())
1943        {
1944                vc = tstack.top();
1945                tstack.pop();
1946       
1947                // count the pvs entries different from the already found ones 
1948                pvsSize += CountPvsContribution(vc);
1949
1950                if (!vc->IsLeaf())
1951                {
1952                        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
1953
1954                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1955
1956                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
1957                        {
1958                                tstack.push(*it);
1959                        }               
1960                }
1961        }
1962
1963        return pvsSize;
1964}
1965
1966
1967float ViewCellsTree::GetPvsCost(ViewCell *vc) const
1968{
1969        float pvsCost = 0;
1970        Intersectable::NewMail();
1971
1972        ////////////////////////////////////////////////
1973        // for interiors, pvs can be stored using different methods
1974        //
1975
1976        switch (mViewCellsStorage)
1977        {
1978        case PVS_IN_LEAVES:
1979                // pvs is stored only in leaves
1980                pvsCost = GetPvsCostForLeafStorage(vc);                 
1981                break;
1982        case COMPRESSED:
1983                pvsCost = GetPvsCostForCompressedStorage(vc);
1984                break;
1985        case PVS_IN_INTERIORS:
1986        default:
1987                // pvs is stored consistently in the tree up
1988                //to the root just return pvs size
1989                pvsCost = vc->GetPvs().EvalPvsCost();   
1990                break;
1991        }
1992
1993        return pvsCost; 
1994}
1995
1996
1997int ViewCellsTree::GetPvsEntries(ViewCell *vc) const
1998{
1999        int pvsSize = 0;
2000
2001        Intersectable::NewMail();
2002
2003        ////////////////////////////////////////////////
2004        // for interiors, pvs can be stored using different methods
2005       
2006        switch (mViewCellsStorage)
2007        {
2008        case PVS_IN_LEAVES:
2009                {
2010                        //-- store pvs only in leaves
2011                        pvsSize = GetEntriesInPvsForLeafStorage(vc);
2012                        break;
2013                }
2014        case COMPRESSED:
2015                {
2016                        pvsSize = GetEntriesInPvsForCompressedStorage(vc);
2017                        break;
2018                }
2019        case PVS_IN_INTERIORS:
2020        default:
2021                // pvs is stored consistently in the tree up to the root
2022                // just return pvs size
2023                pvsSize = vc->GetPvs().GetSize();       
2024                break;
2025        }
2026
2027        return pvsSize; 
2028}
2029
2030
2031float ViewCellsTree::GetMemoryCost(ViewCell *vc) const
2032{
2033        return (float)CountStoredPvsEntries(vc) * ObjectPvs::GetEntrySize();
2034}
2035
2036//#if HAS_TO_BE_REDONE
2037int ViewCellsTree::CountStoredPvsEntries(ViewCell *root) const
2038{
2039        int pvsSize = root->GetPvs().GetSize();
2040
2041        // recursivly count leaves
2042        if (!root->IsLeaf())
2043        {
2044                ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(root);
2045
2046                ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
2047
2048                for (it = interior->mChildren.begin(); it != it_end; ++ it)
2049                {
2050                        pvsSize += CountStoredPvsEntries(*it);
2051                }
2052        }
2053
2054        return pvsSize;         
2055}
2056//#endif
2057
2058int ViewCellsTree::ViewCellsStorage() const
2059{
2060        return mViewCellsStorage;
2061}
2062
2063
2064ViewCell *ViewCellsTree::GetActiveViewCell(ViewCellLeaf *vc) const
2065{
2066        return vc->GetActiveViewCell();
2067}
2068
2069
2070void ViewCellsTree::PropagatePvs(ViewCell *root)
2071{       
2072        ViewCell *viewCell = root;
2073
2074        // propagate pvs up
2075        while (viewCell->GetParent())
2076        {
2077                ObjectPvs mergedPvs;
2078                viewCell->GetParent()->GetPvs().MergeInPlace(root->GetPvs());
2079
2080                viewCell = viewCell->GetParent();
2081        }
2082
2083        if (root->IsLeaf())
2084                return;
2085
2086        // propagate pvs to the leaves
2087        stack<ViewCell *> tstack;
2088        tstack.push(root);
2089
2090        while (!tstack.empty())
2091        {
2092                ViewCell *viewCell = tstack.top();
2093                tstack.pop();
2094
2095                if (viewCell != root)
2096                {
2097                        viewCell->GetPvs().MergeInPlace(root->GetPvs());
2098                }
2099
2100                if (!viewCell->IsLeaf())
2101                {
2102                        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(viewCell);
2103
2104                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
2105
2106                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
2107                        {
2108                                tstack.push(*it);
2109                        }
2110                }
2111        }
2112}
2113
2114
2115void ViewCellsTree::AssignRandomColors()
2116{
2117        TraversalQueue tqueue;
2118        tqueue.push(mRoot);
2119       
2120        mRoot->SetColor(RandomColor(0.3f, 1.0f));
2121       
2122        while (!tqueue.empty())
2123        {
2124                ViewCell *vc = tqueue.top();
2125                tqueue.pop();
2126
2127                // save the view cells if it is a leaf or if enough view cells
2128                // have already been traversed because of the priority queue,
2129                // this will be the optimal set of v
2130                if (!vc->IsLeaf())
2131                {       
2132                        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
2133                 
2134                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
2135                 
2136                        float maxProbability = -1.0f;
2137                 
2138                        ViewCell *maxViewCell = NULL;
2139                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
2140                        {
2141                                ViewCell *v = *it;
2142                         
2143                                // set random color
2144                                v->SetColor(RandomColor(0.3f, 1.0f));
2145                         
2146                                if (v->GetVolume() > maxProbability)
2147                                {
2148                                        maxProbability = v->GetVolume();
2149                                        maxViewCell = v;
2150                                }
2151
2152                                if (maxViewCell)
2153                                {
2154                                        maxViewCell->SetColor(vc->GetColor());
2155                                }
2156                               
2157                                tqueue.push(v);
2158                        }
2159                }       
2160        }
2161}
2162
2163
2164/** Get costs resulting from each merge step.
2165*/
2166void ViewCellsTree::GetCostFunction(vector<float> &costFunction)
2167{
2168        TraversalQueue tqueue;
2169        tqueue.push(mRoot);
2170
2171        int numViewCells = 1;
2172
2173        const float vol = mViewCellsManager->GetViewSpaceBox().GetVolume();
2174        const float rootPvs = GetPvsCost(mRoot);
2175       
2176        float totalRenderCost;
2177
2178        float totalPvsCost = rootPvs;
2179        totalRenderCost = (float)rootPvs;
2180
2181        costFunction.push_back(totalRenderCost);
2182
2183        //-- go through tree in the order of render cost decrease
2184        //-- which is the same order as the view cells were merged
2185        //-- or the reverse order of subdivision for subdivision-only
2186        //-- view cell hierarchies.
2187
2188        while (!tqueue.empty())
2189        {
2190                ViewCell *vc = tqueue.top();
2191                tqueue.pop();
2192
2193                if (!vc->IsLeaf())
2194                {       
2195                        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
2196
2197                        const float parentCost = GetPvsCost(interior);
2198                        const float parentExpCost = parentCost * interior->GetVolume();
2199
2200                        -- numViewCells;
2201
2202                        float childExpCost = 0;
2203                        float childCost = 0;
2204                       
2205                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
2206
2207                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
2208                        {
2209                                ViewCell *vc = *it;
2210
2211                                const float pvsCost = GetPvsCost(vc);
2212                               
2213                                childExpCost += (float) pvsCost * vc->GetVolume();
2214                                childCost += pvsCost;
2215                               
2216                                tqueue.push(vc);
2217                                ++ numViewCells;
2218                        }
2219
2220                        // update stats for this view cell
2221                        const float costDecr = (parentExpCost - childExpCost) / vol;
2222                        totalRenderCost -= costDecr;
2223                       
2224                        costFunction.push_back(totalRenderCost);
2225                }
2226        }
2227}
2228
2229
2230/** Get storage costs resulting from each merge step.
2231*/
2232void ViewCellsTree::GetStorageFunction(vector<int> &storageFunction)
2233{
2234        TraversalQueue tqueue;
2235        tqueue.push(mRoot);
2236
2237        int numViewCells = 1;
2238
2239        const float vol = mViewCellsManager->GetViewSpaceBox().GetVolume();
2240        const int rootEntries = GetPvsEntries(mRoot);
2241
2242        int entriesInPvs = rootEntries;
2243    const int entryStorage = sizeof(PvsData) + sizeof(int); // one entry into the pvs
2244
2245        storageFunction.push_back(rootEntries);
2246
2247        ////////////
2248        //-- go through tree in the order of render cost decrease
2249        //-- which is the same order as the view cells were merged
2250        //-- or the reverse order of subdivision for subdivision-only
2251        //-- view cell hierarchies.
2252
2253        while (!tqueue.empty())
2254        {
2255                ViewCell *vc = tqueue.top();
2256                tqueue.pop();
2257
2258                if (!vc->IsLeaf())
2259                {       
2260                        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
2261
2262                        const float parentPvsCost = GetPvsCost(interior);
2263                        const int parentPvsEntries = GetPvsEntries(interior);
2264            const float parentExpCost = (float)parentPvsCost * interior->GetVolume();
2265
2266                        float childExpCost = 0;
2267                        int childPvs = 0;
2268                        int childPvsEntries = 0;
2269
2270                        -- numViewCells;
2271
2272                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
2273
2274                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
2275                        {
2276                                ViewCell *vc = *it;
2277
2278                                const int pvsEntries = GetPvsEntries(vc);
2279                                childPvsEntries += pvsEntries;
2280
2281                                tqueue.push(vc);
2282                                ++ numViewCells;
2283                        }
2284
2285                        // update stats for this view cell
2286                        const float costDecr = (parentExpCost - childExpCost) / vol;
2287
2288                        entriesInPvs += childPvsEntries - parentPvsEntries;
2289
2290                        const int storageCost = entriesInPvs * entryStorage;
2291                        storageFunction.push_back(storageCost);
2292                }
2293        }
2294}
2295
2296
2297
2298void ViewCellsTree::UpdateViewCellsStats(ViewCell *vc,
2299                                                                                 ViewCellsStatistics &vcStat)
2300{
2301        ++ vcStat.viewCells;
2302               
2303        const float pvsCost = GetPvsCost(vc);
2304
2305        vcStat.pvsCost += pvsCost;
2306
2307        if (pvsCost < Limits::Small)
2308                ++ vcStat.emptyPvs;
2309
2310        if (pvsCost > vcStat.maxPvs)
2311                vcStat.maxPvs = pvsCost;
2312
2313        if (pvsCost < vcStat.minPvs)
2314                vcStat.minPvs = pvsCost;
2315
2316        if (!vc->GetValid())
2317                ++ vcStat.invalid;
2318}
2319
2320
2321bool ViewCellsTree::Export(OUT_STREAM &stream, const bool exportPvs)
2322{
2323        // export recursivly all view cells from the root
2324        ExportViewCell(mRoot, stream, exportPvs);
2325
2326        return true;
2327}
2328
2329
2330void ViewCellsTree::CreateUniqueViewCellsIds()
2331{
2332        stack<ViewCell *> tstack;
2333
2334        int currentId = 0;
2335
2336        tstack.push(mRoot);
2337
2338        while (!tstack.empty())
2339        {
2340                ViewCell *vc = tstack.top();
2341                tstack.pop();
2342
2343                if (vc->GetId() != -1) // out of bounds
2344                        vc->SetId(currentId ++);
2345
2346                if (!vc->IsLeaf())
2347                {
2348                        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
2349                       
2350                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
2351                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
2352                        {
2353                                tstack.push(*it);
2354                        }
2355                }
2356        }
2357}
2358
2359
2360void ViewCellsTree::ExportPvs(ViewCell *viewCell, OUT_STREAM &stream)
2361{
2362        ObjectPvsIterator it = viewCell->GetPvs().GetIterator();
2363
2364        while (it.HasMoreEntries())
2365        {
2366                ObjectPvsEntry entry = it.Next();
2367                Intersectable *obj = entry.mObject;
2368
2369                // hack: just output full pvs
2370                if (obj->Type() == Intersectable::BVH_INTERSECTABLE)
2371                {
2372                        ObjectContainer objects;
2373                        BvhNode *node = dynamic_cast<BvhNode *>(obj);
2374                        node->CollectObjects(objects);
2375               
2376                        ObjectContainer::const_iterator oit, oit_end = objects.end();
2377                        for (oit = objects.begin(); oit != oit_end; ++ oit)
2378                        {
2379                                stream << (*oit)->GetId() << " ";
2380                        }
2381                }
2382                else
2383                {
2384                        stream << entry.mObject->GetId() << " ";
2385                }
2386        }
2387}
2388
2389
2390void ViewCellsTree::ExportViewCell(ViewCell *viewCell,
2391                                                                   OUT_STREAM &stream,
2392                                                                   const bool exportPvs)
2393{
2394        if (viewCell->IsLeaf())
2395        {
2396                stream << "<Leaf ";
2397                stream << "id=\"" << viewCell->GetId() << "\" ";
2398                stream << "active=\"" << dynamic_cast<ViewCellLeaf *>(viewCell)->GetActiveViewCell()->GetId() << "\" ";
2399                stream << "mergecost=\"" << viewCell->GetMergeCost() << "\" ";
2400                stream << "pvs=\"";
2401               
2402                //-- export pvs, i.e., the ids of the objects in the pvs
2403                if (exportPvs)
2404                {
2405                        ExportPvs(viewCell, stream);
2406                }
2407                stream << "\" />" << endl;
2408        }
2409        else
2410        {
2411                ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(viewCell);
2412       
2413                stream << "<Interior ";
2414                stream << "id=\"" << viewCell->GetId() << "\" ";
2415                stream << "mergecost=\"" << viewCell->GetMergeCost() << "\" ";
2416                stream << "pvs=\"";
2417
2418                // NOTE: do not export pvss for interior view cells because
2419                // they can be completely reconstructed from the leaf pvss
2420                // on the other hand: we could store a tag with the compression scheme,
2421        // then some scheme were pvs is in the interiors could be used
2422                if (0) ExportPvs(viewCell, stream);
2423               
2424                stream << "\" >" << endl;
2425
2426                //-- recursivly export child view cells
2427                ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
2428
2429                for (it = interior->mChildren.begin(); it != it_end; ++ it)
2430                {
2431                        ExportViewCell(*it, stream, exportPvs);
2432                }
2433
2434                stream << "</Interior>" << endl;
2435        }
2436}
2437
2438
2439void ViewCellsTree::ResetPvs()
2440{
2441        stack<ViewCell *> tstack;
2442
2443        tstack.push(mRoot);
2444
2445        while (!tstack.empty())
2446        {
2447                ViewCell *vc = tstack.top();
2448                tstack.pop();
2449
2450                vc->GetPvs().Clear();
2451               
2452                if (!vc->IsLeaf())
2453                {
2454                        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
2455                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
2456
2457                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
2458                        {
2459                                tstack.push(*it);
2460                        }
2461                }
2462        }
2463}
2464
2465
2466void ViewCellsTree::SetViewCellsManager(ViewCellsManager *vcm)
2467{
2468        mViewCellsManager = vcm;
2469}
2470
2471
2472void ViewCellsTree::SetActiveSetToLeaves()
2473{
2474        // todo
2475}
2476
2477
2478/**************************************************************************/
2479/*                     MergeCandidate implementation                      */
2480/**************************************************************************/
2481
2482
2483MergeCandidate::MergeCandidate(ViewCell *l, ViewCell *r):
2484mRenderCost(0),
2485mDeviationIncr(0),
2486mLeftViewCell(l),
2487mRightViewCell(r),
2488mInitialLeftViewCell(l),
2489mInitialRightViewCell(r)
2490{
2491        //EvalMergeCost();
2492}
2493
2494
2495void MergeCandidate::SetRightViewCell(ViewCell *v)
2496{
2497        mRightViewCell = v;
2498}
2499
2500
2501void MergeCandidate::SetLeftViewCell(ViewCell *v)
2502{
2503        mLeftViewCell = v;
2504}
2505
2506
2507ViewCell *MergeCandidate::GetRightViewCell() const
2508{
2509        return mRightViewCell;
2510}
2511
2512
2513ViewCell *MergeCandidate::GetLeftViewCell() const
2514{
2515        return mLeftViewCell;
2516}
2517
2518
2519ViewCell *MergeCandidate::GetInitialRightViewCell() const
2520{
2521        return mInitialRightViewCell;
2522}
2523
2524
2525ViewCell *MergeCandidate::GetInitialLeftViewCell() const
2526{
2527        return mInitialLeftViewCell;
2528}
2529
2530
2531bool MergeCandidate::IsValid() const
2532{
2533        // if one has a parent, it was already merged
2534        return !(mLeftViewCell->GetParent() || mRightViewCell->GetParent());
2535}
2536
2537
2538float MergeCandidate::GetRenderCost() const
2539{
2540        return mRenderCost;
2541}
2542
2543
2544float MergeCandidate::GetDeviationIncr() const
2545{
2546        return mDeviationIncr;
2547}
2548
2549
2550float MergeCandidate::GetMergeCost() const
2551{
2552        return mRenderCost * sRenderCostWeight +
2553                   mDeviationIncr * (1.0f - sRenderCostWeight);
2554}
2555
2556
2557
2558/************************************************************************/
2559/*                    MergeStatistics implementation                    */
2560/************************************************************************/
2561
2562
2563void MergeStatistics::Print(ostream &app) const
2564{
2565        app << "===== Merge statistics ===============\n";
2566
2567        app << setprecision(4);
2568
2569        app << "#N_CTIME ( Overall time [s] )\n" << Time() << " \n";
2570
2571        app << "#N_CCTIME ( Collect candidates time [s] )\n" << collectTime * 1e-3f << " \n";
2572
2573        app << "#N_MTIME ( Merge time [s] )\n" << mergeTime * 1e-3f << " \n";
2574
2575        app << "#N_NODES ( Number of nodes before merge )\n" << nodes << "\n";
2576
2577        app << "#N_CANDIDATES ( Number of merge candidates )\n" << candidates << "\n";
2578
2579        app << "#N_MERGEDSIBLINGS ( Number of merged siblings )\n" << siblings << "\n";
2580
2581        app << "#OVERALLCOST ( overall merge cost )\n" << overallCost << "\n";
2582
2583        app << "#N_MERGEDNODES ( Number of merged nodes )\n" << merged << "\n";
2584
2585        app << "#MAX_TREEDIST ( Maximal distance in tree of merged leaves )\n" << maxTreeDist << "\n";
2586
2587        app << "#AVG_TREEDIST ( Average distance in tree of merged leaves )\n" << AvgTreeDist() << "\n";
2588
2589        app << "#EXPECTEDCOST ( expected render cost )\n" << expectedRenderCost << "\n";
2590
2591        app << "#DEVIATION ( deviation )\n" << deviation << "\n";
2592
2593        app << "#HEURISTICS ( heuristics )\n" << heuristics << "\n";
2594       
2595
2596        app << "===== END OF BspTree statistics ==========\n";
2597}
2598
2599
2600}
Note: See TracBrowser for help on using the repository browser.