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

Revision 704, 95.6 KB checked in by mattausch, 19 years ago (diff)

implemented first version of the visibility filter

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