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

Revision 1715, 147.2 KB checked in by bittner, 18 years ago (diff)

new visibility filter support

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