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

Revision 2176, 177.2 KB checked in by mattausch, 17 years ago (diff)

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