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

Revision 713, 98.9 KB checked in by bittner, 19 years ago (diff)

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