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

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