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

Revision 1843, 60.8 KB checked in by mattausch, 18 years ago (diff)

warning! changed pvs output because of paper hack
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                /*cout << "***************\nbefore pulling up:\n";
1491                for (it = interior->mChildren.begin(); it != it_end; ++ it)
1492                {
1493                        cout << "vc:\n" << (*it)->GetPvs() << endl;
1494                }*/
1495
1496                // compress root node
1497                PullUpVisibility(interior);
1498
1499                /*cout << "after pulling up:\n";
1500                cout << "interior:\n" << interior->GetPvs() << endl;
1501
1502                for (it = interior->mChildren.begin(); it != it_end; ++ it)
1503                {
1504                        cout << "vc:\n" << (*it)->GetPvs() << endl;
1505                }*/
1506        }
1507}
1508
1509
1510void ViewCellsTree::UpdateStats(ofstream &stats,
1511                                                                const ViewCellsTreeStats &vcStats)
1512{
1513         stats << "#Pass\n" << vcStats.mPass << endl
1514                   << "#Splits\n" << vcStats.mNumViewCells << endl
1515                   << "#RenderCostDecrease\n" << vcStats.mRenderCostDecrease << endl // TODO
1516                   << "#TotalRenderCost\n" << vcStats.mTotalRenderCost << endl
1517                   << "#CurrentPvs\n" << vcStats.mCurrentPvsCost << endl
1518                   << "#ExpectedCost\n" << vcStats.mExpectedCost << endl
1519                   << "#AvgRenderCost\n" << vcStats.mAvgRenderCost << endl
1520                   << "#Deviation\n" << vcStats.mDeviation << endl
1521                   << "#TotalPvs\n" << vcStats.mTotalPvsCost << endl
1522                   << "#TotalEntriesInPvs\n" << vcStats.mEntriesInPvs << endl
1523                   << "#Memory\n" << vcStats.mMemoryCost << endl
1524                   << "#PvsSizeDecrease\n" << vcStats.mPvsSizeDecr << endl
1525                   << "#Volume\n" << vcStats.mVolume << endl
1526                   << endl;
1527}
1528
1529
1530void ViewCellsTree::ExportStats(const string &mergeStats)
1531{
1532        TraversalQueue tqueue;
1533        tqueue.push(mRoot);
1534
1535        ViewCellsTreeStats vcStats;
1536        vcStats.Reset();
1537
1538        //cout << "exporting stats ... " << endl;
1539        vcStats.mNumViewCells = 1;
1540       
1541        const AxisAlignedBox3 box = mViewCellsManager->GetViewSpaceBox();
1542        const float vol = box.GetVolume();
1543
1544        const float rootPvs = GetPvsCost(mRoot);
1545        const int rootEntries = GetPvsEntries(mRoot);
1546       
1547        vcStats.mTotalPvsCost = rootPvs;
1548        vcStats.mTotalRenderCost = rootPvs;
1549        vcStats.mAvgRenderCost = rootPvs;
1550        vcStats.mExpectedCost = rootPvs;
1551       
1552        vcStats.mEntriesInPvs = rootEntries;
1553
1554        ofstream stats;
1555        stats.open(mergeStats.c_str());
1556
1557        vcStats.mMemoryCost = (float)vcStats.mEntriesInPvs * ObjectPvs::GetEntrySize();
1558
1559        /////////////
1560        //-- first view cell
1561
1562        UpdateStats(stats, vcStats);
1563                               
1564               
1565        //-- go through tree in the order of render cost decrease
1566        //-- which is the same order as the view cells were merged
1567        //-- or the reverse order of subdivision for subdivision-only
1568        //-- view cell hierarchies.
1569
1570        while (!tqueue.empty())
1571        {
1572                ViewCell *vc = tqueue.top();
1573                tqueue.pop();
1574
1575                if (!vc->IsLeaf())
1576                {       
1577                        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
1578
1579                        const float parentCost = GetPvsCost(interior);
1580                        const int parentPvsEntries = GetPvsEntries(interior);
1581            const float parentExpCost = (float)parentCost * interior->GetVolume();
1582
1583                        float childExpCost = 0;
1584                        float childCost = 0;
1585                        int childPvsEntries = 0;
1586
1587                        -- vcStats.mNumViewCells;
1588
1589                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1590
1591                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
1592                        {
1593                                ViewCell *vc = *it;
1594
1595                                const float pvsCost = GetPvsCost(vc);
1596                                const int pvsEntries = GetPvsEntries(vc);
1597
1598                                childExpCost += childCost * vc->GetVolume();
1599                                childCost += pvsCost;
1600                                childPvsEntries += pvsEntries;
1601
1602                                tqueue.push(vc);
1603                                ++ vcStats.mNumViewCells;
1604                        }
1605
1606                        // update stats for this view cell
1607                        const float costDecr = (parentExpCost - childExpCost) / vol;
1608
1609                        vcStats.mTotalRenderCost -= costDecr;
1610                        vcStats.mTotalPvsCost += childCost - parentCost;
1611                        vcStats.mEntriesInPvs += childPvsEntries - parentPvsEntries;
1612
1613                        vcStats.mExpectedCost = vcStats.mTotalRenderCost / (float)vcStats.mNumViewCells;
1614                        vcStats.mAvgRenderCost = vcStats.mTotalPvsCost / (float)vcStats.mNumViewCells;
1615
1616                        vcStats.mMemoryCost = vcStats.mEntriesInPvs * ObjectPvs::GetEntrySize();
1617
1618                        UpdateStats(stats, vcStats);
1619                }
1620        }
1621
1622        stats.close();
1623}
1624
1625
1626void ViewCellsTree::SetRoot(ViewCell *root)
1627{
1628        mRoot = root;
1629}
1630
1631
1632void ViewCellsTree::CollectBestViewCellSet(ViewCellContainer &viewCells,
1633                                                                                   const int numViewCells)
1634{
1635        TraversalQueue tqueue;
1636        tqueue.push(mRoot);
1637       
1638        while (!tqueue.empty())
1639        {
1640                ViewCell *vc = tqueue.top();
1641                tqueue.pop();
1642
1643                // save the view cells if it is a leaf or if enough view cells have already been traversed
1644                // because of the priority queue, this will be the optimal set of v
1645                if (vc->IsLeaf() || ((viewCells.size() + tqueue.size() + 1) >= numViewCells))
1646                {
1647                        viewCells.push_back(vc);
1648                }
1649                else
1650                {       
1651                        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
1652
1653                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1654
1655                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
1656                        {
1657                                tqueue.push(*it);
1658                        }
1659                }
1660        }
1661}
1662
1663
1664void ViewCellsTree::PullUpVisibility(ViewCellInterior *interior)
1665{
1666        const int mail = (int)interior->mChildren.size();
1667        Intersectable::NewMail(mail);
1668
1669        ViewCellContainer::const_iterator cit, cit_end = interior->mChildren.end();
1670
1671    // mail all objects in the leaf sets
1672        // we are interested in the objects which are present in all leaves
1673        // => count how often an object is part of a child set
1674        for (cit = interior->mChildren.begin(); cit != cit_end; ++ cit)
1675        {
1676                ViewCell *vc = *cit;
1677                ObjectPvsIterator pit = vc->GetPvs().GetIterator();
1678
1679                while (pit.HasMoreEntries())
1680                {               
1681                        const ObjectPvsEntry &entry = pit.Next();
1682                        Intersectable *obj = entry.mObject;
1683                        obj->Mail();
1684                }
1685        }
1686
1687        for (cit = interior->mChildren.begin(); cit != cit_end; ++ cit)
1688        {
1689                ViewCell *vc = *cit;
1690
1691                ObjectPvsIterator pit = vc->GetPvs().GetIterator();
1692
1693                while (pit.HasMoreEntries())
1694                {               
1695                        const ObjectPvsEntry &entry = pit.Next();
1696                        Intersectable *obj = entry.mObject;
1697
1698                        obj->IncMail();
1699                }
1700        }
1701
1702        // reset pvs
1703    interior->GetPvs().Clear(false);
1704               
1705        // only the objects which are present in all leaf pvs
1706        // should remain in the parent pvs
1707        // these are the objects which have been mailed in all children
1708        for (cit = interior->mChildren.begin(); cit != cit_end; ++ cit)
1709        {
1710                ViewCell *vc = *cit;
1711               
1712                ObjectPvsIterator pit = vc->GetPvs().GetIterator();
1713
1714                while (pit.HasMoreEntries())
1715                {               
1716                        ObjectPvsEntry entry = pit.Next();
1717
1718                        if (entry.mObject->Mailed(mail))
1719                        {       
1720                                interior->GetPvs().AddSample(entry.mObject, entry.mData.mSumPdf);
1721                        }
1722                }
1723        }
1724
1725        // delete entries which are pulled up
1726        // note: could be inefficent, rather gather unmailed pvs and reassign
1727        for (cit = interior->mChildren.begin(); cit != cit_end; ++ cit)
1728        {
1729                ViewCell *vc = *cit;
1730                ObjectPvsIterator pit = vc->GetPvs().GetIterator();
1731
1732                ObjectPvs newPvs;
1733
1734                while (pit.HasMoreEntries())
1735                {               
1736                        const ObjectPvsEntry &entry = pit.Next();
1737                        Intersectable *obj = entry.mObject;
1738
1739                        /*if (obj->Mailed(mail))
1740                        {
1741                                vc->GetPvs().RemoveSample(entry.mObject, Limits::Infinity))
1742                        }*/
1743                        if (!obj->Mailed(mail))
1744                        {
1745                                newPvs.AddSampleDirty(obj, entry.mData.mSumPdf);
1746                        }
1747                }
1748
1749                vc->SetPvs(newPvs);
1750        }
1751}
1752
1753
1754// TODO matt: implement this function for different storing methods
1755void ViewCellsTree::GetPvs(ViewCell *vc, ObjectPvs &pvs) const
1756{
1757        // pvs is stored in each cell => just return pvs
1758        if (mViewCellsStorage == PVS_IN_INTERIORS)
1759        {
1760                pvs = vc->GetPvs();
1761                return;
1762        }
1763
1764        ////////////////
1765        //-- pvs is not stored with the interiors => reconstruct
1766        ViewCell *root = vc;
1767       
1768        // add pvs from this view cell to root
1769        while (root->GetParent())
1770        {
1771                root = root->GetParent();
1772                pvs.MergeInPlace(root->GetPvs());
1773        }
1774
1775        // add pvs from leaves
1776        stack<ViewCell *> tstack;
1777        tstack.push(vc);
1778
1779        while (!tstack.empty())
1780        {
1781                vc = tstack.top();
1782                tstack.pop();
1783       
1784                // add newly found pvs to merged pvs
1785                pvs.MergeInPlace(vc->GetPvs());
1786               
1787                if (!vc->IsLeaf()) // interior cells: go down to leaf level
1788                {
1789                        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
1790                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1791
1792                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
1793                        {
1794                                tstack.push(*it);
1795                        }               
1796                }
1797        }
1798}
1799
1800
1801float ViewCellsTree::GetPvsCostForLeafStorage(ViewCell *vc) const
1802{
1803        // pvs is always stored directly in leaves
1804        if (vc->IsLeaf())
1805        {
1806                return vc->GetPvs().EvalPvsCost();
1807        }
1808       
1809        // interior nodes: pvs is either stored as a
1810        // scalar or has to be reconstructed from the leaves
1811        // the stored pvs size is the valid pvs size => just return scalar
1812        if (vc->mPvsSizeValid)
1813        {
1814                return vc->mPvsCost;
1815        }
1816       
1817        // if no valid pvs size stored as a scalar =>
1818        // compute current pvs size of interior from it's leaf nodes
1819        ViewCellContainer leaves;
1820        CollectLeaves(vc, leaves);
1821
1822        ViewCellContainer::const_iterator it, it_end = leaves.end();
1823
1824        ObjectPvs newPvs;
1825
1826        // sum up uniquely found intersectables
1827        for (it = leaves.begin(); it != it_end; ++ it)
1828        {
1829                newPvs.MergeInPlace((*it)->GetPvs());
1830        }
1831
1832        return newPvs.EvalPvsCost();
1833}
1834
1835
1836int ViewCellsTree::GetEntriesInPvsForLeafStorage(ViewCell *vc) const
1837{
1838        // pvs is always stored directly in leaves
1839        if (vc->IsLeaf())
1840        {
1841                return vc->GetPvs().GetSize();
1842        }
1843       
1844        // interior node
1845
1846        // interior nodes: pvs is either stored as a scalar or
1847        // has to be reconstructed from the leaves
1848
1849        // the stored pvs size is the valid pvs size => just return scalar
1850        if (vc->mPvsSizeValid)
1851        {
1852                return vc->mEntriesInPvs;
1853        }
1854       
1855        int pvsSize = 0;
1856
1857        // if no valid pvs size stored as a scalar =>
1858        // compute current pvs size of interior from it's leaf nodes
1859        ViewCellContainer leaves;
1860        CollectLeaves(vc, leaves);
1861
1862        ViewCellContainer::const_iterator it, it_end = leaves.end();
1863        Intersectable::NewMail();
1864
1865        // sum different intersectables
1866        for (it = leaves.begin(); it != it_end; ++ it)
1867        {
1868                ObjectPvsIterator oit = (*it)->GetPvs().GetIterator();
1869
1870                while (oit.HasMoreEntries())
1871                {
1872                        ObjectPvsEntry entry = oit.Next();
1873                        Intersectable *intersect = entry.mObject;
1874
1875                        if (!intersect->Mailed())
1876                        {
1877                                intersect->Mail();
1878                                ++ pvsSize;
1879                        }
1880                }
1881        }
1882
1883        return pvsSize;
1884}
1885
1886
1887float ViewCellsTree::GetPvsCostForCompressedStorage(ViewCell *vc) const
1888{
1889        float pvsCost = 0;
1890
1891        /////////////
1892        //-- compressed pvs
1893
1894        // the stored pvs size is the valid pvs size => just return scalar
1895        if (vc->mPvsSizeValid)
1896        {
1897                pvsCost = vc->mPvsCost;
1898        }
1899
1900        // if no pvs size stored, compute new one
1901        ViewCell *root = vc;
1902       
1903        // also add pvs from this view cell to root
1904        while (root->GetParent())
1905        {
1906                root = root->GetParent();
1907       
1908                // matt: bug! must evaluate kd pvss also
1909                pvsCost += CountPvsContribution(root);
1910        }
1911
1912        stack<ViewCell *> tstack;
1913        tstack.push(vc);
1914
1915        while (!tstack.empty())
1916        {
1917                vc = tstack.top();
1918                tstack.pop();
1919
1920                // matt: bug! must evaluate kd pvss also
1921                pvsCost += CountPvsContribution(vc);
1922
1923                if (!vc->IsLeaf())
1924                {
1925                        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
1926                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1927
1928                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
1929                        {
1930                                tstack.push(*it);
1931                        }               
1932                }
1933        }
1934
1935        return pvsCost;
1936}
1937
1938
1939int ViewCellsTree::GetEntriesInPvsForCompressedStorage(ViewCell *vc) const
1940{
1941        int pvsSize = 0;
1942
1943        /////////////////
1944        //-- compressed pvs
1945
1946        // the stored pvs size is the valid pvs size => just return scalar
1947        if (vc->mPvsSizeValid)
1948        {
1949                pvsSize = vc->mEntriesInPvs;
1950        }
1951
1952        // if no pvs size stored, compute new one
1953        ViewCell *root = vc;
1954       
1955        // also add pvs from this view cell to root
1956        while (root->GetParent())
1957        {
1958                root = root->GetParent();
1959                // count the pvs entries different from the already found ones 
1960                pvsSize += CountPvsContribution(root);
1961        }
1962
1963        stack<ViewCell *> tstack;
1964        tstack.push(vc);
1965
1966        while (!tstack.empty())
1967        {
1968                vc = tstack.top();
1969                tstack.pop();
1970       
1971                // count the pvs entries different from the already found ones 
1972                pvsSize += CountPvsContribution(vc);
1973
1974                if (!vc->IsLeaf())
1975                {
1976                        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
1977
1978                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1979
1980                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
1981                        {
1982                                tstack.push(*it);
1983                        }               
1984                }
1985        }
1986
1987        return pvsSize;
1988}
1989
1990
1991float ViewCellsTree::GetPvsCost(ViewCell *vc) const
1992{
1993        float pvsCost = 0;
1994        Intersectable::NewMail();
1995
1996        ////////////////////////////////////////////////
1997        // for interiors, pvs can be stored using different methods
1998        //
1999
2000        switch (mViewCellsStorage)
2001        {
2002        case PVS_IN_LEAVES:
2003                // pvs is stored only in leaves
2004                pvsCost = GetPvsCostForLeafStorage(vc);                 
2005                break;
2006        case COMPRESSED:
2007                pvsCost = GetPvsCostForCompressedStorage(vc);
2008                break;
2009        case PVS_IN_INTERIORS:
2010        default:
2011                // pvs is stored consistently in the tree up
2012                //to the root just return pvs size
2013                pvsCost = vc->GetPvs().EvalPvsCost();   
2014                break;
2015        }
2016
2017        return pvsCost; 
2018}
2019
2020
2021int ViewCellsTree::GetPvsEntries(ViewCell *vc) const
2022{
2023        int pvsSize = 0;
2024
2025        Intersectable::NewMail();
2026
2027        ////////////////////////////////////////////////
2028        // for interiors, pvs can be stored using different methods
2029       
2030        switch (mViewCellsStorage)
2031        {
2032        case PVS_IN_LEAVES:
2033                {
2034                        //-- store pvs only in leaves
2035                        pvsSize = GetEntriesInPvsForLeafStorage(vc);
2036                        break;
2037                }
2038        case COMPRESSED:
2039                {
2040                        pvsSize = GetEntriesInPvsForCompressedStorage(vc);
2041                        break;
2042                }
2043        case PVS_IN_INTERIORS:
2044        default:
2045                // pvs is stored consistently in the tree up to the root
2046                // just return pvs size
2047                pvsSize = vc->GetPvs().GetSize();       
2048                break;
2049        }
2050
2051        return pvsSize; 
2052}
2053
2054
2055float ViewCellsTree::GetMemoryCost(ViewCell *vc) const
2056{
2057        return (float)CountStoredPvsEntries(vc) * ObjectPvs::GetEntrySize();
2058}
2059
2060//#if HAS_TO_BE_REDONE
2061int ViewCellsTree::CountStoredPvsEntries(ViewCell *root) const
2062{
2063        int pvsSize = root->GetPvs().GetSize();
2064
2065        // recursivly count leaves
2066        if (!root->IsLeaf())
2067        {
2068                ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(root);
2069
2070                ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
2071
2072                for (it = interior->mChildren.begin(); it != it_end; ++ it)
2073                {
2074                        pvsSize += CountStoredPvsEntries(*it);
2075                }
2076        }
2077
2078        return pvsSize;         
2079}
2080//#endif
2081
2082int ViewCellsTree::ViewCellsStorage() const
2083{
2084        return mViewCellsStorage;
2085}
2086
2087
2088ViewCell *ViewCellsTree::GetActiveViewCell(ViewCellLeaf *vc) const
2089{
2090        return vc->GetActiveViewCell();
2091}
2092
2093
2094void ViewCellsTree::PropagatePvs(ViewCell *root)
2095{       
2096        ViewCell *viewCell = root;
2097
2098        // propagate pvs up
2099        while (viewCell->GetParent())
2100        {
2101                ObjectPvs mergedPvs;
2102                viewCell->GetParent()->GetPvs().MergeInPlace(root->GetPvs());
2103
2104                viewCell = viewCell->GetParent();
2105        }
2106
2107        if (root->IsLeaf())
2108                return;
2109
2110        // propagate pvs to the leaves
2111        stack<ViewCell *> tstack;
2112        tstack.push(root);
2113
2114        while (!tstack.empty())
2115        {
2116                ViewCell *viewCell = tstack.top();
2117                tstack.pop();
2118
2119                if (viewCell != root)
2120                {
2121                        viewCell->GetPvs().MergeInPlace(root->GetPvs());
2122                }
2123
2124                if (!viewCell->IsLeaf())
2125                {
2126                        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(viewCell);
2127
2128                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
2129
2130                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
2131                        {
2132                                tstack.push(*it);
2133                        }
2134                }
2135        }
2136}
2137
2138
2139void ViewCellsTree::AssignRandomColors()
2140{
2141        TraversalQueue tqueue;
2142        tqueue.push(mRoot);
2143       
2144        mRoot->SetColor(RandomColor(0.3f, 1.0f));
2145       
2146        while (!tqueue.empty())
2147        {
2148                ViewCell *vc = tqueue.top();
2149                tqueue.pop();
2150
2151                // save the view cells if it is a leaf or if enough view cells
2152                // have already been traversed because of the priority queue,
2153                // this will be the optimal set of v
2154                if (!vc->IsLeaf())
2155                {       
2156                        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
2157                 
2158                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
2159                 
2160                        float maxProbability = -1.0f;
2161                 
2162                        ViewCell *maxViewCell = NULL;
2163                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
2164                        {
2165                                ViewCell *v = *it;
2166                         
2167                                // set random color
2168                                v->SetColor(RandomColor(0.3f, 1.0f));
2169                         
2170                                if (v->GetVolume() > maxProbability)
2171                                {
2172                                        maxProbability = v->GetVolume();
2173                                        maxViewCell = v;
2174                                }
2175
2176                                if (maxViewCell)
2177                                {
2178                                        maxViewCell->SetColor(vc->GetColor());
2179                                }
2180                               
2181                                tqueue.push(v);
2182                        }
2183                }       
2184        }
2185}
2186
2187
2188/** Get costs resulting from each merge step.
2189*/
2190void ViewCellsTree::GetCostFunction(vector<float> &costFunction)
2191{
2192        TraversalQueue tqueue;
2193        tqueue.push(mRoot);
2194
2195        int numViewCells = 1;
2196
2197        const float vol = mViewCellsManager->GetViewSpaceBox().GetVolume();
2198        const float rootPvs = GetPvsCost(mRoot);
2199       
2200        float totalRenderCost;
2201
2202        float totalPvsCost = rootPvs;
2203        totalRenderCost = (float)rootPvs;
2204
2205        costFunction.push_back(totalRenderCost);
2206
2207        //-- go through tree in the order of render cost decrease
2208        //-- which is the same order as the view cells were merged
2209        //-- or the reverse order of subdivision for subdivision-only
2210        //-- view cell hierarchies.
2211
2212        while (!tqueue.empty())
2213        {
2214                ViewCell *vc = tqueue.top();
2215                tqueue.pop();
2216
2217                if (!vc->IsLeaf())
2218                {       
2219                        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
2220
2221                        const float parentCost = GetPvsCost(interior);
2222                        const float parentExpCost = parentCost * interior->GetVolume();
2223
2224                        -- numViewCells;
2225
2226                        float childExpCost = 0;
2227                        float childCost = 0;
2228                       
2229                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
2230
2231                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
2232                        {
2233                                ViewCell *vc = *it;
2234
2235                                const float pvsCost = GetPvsCost(vc);
2236                               
2237                                childExpCost += (float) pvsCost * vc->GetVolume();
2238                                childCost += pvsCost;
2239                               
2240                                tqueue.push(vc);
2241                                ++ numViewCells;
2242                        }
2243
2244                        // update stats for this view cell
2245                        const float costDecr = (parentExpCost - childExpCost) / vol;
2246                        totalRenderCost -= costDecr;
2247                       
2248                        costFunction.push_back(totalRenderCost);
2249                }
2250        }
2251}
2252
2253
2254/** Get storage costs resulting from each merge step.
2255*/
2256void ViewCellsTree::GetStorageFunction(vector<int> &storageFunction)
2257{
2258        TraversalQueue tqueue;
2259        tqueue.push(mRoot);
2260
2261        int numViewCells = 1;
2262
2263        const float vol = mViewCellsManager->GetViewSpaceBox().GetVolume();
2264        const int rootEntries = GetPvsEntries(mRoot);
2265
2266        int entriesInPvs = rootEntries;
2267    const int entryStorage = sizeof(PvsData) + sizeof(int); // one entry into the pvs
2268
2269        storageFunction.push_back(rootEntries);
2270
2271        ////////////
2272        //-- go through tree in the order of render cost decrease
2273        //-- which is the same order as the view cells were merged
2274        //-- or the reverse order of subdivision for subdivision-only
2275        //-- view cell hierarchies.
2276
2277        while (!tqueue.empty())
2278        {
2279                ViewCell *vc = tqueue.top();
2280                tqueue.pop();
2281
2282                if (!vc->IsLeaf())
2283                {       
2284                        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
2285
2286                        const float parentPvsCost = GetPvsCost(interior);
2287                        const int parentPvsEntries = GetPvsEntries(interior);
2288            const float parentExpCost = (float)parentPvsCost * interior->GetVolume();
2289
2290                        float childExpCost = 0;
2291                        int childPvs = 0;
2292                        int childPvsEntries = 0;
2293
2294                        -- numViewCells;
2295
2296                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
2297
2298                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
2299                        {
2300                                ViewCell *vc = *it;
2301
2302                                const int pvsEntries = GetPvsEntries(vc);
2303                                childPvsEntries += pvsEntries;
2304
2305                                tqueue.push(vc);
2306                                ++ numViewCells;
2307                        }
2308
2309                        // update stats for this view cell
2310                        const float costDecr = (parentExpCost - childExpCost) / vol;
2311
2312                        entriesInPvs += childPvsEntries - parentPvsEntries;
2313
2314                        const int storageCost = entriesInPvs * entryStorage;
2315                        storageFunction.push_back(storageCost);
2316                }
2317        }
2318}
2319
2320
2321
2322void ViewCellsTree::UpdateViewCellsStats(ViewCell *vc,
2323                                                                                 ViewCellsStatistics &vcStat)
2324{
2325        ++ vcStat.viewCells;
2326               
2327        const float pvsCost = GetPvsCost(vc);
2328
2329        vcStat.pvsCost += pvsCost;
2330
2331        if (pvsCost < Limits::Small)
2332                ++ vcStat.emptyPvs;
2333
2334        if (pvsCost > vcStat.maxPvs)
2335                vcStat.maxPvs = pvsCost;
2336
2337        if (pvsCost < vcStat.minPvs)
2338                vcStat.minPvs = pvsCost;
2339
2340        if (!vc->GetValid())
2341                ++ vcStat.invalid;
2342}
2343
2344
2345bool ViewCellsTree::Export(OUT_STREAM &stream, const bool exportPvs)
2346{
2347        // export recursivly all view cells from the root
2348        ExportViewCell(mRoot, stream, exportPvs);
2349
2350        return true;
2351}
2352
2353
2354void ViewCellsTree::CreateUniqueViewCellsIds()
2355{
2356        stack<ViewCell *> tstack;
2357
2358        int currentId = 0;
2359
2360        tstack.push(mRoot);
2361
2362        while (!tstack.empty())
2363        {
2364                ViewCell *vc = tstack.top();
2365                tstack.pop();
2366
2367                if (vc->GetId() != -1) // out of bounds
2368                        vc->SetId(currentId ++);
2369
2370                if (!vc->IsLeaf())
2371                {
2372                        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
2373                       
2374                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
2375                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
2376                        {
2377                                tstack.push(*it);
2378                        }
2379                }
2380        }
2381}
2382
2383
2384void ViewCellsTree::ExportPvs(ViewCell *viewCell, OUT_STREAM &stream)
2385{
2386        ObjectPvsIterator it = viewCell->GetPvs().GetIterator();
2387
2388        while (it.HasMoreEntries())
2389        {
2390                ObjectPvsEntry entry = it.Next();
2391                Intersectable *obj = entry.mObject;
2392
2393                // hack: just output full pvs
2394                if (0 && (obj->Type() == Intersectable::BVH_INTERSECTABLE))
2395                {
2396                        ObjectContainer objects;
2397                        BvhNode *node = dynamic_cast<BvhNode *>(obj);
2398                        node->CollectObjects(objects);
2399               
2400                        ObjectContainer::const_iterator oit, oit_end = objects.end();
2401                        for (oit = objects.begin(); oit != oit_end; ++ oit)
2402                        {
2403                                stream << (*oit)->GetId() << " ";
2404                        }
2405                }
2406                else
2407                {
2408                        stream << entry.mObject->GetId() << " ";
2409                }
2410        }
2411}
2412
2413
2414void ViewCellsTree::ExportViewCell(ViewCell *viewCell,
2415                                                                   OUT_STREAM &stream,
2416                                                                   const bool exportPvs)
2417{
2418        if (viewCell->IsLeaf())
2419        {
2420                stream << "<Leaf ";
2421                stream << "id=\"" << viewCell->GetId() << "\" ";
2422                stream << "active=\"" << dynamic_cast<ViewCellLeaf *>(viewCell)->GetActiveViewCell()->GetId() << "\" ";
2423                stream << "mergecost=\"" << viewCell->GetMergeCost() << "\" ";
2424                stream << "pvs=\"";
2425               
2426                //-- export pvs, i.e., the ids of the objects in the pvs
2427                if (exportPvs)
2428                {
2429                        ExportPvs(viewCell, stream);
2430                }
2431                stream << "\" />" << endl;
2432        }
2433        else
2434        {
2435                ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(viewCell);
2436       
2437                stream << "<Interior ";
2438                stream << "id=\"" << viewCell->GetId() << "\" ";
2439                stream << "mergecost=\"" << viewCell->GetMergeCost() << "\" ";
2440                stream << "pvs=\"";
2441
2442                // NOTE: do not export pvss for interior view cells because
2443                // they can be completely reconstructed from the leaf pvss
2444                // on the other hand: we could store a tag with the compression scheme,
2445        // then some scheme were pvs is in the interiors could be used
2446                if (0) ExportPvs(viewCell, stream);
2447               
2448                stream << "\" >" << endl;
2449
2450                //-- recursivly export child view cells
2451                ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
2452
2453                for (it = interior->mChildren.begin(); it != it_end; ++ it)
2454                {
2455                        ExportViewCell(*it, stream, exportPvs);
2456                }
2457
2458                stream << "</Interior>" << endl;
2459        }
2460}
2461
2462
2463void ViewCellsTree::ResetPvs()
2464{
2465        stack<ViewCell *> tstack;
2466
2467        tstack.push(mRoot);
2468
2469        while (!tstack.empty())
2470        {
2471                ViewCell *vc = tstack.top();
2472                tstack.pop();
2473
2474                vc->GetPvs().Clear();
2475               
2476                if (!vc->IsLeaf())
2477                {
2478                        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
2479                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
2480
2481                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
2482                        {
2483                                tstack.push(*it);
2484                        }
2485                }
2486        }
2487}
2488
2489
2490void ViewCellsTree::SetViewCellsManager(ViewCellsManager *vcm)
2491{
2492        mViewCellsManager = vcm;
2493}
2494
2495
2496void ViewCellsTree::SetActiveSetToLeaves()
2497{
2498        // todo
2499}
2500
2501
2502
2503/**************************************************************************/
2504/*                     MergeCandidate implementation                      */
2505/**************************************************************************/
2506
2507
2508MergeCandidate::MergeCandidate(ViewCell *l, ViewCell *r):
2509mRenderCost(0),
2510mDeviationIncr(0),
2511mLeftViewCell(l),
2512mRightViewCell(r),
2513mInitialLeftViewCell(l),
2514mInitialRightViewCell(r)
2515{
2516        //EvalMergeCost();
2517}
2518
2519
2520void MergeCandidate::SetRightViewCell(ViewCell *v)
2521{
2522        mRightViewCell = v;
2523}
2524
2525
2526void MergeCandidate::SetLeftViewCell(ViewCell *v)
2527{
2528        mLeftViewCell = v;
2529}
2530
2531
2532ViewCell *MergeCandidate::GetRightViewCell() const
2533{
2534        return mRightViewCell;
2535}
2536
2537
2538ViewCell *MergeCandidate::GetLeftViewCell() const
2539{
2540        return mLeftViewCell;
2541}
2542
2543
2544ViewCell *MergeCandidate::GetInitialRightViewCell() const
2545{
2546        return mInitialRightViewCell;
2547}
2548
2549
2550ViewCell *MergeCandidate::GetInitialLeftViewCell() const
2551{
2552        return mInitialLeftViewCell;
2553}
2554
2555
2556bool MergeCandidate::IsValid() const
2557{
2558        // if one has a parent, it was already merged
2559        return !(mLeftViewCell->GetParent() || mRightViewCell->GetParent());
2560}
2561
2562
2563float MergeCandidate::GetRenderCost() const
2564{
2565        return mRenderCost;
2566}
2567
2568
2569float MergeCandidate::GetDeviationIncr() const
2570{
2571        return mDeviationIncr;
2572}
2573
2574
2575float MergeCandidate::GetMergeCost() const
2576{
2577        return mRenderCost * sRenderCostWeight +
2578                   mDeviationIncr * (1.0f - sRenderCostWeight);
2579}
2580
2581
2582
2583/************************************************************************/
2584/*                    MergeStatistics implementation                    */
2585/************************************************************************/
2586
2587
2588void MergeStatistics::Print(ostream &app) const
2589{
2590        app << "===== Merge statistics ===============\n";
2591
2592        app << setprecision(4);
2593
2594        app << "#N_CTIME ( Overall time [s] )\n" << Time() << " \n";
2595
2596        app << "#N_CCTIME ( Collect candidates time [s] )\n" << collectTime * 1e-3f << " \n";
2597
2598        app << "#N_MTIME ( Merge time [s] )\n" << mergeTime * 1e-3f << " \n";
2599
2600        app << "#N_NODES ( Number of nodes before merge )\n" << nodes << "\n";
2601
2602        app << "#N_CANDIDATES ( Number of merge candidates )\n" << candidates << "\n";
2603
2604        app << "#N_MERGEDSIBLINGS ( Number of merged siblings )\n" << siblings << "\n";
2605
2606        app << "#OVERALLCOST ( overall merge cost )\n" << overallCost << "\n";
2607
2608        app << "#N_MERGEDNODES ( Number of merged nodes )\n" << merged << "\n";
2609
2610        app << "#MAX_TREEDIST ( Maximal distance in tree of merged leaves )\n" << maxTreeDist << "\n";
2611
2612        app << "#AVG_TREEDIST ( Average distance in tree of merged leaves )\n" << AvgTreeDist() << "\n";
2613
2614        app << "#EXPECTEDCOST ( expected render cost )\n" << expectedRenderCost << "\n";
2615
2616        app << "#DEVIATION ( deviation )\n" << deviation << "\n";
2617
2618        app << "#HEURISTICS ( heuristics )\n" << heuristics << "\n";
2619       
2620
2621        app << "===== END OF BspTree statistics ==========\n";
2622}
2623
2624
2625}
Note: See TracBrowser for help on using the repository browser.