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

Revision 650, 44.9 KB checked in by mattausch, 19 years ago (diff)

added spatial hierarchy based merge tree

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