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

Revision 2643, 61.6 KB checked in by mattausch, 17 years ago (diff)

compiling under release internal

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