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

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