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

Revision 1660, 143.2 KB checked in by mattausch, 18 years ago (diff)

added ratio for rc / storage

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