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

Revision 660, 46.8 KB checked in by mattausch, 19 years ago (diff)

adding function for testing purpose

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