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

Revision 587, 39.0 KB checked in by mattausch, 18 years ago (diff)

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