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

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