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

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

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