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

Revision 1233, 56.4 KB checked in by mattausch, 18 years ago (diff)
Line 
1#include <time.h>
2#include <iomanip>
3#include <stack>
4
5
6#include "ViewCell.h"
7#include "Mesh.h"
8#include "Intersectable.h"
9#include "KdTree.h"
10#include "Triangle3.h"
11#include "common.h"
12#include "Environment.h"
13#include "ViewCellsManager.h"
14#include "Exporter.h"
15
16
17namespace GtpVisibilityPreprocessor {
18
19
20
21template <typename T> class myless
22{
23public:
24        bool operator() (T v1, T v2) const
25        {
26                return (v1->GetMergeCost() < v2->GetMergeCost());
27        }
28};
29
30
31typedef priority_queue<ViewCell *, vector<ViewCell *>,
32                                           myless<vector<ViewCell *>::value_type> > TraversalQueue;
33
34int ViewCell::sMailId = 0;//21843194198;
35int ViewCell::sReservedMailboxes = 1;
36
37
38float MergeCandidate::sRenderCostWeight = 0;
39
40
41// pvs penalty can be different from pvs size
42inline static float EvalPvsPenalty(const int pvs,
43                                                                   const int lower,
44                                                                   const int upper)
45{
46        // clamp to minmax values
47        if (pvs < lower)
48                return (float)lower;
49        if (pvs > upper)
50                return (float)upper;
51
52        return (float)pvs;
53}
54
55/// Counts differences between pvss.
56inline int CountDiffPvs(ViewCell *vc)
57{
58        int count = 0;
59
60        ObjectPvsMap::const_iterator it, it_end = vc->GetPvs().mEntries.end();
61        for (it = vc->GetPvs().mEntries.begin(); it != it_end; ++ it)
62        {
63                if (!(*it).first->Mailed())
64                {
65                        (*it).first->Mail();
66                        ++ count;
67                }
68        }
69
70        return count;
71}
72
73
74/// Fast computation of merged pvs size
75static int ComputeMergedPvsSize(const ObjectPvs &pvs1, const ObjectPvs &pvs2)
76{
77        // add first pvs
78        int pvs = pvs1.GetSize();
79
80        ObjectPvsMap::const_iterator it, it_end =  pvs1.mEntries.end();
81
82        Intersectable::NewMail();
83
84        // mail all objects in first pvs
85        for (it = pvs1.mEntries.begin(); it != it_end; ++ it)
86        {
87                (*it).first->Mail();
88        }
89
90        it_end = pvs2.mEntries.end();
91
92        // look if the entries are also in second pvs
93        for (it = pvs2.mEntries.begin(); it != it_end; ++ it)
94        {
95                Intersectable *obj = (*it).first;
96                if (!obj->Mailed())
97                        ++ pvs;
98        }
99
100        return pvs;
101}
102
103
104ViewCell::ViewCell():
105MeshInstance(NULL),
106mPiercingRays(0),
107mArea(-1),
108mVolume(-1),
109mValid(true),
110mParent(NULL),
111mMergeCost(0),
112mPvsSize(0),
113mEntriesInPvs(0),
114mPvsSizeValid(false)
115{
116}
117
118ViewCell::ViewCell(Mesh *mesh):
119MeshInstance(mesh),
120mPiercingRays(0),
121mArea(-1),
122mVolume(-1),
123mValid(true),
124mParent(NULL),
125mMergeCost(0),
126mPvsSize(0),
127mPvsSizeValid(false)
128{
129}
130
131
132const ObjectPvs &ViewCell::GetPvs() const
133{
134        return mPvs;
135}
136
137
138ObjectPvs &ViewCell::GetPvs()
139{
140        return mPvs;
141}
142
143
144void ViewCell::SetPvs(const ObjectPvs &pvs)
145{
146        mPvs = pvs;
147}
148
149
150int ViewCell::Type() const
151{
152        return VIEW_CELL;
153}
154
155
156float ViewCell::GetVolume() const
157{
158        return mVolume;
159}
160
161
162void ViewCell::SetVolume(float volume)
163{
164        mVolume = volume;
165}
166
167
168void ViewCell::SetMesh(Mesh *mesh)
169{
170        mMesh = mesh;
171}
172
173
174float ViewCell::GetArea() const
175{
176        return mArea;
177}
178
179
180void ViewCell::SetArea(float area)
181{
182        mArea = area;
183}
184
185
186void ViewCell::SetColor(const RgbColor &color)
187{
188        mColor = color;
189}
190
191
192RgbColor ViewCell::GetColor() const
193{
194        return mColor;
195}
196
197
198void ViewCell::SetValid(const bool valid)
199{
200        mValid = valid;
201}
202
203
204bool ViewCell::GetValid() const
205{
206        return mValid;
207}
208
209
210void ViewCell::SetParent(ViewCellInterior *parent)
211{
212        mParent = parent;
213}
214
215
216bool ViewCell::IsRoot() const
217{
218        return !mParent;
219}
220
221
222ViewCellInterior *ViewCell::GetParent() const
223{
224        return mParent;
225}
226
227
228void ViewCell::SetMergeCost(const float mergeCost)
229{
230        mMergeCost = mergeCost;
231}
232
233
234float ViewCell::GetRenderCost() const
235{
236        //return (float)mPvs.GetSize() * GetVolume();
237        return (float)mPvsSize * GetVolume();
238}
239
240
241float ViewCell::GetMergeCost() const
242{
243        return mMergeCost;
244}
245
246
247bool ViewCell::AddPvsSample(Intersectable *sample,
248                                                        const float pdf,
249                                                        float &contribution)
250{
251        const bool result = mPvs.AddSample(sample, pdf, contribution);
252       
253        mPvsSizeValid = false; // have to recompute pvs size
254
255        return result;
256}
257
258
259
260/************************************************************************/
261/*                class ViewCellInterior implementation                 */
262/************************************************************************/
263
264
265ViewCellInterior::ViewCellInterior()
266{
267}
268
269
270ViewCellInterior::~ViewCellInterior()
271{
272        ViewCellContainer::const_iterator it, it_end = mChildren.end();
273
274        for (it = mChildren.begin(); it != it_end; ++ it)
275                delete (*it);
276}
277
278
279ViewCellInterior::ViewCellInterior(Mesh *mesh):
280ViewCell(mesh)
281{
282}
283
284
285bool ViewCellInterior::IsLeaf() const
286{
287        return false;
288}
289
290
291void ViewCellInterior::SetupChildLink(ViewCell *vc)
292{
293    mChildren.push_back(vc);
294    vc->SetParent(this);
295}
296
297
298void ViewCellInterior::RemoveChildLink(ViewCell *l)
299{
300        // erase leaf from old view cell
301        ViewCellContainer::iterator it = mChildren.begin();
302
303        for (; (*it) != l; ++ it);
304        if (it == mChildren.end())
305                Debug << "error" << endl;
306        else
307                mChildren.erase(it);
308}
309
310
311/************************************************************************/
312/*                class ViewCellsStatistics implementation              */
313/************************************************************************/
314
315
316
317
318void ViewCellsStatistics::Print(ostream &app) const
319{
320        app << "=========== View Cells Statistics ===============\n";
321
322        app << setprecision(4);
323
324        //app << "#N_CTIME  ( Construction time [s] )\n" << Time() << " \n";
325
326        app << "#N_OVERALLPVS ( objects in PVS )\n" << pvsSize << endl;
327
328        app << "#N_PMAXPVS ( largest PVS )\n" << maxPvs << endl;
329
330        app << "#N_PMINPVS ( smallest PVS )\n" << minPvs << endl;
331
332        app << "#N_PAVGPVS ( average PVS )\n" << AvgPvs() << endl;
333
334        app << "#N_PEMPTYPVS ( view cells with empty PVS )\n" << emptyPvs << endl;
335
336        app << "#N_VIEWCELLS ( number of view cells)\n" << viewCells << endl;
337
338        app << "#N_AVGLEAVES (average number of leaves per view cell )\n" << AvgLeaves() << endl;
339
340        app << "#N_MAXLEAVES ( maximal number of leaves per view cell )\n" << maxLeaves << endl;
341       
342        app << "#N_INVALID ( number of invalid view cells )\n" << invalid << endl;
343
344        app << "========== End of View Cells Statistics ==========\n";
345}
346
347
348/*************************************************************************/
349/*                    class ViewCellsTree implementation                 */
350/*************************************************************************/
351
352
353ViewCellsTree::ViewCellsTree(ViewCellsManager *vcm):
354mRoot(NULL),
355mUseAreaForPvs(false),
356mViewCellsManager(vcm),
357#if 0
358mViewCellsStorage(PVS_IN_INTERIORS)
359#else
360mViewCellsStorage(PVS_IN_LEAVES)
361#endif
362{
363        Environment::GetSingleton()->GetBoolValue("ViewCells.Visualization.exportMergedViewCells", mExportMergedViewCells);
364        Environment::GetSingleton()->GetFloatValue("ViewCells.maxStaticMemory", mMaxMemory);
365
366        //-- merge options
367        Environment::GetSingleton()->GetFloatValue("ViewCells.PostProcess.renderCostWeight", mRenderCostWeight);
368        Environment::GetSingleton()->GetIntValue("ViewCells.PostProcess.minViewCells", mMergeMinViewCells);
369        Environment::GetSingleton()->GetFloatValue("ViewCells.PostProcess.maxCostRatio", mMergeMaxCostRatio);
370        Environment::GetSingleton()->GetBoolValue("ViewCells.PostProcess.refine", mRefineViewCells);   
371
372        Environment::GetSingleton()->GetIntValue("ViewCells.PostProcess.maxMergesPerPass", mMaxMergesPerPass);
373        Environment::GetSingleton()->GetFloatValue("ViewCells.PostProcess.avgCostMaxDeviation", mAvgCostMaxDeviation);
374
375        Debug << "============= view cell tree options ================\n";
376        Debug << "minimum view cells: " << mMergeMinViewCells << endl;
377        Debug << "max cost ratio: " << mMergeMaxCostRatio << endl;
378        Debug << "max memory: " << mMaxMemory << endl;
379        Debug << "refining view cells: " << mRefineViewCells << endl;
380        Debug << "=========== end view cell tree options ===============\n";
381
382        MergeCandidate::sRenderCostWeight = mRenderCostWeight;
383}
384
385
386// return memory usage in MB
387float ViewCellsTree::GetMemUsage() const
388{
389        // TODO
390        return 0;
391                /*(sizeof(ViewCellsTree) +
392                 mBspStats.Leaves() * sizeof(BspLeaf) +
393                 mBspStats.Interior() * sizeof(BspInterior) +
394                 mBspStats.accumRays * sizeof(RayInfo)) / (1024.0f * 1024.0f);*/
395}
396
397
398int ViewCellsTree::GetNumInitialViewCells(ViewCell *vc) const
399{
400        int vcSize = 0;
401
402        stack<ViewCell *> tstack;
403
404        tstack.push(vc);
405
406        while (!tstack.empty())
407        {
408                ViewCell *vc = tstack.top();
409                tstack.pop();
410
411                if (vc->IsLeaf())
412                {
413                        ++ vcSize;
414                }
415                else
416                {
417                        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
418
419                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
420                       
421                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
422                        {
423                                tstack.push(*it);
424                        }
425                       
426                }
427        }
428
429        return vcSize;
430}
431
432
433void ViewCellsTree::CollectLeaves(ViewCell *vc, ViewCellContainer &leaves) const
434{
435        stack<ViewCell *> tstack;
436
437        tstack.push(vc);
438
439        while (!tstack.empty())
440        {
441                ViewCell *vc = tstack.top();
442                tstack.pop();
443
444                if (vc->IsLeaf())
445                {
446                        leaves.push_back(vc);
447                }
448                else
449                {
450                        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
451                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
452
453                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
454                        {
455                                tstack.push(*it);
456                        }
457                       
458                }
459        }
460}
461
462
463ViewCellsTree::~ViewCellsTree()
464{
465        DEL_PTR(mRoot);
466}
467
468
469int ViewCellsTree::ConstructMergeTree(const VssRayContainer &rays,
470                                                                          const ObjectContainer &objects)
471{
472        mNumActiveViewCells = (int)mViewCellsManager->GetViewCells().size();
473
474        float variance = 0;
475        int totalPvs = 0;
476        float totalRenderCost = 0;
477
478        //-- compute statistics values of initial view cells
479        mViewCellsManager->EvaluateRenderStatistics(totalRenderCost,
480                                                                                                mExpectedCost,
481                                                                                                mDeviation,
482                                                                                                variance,
483                                                                                                totalPvs,
484                                                                                                mAvgRenderCost);
485
486
487        //-- fill merge queue
488        vector<MergeCandidate> candidates;
489
490        mViewCellsManager->CollectMergeCandidates(rays, candidates);
491
492        while(!candidates.empty())
493        {
494                MergeCandidate mc = candidates.back();
495                candidates.pop_back();
496                EvalMergeCost(mc);
497                mMergeQueue.push(mc);
498        }
499
500        Debug << "************************* merge ***********************************" << endl; 
501        Debug << "deviation: " << mDeviation << endl;
502        Debug << "avg render cost: " << mAvgRenderCost << endl;
503        Debug << "expected cost: " << mExpectedCost << endl;
504
505
506        ViewCellsManager::PvsStatistics pvsStats;
507        mViewCellsManager->GetPvsStatistics(pvsStats);
508
509        //static float expectedValue = pvsStats.avgPvs;
510       
511        //-- the current view cells are kept in this container
512        //-- we start with the current view cells from the view cell manager.
513        //-- The active view cells will change with subsequent merges
514       
515        // todo: should rather take initial view cells
516    ViewCellContainer &activeViewCells = mViewCellsManager->GetViewCells();
517       
518       
519        ViewCell::NewMail();
520
521        MergeStatistics mergeStats;
522        mergeStats.Start();
523       
524        long startTime = GetTime();
525
526        mergeStats.collectTime = TimeDiff(startTime, GetTime());
527        mergeStats.candidates = (int)mMergeQueue.size();
528        startTime = GetTime();
529
530        // frequency stats are updated
531        const int statsOut = 500;
532       
533        // passes are needed for statistics, because we don't want to record
534        // every merge
535        int pass = 0;
536        int mergedPerPass = 0;
537        float realExpectedCost = mExpectedCost;
538        float realAvgRenderCost = mAvgRenderCost;
539        int realNumActiveViewCells = mNumActiveViewCells;
540       
541        // maximal ratio of old expected render cost to expected render
542        // when the the render queue has to be reset.
543        int numMergedViewCells = 0;
544               
545
546        cout << "actual merge starts now ... " << endl;
547
548        //-- use priority queue to merge leaf pairs
549
550        while (!mMergeQueue.empty())
551        {
552                //-- reset merge queue if the ratio of current expected cost / real expected cost
553                //   too small or after a given number of merges
554                if ((mergedPerPass > mMaxMergesPerPass) ||
555                        (mAvgCostMaxDeviation > mAvgRenderCost / realAvgRenderCost))
556                {
557                        Debug << "************ reset queue *****************\n"
558                                  << "ratios: " << mAvgCostMaxDeviation
559                                  << " real avg render cost " << realAvgRenderCost << " average render cost " << mAvgRenderCost
560                                  << " merged per pass : " << mergedPerPass << " of maximal " << mMaxMergesPerPass << endl;
561
562                        Debug << "Values before reset: " 
563                                  << " erc: " << mExpectedCost
564                                  << " avgrc: " << mAvgRenderCost
565                                  << " dev: " << mDeviation << endl;
566       
567                        // adjust render cost
568                        ++ pass;
569
570                        mergedPerPass = 0;
571                        mExpectedCost = realExpectedCost;
572                        mAvgRenderCost = realAvgRenderCost;
573                        mNumActiveViewCells = realNumActiveViewCells;
574                       
575                        const int numMergedViewCells = UpdateActiveViewCells(activeViewCells);
576               
577                       
578                        //-- resets / refines the view cells
579                        //-- priorities are recomputed
580                        //-- the candidates are put back into merge queue
581                        if (mRefineViewCells)
582                                RefineViewCells(rays, objects);
583                        else
584                                ResetMergeQueue();
585
586                        Debug << "Values after reset: " 
587                                  << " erc: " << mExpectedCost
588                                  << " avg: " << mAvgRenderCost
589                                  << " dev: " << mDeviation << endl;
590
591                        if (mExportMergedViewCells)
592                        {
593                                ExportMergedViewCells(activeViewCells, objects, numMergedViewCells);
594                        }
595                }
596
597
598                MergeCandidate mc = mMergeQueue.top();
599                mMergeQueue.pop();
600       
601                // both view cells equal because of previous merges
602                // NOTE: do I really still need this? probably cannot happen!!
603                if (mc.mLeftViewCell == mc.mRightViewCell)
604                        continue;
605
606                if (mc.IsValid())
607                {
608                        ViewCell::NewMail();
609
610                        //-- update statistical values
611                        -- realNumActiveViewCells;
612                        ++ mergeStats.merged;
613                        ++ mergedPerPass;
614
615                        const float renderCostIncr = mc.GetRenderCost();
616                        const float mergeCostIncr = mc.GetMergeCost();
617
618                        totalRenderCost += renderCostIncr;
619                        mDeviation += mc.GetDeviationIncr();
620
621                                               
622                        //-- merge the view cells of leaf1 and leaf2
623                        int pvsDiff;
624                        ViewCellInterior *mergedVc =
625                                MergeViewCells(mc.mLeftViewCell, mc.mRightViewCell, pvsDiff);
626                       
627
628                        // total render cost and deviation has changed
629                        // real expected cost will be larger than expected cost used for the
630                        // cost heuristics, but cannot recompute costs on each increase of the
631                        // expected cost
632                        totalPvs += pvsDiff;
633                        realExpectedCost = totalRenderCost / (float)realNumActiveViewCells;
634                        realAvgRenderCost = (float)totalPvs / (float)realNumActiveViewCells;
635       
636                        // set merge cost to this node for priority traversal
637                        mergedVc->SetMergeCost(totalRenderCost);
638                       
639                        // HACK
640                        //mergedVc->SetMergeCost(1.0f / (float)realNumActiveViewCells);
641
642                        // check if "siblings (back and front node of the same parent)
643                        if (0 && mViewCellsManager->EqualToSpatialNode(mergedVc))
644                                ++ mergeStats.siblings;
645                        // set the coŽst for rendering a view cell
646                        mergedVc->SetCost(realExpectedCost);
647
648                        if ((mergeStats.merged % statsOut) == 0)
649                                cout << "merged " << mergeStats.merged << " view cells" << endl;
650
651                }
652                else
653                {
654                        // merge candidate not valid, because one of the leaves was already
655                        // merged with another one => validate and reinsert into queue
656                        if (ValidateMergeCandidate(mc))
657                        {
658                                EvalMergeCost(mc);
659                                mMergeQueue.push(mc);
660                        }
661                }
662               
663        }
664
665        // adjust stats and reset queue one final time
666        mExpectedCost = realExpectedCost;
667        mAvgRenderCost = realAvgRenderCost;
668        mNumActiveViewCells = realNumActiveViewCells;
669
670        UpdateActiveViewCells(activeViewCells);
671
672        // refine view cells and reset costs
673        if (mRefineViewCells)
674                RefineViewCells(rays, objects);
675        else
676                ResetMergeQueue();
677
678
679        // create a root node if the merge was not done till root level,
680        // else take the single node as new root
681        if ((int)activeViewCells.size() > 1)
682        {
683                Debug << "creating root of view cell hierarchy for "
684                          << (int)activeViewCells.size() << " view cells" << endl;
685               
686                ViewCellInterior *root = mViewCellsManager->MergeViewCells(activeViewCells);
687       
688                ViewCellContainer::const_iterator it, it_end = root->mChildren.end();
689
690                for (it = root->mChildren.begin(); it != it_end; ++ it)
691                        (*it)->SetParent(root);
692       
693                root->SetMergeCost(totalRenderCost);
694                // $$JB keep this 0 temporarilly
695                root->SetCost(0.0f);
696
697                mRoot = root;
698        }
699        // normal case
700        else if (!activeViewCells.empty())
701        {
702                Debug << "setting root of the merge history" << endl;
703                mRoot = activeViewCells[0];
704        }
705        else
706        {
707                Debug << "big error, root is NULL" << endl;
708        }
709       
710        //-- empty merge queue just in case
711        while (!mMergeQueue.empty())
712        {
713                mMergeQueue.pop();
714        }
715
716        // test if voluje is equal
717        Debug << "volume of the root view cell: " << mRoot->GetVolume() << " " << mViewCellsManager->GetViewSpaceBox().GetVolume() << endl;
718
719        //hack!!
720        //mRoot->GetPvs().Clear();
721       
722        // TODO: delete because makes no sense here
723        mergeStats.expectedRenderCost = realExpectedCost;
724        mergeStats.deviation = mDeviation;
725
726        // we want to optimize this heuristics
727        mergeStats.heuristics =
728                mDeviation * (1.0f - mRenderCostWeight) +
729                mExpectedCost * mRenderCostWeight;
730
731        mergeStats.mergeTime = TimeDiff(startTime, GetTime());
732        mergeStats.Stop();
733        Debug << mergeStats << endl << endl;
734
735        // assign colors for the view cells so that at least one is always consistent
736        AssignRandomColors();
737
738        //TODO: should return sample contributions?
739        return mergeStats.merged;
740}
741
742
743ViewCell *ViewCellsTree::GetRoot() const
744{
745        return mRoot;
746}
747
748
749void ViewCellsTree::ResetMergeQueue()
750{
751        cout << "reset merge queue ... ";
752       
753        vector<MergeCandidate> buf;
754        buf.reserve(mMergeQueue.size());
755                       
756       
757        // store merge candidates in intermediate buffer
758        while (!mMergeQueue.empty())
759        {
760                MergeCandidate mc = mMergeQueue.top();
761                mMergeQueue.pop();
762               
763                // recalculate cost
764                if (ValidateMergeCandidate(mc))
765                {
766                        EvalMergeCost(mc);
767                        buf.push_back(mc);                             
768                }
769        }
770
771        vector<MergeCandidate>::const_iterator bit, bit_end = buf.end();
772
773        // reinsert back into queue
774        for (bit = buf.begin(); bit != bit_end; ++ bit)
775        {     
776                mMergeQueue.push(*bit);
777        }
778
779        cout << "finished" << endl;
780}
781
782
783float ViewCellsTree::ComputeMergedPvsCost(const ObjectPvs &pvs1,
784                                                                                  const ObjectPvs &pvs2) const
785{
786        // computes render cost of merge
787        float renderCost = 0;
788
789        // compute new pvs size
790        ObjectPvsMap::const_iterator it, it_end =  pvs1.mEntries.end();
791
792        Intersectable::NewMail();
793
794        // first mail all objects in first pvs
795        for (it = pvs1.mEntries.begin(); it != it_end; ++ it)
796        {
797                Intersectable *obj = (*it).first;
798
799                obj->Mail();
800                renderCost += mViewCellsManager->EvalRenderCost(obj);
801        }
802
803        it_end = pvs2.mEntries.end();
804
805       
806        for (it = pvs2.mEntries.begin(); it != it_end; ++ it)
807        {
808                Intersectable *obj = (*it).first;
809
810                // test if object already considered   
811                if (!obj->Mailed())
812                {
813                        renderCost += mViewCellsManager->EvalRenderCost(obj);
814                }
815        }
816
817        return renderCost;
818}
819
820
821int ViewCellsTree::UpdateActiveViewCells(ViewCellContainer &viewCells)
822{
823        int numMergedViewCells = 0;
824
825        Debug << "updating active vc: " << (int)viewCells.size() << endl;
826       
827        // find all already merged view cells and remove them from the
828        // container view cells
829               
830        // sort out all view cells which are not active anymore, i.e., they
831        // were already part of a merge
832        int i = 0;
833
834        ViewCell::NewMail();
835
836        while (1)
837        {
838                // remove all merged view cells from end of the vector
839                while (!viewCells.empty() && (viewCells.back()->GetParent()))
840                {
841                        viewCells.pop_back();
842                }
843
844                // all merged view cells have been found
845                if (i >= (int)viewCells.size())
846                        break;
847
848                // already merged this view cell, put it to end of vector
849                if (viewCells[i]->GetParent())
850                        swap(viewCells[i], viewCells.back());
851               
852                // mail view cell that it has not been merged
853                viewCells[i]->Mail();
854
855                // increase loop counter
856                ++ i;
857        }
858
859
860        // add new view cells to container only if they don't have been
861        // merged in the mean time
862        ViewCellContainer::const_iterator ait, ait_end = mMergedViewCells.end();
863
864        for (ait = mMergedViewCells.begin(); ait != ait_end; ++ ait)
865        {
866                ViewCell *vc = mMergedViewCells.back();
867                if (!vc->GetParent() && !vc->Mailed())
868                {
869                        vc->Mail();
870                        viewCells.push_back(vc);
871                        ++ numMergedViewCells;
872                }
873        }
874
875        // dispose old merged view cells
876        mMergedViewCells.clear();
877
878        // update standard deviation
879        ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
880       
881        mDeviation = 0;
882
883        for (vit = viewCells.begin(); vit != vit_end; ++ vit)
884        {
885                const int lower = mViewCellsManager->GetMinPvsSize();
886                const int upper = mViewCellsManager->GetMaxPvsSize();
887
888                const float penalty = EvalPvsPenalty((*vit)->GetPvs().CountObjectsInPvs(), lower, upper);
889               
890                mDeviation += fabs(mAvgRenderCost - penalty);
891        }
892
893        mDeviation /= (float)viewCells.size();
894       
895        return numMergedViewCells;
896}
897
898
899void ViewCellsTree::ExportMergedViewCells(ViewCellContainer &viewCells,
900                                                                                  const ObjectContainer &objects,
901                                                                                  const int numMergedViewCells)
902{
903       
904
905        char s[64];
906
907        sprintf(s, "merged_viewcells%07d.x3d", (int)viewCells.size());
908        Exporter *exporter = Exporter::GetExporter(s);
909
910        if (exporter)
911        {
912                cout << "exporting " << (int)viewCells.size() << " merged view cells ... ";
913                exporter->ExportGeometry(objects);
914                //Debug << "vc size " << (int)viewCells.size() << " merge queue size: " << (int)mMergeQueue.size() << endl;
915                ViewCellContainer::const_iterator it, it_end = viewCells.end();
916
917                int i = 0;
918                for (it = viewCells.begin(); it != it_end; ++ it)
919                {
920                        Material m;
921                        // assign special material to new view cells
922                        // new view cells are on the back of container
923                        if (i ++ >= (viewCells.size() - numMergedViewCells))
924                        {
925                                //m = RandomMaterial();
926                                m.mDiffuseColor.r = RandomValue(0.5f, 1.0f);
927                                m.mDiffuseColor.g = RandomValue(0.5f, 1.0f);
928                                m.mDiffuseColor.b = RandomValue(0.5f, 1.0f);
929                        }
930                        else
931                        {
932                                float col = RandomValue(0.1f, 0.4f);
933                                m.mDiffuseColor.r = col;
934                                m.mDiffuseColor.g = col;
935                                m.mDiffuseColor.b = col;
936                        }
937
938                        exporter->SetForcedMaterial(m);
939                        mViewCellsManager->ExportViewCellGeometry(exporter, *it);
940                }
941                delete exporter;
942                cout << "finished" << endl;
943        }
944}
945
946
947// TODO: should be done in view cells manager
948ViewCellInterior *ViewCellsTree::MergeViewCells(ViewCell *left,
949                                                                                                ViewCell *right,
950                                                                                                int &pvsDiff) //const
951{
952        // create merged view cell
953        ViewCellInterior *vc =
954                mViewCellsManager->MergeViewCells(left, right);
955
956        // if merge was unsuccessful
957        if (!vc) return NULL;
958
959        // set to the new parent view cell
960        left->SetParent(vc);
961        right->SetParent(vc);
962
963       
964        if (mUseAreaForPvs)
965        {
966                // set new area of view cell
967                // not not correct, but costly to compute real area!!
968                vc->SetArea(left->GetArea() + right->GetArea());
969        }
970        else
971        {       // set new volume of view cell
972                vc->SetVolume(left->GetVolume() + right->GetVolume());
973        }
974
975       
976        // important so other merge candidates sharing this view cell
977        // are notified that the merge cost must be updated!!
978        vc->Mail();
979
980        const int pvs1 = left->GetPvs().CountObjectsInPvs();
981        const int pvs2 = right->GetPvs().CountObjectsInPvs();
982
983
984        // the new view cells are stored in this container
985        mMergedViewCells.push_back(vc);
986
987        pvsDiff = vc->GetPvs().CountObjectsInPvs() - pvs1 - pvs2;
988
989
990        // don't store pvs in interior cells, just a scalar
991        if (mViewCellsStorage == PVS_IN_LEAVES)
992        {
993                // set scalars
994                mViewCellsManager->UpdateScalarPvsSize(left,
995                        left->GetPvs().CountObjectsInPvs(),
996                        left->GetPvs().GetSize());
997                       
998                // remove pvs, we don't store interior pvss
999                if (!left->IsLeaf())
1000                {
1001                        left->GetPvs().Clear();
1002                }
1003
1004                // set scalars
1005                mViewCellsManager->UpdateScalarPvsSize(right,
1006                        right->GetPvs().CountObjectsInPvs(),
1007                        right->GetPvs().GetSize());
1008
1009                right->mPvsSizeValid = true;
1010               
1011                // remove pvs, we don't store interior pvss
1012                if (!right->IsLeaf())
1013                {
1014                        right->GetPvs().Clear();
1015                }
1016        }
1017
1018        return vc;
1019}
1020
1021
1022int ViewCellsTree::RefineViewCells(const VssRayContainer &rays,
1023                                                                   const ObjectContainer &objects)
1024{
1025        Debug << "refining " << (int)mMergeQueue.size() << " candidates " << endl;
1026
1027        // intermediate buffer for shuffled view cells
1028        vector<MergeCandidate> buf;
1029        buf.reserve(mMergeQueue.size());
1030                       
1031        // Use priority queue of remaining leaf pairs
1032        // The candidates either share the same view cells or
1033        // are border leaves which share a boundary.
1034        // We test if they can be shuffled, i.e.,
1035        // either one leaf is made part of one view cell or the other
1036        // leaf is made part of the other view cell. It is tested if the
1037        // remaining view cells are "better" than the old ones.
1038       
1039        const int numPasses = 3;
1040        int pass = 0;
1041        int passShuffled = 0;
1042        int shuffled = 0;
1043        int shuffledViewCells = 0;
1044
1045        ViewCell::NewMail();
1046       
1047        while (!mMergeQueue.empty())
1048        {
1049                MergeCandidate mc = mMergeQueue.top();
1050                mMergeQueue.pop();
1051
1052                // both view cells equal or already shuffled
1053                if ((mc.GetLeftViewCell() == mc.GetRightViewCell()) ||
1054                        mc.GetLeftViewCell()->IsLeaf() || mc.GetRightViewCell()->IsLeaf())
1055                {                       
1056                        continue;
1057                }
1058
1059                // candidate for shuffling
1060                const bool wasShuffled = ShuffleLeaves(mc);
1061               
1062                // shuffled or put into other queue for further refine
1063                if (wasShuffled)
1064                {
1065                        ++ passShuffled;
1066
1067                        if (!mc.GetLeftViewCell()->Mailed())
1068                        {
1069                                mc.GetLeftViewCell()->Mail();
1070                                ++ shuffledViewCells;
1071                        }
1072                        if (!mc.GetRightViewCell()->Mailed())
1073                        {
1074                                mc.GetRightViewCell()->Mail();
1075                                ++ shuffledViewCells;
1076                        }
1077                }
1078
1079                // put back into intermediate vector
1080                buf.push_back(mc);
1081        }
1082
1083
1084        //-- in the end, the candidates must be in the mergequeue again
1085        //   with the correct cost
1086
1087        cout << "reset merge queue ... ";
1088       
1089       
1090        vector<MergeCandidate>::const_iterator bit, bit_end = buf.end();
1091       
1092        for (bit = buf.begin(); bit != bit_end; ++ bit)
1093        {   
1094                MergeCandidate mc = *bit;
1095                // recalculate cost
1096                if (ValidateMergeCandidate(mc))
1097                {
1098                        EvalMergeCost(mc);
1099                        mMergeQueue.push(mc);   
1100                }
1101        }
1102
1103        cout << "finished" << endl;
1104
1105        return shuffledViewCells;
1106}
1107
1108
1109inline int AddedPvsSize(ObjectPvs pvs1, const ObjectPvs &pvs2)
1110{
1111        return pvs1.AddPvs(pvs2);
1112}
1113
1114
1115// recomputes pvs size minus pvs of leaf l
1116#if 0
1117inline int SubtractedPvsSize(BspViewCell *vc, BspLeaf *l, const ObjectPvs &pvs2)
1118{
1119        ObjectPvs pvs;
1120        vector<BspLeaf *>::const_iterator it, it_end = vc->mLeaves.end();
1121        for (it = vc->mLeaves.begin(); it != vc->mLeaves.end(); ++ it)
1122                if (*it != l)
1123                        pvs.AddPvs(*(*it)->mPvs);
1124        return pvs.GetSize();
1125}
1126#endif
1127
1128
1129// computes pvs1 minus pvs2
1130inline int SubtractedPvsSize(ObjectPvs pvs1, const ObjectPvs &pvs2)
1131{
1132        return pvs1.SubtractPvs(pvs2);
1133}
1134
1135
1136float ViewCellsTree::EvalShuffleCost(ViewCell *leaf,
1137                                                                         ViewCellInterior *vc1,
1138                                                                         ViewCellInterior *vc2) const
1139{
1140        //const int pvs1 = SubtractedPvsSize(vc1, leaf, *leaf->mPvs);
1141        const int pvs1 = SubtractedPvsSize(vc1->GetPvs(), leaf->GetPvs());
1142        const int pvs2 = AddedPvsSize(vc2->GetPvs(), leaf->GetPvs());
1143
1144        const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize();
1145        const int upperPvsLimit = mViewCellsManager->GetMaxPvsSize();
1146
1147        const float pvsPenalty1 =
1148                EvalPvsPenalty(pvs1, lowerPvsLimit, upperPvsLimit);
1149
1150        const float pvsPenalty2 =
1151                EvalPvsPenalty(pvs2, lowerPvsLimit, upperPvsLimit);
1152
1153
1154        // don't shuffle leaves with pvs > max
1155        if (0 && (pvs1 + pvs2 > mViewCellsManager->GetMaxPvsSize()))
1156        {
1157                return 1e20f;
1158        }
1159
1160        float p1, p2;
1161
1162    if (mUseAreaForPvs)
1163        {
1164                p1 = vc1->GetArea() - leaf->GetArea();
1165                p2 = vc2->GetArea() + leaf->GetArea();
1166        }
1167        else
1168        {
1169                p1 = vc1->GetVolume() - leaf->GetVolume();
1170                p2 = vc2->GetVolume() + leaf->GetVolume();
1171        }
1172
1173        const float renderCost1 = pvsPenalty1 * p1;
1174        const float renderCost2 = pvsPenalty2 * p2;
1175
1176        float dev1, dev2;
1177
1178        if (1)
1179        {
1180                dev1 = fabs(mAvgRenderCost - pvsPenalty1);
1181                dev2 = fabs(mAvgRenderCost - pvsPenalty2);
1182        }
1183        else
1184        {
1185                dev1 = fabs(mExpectedCost - renderCost1);
1186                dev2 = fabs(mExpectedCost - renderCost2);
1187        }
1188       
1189        return mRenderCostWeight * (renderCost1 + renderCost2) +
1190                  (1.0f - mRenderCostWeight) * (dev1 + dev2) / (float)mNumActiveViewCells;
1191}
1192
1193
1194void ViewCellsTree::ShuffleLeaf(ViewCell *leaf,
1195                                                                ViewCellInterior *vc1,
1196                                                                ViewCellInterior *vc2) const
1197{
1198        // compute new pvs and area
1199        // TODO change
1200        vc1->GetPvs().SubtractPvs(leaf->GetPvs());
1201        vc2->GetPvs().AddPvs(leaf->GetPvs());
1202       
1203        if (mUseAreaForPvs)
1204        {
1205                vc1->SetArea(vc1->GetArea() - leaf->GetArea());
1206                vc2->SetArea(vc2->GetArea() + leaf->GetArea());
1207        }
1208        else
1209        {
1210                vc1->SetVolume(vc1->GetVolume() - leaf->GetVolume());
1211                vc2->SetVolume(vc2->GetVolume() + leaf->GetVolume());
1212        }
1213
1214       
1215        ViewCellInterior *p = dynamic_cast<ViewCellInterior *>(leaf->GetParent());
1216
1217        p->RemoveChildLink(leaf);
1218        vc2->SetupChildLink(leaf);
1219}
1220
1221
1222bool ViewCellsTree::ShuffleLeaves(MergeCandidate &mc) const
1223{
1224        float cost1, cost2;
1225
1226        ViewCellInterior *vc1 = dynamic_cast<ViewCellInterior *>(mc.GetLeftViewCell());
1227        ViewCellInterior *vc2 = dynamic_cast<ViewCellInterior *>(mc.GetRightViewCell());
1228
1229        ViewCell *leaf1 = mc.GetInitialLeftViewCell();
1230        ViewCell *leaf2 = mc.GetInitialRightViewCell();
1231
1232        //-- first test if shuffling would decrease cost
1233        cost1 = GetCostHeuristics(vc1);
1234        cost2 = GetCostHeuristics(vc2);
1235
1236        const float oldCost = cost1 + cost2;
1237       
1238        float shuffledCost1 = Limits::Infinity;
1239        float shuffledCost2 = Limits::Infinity;
1240
1241        if (leaf1)
1242                shuffledCost1 = EvalShuffleCost(leaf1, vc1, vc2);       
1243        if (leaf2)
1244                shuffledCost2 = EvalShuffleCost(leaf2, vc2, vc1);
1245
1246        // if cost of shuffle is less than old cost => shuffle
1247        if ((oldCost <= shuffledCost1) && (oldCost <= shuffledCost2))
1248                return false;
1249       
1250        if (shuffledCost1 < shuffledCost2)
1251        {
1252                if (leaf1)
1253                        ShuffleLeaf(leaf1, vc1, vc2);
1254                mc.mInitialLeftViewCell = NULL;
1255        }
1256        else
1257        {
1258                if (leaf2)
1259                        ShuffleLeaf(leaf2, vc2, vc1);
1260                mc.mInitialRightViewCell = NULL;
1261        }
1262
1263        return true;
1264}
1265
1266
1267float ViewCellsTree::GetVariance(ViewCell *vc) const
1268{
1269        const int upper = mViewCellsManager->GetMaxPvsSize();
1270        const int lower = mViewCellsManager->GetMinPvsSize();
1271
1272        if (1)
1273        {
1274                const float penalty =
1275                        EvalPvsPenalty(vc->GetPvs().GetSize(), lower, upper);
1276
1277                return (mAvgRenderCost - penalty) * (mAvgRenderCost - penalty) /
1278                        (float)mNumActiveViewCells;
1279        }
1280
1281    const float leafCost = GetRenderCost(vc);
1282        return (mExpectedCost - leafCost) * (mExpectedCost - leafCost);
1283}
1284
1285
1286float ViewCellsTree::GetDeviation(ViewCell *vc) const
1287{
1288        const int upper = mViewCellsManager->GetMaxPvsSize();
1289        const int lower = mViewCellsManager->GetMinPvsSize();
1290
1291        if (1)
1292        {
1293                const float penalty = EvalPvsPenalty(vc->GetPvs().CountObjectsInPvs(), lower, upper);
1294                return fabs(mAvgRenderCost - penalty) / (float)mNumActiveViewCells;
1295        }
1296
1297    const float renderCost = GetRenderCost(vc);
1298        return fabs(mExpectedCost - renderCost);
1299}
1300
1301
1302float ViewCellsTree::GetRenderCost(ViewCell *vc) const
1303{
1304        if (mUseAreaForPvs)
1305        {
1306                return vc->GetPvs().CountObjectsInPvs() * vc->GetArea();
1307        }
1308
1309        return vc->GetPvs().CountObjectsInPvs() * vc->GetVolume();
1310}
1311
1312
1313float ViewCellsTree::GetCostHeuristics(ViewCell *vc) const
1314{
1315        return GetRenderCost(vc) * mRenderCostWeight +
1316                   GetDeviation(vc) * (1.0f - mRenderCostWeight);
1317}
1318
1319
1320bool ViewCellsTree::ValidateMergeCandidate(MergeCandidate &mc) const
1321{
1322        // propagate up so we have only the active view cells
1323        while (mc.mLeftViewCell->mParent)
1324        {
1325                mc.mLeftViewCell = mc.mLeftViewCell->mParent;
1326        }
1327
1328        while (mc.mRightViewCell->mParent)
1329        {
1330                mc.mRightViewCell = mc.mRightViewCell->mParent;
1331        }
1332
1333        // this view cell was already merged
1334        //return mc.mLeftViewCell && (mc.mLeftViewCell != mc.mRightViewCell);
1335        return mc.mLeftViewCell != mc.mRightViewCell;
1336}
1337
1338
1339void ViewCellsTree::EvalMergeCost(MergeCandidate &mc) const
1340{
1341        //-- compute pvs difference
1342        int newPvs;
1343        if (1) // not valid if not using const cost per object!!
1344                newPvs = ComputeMergedPvsSize(mc.mLeftViewCell->GetPvs(), mc.mRightViewCell->GetPvs());
1345        else
1346                newPvs = (int)ComputeMergedPvsCost(mc.mLeftViewCell->GetPvs(), mc.mRightViewCell->GetPvs());
1347
1348        const float newPenalty = EvalPvsPenalty(newPvs,
1349                                                                                        mViewCellsManager->GetMinPvsSize(),
1350                                                                                        mViewCellsManager->GetMaxPvsSize());
1351
1352        ViewCell *vc1 = mc.mLeftViewCell;
1353        ViewCell *vc2 = mc.mRightViewCell;
1354
1355        //-- compute ratio of old cost
1356        //   (i.e., added size of left and right view cell times pvs size)
1357        //   to new rendering cost (i.e, size of merged view cell times pvs size)
1358        const float oldCost = GetRenderCost(vc1) + GetRenderCost(vc2);
1359
1360    const float newCost = mUseAreaForPvs ?
1361                (float)newPenalty * (vc1->GetArea() + vc2->GetArea()) :
1362                (float)newPenalty * (vc1->GetVolume() + vc2->GetVolume());
1363
1364
1365        // strong penalty if pvs size too large
1366        if (0 && (newPvs > mViewCellsManager->GetMaxPvsSize()))
1367        {
1368                mc.mRenderCost = 1e20f;
1369        }
1370        else
1371        {
1372                mc.mRenderCost = (newCost - oldCost) /
1373                        mViewCellsManager->GetViewSpaceBox().GetVolume();
1374        }       
1375       
1376
1377        //-- merge cost also takes deviation into account
1378        float newDev, oldDev;
1379
1380        if (1)
1381                newDev = fabs(mAvgRenderCost - newPenalty) / (float)mNumActiveViewCells;
1382        else
1383                newDev = fabs(mExpectedCost - newCost) / (float)mNumActiveViewCells;
1384       
1385        oldDev = GetDeviation(vc1) + GetDeviation(vc2);
1386
1387        // compute deviation increase
1388        mc.mDeviationIncr = newDev - oldDev;
1389       
1390        //Debug << "render cost: " << mc.mRenderCost * mRenderCostWeight << endl;
1391        //Debug << "standard deviation: " << mc.mDeviationIncr * mRenderCostWeight << endl;
1392}
1393
1394
1395void ViewCellsTree::SetViewCellsStorage(int stype)
1396{
1397        if (mViewCellsStorage == stype)
1398                return;
1399
1400        // TODO
1401        switch (stype)
1402        {
1403        case COMPRESSED:
1404                CompressViewCellsPvs(mRoot);
1405                break;
1406        default:
1407                break;
1408        }
1409
1410        mViewCellsStorage = stype;
1411}
1412
1413
1414void ViewCellsTree::CompressViewCellsPvs(ViewCell *root)
1415{
1416        if (!root->IsLeaf())
1417        {
1418                ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(root);
1419
1420        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1421               
1422                // compress child sets first
1423                for (it = interior->mChildren.begin(); it != it_end; ++ it)
1424                {
1425                        CompressViewCellsPvs(*it);
1426                }
1427
1428                // compress root node
1429                PullUpVisibility(interior);
1430        }
1431}
1432
1433
1434void ViewCellsTree::UpdateStats(ofstream &stats,
1435                                                                const int pass,
1436                                                                const int viewCells,
1437                                                                const float renderCostDecrease,
1438                                                                const float totalRenderCost,
1439                                                                const int currentPvs,
1440                                                                const float expectedCost,
1441                                                                const float avgRenderCost,
1442                                                                const float deviation,
1443                                                                const int totalPvs,
1444                                                                const int entriesInPvs,
1445                                                                const int pvsSizeDecr,
1446                                                                const float volume)
1447{
1448         stats << "#Pass\n" << pass << endl
1449                //<< "#Merged\n" << mergeStats.merged << endl
1450                << "#ViewCells\n" << viewCells << endl
1451        << "#RenderCostDecrease\n" << renderCostDecrease << endl // TODO
1452                << "#TotalRenderCost\n" << totalRenderCost << endl
1453                << "#CurrentPvs\n" << currentPvs << endl
1454                << "#ExpectedCost\n" << expectedCost << endl
1455                << "#AvgRenderCost\n" << avgRenderCost << endl
1456                << "#Deviation\n" << deviation << endl
1457                << "#TotalPvs\n" << totalPvs << endl
1458                << "#TotalEntriesInPvs\n" << entriesInPvs << endl
1459                << "#PvsSizeDecrease\n" << pvsSizeDecr << endl // TODO
1460                << "#Volume\n" << volume << endl
1461                << endl;
1462}
1463
1464void ViewCellsTree::ExportStats(const string &mergeStats)
1465{
1466        TraversalQueue tqueue;
1467
1468        tqueue.push(mRoot);
1469        int numViewCells = 1;
1470       
1471        const AxisAlignedBox3 box = mViewCellsManager->GetViewSpaceBox();
1472        const float vol = box.GetVolume();
1473
1474        const int rootPvs = GetPvsSize(mRoot);
1475        const int rootEntries = GetPvsEntries(mRoot);
1476
1477        Debug << "******** Export stats **********" << endl;
1478        /*Debug << "vsb volume: " << vol << endl;
1479        Debug << "root volume: " << mRoot->GetVolume() << endl;
1480        Debug << "root pvs: " << rootPvs << endl;
1481        */
1482
1483        float totalRenderCost, avgRenderCost, expectedCost;
1484
1485        float deviation = 0;
1486        int totalPvs = rootPvs;
1487        int entriesInPvs = rootEntries;
1488
1489        totalRenderCost = avgRenderCost = expectedCost = (float)rootPvs;
1490
1491        ofstream stats;
1492        stats.open(mergeStats.c_str());
1493
1494        //-- first view cell
1495        UpdateStats(stats,
1496                                0, numViewCells, 0, totalRenderCost,
1497                                rootPvs, expectedCost, avgRenderCost, deviation,
1498                                totalPvs, entriesInPvs, 0, mRoot->GetVolume());
1499               
1500
1501        //-- go through tree in the order of render cost decrease
1502        //-- which is the same order as the view cells were merged
1503        //-- or the reverse order of subdivision for subdivision-only
1504        //-- view cell hierarchies.
1505
1506        while (!tqueue.empty())
1507        {
1508                ViewCell *vc = tqueue.top();
1509                tqueue.pop();
1510
1511                if (!vc->IsLeaf())
1512                {       
1513                        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
1514
1515                        const int parentPvs = GetPvsSize(interior);
1516                        const int parentPvsEntries = GetPvsEntries(interior);
1517            const float parentCost = (float)parentPvs * interior->GetVolume();
1518
1519                        float childCost = 0;
1520                        int childPvs = 0;
1521                        int childPvsEntries = 0;
1522
1523                        -- numViewCells;
1524
1525                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1526
1527                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
1528                        {
1529                                ViewCell *vc = *it;
1530
1531                                const int pvsSize = GetPvsSize(vc);
1532                                const int pvsEntries = GetPvsEntries(vc);
1533
1534                                childCost += (float) pvsSize * vc->GetVolume();
1535                                childPvs += pvsSize;
1536                                childPvsEntries += pvsEntries;
1537
1538                                tqueue.push(vc);
1539                                ++ numViewCells;
1540                        }
1541
1542
1543                        const float costDecr = (parentCost - childCost) / vol;
1544
1545                        totalRenderCost -= costDecr;
1546                        totalPvs += childPvs - parentPvs;
1547                        entriesInPvs += childPvsEntries - parentPvsEntries;
1548
1549                        expectedCost = totalRenderCost / (float)numViewCells;
1550                        avgRenderCost = (float)totalPvs / (float)numViewCells;
1551
1552                        UpdateStats(stats,
1553                                                0, numViewCells, costDecr, totalRenderCost,
1554                                                parentPvs, expectedCost, avgRenderCost, deviation,
1555                        totalPvs, entriesInPvs, childPvs - parentPvs,
1556                                                vc->GetVolume());
1557
1558                }
1559        }
1560
1561        stats.close();
1562}
1563
1564
1565void ViewCellsTree::SetRoot(ViewCell *root)
1566{
1567        mRoot = root;
1568}
1569
1570
1571void ViewCellsTree::CollectBestViewCellSet(ViewCellContainer &viewCells,
1572                                                                                   const int numViewCells)
1573{
1574        TraversalQueue tqueue;
1575        tqueue.push(mRoot);
1576       
1577        while (!tqueue.empty())
1578        {
1579                ViewCell *vc = tqueue.top();
1580                tqueue.pop();
1581
1582                // save the view cells if it is a leaf or if enough view cells have already been traversed
1583                // because of the priority queue, this will be the optimal set of v
1584                if (vc->IsLeaf() || ((viewCells.size() + tqueue.size() + 1) >= numViewCells))
1585                {
1586                        viewCells.push_back(vc);
1587                }
1588                else
1589                {       
1590                        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
1591
1592                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1593
1594                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
1595                        {
1596                                tqueue.push(*it);
1597                        }
1598                }
1599        }
1600}
1601       
1602
1603void ViewCellsTree::PullUpVisibility(ViewCellInterior *interior)
1604{
1605        Intersectable::NewMail((int)interior->mChildren.size());
1606
1607        ViewCellContainer::const_iterator cit, cit_end = interior->mChildren.end();
1608
1609        ObjectPvsMap::const_iterator oit;
1610
1611        // mail all objects in the leaf sets
1612        // we are interested in the objects which are present in all leaves
1613        // => count how often an object is part of a child set
1614        for (cit = interior->mChildren.begin(); cit != cit_end; ++ cit)
1615        {
1616                ViewCell *vc = *cit;
1617
1618                ObjectPvsMap::const_iterator oit_end = vc->GetPvs().mEntries.end();
1619
1620                for (oit = vc->GetPvs().mEntries.begin(); oit != oit_end; ++ oit)
1621                {
1622                        Intersectable *obj = (*oit).first;
1623                        if ((cit == interior->mChildren.begin()) && !obj->Mailed())
1624                                obj->Mail();
1625                       
1626                        int incm = obj->IncMail();
1627                }
1628        }
1629
1630        interior->GetPvs().Clear();
1631       
1632       
1633        // only the objects which are present in all leaf pvs
1634        // should remain in the parent pvs
1635        // these are the objects which have been mailed in all children
1636        for (cit = interior->mChildren.begin(); cit != cit_end; ++ cit)
1637        {
1638                ViewCell *vc = *cit;
1639
1640                ObjectPvsMap::const_iterator oit_end = vc->GetPvs().mEntries.end();
1641
1642                for (oit = vc->GetPvs().mEntries.begin(); oit != oit_end; ++ oit)
1643                {               
1644                        if ((*oit).first->Mailed((int)interior->mChildren.size()))
1645                        {       
1646                                interior->GetPvs().AddSample((*oit).first, (*oit).second.mSumPdf);
1647                        }
1648                }
1649        }
1650
1651
1652        // delete all the objects from the leaf sets which were moved to parent pvs
1653        ObjectPvsMap::const_iterator oit_end = interior->GetPvs().mEntries.end();
1654
1655        for (oit = interior->GetPvs().mEntries.begin(); oit != oit_end; ++ oit)
1656        {
1657                for (cit = interior->mChildren.begin(); cit != cit_end; ++ cit)
1658                {
1659                        if (!(*cit)->GetPvs().RemoveSample((*oit).first, Limits::Infinity))
1660                        {
1661                                Debug << "should not come here!" << endl;
1662                        }
1663                }
1664        }
1665}
1666
1667
1668// TODO matt: implement this function for different storing methods
1669void ViewCellsTree::GetPvs(ViewCell *vc, ObjectPvs &pvs) const
1670{
1671        // pvs is stored in each cell => just return pvs
1672        if (mViewCellsStorage == PVS_IN_INTERIORS)
1673        {
1674                pvs = vc->GetPvs();
1675                return;
1676        }
1677
1678
1679        //-- pvs is not stored with the interiors => reconstruct
1680        Intersectable::NewMail();
1681
1682        int pvsSize = 0;
1683        ViewCell *root = vc;
1684       
1685        // add pvs from this view cell to root
1686        while (root->GetParent())
1687        {
1688                root = root->GetParent();
1689                pvs.AddPvs(root->GetPvs());
1690        }
1691
1692        // add pvs from leaves
1693        stack<ViewCell *> tstack;
1694        tstack.push(vc);
1695
1696        while (!tstack.empty())
1697        {
1698                vc = tstack.top();
1699                tstack.pop();
1700
1701                // add newly found pvs to merged pvs
1702                pvs.AddPvs(vc->GetPvs());
1703
1704                if (!vc->IsLeaf()) // interior cells: go down to leaf level
1705                {
1706                        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
1707
1708                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1709
1710                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
1711                        {
1712                                tstack.push(*it);
1713                        }               
1714                }
1715        }
1716}
1717
1718
1719int ViewCellsTree::GetPvsSizeForLeafStorage(ViewCell *vc) const
1720{
1721        // pvs is always stored directly in leaves
1722        if (vc->IsLeaf())
1723        {
1724                return vc->GetPvs().CountObjectsInPvs();
1725        }
1726       
1727        // interior node
1728       
1729        // interior nodes: pvs is either stored as a scalar or
1730        // has to be reconstructed from the leaves
1731
1732        // the stored pvs size is the valid pvs size => just return scalar
1733        if (vc->mPvsSizeValid)
1734        {
1735                return vc->mPvsSize;
1736        }
1737       
1738        // if no valid pvs size stored as a scalar =>
1739        // compute current pvs size of interior from it's leaf nodes
1740        ViewCellContainer leaves;
1741        CollectLeaves(vc, leaves);
1742
1743        ViewCellContainer::const_iterator it, it_end = leaves.end();
1744
1745        Intersectable::NewMail();
1746        ObjectPvs newPvs;
1747
1748        // sum different intersectables
1749        for (it = leaves.begin(); it != it_end; ++ it)
1750        {
1751                ObjectPvsMap::iterator oit, oit_end = (*it)->GetPvs().mEntries.end();
1752
1753                for (oit = (*it)->GetPvs().mEntries.begin(); oit != oit_end; ++ oit)
1754                {
1755                        Intersectable *intersect = (*oit).first;
1756
1757                        if (!intersect->Mailed())
1758                        {
1759                                intersect->Mail();
1760                                newPvs.AddSample(intersect, (*oit).second.mSumPdf);
1761                        }
1762                }
1763        }
1764
1765        return newPvs.CountObjectsInPvs();
1766}
1767
1768
1769int ViewCellsTree::GetEntriesInPvsForLeafStorage(ViewCell *vc) const
1770{
1771        // pvs is always stored directly in leaves
1772        if (vc->IsLeaf())
1773        {
1774                return vc->GetPvs().GetSize();
1775        }
1776       
1777        // interior node
1778
1779        // interior nodes: pvs is either stored as a scalar or
1780        // has to be reconstructed from the leaves
1781
1782        // the stored pvs size is the valid pvs size => just return scalar
1783        if (vc->mPvsSizeValid)
1784        {
1785                return vc->mEntriesInPvs;
1786        }
1787       
1788        int pvsSize = 0;
1789
1790        // if no valid pvs size stored as a scalar =>
1791        // compute current pvs size of interior from it's leaf nodes
1792        ViewCellContainer leaves;
1793        CollectLeaves(vc, leaves);
1794
1795        ViewCellContainer::const_iterator it, it_end = leaves.end();
1796        Intersectable::NewMail();
1797
1798        // sum different intersectables
1799        for (it = leaves.begin(); it != it_end; ++ it)
1800        {
1801                ObjectPvsMap::iterator oit, oit_end = (*it)->GetPvs().mEntries.end();
1802
1803                for (oit = (*it)->GetPvs().mEntries.begin(); oit != oit_end; ++ oit)
1804                {
1805                        Intersectable *intersect = (*oit).first;
1806
1807                        if (!intersect->Mailed())
1808                        {
1809                                intersect->Mail();
1810                                ++ pvsSize;
1811                        }
1812                }
1813        }
1814
1815        return pvsSize;
1816}
1817
1818
1819int ViewCellsTree::GetPvsSizeForCompressedStorage(ViewCell *vc) const
1820{
1821        int pvsSize = 0;
1822
1823        //-- compressed pvs
1824
1825        // the stored pvs size is the valid pvs size => just return scalar
1826        if (vc->mPvsSizeValid)
1827        {
1828                pvsSize = vc->mPvsSize;
1829        }
1830
1831        // if no pvs size stored, compute new one
1832        ViewCell *root = vc;
1833       
1834        // also add pvs from this view cell to root
1835        while (root->GetParent())
1836        {
1837                root = root->GetParent();
1838       
1839                // matt: bug! must evaluate kd pvss also
1840                pvsSize += CountDiffPvs(root);
1841        }
1842
1843        stack<ViewCell *> tstack;
1844        tstack.push(vc);
1845
1846        while (!tstack.empty())
1847        {
1848                vc = tstack.top();
1849                tstack.pop();
1850                // matt: bug! must evaluate kd pvss also
1851                pvsSize += CountDiffPvs(vc);
1852
1853                if (!vc->IsLeaf())
1854                {
1855                        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
1856
1857                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1858
1859                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
1860                        {
1861                                tstack.push(*it);
1862                        }               
1863                }
1864        }
1865
1866        return pvsSize;
1867}
1868
1869
1870int ViewCellsTree::GetEntriesInPvsForCompressedStorage(ViewCell *vc) const
1871{
1872        int pvsSize = 0;
1873
1874        //-- compressed pvs
1875
1876        // the stored pvs size is the valid pvs size => just return scalar
1877        if (vc->mPvsSizeValid)
1878        {
1879                pvsSize = vc->mEntriesInPvs;
1880        }
1881
1882        // if no pvs size stored, compute new one
1883        ViewCell *root = vc;
1884       
1885        // also add pvs from this view cell to root
1886        while (root->GetParent())
1887        {
1888                root = root->GetParent();
1889                // count the pvs entries different from the already found ones 
1890                pvsSize += CountDiffPvs(root);
1891        }
1892
1893        stack<ViewCell *> tstack;
1894        tstack.push(vc);
1895
1896        while (!tstack.empty())
1897        {
1898                vc = tstack.top();
1899                tstack.pop();
1900       
1901                // count the pvs entries different from the already found ones 
1902                pvsSize += CountDiffPvs(vc);
1903
1904                if (!vc->IsLeaf())
1905                {
1906                        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
1907
1908                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1909
1910                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
1911                        {
1912                                tstack.push(*it);
1913                        }               
1914                }
1915        }
1916
1917        return pvsSize;
1918}
1919
1920
1921int ViewCellsTree::GetPvsSize(ViewCell *vc) const
1922{
1923        int pvsSize = 0;
1924
1925        Intersectable::NewMail();
1926
1927        ////////////////////////////////////////////////
1928        //  for interiors, pvs can be stored using different methods
1929        //
1930
1931        switch (mViewCellsStorage)
1932        {
1933        case PVS_IN_LEAVES: //-- store pvs only in leaves
1934                {                       
1935                        pvsSize = GetPvsSizeForLeafStorage(vc);                 
1936                        break;
1937                }
1938        case COMPRESSED:
1939                {
1940                        pvsSize = GetPvsSizeForCompressedStorage(vc);
1941                        break;
1942                }
1943        case PVS_IN_INTERIORS:
1944        default:
1945                // pvs is stored consistently in the tree up to the root
1946                // just return pvs size
1947                pvsSize = vc->GetPvs().CountObjectsInPvs();     
1948                break;
1949        }
1950
1951        return pvsSize; 
1952}
1953
1954
1955int ViewCellsTree::GetPvsEntries(ViewCell *vc) const
1956{
1957        int pvsSize = 0;
1958
1959        Intersectable::NewMail();
1960
1961        ////////////////////////////////////////////////
1962        // for interiors, pvs can be stored using different methods
1963       
1964        switch (mViewCellsStorage)
1965        {
1966        case PVS_IN_LEAVES: //-- store pvs only in leaves
1967                {                       
1968                        pvsSize = GetEntriesInPvsForLeafStorage(vc);
1969                        break;
1970                }
1971        case COMPRESSED:
1972                {
1973                        pvsSize = GetEntriesInPvsForCompressedStorage(vc);
1974                        break;
1975                }
1976        case PVS_IN_INTERIORS:
1977        default:
1978                // pvs is stored consistently in the tree up to the root
1979                // just return pvs size
1980                pvsSize = vc->GetPvs().GetSize();       
1981                break;
1982        }
1983
1984        return pvsSize; 
1985}
1986
1987
1988float ViewCellsTree::GetMemoryCost(ViewCell *vc) const
1989{
1990        const float entrySize =
1991                sizeof(PvsData) + sizeof(Intersectable *);
1992
1993        return (float)GetStoredPvsEntriesNum(vc) * entrySize;
1994}
1995
1996
1997int ViewCellsTree::GetStoredPvsEntriesNum(ViewCell *root) const
1998{
1999        int pvsSize = root->GetPvs().GetSize();
2000
2001        // recursivly count leaves
2002        if (!root->IsLeaf())
2003        {
2004                ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(root);
2005
2006                ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
2007
2008                for (it = interior->mChildren.begin(); it != it_end; ++ it)
2009                {
2010                        pvsSize += GetStoredPvsEntriesNum(*it);
2011                }
2012        }
2013
2014        return pvsSize;         
2015}
2016
2017
2018int ViewCellsTree::ViewCellsStorage() const
2019{
2020        return mViewCellsStorage;
2021}
2022
2023
2024ViewCell *ViewCellsTree::GetActiveViewCell(ViewCellLeaf *vc) const
2025{
2026        return vc->GetActiveViewCell();
2027}
2028
2029
2030void ViewCellsTree::PropagatePvs(ViewCell *vc)
2031{       
2032        ViewCell *viewCell = vc;
2033
2034        // propagate pvs up
2035        while (viewCell->GetParent())
2036        {
2037                viewCell->GetParent()->GetPvs().Merge(vc->GetPvs());
2038                viewCell = viewCell->GetParent();
2039        }
2040
2041        if (vc->IsLeaf())
2042                return;
2043
2044        // propagate pvs to the leaves
2045        stack<ViewCell *> tstack;
2046        tstack.push(vc);
2047
2048        while (!tstack.empty())
2049        {
2050                ViewCell *viewCell = tstack.top();
2051                tstack.pop();
2052
2053                if (viewCell != vc)
2054                {
2055                        viewCell->GetPvs().Merge(vc->GetPvs());
2056                }
2057
2058                if (!viewCell->IsLeaf())
2059                {
2060                        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(viewCell);
2061
2062                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
2063
2064                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
2065                        {
2066                                tstack.push(*it);
2067                        }
2068                }
2069        }
2070}
2071
2072
2073void ViewCellsTree::AssignRandomColors()
2074{
2075        TraversalQueue tqueue;
2076       
2077        tqueue.push(mRoot);
2078       
2079        mRoot->SetColor(RandomColor(0.3f, 1.0f));
2080       
2081        while (!tqueue.empty())
2082        {
2083                ViewCell *vc = tqueue.top();
2084                tqueue.pop();
2085
2086                // save the view cells if it is a leaf or if enough view cells have already been traversed
2087                // because of the priority queue, this will be the optimal set of v
2088                if (!vc->IsLeaf())
2089                {       
2090                        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
2091                 
2092                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
2093                 
2094                        float maxProbability = -1.0f;
2095                 
2096                        ViewCell *maxViewCell = NULL;
2097                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
2098                        {
2099                                ViewCell *v = *it;
2100                         
2101                                // set random color
2102                                v->SetColor(RandomColor(0.3f, 1.0f));
2103                         
2104                                if (v->GetVolume() > maxProbability)
2105                                {
2106                                        maxProbability = v->GetVolume();
2107                                        maxViewCell = v;
2108                                }
2109
2110                                if (maxViewCell)
2111                                {
2112                                        maxViewCell->SetColor(vc->GetColor());
2113                                }
2114                               
2115                                tqueue.push(v);
2116                        }
2117                }       
2118        }
2119}
2120
2121
2122/** Get costs resulting from each merge step.
2123*/
2124void
2125ViewCellsTree::GetCostFunction(vector<float> &costFunction)
2126{
2127        TraversalQueue tqueue;
2128        tqueue.push(mRoot);
2129       
2130        while (!tqueue.empty())
2131        {
2132                ViewCell *vc = tqueue.top();
2133                tqueue.pop();
2134                // save the view cells if it is a leaf or if enough view cells have already been traversed
2135                // because of the priority queue, this will be the optimal set of v
2136                if (!vc->IsLeaf()) {   
2137                        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
2138                        costFunction.push_back(interior->GetMergeCost());
2139
2140                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
2141
2142                        for (it = interior->mChildren.begin(); it != it_end; ++ it) {
2143                                tqueue.push(*it);
2144                        }
2145
2146                }
2147        }
2148}
2149
2150
2151void ViewCellsTree::UpdateViewCellsStats(ViewCell *vc,
2152                                                                                 ViewCellsStatistics &vcStat)
2153{
2154        ++ vcStat.viewCells;
2155               
2156        const int pvsSize = GetPvsSize(vc);
2157
2158        vcStat.pvsSize += pvsSize;
2159
2160        if (pvsSize == 0)
2161                ++ vcStat.emptyPvs;
2162
2163        if (pvsSize > vcStat.maxPvs)
2164                vcStat.maxPvs = pvsSize;
2165
2166        if (pvsSize < vcStat.minPvs)
2167                vcStat.minPvs = pvsSize;
2168
2169        if (!vc->GetValid())
2170                ++ vcStat.invalid;
2171}
2172
2173
2174bool ViewCellsTree::Export(OUT_STREAM &stream, const bool exportPvs)
2175{
2176        // export recursivly all view cells from the root
2177        ExportViewCell(mRoot, stream, exportPvs);
2178
2179        return true;
2180}
2181
2182
2183void ViewCellsTree::CreateUniqueViewCellsIds()
2184{
2185        stack<ViewCell *> tstack;
2186
2187        int currentId = 0;
2188
2189        tstack.push(mRoot);
2190
2191        while (!tstack.empty())
2192        {
2193                ViewCell *vc = tstack.top();
2194                tstack.pop();
2195
2196                vc->SetId(currentId ++);
2197
2198                if (!vc->IsLeaf())
2199                {
2200                        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
2201                       
2202                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
2203                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
2204                        {
2205                                tstack.push(*it);
2206                        }
2207                }
2208        }
2209}
2210
2211
2212void ViewCellsTree::ExportPvs(ViewCell *viewCell, OUT_STREAM &stream)
2213{
2214        ObjectPvsMap::iterator it, it_end = viewCell->GetPvs().mEntries.end();
2215
2216        for (it = viewCell->GetPvs().mEntries.begin(); it != it_end; ++ it)
2217        {
2218                stream << (*it).first->GetId() << " ";
2219        }
2220}
2221
2222
2223void ViewCellsTree::ExportViewCell(ViewCell *viewCell,
2224                                                                   OUT_STREAM &stream,
2225                                                                   const bool exportPvs)
2226{
2227        if (viewCell->IsLeaf())
2228        {
2229                stream << "<Leaf ";
2230                stream << "id=\"" << viewCell->GetId() << "\" ";
2231                stream << "active=\"" << dynamic_cast<ViewCellLeaf *>(viewCell)->GetActiveViewCell()->GetId() << "\" ";
2232                stream << "mergecost=\"" << viewCell->GetMergeCost() << "\" ";
2233                stream << "pvs=\"";
2234               
2235                //-- export pvs
2236                if (exportPvs)
2237                {
2238                        ExportPvs(viewCell, stream);
2239                }
2240
2241                stream << "\" />" << endl;
2242        }
2243        else
2244        {
2245                ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(viewCell);
2246       
2247                stream << "<Interior ";
2248                stream << "id=\"" << viewCell->GetId() << "\" ";
2249                stream << "mergecost=\"" << viewCell->GetMergeCost() << "\" ";
2250                stream << "pvs=\"";
2251
2252                //-- NOTE: do not export pvss for interior view cells because
2253                // they can be completely reconstructed from the leaf pvss
2254                if (0)
2255                        ExportPvs(viewCell, stream);
2256               
2257                stream << "\" >" << endl;
2258
2259                //-- recursivly export child view cells
2260                ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
2261
2262                for (it = interior->mChildren.begin(); it != it_end; ++ it)
2263                {
2264                        ExportViewCell(*it, stream, exportPvs);
2265                }
2266
2267                stream << "</Interior>" << endl;
2268        }
2269}
2270
2271
2272void ViewCellsTree::ResetPvs()
2273{
2274        stack<ViewCell *> tstack;
2275
2276        tstack.push(mRoot);
2277
2278        while (!tstack.empty())
2279        {
2280                ViewCell *vc = tstack.top();
2281                tstack.pop();
2282
2283                vc->GetPvs().Clear();
2284               
2285                if (!vc->IsLeaf())
2286                {
2287                        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
2288                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
2289
2290                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
2291                        {
2292                                tstack.push(*it);
2293                        }
2294                }
2295        }
2296}
2297
2298
2299void ViewCellsTree::SetActiveSetToLeaves()
2300{
2301        // todo
2302}
2303
2304/**************************************************************************/
2305/*                     MergeCandidate implementation                      */
2306/**************************************************************************/
2307
2308
2309MergeCandidate::MergeCandidate(ViewCell *l, ViewCell *r):
2310mRenderCost(0),
2311mDeviationIncr(0),
2312mLeftViewCell(l),
2313mRightViewCell(r),
2314mInitialLeftViewCell(l),
2315mInitialRightViewCell(r)
2316{
2317        //EvalMergeCost();
2318}
2319
2320
2321void MergeCandidate::SetRightViewCell(ViewCell *v)
2322{
2323        mRightViewCell = v;
2324}
2325
2326
2327void MergeCandidate::SetLeftViewCell(ViewCell *v)
2328{
2329        mLeftViewCell = v;
2330}
2331
2332
2333ViewCell *MergeCandidate::GetRightViewCell() const
2334{
2335        return mRightViewCell;
2336}
2337
2338
2339ViewCell *MergeCandidate::GetLeftViewCell() const
2340{
2341        return mLeftViewCell;
2342}
2343
2344
2345ViewCell *MergeCandidate::GetInitialRightViewCell() const
2346{
2347        return mInitialRightViewCell;
2348}
2349
2350
2351ViewCell *MergeCandidate::GetInitialLeftViewCell() const
2352{
2353        return mInitialLeftViewCell;
2354}
2355
2356
2357bool MergeCandidate::IsValid() const
2358{
2359        // if one has a parent, it was already merged
2360        return !(mLeftViewCell->GetParent() || mRightViewCell->GetParent());
2361}
2362
2363
2364float MergeCandidate::GetRenderCost() const
2365{
2366        return mRenderCost;
2367}
2368
2369
2370float MergeCandidate::GetDeviationIncr() const
2371{
2372        return mDeviationIncr;
2373}
2374
2375
2376float MergeCandidate::GetMergeCost() const
2377{
2378        return mRenderCost * sRenderCostWeight +
2379                   mDeviationIncr * (1.0f - sRenderCostWeight);
2380}
2381
2382
2383
2384
2385
2386
2387/************************************************************************/
2388/*                    MergeStatistics implementation                    */
2389/************************************************************************/
2390
2391
2392void MergeStatistics::Print(ostream &app) const
2393{
2394        app << "===== Merge statistics ===============\n";
2395
2396        app << setprecision(4);
2397
2398        app << "#N_CTIME ( Overall time [s] )\n" << Time() << " \n";
2399
2400        app << "#N_CCTIME ( Collect candidates time [s] )\n" << collectTime * 1e-3f << " \n";
2401
2402        app << "#N_MTIME ( Merge time [s] )\n" << mergeTime * 1e-3f << " \n";
2403
2404        app << "#N_NODES ( Number of nodes before merge )\n" << nodes << "\n";
2405
2406        app << "#N_CANDIDATES ( Number of merge candidates )\n" << candidates << "\n";
2407
2408        app << "#N_MERGEDSIBLINGS ( Number of merged siblings )\n" << siblings << "\n";
2409
2410        app << "#OVERALLCOST ( overall merge cost )\n" << overallCost << "\n";
2411
2412        app << "#N_MERGEDNODES ( Number of merged nodes )\n" << merged << "\n";
2413
2414        app << "#MAX_TREEDIST ( Maximal distance in tree of merged leaves )\n" << maxTreeDist << "\n";
2415
2416        app << "#AVG_TREEDIST ( Average distance in tree of merged leaves )\n" << AvgTreeDist() << "\n";
2417
2418        app << "#EXPECTEDCOST ( expected render cost )\n" << expectedRenderCost << "\n";
2419
2420        app << "#DEVIATION ( deviation )\n" << deviation << "\n";
2421
2422        app << "#HEURISTICS ( heuristics )\n" << heuristics << "\n";
2423       
2424
2425        app << "===== END OF BspTree statistics ==========\n";
2426}
2427
2428}
Note: See TracBrowser for help on using the repository browser.