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

Revision 649, 43.7 KB checked in by mattausch, 19 years ago (diff)
Line 
1#include "ViewCell.h"
2#include "Mesh.h"
3#include "Intersectable.h"
4#include "MeshKdTree.h"
5#include "Triangle3.h"
6#include "common.h"
7#include "Environment.h"
8#include "ViewCellsManager.h"
9#include "Exporter.h"
10
11#include <time.h>
12#include <iomanip>
13#include <stack>
14
15
16
17template <typename T> class myless
18{
19public:
20        //bool operator() (HierarchyNode *v1, HierarchyNode *v2) const
21        bool operator() (T v1, T v2) const
22        {
23                return (v1->GetMergeCost() < v2->GetMergeCost());
24        }
25};
26
27
28typedef priority_queue<ViewCell *, vector<ViewCell *>, myless<vector<ViewCell *>::value_type> > TraversalQueue;
29
30int ViewCell::sMailId = 21843194198;
31int ViewCell::sReservedMailboxes = 1;
32
33//int upperPvsLimit = 120;
34//int lowerPvsLimit = 5;
35
36float MergeCandidate::sRenderCostWeight = 0;
37
38
39// pvs penalty can be different from pvs size
40inline float EvalPvsPenalty(const int pvs,
41                                                        const int lower,
42                                                        const int upper)
43{
44        // clamp to minmax values
45        /*if (pvs < lower)
46                return (float)lower;
47        if (pvs > upper)
48                return (float)upper;
49*/
50        return (float)pvs;
51}
52
53
54inline int CountDiffPvs(ViewCell *vc)
55{
56        int count = 0;
57
58        ObjectPvsMap::const_iterator it, it_end = vc->GetPvs().mEntries.end();
59        for (it = vc->GetPvs().mEntries.begin(); it != it_end; ++ it)
60        {
61                if (!(*it).first->Mailed())
62                {
63                        (*it).first->Mail();
64                        ++ count;
65                }
66        }
67
68        return count;
69}
70
71
72int ComputeMergedPvsSize(const ObjectPvs &pvs1, const ObjectPvs &pvs2)
73{
74        int pvs = pvs1.GetSize();
75
76        // compute new pvs size
77        ObjectPvsMap::const_iterator it, it_end =  pvs1.mEntries.end();
78
79        Intersectable::NewMail();
80
81        for (it = pvs1.mEntries.begin(); it != it_end; ++ it)
82        {
83                (*it).first->Mail();
84        }
85
86        it_end = pvs2.mEntries.end();
87
88        for (it = pvs2.mEntries.begin(); it != it_end; ++ it)
89        {
90                Intersectable *obj = (*it).first;
91                if (!obj->Mailed())
92                        ++ pvs;
93        }
94
95        return pvs;
96}
97
98
99ViewCell::ViewCell():
100MeshInstance(NULL),
101mPiercingRays(0),
102mArea(-1),
103mVolume(-1),
104mValid(true),
105mParent(NULL),
106mMergeCost(0),
107mIsActive(false)
108{
109}
110
111ViewCell::ViewCell(Mesh *mesh):
112MeshInstance(mesh),
113mPiercingRays(0),
114mArea(-1),
115mVolume(-1),
116mValid(true),
117mParent(NULL),
118mMergeCost(0),
119mIsActive(false)
120{
121}
122
123
124const ObjectPvs &ViewCell::GetPvs() const
125{
126        return mPvs;
127}
128
129ObjectPvs &ViewCell::GetPvs()
130{
131        return mPvs;
132}
133
134
135int ViewCell::Type() const
136{
137        return VIEW_CELL;
138}
139
140
141float ViewCell::GetVolume() const
142{
143        return mVolume;
144}
145
146
147void ViewCell::SetVolume(float volume)
148{
149        mVolume = volume;
150}
151
152
153void ViewCell::SetMesh(Mesh *mesh)
154{
155        mMesh = mesh;
156}
157
158
159float ViewCell::GetArea() const
160{
161        return mArea;
162}
163
164
165void ViewCell::SetArea(float area)
166{
167        mArea = area;
168}
169
170
171void ViewCell::SetValid(const bool valid)
172{
173        mValid = valid;
174}
175
176
177bool ViewCell::GetValid() const
178{
179        return mValid;
180}
181
182
183/*bool ViewCell::IsLeaf() const
184{
185        return true;
186}*/
187
188
189void ViewCell::SetParent(ViewCellInterior *parent)
190{
191        mParent = parent;
192}
193
194
195bool ViewCell::IsRoot() const
196{
197        return !mParent;
198}
199
200
201ViewCellInterior *ViewCell::GetParent() const
202{
203        return mParent;
204}
205
206
207void ViewCell::SetMergeCost(const float mergeCost)
208{
209        mMergeCost = mergeCost;
210}
211
212
213float ViewCell::GetMergeCost() const
214{
215        return mMergeCost;
216}
217
218
219
220/************************************************************************/
221/*                class ViewCellInterior implementation                 */
222/************************************************************************/
223
224
225ViewCellInterior::ViewCellInterior()
226{
227}
228
229
230ViewCellInterior::~ViewCellInterior()
231{
232        ViewCellContainer::const_iterator it, it_end = mChildren.end();
233
234        for (it = mChildren.begin(); it != it_end; ++ it)
235                delete (*it);
236}
237
238
239ViewCellInterior::ViewCellInterior(Mesh *mesh):
240ViewCell(mesh)
241{
242}
243
244
245bool ViewCellInterior::IsLeaf() const
246{
247        return false;
248}
249
250
251void ViewCellInterior::SetupChildLink(ViewCell *l)
252{
253    mChildren.push_back(l);
254    l->mParent = this;
255}
256
257
258void ViewCellInterior::RemoveChildLink(ViewCell *l)
259{
260        // erase leaf from old view cell
261        ViewCellContainer::iterator it = mChildren.begin();
262
263        for (; (*it) != l; ++ it);
264        if (it == mChildren.end())
265                Debug << "error" << endl;
266        else
267                mChildren.erase(it);
268}
269
270/************************************************************************/
271/*                class ViewCellsStatistics implementation              */
272/************************************************************************/
273
274
275
276
277void ViewCellsStatistics::Print(ostream &app) const
278{
279        app << "=========== View Cells Statistics ===============\n";
280
281        app << setprecision(4);
282
283        //app << "#N_CTIME  ( Construction time [s] )\n" << Time() << " \n";
284
285        app << "#N_OVERALLPVS ( objects in PVS )\n" << pvsSize << endl;
286
287        app << "#N_PMAXPVS ( largest PVS )\n" << maxPvs << endl;
288
289        app << "#N_PMINPVS ( smallest PVS )\n" << minPvs << endl;
290
291        app << "#N_PAVGPVS ( average PVS )\n" << AvgPvs() << endl;
292
293        app << "#N_PEMPTYPVS ( view cells with empty PVS )\n" << emptyPvs << endl;
294
295        app << "#N_VIEWCELLS ( number of view cells)\n" << viewCells << endl;
296
297        app << "#N_AVGLEAVES (average number of leaves per view cell )\n" << AvgLeaves() << endl;
298
299        app << "#N_MAXLEAVES ( maximal number of leaves per view cell )\n" << maxLeaves << endl;
300       
301        app << "#N_INVALID ( number of invalid view cells )\n" << invalid << endl;
302
303        app << "========== End of View Cells Statistics ==========\n";
304}
305
306
307/*************************************************************************/
308/*                    class ViewCellsTree implementation                 */
309/*************************************************************************/
310
311
312ViewCellsTree::ViewCellsTree(ViewCellsManager *vcm):
313mRoot(NULL),
314mUseAreaForPvs(false),
315mViewCellsManager(vcm),
316mIsCompressed(false)
317{
318        environment->GetBoolValue("ViewCells.Visualization.exportMergedViewCells", mExportMergedViewCells);
319        environment->GetFloatValue("ViewCells.maxStaticMemory", mMaxMemory);
320
321        //-- merge options
322        environment->GetFloatValue("ViewCells.PostProcess.renderCostWeight", mRenderCostWeight);
323        environment->GetIntValue("ViewCells.PostProcess.minViewCells", mMergeMinViewCells);
324        environment->GetFloatValue("ViewCells.PostProcess.maxCostRatio", mMergeMaxCostRatio);
325        environment->GetBoolValue("ViewCells.PostProcess.refine", mRefineViewCells);   
326
327
328        Debug << "========= view cell tree options ================\n";
329        Debug << "minimum view cells: " << mMergeMinViewCells << endl;
330        Debug << "max cost ratio: " << mMergeMaxCostRatio << endl;
331        Debug << "max memory: " << mMaxMemory << endl;
332        Debug << "refining view cells: " << mRefineViewCells << endl;
333
334        MergeCandidate::sRenderCostWeight = mRenderCostWeight;
335
336        mStats.open("mergeStats.log");
337}
338
339
340// return memory usage in MB
341float ViewCellsTree::GetMemUsage() const
342{
343        return 0;
344                /*(sizeof(ViewCellsTree) +
345                 mBspStats.Leaves() * sizeof(BspLeaf) +
346                 mBspStats.Interior() * sizeof(BspInterior) +
347                 mBspStats.accumRays * sizeof(RayInfo)) / (1024.0f * 1024.0f);*/
348}
349
350
351int ViewCellsTree::GetSize(ViewCell *vc) const
352{
353        int vcSize = 0;
354
355        stack<ViewCell *> tstack;
356
357        tstack.push(vc);
358
359        while (!tstack.empty())
360        {
361                ViewCell *vc = tstack.top();
362                tstack.pop();
363
364                if (vc->IsLeaf())
365                {
366                        ++ vcSize;
367                }
368                else
369                {
370                        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
371                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
372                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
373                                tstack.push(*it);
374                       
375                }
376        }
377
378        return vcSize;
379}
380
381
382void ViewCellsTree::CollectLeaves(ViewCell *vc, ViewCellContainer &leaves) const
383{
384        stack<ViewCell *> tstack;
385
386        tstack.push(vc);
387
388        while (!tstack.empty())
389        {
390                ViewCell *vc = tstack.top();
391                tstack.pop();
392
393                if (vc->IsLeaf())
394                {
395                        leaves.push_back(vc);
396                }
397                else
398                {
399                        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
400                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
401                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
402                                tstack.push(*it);
403                       
404                }
405        }
406}
407
408
409ViewCellsTree::~ViewCellsTree()
410{
411        DEL_PTR(mRoot);
412}
413
414
415int ViewCellsTree::ConstructMergeTree(const VssRayContainer &rays,
416                                                                          const ObjectContainer &objects)
417{
418        mNumActiveViewCells = (int)mViewCellsManager->GetViewCells().size();
419
420        float variance = 0;
421        int totalPvs = 0;
422        float totalRenderCost = 0;
423
424        //-- compute statistics values of initial view cells
425        mViewCellsManager->EvaluateRenderStatistics(totalRenderCost,
426                                                                                                mExpectedCost,
427                                                                                                mDeviation,
428                                                                                                variance,
429                                                                                                totalPvs,
430                                                                                                mAvgRenderCost);
431
432
433        //-- fill merge queue
434        vector<MergeCandidate> candidates;
435
436        mViewCellsManager->CollectMergeCandidates(rays, candidates);
437        while(!candidates.empty())
438        {
439                MergeCandidate mc = candidates.back();
440                candidates.pop_back();
441                EvalMergeCost(mc);
442                mMergeQueue.push(mc);
443        }
444
445        Debug << "************************* merge ***********************************" << endl; 
446        Debug << "deviation: " << mDeviation << endl;
447        Debug << "avg render cost: " << mAvgRenderCost << endl;
448        Debug << "expected cost: " << mExpectedCost << endl;
449
450
451        ViewCellsManager::PvsStatistics pvsStats;
452        mViewCellsManager->GetPvsStatistics(pvsStats);
453
454        //static float expectedValue = pvsStats.avgPvs;
455       
456        // the current view cells are kept in this container
457        // we start with the current view cells from the
458        // view cell manager. They will change with
459        // subsequent merges
460        ViewCellContainer &activeViewCells = mViewCellsManager->GetViewCells();
461
462
463        ViewCell::NewMail();
464
465        MergeStatistics mergeStats;
466        mergeStats.Start();
467       
468        long startTime = GetTime();
469
470        mergeStats.collectTime = TimeDiff(startTime, GetTime());
471        mergeStats.candidates = (int)mMergeQueue.size();
472        startTime = GetTime();
473
474        // frequency stats are updated
475        const int statsOut = 1;
476
477        // passes are needed for statistics, because we don't want to record
478        // every merge
479        int pass = 0;
480        int mergedPerPass = 0;
481        float realExpectedCost = mExpectedCost;
482        float realAvgRenderCost = mAvgRenderCost;
483        int realNumActiveViewCells = mNumActiveViewCells;
484       
485        // maximal ratio of old expected render cost to expected render
486        // when the the render queue has to be reset.
487        float avgCostMaxDeviation;
488        int maxMergesPerPass;
489        int numMergedViewCells = 0;
490
491        environment->GetIntValue("ViewCells.PostProcess.maxMergesPerPass", maxMergesPerPass);
492        environment->GetFloatValue("ViewCells.PostProcess.avgCostMaxDeviation", avgCostMaxDeviation);
493
494        cout << "actual merge starts now ... " << endl;
495       
496        mStats << "#Pass\n" << pass << endl
497                   << "#Merged\n" << mergeStats.merged << endl
498                   << "#ViewCells\n" << realNumActiveViewCells << endl
499                   << "#RenderCostIncrease\n" << 0 << endl
500                   << "#TotalRenderCost\n" << totalRenderCost << endl
501                   << "#CurrentPvs\n" << 0 << endl
502                   << "#ExpectedCost\n" << realExpectedCost << endl
503                   << "#AvgRenderCost\n" << realAvgRenderCost << endl
504                   << "#Deviation\n" << mDeviation << endl
505                   << "#TotalPvs\n" << totalPvs << endl
506                   << "#PvsSizeDecrease\n0" << endl
507                   << "#Volume\n0" << endl
508                   //<< "#Siblings\n" << mergeStats.siblings << endl
509                   << endl;
510
511        //-- use priority queue to merge leaf pairs
512
513        //const float maxAvgCost = 350;
514        while (!mMergeQueue.empty())//NumActiveViewCells > mMergeMinViewCells))
515        {
516                //-- reset merge queue if the ratio of current expected cost / real expected cost
517                //   too small or after a given number of merges
518                if ((mergedPerPass > maxMergesPerPass) ||
519                        (avgCostMaxDeviation > mAvgRenderCost / realAvgRenderCost))
520                {
521                        Debug << "************ reset queue *****************\n"
522                                  << "ratios: " << avgCostMaxDeviation
523                                  << " real avg render cost " << realAvgRenderCost << " average render cost " << mAvgRenderCost
524                                  << " merged per pass : " << mergedPerPass << " of maximal " << maxMergesPerPass << endl;
525
526                        Debug << "Values before reset: " 
527                                  << " erc: " << mExpectedCost
528                                  << " avgrc: " << mAvgRenderCost
529                                  << " dev: " << mDeviation << endl;
530       
531                        // adjust render cost
532                        ++ pass;
533
534                        mergedPerPass = 0;
535                        mExpectedCost = realExpectedCost;
536                        mAvgRenderCost = realAvgRenderCost;
537                        mNumActiveViewCells = realNumActiveViewCells;
538                       
539                        const int numMergedViewCells = UpdateActiveViewCells(activeViewCells);
540               
541                        // refines the view cells
542                        // then priorities are recomputed
543                        // and the candidates are put back into merge queue
544                        if (mRefineViewCells)
545                                RefineViewCells(rays, objects);
546                        else
547                                ResetMergeQueue();
548
549                        Debug << "Values after reset: " 
550                                  << " erc: " << mExpectedCost
551                                  << " avg: " << mAvgRenderCost
552                                  << " dev: " << mDeviation << endl;
553
554                        if (mExportMergedViewCells)
555                        {
556                                ExportMergedViewCells(activeViewCells, objects, numMergedViewCells);
557                        }
558                }
559
560
561                MergeCandidate mc = mMergeQueue.top();
562                mMergeQueue.pop();
563       
564                // both view cells equal
565                // NOTE: do I really still need this? probably cannot happen!!
566                if (mc.mLeftViewCell == mc.mRightViewCell)
567                        continue;
568
569                if (mc.IsValid())
570                {
571                        ViewCell::NewMail();
572
573                        //-- update statistical values
574                        -- realNumActiveViewCells;
575                        ++ mergeStats.merged;
576                        ++ mergedPerPass;
577
578                        const float renderCostIncr = mc.GetRenderCost();
579                        const float mergeCostIncr = mc.GetMergeCost();
580
581                        totalRenderCost += renderCostIncr;
582                        mDeviation += mc.GetDeviationIncr();
583                       
584                       
585                        // merge the view cells of leaf1 and leaf2
586                        int pvsDiff;
587                        ViewCellInterior *mergedVc =
588                                MergeViewCells(mc.mLeftViewCell, mc.mRightViewCell, pvsDiff);
589
590
591                        // total render cost and deviation has changed
592                        // real expected cost will be larger than expected cost used for the
593                        // cost heuristics, but cannot recompute costs on each increase of the
594                        // expected cost
595                        totalPvs += pvsDiff;
596                        realExpectedCost = totalRenderCost / (float)realNumActiveViewCells;
597                        realAvgRenderCost = (float)totalPvs / (float)realNumActiveViewCells;
598       
599                        // set merge cost to this node
600                        mergedVc->SetMergeCost(totalRenderCost);
601
602                        //if (mViewCellsManager->EqualToSpatialNode(mergedVc))
603                        //      ++ mergeStats.siblings;
604                        mergedVc->SetCost(realExpectedCost);
605
606                        if (((mergeStats.merged % statsOut) == 0) ||
607                        (realNumActiveViewCells == mMergeMinViewCells))
608                        {
609                                cout << "merged " << mergeStats.merged << " view cells" << endl;
610
611                                mStats
612                                        << "#Pass\n" << pass << endl
613                                        << "#Merged\n" << mergeStats.merged << endl
614                                        << "#ViewCells\n" << realNumActiveViewCells << endl
615                    << "#RenderCostIncrease\n" << renderCostIncr << endl
616                                        << "#TotalRenderCost\n" << totalRenderCost << endl
617                                        << "#CurrentPvs\n" << mergedVc->GetPvs().GetSize() << endl
618                    << "#ExpectedCost\n" << realExpectedCost << endl
619                                        << "#AvgRenderCost\n" << realAvgRenderCost << endl
620                                        << "#Deviation\n" << mDeviation << endl
621                                        << "#TotalPvs\n" << totalPvs << endl
622                                        << "#PvsSizeDecrease\n" << -pvsDiff << endl
623                                        << "#Volume\n" << mergedVc->GetVolume() << endl
624                                        << endl;
625                               
626                        }
627                }
628                else
629                {
630                        // merge candidate not valid, because one of the leaves was already
631                        // merged with another one => validate and reinsert into queue
632                        if (ValidateMergeCandidate(mc))
633                        {
634                                EvalMergeCost(mc);
635                                mMergeQueue.push(mc);
636                        }
637                }
638               
639        }
640
641        // adjust stats and reset queue one final time
642        mExpectedCost = realExpectedCost;
643        mAvgRenderCost = realAvgRenderCost;
644        mNumActiveViewCells = realNumActiveViewCells;
645
646        UpdateActiveViewCells(activeViewCells);
647
648        // refine view cells and reset costs
649        if (mRefineViewCells)
650                RefineViewCells(rays, objects);
651        else
652                ResetMergeQueue();
653
654        // create a root node if the merge was not done till root level,
655        // else take the single node as new root
656        if ((int)activeViewCells.size() > 1)
657        {
658                Debug << "creating root of view cell hierarchy for "
659                          << (int)activeViewCells.size() << " view cells" << endl;
660               
661                ViewCellInterior *root = mViewCellsManager->MergeViewCells(activeViewCells);
662                root->SetMergeCost(totalRenderCost);
663                // $$JB keep this 0 temporarilly
664                root->SetCost(0.0f);
665               
666                mStats
667                        << "#Pass\n" << pass << endl
668                        << "#Merged\n" << mergeStats.merged << endl
669                        << "#ViewCells\n" << realNumActiveViewCells << endl
670            << "#RenderCostIncrease\n" << 0 << endl // TODO
671                        << "#TotalRenderCost\n" << totalRenderCost << endl
672                        << "#CurrentPvs\n" << root->GetPvs().GetSize() << endl
673            << "#ExpectedCost\n" << realExpectedCost << endl
674                        << "#AvgRenderCost\n" << realAvgRenderCost << endl
675                        << "#Deviation\n" << mDeviation << endl
676                        << "#TotalPvs\n" << totalPvs << endl
677                        << "#PvsSizeDecrease\n" << 0 << endl // TODO
678                        << "#Volume\n" << root->GetVolume() << endl
679                        << endl;
680
681                mRoot = root;
682        }
683        else if ((int)activeViewCells.size() == 1)
684        {
685                Debug << "setting root of the merge history" << endl;
686                mRoot = activeViewCells[0];
687        }
688
689        //-- empty merge queue just in case
690        while (!mMergeQueue.empty())
691        {
692                mMergeQueue.pop();
693        }
694       
695       
696        // TODO delete because makes no sense here
697        mergeStats.expectedRenderCost = realExpectedCost;
698        mergeStats.deviation = mDeviation;
699
700        // we want to optimize this heuristics
701        mergeStats.heuristics =
702                mDeviation * (1.0f - mRenderCostWeight) +
703                mExpectedCost * mRenderCostWeight;
704
705        mergeStats.mergeTime = TimeDiff(startTime, GetTime());
706        mergeStats.Stop();
707
708        Debug << mergeStats << endl << endl;
709
710        // assign colors for the view cells so that at least one is always consistent
711        AssignRandomColors();
712        //TODO: should return sample contributions?
713        return mergeStats.merged;
714}
715
716
717ViewCell *ViewCellsTree::GetRoot() const
718{
719        return mRoot;
720}
721
722
723void ViewCellsTree::ResetMergeQueue()
724{
725        cout << "reset merge queue ... ";
726       
727        vector<MergeCandidate> buf;
728        buf.reserve(mMergeQueue.size());
729                       
730       
731        // store merge candidates in intermediate buffer
732        while (!mMergeQueue.empty())
733        {
734                MergeCandidate mc = mMergeQueue.top();
735                mMergeQueue.pop();
736               
737                // recalculate cost
738                if (ValidateMergeCandidate(mc))
739                {
740                        EvalMergeCost(mc);
741                        buf.push_back(mc);                             
742                }
743        }
744
745        vector<MergeCandidate>::const_iterator bit, bit_end = buf.end();
746
747        // reinsert back into queue
748        for (bit = buf.begin(); bit != bit_end; ++ bit)
749        {     
750                mMergeQueue.push(*bit);
751        }
752
753        cout << "finished" << endl;
754}
755
756
757int ViewCellsTree::UpdateActiveViewCells(ViewCellContainer &viewCells)
758{
759        int numMergedViewCells = 0;
760
761        Debug << "updating active vc: " << (int)viewCells.size() << endl;
762        // find all already merged view cells and remove them from view cells
763               
764        // sort out all view cells which are not active anymore, i.e., they
765        // were already part of a merge
766        int i = 0;
767
768        ViewCell::NewMail();
769
770        while (1)
771        {
772                // remove all merged view cells from end of the vector
773                while (!viewCells.empty() && (viewCells.back()->GetParent()))
774                {
775                        viewCells.pop_back();
776                }
777
778                // all merged view cells have been found
779                if (i >= viewCells.size())
780                        break;
781
782                // already merged view cell, put it to end of vector
783                if (viewCells[i]->GetParent())
784                        swap(viewCells[i], viewCells.back());
785               
786                viewCells[i ++]->Mail();
787        }
788
789
790        // add new view cells to container only if they don't have been
791        // merged in the mean time
792        ViewCellContainer::const_iterator ait, ait_end = mMergedViewCells.end();
793        for (ait = mMergedViewCells.begin(); ait != ait_end; ++ ait)
794        {
795                ViewCell *vc = mMergedViewCells.back();
796                if (!vc->GetParent() && !vc->Mailed())
797                {
798                        vc->Mail();
799                        viewCells.push_back(vc);
800                        ++ numMergedViewCells;
801                }
802        }
803
804        mMergedViewCells.clear();
805
806        // update standard deviation
807        ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
808       
809        mDeviation = 0;
810
811        for (vit = viewCells.begin(); vit != vit_end; ++ vit)
812        {
813                int lower = mViewCellsManager->GetMinPvsSize();
814                int upper = mViewCellsManager->GetMaxPvsSize();
815                float penalty = EvalPvsPenalty((*vit)->GetPvs().GetSize(), lower, upper);
816               
817                mDeviation += fabs(mAvgRenderCost - penalty);
818        }
819
820        mDeviation /= (float)viewCells.size();
821       
822        return numMergedViewCells;
823}
824
825
826void ViewCellsTree::ExportMergedViewCells(ViewCellContainer &viewCells,
827                                                                                  const ObjectContainer &objects,
828                                                                                  const int numMergedViewCells)
829{
830       
831
832        char s[64];
833
834        sprintf(s, "merged_viewcells%07d.x3d", (int)viewCells.size());
835        Exporter *exporter = Exporter::GetExporter(s);
836
837        if (exporter)
838        {
839                cout << "exporting " << (int)viewCells.size() << " merged view cells ... ";
840                exporter->ExportGeometry(objects);
841                //Debug << "vc size " << (int)viewCells.size() << " merge queue size: " << (int)mMergeQueue.size() << endl;
842                ViewCellContainer::const_iterator it, it_end = viewCells.end();
843
844                int i = 0;
845                for (it = viewCells.begin(); it != it_end; ++ it)
846                {
847                        Material m;
848                        // assign special material to new view cells
849                        // new view cells are on the back of container
850                        if (i ++ >= (viewCells.size() - numMergedViewCells))
851                        {
852                                //m = RandomMaterial();
853                                m.mDiffuseColor.r = RandomValue(0.5f, 1.0f);
854                                m.mDiffuseColor.g = RandomValue(0.5f, 1.0f);
855                                m.mDiffuseColor.b = RandomValue(0.5f, 1.0f);
856                        }
857                        else
858                        {
859                                float col = RandomValue(0.1f, 0.4f);
860                                m.mDiffuseColor.r = col;
861                                m.mDiffuseColor.g = col;
862                                m.mDiffuseColor.b = col;
863                        }
864
865                        exporter->SetForcedMaterial(m);
866                        mViewCellsManager->ExportViewCellGeometry(exporter, *it);
867                }
868                delete exporter;
869                cout << "finished" << endl;
870        }
871}
872
873
874// TODO: should be done in view cells manager
875ViewCellInterior *ViewCellsTree::MergeViewCells(ViewCell *l,
876                                                                                                ViewCell *r,
877                                                                                                int &pvsDiff) //const
878{
879        ViewCellInterior *vc = mViewCellsManager->MergeViewCells(l, r);
880
881        // if merge was unsuccessful
882        if (!vc) return NULL;
883
884        // set new size of view cell
885        if (mUseAreaForPvs)
886                vc->SetArea(l->GetArea() + l->GetArea());
887        else
888        {
889                vc->SetVolume(r->GetVolume() + l->GetVolume());
890        }
891        // important so other merge candidates sharing this view cell
892        // are notified that the merge cost must be updated!!
893        vc->Mail();
894
895        const int pvs1 = l->GetPvs().GetSize();
896        const int pvs2 = r->GetPvs().GetSize();
897
898
899        // new view cells are stored in this vector
900        mMergedViewCells.push_back(vc);
901
902        pvsDiff = vc->GetPvs().GetSize() - pvs1 - pvs2;
903
904        return vc;
905}
906
907
908
909int ViewCellsTree::RefineViewCells(const VssRayContainer &rays,
910                                                                   const ObjectContainer &objects)
911{
912        Debug << "refining " << (int)mMergeQueue.size() << " candidates " << endl;
913
914        // intermediate buffer for shuffled view cells
915        vector<MergeCandidate> buf;
916        buf.reserve(mMergeQueue.size());
917                       
918        // Use priority queue of remaining leaf pairs
919        // The candidates either share the same view cells or
920        // are border leaves which share a boundary.
921        // We test if they can be shuffled, i.e.,
922        // either one leaf is made part of one view cell or the other
923        // leaf is made part of the other view cell. It is tested if the
924        // remaining view cells are "better" than the old ones.
925       
926        const int numPasses = 3;
927        int pass = 0;
928        int passShuffled = 0;
929        int shuffled = 0;
930        int shuffledViewCells = 0;
931
932        ViewCell::NewMail();
933       
934        while (!mMergeQueue.empty())
935        {
936                MergeCandidate mc = mMergeQueue.top();
937                mMergeQueue.pop();
938
939                // both view cells equal or already shuffled
940                if ((mc.GetLeftViewCell() == mc.GetRightViewCell()) ||
941                        mc.GetLeftViewCell()->IsLeaf() || mc.GetRightViewCell()->IsLeaf())
942                {                       
943                        continue;
944                }
945
946                // candidate for shuffling
947                const bool wasShuffled = ShuffleLeaves(mc);
948               
949                // shuffled or put into other queue for further refine
950                if (wasShuffled)
951                {
952                        ++ passShuffled;
953
954                        if (!mc.GetLeftViewCell()->Mailed())
955                        {
956                                mc.GetLeftViewCell()->Mail();
957                                ++ shuffledViewCells;
958                        }
959                        if (!mc.GetRightViewCell()->Mailed())
960                        {
961                                mc.GetRightViewCell()->Mail();
962                                ++ shuffledViewCells;
963                        }
964                }
965
966                // put back into intermediate vector
967                buf.push_back(mc);
968        }
969
970
971        //-- in the end, the candidates must be in the mergequeue again
972        //   with the correct cost
973
974        cout << "reset merge queue ... ";
975       
976       
977        vector<MergeCandidate>::const_iterator bit, bit_end = buf.end();
978       
979        for (bit = buf.begin(); bit != bit_end; ++ bit)
980        {   
981                MergeCandidate mc = *bit;
982                // recalculate cost
983                if (ValidateMergeCandidate(mc))
984                {
985                        EvalMergeCost(mc);
986                        mMergeQueue.push(mc);   
987                }
988        }
989
990        cout << "finished" << endl;
991
992        return shuffledViewCells;
993}
994
995
996
997
998inline int AddedPvsSize(ObjectPvs pvs1, const ObjectPvs &pvs2)
999{
1000        return pvs1.AddPvs(pvs2);
1001}
1002
1003
1004// recomputes pvs size minus pvs of leaf l
1005#if 0
1006inline int SubtractedPvsSize(BspViewCell *vc, BspLeaf *l, const ObjectPvs &pvs2)
1007{
1008        ObjectPvs pvs;
1009        vector<BspLeaf *>::const_iterator it, it_end = vc->mLeaves.end();
1010        for (it = vc->mLeaves.begin(); it != vc->mLeaves.end(); ++ it)
1011                if (*it != l)
1012                        pvs.AddPvs(*(*it)->mPvs);
1013        return pvs.GetSize();
1014}
1015#endif
1016
1017
1018// computes pvs1 minus pvs2
1019inline int SubtractedPvsSize(ObjectPvs pvs1, const ObjectPvs &pvs2)
1020{
1021        return pvs1.SubtractPvs(pvs2);
1022}
1023
1024
1025float ViewCellsTree::EvalShuffleCost(ViewCell *leaf,
1026                                                                         ViewCellInterior *vc1,
1027                                                                         ViewCellInterior *vc2) const
1028{
1029        //const int pvs1 = SubtractedPvsSize(vc1, leaf, *leaf->mPvs);
1030        const int pvs1 = SubtractedPvsSize(vc1->GetPvs(), leaf->GetPvs());
1031        const int pvs2 = AddedPvsSize(vc2->GetPvs(), leaf->GetPvs());
1032
1033        const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize();
1034        const int upperPvsLimit = mViewCellsManager->GetMaxPvsSize();
1035
1036        const float pvsPenalty1 =
1037                EvalPvsPenalty(pvs1, lowerPvsLimit, upperPvsLimit);
1038
1039        const float pvsPenalty2 =
1040                EvalPvsPenalty(pvs2, lowerPvsLimit, upperPvsLimit);
1041
1042
1043        // don't shuffle leaves with pvs > max
1044        if (0 && (pvs1 + pvs2 > mViewCellsManager->GetMaxPvsSize()))
1045        {
1046                return 1e20f;
1047        }
1048
1049        float p1, p2;
1050
1051    if (mUseAreaForPvs)
1052        {
1053                p1 = vc1->GetArea() - leaf->GetArea();
1054                p2 = vc2->GetArea() + leaf->GetArea();
1055        }
1056        else
1057        {
1058                p1 = vc1->GetVolume() - leaf->GetVolume();
1059                p2 = vc2->GetVolume() + leaf->GetVolume();
1060        }
1061
1062        const float renderCost1 = pvsPenalty1 * p1;
1063        const float renderCost2 = pvsPenalty2 * p2;
1064
1065        float dev1, dev2;
1066
1067        if (1)
1068        {
1069                dev1 = fabs(mAvgRenderCost - pvsPenalty1);
1070                dev2 = fabs(mAvgRenderCost - pvsPenalty2);
1071        }
1072        else
1073        {
1074                dev1 = fabs(mExpectedCost - renderCost1);
1075                dev2 = fabs(mExpectedCost - renderCost2);
1076        }
1077       
1078        return mRenderCostWeight * (renderCost1 + renderCost2) +
1079                  (1.0f - mRenderCostWeight) * (dev1 + dev2) / (float)mNumActiveViewCells;
1080}
1081
1082
1083void ViewCellsTree::ShuffleLeaf(ViewCell *leaf,
1084                                                                ViewCellInterior *vc1,
1085                                                                ViewCellInterior *vc2) const
1086{
1087        // compute new pvs and area
1088        // TODO change
1089        vc1->GetPvs().SubtractPvs(leaf->GetPvs());
1090        vc2->GetPvs().AddPvs(leaf->GetPvs());
1091       
1092        if (mUseAreaForPvs)
1093        {
1094                vc1->SetArea(vc1->GetArea() - leaf->GetArea());
1095                vc2->SetArea(vc2->GetArea() + leaf->GetArea());
1096        }
1097        else
1098        {
1099                vc1->SetVolume(vc1->GetVolume() - leaf->GetVolume());
1100                vc2->SetVolume(vc2->GetVolume() + leaf->GetVolume());
1101        }
1102
1103       
1104        ViewCellInterior *p = dynamic_cast<ViewCellInterior *>(leaf->GetParent());
1105
1106        p->RemoveChildLink(leaf);
1107        vc2->SetupChildLink(leaf);
1108}
1109
1110
1111bool ViewCellsTree::ShuffleLeaves(MergeCandidate &mc) const
1112{
1113        float cost1, cost2;
1114
1115        ViewCellInterior *vc1 = dynamic_cast<ViewCellInterior *>(mc.GetLeftViewCell());
1116        ViewCellInterior *vc2 = dynamic_cast<ViewCellInterior *>(mc.GetRightViewCell());
1117
1118        ViewCell *leaf1 = mc.GetInitialLeftViewCell();
1119        ViewCell *leaf2 = mc.GetInitialRightViewCell();
1120
1121        //-- first test if shuffling would decrease cost
1122        cost1 = GetCostHeuristics(vc1);
1123        cost2 = GetCostHeuristics(vc2);
1124
1125        const float oldCost = cost1 + cost2;
1126       
1127        float shuffledCost1 = Limits::Infinity;
1128        float shuffledCost2 = Limits::Infinity;
1129
1130        if (leaf1)
1131                shuffledCost1 = EvalShuffleCost(leaf1, vc1, vc2);       
1132        if (leaf2)
1133                shuffledCost2 = EvalShuffleCost(leaf2, vc2, vc1);
1134
1135        // if cost of shuffle is less than old cost => shuffle
1136        if ((oldCost <= shuffledCost1) && (oldCost <= shuffledCost2))
1137                return false;
1138       
1139        if (shuffledCost1 < shuffledCost2)
1140        {
1141                if (leaf1)
1142                        ShuffleLeaf(leaf1, vc1, vc2);
1143                mc.mInitialLeftViewCell = NULL;
1144        }
1145        else
1146        {
1147                if (leaf2)
1148                        ShuffleLeaf(leaf2, vc2, vc1);
1149                mc.mInitialRightViewCell = NULL;
1150        }
1151
1152        return true;
1153}
1154
1155
1156float ViewCellsTree::GetVariance(ViewCell *vc) const
1157{
1158        const int upper = mViewCellsManager->GetMaxPvsSize();
1159        const int lower = mViewCellsManager->GetMinPvsSize();
1160
1161        if (1)
1162        {
1163                const float penalty = EvalPvsPenalty(vc->GetPvs().GetSize(), lower, upper);
1164                return (mAvgRenderCost - penalty) * (mAvgRenderCost - penalty) / (float)mNumActiveViewCells;
1165        }
1166
1167    const float leafCost = GetRenderCost(vc);
1168        return (mExpectedCost - leafCost) * (mExpectedCost - leafCost);
1169}
1170
1171
1172float ViewCellsTree::GetDeviation(ViewCell *vc) const
1173{
1174        const int upper = mViewCellsManager->GetMaxPvsSize();
1175        const int lower = mViewCellsManager->GetMinPvsSize();
1176
1177        if (1)
1178        {
1179                const float penalty = EvalPvsPenalty(vc->GetPvs().GetSize(), lower, upper);
1180                return fabs(mAvgRenderCost - penalty) / (float)mNumActiveViewCells;
1181        }
1182
1183    const float renderCost = GetRenderCost(vc);
1184        return fabs(mExpectedCost - renderCost);
1185}
1186
1187
1188
1189float ViewCellsTree::GetRenderCost(ViewCell *vc) const
1190{
1191        if (mUseAreaForPvs)
1192                return vc->GetPvs().GetSize() * vc->GetArea();
1193
1194        return vc->GetPvs().GetSize() * vc->GetVolume();
1195}
1196
1197
1198float ViewCellsTree::GetCostHeuristics(ViewCell *vc) const
1199{
1200        return GetRenderCost(vc) * mRenderCostWeight +
1201                   GetDeviation(vc) * (1.0f - mRenderCostWeight);
1202}
1203
1204
1205bool ViewCellsTree::ValidateMergeCandidate(MergeCandidate &mc) const
1206{
1207        while (mc.mLeftViewCell->mParent)
1208        {
1209                mc.mLeftViewCell = mc.mLeftViewCell->mParent;
1210        }
1211
1212        while (mc.mRightViewCell->mParent)
1213        {
1214                mc.mRightViewCell = mc.mRightViewCell->mParent;
1215        }
1216
1217        return mc.mLeftViewCell != mc.mRightViewCell;
1218}
1219
1220
1221void ViewCellsTree::EvalMergeCost(MergeCandidate &mc) const
1222{
1223        //-- compute pvs difference
1224        const int newPvs =
1225                ComputeMergedPvsSize(mc.mLeftViewCell->GetPvs(),
1226                                                         mc.mRightViewCell->GetPvs());
1227                       
1228        const float newPenalty =
1229                EvalPvsPenalty(newPvs,
1230                                           mViewCellsManager->GetMinPvsSize(),
1231                                           mViewCellsManager->GetMaxPvsSize());
1232
1233        ViewCell *vc1 = mc.mLeftViewCell;
1234        ViewCell *vc2 = mc.mRightViewCell;
1235
1236        //-- compute ratio of old cost
1237        //   (i.e., added size of left and right view cell times pvs size)
1238        //   to new rendering cost (i.e, size of merged view cell times pvs size)
1239        const float oldCost = GetRenderCost(vc1) + GetRenderCost(vc2);
1240
1241    const float newCost = mUseAreaForPvs ?
1242                (float)newPenalty * (vc1->GetArea() + vc2->GetArea()) :
1243                (float)newPenalty * (vc1->GetVolume() + vc2->GetVolume());
1244
1245
1246        // strong penalty if pvs size too large
1247        if (0 && (newPvs > mViewCellsManager->GetMaxPvsSize()))
1248        {
1249                mc.mRenderCost = 1e20f;
1250        }
1251        else
1252        {
1253                mc.mRenderCost = (newCost - oldCost) /
1254                        mViewCellsManager->GetViewSpaceBox().GetVolume();
1255        }       
1256       
1257
1258        //-- merge cost also takes deviation into account
1259        float newDev, oldDev;
1260
1261        if (1)
1262                newDev = fabs(mAvgRenderCost - newPenalty) / (float)mNumActiveViewCells;
1263        else
1264                newDev = fabs(mExpectedCost - newCost) / (float)mNumActiveViewCells;
1265       
1266        oldDev = GetDeviation(vc1) + GetDeviation(vc2);
1267
1268        // compute deviation increase
1269        mc.mDeviationIncr = newDev - oldDev;
1270       
1271        //Debug << "render cost: " << mc.mRenderCost * mRenderCostWeight << endl;
1272        //Debug << "standard deviation: " << mc.mDeviationIncr * mRenderCostWeight << endl;
1273}
1274
1275void ViewCellsTree::CompressViewCellsPvs()
1276{
1277        if (!mIsCompressed)
1278        {
1279                mIsCompressed = true;
1280                CompressViewCellsPvs(mRoot);
1281        }
1282}
1283
1284void ViewCellsTree::CompressViewCellsPvs(ViewCell *root)
1285{
1286        if (!root->IsLeaf())
1287        {
1288                ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(root);
1289
1290        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1291               
1292                // compress child sets first
1293                for (it = interior->mChildren.begin(); it != it_end; ++ it)
1294                {
1295                        CompressViewCellsPvs(*it);
1296                }
1297
1298                // compress root node
1299                PullUpVisibility(interior);
1300        }
1301}
1302
1303
1304void ViewCellsTree::CollectBestViewCellSet(ViewCellContainer &viewCells,
1305                                                                                   const int numViewCells)
1306{
1307        TraversalQueue tqueue;
1308        tqueue.push(mRoot);
1309       
1310        while (!tqueue.empty())
1311        {
1312                ViewCell *vc = tqueue.top();
1313               
1314                // save the view cells if it is a leaf or if enough view cells have already been traversed
1315                // because of the priority queue, this will be the optimal set of v
1316                if (vc->IsLeaf() || ((viewCells.size() + tqueue.size()) >= numViewCells))
1317                {
1318                        // todo: should be done with a function taking the active flag and some
1319                        // time stamp so I don't have to reset view cells, this also means that
1320                        // the leaf view cells can be set active fist
1321                        vc->mIsActive = true;
1322                        viewCells.push_back(vc);
1323                }
1324                else
1325                {       
1326                        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
1327
1328                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1329
1330                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
1331                        {
1332                                tqueue.push(*it);
1333                        }
1334                }
1335
1336                tqueue.pop();
1337        }
1338}
1339       
1340
1341void ViewCellsTree::PullUpVisibility(ViewCellInterior *interior)
1342{
1343        Intersectable::NewMail((int)interior->mChildren.size());
1344
1345        ViewCellContainer::const_iterator cit, cit_end = interior->mChildren.end();
1346
1347        ObjectPvsMap::const_iterator oit;
1348
1349        // mail all objects in the leaf sets
1350        // we are interested in the objects which are present in all leaves
1351        // => count how often an object is part of a child set
1352        for (cit = interior->mChildren.begin(); cit != cit_end; ++ cit)
1353        {
1354                ViewCell *vc = *cit;
1355
1356                ObjectPvsMap::const_iterator oit_end = vc->GetPvs().mEntries.end();
1357
1358                for (oit = vc->GetPvs().mEntries.begin(); oit != oit_end; ++ oit)
1359                {
1360                        Intersectable *obj = (*oit).first;
1361                        if ((cit == interior->mChildren.begin()) && !obj->Mailed())
1362                                obj->Mail();
1363                       
1364                        int incm = obj->IncMail();
1365                }
1366        }
1367
1368        interior->GetPvs().mEntries.clear();
1369       
1370       
1371        // only the objects which are present in all leaf pvs
1372        // should remain in the parent pvs
1373        // these are the objects which have been mailed in all children
1374        for (cit = interior->mChildren.begin(); cit != cit_end; ++ cit)
1375        {
1376                ViewCell *vc = *cit;
1377
1378                ObjectPvsMap::const_iterator oit_end = vc->GetPvs().mEntries.end();
1379
1380                for (oit = vc->GetPvs().mEntries.begin(); oit != oit_end; ++ oit)
1381                {               
1382                        if ((*oit).first->Mailed((int)interior->mChildren.size()))
1383                        {       
1384                                interior->GetPvs().AddSample((*oit).first, (*oit).second.mSumPdf);
1385                        }
1386                }
1387        }
1388
1389
1390
1391        // delete all the objects from the leaf sets which were moved to parent pvs
1392        ObjectPvsMap::const_iterator oit_end = interior->GetPvs().mEntries.end();
1393
1394        for (oit = interior->GetPvs().mEntries.begin(); oit != oit_end; ++ oit)
1395        {
1396                for (cit = interior->mChildren.begin(); cit != cit_end; ++ cit)
1397                {
1398                        if (!(*cit)->GetPvs().RemoveSample((*oit).first, Limits::Infinity))
1399                                Debug << "should not come here!" << endl;
1400                }
1401        }
1402
1403        int dummy = interior->GetPvs().GetSize();
1404
1405        for (cit = interior->mChildren.begin(); cit != cit_end; ++ cit)
1406        {
1407                dummy += (*cit)->GetPvs().GetSize();
1408        }
1409
1410}
1411
1412
1413void ViewCellsTree::ExportStats()
1414{
1415
1416}
1417
1418void ViewCellsTree::GetPvs(ViewCell *vc, ObjectPvs &pvs) const
1419{
1420        Intersectable::NewMail();
1421
1422        if (!mIsCompressed)
1423                pvs = vc->GetPvs();
1424
1425        int pvsSize = 0;
1426        ViewCell *root = vc;
1427       
1428        // also add pvs from this view cell to root
1429        while (root->GetParent())
1430        {
1431                root = root->GetParent();
1432                pvs.AddPvs(root->GetPvs());
1433        }
1434
1435        stack<ViewCell *> tstack;
1436        tstack.push(vc);
1437
1438        while (!tstack.empty())
1439        {
1440                vc = tstack.top();
1441                tstack.pop();
1442
1443                pvs.AddPvs(vc->GetPvs());
1444
1445                if (!vc->IsLeaf())
1446                {
1447                        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
1448
1449                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1450
1451                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
1452                        {
1453                                tstack.push(*it);
1454                        }               
1455                }
1456        }
1457}
1458
1459
1460int ViewCellsTree::GetPvsSize(ViewCell *vc) const
1461{
1462        Intersectable::NewMail();
1463
1464        if (!mIsCompressed)
1465                return vc->GetPvs().GetSize();
1466
1467        int pvsSize = 0;
1468        ViewCell *root = vc;
1469       
1470        // also add pvs from this view cell to root
1471        while (root->GetParent())
1472        {
1473                root = root->GetParent();
1474                pvsSize += CountDiffPvs(root);
1475        }
1476
1477        stack<ViewCell *> tstack;
1478        tstack.push(vc);
1479
1480        while (!tstack.empty())
1481        {
1482                vc = tstack.top();
1483                tstack.pop();
1484
1485                pvsSize += CountDiffPvs(vc);
1486
1487                if (!vc->IsLeaf())
1488                {
1489                        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
1490
1491                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1492
1493                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
1494                        {
1495                                tstack.push(*it);
1496                        }               
1497                }
1498        }
1499
1500        return pvsSize; 
1501
1502}
1503
1504
1505float ViewCellsTree::GetMemoryCost(ViewCell *vc) const
1506{
1507        const float entrySize =
1508                sizeof(PvsData<Intersectable *>) + sizeof(Intersectable *);
1509
1510        return (float)GetNumPvsEntries(vc) * entrySize;
1511}
1512
1513
1514int ViewCellsTree::GetNumPvsEntries(ViewCell *vc) const
1515{
1516        int pvsSize = 0;
1517        // only count leaves for uncompressed method for fairness
1518        if (mIsCompressed || vc->IsLeaf())
1519                pvsSize = vc->GetPvs().GetSize();
1520
1521        if (!vc->IsLeaf())
1522        {
1523                ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
1524
1525                ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1526
1527                for (it = interior->mChildren.begin(); it != it_end; ++ it)
1528                {
1529                        pvsSize += GetNumPvsEntries(*it);
1530                }
1531        }
1532
1533        return pvsSize;         
1534}
1535
1536
1537bool ViewCellsTree::IsCompressed() const
1538{
1539        return mIsCompressed;
1540}
1541
1542
1543ViewCell *ViewCellsTree::GetActiveViewCell(ViewCell *vc) const
1544{
1545        while (vc->GetParent() && !vc->mIsActive)
1546        {
1547                vc = vc->GetParent();
1548        }
1549
1550        return vc;
1551}
1552
1553
1554void ViewCellsTree::PropagateUpPvs(ViewCell *vc)
1555{
1556        while (vc->GetParent())
1557        {
1558                vc->GetParent()->GetPvs().Merge(vc->GetPvs());
1559                vc = vc->GetParent();
1560        }
1561}
1562
1563
1564void
1565ViewCellsTree::AssignRandomColors()
1566{
1567  TraversalQueue tqueue;
1568  tqueue.push(mRoot);
1569  mRoot->SetColor(RandomColor(0.3f, 1.0f));
1570  while (!tqueue.empty())
1571        {
1572          ViewCell *vc = tqueue.top();
1573         
1574          // save the view cells if it is a leaf or if enough view cells have already been traversed
1575          // because of the priority queue, this will be the optimal set of v
1576          if (!vc->IsLeaf()) { 
1577                ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
1578               
1579                ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1580                float maxProbability = -1.0f;
1581                ViewCell *maxViewCell = NULL;
1582                for (it = interior->mChildren.begin(); it != it_end; ++ it) {
1583                  ViewCell *v = *it;
1584                  // set random color
1585                  v->SetColor(RandomColor(0.3f, 1.0f));
1586                  if (v->GetVolume() > maxProbability) {
1587                        maxProbability = v->GetVolume();
1588                        maxViewCell = v;
1589                  }
1590                  maxViewCell->SetColor(vc->GetColor());
1591                  tqueue.push(v);
1592                }
1593               
1594          }
1595         
1596          tqueue.pop();
1597        }
1598}
1599
1600/** Get costs resulting from each merge step. */
1601void
1602ViewCellsTree::GetCostFunction(vector<float> &costFunction)
1603{
1604  TraversalQueue tqueue;
1605  tqueue.push(mRoot);
1606  while (!tqueue.empty()) {
1607        ViewCell *vc = tqueue.top();
1608       
1609        // save the view cells if it is a leaf or if enough view cells have already been traversed
1610        // because of the priority queue, this will be the optimal set of v
1611        if (!vc->IsLeaf()) {   
1612          ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
1613          costFunction.push_back(interior->GetCost());
1614         
1615          ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1616         
1617          for (it = interior->mChildren.begin(); it != it_end; ++ it) {
1618                tqueue.push(*it);
1619          }
1620         
1621        }
1622       
1623        tqueue.pop();
1624  }
1625}
1626
1627
1628void  ViewCellsTree::UpdateViewCellsStats(ViewCell *vc, ViewCellsStatistics &vcStat)
1629{
1630        ++ vcStat.viewCells;
1631               
1632        const int pvsSize = GetPvsSize(vc);
1633
1634        vcStat.pvsSize += pvsSize;
1635
1636        if (pvsSize == 0)
1637                ++ vcStat.emptyPvs;
1638
1639        if (pvsSize > vcStat.maxPvs)
1640                vcStat.maxPvs = pvsSize;
1641
1642        if (pvsSize < vcStat.minPvs)
1643                vcStat.minPvs = pvsSize;
1644
1645        if (!vc->GetValid())
1646                ++ vcStat.invalid;
1647
1648        /*ViewCellsContainer leaves;
1649        CollectLeaves(vc, leaves);
1650
1651        vcStat.leaves = (int)leaves.size();*/
1652}
1653
1654
1655bool ViewCellsTree::Export(ofstream &stream)
1656{
1657        ExportViewCell(mRoot, stream);
1658
1659        return true;
1660}
1661
1662
1663void ViewCellsTree::ExportViewCell(ViewCell *viewCell, ofstream &stream)
1664{
1665        ObjectPvsMap::iterator it, it_end = viewCell->GetPvs().mEntries.end();
1666
1667        if (0) // test with empty pvs
1668        for (it = viewCell->GetPvs().mEntries.begin(); it != it_end; ++ it)
1669        {
1670                stream << (*it).first->GetId() << " ";
1671        }
1672
1673        stream << "\" />" << endl;
1674
1675        if (viewCell->IsLeaf())
1676        {
1677                stream << "<Leaf ";
1678                stream << "id=\"" << viewCell->GetId() << "\" ";
1679                stream << "active=\"" << viewCell->mIsActive << "\" ";
1680                stream << "mergecost=\"" << viewCell->GetMergeCost() << "\" ";
1681                stream << "pvs=\"";
1682                stream << "</Leaf>" << endl;
1683        }
1684        else
1685        {
1686                ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(viewCell);
1687       
1688                stream << "<Interior ";
1689                stream << "id=\"" << viewCell->GetId() << "\" ";
1690                stream << "active=\"" << viewCell->mIsActive << "\" ";
1691                stream << "mergecost=\"" << viewCell->GetMergeCost() << "\" ";
1692                stream << "pvs=\"";
1693
1694                ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1695
1696                for (it = interior->mChildren.begin(); it != it_end; ++ it)
1697                {
1698                        ExportViewCell(*it, stream);
1699                }
1700
1701                stream << "</Interior>" << endl;
1702        }
1703}
1704
1705
1706
1707/**************************************************************************/
1708/*                     MergeCandidate implementation                      */
1709/**************************************************************************/
1710
1711
1712MergeCandidate::MergeCandidate(ViewCell *l, ViewCell *r):
1713mRenderCost(0),
1714mDeviationIncr(0),
1715mLeftViewCell(l),
1716mRightViewCell(r),
1717mInitialLeftViewCell(l),
1718mInitialRightViewCell(r)
1719{
1720        //EvalMergeCost();
1721}
1722
1723
1724void MergeCandidate::SetRightViewCell(ViewCell *v)
1725{
1726        mRightViewCell = v;
1727}
1728
1729
1730void MergeCandidate::SetLeftViewCell(ViewCell *v)
1731{
1732        mLeftViewCell = v;
1733}
1734
1735
1736ViewCell *MergeCandidate::GetRightViewCell() const
1737{
1738        return mRightViewCell;
1739}
1740
1741
1742ViewCell *MergeCandidate::GetLeftViewCell() const
1743{
1744        return mLeftViewCell;
1745}
1746
1747
1748ViewCell *MergeCandidate::GetInitialRightViewCell() const
1749{
1750        return mInitialRightViewCell;
1751}
1752
1753
1754ViewCell *MergeCandidate::GetInitialLeftViewCell() const
1755{
1756        return mInitialLeftViewCell;
1757}
1758
1759
1760bool MergeCandidate::IsValid() const
1761{
1762        return !(mLeftViewCell->mParent || mRightViewCell->mParent);
1763}
1764
1765
1766float MergeCandidate::GetRenderCost() const
1767{
1768        return mRenderCost;
1769}
1770
1771
1772float MergeCandidate::GetDeviationIncr() const
1773{
1774        return mDeviationIncr;
1775}
1776
1777
1778float MergeCandidate::GetMergeCost() const
1779{
1780        return mRenderCost * sRenderCostWeight +
1781                   mDeviationIncr * (1.0f - sRenderCostWeight);
1782}
1783
1784
1785
1786
1787
1788
1789/************************************************************************/
1790/*                    MergeStatistics implementation                    */
1791/************************************************************************/
1792
1793
1794void MergeStatistics::Print(ostream &app) const
1795{
1796        app << "===== Merge statistics ===============\n";
1797
1798        app << setprecision(4);
1799
1800        app << "#N_CTIME ( Overall time [s] )\n" << Time() << " \n";
1801
1802        app << "#N_CCTIME ( Collect candidates time [s] )\n" << collectTime * 1e-3f << " \n";
1803
1804        app << "#N_MTIME ( Merge time [s] )\n" << mergeTime * 1e-3f << " \n";
1805
1806        app << "#N_NODES ( Number of nodes before merge )\n" << nodes << "\n";
1807
1808        app << "#N_CANDIDATES ( Number of merge candidates )\n" << candidates << "\n";
1809
1810        app << "#N_MERGEDSIBLINGS ( Number of merged siblings )\n" << siblings << "\n";
1811
1812        app << "#OVERALLCOST ( overall merge cost )\n" << overallCost << "\n";
1813
1814        app << "#N_MERGEDNODES ( Number of merged nodes )\n" << merged << "\n";
1815
1816        app << "#MAX_TREEDIST ( Maximal distance in tree of merged leaves )\n" << maxTreeDist << "\n";
1817
1818        app << "#AVG_TREEDIST ( Average distance in tree of merged leaves )\n" << AvgTreeDist() << "\n";
1819
1820        app << "#EXPECTEDCOST ( expected render cost )\n" << expectedRenderCost << "\n";
1821
1822        app << "#DEVIATION ( deviation )\n" << deviation << "\n";
1823
1824        app << "#HEURISTICS ( heuristics )\n" << heuristics << "\n";
1825       
1826
1827        app << "===== END OF BspTree statistics ==========\n";
1828}
Note: See TracBrowser for help on using the repository browser.