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

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