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

Revision 608, 41.7 KB checked in by bittner, 19 years ago (diff)

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