source: GTP/trunk/Lib/Vis/Preprocessing/src/ViewCellsManager.cpp @ 2015

Revision 2015, 168.5 KB checked in by bittner, 17 years ago (diff)

pvs efficiency tuning
Line 
1#include "ViewCellsManager.h"
2#include "RenderSimulator.h"
3#include "Mesh.h"
4#include "Triangle3.h"
5#include "ViewCell.h"
6#include "Environment.h"
7#include "X3dParser.h"
8#include "ViewCellBsp.h"
9#include "KdTree.h"
10#include "HierarchyManager.h"
11#include "Exporter.h"
12#include "VspBspTree.h"
13#include "ViewCellsParser.h"
14#include "Beam.h"
15#include "VssPreprocessor.h"
16#include "RssPreprocessor.h"
17#include "BoundingBoxConverter.h"
18#include "GlRenderer.h"
19#include "ResourceManager.h"
20#include "IntersectableWrapper.h"
21#include "VspTree.h"
22#include "OspTree.h"
23#include "BvHierarchy.h"
24#include "SamplingStrategy.h"
25#include "SceneGraph.h"
26
27#include "PerfTimer.h"
28
29
30
31#define USE_RAY_LENGTH_AS_CONTRIBUTION 0
32#define DIST_WEIGHTED_CONTRIBUTION 0
33#define SUM_RAY_CONTRIBUTIONS 1
34#define AVG_RAY_CONTRIBUTIONS 0
35#define CONTRIBUTION_RELATIVE_TO_PVS_SIZE 0
36#define PVS_ADD_DIRTY 1
37
38namespace GtpVisibilityPreprocessor {
39
40
41PerfTimer viewCellCastTimer;
42PerfTimer pvsTimer;
43PerfTimer objTimer;
44
45// HACK
46const static bool SAMPLE_AFTER_SUBDIVISION = true;
47//const static bool CLAMP_TO_BOX = false;
48const static bool CLAMP_TO_BOX = true;
49
50
51int ViewCellsManager::sRenderCostEvaluationType = 0;
52
53
54template <typename T> class myless
55{
56public:
57        //bool operator() (HierarchyNode *v1, HierarchyNode *v2) const
58        bool operator() (T v1, T v2) const
59        {
60                return (v1->GetMergeCost() < v2->GetMergeCost());
61        }
62};
63
64
65ViewCellsManager::ViewCellsManager(ViewCellsTree *viewCellsTree):
66mRenderer(NULL),
67mInitialSamples(0),
68mConstructionSamples(0),
69mPostProcessSamples(0),
70mVisualizationSamples(0),
71mTotalAreaValid(false),
72mTotalArea(0.0f),
73mViewCellsFinished(false),
74mMaxPvsSize(9999999),
75mMinPvsSize(0),
76mMaxPvsRatio(1.0),
77mViewCellPvsIsUpdated(false),
78mPreprocessor(NULL),
79mViewCellsTree(viewCellsTree),
80mUsePredefinedViewCells(false)
81{
82        mViewSpaceBox.Initialize();
83        ParseEnvironment();
84
85        mViewCellsTree->SetViewCellsManager(this);
86        mSamplesStat.Reset();
87}
88
89
90int ViewCellsManager::CastPassSamples2(const int samplesPerPass,
91                                                                           VssRayContainer &passSamples) const
92{
93        long startTime = GetTime();
94
95        SimpleRayContainer simpleRays;
96       
97        simpleRays.reserve(samplesPerPass);
98        passSamples.reserve(samplesPerPass * 2); // always creates double rays
99
100        // create one third of each type
101        int castRays = 0;
102
103        mMixtureDistribution->GenerateSamples(mSamplesPerPass, simpleRays);
104
105        cout << "generated " << (int)simpleRays.size() << " samples in "
106                 << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
107
108        startTime = GetTime();
109
110        // shoot simple ray and add it to importance samples
111        mPreprocessor->CastRays(simpleRays, passSamples, true);
112
113    cout << "cast " <<  samplesPerPass << " samples in "
114                 << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
115
116        mMixtureDistribution->ComputeContributions(passSamples);
117
118        return (int)passSamples.size();
119}
120
121
122void ViewCellsManager::ParseEnvironment()
123{
124        // visualization stuff
125        Environment::GetSingleton()->GetBoolValue("ViewCells.Visualization.exportRays", mExportRays);
126        Environment::GetSingleton()->GetBoolValue("ViewCells.Visualization.exportGeometry", mExportGeometry);
127        Environment::GetSingleton()->GetFloatValue("ViewCells.maxPvsRatio", mMaxPvsRatio);
128       
129        Environment::GetSingleton()->GetBoolValue("ViewCells.processOnlyValidViewCells", mOnlyValidViewCells);
130
131        Environment::GetSingleton()->GetIntValue("ViewCells.Construction.samples", mConstructionSamples);
132        Environment::GetSingleton()->GetIntValue("ViewCells.PostProcess.samples", mPostProcessSamples);
133        Environment::GetSingleton()->GetBoolValue("ViewCells.PostProcess.useRaysForMerge", mUseRaysForMerge);
134
135        Environment::GetSingleton()->GetIntValue("ViewCells.Visualization.samples", mVisualizationSamples);
136
137        Environment::GetSingleton()->GetIntValue("ViewCells.Construction.samplesPerPass", mSamplesPerPass);
138        Environment::GetSingleton()->GetBoolValue("ViewCells.exportToFile", mExportViewCells);
139       
140        Environment::GetSingleton()->GetIntValue("ViewCells.active", mNumActiveViewCells);
141        Environment::GetSingleton()->GetBoolValue("ViewCells.PostProcess.compress", mCompressViewCells);
142        Environment::GetSingleton()->GetBoolValue("ViewCells.Visualization.useClipPlane", mUseClipPlaneForViz);
143        Environment::GetSingleton()->GetBoolValue("ViewCells.PostProcess.merge", mMergeViewCells);
144        Environment::GetSingleton()->GetBoolValue("ViewCells.evaluateViewCells", mEvaluateViewCells);
145        Environment::GetSingleton()->GetBoolValue("ViewCells.showVisualization", mShowVisualization);
146        Environment::GetSingleton()->GetIntValue("ViewCells.Filter.maxSize", mMaxFilterSize);
147        Environment::GetSingleton()->GetFloatValue("ViewCells.Filter.width", mFilterWidth);
148        Environment::GetSingleton()->GetIntValue("ViewCells.renderCostEvaluationType", sRenderCostEvaluationType);
149
150        Environment::GetSingleton()->GetBoolValue("ViewCells.exportBboxesForPvs", mExportBboxesForPvs);
151        Environment::GetSingleton()->GetBoolValue("ViewCells.exportPvs", mExportPvs);
152
153        Environment::GetSingleton()->GetBoolValue("ViewCells.useKdPvs", mUseKdPvs);
154
155        char buf[100];
156        Environment::GetSingleton()->GetStringValue("ViewCells.samplingType", buf);
157
158        // mix of sampling strategies
159        if (0)
160        {
161                mStrategies.push_back(SamplingStrategy::OBJECT_DIRECTION_BASED_DISTRIBUTION);
162        }
163        else
164        {
165                /*mStrategies.push_back(SamplingStrategy::OBJECT_BASED_DISTRIBUTION);
166                mStrategies.push_back(SamplingStrategy::REVERSE_VIEWSPACE_BORDER_BASED_DISTRIBUTION);
167                mStrategies.push_back(SamplingStrategy::REVERSE_OBJECT_BASED_DISTRIBUTION);
168                */
169       
170                mStrategies.push_back(SamplingStrategy::SPATIAL_BOX_BASED_DISTRIBUTION);
171        }
172               
173    Debug << "casting strategies: ";
174        for (int i = 0; i < (int)mStrategies.size(); ++ i)
175                Debug << mStrategies[i] << " ";
176        Debug << endl;
177
178        // now decode distribution string
179        char buff[1024];
180        Environment::GetSingleton()->GetStringValue("RssPreprocessor.distributions", buff);
181
182        mMixtureDistribution = new MixtureDistribution(*mPreprocessor);
183        mMixtureDistribution->Construct(buff);
184
185
186        // sampling type for view cells construction samples
187        if (strcmp(buf, "object") == 0)
188        {
189                mSamplingType = SamplingStrategy::OBJECT_BASED_DISTRIBUTION;
190        }
191        else if (strcmp(buf, "box") == 0)
192        {
193                mSamplingType = SamplingStrategy::SPATIAL_BOX_BASED_DISTRIBUTION;
194        }
195        else if (strcmp(buf, "directional") == 0)
196        {
197                mSamplingType = SamplingStrategy::DIRECTION_BASED_DISTRIBUTION;
198        }
199        else if (strcmp(buf, "object_directional") == 0)
200        {
201                mSamplingType = SamplingStrategy::OBJECT_DIRECTION_BASED_DISTRIBUTION;
202        }
203        else if (strcmp(buf, "reverse_object") == 0)
204        {
205                mSamplingType = SamplingStrategy::REVERSE_OBJECT_BASED_DISTRIBUTION;
206        }
207        /*else if (strcmp(buf, "interior") == 0)
208        {
209                mSamplingType = Preprocessor::OBJECTS_INTERIOR_DISTRIBUTION;
210        }*/
211        else
212        {
213                Debug << "error! wrong sampling type" << endl;
214                exit(0);
215        }
216
217        // sampling type for evaluation samples
218        Environment::GetSingleton()->GetStringValue("ViewCells.Evaluation.samplingType", buf);
219       
220        if (strcmp(buf, "object") == 0)
221        {
222                mEvaluationSamplingType = SamplingStrategy::OBJECT_BASED_DISTRIBUTION;
223        }
224        else if (strcmp(buf, "box") == 0)
225        {
226                mEvaluationSamplingType = SamplingStrategy::SPATIAL_BOX_BASED_DISTRIBUTION;
227        }
228        else if (strcmp(buf, "directional") == 0)
229        {
230                mEvaluationSamplingType = SamplingStrategy::DIRECTION_BASED_DISTRIBUTION;
231        }
232        else if (strcmp(buf, "object_directional") == 0)
233        {
234                mEvaluationSamplingType = SamplingStrategy::OBJECT_DIRECTION_BASED_DISTRIBUTION;
235        }
236        else if (strcmp(buf, "reverse_object") == 0)
237        {
238                mEvaluationSamplingType = SamplingStrategy::REVERSE_OBJECT_BASED_DISTRIBUTION;
239        }
240        /*else if (strcmp(buf, "interior") == 0)
241        {
242                mEvaluationSamplingType = SamplingStrategy::OBJECTS_INTERIOR_DISTRIBUTION;
243        }*/
244        else
245        {
246                mEvaluationSamplingType = -1;
247                Debug << "error! wrong sampling type" << endl;
248                exit(0);
249        }
250
251        Environment::GetSingleton()->GetStringValue("ViewCells.renderCostEvaluationType", buf);
252       
253        if (strcmp(buf, "perobject") == 0)
254        {
255                sRenderCostEvaluationType = ViewCellsManager::PER_OBJECT;
256        }
257        else if (strcmp(buf, "pertriangle") == 0)
258        {
259                sRenderCostEvaluationType = ViewCellsManager::PER_TRIANGLE;
260        }
261        else
262        {
263                Debug << "error! wrong sampling type" << endl;
264                exit(0);
265        }
266
267    Environment::GetSingleton()->GetStringValue("ViewCells.Visualization.colorCode", buf);
268
269        if (strcmp(buf, "PVS") == 0)
270                mColorCode = 1;
271        else if (strcmp(buf, "MergedLeaves") == 0)
272                mColorCode = 2;
273        else if (strcmp(buf, "MergedTreeDiff") == 0)
274                mColorCode = 3;
275        else
276                mColorCode = 0;
277
278
279        Debug << "************ View Cells Manager options ***************" << endl;
280        Debug << "color code: " << mColorCode << endl;
281
282        Debug << "export rays: " << mExportRays << endl;
283        Debug << "export geometry: " << mExportGeometry << endl;
284        Debug << "max pvs ratio: " << mMaxPvsRatio << endl;
285       
286        Debug << "process only valid view cells: " << mOnlyValidViewCells << endl;
287        Debug << "construction samples: " << mConstructionSamples << endl;
288        Debug << "post process samples: " << mPostProcessSamples << endl;
289        Debug << "post process use rays for merge: " << mUseRaysForMerge << endl;
290        Debug << "visualization samples: " << mVisualizationSamples << endl;
291        Debug << "construction samples per pass: " << mSamplesPerPass << endl;
292        Debug << "export to file: " << mExportViewCells << endl;
293       
294        Debug << "active view cells: " << mNumActiveViewCells << endl;
295        Debug << "post process compress: " << mCompressViewCells << endl;
296        Debug << "visualization use clipPlane: " << mUseClipPlaneForViz << endl;
297        Debug << "post process merge: " << mMergeViewCells << endl;
298        Debug << "evaluate view cells: " << mEvaluateViewCells << endl;
299        Debug << "sampling type: " << mSamplingType << endl;
300        Debug << "render cost evaluation type: " << sRenderCostEvaluationType << endl;
301        Debug << "evaluation sampling type: " << mEvaluationSamplingType << endl;
302        Debug << "show visualization: " << mShowVisualization << endl;
303        Debug << "filter width: " << mFilterWidth << endl;
304        Debug << "sample after subdivision: " << SAMPLE_AFTER_SUBDIVISION << endl;
305
306        Debug << "export bounding boxes: " << mExportBboxesForPvs << endl;
307        Debug << "export pvs for view cells: " << mExportPvs << endl;
308        Debug << "use kd pvs " << mUseKdPvs << endl;
309        Debug << endl;
310}
311
312
313ViewCellsManager::~ViewCellsManager()
314{
315        // HACK: if view cells tree does not
316        // handle view cells, we have to do it here
317        // question: rather create view cells resource manager?
318        if (!ViewCellsTreeConstructed())
319        {
320                CLEAR_CONTAINER(mViewCells);
321        }
322        else
323        {
324                DEL_PTR(mViewCellsTree);
325        }
326
327        DEL_PTR(mMixtureDistribution);
328}
329
330
331Intersectable *
332ViewCellsManager::GetIntersectable(const VssRay &ray, const bool isTermination) const
333{
334        if (mUseKdPvs)
335        {
336          KdNode *node = GetPreprocessor()->mKdTree->GetPvsNode(isTermination ?
337                                                                                                                        ray.mTermination : ray.mOrigin);
338          return GetPreprocessor()->mKdTree->GetOrCreateKdIntersectable(node);
339        }
340        else
341          {
342                return isTermination ? ray.mTerminationObject : ray.mOriginObject;
343          }
344}
345
346
347void
348ViewCellsManager::CollectObjects(const AxisAlignedBox3 &box, ObjectContainer &objects)
349{
350        GetPreprocessor()->mKdTree->CollectObjects(box, objects);
351}
352
353AxisAlignedBox3 ViewCellsManager::GetViewCellBox(ViewCell *vc)
354{
355  Mesh *m = vc->GetMesh();
356 
357  if (m)
358  {
359          m->ComputeBoundingBox();
360          return m->mBox;
361  }
362
363  AxisAlignedBox3 box;
364  box.Initialize();
365 
366  if (!vc->IsLeaf()) {
367        ViewCellInterior *vci = (ViewCellInterior *) vc;
368       
369        ViewCellContainer::iterator it = vci->mChildren.begin();
370        for (; it != vci->mChildren.end(); ++it) {
371          box.Include(GetViewCellBox(*it));
372        }
373  }
374 
375  return box;
376}
377
378
379int ViewCellsManager::CastPassSamples(const int samplesPerPass,
380                                                                          const vector<int> &strategies,
381                                                                          VssRayContainer &passSamples
382                                                                          ) const
383{
384        long startTime = GetTime();
385
386        SimpleRayContainer simpleRays;
387       
388        simpleRays.reserve(samplesPerPass);
389        passSamples.reserve(samplesPerPass * 2); // always creates double rays
390
391        // create one third of each type
392        int castRays = 0;
393       
394        const int numRaysPerPass = samplesPerPass / (int)strategies.size();
395        vector<int>::const_iterator iit, iit_end = strategies.end();
396
397        for (iit = strategies.begin(); iit != iit_end; ++ iit)
398        {
399                const int stype = *iit;
400                const int newRays =
401                        mPreprocessor->GenerateRays(numRaysPerPass, stype, simpleRays);
402
403                cout << "cast " << newRays << " rays of strategy " << stype << endl;
404                castRays += newRays;
405        }
406
407        cout << "generated " << samplesPerPass << " samples in "
408                 << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
409
410        startTime = GetTime();
411
412        // shoot simple ray and add it to importance samples
413        mPreprocessor->CastRays(simpleRays, passSamples, true);
414        cout << "cast " <<  samplesPerPass << " samples in "
415                 << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
416
417        return (int)passSamples.size();
418}
419
420
421/// helper function which destroys rays or copies them into the output ray container
422inline void disposeRays(VssRayContainer &rays, VssRayContainer *outRays)
423{
424        cout << "disposing samples ... ";
425        long startTime = GetTime();
426        int n = (int)rays.size();
427
428        if (outRays)
429        {
430                VssRayContainer::const_iterator it, it_end = rays.end();
431                for (it = rays.begin(); it != it_end; ++ it)
432                {
433                        outRays->push_back(*it);
434                }
435        }
436        else
437        {
438                VssRayContainer::const_iterator it, it_end = rays.end();
439                for (it = rays.begin(); it != it_end; ++ it)
440                {
441                        if (!(*it)->IsActive())
442                                delete (*it);
443                }
444        }
445
446        cout << "finished" << endl;
447        Debug << "disposed " << n << " samples in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
448}
449
450
451int ViewCellsManager::Construct(Preprocessor *preprocessor, VssRayContainer *outRays)
452{
453        int numSamples = 0;
454
455        SimpleRayContainer simpleRays;
456        VssRayContainer initialSamples;
457
458        // store pointer to preprocessor for further use during construction
459        mPreprocessor = preprocessor;
460       
461
462        ///////////////////////////////////////////////////////
463        //-- Initial sampling for the construction of the view cell hierarchy.
464        //-- We use uniform sampling / box based sampling.
465       
466        long startTime = GetTime();
467        cout << "view cell construction: casting " << mInitialSamples << " initial samples ... " << endl;
468
469        // cast initial samples
470       
471        // mix of sampling strategies
472        vector<int>dummy;
473        //dummy.push_back(SamplingStrategy::OBJECT_BASED_DISTRIBUTION);
474        //dummy.push_back(SamplingStrategy::SPATIAL_BOX_BASED_DISTRIBUTION);
475        //dummy.push_back(SamplingStrategy::REVERSE_OBJECT_BASED_DISTRIBUTION);
476
477        CastPassSamples(mInitialSamples, mStrategies, initialSamples);
478
479        cout << "finished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
480
481        // construct view cells
482        ConstructSubdivision(preprocessor->mObjects, initialSamples);
483
484        // initial samples count for overall samples ...
485        numSamples += mInitialSamples;
486
487        // rays can be passed or deleted
488        disposeRays(initialSamples, outRays);
489
490        cout << "time needed for initial construction: "
491                 << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
492
493        Debug << "time needed for initial construction: "
494                  << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
495
496        // collect view cells and compute statistics
497        ResetViewCells();
498
499
500        ///////////////////
501        //-- Initial hierarchy construction finished.
502        //-- We can do some stats and visualization
503       
504        if (0)
505        {
506                //-- export initial view cell partition
507                Debug << "\nView cells after initial sampling:\n" << mCurrentViewCellsStats << endl;
508
509                const string filename("viewcells.wrl");
510                Exporter *exporter = Exporter::GetExporter(filename.c_str());
511       
512                if (exporter)
513                {
514                        cout << "exporting initial view cells (=leaves) to " << filename.c_str() << " ... ";
515
516                        if (mExportGeometry)
517                        {
518                                exporter->ExportGeometry(preprocessor->mObjects);
519                        }
520
521                        exporter->SetWireframe();
522                        ExportViewCellsForViz(exporter, NULL, mColorCode, GetClipPlane());
523
524                        delete exporter;
525                        cout << "finished" << endl;
526                }
527        }
528
529
530        //////////////////////
531        //-- Cast some more sampling after initial construction.
532        //-- The additional rays can be used to gain
533        //-- some more information before the bottom-up merge
534        //-- note: guided rays could be used for this task
535
536        // time spent after construction of the initial partition
537        startTime = GetTime();
538        const int n = mConstructionSamples; //+initialSamples;
539
540        while (numSamples < n)
541        {
542                cout << "casting " << mSamplesPerPass << " samples of " << n << " ... ";
543                Debug << "casting " << mSamplesPerPass << " samples of " << n << " ... ";
544
545                VssRayContainer constructionSamples;
546
547                // cast new samples
548                numSamples += CastPassSamples(mSamplesPerPass,
549                                                                          mStrategies,
550                                                                          constructionSamples);
551
552                cout << "finished" << endl;
553                cout << "computing sample contribution for " << (int)constructionSamples.size() << " samples ... ";
554
555                // computes sample contribution of cast rays TODO: leak?
556                if (SAMPLE_AFTER_SUBDIVISION)
557                        ComputeSampleContributions(constructionSamples, true, false);
558
559                cout << "finished" << endl;
560
561                disposeRays(constructionSamples, outRays);
562                cout << "total samples: " << numSamples << endl;
563        }
564
565        if (0)
566        {
567                ///////////////
568                //-- Get stats after the additional sampling step
569                //-- and before the bottom-up merge step
570
571                EvaluateViewCellsStats();
572                Debug << "\noriginal view cell partition before post process:\n"
573                          << mCurrentViewCellsStats << endl;
574       
575                mRenderer->RenderScene();
576                SimulationStatistics ss;
577                dynamic_cast<RenderSimulator *>(mRenderer)->GetStatistics(ss);
578
579                Debug << ss << endl;
580        }
581
582        ////////////////////
583        //-- post processing of the initial construction
584        //-- We can bottom-up merge the view cells in this step
585        //-- We can additionally cast some post processing sample rays.
586        //-- These rays can be used to store the view cells with the rays
587
588        VssRayContainer postProcessSamples;
589        cout << "casting " << mPostProcessSamples << " post processing samples ... ";
590       
591        CastPassSamples(mPostProcessSamples, mStrategies, postProcessSamples);
592
593        cout << "finished" << endl;
594        cout << "starting post processing and visualization" << endl;
595
596        // store view cells with rays for post processing?
597        const bool storeViewCells = true;
598
599        if (SAMPLE_AFTER_SUBDIVISION)
600                ComputeSampleContributions(postProcessSamples, true, storeViewCells);
601
602        PostProcess(preprocessor->mObjects, postProcessSamples);
603
604        const float secs = TimeDiff(startTime, GetTime()) * 1e-3f;
605        cout << "post processing (=merge) finished in " << secs << " secs" << endl;
606
607        Debug << "post processing time: " << secs << endl;
608        disposeRays(postProcessSamples, outRays);
609
610
611        ////////////////
612        //-- Evaluation of the resulting view cell partition.
613        //-- We cast a number of new samples and measure the render cost
614
615        if (mEvaluateViewCells)
616        {
617                EvalViewCellPartition();
618        }
619       
620        /////////////////
621        //-- Show some visualizations
622
623        if (mShowVisualization)
624        {
625                if (0)
626                {
627                        mStrategies.clear();
628                        mStrategies.push_back(SamplingStrategy::VIEWCELL_BORDER_BASED_DISTRIBUTION);
629                }
630
631                ///////////////
632                //-- visualization rays, e.g., to show some samples in the scene
633               
634                VssRayContainer visSamples;
635                int numSamples = CastPassSamples(mVisualizationSamples,
636                                                                                 mStrategies,
637                                                                                 visSamples);
638
639                if (SAMPLE_AFTER_SUBDIVISION)
640                        ComputeSampleContributions(visSamples, true, storeViewCells);
641
642                // various visualizations
643                Visualize(preprocessor->mObjects, visSamples);
644
645                disposeRays(visSamples, outRays);
646        }
647
648        // recalculate view cells
649        EvaluateViewCellsStats();
650
651        if (1) CompressViewCells();
652
653        // write view cells to disc
654        if (mExportViewCells)
655        {
656                char filename[100];
657
658                Environment::GetSingleton()->GetStringValue("ViewCells.filename", filename);
659                ExportViewCells(filename, mExportPvs, mPreprocessor->mObjects);
660        }
661
662        return numSamples;
663}
664
665
666AxisAlignedPlane *ViewCellsManager::GetClipPlane()
667{
668        return mUseClipPlaneForViz ? &mClipPlaneForViz : NULL;
669}
670
671
672
673
674ViewCellsManager *ViewCellsManager::LoadViewCells(const string &filename,
675                                                                                                  ObjectContainer *objects,
676                                                                                                  bool finalizeViewCells,
677                                                                                                  BoundingBoxConverter *bconverter)
678                                                                                                 
679{
680        ViewCellsParser parser;
681        ViewCellsManager *vm = NULL;
682
683        const long startTime = GetTime();
684        bool success = parser.ParseViewCellsFile(filename, &vm, objects, bconverter);
685
686        cout<<"viewcells parsed "<<endl<<flush;
687       
688        if (success)
689        {
690                if (0)
691                {
692                        vm->ResetViewCells();
693                }
694                else
695                {
696                        //hack: should work with reset function
697                        ViewCellContainer leaves;
698
699                        vm->mViewCells.clear();
700                        vm->mViewCellsTree->CollectLeaves(vm->mViewCellsTree->GetRoot(), leaves);
701               
702                        ViewCellContainer::const_iterator it, it_end = leaves.end();
703
704                        for (it = leaves.begin(); it != it_end; ++ it)
705                        {
706                                vm->mViewCells.push_back(*it);
707                        }
708                }
709
710                vm->mViewCellsFinished = true;
711                vm->mMaxPvsSize = (int)objects->size();
712
713                if (finalizeViewCells)
714                {
715                        // create the meshes and compute volumes
716                        vm->FinalizeViewCells(true);
717                        // vm->mViewCellsTree->AssignRandomColors();
718                }
719
720                Debug << (int)vm->mViewCells.size() << " view cells loaded in "
721                          << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
722        }
723        else
724        {
725                Debug << "Error: loading view cells failed!" << endl;
726                DEL_PTR(vm);
727        }
728
729        return vm;
730}
731
732
733bool VspBspViewCellsManager::ExportViewCells(const string filename,
734                                                                                         const bool exportPvs,
735                                                                                         const ObjectContainer &objects)
736{
737        if (!ViewCellsConstructed() || !ViewCellsTreeConstructed())
738        {
739                return false;
740        }
741
742        cout << "exporting view cells to xml ... ";
743
744        OUT_STREAM stream(filename.c_str());
745
746        // for output we need unique ids for each view cell
747        CreateUniqueViewCellIds();
748
749        stream << "<?xml version=\"1.0\" encoding=\"UTF-8\"?>"<<endl;
750        stream << "<VisibilitySolution>" << endl;
751
752        if (exportPvs)
753        {
754                //-- export bounding boxes
755                stream << "<BoundingBoxes>" << endl;
756
757                if (mUseKdPvs)
758                {
759                        vector<KdIntersectable *>::iterator kit, kit_end = GetPreprocessor()->mKdTree->mKdIntersectables.end();
760
761                        int id = 0;
762                        for (kit = GetPreprocessor()->mKdTree->mKdIntersectables.begin(); kit != kit_end; ++ kit, ++ id)
763                        {
764                                Intersectable *obj = *kit;
765                                const AxisAlignedBox3 box = obj->GetBox();
766                 
767                                obj->SetId(id);
768       
769                                stream << "<BoundingBox" << " id=\"" << id << "\""
770                                           << " min=\"" << box.Min().x << " " << box.Min().y << " " << box.Min().z << "\""
771                                           << " max=\"" << box.Max().x << " " << box.Max().y << " " << box.Max().z << "\" />" << endl;
772                        }
773                }
774                else
775                {
776                        ObjectContainer::const_iterator oit, oit_end = objects.end();
777               
778                        for (oit = objects.begin(); oit != oit_end; ++ oit)
779                        {
780                                const AxisAlignedBox3 box = (*oit)->GetBox();
781
782                                ////////////
783                                //-- the bounding boxes
784
785                                stream << "<BoundingBox" << " id=\"" << (*oit)->GetId() << "\""
786                                           << " min=\"" << box.Min().x << " " << box.Min().y << " " << box.Min().z << "\""
787                                           << " max=\"" << box.Max().x << " " << box.Max().y << " " << box.Max().z << "\" />" << endl;
788                        }
789                }
790
791                stream << "</BoundingBoxes>" << endl;
792        }
793
794       
795        /////////////
796        //-- export the view cells and the pvs
797
798        const int numViewCells = mCurrentViewCellsStats.viewCells;
799        stream << "<ViewCells number=\"" << numViewCells << "\" >" << endl;
800
801        mViewCellsTree->Export(stream, exportPvs);
802
803        stream << "</ViewCells>" << endl;
804
805
806        //////////
807        //-- export the view space hierarchy
808       
809        stream << "<ViewSpaceHierarchy type=\"bsp\""
810                   << " min=\"" << mViewSpaceBox.Min().x << " " << mViewSpaceBox.Min().y << " " << mViewSpaceBox.Min().z << "\""
811                   << " max=\"" << mViewSpaceBox.Max().x << " " << mViewSpaceBox.Max().y << " " << mViewSpaceBox.Max().z << "\">" << endl;
812
813        mVspBspTree->Export(stream);
814        stream << "</ViewSpaceHierarchy>" << endl;
815
816        stream << "</VisibilitySolution>" << endl;
817
818        stream.close();
819        cout << "finished" << endl;
820
821        return true;
822}
823
824void ViewCellsManager::EvalViewCellHistogram(const string filename,
825                                                                                         const int nViewCells)
826{
827        std::ofstream outstream;
828        outstream.open(filename.c_str());
829
830        ViewCellContainer viewCells;
831        // $$ JB hack - the collect best viewcells does not work?
832#if 1
833        mViewCellsTree->CollectBestViewCellSet(viewCells, nViewCells);
834#else
835        viewCells = mViewCells;
836#endif
837
838        float maxRenderCost, minRenderCost;
839
840        // sort by render cost
841        sort(viewCells.begin(), viewCells.end(), ViewCell::SmallerRenderCost);
842
843        minRenderCost = viewCells.front()->GetRenderCost();
844        maxRenderCost = viewCells.back()->GetRenderCost();
845
846        Debug << "histogram min rc: " << minRenderCost << " max rc: " << maxRenderCost << endl;
847
848    int histoIntervals;
849        Environment::GetSingleton()->GetIntValue("Preprocessor.histogram.intervals", histoIntervals);
850        const int intervals = min(histoIntervals, (int)viewCells.size());
851
852        int histoMaxVal;
853        Environment::GetSingleton()->GetIntValue("Preprocessor.histogram.maxValue", histoMaxVal);
854        maxRenderCost = min((float)histoMaxVal, maxRenderCost);
855
856       
857        const float range = maxRenderCost - minRenderCost;
858        const float stepSize = range / (float)intervals;
859
860        float currentRenderCost = minRenderCost;//(int)ceil(minRenderCost);
861
862        const float totalRenderCost = mViewCellsTree->GetRoot()->GetRenderCost();
863        const float totalVol = GetViewSpaceBox().GetVolume();
864        //const float totalVol = mViewCellsTree->GetRoot()->GetVolume();
865
866        int j = 0;
867        int i = 0;
868       
869        ViewCellContainer::const_iterator it = viewCells.begin(), it_end = viewCells.end();             
870
871        // count for integral
872        float volSum = 0;
873        int smallerCostSum = 0;
874       
875        // note can skip computations for view cells already
876        // evaluated and delete them from vector ...
877    while (1)
878        {
879                // count for histogram value
880                float volDif = 0;
881                int smallerCostDif = 0;
882
883                while ((i < (int)viewCells.size()) && (viewCells[i]->GetRenderCost() < currentRenderCost))
884                {
885                        volSum += viewCells[i]->GetVolume();
886                        volDif += viewCells[i]->GetVolume();
887
888                        ++ i;
889                        ++ smallerCostSum;
890                        ++ smallerCostDif;
891                }
892               
893                if ((i >= (int)viewCells.size()) || (currentRenderCost >= maxRenderCost))
894                        break;
895               
896                const float rcRatio = currentRenderCost / maxRenderCost;
897                const float volRatioSum = volSum / totalVol;
898                const float volRatioDif = volDif / totalVol;
899
900                outstream << "#Pass\n" << j ++ << endl;
901                outstream << "#RenderCostRatio\n" << rcRatio << endl;
902                outstream << "#WeightedCost\n" << currentRenderCost / totalVol << endl;
903                outstream << "#ViewCellsDif\n" << smallerCostDif << endl;
904                outstream << "#ViewCellsSum\n" << smallerCostSum << endl;       
905                outstream << "#VolumeDif\n" << volRatioDif << endl << endl;
906                outstream << "#VolumeSum\n" << volRatioSum << endl << endl;
907
908                // increase current render cost
909                currentRenderCost += stepSize;
910        }
911
912        outstream.close();
913}
914
915void ViewCellsManager::EvalViewCellHistogramForPvsSize(const string filename,
916                                                                                                           const int nViewCells)
917{
918        std::ofstream outstream;
919        outstream.open(filename.c_str());
920
921        ViewCellContainer viewCells;
922       
923        // $$ JB hack - the collect best viewcells does not work?
924#if 0
925        mViewCellsTree->CollectBestViewCellSet(viewCells, nViewCells);
926#else
927        viewCells = mViewCells;
928#endif
929        ViewCellContainer::iterator it = viewCells.begin(), it_end = viewCells.end();           
930        for (; it != it_end; ++it)
931        {
932                if (1)
933                        (*it)->UpdatePvsCost();
934                else
935                        (*it)->SetPvsCost((float)(*it)->GetFilteredPvsSize());
936        }
937
938        float maxPvs, maxVal, minVal;
939       
940        // sort by pvs size
941        sort(viewCells.begin(), viewCells.end(), ViewCell::SmallerPvs);
942
943        maxPvs = viewCells.back()->GetPvsCost();
944        minVal = 0;
945
946        // hack: normalize pvs size
947        int histoMaxVal;
948        Environment::GetSingleton()->GetIntValue("Preprocessor.histogram.maxValue", histoMaxVal);
949        maxVal = max((float)histoMaxVal, maxPvs);
950               
951        Debug << "histogram minpvssize: " << minVal << " maxpvssize: " << maxVal
952                << " real maxpvs " << maxPvs << endl;
953
954        int histoIntervals;
955        Environment::GetSingleton()->GetIntValue("Preprocessor.histogram.intervals", histoIntervals);
956        const int intervals = min(histoIntervals, (int)viewCells.size());
957
958        const float range = maxVal - minVal;
959        int stepSize = (int)(range / intervals);
960
961        // set step size to avoid endless loop
962        if (!stepSize) stepSize = 1;
963       
964        Debug << "intervals " << histoIntervals << endl;
965        Debug << "stepsize: " << stepSize << endl;
966        cout << "intervals " << histoIntervals << endl;
967        cout << "stepsize: " << stepSize << endl;
968
969        const float totalRenderCost = mViewCellsTree->GetRoot()->GetRenderCost();
970        const float totalVol = GetViewSpaceBox().GetVolume();
971
972        float currentPvs = minVal;
973       
974        int i = 0;
975        int j = 0;
976        float volSum = 0;
977        int smallerSum = 0;
978
979        it = viewCells.begin();
980       
981        for (int j = 0; j < intervals; ++ j)
982        {
983                float volDif = 0;
984                int smallerDif = 0;
985
986                while ((i < (int)viewCells.size()) &&
987                           (viewCells[i]->GetPvsCost() < currentPvs))
988                {
989                        volDif += viewCells[i]->GetVolume();
990                        volSum += viewCells[i]->GetVolume();
991
992                        ++ i;
993                        ++ smallerDif;
994                        ++ smallerSum;
995                }
996               
997                //              if (0 && (i < (int)viewCells.size()))
998                //                Debug << "new pvs cost increase: " << mViewCellsTree->GetPvsCost(viewCells[i])
999                //                              << " " << currentPvs << endl;
1000               
1001                const float volRatioDif = volDif / totalVol;
1002                const float volRatioSum = volSum / totalVol;
1003
1004                outstream << "#Pass\n" << j << endl;
1005                outstream << "#Pvs\n" << currentPvs << endl;
1006                outstream << "#ViewCellsDif\n" << smallerDif << endl;
1007                outstream << "#ViewCellsSum\n" << smallerSum << endl;   
1008                outstream << "#VolumeDif\n" << volRatioDif << endl << endl;
1009                outstream << "#VolumeSum\n" << volRatioSum << endl << endl;
1010       
1011                //-- increase current pvs size to define next interval
1012                currentPvs += stepSize;
1013        }
1014
1015        outstream.close();
1016}
1017
1018
1019void ViewCellsManager::EvalViewCellHistogramForPvsSize(const string filename,
1020                                                                                                           ViewCellContainer &viewCells)
1021{
1022        std::ofstream outstream;
1023        outstream.open(filename.c_str());
1024
1025        float maxPvs, maxVal, minVal;
1026       
1027        // sort by pvs size
1028        sort(viewCells.begin(), viewCells.end(), ViewCell::SmallerPvs);
1029
1030        maxPvs = viewCells.back()->GetPvsCost();
1031        minVal = 0;
1032
1033        // hack: normalize pvs size
1034        int histoMaxVal;
1035        Environment::GetSingleton()->GetIntValue("Preprocessor.histogram.maxValue", histoMaxVal);
1036        maxVal = max((float)histoMaxVal, maxPvs);
1037               
1038        Debug << "histogram minpvssize: " << minVal << " maxpvssize: " << maxVal
1039                << " real maxpvs " << maxPvs << endl;
1040
1041        int histoIntervals;
1042        Environment::GetSingleton()->GetIntValue("Preprocessor.histogram.intervals", histoIntervals);
1043        const int intervals = min(histoIntervals, (int)viewCells.size());
1044
1045        const float range = maxVal - minVal;
1046        int stepSize = (int)(range / intervals);
1047
1048        // set step size to avoid endless loop
1049        if (!stepSize) stepSize = 1;
1050       
1051        Debug << "intervals " << histoIntervals << endl;
1052        Debug << "stepsize: " << stepSize << endl;
1053        cout << "intervals " << histoIntervals << endl;
1054        cout << "stepsize: " << stepSize << endl;
1055
1056        const float totalRenderCost = mViewCellsTree->GetRoot()->GetRenderCost();
1057        const float totalVol = GetViewSpaceBox().GetVolume();
1058
1059        float currentPvs = minVal;
1060       
1061        int i = 0;
1062        int j = 0;
1063        float volSum = 0;
1064        int smallerSum = 0;
1065
1066        //ViewCellContainer::const_iterator it = viewCells.begin(), it_end = viewCells.end();   
1067       
1068        for (int j = 0; j < intervals; ++ j)
1069        {
1070                float volDif = 0;
1071                int smallerDif = 0;
1072
1073                while ((i < (int)viewCells.size()) &&
1074                           (viewCells[i]->GetPvsCost() < currentPvs))
1075                {
1076                        volDif += viewCells[i]->GetVolume();
1077                        volSum += viewCells[i]->GetVolume();
1078
1079                        ++ i;
1080                        ++ smallerDif;
1081                        ++ smallerSum;
1082                }
1083               
1084                //              if (0 && (i < (int)viewCells.size()))
1085                //                Debug << "new pvs cost increase: " << mViewCellsTree->GetPvsCost(viewCells[i])
1086                //                              << " " << currentPvs << endl;
1087               
1088                const float volRatioDif = volDif / totalVol;
1089                const float volRatioSum = volSum / totalVol;
1090
1091                outstream << "#Pass\n" << j << endl;
1092                outstream << "#Pvs\n" << currentPvs << endl;
1093                outstream << "#ViewCellsDif\n" << smallerDif << endl;
1094                outstream << "#ViewCellsSum\n" << smallerSum << endl;   
1095                outstream << "#VolumeDif\n" << volRatioDif << endl << endl;
1096                outstream << "#VolumeSum\n" << volRatioSum << endl << endl;
1097       
1098                //-- increase current pvs size to define next interval
1099                currentPvs += stepSize;
1100        }
1101
1102        outstream.close();
1103}
1104
1105
1106bool ViewCellsManager::GetExportPvs() const
1107{
1108        return mExportPvs;
1109}
1110
1111
1112void ViewCellsManager::ResetPvs()
1113{
1114        if (ViewCellsTreeConstructed())
1115        {
1116                mViewCellsTree->ResetPvs();
1117        }
1118        else
1119        {
1120                cout << "view cells tree not constructed" << endl;
1121        }
1122}
1123
1124
1125void ViewCellsManager::ExportStats(const string &fileName)
1126{
1127        mViewCellsTree->ExportStats(fileName);
1128}
1129
1130
1131void ViewCellsManager::EvalViewCellPartition()
1132{
1133        int samplesPerPass;
1134        int numSamples;
1135        int castSamples = 0;
1136        char str[64];
1137        int oldSamples = 0;
1138
1139        int samplesForStats;
1140
1141        Environment::GetSingleton()->GetIntValue("ViewCells.Evaluation.samplesPerPass", samplesPerPass);
1142        Environment::GetSingleton()->GetIntValue("ViewCells.Evaluation.samplesForStats", samplesForStats);
1143        Environment::GetSingleton()->GetIntValue("ViewCells.Evaluation.samples", numSamples);
1144
1145        char statsPrefix[100];
1146        Environment::GetSingleton()->GetStringValue("ViewCells.Evaluation.statsPrefix", statsPrefix);
1147
1148        Debug << "view cell evaluation samples per pass: " << samplesPerPass << endl;
1149        Debug << "view cell evaluation samples: " << numSamples << endl;
1150        Debug << "view cell stats prefix: " << statsPrefix << endl;
1151
1152        cout << "reseting pvs ... ";
1153               
1154        const bool startFromZero = true;
1155
1156        // reset pvs and start over from zero
1157        if (startFromZero)
1158        {
1159                mViewCellsTree->ResetPvs();
1160        }
1161        else // start from current sampless
1162        {
1163                // statistics before casting more samples
1164                cout << "compute new statistics ... ";
1165                sprintf(str, "-%09d-eval.log", castSamples);
1166                string fName = string(statsPrefix) + string(str);
1167
1168                mViewCellsTree->ExportStats(fName);
1169                cout << "finished" << endl;
1170        }
1171
1172        cout << "finished" << endl;
1173    cout << "Evaluating view cell partition ... " << endl;
1174
1175        while (castSamples < numSamples)
1176        {               
1177                ///////////////
1178                //-- we have to use uniform sampling strategy for construction rays
1179
1180                VssRayContainer evaluationSamples;
1181                const int samplingType = mEvaluationSamplingType;
1182
1183                long startTime = GetTime();
1184
1185                cout << "casting " << samplesPerPass << " samples ... ";
1186                Debug << "casting " << samplesPerPass << " samples ... ";
1187
1188                CastPassSamples(samplesPerPass, mStrategies, evaluationSamples);
1189               
1190                castSamples += samplesPerPass;
1191
1192                Real timeDiff = TimeDiff(startTime, GetTime());
1193               
1194                cout << "finished in " << timeDiff * 1e-3f << " secs" << endl;
1195                cout << "computing sample contributions of " << (int)evaluationSamples.size()  << " samples ... ";
1196               
1197                Debug << "finished in " << timeDiff * 1e-3f << " secs" << endl;
1198                Debug << "computing sample contributions of " << (int)evaluationSamples.size()  << " samples ... ";
1199
1200                startTime = GetTime();
1201
1202                ComputeSampleContributions(evaluationSamples, true, false);
1203
1204                timeDiff = TimeDiff(startTime, GetTime());
1205                cout << "finished in " << timeDiff * 1e-3 << " secs" << endl;
1206                Debug << "finished in " << timeDiff * 1e-3 << " secs" << endl;
1207
1208                if ((castSamples >= samplesForStats + oldSamples) || (castSamples >= numSamples))
1209                {
1210                        oldSamples += samplesForStats;
1211
1212                        ///////////
1213                        //-- output stats
1214
1215                        sprintf(str, "-%09d-eval.log", castSamples);
1216                        string fileName = string(statsPrefix) + string(str);
1217
1218                        ///////////////
1219                        //-- propagate pvs or pvs size information
1220
1221                        startTime = GetTime();
1222                        ObjectPvs pvs;
1223
1224                        cout << "updating pvs for evaluation ... " << endl;
1225
1226                        UpdatePvsForEvaluation(mViewCellsTree->GetRoot(), pvs);
1227
1228                        timeDiff = TimeDiff(startTime, GetTime());
1229                        cout << "finished updating the pvs in " << timeDiff * 1e-3 << " secs" << endl;
1230                        Debug << "pvs evaluated in " << timeDiff * 1e-3 << " secs" << endl;
1231               
1232                        startTime = GetTime();
1233                        cout << "compute new statistics ... " << endl;
1234
1235                        ExportStats(fileName);
1236
1237                        timeDiff = TimeDiff(startTime, GetTime());
1238                        cout << "finished in " << timeDiff * 1e-3 << " secs" << endl;
1239                        Debug << "statistis computed in " << timeDiff * 1e-3 << " secs" << endl;
1240                }
1241
1242                disposeRays(evaluationSamples, NULL);
1243        }
1244       
1245
1246        ////////////
1247        //-- histogram
1248
1249        const int numLeaves = mViewCellsTree->GetNumInitialViewCells(mViewCellsTree->GetRoot());
1250        bool useHisto;
1251        int histoStepSize;
1252
1253        Environment::GetSingleton()->GetBoolValue("ViewCells.Evaluation.histogram", useHisto);
1254        Environment::GetSingleton()->GetIntValue("ViewCells.Evaluation.histoStepSize", histoStepSize);
1255
1256        if (useHisto)
1257        {
1258                // evaluate view cells in a histogram           
1259                char s[64];
1260
1261                for (int pass = histoStepSize; pass <= numLeaves; pass += histoStepSize)
1262                {
1263                        string filename;
1264
1265                        cout << "computing histogram for " << pass << " view cells" << endl;
1266#if 0
1267                        //-- evaluate histogram for render cost
1268                        sprintf(s, "-%09d-histo.log", pass);
1269                        filename = string(statsPrefix) + string(s);
1270
1271                        EvalViewCellHistogram(filename, pass);
1272
1273#endif
1274                        //////////////////////////////////////////
1275            //-- evaluate histogram for pvs size
1276
1277                        cout << "computing pvs histogram for " << pass << " view cells" << endl;
1278
1279                        sprintf(s, "-%09d-histo-pvs.log", pass);
1280                        filename = string(statsPrefix) + string(s);
1281
1282                        EvalViewCellHistogram(filename, pass);
1283                        //                      EvalViewCellHistogramForPvsSize(filename, pass);
1284                }
1285        }
1286}
1287
1288
1289inline float EvalMergeCost(ViewCell *root, ViewCell *candidate)
1290{
1291        return root->GetPvs().GetPvsHomogenity(candidate->GetPvs());
1292}
1293
1294
1295/// Returns index of the best view cells of the neighborhood
1296static int GetBestViewCellIdx(ViewCell *root, const ViewCellContainer &neighborhood)
1297{
1298        int bestViewCellIdx = 0;
1299
1300        float mergeCost = Limits::Infinity;
1301        int i = 0;
1302
1303        ViewCellContainer::const_iterator vit, vit_end = neighborhood.end();
1304
1305        for (vit = neighborhood.begin(); vit != vit_end; ++ vit, ++ i)
1306        {
1307                const float mc = EvalMergeCost(root, *vit);
1308               
1309                if (mc < mergeCost)
1310                {
1311                        mergeCost = mc;
1312                        bestViewCellIdx = i;
1313                }
1314        }
1315
1316        return bestViewCellIdx;
1317}
1318
1319
1320void ViewCellsManager::SetMaxFilterSize(const int size)
1321{
1322        mMaxFilterSize = size;
1323}
1324
1325
1326float ViewCellsManager::EvalRenderCost(Intersectable *obj) //const
1327{
1328        switch (sRenderCostEvaluationType)
1329        {
1330        case PER_OBJECT:
1331                return 1.0f;
1332       
1333        case PER_TRIANGLE:
1334                {
1335                        return (float)obj->NumberOfFaces();
1336                }
1337        default:
1338                cout << "default" << endl;
1339                return 1.0f;
1340        }
1341
1342        // should not come here
1343        return 0.0f;
1344}
1345
1346
1347ViewCell *ViewCellsManager::ConstructLocalMergeTree(ViewCell *currentViewCell,
1348                                                                                                        const ViewCellContainer &viewCells)
1349{
1350        ViewCell *root = currentViewCell;
1351        ViewCellContainer neighborhood = viewCells;
1352
1353        ViewCellContainer::const_iterator it, it_end = neighborhood.end();
1354
1355        const int n = min(mMaxFilterSize, (int)neighborhood.size());
1356       
1357        /////////////////
1358        //-- use priority queue to merge leaf pairs
1359       
1360        for (int nMergedViewCells = 0; nMergedViewCells < n; ++ nMergedViewCells)
1361        {
1362                const int bestViewCellIdx = GetBestViewCellIdx(root, neighborhood);
1363               
1364                ViewCell *bestViewCell = neighborhood[bestViewCellIdx];
1365       
1366                // remove from vector
1367                swap(neighborhood[bestViewCellIdx], neighborhood.back());
1368                neighborhood.pop_back();
1369       
1370                if (!bestViewCell || !root)
1371            cout << "warning!!" << endl;
1372               
1373                // create new root of the hierarchy
1374                root = MergeViewCells(root, bestViewCell);
1375        }
1376
1377        return root;   
1378}
1379
1380
1381struct SortableViewCellEntry {
1382
1383        SortableViewCellEntry() {}
1384        SortableViewCellEntry(const float v, ViewCell *cell):mValue(v), mViewCell(cell) {}
1385
1386        float mValue;
1387        ViewCell *mViewCell;
1388
1389        friend bool operator<(const SortableViewCellEntry &a, const SortableViewCellEntry &b) {
1390                return a.mValue < b.mValue;
1391        }
1392};
1393
1394
1395ViewCell * ViewCellsManager::ConstructLocalMergeTree2(ViewCell *currentViewCell,
1396                                                                                                          const ViewCellContainer &viewCells)
1397{
1398 
1399  vector<SortableViewCellEntry> neighborhood(viewCells.size());
1400  int i, j;
1401  for (i = 0, j = 0; i < viewCells.size(); i++) {
1402        if (viewCells[i] != currentViewCell)
1403          neighborhood[j++] = SortableViewCellEntry(
1404                                                                                                EvalMergeCost(currentViewCell, viewCells[i]),
1405                                                                                                viewCells[i]);
1406  }
1407  neighborhood.resize(j);
1408 
1409  sort(neighborhood.begin(), neighborhood.end());
1410 
1411  ViewCell *root = currentViewCell;
1412 
1413  vector<SortableViewCellEntry>::const_iterator it, it_end = neighborhood.end();
1414 
1415  const int n = min(mMaxFilterSize, (int)neighborhood.size());
1416  //-- use priority queue to merge leaf pairs
1417 
1418  //cout << "neighborhood: " << neighborhood.size() << endl;
1419  for (int nMergedViewCells = 0; nMergedViewCells < n; ++ nMergedViewCells)
1420  {
1421          ViewCell *bestViewCell = neighborhood[nMergedViewCells].mViewCell;
1422          //cout <<nMergedViewCells<<":"<<"homogenity=" <<neighborhood[nMergedViewCells].mValue<<endl;
1423          // create new root of the hierarchy
1424          root = MergeViewCells(root, bestViewCell);
1425          // set negative cost so that this view cell gets deleted
1426          root->SetMergeCost(-1.0f);
1427  }
1428 
1429  return root; 
1430}
1431
1432void
1433ViewCellsManager::DeleteLocalMergeTree(ViewCell *vc
1434                                                                           ) const
1435{
1436        if (!vc->IsLeaf() && vc->GetMergeCost() < 0.0f)
1437        {       
1438                ViewCellInterior *vci = (ViewCellInterior *) vc;
1439                ViewCellContainer::const_iterator it, it_end = vci->mChildren.end();
1440
1441        for (it = vci->mChildren.begin(); it != it_end; ++ it)
1442                        DeleteLocalMergeTree(*it);
1443               
1444                vci->mChildren.clear();
1445               
1446                delete vci;
1447  }
1448}
1449
1450
1451bool ViewCellsManager::CheckValidity(ViewCell *vc,
1452                                                                         int minPvsSize,
1453                                                                         int maxPvsSize) const
1454{
1455
1456        if ((vc->GetPvs().EvalPvsCost() > maxPvsSize) ||
1457                (vc->GetPvs().EvalPvsCost() < minPvsSize))
1458        {
1459                return false;
1460        }
1461
1462        return true;
1463}
1464
1465
1466int ViewCellsManager::ComputeBoxIntersections(const AxisAlignedBox3 &box,
1467                                                                                          ViewCellContainer &viewCells) const
1468{
1469        return 0;
1470};
1471
1472
1473AxisAlignedBox3 ViewCellsManager::GetFilterBBox(const Vector3 &viewPoint,
1474                                                                                                const float width) const
1475{
1476  float w = Magnitude(mViewSpaceBox.Size())*width;
1477  Vector3 min = viewPoint - w * 0.5f;
1478  Vector3 max = viewPoint + w * 0.5f;
1479 
1480  return AxisAlignedBox3(min, max);
1481}
1482
1483
1484void ViewCellsManager::GetPrVS(const Vector3 &viewPoint,
1485                                                           PrVs &prvs,
1486                                                           const float filterWidth)
1487{
1488  ViewCell *currentViewCell = GetViewCell(viewPoint);
1489
1490  if (mMaxFilterSize < 1) {
1491        prvs.mViewCell = currentViewCell;
1492        return;
1493  }
1494 
1495  const AxisAlignedBox3 box = GetFilterBBox(viewPoint, filterWidth);
1496 
1497  if (currentViewCell)
1498        {
1499          ViewCellContainer viewCells;
1500          ComputeBoxIntersections(box, viewCells);
1501         
1502          ViewCell *root = ConstructLocalMergeTree2(currentViewCell, viewCells);
1503          prvs.mViewCell = root;
1504         
1505        }
1506  else
1507        {
1508          prvs.mViewCell = NULL;
1509          //prvs.mPvs = root->GetPvs();
1510        }
1511}
1512
1513
1514bool ViewCellsManager::ViewCellsTreeConstructed() const
1515{
1516    return (mViewCellsTree && mViewCellsTree->GetRoot());
1517}
1518
1519
1520void ViewCellsManager::SetValidity(ViewCell *vc,
1521                                                                   int minPvs,
1522                                                                   int maxPvs) const
1523{
1524        vc->SetValid(CheckValidity(vc, minPvs, maxPvs));
1525}
1526
1527
1528void
1529ViewCellsManager::SetValidity(
1530                                                          int minPvsSize,
1531                                                          int maxPvsSize) const
1532{
1533        ViewCellContainer::const_iterator it, it_end = mViewCells.end();
1534
1535
1536        for (it = mViewCells.begin(); it != it_end; ++ it)
1537        {
1538                SetValidity(*it, minPvsSize, maxPvsSize);
1539        }
1540}
1541
1542void
1543ViewCellsManager::SetValidityPercentage(
1544                                                                                const float minValid,
1545                                                                                const float maxValid
1546                                                                                )
1547{
1548  ObjectPvs dummyPvs;
1549  // update pvs sizes
1550  for (int i = 0; i < (int)mViewCells.size(); ++ i) {
1551        UpdatePvsForEvaluation(mViewCells[i], dummyPvs);
1552  }
1553 
1554  sort(mViewCells.begin(), mViewCells.end(), ViewCell::SmallerPvs);
1555 
1556  int start = (int)(mViewCells.size() * minValid);
1557  int end = (int)(mViewCells.size() * maxValid);
1558 
1559  for (int i = 0; i < (int)mViewCells.size(); ++ i)
1560        {
1561          //      cout<<"pvs:"<<mViewCells[i]->GetCachedPvsCost()<<endl;
1562          mViewCells[i]->SetValid(i >= start && i <= end);
1563        }
1564}
1565
1566
1567int ViewCellsManager::CountValidViewcells() const
1568{
1569        ViewCellContainer::const_iterator it, it_end = mViewCells.end();
1570        int valid = 0;
1571
1572        for (it = mViewCells.begin(); it != it_end; ++ it)
1573        {       
1574                if ((*it)->GetValid())
1575                        ++ valid;
1576        }
1577
1578        return valid;
1579}
1580
1581
1582bool ViewCellsManager::LoadViewCellsGeometry(const string filename,
1583                                                                                         const bool extrudeBaseTriangles)
1584{
1585        /// we use predefined view cells from now on
1586        mUsePredefinedViewCells = true;
1587        X3dParser parser;
1588       
1589        if (extrudeBaseTriangles)
1590        {
1591                Environment::GetSingleton()->GetFloatValue("ViewCells.height", parser.mViewCellHeight);
1592                const bool success = parser.ParseFile(filename, *this);
1593
1594                if (!success)
1595                        return false;
1596        }
1597        else
1598        {
1599                // hack: use standard mesh loading
1600                // create temporary scene graph for loading the view cells geometry
1601                // note: delete the meshes as they are created two times for transformed mesh instances.
1602                SceneGraphNode *root = new SceneGraphNode();
1603                const bool success = parser.ParseFile(filename, root, true);
1604               
1605                if (!success)
1606                {
1607                        DEL_PTR(root);
1608                        return false;
1609                }
1610
1611                ObjectContainer::const_iterator oit, oit_end = root->mGeometry.end();
1612               
1613                for (oit = root->mGeometry.begin(); oit != oit_end; ++ oit)
1614                {
1615                        Mesh *mesh;
1616                        if ((*oit)->Type() == Intersectable::TRANSFORMED_MESH_INSTANCE)
1617                        {
1618                                TransformedMeshInstance *mit = dynamic_cast<TransformedMeshInstance *>(*oit);
1619                                mesh = MeshManager::GetSingleton()->CreateResource();
1620                                mit->GetTransformedMesh(*mesh);
1621                        }
1622                        else if ((*oit)->Type() == Intersectable::MESH_INSTANCE)
1623                        {
1624                                MeshInstance *mit = dynamic_cast<MeshInstance *>(*oit);
1625                                mesh = mit->GetMesh();
1626                        }
1627                        mesh->ComputeBoundingBox();
1628                        mViewCells.push_back(GenerateViewCell(mesh));
1629                }
1630
1631                DEL_PTR(root);
1632        }
1633
1634        // set view space box to bounding box of the view cells
1635        AxisAlignedBox3 bbox;
1636        bbox.Initialize();
1637        ViewCellContainer::iterator it = mViewCells.begin(), it_end = mViewCells.end();
1638
1639        for (; it != it_end; ++ it)
1640        {
1641                bbox.Include((*it)->GetMesh()->mBox);
1642        }
1643
1644        SetViewSpaceBox(bbox);
1645        cout << "view space box: " << bbox << endl;
1646        cout << "generated " << (int)mViewCells.size() << " view cells using the geometry " << filename << endl;
1647
1648        return true;
1649}
1650
1651
1652bool ViewCellsManager::GetViewPoint(Vector3 &viewPoint) const
1653{
1654  viewPoint = mViewSpaceBox.GetRandomPoint();
1655  return true;
1656}
1657
1658bool ViewCellsManager::GetViewPoint(Vector3 &viewPoint, const Vector3 &params) const
1659{
1660  viewPoint = mViewSpaceBox.GetRandomPoint(params);
1661  return true;
1662}
1663
1664
1665float ViewCellsManager::GetViewSpaceVolume()
1666{
1667        return mViewSpaceBox.GetVolume() * (2.0f * sqr((float)M_PI));
1668}
1669
1670
1671bool ViewCellsManager::ViewPointValid(const Vector3 &viewPoint) const
1672{
1673        if (!ViewCellsConstructed())
1674        {
1675                return mViewSpaceBox.IsInside(viewPoint);
1676        }
1677        else
1678        {
1679                if (!mViewSpaceBox.IsInside(viewPoint))
1680                        return false;
1681
1682                ViewCell *viewcell = GetViewCell(viewPoint);
1683
1684                if (!viewcell || !viewcell->GetValid())
1685                        return false;
1686        }
1687
1688        return true;
1689}
1690
1691
1692float
1693ViewCellsManager::ComputeSampleContributions(const VssRayContainer &rays,
1694                                                                                         const bool addRays,
1695                                                                                         const bool storeViewCells,
1696                                                                                         const bool useHitObjects)
1697{
1698  float sum = 0.0f;
1699
1700  VssRayContainer::const_iterator it, it_end = rays.end();
1701
1702  for (it = rays.begin(); it != it_end; ++ it)
1703        {
1704          if (!ViewCellsConstructed()) {
1705                // view cells not yet constructed
1706                // just take the lenghts of the rays as contributions
1707                if ((*it)->mTerminationObject)
1708                  sum += (*it)->Length();
1709          } else {
1710                sum += ComputeSampleContribution(*(*it), addRays, storeViewCells, useHitObjects);
1711          }
1712        }
1713
1714  cout<<"view cell cast time:"<<viewCellCastTimer.TotalTime()<<" s"<<endl;
1715  cout<<"pvs time:"<<pvsTimer.TotalTime()<<" s"<<endl;
1716 
1717  return sum;
1718}
1719
1720
1721void ViewCellsManager::EvaluateViewCellsStats()
1722{
1723        mCurrentViewCellsStats.Reset();
1724        ViewCellContainer::const_iterator it, it_end = mViewCells.end();
1725
1726        for (it = mViewCells.begin(); it != it_end; ++ it)
1727        {
1728                mViewCellsTree->UpdateViewCellsStats(*it, mCurrentViewCellsStats);
1729        }
1730}
1731
1732
1733void ViewCellsManager::EvaluateRenderStatistics(float &totalRenderCost,
1734                                                                                                float &expectedRenderCost,
1735                                                                                                float &deviation,
1736                                                                                                float &variance,
1737                                                                                                float &totalCost,
1738                                                                                                float &avgRenderCost)
1739{
1740        ////////////
1741        //-- compute expected value
1742
1743        totalRenderCost = 0;
1744        totalCost = 0;
1745
1746        ViewCellContainer::const_iterator it, it_end = mViewCells.end();
1747
1748        for (it = mViewCells.begin(); it != it_end; ++ it)
1749        {
1750                ViewCell *vc = *it;
1751                totalRenderCost += vc->GetPvs().EvalPvsCost() * vc->GetVolume();
1752                totalCost += (int)vc->GetPvs().EvalPvsCost();
1753        }
1754
1755        // normalize with view space box
1756        totalRenderCost /= mViewSpaceBox.GetVolume();
1757        expectedRenderCost = totalRenderCost / (float)mViewCells.size();
1758        avgRenderCost = totalCost / (float)mViewCells.size();
1759
1760
1761        ///////////
1762        //-- compute standard defiation
1763
1764        variance = 0;
1765        deviation = 0;
1766
1767        for (it = mViewCells.begin(); it != it_end; ++ it)
1768        {
1769                ViewCell *vc = *it;
1770
1771                float renderCost = vc->GetPvs().EvalPvsCost() * vc->GetVolume();
1772                float dev;
1773
1774                if (1)
1775                        dev = fabs(avgRenderCost - (float)vc->GetPvs().EvalPvsCost());
1776                else
1777                        dev = fabs(expectedRenderCost - renderCost);
1778
1779                deviation += dev;
1780                variance += dev * dev;
1781        }
1782
1783        variance /= (float)mViewCells.size();
1784        deviation /= (float)mViewCells.size();
1785}
1786
1787
1788float ViewCellsManager::GetArea(ViewCell *viewCell) const
1789{
1790        return viewCell->GetArea();
1791}
1792
1793
1794float ViewCellsManager::GetVolume(ViewCell *viewCell) const
1795{
1796        return viewCell->GetVolume();
1797}
1798
1799
1800void ViewCellsManager::CompressViewCells()
1801{
1802        if (!(ViewCellsTreeConstructed() && mCompressViewCells))
1803                return;
1804
1805        ////////////
1806        //-- compression
1807       
1808        int pvsEntries = mViewCellsTree->CountStoredPvsEntries(mViewCellsTree->GetRoot());
1809
1810        cout << "number of entries before compress: " << pvsEntries << endl;
1811        Debug << "number of entries before compress: " << pvsEntries << endl;
1812
1813        mViewCellsTree->SetViewCellsStorage(ViewCellsTree::COMPRESSED);
1814
1815        pvsEntries = mViewCellsTree->CountStoredPvsEntries(mViewCellsTree->GetRoot());
1816
1817        Debug << "number of entries after compress: " << pvsEntries << endl;
1818        cout << "number of entries after compress: " << pvsEntries << endl;
1819}
1820
1821
1822ViewCell *ViewCellsManager::ExtrudeViewCell(const Triangle3 &baseTri,
1823                                                                                        const float height) const
1824{
1825        // one mesh per view cell
1826        Mesh *mesh = MeshManager::GetSingleton()->CreateResource();
1827
1828        ////////////
1829        //-- construct prism
1830
1831        // bottom
1832        mesh->mFaces.push_back(new Face(2,1,0));
1833        // top
1834    mesh->mFaces.push_back(new Face(3,4,5));
1835        // sides
1836        mesh->mFaces.push_back(new Face(1, 4, 3, 0));
1837        mesh->mFaces.push_back(new Face(2, 5, 4, 1));
1838        mesh->mFaces.push_back(new Face(3, 5, 2, 0));
1839
1840
1841        /////////////
1842        //-- extrude new vertices for top of prism
1843
1844        const Vector3 triNorm = baseTri.GetNormal();
1845        Triangle3 topTri;
1846
1847        // add base vertices and calculate top vertices
1848        for (int i = 0; i < 3; ++ i)
1849        {
1850                mesh->mVertices.push_back(baseTri.mVertices[i]);
1851        }
1852
1853        // add top vertices
1854        for (int i = 0; i < 3; ++ i)
1855        {
1856                mesh->mVertices.push_back(baseTri.mVertices[i] + height * triNorm);
1857        }
1858
1859        // do we have to preprocess this mesh (we don't want to trace view cells!)?
1860        mesh->ComputeBoundingBox();
1861       
1862        return GenerateViewCell(mesh);
1863}
1864
1865
1866void ViewCellsManager::FinalizeViewCells(const bool createMesh)
1867{
1868        ViewCellContainer::const_iterator it, it_end = mViewCells.end();
1869
1870        // volume and area of the view cells are recomputed
1871        // a view cell mesh is created
1872        for (it = mViewCells.begin(); it != it_end; ++ it)
1873        {
1874                Finalize(*it, createMesh);
1875        }
1876
1877        mViewCellsTree->AssignRandomColors();
1878
1879        mTotalAreaValid = false;
1880}
1881
1882
1883void ViewCellsManager::Finalize(ViewCell *viewCell, const bool createMesh)
1884{
1885        // implemented in subclasses
1886}
1887
1888
1889/** fast way of merging 2 view cells.
1890*/
1891ViewCellInterior *ViewCellsManager::MergeViewCells(ViewCell *left, ViewCell *right) const
1892{
1893        // generate parent view cell
1894        ViewCellInterior *vc = new ViewCellInterior();
1895
1896        vc->GetPvs().Clear();
1897        ObjectPvs::Merge(vc->GetPvs(), left->GetPvs(), right->GetPvs());
1898
1899        // set only links to child (not from child to parent, maybe not wished!!)
1900        vc->mChildren.push_back(left);
1901        vc->mChildren.push_back(right);
1902
1903        // update pvs size
1904        UpdateScalarPvsSize(vc, vc->GetPvs().EvalPvsCost(), vc->GetPvs().GetSize());
1905
1906        return vc;
1907}
1908
1909
1910ViewCellInterior *ViewCellsManager::MergeViewCells(ViewCellContainer &children) const
1911{
1912        ViewCellInterior *vc = new ViewCellInterior();
1913        ViewCellContainer::const_iterator it, it_end = children.end();
1914
1915        for (it = children.begin(); it != it_end; ++ it)
1916        {
1917                vc->GetPvs().MergeInPlace((*it)->GetPvs());
1918       
1919                vc->mChildren.push_back(*it);
1920        }
1921
1922        return vc;
1923}
1924
1925
1926void ViewCellsManager::SetRenderer(Renderer *renderer)
1927{
1928        mRenderer = renderer;
1929}
1930
1931
1932ViewCellsTree *ViewCellsManager::GetViewCellsTree()
1933{
1934        return mViewCellsTree;
1935}
1936
1937
1938void ViewCellsManager::SetVisualizationSamples(const int visSamples)
1939{
1940        mVisualizationSamples = visSamples;
1941}
1942
1943
1944void ViewCellsManager::SetConstructionSamples(const int constructionSamples)
1945{
1946        mConstructionSamples = constructionSamples;
1947}
1948
1949
1950void ViewCellsManager::SetInitialSamples(const int initialSamples)
1951{
1952        mInitialSamples = initialSamples;
1953}
1954
1955
1956void ViewCellsManager::SetPostProcessSamples(const int postProcessSamples)
1957{
1958        mPostProcessSamples = postProcessSamples;
1959}
1960
1961
1962int ViewCellsManager::GetVisualizationSamples() const
1963{
1964        return mVisualizationSamples;
1965}
1966
1967
1968int ViewCellsManager::GetConstructionSamples() const
1969{
1970        return mConstructionSamples;
1971}
1972
1973
1974int ViewCellsManager::GetPostProcessSamples() const
1975{
1976        return mPostProcessSamples;
1977}
1978
1979
1980void ViewCellsManager::UpdatePvs()
1981{
1982  if (mViewCellPvsIsUpdated || !ViewCellsTreeConstructed())
1983        return;
1984 
1985  mViewCellPvsIsUpdated = true;
1986 
1987  ViewCellContainer leaves;
1988  mViewCellsTree->CollectLeaves(mViewCellsTree->GetRoot(), leaves);
1989 
1990  ViewCellContainer::const_iterator it, it_end = leaves.end();
1991 
1992  for (it = leaves.begin(); it != it_end; ++ it)
1993        {
1994          mViewCellsTree->PropagatePvs(*it);
1995        }
1996}
1997
1998
1999void ViewCellsManager::GetPvsStatistics(PvsStatistics &stat)
2000{
2001  // update pvs of view cells tree if necessary
2002  UpdatePvs();
2003 
2004  ViewCellContainer::const_iterator it = mViewCells.begin();
2005 
2006  stat.viewcells = 0;
2007  stat.minPvs = 100000000;
2008  stat.maxPvs = 0;
2009  stat.avgPvs = 0.0f;
2010  stat.avgPvsEntries = 0.0f;
2011  stat.avgFilteredPvs = 0.0f;
2012  stat.avgFilteredPvsEntries = 0.0f;
2013  stat.avgFilterContribution = 0.0f;
2014  stat.avgFilterRadius = 0;
2015  stat.avgFilterRatio = 0;
2016  stat.avgRelPvsIncrease = 0.0f;
2017  stat.devRelPvsIncrease = 0.0f;
2018 
2019  if (mPerViewCellStat.size() != mViewCells.size()) {
2020        // reset the pvs size array after the first call to this routine
2021        mPerViewCellStat.resize(mViewCells.size());
2022        for (int i=0; i < mPerViewCellStat.size(); i++) {
2023          mPerViewCellStat[i].pvsSize = 0.0f;
2024          mPerViewCellStat[i].relPvsIncrease = 0.0f;
2025        }
2026  }
2027  int i;
2028  bool evaluateFilter;
2029  Environment::GetSingleton()->GetBoolValue("Preprocessor.evaluateFilter", evaluateFilter);
2030
2031  for (i=0; it != mViewCells.end(); ++ it, i++)
2032        {
2033          ViewCell *viewcell = *it;
2034          if (viewcell->GetValid()) {
2035                const float pvsCost = mViewCellsTree->GetPvsCost(viewcell);
2036
2037                if (pvsCost < stat.minPvs)
2038                  stat.minPvs = pvsCost;
2039                if (pvsCost > stat.maxPvs)
2040                  stat.maxPvs = pvsCost;
2041               
2042                stat.avgPvs += pvsCost;
2043
2044                const float pvsEntries = (float)mViewCellsTree->GetPvsEntries(viewcell);
2045                stat.avgPvsEntries += pvsEntries;
2046               
2047                if (mPerViewCellStat[i].pvsSize > 0.0f)
2048                  mPerViewCellStat[i].relPvsIncrease = (pvsCost - mPerViewCellStat[i].pvsSize)/mPerViewCellStat[i].pvsSize;
2049               
2050                stat.avgRelPvsIncrease += mPerViewCellStat[i].relPvsIncrease;
2051               
2052                // update the pvs size
2053                mPerViewCellStat[i].pvsSize = pvsCost;
2054               
2055               
2056               
2057                if (evaluateFilter) {
2058                  ObjectPvs filteredPvs;
2059                 
2060                  PvsFilterStatistics fstat = ApplyFilter2(viewcell,
2061                                                                                                   false,
2062                                                                                                   1.0f,
2063                                                                                                   filteredPvs);
2064                 
2065                  float filteredCost = filteredPvs.EvalPvsCost();
2066
2067                  stat.avgFilteredPvs += filteredCost;
2068                  stat.avgFilteredPvsEntries += filteredPvs.GetSize();
2069                 
2070                  stat.avgFilterContribution += filteredCost - pvsCost;
2071                 
2072                  stat.avgFilterRadius += fstat.mAvgFilterRadius;
2073                  int sum = fstat.mGlobalFilterCount + fstat.mLocalFilterCount;
2074                  if (sum) {
2075                        stat.avgFilterRatio += fstat.mLocalFilterCount /
2076                          (float) sum;
2077                  }
2078                 
2079                } else {
2080                  stat.avgFilteredPvs += pvsCost;
2081                  stat.avgFilterContribution += 0;
2082                }
2083               
2084                ++ stat.viewcells;
2085          }
2086        }
2087
2088 
2089 
2090  if (stat.viewcells) {
2091        stat.avgPvs/=stat.viewcells;
2092        stat.avgPvsEntries/=stat.viewcells;
2093        stat.avgFilteredPvsEntries/=stat.viewcells;
2094        stat.avgFilteredPvs/=stat.viewcells;
2095        stat.avgFilterContribution/=stat.viewcells;
2096        stat.avgFilterRadius/=stat.viewcells;
2097        stat.avgFilterRatio/=stat.viewcells;
2098        stat.avgRelPvsIncrease/=stat.viewcells;
2099
2100        // evaluate std deviation of relPvsIncrease
2101        float sum=0.0f;
2102        for (i=0; i < stat.viewcells; i++) {
2103          sum += sqr(mPerViewCellStat[i].relPvsIncrease - stat.avgRelPvsIncrease);
2104        }
2105        stat.devRelPvsIncrease = sqrt(sum/stat.viewcells);
2106  }
2107 
2108}
2109
2110
2111void ViewCellsManager::PrintPvsStatistics(ostream &s)
2112{
2113  s<<"############# Viewcell PVS STAT ##################\n";
2114  PvsStatistics pvsStat;
2115  GetPvsStatistics(pvsStat);
2116  s<<"#AVG_PVS\n"<<pvsStat.avgPvs<<endl;
2117  s<<"#AVG_ENTRIES_PVS\n"<<pvsStat.avgPvsEntries<<endl;
2118  s<<"#AVG_FILTERED_PVS\n"<<pvsStat.avgFilteredPvs<<endl;
2119  s<<"#AVG_FILTERED_ENTRIES_PVS\n"<<pvsStat.avgFilteredPvsEntries<<endl;
2120  s<<"#AVG_FILTER_CONTRIBUTION\n"<<pvsStat.avgFilterContribution<<endl;
2121  s<<"#AVG_FILTER_RADIUS\n"<<pvsStat.avgFilterRadius<<endl;
2122  s<<"#AVG_FILTER_RATIO\n"<<pvsStat.avgFilterRatio<<endl;
2123  s<<"#MAX_PVS\n"<<pvsStat.maxPvs<<endl;
2124  s<<"#MIN_PVS\n"<<pvsStat.minPvs<<endl;
2125  s<<"#AVG_REL_PVS_INCREASE\n"<<pvsStat.avgRelPvsIncrease<<endl;
2126  s<<"#DEV_REL_PVS_INCREASE\n"<<pvsStat.devRelPvsIncrease<<endl;
2127
2128  s<<"#CONTRIBUTING_RAYS\n"<<mSamplesStat.mContributingRays<<endl;
2129
2130  if (mSamplesStat.mRays) {
2131        s<<"#AVG_VIEWCELLS_PER_RAY\n"<<mSamplesStat.mViewCells/(float)mSamplesStat.mRays<<endl;
2132  } else {
2133        s<<"#AVG_VIEWCELLS_PER_RAY\n 1 \n";
2134  }
2135  mSamplesStat.Reset();
2136}
2137
2138
2139int ViewCellsManager::CastBeam(Beam &beam)
2140{
2141        return 0;
2142}
2143
2144
2145ViewCellContainer &ViewCellsManager::GetViewCells()
2146{
2147        return mViewCells;
2148}
2149
2150
2151void ViewCellsManager::SetViewSpaceBox(const AxisAlignedBox3 &box)
2152{
2153        mViewSpaceBox = box;
2154       
2155        // hack: create clip plane relative to new view space box
2156        CreateClipPlane();
2157        // the total area of the view space has changed
2158        mTotalAreaValid = false;
2159}
2160
2161
2162void ViewCellsManager::CreateClipPlane()
2163{
2164        int axis = 0;
2165        float pos;
2166        bool orientation;
2167        Vector3 absPos;
2168
2169        Environment::GetSingleton()->GetFloatValue("ViewCells.Visualization.clipPlanePos", pos);
2170        Environment::GetSingleton()->GetIntValue("ViewCells.Visualization.clipPlaneAxis", axis);
2171
2172        if (axis < 0)
2173        {
2174                axis = -axis;
2175                orientation = false;
2176                absPos = mViewSpaceBox.Max() -  mViewSpaceBox.Size() * pos;
2177        }
2178        else
2179        {
2180                orientation = true;
2181                absPos = mViewSpaceBox.Min() +  mViewSpaceBox.Size() * pos;
2182        }
2183
2184        mClipPlaneForViz = AxisAlignedPlane(axis, absPos[axis]);
2185        mClipPlaneForViz.mOrientation = orientation;
2186}
2187
2188
2189AxisAlignedBox3 ViewCellsManager::GetViewSpaceBox() const
2190{
2191        return mViewSpaceBox;
2192}
2193
2194
2195void ViewCellsManager::ResetViewCells()
2196{
2197        // recollect view cells
2198        mViewCells.clear();
2199        CollectViewCells();
2200       
2201        // stats are computed once more
2202        EvaluateViewCellsStats();
2203
2204        // has to be recomputed
2205        mTotalAreaValid = false;
2206}
2207
2208
2209int ViewCellsManager::GetMaxPvsSize() const
2210{
2211        return mMaxPvsSize;
2212}
2213
2214
2215int ViewCellsManager::GetMinPvsSize() const
2216{
2217        return mMinPvsSize;
2218}
2219
2220
2221
2222float ViewCellsManager::GetMaxPvsRatio() const
2223{
2224        return mMaxPvsRatio;
2225}
2226
2227
2228inline static void AddSampleToPvs(ObjectPvs &pvs,
2229                                                                  Intersectable *obj,
2230                                                                  const float pdf)
2231{
2232#if PVS_ADD_DIRTY
2233        pvs.AddSampleDirtyCheck(obj, pdf);
2234
2235        if (pvs.RequiresResort())
2236        {
2237                pvs.SimpleSort();
2238        }
2239#else
2240        pvs.AddSample(obj, pdf);
2241#endif
2242}
2243
2244
2245void
2246ViewCellsManager::SortViewCellPvs()
2247{
2248
2249  ViewCellContainer::iterator it, it_end = mViewCells.end();
2250  for (it = mViewCells.begin(); it != it_end; ++ it) {
2251        ObjectPvs &pvs = (*it)->GetPvs();
2252        if (pvs.RequiresResortLog())
2253          pvs.Sort();
2254  }
2255}
2256
2257void ViewCellsManager::ComputeViewCellContribution(ViewCell *viewCell,
2258                                                                                                   VssRay &ray,
2259                                                                                                   Intersectable *obj,
2260                                                                                                   const Vector3 &pt,
2261                                                                                                   const bool addRays)
2262{
2263  // check if we are outside of view space
2264  // $$JB tmp commented to speedup up computations
2265#if 0
2266  if (!obj || !viewCell->GetValid())
2267        return;
2268#endif
2269 
2270 
2271  // if ray not outside of view space
2272  float relContribution = 0.0f;
2273  float absContribution = 0.0f;
2274  bool hasAbsContribution;
2275 
2276  // todo: maybe not correct for kd node pvs
2277  if (addRays) {
2278        hasAbsContribution = viewCell->GetPvs().AddSampleDirtyCheck(obj,
2279                                                                                                                                ray.mPdf);
2280  }
2281  else {
2282        hasAbsContribution = viewCell->GetPvs().GetSampleContribution(
2283                                                                                                                                  obj,
2284                                                                                                                                  ray.mPdf,
2285                                                                                                                                  relContribution);
2286  }
2287 
2288  // $$ clear the relative contribution as it is currently not correct anyway
2289  //  relContribution = 0.0f;
2290 
2291  if (hasAbsContribution)  {
2292        ++ ray.mPvsContribution;
2293        absContribution = relContribution = 1.0f;
2294        if (viewCell->GetPvs().RequiresResort())
2295          viewCell->GetPvs().SimpleSort();
2296
2297#if CONTRIBUTION_RELATIVE_TO_PVS_SIZE
2298        relContribution /= viewcell->GetPvs().GetSize();
2299#endif
2300       
2301#if DIST_WEIGHTED_CONTRIBUTION
2302        // recalculate the contribution - weight the 1.0f contribution by the sqr distance to the
2303        // object-> a new contribution in the proximity of the viewcell has a larger weight!
2304        relContribution /= SqrDistance(GetViewCellBox(viewcell).Center(),
2305                                                                   ray.mTermination);
2306       
2307#endif
2308        }
2309 
2310#if SUM_RAY_CONTRIBUTIONS || AVG_RAY_CONTRIBUTIONS
2311  ray.mRelativePvsContribution += relContribution;
2312#else
2313  // recalculate relative contribution - use max of Rel Contribution
2314  if (ray.mRelativePvsContribution < relContribution)
2315        ray.mRelativePvsContribution = relContribution;
2316#endif
2317}
2318
2319
2320
2321
2322int ViewCellsManager::GetNumViewCells() const
2323{
2324        return (int)mViewCells.size();
2325}
2326
2327
2328float ViewCellsManager::ComputeSampleContribution(VssRay &ray,
2329                                                                                                  const bool addRays,
2330                                                                                                  ViewCell *currentViewCell,
2331                                                                                                  const bool useHitObjects)
2332{
2333        ray.mPvsContribution = 0;
2334        ray.mRelativePvsContribution = 0.0f;
2335
2336        if (!ray.mTerminationObject)
2337                return 0.0f;
2338
2339        // optain pvs entry (can be different from hit object)
2340        Intersectable *terminationObj;
2341
2342        if (!useHitObjects)
2343                terminationObj = GetIntersectable(ray, true);
2344        else
2345                terminationObj = ray.mTerminationObject;
2346
2347        ComputeViewCellContribution(currentViewCell,
2348                                                                ray,
2349                                                                terminationObj,
2350                                                                ray.mTermination,
2351                                                                addRays);
2352       
2353#if USE_RAY_LENGTH_AS_CONTRIBUTION
2354        float c = 0.0f;
2355        if (terminationObj)
2356                c = ray.Length();
2357
2358        ray.mRelativePvsContribution = ray.mPvsContribution = c;
2359        return c;
2360#else
2361        return ABS_CONTRIBUTION_WEIGHT*ray.mPvsContribution +
2362          (1.0f - ABS_CONTRIBUTION_WEIGHT)*ray.mRelativePvsContribution;
2363#endif
2364}
2365
2366
2367float
2368ViewCellsManager::ComputeSampleContribution(VssRay &ray,
2369                                                                                        const bool addRays,
2370                                                                                        const bool storeViewCells,
2371                                                                                        const bool useHitObjects)
2372{
2373        ray.mPvsContribution = 0;
2374        ray.mRelativePvsContribution = 0.0f;
2375
2376        mSamplesStat.mRays++;
2377       
2378        if (!ray.mTerminationObject)
2379          return 0.0f;
2380       
2381        static Ray hray;
2382        hray.Init(ray);
2383
2384        float tmin = 0, tmax = 1.0;
2385
2386        if (!GetViewSpaceBox().GetRaySegment(hray, tmin, tmax) || (tmin > tmax)) {
2387          //      cerr<<"ray outside view space box\n";
2388          return 0;
2389        }
2390
2391        Vector3 origin = hray.Extrap(tmin);
2392        Vector3 termination = hray.Extrap(tmax);
2393       
2394        ViewCell::NewMail();
2395       
2396        viewCellCastTimer.Entry();
2397
2398        static ViewCellContainer viewCells;
2399        static VssRay *lastVssRay = NULL;
2400       
2401        if (lastVssRay == NULL ||
2402                !(ray.mOrigin == lastVssRay->mTermination) ||
2403                !(ray.mTermination == lastVssRay->mOrigin)) {
2404          viewCells.clear();
2405          // traverse the view space subdivision
2406          CastLineSegment(origin, termination, viewCells);
2407          lastVssRay = &ray;
2408        }
2409       
2410        viewCellCastTimer.Exit();
2411
2412        mSamplesStat.mViewCells += (int)viewCells.size();
2413
2414        if (storeViewCells)
2415        {       
2416          cerr<<"Store viewcells should not be used in the test!"<<endl;
2417          // copy viewcells memory efficiently
2418#if VSS_STORE_VIEWCELLS
2419          ray.mViewCells.reserve(viewCells.size());
2420          ray.mViewCells = viewCells;
2421#else
2422          cerr<<"Vss store viewcells not supported."<<endl;
2423          exit(1);
2424#endif
2425        }
2426       
2427        Intersectable *terminationObj;
2428       
2429        objTimer.Entry();
2430
2431        // obtain pvs entry (can be different from hit object)
2432        if (!useHitObjects)
2433          terminationObj = GetIntersectable(ray, true);
2434        else
2435          terminationObj = ray.mTerminationObject;
2436       
2437        objTimer.Exit();
2438       
2439        pvsTimer.Entry();
2440
2441        ViewCellContainer::const_iterator it = viewCells.begin();
2442
2443        for (; it != viewCells.end(); ++ it)
2444        {
2445                ComputeViewCellContribution(*it,
2446                                                                        ray,
2447                                                                        terminationObj,
2448                                                                        ray.mTermination,
2449                                                                        addRays);
2450        }
2451
2452        pvsTimer.Exit();
2453
2454        mSamplesStat.mPvsContributions += ray.mPvsContribution;
2455        if (ray.mPvsContribution)
2456          mSamplesStat.mContributingRays++;
2457       
2458#if AVG_RAY_CONTRIBUTIONS
2459        ray.mRelativePvsContribution /= (float)viewCells.size();
2460#endif
2461 
2462#if USE_RAY_LENGTH_AS_CONTRIBUTION
2463        float c = 0.0f;
2464        if (terminationObj)
2465          c = ray.Length();
2466        ray.mRelativePvsContribution = ray.mPvsContribution = c;
2467        return c;
2468#else
2469        return ABS_CONTRIBUTION_WEIGHT*ray.mPvsContribution +
2470          (1.0f - ABS_CONTRIBUTION_WEIGHT)*ray.mRelativePvsContribution;
2471#endif
2472}
2473
2474
2475void ViewCellsManager::GetRaySets(const VssRayContainer &sourceRays,
2476                                                                  const int maxSize,
2477                                                                  VssRayContainer &usedRays,
2478                                                                  VssRayContainer *savedRays) const
2479{
2480        const int limit = min(maxSize, (int)sourceRays.size());
2481        const float prop = (float)limit / ((float)sourceRays.size() + Limits::Small);
2482
2483        VssRayContainer::const_iterator it, it_end = sourceRays.end();
2484        for (it = sourceRays.begin(); it != it_end; ++ it)
2485        {
2486                if (Random(1.0f) < prop)
2487                        usedRays.push_back(*it);
2488                else if (savedRays)
2489                        savedRays->push_back(*it);
2490        }
2491}
2492
2493
2494float ViewCellsManager::GetRendercost(ViewCell *viewCell) const
2495{
2496        return (float)mViewCellsTree->GetPvsCost(viewCell);
2497}
2498
2499
2500float ViewCellsManager::GetAccVcArea()
2501{
2502        // if already computed
2503        if (mTotalAreaValid)
2504        {
2505                return mTotalArea;
2506        }
2507
2508        mTotalArea = 0;
2509        ViewCellContainer::const_iterator it, it_end = mViewCells.end();
2510
2511        for (it = mViewCells.begin(); it != it_end; ++ it)
2512        {
2513                //Debug << "area: " << GetArea(*it);
2514        mTotalArea += GetArea(*it);
2515        }
2516
2517        mTotalAreaValid = true;
2518
2519        return mTotalArea;
2520}
2521
2522
2523void ViewCellsManager::PrintStatistics(ostream &s) const
2524{
2525        s << mCurrentViewCellsStats << endl;
2526}
2527
2528
2529void ViewCellsManager::CreateUniqueViewCellIds()
2530{
2531        if (ViewCellsTreeConstructed())
2532        {
2533                mViewCellsTree->CreateUniqueViewCellsIds();
2534        }
2535        else // no view cells tree, handle view cells "myself"
2536        {
2537                int i = 0;
2538                ViewCellContainer::const_iterator vit, vit_end = mViewCells.end();
2539                for (vit = mViewCells.begin(); vit != vit_end; ++ vit)
2540                {
2541                        if ((*vit)->GetId() != OUT_OF_BOUNDS_ID)
2542                        {
2543                                mViewCells[i]->SetId(i ++);
2544                        }
2545                }
2546        }
2547}
2548
2549
2550void ViewCellsManager::ExportViewCellsForViz(Exporter *exporter,
2551                                                                                         const AxisAlignedBox3 *sceneBox,
2552                                                                                         const bool colorCode,
2553                                                                                         const AxisAlignedPlane *clipPlane
2554                                                                                         ) const
2555{
2556        ViewCellContainer::const_iterator it, it_end = mViewCells.end();
2557
2558        for (it = mViewCells.begin(); it != it_end; ++ it)
2559        {
2560                if (!mOnlyValidViewCells || (*it)->GetValid())
2561                {
2562                        ExportColor(exporter, *it, colorCode); 
2563                        ExportViewCellGeometry(exporter, *it, sceneBox, clipPlane);
2564                }
2565        }
2566}
2567
2568
2569void ViewCellsManager::CreateViewCellMeshes()
2570{
2571        // convert to meshes
2572        ViewCellContainer::const_iterator it, it_end = mViewCells.end();
2573
2574        for (it = mViewCells.begin(); it != it_end; ++ it)
2575        {
2576                if (!(*it)->GetMesh())
2577                {
2578                        CreateMesh(*it);
2579                }
2580        }
2581}
2582
2583
2584bool ViewCellsManager::ExportViewCells(const string filename,
2585                                                                           const bool exportPvs,
2586                                                                           const ObjectContainer &objects)
2587{
2588        return false;
2589}
2590
2591
2592void ViewCellsManager::CollectViewCells(const int n)
2593{
2594        mNumActiveViewCells = n;
2595        mViewCells.clear();
2596        // implemented in subclasses
2597        CollectViewCells();
2598}
2599
2600
2601void ViewCellsManager::SetViewCellActive(ViewCell *vc) const
2602{
2603        ViewCellContainer leaves;
2604        // sets the pointers to the currently active view cells
2605        mViewCellsTree->CollectLeaves(vc, leaves);
2606
2607        ViewCellContainer::const_iterator lit, lit_end = leaves.end();
2608        for (lit = leaves.begin(); lit != lit_end; ++ lit)
2609        {
2610                dynamic_cast<ViewCellLeaf *>(*lit)->SetActiveViewCell(vc);
2611        }
2612}
2613
2614
2615void ViewCellsManager::SetViewCellsActive()
2616{
2617        // collect leaf view cells and set the pointers to
2618        // the currently active view cells
2619        ViewCellContainer::const_iterator it, it_end = mViewCells.end();
2620
2621        for (it = mViewCells.begin(); it != it_end; ++ it)
2622        {
2623                SetViewCellActive(*it);
2624        }
2625}
2626
2627
2628int ViewCellsManager::GetMaxFilterSize() const
2629{
2630        return mMaxFilterSize; 
2631}
2632
2633
2634static const bool USE_ASCII = true;
2635
2636
2637bool ViewCellsManager::ExportBoundingBoxes(const string filename,
2638                                                                                   const ObjectContainer &objects) const
2639{
2640        ObjectContainer::const_iterator it, it_end = objects.end();
2641       
2642        if (USE_ASCII)
2643        {
2644                ofstream boxesOut(filename.c_str());
2645                if (!boxesOut.is_open())
2646                        return false;
2647
2648                for (it = objects.begin(); it != it_end; ++ it)
2649                {
2650                        MeshInstance *mi = dynamic_cast<MeshInstance *>(*it);
2651                        const AxisAlignedBox3 box = mi->GetBox();
2652
2653                        boxesOut << mi->GetId() << " "
2654                                         << box.Min().x << " "
2655                                         << box.Min().y << " "
2656                                         << box.Min().z << " "
2657                                         << box.Max().x << " "
2658                                         << box.Max().y << " "
2659                     << box.Max().z << endl;   
2660                }
2661
2662                boxesOut.close();
2663        }
2664        else
2665        {
2666                ofstream boxesOut(filename.c_str(), ios::binary);
2667
2668                if (!boxesOut.is_open())
2669                        return false;
2670
2671                for (it = objects.begin(); it != it_end; ++ it)
2672                {       
2673                        MeshInstance *mi = dynamic_cast<MeshInstance *>(*it);
2674                        const AxisAlignedBox3 box = mi->GetBox();
2675                        Vector3 bmin = box.Min();
2676                        Vector3 bmax = box.Max();
2677                        int id = mi->GetId();
2678
2679                        boxesOut.write(reinterpret_cast<char *>(&id), sizeof(int));
2680                        boxesOut.write(reinterpret_cast<char *>(&bmin), sizeof(Vector3));
2681                        boxesOut.write(reinterpret_cast<char *>(&bmax), sizeof(Vector3));
2682                }
2683               
2684                boxesOut.close();
2685        }
2686
2687        return true;
2688}
2689
2690
2691bool ViewCellsManager::LoadBoundingBoxes(const string filename,
2692                                                                                 IndexedBoundingBoxContainer &boxes) const
2693{
2694        Vector3 bmin, bmax;
2695        int id;
2696
2697        if (USE_ASCII)
2698        {
2699                ifstream boxesIn(filename.c_str());
2700               
2701                if (!boxesIn.is_open())
2702                {
2703                        cout << "failed to open file " << filename << endl;
2704                        return false;
2705                }
2706
2707                string buf;
2708                while (!(getline(boxesIn, buf)).eof())
2709                {
2710                        sscanf(buf.c_str(), "%d %f %f %f %f %f %f",
2711                                   &id, &bmin.x, &bmin.y, &bmin.z,
2712                                   &bmax.x, &bmax.y, &bmax.z);
2713               
2714                        AxisAlignedBox3 box(bmin, bmax);
2715                        //      MeshInstance *mi = new MeshInstance();
2716                        // HACK: set bounding box to new box
2717                        //mi->mBox = box;
2718
2719                        boxes.push_back(IndexedBoundingBox(id, box));
2720                }
2721
2722                boxesIn.close();
2723        }
2724        else
2725        {
2726                ifstream boxesIn(filename.c_str(), ios::binary);
2727
2728                if (!boxesIn.is_open())
2729                        return false;
2730
2731                while (1)
2732                {
2733                        boxesIn.read(reinterpret_cast<char *>(&id), sizeof(Vector3));
2734                        boxesIn.read(reinterpret_cast<char *>(&bmin), sizeof(Vector3));
2735                        boxesIn.read(reinterpret_cast<char *>(&bmax), sizeof(Vector3));
2736                       
2737                        if (boxesIn.eof())
2738                                break;
2739
2740                       
2741                        AxisAlignedBox3 box(bmin, bmax);
2742                        MeshInstance *mi = new MeshInstance(NULL);
2743
2744                        // HACK: set bounding box to new box
2745                        //mi->mBox = box;
2746                        //boxes.push_back(mi);
2747                        boxes.push_back(IndexedBoundingBox(id, box));
2748                }
2749
2750                boxesIn.close();
2751        }
2752
2753        return true;
2754}
2755
2756
2757float ViewCellsManager::GetFilterWidth()
2758{
2759        return mFilterWidth;
2760}
2761
2762
2763float ViewCellsManager::GetAbsFilterWidth()
2764{
2765        return Magnitude(mViewSpaceBox.Size()) * mFilterWidth;
2766}
2767
2768
2769void ViewCellsManager::UpdateScalarPvsSize(ViewCell *vc,
2770                                                                                   const float pvsCost,
2771                                                                                   const int entriesInPvs) const
2772{
2773        vc->mPvsCost = pvsCost;
2774        vc->mEntriesInPvs = entriesInPvs;
2775
2776        vc->mPvsSizeValid = true;
2777}
2778
2779
2780void
2781ViewCellsManager::ApplyFilter(ViewCell *viewCell,
2782                                                          KdTree *kdTree,
2783                                                          const float viewSpaceFilterSize,
2784                                                          const float spatialFilterSize,
2785                                                          ObjectPvs &pvs
2786                                                          )
2787{
2788  // extend the pvs of the viewcell by pvs of its neighbors
2789  // and apply spatial filter by including all neighbors of the objects
2790  // in the pvs
2791
2792  // get all viewcells intersecting the viewSpaceFilterBox
2793  // and compute the pvs union
2794 
2795  //Vector3 center = viewCell->GetBox().Center();
2796  //  Vector3 center = m->mBox.Center();
2797
2798        //  AxisAlignedBox3 box(center - Vector3(viewSpaceFilterSize/2),
2799        //                                        center + Vector3(viewSpaceFilterSize/2));
2800        if (!ViewCellsConstructed())
2801                return;
2802
2803        if (viewSpaceFilterSize >= 0.0f) {
2804
2805                const bool usePrVS = false;
2806
2807                if (!usePrVS) {
2808                        AxisAlignedBox3 box = GetViewCellBox(viewCell);
2809                        box.Enlarge(Vector3(viewSpaceFilterSize/2));
2810
2811                        ViewCellContainer viewCells;
2812                        ComputeBoxIntersections(box, viewCells);
2813
2814                        //  cout<<"box="<<box<<endl;
2815                        ViewCellContainer::const_iterator it = viewCells.begin(), it_end = viewCells.end();
2816
2817                        for (; it != it_end; ++ it)
2818                        {
2819                                ObjectPvs interPvs;
2820                                //cout<<"v"<<i<<" pvs="<<(*it)->GetPvs().mEntries.size()<<endl;
2821                                ObjectPvs::Merge(interPvs, pvs, (*it)->GetPvs());
2822
2823                                pvs = interPvs;
2824                        }
2825                } else
2826                {
2827                        PrVs prvs;
2828                        AxisAlignedBox3 box = GetViewCellBox(viewCell);
2829
2830                        //  mViewCellsManager->SetMaxFilterSize(1);
2831                        GetPrVS(box.Center(), prvs, viewSpaceFilterSize);
2832                        pvs = prvs.mViewCell->GetPvs();
2833                        DeleteLocalMergeTree(prvs.mViewCell);
2834                }
2835        }
2836        else
2837        {
2838                pvs = viewCell->GetPvs();
2839        }
2840
2841        if (spatialFilterSize >=0.0f)
2842                ApplySpatialFilter(kdTree, spatialFilterSize, pvs);
2843
2844}
2845
2846
2847
2848void
2849ViewCellsManager::ApplyFilter(KdTree *kdTree,
2850                                                          const float relViewSpaceFilterSize,
2851                                                          const float relSpatialFilterSize
2852                                                          )
2853{
2854
2855        if (!ViewCellsConstructed())
2856                return;
2857
2858        ViewCellContainer::const_iterator it, it_end = mViewCells.end();
2859
2860        ObjectPvs *newPvs;
2861        newPvs = new ObjectPvs[mViewCells.size()];
2862
2863        float viewSpaceFilterSize = Magnitude(mViewSpaceBox.Size())*relViewSpaceFilterSize;
2864        float spatialFilterSize = Magnitude(kdTree->GetBox().Size())*relSpatialFilterSize;
2865       
2866        int i;
2867        for (i=0, it = mViewCells.begin(); it != it_end; ++ it, ++ i) {
2868          ApplyFilter(*it,
2869                                  kdTree,
2870                                  viewSpaceFilterSize,
2871                                  spatialFilterSize,
2872                                  newPvs[i]
2873                                  );
2874        }
2875       
2876        // now replace all pvss
2877        for (i = 0, it = mViewCells.begin(); it != it_end; ++ it, ++ i) {
2878         
2879          ObjectPvs &pvs = (*it)->GetPvs();
2880          pvs.Clear();
2881          pvs = newPvs[i];
2882          newPvs[i].Clear();
2883        }
2884
2885        delete [] newPvs;
2886}
2887
2888
2889void
2890ViewCellsManager::ApplySpatialFilter(
2891                                                                         KdTree *kdTree,
2892                                                                         const float spatialFilterSize,
2893                                                                         ObjectPvs &pvs
2894                                                                         )
2895{
2896  // now compute a new Pvs by including also objects intersecting the
2897  // extended boxes of visible objects
2898  Intersectable::NewMail();
2899
2900  ObjectPvsIterator pit = pvs.GetIterator();
2901
2902  while (pit.HasMoreEntries())
2903  {             
2904          ObjectPvsEntry entry = pit.Next();
2905 
2906          Intersectable *object = entry.mObject;
2907      object->Mail();
2908  }
2909
2910  ObjectPvs nPvs;
2911  int nPvsSize = 0;
2912 
2913  ObjectPvsIterator pit2 = pvs.GetIterator();
2914
2915  while (pit2.HasMoreEntries())
2916  {             
2917          // now go through the pvs again
2918          ObjectPvsEntry entry = pit2.Next();
2919          Intersectable *object = entry.mObject;
2920
2921          //    Vector3 center = object->GetBox().Center();
2922          //    AxisAlignedBox3 box(center - Vector3(spatialFilterSize/2),
2923          //                                            center + Vector3(spatialFilterSize/2));
2924
2925          AxisAlignedBox3 box = object->GetBox();
2926          box.Enlarge(Vector3(spatialFilterSize/2));
2927
2928          ObjectContainer objects;
2929
2930          // $$ warning collect objects takes only unmailed ones!
2931          kdTree->CollectObjects(box, objects);
2932          //    cout<<"collected objects="<<objects.size()<<endl;
2933          ObjectContainer::const_iterator noi = objects.begin();
2934          for (; noi != objects.end(); ++ noi)
2935          {
2936                  Intersectable *o = *noi;
2937                 
2938                  // $$ JB warning: pdfs are not correct at this point!   
2939                  nPvs.AddSample(o, Limits::Small);
2940                  nPvsSize ++;
2941          }
2942  }
2943
2944  // cout<<"nPvs size = "<<nPvsSize<<endl;
2945  pvs.MergeInPlace(nPvs);
2946}
2947
2948
2949void ViewCellsManager::MergeViewCellsRecursivly(ObjectPvs &pvs,
2950                                                                                                const ViewCellContainer &viewCells) const
2951{
2952        MergeViewCellsRecursivly(pvs, viewCells, 0, (int)viewCells.size() - 1);
2953}
2954
2955
2956void ViewCellsManager::MergeViewCellsRecursivly(ObjectPvs &pvs,
2957                                                                                                const ViewCellContainer &viewCells,
2958                                                                                                const int leftIdx,
2959                                                                                                const int rightIdx) const
2960{
2961        if (leftIdx == rightIdx)
2962        {
2963                pvs = viewCells[leftIdx]->GetPvs();
2964        }
2965        else
2966        {
2967                const int midSplit = (leftIdx + rightIdx) / 2;
2968       
2969                ObjectPvs leftPvs, rightPvs;
2970                MergeViewCellsRecursivly(leftPvs, viewCells, leftIdx, midSplit);
2971                MergeViewCellsRecursivly(rightPvs, viewCells, midSplit, rightIdx);
2972
2973        ObjectPvs::Merge(pvs, leftPvs, rightPvs);
2974        }
2975}
2976
2977
2978PvsFilterStatistics
2979ViewCellsManager::ApplyFilter2(ViewCell *viewCell,
2980                                                           const bool useViewSpaceFilter,
2981                                                           const float filterSize,
2982                                                           ObjectPvs &pvs,
2983                                                           vector<AxisAlignedBox3> *filteredBoxes
2984                                                           )
2985{
2986  PvsFilterStatistics stats;
2987
2988  AxisAlignedBox3 vbox = GetViewCellBox(viewCell);
2989  Vector3 center = vbox.Center();
2990  // copy the PVS
2991  Intersectable::NewMail();
2992  ObjectPvs basePvs = viewCell->GetPvs();
2993  ObjectPvsIterator pit = basePvs.GetIterator();
2994
2995  pvs.Reserve(viewCell->GetFilteredPvsSize());
2996
2997  if (!mUseKdPvs)
2998  {
2999          // first mark all objects from this pvs
3000          while (pit.HasMoreEntries()) 
3001          {
3002                  ObjectPvsEntry entry = pit.Next();
3003                  Intersectable *object = entry.mObject;
3004                  object->Mail();
3005          }
3006  }
3007 
3008  int pvsSize = 0;
3009  int nPvsSize = 0;
3010  float samples = (float)basePvs.GetSamples();
3011 
3012  Debug<<"f #s="<<samples<<"  pvs size = "<<basePvs.GetSize();
3013  //  cout<<"Filter size = "<<filterSize<<endl;
3014  //  cout<<"vbox = "<<vbox<<endl;
3015  //  cout<<"center = "<<center<<endl;
3016
3017
3018   // Minimal number of local samples to take into account
3019   // the local sampling density.
3020   // The size of the filter is a minimum of the conservative
3021   // local sampling density estimate (#rays intersecting teh viewcell and
3022   // the object)
3023   // and gobal estimate for the view cell
3024   // (total #rays intersecting the viewcell)
3025  int minLocalSamples = 2;
3026 
3027  float viewCellRadius = 0.5f*Magnitude(vbox.Diagonal());
3028 
3029  // now compute the filter box around the current viewCell
3030 
3031  if (useViewSpaceFilter) {
3032        //      float radius = Max(viewCellRadius/100.0f, avgRadius - viewCellRadius);
3033        float radius = viewCellRadius/100.0f;
3034        vbox.Enlarge(radius);
3035        cout<<"vbox = "<<vbox<<endl;
3036        ViewCellContainer viewCells;
3037        ComputeBoxIntersections(vbox, viewCells);
3038       
3039        ViewCellContainer::const_iterator it = viewCells.begin(),
3040          it_end = viewCells.end();
3041        int i = 0;
3042        for (i=0; it != it_end; ++ it, ++ i)
3043          if ((*it) != viewCell) {
3044                //cout<<"v"<<i<<" pvs="<<(*it)->GetPvs().mEntries.size()<<endl;
3045                basePvs.MergeInPlace((*it)->GetPvs());
3046          }
3047       
3048        // update samples and globalC
3049        samples = (float)pvs.GetSamples();
3050        //      cout<<"neighboring viewcells = "<<i-1<<endl;
3051        //      cout<<"Samples' = "<<samples<<endl;
3052  }
3053 
3054  // Minimal number of samples so that filtering takes place
3055#define MIN_SAMPLES  50
3056 
3057  if (samples > MIN_SAMPLES) {
3058        float globalC = 2.0f*filterSize/sqrt(samples);
3059       
3060        pit = basePvs.GetIterator();
3061       
3062        ObjectContainer objects;
3063       
3064        while (pit.HasMoreEntries()) {         
3065          ObjectPvsEntry entry = pit.Next();
3066         
3067          Intersectable *object = entry.mObject;
3068          // compute filter size based on the distance and the numebr of samples
3069          AxisAlignedBox3 box = object->GetBox();
3070         
3071          float distance = Distance(center, box.Center());
3072          float globalRadius = distance*globalC;
3073         
3074          int objectSamples = (int)entry.mData.mSumPdf;
3075          float localRadius = MAX_FLOAT;
3076         
3077          localRadius = filterSize*0.5f*Magnitude(box.Diagonal())/
3078                sqrt((float)objectSamples);
3079         
3080          //      cout<<"os="<<objectSamples<<" lr="<<localRadius<<" gr="<<globalRadius<<endl;
3081         
3082          // now compute the filter size
3083          float radius;
3084         
3085#if 0
3086          if (objectSamples <= 1) {
3087                if (localRadius > globalRadius) {
3088                  radius = 0.5flRadius;
3089                  stats.mLocalFilterCount++;
3090                } else {
3091                  radius = globalRadius;
3092                  stats.mGlobalFilterCount++;
3093                }
3094          } else {
3095                radius = localRadius;
3096                stats.mLocalFilterCount++;
3097          }
3098#else
3099          radius = 0.5f*globalRadius + 0.5f*localRadius;
3100
3101          if (localRadius > globalRadius)
3102                stats.mLocalFilterCount++;
3103          else
3104                stats.mGlobalFilterCount++;
3105#endif
3106         
3107          stats.mAvgFilterRadius += radius;
3108         
3109          // cout<<"box = "<<box<<endl;
3110          //    cout<<"distance = "<<distance<<endl;
3111          //    cout<<"radiues = "<<radius<<endl;
3112         
3113          box.Enlarge(Vector3(radius));
3114
3115          if (filteredBoxes)
3116                filteredBoxes->push_back(box);
3117
3118          objects.clear();
3119          // $$ warning collect objects takes only unmailed ones!
3120          if (mUseKdPvsAfterFiltering) {
3121                GetPreprocessor()->mKdTree->CollectKdObjects(box, objects);
3122          } else
3123                CollectObjects(box, objects);
3124         
3125          //    cout<<"collected objects="<<objects.size()<<endl;
3126          ObjectContainer::const_iterator noi = objects.begin();
3127          for (; noi != objects.end(); ++ noi) {
3128                Intersectable *o = *noi;
3129                // $$ JB warning: pdfs are not correct at this point!     
3130                pvs.AddSampleDirty(o, Limits::Small);
3131          }
3132        }
3133        stats.mAvgFilterRadius /= (stats.mLocalFilterCount + stats.mGlobalFilterCount);
3134  }
3135 
3136  Debug<<" nPvs size = "<<pvs.GetSize()<<endl;
3137 
3138  if (!mUseKdPvs)
3139  {
3140          // copy the base pvs to the new pvs
3141          pit = basePvs.GetIterator();
3142          while (pit.HasMoreEntries())
3143          {             
3144                  ObjectPvsEntry entry = pit.Next();
3145                  pvs.AddSampleDirty(entry.mObject, entry.mData.mSumPdf);
3146          }
3147  }
3148 
3149  pvs.SimpleSort();
3150  viewCell->SetFilteredPvsSize(pvs.GetSize());
3151 
3152  Intersectable::NewMail();
3153  return stats;
3154}
3155
3156
3157
3158void ViewCellsManager::ExportColor(Exporter *exporter,
3159                                                                   ViewCell *vc,
3160                                                                   bool colorCode) const
3161{
3162        const bool vcValid = CheckValidity(vc, mMinPvsSize, mMaxPvsSize);
3163
3164        float importance = 0;
3165        static Material m;
3166        //cout << "color code: " << colorCode << endl;
3167        switch (mColorCode)
3168        {
3169        case 0: // Random
3170                {
3171                        if (vcValid)
3172                        {
3173                                m.mDiffuseColor.r = 0.2f + RandomValue(0.0f, 0.8f);
3174                                m.mDiffuseColor.g = 0.2f + RandomValue(0.0f, 0.8f);
3175                                m.mDiffuseColor.b = 0.2f + RandomValue(0.0f, 0.8f);
3176                        }
3177                        else
3178                        {
3179                                m.mDiffuseColor.r = 0.0f;
3180                                m.mDiffuseColor.g = 1.0f;
3181                                m.mDiffuseColor.b = 0.0f;
3182                        }
3183
3184                        exporter->SetForcedMaterial(m);
3185                        return;
3186                }
3187               
3188        case 1: // pvs
3189                {
3190                        if (mCurrentViewCellsStats.maxPvs)
3191                        {
3192                                importance = (float)mViewCellsTree->GetPvsCost(vc) /
3193                                                         (float)mCurrentViewCellsStats.maxPvs;
3194                        }
3195                }
3196                break;
3197        case 2: // merges
3198                {
3199            const int lSize = mViewCellsTree->GetNumInitialViewCells(vc);
3200                        importance = (float)lSize / (float)mCurrentViewCellsStats.maxLeaves;
3201                }
3202                break;
3203#if 0
3204        case 3: // merge tree differene
3205                {
3206                        importance = (float)GetMaxTreeDiff(vc) /
3207                                (float)(mVspBspTree->GetStatistics().maxDepth * 2);
3208
3209                }
3210                break;
3211#endif
3212        default:
3213                break;
3214        }
3215
3216        // special color code for invalid view cells
3217        m.mDiffuseColor.r = importance;
3218        m.mDiffuseColor.b = 1.0f;//vcValid ? 0.0f : 1.0f;
3219        m.mDiffuseColor.g = 1.0f - importance;
3220
3221        //Debug << "importance: " << importance << endl;
3222        exporter->SetForcedMaterial(m);
3223}
3224
3225
3226void ViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays,
3227                                                                                          vector<MergeCandidate> &candidates)
3228{
3229        // implemented in subclasses
3230}
3231
3232
3233void ViewCellsManager::UpdatePvsForEvaluation()
3234{
3235        ObjectPvs objPvs;
3236        UpdatePvsForEvaluation(mViewCellsTree->GetRoot(), objPvs);
3237}
3238
3239void ViewCellsManager::UpdatePvsForEvaluation(ViewCell *root, ObjectPvs &pvs)
3240{
3241        // terminate traversal
3242        if (root->IsLeaf())
3243        {
3244                //cout << "updating leaf" << endl;
3245                // we assume that pvs is explicitly stored in leaves
3246                pvs = root->GetPvs();
3247                UpdateScalarPvsSize(root, pvs.EvalPvsCost(), pvs.GetSize());
3248                return;
3249        }
3250
3251        ////////////////
3252        //-- interior node => propagate pvs up the tree
3253
3254        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(root);
3255
3256        // reset interior pvs
3257        interior->GetPvs().Clear();
3258        // reset recursive pvs
3259        pvs.Clear();
3260
3261        // pvss of child nodes
3262        vector<ObjectPvs> pvsList;
3263        pvsList.resize((int)interior->mChildren.size());
3264
3265        ViewCellContainer::const_iterator vit, vit_end = interior->mChildren.end();
3266       
3267        int i = 0;
3268
3269        for (vit = interior->mChildren.begin(); vit != vit_end; ++ vit, ++ i)
3270        {
3271                //////////////////
3272                //-- recursivly compute child pvss
3273                UpdatePvsForEvaluation(*vit, pvsList[i]/*objPvs*/);
3274        }
3275
3276#if 1
3277        Intersectable::NewMail();
3278
3279        //-- faster way of computing pvs:
3280        //-- construct merged pvs by adding
3281        //-- and only those of the next pvs which were not mailed.
3282        //-- note: sumpdf is not correct!!
3283
3284        vector<ObjectPvs>::iterator oit = pvsList.begin();
3285
3286        for (vit = interior->mChildren.begin(); vit != vit_end; ++ vit, ++ oit)
3287        {
3288                ObjectPvsIterator pit = (*oit).GetIterator();
3289               
3290                // first mark all object from this pvs
3291                while (pit.HasMoreEntries())
3292                {               
3293                        ObjectPvsEntry entry = pit.Next();
3294
3295                        Intersectable *intersect = entry.mObject;
3296
3297                        if (!intersect->Mailed())
3298                        {
3299                                pvs.AddSample(intersect, entry.mData.mSumPdf);
3300                                intersect->Mail();
3301                        }
3302                }
3303        }
3304
3305        // store pvs in this node
3306        if (mViewCellsTree->ViewCellsStorage() == ViewCellsTree::PVS_IN_INTERIORS)
3307        {
3308                interior->SetPvs(pvs);
3309        }
3310       
3311        // set new pvs size
3312        UpdateScalarPvsSize(interior, pvs.EvalPvsCost(), pvs.GetSize());
3313       
3314#else
3315        // really merge cells: slow put sumPdf is correct
3316        viewCellInterior->GetPvs().Merge(backVc->GetPvs());
3317        viewCellInterior->GetPvs().Merge(frontVc->GetPvs());
3318#endif
3319}
3320
3321
3322
3323/*******************************************************************/
3324/*               BspViewCellsManager implementation                */
3325/*******************************************************************/
3326
3327
3328BspViewCellsManager::BspViewCellsManager(ViewCellsTree *vcTree, BspTree *bspTree):
3329ViewCellsManager(vcTree), mBspTree(bspTree)
3330{
3331        Environment::GetSingleton()->GetIntValue("BspTree.Construction.samples", mInitialSamples);
3332
3333        mBspTree->SetViewCellsManager(this);
3334        mBspTree->SetViewCellsTree(mViewCellsTree);
3335}
3336
3337
3338bool BspViewCellsManager::ViewCellsConstructed() const
3339{
3340        return mBspTree->GetRoot() != NULL;
3341}
3342
3343
3344ViewCell *BspViewCellsManager::GenerateViewCell(Mesh *mesh) const
3345{
3346        return new BspViewCell(mesh);
3347}
3348
3349
3350int BspViewCellsManager::ConstructSubdivision(const ObjectContainer &objects,
3351                                                                                          const VssRayContainer &rays)
3352{
3353        // if view cells were already constructed, we can finish
3354        if (ViewCellsConstructed())
3355                return 0;
3356
3357        int sampleContributions = 0;
3358
3359        // construct view cells using the collected samples
3360        RayContainer constructionRays;
3361        VssRayContainer savedRays;
3362
3363        // choose a a number of rays based on the ratio of cast rays / requested rays
3364        const int limit = min(mInitialSamples, (int)rays.size());
3365        VssRayContainer::const_iterator it, it_end = rays.end();
3366
3367        const float prop = (float)limit / ((float)rays.size() + Limits::Small);
3368
3369        for (it = rays.begin(); it != it_end; ++ it)
3370        {
3371                if (Random(1.0f) < prop)
3372                        constructionRays.push_back(new Ray(*(*it)));
3373                else
3374                        savedRays.push_back(*it);
3375        }
3376
3377    if (!mUsePredefinedViewCells)
3378        {
3379                // no view cells loaded
3380                mBspTree->Construct(objects, constructionRays, &mViewSpaceBox);
3381                // collect final view cells
3382                mBspTree->CollectViewCells(mViewCells);
3383        }
3384        else
3385        {       
3386                // use predefined view cells geometry =>
3387                // contruct bsp hierarchy over them
3388                mBspTree->Construct(mViewCells);
3389        }
3390
3391        // destroy rays created only for construction
3392        CLEAR_CONTAINER(constructionRays);
3393
3394        Debug << mBspTree->GetStatistics() << endl;
3395        Debug << "\nView cells after construction:\n" << mCurrentViewCellsStats << endl;
3396
3397        // recast rest of the rays
3398        if (SAMPLE_AFTER_SUBDIVISION)
3399                ComputeSampleContributions(savedRays, true, false);
3400
3401        // real meshes are contructed at this stage
3402        if (0)
3403        {
3404                cout << "finalizing view cells ... ";
3405                FinalizeViewCells(true);
3406                cout << "finished" << endl;     
3407        }
3408
3409        return sampleContributions;
3410}
3411
3412
3413void BspViewCellsManager::CollectViewCells()
3414{       
3415        if (!ViewCellsTreeConstructed())
3416        {       // view cells tree constructed 
3417                mBspTree->CollectViewCells(mViewCells);
3418        }
3419        else
3420        {       // we can use the view cells tree hierarchy to get the right set
3421                mViewCellsTree->CollectBestViewCellSet(mViewCells, mNumActiveViewCells);
3422        }
3423}
3424
3425
3426float BspViewCellsManager::GetProbability(ViewCell *viewCell)
3427{
3428        if (1)
3429                return GetVolume(viewCell) / GetViewSpaceBox().GetVolume();
3430        else
3431                // compute view cell area as subsititute for probability
3432                return GetArea(viewCell) / GetAccVcArea();
3433}
3434
3435
3436
3437int BspViewCellsManager::CastLineSegment(const Vector3 &origin,
3438                                                                                 const Vector3 &termination,
3439                                                                                 ViewCellContainer &viewcells)
3440{
3441        return mBspTree->CastLineSegment(origin, termination, viewcells);
3442}
3443
3444
3445bool BspViewCellsManager::LineSegmentIntersects(const Vector3 &origin,
3446                                                                                                const Vector3 &termination,
3447                                                                                                ViewCell *viewCell)
3448{
3449        return false;
3450}
3451
3452
3453void ViewCellsManager::ExportMergedViewCells(const ObjectContainer &objects)
3454{
3455        // save color code
3456        const int savedColorCode = mColorCode;
3457
3458        Exporter *exporter;
3459
3460#if 0
3461        // export merged view cells
3462        mColorCode = 0; // use random colors
3463
3464        exporter = Exporter::GetExporter("merged_view_cells.wrl");
3465
3466        cout << "exporting view cells after merge ... ";
3467
3468        if (exporter)
3469        {
3470                if (mExportGeometry)
3471                {
3472                        exporter->ExportGeometry(objects);
3473                }
3474
3475                exporter->SetFilled();
3476                ExportViewCellsForViz(exporter, NULL, mColorCode, GetClipPlane());
3477
3478                delete exporter;
3479        }
3480        cout << "finished" << endl;
3481#endif
3482
3483        // export merged view cells using pvs color coding
3484        exporter = Exporter::GetExporter("merged_view_cells_pvs.wrl");
3485        cout << "exporting view cells after merge (pvs size) ... ";     
3486
3487        if (exporter)
3488        {
3489                if (mExportGeometry)
3490                {
3491                        exporter->ExportGeometry(objects);
3492                }
3493
3494                exporter->SetFilled();
3495                mColorCode = 1;
3496
3497                ExportViewCellsForViz(exporter, NULL,  mColorCode, GetClipPlane());
3498
3499                delete exporter;
3500        }
3501        cout << "finished" << endl;
3502       
3503        mColorCode = savedColorCode;
3504}
3505
3506
3507int BspViewCellsManager::PostProcess(const ObjectContainer &objects,
3508                                                                         const VssRayContainer &rays)
3509{
3510        if (!ViewCellsConstructed())
3511        {
3512                Debug << "view cells not constructed" << endl;
3513                return 0;
3514        }
3515       
3516        // view cells already finished before post processing step,
3517        // i.e., because they were loaded from disc
3518        if (mViewCellsFinished)
3519        {
3520                FinalizeViewCells(true);
3521                EvaluateViewCellsStats();
3522
3523                return 0;
3524        }
3525
3526        //////////////////
3527        //-- merge leaves of the view cell hierarchy   
3528       
3529        cout << "starting post processing using " << mPostProcessSamples << " samples ... ";
3530        long startTime = GetTime();
3531       
3532        VssRayContainer postProcessRays;
3533        GetRaySets(rays, mPostProcessSamples, postProcessRays);
3534
3535        if (mMergeViewCells)
3536        {
3537                cout << "constructing visibility based merge tree" << endl;
3538                mViewCellsTree->ConstructMergeTree(rays, objects);
3539        }
3540        else
3541        {
3542                cout << "constructing spatial merge tree" << endl;
3543                ViewCell *root;
3544                // the spatial merge tree is difficult to build for
3545                // this type of construction, as view cells cover several
3546                // leaves => create dummy tree which is only 2 levels deep
3547                if (mUsePredefinedViewCells)
3548                {
3549                        root = ConstructDummyMergeTree(mBspTree->GetRoot());
3550                }
3551                else
3552                {
3553                        // create spatial merge hierarchy
3554                        root = ConstructSpatialMergeTree(mBspTree->GetRoot());
3555                }
3556               
3557                mViewCellsTree->SetRoot(root);
3558
3559                // recompute pvs in the whole hierarchy
3560                ObjectPvs pvs;
3561                UpdatePvsForEvaluation(root, pvs);
3562        }
3563
3564        cout << "finished" << endl;
3565        cout << "merged view cells in "
3566                 << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
3567
3568        Debug << "Postprocessing: Merged view cells in "
3569                << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl << endl;
3570
3571       
3572        ////////////////////////
3573        //-- visualization and statistics after merge
3574
3575        if (1)
3576        {
3577                char mstats[100];
3578                Environment::GetSingleton()->GetStringValue("ViewCells.mergeStats", mstats);
3579                mViewCellsTree->ExportStats(mstats);
3580        }
3581
3582        // recompute view cells and stats
3583        ResetViewCells();
3584        Debug << "\nView cells after merge:\n" << mCurrentViewCellsStats << endl;
3585
3586        //  visualization of the view cells
3587        if (1) ExportMergedViewCells(objects);
3588
3589        // compute final meshes and volume / area
3590        if (1) FinalizeViewCells(true);
3591       
3592        return 0;
3593}
3594
3595
3596BspViewCellsManager::~BspViewCellsManager()
3597{
3598}
3599
3600
3601int BspViewCellsManager::GetType() const
3602{
3603        return BSP;
3604}
3605
3606
3607void BspViewCellsManager::Visualize(const ObjectContainer &objects,
3608                                                                        const VssRayContainer &sampleRays)
3609{
3610        if (!ViewCellsConstructed())
3611                return;
3612       
3613        const int savedColorCode = mColorCode;
3614       
3615        if (1) // export final view cells
3616        {
3617                mColorCode = 1; // hack color code
3618                Exporter *exporter = Exporter::GetExporter("final_view_cells.wrl");
3619       
3620                cout << "exporting view cells after merge (pvs size) ... ";     
3621
3622                if (exporter)
3623                {
3624                        if (mExportGeometry)
3625                        {
3626                                exporter->ExportGeometry(objects);
3627                        }
3628
3629                        ExportViewCellsForViz(exporter, NULL, mColorCode, GetClipPlane());
3630                        delete exporter;
3631                }
3632                cout << "finished" << endl;
3633        }
3634
3635        // reset color code
3636        mColorCode = savedColorCode;
3637
3638
3639        //////////////////
3640        //-- visualization of the BSP splits
3641
3642        bool exportSplits = false;
3643        Environment::GetSingleton()->GetBoolValue("BspTree.Visualization.exportSplits", exportSplits);
3644
3645        if (exportSplits)
3646        {
3647                cout << "exporting splits ... ";
3648                ExportSplits(objects);
3649                cout << "finished" << endl;
3650        }
3651
3652        int leafOut;
3653        Environment::GetSingleton()->GetIntValue("ViewCells.Visualization.maxOutput", leafOut);
3654        const int raysOut = 100;
3655        ExportSingleViewCells(objects, leafOut, false, true, false, raysOut, "");
3656}
3657
3658
3659void BspViewCellsManager::ExportSplits(const ObjectContainer &objects)
3660{
3661        Exporter *exporter = Exporter::GetExporter("bsp_splits.x3d");
3662
3663        if (exporter)
3664        {
3665                //exporter->SetFilled();
3666                if (mExportGeometry)
3667                {
3668                        exporter->ExportGeometry(objects);
3669                }
3670
3671                Material m;
3672                m.mDiffuseColor = RgbColor(1, 0, 0);
3673                exporter->SetForcedMaterial(m);
3674                exporter->SetWireframe();
3675
3676                exporter->ExportBspSplits(*mBspTree, true);
3677
3678                // NOTE: take forced material, else big scenes cannot be viewed
3679                m.mDiffuseColor = RgbColor(0, 1, 0);
3680                exporter->SetForcedMaterial(m);
3681                //exporter->ResetForcedMaterial();
3682
3683                delete exporter;
3684        }
3685}
3686
3687
3688void BspViewCellsManager::ExportSingleViewCells(const ObjectContainer &objects,
3689                                                                                                const int maxViewCells,
3690                                                                                                const bool sortViewCells,
3691                                                                                                const bool exportPvs,
3692                                                                                                const bool exportRays,
3693                                                                                                const int maxRays,
3694                                                                                                const string prefix,
3695                                                                                                VssRayContainer *visRays)
3696{
3697        if (sortViewCells)
3698        {       // sort view cells to visualize the largest view cells
3699                sort(mViewCells.begin(), mViewCells.end(), ViewCell::LargerRenderCost);
3700        }
3701
3702        //////////
3703        //-- some view cells for output
3704
3705        ViewCell::NewMail();
3706        const int limit = min(maxViewCells, (int)mViewCells.size());
3707       
3708        for (int i = 0; i < limit; ++ i)
3709        {
3710                const int idx = sortViewCells ? (int)RandomValue(0, (float)mViewCells.size() - 0.5f) : i;
3711                ViewCell *vc = mViewCells[idx];
3712
3713                if (vc->Mailed() || vc->GetId() == OUT_OF_BOUNDS_ID)
3714                        continue;
3715
3716                vc->Mail();
3717
3718                ObjectPvs pvs;
3719                mViewCellsTree->GetPvs(vc, pvs);
3720
3721                char s[64]; sprintf(s, "%sviewcell-%04d.wrl", prefix.c_str(), i);
3722                Exporter *exporter = Exporter::GetExporter(s);
3723               
3724                cout << "view cell " << idx << ": pvs cost=" << (int)mViewCellsTree->GetPvsCost(vc) << endl;
3725
3726                if (exportRays)
3727                {
3728                        ////////////
3729                        //-- export rays piercing this view cell
3730
3731                        // use rays stored with the view cells
3732                        VssRayContainer vcRays, vcRays2, vcRays3;
3733            VssRayContainer collectRays;
3734
3735                        // collect initial view cells
3736                        ViewCellContainer leaves;
3737                        mViewCellsTree->CollectLeaves(vc, leaves);
3738
3739                        ViewCellContainer::const_iterator vit, vit_end = leaves.end();
3740                for (vit = leaves.begin(); vit != vit_end; ++ vit)
3741                        {       
3742                                // prepare some rays for output
3743                                VssRayContainer::const_iterator rit, rit_end = (*vit)->GetOrCreateRays()->end();
3744                                for (rit = (*vit)->GetOrCreateRays()->begin(); rit != rit_end; ++ rit)
3745                                {
3746                                        collectRays.push_back(*rit);
3747                                }
3748                        }
3749
3750                        const int raysOut = min((int)collectRays.size(), maxRays);
3751
3752                        // prepare some rays for output
3753                        VssRayContainer::const_iterator rit, rit_end = collectRays.end();
3754                        for (rit = collectRays.begin(); rit != rit_end; ++ rit)
3755                        {
3756                                const float p = RandomValue(0.0f, (float)collectRays.size());
3757                                if (p < raysOut)
3758                                {
3759                                        if ((*rit)->mFlags & VssRay::BorderSample)
3760                                        {
3761                                                vcRays.push_back(*rit);
3762                                        }
3763                                        else if ((*rit)->mFlags & VssRay::ReverseSample)
3764                                        {
3765                                                vcRays2.push_back(*rit);
3766                                        }
3767                                        else
3768                                        {
3769                                                vcRays3.push_back(*rit);
3770                                        }       
3771                                }
3772                        }
3773
3774                        exporter->ExportRays(vcRays, RgbColor(1, 0, 0));
3775                        exporter->ExportRays(vcRays2, RgbColor(0, 1, 0));
3776                        exporter->ExportRays(vcRays3, RgbColor(1, 1, 1));
3777                }
3778               
3779                ////////////////
3780                //-- export view cell geometry
3781
3782                exporter->SetWireframe();
3783
3784                Material m;//= RandomMaterial();
3785                m.mDiffuseColor = RgbColor(0, 1, 0);
3786                exporter->SetForcedMaterial(m);
3787
3788                ExportViewCellGeometry(exporter, vc, NULL, NULL);
3789                exporter->SetFilled();
3790
3791                if (exportPvs)
3792                {
3793                        Intersectable::NewMail();
3794                        ObjectPvsIterator pit = pvs.GetIterator();
3795
3796                        while (pit.HasMoreEntries())
3797                        {               
3798                                ObjectPvsEntry entry = pit.Next();
3799
3800                // output PVS of view cell
3801                                Intersectable *intersect = entry.mObject;
3802                               
3803                                if (!intersect->Mailed())
3804                                {
3805                                        intersect->Mail();
3806
3807                                        m = RandomMaterial();
3808                                        exporter->SetForcedMaterial(m);
3809                                        exporter->ExportIntersectable(intersect);
3810                                }
3811                        }
3812                        cout << endl;
3813                }
3814               
3815                DEL_PTR(exporter);
3816                cout << "finished" << endl;
3817        }
3818}
3819
3820
3821void BspViewCellsManager::TestSubdivision()
3822{
3823        ViewCellContainer leaves;
3824        mViewCellsTree->CollectLeaves(mViewCellsTree->GetRoot(), leaves);
3825
3826        ViewCellContainer::const_iterator it, it_end = leaves.end();
3827
3828        const float vol = mViewSpaceBox.GetVolume();
3829        float subdivVol = 0;
3830        float newVol = 0;
3831
3832        for (it = leaves.begin(); it != it_end; ++ it)
3833        {
3834                BspNodeGeometry geom;
3835                mBspTree->ConstructGeometry(*it, geom);
3836
3837                const float lVol = geom.GetVolume();
3838                newVol += lVol;
3839                subdivVol += (*it)->GetVolume();
3840
3841                const float thres = 0.9f;
3842                if ((lVol < ((*it)->GetVolume() * thres)) ||
3843                        (lVol * thres > ((*it)->GetVolume())))
3844                        Debug << "warning: " << lVol << " " << (*it)->GetVolume() << endl;
3845        }
3846       
3847        Debug << "exact volume: " << vol << endl;
3848        Debug << "subdivision volume: " << subdivVol << endl;
3849        Debug << "new volume: " << newVol << endl;
3850}
3851
3852
3853void BspViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
3854                                                                                                 ViewCell *vc,
3855                                                                                                 const AxisAlignedBox3 *sceneBox,
3856                                                                                                 const AxisAlignedPlane *clipPlane
3857                                                                                                 ) const
3858{
3859        if (clipPlane)
3860        {
3861                const Plane3 plane = clipPlane->GetPlane();
3862
3863                ViewCellContainer leaves;
3864                mViewCellsTree->CollectLeaves(vc, leaves);
3865                ViewCellContainer::const_iterator it, it_end = leaves.end();
3866
3867                for (it = leaves.begin(); it != it_end; ++ it)
3868                {
3869                        BspNodeGeometry geom;
3870                        BspNodeGeometry front;
3871                        BspNodeGeometry back;
3872
3873                        mBspTree->ConstructGeometry(*it, geom);
3874
3875                        const float eps = 0.0001f;
3876                        const int cf = geom.Side(plane, eps);
3877
3878                        if (cf == -1)
3879                        {
3880                                exporter->ExportPolygons(geom.GetPolys());
3881                        }
3882                        else if (cf == 0)
3883                        {
3884                                geom.SplitGeometry(front,
3885                                                                   back,
3886                                                                   plane,
3887                                                                   mViewSpaceBox,
3888                                                                   eps);
3889
3890                                if (back.Valid())
3891                                {
3892                                        exporter->ExportPolygons(back.GetPolys());
3893                                }                       
3894                        }
3895                }
3896        }
3897        else
3898        {
3899                // export mesh if available
3900                // TODO: some bug here?
3901                if (1 && vc->GetMesh())
3902                {
3903                        exporter->ExportMesh(vc->GetMesh());
3904                }
3905                else
3906                {
3907                        BspNodeGeometry geom;
3908                        mBspTree->ConstructGeometry(vc, geom);
3909                        exporter->ExportPolygons(geom.GetPolys());
3910                }
3911        }
3912}
3913
3914
3915void BspViewCellsManager::CreateMesh(ViewCell *vc)
3916{
3917        // note: should previous mesh be deleted (via mesh manager?)
3918        BspNodeGeometry geom;
3919        mBspTree->ConstructGeometry(vc, geom);
3920
3921        Mesh *mesh = MeshManager::GetSingleton()->CreateResource();
3922
3923        IncludeNodeGeomInMesh(geom, *mesh);
3924        vc->SetMesh(mesh);
3925}
3926
3927
3928void BspViewCellsManager::Finalize(ViewCell *viewCell,
3929                                                                   const bool createMesh)
3930{
3931        float area = 0;
3932        float volume = 0;
3933
3934        ViewCellContainer leaves;
3935        mViewCellsTree->CollectLeaves(viewCell, leaves);
3936
3937        ViewCellContainer::const_iterator it, it_end = leaves.end();
3938
3939    for (it = leaves.begin(); it != it_end; ++ it)
3940        {
3941                BspNodeGeometry geom;
3942
3943                mBspTree->ConstructGeometry(*it, geom);
3944
3945                const float lVol = geom.GetVolume();
3946                const float lArea = geom.GetArea();
3947
3948                area += lArea;
3949                volume += lVol;
3950       
3951                CreateMesh(*it);
3952        }
3953
3954        viewCell->SetVolume(volume);
3955        viewCell->SetArea(area);
3956}
3957
3958
3959ViewCell *BspViewCellsManager::GetViewCell(const Vector3 &point, const bool active) const
3960{
3961        if (!ViewCellsConstructed())
3962        {
3963                return NULL;
3964        }
3965        if (!mViewSpaceBox.IsInside(point))
3966        {
3967                return NULL;
3968        }
3969        return mBspTree->GetViewCell(point);
3970}
3971
3972
3973void BspViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays,
3974                                                                                                 vector<MergeCandidate> &candidates)
3975{
3976        cout << "collecting merge candidates ... " << endl;
3977
3978        if (mUseRaysForMerge)
3979        {
3980                mBspTree->CollectMergeCandidates(rays, candidates);
3981        }
3982        else
3983        {
3984                vector<BspLeaf *> leaves;
3985                mBspTree->CollectLeaves(leaves);
3986                mBspTree->CollectMergeCandidates(leaves, candidates);
3987        }
3988
3989        cout << "fininshed collecting candidates" << endl;
3990}
3991
3992
3993
3994bool BspViewCellsManager::ExportViewCells(const string filename,
3995                                                                                  const bool exportPvs,
3996                                                                                  const ObjectContainer &objects)
3997{
3998        if (!ViewCellsConstructed() || !ViewCellsTreeConstructed())
3999        {
4000                return false;
4001        }
4002
4003        cout << "exporting view cells to xml ... ";
4004
4005        OUT_STREAM stream(filename.c_str());
4006
4007        // for output we need unique ids for each view cell
4008        CreateUniqueViewCellIds();
4009
4010        stream << "<?xml version=\"1.0\" encoding=\"UTF-8\"?>"<<endl;
4011        stream << "<VisibilitySolution>" << endl;
4012
4013        if (exportPvs)
4014        {
4015                //////////
4016                //-- export bounding boxes: they are used to identify the objects from the pvs and
4017                //-- assign them to the entities in the rendering engine
4018
4019                stream << "<BoundingBoxes>" << endl;
4020                ObjectContainer::const_iterator oit, oit_end = objects.end();
4021
4022                for (oit = objects.begin(); oit != oit_end; ++ oit)
4023                {
4024                        const AxisAlignedBox3 box = (*oit)->GetBox();
4025                       
4026                        stream << "<BoundingBox" << " id=\"" << (*oit)->GetId() << "\""
4027                                   << " min=\"" << box.Min().x << " " << box.Min().y << " " << box.Min().z << "\""
4028                                   << " max=\"" << box.Max().x << " " << box.Max().y << " " << box.Max().z << "\" />" << endl;
4029                }
4030
4031                stream << "</BoundingBoxes>" << endl;
4032        }
4033
4034        ///////////
4035        //-- export the view cells and the pvs
4036
4037        const int numViewCells = mCurrentViewCellsStats.viewCells;
4038        stream << "<ViewCells number=\"" << numViewCells << "\" >" << endl;
4039
4040        mViewCellsTree->Export(stream, exportPvs);
4041       
4042        stream << "</ViewCells>" << endl;
4043
4044        /////////////
4045        //-- export the view space hierarchy
4046        stream << "<ViewSpaceHierarchy type=\"bsp\""
4047                   << " min=\"" << mViewSpaceBox.Min().x << " " << mViewSpaceBox.Min().y << " " << mViewSpaceBox.Min().z << "\""
4048                   << " max=\"" << mViewSpaceBox.Max().x << " " << mViewSpaceBox.Max().y << " " << mViewSpaceBox.Max().z << "\">" << endl;
4049
4050        mBspTree->Export(stream);
4051
4052        // end tags
4053        stream << "</ViewSpaceHierarchy>" << endl;
4054        stream << "</VisibilitySolution>" << endl;
4055
4056        stream.close();
4057        cout << "finished" << endl;
4058
4059        return true;
4060}
4061
4062
4063ViewCell *BspViewCellsManager::ConstructDummyMergeTree(BspNode *root)
4064{
4065        ViewCellInterior *vcRoot = new ViewCellInterior();
4066               
4067        // evaluate merge cost for priority traversal
4068        const float mergeCost =  -(float)root->mTimeStamp;
4069        vcRoot->SetMergeCost(mergeCost);
4070
4071        float volume = 0;
4072        vector<BspLeaf *> leaves;
4073        mBspTree->CollectLeaves(leaves);
4074        vector<BspLeaf *>::const_iterator lit, lit_end = leaves.end();
4075        ViewCell::NewMail();
4076
4077        for (lit = leaves.begin(); lit != lit_end; ++ lit)
4078        {
4079                BspLeaf *leaf = *lit;
4080                ViewCell *vc = leaf->GetViewCell();
4081
4082                if (!vc->Mailed())
4083                {
4084                        vc->Mail();
4085                        vc->SetMergeCost(0.0f);
4086                        vcRoot->SetupChildLink(vc);
4087
4088                        volume += vc->GetVolume();
4089                        volume += vc->GetVolume();     
4090                        vcRoot->SetVolume(volume);
4091                }
4092        }
4093       
4094        return vcRoot;
4095}
4096
4097
4098ViewCell *BspViewCellsManager::ConstructSpatialMergeTree(BspNode *root)
4099{
4100        // terminate recursion
4101        if (root->IsLeaf())
4102        {
4103                BspLeaf *leaf = dynamic_cast<BspLeaf *>(root);
4104                leaf->GetViewCell()->SetMergeCost(0.0f);
4105                return leaf->GetViewCell();
4106        }
4107       
4108        BspInterior *interior = dynamic_cast<BspInterior *>(root);
4109        ViewCellInterior *viewCellInterior = new ViewCellInterior();
4110               
4111        // evaluate merge cost for priority traversal
4112        const float mergeCost = -(float)root->mTimeStamp;
4113        viewCellInterior->SetMergeCost(mergeCost);
4114
4115        float volume = 0;
4116       
4117        BspNode *front = interior->GetFront();
4118        BspNode *back = interior->GetBack();
4119
4120
4121        ////////////
4122        //-- recursivly compute child hierarchies
4123
4124        ViewCell *backVc = ConstructSpatialMergeTree(back);
4125        ViewCell *frontVc = ConstructSpatialMergeTree(front);
4126
4127        viewCellInterior->SetupChildLink(backVc);
4128        viewCellInterior->SetupChildLink(frontVc);
4129
4130        volume += backVc->GetVolume();
4131        volume += frontVc->GetVolume();
4132
4133        viewCellInterior->SetVolume(volume);
4134
4135        return viewCellInterior;
4136}
4137
4138
4139/************************************************************************/
4140/*                   KdViewCellsManager implementation                  */
4141/************************************************************************/
4142
4143
4144
4145KdViewCellsManager::KdViewCellsManager(ViewCellsTree *vcTree, KdTree *kdTree):
4146ViewCellsManager(vcTree), mKdTree(kdTree), mKdPvsDepth(100)
4147{
4148}
4149
4150
4151float KdViewCellsManager::GetProbability(ViewCell *viewCell)
4152{
4153        // compute view cell area / volume as subsititute for probability
4154        if (0)
4155                return GetArea(viewCell) / GetViewSpaceBox().SurfaceArea();
4156        else
4157                return GetVolume(viewCell) / GetViewSpaceBox().GetVolume();
4158}
4159
4160
4161
4162
4163void KdViewCellsManager::CollectViewCells()
4164{
4165        //mKdTree->CollectViewCells(mViewCells); TODO
4166}
4167
4168
4169int KdViewCellsManager::ConstructSubdivision(const ObjectContainer &objects,
4170                                                                  const VssRayContainer &rays)
4171{
4172        // if view cells already constructed
4173        if (ViewCellsConstructed())
4174                return 0;
4175
4176        mKdTree->Construct();
4177
4178        mTotalAreaValid = false;
4179        // create the view cells
4180        mKdTree->CreateAndCollectViewCells(mViewCells);
4181        // cast rays
4182        ComputeSampleContributions(rays, true, false);
4183
4184        EvaluateViewCellsStats();
4185        Debug << "\nView cells after construction:\n" << mCurrentViewCellsStats << endl;
4186
4187        return 0;
4188}
4189
4190
4191bool KdViewCellsManager::ViewCellsConstructed() const
4192{
4193        return mKdTree->GetRoot() != NULL;
4194}
4195
4196
4197int KdViewCellsManager::PostProcess(const ObjectContainer &objects,
4198                                                                        const VssRayContainer &rays)
4199{
4200        return 0;
4201}
4202
4203
4204void KdViewCellsManager::ExportSingleViewCells(const ObjectContainer &objects,
4205                                                                                           const int maxViewCells,
4206                                                                                           const bool sortViewCells,
4207                                                                                           const bool exportPvs,
4208                                                                                           const bool exportRays,
4209                                                                                           const int maxRays,
4210                                                                                           const string prefix,
4211                                                                                           VssRayContainer *visRays)
4212{
4213        // TODO
4214}
4215
4216
4217void KdViewCellsManager::Visualize(const ObjectContainer &objects,
4218                                                                   const VssRayContainer &sampleRays)
4219{
4220        if (!ViewCellsConstructed())
4221                return;
4222
4223        // using view cells instead of the kd PVS of objects
4224        const bool useViewCells = true;
4225        bool exportRays = false;
4226
4227        int limit = min(mVisualizationSamples, (int)sampleRays.size());
4228        const int pvsOut = min((int)objects.size(), 10);
4229        VssRayContainer *rays = new VssRayContainer[pvsOut];
4230
4231        if (useViewCells)
4232        {
4233                const int leafOut = 10;
4234
4235                ViewCell::NewMail();
4236
4237                //-- some rays for output
4238                const int raysOut = min((int)sampleRays.size(), mVisualizationSamples);
4239                Debug << "visualization using " << raysOut << " samples" << endl;
4240
4241                //-- some random view cells and rays for output
4242                vector<KdLeaf *> kdLeaves;
4243
4244                for (int i = 0; i < leafOut; ++ i)
4245                        kdLeaves.push_back(dynamic_cast<KdLeaf *>(mKdTree->GetRandomLeaf()));
4246
4247                for (int i = 0; i < kdLeaves.size(); ++ i)
4248                {
4249                        KdLeaf *leaf = kdLeaves[i];
4250                        RayContainer vcRays;
4251
4252                        cout << "creating output for view cell " << i << " ... ";
4253#if 0
4254                        // check whether we can add the current ray to the output rays
4255                        for (int k = 0; k < raysOut; ++ k)
4256                        {
4257                                Ray *ray = sampleRays[k];
4258
4259                                for (int j = 0; j < (int)ray->bspIntersections.size(); ++ j)
4260                                {
4261                                        BspLeaf *leaf2 = ray->bspIntersections[j].mLeaf;
4262
4263                                        if (leaf->GetViewCell() == leaf2->GetViewCell())
4264                                        {
4265                                                vcRays.push_back(ray);
4266                                        }
4267                                }
4268                        }
4269#endif
4270                        Intersectable::NewMail();
4271
4272                        ViewCell *vc = leaf->mViewCell;
4273                        char str[64]; sprintf(str, "viewcell%04d.wrl", i);
4274
4275                        Exporter *exporter = Exporter::GetExporter(str);
4276                        exporter->SetFilled();
4277
4278                        exporter->SetWireframe();
4279                        //exporter->SetFilled();
4280
4281                        Material m;//= RandomMaterial();
4282                        m.mDiffuseColor = RgbColor(1, 1, 0);
4283                        exporter->SetForcedMaterial(m);
4284
4285                        AxisAlignedBox3 box = mKdTree->GetBox(leaf);
4286                        exporter->ExportBox(box);
4287
4288                        // export rays piercing this view cell
4289                        exporter->ExportRays(vcRays, 1000, RgbColor(0, 1, 0));
4290
4291                        m.mDiffuseColor = RgbColor(1, 0, 0);
4292                        exporter->SetForcedMaterial(m);
4293
4294                        // exporter->SetWireframe();
4295                        exporter->SetFilled();
4296
4297                        ObjectPvsIterator pit = vc->GetPvs().GetIterator();
4298                       
4299                        while (pit.HasMoreEntries())
4300                        {               
4301                                ObjectPvsEntry entry = pit.Next();
4302                               
4303                                //-- output PVS of view cell
4304                                Intersectable *intersect = entry.mObject;
4305                                if (!intersect->Mailed())
4306                                {
4307                                        exporter->ExportIntersectable(intersect);
4308                                        intersect->Mail();
4309                                }
4310                        }
4311
4312                        DEL_PTR(exporter);
4313                        cout << "finished" << endl;
4314                }
4315
4316                DEL_PTR(rays);
4317        }
4318        else // using kd PVS of objects
4319        {
4320                for (int i = 0; i < limit; ++ i)
4321                {
4322                        VssRay *ray = sampleRays[i];
4323
4324                        // check whether we can add this to the rays
4325                        for (int j = 0; j < pvsOut; j++)
4326                        {
4327                                if (objects[j] == ray->mTerminationObject)
4328                                {
4329                                        rays[j].push_back(ray);
4330                                }
4331                        }
4332                }
4333
4334                if (exportRays)
4335                {
4336                        Exporter *exporter = NULL;
4337                        exporter = Exporter::GetExporter("sample-rays.x3d");
4338                        exporter->SetWireframe();
4339                        exporter->ExportKdTree(*mKdTree);
4340
4341                        for (int i = 0; i < pvsOut; i++)
4342                                exporter->ExportRays(rays[i], RgbColor(1, 0, 0));
4343
4344                        exporter->SetFilled();
4345                        delete exporter;
4346                }
4347
4348                for (int k=0; k < pvsOut; k++)
4349                {
4350                        Intersectable *object = objects[k];
4351                        char str[64]; sprintf(str, "viewcell%04d.wrl", k);
4352
4353                        Exporter *exporter = Exporter::GetExporter(str);
4354                        exporter->SetWireframe();
4355
4356                        // matt: we don't have no kd pvs
4357#if 0
4358                        KdPvsMap::iterator kit = object->mKdPvs.mEntries.begin();
4359                        Intersectable::NewMail();
4360
4361                        // avoid adding the object to the list
4362                        object->Mail();
4363                        ObjectContainer visibleObjects;
4364
4365                        for (; kit != object->mKdPvs.mEntries.end(); i++)
4366                        {
4367                                KdNode *node = (*kit).first;
4368                                exporter->ExportBox(mKdTree->GetBox(node));
4369
4370                                mKdTree->CollectObjects(node, visibleObjects);
4371                        }
4372
4373                        exporter->ExportRays(rays[k],  RgbColor(0, 1, 0));
4374                        exporter->SetFilled();
4375
4376                        for (int j = 0; j < visibleObjects.size(); j++)
4377                                exporter->ExportIntersectable(visibleObjects[j]);
4378
4379                        Material m;
4380                        m.mDiffuseColor = RgbColor(1, 0, 0);
4381                        exporter->SetForcedMaterial(m);
4382                        exporter->ExportIntersectable(object);
4383#endif
4384                        delete exporter;
4385                }
4386        }
4387}
4388
4389
4390ViewCell *KdViewCellsManager::GenerateViewCell(Mesh *mesh) const
4391{
4392        return new KdViewCell(mesh);
4393}
4394
4395
4396void KdViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
4397                                                                                                ViewCell *vc,
4398                                                                                                const AxisAlignedBox3 *sceneBox,
4399                                                                                                const AxisAlignedPlane *clipPlane
4400                                                                                                ) const
4401{
4402        ViewCellContainer leaves;
4403        mViewCellsTree->CollectLeaves(vc, leaves);
4404        ViewCellContainer::const_iterator it, it_end = leaves.end();
4405
4406        for (it = leaves.begin(); it != it_end; ++ it)
4407        {
4408                KdViewCell *kdVc = dynamic_cast<KdViewCell *>(*it);
4409                exporter->ExportBox(mKdTree->GetBox(kdVc->mLeaves[0]));
4410        }
4411}
4412
4413
4414int KdViewCellsManager::GetType() const
4415{
4416        return ViewCellsManager::KD;
4417}
4418
4419
4420
4421KdNode *KdViewCellsManager::GetNodeForPvs(KdLeaf *leaf)
4422{
4423        KdNode *node = leaf;
4424
4425        while (node->mParent && node->mDepth > mKdPvsDepth)
4426                node = node->mParent;
4427
4428        return node;
4429}
4430
4431int KdViewCellsManager::CastLineSegment(const Vector3 &origin,
4432                                                                                const Vector3 &termination,
4433                                                                                ViewCellContainer &viewcells)
4434{
4435        return mKdTree->CastLineSegment(origin, termination, viewcells);
4436}
4437
4438
4439bool KdViewCellsManager::LineSegmentIntersects(const Vector3 &origin,
4440                                                                                           const Vector3 &termination,
4441                                                                                           ViewCell *viewCell)
4442{
4443        return false;
4444}
4445
4446
4447void KdViewCellsManager::CreateMesh(ViewCell *vc)
4448{
4449        // TODO
4450}
4451
4452
4453
4454void KdViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays,
4455                                                                                                vector<MergeCandidate> &candidates)
4456{
4457        // TODO
4458}
4459
4460
4461
4462/**************************************************************************/
4463/*                   VspBspViewCellsManager implementation                */
4464/**************************************************************************/
4465
4466
4467VspBspViewCellsManager::VspBspViewCellsManager(ViewCellsTree *vcTree, VspBspTree *vspBspTree):
4468ViewCellsManager(vcTree), mVspBspTree(vspBspTree)
4469{
4470        Environment::GetSingleton()->GetIntValue("VspBspTree.Construction.samples", mInitialSamples);
4471        mVspBspTree->SetViewCellsManager(this);
4472        mVspBspTree->mViewCellsTree = mViewCellsTree;
4473}
4474
4475
4476VspBspViewCellsManager::~VspBspViewCellsManager()
4477{
4478}
4479
4480
4481float VspBspViewCellsManager::GetProbability(ViewCell *viewCell)
4482{
4483        if (0 && mVspBspTree->mUseAreaForPvs)
4484                return GetArea(viewCell) / GetAccVcArea();
4485        else
4486                return GetVolume(viewCell) / mViewSpaceBox.GetVolume();
4487}
4488
4489
4490void VspBspViewCellsManager::CollectViewCells()
4491{
4492        // view cells tree constructed?
4493        if (!ViewCellsTreeConstructed())
4494        {
4495                mVspBspTree->CollectViewCells(mViewCells, false);
4496        }
4497        else
4498        {       
4499                // we can use the view cells tree hierarchy to get the right set
4500                mViewCellsTree->CollectBestViewCellSet(mViewCells, mNumActiveViewCells);
4501        }
4502}
4503
4504
4505void VspBspViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays,
4506                                                                                                        vector<MergeCandidate> &candidates)
4507{       
4508        cout << "collecting merge candidates ... " << endl;
4509
4510        if (mUseRaysForMerge)
4511        {
4512                mVspBspTree->CollectMergeCandidates(rays, candidates);
4513        }
4514        else
4515        {
4516                vector<BspLeaf *> leaves;
4517                mVspBspTree->CollectLeaves(leaves);
4518       
4519                mVspBspTree->CollectMergeCandidates(leaves, candidates);
4520        }
4521
4522        cout << "fininshed collecting candidates" << endl;
4523}
4524
4525
4526bool VspBspViewCellsManager::ViewCellsConstructed() const
4527{
4528        return mVspBspTree->GetRoot() != NULL;
4529}
4530
4531
4532ViewCell *VspBspViewCellsManager::GenerateViewCell(Mesh *mesh) const
4533{
4534        return new BspViewCell(mesh);
4535}
4536
4537
4538int VspBspViewCellsManager::ConstructSubdivision(const ObjectContainer &objects,
4539                                                                                                 const VssRayContainer &rays)
4540{
4541        mMaxPvsSize = (int)(mMaxPvsRatio * (float)objects.size());
4542
4543        // if view cells were already constructed
4544        if (ViewCellsConstructed())
4545        {
4546                return 0;
4547        }
4548
4549        int sampleContributions = 0;
4550        VssRayContainer sampleRays;
4551
4552        const int limit = min(mInitialSamples, (int)rays.size());
4553
4554        Debug << "samples used for vsp bsp subdivision: " << mInitialSamples
4555                  << ", actual rays: " << (int)rays.size() << endl;
4556
4557        VssRayContainer savedRays;
4558
4559        if (SAMPLE_AFTER_SUBDIVISION)
4560        {
4561                VssRayContainer constructionRays;
4562               
4563                GetRaySets(rays, mInitialSamples, constructionRays, &savedRays);
4564
4565                Debug << "rays used for initial construction: " << (int)constructionRays.size() << endl;
4566                Debug << "rays saved for later use: " << (int)savedRays.size() << endl;
4567       
4568                mVspBspTree->Construct(constructionRays, &mViewSpaceBox);
4569        }
4570        else
4571        {
4572                Debug << "rays used for initial construction: " << (int)rays.size() << endl;
4573                mVspBspTree->Construct(rays, &mViewSpaceBox);
4574        }
4575
4576        // collapse invalid regions
4577        cout << "collapsing invalid tree regions ... ";
4578        long startTime = GetTime();
4579
4580        const int collapsedLeaves = mVspBspTree->CollapseTree();
4581        Debug << "collapsed in " << TimeDiff(startTime, GetTime()) * 1e-3
4582                  << " seconds" << endl;
4583
4584    cout << "finished" << endl;
4585
4586        /////////////////
4587        //-- stats after construction
4588
4589        Debug << mVspBspTree->GetStatistics() << endl;
4590
4591        ResetViewCells();
4592        Debug << "\nView cells after construction:\n" << mCurrentViewCellsStats << endl;
4593
4594
4595        //////////////////////
4596        //-- recast the rest of the rays
4597
4598        startTime = GetTime();
4599
4600        cout << "Computing remaining ray contributions ... ";
4601
4602        if (SAMPLE_AFTER_SUBDIVISION)
4603                ComputeSampleContributions(savedRays, true, false);
4604
4605        cout << "finished" << endl;
4606
4607        Debug << "Computed remaining ray contribution in " << TimeDiff(startTime, GetTime()) * 1e-3
4608                  << " secs" << endl;
4609
4610        cout << "construction finished" << endl;
4611
4612        if (0)
4613        {       ////////
4614                //-- real meshes are contructed at this stage
4615
4616                cout << "finalizing view cells ... ";
4617                FinalizeViewCells(true);
4618                cout << "finished" << endl;
4619        }
4620
4621        return sampleContributions;
4622}
4623
4624
4625void VspBspViewCellsManager::MergeViewCells(const VssRayContainer &rays,
4626                                                                                        const ObjectContainer &objects)
4627{
4628    int vcSize = 0;
4629        int pvsSize = 0;
4630
4631        //-- merge view cells
4632        cout << "starting merge using " << mPostProcessSamples << " samples ... " << endl;
4633        long startTime = GetTime();
4634
4635
4636        if (mMergeViewCells)
4637        {
4638                // TODO: should be done BEFORE the ray casting
4639                // compute tree by merging the nodes based on cost heuristics
4640                mViewCellsTree->ConstructMergeTree(rays, objects);
4641        }
4642        else
4643        {
4644                // compute tree by merging the nodes of the spatial hierarchy
4645                ViewCell *root = ConstructSpatialMergeTree(mVspBspTree->GetRoot());
4646                mViewCellsTree->SetRoot(root);
4647
4648                // compute pvs
4649                ObjectPvs pvs;
4650                UpdatePvsForEvaluation(root, pvs);
4651        }
4652
4653        if (1)
4654        {
4655                char mstats[100];
4656                ObjectPvs pvs;
4657
4658                Environment::GetSingleton()->GetStringValue("ViewCells.mergeStats", mstats);
4659                mViewCellsTree->ExportStats(mstats);
4660        }
4661
4662        cout << "merged view cells in "
4663                 << TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl;
4664
4665        Debug << "Postprocessing: Merged view cells in "
4666                  << TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl << endl;
4667       
4668
4669        //////////////////
4670        //-- stats and visualizations
4671
4672        int savedColorCode = mColorCode;
4673       
4674        // get currently active view cell set
4675        ResetViewCells();
4676        Debug << "\nView cells after merge:\n" << mCurrentViewCellsStats << endl;
4677       
4678        if (mShowVisualization) // export merged view cells
4679        {
4680                mColorCode = 0;
4681                Exporter *exporter = Exporter::GetExporter("merged_view_cells.wrl");
4682               
4683                cout << "exporting view cells after merge ... ";
4684
4685                if (exporter)
4686                {
4687                        if (0)
4688                                exporter->SetWireframe();
4689                        else
4690                                exporter->SetFilled();
4691
4692                        ExportViewCellsForViz(exporter, NULL, mColorCode, GetClipPlane());
4693
4694                        if (mExportGeometry)
4695                        {
4696                                Material m;
4697                                m.mDiffuseColor = RgbColor(0, 1, 0);
4698                                exporter->SetForcedMaterial(m);
4699                                exporter->SetFilled();
4700
4701                                exporter->ExportGeometry(objects);
4702                        }
4703
4704                        delete exporter;
4705                }
4706                cout << "finished" << endl;
4707        }
4708
4709        if (mShowVisualization)
4710        {
4711                // use pvs size for color coding
4712                mColorCode = 1;
4713                Exporter *exporter = Exporter::GetExporter("merged_view_cells_pvs.wrl");
4714
4715                cout << "exporting view cells after merge (pvs size) ... ";     
4716
4717                if (exporter)
4718                {
4719                        exporter->SetFilled();
4720
4721                        ExportViewCellsForViz(exporter, NULL, mColorCode, GetClipPlane());
4722
4723                        if (mExportGeometry)
4724                        {
4725                                Material m;
4726                                m.mDiffuseColor = RgbColor(0, 1, 0);
4727                                exporter->SetForcedMaterial(m);
4728                                exporter->SetFilled();
4729
4730                                exporter->ExportGeometry(objects);
4731                        }
4732
4733                        delete exporter;
4734                }
4735                cout << "finished" << endl;
4736        }
4737
4738        mColorCode = savedColorCode;
4739}
4740
4741
4742void VspBspViewCellsManager::RefineViewCells(const VssRayContainer &rays,
4743                                                                                         const ObjectContainer &objects)
4744{
4745        mRenderer->RenderScene();
4746
4747        SimulationStatistics ss;
4748        dynamic_cast<RenderSimulator *>(mRenderer)->GetStatistics(ss);
4749    Debug << "render time before refine\n\n" << ss << endl;
4750
4751        const long startTime = GetTime();
4752        cout << "Refining the merged view cells ... ";
4753
4754        // refining the merged view cells
4755        const int refined = mViewCellsTree->RefineViewCells(rays, objects);
4756
4757        //-- stats and visualizations
4758        cout << "finished" << endl;
4759        cout << "refined " << refined << " view cells in "
4760                 << TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl;
4761
4762        Debug << "Postprocessing: refined " << refined << " view cells in "
4763                  << TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl << endl;
4764}
4765
4766
4767int VspBspViewCellsManager::PostProcess(const ObjectContainer &objects,
4768                                                                                const VssRayContainer &rays)
4769{
4770        if (!ViewCellsConstructed())
4771        {
4772                Debug << "postprocess error: no view cells constructed" << endl;
4773                return 0;
4774        }
4775
4776        // view cells already finished before post processing step
4777        // (i.e. because they were loaded)
4778        if (mViewCellsFinished)
4779        {
4780                FinalizeViewCells(true);
4781                EvaluateViewCellsStats();
4782
4783                return 0;
4784        }
4785
4786        // check if new view cells turned invalid
4787        int minPvs, maxPvs;
4788
4789        if (0)
4790        {
4791                minPvs = mMinPvsSize;
4792                maxPvs = mMaxPvsSize;
4793        }
4794        else
4795        {
4796                // problem matt: why did I start here from zero?
4797                minPvs = 0;
4798                maxPvs = mMaxPvsSize;
4799        }
4800
4801        Debug << "setting validity, min: " << minPvs << " max: " << maxPvs << endl;
4802        cout << "setting validity, min: " << minPvs << " max: " << maxPvs << endl;
4803       
4804        SetValidity(minPvs, maxPvs);
4805
4806        // update valid view space according to valid view cells
4807        if (0) mVspBspTree->ValidateTree();
4808
4809        // area has to be recomputed
4810        mTotalAreaValid = false;
4811        VssRayContainer postProcessRays;
4812        GetRaySets(rays, mPostProcessSamples, postProcessRays);
4813
4814        Debug << "post processing using " << (int)postProcessRays.size() << " samples" << endl;
4815
4816        //////////
4817        //-- merge neighbouring view cells
4818        MergeViewCells(postProcessRays, objects);
4819       
4820        // refines the merged view cells
4821        if (0) RefineViewCells(postProcessRays, objects);
4822
4823
4824        ///////////
4825        //-- render simulation after merge + refine
4826
4827        cout << "\nview cells partition render time before compress" << endl << endl;;
4828        dynamic_cast<RenderSimulator *>(mRenderer)->RenderScene();
4829        SimulationStatistics ss;
4830        dynamic_cast<RenderSimulator *>(mRenderer)->GetStatistics(ss);
4831        cout << ss << endl;
4832       
4833        if (0) CompressViewCells();
4834       
4835        // collapse sibling leaves that share the same view cell
4836        if (0) mVspBspTree->CollapseTree();
4837
4838        // recompute view cell list and statistics
4839        ResetViewCells();
4840
4841        // compute final meshes and volume / area
4842        if (1) FinalizeViewCells(true);
4843
4844        return 0;
4845}
4846
4847
4848int VspBspViewCellsManager::GetType() const
4849{
4850        return VSP_BSP;
4851}
4852
4853
4854ViewCell *VspBspViewCellsManager::ConstructSpatialMergeTree(BspNode *root)
4855{
4856        // terminate recursion
4857        if (root->IsLeaf())
4858        {
4859                BspLeaf *leaf = dynamic_cast<BspLeaf *>(root);
4860                leaf->GetViewCell()->SetMergeCost(0.0f);
4861                return leaf->GetViewCell();
4862        }
4863       
4864       
4865        BspInterior *interior = dynamic_cast<BspInterior *>(root);
4866        ViewCellInterior *viewCellInterior = new ViewCellInterior();
4867               
4868        // evaluate merge cost for priority traversal
4869        float mergeCost = 1.0f / (float)root->mTimeStamp;
4870        viewCellInterior->SetMergeCost(mergeCost);
4871
4872        float volume = 0;
4873       
4874        BspNode *front = interior->GetFront();
4875        BspNode *back = interior->GetBack();
4876
4877
4878        ObjectPvs frontPvs, backPvs;
4879
4880        //-- recursivly compute child hierarchies
4881        ViewCell *backVc = ConstructSpatialMergeTree(back);
4882        ViewCell *frontVc = ConstructSpatialMergeTree(front);
4883
4884
4885        viewCellInterior->SetupChildLink(backVc);
4886        viewCellInterior->SetupChildLink(frontVc);
4887
4888        volume += backVc->GetVolume();
4889        volume += frontVc->GetVolume();
4890
4891        viewCellInterior->SetVolume(volume);
4892
4893        return viewCellInterior;
4894}
4895
4896
4897bool VspBspViewCellsManager::GetViewPoint(Vector3 &viewPoint) const
4898{
4899        if (!ViewCellsConstructed())
4900                return ViewCellsManager::GetViewPoint(viewPoint);
4901
4902        // TODO: set reasonable limit
4903        const int limit = 20;
4904
4905        for (int i = 0; i < limit; ++ i)
4906        {
4907                viewPoint = mViewSpaceBox.GetRandomPoint();
4908                if (mVspBspTree->ViewPointValid(viewPoint))
4909                {
4910                        return true;
4911                }
4912        }
4913
4914        Debug << "failed to find valid view point, taking " << viewPoint << endl;
4915        return false;
4916}
4917
4918
4919bool VspBspViewCellsManager::ViewPointValid(const Vector3 &viewPoint) const
4920{
4921        // $$JB -> implemented in viewcellsmanager (slower, but allows dynamic
4922        // validy update in preprocessor for all managers)
4923        return ViewCellsManager::ViewPointValid(viewPoint);
4924
4925        //      return mViewSpaceBox.IsInside(viewPoint) &&
4926        //                 mVspBspTree->ViewPointValid(viewPoint);
4927}
4928
4929
4930void VspBspViewCellsManager::Visualize(const ObjectContainer &objects,
4931                                                                           const VssRayContainer &sampleRays)
4932{
4933        if (!ViewCellsConstructed())
4934                return;
4935
4936        VssRayContainer visRays;
4937        GetRaySets(sampleRays, mVisualizationSamples, visRays);
4938       
4939        if (1)
4940        {       
4941                //////////////////
4942                //-- export final view cell partition
4943
4944                Exporter *exporter = Exporter::GetExporter("final_view_cells.wrl");
4945               
4946                if (exporter)
4947                {
4948                        cout << "exporting view cells after post process ... ";
4949                        if (0)
4950                        {       // export view space box
4951                                exporter->SetWireframe();
4952                                exporter->ExportBox(mViewSpaceBox);
4953                                exporter->SetFilled();
4954                        }
4955
4956                        Material m;
4957                        m.mDiffuseColor.r = 0.0f;
4958                        m.mDiffuseColor.g = 0.5f;
4959                        m.mDiffuseColor.b = 0.5f;
4960
4961            exporter->SetForcedMaterial(m);
4962
4963                        if (1 && mExportGeometry)
4964                        {
4965                                exporter->ExportGeometry(objects);
4966                        }
4967
4968                        if (0 && mExportRays)
4969                        {
4970                                exporter->ExportRays(visRays, RgbColor(1, 0, 0));
4971                        }
4972                        ExportViewCellsForViz(exporter, NULL, mColorCode, GetClipPlane());
4973
4974                        delete exporter;
4975                        cout << "finished" << endl;
4976                }
4977        }
4978
4979        ////////////////
4980        //-- visualization of the BSP splits
4981
4982        bool exportSplits = false;
4983        Environment::GetSingleton()->GetBoolValue("VspBspTree.Visualization.exportSplits", exportSplits);
4984
4985        if (exportSplits)
4986        {
4987                cout << "exporting splits ... ";
4988                ExportSplits(objects, visRays);
4989                cout << "finished" << endl;
4990        }
4991
4992        ////////
4993        //-- export single view cells
4994       
4995        int leafOut;
4996        Environment::GetSingleton()->GetIntValue("ViewCells.Visualization.maxOutput", leafOut);
4997        const int raysOut = 100;
4998       
4999        ExportSingleViewCells(objects, leafOut, false, true, false, raysOut, "");
5000}
5001
5002
5003void VspBspViewCellsManager::ExportSplits(const ObjectContainer &objects,
5004                                                                                  const VssRayContainer &rays)
5005{
5006        Exporter *exporter = Exporter::GetExporter("bsp_splits.x3d");
5007
5008        if (exporter)
5009        {
5010                Material m;
5011                m.mDiffuseColor = RgbColor(1, 0, 0);
5012                exporter->SetForcedMaterial(m);
5013                exporter->SetWireframe();
5014
5015                exporter->ExportBspSplits(*mVspBspTree, true);
5016
5017                // take forced material, else big scenes cannot be viewed
5018                m.mDiffuseColor = RgbColor(0, 1, 0);
5019                exporter->SetForcedMaterial(m);
5020                exporter->SetFilled();
5021
5022                exporter->ResetForcedMaterial();
5023
5024                // export rays
5025                if (mExportRays)
5026                {
5027                        exporter->ExportRays(rays, RgbColor(1, 1, 0));
5028                }
5029
5030                if (mExportGeometry)
5031                {
5032                        exporter->ExportGeometry(objects);
5033                }
5034                delete exporter;
5035        }
5036}
5037
5038
5039void VspBspViewCellsManager::ExportSingleViewCells(const ObjectContainer &objects,
5040                                                                                                   const int maxViewCells,
5041                                                                                                   const bool sortViewCells,
5042                                                                                                   const bool exportPvs,
5043                                                                                                   const bool exportRays,
5044                                                                                                   const int maxRays,
5045                                                                                                   const string prefix,
5046                                                                                                   VssRayContainer *visRays)
5047{       
5048        if (sortViewCells)
5049        {
5050                // sort view cells to visualize the largest view cells
5051                sort(mViewCells.begin(), mViewCells.end(), ViewCell::LargerRenderCost);
5052        }
5053
5054        //////////
5055        //-- some view cells for output
5056
5057        ViewCell::NewMail();
5058        const int limit = min(maxViewCells, (int)mViewCells.size());
5059       
5060        for (int i = 0; i < limit; ++ i)
5061        {
5062                cout << "creating output for view cell " << i << " ... ";
5063
5064                ViewCell *vc = sortViewCells ? // largest view cell pvs first?
5065                        mViewCells[(int)RandomValue(0, (float)mViewCells.size() - 0.5f)] : mViewCells[i];
5066
5067                if (vc->Mailed() || vc->GetId() == OUT_OF_BOUNDS_ID)
5068                        continue;
5069
5070                vc->Mail();
5071
5072                ObjectPvs pvs;
5073                mViewCellsTree->GetPvs(vc, pvs);
5074
5075                char s[64]; sprintf(s, "%sviewcell%04d.wrl", prefix.c_str(), i);
5076                Exporter *exporter = Exporter::GetExporter(s);
5077               
5078                const float pvsCost = mViewCellsTree->GetPvsCost(vc);
5079                cout << "view cell " << vc->GetId() << ": pvs cost=" << pvsCost << endl;
5080
5081                if (exportRays)
5082                {
5083                        ////////////
5084                        //-- export rays piercing this view cell
5085
5086                        // take rays stored with the view cells during subdivision
5087                        VssRayContainer vcRays;
5088            VssRayContainer collectRays;
5089
5090                        // collect initial view cells
5091                        ViewCellContainer leaves;
5092                        mViewCellsTree->CollectLeaves(vc, leaves);
5093
5094                        ViewCellContainer::const_iterator vit, vit_end = leaves.end();
5095                for (vit = leaves.begin(); vit != vit_end; ++ vit)
5096                        {       
5097                                BspLeaf *vcLeaf = dynamic_cast<BspViewCell *>(*vit)->mLeaves[0];
5098                                VssRayContainer::const_iterator rit, rit_end = vcLeaf->mVssRays.end();
5099
5100                                for (rit = vcLeaf->mVssRays.begin(); rit != rit_end; ++ rit)
5101                                {
5102                                        collectRays.push_back(*rit);
5103                                }
5104                        }
5105
5106                        const int raysOut = min((int)collectRays.size(), maxRays);
5107               
5108                        // prepare some rays for output
5109                        VssRayContainer::const_iterator rit, rit_end = collectRays.end();
5110                        for (rit = collectRays.begin(); rit != rit_end; ++ rit)
5111                        {
5112                                const float p = RandomValue(0.0f, (float)collectRays.size());
5113                       
5114                                if (p < raysOut)
5115                                {
5116                                        vcRays.push_back(*rit);
5117                                }
5118                        }
5119
5120                        exporter->ExportRays(vcRays, RgbColor(1, 1, 1));
5121                }
5122               
5123                ////////////////
5124                //-- export view cell geometry
5125
5126                exporter->SetWireframe();
5127
5128                Material m;//= RandomMaterial();
5129                m.mDiffuseColor = RgbColor(0, 1, 0);
5130                exporter->SetForcedMaterial(m);
5131
5132                ExportViewCellGeometry(exporter, vc, NULL, NULL);
5133                exporter->SetFilled();
5134
5135                if (exportPvs)
5136                {
5137                        Intersectable::NewMail();
5138
5139                        ObjectPvsIterator pit = pvs.GetIterator();
5140
5141                        cout << endl;
5142
5143                        // output PVS of view cell
5144                        while (pit.HasMoreEntries())
5145                        {
5146                                ObjectPvsEntry entry = pit.Next();             
5147                                Intersectable *intersect = entry.mObject;
5148                               
5149                                if (!intersect->Mailed())
5150                                {
5151                                        intersect->Mail();
5152
5153                                        m = RandomMaterial();
5154                                        exporter->SetForcedMaterial(m);
5155                                        exporter->ExportIntersectable(intersect);
5156                                }
5157                        }
5158                        cout << endl;
5159                }
5160               
5161                DEL_PTR(exporter);
5162                cout << "finished" << endl;
5163        }
5164}
5165
5166
5167void VspBspViewCellsManager::TestFilter(const ObjectContainer &objects)
5168{
5169        Exporter *exporter = Exporter::GetExporter("filter.x3d");
5170
5171        Vector3 bsize = mViewSpaceBox.Size();
5172        const Vector3 viewPoint(mViewSpaceBox.Center());
5173        float w = Magnitude(mViewSpaceBox.Size()) * mFilterWidth;
5174        const Vector3 width = Vector3(w);
5175       
5176        PrVs testPrVs;
5177       
5178        if (exporter)
5179        {
5180                ViewCellContainer viewCells;
5181       
5182        const AxisAlignedBox3 tbox = GetFilterBBox(viewPoint, mFilterWidth);
5183
5184                GetPrVS(viewPoint, testPrVs, GetFilterWidth());
5185
5186                exporter->SetWireframe();
5187
5188                exporter->SetForcedMaterial(RgbColor(1,1,1));
5189                exporter->ExportBox(tbox);
5190               
5191                exporter->SetFilled();
5192
5193                exporter->SetForcedMaterial(RgbColor(0,1,0));
5194                ExportViewCellGeometry(exporter, GetViewCell(viewPoint), NULL, NULL);
5195
5196                //exporter->ResetForcedMaterial();
5197                exporter->SetForcedMaterial(RgbColor(0,0,1));
5198                ExportViewCellGeometry(exporter, testPrVs.mViewCell, NULL, NULL);
5199
5200        exporter->SetForcedMaterial(RgbColor(1,0,0));
5201                exporter->ExportGeometry(objects);
5202
5203                delete exporter;
5204        }
5205}
5206
5207
5208int VspBspViewCellsManager::ComputeBoxIntersections(const AxisAlignedBox3 &box,
5209                                                                                                        ViewCellContainer &viewCells) const
5210{
5211        return mVspBspTree->ComputeBoxIntersections(box, viewCells);
5212}
5213
5214
5215int VspBspViewCellsManager::CastLineSegment(const Vector3 &origin,
5216                                                                                        const Vector3 &termination,
5217                                                                                        ViewCellContainer &viewcells)
5218{
5219        return mVspBspTree->CastLineSegment(origin, termination, viewcells);
5220}
5221
5222
5223bool VspBspViewCellsManager::LineSegmentIntersects(const Vector3 &origin,
5224                                                                                                   const Vector3 &termination,
5225                                                                                                   ViewCell *viewCell)
5226{
5227        return false;
5228}
5229
5230
5231void VspBspViewCellsManager::VisualizeWithFromPointQueries()
5232{
5233        int numSamples;
5234       
5235        Environment::GetSingleton()->GetIntValue("RenderSampler.samples", numSamples);
5236        cout << "samples" << numSamples << endl;
5237
5238        vector<RenderCostSample> samples;
5239 
5240        if (!mPreprocessor->GetRenderer())
5241                return;
5242
5243        //start the view point queries
5244        long startTime = GetTime();
5245        cout << "starting sampling of render cost ... ";
5246       
5247        mPreprocessor->GetRenderer()->SampleRenderCost(numSamples, samples, true);
5248
5249        cout << "finished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
5250
5251
5252        // for each sample:
5253        //    find view cells associated with the samples
5254        //    store the sample pvs with the pvs associated with the view cell
5255        //
5256        // for each view cell:
5257        //    compute difference point sampled pvs - view cell pvs
5258        //    export geometry with color coded pvs difference
5259       
5260    std::map<ViewCell *, ObjectPvs> sampleMap;
5261
5262        vector<RenderCostSample>::const_iterator rit, rit_end = samples.end();
5263
5264        for (rit = samples.begin(); rit != rit_end; ++ rit)
5265        {
5266                RenderCostSample sample = *rit;
5267       
5268                ViewCell *vc = GetViewCell(sample.mPosition);
5269
5270                std::map<ViewCell *, ObjectPvs>::iterator it = sampleMap.find(vc);
5271
5272                if (it == sampleMap.end())
5273                {
5274                        sampleMap[vc] = sample.mPvs;
5275                }
5276                else
5277                {
5278                        (*it).second.MergeInPlace(sample.mPvs);
5279                }
5280        }
5281
5282        // visualize the view cells
5283        std::map<ViewCell *, ObjectPvs>::const_iterator vit, vit_end = sampleMap.end();
5284
5285        Material m;//= RandomMaterial();
5286
5287        for (vit = sampleMap.begin(); vit != vit_end; ++ vit)
5288        {
5289                ViewCell *vc = (*vit).first;
5290               
5291                const int pvsVc = mViewCellsTree->GetPvsEntries(vc);
5292                const int pvsPtSamples = (*vit).second.GetSize();
5293
5294        m.mDiffuseColor.r = (float) (pvsVc - pvsPtSamples);
5295                m.mDiffuseColor.b = 1.0f;
5296                //exporter->SetForcedMaterial(m);
5297                //ExportViewCellGeometry(exporter, vc, mClipPlaneForViz);
5298
5299                /*      // counting the pvss
5300                for (rit = samples.begin(); rit != rit_end; ++ rit)
5301                {
5302                        RenderCostSample sample = *rit;
5303                        ViewCell *vc = GetViewCell(sample.mPosition);
5304
5305                        AxisAlignedBox3 box(sample.mPosition - Vector3(1, 1, 1), sample.mPosition + Vector3(1, 1, 1));
5306                        Mesh *hMesh = CreateMeshFromBox(box);
5307
5308                        DEL_PTR(hMesh);
5309                }
5310                */
5311        }
5312}
5313
5314
5315void VspBspViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
5316                                                                                                        ViewCell *vc,
5317                                                                                                        const AxisAlignedBox3 *sceneBox,
5318                                                                                                        const AxisAlignedPlane *clipPlane
5319                                                                                                        ) const
5320{
5321        if (clipPlane)
5322        {
5323                const Plane3 plane = clipPlane->GetPlane();
5324
5325                ViewCellContainer leaves;
5326                mViewCellsTree->CollectLeaves(vc, leaves);
5327                ViewCellContainer::const_iterator it, it_end = leaves.end();
5328
5329                for (it = leaves.begin(); it != it_end; ++ it)
5330                {
5331                        BspNodeGeometry geom;
5332                        BspNodeGeometry front;
5333                        BspNodeGeometry back;
5334
5335                        mVspBspTree->ConstructGeometry(*it, geom);
5336
5337                        const float eps = 0.0001f;
5338                        const int cf = geom.Side(plane, eps);
5339
5340                        if (cf == -1)
5341                        {
5342                                exporter->ExportPolygons(geom.GetPolys());
5343                        }
5344                        else if (cf == 0)
5345                        {
5346                                geom.SplitGeometry(front,
5347                                                                   back,
5348                                                                   plane,
5349                                                                   mViewSpaceBox,
5350                                                                   eps);
5351
5352                                if (back.Valid())
5353                                {
5354                                        exporter->ExportPolygons(back.GetPolys());
5355                                }                       
5356                        }
5357                }
5358        }
5359        else
5360        {
5361                // export mesh if available
5362                // TODO: some bug here?
5363                if (1 && vc->GetMesh())
5364                {
5365                        exporter->ExportMesh(vc->GetMesh());
5366                }
5367                else
5368                {
5369                        BspNodeGeometry geom;
5370                        mVspBspTree->ConstructGeometry(vc, geom);
5371                        exporter->ExportPolygons(geom.GetPolys());
5372                }
5373        }
5374}
5375
5376
5377int VspBspViewCellsManager::GetMaxTreeDiff(ViewCell *vc) const
5378{
5379        ViewCellContainer leaves;
5380        mViewCellsTree->CollectLeaves(vc, leaves);
5381
5382        int maxDist = 0;
5383       
5384        // compute max height difference
5385        for (int i = 0; i < (int)leaves.size(); ++ i)
5386        {
5387                for (int j = 0; j < (int)leaves.size(); ++ j)
5388                {
5389                        BspLeaf *leaf = dynamic_cast<BspViewCell *>(leaves[i])->mLeaves[0];
5390
5391                        if (i != j)
5392                        {
5393                                BspLeaf *leaf2 =dynamic_cast<BspViewCell *>(leaves[j])->mLeaves[0];
5394                                const int dist = mVspBspTree->TreeDistance(leaf, leaf2);
5395                               
5396                                if (dist > maxDist)
5397                                        maxDist = dist;
5398                        }
5399                }
5400        }
5401
5402        return maxDist;
5403}
5404
5405
5406ViewCell *VspBspViewCellsManager::GetViewCell(const Vector3 &point, const bool active) const
5407{
5408        if (!ViewCellsConstructed())
5409                return NULL;
5410
5411        if (!mViewSpaceBox.IsInside(point))
5412          return NULL;
5413
5414        return mVspBspTree->GetViewCell(point, active);
5415}
5416
5417
5418void VspBspViewCellsManager::CreateMesh(ViewCell *vc)
5419{
5420        BspNodeGeometry geom;
5421        mVspBspTree->ConstructGeometry(vc, geom);
5422       
5423        Mesh *mesh = MeshManager::GetSingleton()->CreateResource();
5424        IncludeNodeGeomInMesh(geom, *mesh);
5425
5426        vc->SetMesh(mesh);
5427}
5428
5429
5430int VspBspViewCellsManager::CastBeam(Beam &beam)
5431{
5432        return mVspBspTree->CastBeam(beam);
5433}
5434
5435
5436void VspBspViewCellsManager::Finalize(ViewCell *viewCell,
5437                                                                          const bool createMesh)
5438{
5439        float area = 0;
5440        float volume = 0;
5441
5442        ViewCellContainer leaves;
5443        mViewCellsTree->CollectLeaves(viewCell, leaves);
5444
5445        ViewCellContainer::const_iterator it, it_end = leaves.end();
5446
5447    for (it = leaves.begin(); it != it_end; ++ it)
5448        {
5449                BspNodeGeometry geom;
5450                mVspBspTree->ConstructGeometry(*it, geom);
5451
5452                const float lVol = geom.GetVolume();
5453                const float lArea = geom.GetArea();
5454
5455                area += lArea;
5456                volume += lVol;
5457
5458                if (createMesh)
5459                        CreateMesh(*it);
5460        }
5461
5462        viewCell->SetVolume(volume);
5463        viewCell->SetArea(area);
5464}
5465
5466
5467void VspBspViewCellsManager::TestSubdivision()
5468{
5469        ViewCellContainer leaves;
5470        mViewCellsTree->CollectLeaves(mViewCellsTree->GetRoot(), leaves);
5471
5472        ViewCellContainer::const_iterator it, it_end = leaves.end();
5473
5474        const float vol = mViewSpaceBox.GetVolume();
5475        float subdivVol = 0;
5476        float newVol = 0;
5477
5478        for (it = leaves.begin(); it != it_end; ++ it)
5479        {
5480                BspNodeGeometry geom;
5481                mVspBspTree->ConstructGeometry(*it, geom);
5482
5483                const float lVol = geom.GetVolume();
5484               
5485                newVol += lVol;
5486                subdivVol += (*it)->GetVolume();
5487               
5488                float thres = 0.9f;
5489                if ((lVol < ((*it)->GetVolume() * thres)) || (lVol * thres > ((*it)->GetVolume())))
5490                        Debug << "warning: " << lVol << " " << (*it)->GetVolume() << endl;
5491        }
5492       
5493        Debug << "exact volume: " << vol << endl;
5494        Debug << "subdivision volume: " << subdivVol << endl;
5495        Debug << "new volume: " << newVol << endl;
5496}
5497
5498
5499void VspBspViewCellsManager::PrepareLoadedViewCells()
5500{
5501        // TODO: do I still need this here?
5502        if (0)
5503                mVspBspTree->RepairViewCellsLeafLists();
5504}
5505
5506
5507
5508/************************************************************************/
5509/*                 VspOspViewCellsManager implementation                */
5510/************************************************************************/
5511
5512
5513VspOspViewCellsManager::VspOspViewCellsManager(ViewCellsTree *vcTree,
5514                                                                                           const string &hierarchyType)
5515: ViewCellsManager(vcTree)
5516{
5517        Environment::GetSingleton()->GetIntValue("Hierarchy.Construction.samples", mInitialSamples);
5518
5519        Environment::GetSingleton()->GetBoolValue("ViewCells.compressObjects", mCompressObjects);
5520
5521        Debug << "compressing objects: " << mCompressObjects << endl;
5522        cout << "compressing objects: " << mCompressObjects << endl;
5523
5524        mHierarchyManager = CreateHierarchyManager(hierarchyType);
5525        mHierarchyManager->SetViewCellsManager(this);
5526        mHierarchyManager->SetViewCellsTree(mViewCellsTree);
5527}
5528
5529
5530VspOspViewCellsManager::VspOspViewCellsManager(ViewCellsTree *vcTree, HierarchyManager *hm)
5531: ViewCellsManager(vcTree), mHierarchyManager(hm)
5532{
5533        Environment::GetSingleton()->GetIntValue("Hierarchy.Construction.samples", mInitialSamples);
5534        Environment::GetSingleton()->GetBoolValue("ViewCells.compressObjects", mCompressObjects);
5535
5536        Debug << "compressing objects: " << mCompressObjects << endl;
5537        cout << "compressing objects: " << mCompressObjects << endl;
5538
5539        mHierarchyManager->SetViewCellsManager(this);
5540        mHierarchyManager->SetViewCellsTree(mViewCellsTree);
5541}
5542
5543
5544Intersectable *
5545VspOspViewCellsManager::GetIntersectable(const VssRay &ray, const bool isTermination) const
5546{
5547        if (mUseKdPvs)
5548        {
5549                return ViewCellsManager::GetIntersectable(ray, isTermination);
5550        }
5551        else
5552        {
5553                return mHierarchyManager->GetIntersectable(ray, isTermination);
5554        }
5555}
5556
5557
5558HierarchyManager *VspOspViewCellsManager::CreateHierarchyManager(const string &hierarchyType)
5559{
5560        HierarchyManager *hierarchyManager;
5561
5562        if (strcmp(hierarchyType.c_str(), "osp") == 0)
5563        {
5564                Debug << "hierarchy manager: osp" << endl;
5565                hierarchyManager = new HierarchyManager(HierarchyManager::KD_BASED_OBJ_SUBDIV);
5566        }
5567        else if (strcmp(hierarchyType.c_str(), "bvh") == 0)
5568        {
5569                Debug << "hierarchy manager: bvh" << endl;
5570                hierarchyManager = new HierarchyManager(HierarchyManager::BV_BASED_OBJ_SUBDIV);
5571        }
5572        else // only view space partition
5573        {
5574                Debug << "hierarchy manager: obj" << endl;
5575                hierarchyManager = new HierarchyManager(HierarchyManager::NO_OBJ_SUBDIV);
5576        }
5577
5578        return hierarchyManager;
5579}
5580
5581
5582VspOspViewCellsManager::~VspOspViewCellsManager()
5583{
5584        DEL_PTR(mHierarchyManager);
5585}
5586
5587
5588float VspOspViewCellsManager::GetProbability(ViewCell *viewCell)
5589{
5590        return GetVolume(viewCell) / mViewSpaceBox.GetVolume();
5591}
5592
5593
5594void VspOspViewCellsManager::CollectViewCells()
5595{
5596        // view cells tree constructed
5597        if (!ViewCellsTreeConstructed())
5598        {
5599                mHierarchyManager->GetVspTree()->CollectViewCells(mViewCells, false);
5600        }
5601        else
5602        {       // we can use the view cells tree hierarchy to get the right set
5603                mViewCellsTree->CollectBestViewCellSet(mViewCells, mNumActiveViewCells);
5604        }
5605}
5606
5607
5608bool VspOspViewCellsManager::ViewCellsConstructed() const
5609{
5610        return mHierarchyManager->GetVspTree()->GetRoot() != NULL;
5611}
5612
5613
5614ViewCell *VspOspViewCellsManager::GenerateViewCell(Mesh *mesh) const
5615{
5616        return new VspViewCell(mesh);
5617}
5618
5619
5620int VspOspViewCellsManager::ConstructSubdivision(const ObjectContainer &objects,
5621                                                                                                 const VssRayContainer &rays)
5622{
5623        mMaxPvsSize = (int)(mMaxPvsRatio * (float)objects.size());
5624
5625        // skip rest if view cells were already constructed
5626        if (ViewCellsConstructed())
5627                return 0;
5628
5629        int sampleContributions = 0;
5630        VssRayContainer sampleRays;
5631
5632        int limit = min (mInitialSamples, (int)rays.size());
5633
5634        VssRayContainer constructionRays;
5635        VssRayContainer savedRays;
5636
5637        Debug << "samples used for vsp bsp subdivision: " << mInitialSamples
5638                  << ", actual rays: " << (int)rays.size() << endl;
5639
5640        GetRaySets(rays, mInitialSamples, constructionRays, &savedRays);
5641
5642        Debug << "initial rays used for construction: " << (int)constructionRays.size() << endl;
5643        Debug << "saved rays: " << (int)savedRays.size() << endl;
5644
5645        mHierarchyManager->Construct(constructionRays, objects, &mViewSpaceBox);
5646
5647#if TEST_EVALUATION
5648        VssRayContainer::const_iterator tit, tit_end = constructionRays.end();
5649        for (tit = constructionRays.begin(); tit != tit_end; ++ tit)
5650        {
5651                storedRays.push_back(new VssRay(*(*tit)));
5652        }
5653#endif
5654
5655        /////////////////////////
5656        //-- print satistics for subdivision and view cells
5657
5658        Debug << endl << endl << *mHierarchyManager << endl;
5659
5660        ResetViewCells();
5661        Debug << "\nView cells after construction:\n" << mCurrentViewCellsStats << endl;
5662
5663        //////////////
5664        //-- recast rest of rays
5665       
5666        const long startTime = GetTime();
5667        cout << "Computing remaining ray contributions ... ";
5668
5669        if (SAMPLE_AFTER_SUBDIVISION)
5670                ComputeSampleContributions(savedRays, true, false);
5671
5672        Debug << "finished computing remaining ray contribution in " << TimeDiff(startTime, GetTime()) * 1e-3
5673                  << " secs" << endl;
5674
5675        if (0)
5676        {       
5677                // real meshes are constructed at this stage
5678                cout << "finalizing view cells ... ";
5679        FinalizeViewCells(true);
5680                cout << "finished" << endl;
5681        }
5682
5683        return sampleContributions;
5684}
5685
5686
5687int VspOspViewCellsManager::PostProcess(const ObjectContainer &objects,
5688                                                                                const VssRayContainer &rays)
5689{
5690        if (!ViewCellsConstructed())
5691        {
5692                Debug << "post process error: no view cells constructed" << endl;
5693                return 0;
5694        }
5695
5696        // if view cells were already constructed before post processing step
5697        // (e.g., because they were loaded), we are finished
5698        if (mViewCellsFinished)
5699        {
5700                FinalizeViewCells(true);
5701                EvaluateViewCellsStats();
5702
5703                return 0;
5704        }
5705
5706        // check if new view cells turned invalid
5707        int minPvs, maxPvs;
5708
5709        if (0)
5710        {
5711                minPvs = mMinPvsSize;
5712                maxPvs = mMaxPvsSize;
5713        }
5714        else
5715        {
5716                // problem matt: why did I start here from zero?
5717                minPvs = 0;
5718                maxPvs = mMaxPvsSize;
5719        }
5720
5721        Debug << "setting validity, min: " << minPvs << " max: " << maxPvs << endl;
5722        cout << "setting validity, min: " << minPvs << " max: " << maxPvs << endl;
5723       
5724        SetValidity(minPvs, maxPvs);
5725
5726       
5727        // area is not up to date, has to be recomputed
5728        mTotalAreaValid = false;
5729        VssRayContainer postProcessRays;
5730        GetRaySets(rays, mPostProcessSamples, postProcessRays);
5731
5732        Debug << "post processing using " << (int)postProcessRays.size() << " samples" << endl;
5733
5734
5735        // compute tree by merging the nodes of the spatial hierarchy
5736        ViewCell *root = ConstructSpatialMergeTree(mHierarchyManager->GetVspTree()->GetRoot());
5737        mViewCellsTree->SetRoot(root);
5738
5739        //////////////////////////
5740        //-- update pvs up to the root of the hierarchy
5741
5742        ObjectPvs pvs;
5743        UpdatePvsForEvaluation(root, pvs);
5744
5745
5746        //////////////////////
5747        //-- render simulation after merge + refine
5748
5749        cout << "\nview cells partition render time before compress" << endl << endl;
5750        dynamic_cast<RenderSimulator *>(mRenderer)->RenderScene();
5751        SimulationStatistics ss;
5752        dynamic_cast<RenderSimulator *>(mRenderer)->GetStatistics(ss);
5753        cout << ss << endl;
5754       
5755
5756        mHierarchyManager->CreateUniqueObjectIds();
5757
5758        ///////////
5759        //-- compression
5760
5761        if (0) CompressViewCells();
5762
5763        /////////////
5764        //-- some tasks still to do on the view cells:
5765        //-- Compute meshes from view cell geometry, evaluate volume and / or area
5766
5767        if (1) FinalizeViewCells(true);
5768
5769        return 0;
5770}
5771
5772
5773int VspOspViewCellsManager::GetType() const
5774{
5775        return VSP_OSP;
5776}
5777
5778
5779ViewCell *VspOspViewCellsManager::ConstructSpatialMergeTree(VspNode *root)
5780{
5781        // terminate recursion
5782        if (root->IsLeaf())
5783        {
5784                VspLeaf *leaf = dynamic_cast<VspLeaf *>(root);
5785                leaf->GetViewCell()->SetMergeCost(0.0f);
5786                return leaf->GetViewCell();
5787        }
5788       
5789        VspInterior *interior = dynamic_cast<VspInterior *>(root);
5790        ViewCellInterior *viewCellInterior = new ViewCellInterior();
5791               
5792        // evaluate merge cost for priority traversal
5793        const float mergeCost = -(float)root->mTimeStamp;
5794        viewCellInterior->SetMergeCost(mergeCost);
5795
5796        float volume = 0;
5797       
5798        VspNode *front = interior->GetFront();
5799        VspNode *back = interior->GetBack();
5800
5801        ObjectPvs frontPvs, backPvs;
5802
5803        /////////
5804        //-- recursivly compute child hierarchies
5805
5806        ViewCell *backVc = ConstructSpatialMergeTree(back);
5807        ViewCell *frontVc = ConstructSpatialMergeTree(front);
5808
5809        viewCellInterior->SetupChildLink(backVc);
5810        viewCellInterior->SetupChildLink(frontVc);
5811
5812        volume += backVc->GetVolume();
5813        volume += frontVc->GetVolume();
5814
5815        viewCellInterior->SetVolume(volume);
5816
5817        return viewCellInterior;
5818}
5819
5820
5821bool VspOspViewCellsManager::GetViewPoint(Vector3 &viewPoint) const
5822{
5823        if (!ViewCellsConstructed())
5824                return ViewCellsManager::GetViewPoint(viewPoint);
5825
5826        // TODO: set reasonable limit
5827        const int limit = 20;
5828
5829        for (int i = 0; i < limit; ++ i)
5830        {
5831                viewPoint = mViewSpaceBox.GetRandomPoint();
5832
5833                if (mHierarchyManager->GetVspTree()->ViewPointValid(viewPoint))
5834                {
5835                        return true;
5836                }
5837        }
5838
5839        Debug << "failed to find valid view point, taking " << viewPoint << endl;
5840        return false;
5841}
5842
5843
5844void VspOspViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
5845                                                                                                        ViewCell *vc,
5846                                                                                                        const AxisAlignedBox3 *sceneBox,
5847                                                                                                        const AxisAlignedPlane *clipPlane
5848                                                                                                        ) const
5849{
5850        ViewCellContainer leaves;
5851        mViewCellsTree->CollectLeaves(vc, leaves);
5852        ViewCellContainer::const_iterator it, it_end = leaves.end();
5853
5854        Plane3 plane;
5855        if (clipPlane)
5856        {
5857                // arbitrary plane definition
5858                plane = clipPlane->GetPlane();
5859        }
5860
5861        for (it = leaves.begin(); it != it_end; ++ it)
5862        {
5863                VspViewCell *vspVc = dynamic_cast<VspViewCell *>(*it);
5864                VspLeaf *l = vspVc->mLeaves[0];
5865
5866                const AxisAlignedBox3 box =
5867                        mHierarchyManager->GetVspTree()->GetBoundingBox(vspVc->mLeaves[0]);
5868               
5869                if (sceneBox && !Overlap(*sceneBox, box))
5870                        continue;
5871
5872                if (clipPlane)
5873                {
5874                        if (box.Side(plane) == -1)
5875                        {
5876                                exporter->ExportBox(box);
5877                        }
5878                        else if (box.Side(plane) == 0)
5879                        {
5880                                // intersection
5881                                AxisAlignedBox3 fbox, bbox;
5882                                box.Split(clipPlane->mAxis, clipPlane->mPosition, fbox, bbox);
5883                                exporter->ExportBox(bbox);
5884                        }
5885                }
5886                else
5887                {
5888                        exporter->ExportBox(box);
5889                }
5890        }
5891}
5892
5893
5894bool VspOspViewCellsManager::ViewPointValid(const Vector3 &viewPoint) const
5895{
5896  // $$JB -> implemented in viewcellsmanager (slower, but allows dynamic
5897  // validy update in preprocessor for all managers)
5898  return ViewCellsManager::ViewPointValid(viewPoint);
5899
5900  //    return mViewSpaceBox.IsInside(viewPoint) &&
5901  //               mVspTree->ViewPointValid(viewPoint);
5902}
5903
5904
5905float VspOspViewCellsManager::UpdateObjectCosts()
5906{
5907        float maxRenderCost = 0;
5908
5909        cout << "updating object pvs cost ... ";
5910        const long startTime = GetTime();
5911
5912        ViewCellContainer::const_iterator vit, vit_end = mViewCells.end();
5913
5914        Intersectable::NewMail();
5915
5916        const float invViewSpaceVol = 1.0f / GetViewSpaceBox().GetVolume();
5917
5918        for (vit = mViewCells.begin(); vit != vit_end; ++ vit)
5919        {
5920                ViewCell *vc = *vit;
5921
5922                ObjectPvsIterator pit = vc->GetPvs().GetIterator();
5923
5924                // output PVS of view cell
5925                while (pit.HasMoreEntries())
5926                {               
5927                        ObjectPvsEntry entry = pit.Next();
5928                               
5929                        BvhNode *node = dynamic_cast<BvhNode *>(entry.mObject);
5930                       
5931                        // hack!!
5932                        if (!node->IsLeaf())
5933                        {
5934                                cout << "error, can only do leaves" << endl;
5935                                return 0;
5936                        }
5937       
5938                        if (!node->Mailed())
5939                        {
5940                                node->Mail();
5941                                node->mRenderCost = 0;
5942                        }
5943
5944                        const float rc = (float)((BvhLeaf *)node)->mObjects.size();
5945
5946                        node->mRenderCost += rc * vc->GetVolume() * invViewSpaceVol;
5947
5948                        if (node->mRenderCost > maxRenderCost)
5949                                maxRenderCost = node->mRenderCost;
5950                }
5951        }
5952
5953        cout << "finished in " << TimeDiff(startTime, GetTime()) * 1e-3f << " secs" << endl;
5954
5955        return maxRenderCost;
5956}
5957
5958
5959void VspOspViewCellsManager::Visualize(const ObjectContainer &objects,
5960                                                                           const VssRayContainer &sampleRays)
5961{
5962        if (!ViewCellsConstructed())
5963                return;
5964
5965        VssRayContainer visRays;
5966        GetRaySets(sampleRays, mVisualizationSamples, visRays);
5967
5968        ////////////
5969        //-- export final view cells
5970
5971        Exporter *exporter = Exporter::GetExporter("final_view_cells.wrl");
5972
5973        //Vector3 scale(0.9f, 0.9f, 0.9f);
5974        Vector3 scale(1.0f, 1.0f, 1.0f);
5975
5976        if (exporter)
5977        {
5978                if (CLAMP_TO_BOX)
5979                {       
5980                        exporter->mClampToBox = true;   
5981                }
5982
5983                EvaluateViewCellsStats();
5984
5985                const long starttime = GetTime();
5986                cout << "exporting final view cells (after initial construction + post process) ... " << endl;
5987
5988                // matt: hack for clamping scene
5989                AxisAlignedBox3 bbox = mViewSpaceBox;
5990                bbox.Scale(scale);
5991
5992                if (1 && mExportRays)
5993                {       
5994                        exporter->ExportRays(visRays, RgbColor(0, 1, 0));
5995                }
5996
5997                // hack color code
5998                const int savedColorCode = mColorCode;
5999
6000                const float maxRenderCost = UpdateObjectCosts();
6001                cout << "maxRenderCost: " << maxRenderCost << endl;
6002                mColorCode = 0; // 0 = random, 1 = export pvs
6003
6004                if (0)
6005                mHierarchyManager->ExportObjectSpaceHierarchy(exporter, objects,
6006                                                                                                          CLAMP_TO_BOX ? &bbox : NULL, maxRenderCost, false);
6007               
6008
6009                //ExportViewCellsForViz(exporter, CLAMP_TO_BOX ? &bbox : NULL, mColorCode, GetClipPlane());
6010                ExportViewCellsForViz(exporter, NULL, mColorCode, GetClipPlane());
6011
6012                delete exporter;
6013
6014                cout << "finished in " << TimeDiff(starttime, GetTime()) * 1e-3f << " secs" << endl;
6015                mColorCode = savedColorCode;
6016        }
6017
6018        exporter = Exporter::GetExporter("final_object_partition.wrl");
6019
6020        if (exporter)
6021        {
6022                if (CLAMP_TO_BOX)
6023                {       
6024                        exporter->mClampToBox = true;   
6025                }
6026
6027                EvaluateViewCellsStats();
6028
6029                const long starttime = GetTime();
6030                cout << "exporting final objects (after initial construction + post process) ... ";
6031
6032                // matt: hack for clamping scene
6033                AxisAlignedBox3 bbox = mViewSpaceBox;
6034                bbox.Scale(scale);
6035
6036                // hack color code (show pvs size)
6037                const int savedColorCode = mColorCode;
6038
6039                mColorCode = 1; // 0 = random, 1 = export pvs
6040                // don't visualize render cost
6041                const float maxRenderCost = -1;
6042
6043                if (1)
6044                mHierarchyManager->ExportObjectSpaceHierarchy(exporter, objects,
6045                                                                                                          CLAMP_TO_BOX ? &bbox : NULL, maxRenderCost, false);
6046               
6047
6048                //ExportViewCellsForViz(exporter, CLAMP_TO_BOX ? &bbox : NULL, mColorCode, GetClipPlane());
6049                if (0)
6050                        ExportViewCellsForViz(exporter, NULL, mColorCode, GetClipPlane());
6051
6052                delete exporter;
6053
6054                cout << "finished in " << TimeDiff(starttime, GetTime()) * 1e-3f << " secs" << endl;
6055                mColorCode = savedColorCode;
6056        }
6057
6058        // visualization of the merged view cells
6059    if (0)
6060        {       
6061                ExportMergedViewCells(objects);
6062        }
6063
6064        // export some view cells
6065        int leafOut;
6066        Environment::GetSingleton()->GetIntValue("ViewCells.Visualization.maxOutput", leafOut);
6067
6068        const bool sortViewCells = false;
6069        const bool exportPvs = true;
6070        const bool exportRays = true;
6071        const int raysOut = 100;
6072
6073        ExportSingleViewCells(objects,
6074                                                  leafOut,
6075                                                  sortViewCells,
6076                                                  exportPvs,
6077                                                  exportRays,
6078                                                  raysOut,
6079                                                  "");
6080}
6081
6082
6083void VspOspViewCellsManager::ExportSingleViewCells(const ObjectContainer &objects,
6084                                                                                                   const int maxViewCells,
6085                                                                                                   const bool sortViewCells,
6086                                                                                                   const bool exportPvs,
6087                                                                                                   const bool exportRays,
6088                                                                                                   const int maxRays,
6089                                                                                                   const string prefix,
6090                                                                                                   VssRayContainer *visRays)
6091{
6092        if (sortViewCells)
6093        {
6094                // sort view cells to visualize the view cells with highest render cost
6095                sort(mViewCells.begin(), mViewCells.end(), ViewCell::LargerRenderCost);
6096        }
6097
6098        ViewCell::NewMail();
6099        const int limit = min(maxViewCells, (int)mViewCells.size());
6100       
6101        cout << "\nExporting " << limit << " single view cells: " << endl;
6102       
6103        for (int i = 0; i < limit; ++ i)
6104        {
6105                cout << "creating output for view cell " << i << " ... ";
6106               
6107                // largest view cell pvs first of random view cell
6108                ViewCell *vc = sortViewCells ?
6109                        mViewCells[i] : mViewCells[(int)RandomValue(0, (float)mViewCells.size() - 1)];
6110               
6111                if (vc->Mailed()) // view cell already processed
6112                        continue;
6113
6114                vc->Mail();
6115
6116                ObjectPvs pvs;
6117                mViewCellsTree->GetPvs(vc, pvs);
6118
6119                char s[64]; sprintf(s, "%sviewcell%04d.wrl", prefix.c_str(), i);
6120                Exporter *exporter = Exporter::GetExporter(s);
6121               
6122                cout << "view cell " << vc->GetId() << ": pvs cost=" << mViewCellsTree->GetPvsCost(vc) << endl;
6123
6124                if (exportPvs)
6125                {
6126                        Material m;
6127
6128                        Intersectable::NewMail();
6129                       
6130                        ObjectPvsIterator pit = pvs.GetIterator();
6131
6132                        // output PVS of view cell
6133                        while (pit.HasMoreEntries())
6134                        {               
6135                                ObjectPvsEntry entry = pit.Next();
6136                               
6137                                Intersectable *intersect = entry.mObject;
6138
6139                                if (!intersect->Mailed())
6140                                {
6141                                        m = RandomMaterial();
6142                                        exporter->SetForcedMaterial(m);
6143
6144                                        exporter->ExportIntersectable(intersect);
6145                                        intersect->Mail();
6146                                }
6147                        }
6148                }
6149
6150                if (exportRays)
6151                {
6152                        ////////////
6153                        //-- export the sample rays
6154
6155                        // output rays stored with the view cells during subdivision
6156                        VssRayContainer vcRays;
6157                        VssRayContainer collectRays;
6158
6159                        // collect intial view cells
6160                        ViewCellContainer leaves;
6161                        mViewCellsTree->CollectLeaves(vc, leaves);
6162
6163                        ViewCellContainer::const_iterator vit, vit_end = leaves.end();
6164
6165                        for (vit = leaves.begin(); vit != vit_end; ++ vit)
6166                        {
6167                                VspLeaf *vcLeaf = dynamic_cast<VspViewCell *>(*vit)->mLeaves[0];
6168                                VssRayContainer::const_iterator rit, rit_end = vcLeaf->mVssRays.end();
6169
6170                                for (rit = vcLeaf->mVssRays.begin(); rit != rit_end; ++ rit)
6171                                {
6172                                        collectRays.push_back(*rit);
6173                                }
6174                        }
6175
6176                        const int raysOut = min((int)collectRays.size(), maxRays);
6177
6178                        VssRayContainer::const_iterator rit, rit_end = collectRays.end();
6179
6180                        for (rit = collectRays.begin(); rit != rit_end; ++ rit)
6181                        {
6182                                const float p = RandomValue(0.0f, (float)collectRays.size());
6183
6184                                if (p < raysOut)
6185                                        vcRays.push_back(*rit);
6186                        }
6187
6188                        exporter->ExportRays(vcRays, RgbColor(1, 1, 1));
6189                }
6190               
6191       
6192                /////////////////
6193                //-- export view cell geometry
6194
6195                exporter->SetWireframe();
6196
6197                Material m;
6198                m.mDiffuseColor = RgbColor(0, 1, 0);
6199                exporter->SetForcedMaterial(m);
6200
6201                ExportViewCellGeometry(exporter, vc, NULL, NULL);
6202                exporter->SetFilled();
6203
6204                DEL_PTR(exporter);
6205                cout << "finished" << endl;
6206        }
6207
6208        cout << endl;
6209}
6210
6211
6212int VspOspViewCellsManager::ComputeBoxIntersections(const AxisAlignedBox3 &box,
6213                                                                                                        ViewCellContainer &viewCells) const
6214{
6215        return mHierarchyManager->GetVspTree()->ComputeBoxIntersections(box, viewCells);
6216}
6217
6218
6219int VspOspViewCellsManager::CastLineSegment(const Vector3 &origin,
6220                                                                                        const Vector3 &termination,
6221                                                                                        ViewCellContainer &viewcells)
6222{
6223        return mHierarchyManager->
6224                GetVspTree()->CastLineSegment(origin, termination, viewcells);
6225}
6226
6227
6228bool VspOspViewCellsManager::LineSegmentIntersects(const Vector3 &origin,
6229                                                                                                   const Vector3 &termination,
6230                                                                                                   ViewCell *viewCell)
6231{
6232        return mHierarchyManager->
6233                GetVspTree()->LineSegmentIntersects(origin, termination, viewCell);
6234}
6235
6236
6237bool VspOspViewCellsManager::ExportViewCells(const string filename,
6238                                                                                         const bool exportPvs,
6239                                                                                         const ObjectContainer &objects)
6240{
6241        if (!ViewCellsConstructed() || !ViewCellsTreeConstructed())
6242                return false;
6243
6244        const long starttime = GetTime();
6245        cout << "exporting view cells to xml ... ";
6246       
6247        OUT_STREAM stream(filename.c_str());
6248
6249        // for output we need unique ids for each view cell
6250        CreateUniqueViewCellIds();
6251
6252        stream << "<?xml version=\"1.0\" encoding=\"UTF-8\"?>"<<endl;
6253        stream << "<VisibilitySolution>" << endl;
6254
6255        // §§ tmp matt: for storage cost
6256        if (0 && exportPvs)
6257        {
6258        ///////////////
6259                //-- export bounding boxes
6260                //-- The bounding boxes are used to identify
6261                //-- the objects in the rendering engine
6262                mHierarchyManager->ExportBoundingBoxes(stream, objects);
6263        }
6264
6265        //////////////////////////
6266        //-- export the view cells and the pvs
6267
6268        const int numViewCells = mCurrentViewCellsStats.viewCells;
6269
6270        stream << "<ViewCells number=\"" << numViewCells << "\" >" << endl;
6271        mViewCellsTree->Export(stream, exportPvs);
6272        stream << "</ViewCells>" << endl;
6273
6274        //////////////////////
6275        //-- export the view space hierarchy
6276       
6277        stream << "<ViewSpaceHierarchy type=\"vsp\""
6278                   << " min=\"" << mViewSpaceBox.Min().x << " " << mViewSpaceBox.Min().y << " " << mViewSpaceBox.Min().z << "\""
6279                   << " max=\"" << mViewSpaceBox.Max().x << " " << mViewSpaceBox.Max().y << " " << mViewSpaceBox.Max().z << "\">" << endl;
6280
6281        mHierarchyManager->GetVspTree()->Export(stream);
6282        stream << "</ViewSpaceHierarchy>" << endl;
6283
6284        ////////////////////// 
6285        //-- export the object space partition
6286       
6287        mHierarchyManager->ExportObjectSpaceHierarchy(stream);
6288       
6289        stream << "</VisibilitySolution>" << endl;
6290        stream.close();
6291       
6292        cout << "finished in " << TimeDiff(starttime, GetTime()) * 1e-3 << " secs" << endl;
6293        return true;
6294}
6295
6296
6297
6298ViewCell *VspOspViewCellsManager::GetViewCell(const Vector3 &point,
6299                                                                                          const bool active) const
6300{
6301        if (!ViewCellsConstructed())
6302                return NULL;
6303
6304        if (!mViewSpaceBox.IsInside(point))
6305                return NULL;
6306
6307        return mHierarchyManager->GetVspTree()->GetViewCell(point, active);
6308}
6309
6310
6311void VspOspViewCellsManager::CreateMesh(ViewCell *vc)
6312{
6313        // matt: TODO
6314        Mesh *mesh = MeshManager::GetSingleton()->CreateResource();
6315
6316        ViewCellContainer leaves;
6317        mViewCellsTree->CollectLeaves(vc, leaves);
6318
6319        ViewCellContainer::const_iterator it, it_end = leaves.end();
6320
6321    for (it = leaves.begin(); it != it_end; ++ it)
6322        {
6323                VspLeaf *leaf = dynamic_cast<VspViewCell *>(*it)->mLeaves[0];
6324                const AxisAlignedBox3 box = mHierarchyManager->GetVspTree()->GetBoundingBox(leaf);
6325        IncludeBoxInMesh(box, *mesh);
6326        }
6327
6328        vc->SetMesh(mesh);
6329}
6330
6331
6332int VspOspViewCellsManager::CastBeam(Beam &beam)
6333{
6334        // matt: TODO
6335        return 0;
6336}
6337
6338
6339void VspOspViewCellsManager::Finalize(ViewCell *viewCell, const bool createMesh)
6340{
6341        float area = 0;
6342        float volume = 0;
6343
6344        ViewCellContainer leaves;
6345        mViewCellsTree->CollectLeaves(viewCell, leaves);
6346
6347        ViewCellContainer::const_iterator it, it_end = leaves.end();
6348
6349    for (it = leaves.begin(); it != it_end; ++ it)
6350        {
6351                VspLeaf *leaf = dynamic_cast<VspViewCell *>(*it)->mLeaves[0];
6352               
6353                const AxisAlignedBox3 box = mHierarchyManager->GetVspTree()->GetBoundingBox(leaf);
6354
6355                const float lVol = box.GetVolume();
6356                const float lArea = box.SurfaceArea();
6357
6358                area += lArea;
6359                volume += lVol;
6360
6361        CreateMesh(*it);
6362        }
6363
6364        viewCell->SetVolume(volume);
6365        viewCell->SetArea(area);
6366}
6367
6368
6369void VspOspViewCellsManager::PrepareLoadedViewCells()
6370{
6371        // TODO
6372}
6373
6374
6375static void PrintCompressionStats(HierarchyManager *hm, const int pvsEntries)
6376{
6377        float mem = (float)pvsEntries * ObjectPvs::GetEntrySize();
6378               
6379        float fullmem = mem +
6380                        (hm->GetVspTree()->GetStatistics().Leaves() * 16 +
6381                         hm->mBvHierarchy->GetStatistics().Leaves() * 16) / float(1024 * 1024);
6382
6383        cout << "entries: " << pvsEntries << ", mem=" << mem << ", fullmem=" << fullmem <<endl;
6384        Debug << "entries: " << pvsEntries << ", mem=" << mem << ", fullmem=" << fullmem <<endl;
6385}
6386
6387
6388void VspOspViewCellsManager::CompressViewCells()
6389{
6390        if (!(ViewCellsTreeConstructed() && mCompressViewCells))
6391                return;
6392
6393        ////////////
6394        //-- compression
6395
6396        int pvsEntries = mViewCellsTree->CountStoredPvsEntries(mViewCellsTree->GetRoot());
6397
6398        cout << "before compression: " << endl;
6399        Debug << "before compression: " << endl;
6400       
6401        PrintCompressionStats(mHierarchyManager, pvsEntries);
6402
6403        if (mCompressObjects)
6404        {
6405                cout << "compressing in the objects: " << endl;
6406                Debug << "compressing in the objects: " << endl;
6407
6408                pvsEntries = mHierarchyManager->CompressObjectSpace();
6409        }
6410        else
6411        {
6412                cout << "compressing in the view space: " << endl;
6413                Debug << "compressing in the view space: " << endl;
6414
6415                mViewCellsTree->SetViewCellsStorage(ViewCellsTree::COMPRESSED);
6416                pvsEntries = mViewCellsTree->CountStoredPvsEntries(mViewCellsTree->GetRoot());
6417        }
6418
6419        PrintCompressionStats(mHierarchyManager, pvsEntries);
6420}
6421
6422
6423ViewCellsManager *VspOspViewCellsManager::LoadViewCells(const string &filename,
6424                                                                                                                ObjectContainer *objects,
6425                                                                                                                const bool finalizeViewCells,
6426                                                                                                                BoundingBoxConverter *bconverter)
6427                                                                                                 
6428{
6429        ViewCellsManager *vm =
6430                ViewCellsManager::LoadViewCells(filename, objects, finalizeViewCells, bconverter);
6431
6432        return vm;
6433}
6434
6435
6436void
6437VspOspViewCellsManager::CollectObjects(const AxisAlignedBox3 &box, ObjectContainer &objects)
6438{
6439        mHierarchyManager->CollectObjects(box, objects);
6440}
6441
6442
6443#if 1
6444
6445void VspOspViewCellsManager::EvalViewCellPartition()
6446{
6447        int samplesPerPass;
6448        int numSamples;
6449        int castSamples = 0;
6450        int oldSamples = 0;
6451        int samplesForStats;
6452        char statsPrefix[100];
6453        char suffix[100];
6454        int splitsStepSize;
6455
6456        Environment::GetSingleton()->GetIntValue("ViewCells.Evaluation.samplesPerPass", samplesPerPass);
6457        Environment::GetSingleton()->GetIntValue("ViewCells.Evaluation.samplesForStats", samplesForStats);
6458        Environment::GetSingleton()->GetIntValue("ViewCells.Evaluation.samples", numSamples);
6459        Environment::GetSingleton()->GetStringValue("ViewCells.Evaluation.statsPrefix", statsPrefix);
6460        Environment::GetSingleton()->GetIntValue("ViewCells.Evaluation.stepSize", splitsStepSize);
6461       
6462        bool useHisto;
6463        int histoMem;
6464
6465        Environment::GetSingleton()->GetBoolValue("ViewCells.Evaluation.histogram", useHisto);
6466        Environment::GetSingleton()->GetIntValue("ViewCells.Evaluation.histoMem", histoMem);
6467
6468        Debug << "step size: " << splitsStepSize << endl;
6469        Debug << "view cell evaluation samples per pass: " << samplesPerPass << endl;
6470        Debug << "view cell evaluation samples: " << numSamples << endl;
6471        Debug << "view cell stats prefix: " << statsPrefix << endl;
6472
6473    cout << "reseting pvs ... ";
6474               
6475        // reset pvs and start over from zero
6476        mViewCellsTree->ResetPvs();
6477       
6478        cout << "finished" << endl;
6479    cout << "Evaluating view cell partition ... " << endl;
6480
6481        vector<int> evalStrats;
6482
6483        // mix of sampling strategies
6484        if (0)
6485        {
6486                evalStrats.push_back(SamplingStrategy::OBJECT_DIRECTION_BASED_DISTRIBUTION);
6487        }
6488        else
6489        {
6490                /*evalStrats.push_back(SamplingStrategy::OBJECT_BASED_DISTRIBUTION);
6491                evalStrats.push_back(SamplingStrategy::REVERSE_VIEWSPACE_BORDER_BASED_DISTRIBUTION);
6492                evalStrats.push_back(SamplingStrategy::REVERSE_OBJECT_BASED_DISTRIBUTION);
6493                */
6494                evalStrats.push_back(SamplingStrategy::SPATIAL_BOX_BASED_DISTRIBUTION);
6495        }
6496                       
6497    Debug << "casting eval strategies: ";
6498        for (int i = 0; i < (int)evalStrats.size(); ++ i)
6499                Debug << evalStrats[i] << " ";
6500        Debug << endl;
6501
6502        cout << "casting eval strategies: ";
6503        for (int i = 0; i < (int)evalStrats.size(); ++ i)
6504                cout << evalStrats[i] << " ";
6505        cout << endl;
6506
6507        int pass = 0;
6508
6509        while (castSamples < numSamples)
6510        {               
6511                ///////////////
6512                //-- we have to use uniform sampling strategy for construction rays
6513
6514                VssRayContainer evaluationSamples;
6515                const int samplingType = mEvaluationSamplingType;
6516
6517                long startTime = GetTime();
6518
6519                cout << "casting " << samplesPerPass << " samples ... ";
6520                Debug << "casting " << samplesPerPass << " samples ... ";
6521       
6522                if (1)
6523                {
6524                        CastPassSamples(samplesPerPass, evalStrats, evaluationSamples);
6525                }
6526                else
6527                {
6528                        // use mixed distributions
6529                        CastPassSamples2(samplesPerPass, evaluationSamples);
6530                }
6531
6532                castSamples += samplesPerPass;
6533
6534                Real timeDiff = TimeDiff(startTime, GetTime());
6535               
6536                cout << "finished in " << timeDiff * 1e-3f << " secs" << endl;
6537                cout << "computing sample contributions of " << (int)evaluationSamples.size()  << " samples ... ";
6538               
6539                Debug << "finished in " << timeDiff * 1e-3f << " secs" << endl;
6540                Debug << "computing sample contributions of " << (int)evaluationSamples.size()  << " samples ... ";
6541
6542                startTime = GetTime();
6543
6544                ComputeSampleContributions(evaluationSamples, true, false);
6545
6546                timeDiff = TimeDiff(startTime, GetTime());
6547                cout << "finished in " << timeDiff * 1e-3 << " secs" << endl;
6548                Debug << "finished in " << timeDiff * 1e-3 << " secs" << endl;
6549
6550                if ((castSamples >= samplesForStats + oldSamples) ||
6551                        (castSamples >= numSamples))
6552                {
6553                        oldSamples += samplesForStats;
6554
6555                        ///////////
6556                        //-- output stats
6557
6558                        sprintf(suffix, "-%09d-eval.log", castSamples);
6559                        const string filename = string(statsPrefix) + string(suffix);
6560
6561                        startTime = GetTime();
6562                       
6563                        cout << "compute new statistics ... " << endl;
6564
6565                        ofstream ofstr(filename.c_str());
6566                        mHierarchyManager->EvaluateSubdivision2(ofstr, splitsStepSize, false, useHisto, histoMem, pass);
6567
6568                        timeDiff = TimeDiff(startTime, GetTime());
6569                        cout << "finished in " << timeDiff * 1e-3 << " secs" << endl;
6570                        cout << "*************************************" << endl;
6571
6572                        Debug << "statistics computed in " << timeDiff * 1e-3 << " secs" << endl;
6573
6574#if 0
6575                        //////////////
6576                        // filtered stats
6577
6578                        sprintf(suffix, "-%09d-eval-filter.log", castSamples);
6579                        const string filename2 = string(statsPrefix) + string(suffix);
6580
6581                        startTime = GetTime();
6582                       
6583                        cout << "compute new statistics for filtered pvs ... " << endl;
6584
6585                        ofstream ofstr2(filename2.c_str());
6586                        mHierarchyManager->EvaluateSubdivision2(ofstr2, splitsStepSize, true);
6587
6588                        timeDiff = TimeDiff(startTime, GetTime());
6589                        cout << "finished in " << timeDiff * 1e-3 << " secs" << endl;
6590                        cout << "*************************************" << endl;
6591                        Debug << "filtered statistics computed in " << timeDiff * 1e-3 << " secs" << endl;
6592#endif
6593
6594                        // only for debugging purpose
6595                        if (0)
6596                        {
6597                                ViewCellContainer viewCells;
6598                                mViewCellsTree->CollectLeaves(mViewCellsTree->GetRoot(), viewCells);
6599
6600                                ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
6601                                int pvsSize = 0;
6602
6603                                for (vit = viewCells.begin(); vit != vit_end; ++ vit)
6604                                {
6605                                        pvsSize += (*vit)->GetPvs().GetSize();
6606                                }
6607
6608                                cout << "debug entries: " << pvsSize << ", memcost: "
6609                                         << (float)pvsSize * ObjectPvs::GetEntrySize() << endl;
6610                        }
6611                        ++ pass;
6612                }
6613
6614                disposeRays(evaluationSamples, NULL);
6615        }
6616
6617        ////////////
6618        //-- histogram
6619#if 1
6620        const int numLeaves = mViewCellsTree->GetNumInitialViewCells(mViewCellsTree->GetRoot());
6621        int histoStepSize;
6622
6623        Environment::GetSingleton()->GetBoolValue("ViewCells.Evaluation.histogram", useHisto);
6624        Environment::GetSingleton()->GetIntValue("ViewCells.Evaluation.histoStepSize", histoStepSize);
6625
6626        if (useHisto)
6627        {
6628                // evaluate view cells in a histogram           
6629                char str[64];
6630
6631                // hack: just show final view cells
6632                int pass = (int)mViewCells.size();
6633                //for (int pass = histoStepSize; pass <= numLeaves; pass += histoStepSize)
6634                if (1)
6635                {
6636                        string filename;
6637
6638                        cout << "computing histogram for " << pass << " view cells" << endl;
6639
6640                        //////////////////////////////////////////
6641            //-- evaluate histogram for pvs size
6642
6643                        cout << "computing pvs histogram for " << pass << " view cells" << endl;
6644
6645                        sprintf(str, "-%09d-histo-pvs2.log", pass);
6646                        filename = string(statsPrefix) + string(str);
6647
6648                        EvalViewCellHistogramForPvsSize(filename, pass);
6649                }
6650        }
6651#endif
6652}
6653
6654#endif
6655
6656
6657
6658}
Note: See TracBrowser for help on using the repository browser.