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

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