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

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