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

Revision 1221, 56.8 KB checked in by mattausch, 18 years ago (diff)

added intel ray tracing

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