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

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