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

Revision 1888, 154.3 KB checked in by mattausch, 18 years ago (diff)

removed possible bug in mixtedstrategy

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