source: trunk/VUT/GtpVisibilityPreprocessor/src/ViewCell.cpp @ 581

Revision 581, 34.3 KB checked in by mattausch, 18 years ago (diff)

added function for pvs compression
Line 
1#include "ViewCell.h"
2#include "Mesh.h"
3#include "Intersectable.h"
4#include "MeshKdTree.h"
5#include "Triangle3.h"
6#include "common.h"
7#include "Environment.h"
8#include "ViewCellsManager.h"
9#include "Exporter.h"
10
11#include <time.h>
12#include <iomanip>
13#include <stack>
14
15
16
17template <typename T> class myless
18{
19public:
20       
21        //bool operator() (HierarchyNode *v1, HierarchyNode *v2) const
22        bool operator() (T v1, T v2) const
23        {
24                return (v1->GetTimeStamp() < v2->GetTimeStamp());
25        }
26};
27
28
29typedef priority_queue<ViewCell *, vector<ViewCell *>, myless<vector<ViewCell *>::value_type> > TraversalQueue;
30
31int ViewCell::sMailId = 21843194198;
32int ViewCell::sReservedMailboxes = 1;
33
34//int upperPvsLimit = 120;
35//int lowerPvsLimit = 5;
36
37float MergeCandidate::sRenderCostWeight = 0;
38
39
40// pvs penalty can be different from pvs size
41inline float EvalPvsPenalty(const int pvs,
42                                                        const int lower,
43                                                        const int upper)
44{
45        // clamp to minmax values
46        if (pvs < lower)
47                return (float)lower;
48        if (pvs > upper)
49                return (float)upper;
50
51        return (float)pvs;
52}
53
54
55int ComputeMergedPvsSize(const ObjectPvs &pvs1, const ObjectPvs &pvs2)
56{
57        int pvs = pvs1.GetSize();
58
59        // compute new pvs size
60        ObjectPvsMap::const_iterator it, it_end =  pvs1.mEntries.end();
61
62        Intersectable::NewMail();
63
64        for (it = pvs1.mEntries.begin(); it != it_end; ++ it)
65        {
66                (*it).first->Mail();
67        }
68
69        it_end = pvs2.mEntries.end();
70
71        for (it = pvs2.mEntries.begin(); it != it_end; ++ it)
72        {
73                Intersectable *obj = (*it).first;
74                if (!obj->Mailed())
75                        ++ pvs;
76        }
77
78        return pvs;
79}
80
81
82ViewCell::ViewCell():
83MeshInstance(NULL),
84mPiercingRays(0),
85mArea(-1),
86mVolume(-1),
87mValid(true),
88mParent(NULL),
89mTimeStamp(0)
90{
91}
92
93ViewCell::ViewCell(Mesh *mesh):
94MeshInstance(mesh),
95mPiercingRays(0),
96mArea(-1),
97mVolume(-1),
98mValid(true),
99mParent(NULL),
100mTimeStamp(0)
101{
102}
103
104
105const ObjectPvs &ViewCell::GetPvs() const
106{
107        return mPvs;
108}
109
110ObjectPvs &ViewCell::GetPvs()
111{
112        return mPvs;
113}
114
115
116int ViewCell::Type() const
117{
118        return VIEW_CELL;
119}
120
121
122float ViewCell::GetVolume() const
123{
124        return mVolume;
125}
126
127
128void ViewCell::SetVolume(float volume)
129{
130        mVolume = volume;
131}
132
133
134void ViewCell::SetMesh(Mesh *mesh)
135{
136        mMesh = mesh;
137}
138
139
140void ViewCell::UpdateViewCellsStats(ViewCellsStatistics &vcStat)
141{
142        ++ vcStat.viewCells;
143               
144        const int pvsSize = mPvs.GetSize();
145
146        vcStat.pvs += pvsSize;
147
148        if (pvsSize == 0)
149                ++ vcStat.emptyPvs;
150
151        if (pvsSize > vcStat.maxPvs)
152                vcStat.maxPvs = pvsSize;
153
154        if (pvsSize < vcStat.minPvs)
155                vcStat.minPvs = pvsSize;
156
157        if (!mValid)
158                ++ vcStat.invalid;
159}
160
161
162float ViewCell::GetArea() const
163{
164        return mArea;
165}
166
167
168void ViewCell::SetArea(float area)
169{
170        mArea = area;
171}
172
173
174void ViewCell::SetValid(const bool valid)
175{
176        mValid = valid;
177}
178
179
180bool ViewCell::GetValid() const
181{
182        return mValid;
183}
184
185
186/*bool ViewCell::IsLeaf() const
187{
188        return true;
189}*/
190
191
192void ViewCell::SetParent(ViewCellInterior *parent)
193{
194        mParent = parent;
195}
196
197
198bool ViewCell::IsRoot() const
199{
200        return !mParent;
201}
202
203
204ViewCellInterior *ViewCell::GetParent() const
205{
206        return mParent;
207}
208
209
210void ViewCell::SetTimeStamp(const int timeStamp)
211{
212        mTimeStamp = timeStamp;
213}
214
215
216int ViewCell::GetTimeStamp() const
217{
218        return mTimeStamp;
219}
220
221
222
223/************************************************************************/
224/*                class ViewCellInterior implementation                 */
225/************************************************************************/
226
227
228ViewCellInterior::ViewCellInterior()
229{
230}
231
232
233ViewCellInterior::~ViewCellInterior()
234{
235        ViewCellContainer::const_iterator it, it_end = mChildren.end();
236
237        for (it = mChildren.begin(); it != it_end; ++ it)
238                delete (*it);
239}
240
241
242ViewCellInterior::ViewCellInterior(Mesh *mesh):
243ViewCell(mesh)
244{
245}
246
247
248bool ViewCellInterior::IsLeaf() const
249{
250        return false;
251}
252
253
254void ViewCellInterior::SetupChildLink(ViewCell *l)
255{
256    mChildren.push_back(l);
257    l->mParent = this;
258}
259
260
261
262/************************************************************************/
263/*                class ViewCellsStatistics implementation              */
264/************************************************************************/
265
266
267
268
269void ViewCellsStatistics::Print(ostream &app) const
270{
271        app << "=========== View Cells Statistics ===============\n";
272
273        app << setprecision(4);
274
275        //app << "#N_CTIME  ( Construction time [s] )\n" << Time() << " \n";
276
277        app << "#N_OVERALLPVS ( objects in PVS )\n" << pvs << endl;
278
279        app << "#N_PMAXPVS ( largest PVS )\n" << maxPvs << endl;
280
281        app << "#N_PMINPVS ( smallest PVS )\n" << minPvs << endl;
282
283        app << "#N_PAVGPVS ( average PVS )\n" << AvgPvs() << endl;
284
285        app << "#N_PEMPTYPVS ( view cells with empty PVS )\n" << emptyPvs << endl;
286
287        app << "#N_VIEWCELLS ( number of view cells)\n" << viewCells << endl;
288
289        app << "#N_AVGLEAVES (average number of leaves per view cell )\n" << AvgLeaves() << endl;
290
291        app << "#N_MAXLEAVES ( maximal number of leaves per view cell )\n" << maxLeaves << endl;
292       
293        app << "#N_INVALID ( number of invalid view cells )\n" << invalid << endl;
294
295        app << "========== End of View Cells Statistics ==========\n";
296}
297
298
299/*************************************************************************/
300/*                    class ViewCellsTree implementation                 */
301/*************************************************************************/
302
303
304ViewCellsTree::ViewCellsTree(ViewCellsManager *vcm):
305mRoot(NULL),
306mUseAreaForPvs(false),
307mViewCellsManager(vcm)
308{
309        environment->GetBoolValue("ViewCells.Visualization.exportMergedViewCells", mExportMergedViewCells);
310
311        //-- merge options
312        environment->GetFloatValue("ViewCells.PostProcess.renderCostWeight", mRenderCostWeight);
313        environment->GetIntValue("ViewCells.PostProcess.minViewCells", mMergeMinViewCells);
314        environment->GetFloatValue("ViewCells.PostProcess.maxCostRatio", mMergeMaxCostRatio);
315       
316        MergeCandidate::sRenderCostWeight = mRenderCostWeight;
317
318        mStats.open("mergeStats.log");
319}
320
321
322int ViewCellsTree::GetSize(ViewCell *vc) const
323{
324        int vcSize = 0;
325
326        stack<ViewCell *> tstack;
327
328        tstack.push(vc);
329
330        while (!tstack.empty())
331        {
332                ViewCell *vc = tstack.top();
333                tstack.pop();
334
335                if (vc->IsLeaf())
336                {
337                        ++ vcSize;
338                }
339                else
340                {
341                        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
342                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
343                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
344                                tstack.push(*it);
345                       
346                }
347        }
348
349        return vcSize;
350}
351
352
353void ViewCellsTree::CollectLeaves(ViewCell *vc, ViewCellContainer &leaves) const
354{
355        stack<ViewCell *> tstack;
356
357        tstack.push(vc);
358
359        while (!tstack.empty())
360        {
361                ViewCell *vc = tstack.top();
362                tstack.pop();
363
364                if (vc->IsLeaf())
365                {
366                        leaves.push_back(vc);
367                }
368                else
369                {
370                        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
371                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
372                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
373                                tstack.push(*it);
374                       
375                }
376        }
377}
378
379
380ViewCellsTree::~ViewCellsTree()
381{
382        DEL_PTR(mRoot);
383}
384
385
386int ViewCellsTree::ConstructMergeTree(const VssRayContainer &rays,
387                                                                          const ObjectContainer &objects)
388{
389        // number of view cells equals the number of leaves
390        // (without the invalid ones )
391        //mNumViewCells = mBspStats.Leaves();//- mBspStats.invalidLeaves;
392        mNumViewCells = (int)mViewCellsManager->GetViewCells().size();
393
394        float variance = 0;
395        int totalPvs = 0;
396        float totalCost = 0;
397
398        //-- compute statistics values of initial view cells
399        mViewCellsManager->EvaluateRenderStatistics(totalCost,
400                                                                                                mExpectedCost,
401                                                                                                mDeviation,
402                                                                                                variance,
403                                                                                                totalPvs,
404                                                                                                mAvgRenderCost);
405
406
407        //-- fill merge queue
408        vector<MergeCandidate> candidates;
409
410        mViewCellsManager->CollectMergeCandidates(rays, candidates);
411        while(!candidates.empty())
412        {
413                MergeCandidate mc = candidates.back();
414                candidates.pop_back();
415                EvalMergeCost(mc);
416                mMergeQueue.push(mc);
417        }
418
419        Debug << "************************* merge ***********************************" << endl; 
420        Debug << "deviation: " << mDeviation << endl;
421        Debug << "avg render cost: " << mAvgRenderCost << endl;
422        Debug << "expected cost: " <<mExpectedCost << endl;
423
424
425        ViewCellsManager::PvsStatistics pvsStats;
426        mViewCellsManager->GetPvsStatistics(pvsStats);
427
428        static float expectedValue = pvsStats.avgPvs;
429       
430        // the current view cells are kept in this container
431        // we start with the current view cells from the
432        // view cell manager. They will change with
433        // subsequent merges
434        ViewCellContainer &viewCells = mViewCellsManager->GetViewCells();
435
436
437        ViewCell::NewMail();
438
439        MergeStatistics mergeStats;
440        mergeStats.Start();
441       
442        long startTime = GetTime();
443
444        mergeStats.collectTime = TimeDiff(startTime, GetTime());
445        mergeStats.candidates = (int)mMergeQueue.size();
446        startTime = GetTime();
447
448        // frequency stats are updated
449        const int statsOut = 100;
450
451        // passes are needed for statistics, because we don't want to record
452        // every merge
453        int pass = 0;
454        int mergedPerPass = 0;
455        float realExpectedCost = mExpectedCost;
456        float realAvgRenderCost = mAvgRenderCost;
457        int realNumViewCells = mNumViewCells;
458       
459        // maximal ratio of old expected render cost to expected render
460        // when the the render queue has to be reset.
461        float avgCostMaxDeviation;
462        int maxMergesPerPass;
463        int numActiveViewCells = 0;
464
465        environment->GetIntValue("ViewCells.PostProcess.maxMergesPerPass", maxMergesPerPass);
466        environment->GetFloatValue("ViewCells.PostProcess.avgCostMaxDeviation", avgCostMaxDeviation);
467
468        cout << "actual merge starts now ... " << endl;
469       
470        //ResetMergeQueue();
471
472        //-- use priority queue to merge leaf pairs
473
474        while (!mMergeQueue.empty() && (realNumViewCells > mMergeMinViewCells))
475        {
476                //-- reset merge queue if the ratio of current expected cost / real expected cost
477                //   too small or after a given number of merges
478                if ((mergedPerPass > maxMergesPerPass) ||
479                        (avgCostMaxDeviation > mAvgRenderCost / realAvgRenderCost))
480                {
481                        Debug << "************ reset queue *****************\n"
482                                  << "ratios: " << avgCostMaxDeviation
483                                  << " real avg render cost " << realAvgRenderCost << " average render cost " << mAvgRenderCost
484                                  << " merged per pass : " << mergedPerPass << " of maximal " << maxMergesPerPass << endl;
485
486                        Debug << "Values before reset: " 
487                                  << " erc: " << mExpectedCost
488                                  << " avgrc: " << mAvgRenderCost
489                                  << " dev: " << mDeviation << endl;
490       
491                        // adjust render cost
492                        ++ pass;
493
494                        mergedPerPass = 0;
495                        mExpectedCost = realExpectedCost;
496                        mAvgRenderCost = realAvgRenderCost;
497                        mNumViewCells = realNumViewCells;
498                       
499                        const int numActiveViewCells = UpdateMergedViewCells(viewCells);
500
501                    ResetMergeQueue();
502
503                       
504                        Debug << "Values after reset: " 
505                                  << " erc: " << mExpectedCost
506                                  << " avg: " << mAvgRenderCost
507                                  << " dev: " << mDeviation << endl;
508
509                        if (mExportMergedViewCells)
510                        {
511                                ExportMergedViewCells(viewCells, objects, numActiveViewCells);
512                        }
513                }
514
515#ifdef _DEBUG
516                Debug << "abs mergecost: " << mMergeQueue.top().GetMergeCost() <<
517                          << " rel mergecost: " << mMergeQueue.top().GetRenderCost() / mExpectedCost <<
518                          << " max ratio: " << mMergeMaxCostRatio << endl
519                          << " expected value: " << realExpectedCost << endl;
520#endif
521
522       
523                MergeCandidate mc = mMergeQueue.top();
524                mMergeQueue.pop();
525       
526                // both view cells equal!
527                if (mc.mLeftViewCell == mc.mRightViewCell)
528                        continue;
529
530                if (mc.IsValid())
531                {
532                        ViewCell::NewMail();
533                                               
534                        -- realNumViewCells;
535                        ++ mergeStats.merged;
536                        ++ mergedPerPass;
537
538
539                        //-- update statistical values
540
541                        // total render cost and deviation has changed
542                        // real expected cost will be larger than expected cost used for the
543                        // cost heuristics, but cannot recompute costs on each increase of the
544                        // expected cost
545
546                        totalCost += mc.GetRenderCost();
547                        mDeviation += mc.GetDeviationIncr();
548                                               
549                        realExpectedCost = totalCost / (float)realNumViewCells;
550                       
551                        const float currentMergeCost = mc.GetMergeCost();
552
553                        // merge the view cells of leaf1 and leaf2
554                        int pvsDiff;
555                        ViewCellInterior *mergedVc =
556                                MergeViewCells(mc.mLeftViewCell, mc.mRightViewCell, pvsDiff);
557
558                        totalPvs += pvsDiff;
559                        // set timestamp
560                        mergedVc->SetTimeStamp(mergeStats.merged);
561
562                        realAvgRenderCost = (float)totalPvs / (float)realNumViewCells;
563#if VC_HISTORY
564                        if (mc.mLeftViewCell->IsSibling(mc.mRightViewCell))
565                                ++ mergeStats.siblings;
566#endif
567                        if (((mergeStats.merged % statsOut) == 0) ||
568                                (realNumViewCells == mMergeMinViewCells))
569                        {
570                                cout << "merged " << mergeStats.merged << " view cells" << endl;
571
572                                mStats
573                                        << "#Pass\n" << pass << endl
574                                        << "#Merged\n" << mergeStats.merged << endl
575                                        << "#Viewcells\n" << realNumViewCells << endl
576                                        << "#CurrentCost\n" << currentMergeCost << endl
577                                        << "#RelativeCost\n" << currentMergeCost / mOverallCost << endl
578                                        << "#CurrentPvs\n" << mc.GetLeftViewCell()->GetPvs().GetSize() << endl
579                                        << "#MergedSiblings\n" << mergeStats.siblings << endl
580                                        << "#AvgTreeDist\n" << mergeStats.AvgTreeDist() << endl
581                                        << "#UsedExpectedCost\n" << mExpectedCost << endl
582                                        << "#RealExpectedCost\n" << realExpectedCost << endl
583                                        << "#RealAvgRenderCost\n" << realAvgRenderCost << endl
584                                        << "#AvgRenderCost\n" << mAvgRenderCost << endl
585                                        << "#expectedCostRatio\n" << mExpectedCost / realExpectedCost << endl
586                                        << "#Deviation\n" << mDeviation / (float)realNumViewCells << endl
587                                        << "#TotalDeviation\n" << mDeviation<< endl;
588                        }
589                }
590                else
591                {
592                        // merge candidate not valid, because one of the leaves was already
593                        // merged with another one => validate and reinsert into queue
594                        SetMergeCandidateValid(mc);
595                        mMergeQueue.push(mc);
596                }
597        }
598
599        // adjust stats and reset queue one final time
600        mExpectedCost = realExpectedCost;
601        mAvgRenderCost = realAvgRenderCost;
602        mNumViewCells = realNumViewCells;
603
604        UpdateMergedViewCells(viewCells);
605        ResetMergeQueue();
606
607
608        // create a root node if the merge was not done till root level,
609        // else take the single node as new root
610        if ((int)viewCells.size() > 1)
611        {
612                Debug << "here888" << endl;
613                ViewCellInterior *root = new ViewCellInterior();
614
615                root->SetTimeStamp(mergeStats.merged + 1);
616
617                ViewCellContainer::const_iterator it, it_end = viewCells.end();
618                for (it = viewCells.begin(); it != it_end; ++ it)
619                        root->SetupChildLink(*it);
620
621                mRoot = root;
622        }
623        else if ((int)viewCells.size() == 1)
624        {
625                Debug << "here555" << endl;
626                mRoot = viewCells[0];
627        }
628
629        // TODO delete because makes no sense here
630        mergeStats.expectedRenderCost = realExpectedCost;
631        mergeStats.deviation = mDeviation;
632
633        // we want to optimize this heuristics
634        mergeStats.heuristics =
635                mDeviation * (1.0f - mRenderCostWeight) +
636                mExpectedCost * mRenderCostWeight;
637
638        mergeStats.mergeTime = TimeDiff(startTime, GetTime());
639        mergeStats.Stop();
640
641        Debug << mergeStats << endl << endl;
642
643
644        //TODO: should return sample contributions?
645        return mergeStats.merged;
646}
647
648
649ViewCell *ViewCellsTree::GetRoot()
650{
651        return mRoot;
652}
653
654
655void ViewCellsTree::ResetMergeQueue()
656{
657        cout << "reset merge queue ... ";
658       
659        vector<MergeCandidate> buf;
660        buf.reserve(mMergeQueue.size());
661                       
662       
663        // store merge candidates in intermediate buffer
664        while (!mMergeQueue.empty())
665        {
666                MergeCandidate mc = mMergeQueue.top();
667                mMergeQueue.pop();
668               
669                // recalculate cost
670                SetMergeCandidateValid(mc);
671                buf.push_back(mc);                             
672        }
673
674        vector<MergeCandidate>::const_iterator bit, bit_end = buf.end();
675
676        // reinsert back into queue
677        for (bit = buf.begin(); bit != bit_end; ++ bit)
678        {     
679                mMergeQueue.push(*bit);
680        }
681
682        cout << "finished" << endl;
683}
684
685
686int ViewCellsTree::UpdateMergedViewCells(ViewCellContainer &viewCells)
687{
688        int numActiveViewCells = 0;
689
690        // find all already merged view cells and remove them from view cells
691        int i = 0;
692
693        while (1)
694        {
695                while (!viewCells.empty() && (!viewCells.back()->GetParent()))
696                {
697                        viewCells.pop_back();
698                }
699
700                // all merged view cells have been found
701                if (i >= viewCells.size())
702                        break;
703
704                // already merged view cell, put it to end of vector
705                if (!viewCells[i]->IsRoot())
706                        swap(viewCells[i], viewCells.back());
707               
708                ++ i;
709        }
710
711        // add new view cells to container only if they don't have been
712        // merged in the mean time
713        while (!mActiveViewCells.empty())
714        {
715                if (!mActiveViewCells.back()->GetParent())
716                {
717                        viewCells.push_back(mActiveViewCells.back());
718                        ++ numActiveViewCells;
719                }
720
721                mActiveViewCells.pop_back();
722        }
723
724        // update standard deviation
725        ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
726       
727        mDeviation = 0;
728
729        for (vit = viewCells.begin(); vit != vit_end; ++ vit)
730        {
731                int lower = mViewCellsManager->GetMinPvsSize();
732                int upper = mViewCellsManager->GetMaxPvsSize();
733                float penalty = EvalPvsPenalty((*vit)->GetPvs().GetSize(), lower, upper);
734               
735                mDeviation += fabs(mAvgRenderCost - penalty);
736        }
737
738        mDeviation /= (float)viewCells.size();
739
740        // clear the view cells which were merged
741        mInactiveViewCells.clear();
742        // remove the new view cells
743        mActiveViewCells.clear();
744
745        return numActiveViewCells;
746}
747
748
749void ViewCellsTree::ExportMergedViewCells(ViewCellContainer &viewCells,
750                                                                                  const ObjectContainer &objects,
751                                                                                  const int numActiveViewCells)
752{
753       
754
755        char s[64];
756
757        sprintf(s, "merged_viewcells%07d.x3d", (int)viewCells.size());
758        Exporter *exporter = Exporter::GetExporter(s);
759
760        if (exporter)
761        {
762                cout << "exporting " << (int)viewCells.size() << " merged view cells ... ";
763                exporter->ExportGeometry(objects);
764                //Debug << "vc size " << (int)viewCells.size() << " merge queue size: " << (int)mMergeQueue.size() << endl;
765                ViewCellContainer::const_iterator it, it_end = viewCells.end();
766
767                int i = 0;
768                for (it = viewCells.begin(); it != it_end; ++ it)
769                {
770                        Material m;
771                        // assign special material to new view cells
772                        // new view cells are on the back of container
773                        if (i ++ >= (viewCells.size() - numActiveViewCells))
774                        {
775                                //m = RandomMaterial();
776                                m.mDiffuseColor.r = RandomValue(0.5f, 1.0f);
777                                m.mDiffuseColor.g = RandomValue(0.5f, 1.0f);
778                                m.mDiffuseColor.b = RandomValue(0.5f, 1.0f);
779                        }
780                        else
781                        {
782                                float col = RandomValue(0.1f, 0.4f);
783                                m.mDiffuseColor.r = col;
784                                m.mDiffuseColor.g = col;
785                                m.mDiffuseColor.b = col;
786                        }
787
788                        exporter->SetForcedMaterial(m);
789                        mViewCellsManager->ExportViewCellGeometry(exporter, *it);
790                }
791                delete exporter;
792                cout << "finished" << endl;
793        }
794}
795
796
797// TODO: should be done in view cells manager
798ViewCellInterior *ViewCellsTree::MergeViewCells(ViewCell *l, ViewCell *r, int &pvsDiff) //const
799{
800        ViewCellInterior *vc = mViewCellsManager->MergeViewCells(*l, *r);
801
802        // if merge was unsuccessful
803        if (!vc) return NULL;
804
805        // set new size of view cell
806        if (mUseAreaForPvs)
807                vc->SetArea(l->GetArea() + l->GetArea());
808        else
809                vc->SetVolume(r->GetVolume() + r->GetVolume());
810       
811        // important so other merge candidates sharing this view cell
812        // are notified that the merge cost must be updated!!
813        vc->Mail();
814
815        const int pvs1 = l->GetPvs().GetSize();
816        const int pvs2 = r->GetPvs().GetSize();
817
818
819        //-- clean up old view cells
820        if (0 && !mExportMergedViewCells)
821        {
822                DEL_PTR(l);
823                DEL_PTR(r);
824        }
825        else
826        {
827                mInactiveViewCells.push_back(l);
828                mInactiveViewCells.push_back(r);
829               
830                mActiveViewCells.push_back(vc);
831        }
832
833        pvsDiff = vc->GetPvs().GetSize() - pvs1 - pvs2;
834
835        return vc;
836}
837
838
839
840
841int ViewCellsTree::RefineViewCells(const VssRayContainer &rays, const ObjectContainer &objects)
842{
843        Debug << "refining " << (int)mMergeQueue.size() << " candidates " << endl;
844       
845        // Use priority queue of remaining leaf pairs
846        // The candidates either share the same view cells or
847        // are border leaves which share a boundary.
848        // We test if they can be shuffled, i.e.,
849        // either one leaf is made part of one view cell or the other
850        // leaf is made part of the other view cell. It is tested if the
851        // remaining view cells are "better" than the old ones.
852        //
853        // repeat the merging test numPasses times. For example, it could be
854        // that a shuffle only makes sense if another pair was shuffled before.
855        // Therefore we keep two queues and shift the merge candidates between
856        // those two queues until numPasses is reached
857       
858        queue<MergeCandidate> queue1;
859        queue<MergeCandidate> queue2;
860
861        queue<MergeCandidate> *shuffleQueue = &queue1;
862        queue<MergeCandidate> *backQueue = &queue2;
863
864        while (!mMergeQueue.empty())
865        {
866                MergeCandidate mc = mMergeQueue.top();
867                shuffleQueue->push(mc);
868                mMergeQueue.pop();
869        }
870
871        const int numPasses = 5;
872        int pass = 0;
873        int passShuffled = 0;
874        int shuffled = 0;
875        int shuffledViewCells = 0;
876
877        ViewCell::NewMail();
878       
879        do
880        {
881                passShuffled = 0;
882                while (!shuffleQueue->empty())
883                {
884                        MergeCandidate mc = shuffleQueue->front();
885                        shuffleQueue->pop();
886
887                        // both view cells equal or already shuffled
888                        if ((mc.GetLeftViewCell() == mc.GetRightViewCell()) ||
889                                (GetSize(mc.GetLeftViewCell()) == 1) ||
890                                (GetSize(mc.GetRightViewCell()) == 1))
891                        {                       
892                                continue;
893                        }
894
895                        // candidate for shuffling
896                        const bool wasShuffled =
897                                ShuffleLeaves(mc.GetLeftViewCell(), mc.GetRightViewCell());
898               
899                        // shuffled or put into other queue for further refine
900                        if (wasShuffled)
901                        {
902                                ++ passShuffled;
903
904                                if (!mc.GetLeftViewCell()->Mailed())
905                                {
906                                        mc.GetLeftViewCell()->Mail();
907                                        ++ shuffledViewCells;
908                                }
909                                if (!mc.GetRightViewCell()->Mailed())
910                                {
911                                        mc.GetRightViewCell()->Mail();
912                                        ++ shuffledViewCells;
913                                }
914                        }
915                        else
916                        {
917                                backQueue->push(mc);
918                        }
919                }
920
921                // now the back queue is the current shuffle queue
922                swap(shuffleQueue, backQueue);
923                shuffled += passShuffled;
924                Debug << "shuffled in pass: " << passShuffled << endl;
925        }
926        while (((++ pass) < numPasses) && passShuffled);
927
928        while (!shuffleQueue->empty())
929        {
930                shuffleQueue->pop();
931        }
932
933        return shuffledViewCells;
934}
935
936
937
938
939inline int AddedPvsSize(ObjectPvs pvs1, const ObjectPvs &pvs2)
940{
941        return pvs1.AddPvs(pvs2);
942}
943
944
945// recomputes pvs size minus pvs of leaf l
946#if 0
947inline int SubtractedPvsSize(BspViewCell *vc, BspLeaf *l, const ObjectPvs &pvs2)
948{
949        ObjectPvs pvs;
950        vector<BspLeaf *>::const_iterator it, it_end = vc->mLeaves.end();
951        for (it = vc->mLeaves.begin(); it != vc->mLeaves.end(); ++ it)
952                if (*it != l)
953                        pvs.AddPvs(*(*it)->mPvs);
954        return pvs.GetSize();
955}
956#endif
957
958
959// computes pvs1 minus pvs2
960inline int SubtractedPvsSize(ObjectPvs pvs1, const ObjectPvs &pvs2)
961{
962        return pvs1.SubtractPvs(pvs2);
963}
964
965
966float ViewCellsTree::EvalShuffleCost(ViewCell *leaf,
967                                                                         ViewCell *vc1,
968                                                                         ViewCell *vc2) const
969{
970        //const int pvs1 = SubtractedPvsSize(vc1, leaf, *leaf->mPvs);
971        const int pvs1 = SubtractedPvsSize(vc1->GetPvs(), leaf->GetPvs());
972        const int pvs2 = AddedPvsSize(vc2->GetPvs(), leaf->GetPvs());
973
974        const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize();
975        const int upperPvsLimit = mViewCellsManager->GetMaxPvsSize();
976
977        const float pvsPenalty1 =
978                EvalPvsPenalty(pvs1, lowerPvsLimit, upperPvsLimit);
979
980        const float pvsPenalty2 =
981                EvalPvsPenalty(pvs2, lowerPvsLimit, upperPvsLimit);
982
983
984        // don't shuffle leaves with pvs > max
985        if (0 && (pvs1 + pvs2 > mViewCellsManager->GetMaxPvsSize()))
986        {
987                return 1e20f;
988        }
989
990        float p1, p2;
991
992    if (mUseAreaForPvs)
993        {
994                p1 = vc1->GetArea() - leaf->GetArea();
995                p2 = vc2->GetArea() + leaf->GetArea();
996        }
997        else
998        {
999                p1 = vc1->GetVolume() - leaf->GetVolume();
1000                p2 = vc2->GetVolume() + leaf->GetVolume();
1001        }
1002
1003        const float renderCost1 = pvsPenalty1 * p1;
1004        const float renderCost2 = pvsPenalty2 * p2;
1005
1006        float dev1, dev2;
1007
1008        if (1)
1009        {
1010                dev1 = fabs(mAvgRenderCost - pvsPenalty1);
1011                dev2 = fabs(mAvgRenderCost - pvsPenalty2);
1012        }
1013        else
1014        {
1015                dev1 = fabs(mExpectedCost - renderCost1);
1016                dev2 = fabs(mExpectedCost - renderCost2);
1017        }
1018       
1019        return mRenderCostWeight * (renderCost1 + renderCost2) +
1020                  (1.0f - mRenderCostWeight) * (dev1 + dev2) / (float)mNumViewCells;
1021}
1022
1023
1024void ViewCellsTree::ShuffleLeaf(ViewCell *leaf,
1025                                                                ViewCell *vc1,
1026                                                                ViewCell *vc2) const
1027{
1028        // compute new pvs and area
1029        vc1->GetPvs().SubtractPvs(leaf->GetPvs());
1030        vc2->GetPvs().AddPvs(leaf->GetPvs());
1031       
1032        if (mUseAreaForPvs)
1033        {
1034                vc1->SetArea(vc1->GetArea() - leaf->GetArea());
1035                vc2->SetArea(vc2->GetArea() + leaf->GetArea());
1036        }
1037        else
1038        {
1039                vc1->SetVolume(vc1->GetVolume() - leaf->GetVolume());
1040                vc2->SetVolume(vc2->GetVolume() + leaf->GetVolume());
1041        }
1042
1043        // TODO
1044#if VC_HISTORY
1045        /// add to second view cell
1046        vc2->mLeaves.push_back(leaf);
1047
1048        // erase leaf from old view cell
1049        vector<BspLeaf *>::iterator it = vc1->mLeaves.begin();
1050
1051        for (; *it != leaf; ++ it);
1052        vc1->mLeaves.erase(it);
1053
1054        /*vc1->GetPvs().mEntries.clear();
1055        for (; it != vc1->mLeaves.end(); ++ it)
1056        {
1057                if (*it == leaf)
1058                        vc1->mLeaves.erase(it);
1059                else
1060                        vc1->GetPvs().AddPvs(*(*it)->mPvs);
1061        }*/
1062
1063        leaf->SetViewCell(vc2); // finally change view cell
1064#endif
1065}
1066
1067
1068bool ViewCellsTree::ShuffleLeaves(ViewCell *l, ViewCell *r) const
1069{
1070        float cost1, cost2;
1071
1072        //-- first test if shuffling would decrease cost
1073        cost1 = GetCostHeuristics(l);
1074        cost2 = GetCostHeuristics(r);
1075
1076        const float oldCost = cost1 + cost2;
1077       
1078        float shuffledCost1 = Limits::Infinity;
1079        float shuffledCost2 = Limits::Infinity;
1080
1081        // the view cell should not be empty after the shuffle
1082#if VC_HISTORY
1083        shuffledCost1 = EvalShuffleCost(l, vc1, vc2);
1084        /shuffledCost2 = EvalShuffleCost(r, vc2, vc1);
1085
1086        // if cost of shuffle is less than old cost => shuffle
1087        if ((oldCost <= shuffledCost1) && (oldCost <= shuffledCost2))
1088                return false;
1089       
1090       
1091        if (shuffledCost1 < shuffledCost2)
1092        {
1093                ShuffleLeaf(leaf1, vc1, vc2);
1094                leaf1->Mail();
1095        }
1096        else
1097        {
1098                ShuffleLeaf(leaf2, vc2, vc1);
1099                leaf2->Mail();
1100        }
1101#endif
1102        return true;
1103}
1104
1105
1106float ViewCellsTree::GetVariance(ViewCell *vc) const
1107{
1108        const int upper = mViewCellsManager->GetMaxPvsSize();
1109        const int lower = mViewCellsManager->GetMinPvsSize();
1110
1111        if (1)
1112        {
1113                const float penalty = EvalPvsPenalty(vc->GetPvs().GetSize(), lower, upper);
1114                return (mAvgRenderCost - penalty) * (mAvgRenderCost - penalty) / (float)mNumViewCells;
1115        }
1116
1117    const float leafCost = GetRenderCost(vc);
1118        return (mExpectedCost - leafCost) * (mExpectedCost - leafCost);
1119}
1120
1121
1122float ViewCellsTree::GetDeviation(ViewCell *vc) const
1123{
1124        const int upper = mViewCellsManager->GetMaxPvsSize();
1125        const int lower = mViewCellsManager->GetMinPvsSize();
1126
1127        if (1)
1128        {
1129                const float penalty = EvalPvsPenalty(vc->GetPvs().GetSize(), lower, upper);
1130                return fabs(mAvgRenderCost - penalty) / (float)mNumViewCells;
1131        }
1132
1133    const float renderCost = GetRenderCost(vc);
1134        return fabs(mExpectedCost - renderCost);
1135}
1136
1137
1138
1139float ViewCellsTree::GetRenderCost(ViewCell *vc) const
1140{
1141        if (mUseAreaForPvs)
1142                return vc->GetPvs().GetSize() * vc->GetArea();
1143
1144        return vc->GetPvs().GetSize() * vc->GetVolume();
1145}
1146
1147
1148float ViewCellsTree::GetCostHeuristics(ViewCell *vc) const
1149{
1150        return GetRenderCost(vc) * mRenderCostWeight +
1151                   GetDeviation(vc) * (1.0f - mRenderCostWeight);
1152}
1153
1154
1155void ViewCellsTree::SetMergeCandidateValid(MergeCandidate &mc) const
1156{
1157        while (mc.mLeftViewCell->mParent)
1158        {
1159                mc.mLeftViewCell = mc.mLeftViewCell->mParent;
1160        }
1161
1162        while (mc.mRightViewCell->mParent)
1163        {
1164                mc.mRightViewCell = mc.mRightViewCell->mParent;
1165        }
1166
1167        EvalMergeCost(mc);
1168}
1169
1170
1171void ViewCellsTree::EvalMergeCost(MergeCandidate &mc) const
1172{
1173        //-- compute pvs difference
1174        const int newPvs =
1175                ComputeMergedPvsSize(mc.mLeftViewCell->GetPvs(),
1176                                                         mc.mRightViewCell->GetPvs());
1177                       
1178        const float newPenalty =
1179                EvalPvsPenalty(newPvs,
1180                                           mViewCellsManager->GetMinPvsSize(),
1181                                           mViewCellsManager->GetMaxPvsSize());
1182
1183        ViewCell *vc1 = mc.mLeftViewCell;
1184        ViewCell *vc2 = mc.mRightViewCell;
1185
1186        //-- compute ratio of old cost
1187        //   (i.e., added size of left and right view cell times pvs size)
1188        //   to new rendering cost (i.e, size of merged view cell times pvs size)
1189        const float oldCost = GetRenderCost(vc1) + GetRenderCost(vc2);
1190
1191    const float newCost = mUseAreaForPvs ?
1192                (float)newPenalty * (vc1->GetArea() + vc2->GetArea()) :
1193                (float)newPenalty * (vc1->GetVolume() + vc2->GetVolume());
1194
1195
1196        // strong penalty if pvs size too large
1197        if (0 && (newPvs > mViewCellsManager->GetMaxPvsSize()))
1198        {
1199                mc.mRenderCost = 1e20f;
1200        }
1201        else
1202        {
1203                mc.mRenderCost = (newCost - oldCost) /
1204                        mViewCellsManager->GetViewSpaceBox().GetVolume();
1205        }       
1206       
1207
1208        //-- merge cost also takes deviation into account
1209        float newDev, oldDev;
1210
1211        if (1)
1212                newDev = fabs(mAvgRenderCost - newPenalty) / (float)mNumViewCells;
1213        else
1214                newDev = fabs(mExpectedCost - newCost) / (float)mNumViewCells;
1215       
1216        oldDev = GetDeviation(vc1) + GetDeviation(vc2);
1217
1218        // compute deviation increase
1219        mc.mDeviationIncr = newDev - oldDev;
1220       
1221        //Debug << "render cost: " << mc.mRenderCost * mRenderCostWeight << endl;
1222        //Debug << "standard deviation: " << mc.mDeviationIncr * mRenderCostWeight << endl;
1223}
1224
1225
1226void ViewCellsTree::CompressViewCellsPvs()
1227{
1228        stack<ViewCell *> tstack;
1229       
1230        while (!tstack.empty())
1231        {
1232                ViewCell *viewCell = tstack.top();
1233                tstack.pop();
1234
1235                if (viewCell->IsLeaf())
1236                {
1237                       
1238                }
1239                else
1240                {
1241                        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(viewCell);                       
1242                        ComputeCommonPvs(interior);
1243                }
1244        }
1245}
1246
1247
1248void ViewCellsTree::CollectBestViewCellSet(ViewCellContainer &viewCells,
1249                                                                                   const int numViewCells)
1250{
1251        TraversalQueue tqueue;
1252        tqueue.push(mRoot);
1253        Debug << "here34 " << numViewCells << endl;
1254        while (!tqueue.empty())
1255        {
1256                ViewCell *vc = tqueue.top();
1257                tqueue.pop();
1258                Debug << "here7 " << vc->GetTimeStamp() << endl;
1259                if (vc->IsLeaf())
1260                {
1261                        Debug << "here6" << endl;
1262                        viewCells.push_back(vc);
1263                }
1264                else if (viewCells.size() + tqueue.size() < numViewCells)
1265                {       Debug << "here4" << endl;
1266                        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
1267
1268                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1269
1270                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
1271                        {
1272                                tqueue.push(*it);
1273                        }
1274                }
1275        }
1276}
1277       
1278
1279void ViewCellsTree::ComputeCommonPvs(ViewCellInterior *interior)
1280{
1281        Intersectable::NewMail();
1282
1283        ViewCellContainer::const_iterator cit, cit_end = interior->mChildren.end();
1284
1285        ObjectPvsMap::const_iterator oit;
1286
1287        // mail all objects in the leaf sets
1288        for (cit = interior->mChildren.begin(); cit != cit_end; ++ cit)
1289        {
1290                ViewCell *vc = *cit;
1291
1292                ObjectPvsMap::const_iterator oit_end = vc->GetPvs().mEntries.end();
1293
1294                for (oit = vc->GetPvs().mEntries.begin(); oit != oit_end; ++ oit)
1295                {
1296                        if (!(*oit).first->Mailed())
1297                                (*oit).first->Mail();
1298                       
1299                        (*oit).first->IncMail();
1300                }
1301        }
1302
1303        interior->GetPvs().mEntries.clear();
1304    cit_end = interior->mChildren.end();
1305       
1306        // only the objects which are present in all leaf pvs
1307        // should remain in the parent pvs
1308
1309        for (cit = interior->mChildren.begin(); cit != cit_end; ++ cit)
1310        {
1311                ViewCell *vc = *cit;
1312
1313                ObjectPvsMap::const_iterator oit_end = vc->GetPvs().mEntries.end();
1314
1315                for (oit = vc->GetPvs().mEntries.begin(); oit != oit_end; ++ oit)
1316                {
1317                        if ((*oit).first->Mailed((int)interior->mChildren.size()))
1318                        {       
1319                                interior->GetPvs().AddSample((*oit).first, (*oit).second.mSumPdf);
1320                                //(*oit)->remove();
1321                        }
1322                }
1323        }
1324
1325        // delete all the objects from the leaf sets which were moved
1326        // to parent pvs
1327        ObjectPvsMap::const_iterator oit_end = interior->GetPvs().mEntries.end();
1328
1329        for (oit = interior->GetPvs().mEntries.begin(); oit != oit_end; ++ oit)
1330        {
1331                for (cit = interior->mChildren.begin(); cit != cit_end; ++ cit)
1332                {
1333                        (*cit)->GetPvs().RemoveSample((*oit).first, Limits::Infinity);
1334                }
1335        }
1336}
1337
1338
1339/**************************************************************************/
1340/*                     MergeCandidate implementation                      */
1341/**************************************************************************/
1342
1343
1344MergeCandidate::MergeCandidate(ViewCell *l, ViewCell *r):
1345mRenderCost(0),
1346mDeviationIncr(0),
1347mLeftViewCell(l),
1348mRightViewCell(r)
1349{
1350        //EvalMergeCost();
1351}
1352
1353
1354void MergeCandidate::SetRightViewCell(ViewCell *v)
1355{
1356        mRightViewCell = v;
1357}
1358
1359
1360void MergeCandidate::SetLeftViewCell(ViewCell *v)
1361{
1362        mLeftViewCell = v;
1363}
1364
1365
1366ViewCell *MergeCandidate::GetRightViewCell() const
1367{
1368        return mRightViewCell;
1369}
1370
1371
1372ViewCell *MergeCandidate::GetLeftViewCell() const
1373{
1374        return mLeftViewCell;
1375}
1376
1377
1378ViewCell *MergeCandidate::GetInitialRightViewCell() const
1379{
1380        return mInitialRightViewCell;
1381}
1382
1383
1384ViewCell *MergeCandidate::GetInitialLeftViewCell() const
1385{
1386        return mInitialLeftViewCell;
1387}
1388
1389
1390bool MergeCandidate::IsValid() const
1391{
1392        return !(mLeftViewCell->mParent && mRightViewCell->mParent);
1393}
1394
1395
1396float MergeCandidate::GetRenderCost() const
1397{
1398        return mRenderCost;
1399}
1400
1401
1402float MergeCandidate::GetDeviationIncr() const
1403{
1404        return mDeviationIncr;
1405}
1406
1407
1408float MergeCandidate::GetMergeCost() const
1409{
1410        return mRenderCost * sRenderCostWeight +
1411                   mDeviationIncr * (1.0f - sRenderCostWeight);
1412}
1413
1414
1415/************************************************************************/
1416/*                    MergeStatistics implementation                    */
1417/************************************************************************/
1418
1419
1420void MergeStatistics::Print(ostream &app) const
1421{
1422        app << "===== Merge statistics ===============\n";
1423
1424        app << setprecision(4);
1425
1426        app << "#N_CTIME ( Overall time [s] )\n" << Time() << " \n";
1427
1428        app << "#N_CCTIME ( Collect candidates time [s] )\n" << collectTime * 1e-3f << " \n";
1429
1430        app << "#N_MTIME ( Merge time [s] )\n" << mergeTime * 1e-3f << " \n";
1431
1432        app << "#N_NODES ( Number of nodes before merge )\n" << nodes << "\n";
1433
1434        app << "#N_CANDIDATES ( Number of merge candidates )\n" << candidates << "\n";
1435
1436        app << "#N_MERGEDSIBLINGS ( Number of merged siblings )\n" << siblings << "\n";
1437
1438        app << "#OVERALLCOST ( overall merge cost )\n" << overallCost << "\n";
1439
1440        app << "#N_MERGEDNODES ( Number of merged nodes )\n" << merged << "\n";
1441
1442        app << "#MAX_TREEDIST ( Maximal distance in tree of merged leaves )\n" << maxTreeDist << "\n";
1443
1444        app << "#AVG_TREEDIST ( Average distance in tree of merged leaves )\n" << AvgTreeDist() << "\n";
1445
1446        app << "#EXPECTEDCOST ( expected render cost )\n" << expectedRenderCost << "\n";
1447
1448        app << "#DEVIATION ( deviation )\n" << deviation << "\n";
1449
1450        app << "#HEURISTICS ( heuristics )\n" << heuristics << "\n";
1451       
1452
1453        app << "===== END OF BspTree statistics ==========\n";
1454}
Note: See TracBrowser for help on using the repository browser.