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

Revision 607, 39.8 KB checked in by mattausch, 18 years ago (diff)

added method for associating spatial hierarchy leaf with view cell
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        mStats << "#Pass\n" << pass << endl
500                   << "#Merged\n" << mergeStats.merged << endl
501                   << "#ViewCells\n" << realNumActiveViewCells << endl
502                   << "#RenderCostIncrease\n" << 0 << endl
503                   << "#TotalRenderCost\n" << totalRenderCost << endl
504                   << "#CurrentPvs\n" << 0 << endl
505                   << "#ExpectedCost\n" << realExpectedCost << endl
506                   << "#AvgRenderCost\n" << realAvgRenderCost << endl
507                   << "#Deviation\n" << mDeviation << endl
508                   << "#TotalPvs\n" << totalPvs << endl
509                   << "#PvsSizeDecrease\n0" << endl
510                   << "#Volume\n" << endl
511                   << "#Siblings\n" << mergeStats.siblings << 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 (mViewCellsManager->EqualToSpatialNode(mergedVc))
607                                ++ mergeStats.siblings;
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                        }
628                }
629                else
630                {
631                        // merge candidate not valid, because one of the leaves was already
632                        // merged with another one => validate and reinsert into queue
633                        if (ValidateMergeCandidate(mc))
634                        {
635                                EvalMergeCost(mc);
636                                mMergeQueue.push(mc);
637                        }
638                }
639        }
640
641        // adjust stats and reset queue one final time
642        mExpectedCost = realExpectedCost;
643        mAvgRenderCost = realAvgRenderCost;
644        mNumActiveViewCells = realNumActiveViewCells;
645
646        UpdateActiveViewCells(activeViewCells);
647
648        // refine view cells and reset costs
649        if (mRefineViewCells)
650                RefineViewCells(rays, objects);
651        else
652                ResetMergeQueue();
653
654        // create a root node if the merge was not done till root level,
655        // else take the single node as new root
656        if ((int)activeViewCells.size() > 1)
657        {
658                Debug << "creating root of view cell hierarchy for "
659                          << (int)activeViewCells.size() << " view cells" << endl;
660                /*for (int i = 0;  i < activeViewCells.size(); ++ i){
661                        Debug << "parent " << activeViewCells[i]->GetParent() << endl;
662                        Debug << "viewcell " << activeViewCells[i] << endl;
663                }*/
664                ViewCellInterior *root = mViewCellsManager->MergeViewCells(activeViewCells);
665                root->SetMergeCost(totalRenderCost);
666                mRoot = root;
667        }
668        else if ((int)activeViewCells.size() == 1)
669        {
670                Debug << "setting root of the merge history" << endl;
671                mRoot = activeViewCells[0];
672        }
673
674
675        while (!mMergeQueue.empty())
676        {
677                mMergeQueue.pop();
678        }
679       
680       
681        // TODO delete because makes no sense here
682        mergeStats.expectedRenderCost = realExpectedCost;
683        mergeStats.deviation = mDeviation;
684
685        // we want to optimize this heuristics
686        mergeStats.heuristics =
687                mDeviation * (1.0f - mRenderCostWeight) +
688                mExpectedCost * mRenderCostWeight;
689
690        mergeStats.mergeTime = TimeDiff(startTime, GetTime());
691        mergeStats.Stop();
692
693        Debug << mergeStats << endl << endl;
694
695
696        //TODO: should return sample contributions?
697        return mergeStats.merged;
698}
699
700
701ViewCell *ViewCellsTree::GetRoot() const
702{
703        return mRoot;
704}
705
706
707void ViewCellsTree::ResetMergeQueue()
708{
709        cout << "reset merge queue ... ";
710       
711        vector<MergeCandidate> buf;
712        buf.reserve(mMergeQueue.size());
713                       
714       
715        // store merge candidates in intermediate buffer
716        while (!mMergeQueue.empty())
717        {
718                MergeCandidate mc = mMergeQueue.top();
719                mMergeQueue.pop();
720               
721                // recalculate cost
722                if (ValidateMergeCandidate(mc))
723                {
724                        EvalMergeCost(mc);
725                        buf.push_back(mc);                             
726                }
727        }
728
729        vector<MergeCandidate>::const_iterator bit, bit_end = buf.end();
730
731        // reinsert back into queue
732        for (bit = buf.begin(); bit != bit_end; ++ bit)
733        {     
734                mMergeQueue.push(*bit);
735        }
736
737        cout << "finished" << endl;
738}
739
740
741int ViewCellsTree::UpdateActiveViewCells(ViewCellContainer &viewCells)
742{
743        int numMergedViewCells = 0;
744
745        Debug << "updating active vc: " << (int)viewCells.size() << endl;
746        // find all already merged view cells and remove them from view cells
747               
748        // sort out all view cells which are not active anymore, i.e., they
749        // were already part of a merge
750        int i = 0;
751
752        ViewCell::NewMail();
753
754        while (1)
755        {
756                // remove all merged view cells from end of the vector
757                while (!viewCells.empty() && (viewCells.back()->GetParent()))
758                {
759                        viewCells.pop_back();
760                }
761
762                // all merged view cells have been found
763                if (i >= viewCells.size())
764                        break;
765
766                // already merged view cell, put it to end of vector
767                if (viewCells[i]->GetParent())
768                        swap(viewCells[i], viewCells.back());
769               
770                viewCells[i ++]->Mail();
771        }
772
773
774        // add new view cells to container only if they don't have been
775        // merged in the mean time
776        ViewCellContainer::const_iterator ait, ait_end = mMergedViewCells.end();
777        for (ait = mMergedViewCells.begin(); ait != ait_end; ++ ait)
778        {
779                ViewCell *vc = mMergedViewCells.back();
780                if (!vc->GetParent() && !vc->Mailed())
781                {
782                        vc->Mail();
783                        viewCells.push_back(vc);
784                        ++ numMergedViewCells;
785                }
786        }
787
788        mMergedViewCells.clear();
789
790        // update standard deviation
791        ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
792       
793        mDeviation = 0;
794
795        for (vit = viewCells.begin(); vit != vit_end; ++ vit)
796        {
797                int lower = mViewCellsManager->GetMinPvsSize();
798                int upper = mViewCellsManager->GetMaxPvsSize();
799                float penalty = EvalPvsPenalty((*vit)->GetPvs().GetSize(), lower, upper);
800               
801                mDeviation += fabs(mAvgRenderCost - penalty);
802        }
803
804        mDeviation /= (float)viewCells.size();
805       
806        return numMergedViewCells;
807}
808
809
810void ViewCellsTree::ExportMergedViewCells(ViewCellContainer &viewCells,
811                                                                                  const ObjectContainer &objects,
812                                                                                  const int numMergedViewCells)
813{
814       
815
816        char s[64];
817
818        sprintf(s, "merged_viewcells%07d.x3d", (int)viewCells.size());
819        Exporter *exporter = Exporter::GetExporter(s);
820
821        if (exporter)
822        {
823                cout << "exporting " << (int)viewCells.size() << " merged view cells ... ";
824                exporter->ExportGeometry(objects);
825                //Debug << "vc size " << (int)viewCells.size() << " merge queue size: " << (int)mMergeQueue.size() << endl;
826                ViewCellContainer::const_iterator it, it_end = viewCells.end();
827
828                int i = 0;
829                for (it = viewCells.begin(); it != it_end; ++ it)
830                {
831                        Material m;
832                        // assign special material to new view cells
833                        // new view cells are on the back of container
834                        if (i ++ >= (viewCells.size() - numMergedViewCells))
835                        {
836                                //m = RandomMaterial();
837                                m.mDiffuseColor.r = RandomValue(0.5f, 1.0f);
838                                m.mDiffuseColor.g = RandomValue(0.5f, 1.0f);
839                                m.mDiffuseColor.b = RandomValue(0.5f, 1.0f);
840                        }
841                        else
842                        {
843                                float col = RandomValue(0.1f, 0.4f);
844                                m.mDiffuseColor.r = col;
845                                m.mDiffuseColor.g = col;
846                                m.mDiffuseColor.b = col;
847                        }
848
849                        exporter->SetForcedMaterial(m);
850                        mViewCellsManager->ExportViewCellGeometry(exporter, *it);
851                }
852                delete exporter;
853                cout << "finished" << endl;
854        }
855}
856
857
858// TODO: should be done in view cells manager
859ViewCellInterior *ViewCellsTree::MergeViewCells(ViewCell *l,
860                                                                                                ViewCell *r,
861                                                                                                int &pvsDiff) //const
862{
863        ViewCellInterior *vc = mViewCellsManager->MergeViewCells(l, r);
864
865        // if merge was unsuccessful
866        if (!vc) return NULL;
867
868        // set new size of view cell
869        if (mUseAreaForPvs)
870                vc->SetArea(l->GetArea() + l->GetArea());
871        else
872        {
873                vc->SetVolume(r->GetVolume() + l->GetVolume());
874        }
875        // important so other merge candidates sharing this view cell
876        // are notified that the merge cost must be updated!!
877        vc->Mail();
878
879        const int pvs1 = l->GetPvs().GetSize();
880        const int pvs2 = r->GetPvs().GetSize();
881
882
883        // new view cells are stored in this vector
884        mMergedViewCells.push_back(vc);
885
886        pvsDiff = vc->GetPvs().GetSize() - pvs1 - pvs2;
887
888        return vc;
889}
890
891
892
893int ViewCellsTree::RefineViewCells(const VssRayContainer &rays,
894                                                                   const ObjectContainer &objects)
895{
896        Debug << "refining " << (int)mMergeQueue.size() << " candidates " << endl;
897
898        // intermediate buffer for shuffled view cells
899        vector<MergeCandidate> buf;
900        buf.reserve(mMergeQueue.size());
901                       
902        // Use priority queue of remaining leaf pairs
903        // The candidates either share the same view cells or
904        // are border leaves which share a boundary.
905        // We test if they can be shuffled, i.e.,
906        // either one leaf is made part of one view cell or the other
907        // leaf is made part of the other view cell. It is tested if the
908        // remaining view cells are "better" than the old ones.
909       
910        const int numPasses = 3;
911        int pass = 0;
912        int passShuffled = 0;
913        int shuffled = 0;
914        int shuffledViewCells = 0;
915
916        ViewCell::NewMail();
917       
918        while (!mMergeQueue.empty())
919        {
920                MergeCandidate mc = mMergeQueue.top();
921                mMergeQueue.pop();
922
923                // both view cells equal or already shuffled
924                if ((mc.GetLeftViewCell() == mc.GetRightViewCell()) ||
925                        mc.GetLeftViewCell()->IsLeaf() || mc.GetRightViewCell()->IsLeaf())
926                {                       
927                        continue;
928                }
929
930                // candidate for shuffling
931                const bool wasShuffled = ShuffleLeaves(mc);
932               
933                // shuffled or put into other queue for further refine
934                if (wasShuffled)
935                {
936                        ++ passShuffled;
937
938                        if (!mc.GetLeftViewCell()->Mailed())
939                        {
940                                mc.GetLeftViewCell()->Mail();
941                                ++ shuffledViewCells;
942                        }
943                        if (!mc.GetRightViewCell()->Mailed())
944                        {
945                                mc.GetRightViewCell()->Mail();
946                                ++ shuffledViewCells;
947                        }
948                }
949
950                // put back into intermediate vector
951                buf.push_back(mc);
952        }
953
954
955        //-- in the end, the candidates must be in the mergequeue again
956        //   with the correct cost
957
958        cout << "reset merge queue ... ";
959       
960       
961        vector<MergeCandidate>::const_iterator bit, bit_end = buf.end();
962       
963        for (bit = buf.begin(); bit != bit_end; ++ bit)
964        {   
965                MergeCandidate mc = *bit;
966                // recalculate cost
967                if (ValidateMergeCandidate(mc))
968                {
969                        EvalMergeCost(mc);
970                        mMergeQueue.push(mc);   
971                }
972        }
973
974        cout << "finished" << endl;
975
976        return shuffledViewCells;
977}
978
979
980
981
982inline int AddedPvsSize(ObjectPvs pvs1, const ObjectPvs &pvs2)
983{
984        return pvs1.AddPvs(pvs2);
985}
986
987
988// recomputes pvs size minus pvs of leaf l
989#if 0
990inline int SubtractedPvsSize(BspViewCell *vc, BspLeaf *l, const ObjectPvs &pvs2)
991{
992        ObjectPvs pvs;
993        vector<BspLeaf *>::const_iterator it, it_end = vc->mLeaves.end();
994        for (it = vc->mLeaves.begin(); it != vc->mLeaves.end(); ++ it)
995                if (*it != l)
996                        pvs.AddPvs(*(*it)->mPvs);
997        return pvs.GetSize();
998}
999#endif
1000
1001
1002// computes pvs1 minus pvs2
1003inline int SubtractedPvsSize(ObjectPvs pvs1, const ObjectPvs &pvs2)
1004{
1005        return pvs1.SubtractPvs(pvs2);
1006}
1007
1008
1009float ViewCellsTree::EvalShuffleCost(ViewCell *leaf,
1010                                                                         ViewCellInterior *vc1,
1011                                                                         ViewCellInterior *vc2) const
1012{
1013        //const int pvs1 = SubtractedPvsSize(vc1, leaf, *leaf->mPvs);
1014        const int pvs1 = SubtractedPvsSize(vc1->GetPvs(), leaf->GetPvs());
1015        const int pvs2 = AddedPvsSize(vc2->GetPvs(), leaf->GetPvs());
1016
1017        const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize();
1018        const int upperPvsLimit = mViewCellsManager->GetMaxPvsSize();
1019
1020        const float pvsPenalty1 =
1021                EvalPvsPenalty(pvs1, lowerPvsLimit, upperPvsLimit);
1022
1023        const float pvsPenalty2 =
1024                EvalPvsPenalty(pvs2, lowerPvsLimit, upperPvsLimit);
1025
1026
1027        // don't shuffle leaves with pvs > max
1028        if (0 && (pvs1 + pvs2 > mViewCellsManager->GetMaxPvsSize()))
1029        {
1030                return 1e20f;
1031        }
1032
1033        float p1, p2;
1034
1035    if (mUseAreaForPvs)
1036        {
1037                p1 = vc1->GetArea() - leaf->GetArea();
1038                p2 = vc2->GetArea() + leaf->GetArea();
1039        }
1040        else
1041        {
1042                p1 = vc1->GetVolume() - leaf->GetVolume();
1043                p2 = vc2->GetVolume() + leaf->GetVolume();
1044        }
1045
1046        const float renderCost1 = pvsPenalty1 * p1;
1047        const float renderCost2 = pvsPenalty2 * p2;
1048
1049        float dev1, dev2;
1050
1051        if (1)
1052        {
1053                dev1 = fabs(mAvgRenderCost - pvsPenalty1);
1054                dev2 = fabs(mAvgRenderCost - pvsPenalty2);
1055        }
1056        else
1057        {
1058                dev1 = fabs(mExpectedCost - renderCost1);
1059                dev2 = fabs(mExpectedCost - renderCost2);
1060        }
1061       
1062        return mRenderCostWeight * (renderCost1 + renderCost2) +
1063                  (1.0f - mRenderCostWeight) * (dev1 + dev2) / (float)mNumActiveViewCells;
1064}
1065
1066
1067void ViewCellsTree::ShuffleLeaf(ViewCell *leaf,
1068                                                                ViewCellInterior *vc1,
1069                                                                ViewCellInterior *vc2) const
1070{
1071        // compute new pvs and area
1072        // TODO change
1073        vc1->GetPvs().SubtractPvs(leaf->GetPvs());
1074        vc2->GetPvs().AddPvs(leaf->GetPvs());
1075       
1076        if (mUseAreaForPvs)
1077        {
1078                vc1->SetArea(vc1->GetArea() - leaf->GetArea());
1079                vc2->SetArea(vc2->GetArea() + leaf->GetArea());
1080        }
1081        else
1082        {
1083                vc1->SetVolume(vc1->GetVolume() - leaf->GetVolume());
1084                vc2->SetVolume(vc2->GetVolume() + leaf->GetVolume());
1085        }
1086
1087       
1088        ViewCellInterior *p = dynamic_cast<ViewCellInterior *>(leaf->GetParent());
1089
1090        p->RemoveChildLink(leaf);
1091        vc2->SetupChildLink(leaf);
1092}
1093
1094
1095bool ViewCellsTree::ShuffleLeaves(MergeCandidate &mc) const
1096{
1097        float cost1, cost2;
1098
1099        ViewCellInterior *vc1 = dynamic_cast<ViewCellInterior *>(mc.GetLeftViewCell());
1100        ViewCellInterior *vc2 = dynamic_cast<ViewCellInterior *>(mc.GetRightViewCell());
1101
1102        ViewCell *leaf1 = mc.GetInitialLeftViewCell();
1103        ViewCell *leaf2 = mc.GetInitialRightViewCell();
1104
1105        //-- first test if shuffling would decrease cost
1106        cost1 = GetCostHeuristics(vc1);
1107        cost2 = GetCostHeuristics(vc2);
1108
1109        const float oldCost = cost1 + cost2;
1110       
1111        float shuffledCost1 = Limits::Infinity;
1112        float shuffledCost2 = Limits::Infinity;
1113
1114        if (leaf1)
1115                shuffledCost1 = EvalShuffleCost(leaf1, vc1, vc2);       
1116        if (leaf2)
1117                shuffledCost2 = EvalShuffleCost(leaf2, vc2, vc1);
1118
1119        // if cost of shuffle is less than old cost => shuffle
1120        if ((oldCost <= shuffledCost1) && (oldCost <= shuffledCost2))
1121                return false;
1122       
1123        if (shuffledCost1 < shuffledCost2)
1124        {
1125                if (leaf1)
1126                        ShuffleLeaf(leaf1, vc1, vc2);
1127                mc.mInitialLeftViewCell = NULL;
1128        }
1129        else
1130        {
1131                if (leaf2)
1132                        ShuffleLeaf(leaf2, vc2, vc1);
1133                mc.mInitialRightViewCell = NULL;
1134        }
1135
1136        return true;
1137}
1138
1139
1140float ViewCellsTree::GetVariance(ViewCell *vc) const
1141{
1142        const int upper = mViewCellsManager->GetMaxPvsSize();
1143        const int lower = mViewCellsManager->GetMinPvsSize();
1144
1145        if (1)
1146        {
1147                const float penalty = EvalPvsPenalty(vc->GetPvs().GetSize(), lower, upper);
1148                return (mAvgRenderCost - penalty) * (mAvgRenderCost - penalty) / (float)mNumActiveViewCells;
1149        }
1150
1151    const float leafCost = GetRenderCost(vc);
1152        return (mExpectedCost - leafCost) * (mExpectedCost - leafCost);
1153}
1154
1155
1156float ViewCellsTree::GetDeviation(ViewCell *vc) const
1157{
1158        const int upper = mViewCellsManager->GetMaxPvsSize();
1159        const int lower = mViewCellsManager->GetMinPvsSize();
1160
1161        if (1)
1162        {
1163                const float penalty = EvalPvsPenalty(vc->GetPvs().GetSize(), lower, upper);
1164                return fabs(mAvgRenderCost - penalty) / (float)mNumActiveViewCells;
1165        }
1166
1167    const float renderCost = GetRenderCost(vc);
1168        return fabs(mExpectedCost - renderCost);
1169}
1170
1171
1172
1173float ViewCellsTree::GetRenderCost(ViewCell *vc) const
1174{
1175        if (mUseAreaForPvs)
1176                return vc->GetPvs().GetSize() * vc->GetArea();
1177
1178        return vc->GetPvs().GetSize() * vc->GetVolume();
1179}
1180
1181
1182float ViewCellsTree::GetCostHeuristics(ViewCell *vc) const
1183{
1184        return GetRenderCost(vc) * mRenderCostWeight +
1185                   GetDeviation(vc) * (1.0f - mRenderCostWeight);
1186}
1187
1188
1189bool ViewCellsTree::ValidateMergeCandidate(MergeCandidate &mc) const
1190{
1191        while (mc.mLeftViewCell->mParent)
1192        {
1193                mc.mLeftViewCell = mc.mLeftViewCell->mParent;
1194        }
1195
1196        while (mc.mRightViewCell->mParent)
1197        {
1198                mc.mRightViewCell = mc.mRightViewCell->mParent;
1199        }
1200
1201        return mc.mLeftViewCell != mc.mRightViewCell;
1202}
1203
1204
1205void ViewCellsTree::EvalMergeCost(MergeCandidate &mc) const
1206{
1207        //-- compute pvs difference
1208        const int newPvs =
1209                ComputeMergedPvsSize(mc.mLeftViewCell->GetPvs(),
1210                                                         mc.mRightViewCell->GetPvs());
1211                       
1212        const float newPenalty =
1213                EvalPvsPenalty(newPvs,
1214                                           mViewCellsManager->GetMinPvsSize(),
1215                                           mViewCellsManager->GetMaxPvsSize());
1216
1217        ViewCell *vc1 = mc.mLeftViewCell;
1218        ViewCell *vc2 = mc.mRightViewCell;
1219
1220        //-- compute ratio of old cost
1221        //   (i.e., added size of left and right view cell times pvs size)
1222        //   to new rendering cost (i.e, size of merged view cell times pvs size)
1223        const float oldCost = GetRenderCost(vc1) + GetRenderCost(vc2);
1224
1225    const float newCost = mUseAreaForPvs ?
1226                (float)newPenalty * (vc1->GetArea() + vc2->GetArea()) :
1227                (float)newPenalty * (vc1->GetVolume() + vc2->GetVolume());
1228
1229
1230        // strong penalty if pvs size too large
1231        if (0 && (newPvs > mViewCellsManager->GetMaxPvsSize()))
1232        {
1233                mc.mRenderCost = 1e20f;
1234        }
1235        else
1236        {
1237                mc.mRenderCost = (newCost - oldCost) /
1238                        mViewCellsManager->GetViewSpaceBox().GetVolume();
1239        }       
1240       
1241
1242        //-- merge cost also takes deviation into account
1243        float newDev, oldDev;
1244
1245        if (1)
1246                newDev = fabs(mAvgRenderCost - newPenalty) / (float)mNumActiveViewCells;
1247        else
1248                newDev = fabs(mExpectedCost - newCost) / (float)mNumActiveViewCells;
1249       
1250        oldDev = GetDeviation(vc1) + GetDeviation(vc2);
1251
1252        // compute deviation increase
1253        mc.mDeviationIncr = newDev - oldDev;
1254       
1255        //Debug << "render cost: " << mc.mRenderCost * mRenderCostWeight << endl;
1256        //Debug << "standard deviation: " << mc.mDeviationIncr * mRenderCostWeight << endl;
1257}
1258
1259void ViewCellsTree::CompressViewCellsPvs()
1260{
1261        if (!mIsCompressed)
1262        {
1263                mIsCompressed = true;
1264                CompressViewCellsPvs(mRoot);
1265        }
1266}
1267
1268void ViewCellsTree::CompressViewCellsPvs(ViewCell *root)
1269{
1270        if (!root->IsLeaf())
1271        {
1272                ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(root);
1273
1274        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1275               
1276                // compress child sets first
1277                for (it = interior->mChildren.begin(); it != it_end; ++ it)
1278                {
1279                        CompressViewCellsPvs(*it);
1280                }
1281
1282                // compress root node
1283                PropagateUpVisibility(interior);
1284        }
1285}
1286
1287
1288void ViewCellsTree::CollectBestViewCellSet(ViewCellContainer &viewCells,
1289                                                                                   const int numViewCells)
1290{
1291        TraversalQueue tqueue;
1292        tqueue.push(mRoot);
1293       
1294        while (!tqueue.empty())
1295        {
1296                ViewCell *vc = tqueue.top();
1297               
1298                // save the view cells if it is a leaf or if enough view cells have already been traversed
1299                // because of the priority queue, this will be the optimal set of v
1300                if (vc->IsLeaf() || ((viewCells.size() + tqueue.size()) >= numViewCells))
1301                {
1302                        // todo: should be done with a function taking the active flag and some
1303                        // time stamp so I don't have to reset view cells, this also means that
1304                        // the leaf view cells can be set active fist
1305                        vc->mIsActive = true;
1306                        viewCells.push_back(vc);
1307                }
1308                else
1309                {       
1310                        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
1311
1312                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1313
1314                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
1315                        {
1316                                tqueue.push(*it);
1317                        }
1318                }
1319
1320                tqueue.pop();
1321        }
1322}
1323       
1324
1325void ViewCellsTree::PropagateUpVisibility(ViewCellInterior *interior)
1326{
1327        Intersectable::NewMail((int)interior->mChildren.size());
1328
1329        ViewCellContainer::const_iterator cit, cit_end = interior->mChildren.end();
1330
1331        ObjectPvsMap::const_iterator oit;
1332
1333        // mail all objects in the leaf sets
1334        // we are interested in the objects which are present in all leaves
1335        // => count how often an object is part of a child set
1336        for (cit = interior->mChildren.begin(); cit != cit_end; ++ cit)
1337        {
1338                ViewCell *vc = *cit;
1339
1340                ObjectPvsMap::const_iterator oit_end = vc->GetPvs().mEntries.end();
1341
1342                for (oit = vc->GetPvs().mEntries.begin(); oit != oit_end; ++ oit)
1343                {
1344                        Intersectable *obj = (*oit).first;
1345                        if ((cit == interior->mChildren.begin()) && !obj->Mailed())
1346                                obj->Mail();
1347                       
1348                        int incm = obj->IncMail();
1349                }
1350        }
1351
1352        interior->GetPvs().mEntries.clear();
1353       
1354       
1355        // only the objects which are present in all leaf pvs
1356        // should remain in the parent pvs
1357        // these are the objects which have been mailed in all children
1358        for (cit = interior->mChildren.begin(); cit != cit_end; ++ cit)
1359        {
1360                ViewCell *vc = *cit;
1361
1362                ObjectPvsMap::const_iterator oit_end = vc->GetPvs().mEntries.end();
1363
1364                for (oit = vc->GetPvs().mEntries.begin(); oit != oit_end; ++ oit)
1365                {               
1366                        if ((*oit).first->Mailed((int)interior->mChildren.size()))
1367                        {       
1368                                interior->GetPvs().AddSample((*oit).first, (*oit).second.mSumPdf);
1369                        }
1370                }
1371        }
1372
1373
1374
1375        // delete all the objects from the leaf sets which were moved to parent pvs
1376        ObjectPvsMap::const_iterator oit_end = interior->GetPvs().mEntries.end();
1377
1378        for (oit = interior->GetPvs().mEntries.begin(); oit != oit_end; ++ oit)
1379        {
1380                for (cit = interior->mChildren.begin(); cit != cit_end; ++ cit)
1381                {
1382                        if (!(*cit)->GetPvs().RemoveSample((*oit).first, Limits::Infinity))
1383                                Debug << "should not come here!" << endl;
1384                }
1385        }
1386
1387        int dummy = interior->GetPvs().GetSize();
1388
1389        for (cit = interior->mChildren.begin(); cit != cit_end; ++ cit)
1390        {
1391                dummy += (*cit)->GetPvs().GetSize();
1392        }
1393
1394}
1395
1396
1397
1398void ViewCellsTree::GetPvs(ViewCell *vc, ObjectPvs &pvs) const
1399{
1400        Intersectable::NewMail();
1401
1402        if (!mIsCompressed)
1403                pvs = vc->GetPvs();
1404
1405        int pvsSize = 0;
1406        ViewCell *root = vc;
1407       
1408        // also add pvs from this view cell to root
1409        while (root->GetParent())
1410        {
1411                root = root->GetParent();
1412                pvs.AddPvs(root->GetPvs());
1413        }
1414
1415        stack<ViewCell *> tstack;
1416        tstack.push(vc);
1417
1418        while (!tstack.empty())
1419        {
1420                vc = tstack.top();
1421                tstack.pop();
1422
1423                pvs.AddPvs(vc->GetPvs());
1424
1425                if (!vc->IsLeaf())
1426                {
1427                        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
1428
1429                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1430
1431                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
1432                        {
1433                                tstack.push(*it);
1434                        }               
1435                }
1436        }
1437}
1438
1439
1440int ViewCellsTree::GetPvsSize(ViewCell *vc) const
1441{
1442        Intersectable::NewMail();
1443
1444        if (!mIsCompressed)
1445                return vc->GetPvs().GetSize();
1446
1447        int pvsSize = 0;
1448        ViewCell *root = vc;
1449       
1450        // also add pvs from this view cell to root
1451        while (root->GetParent())
1452        {
1453                root = root->GetParent();
1454                pvsSize += CountDiffPvs(root);
1455        }
1456
1457        stack<ViewCell *> tstack;
1458        tstack.push(vc);
1459
1460        while (!tstack.empty())
1461        {
1462                vc = tstack.top();
1463                tstack.pop();
1464
1465                pvsSize += CountDiffPvs(vc);
1466
1467                if (!vc->IsLeaf())
1468                {
1469                        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
1470
1471                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1472
1473                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
1474                        {
1475                                tstack.push(*it);
1476                        }               
1477                }
1478        }
1479
1480        return pvsSize; 
1481
1482}
1483
1484
1485float ViewCellsTree::GetMemoryCost(ViewCell *vc) const
1486{
1487        const float entrySize =
1488                sizeof(PvsData<Intersectable *>) + sizeof(Intersectable *);
1489
1490        return (float)GetNumPvsEntries(vc) * entrySize;
1491}
1492
1493
1494int ViewCellsTree::GetNumPvsEntries(ViewCell *vc) const
1495{
1496        int pvsSize = 0;
1497        // only count leaves for uncompressed method for fairness
1498        if (mIsCompressed || vc->IsLeaf())
1499                pvsSize = vc->GetPvs().GetSize();
1500
1501        if (!vc->IsLeaf())
1502        {
1503                ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
1504
1505                ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1506
1507                for (it = interior->mChildren.begin(); it != it_end; ++ it)
1508                {
1509                        pvsSize += GetNumPvsEntries(*it);
1510                }
1511        }
1512
1513        return pvsSize;         
1514}
1515
1516
1517bool ViewCellsTree::IsCompressed() const
1518{
1519        return mIsCompressed;
1520}
1521
1522
1523ViewCell *ViewCellsTree::GetActiveViewCell(ViewCell *vc) const
1524{
1525        while (vc->GetParent() && !vc->mIsActive)
1526        {
1527                vc = vc->GetParent();
1528        }
1529
1530        return vc;
1531}
1532
1533
1534
1535void  ViewCellsTree::UpdateViewCellsStats(ViewCell *vc, ViewCellsStatistics &vcStat)
1536{
1537        ++ vcStat.viewCells;
1538               
1539        const int pvsSize = GetPvsSize(vc);
1540
1541        vcStat.pvs += pvsSize;
1542
1543        if (pvsSize == 0)
1544                ++ vcStat.emptyPvs;
1545
1546        if (pvsSize > vcStat.maxPvs)
1547                vcStat.maxPvs = pvsSize;
1548
1549        if (pvsSize < vcStat.minPvs)
1550                vcStat.minPvs = pvsSize;
1551
1552        if (!vc->GetValid())
1553                ++ vcStat.invalid;
1554}
1555
1556
1557
1558/**************************************************************************/
1559/*                     MergeCandidate implementation                      */
1560/**************************************************************************/
1561
1562
1563MergeCandidate::MergeCandidate(ViewCell *l, ViewCell *r):
1564mRenderCost(0),
1565mDeviationIncr(0),
1566mLeftViewCell(l),
1567mRightViewCell(r),
1568mInitialLeftViewCell(l),
1569mInitialRightViewCell(r)
1570{
1571        //EvalMergeCost();
1572}
1573
1574
1575void MergeCandidate::SetRightViewCell(ViewCell *v)
1576{
1577        mRightViewCell = v;
1578}
1579
1580
1581void MergeCandidate::SetLeftViewCell(ViewCell *v)
1582{
1583        mLeftViewCell = v;
1584}
1585
1586
1587ViewCell *MergeCandidate::GetRightViewCell() const
1588{
1589        return mRightViewCell;
1590}
1591
1592
1593ViewCell *MergeCandidate::GetLeftViewCell() const
1594{
1595        return mLeftViewCell;
1596}
1597
1598
1599ViewCell *MergeCandidate::GetInitialRightViewCell() const
1600{
1601        return mInitialRightViewCell;
1602}
1603
1604
1605ViewCell *MergeCandidate::GetInitialLeftViewCell() const
1606{
1607        return mInitialLeftViewCell;
1608}
1609
1610
1611bool MergeCandidate::IsValid() const
1612{
1613        return !(mLeftViewCell->mParent || mRightViewCell->mParent);
1614}
1615
1616
1617float MergeCandidate::GetRenderCost() const
1618{
1619        return mRenderCost;
1620}
1621
1622
1623float MergeCandidate::GetDeviationIncr() const
1624{
1625        return mDeviationIncr;
1626}
1627
1628
1629float MergeCandidate::GetMergeCost() const
1630{
1631        return mRenderCost * sRenderCostWeight +
1632                   mDeviationIncr * (1.0f - sRenderCostWeight);
1633}
1634
1635
1636
1637/************************************************************************/
1638/*                    MergeStatistics implementation                    */
1639/************************************************************************/
1640
1641
1642void MergeStatistics::Print(ostream &app) const
1643{
1644        app << "===== Merge statistics ===============\n";
1645
1646        app << setprecision(4);
1647
1648        app << "#N_CTIME ( Overall time [s] )\n" << Time() << " \n";
1649
1650        app << "#N_CCTIME ( Collect candidates time [s] )\n" << collectTime * 1e-3f << " \n";
1651
1652        app << "#N_MTIME ( Merge time [s] )\n" << mergeTime * 1e-3f << " \n";
1653
1654        app << "#N_NODES ( Number of nodes before merge )\n" << nodes << "\n";
1655
1656        app << "#N_CANDIDATES ( Number of merge candidates )\n" << candidates << "\n";
1657
1658        app << "#N_MERGEDSIBLINGS ( Number of merged siblings )\n" << siblings << "\n";
1659
1660        app << "#OVERALLCOST ( overall merge cost )\n" << overallCost << "\n";
1661
1662        app << "#N_MERGEDNODES ( Number of merged nodes )\n" << merged << "\n";
1663
1664        app << "#MAX_TREEDIST ( Maximal distance in tree of merged leaves )\n" << maxTreeDist << "\n";
1665
1666        app << "#AVG_TREEDIST ( Average distance in tree of merged leaves )\n" << AvgTreeDist() << "\n";
1667
1668        app << "#EXPECTEDCOST ( expected render cost )\n" << expectedRenderCost << "\n";
1669
1670        app << "#DEVIATION ( deviation )\n" << deviation << "\n";
1671
1672        app << "#HEURISTICS ( heuristics )\n" << heuristics << "\n";
1673       
1674
1675        app << "===== END OF BspTree statistics ==========\n";
1676}
Note: See TracBrowser for help on using the repository browser.