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

Revision 584, 37.8 KB checked in by mattausch, 18 years ago (diff)
Line 
1#include "ViewCell.h"
2#include "Mesh.h"
3#include "Intersectable.h"
4#include "MeshKdTree.h"
5#include "Triangle3.h"
6#include "common.h"
7#include "Environment.h"
8#include "ViewCellsManager.h"
9#include "Exporter.h"
10
11#include <time.h>
12#include <iomanip>
13#include <stack>
14
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),
308mIsCompressed(false)
309{
310        environment->GetBoolValue("ViewCells.Visualization.exportMergedViewCells", mExportMergedViewCells);
311        environment->GetFloatValue("ViewCells.maxStaticMemory", mMaxMemory);
312
313        //-- merge options
314        environment->GetFloatValue("ViewCells.PostProcess.renderCostWeight", mRenderCostWeight);
315        environment->GetIntValue("ViewCells.PostProcess.minViewCells", mMergeMinViewCells);
316        environment->GetFloatValue("ViewCells.PostProcess.maxCostRatio", mMergeMaxCostRatio);
317       
318
319        Debug << "========= view cell tree options ================\n";
320        Debug << "minimum view cells: " << mMergeMinViewCells << endl;
321        Debug << "max cost ratio: " << mMergeMaxCostRatio << endl;
322        Debug << "max memory: " << mMaxMemory << endl;
323
324        MergeCandidate::sRenderCostWeight = mRenderCostWeight;
325
326        mStats.open("mergeStats.log");
327}
328
329
330// return memory usage in MB
331float ViewCellsTree::GetMemUsage() const
332{
333        return 0;
334                /*(sizeof(ViewCellsTree) +
335                 mBspStats.Leaves() * sizeof(BspLeaf) +
336                 mBspStats.Interior() * sizeof(BspInterior) +
337                 mBspStats.accumRays * sizeof(RayInfo)) / (1024.0f * 1024.0f);*/
338}
339
340
341int ViewCellsTree::GetSize(ViewCell *vc) const
342{
343        int vcSize = 0;
344
345        stack<ViewCell *> tstack;
346
347        tstack.push(vc);
348
349        while (!tstack.empty())
350        {
351                ViewCell *vc = tstack.top();
352                tstack.pop();
353
354                if (vc->IsLeaf())
355                {
356                        ++ vcSize;
357                }
358                else
359                {
360                        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
361                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
362                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
363                                tstack.push(*it);
364                       
365                }
366        }
367
368        return vcSize;
369}
370
371
372void ViewCellsTree::CollectLeaves(ViewCell *vc, ViewCellContainer &leaves) const
373{
374        stack<ViewCell *> tstack;
375
376        tstack.push(vc);
377
378        while (!tstack.empty())
379        {
380                ViewCell *vc = tstack.top();
381                tstack.pop();
382
383                if (vc->IsLeaf())
384                {
385                        leaves.push_back(vc);
386                }
387                else
388                {
389                        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
390                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
391                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
392                                tstack.push(*it);
393                       
394                }
395        }
396}
397
398
399ViewCellsTree::~ViewCellsTree()
400{
401        DEL_PTR(mRoot);
402}
403
404
405int ViewCellsTree::ConstructMergeTree(const VssRayContainer &rays,
406                                                                          const ObjectContainer &objects)
407{
408        mNumActiveViewCells = (int)mViewCellsManager->GetViewCells().size();
409
410        float variance = 0;
411        int totalPvs = 0;
412        float totalCost = 0;
413
414        //-- compute statistics values of initial view cells
415        mViewCellsManager->EvaluateRenderStatistics(totalCost,
416                                                                                                mExpectedCost,
417                                                                                                mDeviation,
418                                                                                                variance,
419                                                                                                totalPvs,
420                                                                                                mAvgRenderCost);
421
422
423        //-- fill merge queue
424        vector<MergeCandidate> candidates;
425
426        mViewCellsManager->CollectMergeCandidates(rays, candidates);
427        while(!candidates.empty())
428        {
429                MergeCandidate mc = candidates.back();
430                candidates.pop_back();
431                EvalMergeCost(mc);
432                mMergeQueue.push(mc);
433        }
434
435        Debug << "************************* merge ***********************************" << endl; 
436        Debug << "deviation: " << mDeviation << endl;
437        Debug << "avg render cost: " << mAvgRenderCost << endl;
438        Debug << "expected cost: " <<mExpectedCost << endl;
439
440
441        ViewCellsManager::PvsStatistics pvsStats;
442        mViewCellsManager->GetPvsStatistics(pvsStats);
443
444        static float expectedValue = pvsStats.avgPvs;
445       
446        // the current view cells are kept in this container
447        // we start with the current view cells from the
448        // view cell manager. They will change with
449        // subsequent merges
450        ViewCellContainer &activeViewCells = mViewCellsManager->GetViewCells();
451
452
453        ViewCell::NewMail();
454
455        MergeStatistics mergeStats;
456        mergeStats.Start();
457       
458        long startTime = GetTime();
459
460        mergeStats.collectTime = TimeDiff(startTime, GetTime());
461        mergeStats.candidates = (int)mMergeQueue.size();
462        startTime = GetTime();
463
464        // frequency stats are updated
465        const int statsOut = 100;
466
467        // passes are needed for statistics, because we don't want to record
468        // every merge
469        int pass = 0;
470        int mergedPerPass = 0;
471        float realExpectedCost = mExpectedCost;
472        float realAvgRenderCost = mAvgRenderCost;
473        int realNumActiveViewCells = mNumActiveViewCells;
474       
475        // maximal ratio of old expected render cost to expected render
476        // when the the render queue has to be reset.
477        float avgCostMaxDeviation;
478        int maxMergesPerPass;
479        int numMergedViewCells = 0;
480
481        environment->GetIntValue("ViewCells.PostProcess.maxMergesPerPass", maxMergesPerPass);
482        environment->GetFloatValue("ViewCells.PostProcess.avgCostMaxDeviation", avgCostMaxDeviation);
483
484        cout << "actual merge starts now ... " << endl;
485       
486        //ResetMergeQueue();
487
488        //-- use priority queue to merge leaf pairs
489
490        while (!mMergeQueue.empty())// && (realNumActiveViewCells > mMergeMinViewCells))
491        {
492                //-- reset merge queue if the ratio of current expected cost / real expected cost
493                //   too small or after a given number of merges
494                if ((mergedPerPass > maxMergesPerPass) ||
495                        (avgCostMaxDeviation > mAvgRenderCost / realAvgRenderCost))
496                {
497                        Debug << "************ reset queue *****************\n"
498                                  << "ratios: " << avgCostMaxDeviation
499                                  << " real avg render cost " << realAvgRenderCost << " average render cost " << mAvgRenderCost
500                                  << " merged per pass : " << mergedPerPass << " of maximal " << maxMergesPerPass << endl;
501
502                        Debug << "Values before reset: " 
503                                  << " erc: " << mExpectedCost
504                                  << " avgrc: " << mAvgRenderCost
505                                  << " dev: " << mDeviation << endl;
506       
507                        // adjust render cost
508                        ++ pass;
509
510                        mergedPerPass = 0;
511                        mExpectedCost = realExpectedCost;
512                        mAvgRenderCost = realAvgRenderCost;
513                        mNumActiveViewCells = realNumActiveViewCells;
514                       
515                        const int numMergedViewCells = UpdateActiveViewCells(activeViewCells);
516               
517                        // recompute priorities => reset render cost
518                    ResetMergeQueue();
519
520                       
521                        Debug << "Values after reset: " 
522                                  << " erc: " << mExpectedCost
523                                  << " avg: " << mAvgRenderCost
524                                  << " dev: " << mDeviation << endl;
525
526                        if (mExportMergedViewCells)
527                        {
528                                ExportMergedViewCells(activeViewCells, objects, numMergedViewCells);
529                        }
530                }
531
532#ifdef _DEBUG
533                Debug << "abs mergecost: " << mMergeQueue.top().GetMergeCost() <<
534                          << " rel mergecost: " << mMergeQueue.top().GetRenderCost() / mExpectedCost <<
535                          << " max ratio: " << mMergeMaxCostRatio << endl
536                          << " expected value: " << realExpectedCost << endl;
537#endif
538
539       
540                MergeCandidate mc = mMergeQueue.top();
541                mMergeQueue.pop();
542       
543                // both view cells equal
544                // NOTE: do I really still need this? probably cannot happen!!
545                if (mc.mLeftViewCell == mc.mRightViewCell)
546                        continue;
547
548                if (mc.IsValid())
549                {
550                        ViewCell::NewMail();
551                                               
552                        -- realNumActiveViewCells;
553                        ++ mergeStats.merged;
554                        ++ mergedPerPass;
555
556
557                        //-- update statistical values
558
559                        // total render cost and deviation has changed
560                        // real expected cost will be larger than expected cost used for the
561                        // cost heuristics, but cannot recompute costs on each increase of the
562                        // expected cost
563
564                        totalCost += mc.GetRenderCost();
565                        mDeviation += mc.GetDeviationIncr();
566                                               
567                        realExpectedCost = totalCost / (float)realNumActiveViewCells;
568                       
569                        const float currentMergeCost = mc.GetMergeCost();
570
571                        // merge the view cells of leaf1 and leaf2
572                        int pvsDiff;
573                        ViewCellInterior *mergedVc =
574                                MergeViewCells(mc.mLeftViewCell, mc.mRightViewCell, pvsDiff);
575
576                        totalPvs += pvsDiff;
577
578                        // set timestamp
579                        mergedVc->SetTimeStamp(mergeStats.merged);
580
581                        realAvgRenderCost = (float)totalPvs / (float)realNumActiveViewCells;
582#if VC_HISTORY
583                        if (mc.mLeftViewCell->IsSibling(mc.mRightViewCell))
584                                ++ mergeStats.siblings;
585#endif
586                        if (((mergeStats.merged % statsOut) == 0) ||
587                                (realNumActiveViewCells == mMergeMinViewCells))
588                        {
589                                cout << "merged " << mergeStats.merged << " view cells" << endl;
590
591                                mStats
592                                        << "#Pass\n" << pass << endl
593                                        << "#Merged\n" << mergeStats.merged << endl
594                                        << "#Viewcells\n" << realNumActiveViewCells << endl
595                                        << "#CurrentCost\n" << currentMergeCost << endl
596                                        << "#RelativeCost\n" << currentMergeCost / mOverallCost << endl
597                                        << "#CurrentPvs\n" << mc.GetLeftViewCell()->GetPvs().GetSize() << endl
598                                        << "#MergedSiblings\n" << mergeStats.siblings << endl
599                                        << "#AvgTreeDist\n" << mergeStats.AvgTreeDist() << endl
600                                        << "#UsedExpectedCost\n" << mExpectedCost << endl
601                                        << "#RealExpectedCost\n" << realExpectedCost << endl
602                                        << "#RealAvgRenderCost\n" << realAvgRenderCost << endl
603                                        << "#AvgRenderCost\n" << mAvgRenderCost << endl
604                                        << "#expectedCostRatio\n" << mExpectedCost / realExpectedCost << endl
605                                        << "#Deviation\n" << mDeviation / (float)realNumActiveViewCells << endl
606                                        << "#TotalDeviation\n" << mDeviation<< endl;
607                        }
608                }
609                else
610                {
611                        // merge candidate not valid, because one of the leaves was already
612                        // merged with another one => validate and reinsert into queue
613                        if (ValidateMergeCandidate(mc))
614                        {
615                                EvalMergeCost(mc);
616                                mMergeQueue.push(mc);
617                        }
618                }
619        }
620
621        // adjust stats and reset queue one final time
622        mExpectedCost = realExpectedCost;
623        mAvgRenderCost = realAvgRenderCost;
624        mNumActiveViewCells = realNumActiveViewCells;
625
626        UpdateActiveViewCells(activeViewCells);
627        ResetMergeQueue();
628
629        // create a root node if the merge was not done till root level,
630        // else take the single node as new root
631        if ((int)activeViewCells.size() > 1)
632        {
633                Debug << "creating root of view cell hierarchy for " << (int)activeViewCells.size() << " view cells" << endl;
634                for (int i = 0;  i < activeViewCells.size(); ++ i){
635                        Debug << "here233 " << activeViewCells[i]->GetParent() << endl;
636                        Debug << "here233 " << activeViewCells[i] << endl;
637                }
638                ViewCellInterior *root = mViewCellsManager->MergeViewCells(activeViewCells);
639
640                root->SetTimeStamp(mergeStats.merged + 1);
641                mRoot = root;
642        }
643        else if ((int)activeViewCells.size() == 1)
644        {
645                Debug << "setting root of the merge history" << endl;
646                mRoot = activeViewCells[0];
647        }
648
649        // TODO delete because makes no sense here
650        mergeStats.expectedRenderCost = realExpectedCost;
651        mergeStats.deviation = mDeviation;
652
653        // we want to optimize this heuristics
654        mergeStats.heuristics =
655                mDeviation * (1.0f - mRenderCostWeight) +
656                mExpectedCost * mRenderCostWeight;
657
658        mergeStats.mergeTime = TimeDiff(startTime, GetTime());
659        mergeStats.Stop();
660
661        Debug << mergeStats << endl << endl;
662
663
664        //TODO: should return sample contributions?
665        return mergeStats.merged;
666}
667
668
669ViewCell *ViewCellsTree::GetRoot() const
670{
671        return mRoot;
672}
673
674
675void ViewCellsTree::ResetMergeQueue()
676{
677        cout << "reset merge queue ... ";
678       
679        vector<MergeCandidate> buf;
680        buf.reserve(mMergeQueue.size());
681                       
682       
683        // store merge candidates in intermediate buffer
684        while (!mMergeQueue.empty())
685        {
686                MergeCandidate mc = mMergeQueue.top();
687                mMergeQueue.pop();
688               
689                // recalculate cost
690                if (ValidateMergeCandidate(mc))
691                {
692                        EvalMergeCost(mc);
693                        buf.push_back(mc);                             
694                }
695        }
696
697        vector<MergeCandidate>::const_iterator bit, bit_end = buf.end();
698
699        // reinsert back into queue
700        for (bit = buf.begin(); bit != bit_end; ++ bit)
701        {     
702                mMergeQueue.push(*bit);
703        }
704
705        cout << "finished" << endl;
706}
707
708
709int ViewCellsTree::UpdateActiveViewCells(ViewCellContainer &viewCells)
710{
711        int numMergedViewCells = 0;
712
713        Debug << "updating active vc: " << (int)viewCells.size() << endl;
714        // find all already merged view cells and remove them from view cells
715               
716        // sort out all view cells which are not active anymore, i.e., they
717        // were already part of a merge
718        int i = 0;
719
720        ViewCell::NewMail();
721
722        while (1)
723        {
724                // remove all merged view cells from end of the vector
725                while (!viewCells.empty() && (viewCells.back()->GetParent()))
726                {
727                        viewCells.pop_back();
728                }
729
730                // all merged view cells have been found
731                if (i >= viewCells.size())
732                        break;
733
734                // already merged view cell, put it to end of vector
735                if (viewCells[i]->GetParent())
736                        swap(viewCells[i], viewCells.back());
737               
738                viewCells[i ++]->Mail();
739        }
740
741
742        // add new view cells to container only if they don't have been
743        // merged in the mean time
744        ViewCellContainer::const_iterator ait, ait_end = mMergedViewCells.end();
745        for (ait = mMergedViewCells.begin(); ait != ait_end; ++ ait)
746        {
747                ViewCell *vc = mMergedViewCells.back();
748                if (!vc->GetParent() && !vc->Mailed())
749                {
750                        vc->Mail();
751                        viewCells.push_back(vc);
752                        ++ numMergedViewCells;
753                }
754        }
755
756        mMergedViewCells.clear();
757
758        // update standard deviation
759        ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
760       
761        mDeviation = 0;
762
763        for (vit = viewCells.begin(); vit != vit_end; ++ vit)
764        {
765                int lower = mViewCellsManager->GetMinPvsSize();
766                int upper = mViewCellsManager->GetMaxPvsSize();
767                float penalty = EvalPvsPenalty((*vit)->GetPvs().GetSize(), lower, upper);
768               
769                mDeviation += fabs(mAvgRenderCost - penalty);
770        }
771
772        mDeviation /= (float)viewCells.size();
773       
774        return numMergedViewCells;
775}
776
777
778void ViewCellsTree::ExportMergedViewCells(ViewCellContainer &viewCells,
779                                                                                  const ObjectContainer &objects,
780                                                                                  const int numMergedViewCells)
781{
782       
783
784        char s[64];
785
786        sprintf(s, "merged_viewcells%07d.x3d", (int)viewCells.size());
787        Exporter *exporter = Exporter::GetExporter(s);
788
789        if (exporter)
790        {
791                cout << "exporting " << (int)viewCells.size() << " merged view cells ... ";
792                exporter->ExportGeometry(objects);
793                //Debug << "vc size " << (int)viewCells.size() << " merge queue size: " << (int)mMergeQueue.size() << endl;
794                ViewCellContainer::const_iterator it, it_end = viewCells.end();
795
796                int i = 0;
797                for (it = viewCells.begin(); it != it_end; ++ it)
798                {
799                        Material m;
800                        // assign special material to new view cells
801                        // new view cells are on the back of container
802                        if (i ++ >= (viewCells.size() - numMergedViewCells))
803                        {
804                                //m = RandomMaterial();
805                                m.mDiffuseColor.r = RandomValue(0.5f, 1.0f);
806                                m.mDiffuseColor.g = RandomValue(0.5f, 1.0f);
807                                m.mDiffuseColor.b = RandomValue(0.5f, 1.0f);
808                        }
809                        else
810                        {
811                                float col = RandomValue(0.1f, 0.4f);
812                                m.mDiffuseColor.r = col;
813                                m.mDiffuseColor.g = col;
814                                m.mDiffuseColor.b = col;
815                        }
816
817                        exporter->SetForcedMaterial(m);
818                        mViewCellsManager->ExportViewCellGeometry(exporter, *it);
819                }
820                delete exporter;
821                cout << "finished" << endl;
822        }
823}
824
825
826// TODO: should be done in view cells manager
827ViewCellInterior *ViewCellsTree::MergeViewCells(ViewCell *l, ViewCell *r, int &pvsDiff) //const
828{
829        ViewCellInterior *vc = mViewCellsManager->MergeViewCells(l, r);
830
831        // if merge was unsuccessful
832        if (!vc) return NULL;
833
834        // set new size of view cell
835        if (mUseAreaForPvs)
836                vc->SetArea(l->GetArea() + l->GetArea());
837        else
838                vc->SetVolume(r->GetVolume() + r->GetVolume());
839       
840        // important so other merge candidates sharing this view cell
841        // are notified that the merge cost must be updated!!
842        vc->Mail();
843
844        const int pvs1 = l->GetPvs().GetSize();
845        const int pvs2 = r->GetPvs().GetSize();
846
847
848        // new view cells are stored in this vector
849        mMergedViewCells.push_back(vc);
850
851        pvsDiff = vc->GetPvs().GetSize() - pvs1 - pvs2;
852
853        return vc;
854}
855
856
857
858
859int ViewCellsTree::RefineViewCells(const VssRayContainer &rays, const ObjectContainer &objects)
860{
861        Debug << "refining " << (int)mMergeQueue.size() << " candidates " << endl;
862       
863        // Use priority queue of remaining leaf pairs
864        // The candidates either share the same view cells or
865        // are border leaves which share a boundary.
866        // We test if they can be shuffled, i.e.,
867        // either one leaf is made part of one view cell or the other
868        // leaf is made part of the other view cell. It is tested if the
869        // remaining view cells are "better" than the old ones.
870        //
871        // repeat the merging test numPasses times. For example, it could be
872        // that a shuffle only makes sense if another pair was shuffled before.
873        // Therefore we keep two queues and shift the merge candidates between
874        // those two queues until numPasses is reached
875       
876        queue<MergeCandidate> queue1;
877        queue<MergeCandidate> queue2;
878
879        queue<MergeCandidate> *shuffleQueue = &queue1;
880        queue<MergeCandidate> *backQueue = &queue2;
881
882        while (!mMergeQueue.empty())
883        {
884                MergeCandidate mc = mMergeQueue.top();
885                shuffleQueue->push(mc);
886                mMergeQueue.pop();
887        }
888
889        const int numPasses = 5;
890        int pass = 0;
891        int passShuffled = 0;
892        int shuffled = 0;
893        int shuffledViewCells = 0;
894
895        ViewCell::NewMail();
896       
897        do
898        {
899                passShuffled = 0;
900                while (!shuffleQueue->empty())
901                {
902                        MergeCandidate mc = shuffleQueue->front();
903                        shuffleQueue->pop();
904
905                        // both view cells equal or already shuffled
906                        if ((mc.GetLeftViewCell() == mc.GetRightViewCell()) ||
907                                (GetSize(mc.GetLeftViewCell()) == 1) ||
908                                (GetSize(mc.GetRightViewCell()) == 1))
909                        {                       
910                                continue;
911                        }
912
913                        // candidate for shuffling
914                        const bool wasShuffled =
915                                ShuffleLeaves(mc.GetLeftViewCell(), mc.GetRightViewCell());
916               
917                        // shuffled or put into other queue for further refine
918                        if (wasShuffled)
919                        {
920                                ++ passShuffled;
921
922                                if (!mc.GetLeftViewCell()->Mailed())
923                                {
924                                        mc.GetLeftViewCell()->Mail();
925                                        ++ shuffledViewCells;
926                                }
927                                if (!mc.GetRightViewCell()->Mailed())
928                                {
929                                        mc.GetRightViewCell()->Mail();
930                                        ++ shuffledViewCells;
931                                }
932                        }
933                        else
934                        {
935                                backQueue->push(mc);
936                        }
937                }
938
939                // now the back queue is the current shuffle queue
940                swap(shuffleQueue, backQueue);
941                shuffled += passShuffled;
942                Debug << "shuffled in pass: " << passShuffled << endl;
943        }
944        while (((++ pass) < numPasses) && passShuffled);
945
946        while (!shuffleQueue->empty())
947        {
948                shuffleQueue->pop();
949        }
950
951        return shuffledViewCells;
952}
953
954
955
956
957inline int AddedPvsSize(ObjectPvs pvs1, const ObjectPvs &pvs2)
958{
959        return pvs1.AddPvs(pvs2);
960}
961
962
963// recomputes pvs size minus pvs of leaf l
964#if 0
965inline int SubtractedPvsSize(BspViewCell *vc, BspLeaf *l, const ObjectPvs &pvs2)
966{
967        ObjectPvs pvs;
968        vector<BspLeaf *>::const_iterator it, it_end = vc->mLeaves.end();
969        for (it = vc->mLeaves.begin(); it != vc->mLeaves.end(); ++ it)
970                if (*it != l)
971                        pvs.AddPvs(*(*it)->mPvs);
972        return pvs.GetSize();
973}
974#endif
975
976
977// computes pvs1 minus pvs2
978inline int SubtractedPvsSize(ObjectPvs pvs1, const ObjectPvs &pvs2)
979{
980        return pvs1.SubtractPvs(pvs2);
981}
982
983
984float ViewCellsTree::EvalShuffleCost(ViewCell *leaf,
985                                                                         ViewCell *vc1,
986                                                                         ViewCell *vc2) const
987{
988        //const int pvs1 = SubtractedPvsSize(vc1, leaf, *leaf->mPvs);
989        const int pvs1 = SubtractedPvsSize(vc1->GetPvs(), leaf->GetPvs());
990        const int pvs2 = AddedPvsSize(vc2->GetPvs(), leaf->GetPvs());
991
992        const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize();
993        const int upperPvsLimit = mViewCellsManager->GetMaxPvsSize();
994
995        const float pvsPenalty1 =
996                EvalPvsPenalty(pvs1, lowerPvsLimit, upperPvsLimit);
997
998        const float pvsPenalty2 =
999                EvalPvsPenalty(pvs2, lowerPvsLimit, upperPvsLimit);
1000
1001
1002        // don't shuffle leaves with pvs > max
1003        if (0 && (pvs1 + pvs2 > mViewCellsManager->GetMaxPvsSize()))
1004        {
1005                return 1e20f;
1006        }
1007
1008        float p1, p2;
1009
1010    if (mUseAreaForPvs)
1011        {
1012                p1 = vc1->GetArea() - leaf->GetArea();
1013                p2 = vc2->GetArea() + leaf->GetArea();
1014        }
1015        else
1016        {
1017                p1 = vc1->GetVolume() - leaf->GetVolume();
1018                p2 = vc2->GetVolume() + leaf->GetVolume();
1019        }
1020
1021        const float renderCost1 = pvsPenalty1 * p1;
1022        const float renderCost2 = pvsPenalty2 * p2;
1023
1024        float dev1, dev2;
1025
1026        if (1)
1027        {
1028                dev1 = fabs(mAvgRenderCost - pvsPenalty1);
1029                dev2 = fabs(mAvgRenderCost - pvsPenalty2);
1030        }
1031        else
1032        {
1033                dev1 = fabs(mExpectedCost - renderCost1);
1034                dev2 = fabs(mExpectedCost - renderCost2);
1035        }
1036       
1037        return mRenderCostWeight * (renderCost1 + renderCost2) +
1038                  (1.0f - mRenderCostWeight) * (dev1 + dev2) / (float)mNumActiveViewCells;
1039}
1040
1041
1042void ViewCellsTree::ShuffleLeaf(ViewCell *leaf,
1043                                                                ViewCell *vc1,
1044                                                                ViewCell *vc2) const
1045{
1046        // compute new pvs and area
1047        vc1->GetPvs().SubtractPvs(leaf->GetPvs());
1048        vc2->GetPvs().AddPvs(leaf->GetPvs());
1049       
1050        if (mUseAreaForPvs)
1051        {
1052                vc1->SetArea(vc1->GetArea() - leaf->GetArea());
1053                vc2->SetArea(vc2->GetArea() + leaf->GetArea());
1054        }
1055        else
1056        {
1057                vc1->SetVolume(vc1->GetVolume() - leaf->GetVolume());
1058                vc2->SetVolume(vc2->GetVolume() + leaf->GetVolume());
1059        }
1060
1061        // TODO
1062#if VC_HISTORY
1063        /// add to second view cell
1064        vc2->mLeaves.push_back(leaf);
1065
1066        // erase leaf from old view cell
1067        vector<BspLeaf *>::iterator it = vc1->mLeaves.begin();
1068
1069        for (; *it != leaf; ++ it);
1070        vc1->mLeaves.erase(it);
1071
1072        /*vc1->GetPvs().mEntries.clear();
1073        for (; it != vc1->mLeaves.end(); ++ it)
1074        {
1075                if (*it == leaf)
1076                        vc1->mLeaves.erase(it);
1077                else
1078                        vc1->GetPvs().AddPvs(*(*it)->mPvs);
1079        }*/
1080
1081        leaf->SetViewCell(vc2); // finally change view cell
1082#endif
1083}
1084
1085
1086bool ViewCellsTree::ShuffleLeaves(ViewCell *l, ViewCell *r) const
1087{
1088        float cost1, cost2;
1089
1090        //-- first test if shuffling would decrease cost
1091        cost1 = GetCostHeuristics(l);
1092        cost2 = GetCostHeuristics(r);
1093
1094        const float oldCost = cost1 + cost2;
1095       
1096        float shuffledCost1 = Limits::Infinity;
1097        float shuffledCost2 = Limits::Infinity;
1098
1099        // the view cell should not be empty after the shuffle
1100#if VC_HISTORY
1101        shuffledCost1 = EvalShuffleCost(l, vc1, vc2);
1102        /shuffledCost2 = EvalShuffleCost(r, vc2, vc1);
1103
1104        // if cost of shuffle is less than old cost => shuffle
1105        if ((oldCost <= shuffledCost1) && (oldCost <= shuffledCost2))
1106                return false;
1107       
1108       
1109        if (shuffledCost1 < shuffledCost2)
1110        {
1111                ShuffleLeaf(leaf1, vc1, vc2);
1112                leaf1->Mail();
1113        }
1114        else
1115        {
1116                ShuffleLeaf(leaf2, vc2, vc1);
1117                leaf2->Mail();
1118        }
1119#endif
1120        return true;
1121}
1122
1123
1124float ViewCellsTree::GetVariance(ViewCell *vc) const
1125{
1126        const int upper = mViewCellsManager->GetMaxPvsSize();
1127        const int lower = mViewCellsManager->GetMinPvsSize();
1128
1129        if (1)
1130        {
1131                const float penalty = EvalPvsPenalty(vc->GetPvs().GetSize(), lower, upper);
1132                return (mAvgRenderCost - penalty) * (mAvgRenderCost - penalty) / (float)mNumActiveViewCells;
1133        }
1134
1135    const float leafCost = GetRenderCost(vc);
1136        return (mExpectedCost - leafCost) * (mExpectedCost - leafCost);
1137}
1138
1139
1140float ViewCellsTree::GetDeviation(ViewCell *vc) const
1141{
1142        const int upper = mViewCellsManager->GetMaxPvsSize();
1143        const int lower = mViewCellsManager->GetMinPvsSize();
1144
1145        if (1)
1146        {
1147                const float penalty = EvalPvsPenalty(vc->GetPvs().GetSize(), lower, upper);
1148                return fabs(mAvgRenderCost - penalty) / (float)mNumActiveViewCells;
1149        }
1150
1151    const float renderCost = GetRenderCost(vc);
1152        return fabs(mExpectedCost - renderCost);
1153}
1154
1155
1156
1157float ViewCellsTree::GetRenderCost(ViewCell *vc) const
1158{
1159        if (mUseAreaForPvs)
1160                return vc->GetPvs().GetSize() * vc->GetArea();
1161
1162        return vc->GetPvs().GetSize() * vc->GetVolume();
1163}
1164
1165
1166float ViewCellsTree::GetCostHeuristics(ViewCell *vc) const
1167{
1168        return GetRenderCost(vc) * mRenderCostWeight +
1169                   GetDeviation(vc) * (1.0f - mRenderCostWeight);
1170}
1171
1172
1173bool ViewCellsTree::ValidateMergeCandidate(MergeCandidate &mc) const
1174{
1175        while (mc.mLeftViewCell->mParent)
1176        {
1177                mc.mLeftViewCell = mc.mLeftViewCell->mParent;
1178        }
1179
1180        while (mc.mRightViewCell->mParent)
1181        {
1182                mc.mRightViewCell = mc.mRightViewCell->mParent;
1183        }
1184
1185        return mc.mLeftViewCell != mc.mRightViewCell;
1186}
1187
1188
1189void ViewCellsTree::EvalMergeCost(MergeCandidate &mc) const
1190{
1191        //-- compute pvs difference
1192        const int newPvs =
1193                ComputeMergedPvsSize(mc.mLeftViewCell->GetPvs(),
1194                                                         mc.mRightViewCell->GetPvs());
1195                       
1196        const float newPenalty =
1197                EvalPvsPenalty(newPvs,
1198                                           mViewCellsManager->GetMinPvsSize(),
1199                                           mViewCellsManager->GetMaxPvsSize());
1200
1201        ViewCell *vc1 = mc.mLeftViewCell;
1202        ViewCell *vc2 = mc.mRightViewCell;
1203
1204        //-- compute ratio of old cost
1205        //   (i.e., added size of left and right view cell times pvs size)
1206        //   to new rendering cost (i.e, size of merged view cell times pvs size)
1207        const float oldCost = GetRenderCost(vc1) + GetRenderCost(vc2);
1208
1209    const float newCost = mUseAreaForPvs ?
1210                (float)newPenalty * (vc1->GetArea() + vc2->GetArea()) :
1211                (float)newPenalty * (vc1->GetVolume() + vc2->GetVolume());
1212
1213
1214        // strong penalty if pvs size too large
1215        if (0 && (newPvs > mViewCellsManager->GetMaxPvsSize()))
1216        {
1217                mc.mRenderCost = 1e20f;
1218        }
1219        else
1220        {
1221                mc.mRenderCost = (newCost - oldCost) /
1222                        mViewCellsManager->GetViewSpaceBox().GetVolume();
1223        }       
1224       
1225
1226        //-- merge cost also takes deviation into account
1227        float newDev, oldDev;
1228
1229        if (1)
1230                newDev = fabs(mAvgRenderCost - newPenalty) / (float)mNumActiveViewCells;
1231        else
1232                newDev = fabs(mExpectedCost - newCost) / (float)mNumActiveViewCells;
1233       
1234        oldDev = GetDeviation(vc1) + GetDeviation(vc2);
1235
1236        // compute deviation increase
1237        mc.mDeviationIncr = newDev - oldDev;
1238       
1239        //Debug << "render cost: " << mc.mRenderCost * mRenderCostWeight << endl;
1240        //Debug << "standard deviation: " << mc.mDeviationIncr * mRenderCostWeight << endl;
1241}
1242
1243void ViewCellsTree::CompressViewCellsPvs()
1244{
1245        if (!mIsCompressed)
1246        {
1247                mIsCompressed = true;
1248                CompressViewCellsPvs(mRoot);
1249        }
1250}
1251
1252void ViewCellsTree::CompressViewCellsPvs(ViewCell *root)
1253{
1254        if (!root->IsLeaf())
1255        {
1256                ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(root);
1257
1258        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1259                // compress child sets first
1260                for (it = interior->mChildren.begin(); it != it_end; ++ it)
1261                {
1262                        CompressViewCellsPvs(*it);
1263                }
1264
1265                PropagateUpVisibility(interior);
1266        }
1267}
1268
1269
1270void ViewCellsTree::CollectBestViewCellSet(ViewCellContainer &viewCells,
1271                                                                                   const int numViewCells)
1272{
1273        TraversalQueue tqueue;
1274        tqueue.push(mRoot);
1275       
1276        while (!tqueue.empty())
1277        {
1278                ViewCell *vc = tqueue.top();
1279               
1280                // save the view cells if it is a leaf or if enough view cells have already been traversed
1281                // because of the priority queue, this will be the optimal set of v
1282                if (vc->IsLeaf() || ((viewCells.size() + tqueue.size()) >= numViewCells))
1283                {
1284                        viewCells.push_back(vc);
1285                }
1286                else
1287                {       
1288                        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
1289
1290                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1291
1292                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
1293                        {
1294                                tqueue.push(*it);
1295                        }
1296                }
1297
1298                tqueue.pop();
1299        }
1300}
1301       
1302
1303void ViewCellsTree::PropagateUpVisibility(ViewCellInterior *interior)
1304{
1305        Intersectable::NewMail((int)interior->mChildren.size());
1306
1307        ViewCellContainer::const_iterator cit, cit_end = interior->mChildren.end();
1308
1309        ObjectPvsMap::const_iterator oit;
1310
1311        // mail all objects in the leaf sets
1312        // we are interested in the objects which are present in all leaves
1313        // => count how often an object is part of a child set
1314        for (cit = interior->mChildren.begin(); cit != cit_end; ++ cit)
1315        {
1316                ViewCell *vc = *cit;
1317
1318                ObjectPvsMap::const_iterator oit_end = vc->GetPvs().mEntries.end();
1319
1320                for (oit = vc->GetPvs().mEntries.begin(); oit != oit_end; ++ oit)
1321                {
1322                        Intersectable *obj = (*oit).first;
1323                        if ((cit == interior->mChildren.begin()) && !obj->Mailed())
1324                                obj->Mail();
1325                       
1326                        int incm = obj->IncMail();
1327                }
1328        }
1329
1330        interior->GetPvs().mEntries.clear();
1331       
1332       
1333        // only the objects which are present in all leaf pvs
1334        // should remain in the parent pvs
1335        // these are the objects which have been mailed in all children
1336        for (cit = interior->mChildren.begin(); cit != cit_end; ++ cit)
1337        {
1338                ViewCell *vc = *cit;
1339
1340                ObjectPvsMap::const_iterator oit_end = vc->GetPvs().mEntries.end();
1341
1342                for (oit = vc->GetPvs().mEntries.begin(); oit != oit_end; ++ oit)
1343                {
1344                        Debug << "mail: " << (*oit).first->mMailbox << endl;
1345
1346                        if ((*oit).first->Mailed((int)interior->mChildren.size()))
1347                        {       
1348                                //Debug << "adding sample" << endl;
1349                                interior->GetPvs().AddSample((*oit).first, (*oit).second.mSumPdf);
1350                                //(*oit)->remove();
1351                        }
1352                }
1353        }
1354
1355
1356
1357        // delete all the objects from the leaf sets which were moved to parent pvs
1358        ObjectPvsMap::const_iterator oit_end = interior->GetPvs().mEntries.end();
1359
1360        for (oit = interior->GetPvs().mEntries.begin(); oit != oit_end; ++ oit)
1361        {
1362                for (cit = interior->mChildren.begin(); cit != cit_end; ++ cit)
1363                {
1364                        if (!(*cit)->GetPvs().RemoveSample((*oit).first, Limits::Infinity))
1365                                Debug << "should not come here!" << endl;
1366                }
1367        }
1368}
1369
1370
1371void ViewCellsTree::GetPvs(ViewCell *vc, ObjectPvs &pvs) const
1372{
1373        if (mIsCompressed)
1374        {
1375                ObjectPvsMap::const_iterator oit, oit_end = vc->GetPvs().mEntries.end();
1376
1377                for (oit = vc->GetPvs().mEntries.begin(); oit != oit_end; ++ oit)
1378                {
1379                        pvs.AddSample((*oit).first, (*oit).second.mSumPdf);
1380                }
1381
1382                if (!vc->IsLeaf())
1383                {
1384                        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
1385                        ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1386
1387                        for (it = interior->mChildren.begin(); it != it_end; ++ it)
1388                        {
1389                                GetPvs(*it, pvs);
1390                        }
1391                }
1392        }
1393        else
1394        {
1395                pvs = vc->GetPvs();
1396        }
1397}
1398
1399
1400int ViewCellsTree::GetPvsSize(ViewCell *vc) const
1401{
1402        int pvsSize = vc->GetPvs().GetSize();
1403
1404        //Debug << "current size: " << pvsSize << endl;
1405        if (mIsCompressed && !vc->IsLeaf())
1406        {
1407                ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
1408
1409                ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1410
1411                for (it = interior->mChildren.begin(); it != it_end; ++ it)
1412                {
1413                        pvsSize += GetPvsSize(*it);
1414                }
1415        }
1416
1417        return pvsSize; 
1418
1419}
1420
1421
1422float ViewCellsTree::GetMemoryCost(ViewCell *vc) const
1423{
1424        const float entrySize =
1425                sizeof(PvsData<Intersectable *>) + sizeof(Intersectable *);
1426
1427        return (float)GetNumPvsEntries(vc) * entrySize;
1428}
1429
1430
1431int ViewCellsTree::GetNumPvsEntries(ViewCell *vc) const
1432{
1433        int pvsSize = vc->GetPvs().GetSize();
1434
1435        if (!vc->IsLeaf())
1436        {
1437                ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
1438
1439                ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1440
1441                for (it = interior->mChildren.begin(); it != it_end; ++ it)
1442                {
1443                        pvsSize += GetNumPvsEntries(*it);
1444                }
1445        }
1446
1447        return pvsSize;         
1448}
1449
1450
1451bool ViewCellsTree::IsCompressed() const
1452{
1453        return mIsCompressed;
1454}
1455
1456
1457/**************************************************************************/
1458/*                     MergeCandidate implementation                      */
1459/**************************************************************************/
1460
1461
1462MergeCandidate::MergeCandidate(ViewCell *l, ViewCell *r):
1463mRenderCost(0),
1464mDeviationIncr(0),
1465mLeftViewCell(l),
1466mRightViewCell(r)
1467{
1468        //EvalMergeCost();
1469}
1470
1471
1472void MergeCandidate::SetRightViewCell(ViewCell *v)
1473{
1474        mRightViewCell = v;
1475}
1476
1477
1478void MergeCandidate::SetLeftViewCell(ViewCell *v)
1479{
1480        mLeftViewCell = v;
1481}
1482
1483
1484ViewCell *MergeCandidate::GetRightViewCell() const
1485{
1486        return mRightViewCell;
1487}
1488
1489
1490ViewCell *MergeCandidate::GetLeftViewCell() const
1491{
1492        return mLeftViewCell;
1493}
1494
1495
1496ViewCell *MergeCandidate::GetInitialRightViewCell() const
1497{
1498        return mInitialRightViewCell;
1499}
1500
1501
1502ViewCell *MergeCandidate::GetInitialLeftViewCell() const
1503{
1504        return mInitialLeftViewCell;
1505}
1506
1507
1508bool MergeCandidate::IsValid() const
1509{
1510        return !(mLeftViewCell->mParent || mRightViewCell->mParent);
1511}
1512
1513
1514float MergeCandidate::GetRenderCost() const
1515{
1516        return mRenderCost;
1517}
1518
1519
1520float MergeCandidate::GetDeviationIncr() const
1521{
1522        return mDeviationIncr;
1523}
1524
1525
1526float MergeCandidate::GetMergeCost() const
1527{
1528        return mRenderCost * sRenderCostWeight +
1529                   mDeviationIncr * (1.0f - sRenderCostWeight);
1530}
1531
1532
1533/************************************************************************/
1534/*                    MergeStatistics implementation                    */
1535/************************************************************************/
1536
1537
1538void MergeStatistics::Print(ostream &app) const
1539{
1540        app << "===== Merge statistics ===============\n";
1541
1542        app << setprecision(4);
1543
1544        app << "#N_CTIME ( Overall time [s] )\n" << Time() << " \n";
1545
1546        app << "#N_CCTIME ( Collect candidates time [s] )\n" << collectTime * 1e-3f << " \n";
1547
1548        app << "#N_MTIME ( Merge time [s] )\n" << mergeTime * 1e-3f << " \n";
1549
1550        app << "#N_NODES ( Number of nodes before merge )\n" << nodes << "\n";
1551
1552        app << "#N_CANDIDATES ( Number of merge candidates )\n" << candidates << "\n";
1553
1554        app << "#N_MERGEDSIBLINGS ( Number of merged siblings )\n" << siblings << "\n";
1555
1556        app << "#OVERALLCOST ( overall merge cost )\n" << overallCost << "\n";
1557
1558        app << "#N_MERGEDNODES ( Number of merged nodes )\n" << merged << "\n";
1559
1560        app << "#MAX_TREEDIST ( Maximal distance in tree of merged leaves )\n" << maxTreeDist << "\n";
1561
1562        app << "#AVG_TREEDIST ( Average distance in tree of merged leaves )\n" << AvgTreeDist() << "\n";
1563
1564        app << "#EXPECTEDCOST ( expected render cost )\n" << expectedRenderCost << "\n";
1565
1566        app << "#DEVIATION ( deviation )\n" << deviation << "\n";
1567
1568        app << "#HEURISTICS ( heuristics )\n" << heuristics << "\n";
1569       
1570
1571        app << "===== END OF BspTree statistics ==========\n";
1572}
Note: See TracBrowser for help on using the repository browser.