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

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