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

Revision 1454, 139.8 KB checked in by bittner, 18 years ago (diff)

kd sah - debug logs

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