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

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