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

Revision 2588, 61.7 KB checked in by bittner, 17 years ago (diff)

sceneBox bugfix

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