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

Revision 697, 94.0 KB checked in by mattausch, 19 years ago (diff)
Line 
1#include "ViewCellsManager.h"
2#include "RenderSimulator.h"
3#include "Mesh.h"
4#include "Triangle3.h"
5#include "ViewCell.h"
6#include "Environment.h"
7#include "X3dParser.h"
8#include "ViewCellBsp.h"
9#include "KdTree.h"
10#include "VspKdTree.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
18#define SAMPLE_AFTER_SUBDIVISION 1
19#define TEST_EMPTY_VIEW_CELLS 0
20
21
22
23template <typename T> class myless
24{
25public:
26        //bool operator() (HierarchyNode *v1, HierarchyNode *v2) const
27        bool operator() (T v1, T v2) const
28        {
29                return (v1->GetMergeCost() < v2->GetMergeCost());
30        }
31};
32
33typedef priority_queue<ViewCell *, vector<ViewCell *>, myless<vector<ViewCell *>::value_type> > FilterQueue;
34
35
36
37ViewCellsManager::ViewCellsManager():
38mRenderer(NULL),
39mInitialSamples(0),
40mConstructionSamples(0),
41mPostProcessSamples(0),
42mVisualizationSamples(0),
43mTotalAreaValid(false),
44mTotalArea(0.0f),
45mViewCellsFinished(false),
46mMaxPvsSize(9999999),
47mMinPvsSize(0), // one means only empty view cells are invalid
48mMaxPvsRatio(1.0)
49{
50        mViewSpaceBox.Initialize();
51        ParseEnvironment();
52
53        mViewCellsTree = new ViewCellsTree(this);
54}
55
56
57void ViewCellsManager::ParseEnvironment()
58{
59        // visualization stuff
60        environment->GetBoolValue("ViewCells.Visualization.exportRays", mExportRays);
61        environment->GetBoolValue("ViewCells.Visualization.exportGeometry", mExportGeometry);
62        environment->GetFloatValue("ViewCells.maxPvsRatio", mMaxPvsRatio);
63       
64        bool emptyViewCells = false;
65        environment->GetBoolValue("ViewCells.pruneEmptyViewCells", emptyViewCells);
66        mMinPvsSize = emptyViewCells ? 1 : 0;
67
68        environment->GetBoolValue("ViewCells.processOnlyValidViewCells", mOnlyValidViewCells);
69
70        environment->GetIntValue("ViewCells.Construction.samples", mConstructionSamples);
71        environment->GetIntValue("ViewCells.PostProcess.samples", mPostProcessSamples);
72        environment->GetBoolValue("ViewCells.PostProcess.useRaysForMerge", mUseRaysForMerge);
73
74        environment->GetIntValue("ViewCells.Visualization.samples", mVisualizationSamples);
75
76        environment->GetIntValue("ViewCells.Construction.samplesPerPass", mSamplesPerPass);
77        environment->GetBoolValue("ViewCells.exportToFile", mExportViewCells);
78       
79        environment->GetIntValue("ViewCells.active", mNumActiveViewCells);
80        environment->GetBoolValue("ViewCells.PostProcess.compress", mCompressViewCells);
81        environment->GetBoolValue("ViewCells.Visualization.useClipPlane", mUseClipPlaneForViz);
82        environment->GetBoolValue("ViewCells.PostProcess.merge", mMergeViewCells);
83        environment->GetBoolValue("ViewCells.evaluateViewCells", mEvaluateViewCells);
84        environment->GetBoolValue("ViewCells.showVisualization", mShowVisualization);
85        environment->GetIntValue("ViewCells.Filter.maxSize", mMaxFilterSize);
86        environment->GetFloatValue("ViewCells.Filter.width", mFilterWidth);
87
88        char buf[100];
89        environment->GetStringValue("ViewCells.samplingType", buf);
90
91       
92        if (strcmp(buf, "box") == 0)
93                mSamplingType = Preprocessor::SPATIAL_BOX_BASED_DISTRIBUTION;
94        else if (strcmp(buf, "directional") == 0)
95                mSamplingType = Preprocessor::DIRECTION_BASED_DISTRIBUTION;
96        else
97        {
98                Debug << "error! wrong sampling type" << endl;
99                exit(0);
100        }
101
102        environment->GetStringValue("ViewCells.Visualization.colorCode", buf);
103
104        if (strcmp(buf, "PVS") == 0)
105                mColorCode = 1;
106        else if (strcmp(buf, "MergedLeaves") == 0)
107                mColorCode = 2;
108        else if (strcmp(buf, "MergedTreeDiff") == 0)
109                mColorCode = 3;
110        else
111                mColorCode = 0;
112
113
114        Debug << "***********View Cells options ****************" << endl;
115        Debug << "color code: " << mColorCode << endl;
116
117        Debug << "export rays: " << mExportRays << endl;
118        Debug << "export geometry: " << mExportGeometry << endl;
119        Debug << "max pvs ratio: " << mMaxPvsRatio << endl;
120       
121        Debug << "prune empty view cells: " << emptyViewCells << endl;
122       
123        Debug << "process only valid view cells: " << mOnlyValidViewCells << endl;
124        Debug << "construction samples: " << mConstructionSamples << endl;
125        Debug << "post process samples: " << mPostProcessSamples << endl;
126        Debug << "post process use rays for merge: " << mUseRaysForMerge << endl;
127        Debug << "visualization samples: " << mVisualizationSamples << endl;
128        Debug << "construction samples per pass: " << mSamplesPerPass << endl;
129        Debug << "export to file: " << mExportViewCells << endl;
130       
131        Debug << "active: " << mNumActiveViewCells << endl;
132        Debug << "post process compress: " << mCompressViewCells << endl;
133        Debug << "visualization use clipPlane: " << mUseClipPlaneForViz << endl;
134        Debug << "post process merge: " << mMergeViewCells << endl;
135        Debug << "evaluate view cells: " << mEvaluateViewCells << endl;
136        Debug << "sampling type: " << mSamplingType << endl;
137        Debug << "show visualization: " << mShowVisualization << endl;
138        Debug << "filter width: " << mFilterWidth << endl;
139
140        Debug << endl;
141}
142
143
144ViewCellsManager::~ViewCellsManager()
145{
146        DEL_PTR(mRenderer);
147
148        if (!ViewCellsTreeConstructed())
149                CLEAR_CONTAINER(mViewCells);
150        else
151                DEL_PTR(mViewCellsTree);
152
153        CLEAR_CONTAINER(mMeshContainer);
154}
155
156
157void ViewCellsManager::CollectEmptyViewCells()
158{
159        mEmptyViewCells.clear();
160        ViewCellContainer leaves;
161        mViewCellsTree->CollectLeaves(mViewCellsTree->GetRoot(), leaves);
162
163        ViewCellContainer::const_iterator it, it_end = leaves.end();
164
165        cout << "collecting empty view cells" << endl;
166       
167        for (it = leaves.begin(); it != it_end; ++ it)
168        {
169                if ((*it)->GetPvs().Empty())
170                {
171                        mEmptyViewCells.push_back(*it);
172                }
173        }
174        Debug << "empty view cells found: " << (int)mEmptyViewCells.size() << endl;
175}
176
177
178void ViewCellsManager::TestEmptyViewCells(const ObjectContainer &obj)
179{
180        ViewCellContainer::const_iterator it, it_end = mEmptyViewCells.end();
181
182        char buf[50];
183        int i = 0;
184        for (it = mEmptyViewCells.begin(); it != it_end; ++ it)
185        {
186                if (!(*it)->GetPvs().Empty())
187                {
188                        sprintf(buf, "empty-viewcells-%09d.x3d", i/*(*it)->GetId()*/);
189                        Exporter *exporter = Exporter::GetExporter(buf);
190                       
191                        if (exporter && i < 20)
192                        {
193                                Ray *pray = (*it)->mPiercingRays[0];
194                                Debug << "view cell " << (*it)->GetId() << " not empty, pvs: " << (*it)->GetPvs().GetSize() << " " << (int)pray->intersections.size() << endl;
195
196                                exporter->ExportRays((*it)->mPiercingRays);
197                                                       
198                                exporter->SetFilled();
199                                exporter->SetForcedMaterial(RgbColor(0,0,1));
200
201                                for (int j = 0; j < (int)pray->intersections.size(); ++ j)
202                                {
203                                        if (pray->intersections[j].mObject)
204                                                exporter->ExportIntersectable(pray->intersections[j].mObject);
205                                }
206
207                                //exporter->SetWireframe();
208                                exporter->SetForcedMaterial(RgbColor(0,1,0));
209                                exporter->ExportGeometry(obj);
210
211                                exporter->SetFilled();
212
213                                exporter->SetForcedMaterial(RgbColor(1,0,0));
214                                ExportViewCellGeometry(exporter, *it);
215
216                                delete exporter;               
217                        }
218
219               
220                        ++ i;
221                }
222        }
223        Debug << "\nSampled " << i << " new view cells (" << " of " << (int)mEmptyViewCells.size() << ")" << endl << endl;
224}
225
226
227int ViewCellsManager::CastPassSamples(const int samplesPerPass,
228                                                                          const int sampleType,
229                                                                          VssRayContainer &passSamples) const
230{
231        SimpleRayContainer simpleRays;
232
233        preprocessor->GenerateRays(samplesPerPass,
234                                                           sampleType,
235                                                           simpleRays);
236
237        // shoot simple ray and add it to importance samples
238        preprocessor->CastRays(simpleRays, passSamples);
239
240        return (int)passSamples.size();
241}
242
243
244
245/// helper function which destroys rays or copies them into the output ray container
246inline void disposeRays(VssRayContainer &rays, VssRayContainer *outRays)
247{
248        cout << "disposing samples ... ";
249        long startTime = GetTime();
250        int n = (int)rays.size();
251
252        if (outRays)
253        {
254                VssRayContainer::const_iterator it, it_end = rays.end();
255
256                for (it = rays.begin(); it != it_end; ++ it)
257                {
258                        outRays->push_back(*it);
259                }
260        }
261        else
262        {
263                VssRayContainer::const_iterator it, it_end = rays.end();
264
265                for (it = rays.begin(); it != it_end; ++ it)
266                {
267                        //(*it)->Unref();
268                        if (!(*it)->IsActive())
269                                delete (*it);
270                }
271        }
272
273        cout << "finished" << endl;
274        Debug << "disposed " << n << " samples in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
275}
276
277
278int ViewCellsManager::Construct(Preprocessor *preprocessor, VssRayContainer *outRays)
279{
280        int numSamples = 0;
281        SimpleRayContainer simpleRays;
282       
283        VssRayContainer initialSamples;
284
285        cout << "view cell construction: casting " << mInitialSamples << " initial samples ... ";
286        //-- construction rays => we use uniform samples for this
287        CastPassSamples(mInitialSamples,
288                                        mSamplingType,
289                                        initialSamples);
290       
291        cout << "finished" << endl;
292
293       
294        // construct view cells
295        const int numInitialSamples =
296                ConstructSubdivision(preprocessor->mObjects, initialSamples);
297
298        numSamples += numInitialSamples;
299
300        // rays can be passed or deleted
301        disposeRays(initialSamples, outRays);
302       
303        cout << "testing filter ... ";
304
305        TestFilter(preprocessor->mObjects);
306
307        cout << "finished" << endl;
308
309        // -- stats after contruction
310        ResetViewCells();
311
312        Debug << "\nView cells after initial sampling:\n" << mCurrentViewCellsStats << endl;
313
314        if (1) // export initial view cells
315        {
316                cout << "exporting initial view cells (=leaves) ... ";
317                Exporter *exporter = Exporter::GetExporter("view_cells.x3d");
318
319                if (exporter)
320                {
321                        if (mExportGeometry)
322                                exporter->ExportGeometry(preprocessor->mObjects);
323
324                        ExportViewCellsForViz(exporter);
325
326                        delete exporter;
327                }
328                cout << "finished" << endl;
329        }
330
331        //-- guided rays are used for further sampling
332        const int n = mConstructionSamples; //+initialSamples;
333
334        // should we use directional samples?
335        bool dirSamples = (mSamplingType == Preprocessor::DIRECTION_BASED_DISTRIBUTION);
336
337        while (numSamples < n)
338        {
339                cout << "casting " << mSamplesPerPass << " samples of " << n << " ... ";
340                VssRayContainer constructionSamples;
341
342                const int samplingType = mSamplingType;
343                        /*dirSamples ?
344                                                Preprocessor::DIRECTION_BASED_DISTRIBUTION :
345                                                Preprocessor::SPATIAL_BOX_BASED_DISTRIBUTION;*/
346
347                if (0)
348                        dirSamples = !dirSamples; // toggle sampling method
349
350                numSamples += CastPassSamples(mSamplesPerPass,
351                                                                          samplingType,
352                                                                          constructionSamples);
353
354                cout << "finished" << endl;
355
356                cout << "computing sample contribution for " << (int)constructionSamples.size() << " samples ... ";
357
358                // TODO: leak?
359                if (SAMPLE_AFTER_SUBDIVISION)
360                        ComputeSampleContributions(constructionSamples, true, false);
361                cout << "finished" << endl;
362
363
364                disposeRays(constructionSamples, outRays);
365
366                cout << "total samples: " << numSamples << endl;
367        }
368       
369
370        //-- post processing
371        VssRayContainer postProcessSamples;
372
373        //-- construction rays
374        CastPassSamples(mPostProcessSamples,
375                                        mSamplingType,
376                                        postProcessSamples);
377
378
379        // stats before post processing (i.e., merge)
380        EvaluateViewCellsStats();
381        Debug << "\noriginal view cell partition before post process:\n" << mCurrentViewCellsStats << endl;
382
383        mRenderer->RenderScene();
384        SimulationStatistics ss;
385        dynamic_cast<RenderSimulator *>(mRenderer)->GetStatistics(ss);
386
387    Debug << ss << endl;
388
389
390
391        cout << "starting post processing and visualization" << endl;
392
393
394        // store view cells for postprocessing
395        const bool storeViewCells = true;
396
397
398        if (SAMPLE_AFTER_SUBDIVISION)
399                ComputeSampleContributions(postProcessSamples, true, storeViewCells);
400
401        // merge the view cells
402        PostProcess(preprocessor->mObjects, postProcessSamples);
403
404        // only for testing
405        if (TEST_EMPTY_VIEW_CELLS)
406                CollectEmptyViewCells();
407
408
409        //-- visualization
410        if (mShowVisualization)
411        {
412                VssRayContainer visualizationSamples;
413
414                //-- construction rays => we use uniform samples for this
415                CastPassSamples(mVisualizationSamples,
416                                            Preprocessor::DIRECTION_BASED_DISTRIBUTION,
417                                                visualizationSamples);
418
419                if (SAMPLE_AFTER_SUBDIVISION)
420                        ComputeSampleContributions(visualizationSamples, true, storeViewCells);
421
422                // different visualizations
423                Visualize(preprocessor->mObjects, visualizationSamples);
424
425                disposeRays(visualizationSamples, outRays);
426        }
427
428        if (mEvaluateViewCells)
429        {
430                EvalViewCellPartition(preprocessor);
431        }
432       
433        if (0)
434        {
435                ViewCellContainer leaves;
436                mViewCellsTree->CollectLeaves(mViewCellsTree->GetRoot(), leaves);
437                mViewCellsTree->ResetPvs();
438                VssRayContainer dummyRays;
439                CastPassSamples(mInitialSamples, mSamplingType, dummyRays);
440       
441                //ComputeSampleContributions(initialSamples, true, false);
442                ComputeSampleContributions(dummyRays, true, false);
443
444                ViewCellContainer::const_iterator it, it_end = leaves.end();
445
446                for (it = leaves.begin(); it != it_end; ++ it)
447                {
448                        mViewCellsTree->PropagatePvs(*it);
449                }
450
451                mViewCellsTree->ExportStats("dummy.log");
452        }
453
454        return numSamples;
455}
456
457
458void ViewCellsManager::EvalViewCellPartition(Preprocessor *preprocessor)
459{
460        int samplesPerPass;
461        int numSamples;
462        int castSamples = 0;
463
464        char s[64];
465
466        environment->GetIntValue("ViewCells.Evaluation.samplesPerPass", samplesPerPass);
467        environment->GetIntValue("ViewCells.Evaluation.samples", numSamples);
468
469        char statsPrefix[100];
470        environment->GetStringValue("ViewCells.Evaluation.statsPrefix", statsPrefix);
471
472        Debug << "view cell evaluation samples per pass: " << samplesPerPass << endl;
473        Debug << "view cell evaluation samples: " << numSamples << endl;
474        Debug << "view cell stats prefix: " << statsPrefix << endl;
475
476        //VssRayContainer outRays;
477        // should directional sampling be used?
478        bool dirSamples = mSamplingType == Preprocessor::DIRECTION_BASED_DISTRIBUTION;
479
480        cout << "Evaluating view cell partition" << endl;
481
482        ViewCellContainer leaves;
483        mViewCellsTree->CollectLeaves(mViewCellsTree->GetRoot(), leaves);
484
485        bool startFromZero = true;
486
487        // reset pvs and start over from zero
488        if (startFromZero)
489        {
490                mViewCellsTree->ResetPvs();
491        }
492        else // statistics without addidtional samples
493        {
494                cout << "compute new statistics ... ";
495                sprintf(s, "-%09d-eval.log", castSamples);
496                string fName = string(statsPrefix) + string(s);
497
498                mViewCellsTree->ExportStats(fName);
499                cout << "finished" << endl;
500        }
501       
502
503        while (castSamples < numSamples)
504        {
505                VssRayContainer evaluationSamples;
506
507                const int samplingType = mSamplingType;
508                /*      dirSamples ?
509                                                Preprocessor::DIRECTION_BASED_DISTRIBUTION :
510                                                Preprocessor::SPATIAL_BOX_BASED_DISTRIBUTION;
511                */
512                //-- construction rays => we use uniform samples for this
513                CastPassSamples(samplesPerPass, samplingType, evaluationSamples);
514               
515                castSamples += samplesPerPass;
516
517                cout << "casting " << (int)evaluationSamples.size() << " samples " << endl;
518
519                ComputeSampleContributions(evaluationSamples, true, false);
520
521                cout << "compute new statistics ... ";
522
523                ViewCellContainer::const_iterator it, it_end = leaves.end();
524
525                for (it = leaves.begin(); it != it_end; ++ it)
526                {
527                        mViewCellsTree->PropagatePvs(*it);
528                }
529
530                // output stats
531                sprintf(s, "-%09d-eval.log", castSamples);
532                string fileName = string(statsPrefix) + string(s);
533
534                mViewCellsTree->ExportStats(fileName);
535
536                cout << "finished" << endl;
537       
538                disposeRays(evaluationSamples, NULL);
539        }
540
541        // find empty view cells bug
542        if (TEST_EMPTY_VIEW_CELLS)
543                TestEmptyViewCells(preprocessor->mObjects);
544}
545
546
547bool ViewCellsManager::CheckValidity(ViewCell *vc,
548                                                                         int minPvsSize,
549                                                                         int maxPvsSize) const
550{
551
552  if ((vc->GetPvs().GetSize() > maxPvsSize) ||
553          (vc->GetPvs().GetSize() < minPvsSize))
554        {
555          return false;
556        }
557
558  return true;
559}
560
561
562AxisAlignedBox3 ViewCellsManager::GetFilterBBox(const Vector3 &viewPoint,
563                                                                                                const float width) const
564{
565        Vector3 min = viewPoint - width * 0.5f;
566        Vector3 max = viewPoint + width * 0.5;
567
568        return AxisAlignedBox3(min, max);
569}
570
571
572void ViewCellsManager::GetPrVS(const Vector3 &viewPoint, PrVs &prvs)
573{
574        const AxisAlignedBox3 box = GetFilterBBox(viewPoint, mFilterWidth);
575
576        ViewCellContainer viewCells;
577        ComputeBoxIntersections(box, viewCells);
578
579               
580}
581
582
583bool ViewCellsManager::ViewCellsTreeConstructed() const
584{
585        return mViewCellsTree->GetRoot();
586}
587
588
589void ViewCellsManager::SetValidity(ViewCell *vc,
590                                                                   int minPvs,
591                                                                   int maxPvs) const
592{
593        vc->SetValid(CheckValidity(vc, minPvs, maxPvs));
594}
595
596
597void
598ViewCellsManager::SetValidity(
599                                                          int minPvsSize,
600                                                          int maxPvsSize) const
601{
602  ViewCellContainer::const_iterator it, it_end = mViewCells.end();
603
604  for (it = mViewCells.begin(); it != it_end; ++ it) {
605        SetValidity(*it, minPvsSize, maxPvsSize);
606  }
607}
608
609void
610ViewCellsManager::SetValidityPercentage(
611                                                                                const float minValid,
612                                                                                const float maxValid
613                                                                                )
614{
615  sort(mViewCells.begin(), mViewCells.end(), ViewCell::SmallerPvs);
616
617  int start = mViewCells.size()*minValid;
618  int end = mViewCells.size()*maxValid;
619
620  for (int i=0; i < mViewCells.size(); i++)
621        mViewCells[i]->SetValid(i >= start && i <= end);
622}
623
624int
625ViewCellsManager::CountValidViewcells() const
626{
627  ViewCellContainer::const_iterator it, it_end = mViewCells.end();
628  int valid = 0;
629  for (it = mViewCells.begin(); it != it_end; ++ it) {
630        if ((*it)->GetValid())
631          valid++;
632  }
633  return valid;
634}
635
636
637bool ViewCellsManager::LoadViewCellsGeometry(const string filename)
638{
639        X3dParser parser;
640
641        environment->GetFloatValue("ViewCells.height", parser.mViewCellHeight);
642
643        bool success = parser.ParseFile(filename, *this);
644        Debug << (int)mViewCells.size() << " view cells loaded" << endl;
645
646        return success;
647}
648
649
650bool ViewCellsManager::GetViewPoint(Vector3 &viewPoint) const
651{
652        viewPoint = mViewSpaceBox.GetRandomPoint();
653
654        return true;
655}
656
657
658float ViewCellsManager::GetViewSpaceVolume()
659{
660        return mViewSpaceBox.GetVolume() * (2.0f * sqr((float)M_PI));
661}
662
663
664bool ViewCellsManager::ViewPointValid(const Vector3 &viewPoint) const
665{
666  if (!ViewCellsConstructed())
667        return mViewSpaceBox.IsInside(viewPoint);
668  else {
669        if (!mViewSpaceBox.IsInside(viewPoint))
670          return false;
671        ViewCell *viewcell = GetViewCell(viewPoint);
672        if (!viewcell || !viewcell->GetValid())
673          return false;
674  }
675  return true;
676}
677
678
679float
680ViewCellsManager::ComputeSampleContributions(const VssRayContainer &rays,
681                                                                                         const bool addRays,
682                                                                                         const bool storeViewCells
683                                                                                         )
684{
685  // view cells not yet constructed
686  if (!ViewCellsConstructed())
687        return 0.0f;
688
689  VssRayContainer::const_iterator it, it_end = rays.end();
690
691  float sum = 0.0f;
692  for (it = rays.begin(); it != it_end; ++ it)
693  {
694          sum += ComputeSampleContributions(*(*it), addRays, storeViewCells);
695          //ComputeSampleContributions(*(*it), addRays);
696          //    sum += (*it)->mPvsContribution;
697  }
698
699  return sum;
700}
701
702
703void ViewCellsManager::EvaluateViewCellsStats()
704{
705        mCurrentViewCellsStats.Reset();
706
707        ViewCellContainer::const_iterator it, it_end = mViewCells.end();
708
709        for (it = mViewCells.begin(); it != it_end; ++ it)
710        {
711                mViewCellsTree->UpdateViewCellsStats(*it, mCurrentViewCellsStats);
712        }
713}
714
715
716void ViewCellsManager::EvaluateRenderStatistics(float &totalRenderCost,
717                                                                                                float &expectedRenderCost,
718                                                                                                float &deviation,
719                                                                                                float &variance,
720                                                                                                int &totalPvs,
721                                                                                                float &avgRenderCost)
722{
723        ViewCellContainer::const_iterator it, it_end = mViewCells.end();
724
725
726        //-- compute expected value
727
728        totalRenderCost = 0;
729        totalPvs = 0;
730
731        for (it = mViewCells.begin(); it != it_end; ++ it)
732        {
733                ViewCell *vc = *it;
734                totalRenderCost += vc->GetPvs().GetSize() * vc->GetVolume();
735                totalPvs += (int)vc->GetPvs().GetSize();
736        }
737
738        // normalize with view space box
739        totalRenderCost /= mViewSpaceBox.GetVolume();
740        expectedRenderCost = totalRenderCost / (float)mViewCells.size();
741        avgRenderCost = totalPvs / (float)mViewCells.size();
742
743
744        //-- compute standard defiation
745        variance = 0;
746        deviation = 0;
747
748        for (it = mViewCells.begin(); it != it_end; ++ it)
749        {
750                ViewCell *vc = *it;
751
752                float renderCost = vc->GetPvs().GetSize() * vc->GetVolume();
753                float dev;
754
755                if (1)
756                        dev = fabs(avgRenderCost - (float)vc->GetPvs().GetSize());
757                else
758                        dev = fabs(expectedRenderCost - renderCost);
759
760                deviation += dev;
761                variance += dev * dev;
762        }
763
764        variance /= (float)mViewCells.size();
765        deviation /= (float)mViewCells.size();
766}
767
768
769
770void ViewCellsManager::AddViewCell(ViewCell *viewCell)
771{
772        mViewCells.push_back(viewCell);
773}
774
775
776float ViewCellsManager::GetArea(ViewCell *viewCell) const
777{
778        return viewCell->GetArea();
779}
780
781
782float ViewCellsManager::GetVolume(ViewCell *viewCell) const
783{
784        return viewCell->GetVolume();
785}
786
787
788void ViewCellsManager::DeriveViewCells(const ObjectContainer &objects,
789                                                                           ViewCellContainer &viewCells,
790                                                                           const int maxViewCells) const
791{
792        // maximal max viewcells
793        int limit = maxViewCells > 0 ?
794                Min((int)objects.size(), maxViewCells) : (int)objects.size();
795
796        for (int i = 0; i < limit; ++ i)
797        {
798                Intersectable *object = objects[i];
799
800                // extract the mesh instances
801                if (object->Type() == Intersectable::MESH_INSTANCE)
802                {
803                        MeshInstance *inst = dynamic_cast<MeshInstance *>(object);
804
805                        ViewCell *viewCell = GenerateViewCell(inst->GetMesh());
806                        viewCells.push_back(viewCell);
807                }
808                //TODO: transformed meshes
809        }
810}
811
812
813ViewCell *ViewCellsManager::ExtrudeViewCell(const Triangle3 &baseTri,
814                                                                                        const float height) const
815{
816        // one mesh per view cell
817        Mesh *mesh = new Mesh();
818
819        //-- construct prism
820
821        // bottom
822        mesh->mFaces.push_back(new Face(2,1,0));
823        // top
824    mesh->mFaces.push_back(new Face(3,4,5));
825        // sides
826        mesh->mFaces.push_back(new Face(1, 4, 3, 0));
827        mesh->mFaces.push_back(new Face(2, 5, 4, 1));
828        mesh->mFaces.push_back(new Face(3, 5, 2, 0));
829
830        //--- extrude new vertices for top of prism
831        Vector3 triNorm = baseTri.GetNormal();
832
833        Triangle3 topTri;
834
835        // add base vertices and calculate top vertices
836        for (int i = 0; i < 3; ++ i)
837                mesh->mVertices.push_back(baseTri.mVertices[i]);
838
839        // add top vertices
840        for (int i = 0; i < 3; ++ i)
841                mesh->mVertices.push_back(baseTri.mVertices[i] + height * triNorm);
842
843        mesh->Preprocess();
844
845        return GenerateViewCell(mesh);
846}
847
848
849void ViewCellsManager::FinalizeViewCells(const bool createMesh)
850{
851        ViewCellContainer::const_iterator it, it_end = mViewCells.end();
852
853        // volume and area of the view cells are recomputed and a view cell mesh is created
854        for (it = mViewCells.begin(); it != it_end; ++ it)
855        {
856                Finalize(*it, createMesh);
857        }
858
859        mTotalAreaValid = false;
860}
861
862
863void ViewCellsManager::Finalize(ViewCell *viewCell, const bool createMesh)
864{
865        // implemented in subclasses
866}
867
868
869ViewCellInterior *ViewCellsManager::MergeViewCells(ViewCell *left, ViewCell *right) const
870{
871        // generate parent view cell
872        ViewCellInterior *vc = new ViewCellInterior();//GenerateViewCell();
873
874        vc->GetPvs() = left->GetPvs();
875        // merge pvs
876        vc->GetPvs().Merge(right->GetPvs());
877
878        //-- merge ray sets
879        if (0)
880        {
881                stable_sort(left->mPiercingRays.begin(), left->mPiercingRays.end());
882                stable_sort(right->mPiercingRays.begin(), right->mPiercingRays.end());
883
884                std::merge(left->mPiercingRays.begin(), left->mPiercingRays.end(),
885                                   right->mPiercingRays.begin(), right->mPiercingRays.end(),
886                                   vc->mPiercingRays.begin());
887        }
888
889
890        vc->SetupChildLink(left);
891        vc->SetupChildLink(right);
892
893
894        return vc;
895}
896
897
898ViewCellInterior *ViewCellsManager::MergeViewCells(ViewCellContainer &children) const
899{
900        ViewCellInterior *vc = new ViewCellInterior();//GenerateViewCell();
901
902        ViewCellContainer::const_iterator it, it_end = children.end();
903
904        for (it = children.begin(); it != it_end; ++ it)
905        {
906                // merge pvs
907                vc->GetPvs().Merge((*it)->GetPvs());
908
909                vc->SetupChildLink(*it);
910        }
911
912        return vc;
913}
914
915
916void ViewCellsManager::SetRenderer(Renderer *renderer)
917{
918        mRenderer = renderer;
919}
920
921
922ViewCellsTree *ViewCellsManager::GetViewCellsTree()
923{
924        return mViewCellsTree;
925}
926
927
928void ViewCellsManager::SetVisualizationSamples(const int visSamples)
929{
930        mVisualizationSamples = visSamples;
931}
932
933
934void ViewCellsManager::SetConstructionSamples(const int constructionSamples)
935{
936        mConstructionSamples = constructionSamples;
937}
938
939
940void ViewCellsManager::SetInitialSamples(const int initialSamples)
941{
942        mInitialSamples = initialSamples;
943}
944
945
946void ViewCellsManager::SetPostProcessSamples(const int postProcessSamples)
947{
948        mPostProcessSamples = postProcessSamples;
949}
950
951
952int ViewCellsManager::GetVisualizationSamples() const
953{
954        return mVisualizationSamples;
955}
956
957
958int ViewCellsManager::GetConstructionSamples() const
959{
960        return mConstructionSamples;
961}
962
963
964int ViewCellsManager::GetPostProcessSamples() const
965{
966        return mPostProcessSamples;
967}
968
969
970void ViewCellsManager::GetPvsStatistics(PvsStatistics &stat)
971{
972  ViewCellContainer::const_iterator it = mViewCells.begin();
973  stat.viewcells = 0;
974  stat.minPvs = 100000000;
975  stat.maxPvs = 0;
976  stat.avgPvs = 0.0f;
977
978  for (; it != mViewCells.end(); ++it) {
979        ViewCell *viewcell = *it;
980        int pvsSize = viewcell->GetPvs().GetSize();
981        if ( pvsSize < stat.minPvs)
982          stat.minPvs = pvsSize;
983        if (pvsSize > stat.maxPvs)
984          stat.maxPvs = pvsSize;
985        stat.avgPvs += pvsSize;
986        stat.viewcells++;
987  }
988  if (stat.viewcells)
989        stat.avgPvs/=stat.viewcells;
990}
991
992
993void ViewCellsManager::PrintPvsStatistics(ostream &s)
994{
995  s<<"############# Viewcell PVS STAT ##################\n";
996  PvsStatistics pvsStat;
997  GetPvsStatistics(pvsStat);
998  s<<"#AVG_PVS\n"<<pvsStat.avgPvs<<endl;
999  s<<"#MAX_PVS\n"<<pvsStat.maxPvs<<endl;
1000  s<<"#MIN_PVS\n"<<pvsStat.minPvs<<endl;
1001}
1002
1003
1004int ViewCellsManager::CastBeam(Beam &beam)
1005{
1006        return 0;
1007}
1008
1009
1010ViewCellContainer &ViewCellsManager::GetViewCells()
1011{
1012        return mViewCells;
1013}
1014
1015
1016void ViewCellsManager::SetViewSpaceBox(const AxisAlignedBox3 &box)
1017{
1018        mViewSpaceBox = box;
1019
1020        CreateClipPlane();
1021       
1022        mTotalAreaValid = false;
1023}
1024
1025
1026void ViewCellsManager::CreateClipPlane()
1027{
1028        int axis = 0;
1029        float pos;
1030
1031        environment->GetFloatValue("ViewCells.Visualization.clipPlanePos", pos);
1032
1033        Vector3 point = mViewSpaceBox.Min() +  mViewSpaceBox.Size() * pos;
1034
1035        if (mUseClipPlaneForViz)
1036        environment->GetIntValue("ViewCells.Visualization.clipPlaneAxis", axis);
1037
1038        Vector3 normal(0,0,0);
1039        normal[axis] = 1;
1040
1041        mClipPlane = Plane3(normal, point);
1042}
1043
1044
1045AxisAlignedBox3 ViewCellsManager::GetViewSpaceBox() const
1046{
1047        return mViewSpaceBox;
1048}
1049
1050
1051void ViewCellsManager::ResetViewCells()
1052{
1053        mViewCells.clear();
1054       
1055        CollectViewCells();
1056       
1057        mCurrentViewCellsStats.Reset();
1058        EvaluateViewCellsStats();
1059
1060        // has to be recomputed
1061        mTotalAreaValid = false;
1062}
1063
1064
1065int ViewCellsManager::GetMaxPvsSize() const
1066{
1067        return mMaxPvsSize;
1068}
1069
1070
1071void
1072ViewCellsManager::AddSampleContributions(const VssRayContainer &rays)
1073{
1074  if (!ViewCellsConstructed())
1075        return;
1076
1077  VssRayContainer::const_iterator it, it_end = rays.end();
1078
1079  for (it = rays.begin(); it != it_end; ++ it) {
1080        AddSampleContributions(*(*it));
1081  }
1082}
1083
1084
1085int ViewCellsManager::GetMinPvsSize() const
1086{
1087        return mMinPvsSize;
1088}
1089
1090
1091
1092float ViewCellsManager::GetMaxPvsRatio() const
1093{
1094        return mMaxPvsRatio;
1095}
1096
1097
1098void
1099ViewCellsManager::AddSampleContributions(VssRay &ray)
1100{
1101  // assumes viewcells have been stored...
1102  ViewCellContainer *viewcells = &ray.mViewCells;
1103  ViewCellContainer::const_iterator it;
1104  for (it = viewcells->begin(); it != viewcells->end(); ++it) {
1105        ViewCell *viewcell = *it;
1106        if (viewcell->GetValid()) {
1107          // if ray not outside of view space
1108          viewcell->GetPvs().AddSample(ray.mTerminationObject, ray.mPdf);
1109        }
1110  }
1111}
1112
1113
1114float ViewCellsManager::ComputeSampleContributions(VssRay &ray,
1115                                                                                                   const bool addRays,
1116                                                                                                   const bool storeViewCells)
1117{
1118        ViewCellContainer viewcells;
1119
1120        ray.mPvsContribution = 0;
1121        ray.mRelativePvsContribution = 0.0f;
1122
1123        static Ray hray;
1124        hray.Init(ray);
1125        //hray.mFlags |= Ray::CULL_BACKFACES;
1126        //Ray hray(ray);
1127
1128        float tmin = 0, tmax = 1.0;
1129
1130        if (!GetViewSpaceBox().GetRaySegment(hray, tmin, tmax) || (tmin > tmax))
1131                return 0;
1132
1133        Vector3 origin = hray.Extrap(tmin);
1134        Vector3 termination = hray.Extrap(tmax);
1135
1136        CastLineSegment(origin, termination, viewcells);
1137
1138        // copy viewcells memory efficiently
1139        //const bool storeViewcells = !addRays;
1140
1141        if (storeViewCells)
1142        {
1143                ray.mViewCells.reserve(viewcells.size());
1144                ray.mViewCells = viewcells;
1145        }
1146
1147        ViewCellContainer::const_iterator it = viewcells.begin();
1148
1149        for (; it != viewcells.end(); ++ it)
1150        {
1151                ViewCell *viewcell = *it;
1152
1153                if (viewcell->GetValid())
1154                {
1155                        // HACK
1156                        if (TEST_EMPTY_VIEW_CELLS)
1157                                for (int i = 0; i < mEmptyViewCells.size(); ++i)
1158                                {
1159                                        if (viewcell == mEmptyViewCells[i])
1160                                        {
1161                                                viewcell->mPiercingRays.push_back(new Ray(ray));
1162                                                Debug << "empty view cell ray found: " << ray.mOriginObject << ", " << ray.mTerminationObject << endl;
1163                                        }
1164                                }
1165
1166                        // if ray not outside of view space
1167                        float contribution;
1168                        if (ray.mTerminationObject &&
1169                                viewcell->GetPvs().GetSampleContribution(ray.mTerminationObject,
1170                                                                                                                 ray.mPdf,
1171                                                                                                                 contribution))
1172                        {
1173                                ++ ray.mPvsContribution;
1174                                ray.mRelativePvsContribution += contribution;
1175                        }
1176                        if (ray.mOriginObject &&
1177                                viewcell->GetPvs().GetSampleContribution(ray.mOriginObject,
1178                                                                                                                 ray.mPdf,
1179                                                                                                                 contribution))
1180                        {
1181                                ++ ray.mPvsContribution;
1182                                ray.mRelativePvsContribution += contribution;
1183                        }
1184                }
1185        }
1186
1187       
1188        if (addRays)
1189        {
1190                for (it = viewcells.begin(); it != viewcells.end(); ++ it)
1191                {
1192                        ViewCell *viewcell = *it;
1193           
1194                        if (viewcell->GetValid())
1195                        {
1196                                // if ray not outside of view space
1197                                 if (ray.mTerminationObject)
1198                                         viewcell->GetPvs().AddSample(ray.mTerminationObject, ray.mPdf);
1199                                 if (ray.mOriginObject)
1200                                         viewcell->GetPvs().AddSample(ray.mOriginObject, ray.mPdf);
1201                        }
1202                }
1203        }
1204
1205        return ray.mRelativePvsContribution;
1206}
1207
1208
1209void ViewCellsManager::GetRaySets(const VssRayContainer &sourceRays,
1210                                                                  const int maxSize,
1211                                                                  VssRayContainer &usedRays,
1212                                                                  VssRayContainer *savedRays) const
1213{
1214        const int limit = min(maxSize, (int)sourceRays.size());
1215        const float prop = (float)limit / ((float)sourceRays.size() + Limits::Small);
1216
1217        VssRayContainer::const_iterator it, it_end = sourceRays.end();
1218        for (it = sourceRays.begin(); it != it_end; ++ it)
1219        {
1220                if (Random(1.0f) < prop)
1221                        usedRays.push_back(*it);
1222                else if (savedRays)
1223                        savedRays->push_back(*it);
1224        }
1225}
1226
1227
1228float ViewCellsManager::GetRendercost(ViewCell *viewCell, float objRendercost) const
1229{
1230        return mViewCellsTree->GetPvsSize(viewCell) * objRendercost;
1231}
1232
1233
1234float ViewCellsManager::GetAccVcArea()
1235{
1236        // if already computed
1237        if (mTotalAreaValid)
1238                return mTotalArea;
1239
1240        mTotalArea = 0;
1241        ViewCellContainer::const_iterator it, it_end = mViewCells.end();
1242
1243        for (it = mViewCells.begin(); it != it_end; ++ it)
1244        {
1245                //Debug << "area: " << GetArea(*it);
1246        mTotalArea += GetArea(*it);
1247        }
1248
1249        mTotalAreaValid = true;
1250
1251        return mTotalArea;
1252}
1253
1254
1255void ViewCellsManager::PrintStatistics(ostream &s) const
1256{
1257        s << mCurrentViewCellsStats << endl;
1258}
1259
1260
1261void ViewCellsManager::CreateUniqueViewCellIds()
1262{
1263        if (ViewCellsTreeConstructed())
1264                mViewCellsTree->CreateUniqueViewCellsIds();
1265        else
1266                for (int i = 0; i < (int)mViewCells.size(); ++ i)
1267                        mViewCells[i]->SetId(i);
1268}
1269
1270
1271void ViewCellsManager::ExportViewCellsForViz(Exporter *exporter) const
1272{
1273        ViewCellContainer::const_iterator it, it_end = mViewCells.end();
1274
1275        for (it = mViewCells.begin(); it != it_end; ++ it)
1276        {
1277                if (!mOnlyValidViewCells || (*it)->GetValid())
1278                {
1279                        ExportColor(exporter, *it);             
1280                        ExportViewCellGeometry(exporter, *it,
1281                                mUseClipPlaneForViz ? &mClipPlane : NULL);
1282                }
1283        }
1284}
1285
1286
1287void ViewCellsManager::CreateViewCellMeshes()
1288{
1289        // convert to meshes
1290        ViewCellContainer::const_iterator it, it_end = mViewCells.end();
1291
1292        for (it = mViewCells.begin(); it != it_end; ++ it)
1293        {
1294                if (!(*it)->GetMesh())
1295                        CreateMesh(*it);
1296        }
1297}
1298
1299
1300bool ViewCellsManager::ExportViewCells(const string filename)
1301{
1302        return false;
1303}
1304
1305
1306void ViewCellsManager::CollectViewCells(const int n)
1307{
1308        mNumActiveViewCells = n;
1309        mViewCells.clear();
1310        CollectViewCells();
1311}
1312
1313
1314void ViewCellsManager::SetViewCellsActive()
1315{
1316        ++ ViewCell::sLastUpdated;
1317        ViewCellContainer::const_iterator it, it_end = mViewCells.end();
1318        for (it = mViewCells.begin(); it != it_end; ++ it)
1319        {
1320                (*it)->SetActive();
1321        }
1322}
1323
1324/**********************************************************************/
1325/*                   BspViewCellsManager implementation               */
1326/**********************************************************************/
1327
1328
1329BspViewCellsManager::BspViewCellsManager(BspTree *bspTree):
1330ViewCellsManager(), mBspTree(bspTree)
1331{
1332        environment->GetIntValue("BspTree.Construction.samples", mInitialSamples);
1333        mBspTree->SetViewCellsManager(this);
1334        mBspTree->mViewCellsTree = mViewCellsTree;
1335}
1336
1337
1338bool BspViewCellsManager::ViewCellsConstructed() const
1339{
1340        return mBspTree->GetRoot() != NULL;
1341}
1342
1343
1344ViewCell *BspViewCellsManager::GenerateViewCell(Mesh *mesh) const
1345{
1346        return new BspViewCell(mesh);
1347}
1348
1349
1350int BspViewCellsManager::ConstructSubdivision(const ObjectContainer &objects,
1351                                                                                          const VssRayContainer &rays)
1352{
1353        // if view cells were already constructed
1354        if (ViewCellsConstructed())
1355                return 0;
1356
1357        int sampleContributions = 0;
1358
1359        // construct view cells using the collected samples
1360        RayContainer constructionRays;
1361        VssRayContainer savedRays;
1362
1363        const int limit = min(mInitialSamples, (int)rays.size());
1364
1365        VssRayContainer::const_iterator it, it_end = rays.end();
1366
1367        const float prop = (float)limit / ((float)rays.size() + Limits::Small);
1368
1369        for (it = rays.begin(); it != it_end; ++ it)
1370        {
1371                if (Random(1.0f) < prop)
1372                        constructionRays.push_back(new Ray(*(*it)));
1373                else
1374                        savedRays.push_back(*it);
1375        }
1376
1377    if (mViewCells.empty())
1378        {
1379                // no view cells loaded
1380                mBspTree->Construct(objects, constructionRays, &mViewSpaceBox);
1381                // collect final view cells
1382                mBspTree->CollectViewCells(mViewCells);
1383        }
1384        else
1385        {
1386                mBspTree->Construct(mViewCells);
1387        }
1388
1389        // destroy rays created only for construction
1390        CLEAR_CONTAINER(constructionRays);
1391
1392        Debug << mBspTree->GetStatistics() << endl;
1393
1394        //EvaluateViewCellsStats();
1395        Debug << "\nView cells after construction:\n" << mCurrentViewCellsStats << endl;
1396
1397        // recast rest of the rays
1398        if (SAMPLE_AFTER_SUBDIVISION)
1399                ComputeSampleContributions(savedRays, true, false);
1400
1401        return sampleContributions;
1402}
1403
1404
1405void BspViewCellsManager::CollectViewCells()
1406{
1407        // view cells tree constructed
1408        if (!ViewCellsTreeConstructed())
1409        {               
1410                mBspTree->CollectViewCells(mViewCells);
1411        }
1412        else
1413        {
1414                // we can use the view cells tree hierarchy to get the right set
1415                mViewCellsTree->CollectBestViewCellSet(mViewCells,
1416                                                                                           mNumActiveViewCells);
1417        }
1418}
1419
1420
1421float BspViewCellsManager::GetProbability(ViewCell *viewCell)
1422{
1423        // compute view cell area as subsititute for probability
1424        if (1)
1425                return GetVolume(viewCell) / GetViewSpaceBox().GetVolume();
1426        else
1427                return GetArea(viewCell) / GetAccVcArea();
1428}
1429
1430
1431
1432int BspViewCellsManager::CastLineSegment(const Vector3 &origin,
1433                                                                                 const Vector3 &termination,
1434                                                                                 ViewCellContainer &viewcells)
1435{
1436        return mBspTree->CastLineSegment(origin, termination, viewcells);
1437}
1438
1439
1440int BspViewCellsManager::PostProcess(const ObjectContainer &objects,
1441                                                                         const VssRayContainer &rays)
1442{
1443        if (!ViewCellsConstructed())
1444        {
1445                Debug << "view cells not constructed" << endl;
1446                return 0;
1447        }
1448       
1449        // view cells already finished before post processing step (i.e. because they were loaded)
1450        if (mViewCellsFinished)
1451        {
1452                FinalizeViewCells(true);
1453                EvaluateViewCellsStats();
1454
1455                return 0;
1456        }
1457
1458        //-- post processing of bsp view cells
1459
1460    int vcSize = 0;
1461        int pvsSize = 0;
1462
1463        //-- merge view cells
1464        cout << "starting post processing using " << mPostProcessSamples << " samples ... ";
1465        long startTime = GetTime();
1466       
1467        VssRayContainer postProcessRays;
1468        GetRaySets(rays, mPostProcessSamples, postProcessRays);
1469
1470        if (mMergeViewCells)
1471        {
1472                cout << "constructing visibility based merge tree" << endl;
1473                mViewCellsTree->ConstructMergeTree(rays, objects);
1474        }
1475        else
1476        {
1477                cout << "constructing spatial merge tree" << endl;
1478                // create spatial merge hierarchy
1479                mViewCellsTree->SetRoot(ConstructSpatialMergeTree(mBspTree->GetRoot()));
1480        }
1481
1482        // export statistics after merge
1483        if (1)
1484        {
1485                char mstats[100];
1486                environment->GetStringValue("ViewCells.mergeStats", mstats);
1487                mViewCellsTree->ExportStats(mstats);
1488        }
1489
1490        //-- stats and visualizations
1491        cout << "finished" << endl;
1492        cout << "merged view cells in "
1493                 << TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl;
1494
1495        Debug << "Postprocessing: Merged view cells in "
1496                << TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl << endl;
1497       
1498
1499        //-- visualization and statistics
1500    // reset view cells and stats
1501        ResetViewCells();
1502        Debug << "\nView cells after merge:\n" << mCurrentViewCellsStats << endl;
1503
1504
1505        int savedColorCode  = mColorCode;
1506       
1507        //BspLeaf::NewMail();
1508        if (1) // export merged view cells
1509        {
1510                mColorCode = 0;
1511               
1512                Exporter *exporter = Exporter::GetExporter("merged_view_cells.x3d");
1513               
1514
1515                cout << "exporting view cells after merge ... ";
1516
1517                if (exporter)
1518                {
1519                        if (mExportGeometry)
1520                                exporter->ExportGeometry(objects);
1521
1522                        //exporter->SetWireframe();
1523                        exporter->SetFilled();
1524                        ExportViewCellsForViz(exporter);
1525
1526
1527                        delete exporter;
1528                }
1529                cout << "finished" << endl;
1530        }
1531
1532        if (1) // export merged view cells
1533        {
1534                mColorCode = 1;
1535
1536                Exporter *exporter = Exporter::GetExporter("merged_view_cells_pvs.x3d");
1537       
1538                cout << "exporting view cells after merge (pvs size) ... ";     
1539
1540                if (exporter)
1541                {
1542                        //exporter->SetWireframe();
1543                       
1544                        if (mExportGeometry)
1545                                exporter->ExportGeometry(objects);
1546
1547                        //exporter->SetWireframe();
1548                        exporter->SetFilled();
1549                        ExportViewCellsForViz(exporter);
1550
1551                        delete exporter;
1552                }
1553                cout << "finished" << endl;
1554        }
1555
1556       
1557        // only for testing
1558        TestSubdivision();
1559
1560        mColorCode = savedColorCode;
1561
1562        FinalizeViewCells(true);
1563       
1564        // write view cells to disc
1565        if (mExportViewCells)
1566        {
1567                char buff[100];
1568                environment->GetStringValue("ViewCells.filename", buff);
1569                string vcFilename(buff);
1570
1571                ExportViewCells(buff);
1572        }
1573
1574        return 0;
1575}
1576
1577
1578BspViewCellsManager::~BspViewCellsManager()
1579{
1580}
1581
1582
1583int BspViewCellsManager::GetType() const
1584{
1585        return BSP;
1586}
1587
1588
1589void BspViewCellsManager::Visualize(const ObjectContainer &objects,
1590                                                                        const VssRayContainer &sampleRays)
1591{
1592        if (!ViewCellsConstructed())
1593                return;
1594       
1595        int savedColorCode = mColorCode;
1596
1597       
1598       
1599        if (1) // export final view cells
1600        {
1601                mColorCode = 1;
1602
1603                Exporter *exporter = Exporter::GetExporter("final_view_cells.x3d");
1604       
1605                cout << "exporting view cells after merge (pvs size) ... ";     
1606
1607                if (exporter)
1608                {
1609                        //exporter->SetWireframe();
1610                       
1611                        if (mExportGeometry)
1612                                exporter->ExportGeometry(objects);
1613
1614                        //exporter->SetWireframe();
1615                        exporter->SetFilled();
1616                        ExportViewCellsForViz(exporter);
1617
1618                        delete exporter;
1619                }
1620                cout << "finished" << endl;
1621        }
1622
1623        mColorCode = savedColorCode;
1624
1625        //-- visualization of the BSP splits
1626        bool exportSplits = false;
1627        environment->GetBoolValue("BspTree.Visualization.exportSplits", exportSplits);
1628
1629        if (exportSplits)
1630        {
1631                cout << "exporting splits ... ";
1632                ExportSplits(objects);
1633                cout << "finished" << endl;
1634        }
1635
1636        // export single view cells
1637        ExportBspPvs(objects);
1638}
1639
1640
1641inline bool vc_gt(ViewCell *a, ViewCell *b)
1642{
1643        return a->GetPvs().GetSize() > b->GetPvs().GetSize();
1644}
1645
1646
1647void BspViewCellsManager::ExportSplits(const ObjectContainer &objects)
1648{
1649        Exporter *exporter = Exporter::GetExporter("bsp_splits.x3d");
1650
1651        if (exporter)
1652        {
1653                //exporter->SetFilled();
1654
1655                if (mExportGeometry)
1656                        exporter->ExportGeometry(objects);
1657
1658                Material m;
1659                m.mDiffuseColor = RgbColor(1, 0, 0);
1660                exporter->SetForcedMaterial(m);
1661                exporter->SetWireframe();
1662
1663                exporter->ExportBspSplits(*mBspTree, true);
1664
1665                //NOTE: take forced material, else big scenes cannot be viewed
1666                m.mDiffuseColor = RgbColor(0, 1, 0);
1667                exporter->SetForcedMaterial(m);
1668                //exporter->ResetForcedMaterial();
1669
1670                delete exporter;
1671        }
1672}
1673
1674
1675void BspViewCellsManager::ExportBspPvs(const ObjectContainer &objects)
1676{
1677        const int leafOut = 10;
1678
1679        ViewCell::NewMail();
1680
1681        //-- some rays for output
1682        const int raysOut = min((int)mBspRays.size(), mVisualizationSamples);
1683
1684        cout << "visualization using " << mVisualizationSamples << " samples" << endl;
1685        Debug << "\nOutput view cells: " << endl;
1686
1687        // sort view cells to get largest view cells
1688        if (0)
1689                stable_sort(mViewCells.begin(), mViewCells.end(), vc_gt);
1690
1691        int limit = min(leafOut, (int)mViewCells.size());
1692
1693        for (int i = 0; i < limit; ++ i)
1694        {
1695                cout << "creating output for view cell " << i << " ... ";
1696                VssRayContainer vcRays;
1697                Intersectable::NewMail();
1698                ViewCell *vc;
1699
1700                if (0)
1701                        vc = mViewCells[i];
1702                else
1703                        vc = mViewCells[Random((int)mViewCells.size())];
1704
1705                cout << "creating output for view cell " << i << " ... ";
1706
1707                if(0)
1708                {
1709                        // check whether we can add the current ray to the output rays
1710                        for (int k = 0; k < raysOut; ++ k)
1711                        {
1712                                BspRay *ray = mBspRays[k];
1713                                for     (int j = 0; j < (int)ray->intersections.size(); ++ j)
1714                                {
1715                                        BspLeaf *leaf = ray->intersections[j].mLeaf;
1716                                        if (vc == leaf->GetViewCell())
1717                                                vcRays.push_back(ray->vssRay);
1718                                }
1719                        }
1720                }
1721
1722                //bspLeaves[j]->Mail();
1723                char s[64]; sprintf(s, "bsp-pvs%04d.x3d", i);
1724
1725                Exporter *exporter = Exporter::GetExporter(s);
1726
1727                exporter->SetWireframe();
1728
1729                Material m;//= RandomMaterial();
1730                m.mDiffuseColor = RgbColor(0, 1, 0);
1731                exporter->SetForcedMaterial(m);
1732
1733                ExportViewCellGeometry(exporter, vc);
1734               
1735                // export rays piercing this view cell
1736                exporter->ExportRays(vcRays, RgbColor(0, 1, 0));
1737
1738                m.mDiffuseColor = RgbColor(1, 0, 0);
1739                exporter->SetForcedMaterial(m);
1740
1741                ObjectPvsMap::const_iterator it,
1742                        it_end = vc->GetPvs().mEntries.end();
1743
1744                exporter->SetFilled();
1745
1746                // output PVS of view cell
1747                for (it = vc->GetPvs().mEntries.begin(); it != it_end; ++ it)
1748                {
1749                        Intersectable *intersect = (*it).first;
1750
1751                        if (!intersect->Mailed())
1752                        {
1753                                Material m = RandomMaterial();
1754                                exporter->SetForcedMaterial(m);
1755
1756                                exporter->ExportIntersectable(intersect);
1757                                intersect->Mail();
1758                        }
1759                }
1760
1761                DEL_PTR(exporter);
1762                cout << "finished" << endl;
1763        }
1764
1765        Debug << endl;
1766}
1767
1768
1769void BspViewCellsManager::ExportColor(Exporter *exporter,
1770                                                                          ViewCell *vc) const
1771{
1772        const bool vcValid = CheckValidity(vc, mMinPvsSize, mMaxPvsSize);
1773
1774        float importance = 0;
1775        static Material m;
1776
1777        switch (mColorCode)
1778        {
1779        case 0: // Random
1780                {
1781                        if (vcValid)
1782                        {
1783                                m.mDiffuseColor.r = 0.5f + RandomValue(0.0f, 0.5f);
1784                                m.mDiffuseColor.g = 0.5f + RandomValue(0.0f, 0.5f);
1785                                m.mDiffuseColor.b = 0.5f + RandomValue(0.0f, 0.5f);
1786                        }
1787                        else
1788                        {
1789                                m.mDiffuseColor.r = 0.0f;
1790                                m.mDiffuseColor.g = 1.0f;
1791                                m.mDiffuseColor.b = 0.0f;
1792                        }
1793
1794                        exporter->SetForcedMaterial(m);
1795                        return;
1796                }
1797               
1798        case 1: // pvs
1799                {
1800                        importance = (float)vc->GetPvs().GetSize() /
1801                                (float)mCurrentViewCellsStats.maxPvs;
1802
1803                }
1804                break;
1805        case 2: // merges
1806                {
1807            int lSize = mViewCellsTree->GetSize(vc);
1808                        importance = (float)lSize / (float)mCurrentViewCellsStats.maxLeaves;
1809                }
1810                //break;
1811        case 3: // merge tree differene
1812                {
1813                        // TODO
1814                        //importance = (float)GetMaxTreeDiff(vc) /
1815                        //      (float)(mVspBspTree->GetStatistics().maxDepth * 2);
1816
1817                }
1818                break;
1819        default:
1820                break;
1821        }
1822
1823        // special color code for invalid view cells
1824        m.mDiffuseColor.r = importance;
1825        m.mDiffuseColor.g = 1.0f - m.mDiffuseColor.r;
1826        m.mDiffuseColor.b = vcValid ? 1.0f : 0.0f;
1827
1828        //Debug << "importance: " << importance << endl;
1829        exporter->SetForcedMaterial(m);
1830}
1831
1832
1833void BspViewCellsManager::TestSubdivision()
1834{
1835        ViewCellContainer leaves;
1836        mViewCellsTree->CollectLeaves(mViewCellsTree->GetRoot(), leaves);
1837
1838        ViewCellContainer::const_iterator it, it_end = leaves.end();
1839
1840        const float vol = mViewSpaceBox.GetVolume();
1841        float subdivVol = 0;
1842        float newVol = 0;
1843
1844        for (it = leaves.begin(); it != it_end; ++ it)
1845        {
1846                BspNodeGeometry geom;
1847                BspLeaf *leaf = dynamic_cast<BspViewCell *>(*it)->mLeaf;
1848                mBspTree->ConstructGeometry(leaf, geom);
1849
1850                const float lVol = geom.GetVolume();
1851               
1852                newVol += lVol;
1853                subdivVol += (*it)->GetVolume();
1854
1855                float thres = 0.9;
1856                if ((lVol < ((*it)->GetVolume() * thres)) ||
1857                        (lVol * thres > ((*it)->GetVolume())))
1858                        Debug << "warning: " << lVol << " " << (*it)->GetVolume() << endl;
1859        }
1860       
1861        Debug << "exact volume: " << vol << endl;
1862        Debug << "subdivision volume: " << subdivVol << endl;
1863        Debug << "new volume: " << newVol << endl;
1864}
1865
1866
1867void BspViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
1868                                                                                                 ViewCell *vc,
1869                                                                                                 const Plane3 *clipPlane) const
1870{
1871        if (vc->GetMesh())
1872        {
1873                exporter->ExportMesh(vc->GetMesh());
1874                return;
1875        }
1876
1877        BspNodeGeometry geom;
1878        mBspTree->ConstructGeometry(vc, geom);
1879
1880        if (clipPlane)
1881        {
1882                const int cf = Polygon3::ClassifyPlane(geom.GetPolys(), *clipPlane, 0.0001f);
1883
1884                if (cf == Polygon3::BACK_SIDE)
1885                {
1886                        exporter->ExportPolygons(geom.GetPolys());
1887                }
1888                else if (cf == Polygon3::SPLIT)
1889                {
1890                        BspNodeGeometry front;
1891                        BspNodeGeometry back;
1892
1893                        geom.SplitGeometry(front,
1894                                                           back,
1895                                                           *clipPlane,
1896                                                           mViewSpaceBox,
1897                                                           0.0001f);
1898
1899                        if (back.Valid())
1900                                exporter->ExportPolygons(back.GetPolys());
1901                }
1902        }
1903        else
1904        {
1905                exporter->ExportPolygons(geom.GetPolys());
1906        }
1907}
1908
1909
1910void BspViewCellsManager::CreateMesh(ViewCell *vc)
1911{
1912        if (vc->GetMesh())
1913                delete vc->GetMesh();
1914
1915        BspNodeGeometry geom;
1916       
1917        mBspTree->ConstructGeometry(vc, geom);
1918
1919        Mesh *mesh = new Mesh();
1920        geom.AddToMesh(*mesh);
1921        vc->SetMesh(mesh);
1922        mMeshContainer.push_back(mesh);
1923}
1924
1925
1926void BspViewCellsManager::Finalize(ViewCell *viewCell,
1927                                                                   const bool createMesh)
1928{
1929        float area = 0;
1930        float volume = 0;
1931
1932        ViewCellContainer leaves;
1933        mViewCellsTree->CollectLeaves(viewCell, leaves);
1934
1935        ViewCellContainer::const_iterator it, it_end = leaves.end();
1936
1937    for (it = leaves.begin(); it != it_end; ++ it)
1938        {
1939                BspNodeGeometry geom;
1940                BspLeaf *leaf = dynamic_cast<BspViewCell *>(*it)->mLeaf;
1941                mBspTree->ConstructGeometry(leaf, geom);
1942
1943                float lVol = geom.GetVolume();
1944                float lArea = geom.GetArea();
1945
1946                //(*it)->SetVolume(vol);
1947                //(*it)->SetArea(area);
1948
1949                area += lArea;
1950                volume += lVol;
1951
1952        CreateMesh(*it);
1953        }
1954
1955        viewCell->SetVolume(volume);
1956        viewCell->SetArea(area);
1957}
1958
1959
1960ViewCell *BspViewCellsManager::GetViewCell(const Vector3 &point) const
1961{
1962        if (!mBspTree)
1963                return NULL;
1964
1965        if (!mViewSpaceBox.IsInside(point))
1966                return NULL;
1967       
1968        return mBspTree->GetViewCell(point);
1969}
1970
1971
1972void BspViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays,
1973                                                                                                 vector<MergeCandidate> &candidates)
1974{
1975        cout << "collecting merge candidates ... " << endl;
1976
1977        if (mUseRaysForMerge)
1978        {
1979                mBspTree->CollectMergeCandidates(rays, candidates);
1980        }
1981        else
1982        {
1983                vector<BspLeaf *> leaves;
1984                mBspTree->CollectLeaves(leaves);
1985                mBspTree->CollectMergeCandidates(leaves, candidates);
1986        }
1987
1988        cout << "fininshed collecting candidates" << endl;
1989}
1990
1991
1992
1993bool BspViewCellsManager::ExportViewCells(const string filename)
1994{
1995        cout << "exporting view cells to xml ... ";
1996        std::ofstream stream;
1997
1998        // for output we need unique ids for each view cell
1999        CreateUniqueViewCellIds();
2000
2001
2002        stream.open(filename.c_str());
2003        stream << "<?xml version=\"1.0\" encoding=\"UTF-8\"?>"<<endl;
2004        stream << "<Visibility_Solution>" << endl;
2005
2006        //-- the view space bounding box
2007        stream << "<ViewSpaceBox"
2008                   << " min=\"" << mViewSpaceBox.Min().x << " " << mViewSpaceBox.Min().y << " " << mViewSpaceBox.Min().z << "\""
2009                   << " max=\"" << mViewSpaceBox.Max().x << " " << mViewSpaceBox.Max().y << " " << mViewSpaceBox.Max().z << "\" />" << endl;
2010
2011        //-- the type of the view cells hierarchy
2012        //stream << "<Hierarchy name=\"bspTree\" />" << endl;
2013        stream << "<Hierarchy name=\"vspBspTree\" />" << endl; // write vsp bsp here because can use same tree and is bug free
2014        //-- load the view cells itself, i.e., the ids and the pvs
2015        stream << "<ViewCells>" << endl;
2016
2017#if 0
2018       
2019        ViewCellContainer::const_iterator it, it_end = mViewCells.end();
2020               
2021        for (it = mViewCells.begin(); it != it_end; ++ it)
2022                ExportViewCell(*it, stream);
2023#else
2024        mViewCellsTree->Export(stream);
2025#endif
2026
2027        stream << "</ViewCells>" << endl;
2028
2029        //-- load the hierarchy
2030        stream << "<Hierarchy>" << endl;
2031        mBspTree->Export(stream);
2032        stream << endl << "</Hierarchy>" << endl;
2033
2034        stream << "</Visibility_Solution>" << endl;
2035        stream.close();
2036
2037        cout << "finished" << endl;
2038
2039        return true;
2040}
2041
2042
2043void BspViewCellsManager::AddCurrentViewCellsToHierarchy()
2044{
2045        ViewCellContainer::const_iterator it, it_end = mViewCells.end();
2046        for (it = mViewCells.begin(); it != it_end; ++ it)
2047        {
2048                ViewCell *vc = *it;
2049                ViewCellContainer leaves;
2050                mViewCellsTree->CollectLeaves(vc, leaves);
2051               
2052                ViewCellContainer::const_iterator lit, lit_end = leaves.end();
2053
2054                for (lit = leaves.begin(); lit != lit_end; ++ lit)
2055                {
2056                        BspViewCell *bspVc = dynamic_cast<BspViewCell *>(*lit);
2057                        bspVc->mLeaf->SetViewCell(vc);
2058                }
2059        }
2060}
2061
2062
2063ViewCell *BspViewCellsManager::ConstructSpatialMergeTree(BspNode *root)
2064{
2065        if (root->IsLeaf())
2066        {
2067                ViewCell *viewCell = dynamic_cast<BspLeaf *>(root)->GetViewCell();
2068
2069                viewCell->SetMergeCost(0.0f);
2070
2071                return viewCell;
2072        }
2073       
2074        BspInterior *interior = dynamic_cast<BspInterior *>(root);
2075        ViewCellInterior *viewCellInterior = new ViewCellInterior();
2076               
2077        float mergeCost = 1.0f / (float)root->mTimeStamp;
2078        //Debug << "timestamp: " << root->mTimeStamp;
2079        //Debug << "merge cost: " << mergeCost << endl;
2080
2081        viewCellInterior->SetMergeCost(mergeCost);
2082
2083        float volume = 0;
2084       
2085        BspNode *front = interior->GetFront();
2086        BspNode *back = interior->GetBack();
2087
2088        // recursivly compute child hierarchies
2089        ViewCell *backVc = ConstructSpatialMergeTree(back);
2090        ViewCell *frontVc = ConstructSpatialMergeTree(front);
2091
2092        viewCellInterior->SetupChildLink(frontVc);
2093        viewCellInterior->SetupChildLink(backVc);
2094
2095
2096        viewCellInterior->GetPvs().Merge(backVc->GetPvs());
2097        viewCellInterior->GetPvs().Merge(frontVc->GetPvs());
2098
2099        volume += backVc->GetVolume();
2100        volume += frontVc->GetVolume();
2101
2102        viewCellInterior->SetVolume(volume);
2103
2104        return viewCellInterior;
2105}
2106
2107
2108/************************************************************************/
2109/*                   KdViewCellsManager implementation                  */
2110/************************************************************************/
2111
2112
2113
2114KdViewCellsManager::KdViewCellsManager(KdTree *kdTree):
2115ViewCellsManager(), mKdTree(kdTree), mKdPvsDepth(100)
2116{
2117}
2118
2119
2120float KdViewCellsManager::GetProbability(ViewCell *viewCell)
2121{
2122        // compute view cell area / volume as subsititute for probability
2123        if (0)
2124                return GetArea(viewCell) / GetViewSpaceBox().SurfaceArea();
2125        else
2126                return GetVolume(viewCell) / GetViewSpaceBox().GetVolume();
2127}
2128
2129
2130
2131
2132void KdViewCellsManager::CollectViewCells()
2133{
2134        //mKdTree->CollectViewCells(mViewCells); TODO
2135}
2136
2137
2138int KdViewCellsManager::ConstructSubdivision(const ObjectContainer &objects,
2139                                                                  const VssRayContainer &rays)
2140{
2141        // if view cells already constructed
2142        if (ViewCellsConstructed())
2143                return 0;
2144
2145        mKdTree->Construct();
2146
2147        mTotalAreaValid = false;
2148        // create the view cells
2149        mKdTree->CreateAndCollectViewCells(mViewCells);
2150
2151        // cast rays
2152        ComputeSampleContributions(rays, true, false);
2153
2154        EvaluateViewCellsStats();
2155        Debug << "\nView cells after construction:\n" << mCurrentViewCellsStats << endl;
2156
2157        return 0;
2158}
2159
2160
2161bool KdViewCellsManager::ViewCellsConstructed() const
2162{
2163        return mKdTree->GetRoot() != NULL;
2164}
2165
2166int KdViewCellsManager::PostProcess(const ObjectContainer &objects,
2167                                                                        const VssRayContainer &rays)
2168{
2169        return 0;
2170}
2171
2172void KdViewCellsManager::Visualize(const ObjectContainer &objects,
2173                                                                   const VssRayContainer &sampleRays)
2174{
2175        if (!ViewCellsConstructed())
2176                return;
2177
2178        // using view cells instead of the kd PVS of objects
2179        const bool useViewCells = true;
2180        bool exportRays = false;
2181
2182        int limit = min(mVisualizationSamples, (int)sampleRays.size());
2183        const int pvsOut = min((int)objects.size(), 10);
2184        VssRayContainer *rays = new VssRayContainer[pvsOut];
2185
2186        if (useViewCells)
2187        {
2188                const int leafOut = 10;
2189
2190                ViewCell::NewMail();
2191
2192                //-- some rays for output
2193                const int raysOut = min((int)sampleRays.size(), mVisualizationSamples);
2194                Debug << "visualization using " << raysOut << " samples" << endl;
2195
2196                //-- some random view cells and rays for output
2197                vector<KdLeaf *> kdLeaves;
2198
2199                for (int i = 0; i < leafOut; ++ i)
2200                        kdLeaves.push_back(dynamic_cast<KdLeaf *>(mKdTree->GetRandomLeaf()));
2201
2202                for (int i = 0; i < kdLeaves.size(); ++ i)
2203                {
2204                        KdLeaf *leaf = kdLeaves[i];
2205                        RayContainer vcRays;
2206
2207                        cout << "creating output for view cell " << i << " ... ";
2208#if 0
2209                        // check whether we can add the current ray to the output rays
2210                        for (int k = 0; k < raysOut; ++ k)
2211                        {
2212                                Ray *ray = sampleRays[k];
2213
2214                                for (int j = 0; j < (int)ray->bspIntersections.size(); ++ j)
2215                                {
2216                                        BspLeaf *leaf2 = ray->bspIntersections[j].mLeaf;
2217
2218                                        if (leaf->GetViewCell() == leaf2->GetViewCell())
2219                                        {
2220                                                vcRays.push_back(ray);
2221                                        }
2222                                }
2223                        }
2224#endif
2225                        Intersectable::NewMail();
2226
2227                        ViewCell *vc = leaf->mViewCell;
2228
2229                        //bspLeaves[j]->Mail();
2230                        char s[64]; sprintf(s, "kd-pvs%04d.x3d", i);
2231
2232                        Exporter *exporter = Exporter::GetExporter(s);
2233                        exporter->SetFilled();
2234
2235                        exporter->SetWireframe();
2236                        //exporter->SetFilled();
2237
2238                        Material m;//= RandomMaterial();
2239                        m.mDiffuseColor = RgbColor(1, 1, 0);
2240                        exporter->SetForcedMaterial(m);
2241
2242                        AxisAlignedBox3 box = mKdTree->GetBox(leaf);
2243                        exporter->ExportBox(box);
2244
2245                        // export rays piercing this view cell
2246                        exporter->ExportRays(vcRays, 1000, RgbColor(0, 1, 0));
2247
2248                        m.mDiffuseColor = RgbColor(1, 0, 0);
2249                        exporter->SetForcedMaterial(m);
2250
2251                        // exporter->SetWireframe();
2252                        exporter->SetFilled();
2253
2254                        ObjectPvsMap::iterator it, it_end = vc->GetPvs().mEntries.end();
2255                        // output PVS of view cell
2256                        for (it = vc->GetPvs().mEntries.begin(); it !=  it_end; ++ it)
2257                        {
2258                                Intersectable *intersect = (*it).first;
2259                                if (!intersect->Mailed())
2260                                {
2261                                        exporter->ExportIntersectable(intersect);
2262                                        intersect->Mail();
2263                                }
2264                        }
2265
2266                        DEL_PTR(exporter);
2267                        cout << "finished" << endl;
2268                }
2269
2270                DEL_PTR(rays);
2271        }
2272        else // using kd PVS of objects
2273        {
2274                for (int i = 0; i < limit; ++ i)
2275                {
2276                        VssRay *ray = sampleRays[i];
2277
2278                        // check whether we can add this to the rays
2279                        for (int j = 0; j < pvsOut; j++)
2280                        {
2281                                if (objects[j] == ray->mTerminationObject)
2282                                {
2283                                        rays[j].push_back(ray);
2284                                }
2285                        }
2286                }
2287
2288                if (exportRays)
2289                {
2290                        Exporter *exporter = NULL;
2291                        exporter = Exporter::GetExporter("sample-rays.x3d");
2292                        exporter->SetWireframe();
2293                        exporter->ExportKdTree(*mKdTree);
2294
2295                        for (i=0; i < pvsOut; i++)
2296                                exporter->ExportRays(rays[i], RgbColor(1, 0, 0));
2297
2298                        exporter->SetFilled();
2299
2300                        delete exporter;
2301                }
2302
2303                for (int k=0; k < pvsOut; k++)
2304                {
2305                        Intersectable *object = objects[k];
2306                        char s[64];
2307                        sprintf(s, "sample-pvs%04d.x3d", k);
2308
2309                        Exporter *exporter = Exporter::GetExporter(s);
2310                        exporter->SetWireframe();
2311
2312                        KdPvsMap::iterator i = object->mKdPvs.mEntries.begin();
2313                        Intersectable::NewMail();
2314
2315                        // avoid adding the object to the list
2316                        object->Mail();
2317                        ObjectContainer visibleObjects;
2318
2319                        for (; i != object->mKdPvs.mEntries.end(); i++)
2320                        {
2321                                KdNode *node = (*i).first;
2322                                exporter->ExportBox(mKdTree->GetBox(node));
2323
2324                                mKdTree->CollectObjects(node, visibleObjects);
2325                        }
2326
2327                        exporter->ExportRays(rays[k],  RgbColor(0, 1, 0));
2328                        exporter->SetFilled();
2329
2330                        for (int j = 0; j < visibleObjects.size(); j++)
2331                                exporter->ExportIntersectable(visibleObjects[j]);
2332
2333                        Material m;
2334                        m.mDiffuseColor = RgbColor(1, 0, 0);
2335                        exporter->SetForcedMaterial(m);
2336                        exporter->ExportIntersectable(object);
2337
2338                        delete exporter;
2339                }
2340        }
2341}
2342
2343
2344void KdViewCellsManager::ExportColor(Exporter *exporter,
2345                                                                         ViewCell *vc) const
2346{
2347        // TODO
2348}
2349
2350
2351ViewCell *KdViewCellsManager::GenerateViewCell(Mesh *mesh) const
2352{
2353        return new KdViewCell(mesh);
2354}
2355
2356
2357void KdViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
2358                                                                                                ViewCell *vc,
2359                                                                                                const Plane3 *clipPlane) const
2360{
2361        ViewCellContainer leaves;
2362
2363        mViewCellsTree->CollectLeaves(vc, leaves);
2364        ViewCellContainer::const_iterator it, it_end = leaves.end();
2365
2366        for (it = leaves.begin(); it != it_end; ++ it)
2367        {
2368                KdViewCell *kdVc = dynamic_cast<KdViewCell *>(*it);
2369       
2370                exporter->ExportBox(mKdTree->GetBox(kdVc->mLeaf));
2371        }
2372}
2373
2374
2375int KdViewCellsManager::GetType() const
2376{
2377        return ViewCellsManager::KD;
2378}
2379
2380
2381
2382KdNode *KdViewCellsManager::GetNodeForPvs(KdLeaf *leaf)
2383{
2384        KdNode *node = leaf;
2385
2386        while (node->mParent && node->mDepth > mKdPvsDepth)
2387                node = node->mParent;
2388        return node;
2389}
2390
2391int KdViewCellsManager::CastLineSegment(const Vector3 &origin,
2392                                                                                const Vector3 &termination,
2393                                                                                ViewCellContainer &viewcells)
2394{
2395        return mKdTree->CastLineSegment(origin, termination, viewcells);
2396}
2397
2398
2399void KdViewCellsManager::CreateMesh(ViewCell *vc)
2400{
2401        // TODO
2402}
2403
2404
2405
2406void KdViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays,
2407                                                                                                vector<MergeCandidate> &candidates)
2408{
2409        // TODO
2410}
2411
2412
2413/**********************************************************************/
2414/*                   VspKdViewCellsManager implementation             */
2415/**********************************************************************/
2416
2417
2418VspKdViewCellsManager::VspKdViewCellsManager(VspKdTree *vspKdTree):
2419ViewCellsManager(), mVspKdTree(vspKdTree)
2420{
2421        environment->GetIntValue("VspKdTree.Construction.samples", mInitialSamples);
2422        mVspKdTree->SetViewCellsManager(this);
2423}
2424
2425float VspKdViewCellsManager::GetProbability(ViewCell *viewCell)
2426{
2427        // compute view cell area / volume as subsititute for probability
2428        if (0)
2429                return GetArea(viewCell) / GetViewSpaceBox().SurfaceArea();
2430        else
2431                return GetVolume(viewCell) / GetViewSpaceBox().GetVolume();
2432}
2433
2434
2435
2436
2437void VspKdViewCellsManager::CollectViewCells()
2438{
2439        mVspKdTree->CollectViewCells(mViewCells);
2440}
2441
2442
2443int VspKdViewCellsManager::ConstructSubdivision(const ObjectContainer &objects,
2444                                                                                                const VssRayContainer &rays)
2445{
2446        // if view cells already constructed
2447        if (ViewCellsConstructed())
2448                return 0;
2449
2450        VssRayContainer constructionRays;
2451        VssRayContainer savedRays;
2452
2453        GetRaySets(rays,
2454                           mInitialSamples,
2455                           constructionRays,
2456                           &savedRays);
2457
2458        Debug << "constructing vsp kd tree using "
2459                  << (int)constructionRays.size() << " samples" << endl;
2460
2461        mVspKdTree->Construct(constructionRays, &mViewSpaceBox);
2462        Debug << mVspKdTree->GetStatistics() << endl;
2463
2464        // export leaf building blocks
2465        ExportLeaves(objects, rays);
2466
2467        // finally merge kd leaf building blocks to view cells
2468        const int merged = mVspKdTree->MergeViewCells(rays);
2469
2470        // collapse siblings belonging to the same view cell
2471        mVspKdTree->RefineViewCells(rays);
2472
2473        // collapse siblings belonging to the same view cell
2474        mVspKdTree->CollapseTree();
2475
2476        // evaluale view cell stats
2477        ResetViewCells();
2478
2479        Debug << "\nView cells after construction:\n" << mCurrentViewCellsStats << endl;
2480
2481        long startTime = GetTime();
2482
2483        // recast rest of rays
2484        ComputeSampleContributions(savedRays, true, false);
2485
2486        Debug << "Computed remaining ray contribution in " << TimeDiff(startTime, GetTime()) * 1e-3
2487                  << " secs" << endl;
2488
2489        return merged;
2490}
2491
2492bool VspKdViewCellsManager::ViewCellsConstructed() const
2493{
2494        return mVspKdTree->GetRoot() != NULL;
2495}
2496
2497
2498ViewCell *VspKdViewCellsManager::GenerateViewCell(Mesh *mesh) const
2499{
2500        return new VspKdViewCell(mesh);
2501}
2502
2503int VspKdViewCellsManager::PostProcess(const ObjectContainer &objects,
2504                                                                           const VssRayContainer &rays)
2505{
2506        if (!ViewCellsConstructed())
2507                return 0;
2508
2509        // recalculate stats
2510        EvaluateViewCellsStats();
2511
2512        return 0;
2513}
2514
2515
2516void VspKdViewCellsManager::ExportLeaves(const ObjectContainer &objects,
2517                                                                                 const VssRayContainer &sampleRays)
2518{
2519        if (!ViewCellsConstructed())
2520                return;
2521
2522        //-- export leaf building blocks
2523        Exporter *exporter = Exporter::GetExporter("vspkdtree.x3d");
2524        if (!exporter)
2525                return;
2526
2527        if (mExportGeometry)
2528                exporter->ExportGeometry(objects);
2529       
2530        //exporter->SetWireframe();
2531        //exporter->ExportVspKdTree(*mVspKdTree, mVspKdTree->GetStatistics().maxPvsSize);
2532        exporter->ExportVspKdTree(*mVspKdTree);
2533
2534        if (mExportRays)
2535        {
2536                const float prob = (float)mVisualizationSamples
2537                        / ((float)sampleRays.size() + Limits::Small);
2538
2539                exporter->SetWireframe();
2540
2541                //-- collect uniformly distributed rays
2542                VssRayContainer rays;
2543
2544                for (int i = 0; i < sampleRays.size(); ++ i)
2545                {
2546                        if (RandomValue(0,1) < prob)
2547                                rays.push_back(sampleRays[i]);
2548                }
2549                exporter->ExportRays(rays, RgbColor(1, 0, 0));
2550        }
2551
2552        delete exporter;
2553}
2554
2555void VspKdViewCellsManager::Visualize(const ObjectContainer &objects,
2556                                                                          const VssRayContainer &sampleRays)
2557{
2558        if (!ViewCellsConstructed())
2559                return;
2560
2561        //-- export single view cells
2562        for (int i = 0; i < 10; ++ i)
2563        {
2564                char s[64];
2565                sprintf(s, "vsp_viewcell%04d.x3d", i);
2566                Exporter *exporter = Exporter::GetExporter(s);
2567                const int idx =
2568                        (int)RandomValue(0.0, (Real)((int)mViewCells.size() - 1));
2569
2570                VspKdViewCell *vc = dynamic_cast<VspKdViewCell *>(mViewCells[idx]);
2571
2572                //-- export geometry
2573                Material m;
2574                m.mDiffuseColor = RgbColor(0, 1, 1);
2575
2576                exporter->SetForcedMaterial(m);
2577                exporter->SetWireframe();
2578
2579                ExportViewCellGeometry(exporter, vc);
2580
2581                //-- export stored rays
2582               
2583                if (mExportRays)
2584                {
2585                        ViewCellContainer leaves;
2586                        mViewCellsTree->CollectLeaves(vc, leaves);
2587
2588                        ViewCellContainer::const_iterator it,
2589                                it_end = leaves.end();
2590
2591                        for (it = leaves.begin(); it != it_end; ++ it)
2592                        {
2593                                VspKdViewCell *vspKdVc = dynamic_cast<VspKdViewCell *>(*it);
2594                                VspKdLeaf *leaf = vspKdVc->mLeaf;
2595                                AxisAlignedBox3 box = mVspKdTree->GetBBox(leaf);
2596
2597                                VssRayContainer vssRays;
2598
2599                                VssRayContainer castRays;
2600                                VssRayContainer initRays;
2601
2602                                leaf->GetRays(vssRays);
2603
2604                                VssRayContainer::const_iterator it, it_end = vssRays.end();
2605                                const float prop = 200.0f / (float)vssRays.size();
2606
2607                                for (it = vssRays.begin(); it != it_end; ++ it)
2608                                {
2609                                        if (Random(1) < prop)
2610                                                if ((*it)->mTerminationObject == NULL)
2611                                                        castRays.push_back(*it);
2612                                                else
2613                                                        initRays.push_back(*it);
2614                                }
2615
2616                                exporter->ExportRays(castRays, RgbColor(1, 0, 0));
2617                                exporter->ExportRays(initRays, RgbColor(0, 1, 0));
2618                        }
2619                }
2620       
2621                //-- output PVS of view cell
2622                m.mDiffuseColor = RgbColor(1, 0, 0);
2623                exporter->SetForcedMaterial(m);
2624
2625                Intersectable::NewMail();
2626
2627                ObjectPvsMap::const_iterator it,
2628                        it_end = vc->GetPvs().mEntries.end();
2629
2630                exporter->SetFilled();
2631
2632                for (it = vc->GetPvs().mEntries.begin(); it != it_end; ++ it)
2633                {
2634                        Intersectable *intersect = (*it).first;
2635
2636                        if (!intersect->Mailed())
2637                        {
2638                                Material m = RandomMaterial();
2639                                exporter->SetForcedMaterial(m);
2640
2641                                exporter->ExportIntersectable(intersect);
2642                                intersect->Mail();
2643                        }
2644                }
2645
2646                delete exporter;
2647        }
2648
2649        //-- export final view cells
2650        Exporter *exporter = Exporter::GetExporter("vspkdtree_merged.x3d");
2651
2652        //if (exportGeometry) exporter->SetWireframe();
2653        //else exporter->SetFilled();
2654
2655        ExportViewCellsForViz(exporter);
2656
2657        if (mExportGeometry)
2658        {
2659                exporter->SetFilled();
2660                exporter->ExportGeometry(objects);
2661        }
2662
2663        if (mExportRays)
2664        {
2665                const float prob = (float)mVisualizationSamples
2666                        / ((float)sampleRays.size() + Limits::Small);
2667
2668                exporter->SetWireframe();
2669
2670                VssRayContainer rays;
2671
2672                for (int i = 0; i < sampleRays.size(); ++ i)
2673                {
2674                  if (RandomValue(0,1) < prob)
2675                        rays.push_back(sampleRays[i]);
2676                }
2677                exporter->ExportRays(rays, RgbColor(1, 0, 0));
2678        }
2679
2680        delete exporter;
2681}
2682
2683int VspKdViewCellsManager::GetType() const
2684{
2685        return VSP_KD;
2686}
2687
2688
2689int VspKdViewCellsManager::CastLineSegment(const Vector3 &origin,
2690                                                                                   const Vector3 &termination,
2691                                                                                   ViewCellContainer &viewcells)
2692{
2693        return mVspKdTree->CastLineSegment(origin, termination, viewcells);
2694}
2695
2696
2697void VspKdViewCellsManager::ExportColor(Exporter *exporter,
2698                                                                                ViewCell *vc) const
2699{
2700        if (mColorCode == 0) // Random color
2701                return;
2702
2703        float importance = 0;
2704
2705        switch (mColorCode)
2706        {
2707        case 1: // pvs
2708                {
2709                        importance = (float)vc->GetPvs().GetSize() /
2710                                (float)mCurrentViewCellsStats.maxPvs;
2711                }
2712                break;
2713        case 2: // merged leaves
2714                {
2715                int lSize = mViewCellsTree->GetSize(vc);
2716                        importance = (float)lSize /
2717                                (float)mCurrentViewCellsStats.maxLeaves;
2718                }
2719                break;
2720        case 3: // merged tree depth difference
2721                {
2722                        //importance = (float)GetMaxTreeDiff(vc) /
2723                        //      (float)(mVspBspTree->GetStatistics().maxDepth * 2);
2724                }
2725                break;
2726        default:
2727                break;
2728        }
2729
2730        Material m;
2731        m.mDiffuseColor.b = 1.0f;
2732        m.mDiffuseColor.r = importance;
2733        m.mDiffuseColor.g = 1.0f - m.mDiffuseColor.r;
2734        //Debug << "importance: " << importance << endl;
2735        exporter->SetForcedMaterial(m);
2736}
2737
2738
2739void VspKdViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
2740                                                                                                   ViewCell *vc,
2741                                                                                                   const Plane3 *clipPlane) const
2742{
2743        VspKdViewCell *kdVc = dynamic_cast<VspKdViewCell *>(vc);
2744
2745        Mesh m;
2746
2747        ViewCellContainer leaves;
2748        mViewCellsTree->CollectLeaves(vc, leaves);
2749
2750        ViewCellContainer::const_iterator it, it_end = leaves.end();
2751
2752        for (it = leaves.begin(); it != it_end; ++ it)
2753        {
2754                VspKdLeaf *l = dynamic_cast<VspKdViewCell *>(*it)->mLeaf;
2755                mVspKdTree->GetBBox(l).AddBoxToMesh(&m);
2756        }
2757
2758        exporter->ExportMesh(&m);
2759}
2760
2761
2762void VspKdViewCellsManager::CreateMesh(ViewCell *vc)
2763{
2764        //TODO
2765}
2766
2767
2768void VspKdViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays,
2769                                                                                                   vector<MergeCandidate> &candidates)
2770{
2771        // TODO
2772}
2773
2774
2775/**************************************************************************/
2776/*                   VspBspViewCellsManager implementation                */
2777/**************************************************************************/
2778
2779
2780VspBspViewCellsManager::VspBspViewCellsManager(VspBspTree *vspBspTree):
2781ViewCellsManager(), mVspBspTree(vspBspTree)
2782{
2783        environment->GetIntValue("VspBspTree.Construction.samples", mInitialSamples);
2784        mVspBspTree->SetViewCellsManager(this);
2785        mVspBspTree->mViewCellsTree = mViewCellsTree;
2786}
2787
2788
2789VspBspViewCellsManager::~VspBspViewCellsManager()
2790{
2791}
2792
2793
2794float VspBspViewCellsManager::GetProbability(ViewCell *viewCell)
2795{
2796        if (0 && mVspBspTree->mUseAreaForPvs)
2797                return GetArea(viewCell) / GetAccVcArea();
2798        else
2799                return GetVolume(viewCell) / mViewSpaceBox.GetVolume();
2800}
2801
2802
2803void VspBspViewCellsManager::CollectViewCells()
2804{
2805        // view cells tree constructed
2806        if (!ViewCellsTreeConstructed())
2807        {
2808                mVspBspTree->CollectViewCells(mViewCells, false);
2809        }
2810        else
2811        {       // we can use the view cells tree hierarchy to get the right set
2812                mViewCellsTree->CollectBestViewCellSet(mViewCells, mNumActiveViewCells);
2813        }
2814}
2815
2816
2817bool VspBspViewCellsManager::ViewCellsConstructed() const
2818{
2819        return mVspBspTree->GetRoot() != NULL;
2820}
2821
2822
2823ViewCell *VspBspViewCellsManager::GenerateViewCell(Mesh *mesh) const
2824{
2825        return new BspViewCell(mesh);
2826}
2827
2828
2829int VspBspViewCellsManager::ConstructSubdivision(const ObjectContainer &objects,
2830                                                                                                 const VssRayContainer &rays)
2831{
2832        // if view cells were already constructed
2833        if (ViewCellsConstructed())
2834                return 0;
2835
2836        int sampleContributions = 0;
2837
2838        VssRayContainer sampleRays;
2839
2840        int limit = min (mInitialSamples, (int)rays.size());
2841
2842        VssRayContainer constructionRays;
2843        VssRayContainer savedRays;
2844
2845        Debug << "samples used for vsp bsp subdivision: " << mInitialSamples
2846                  << ", actual rays: " << (int)rays.size() << endl;
2847
2848        GetRaySets(rays, mInitialSamples, constructionRays, &savedRays);
2849
2850        Debug << "initial rays: " << (int)constructionRays.size() << endl;
2851        Debug << "saved rays: " << (int)savedRays.size() << endl;
2852
2853        mMaxPvsSize = (int)(mMaxPvsRatio * (float)objects.size());
2854
2855        //TODO: remove
2856        if (1)
2857                mVspBspTree->Construct(constructionRays, &mViewSpaceBox);
2858        else
2859                mVspBspTree->Construct(rays, &mViewSpaceBox);
2860
2861        // collapse invalid regions
2862        cout << "collapsing invalid tree regions ... ";
2863        long startTime = GetTime();
2864        int collapsedLeaves = mVspBspTree->CollapseTree();
2865        Debug << "collapsed in " << TimeDiff(startTime, GetTime()) * 1e-3
2866                  << " seconds" << endl;
2867
2868    cout << "finished" << endl;
2869
2870        // -- stats
2871        Debug << mVspBspTree->GetStatistics() << endl;
2872
2873        ResetViewCells();
2874        Debug << "\nView cells after construction:\n" << mCurrentViewCellsStats << endl;
2875
2876
2877        startTime = GetTime();
2878
2879        cout << "Computing remaining ray contributions ... ";
2880
2881        // recast rest of rays
2882        if (SAMPLE_AFTER_SUBDIVISION)
2883                ComputeSampleContributions(savedRays, true, false);
2884        cout << "finished" << endl;
2885
2886        Debug << "Computed remaining ray contribution in " << TimeDiff(startTime, GetTime()) * 1e-3
2887                  << " secs" << endl;
2888
2889        cout << "construction finished" << endl;
2890
2891        return sampleContributions;
2892}
2893
2894
2895void VspBspViewCellsManager::MergeViewCells(const VssRayContainer &rays,
2896                                                                                        const ObjectContainer &objects)
2897{
2898        //-- post processing of bsp view cells
2899    int vcSize = 0;
2900        int pvsSize = 0;
2901
2902        //-- merge view cells
2903       
2904        cout << "starting merge using " << mPostProcessSamples << " samples ... " << endl;
2905        long startTime = GetTime();
2906
2907
2908        if (mMergeViewCells)
2909        {
2910                // TODO: should be done BEFORE the ray casting
2911                mViewCellsTree->ConstructMergeTree(rays, objects);
2912        }
2913        else
2914        {
2915                mViewCellsTree->SetRoot(ConstructSpatialMergeTree(mVspBspTree->GetRoot()));
2916        }
2917
2918        if (1)
2919        {
2920                char mstats[100];
2921                environment->GetStringValue("ViewCells.mergeStats", mstats);
2922                mViewCellsTree->ExportStats(mstats);
2923        }
2924
2925        //-- stats and visualizations
2926        cout << "finished merging" << endl;
2927        cout << "merged view cells in "
2928                 << TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl;
2929
2930        Debug << "Postprocessing: Merged view cells in "
2931                  << TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl << endl;
2932       
2933
2934        int savedColorCode = mColorCode;
2935       
2936        // get currently active view cell set
2937        ResetViewCells();
2938        Debug << "\nView cells after merge:\n" << mCurrentViewCellsStats << endl;
2939
2940        //BspLeaf::NewMail();
2941        if (1) // export merged view cells
2942        {
2943                mColorCode = 0;
2944                Exporter *exporter = Exporter::GetExporter("merged_view_cells.x3d");
2945               
2946                cout << "exporting view cells after merge ... ";
2947
2948                if (exporter)
2949                {
2950                        if (0)
2951                                exporter->SetWireframe();
2952                        else
2953                                exporter->SetFilled();
2954
2955                        ExportViewCellsForViz(exporter);
2956
2957                        if (mExportGeometry)
2958                        {
2959                                Material m;
2960                                m.mDiffuseColor = RgbColor(0, 1, 0);
2961                                exporter->SetForcedMaterial(m);
2962                                exporter->SetFilled();
2963
2964                                exporter->ExportGeometry(objects);
2965                        }
2966
2967                        delete exporter;
2968                }
2969                cout << "finished" << endl;
2970        }
2971
2972        if (1) // export merged view cells using pvs coding
2973        {
2974                mColorCode = 1;
2975
2976                Exporter *exporter = Exporter::GetExporter("merged_view_cells_pvs.x3d");
2977       
2978                cout << "exporting view cells after merge (pvs size) ... ";     
2979
2980                if (exporter)
2981                {
2982                        if (0)
2983                                exporter->SetWireframe();
2984                        else
2985                                exporter->SetFilled();
2986
2987                        ExportViewCellsForViz(exporter);
2988
2989                        if (mExportGeometry)
2990                        {
2991                                Material m;
2992                                m.mDiffuseColor = RgbColor(0, 1, 0);
2993                                exporter->SetForcedMaterial(m);
2994                                exporter->SetFilled();
2995
2996                                exporter->ExportGeometry(objects);
2997                        }
2998
2999                        delete exporter;
3000                }
3001                cout << "finished" << endl;
3002        }
3003
3004        mColorCode = savedColorCode;
3005
3006}
3007
3008
3009bool VspBspViewCellsManager::EqualToSpatialNode(ViewCell *viewCell) const
3010{
3011        return GetSpatialNode(viewCell) != NULL;
3012}
3013
3014
3015BspNode *VspBspViewCellsManager::GetSpatialNode(ViewCell *viewCell) const
3016{
3017        if (!viewCell->IsLeaf())
3018        {
3019                BspViewCell *bspVc = dynamic_cast<BspViewCell *>(viewCell);
3020
3021                return bspVc->mLeaf;
3022        }
3023        else
3024        {
3025                ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(viewCell);
3026
3027                // cannot be node of binary tree
3028                if (interior->mChildren.size() != 2)
3029                        return NULL;
3030
3031                ViewCell *left = interior->mChildren[0];
3032                ViewCell *right = interior->mChildren[1];
3033
3034                BspNode *leftNode = GetSpatialNode(left);
3035                BspNode *rightNode = GetSpatialNode(right);
3036
3037                if (leftNode && rightNode && leftNode->IsSibling(rightNode))
3038                {
3039                        return leftNode->GetParent();
3040                }
3041        }
3042
3043        return NULL;
3044}
3045
3046
3047void VspBspViewCellsManager::RefineViewCells(const VssRayContainer &rays,
3048                                                                                         const ObjectContainer &objects)
3049{
3050        Debug << "render time before refine:" << endl;
3051        mRenderer->RenderScene();
3052        SimulationStatistics ss;
3053        dynamic_cast<RenderSimulator *>(mRenderer)->GetStatistics(ss);
3054    Debug << ss << endl;
3055
3056        cout << "Refining the merged view cells ... ";
3057        long startTime = GetTime();
3058
3059        // refining the merged view cells
3060        const int refined = mViewCellsTree->RefineViewCells(rays, objects);
3061
3062        //-- stats and visualizations
3063        cout << "finished" << endl;
3064        cout << "refined " << refined << " view cells in "
3065                 << TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl;
3066
3067        Debug << "Postprocessing: refined " << refined << " view cells in "
3068                  << TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl << endl;
3069}
3070
3071
3072int VspBspViewCellsManager::PostProcess(const ObjectContainer &objects,
3073                                                                                const VssRayContainer &rays)
3074{
3075        if (!ViewCellsConstructed())
3076        {
3077                Debug << "postprocess error: no view cells constructed" << endl;
3078                return 0;
3079        }
3080
3081
3082        // view cells already finished before post processing step
3083        // (i.e. because they were loaded)
3084        if (mViewCellsFinished)
3085        {
3086                FinalizeViewCells(true);
3087                EvaluateViewCellsStats();
3088
3089                return 0;
3090        }
3091
3092
3093        // check if new view cells turned invalid
3094        SetValidity(mMinPvsSize, mMaxPvsSize);
3095        // update valid view space according to valid view cells
3096        mVspBspTree->ValidateTree();
3097
3098        // has to be recomputed
3099        mTotalAreaValid = false;
3100        VssRayContainer postProcessRays;
3101        GetRaySets(rays, mPostProcessSamples, postProcessRays);
3102
3103        Debug << "post processing using " << (int)postProcessRays.size() << " samples" << endl;
3104
3105
3106        // should maybe be done here to allow merge working with area or volume
3107        // and to correct the rendering statistics
3108        if (0)
3109        {
3110                FinalizeViewCells(false);
3111        }
3112
3113        //-- merge the individual view cells
3114        MergeViewCells(postProcessRays, objects);
3115       
3116        // only for testing
3117        TestSubdivision();
3118
3119        //-- refines the merged view cells
3120        if (0)
3121                RefineViewCells(postProcessRays, objects);
3122
3123
3124        //-- render simulation after merge + refine
3125       
3126        cout << "\nevaluating bsp view cells render time before compress ... ";
3127        dynamic_cast<RenderSimulator *>(mRenderer)->RenderScene();
3128        SimulationStatistics ss;
3129        dynamic_cast<RenderSimulator *>(mRenderer)->GetStatistics(ss);
3130 
3131
3132        cout << " finished" << endl;
3133        cout << ss << endl;
3134        Debug << ss << endl;
3135
3136
3137        //-- compression
3138
3139        if (ViewCellsTreeConstructed() && mCompressViewCells)
3140        {
3141                int pvsEntries = mViewCellsTree->GetNumPvsEntries(mViewCellsTree->GetRoot());
3142                Debug << "number of entries before compress: " << pvsEntries << endl;
3143
3144                mViewCellsTree->CompressViewCellsPvs();
3145
3146                pvsEntries = mViewCellsTree->GetNumPvsEntries(mViewCellsTree->GetRoot());
3147                Debug << "number of entries after compress: " << pvsEntries << endl;
3148        }
3149
3150
3151        // collapse sibling leaves that share the same view cell
3152        if (0)
3153                mVspBspTree->CollapseTree();
3154
3155        // recompute view cell list and statistics
3156        ResetViewCells();
3157
3158        // real meshes are only contructed only at this stage
3159        FinalizeViewCells(true);
3160
3161        // write view cells to disc
3162        if (mExportViewCells)
3163        {
3164                char buff[100];
3165                environment->GetStringValue("ViewCells.filename", buff);
3166                string vcFilename(buff);
3167
3168                ExportViewCells(buff);
3169        }
3170
3171        return 0;
3172}
3173
3174
3175int VspBspViewCellsManager::GetType() const
3176{
3177        return VSP_BSP;
3178}
3179
3180
3181ViewCell *VspBspViewCellsManager::ConstructSpatialMergeTree(BspNode *root)
3182{
3183        if (root->IsLeaf())
3184        {
3185                ViewCell *viewCell = dynamic_cast<BspLeaf *>(root)->GetViewCell();
3186
3187                viewCell->SetMergeCost(0.0f);
3188
3189                return viewCell;
3190        }
3191       
3192        BspInterior *interior = dynamic_cast<BspInterior *>(root);
3193        ViewCellInterior *viewCellInterior = new ViewCellInterior();
3194               
3195        float mergeCost = 1.0f / (float)root->mTimeStamp;
3196        //Debug << "timestamp: " << root->mTimeStamp;
3197        //Debug << "merge cost: " << mergeCost << endl;
3198
3199        viewCellInterior->SetMergeCost(mergeCost);
3200
3201        float volume = 0;
3202       
3203        BspNode *front = interior->GetFront();
3204        BspNode *back = interior->GetBack();
3205
3206        // recursivly compute child hierarchies
3207        ViewCell *backVc = ConstructSpatialMergeTree(back);
3208        ViewCell *frontVc = ConstructSpatialMergeTree(front);
3209
3210        viewCellInterior->SetupChildLink(frontVc);
3211        viewCellInterior->SetupChildLink(backVc);
3212
3213
3214        viewCellInterior->GetPvs().Merge(backVc->GetPvs());
3215        viewCellInterior->GetPvs().Merge(frontVc->GetPvs());
3216
3217        volume += backVc->GetVolume();
3218        volume += frontVc->GetVolume();
3219
3220        viewCellInterior->SetVolume(volume);
3221
3222        return viewCellInterior;
3223}
3224
3225
3226bool VspBspViewCellsManager::GetViewPoint(Vector3 &viewPoint) const
3227{
3228        if (!ViewCellsConstructed())
3229                return ViewCellsManager::GetViewPoint(viewPoint);
3230
3231        // TODO: set reasonable limit
3232        const int limit = 20;
3233
3234        for (int i = 0; i < limit; ++ i)
3235        {
3236                viewPoint = mViewSpaceBox.GetRandomPoint();
3237                if (mVspBspTree->ViewPointValid(viewPoint))
3238                {
3239                        return true;
3240                }
3241        }
3242        Debug << "failed to find valid view point, taking " << viewPoint << endl;
3243        return false;
3244}
3245
3246
3247bool VspBspViewCellsManager::ViewPointValid(const Vector3 &viewPoint) const
3248{
3249  // $$JB -> implemented in viewcellsmanager (slower, but allows dynamic
3250  // validy update in preprocessor for all managers)
3251  return ViewCellsManager::ViewPointValid(viewPoint);
3252
3253  //    return mViewSpaceBox.IsInside(viewPoint) &&
3254  //               mVspBspTree->ViewPointValid(viewPoint);
3255}
3256
3257
3258void VspBspViewCellsManager::Visualize(const ObjectContainer &objects,
3259                                                                           const VssRayContainer &sampleRays)
3260{
3261        if (!ViewCellsConstructed())
3262                return;
3263
3264        VssRayContainer visRays;
3265        GetRaySets(sampleRays, mVisualizationSamples, visRays);
3266
3267       
3268        if (1) // export view cells
3269        {       // hack pvs
3270                int savedColorCode = mColorCode;
3271                mColorCode = 0;
3272                Exporter *exporter = Exporter::GetExporter("final_view_cells.x3d");
3273               
3274                if (exporter)
3275                {
3276                        cout << "exporting view cells after post process ... ";
3277
3278                        if (0)
3279                        {
3280                                exporter->SetWireframe();
3281                                exporter->ExportBox(mViewSpaceBox);
3282                                exporter->SetFilled();
3283                        }
3284
3285                        if (mExportGeometry)
3286                        {
3287                                exporter->ExportGeometry(objects);
3288                        }
3289
3290                        // export rays
3291                        if (mExportRays)
3292                        {
3293                                exporter->ExportRays(visRays, RgbColor(0, 1, 0));
3294                        }
3295
3296                        ExportViewCellsForViz(exporter);
3297                        delete exporter;
3298                        cout << "finished" << endl;
3299                }
3300
3301                mColorCode = savedColorCode;
3302        }
3303
3304        if (0)
3305        {
3306                cout << "exporting depth map ... ";
3307
3308                Exporter *exporter = Exporter::GetExporter("depth_map.x3d");
3309                if (exporter)
3310                {
3311                        if (1)
3312                        {
3313                                exporter->SetWireframe();
3314                                exporter->ExportBox(mViewSpaceBox);
3315                                exporter->SetFilled();
3316                        }
3317
3318                        if (mExportGeometry)
3319                        {
3320                                exporter->ExportGeometry(objects);
3321                        }
3322
3323                        const int maxDepth = mVspBspTree->mBspStats.maxDepth;
3324
3325                        ViewCellContainer::const_iterator vit, vit_end = mViewCells.end();
3326
3327                        for (vit = mViewCells.begin(); vit != mViewCells.end(); ++ vit)
3328                        {
3329                                ViewCell *vc = *vit;
3330
3331                                ViewCellContainer leaves;
3332                                mViewCellsTree->CollectLeaves(vc, leaves);
3333
3334                                ViewCellContainer::const_iterator lit, lit_end = leaves.end();
3335
3336                                for (lit = leaves.begin(); lit != lit_end; ++ lit)
3337                                {
3338                                        BspLeaf *leaf = dynamic_cast<BspViewCell *>(*lit)->mLeaf;
3339
3340                                        Material m;
3341
3342                                        float relDepth = (float)leaf->GetDepth() / (float)maxDepth;
3343                                        m.mDiffuseColor.r = relDepth;
3344                                        m.mDiffuseColor.g = 0.0f;
3345                                        m.mDiffuseColor.b = 1.0f - relDepth;
3346
3347                    exporter->SetForcedMaterial(m);
3348                               
3349
3350                                        BspNodeGeometry geom;
3351                                        mVspBspTree->ConstructGeometry(leaf, geom);
3352                                        exporter->ExportPolygons(geom.GetPolys());
3353                                }
3354                        }
3355
3356                        delete exporter;
3357                }
3358
3359
3360                cout << "finished" << endl;
3361        }
3362
3363        //-- visualization of the BSP splits
3364        bool exportSplits = false;
3365        environment->GetBoolValue("VspBspTree.Visualization.exportSplits", exportSplits);
3366
3367        if (exportSplits)
3368        {
3369                cout << "exporting splits ... ";
3370                ExportSplits(objects, visRays);
3371                cout << "finished" << endl;
3372        }
3373
3374        //-- export single view cells
3375        ExportBspPvs(objects, visRays);
3376}
3377
3378
3379void VspBspViewCellsManager::ExportSplits(const ObjectContainer &objects,
3380                                                                                  const VssRayContainer &rays)
3381{
3382        Exporter *exporter = Exporter::GetExporter("bsp_splits.x3d");
3383
3384        if (exporter)
3385        {
3386                Material m;
3387                m.mDiffuseColor = RgbColor(1, 0, 0);
3388                exporter->SetForcedMaterial(m);
3389                exporter->SetWireframe();
3390
3391                exporter->ExportBspSplits(*mVspBspTree, true);
3392
3393                // take forced material, else big scenes cannot be viewed
3394                m.mDiffuseColor = RgbColor(0, 1, 0);
3395                exporter->SetForcedMaterial(m);
3396                exporter->SetFilled();
3397
3398                exporter->ResetForcedMaterial();
3399
3400                // export rays
3401                if (mExportRays)
3402                        exporter->ExportRays(rays, RgbColor(1, 1, 0));
3403
3404                if (mExportGeometry)
3405                        exporter->ExportGeometry(objects);
3406
3407                delete exporter;
3408        }
3409}
3410
3411
3412void VspBspViewCellsManager::ExportBspPvs(const ObjectContainer &objects,
3413                                                                                  const VssRayContainer &rays)
3414{
3415        const int leafOut = 20;
3416
3417        ViewCell::NewMail();
3418
3419        cout << "visualization using " << (int)rays.size() << " samples" << endl;
3420        Debug << "visualization using " << (int)rays.size() << " samples" << endl;
3421        Debug << "\nOutput view cells: " << endl;
3422
3423        const bool sortViewCells = true;
3424
3425        // sort view cells to visualize the largest view cells
3426        if (sortViewCells)
3427                stable_sort(mViewCells.begin(), mViewCells.end(), vc_gt);
3428       
3429        int limit = min(leafOut, (int)mViewCells.size());
3430
3431        int raysOut = 0;
3432
3433        //-- some rays for output
3434        for (int i = 0; i < limit; ++ i)
3435        {
3436                cout << "creating output for view cell " << i << " ... ";
3437
3438                ViewCell *vc;
3439       
3440                if (sortViewCells) // largest view cell pvs first
3441                        vc = mViewCells[i];
3442                else
3443                        vc = mViewCells[(int)RandomValue(0, (float)mViewCells.size() - 1)];
3444
3445                //bspLeaves[j]->Mail();
3446                char s[64]; sprintf(s, "bsp-pvs%04d.x3d", i);
3447                Exporter *exporter = Exporter::GetExporter(s);
3448               
3449                Debug << i << ": pvs size=" << (int)mViewCellsTree->GetPvsSize(vc) << endl;
3450
3451                if (1 || mExportRays)
3452                {
3453                        // output rays stored with the view cells during subdivision
3454                        if (0)
3455                        {
3456                                VssRayContainer vcRays;
3457                VssRayContainer collectRays;
3458
3459                                raysOut = min((int)rays.size(), 100);
3460
3461                                // collect intial view cells
3462                                ViewCellContainer leaves;
3463                                mViewCellsTree->CollectLeaves(vc, leaves);
3464
3465                                ViewCellContainer::const_iterator vit, vit_end = leaves.end();
3466       
3467                                for (vit = leaves.begin(); vit != vit_end; ++ vit)
3468                                {
3469                                        BspLeaf *vcLeaf = dynamic_cast<BspViewCell *>(*vit)->mLeaf;
3470                               
3471                                        VssRayContainer::const_iterator rit, rit_end = vcLeaf->mVssRays.end();
3472
3473                                        for (rit = vcLeaf->mVssRays.begin(); rit != rit_end; ++ rit)
3474                                        {
3475                                                collectRays.push_back(*rit);
3476                                        }
3477                                }
3478
3479                                VssRayContainer::const_iterator rit, rit_end = collectRays.end();
3480
3481                                for (rit = collectRays.begin(); rit != rit_end; ++ rit)
3482                                {
3483                                        float p = RandomValue(0.0f, (float)collectRays.size());
3484                       
3485                                        if (p < raysOut)
3486                                                vcRays.push_back(*rit);
3487                                }
3488                                //-- export rays piercing this view cell
3489                                exporter->ExportRays(vcRays, RgbColor(1, 1, 1));
3490                        }
3491               
3492                        // associate new rays with output view cell
3493                        if (1)
3494                        {
3495                                VssRayContainer vcRays;
3496                                raysOut = min((int)rays.size(), mVisualizationSamples);
3497                                // check whether we can add the current ray to the output rays
3498                                for (int k = 0; k < raysOut; ++ k)
3499                                {
3500                                        VssRay *ray = rays[k];
3501                                        for     (int j = 0; j < (int)ray->mViewCells.size(); ++ j)
3502                                        {
3503                                                ViewCell *rayvc = ray->mViewCells[j];
3504       
3505                                                if (rayvc == vc)
3506                                                        vcRays.push_back(ray);
3507                                        }
3508                                }       
3509                               
3510                                //-- export rays piercing this view cell
3511                                exporter->ExportRays(vcRays, RgbColor(1, 1, 0));
3512                        }
3513
3514                }
3515               
3516
3517                exporter->SetWireframe();
3518
3519                Material m;//= RandomMaterial();
3520                m.mDiffuseColor = RgbColor(0, 1, 0);
3521                exporter->SetForcedMaterial(m);
3522
3523                ExportViewCellGeometry(exporter, vc);
3524       
3525                exporter->SetFilled();
3526
3527
3528                if (1)
3529                {
3530                        ObjectPvsMap::const_iterator oit,
3531                                oit_end = vc->GetPvs().mEntries.end();
3532
3533
3534                        exporter->SetFilled();
3535
3536                        Intersectable::NewMail();
3537       
3538                        // output PVS of view cell
3539                        for (oit = vc->GetPvs().mEntries.begin(); oit != oit_end; ++ oit)
3540                        {               
3541                                Intersectable *intersect = (*oit).first;
3542
3543                                if (!intersect->Mailed())
3544                                {
3545                                        m = RandomMaterial();
3546                                        exporter->SetForcedMaterial(m);
3547
3548                                        exporter->ExportIntersectable(intersect);
3549                                        intersect->Mail();
3550                                }
3551                        }
3552                }
3553                else
3554                {
3555                        m.mDiffuseColor = RgbColor(1, 0, 0);
3556                        exporter->SetForcedMaterial(m);
3557
3558                        exporter->ExportGeometry(objects);
3559                }
3560
3561                DEL_PTR(exporter);
3562                cout << "finished" << endl;
3563        }
3564
3565        Debug << endl;
3566}
3567
3568
3569int VspBspViewCellsManager::ComputeBoxIntersections(const AxisAlignedBox3 &box, ViewCellContainer &viewCells) const
3570{
3571        return mVspBspTree->ComputeBoxIntersections(box, viewCells);
3572}
3573
3574
3575int VspBspViewCellsManager::CastLineSegment(const Vector3 &origin,
3576                                                                                        const Vector3 &termination,
3577                                                                                        ViewCellContainer &viewcells)
3578{
3579        return mVspBspTree->CastLineSegment(origin, termination, viewcells);
3580}
3581
3582
3583void VspBspViewCellsManager::ExportColor(Exporter *exporter,
3584                                                                                 ViewCell *vc) const
3585{
3586        const bool vcValid = CheckValidity(vc, mMinPvsSize, mMaxPvsSize);
3587
3588        float importance = 0;
3589        static Material m;
3590
3591        switch (mColorCode)
3592        {
3593        case 0: // Random
3594                {
3595                        if (vcValid)
3596                        {
3597                                m.mDiffuseColor.r = 0.5f + RandomValue(0.0f, 0.5f);
3598                                m.mDiffuseColor.g = 0.5f + RandomValue(0.0f, 0.5f);
3599                                m.mDiffuseColor.b = 0.5f + RandomValue(0.f, 0.5f);
3600                        }
3601                        else
3602                        {
3603                                m.mDiffuseColor.r = 0.0f;
3604                                m.mDiffuseColor.g = 1.0f;
3605                                m.mDiffuseColor.b = 0.0f;
3606                        }
3607
3608                        exporter->SetForcedMaterial(m);
3609                        return;
3610                }
3611               
3612        case 1: // pvs
3613                {
3614                        importance = (float)vc->GetPvs().GetSize() /
3615                                (float)mCurrentViewCellsStats.maxPvs;
3616
3617                }
3618                break;
3619        case 2: // merges
3620                {
3621            int lSize = mViewCellsTree->GetSize(vc);
3622                        importance = (float)lSize / (float)mCurrentViewCellsStats.maxLeaves;
3623                }
3624                break;
3625        case 3: // merge tree differene
3626                {
3627                        importance = (float)GetMaxTreeDiff(vc) /
3628                                (float)(mVspBspTree->GetStatistics().maxDepth * 2);
3629
3630                }
3631                break;
3632        default:
3633                break;
3634        }
3635
3636        // special color code for invalid view cells
3637        m.mDiffuseColor.r = importance;
3638        m.mDiffuseColor.g = 1.0f - m.mDiffuseColor.r;
3639        m.mDiffuseColor.b = vcValid ? 1.0f : 0.0f;
3640
3641        //Debug << "importance: " << importance << endl;
3642        exporter->SetForcedMaterial(m);
3643}
3644
3645
3646void VspBspViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
3647                                                    ViewCell *vc,
3648                                                                                                        const Plane3 *clipPlane) const
3649{
3650        if (vc->GetMesh())
3651        {
3652                exporter->ExportMesh(vc->GetMesh());
3653       
3654                return;
3655        }
3656
3657       
3658        if (clipPlane)
3659        {
3660                ViewCellContainer leaves;
3661                mViewCellsTree->CollectLeaves(vc, leaves);
3662                ViewCellContainer::const_iterator it, it_end = leaves.end();
3663
3664                for (it = leaves.begin(); it != it_end; ++ it)
3665                {
3666                        BspNodeGeometry geom;
3667
3668                        BspNodeGeometry front;
3669                        BspNodeGeometry back;
3670
3671                        BspLeaf *leaf = dynamic_cast<BspViewCell *>(*it)->mLeaf;
3672                        mVspBspTree->ConstructGeometry(leaf, geom);
3673
3674                        const int cf = Polygon3::ClassifyPlane(geom.GetPolys(), *clipPlane, 0.00000001f);
3675
3676                        if (cf == Polygon3::BACK_SIDE)
3677                        {
3678                                exporter->ExportPolygons(geom.GetPolys());
3679                        }
3680                        else if (cf == Polygon3::SPLIT)
3681                        {
3682                                geom.SplitGeometry(front,
3683                                                                   back,
3684                                                                   *clipPlane,
3685                                                                   mViewSpaceBox,
3686                                                                   0.00000001f);
3687       
3688                                //Debug << "geo size: " << geom.Size() << endl;
3689                                //Debug << "size b: " << back.Size() << " f: " << front.Size() << endl;
3690                                if (back.Valid())
3691                                {
3692                                        exporter->ExportPolygons(back.GetPolys());
3693                                }
3694                       
3695                        }
3696                }
3697        }
3698        else
3699        {
3700                BspNodeGeometry geom;
3701                mVspBspTree->ConstructGeometry(vc, geom);
3702                       
3703                exporter->ExportPolygons(geom.GetPolys());
3704        }
3705}
3706
3707
3708int VspBspViewCellsManager::GetMaxTreeDiff(ViewCell *vc) const
3709{
3710        ViewCellContainer leaves;
3711        mViewCellsTree->CollectLeaves(vc, leaves);
3712
3713        int maxDist = 0;
3714       
3715        // compute max height difference
3716        for (int i = 0; i < (int)leaves.size(); ++ i)
3717                for (int j = 0; j < (int)leaves.size(); ++ j)
3718        {
3719                BspLeaf *leaf = dynamic_cast<BspViewCell *>(leaves[i])->mLeaf;
3720
3721                if (i != j)
3722                {
3723                        BspLeaf *leaf2 =dynamic_cast<BspViewCell *>(leaves[j])->mLeaf;
3724                        int dist = mVspBspTree->TreeDistance(leaf, leaf2);
3725                        if (dist > maxDist)
3726                                maxDist = dist;
3727                }
3728        }
3729
3730        return maxDist;
3731}
3732
3733
3734ViewCell *VspBspViewCellsManager::GetViewCell(const Vector3 &point) const
3735{
3736        if (!mVspBspTree)
3737                return NULL;
3738
3739        if (!mViewSpaceBox.IsInside(point))
3740          return NULL;
3741
3742        return mVspBspTree->GetViewCell(point);
3743}
3744
3745
3746void VspBspViewCellsManager::CreateMesh(ViewCell *vc)
3747{
3748        if (vc->GetMesh())
3749                delete vc->GetMesh();
3750
3751       
3752        BspNodeGeometry geom;
3753
3754        mVspBspTree->ConstructGeometry(vc, geom);
3755       
3756        Mesh *mesh = new Mesh();
3757        geom.AddToMesh(*mesh);
3758        vc->SetMesh(mesh);
3759        mMeshContainer.push_back(mesh);
3760}
3761
3762
3763ViewCellsManager *ViewCellsManager::LoadViewCells(const string filename,
3764                                                                                                  ObjectContainer *objects)
3765{
3766        ViewCellsParser parser;
3767
3768        ViewCellsManager *vm = NULL;
3769
3770        if (parser.ParseFile(filename, &vm, objects))
3771        {
3772                //vm->PrepareLoadedViewCells();
3773                vm->ResetViewCells();
3774
3775                vm->mViewCellsFinished = true;
3776                vm->mMaxPvsSize = (int)objects->size();
3777
3778                vm->FinalizeViewCells(true);
3779
3780                vm->mViewCellsTree->AssignRandomColors();
3781                Debug << (int)vm->mViewCells.size() << " view cells loaded" << endl;
3782        }
3783        else
3784        {
3785                Debug << "failed loading view cells" << endl;
3786                DEL_PTR(vm);
3787        }
3788
3789
3790        return vm;
3791}
3792
3793
3794inline bool ilt(Intersectable *obj1, Intersectable *obj2)
3795{
3796        return obj1->mId < obj2->mId;
3797}
3798
3799
3800bool VspBspViewCellsManager::ExportViewCells(const string filename)
3801{
3802        cout << "exporting view cells to xml ... ";
3803        std::ofstream stream;
3804
3805        // for output we need unique ids for each view cell
3806        CreateUniqueViewCellIds();
3807
3808        stream.open(filename.c_str());
3809        stream << "<?xml version=\"1.0\" encoding=\"UTF-8\"?>"<<endl;
3810        stream << "<Visibility_Solution>" << endl;
3811
3812        //-- the view space bounding box
3813        stream << "<ViewSpaceBox"
3814                   << " min=\"" << mViewSpaceBox.Min().x << " " << mViewSpaceBox.Min().y << " " << mViewSpaceBox.Min().z << "\""
3815                   << " max=\"" << mViewSpaceBox.Max().x << " " << mViewSpaceBox.Max().y << " " << mViewSpaceBox.Max().z << "\" />" << endl;
3816
3817        //-- the type of the view cells hierarchy
3818        stream << "<Hierarchy name=\"vspBspTree\" />" << endl;
3819
3820        //-- load the view cells itself, i.e., the ids and the pvs
3821        stream << "<ViewCells>" << endl;
3822       
3823#if 0
3824       
3825        ViewCellContainer::const_iterator it, it_end = mViewCells.end();
3826               
3827        for (it = mViewCells.begin(); it != it_end; ++ it)
3828                ExportViewCell(*it, stream);
3829#else
3830        mViewCellsTree->Export(stream);
3831#endif
3832
3833        stream << "</ViewCells>" << endl;
3834
3835        //-- load the hierarchy
3836        stream << "<Hierarchy>" << endl;
3837        mVspBspTree->Export(stream);
3838        stream << endl << "</Hierarchy>" << endl;
3839
3840        stream << "</Visibility_Solution>" << endl;
3841        stream.close();
3842
3843        cout << "finished" << endl;
3844
3845        return true;
3846}
3847
3848
3849int VspBspViewCellsManager::CastBeam(Beam &beam)
3850{
3851        return mVspBspTree->CastBeam(beam);
3852}
3853
3854
3855void VspBspViewCellsManager::Finalize(ViewCell *viewCell,
3856                                                                          const bool createMesh)
3857{
3858        float area = 0;
3859        float volume = 0;
3860
3861        ViewCellContainer leaves;
3862        mViewCellsTree->CollectLeaves(viewCell, leaves);
3863
3864        ViewCellContainer::const_iterator it, it_end = leaves.end();
3865
3866    for (it = leaves.begin(); it != it_end; ++ it)
3867        {
3868                BspNodeGeometry geom;
3869                BspLeaf *leaf = dynamic_cast<BspViewCell *>(*it)->mLeaf;
3870                mVspBspTree->ConstructGeometry(leaf, geom);
3871
3872                float lVol = geom.GetVolume();
3873                float lArea = geom.GetArea();
3874
3875                //(*it)->SetVolume(vol);
3876                //(*it)->SetArea(area);
3877
3878                area += lArea;
3879                volume += lVol;
3880
3881        CreateMesh(*it);
3882        }
3883
3884        viewCell->SetVolume(volume);
3885        viewCell->SetArea(area);
3886}
3887
3888
3889void VspBspViewCellsManager::TestSubdivision()
3890{
3891        ViewCellContainer leaves;
3892        mViewCellsTree->CollectLeaves(mViewCellsTree->GetRoot(), leaves);
3893
3894        ViewCellContainer::const_iterator it, it_end = leaves.end();
3895
3896        const float vol = mViewSpaceBox.GetVolume();
3897        float subdivVol = 0;
3898        float newVol = 0;
3899
3900        for (it = leaves.begin(); it != it_end; ++ it)
3901        {
3902                BspNodeGeometry geom;
3903                BspLeaf *leaf = dynamic_cast<BspViewCell *>(*it)->mLeaf;
3904                mVspBspTree->ConstructGeometry(leaf, geom);
3905
3906                const float lVol = geom.GetVolume();
3907               
3908                newVol += lVol;
3909                subdivVol += (*it)->GetVolume();
3910               
3911                float thres = 0.9;
3912                if ((lVol < ((*it)->GetVolume() * thres)) || (lVol * thres > ((*it)->GetVolume())))
3913                        Debug << "warning: " << lVol << " " << (*it)->GetVolume() << endl;
3914        }
3915       
3916        Debug << "exact volume: " << vol << endl;
3917        Debug << "subdivision volume: " << subdivVol << endl;
3918        Debug << "new volume: " << newVol << endl;
3919}
3920
3921
3922void VspBspViewCellsManager::PrepareLoadedViewCells()
3923{
3924        // TODO: do I still need this here?
3925        if (0)
3926                mVspBspTree->RepairViewCellsLeafLists();
3927}
3928
3929
3930void VspBspViewCellsManager::TestFilter(const ObjectContainer &objects)
3931{
3932        Exporter *exporter = Exporter::GetExporter("filter.x3d");
3933
3934        if (exporter)
3935        {
3936                AxisAlignedBox3 testBox = mViewSpaceBox;
3937                Vector3 bsize = mViewSpaceBox.Size();
3938
3939                testBox.Enlarge(Vector3(-bsize[0] * 0.3, 0, -bsize[2] * 0.4));
3940               
3941                ViewCellContainer viewCells;
3942       
3943                mVspBspTree->ComputeBoxIntersections(testBox, viewCells);
3944                cout << "view cells: " << viewCells.size() << endl;
3945               
3946                exporter->SetWireframe();
3947
3948                exporter->SetForcedMaterial(RgbColor(1,1,1));
3949                exporter->ExportBox(testBox);
3950               
3951                exporter->SetFilled();
3952                exporter->ResetForcedMaterial();
3953        for (int i = 0; i < viewCells.size(); ++ i)
3954                {
3955                        BspNodeGeometry geom;
3956                               
3957                        mVspBspTree->ConstructGeometry(viewCells[i], geom);
3958                        exporter->ExportPolygons(geom.GetPolys());
3959                }               
3960
3961                exporter->SetForcedMaterial(RgbColor(1,0,0));
3962                exporter->ExportGeometry(objects);
3963
3964                delete exporter;
3965        }
3966}
3967
3968
3969void VspBspViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays,
3970                                                                                                        vector<MergeCandidate> &candidates)
3971{       
3972        cout << "collecting merge candidates ... " << endl;
3973
3974        if (mUseRaysForMerge)
3975        {
3976                mVspBspTree->CollectMergeCandidates(rays, candidates);
3977        }
3978        else
3979        {
3980                vector<BspLeaf *> leaves;
3981                mVspBspTree->CollectLeaves(leaves);
3982                mVspBspTree->CollectMergeCandidates(leaves, candidates);
3983        }
3984
3985        cout << "fininshed collecting candidates" << endl;
3986}
3987
3988
3989void VspBspViewCellsManager::AddCurrentViewCellsToHierarchy()
3990{
3991        ViewCellContainer::const_iterator it, it_end = mViewCells.end();
3992        for (it = mViewCells.begin(); it != it_end; ++ it)
3993        {
3994        }
3995}
3996
3997//////////////////////////////////
3998ViewCellsManager *ViewCellsManagerFactory::Create(const string mName)
3999{
4000        //TODO
4001        return NULL;// new VspBspViewCellsManager();
4002}
4003
Note: See TracBrowser for help on using the repository browser.