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

Revision 1942, 165.0 KB checked in by bittner, 18 years ago (diff)

tmp commit

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