source: trunk/VUT/GtpVisibilityPreprocessor/src/ViewCell.cpp @ 612

Revision 612, 43.6 KB checked in by mattausch, 18 years ago (diff)

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