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

Revision 681, 86.7 KB checked in by mattausch, 19 years ago (diff)

debug version

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