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

Revision 1667, 61.0 KB checked in by mattausch, 18 years ago (diff)

updated priority meaurement: taking total cost and memory into account

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