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

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

worked on vsp osp methodsd

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 0
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 = false;
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                               
1918
1919                          if (viewcell->GetPvs().GetSampleContribution(obj,
1920                                                                                                                   ray.mPdf,
1921                                                                                                                   contribution))
1922                                {
1923                                  ++ ray.mPvsContribution;
1924                                  ray.mRelativePvsContribution += contribution;
1925                                }
1926                        }
1927                       
1928#if SAMPLE_ORIGIN_OBJECTS
1929
1930                        // for directional sampling it is important to count only contributions
1931                        // made in one direction!!!
1932                        // the other contributions of this sample will be counted for the oposite ray!
1933
1934                        if (ray.mOriginObject &&
1935                                viewcell->GetPvs().GetSampleContribution(ray.mOriginObject,
1936                                                                                                                 ray.mPdf,
1937                                                                                                                 contribution))
1938                        {
1939                                ++ ray.mPvsContribution;
1940                                ray.mRelativePvsContribution += contribution;
1941                        }
1942#endif
1943                }
1944        }
1945
1946        // if true, the sampled entities are stored in the pvs
1947        if (addRays)
1948        {
1949                for (it = viewcells.begin(); it != viewcells.end(); ++ it)
1950                {
1951                        ViewCell *viewcell = *it;
1952           
1953                        if (viewcell->GetValid())
1954                        {
1955                                // if view point is valid, add new object to the pvs
1956                                if (ray.mTerminationObject)
1957                                {
1958                                        viewcell->GetPvs().AddSample(obj, ray.mPdf);
1959                                }                               
1960#if SAMPLE_ORIGIN_OBJECTS
1961                                 if (ray.mOriginObject)
1962                                 {
1963                                         viewcell->GetPvs().AddSample(ray.mOriginObject, ray.mPdf);
1964                                 }
1965#endif
1966                        }
1967                }
1968        }
1969
1970        return ray.mRelativePvsContribution;
1971}
1972
1973
1974void ViewCellsManager::GetRaySets(const VssRayContainer &sourceRays,
1975                                                                  const int maxSize,
1976                                                                  VssRayContainer &usedRays,
1977                                                                  VssRayContainer *savedRays) const
1978{
1979        const int limit = min(maxSize, (int)sourceRays.size());
1980        const float prop = (float)limit / ((float)sourceRays.size() + Limits::Small);
1981
1982        VssRayContainer::const_iterator it, it_end = sourceRays.end();
1983        for (it = sourceRays.begin(); it != it_end; ++ it)
1984        {
1985                if (Random(1.0f) < prop)
1986                        usedRays.push_back(*it);
1987                else if (savedRays)
1988                        savedRays->push_back(*it);
1989        }
1990}
1991
1992
1993float ViewCellsManager::GetRendercost(ViewCell *viewCell) const
1994{
1995        return (float)mViewCellsTree->GetPvsSize(viewCell);
1996}
1997
1998
1999float ViewCellsManager::GetAccVcArea()
2000{
2001        // if already computed
2002        if (mTotalAreaValid)
2003        {
2004                return mTotalArea;
2005        }
2006
2007        mTotalArea = 0;
2008        ViewCellContainer::const_iterator it, it_end = mViewCells.end();
2009
2010        for (it = mViewCells.begin(); it != it_end; ++ it)
2011        {
2012                //Debug << "area: " << GetArea(*it);
2013        mTotalArea += GetArea(*it);
2014        }
2015
2016        mTotalAreaValid = true;
2017
2018        return mTotalArea;
2019}
2020
2021
2022void ViewCellsManager::PrintStatistics(ostream &s) const
2023{
2024        s << mCurrentViewCellsStats << endl;
2025}
2026
2027
2028void ViewCellsManager::CreateUniqueViewCellIds()
2029{
2030        if (ViewCellsTreeConstructed())
2031        {
2032                mViewCellsTree->CreateUniqueViewCellsIds();
2033        }
2034        else // no view cells tree, handle view cells "myself"
2035        {
2036                int i = 0;
2037                ViewCellContainer::const_iterator vit, vit_end = mViewCells.end();
2038                for (vit = mViewCells.begin(); vit != vit_end; ++ vit)
2039                {
2040                        if ((*vit)->GetId() != OUT_OF_BOUNDS_ID)
2041                        {
2042                                mViewCells[i]->SetId(i ++);
2043                        }
2044                }
2045        }
2046}
2047
2048
2049void ViewCellsManager::ExportViewCellsForViz(Exporter *exporter,
2050                                                                                         const AxisAlignedBox3 *sceneBox,
2051                                                                                         const AxisAlignedPlane *clipPlane,
2052                                                                                         const bool colorCode
2053                                                                                         ) const
2054{
2055        ViewCellContainer::const_iterator it, it_end = mViewCells.end();
2056
2057        for (it = mViewCells.begin(); it != it_end; ++ it)
2058        {
2059                if (!mOnlyValidViewCells || (*it)->GetValid())
2060                {
2061                        ExportColor(exporter, *it, colorCode); 
2062                        ExportViewCellGeometry(exporter, *it, sceneBox, clipPlane);
2063                }
2064        }
2065}
2066
2067
2068void ViewCellsManager::CreateViewCellMeshes()
2069{
2070        // convert to meshes
2071        ViewCellContainer::const_iterator it, it_end = mViewCells.end();
2072
2073        for (it = mViewCells.begin(); it != it_end; ++ it)
2074        {
2075                if (!(*it)->GetMesh())
2076                {
2077                        CreateMesh(*it);
2078                }
2079        }
2080}
2081
2082
2083bool ViewCellsManager::ExportViewCells(const string filename,
2084                                                                           const bool exportPvs,
2085                                                                           const ObjectContainer &objects)
2086{
2087        return false;
2088}
2089
2090
2091void ViewCellsManager::CollectViewCells(const int n)
2092{
2093        mNumActiveViewCells = n;
2094        mViewCells.clear();
2095        // implemented in subclasses
2096        CollectViewCells();
2097}
2098
2099
2100void ViewCellsManager::SetViewCellsActive()
2101{
2102        // collect leaf view cells and set the pointers to the currently
2103        // active view cells
2104        ViewCellContainer::const_iterator it, it_end = mViewCells.end();
2105
2106        for (it = mViewCells.begin(); it != it_end; ++ it)
2107        {
2108                ViewCellContainer leaves;
2109                mViewCellsTree->CollectLeaves(*it, leaves);
2110
2111                ViewCellContainer::const_iterator lit, lit_end = leaves.end();
2112                for (lit = mViewCells.begin(); lit != lit_end; ++ lit)
2113                {
2114                        dynamic_cast<ViewCellLeaf *>(*lit)->SetActiveViewCell(*it);
2115                }
2116        }
2117}
2118
2119
2120int ViewCellsManager::GetMaxFilterSize() const
2121{
2122        return mMaxFilterSize; 
2123}
2124
2125
2126static const bool USE_ASCII = true;
2127
2128
2129bool ViewCellsManager::ExportBoundingBoxes(const string filename,
2130                                                                                   const ObjectContainer &objects) const
2131{
2132        ObjectContainer::const_iterator it, it_end = objects.end();
2133       
2134        if (USE_ASCII)
2135        {
2136                ofstream boxesOut(filename.c_str());
2137                if (!boxesOut.is_open())
2138                        return false;
2139
2140                for (it = objects.begin(); it != it_end; ++ it)
2141                {
2142                        MeshInstance *mi = dynamic_cast<MeshInstance *>(*it);
2143                        const AxisAlignedBox3 box = mi->GetBox();
2144
2145                        boxesOut << mi->GetId() << " "
2146                                         << box.Min().x << " "
2147                                         << box.Min().y << " "
2148                                         << box.Min().z << " "
2149                                         << box.Max().x << " "
2150                                         << box.Max().y << " "
2151                     << box.Max().z << endl;   
2152                }
2153
2154                boxesOut.close();
2155        }
2156        else
2157        {
2158                ofstream boxesOut(filename.c_str(), ios::binary);
2159
2160                if (!boxesOut.is_open())
2161                        return false;
2162
2163                for (it = objects.begin(); it != it_end; ++ it)
2164                {       
2165                        MeshInstance *mi = dynamic_cast<MeshInstance *>(*it);
2166                        const AxisAlignedBox3 box = mi->GetBox();
2167                        Vector3 bmin = box.Min();
2168                        Vector3 bmax = box.Max();
2169                        int id = mi->GetId();
2170
2171                        boxesOut.write(reinterpret_cast<char *>(&id), sizeof(int));
2172                        boxesOut.write(reinterpret_cast<char *>(&bmin), sizeof(Vector3));
2173                        boxesOut.write(reinterpret_cast<char *>(&bmax), sizeof(Vector3));
2174                }
2175               
2176                boxesOut.close();
2177        }
2178
2179        return true;
2180}
2181
2182
2183bool ViewCellsManager::LoadBoundingBoxes(const string filename,
2184                                                                                 IndexedBoundingBoxContainer &boxes) const
2185{
2186        Vector3 bmin, bmax;
2187        int id;
2188
2189        if (USE_ASCII)
2190        {
2191                ifstream boxesIn(filename.c_str());
2192               
2193                if (!boxesIn.is_open())
2194                {
2195                        cout << "failed to open file " << filename << endl;
2196                        return false;
2197                }
2198
2199                string buf;
2200                while (!(getline(boxesIn, buf)).eof())
2201                {
2202                        sscanf(buf.c_str(), "%d %f %f %f %f %f %f",
2203                                   &id, &bmin.x, &bmin.y, &bmin.z,
2204                                   &bmax.x, &bmax.y, &bmax.z);
2205               
2206                        AxisAlignedBox3 box(bmin, bmax);
2207                        //      MeshInstance *mi = new MeshInstance();
2208                        // HACK: set bounding box to new box
2209                        //mi->mBox = box;
2210
2211                        boxes.push_back(IndexedBoundingBox(id, box));
2212                }
2213
2214                boxesIn.close();
2215        }
2216        else
2217        {
2218                ifstream boxesIn(filename.c_str(), ios::binary);
2219
2220                if (!boxesIn.is_open())
2221                        return false;
2222
2223                while (1)
2224                {
2225                        boxesIn.read(reinterpret_cast<char *>(&id), sizeof(Vector3));
2226                        boxesIn.read(reinterpret_cast<char *>(&bmin), sizeof(Vector3));
2227                        boxesIn.read(reinterpret_cast<char *>(&bmax), sizeof(Vector3));
2228                       
2229                        if (boxesIn.eof())
2230                                break;
2231
2232                       
2233                        AxisAlignedBox3 box(bmin, bmax);
2234                        MeshInstance *mi = new MeshInstance(NULL);
2235
2236                        // HACK: set bounding box to new box
2237                        //mi->mBox = box;
2238                        //boxes.push_back(mi);
2239                        boxes.push_back(IndexedBoundingBox(id, box));
2240                }
2241
2242                boxesIn.close();
2243        }
2244
2245        return true;
2246}
2247
2248
2249float ViewCellsManager::GetFilterWidth()
2250{
2251        return mFilterWidth;
2252}
2253
2254
2255float ViewCellsManager::GetAbsFilterWidth()
2256{
2257        return Magnitude(mViewSpaceBox.Size()) * mFilterWidth;
2258}
2259
2260
2261void ViewCellsManager::UpdateScalarPvsSize(ViewCell *vc,
2262                                                                                   const int pvsSize,
2263                                                                                   const int entriesInPvs) const
2264{
2265        vc->mPvsSize = pvsSize;
2266        vc->mEntriesInPvs = entriesInPvs;
2267
2268        vc->mPvsSizeValid = true;
2269}
2270
2271
2272void
2273ViewCellsManager::ApplyFilter(ViewCell *viewCell,
2274                                                          KdTree *kdTree,
2275                                                          const float viewSpaceFilterSize,
2276                                                          const float spatialFilterSize,
2277                                                          ObjectPvs &pvs
2278                                                          )
2279{
2280  // extend the pvs of the viewcell by pvs of its neighbors
2281  // and apply spatial filter by including all neighbors of the objects
2282  // in the pvs
2283
2284  // get all viewcells intersecting the viewSpaceFilterBox
2285  // and compute the pvs union
2286 
2287  //Vector3 center = viewCell->GetBox().Center();
2288  //  Vector3 center = m->mBox.Center();
2289 
2290  //  AxisAlignedBox3 box(center - Vector3(viewSpaceFilterSize/2),
2291  //                                      center + Vector3(viewSpaceFilterSize/2));
2292        if (!ViewCellsConstructed())
2293                return;
2294
2295        if (viewSpaceFilterSize >= 0.0f) {
2296
2297  const bool usePrVS = false;
2298
2299  if (!usePrVS) {
2300        AxisAlignedBox3 box = GetViewCellBox(viewCell);
2301        box.Enlarge(Vector3(viewSpaceFilterSize/2));
2302       
2303        ViewCellContainer viewCells;
2304        ComputeBoxIntersections(box, viewCells);
2305       
2306  //  cout<<"box="<<box<<endl;
2307        ViewCellContainer::const_iterator it = viewCells.begin(), it_end = viewCells.end();
2308       
2309        int i;
2310        for (i=0; it != it_end; ++ it, ++ i) {
2311                //cout<<"v"<<i<<" pvs="<<(*it)->GetPvs().mEntries.size()<<endl;
2312          pvs.Merge((*it)->GetPvs());
2313        }
2314  } else {
2315        PrVs prvs;
2316        AxisAlignedBox3 box = GetViewCellBox(viewCell);
2317
2318        //  mViewCellsManager->SetMaxFilterSize(1);
2319        GetPrVS(box.Center(), prvs, viewSpaceFilterSize);
2320        pvs = prvs.mViewCell->GetPvs();
2321        DeleteLocalMergeTree(prvs.mViewCell);
2322  }
2323  } else
2324        pvs = viewCell->GetPvs();
2325   
2326  if (spatialFilterSize >=0.0f)
2327        ApplySpatialFilter(kdTree, spatialFilterSize, pvs);
2328 
2329}
2330
2331
2332
2333void
2334ViewCellsManager::ApplyFilter(KdTree *kdTree,
2335                                                          const float relViewSpaceFilterSize,
2336                                                          const float relSpatialFilterSize
2337                                                          )
2338{
2339
2340        if (!ViewCellsConstructed())
2341                return;
2342
2343  ViewCellContainer::const_iterator it, it_end = mViewCells.end();
2344
2345  ObjectPvs *newPvs;
2346  newPvs = new ObjectPvs[mViewCells.size()];
2347
2348  float viewSpaceFilterSize = Magnitude(mViewSpaceBox.Size())*relViewSpaceFilterSize;
2349  float spatialFilterSize = Magnitude(kdTree->GetBox().Size())*relSpatialFilterSize;
2350 
2351  int i;
2352  for (i=0, it = mViewCells.begin(); it != it_end; ++ it, ++ i) {
2353        ApplyFilter(*it,
2354                                kdTree,
2355                                viewSpaceFilterSize,
2356                                spatialFilterSize,
2357                                newPvs[i]
2358                                );
2359  }
2360
2361  // now replace all pvss
2362  for (i = 0, it = mViewCells.begin(); it != it_end; ++ it, ++ i) {
2363           
2364        ObjectPvs &pvs = (*it)->GetPvs();
2365        pvs.Clear();
2366        pvs = newPvs[i];
2367        newPvs[i].Clear();
2368  }
2369 
2370  delete [] newPvs;
2371}
2372
2373
2374
2375
2376void
2377ViewCellsManager::ApplySpatialFilter(
2378                                                                         KdTree *kdTree,
2379                                                                         const float spatialFilterSize,
2380                                                                         ObjectPvs &pvs
2381                                                                         )
2382{
2383  // now compute a new Pvs by including also objects intersecting the
2384  // extended boxes of visible objects
2385  Intersectable::NewMail();
2386 
2387 ObjectPvsMap::const_iterator oi;
2388 
2389  for (oi = pvs.mEntries.begin(); oi != pvs.mEntries.end(); ++ oi)
2390  {
2391          Intersectable *object = (*oi).first;
2392      object->Mail();
2393  }
2394
2395  ObjectPvs nPvs;
2396  int nPvsSize = 0;
2397  // now go through the pvs again
2398  for (oi = pvs.mEntries.begin(); oi != pvs.mEntries.end(); ++oi) {
2399        Intersectable *object = (*oi).first;
2400
2401        //      Vector3 center = object->GetBox().Center();
2402        //      AxisAlignedBox3 box(center - Vector3(spatialFilterSize/2),
2403        //                                              center + Vector3(spatialFilterSize/2));
2404
2405        AxisAlignedBox3 box = object->GetBox();
2406        box.Enlarge(Vector3(spatialFilterSize/2));
2407
2408        ObjectContainer objects;
2409
2410        // $$ warning collect objects takes only unmailed ones!
2411        kdTree->CollectObjects(box, objects);
2412        //      cout<<"collected objects="<<objects.size()<<endl;
2413        ObjectContainer::const_iterator noi = objects.begin();
2414        for (; noi != objects.end(); ++ noi)
2415        {
2416                Intersectable *o = *noi;
2417                // $$ JB warning: pdfs are not correct at this point!     
2418                nPvs.AddSample(o, Limits::Small);
2419                nPvsSize ++;
2420        }
2421  }
2422  //  cout<<"nPvs size = "<<nPvsSize<<endl;
2423  pvs.Merge(nPvs);
2424}
2425
2426
2427void ViewCellsManager::ExportColor(Exporter *exporter,
2428                                                                   ViewCell *vc,
2429                                                                   bool colorCode) const
2430{
2431        const bool vcValid = CheckValidity(vc, mMinPvsSize, mMaxPvsSize);
2432
2433        float importance = 0;
2434        static Material m;
2435
2436        switch (mColorCode)
2437        {
2438        case 0: // Random
2439                {
2440                        if (vcValid)
2441                        {
2442                                m.mDiffuseColor.r = 0.5f + RandomValue(0.0f, 0.5f);
2443                                m.mDiffuseColor.g = 0.5f + RandomValue(0.0f, 0.5f);
2444                                m.mDiffuseColor.b = 0.5f + RandomValue(0.f, 0.5f);
2445                        }
2446                        else
2447                        {
2448                                m.mDiffuseColor.r = 0.0f;
2449                                m.mDiffuseColor.g = 1.0f;
2450                                m.mDiffuseColor.b = 0.0f;
2451                        }
2452
2453                        exporter->SetForcedMaterial(m);
2454                        return;
2455                }
2456               
2457        case 1: // pvs
2458                {
2459                        if (mCurrentViewCellsStats.maxPvs)
2460                        {
2461                                importance =
2462                                        (float)mViewCellsTree->GetPvsSize(vc) /
2463                                        (float)mCurrentViewCellsStats.maxPvs;
2464                        }
2465                }
2466                break;
2467        case 2: // merges
2468                {
2469            const int lSize = mViewCellsTree->GetNumInitialViewCells(vc);
2470                        importance = (float)lSize / (float)mCurrentViewCellsStats.maxLeaves;
2471                }
2472                break;
2473#if 0
2474        case 3: // merge tree differene
2475                {
2476                        importance = (float)GetMaxTreeDiff(vc) /
2477                                (float)(mVspBspTree->GetStatistics().maxDepth * 2);
2478
2479                }
2480                break;
2481#endif
2482        default:
2483                break;
2484        }
2485
2486        // special color code for invalid view cells
2487        m.mDiffuseColor.r = importance;
2488        m.mDiffuseColor.g = 1.0f - m.mDiffuseColor.r;
2489        m.mDiffuseColor.b = vcValid ? 1.0f : 0.0f;
2490
2491        //Debug << "importance: " << importance << endl;
2492        exporter->SetForcedMaterial(m);
2493}
2494
2495
2496void ViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays,
2497                                                                                          vector<MergeCandidate> &candidates)
2498{
2499        // implemented in subclasses
2500}
2501
2502
2503void
2504ViewCellsManager::UpdatePvsForEvaluation()
2505{
2506  ObjectPvs objPvs;
2507  UpdatePvsForEvaluation(mViewCellsTree->GetRoot(), objPvs);
2508}
2509
2510void ViewCellsManager::UpdatePvsForEvaluation(ViewCell *root, ObjectPvs &pvs)
2511{
2512        // terminate traversal
2513        if (root->IsLeaf())
2514        {
2515                // we assume that pvs is explicitly stored in leaves
2516                pvs = root->GetPvs();
2517                UpdateScalarPvsSize(root, pvs.CountObjectsInPvs(), pvs.GetSize());
2518               
2519                return;
2520        }
2521       
2522        ////////////////
2523        //-- interior node => propagate pvs up the tree
2524
2525        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(root);
2526
2527        // reset interior pvs
2528        interior->GetPvs().Clear();
2529        // reset recursive pvs
2530        pvs.Clear();
2531        vector<ObjectPvs> pvsList;
2532
2533        ViewCellContainer::const_iterator vit, vit_end = interior->mChildren.end();
2534
2535        for (vit = interior->mChildren.begin(); vit != vit_end; ++ vit)
2536        {
2537                ObjectPvs objPvs;
2538               
2539                //////////////////
2540                //-- recursivly compute child pvss
2541
2542                UpdatePvsForEvaluation(*vit, objPvs);
2543
2544                // store pvs in vector
2545                pvsList.push_back(objPvs);
2546        }
2547
2548#if 1
2549        Intersectable::NewMail();
2550
2551        //-- faster way of computing pvs:
2552        //-- construct merged pvs by adding
2553        //-- and only those of the next pvs which were not mailed.
2554        //-- note: sumpdf is not correct!!
2555
2556        vector<ObjectPvs>::iterator oit = pvsList.begin();
2557
2558        for (vit = interior->mChildren.begin(); vit != vit_end; ++ vit, ++ oit)
2559        {
2560            ObjectPvsMap::iterator pit, pit_end = (*oit).mEntries.end();
2561       
2562                for (pit = (*oit).mEntries.begin(); pit != pit_end; ++ pit)
2563                {
2564                        Intersectable *intersect = (*pit).first;
2565
2566                        if (!intersect->Mailed())
2567                        {
2568                                pvs.AddSample(intersect, (*pit).second.mSumPdf);
2569                                intersect->Mail();
2570                        }
2571                }
2572        }
2573
2574        // store pvs in this node
2575        if (mViewCellsTree->ViewCellsStorage() == ViewCellsTree::PVS_IN_INTERIORS)
2576        {
2577                interior->SetPvs(pvs);
2578        }
2579       
2580        // set new pvs size
2581        UpdateScalarPvsSize(interior, pvs.CountObjectsInPvs(), pvs.GetSize());
2582       
2583#else
2584        // really merge cells: slow put sumPdf is correct
2585        viewCellInterior->GetPvs().Merge(backVc->GetPvs());
2586        viewCellInterior->GetPvs().Merge(frontVc->GetPvs());
2587#endif
2588}
2589
2590
2591
2592/*******************************************************************/
2593/*               BspViewCellsManager implementation                */
2594/*******************************************************************/
2595
2596
2597BspViewCellsManager::BspViewCellsManager(ViewCellsTree *vcTree, BspTree *bspTree):
2598ViewCellsManager(vcTree), mBspTree(bspTree)
2599{
2600        Environment::GetSingleton()->GetIntValue("BspTree.Construction.samples", mInitialSamples);
2601
2602        mBspTree->SetViewCellsManager(this);
2603        mBspTree->SetViewCellsTree(mViewCellsTree);
2604}
2605
2606
2607bool BspViewCellsManager::ViewCellsConstructed() const
2608{
2609        return mBspTree->GetRoot() != NULL;
2610}
2611
2612
2613ViewCell *BspViewCellsManager::GenerateViewCell(Mesh *mesh) const
2614{
2615        return new BspViewCell(mesh);
2616}
2617
2618
2619int BspViewCellsManager::ConstructSubdivision(const ObjectContainer &objects,
2620                                                                                          const VssRayContainer &rays)
2621{
2622        // if view cells were already constructed, we can finish
2623        if (ViewCellsConstructed())
2624                return 0;
2625
2626        int sampleContributions = 0;
2627
2628        // construct view cells using the collected samples
2629        RayContainer constructionRays;
2630        VssRayContainer savedRays;
2631
2632        // choose a a number of rays based on the ratio of cast rays / requested rays
2633        const int limit = min(mInitialSamples, (int)rays.size());
2634        VssRayContainer::const_iterator it, it_end = rays.end();
2635
2636        const float prop = (float)limit / ((float)rays.size() + Limits::Small);
2637
2638        for (it = rays.begin(); it != it_end; ++ it)
2639        {
2640                if (Random(1.0f) < prop)
2641                        constructionRays.push_back(new Ray(*(*it)));
2642                else
2643                        savedRays.push_back(*it);
2644        }
2645
2646    if (!mUsePredefinedViewCells)
2647        {
2648                // no view cells loaded
2649                mBspTree->Construct(objects, constructionRays, &mViewSpaceBox);
2650                // collect final view cells
2651                mBspTree->CollectViewCells(mViewCells);
2652        }
2653        else
2654        {       
2655                // use predefined view cells geometry =>
2656                // contruct bsp hierarchy over them
2657                mBspTree->Construct(mViewCells);
2658        }
2659
2660        // destroy rays created only for construction
2661        CLEAR_CONTAINER(constructionRays);
2662
2663        Debug << mBspTree->GetStatistics() << endl;
2664        Debug << "\nView cells after construction:\n" << mCurrentViewCellsStats << endl;
2665
2666        // recast rest of the rays
2667        if (SAMPLE_AFTER_SUBDIVISION)
2668                ComputeSampleContributions(savedRays, true, false);
2669
2670        // real meshes are contructed at this stage
2671        if (0)
2672        {
2673                cout << "finalizing view cells ... ";
2674                FinalizeViewCells(true);
2675                cout << "finished" << endl;     
2676        }
2677
2678        return sampleContributions;
2679}
2680
2681
2682void BspViewCellsManager::CollectViewCells()
2683{       
2684        if (!ViewCellsTreeConstructed())
2685        {       // view cells tree constructed 
2686                mBspTree->CollectViewCells(mViewCells);
2687        }
2688        else
2689        {       // we can use the view cells tree hierarchy to get the right set
2690                mViewCellsTree->CollectBestViewCellSet(mViewCells, mNumActiveViewCells);
2691        }
2692}
2693
2694
2695float BspViewCellsManager::GetProbability(ViewCell *viewCell)
2696{
2697        if (1)
2698                return GetVolume(viewCell) / GetViewSpaceBox().GetVolume();
2699        else
2700                // compute view cell area as subsititute for probability
2701                return GetArea(viewCell) / GetAccVcArea();
2702}
2703
2704
2705
2706int BspViewCellsManager::CastLineSegment(const Vector3 &origin,
2707                                                                                 const Vector3 &termination,
2708                                                                                 ViewCellContainer &viewcells)
2709{
2710        return mBspTree->CastLineSegment(origin, termination, viewcells);
2711}
2712
2713
2714void ViewCellsManager::ExportMergedViewCells(const ObjectContainer &objects)
2715{
2716        // save color code
2717        const int savedColorCode = mColorCode;
2718
2719        // export merged view cells
2720        mColorCode = 0; // use random colors
2721
2722        Exporter *exporter = Exporter::GetExporter("merged_view_cells.wrl");
2723
2724        cout << "exporting view cells after merge ... ";
2725
2726        if (exporter)
2727        {
2728                if (mExportGeometry)
2729                {
2730                        exporter->ExportGeometry(objects);
2731                }
2732
2733                exporter->SetFilled();
2734                ExportViewCellsForViz(exporter, NULL, GetClipPlane());
2735
2736                delete exporter;
2737        }
2738        cout << "finished" << endl;
2739
2740        // export merged view cells using pvs color coding
2741        mColorCode = 1;
2742
2743        exporter = Exporter::GetExporter("merged_view_cells_pvs.wrl");
2744        cout << "exporting view cells after merge (pvs size) ... ";     
2745
2746        if (exporter)
2747        {
2748                if (mExportGeometry)
2749                {
2750                        exporter->ExportGeometry(objects);
2751                }
2752
2753                exporter->SetFilled();
2754                ExportViewCellsForViz(exporter, NULL, GetClipPlane());
2755
2756                delete exporter;
2757        }
2758        cout << "finished" << endl;
2759       
2760        mColorCode = savedColorCode;
2761}
2762
2763
2764int BspViewCellsManager::PostProcess(const ObjectContainer &objects,
2765                                                                         const VssRayContainer &rays)
2766{
2767        if (!ViewCellsConstructed())
2768        {
2769                Debug << "view cells not constructed" << endl;
2770                return 0;
2771        }
2772       
2773        // view cells already finished before post processing step,
2774        // i.e., because they were loaded from disc
2775        if (mViewCellsFinished)
2776        {
2777                FinalizeViewCells(true);
2778                EvaluateViewCellsStats();
2779
2780                return 0;
2781        }
2782
2783        //////////////////
2784        //-- merge leaves of the view cell hierarchy   
2785       
2786        cout << "starting post processing using " << mPostProcessSamples << " samples ... ";
2787        long startTime = GetTime();
2788       
2789        VssRayContainer postProcessRays;
2790        GetRaySets(rays, mPostProcessSamples, postProcessRays);
2791
2792        if (mMergeViewCells)
2793        {
2794                cout << "constructing visibility based merge tree" << endl;
2795                mViewCellsTree->ConstructMergeTree(rays, objects);
2796        }
2797        else
2798        {
2799                cout << "constructing spatial merge tree" << endl;
2800                ViewCell *root;
2801                // the spatial merge tree is difficult to build for
2802                // this type of construction, as view cells cover several
2803                // leaves => create dummy tree which is only 2 levels deep
2804                if (mUsePredefinedViewCells)
2805                {
2806                        root = ConstructDummyMergeTree(mBspTree->GetRoot());
2807                }
2808                else
2809                {
2810                        // create spatial merge hierarchy
2811                        root = ConstructSpatialMergeTree(mBspTree->GetRoot());
2812                }
2813               
2814                mViewCellsTree->SetRoot(root);
2815
2816                // recompute pvs in the whole hierarchy
2817                ObjectPvs pvs;
2818                UpdatePvsForEvaluation(root, pvs);
2819        }
2820
2821        cout << "finished" << endl;
2822        cout << "merged view cells in "
2823                 << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
2824
2825        Debug << "Postprocessing: Merged view cells in "
2826                << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl << endl;
2827
2828       
2829        ////////////////////////
2830        //-- visualization and statistics after merge
2831
2832        if (1)
2833        {
2834                char mstats[100];
2835                Environment::GetSingleton()->GetStringValue("ViewCells.mergeStats", mstats);
2836                mViewCellsTree->ExportStats(mstats);
2837        }
2838
2839        // recompute view cells and stats
2840        ResetViewCells();
2841        Debug << "\nView cells after merge:\n" << mCurrentViewCellsStats << endl;
2842
2843        //  visualization of the view cells
2844        if (1) ExportMergedViewCells(objects);
2845
2846        // compute final meshes and volume / area
2847        if (1) FinalizeViewCells(true);
2848
2849        // write view cells to disc
2850        if (1 && mExportViewCells)
2851        {
2852                char filename[100];
2853                Environment::GetSingleton()->GetStringValue("ViewCells.filename", filename);
2854                ExportViewCells(filename, mExportPvs, objects);
2855        }
2856       
2857        return 0;
2858}
2859
2860
2861BspViewCellsManager::~BspViewCellsManager()
2862{
2863}
2864
2865
2866int BspViewCellsManager::GetType() const
2867{
2868        return BSP;
2869}
2870
2871
2872void BspViewCellsManager::Visualize(const ObjectContainer &objects,
2873                                                                        const VssRayContainer &sampleRays)
2874{
2875        if (!ViewCellsConstructed())
2876                return;
2877       
2878        const int savedColorCode = mColorCode;
2879       
2880        if (1) // export final view cells
2881        {
2882                mColorCode = 1; // hack color code
2883                Exporter *exporter = Exporter::GetExporter("final_view_cells.wrl");
2884       
2885                cout << "exporting view cells after merge (pvs size) ... ";     
2886
2887                if (exporter)
2888                {
2889                        if (mExportGeometry)
2890                        {
2891                                exporter->ExportGeometry(objects);
2892                        }
2893
2894                        ExportViewCellsForViz(exporter, NULL, GetClipPlane());
2895                        delete exporter;
2896                }
2897                cout << "finished" << endl;
2898        }
2899
2900        // reset color code
2901        mColorCode = savedColorCode;
2902
2903
2904        //////////////////
2905        //-- visualization of the BSP splits
2906
2907        bool exportSplits = false;
2908        Environment::GetSingleton()->GetBoolValue("BspTree.Visualization.exportSplits", exportSplits);
2909
2910        if (exportSplits)
2911        {
2912                cout << "exporting splits ... ";
2913                ExportSplits(objects);
2914                cout << "finished" << endl;
2915        }
2916
2917        int leafOut;
2918        Environment::GetSingleton()->GetIntValue("ViewCells.Visualization.maxOutput", leafOut);
2919        const int raysOut = 100;
2920        ExportSingleViewCells(objects, leafOut, false, true, false, raysOut, "");
2921}
2922
2923
2924void BspViewCellsManager::ExportSplits(const ObjectContainer &objects)
2925{
2926        Exporter *exporter = Exporter::GetExporter("bsp_splits.x3d");
2927
2928        if (exporter)
2929        {
2930                //exporter->SetFilled();
2931                if (mExportGeometry)
2932                {
2933                        exporter->ExportGeometry(objects);
2934                }
2935
2936                Material m;
2937                m.mDiffuseColor = RgbColor(1, 0, 0);
2938                exporter->SetForcedMaterial(m);
2939                exporter->SetWireframe();
2940
2941                exporter->ExportBspSplits(*mBspTree, true);
2942
2943                // NOTE: take forced material, else big scenes cannot be viewed
2944                m.mDiffuseColor = RgbColor(0, 1, 0);
2945                exporter->SetForcedMaterial(m);
2946                //exporter->ResetForcedMaterial();
2947
2948                delete exporter;
2949        }
2950}
2951
2952
2953void BspViewCellsManager::ExportSingleViewCells(const ObjectContainer &objects,
2954                                                                                                const int maxViewCells,
2955                                                                                                const bool sortViewCells,
2956                                                                                                const bool exportPvs,
2957                                                                                                const bool exportRays,
2958                                                                                                const int maxRays,
2959                                                                                                const string prefix,
2960                                                                                                VssRayContainer *visRays)
2961{
2962        if (sortViewCells)
2963        {       // sort view cells to visualize the largest view cells
2964                stable_sort(mViewCells.begin(), mViewCells.end(), ViewCell::LargerRenderCost);
2965        }
2966
2967        //////////
2968        //-- some view cells for output
2969
2970        ViewCell::NewMail();
2971        const int limit = min(maxViewCells, (int)mViewCells.size());
2972       
2973        for (int i = 0; i < limit; ++ i)
2974        {
2975                const int idx = sortViewCells ? (int)RandomValue(0, (float)mViewCells.size() - 0.5f) : i;
2976                ViewCell *vc = mViewCells[idx];
2977
2978                if (vc->Mailed() || vc->GetId() == OUT_OF_BOUNDS_ID)
2979                        continue;
2980
2981                vc->Mail();
2982
2983                ObjectPvs pvs;
2984                mViewCellsTree->GetPvs(vc, pvs);
2985
2986                char s[64]; sprintf(s, "%sviewcell-%04d.wrl", prefix.c_str(), i);
2987                Exporter *exporter = Exporter::GetExporter(s);
2988               
2989                cout << "view cell " << idx << ": pvs size=" << (int)mViewCellsTree->GetPvsSize(vc) << endl;
2990
2991                if (exportRays)
2992                {
2993                        ////////////
2994                        //-- export rays piercing this view cell
2995
2996                        // use rays stored with the view cells
2997                        VssRayContainer vcRays, vcRays2, vcRays3;
2998            VssRayContainer collectRays;
2999
3000                        // collect initial view cells
3001                        ViewCellContainer leaves;
3002                        mViewCellsTree->CollectLeaves(vc, leaves);
3003
3004                        ViewCellContainer::const_iterator vit, vit_end = leaves.end();
3005                for (vit = leaves.begin(); vit != vit_end; ++ vit)
3006                        {       
3007                                // prepare some rays for output
3008                                VssRayContainer::const_iterator rit, rit_end = (*vit)->mVssRays.end();
3009                                for (rit = (*vit)->mVssRays.begin(); rit != rit_end; ++ rit)
3010                                {
3011                                        collectRays.push_back(*rit);
3012                                }
3013                        }
3014
3015                        const int raysOut = min((int)collectRays.size(), maxRays);
3016
3017                        // prepare some rays for output
3018                        VssRayContainer::const_iterator rit, rit_end = collectRays.end();
3019                        for (rit = collectRays.begin(); rit != rit_end; ++ rit)
3020                        {
3021                                const float p = RandomValue(0.0f, (float)collectRays.size());
3022                                if (p < raysOut)
3023                                {
3024                                        if ((*rit)->mFlags & VssRay::BorderSample)
3025                                        {
3026                                                vcRays.push_back(*rit);
3027                                        }
3028                                        else if ((*rit)->mFlags & VssRay::ReverseSample)
3029                                                vcRays2.push_back(*rit);
3030                                        else
3031                                                vcRays3.push_back(*rit);
3032                                               
3033                                }
3034                        }
3035
3036                        exporter->ExportRays(vcRays, RgbColor(1, 0, 0));
3037                        exporter->ExportRays(vcRays2, RgbColor(0, 1, 0));
3038                        exporter->ExportRays(vcRays3, RgbColor(1, 1, 1));
3039                }
3040               
3041                ////////////////
3042                //-- export view cell geometry
3043
3044                exporter->SetWireframe();
3045
3046                Material m;//= RandomMaterial();
3047                m.mDiffuseColor = RgbColor(0, 1, 0);
3048                exporter->SetForcedMaterial(m);
3049
3050                ExportViewCellGeometry(exporter, vc, NULL, NULL);
3051                exporter->SetFilled();
3052
3053                if (exportPvs)
3054                {
3055                        Intersectable::NewMail();
3056                        ObjectPvsMap::const_iterator oit, oit_end = pvs.mEntries.end();
3057                       
3058                        // output PVS of view cell
3059                        for (oit = pvs.mEntries.begin(); oit != oit_end; ++ oit)
3060                        {               
3061                                Intersectable *intersect = (*oit).first;
3062                               
3063                                if (!intersect->Mailed())
3064                                {
3065                                        intersect->Mail();
3066
3067                                        m = RandomMaterial();
3068                                        exporter->SetForcedMaterial(m);
3069                                        exporter->ExportIntersectable(intersect);
3070                                }
3071                        }
3072                        cout << endl;
3073                }
3074               
3075                DEL_PTR(exporter);
3076                cout << "finished" << endl;
3077        }
3078}
3079
3080
3081void BspViewCellsManager::TestSubdivision()
3082{
3083        ViewCellContainer leaves;
3084        mViewCellsTree->CollectLeaves(mViewCellsTree->GetRoot(), leaves);
3085
3086        ViewCellContainer::const_iterator it, it_end = leaves.end();
3087
3088        const float vol = mViewSpaceBox.GetVolume();
3089        float subdivVol = 0;
3090        float newVol = 0;
3091
3092        for (it = leaves.begin(); it != it_end; ++ it)
3093        {
3094                BspNodeGeometry geom;
3095                mBspTree->ConstructGeometry(*it, geom);
3096
3097                const float lVol = geom.GetVolume();
3098                newVol += lVol;
3099                subdivVol += (*it)->GetVolume();
3100
3101                const float thres = 0.9f;
3102                if ((lVol < ((*it)->GetVolume() * thres)) ||
3103                        (lVol * thres > ((*it)->GetVolume())))
3104                        Debug << "warning: " << lVol << " " << (*it)->GetVolume() << endl;
3105        }
3106       
3107        Debug << "exact volume: " << vol << endl;
3108        Debug << "subdivision volume: " << subdivVol << endl;
3109        Debug << "new volume: " << newVol << endl;
3110}
3111
3112
3113void BspViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
3114                                                                                                 ViewCell *vc,
3115                                                                                                 const AxisAlignedBox3 *sceneBox,
3116                                                                                                 const AxisAlignedPlane *clipPlane
3117                                                                                                 ) const
3118{
3119        if (clipPlane)
3120        {
3121                const Plane3 plane = clipPlane->GetPlane();
3122
3123                ViewCellContainer leaves;
3124                mViewCellsTree->CollectLeaves(vc, leaves);
3125                ViewCellContainer::const_iterator it, it_end = leaves.end();
3126
3127                for (it = leaves.begin(); it != it_end; ++ it)
3128                {
3129                        BspNodeGeometry geom;
3130                        BspNodeGeometry front;
3131                        BspNodeGeometry back;
3132
3133                        mBspTree->ConstructGeometry(*it, geom);
3134
3135                        const float eps = 0.0001f;
3136                        const int cf = geom.Side(plane, eps);
3137
3138                        if (cf == -1)
3139                        {
3140                                exporter->ExportPolygons(geom.GetPolys());
3141                        }
3142                        else if (cf == 0)
3143                        {
3144                                geom.SplitGeometry(front,
3145                                                                   back,
3146                                                                   plane,
3147                                                                   mViewSpaceBox,
3148                                                                   eps);
3149
3150                                if (back.Valid())
3151                                {
3152                                        exporter->ExportPolygons(back.GetPolys());
3153                                }                       
3154                        }
3155                }
3156        }
3157        else
3158        {
3159                // export mesh if available
3160                // TODO: some bug here?
3161                if (1 && vc->GetMesh())
3162                {
3163                        exporter->ExportMesh(vc->GetMesh());
3164                }
3165                else
3166                {
3167                        BspNodeGeometry geom;
3168                        mBspTree->ConstructGeometry(vc, geom);
3169                        exporter->ExportPolygons(geom.GetPolys());
3170                }
3171        }
3172}
3173
3174
3175void BspViewCellsManager::CreateMesh(ViewCell *vc)
3176{
3177        // note: should previous mesh be deleted (via mesh manager?)
3178        BspNodeGeometry geom;
3179        mBspTree->ConstructGeometry(vc, geom);
3180
3181        Mesh *mesh = MeshManager::GetSingleton()->CreateResource();
3182
3183        IncludeNodeGeomInMesh(geom, *mesh);
3184        vc->SetMesh(mesh);
3185}
3186
3187
3188void BspViewCellsManager::Finalize(ViewCell *viewCell,
3189                                                                   const bool createMesh)
3190{
3191        float area = 0;
3192        float volume = 0;
3193
3194        ViewCellContainer leaves;
3195        mViewCellsTree->CollectLeaves(viewCell, leaves);
3196
3197        ViewCellContainer::const_iterator it, it_end = leaves.end();
3198
3199    for (it = leaves.begin(); it != it_end; ++ it)
3200        {
3201                BspNodeGeometry geom;
3202
3203                mBspTree->ConstructGeometry(*it, geom);
3204
3205                const float lVol = geom.GetVolume();
3206                const float lArea = geom.GetArea();
3207
3208                area += lArea;
3209                volume += lVol;
3210       
3211                CreateMesh(*it);
3212        }
3213
3214        viewCell->SetVolume(volume);
3215        viewCell->SetArea(area);
3216}
3217
3218
3219ViewCell *BspViewCellsManager::GetViewCell(const Vector3 &point, const bool active) const
3220{
3221        if (!ViewCellsConstructed())
3222        {
3223                return NULL;
3224        }
3225        if (!mViewSpaceBox.IsInside(point))
3226        {
3227                return NULL;
3228        }
3229        return mBspTree->GetViewCell(point);
3230}
3231
3232
3233void BspViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays,
3234                                                                                                 vector<MergeCandidate> &candidates)
3235{
3236        cout << "collecting merge candidates ... " << endl;
3237
3238        if (mUseRaysForMerge)
3239        {
3240                mBspTree->CollectMergeCandidates(rays, candidates);
3241        }
3242        else
3243        {
3244                vector<BspLeaf *> leaves;
3245                mBspTree->CollectLeaves(leaves);
3246                mBspTree->CollectMergeCandidates(leaves, candidates);
3247        }
3248
3249        cout << "fininshed collecting candidates" << endl;
3250}
3251
3252
3253
3254bool BspViewCellsManager::ExportViewCells(const string filename,
3255                                                                                  const bool exportPvs,
3256                                                                                  const ObjectContainer &objects)
3257{
3258        if (!ViewCellsConstructed() || !ViewCellsTreeConstructed())
3259        {
3260                return false;
3261        }
3262
3263        cout << "exporting view cells to xml ... ";
3264
3265        OUT_STREAM stream(filename.c_str());
3266
3267        // for output we need unique ids for each view cell
3268        CreateUniqueViewCellIds();
3269
3270        stream << "<?xml version=\"1.0\" encoding=\"UTF-8\"?>"<<endl;
3271        stream << "<VisibilitySolution>" << endl;
3272
3273        if (exportPvs)
3274        {
3275                //////////
3276                //-- export bounding boxes: they are used to identify the objects from the pvs and
3277                //-- assign them to the entities in the rendering engine
3278
3279                stream << "<BoundingBoxes>" << endl;
3280                ObjectContainer::const_iterator oit, oit_end = objects.end();
3281
3282                for (oit = objects.begin(); oit != oit_end; ++ oit)
3283                {
3284                        const AxisAlignedBox3 box = (*oit)->GetBox();
3285                       
3286                        stream << "<BoundingBox" << " id=\"" << (*oit)->GetId() << "\""
3287                                   << " min=\"" << box.Min().x << " " << box.Min().y << " " << box.Min().z << "\""
3288                                   << " max=\"" << box.Max().x << " " << box.Max().y << " " << box.Max().z << "\" />" << endl;
3289                }
3290
3291                stream << "</BoundingBoxes>" << endl;
3292        }
3293
3294        ///////////
3295        //-- export the view cells and the pvs
3296
3297        const int numViewCells = mCurrentViewCellsStats.viewCells;
3298        stream << "<ViewCells number=\"" << numViewCells << "\" >" << endl;
3299
3300        mViewCellsTree->Export(stream, exportPvs);
3301       
3302        stream << "</ViewCells>" << endl;
3303
3304        /////////////
3305        //-- export the view space hierarchy
3306        stream << "<ViewSpaceHierarchy type=\"bsp\""
3307                   << " min=\"" << mViewSpaceBox.Min().x << " " << mViewSpaceBox.Min().y << " " << mViewSpaceBox.Min().z << "\""
3308                   << " max=\"" << mViewSpaceBox.Max().x << " " << mViewSpaceBox.Max().y << " " << mViewSpaceBox.Max().z << "\">" << endl;
3309
3310        mBspTree->Export(stream);
3311
3312        // end tags
3313        stream << "</ViewSpaceHierarchy>" << endl;
3314        stream << "</VisibilitySolution>" << endl;
3315
3316        stream.close();
3317        cout << "finished" << endl;
3318
3319        return true;
3320}
3321
3322
3323ViewCell *BspViewCellsManager::ConstructDummyMergeTree(BspNode *root)
3324{
3325        ViewCellInterior *vcRoot = new ViewCellInterior();
3326               
3327        // evaluate merge cost for priority traversal
3328        const float mergeCost = 1.0f / (float)root->mTimeStamp;
3329        vcRoot->SetMergeCost(mergeCost);
3330
3331        float volume = 0;
3332        vector<BspLeaf *> leaves;
3333        mBspTree->CollectLeaves(leaves);
3334        vector<BspLeaf *>::const_iterator lit, lit_end = leaves.end();
3335        ViewCell::NewMail();
3336
3337        for (lit = leaves.begin(); lit != lit_end; ++ lit)
3338        {
3339                BspLeaf *leaf = *lit;
3340                ViewCell *vc = leaf->GetViewCell();
3341
3342                if (!vc->Mailed())
3343                {
3344                        vc->Mail();
3345                        vc->SetMergeCost(0.0f);
3346                        vcRoot->SetupChildLink(vc);
3347
3348                        volume += vc->GetVolume();
3349                        volume += vc->GetVolume();     
3350                        vcRoot->SetVolume(volume);
3351                }
3352        }
3353       
3354        return vcRoot;
3355}
3356
3357
3358ViewCell *BspViewCellsManager::ConstructSpatialMergeTree(BspNode *root)
3359{
3360        // terminate recursion
3361        if (root->IsLeaf())
3362        {
3363                BspLeaf *leaf = dynamic_cast<BspLeaf *>(root);
3364                leaf->GetViewCell()->SetMergeCost(0.0f);
3365                return leaf->GetViewCell();
3366        }
3367       
3368        BspInterior *interior = dynamic_cast<BspInterior *>(root);
3369        ViewCellInterior *viewCellInterior = new ViewCellInterior();
3370               
3371        // evaluate merge cost for priority traversal
3372        float mergeCost = 1.0f / (float)root->mTimeStamp;
3373        viewCellInterior->SetMergeCost(mergeCost);
3374
3375        float volume = 0;
3376       
3377        BspNode *front = interior->GetFront();
3378        BspNode *back = interior->GetBack();
3379
3380
3381        ////////////
3382        //-- recursivly compute child hierarchies
3383
3384        ViewCell *backVc = ConstructSpatialMergeTree(back);
3385        ViewCell *frontVc = ConstructSpatialMergeTree(front);
3386
3387        viewCellInterior->SetupChildLink(backVc);
3388        viewCellInterior->SetupChildLink(frontVc);
3389
3390        volume += backVc->GetVolume();
3391        volume += frontVc->GetVolume();
3392
3393        viewCellInterior->SetVolume(volume);
3394
3395        return viewCellInterior;
3396}
3397
3398
3399/************************************************************************/
3400/*                   KdViewCellsManager implementation                  */
3401/************************************************************************/
3402
3403
3404
3405KdViewCellsManager::KdViewCellsManager(ViewCellsTree *vcTree, KdTree *kdTree):
3406ViewCellsManager(vcTree), mKdTree(kdTree), mKdPvsDepth(100)
3407{
3408}
3409
3410
3411float KdViewCellsManager::GetProbability(ViewCell *viewCell)
3412{
3413        // compute view cell area / volume as subsititute for probability
3414        if (0)
3415                return GetArea(viewCell) / GetViewSpaceBox().SurfaceArea();
3416        else
3417                return GetVolume(viewCell) / GetViewSpaceBox().GetVolume();
3418}
3419
3420
3421
3422
3423void KdViewCellsManager::CollectViewCells()
3424{
3425        //mKdTree->CollectViewCells(mViewCells); TODO
3426}
3427
3428
3429int KdViewCellsManager::ConstructSubdivision(const ObjectContainer &objects,
3430                                                                  const VssRayContainer &rays)
3431{
3432        // if view cells already constructed
3433        if (ViewCellsConstructed())
3434                return 0;
3435
3436        mKdTree->Construct();
3437
3438        mTotalAreaValid = false;
3439        // create the view cells
3440        mKdTree->CreateAndCollectViewCells(mViewCells);
3441        // cast rays
3442        ComputeSampleContributions(rays, true, false);
3443
3444        EvaluateViewCellsStats();
3445        Debug << "\nView cells after construction:\n" << mCurrentViewCellsStats << endl;
3446
3447        return 0;
3448}
3449
3450
3451bool KdViewCellsManager::ViewCellsConstructed() const
3452{
3453        return mKdTree->GetRoot() != NULL;
3454}
3455
3456
3457int KdViewCellsManager::PostProcess(const ObjectContainer &objects,
3458                                                                        const VssRayContainer &rays)
3459{
3460        return 0;
3461}
3462
3463
3464void KdViewCellsManager::ExportSingleViewCells(const ObjectContainer &objects,
3465                                                                                           const int maxViewCells,
3466                                                                                           const bool sortViewCells,
3467                                                                                           const bool exportPvs,
3468                                                                                           const bool exportRays,
3469                                                                                           const int maxRays,
3470                                                                                           const string prefix,
3471                                                                                           VssRayContainer *visRays)
3472{
3473        // TODO
3474}
3475
3476
3477void KdViewCellsManager::Visualize(const ObjectContainer &objects,
3478                                                                   const VssRayContainer &sampleRays)
3479{
3480        if (!ViewCellsConstructed())
3481                return;
3482
3483        // using view cells instead of the kd PVS of objects
3484        const bool useViewCells = true;
3485        bool exportRays = false;
3486
3487        int limit = min(mVisualizationSamples, (int)sampleRays.size());
3488        const int pvsOut = min((int)objects.size(), 10);
3489        VssRayContainer *rays = new VssRayContainer[pvsOut];
3490
3491        if (useViewCells)
3492        {
3493                const int leafOut = 10;
3494
3495                ViewCell::NewMail();
3496
3497                //-- some rays for output
3498                const int raysOut = min((int)sampleRays.size(), mVisualizationSamples);
3499                Debug << "visualization using " << raysOut << " samples" << endl;
3500
3501                //-- some random view cells and rays for output
3502                vector<KdLeaf *> kdLeaves;
3503
3504                for (int i = 0; i < leafOut; ++ i)
3505                        kdLeaves.push_back(dynamic_cast<KdLeaf *>(mKdTree->GetRandomLeaf()));
3506
3507                for (int i = 0; i < kdLeaves.size(); ++ i)
3508                {
3509                        KdLeaf *leaf = kdLeaves[i];
3510                        RayContainer vcRays;
3511
3512                        cout << "creating output for view cell " << i << " ... ";
3513#if 0
3514                        // check whether we can add the current ray to the output rays
3515                        for (int k = 0; k < raysOut; ++ k)
3516                        {
3517                                Ray *ray = sampleRays[k];
3518
3519                                for (int j = 0; j < (int)ray->bspIntersections.size(); ++ j)
3520                                {
3521                                        BspLeaf *leaf2 = ray->bspIntersections[j].mLeaf;
3522
3523                                        if (leaf->GetViewCell() == leaf2->GetViewCell())
3524                                        {
3525                                                vcRays.push_back(ray);
3526                                        }
3527                                }
3528                        }
3529#endif
3530                        Intersectable::NewMail();
3531
3532                        ViewCell *vc = leaf->mViewCell;
3533                        char str[64]; sprintf(str, "viewcell%04d.wrl", i);
3534
3535                        Exporter *exporter = Exporter::GetExporter(str);
3536                        exporter->SetFilled();
3537
3538                        exporter->SetWireframe();
3539                        //exporter->SetFilled();
3540
3541                        Material m;//= RandomMaterial();
3542                        m.mDiffuseColor = RgbColor(1, 1, 0);
3543                        exporter->SetForcedMaterial(m);
3544
3545                        AxisAlignedBox3 box = mKdTree->GetBox(leaf);
3546                        exporter->ExportBox(box);
3547
3548                        // export rays piercing this view cell
3549                        exporter->ExportRays(vcRays, 1000, RgbColor(0, 1, 0));
3550
3551                        m.mDiffuseColor = RgbColor(1, 0, 0);
3552                        exporter->SetForcedMaterial(m);
3553
3554                        // exporter->SetWireframe();
3555                        exporter->SetFilled();
3556
3557                        ObjectPvsMap::iterator it, it_end = vc->GetPvs().mEntries.end();
3558                        // -- output PVS of view cell
3559                        for (it = vc->GetPvs().mEntries.begin(); it != it_end; ++ it)
3560                        {
3561                                Intersectable *intersect = (*it).first;
3562                                if (!intersect->Mailed())
3563                                {
3564                                        exporter->ExportIntersectable(intersect);
3565                                        intersect->Mail();
3566                                }
3567                        }
3568
3569                        DEL_PTR(exporter);
3570                        cout << "finished" << endl;
3571                }
3572
3573                DEL_PTR(rays);
3574        }
3575        else // using kd PVS of objects
3576        {
3577                for (int i = 0; i < limit; ++ i)
3578                {
3579                        VssRay *ray = sampleRays[i];
3580
3581                        // check whether we can add this to the rays
3582                        for (int j = 0; j < pvsOut; j++)
3583                        {
3584                                if (objects[j] == ray->mTerminationObject)
3585                                {
3586                                        rays[j].push_back(ray);
3587                                }
3588                        }
3589                }
3590
3591                if (exportRays)
3592                {
3593                        Exporter *exporter = NULL;
3594                        exporter = Exporter::GetExporter("sample-rays.x3d");
3595                        exporter->SetWireframe();
3596                        exporter->ExportKdTree(*mKdTree);
3597
3598                        for (i = 0; i < pvsOut; i++)
3599                                exporter->ExportRays(rays[i], RgbColor(1, 0, 0));
3600
3601                        exporter->SetFilled();
3602                        delete exporter;
3603                }
3604
3605                for (int k=0; k < pvsOut; k++)
3606                {
3607                        Intersectable *object = objects[k];
3608                        char str[64]; sprintf(str, "viewcell%04d.wrl", i);
3609
3610                        Exporter *exporter = Exporter::GetExporter(str);
3611                        exporter->SetWireframe();
3612
3613                        KdPvsMap::iterator kit = object->mKdPvs.mEntries.begin();
3614                        Intersectable::NewMail();
3615
3616                        // avoid adding the object to the list
3617                        object->Mail();
3618                        ObjectContainer visibleObjects;
3619
3620                        for (; kit != object->mKdPvs.mEntries.end(); i++)
3621                        {
3622                                KdNode *node = (*kit).first;
3623                                exporter->ExportBox(mKdTree->GetBox(node));
3624
3625                                mKdTree->CollectObjects(node, visibleObjects);
3626                        }
3627
3628                        exporter->ExportRays(rays[k],  RgbColor(0, 1, 0));
3629                        exporter->SetFilled();
3630
3631                        for (int j = 0; j < visibleObjects.size(); j++)
3632                                exporter->ExportIntersectable(visibleObjects[j]);
3633
3634                        Material m;
3635                        m.mDiffuseColor = RgbColor(1, 0, 0);
3636                        exporter->SetForcedMaterial(m);
3637                        exporter->ExportIntersectable(object);
3638
3639                        delete exporter;
3640                }
3641        }
3642}
3643
3644
3645ViewCell *KdViewCellsManager::GenerateViewCell(Mesh *mesh) const
3646{
3647        return new KdViewCell(mesh);
3648}
3649
3650
3651void KdViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
3652                                                                                                ViewCell *vc,
3653                                                                                                const AxisAlignedBox3 *sceneBox,
3654                                                                                                const AxisAlignedPlane *clipPlane
3655                                                                                                ) const
3656{
3657        ViewCellContainer leaves;
3658        mViewCellsTree->CollectLeaves(vc, leaves);
3659        ViewCellContainer::const_iterator it, it_end = leaves.end();
3660
3661        for (it = leaves.begin(); it != it_end; ++ it)
3662        {
3663                KdViewCell *kdVc = dynamic_cast<KdViewCell *>(*it);
3664                exporter->ExportBox(mKdTree->GetBox(kdVc->mLeaves[0]));
3665        }
3666}
3667
3668
3669int KdViewCellsManager::GetType() const
3670{
3671        return ViewCellsManager::KD;
3672}
3673
3674
3675
3676KdNode *KdViewCellsManager::GetNodeForPvs(KdLeaf *leaf)
3677{
3678        KdNode *node = leaf;
3679
3680        while (node->mParent && node->mDepth > mKdPvsDepth)
3681                node = node->mParent;
3682
3683        return node;
3684}
3685
3686int KdViewCellsManager::CastLineSegment(const Vector3 &origin,
3687                                                                                const Vector3 &termination,
3688                                                                                ViewCellContainer &viewcells)
3689{
3690        return mKdTree->CastLineSegment(origin, termination, viewcells);
3691}
3692
3693
3694void KdViewCellsManager::CreateMesh(ViewCell *vc)
3695{
3696        // TODO
3697}
3698
3699
3700
3701void KdViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays,
3702                                                                                                vector<MergeCandidate> &candidates)
3703{
3704        // TODO
3705}
3706
3707
3708
3709/**************************************************************************/
3710/*                   VspBspViewCellsManager implementation                */
3711/**************************************************************************/
3712
3713
3714VspBspViewCellsManager::VspBspViewCellsManager(ViewCellsTree *vcTree, VspBspTree *vspBspTree):
3715ViewCellsManager(vcTree), mVspBspTree(vspBspTree)
3716{
3717        Environment::GetSingleton()->GetIntValue("VspBspTree.Construction.samples", mInitialSamples);
3718        mVspBspTree->SetViewCellsManager(this);
3719        mVspBspTree->mViewCellsTree = mViewCellsTree;
3720}
3721
3722
3723VspBspViewCellsManager::~VspBspViewCellsManager()
3724{
3725}
3726
3727
3728float VspBspViewCellsManager::GetProbability(ViewCell *viewCell)
3729{
3730        if (0 && mVspBspTree->mUseAreaForPvs)
3731                return GetArea(viewCell) / GetAccVcArea();
3732        else
3733                return GetVolume(viewCell) / mViewSpaceBox.GetVolume();
3734}
3735
3736
3737void VspBspViewCellsManager::CollectViewCells()
3738{
3739        // view cells tree constructed?
3740        if (!ViewCellsTreeConstructed())
3741        {
3742                mVspBspTree->CollectViewCells(mViewCells, false);
3743        }
3744        else
3745        {       
3746                // we can use the view cells tree hierarchy to get the right set
3747                mViewCellsTree->CollectBestViewCellSet(mViewCells, mNumActiveViewCells);
3748        }
3749}
3750
3751
3752void VspBspViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays,
3753                                                                                                        vector<MergeCandidate> &candidates)
3754{       
3755        cout << "collecting merge candidates ... " << endl;
3756
3757        if (mUseRaysForMerge)
3758        {
3759                mVspBspTree->CollectMergeCandidates(rays, candidates);
3760        }
3761        else
3762        {
3763                vector<BspLeaf *> leaves;
3764                mVspBspTree->CollectLeaves(leaves);
3765       
3766                mVspBspTree->CollectMergeCandidates(leaves, candidates);
3767        }
3768
3769        cout << "fininshed collecting candidates" << endl;
3770}
3771
3772
3773bool VspBspViewCellsManager::ViewCellsConstructed() const
3774{
3775        return mVspBspTree->GetRoot() != NULL;
3776}
3777
3778
3779ViewCell *VspBspViewCellsManager::GenerateViewCell(Mesh *mesh) const
3780{
3781        return new BspViewCell(mesh);
3782}
3783
3784
3785int VspBspViewCellsManager::ConstructSubdivision(const ObjectContainer &objects,
3786                                                                                                 const VssRayContainer &rays)
3787{
3788        mMaxPvsSize = (int)(mMaxPvsRatio * (float)objects.size());
3789
3790        // if view cells were already constructed
3791        if (ViewCellsConstructed())
3792        {
3793                return 0;
3794        }
3795
3796        int sampleContributions = 0;
3797        VssRayContainer sampleRays;
3798
3799        const int limit = min(mInitialSamples, (int)rays.size());
3800
3801        Debug << "samples used for vsp bsp subdivision: " << mInitialSamples
3802                  << ", actual rays: " << (int)rays.size() << endl;
3803
3804        VssRayContainer savedRays;
3805
3806        if (SAMPLE_AFTER_SUBDIVISION)
3807        {
3808                VssRayContainer constructionRays;
3809               
3810                GetRaySets(rays, mInitialSamples, constructionRays, &savedRays);
3811
3812                Debug << "rays used for initial construction: " << (int)constructionRays.size() << endl;
3813                Debug << "rays saved for later use: " << (int)savedRays.size() << endl;
3814       
3815                mVspBspTree->Construct(constructionRays, &mViewSpaceBox);
3816        }
3817        else
3818        {
3819                Debug << "rays used for initial construction: " << (int)rays.size() << endl;
3820                mVspBspTree->Construct(rays, &mViewSpaceBox);
3821        }
3822
3823        // collapse invalid regions
3824        cout << "collapsing invalid tree regions ... ";
3825        long startTime = GetTime();
3826
3827        const int collapsedLeaves = mVspBspTree->CollapseTree();
3828        Debug << "collapsed in " << TimeDiff(startTime, GetTime()) * 1e-3
3829                  << " seconds" << endl;
3830
3831    cout << "finished" << endl;
3832
3833        /////////////////
3834        //-- stats after construction
3835
3836        Debug << mVspBspTree->GetStatistics() << endl;
3837
3838        ResetViewCells();
3839        Debug << "\nView cells after construction:\n" << mCurrentViewCellsStats << endl;
3840
3841
3842        //////////////////////
3843        //-- recast the rest of the rays
3844
3845        startTime = GetTime();
3846
3847        cout << "Computing remaining ray contributions ... ";
3848
3849        if (SAMPLE_AFTER_SUBDIVISION)
3850                ComputeSampleContributions(savedRays, true, false);
3851
3852        cout << "finished" << endl;
3853
3854        Debug << "Computed remaining ray contribution in " << TimeDiff(startTime, GetTime()) * 1e-3
3855                  << " secs" << endl;
3856
3857        cout << "construction finished" << endl;
3858
3859        if (0)
3860        {       ////////
3861                //-- real meshes are contructed at this stage
3862                cout << "finalizing view cells ... ";
3863                FinalizeViewCells(true);
3864                cout << "finished" << endl;
3865        }
3866
3867        return sampleContributions;
3868}
3869
3870
3871void VspBspViewCellsManager::MergeViewCells(const VssRayContainer &rays,
3872                                                                                        const ObjectContainer &objects)
3873{
3874    int vcSize = 0;
3875        int pvsSize = 0;
3876
3877        //-- merge view cells
3878        cout << "starting merge using " << mPostProcessSamples << " samples ... " << endl;
3879        long startTime = GetTime();
3880
3881
3882        if (mMergeViewCells)
3883        {
3884                // TODO: should be done BEFORE the ray casting
3885                // compute tree by merging the nodes based on cost heuristics
3886                mViewCellsTree->ConstructMergeTree(rays, objects);
3887        }
3888        else
3889        {
3890                // compute tree by merging the nodes of the spatial hierarchy
3891                ViewCell *root = ConstructSpatialMergeTree(mVspBspTree->GetRoot());
3892                mViewCellsTree->SetRoot(root);
3893
3894                // compute pvs
3895                ObjectPvs pvs;
3896                UpdatePvsForEvaluation(root, pvs);
3897        }
3898
3899        if (1)
3900        {
3901                char mstats[100];
3902                ObjectPvs pvs;
3903
3904                Environment::GetSingleton()->GetStringValue("ViewCells.mergeStats", mstats);
3905                mViewCellsTree->ExportStats(mstats);
3906        }
3907
3908        cout << "merged view cells in "
3909                 << TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl;
3910
3911        Debug << "Postprocessing: Merged view cells in "
3912                  << TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl << endl;
3913       
3914
3915        //////////////////
3916        //-- stats and visualizations
3917
3918        int savedColorCode = mColorCode;
3919       
3920        // get currently active view cell set
3921        ResetViewCells();
3922        Debug << "\nView cells after merge:\n" << mCurrentViewCellsStats << endl;
3923       
3924        if (mShowVisualization) // export merged view cells
3925        {
3926                mColorCode = 0;
3927                Exporter *exporter = Exporter::GetExporter("merged_view_cells.wrl");
3928               
3929                cout << "exporting view cells after merge ... ";
3930
3931                if (exporter)
3932                {
3933                        if (0)
3934                                exporter->SetWireframe();
3935                        else
3936                                exporter->SetFilled();
3937
3938                        ExportViewCellsForViz(exporter, NULL, GetClipPlane());
3939
3940                        if (mExportGeometry)
3941                        {
3942                                Material m;
3943                                m.mDiffuseColor = RgbColor(0, 1, 0);
3944                                exporter->SetForcedMaterial(m);
3945                                exporter->SetFilled();
3946
3947                                exporter->ExportGeometry(objects);
3948                        }
3949
3950                        delete exporter;
3951                }
3952                cout << "finished" << endl;
3953        }
3954
3955        if (mShowVisualization)
3956        {
3957                // use pvs size for color coding
3958                mColorCode = 1;
3959                Exporter *exporter = Exporter::GetExporter("merged_view_cells_pvs.wrl");
3960
3961                cout << "exporting view cells after merge (pvs size) ... ";     
3962
3963                if (exporter)
3964                {
3965                        exporter->SetFilled();
3966
3967                        ExportViewCellsForViz(exporter, NULL, GetClipPlane());
3968
3969                        if (mExportGeometry)
3970                        {
3971                                Material m;
3972                                m.mDiffuseColor = RgbColor(0, 1, 0);
3973                                exporter->SetForcedMaterial(m);
3974                                exporter->SetFilled();
3975
3976                                exporter->ExportGeometry(objects);
3977                        }
3978
3979                        delete exporter;
3980                }
3981                cout << "finished" << endl;
3982        }
3983
3984        mColorCode = savedColorCode;
3985}
3986
3987
3988void VspBspViewCellsManager::RefineViewCells(const VssRayContainer &rays,
3989                                                                                         const ObjectContainer &objects)
3990{
3991        mRenderer->RenderScene();
3992
3993        SimulationStatistics ss;
3994        dynamic_cast<RenderSimulator *>(mRenderer)->GetStatistics(ss);
3995    Debug << "render time before refine\n\n" << ss << endl;
3996
3997        const long startTime = GetTime();
3998        cout << "Refining the merged view cells ... ";
3999
4000        // refining the merged view cells
4001        const int refined = mViewCellsTree->RefineViewCells(rays, objects);
4002
4003        //-- stats and visualizations
4004        cout << "finished" << endl;
4005        cout << "refined " << refined << " view cells in "
4006                 << TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl;
4007
4008        Debug << "Postprocessing: refined " << refined << " view cells in "
4009                  << TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl << endl;
4010}
4011
4012
4013int VspBspViewCellsManager::PostProcess(const ObjectContainer &objects,
4014                                                                                const VssRayContainer &rays)
4015{
4016        if (!ViewCellsConstructed())
4017        {
4018                Debug << "postprocess error: no view cells constructed" << endl;
4019                return 0;
4020        }
4021
4022        // view cells already finished before post processing step
4023        // (i.e. because they were loaded)
4024        if (mViewCellsFinished)
4025        {
4026                FinalizeViewCells(true);
4027                EvaluateViewCellsStats();
4028
4029                return 0;
4030        }
4031
4032        // check if new view cells turned invalid
4033        int minPvs, maxPvs;
4034
4035        if (0)
4036        {
4037                minPvs = mMinPvsSize;
4038                maxPvs = mMaxPvsSize;
4039        }
4040        else
4041        {
4042                // problem matt: why did I start here from zero?
4043                minPvs = 0;
4044                maxPvs = mMaxPvsSize;
4045        }
4046
4047        Debug << "setting validity, min: " << minPvs << " max: " << maxPvs << endl;
4048        cout << "setting validity, min: " << minPvs << " max: " << maxPvs << endl;
4049       
4050        SetValidity(minPvs, maxPvs);
4051
4052        // update valid view space according to valid view cells
4053        if (0) mVspBspTree->ValidateTree();
4054
4055        // area has to be recomputed
4056        mTotalAreaValid = false;
4057        VssRayContainer postProcessRays;
4058        GetRaySets(rays, mPostProcessSamples, postProcessRays);
4059
4060        Debug << "post processing using " << (int)postProcessRays.size() << " samples" << endl;
4061
4062        // should maybe be done here to allow merge working
4063        // with area or volume and to correct the rendering statistics
4064        if (0) FinalizeViewCells(false);
4065               
4066        //////////
4067        //-- merge the individual view cells
4068        MergeViewCells(postProcessRays, objects);
4069       
4070        // refines the merged view cells
4071        if (0) RefineViewCells(postProcessRays, objects);
4072
4073
4074        ///////////
4075        //-- render simulation after merge + refine
4076
4077        cout << "\nview cells partition render time before compress" << endl << endl;;
4078        dynamic_cast<RenderSimulator *>(mRenderer)->RenderScene();
4079        SimulationStatistics ss;
4080        dynamic_cast<RenderSimulator *>(mRenderer)->GetStatistics(ss);
4081        cout << ss << endl;
4082       
4083
4084        ////////////
4085        //-- compression
4086//#if HAS_TO_BE_REDONE
4087        if (ViewCellsTreeConstructed() && mCompressViewCells)
4088        {
4089                int pvsEntries = mViewCellsTree->CountStoredPvsEntries(mViewCellsTree->GetRoot());
4090                Debug << "number of entries before compress: " << pvsEntries << endl;
4091
4092                mViewCellsTree->SetViewCellsStorage(ViewCellsTree::COMPRESSED);
4093
4094                pvsEntries = mViewCellsTree->CountStoredPvsEntries(mViewCellsTree->GetRoot());
4095                Debug << "number of entries after compress: " << pvsEntries << endl;
4096        }
4097//#endif
4098
4099        // collapse sibling leaves that share the same view cell
4100        if (0) mVspBspTree->CollapseTree();
4101
4102        // recompute view cell list and statistics
4103        ResetViewCells();
4104
4105        // compute final meshes and volume / area
4106        if (1) FinalizeViewCells(true);
4107
4108        // write view cells to disc
4109        if (1 && mExportViewCells)
4110        {
4111                char filename[100];
4112                Environment::GetSingleton()->GetStringValue("ViewCells.filename", filename);
4113                ExportViewCells(filename, mExportPvs, objects);
4114        }
4115
4116        return 0;
4117}
4118
4119
4120int VspBspViewCellsManager::GetType() const
4121{
4122        return VSP_BSP;
4123}
4124
4125
4126ViewCell *VspBspViewCellsManager::ConstructSpatialMergeTree(BspNode *root)
4127{
4128        // terminate recursion
4129        if (root->IsLeaf())
4130        {
4131                BspLeaf *leaf = dynamic_cast<BspLeaf *>(root);
4132                leaf->GetViewCell()->SetMergeCost(0.0f);
4133                return leaf->GetViewCell();
4134        }
4135       
4136       
4137        BspInterior *interior = dynamic_cast<BspInterior *>(root);
4138        ViewCellInterior *viewCellInterior = new ViewCellInterior();
4139               
4140        // evaluate merge cost for priority traversal
4141        float mergeCost = 1.0f / (float)root->mTimeStamp;
4142        viewCellInterior->SetMergeCost(mergeCost);
4143
4144        float volume = 0;
4145       
4146        BspNode *front = interior->GetFront();
4147        BspNode *back = interior->GetBack();
4148
4149
4150        ObjectPvs frontPvs, backPvs;
4151
4152        //-- recursivly compute child hierarchies
4153        ViewCell *backVc = ConstructSpatialMergeTree(back);
4154        ViewCell *frontVc = ConstructSpatialMergeTree(front);
4155
4156
4157        viewCellInterior->SetupChildLink(backVc);
4158        viewCellInterior->SetupChildLink(frontVc);
4159
4160        volume += backVc->GetVolume();
4161        volume += frontVc->GetVolume();
4162
4163        viewCellInterior->SetVolume(volume);
4164
4165        return viewCellInterior;
4166}
4167
4168
4169bool VspBspViewCellsManager::GetViewPoint(Vector3 &viewPoint) const
4170{
4171        if (!ViewCellsConstructed())
4172                return ViewCellsManager::GetViewPoint(viewPoint);
4173
4174        // TODO: set reasonable limit
4175        const int limit = 20;
4176
4177        for (int i = 0; i < limit; ++ i)
4178        {
4179                viewPoint = mViewSpaceBox.GetRandomPoint();
4180                if (mVspBspTree->ViewPointValid(viewPoint))
4181                {
4182                        return true;
4183                }
4184        }
4185
4186        Debug << "failed to find valid view point, taking " << viewPoint << endl;
4187        return false;
4188}
4189
4190
4191bool VspBspViewCellsManager::ViewPointValid(const Vector3 &viewPoint) const
4192{
4193        // $$JB -> implemented in viewcellsmanager (slower, but allows dynamic
4194        // validy update in preprocessor for all managers)
4195        return ViewCellsManager::ViewPointValid(viewPoint);
4196
4197        //      return mViewSpaceBox.IsInside(viewPoint) &&
4198        //                 mVspBspTree->ViewPointValid(viewPoint);
4199}
4200
4201
4202void VspBspViewCellsManager::Visualize(const ObjectContainer &objects,
4203                                                                           const VssRayContainer &sampleRays)
4204{
4205        if (!ViewCellsConstructed())
4206                return;
4207
4208        VssRayContainer visRays;
4209        GetRaySets(sampleRays, mVisualizationSamples, visRays);
4210       
4211        if (1)
4212        {       
4213                //////////////////
4214                //-- export final view cell partition
4215
4216                Exporter *exporter = Exporter::GetExporter("final_view_cells.wrl");
4217               
4218                if (exporter)
4219                {
4220                        cout << "exporting view cells after post process ... ";
4221                        if (0)
4222                        {       // export view space box
4223                                exporter->SetWireframe();
4224                                exporter->ExportBox(mViewSpaceBox);
4225                                exporter->SetFilled();
4226                        }
4227
4228                        Material m;
4229                        m.mDiffuseColor.r = 0.0f;
4230                        m.mDiffuseColor.g = 0.5f;
4231                        m.mDiffuseColor.b = 0.5f;
4232
4233            exporter->SetForcedMaterial(m);
4234
4235                        if (1 && mExportGeometry)
4236                        {
4237                                exporter->ExportGeometry(objects);
4238                        }
4239
4240                        if (0 && mExportRays)
4241                        {
4242                                exporter->ExportRays(visRays, RgbColor(1, 0, 0));
4243                        }
4244                        ExportViewCellsForViz(exporter, NULL, GetClipPlane());
4245
4246                        delete exporter;
4247                        cout << "finished" << endl;
4248                }
4249        }
4250
4251        ////////////////
4252        //-- visualization of the BSP splits
4253
4254        bool exportSplits = false;
4255        Environment::GetSingleton()->GetBoolValue("VspBspTree.Visualization.exportSplits", exportSplits);
4256
4257        if (exportSplits)
4258        {
4259                cout << "exporting splits ... ";
4260                ExportSplits(objects, visRays);
4261                cout << "finished" << endl;
4262        }
4263
4264        ////////
4265        //-- export single view cells
4266       
4267        int leafOut;
4268        Environment::GetSingleton()->GetIntValue("ViewCells.Visualization.maxOutput", leafOut);
4269        const int raysOut = 100;
4270       
4271        ExportSingleViewCells(objects, leafOut, false, true, false, raysOut, "");
4272}
4273
4274
4275void VspBspViewCellsManager::ExportSplits(const ObjectContainer &objects,
4276                                                                                  const VssRayContainer &rays)
4277{
4278        Exporter *exporter = Exporter::GetExporter("bsp_splits.x3d");
4279
4280        if (exporter)
4281        {
4282                Material m;
4283                m.mDiffuseColor = RgbColor(1, 0, 0);
4284                exporter->SetForcedMaterial(m);
4285                exporter->SetWireframe();
4286
4287                exporter->ExportBspSplits(*mVspBspTree, true);
4288
4289                // take forced material, else big scenes cannot be viewed
4290                m.mDiffuseColor = RgbColor(0, 1, 0);
4291                exporter->SetForcedMaterial(m);
4292                exporter->SetFilled();
4293
4294                exporter->ResetForcedMaterial();
4295
4296                // export rays
4297                if (mExportRays)
4298                {
4299                        exporter->ExportRays(rays, RgbColor(1, 1, 0));
4300                }
4301
4302                if (mExportGeometry)
4303                {
4304                        exporter->ExportGeometry(objects);
4305                }
4306                delete exporter;
4307        }
4308}
4309
4310
4311void VspBspViewCellsManager::ExportSingleViewCells(const ObjectContainer &objects,
4312                                                                                                   const int maxViewCells,
4313                                                                                                   const bool sortViewCells,
4314                                                                                                   const bool exportPvs,
4315                                                                                                   const bool exportRays,
4316                                                                                                   const int maxRays,
4317                                                                                                   const string prefix,
4318                                                                                                   VssRayContainer *visRays)
4319{       
4320        if (sortViewCells)
4321        {
4322                // sort view cells to visualize the largest view cells
4323                stable_sort(mViewCells.begin(), mViewCells.end(), ViewCell::LargerRenderCost);
4324        }
4325
4326        //////////
4327        //-- some view cells for output
4328
4329        ViewCell::NewMail();
4330        const int limit = min(maxViewCells, (int)mViewCells.size());
4331       
4332        for (int i = 0; i < limit; ++ i)
4333        {
4334                cout << "creating output for view cell " << i << " ... ";
4335
4336                ViewCell *vc = sortViewCells ? // largest view cell pvs first?
4337                        mViewCells[(int)RandomValue(0, (float)mViewCells.size() - 0.5f)] : mViewCells[i];
4338
4339                if (vc->Mailed() || vc->GetId() == OUT_OF_BOUNDS_ID)
4340                        continue;
4341
4342                vc->Mail();
4343
4344                ObjectPvs pvs;
4345                mViewCellsTree->GetPvs(vc, pvs);
4346
4347                char s[64]; sprintf(s, "%sviewcell%04d.wrl", prefix.c_str(), i);
4348                Exporter *exporter = Exporter::GetExporter(s);
4349               
4350                const int pvsSize = (int)mViewCellsTree->GetPvsSize(vc);
4351                cout << "view cell " << vc->GetId() << ": pvs size=" << pvsSize << endl;
4352
4353                if (exportRays)
4354                {
4355                        ////////////
4356                        //-- export rays piercing this view cell
4357
4358                        // take rays stored with the view cells during subdivision
4359                        VssRayContainer vcRays;
4360            VssRayContainer collectRays;
4361
4362                        // collect initial view cells
4363                        ViewCellContainer leaves;
4364                        mViewCellsTree->CollectLeaves(vc, leaves);
4365
4366                        ViewCellContainer::const_iterator vit, vit_end = leaves.end();
4367                for (vit = leaves.begin(); vit != vit_end; ++ vit)
4368                        {       
4369                                BspLeaf *vcLeaf = dynamic_cast<BspViewCell *>(*vit)->mLeaves[0];
4370                                VssRayContainer::const_iterator rit, rit_end = vcLeaf->mVssRays.end();
4371
4372                                for (rit = vcLeaf->mVssRays.begin(); rit != rit_end; ++ rit)
4373                                {
4374                                        collectRays.push_back(*rit);
4375                                }
4376                        }
4377
4378                        const int raysOut = min((int)collectRays.size(), maxRays);
4379               
4380                        // prepare some rays for output
4381                        VssRayContainer::const_iterator rit, rit_end = collectRays.end();
4382                        for (rit = collectRays.begin(); rit != rit_end; ++ rit)
4383                        {
4384                                const float p = RandomValue(0.0f, (float)collectRays.size());
4385                       
4386                                if (p < raysOut)
4387                                {
4388                                        vcRays.push_back(*rit);
4389                                }
4390                        }
4391
4392                        exporter->ExportRays(vcRays, RgbColor(1, 1, 1));
4393                }
4394               
4395                ////////////////
4396                //-- export view cell geometry
4397
4398                exporter->SetWireframe();
4399
4400                Material m;//= RandomMaterial();
4401                m.mDiffuseColor = RgbColor(0, 1, 0);
4402                exporter->SetForcedMaterial(m);
4403
4404                ExportViewCellGeometry(exporter, vc, NULL, NULL);
4405                exporter->SetFilled();
4406
4407                if (exportPvs)
4408                {
4409                        Intersectable::NewMail();
4410
4411                        ObjectPvsMap::const_iterator oit, oit_end = pvs.mEntries.end();
4412                        cout << endl;
4413                        // output PVS of view cell
4414                        for (oit = pvs.mEntries.begin(); oit != oit_end; ++ oit)
4415                        {               
4416                                Intersectable *intersect = (*oit).first;
4417                               
4418                                if (!intersect->Mailed())
4419                                {
4420                                        intersect->Mail();
4421
4422                                        m = RandomMaterial();
4423                                        exporter->SetForcedMaterial(m);
4424                                        exporter->ExportIntersectable(intersect);
4425                                }
4426                        }
4427                        cout << endl;
4428                }
4429               
4430                DEL_PTR(exporter);
4431                cout << "finished" << endl;
4432        }
4433}
4434
4435
4436void VspBspViewCellsManager::TestFilter(const ObjectContainer &objects)
4437{
4438        Exporter *exporter = Exporter::GetExporter("filter.x3d");
4439
4440        Vector3 bsize = mViewSpaceBox.Size();
4441        const Vector3 viewPoint(mViewSpaceBox.Center());
4442        float w = Magnitude(mViewSpaceBox.Size()) * mFilterWidth;
4443        const Vector3 width = Vector3(w);
4444       
4445        PrVs testPrVs;
4446       
4447        if (exporter)
4448        {
4449                ViewCellContainer viewCells;
4450       
4451        const AxisAlignedBox3 tbox = GetFilterBBox(viewPoint, mFilterWidth);
4452
4453                GetPrVS(viewPoint, testPrVs, GetFilterWidth());
4454
4455                exporter->SetWireframe();
4456
4457                exporter->SetForcedMaterial(RgbColor(1,1,1));
4458                exporter->ExportBox(tbox);
4459               
4460                exporter->SetFilled();
4461
4462                exporter->SetForcedMaterial(RgbColor(0,1,0));
4463                ExportViewCellGeometry(exporter, GetViewCell(viewPoint), NULL, NULL);
4464
4465                //exporter->ResetForcedMaterial();
4466                exporter->SetForcedMaterial(RgbColor(0,0,1));
4467                ExportViewCellGeometry(exporter, testPrVs.mViewCell, NULL, NULL);
4468
4469        exporter->SetForcedMaterial(RgbColor(1,0,0));
4470                exporter->ExportGeometry(objects);
4471
4472                delete exporter;
4473        }
4474}
4475
4476
4477int VspBspViewCellsManager::ComputeBoxIntersections(const AxisAlignedBox3 &box,
4478                                                                                                        ViewCellContainer &viewCells) const
4479{
4480        return mVspBspTree->ComputeBoxIntersections(box, viewCells);
4481}
4482
4483
4484int VspBspViewCellsManager::CastLineSegment(const Vector3 &origin,
4485                                                                                        const Vector3 &termination,
4486                                                                                        ViewCellContainer &viewcells)
4487{
4488        return mVspBspTree->CastLineSegment(origin, termination, viewcells);
4489}
4490
4491
4492void VspBspViewCellsManager::VisualizeWithFromPointQueries()
4493{
4494        int numSamples;
4495       
4496        Environment::GetSingleton()->GetIntValue("RenderSampler.samples", numSamples);
4497        cout << "samples" << numSamples << endl;
4498
4499        vector<RenderCostSample> samples;
4500 
4501        if (!mPreprocessor->GetRenderer())
4502                return;
4503
4504        //start the view point queries
4505        long startTime = GetTime();
4506        cout << "starting sampling of render cost ... ";
4507       
4508        mPreprocessor->GetRenderer()->SampleRenderCost(numSamples, samples, true);
4509
4510        cout << "finished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
4511
4512
4513        // for each sample:
4514        //    find view cells associated with the samples
4515        //    store the sample pvs with the pvs associated with the view cell
4516        //
4517        // for each view cell:
4518        //    compute difference point sampled pvs - view cell pvs
4519        //    export geometry with color coded pvs difference
4520       
4521    std::map<ViewCell *, ObjectPvs> sampleMap;
4522
4523        vector<RenderCostSample>::const_iterator rit, rit_end = samples.end();
4524
4525        for (rit = samples.begin(); rit != rit_end; ++ rit)
4526        {
4527                RenderCostSample sample = *rit;
4528       
4529                ViewCell *vc = GetViewCell(sample.mPosition);
4530
4531                std::map<ViewCell *, ObjectPvs>::iterator it = sampleMap.find(vc);
4532
4533                if (it == sampleMap.end())
4534                {
4535                        sampleMap[vc] = sample.mPvs;
4536                }
4537                else
4538                {
4539                        (*it).second.Merge(sample.mPvs);
4540                }
4541        }
4542
4543        // visualize the view cells
4544        std::map<ViewCell *, ObjectPvs>::const_iterator vit, vit_end = sampleMap.end();
4545
4546        Material m;//= RandomMaterial();
4547
4548        for (vit = sampleMap.begin(); vit != vit_end; ++ vit)
4549        {
4550                ViewCell *vc = (*vit).first;
4551               
4552                const int pvsVc = mViewCellsTree->GetPvsEntries(vc);
4553                const int pvsPtSamples = (*vit).second.GetSize();
4554
4555        m.mDiffuseColor.r = (float) (pvsVc - pvsPtSamples);
4556                m.mDiffuseColor.b = 1.0f;
4557                //exporter->SetForcedMaterial(m);
4558                //ExportViewCellGeometry(exporter, vc, mClipPlaneForViz);
4559
4560                /*      // counting the pvss
4561                for (rit = samples.begin(); rit != rit_end; ++ rit)
4562                {
4563                        RenderCostSample sample = *rit;
4564                        ViewCell *vc = GetViewCell(sample.mPosition);
4565
4566                        AxisAlignedBox3 box(sample.mPosition - Vector3(1, 1, 1), sample.mPosition + Vector3(1, 1, 1));
4567                        Mesh *hMesh = CreateMeshFromBox(box);
4568
4569                        DEL_PTR(hMesh);
4570                }
4571                */
4572        }
4573}
4574
4575
4576void VspBspViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
4577                                                                                                        ViewCell *vc,
4578                                                                                                        const AxisAlignedBox3 *sceneBox,
4579                                                                                                        const AxisAlignedPlane *clipPlane
4580                                                                                                        ) const
4581{
4582        if (clipPlane)
4583        {
4584                const Plane3 plane = clipPlane->GetPlane();
4585
4586                ViewCellContainer leaves;
4587                mViewCellsTree->CollectLeaves(vc, leaves);
4588                ViewCellContainer::const_iterator it, it_end = leaves.end();
4589
4590                for (it = leaves.begin(); it != it_end; ++ it)
4591                {
4592                        BspNodeGeometry geom;
4593                        BspNodeGeometry front;
4594                        BspNodeGeometry back;
4595
4596                        mVspBspTree->ConstructGeometry(*it, geom);
4597
4598                        const float eps = 0.0001f;
4599                        const int cf = geom.Side(plane, eps);
4600
4601                        if (cf == -1)
4602                        {
4603                                exporter->ExportPolygons(geom.GetPolys());
4604                        }
4605                        else if (cf == 0)
4606                        {
4607                                geom.SplitGeometry(front,
4608                                                                   back,
4609                                                                   plane,
4610                                                                   mViewSpaceBox,
4611                                                                   eps);
4612
4613                                if (back.Valid())
4614                                {
4615                                        exporter->ExportPolygons(back.GetPolys());
4616                                }                       
4617                        }
4618                }
4619        }
4620        else
4621        {
4622                // export mesh if available
4623                // TODO: some bug here?
4624                if (1 && vc->GetMesh())
4625                {
4626                        exporter->ExportMesh(vc->GetMesh());
4627                }
4628                else
4629                {
4630                        BspNodeGeometry geom;
4631                        mVspBspTree->ConstructGeometry(vc, geom);
4632                        exporter->ExportPolygons(geom.GetPolys());
4633                }
4634        }
4635}
4636
4637
4638int VspBspViewCellsManager::GetMaxTreeDiff(ViewCell *vc) const
4639{
4640        ViewCellContainer leaves;
4641        mViewCellsTree->CollectLeaves(vc, leaves);
4642
4643        int maxDist = 0;
4644       
4645        // compute max height difference
4646        for (int i = 0; i < (int)leaves.size(); ++ i)
4647        {
4648                for (int j = 0; j < (int)leaves.size(); ++ j)
4649                {
4650                        BspLeaf *leaf = dynamic_cast<BspViewCell *>(leaves[i])->mLeaves[0];
4651
4652                        if (i != j)
4653                        {
4654                                BspLeaf *leaf2 =dynamic_cast<BspViewCell *>(leaves[j])->mLeaves[0];
4655                                const int dist = mVspBspTree->TreeDistance(leaf, leaf2);
4656                               
4657                                if (dist > maxDist)
4658                                        maxDist = dist;
4659                        }
4660                }
4661        }
4662
4663        return maxDist;
4664}
4665
4666
4667ViewCell *VspBspViewCellsManager::GetViewCell(const Vector3 &point, const bool active) const
4668{
4669        if (!ViewCellsConstructed())
4670                return NULL;
4671
4672        if (!mViewSpaceBox.IsInside(point))
4673          return NULL;
4674
4675        return mVspBspTree->GetViewCell(point, active);
4676}
4677
4678
4679void VspBspViewCellsManager::CreateMesh(ViewCell *vc)
4680{
4681        BspNodeGeometry geom;
4682        mVspBspTree->ConstructGeometry(vc, geom);
4683       
4684        Mesh *mesh = MeshManager::GetSingleton()->CreateResource();
4685        IncludeNodeGeomInMesh(geom, *mesh);
4686
4687        vc->SetMesh(mesh);
4688}
4689
4690
4691int VspBspViewCellsManager::CastBeam(Beam &beam)
4692{
4693        return mVspBspTree->CastBeam(beam);
4694}
4695
4696
4697void VspBspViewCellsManager::Finalize(ViewCell *viewCell,
4698                                                                          const bool createMesh)
4699{
4700        float area = 0;
4701        float volume = 0;
4702
4703        ViewCellContainer leaves;
4704        mViewCellsTree->CollectLeaves(viewCell, leaves);
4705
4706        ViewCellContainer::const_iterator it, it_end = leaves.end();
4707
4708    for (it = leaves.begin(); it != it_end; ++ it)
4709        {
4710                BspNodeGeometry geom;
4711                mVspBspTree->ConstructGeometry(*it, geom);
4712
4713                const float lVol = geom.GetVolume();
4714                const float lArea = geom.GetArea();
4715
4716                area += lArea;
4717                volume += lVol;
4718
4719                if (createMesh)
4720                        CreateMesh(*it);
4721        }
4722
4723        viewCell->SetVolume(volume);
4724        viewCell->SetArea(area);
4725}
4726
4727
4728void VspBspViewCellsManager::TestSubdivision()
4729{
4730        ViewCellContainer leaves;
4731        mViewCellsTree->CollectLeaves(mViewCellsTree->GetRoot(), leaves);
4732
4733        ViewCellContainer::const_iterator it, it_end = leaves.end();
4734
4735        const float vol = mViewSpaceBox.GetVolume();
4736        float subdivVol = 0;
4737        float newVol = 0;
4738
4739        for (it = leaves.begin(); it != it_end; ++ it)
4740        {
4741                BspNodeGeometry geom;
4742                mVspBspTree->ConstructGeometry(*it, geom);
4743
4744                const float lVol = geom.GetVolume();
4745               
4746                newVol += lVol;
4747                subdivVol += (*it)->GetVolume();
4748               
4749                float thres = 0.9f;
4750                if ((lVol < ((*it)->GetVolume() * thres)) || (lVol * thres > ((*it)->GetVolume())))
4751                        Debug << "warning: " << lVol << " " << (*it)->GetVolume() << endl;
4752        }
4753       
4754        Debug << "exact volume: " << vol << endl;
4755        Debug << "subdivision volume: " << subdivVol << endl;
4756        Debug << "new volume: " << newVol << endl;
4757}
4758
4759
4760void VspBspViewCellsManager::PrepareLoadedViewCells()
4761{
4762        // TODO: do I still need this here?
4763        if (0)
4764                mVspBspTree->RepairViewCellsLeafLists();
4765}
4766
4767
4768
4769/**************************************************************************/
4770/*                   VspOspViewCellsManager implementation                */
4771/**************************************************************************/
4772
4773
4774VspOspViewCellsManager::VspOspViewCellsManager(ViewCellsTree *vcTree, HierarchyManager *hm)
4775: ViewCellsManager(vcTree), mHierarchyManager(hm)
4776{
4777        Environment::GetSingleton()->GetIntValue("Hierarchy.Construction.samples", mInitialSamples);
4778
4779        mHierarchyManager->SetViewCellsManager(this);
4780        mHierarchyManager->SetViewCellsTree(mViewCellsTree);
4781}
4782
4783
4784VspOspViewCellsManager::~VspOspViewCellsManager()
4785{
4786}
4787
4788
4789float VspOspViewCellsManager::GetProbability(ViewCell *viewCell)
4790{
4791        return GetVolume(viewCell) / mViewSpaceBox.GetVolume();
4792}
4793
4794
4795void VspOspViewCellsManager::CollectViewCells()
4796{
4797        // view cells tree constructed
4798        if (!ViewCellsTreeConstructed())
4799        {
4800                mHierarchyManager->GetVspTree()->CollectViewCells(mViewCells, false);
4801        }
4802        else
4803        {       // we can use the view cells tree hierarchy to get the right set
4804                mViewCellsTree->CollectBestViewCellSet(mViewCells, mNumActiveViewCells);
4805        }
4806}
4807
4808
4809bool VspOspViewCellsManager::ViewCellsConstructed() const
4810{
4811        return mHierarchyManager->GetVspTree()->GetRoot() != NULL;
4812}
4813
4814
4815ViewCell *VspOspViewCellsManager::GenerateViewCell(Mesh *mesh) const
4816{
4817        return new VspViewCell(mesh);
4818}
4819
4820
4821int VspOspViewCellsManager::ConstructSubdivision(const ObjectContainer &objects,
4822                                                                                                 const VssRayContainer &rays)
4823{
4824        mMaxPvsSize = (int)(mMaxPvsRatio * (float)objects.size());
4825
4826        // skip rest if view cells were already constructed
4827        if (ViewCellsConstructed())
4828                return 0;
4829
4830        int sampleContributions = 0;
4831        VssRayContainer sampleRays;
4832
4833        int limit = min (mInitialSamples, (int)rays.size());
4834
4835        VssRayContainer constructionRays;
4836        VssRayContainer savedRays;
4837
4838        Debug << "samples used for vsp bsp subdivision: " << mInitialSamples
4839                  << ", actual rays: " << (int)rays.size() << endl;
4840
4841        GetRaySets(rays, mInitialSamples, constructionRays, &savedRays);
4842
4843        Debug << "initial rays used for construction: " << (int)constructionRays.size() << endl;
4844        Debug << "saved rays: " << (int)savedRays.size() << endl;
4845
4846        mHierarchyManager->Construct(constructionRays, objects, &mViewSpaceBox);
4847
4848#if TEST_EVALUATION
4849        VssRayContainer::const_iterator tit, tit_end = constructionRays.end();
4850        for (tit = constructionRays.begin(); tit != tit_end; ++ tit)
4851        {
4852                storedRays.push_back(new VssRay(*(*tit)));
4853        }
4854#endif
4855
4856        /////////////////////////
4857        //-- print satistics for subdivision and view cells
4858
4859        Debug << endl << endl << *mHierarchyManager << endl;
4860
4861        ResetViewCells();
4862        Debug << "\nView cells after construction:\n" << mCurrentViewCellsStats << endl;
4863
4864        //////////////
4865        //-- recast rest of rays
4866       
4867        const long startTime = GetTime();
4868        cout << "Computing remaining ray contributions ... ";
4869
4870        if (SAMPLE_AFTER_SUBDIVISION)
4871                ComputeSampleContributions(savedRays, true, false);
4872
4873        Debug << "finished computing remaining ray contribution in " << TimeDiff(startTime, GetTime()) * 1e-3
4874                  << " secs" << endl;
4875
4876        if (0)
4877        {       // real meshes are constructed at this stage
4878                cout << "finalizing view cells ... ";
4879                FinalizeViewCells(true);
4880                cout << "finished" << endl;
4881        }
4882
4883        return sampleContributions;
4884}
4885
4886
4887int VspOspViewCellsManager::PostProcess(const ObjectContainer &objects,
4888                                                                                const VssRayContainer &rays)
4889{
4890        if (!ViewCellsConstructed())
4891        {
4892                Debug << "postprocess error: no view cells constructed" << endl;
4893                return 0;
4894        }
4895
4896        // if view cells were already constructed before post processing step
4897        // (e.g., because they were loaded), we are finished
4898        if (mViewCellsFinished)
4899        {
4900                FinalizeViewCells(true);
4901                EvaluateViewCellsStats();
4902
4903                return 0;
4904        }
4905
4906        // check if new view cells turned invalid
4907        int minPvs, maxPvs;
4908
4909        if (0)
4910        {
4911                minPvs = mMinPvsSize;
4912                maxPvs = mMaxPvsSize;
4913        }
4914        else
4915        {
4916                // problem matt: why did I start here from zero?
4917                minPvs = 0;
4918                maxPvs = mMaxPvsSize;
4919        }
4920
4921        Debug << "setting validity, min: " << minPvs << " max: " << maxPvs << endl;
4922        cout << "setting validity, min: " << minPvs << " max: " << maxPvs << endl;
4923       
4924        SetValidity(minPvs, maxPvs);
4925
4926       
4927        // area is not up to date, has to be recomputed
4928        mTotalAreaValid = false;
4929        VssRayContainer postProcessRays;
4930        GetRaySets(rays, mPostProcessSamples, postProcessRays);
4931
4932        Debug << "post processing using " << (int)postProcessRays.size() << " samples" << endl;
4933
4934
4935        // should maybe be done here to allow merge working with area or volume
4936        // and to correct the rendering statistics
4937        if (0) FinalizeViewCells(false);
4938               
4939        // compute tree by merging the nodes of the spatial hierarchy
4940        ViewCell *root = ConstructSpatialMergeTree(mHierarchyManager->GetVspTree()->GetRoot());
4941        mViewCellsTree->SetRoot(root);
4942
4943
4944        //////////////////////////
4945        //-- update pvs in the whole hierarchy
4946        ObjectPvs pvs;
4947        UpdatePvsForEvaluation(root, pvs);
4948
4949
4950        //////////////////////
4951        //-- render simulation after merge + refine
4952
4953        cout << "\nview cells partition render time before compress" << endl << endl;
4954        dynamic_cast<RenderSimulator *>(mRenderer)->RenderScene();
4955        SimulationStatistics ss;
4956        dynamic_cast<RenderSimulator *>(mRenderer)->GetStatistics(ss);
4957        cout << ss << endl;
4958       
4959
4960        ///////////
4961        //-- compression
4962
4963        if (ViewCellsTreeConstructed() && mCompressViewCells)
4964        {
4965                int pvsEntries = mViewCellsTree->CountStoredPvsEntries(mViewCellsTree->GetRoot());
4966                Debug << "number of entries before compress: " << pvsEntries << endl;
4967
4968                mViewCellsTree->SetViewCellsStorage(ViewCellsTree::COMPRESSED);
4969
4970                pvsEntries = mViewCellsTree->CountStoredPvsEntries(mViewCellsTree->GetRoot());
4971                Debug << "number of entries after compress: " << pvsEntries << endl;
4972        }
4973
4974        /////////////
4975        //-- some tasks still to do on the view cells:
4976        //-- Compute meshes from view cell geometry, evaluate volume and / or area
4977        if (1) FinalizeViewCells(true);
4978
4979        // write out view cells (this moved to preprocessor)
4980        if (1 && mExportViewCells)
4981        {
4982                char filename[100];
4983                Environment::GetSingleton()->GetStringValue("ViewCells.filename", filename);
4984                ExportViewCells(filename, mExportPvs, objects);
4985        }
4986
4987        return 0;
4988}
4989
4990
4991int VspOspViewCellsManager::GetType() const
4992{
4993        return VSP_OSP;
4994}
4995
4996
4997ViewCell *VspOspViewCellsManager::ConstructSpatialMergeTree(VspNode *root)
4998{
4999        // terminate recursion
5000        if (root->IsLeaf())
5001        {
5002                VspLeaf *leaf = dynamic_cast<VspLeaf *>(root);
5003                leaf->GetViewCell()->SetMergeCost(0.0f);
5004                return leaf->GetViewCell();
5005        }
5006       
5007        VspInterior *interior = dynamic_cast<VspInterior *>(root);
5008        ViewCellInterior *viewCellInterior = new ViewCellInterior();
5009               
5010        // evaluate merge cost for priority traversal
5011        float mergeCost = 1.0f / (float)root->mTimeStamp;
5012        viewCellInterior->SetMergeCost(mergeCost);
5013
5014        float volume = 0;
5015       
5016        VspNode *front = interior->GetFront();
5017        VspNode *back = interior->GetBack();
5018
5019        ObjectPvs frontPvs, backPvs;
5020
5021        /////////
5022        //-- recursivly compute child hierarchies
5023
5024        ViewCell *backVc = ConstructSpatialMergeTree(back);
5025        ViewCell *frontVc = ConstructSpatialMergeTree(front);
5026
5027        viewCellInterior->SetupChildLink(backVc);
5028        viewCellInterior->SetupChildLink(frontVc);
5029
5030        volume += backVc->GetVolume();
5031        volume += frontVc->GetVolume();
5032
5033        viewCellInterior->SetVolume(volume);
5034
5035        return viewCellInterior;
5036}
5037
5038
5039bool VspOspViewCellsManager::GetViewPoint(Vector3 &viewPoint) const
5040{
5041        if (!ViewCellsConstructed())
5042                return ViewCellsManager::GetViewPoint(viewPoint);
5043
5044        // TODO: set reasonable limit
5045        const int limit = 20;
5046
5047        for (int i = 0; i < limit; ++ i)
5048        {
5049                viewPoint = mViewSpaceBox.GetRandomPoint();
5050
5051                if (mHierarchyManager->GetVspTree()->ViewPointValid(viewPoint))
5052                {
5053                        return true;
5054                }
5055        }
5056
5057        Debug << "failed to find valid view point, taking " << viewPoint << endl;
5058        return false;
5059}
5060
5061
5062void VspOspViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
5063                                                                                                        ViewCell *vc,
5064                                                                                                        const AxisAlignedBox3 *sceneBox,
5065                                                                                                        const AxisAlignedPlane *clipPlane
5066                                                                                                        ) const
5067{
5068        ViewCellContainer leaves;
5069        mViewCellsTree->CollectLeaves(vc, leaves);
5070        ViewCellContainer::const_iterator it, it_end = leaves.end();
5071
5072        Plane3 plane;
5073        if (clipPlane)
5074        {
5075                // arbitrary plane definition
5076                plane = clipPlane->GetPlane();
5077        }
5078
5079        for (it = leaves.begin(); it != it_end; ++ it)
5080        {
5081                VspViewCell *vspVc = dynamic_cast<VspViewCell *>(*it);
5082                VspLeaf *l = vspVc->mLeaves[0];
5083
5084                const AxisAlignedBox3 box =
5085                        mHierarchyManager->GetVspTree()->GetBoundingBox(vspVc->mLeaves[0]);
5086               
5087                if (sceneBox && !Overlap(*sceneBox, box))
5088                        continue;
5089
5090                if (clipPlane)
5091                {
5092                        if (box.Side(plane) == -1)
5093                        {
5094                                exporter->ExportBox(box);
5095                        }
5096                        else if (box.Side(plane) == 0)
5097                        {
5098                                // intersection
5099                                AxisAlignedBox3 fbox, bbox;
5100                                box.Split(clipPlane->mAxis, clipPlane->mPosition, fbox, bbox);
5101                                exporter->ExportBox(bbox);
5102                        }
5103                }
5104                else
5105                {
5106                        exporter->ExportBox(box);
5107                }
5108        }
5109}
5110
5111
5112bool VspOspViewCellsManager::ViewPointValid(const Vector3 &viewPoint) const
5113{
5114  // $$JB -> implemented in viewcellsmanager (slower, but allows dynamic
5115  // validy update in preprocessor for all managers)
5116  return ViewCellsManager::ViewPointValid(viewPoint);
5117
5118  //    return mViewSpaceBox.IsInside(viewPoint) &&
5119  //               mVspTree->ViewPointValid(viewPoint);
5120}
5121
5122
5123void VspOspViewCellsManager::Visualize(const ObjectContainer &objects,
5124                                                                           const VssRayContainer &sampleRays)
5125{
5126        if (!ViewCellsConstructed())
5127                return;
5128
5129        VssRayContainer visRays;
5130        GetRaySets(sampleRays, mVisualizationSamples, visRays);
5131
5132        ////////////
5133        //-- export final view cells
5134
5135        Exporter *exporter = Exporter::GetExporter("final_view_cells.wrl");
5136
5137        if (exporter)
5138        {
5139                // hack color code (show pvs size)
5140                const int savedColorCode = mColorCode;
5141                mColorCode = 0;
5142
5143                const long starttime = GetTime();
5144                cout << "exporting final view cells (after initial construction + post process) ... ";
5145
5146                // matt: hack for clamping scene
5147                AxisAlignedBox3 bbox = mViewSpaceBox;
5148                bbox.Scale(Vector3(0.5, 1, 0.5));
5149                if (CLAMP_TO_BOX)
5150                {       
5151                        exporter->SetWireframe();
5152                        exporter->ExportBox(bbox);
5153                        exporter->SetFilled();
5154                }
5155
5156                if (0 && mExportGeometry)
5157                {
5158                        exporter->ExportGeometry(objects, true, CLAMP_TO_BOX ? &bbox : NULL);
5159                }
5160
5161                if (1 && mExportRays)
5162                {       
5163                        exporter->ExportRays(visRays, RgbColor(0, 1, 0));
5164                }
5165
5166                mHierarchyManager->ExportObjectSpaceHierarchy(exporter, objects, CLAMP_TO_BOX ? &bbox : NULL, false);
5167                ExportViewCellsForViz(exporter, CLAMP_TO_BOX ? &bbox : NULL, GetClipPlane());
5168
5169                delete exporter;
5170                cout << "finished in " << TimeDiff(starttime, GetTime()) * 1e-3f << " secs" << endl;
5171                mColorCode = savedColorCode;
5172        }
5173
5174        // export final object partition
5175        exporter = Exporter::GetExporter("final_object_partition.wrl");
5176
5177        if (exporter)
5178        {
5179                const long starttime = GetTime();
5180
5181                // matt: hack for making visualization smaller in size
5182                AxisAlignedBox3 bbox = mHierarchyManager->GetObjectSpaceBox();
5183                bbox.Scale(Vector3(0.5, 1, 0.5));
5184
5185                cout << "exporting object space hierarchy ... ";
5186                mHierarchyManager->ExportObjectSpaceHierarchy(exporter, objects, CLAMP_TO_BOX ? &bbox : NULL);
5187
5188                delete exporter;
5189                cout << "finished in " << TimeDiff(starttime, GetTime()) * 1e-3f << " secs" << endl;
5190        }
5191
5192       
5193        //  visualization of the view cells
5194        if (0) ExportMergedViewCells(objects);
5195
5196        // export some view cell
5197        int leafOut;
5198        Environment::GetSingleton()->GetIntValue("ViewCells.Visualization.maxOutput", leafOut);
5199        const int raysOut = 100;
5200
5201        ExportSingleViewCells(objects, leafOut, false, true, false, raysOut, "");
5202}
5203
5204
5205void VspOspViewCellsManager::ExportSingleViewCells(const ObjectContainer &objects,
5206                                                                                                   const int maxViewCells,
5207                                                                                                   const bool sortViewCells,
5208                                                                                                   const bool exportPvs,
5209                                                                                                   const bool exportRays,
5210                                                                                                   const int maxRays,
5211                                                                                                   const string prefix,
5212                                                                                                   VssRayContainer *visRays)
5213{
5214        if (sortViewCells)
5215        {
5216                // sort view cells to visualize the view cells with highest render cost
5217                stable_sort(mViewCells.begin(), mViewCells.end(), ViewCell::LargerRenderCost);
5218        }
5219
5220        ViewCell::NewMail();
5221        const int limit = min(maxViewCells, (int)mViewCells.size());
5222       
5223        cout << "\nExporting " << limit << " single view cells: " << endl;
5224       
5225        for (int i = 0; i < limit; ++ i)
5226        {
5227                cout << "creating output for view cell " << i << " ... ";
5228               
5229                // largest view cell pvs first of random view cell
5230                ViewCell *vc = sortViewCells ?
5231                        mViewCells[i] : mViewCells[(int)RandomValue(0, (float)mViewCells.size() - 1)];
5232               
5233                if (vc->Mailed()) // already used
5234                        continue;
5235
5236                vc->Mail();
5237
5238                ObjectPvs pvs;
5239                mViewCellsTree->GetPvs(vc, pvs);
5240
5241                char s[64]; sprintf(s, "%sviewcell%04d.wrl", prefix.c_str(), i);
5242                Exporter *exporter = Exporter::GetExporter(s);
5243               
5244                cout << "view cell " << vc->GetId() << ": pvs size=" << (int)mViewCellsTree->GetPvsSize(vc) << endl;
5245
5246                if (exportPvs)
5247                {
5248                        Material m;
5249
5250                        Intersectable::NewMail();
5251                        ObjectPvsMap::const_iterator oit, oit_end = pvs.mEntries.end();
5252                       
5253                        // output PVS of view cell
5254                        for (oit = pvs.mEntries.begin(); oit != oit_end; ++ oit)
5255                        {               
5256                                Intersectable *intersect = (*oit).first;
5257                                if (!intersect->Mailed())
5258                                {
5259                                        m = RandomMaterial();
5260                                        exporter->SetForcedMaterial(m);
5261
5262                                        exporter->ExportIntersectable(intersect);
5263                                        intersect->Mail();
5264                                }
5265                        }
5266                }
5267
5268                if (exportRays)
5269                {
5270                        ////////////
5271                        //-- export the sample rays
5272
5273                        // output rays stored with the view cells during subdivision
5274                        VssRayContainer vcRays;
5275                        VssRayContainer collectRays;
5276
5277                        // collect intial view cells
5278                        ViewCellContainer leaves;
5279                        mViewCellsTree->CollectLeaves(vc, leaves);
5280
5281                        ViewCellContainer::const_iterator vit, vit_end = leaves.end();
5282
5283                        for (vit = leaves.begin(); vit != vit_end; ++ vit)
5284                        {
5285                                VspLeaf *vcLeaf = dynamic_cast<VspViewCell *>(*vit)->mLeaves[0];
5286                                VssRayContainer::const_iterator rit, rit_end = vcLeaf->mVssRays.end();
5287
5288                                for (rit = vcLeaf->mVssRays.begin(); rit != rit_end; ++ rit)
5289                                {
5290                                        collectRays.push_back(*rit);
5291                                }
5292                        }
5293
5294                        const int raysOut = min((int)collectRays.size(), maxRays);
5295
5296                        VssRayContainer::const_iterator rit, rit_end = collectRays.end();
5297
5298                        for (rit = collectRays.begin(); rit != rit_end; ++ rit)
5299                        {
5300                                const float p = RandomValue(0.0f, (float)collectRays.size());
5301
5302                                if (p < raysOut)
5303                                        vcRays.push_back(*rit);
5304                        }
5305
5306                        exporter->ExportRays(vcRays, RgbColor(1, 1, 1));
5307                }
5308               
5309       
5310                /////////////////
5311                //-- export view cell geometry
5312
5313                exporter->SetWireframe();
5314
5315                Material m;
5316                m.mDiffuseColor = RgbColor(0, 1, 0);
5317                exporter->SetForcedMaterial(m);
5318
5319                ExportViewCellGeometry(exporter, vc, NULL, NULL);
5320                exporter->SetFilled();
5321
5322                DEL_PTR(exporter);
5323                cout << "finished" << endl;
5324        }
5325
5326        cout << endl;
5327}
5328
5329
5330int VspOspViewCellsManager::ComputeBoxIntersections(const AxisAlignedBox3 &box,
5331                                                                                                        ViewCellContainer &viewCells) const
5332{
5333        return mHierarchyManager->GetVspTree()->ComputeBoxIntersections(box, viewCells);
5334}
5335
5336
5337int VspOspViewCellsManager::CastLineSegment(const Vector3 &origin,
5338                                                                                        const Vector3 &termination,
5339                                                                                        ViewCellContainer &viewcells)
5340{
5341        return mHierarchyManager->GetVspTree()->CastLineSegment(origin, termination, viewcells);
5342}
5343
5344
5345bool VspOspViewCellsManager::ExportViewCells(const string filename,
5346                                                                                         const bool exportPvs,
5347                                                                                         const ObjectContainer &objects)
5348{
5349        if (!ViewCellsConstructed() || !ViewCellsTreeConstructed())
5350                return false;
5351
5352        const long starttime = GetTime();
5353        cout << "exporting view cells to xml ... ";
5354       
5355        OUT_STREAM stream(filename.c_str());
5356
5357        // for output we need unique ids for each view cell
5358        CreateUniqueViewCellIds();
5359
5360        stream << "<?xml version=\"1.0\" encoding=\"UTF-8\"?>"<<endl;
5361        stream << "<VisibilitySolution>" << endl;
5362
5363        if (exportPvs)
5364        {
5365        ///////////////
5366                //-- export bounding boxes
5367                //-- The bounding boxes are used to identify
5368                //-- the objects in the rendering engine
5369                mHierarchyManager->ExportBoundingBoxes(stream, objects);
5370        }
5371
5372        //////////////////////////
5373        //-- export the view cells and the pvs
5374
5375        const int numViewCells = mCurrentViewCellsStats.viewCells;
5376
5377        stream << "<ViewCells number=\"" << numViewCells << "\" >" << endl;
5378        mViewCellsTree->Export(stream, exportPvs);
5379        stream << "</ViewCells>" << endl;
5380
5381        //////////////////////
5382        //-- export the view space hierarchy
5383       
5384        stream << "<ViewSpaceHierarchy type=\"vsp\""
5385                   << " min=\"" << mViewSpaceBox.Min().x << " " << mViewSpaceBox.Min().y << " " << mViewSpaceBox.Min().z << "\""
5386                   << " max=\"" << mViewSpaceBox.Max().x << " " << mViewSpaceBox.Max().y << " " << mViewSpaceBox.Max().z << "\">" << endl;
5387
5388        mHierarchyManager->GetVspTree()->Export(stream);
5389        stream << "</ViewSpaceHierarchy>" << endl;
5390
5391        ////////////////////// 
5392        //-- export the object space partition
5393       
5394        mHierarchyManager->ExportObjectSpaceHierarchy(stream);
5395       
5396        stream << "</VisibilitySolution>" << endl;
5397        stream.close();
5398       
5399        cout << "finished in " << TimeDiff(starttime, GetTime()) * 1e-3 << " secs" << endl;
5400        return true;
5401}
5402
5403
5404
5405ViewCell *VspOspViewCellsManager::GetViewCell(const Vector3 &point,
5406                                                                                          const bool active) const
5407{
5408        if (!ViewCellsConstructed())
5409                return NULL;
5410
5411        if (!mViewSpaceBox.IsInside(point))
5412                return NULL;
5413
5414        return mHierarchyManager->GetVspTree()->GetViewCell(point, active);
5415}
5416
5417
5418void VspOspViewCellsManager::CreateMesh(ViewCell *vc)
5419{
5420        // matt: TODO
5421        Mesh *mesh = MeshManager::GetSingleton()->CreateResource();
5422
5423        ViewCellContainer leaves;
5424        mViewCellsTree->CollectLeaves(vc, leaves);
5425
5426        ViewCellContainer::const_iterator it, it_end = leaves.end();
5427
5428    for (it = leaves.begin(); it != it_end; ++ it)
5429        {
5430                VspLeaf *leaf = dynamic_cast<VspViewCell *>(*it)->mLeaves[0];
5431                const AxisAlignedBox3 box = mHierarchyManager->GetVspTree()->GetBoundingBox(leaf);
5432        IncludeBoxInMesh(box, *mesh);
5433        }
5434
5435        vc->SetMesh(mesh);
5436}
5437
5438
5439int VspOspViewCellsManager::CastBeam(Beam &beam)
5440{
5441        // matt: TODO
5442        return 0;
5443}
5444
5445
5446void VspOspViewCellsManager::Finalize(ViewCell *viewCell,
5447                                                                          const bool createMesh)
5448{
5449        float area = 0;
5450        float volume = 0;
5451
5452        ViewCellContainer leaves;
5453        mViewCellsTree->CollectLeaves(viewCell, leaves);
5454
5455        ViewCellContainer::const_iterator it, it_end = leaves.end();
5456
5457    for (it = leaves.begin(); it != it_end; ++ it)
5458        {
5459                VspLeaf *leaf = dynamic_cast<VspViewCell *>(*it)->mLeaves[0];
5460               
5461                const AxisAlignedBox3 box = mHierarchyManager->GetVspTree()->GetBoundingBox(leaf);
5462
5463                const float lVol = box.GetVolume();
5464                const float lArea = box.SurfaceArea();
5465
5466                area += lArea;
5467                volume += lVol;
5468
5469        CreateMesh(*it);
5470        }
5471
5472        viewCell->SetVolume(volume);
5473        viewCell->SetArea(area);
5474}
5475       
5476
5477float VspOspViewCellsManager::ComputeSampleContribution(VssRay &ray,
5478                                                                                                                const bool addRays,
5479                                                                                                                const bool storeViewCells)
5480{
5481        ViewCellContainer viewcells;
5482
5483        ray.mPvsContribution = 0;
5484        ray.mRelativePvsContribution = 0.0f;
5485
5486        static Ray hray;
5487        hray.Init(ray);
5488        //hray.mFlags |= Ray::CULL_BACKFACES;
5489        //Ray hray(ray);
5490
5491        float tmin = 0, tmax = 1.0;
5492
5493        if (!GetViewSpaceBox().GetRaySegment(hray, tmin, tmax) || (tmin > tmax))
5494                return 0;
5495
5496        Vector3 origin = hray.Extrap(tmin);
5497        Vector3 termination = hray.Extrap(tmax);
5498
5499        ViewCell::NewMail();
5500
5501        // traverse the view space subdivision
5502        CastLineSegment(origin, termination, viewcells);
5503
5504        if (storeViewCells)
5505        {       
5506                // copy viewcells memory efficiently
5507                ray.mViewCells.reserve(viewcells.size());
5508                ray.mViewCells = viewcells;
5509        }
5510
5511        ViewCellContainer::const_iterator it = viewcells.begin();
5512
5513        for (; it != viewcells.end(); ++ it)
5514        {
5515                ViewCell *viewcell = *it;
5516               
5517                if (viewcell->GetValid())
5518                {       // if ray not outside of view space
5519                        float contribution;
5520
5521                        if (ray.mTerminationObject)
5522                        {
5523                          // todo: maybe not correct for kd node pvs
5524                          Intersectable *obj = mHierarchyManager->GetIntersectable(ray, true);
5525                         
5526                          if (viewcell->GetPvs().GetSampleContribution(obj,
5527                                                                                                                   ray.mPdf,
5528                                                                                                                   contribution))
5529                                {
5530                                  ++ ray.mPvsContribution;
5531                                }
5532                         
5533                          ray.mRelativePvsContribution += contribution;
5534                        }
5535                       
5536                        // for directional sampling it is important to count only contributions
5537                        // made in one direction!
5538                        // the other contributions of this sample will be counted for the opposite ray!
5539#if SAMPLE_ORIGIN_OBJECTS
5540                        if (ray.mOriginObject &&
5541                                viewcell->GetPvs().GetSampleContribution(ray.mOriginObject,
5542                                                                                                                 ray.mPdf,
5543                                                                                                                 contribution))
5544                        {
5545                                ++ ray.mPvsContribution;
5546                                ray.mRelativePvsContribution += contribution;
5547                        }
5548#endif
5549                }
5550        }
5551
5552        if (!addRays)
5553        {
5554                return ray.mRelativePvsContribution;
5555        }
5556
5557        // sampled objects are stored in the pvs
5558        for (it = viewcells.begin(); it != viewcells.end(); ++ it)
5559        {
5560                ViewCell *viewCell = *it;
5561
5562                if (!viewCell->GetValid())
5563                        break;
5564
5565                AddSampleToPvs(
5566                        ray.mTerminationObject,
5567                        ray.mTermination,
5568                        viewCell,
5569                        ray.mPdf,
5570                        ray.mRelativePvsContribution);
5571
5572#if SAMPLE_ORIGIN_OBJECTS
5573
5574                AddSampleToPvs(
5575                        ray.mOriginObject,
5576                        ray.mOrigin,
5577                        viewCell,
5578                        ray.mPdf,
5579                        ray.mRelativePvsContribution);
5580#endif                 
5581        }
5582
5583        return ray.mRelativePvsContribution;
5584}
5585
5586
5587bool VspOspViewCellsManager::AddSampleToPvs(Intersectable *obj,
5588                                                                                        const Vector3 &hitPoint,
5589                                                                                        ViewCell *vc,
5590                                                                                        const float pdf,
5591                                                                                        float &contribution) const
5592{
5593        // The hierarchy manager decides about the type of sample cast
5594        return mHierarchyManager->AddSampleToPvs(obj, hitPoint, vc, pdf, contribution);
5595}
5596
5597
5598void VspOspViewCellsManager::PrepareLoadedViewCells()
5599{
5600        // TODO
5601}
5602
5603
5604ViewCellsManager *VspOspViewCellsManager::LoadViewCells(const string &filename,
5605                                                                                                                ObjectContainer *objects,
5606                                                                                                                const bool finalizeViewCells,
5607                                                                                                                BoundingBoxConverter *bconverter)
5608                                                                                                 
5609{
5610        ViewCellsManager *vm =
5611                ViewCellsManager::LoadViewCells(filename, objects, finalizeViewCells, bconverter);
5612#if 0
5613        // insert scene objects in tree
5614        mOspTree->InsertObjects(mOspTree->GetRoot(), *objects);
5615#endif
5616        return vm;
5617}
5618
5619
5620#if TEST_EVALUATION
5621void VspOspViewCellsManager::EvalViewCellPartition()
5622{
5623        const int castSamples = (int)storedRays.size();
5624        char s[64];
5625        char statsPrefix[100];
5626
5627        Environment::GetSingleton()->GetStringValue("ViewCells.Evaluation.statsPrefix", statsPrefix);
5628
5629        Debug << "view cell stats prefix: " << statsPrefix << endl;
5630
5631        // should directional sampling be used?
5632        const bool dirSamples = (mEvaluationSamplingType == SamplingStrategy::DIRECTION_BASED_DISTRIBUTION);
5633
5634        cout << "reseting pvs ... ";
5635        const bool startFromZero = true;
5636
5637        if (startFromZero)
5638        {
5639                // reset pvs and start over from zero
5640                mViewCellsTree->ResetPvs();
5641        }
5642        else
5643        {
5644                // statistics before casting more samples
5645                cout << "compute new statistics ... ";
5646                sprintf(s, "-%09d-eval.log", castSamples);
5647                string fName = string(statsPrefix) + string(s);
5648
5649                mViewCellsTree->ExportStats(fName);
5650                cout << "finished" << endl;
5651        }
5652        cout << "finished" << endl;
5653
5654    cout << "Evaluating view cell partition ... " << endl;
5655
5656        VssRayContainer evaluationSamples = storedRays;
5657        const int samplingType = mEvaluationSamplingType;
5658       
5659        cout << "computing sample contributions of " << (int)evaluationSamples.size()  << " samples ... ";
5660       
5661        ComputeSampleContributions(evaluationSamples, true, false);
5662       
5663        cout << "finished" << endl;
5664       
5665        cout << "compute new statistics ... ";
5666       
5667        // propagate pvs or pvs size information
5668        ObjectPvs pvs;
5669        UpdatePvsForEvaluation(mViewCellsTree->GetRoot(), pvs);
5670
5671
5672        /////////////////////
5673        // $§temporary matt: test render cost
5674
5675        sprintf(s, "-%09d-eval.log", castSamples);
5676        string fileName = string(statsPrefix) + string(s);
5677
5678        ViewCellContainer leaves;
5679
5680        mViewCellsTree->CollectLeaves(mViewCellsTree->GetRoot(), leaves);
5681        float rc = 0;
5682
5683        ViewCellContainer::const_iterator vit, vit_end = leaves.end();
5684       
5685        for (vit = leaves.begin(); vit != vit_end; ++ vit)
5686        {
5687                ViewCell *vc = *vit;
5688                int pvs = vc->GetPvs().CountObjectsInPvs();
5689                float vol = vc->GetVolume();
5690                rc += pvs * vol;
5691        }
5692
5693        Debug << "\nrendercost hack: " << rc / mViewSpaceBox.GetVolume() << endl;
5694        mViewCellsTree->ExportStats(fileName);
5695        cout << "finished" << endl;
5696
5697        vector<int> storageFunc;
5698        mViewCellsTree->GetStorageFunction(storageFunc);
5699
5700        vector<float> costFunc;
5701        mViewCellsTree->GetCostFunction(costFunc);
5702
5703        ofstream outstr("out.txt");
5704
5705        for (int i = 0; i < storageFunc.size(); ++ i)
5706                outstr << i << ": " << storageFunc[i] << endl;
5707outstr << endl;
5708        for (int i = 0; i < costFunc.size(); ++ i)
5709                outstr << i << ": " << costFunc[i] << endl;
5710        if (0)
5711        for (int i = 0; i <50; ++ i)
5712        {
5713                Vector3 point = GetViewSpaceBox().GetRandomPoint();
5714                ViewCell *vc = GetViewCell(point);
5715        }
5716        //RenderBvhNode(mHierarchyManager->mBvHierarchy->GetRoot());
5717
5718        disposeRays(evaluationSamples, NULL);
5719}
5720
5721#endif
5722}
Note: See TracBrowser for help on using the repository browser.