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

Revision 2072, 176.5 KB checked in by mattausch, 17 years ago (diff)

prepared view cell generation that is useable.
changed back view cell generation to vsp osp.

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