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

Revision 2729, 180.6 KB checked in by mattausch, 16 years ago (diff)

worked on gvs

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