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

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