source: trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellsManager.cpp @ 491

Revision 491, 53.7 KB checked in by mattausch, 18 years ago (diff)
Line 
1#include "ViewCellsManager.h"
2#include "RenderSimulator.h"
3#include "Mesh.h"
4#include "Triangle3.h"
5#include "ViewCell.h"
6#include "Environment.h"
7#include "X3dParser.h"
8#include "ViewCellBsp.h"
9#include "KdTree.h"
10#include "VspKdTree.h"
11#include "Exporter.h"
12#include "VspBspTree.h"
13
14
15ViewCellsManager::ViewCellsManager():
16mRenderer(NULL),
17mConstructionSamples(0),
18mPostProcessSamples(0),
19mVisualizationSamples(0),
20mTotalAreaValid(false),
21mTotalArea(0.0f)
22{
23        mSceneBox.Initialize();
24        ParseEnvironment();
25}
26
27ViewCellsManager::ViewCellsManager(int constructionSamples):
28mConstructionSamples(constructionSamples),
29mRenderer(NULL),
30mPostProcessSamples(0),
31mVisualizationSamples(0)
32{
33        mSceneBox.Initialize();
34        ParseEnvironment();
35}
36
37void ViewCellsManager::ParseEnvironment()
38{
39        // post processing stuff
40        environment->GetIntValue("ViewCells.PostProcess.minPvsDif", mMinPvsDif);
41        environment->GetIntValue("ViewCells.PostProcess.minPvs", mMinPvs);
42        environment->GetIntValue("ViewCells.PostProcess.maxPvs", mMaxPvs);
43
44        environment->GetBoolValue("ViewCells.Visualization.exportRays", mExportRays);
45        environment->GetBoolValue("ViewCells.Visualization.exportGeometry", mExportGeometry);
46
47        char buf[50];
48       
49        environment->GetStringValue("ViewCells.Visualization.colorCode", buf);
50       
51        if (strcmp(buf, "PVS") == 0)
52                mColorCode = 1;
53        else if (strcmp(buf, "MergedLeaves") == 0)
54                mColorCode = 2;
55        else if (strcmp(buf, "MergedTreeDiff") == 0)
56                mColorCode = 3;
57        else
58                mColorCode = 0;
59
60        Debug << "colorCode: " << mColorCode << endl;
61}
62
63
64ViewCellsManager::~ViewCellsManager()
65{
66        DEL_PTR(mRenderer);
67
68        CLEAR_CONTAINER(mViewCells);
69}
70
71
72bool ViewCellsManager::LoadViewCells(const string filename)
73{
74        X3dParser parser;
75       
76        environment->GetFloatValue("ViewCells.height", parser.mViewCellHeight);
77       
78        bool success = parser.ParseFile(filename, *this);
79        Debug << (int)mViewCells.size() << " view cells loaded" << endl;
80
81        return success;
82}
83
84
85bool ViewCellsManager::GetViewPoint(Vector3 &viewPoint) const
86{
87        viewPoint = mSceneBox.GetRandomPoint();
88
89        return true;
90}
91
92
93bool ViewCellsManager::ViewPointValid(const Vector3 &viewPoint) const
94{
95        return mSceneBox.IsInside(viewPoint);
96}
97
98void ViewCellsManager::ComputeSampleContributions(const VssRayContainer &rays)
99{
100        // view cells not yet constructed
101        if (!ViewCellsConstructed())
102                return;
103 
104        VssRayContainer::const_iterator it, it_end = rays.end();
105
106        for (it = rays.begin(); it != it_end; ++ it)
107        {       
108                ComputeSampleContributions(*(*it));
109        }
110}
111
112
113void ViewCellsManager::EvaluateViewCellsStats()
114{
115        mViewCellsStats.Reset();
116
117        ViewCellContainer::const_iterator it, it_end = mViewCells.end();
118
119        for (it = mViewCells.begin(); it != it_end; ++ it)
120        {
121                (*it)->UpdateViewCellsStats(mViewCellsStats);
122        }
123}
124
125
126void ViewCellsManager::AddViewCell(ViewCell *viewCell)
127{
128        mViewCells.push_back(viewCell);
129}
130
131
132float ViewCellsManager::GetArea(ViewCell *viewCell) const
133{
134        return viewCell->GetArea();
135}
136
137
138float ViewCellsManager::GetVolume(ViewCell *viewCell) const
139{
140        return viewCell->GetVolume();
141}
142
143
144void ViewCellsManager::DeriveViewCells(const ObjectContainer &objects,
145                                                                           ViewCellContainer &viewCells,
146                                                                           const int maxViewCells) const
147{
148        // maximal max viewcells
149        int limit = maxViewCells > 0 ?
150                Min((int)objects.size(), maxViewCells) : (int)objects.size();
151
152        for (int i = 0; i < limit; ++ i)
153        {
154                Intersectable *object = objects[i];
155               
156                // extract the mesh instances
157                if (object->Type() == Intersectable::MESH_INSTANCE)
158                {
159                        MeshInstance *inst = dynamic_cast<MeshInstance *>(object);
160
161                        ViewCell *viewCell = GenerateViewCell(inst->GetMesh());
162                        viewCells.push_back(viewCell);
163                }
164                //TODO: transformed meshes
165        }
166}
167
168
169ViewCell *ViewCellsManager::ExtrudeViewCell(const Triangle3 &baseTri,
170                                                                                        const float height) const
171{
172        // one mesh per view cell
173        Mesh *mesh = new Mesh();
174       
175        //-- construct prism
176
177        // bottom
178        mesh->mFaces.push_back(new Face(2,1,0));
179        // top
180    mesh->mFaces.push_back(new Face(3,4,5));
181        // sides
182        mesh->mFaces.push_back(new Face(1, 4, 3, 0));
183        mesh->mFaces.push_back(new Face(2, 5, 4, 1));
184        mesh->mFaces.push_back(new Face(3, 5, 2, 0));
185
186        //--- extrude new vertices for top of prism
187        Vector3 triNorm = baseTri.GetNormal();
188
189        Triangle3 topTri;       
190
191        // add base vertices and calculate top vertices
192        for (int i = 0; i < 3; ++ i)
193                mesh->mVertices.push_back(baseTri.mVertices[i]);
194       
195        // add top vertices     
196        for (int i = 0; i < 3; ++ i)
197                mesh->mVertices.push_back(baseTri.mVertices[i] + height * triNorm);
198       
199        mesh->Preprocess();
200
201        return GenerateViewCell(mesh);
202}
203
204
205ViewCell *ViewCellsManager::MergeViewCells(ViewCell &front, ViewCell &back) const
206{
207        // generate merged view cell
208        ViewCell *vc = GenerateViewCell();
209
210        // merge pvs
211        vc->GetPvs().Merge(front.GetPvs(), back.GetPvs());
212
213        //-- merge ray sets
214        stable_sort(front.mPiercingRays.begin(), front.mPiercingRays.end());
215        stable_sort(back.mPiercingRays.begin(), back.mPiercingRays.end());
216
217        std::merge(front.mPiercingRays.begin(), front.mPiercingRays.end(),
218                           back.mPiercingRays.begin(), back.mPiercingRays.end(),
219                           vc->mPiercingRays.begin());
220
221        return vc;
222}
223
224
225void ViewCellsManager::SetRenderer(Renderer *renderer)
226{
227        mRenderer = renderer;
228}
229
230
231ViewCell *ViewCellsManager::GenerateViewCell(Mesh *mesh) const
232{
233        return new ViewCell(mesh);
234}
235
236
237void ViewCellsManager::SetVisualizationSamples(const int visSamples)
238{
239        mVisualizationSamples = visSamples;
240}
241
242
243void ViewCellsManager::SetConstructionSamples(const int constructionSamples)
244{
245        mConstructionSamples = constructionSamples;
246}
247
248
249void ViewCellsManager::SetPostProcessSamples(const int postProcessSamples)
250{
251        mPostProcessSamples = postProcessSamples;
252}
253
254
255int ViewCellsManager::GetVisualizationSamples() const
256{
257        return mVisualizationSamples;
258}
259
260
261int ViewCellsManager::GetConstructionSamples() const
262{
263        return mConstructionSamples;
264}
265
266
267int ViewCellsManager::GetPostProcessSamples() const
268{
269        return mPostProcessSamples;
270}
271
272
273void ViewCellsManager::GetPvsStatistics(PvsStatistics &stat)
274{
275  ViewCellContainer::const_iterator it = mViewCells.begin();
276  stat.viewcells = 0;
277  stat.minPvs = 100000000;
278  stat.maxPvs = 0;
279  stat.avgPvs = 0.0f;
280
281  for (; it != mViewCells.end(); ++it) {
282        ViewCell *viewcell = *it;
283        int pvsSize = viewcell->GetPvs().GetSize();
284        if ( pvsSize < stat.minPvs)
285          stat.minPvs = pvsSize;
286        if (pvsSize > stat.maxPvs)
287          stat.maxPvs = pvsSize;
288        stat.avgPvs += pvsSize;
289        stat.viewcells++;
290  }
291  if (stat.viewcells)
292        stat.avgPvs/=stat.viewcells;
293}
294
295
296void ViewCellsManager::PrintPvsStatistics(ostream &s)
297{
298  s<<"############# Viewcell PVS STAT ##################\n";
299  PvsStatistics pvsStat;
300  GetPvsStatistics(pvsStat);
301  s<<"#AVG_PVS\n"<<pvsStat.avgPvs<<endl;
302  s<<"#MAX_PVS\n"<<pvsStat.maxPvs<<endl;
303  s<<"#MIN_PVS\n"<<pvsStat.minPvs<<endl;
304}
305
306
307ViewCellContainer &ViewCellsManager::GetViewCells()
308{
309        return mViewCells;
310}
311
312
313void ViewCellsManager::SetViewSpaceBox(const AxisAlignedBox3 &box)
314{
315        mSceneBox = box;
316}
317
318
319void ViewCellsManager::ResetViewCells()
320{
321        mViewCells.clear();
322        CollectViewCells();
323        mViewCellsStats.Reset();
324        EvaluateViewCellsStats();
325
326        mTotalAreaValid = false;
327}
328
329
330void ViewCellsManager::ComputeSampleContributions(VssRay &ray)
331{
332        ViewCellContainer viewcells;
333               
334        ray.mPvsContribution = 0;
335        ray.mRelativePvsContribution = 0.0f;
336
337        // matt TODO: remove this!!
338        Ray hray(ray);
339        float tmin = 0, tmax = 1.0;
340       
341        //hray.Init(ray.GetOrigin(), ray.GetDir(), Ray::LINE_SEGMENT);
342        if (!GetSceneBbox().GetRaySegment(hray, tmin, tmax) || (tmin > tmax))
343                return;
344
345        Vector3 origin = hray.Extrap(tmin);
346        Vector3 termination = hray.Extrap(tmax);
347       
348        CastLineSegment(origin,
349                                        termination,
350                                        viewcells);
351 
352        ViewCellContainer::const_iterator it = viewcells.begin();
353       
354        for (; it != viewcells.end(); ++it)
355        {       
356                ViewCell *viewcell = *it;
357       
358                // if ray not outside of view space
359                float contribution;
360                bool added =
361                        viewcell->GetPvs().AddSample(ray.mTerminationObject,
362                                                                                 contribution);
363               
364                if (added)
365                        ++ ray.mPvsContribution;
366               
367                ray.mRelativePvsContribution += contribution;
368        }
369}
370
371
372void ViewCellsManager::GetRaySets(const VssRayContainer &sourceRays,
373                                                                  const int maxSize,
374                                                                  VssRayContainer &usedRays,
375                                                                  VssRayContainer *savedRays) const
376{
377        const int limit = min(maxSize, (int)sourceRays.size());
378        const float prop = (float)limit / ((float)sourceRays.size() + Limits::Small);
379
380        VssRayContainer::const_iterator it, it_end = sourceRays.end();
381        for (it = sourceRays.begin(); it != it_end; ++ it)
382        {
383                if (Random(1.0f) < prop)
384                        usedRays.push_back(*it);
385                else if (savedRays)
386                        savedRays->push_back(*it);
387        }
388}
389
390
391float ViewCellsManager::GetAccVcArea()
392{
393        // if already computed
394        if (mTotalAreaValid)
395                return mTotalArea;
396
397        mTotalArea = 0;
398        ViewCellContainer::const_iterator it, it_end = mViewCells.end();
399
400        for (it = mViewCells.begin(); it != it_end; ++ it)
401        {
402                //Debug << "area: " << GetArea(*it);
403        mTotalArea += GetArea(*it);
404        }
405
406        mTotalAreaValid = true;
407
408        return mTotalArea;
409}
410
411
412void ViewCellsManager::PrintStatistics(ostream &s) const
413{
414        s << mViewCellsStats << endl;
415}
416
417
418void ViewCellsManager::ExportViewCells(Exporter *exporter) const
419{
420        ViewCellContainer::const_iterator it, it_end = mViewCells.end();
421
422        for (it = mViewCells.begin(); it != it_end; ++ it)
423        {
424                ExportColor(exporter, *it);
425                ExportVcGeometry(exporter, *it);
426        }
427}
428
429
430/**********************************************************************/
431/*                   BspViewCellsManager implementation               */
432/**********************************************************************/
433
434
435BspViewCellsManager::BspViewCellsManager(BspTree *bspTree,
436                                                                                 int constructionSamples):
437ViewCellsManager(constructionSamples),
438mBspTree(bspTree)
439{
440}
441
442
443bool BspViewCellsManager::ViewCellsConstructed() const
444{
445        return mBspTree->GetRoot() != NULL;
446}
447
448
449ViewCell *BspViewCellsManager::GenerateViewCell(Mesh *mesh) const
450{
451        return new BspViewCell(mesh);
452}
453
454
455int BspViewCellsManager::Construct(const ObjectContainer &objects,
456                                                                   const VssRayContainer &rays)
457{
458        // if view cells were already constructed
459        if (ViewCellsConstructed())
460                return 0;
461
462        int sampleContributions = 0;
463       
464        // construct view cells using the collected samples
465        RayContainer constructionRays;
466        VssRayContainer savedRays;
467
468        const int limit = min(mConstructionSamples, (int)rays.size());
469
470        VssRayContainer::const_iterator it, it_end = rays.end();
471
472        const float prop = (float)limit / ((float)rays.size() + Limits::Small);
473
474        for (it = rays.begin(); it != it_end; ++ it)
475        {
476                if (Random(1.0f) < prop)
477                        constructionRays.push_back(new Ray(*(*it)));
478                else
479                        savedRays.push_back(*it);
480        }
481
482    if (mViewCells.empty())
483        {
484                // no view cells loaded
485                mBspTree->Construct(objects, constructionRays);
486                // collect final view cells
487                mBspTree->CollectViewCells(mViewCells);
488        }
489        else
490        {
491                mBspTree->Construct(mViewCells);
492        }
493
494        // destroy rays created only for construction
495        CLEAR_CONTAINER(constructionRays);
496
497        Debug << mBspTree->GetStatistics() << endl;
498       
499        EvaluateViewCellsStats();
500        Debug << "\nView cells after construction:\n" << mViewCellsStats << endl;
501
502        // recast rest of the rays
503        ComputeSampleContributions(savedRays);
504
505        return sampleContributions;
506}
507
508void BspViewCellsManager::CollectViewCells()
509{
510        mBspTree->CollectViewCells(mViewCells);
511}
512
513float BspViewCellsManager::GetProbability(ViewCell *viewCell)
514{
515        // compute view cell area as subsititute for probability
516#if 0
517        return GetArea(viewCell) / GetSceneBbox().SurfaceArea();
518#else
519        return GetArea(viewCell) / GetAccVcArea();
520#endif
521}
522
523
524float BspViewCellsManager::GetRendercost(ViewCell *viewCell, float objRendercost) const
525{
526        return viewCell->GetPvs().GetSize() * objRendercost;
527}
528
529
530AxisAlignedBox3 BspViewCellsManager::GetSceneBbox() const
531{
532        return mBspTree->GetBoundingBox();
533}
534
535
536int BspViewCellsManager::CastLineSegment(const Vector3 &origin,
537                                                                                 const Vector3 &termination,
538                                                                                 ViewCellContainer &viewcells)
539{
540        return mBspTree->CastLineSegment(origin, termination, viewcells);
541}
542
543
544int BspViewCellsManager::PostProcess(const ObjectContainer &objects,
545                                                                         const VssRayContainer &rays)
546{
547        if (!ViewCellsConstructed())
548        {
549                Debug << "view cells not constructed" << endl;
550                return 0;
551        }
552
553        //-- post processing of bsp view cells
554    int vcSize = 0;
555        int pvsSize = 0;
556
557        EvaluateViewCellsStats();
558        Debug << "\noriginal view cell partition:\n" << mViewCellsStats << endl;
559
560        mRenderer->RenderScene();
561        SimulationStatistics ss;
562        dynamic_cast<RenderSimulator *>(mRenderer)->GetStatistics(ss);
563
564    Debug << ss << endl;
565
566        if (1) // export view cells
567        {
568                cout << "exporting initial view cells (=leaves) ... ";
569                Exporter *exporter = Exporter::GetExporter("view_cells.x3d");
570       
571                if (exporter)
572                {
573                        //exporter->SetWireframe();
574                        exporter->SetFilled();
575                        ExportViewCells(exporter);
576                               
577                        if (mExportGeometry)
578                        {
579                                Material m;
580                                m.mDiffuseColor = RgbColor(0, 1, 0);
581                                exporter->SetForcedMaterial(m);
582                                exporter->SetWireframe();
583
584                                exporter->ExportGeometry(objects);
585                        }
586
587                        delete exporter;
588                }
589                cout << "finished" << endl;
590        }
591
592        cout << "starting post processing using " << mPostProcessSamples << " samples ... ";
593               
594        long startTime = GetTime();
595
596
597        // $$JB we do not have connectivity information from the ray in the moment
598        // perhaps we could recast the rays or remember the cells traversed inside the
599        // vssray (which would on other hand create some overhead)
600        //-- merge or subdivide view cells
601        int merged = 0;
602
603        vector<BspIntersection>::const_iterator iit;
604        CLEAR_CONTAINER(mBspRays);
605        ConstructBspRays(rays, mPostProcessSamples);
606       
607        for (int i = 0; i < (int)mBspRays.size(); ++ i)
608        { 
609                BspRay *ray = mBspRays[i];
610         
611                // traverse leaves stored in the rays and compare and merge consecutive
612                // leaves (i.e., the neighbors in the tree)
613                if (ray->intersections.size() < 2)
614                        continue;
615         
616                iit = ray->intersections.begin();
617
618                BspLeaf *previousLeaf = (*iit).mLeaf;
619                ++ iit;
620               
621                for (; iit != ray->intersections.end(); ++ iit)
622                {
623                        BspLeaf *leaf = (*iit).mLeaf;
624
625                        if (ShouldMerge(leaf, previousLeaf))
626                        {                       
627                                MergeBspLeafViewCells(leaf, previousLeaf);
628
629                                ++ merged;
630                        }
631               
632                        previousLeaf = leaf;
633                }
634        }
635
636        //-- stats and visualizations
637        cout << "finished" << endl;
638        cout << "merged " << merged << " view cells in "
639                 << TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl;
640
641        Debug << "Postprocessing: Merged " << merged << " view cells in "
642                  << TimeDiff(startTime, GetTime()) *1e-3 << " secs"
643                  << "using " << (int)mBspRays.size() << " samples" << endl << endl;
644       
645        CLEAR_CONTAINER(mBspRays);
646
647        // reset view cells and stats
648        ResetViewCells();
649
650        return merged;
651}
652
653
654BspViewCellsManager::~BspViewCellsManager()
655{
656        CLEAR_CONTAINER(mBspRays);
657}
658
659
660int BspViewCellsManager::GetType() const
661{
662        return BSP;
663}
664
665
666void BspViewCellsManager::Visualize(const ObjectContainer &objects,
667                                                                        const VssRayContainer &sampleRays)
668{
669        if (!ViewCellsConstructed())
670                return;
671        CLEAR_CONTAINER(mBspRays);
672        ConstructBspRays(sampleRays, mVisualizationSamples);
673       
674        if (1) // export view cells
675        {
676                cout << "exporting view cells after merge ... ";
677                Exporter *exporter = Exporter::GetExporter("merged_view_cells.x3d");
678
679                if (exporter)
680                {
681                        ExportViewCells(exporter);
682                        delete exporter;
683                }
684               
685                cout << "finished" << endl;
686        }       
687
688        //-- visualization of the BSP splits
689        bool exportSplits = false;
690        environment->GetBoolValue("BspTree.Visualization.exportSplits", exportSplits);
691       
692        if (exportSplits)
693        {
694                cout << "exporting splits ... ";
695                ExportSplits(objects);
696                cout << "finished" << endl;
697        }
698
699        ExportBspPvs(objects);
700}
701
702
703inline bool vc_gt(ViewCell *a, ViewCell *b)
704{
705        return a->GetPvs().GetSize() > b->GetPvs().GetSize();
706}
707
708
709void BspViewCellsManager::ExportSplits(const ObjectContainer &objects)
710{
711        Exporter *exporter = Exporter::GetExporter("bsp_splits.x3d");
712
713        if (exporter)
714        {       
715                Material m;
716                m.mDiffuseColor = RgbColor(1, 0, 0);
717                exporter->SetForcedMaterial(m);
718                exporter->SetWireframe();
719               
720                exporter->ExportBspSplits(*mBspTree, true);
721
722                //NOTE: take forced material, else big scenes cannot be viewed
723                m.mDiffuseColor = RgbColor(0, 1, 0);
724                exporter->SetForcedMaterial(m);
725                //exporter->ResetForcedMaterial();
726
727                exporter->SetFilled();
728                               
729                // export rays
730                if (0)
731                {
732                        VssRayContainer outRays;
733               
734                        int raysSize = min((int)mBspRays.size(), mVisualizationSamples);
735
736                        for (int i = 0; i < raysSize; ++ i)
737                                // only rays piercing geometry
738                                outRays.push_back(mBspRays[i]->vssRay);
739                                               
740                        // export rays
741                        exporter->ExportRays(outRays, RgbColor(1, 1, 0));
742                }
743
744                if (mExportGeometry)
745                        exporter->ExportGeometry(objects);
746
747                delete exporter;
748        }
749}
750
751
752void BspViewCellsManager::ExportBspPvs(const ObjectContainer &objects)
753{
754        const int leafOut = 10;
755       
756        ViewCell::NewMail();
757
758        //-- some rays for output
759        const int raysOut = min((int)mBspRays.size(), mVisualizationSamples);
760       
761        cout << "visualization using " << mVisualizationSamples << " samples" << endl;
762        Debug << "\nOutput view cells: " << endl;
763       
764        // sort view cells to get largest view cells
765#if 0
766        stable_sort(mViewCells.begin(), mViewCells.end(), vc_gt);
767#endif
768        int limit = min(leafOut, (int)mViewCells.size());
769               
770        for (int i = 0; i < limit; ++ i)
771        {
772                cout << "creating output for view cell " << i << " ... ";
773                VssRayContainer vcRays;
774                Intersectable::NewMail();
775#if 0
776                BspViewCell *vc = dynamic_cast<BspViewCell *>(mViewCells[i]);
777#else
778                BspViewCell *vc = dynamic_cast<BspViewCell *>(mViewCells[Random((int)mViewCells.size())]);
779#endif
780                cout << "creating output for view cell " << i << " ... ";
781
782#if 0
783                // check whether we can add the current ray to the output rays
784                for (int k = 0; k < raysOut; ++ k)
785                {
786                        BspRay *ray = mBspRays[k];
787                        for     (int j = 0; j < (int)ray->intersections.size(); ++ j)
788                        {
789                                BspLeaf *leaf = ray->intersections[j].mLeaf;
790                                if (vc == leaf->GetViewCell())
791                                        vcRays.push_back(ray->vssRay);
792                        }
793                }
794#endif
795                //bspLeaves[j]->Mail();
796                char s[64]; sprintf(s, "bsp-pvs%04d.x3d", i);
797
798                Exporter *exporter = Exporter::GetExporter(s);
799                       
800                exporter->SetWireframe();
801
802                Material m;//= RandomMaterial();
803                m.mDiffuseColor = RgbColor(0, 1, 0);
804                exporter->SetForcedMaterial(m);
805
806                if (vc->GetMesh())
807                        exporter->ExportViewCell(vc);
808                else
809                {
810                        PolygonContainer vcGeom;
811                       
812                        //-- export view cell
813                        mBspTree->ConstructGeometry(vc, vcGeom);
814                        exporter->ExportPolygons(vcGeom);
815                        CLEAR_CONTAINER(vcGeom);
816                }
817                       
818                Debug << i << ": pvs size=" << (int)vc->GetPvs().GetSize()
819                          << ", piercing rays=" << (int)vcRays.size()
820                          << ", leaves=" << (int)vc->mLeaves.size() << endl;
821
822                       
823                // export rays piercing this view cell
824#if 0
825                exporter->ExportRays(vcRays, RgbColor(0, 1, 0));
826#else
827                vector<BspLeaf *>::const_iterator lit, lit_end = vc->mLeaves.end();
828                for (lit = vc->mLeaves.begin(); lit != lit_end; ++ lit)
829                        exporter->ExportRays((*lit)->mVssRays);
830#endif
831                m.mDiffuseColor = RgbColor(1, 0, 0);
832                exporter->SetForcedMaterial(m);
833
834                ObjectPvsMap::const_iterator it,
835                        it_end = vc->GetPvs().mEntries.end();
836
837                exporter->SetFilled();
838
839                // output PVS of view cell
840                for (it = vc->GetPvs().mEntries.begin(); it != it_end; ++ it)
841                {
842                        Intersectable *intersect = (*it).first;
843
844                        if (!intersect->Mailed())
845                        {
846                                Material m = RandomMaterial();
847                                exporter->SetForcedMaterial(m);
848
849                                exporter->ExportIntersectable(intersect);
850                                intersect->Mail();
851                        }                       
852                }
853                               
854                DEL_PTR(exporter);
855                cout << "finished" << endl;
856        }
857
858        Debug << endl;
859}
860
861
862bool BspViewCellsManager::MergeBspLeafViewCells(BspLeaf *front, BspLeaf *back) const
863{
864        BspViewCell *viewCell =
865                dynamic_cast<BspViewCell *>(MergeViewCells(*front->GetViewCell(),
866                                                                                                   *back->GetViewCell()));
867       
868        if (!viewCell)
869                return false;
870
871        //-- change pointer to view cells of all leaves associated with the previous view cells
872        BspViewCell *fVc = front->GetViewCell();
873        BspViewCell *bVc = back->GetViewCell();
874
875        vector<BspLeaf *> fLeaves = fVc->mLeaves;
876        vector<BspLeaf *> bLeaves = bVc->mLeaves;
877
878        vector<BspLeaf *>::const_iterator it;
879       
880        for (it = fLeaves.begin(); it != fLeaves.end(); ++ it)
881        {
882                (*it)->SetViewCell(viewCell);
883                viewCell->mLeaves.push_back(*it);
884        }
885        for (it = bLeaves.begin(); it != bLeaves.end(); ++ it)
886        {
887                (*it)->SetViewCell(viewCell);
888                viewCell->mLeaves.push_back(*it);
889        }
890       
891        DEL_PTR(fVc);
892        DEL_PTR(bVc);
893
894        return true;
895}
896
897bool BspViewCellsManager::ShouldMerge(BspLeaf *front, BspLeaf *back) const
898{
899        ViewCell *fvc = front->GetViewCell();
900        ViewCell *bvc = back->GetViewCell();
901
902        if ((fvc == mBspTree->GetRootCell()) || (bvc == mBspTree->GetRootCell()) || (fvc == bvc))
903                return false;
904
905        int fdiff = fvc->GetPvs().Diff(bvc->GetPvs());
906
907        if (fvc->GetPvs().GetSize() + fdiff < mMaxPvs)
908        {
909                if ((fvc->GetPvs().GetSize() < mMinPvs) ||     
910                        (bvc->GetPvs().GetSize() < mMinPvs) ||
911                        ((fdiff < mMinPvsDif) && (bvc->GetPvs().Diff(fvc->GetPvs()) < mMinPvsDif)))
912                {
913                        return true;
914                }
915        }
916       
917        return false;
918}
919
920
921void BspViewCellsManager::ConstructBspRays(const VssRayContainer &rays,
922                                                                                   const int numSamples)
923{
924        VssRayContainer::const_iterator it, it_end = rays.end();
925
926        for (it = rays.begin(); it != rays.end() && mBspRays.size() < numSamples; ++ it)
927        {
928                VssRay *vssRay = *it;
929                BspRay *ray = new BspRay(vssRay);
930
931                ViewCellContainer viewCells;
932
933                // cast line segment to get intersections with bsp leaves
934                CastLineSegment(vssRay->mTermination, vssRay->mOrigin, viewCells);
935
936                ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
937                for (vit = viewCells.begin(); vit != vit_end; ++ vit)
938                {
939                        BspViewCell *vc = dynamic_cast<BspViewCell *>(*vit);
940                        ray->intersections.push_back(BspIntersection(0, vc->mLeaves[0]));
941                }
942
943                mBspRays.push_back(ray);
944        }
945}
946
947
948void BspViewCellsManager::ExportColor(Exporter *exporter,
949                                                                          ViewCell *vc) const
950{
951        if (mColorCode == 0) // Random color
952        {
953                exporter->ResetForcedMaterial();
954                return;
955        }
956
957        float importance = 0;
958
959        switch (mColorCode)
960        {
961        case 1: // pvs
962                {
963                        importance = (float)vc->GetPvs().GetSize() /
964                                (float)mViewCellsStats.maxPvs;
965                }
966                break;
967        case 2: // merges
968                {
969                        BspViewCell *bspVc = dynamic_cast<BspViewCell *>(vc);
970
971                        importance = (float)bspVc->mLeaves.size() /
972                                (float)mViewCellsStats.maxLeaves;
973                }
974                break;
975        case 3: // merge tree differene
976                {
977                        // TODO
978                }
979                break;
980        default:
981                break;
982        }
983
984        Material m;
985        m.mDiffuseColor.b = 1.0f;
986        m.mDiffuseColor.r = importance;
987        m.mDiffuseColor.g = 1.0f - m.mDiffuseColor.r;
988       
989        exporter->SetForcedMaterial(m);
990}
991
992void BspViewCellsManager::ExportVcGeometry(Exporter *exporter,
993                                                                                 ViewCell *vc) const
994{
995        if (vc->GetMesh())
996                exporter->ExportViewCell(vc);
997        else
998        {
999                PolygonContainer cell;
1000                mBspTree->ConstructGeometry(
1001                        dynamic_cast<BspViewCell *>(vc), cell);
1002                exporter->ExportPolygons(cell);
1003        }
1004}
1005
1006/**********************************************************************/
1007/*                   KdViewCellsManager implementation               */
1008/**********************************************************************/
1009
1010KdViewCellsManager::KdViewCellsManager(KdTree *kdTree):
1011ViewCellsManager(), mKdTree(kdTree), mKdPvsDepth(100)
1012{
1013}
1014
1015float KdViewCellsManager::GetProbability(ViewCell *viewCell)
1016{
1017        // compute view cell area / volume as subsititute for probability
1018#if 0
1019        return GetArea(viewCell) / GetSceneBbox().SurfaceArea();
1020#endif
1021#if 1
1022        return GetArea(viewCell) / GetAccVcArea();
1023#endif
1024#if 0
1025        return GetVolume(viewCell) / GetSceneBbox().GetVolume();
1026#endif
1027}
1028
1029
1030float KdViewCellsManager::GetRendercost(ViewCell *viewCell, float objRendercost) const
1031{
1032        return viewCell->GetPvs().GetSize() * objRendercost;
1033}
1034
1035
1036AxisAlignedBox3 KdViewCellsManager::GetSceneBbox() const
1037{
1038        return mKdTree->GetBox();
1039}
1040
1041void KdViewCellsManager::CollectViewCells()
1042{
1043        //mKdTree->CollectViewCells(mViewCells); TODO
1044}
1045
1046int KdViewCellsManager::Construct(const ObjectContainer &objects,
1047                                                                  const VssRayContainer &rays)
1048{
1049        // if view cells already constructed
1050        if (ViewCellsConstructed())
1051                return 0;
1052
1053        mKdTree->Construct();
1054
1055        mTotalAreaValid = false;
1056        // create the view cells
1057        mKdTree->CreateAndCollectViewCells(mViewCells);
1058       
1059        // cast rays
1060        ComputeSampleContributions(rays);
1061
1062        EvaluateViewCellsStats();
1063        Debug << "\nView cells after construction:\n" << mViewCellsStats << endl;
1064
1065        return 0;
1066}
1067
1068bool KdViewCellsManager::ViewCellsConstructed() const
1069{
1070        return mKdTree->GetRoot() != NULL;
1071}
1072
1073int KdViewCellsManager::PostProcess(const ObjectContainer &objects,
1074                                                                        const VssRayContainer &rays)
1075{
1076        return 0;
1077}
1078
1079void KdViewCellsManager::Visualize(const ObjectContainer &objects,
1080                                                                   const VssRayContainer &sampleRays)
1081{
1082        if (!ViewCellsConstructed())
1083                return;
1084
1085        // using view cells instead of the kd PVS of objects
1086        const bool useViewCells = true;
1087        bool exportRays = false;
1088
1089        int limit = min(mVisualizationSamples, (int)sampleRays.size());
1090        const int pvsOut = min((int)objects.size(), 10);
1091        VssRayContainer *rays = new VssRayContainer[pvsOut];
1092
1093        if (useViewCells)
1094        {
1095                const int leafOut = 10;
1096               
1097                ViewCell::NewMail();
1098 
1099                //-- some rays for output
1100                const int raysOut = min((int)sampleRays.size(), mVisualizationSamples);
1101                Debug << "visualization using " << raysOut << " samples" << endl;
1102
1103                //-- some random view cells and rays for output
1104                vector<KdLeaf *> kdLeaves;
1105               
1106                for (int i = 0; i < leafOut; ++ i)
1107                        kdLeaves.push_back(dynamic_cast<KdLeaf *>(mKdTree->GetRandomLeaf()));
1108               
1109                for (int i = 0; i < kdLeaves.size(); ++ i)
1110                {
1111                        KdLeaf *leaf = kdLeaves[i];
1112                        RayContainer vcRays;
1113                       
1114                        cout << "creating output for view cell " << i << " ... ";
1115#if 0                   
1116                        // check whether we can add the current ray to the output rays
1117                        for (int k = 0; k < raysOut; ++ k)
1118                        {
1119                                Ray *ray = sampleRays[k];
1120                               
1121                                for (int j = 0; j < (int)ray->bspIntersections.size(); ++ j)
1122                                {
1123                                        BspLeaf *leaf2 = ray->bspIntersections[j].mLeaf;
1124                                       
1125                                        if (leaf->GetViewCell() == leaf2->GetViewCell())
1126                                        {
1127                                                vcRays.push_back(ray);
1128                                        }
1129                                }
1130                        }
1131#endif                 
1132                        Intersectable::NewMail();
1133                       
1134                        ViewCell *vc = leaf->mViewCell;
1135                       
1136                        //bspLeaves[j]->Mail();
1137                        char s[64]; sprintf(s, "kd-pvs%04d.x3d", i);
1138                       
1139                        Exporter *exporter = Exporter::GetExporter(s);
1140                        exporter->SetFilled();
1141
1142                        exporter->SetWireframe();
1143                        //exporter->SetFilled();
1144                       
1145                        Material m;//= RandomMaterial();
1146                        m.mDiffuseColor = RgbColor(1, 1, 0);
1147                        exporter->SetForcedMaterial(m);
1148                       
1149                        AxisAlignedBox3 box = mKdTree->GetBox(leaf);
1150                        exporter->ExportBox(box);
1151
1152                        Debug << i << ": pvs size=" << (int)vc->GetPvs().GetSize()
1153                                << ", piercing rays=" << (int)vcRays.size() << endl;
1154                       
1155                        // export rays piercing this view cell
1156                        exporter->ExportRays(vcRays, 1000, RgbColor(0, 1, 0)); 
1157                       
1158                        m.mDiffuseColor = RgbColor(1, 0, 0);
1159                        exporter->SetForcedMaterial(m);
1160                       
1161                        // exporter->SetWireframe();
1162                        exporter->SetFilled();
1163                       
1164                        ObjectPvsMap::iterator it, it_end = vc->GetPvs().mEntries.end();
1165                        // output PVS of view cell
1166                        for (it = vc->GetPvs().mEntries.begin(); it !=  it_end; ++ it)
1167                        {
1168                                Intersectable *intersect = (*it).first;
1169                                if (!intersect->Mailed())
1170                                {
1171                                        exporter->ExportIntersectable(intersect);
1172                                        intersect->Mail();
1173                                }                       
1174                        }
1175                       
1176                        DEL_PTR(exporter);
1177                        cout << "finished" << endl;
1178                }
1179
1180                DEL_PTR(rays);
1181        }
1182        else // using kd PVS of objects
1183        {
1184                for (int i = 0; i < limit; ++ i)
1185                {
1186                        VssRay *ray = sampleRays[i];
1187               
1188                        // check whether we can add this to the rays
1189                        for (int j = 0; j < pvsOut; j++)
1190                        {
1191                                if (objects[j] == ray->mTerminationObject)
1192                                {
1193                                        rays[j].push_back(ray);
1194                                }
1195                        }
1196                }
1197
1198                if (exportRays)
1199                {
1200                        Exporter *exporter = NULL;
1201                        exporter = Exporter::GetExporter("sample-rays.x3d");
1202                        exporter->SetWireframe();
1203                        exporter->ExportKdTree(*mKdTree);
1204               
1205                        for (i=0; i < pvsOut; i++)
1206                                exporter->ExportRays(rays[i], RgbColor(1, 0, 0));
1207
1208                        exporter->SetFilled();
1209               
1210                        delete exporter;
1211                }
1212
1213                for (int k=0; k < pvsOut; k++)
1214                {
1215                        Intersectable *object = objects[k];
1216                        char s[64];     
1217                        sprintf(s, "sample-pvs%04d.x3d", k);
1218
1219                        Exporter *exporter = Exporter::GetExporter(s);
1220                        exporter->SetWireframe();
1221               
1222                        KdPvsMap::iterator i = object->mKdPvs.mEntries.begin();
1223                        Intersectable::NewMail();
1224                       
1225                        // avoid adding the object to the list
1226                        object->Mail();
1227                        ObjectContainer visibleObjects;
1228           
1229                        for (; i != object->mKdPvs.mEntries.end(); i++)
1230                        {
1231                                KdNode *node = (*i).first;
1232                                exporter->ExportBox(mKdTree->GetBox(node));
1233               
1234                                mKdTree->CollectObjects(node, visibleObjects);
1235                        }
1236               
1237                        exporter->ExportRays(rays[k],  RgbColor(0, 1, 0));
1238                        exporter->SetFilled();
1239                       
1240                        for (int j = 0; j < visibleObjects.size(); j++)
1241                                exporter->ExportIntersectable(visibleObjects[j]);
1242                       
1243                        Material m;
1244                        m.mDiffuseColor = RgbColor(1, 0, 0);
1245                        exporter->SetForcedMaterial(m);
1246                        exporter->ExportIntersectable(object);
1247               
1248                        delete exporter;
1249                }
1250        }               
1251}
1252
1253
1254void KdViewCellsManager::ExportColor(Exporter *exporter,
1255                                                                         ViewCell *vc) const
1256{
1257        // TODO
1258}
1259
1260
1261void KdViewCellsManager::ExportVcGeometry(Exporter *exporter,
1262                                                                                  ViewCell *vc) const
1263{
1264        KdViewCell *kdVc = dynamic_cast<KdViewCell *>(vc);
1265        vector<KdLeaf *>::const_iterator it, it_end = kdVc->mLeaves.end();
1266
1267        for (it = kdVc->mLeaves.begin(); it != it_end; ++ it)
1268                exporter->ExportBox(mKdTree->GetBox(*it));
1269}
1270
1271
1272int KdViewCellsManager::GetType() const
1273{
1274        return ViewCellsManager::KD;
1275}
1276
1277
1278
1279KdNode *KdViewCellsManager::GetNodeForPvs(KdLeaf *leaf)
1280{
1281        KdNode *node = leaf;
1282
1283        while (node->mParent && node->mDepth > mKdPvsDepth)
1284                node = node->mParent;
1285        return node;
1286}
1287
1288int KdViewCellsManager::CastLineSegment(const Vector3 &origin,
1289                                                                                const Vector3 &termination,
1290                                                                                ViewCellContainer &viewcells)
1291{
1292        return mKdTree->CastLineSegment(origin, termination, viewcells);
1293}
1294
1295
1296/**********************************************************************/
1297/*                   VspKdViewCellsManager implementation             */
1298/**********************************************************************/
1299
1300
1301VspKdViewCellsManager::VspKdViewCellsManager(VspKdTree *vspKdTree,
1302                                                                                         int constructionSamples):
1303ViewCellsManager(constructionSamples),
1304mVspKdTree(vspKdTree)
1305{
1306        mVspKdTree->SetViewCellsManager(this);
1307}
1308
1309float VspKdViewCellsManager::GetProbability(ViewCell *viewCell)
1310{
1311        // volume or area substitutes for view point probability
1312#if 0
1313        return GetArea(viewCell) / GetSceneBbox().SurfaceArea();
1314#else
1315        return GetArea(viewCell) / GetAccVcArea();
1316#endif
1317}
1318
1319
1320float VspKdViewCellsManager::GetRendercost(ViewCell *viewCell, float objRendercost) const
1321{
1322        return viewCell->GetPvs().GetSize() * objRendercost;
1323}
1324
1325void VspKdViewCellsManager::CollectViewCells()
1326{
1327        mVspKdTree->CollectViewCells(mViewCells);
1328}
1329
1330int VspKdViewCellsManager::Construct(const ObjectContainer &objects,
1331                                                                         const VssRayContainer &rays)
1332{
1333        // if view cells already constructed
1334        if (ViewCellsConstructed())
1335                return 0;
1336               
1337        VssRayContainer constructionRays;
1338        VssRayContainer savedRays;
1339
1340        GetRaySets(rays,
1341                           mConstructionSamples,
1342                           constructionRays,
1343                           &savedRays);
1344       
1345        Debug << "constructing vsp kd tree using "
1346                  << (int)constructionRays.size() << " samples" << endl;
1347
1348        mVspKdTree->Construct(constructionRays, &mSceneBox);
1349        Debug << mVspKdTree->GetStatistics() << endl;
1350
1351        // export leaf building blocks
1352        ExportLeaves(objects, rays);
1353
1354        // finally merge kd leaf building blocks to view cells
1355        const int merged = mVspKdTree->MergeViewCells(rays);
1356
1357        // collapse siblings belonging to the same view cell
1358        mVspKdTree->CollapseTree(mVspKdTree->GetRoot());
1359       
1360        // collapse siblings belonging to the same view cell
1361        mVspKdTree->RefineViewCells(rays);
1362
1363        // evaluale view cell stats
1364        ResetViewCells();
1365
1366        Debug << "\nView cells after construction:\n" << mViewCellsStats << endl;
1367
1368        long startTime = GetTime();
1369        // recast rest of rays
1370        ComputeSampleContributions(savedRays);
1371       
1372        Debug << "Computed remaining ray contribution in " << TimeDiff(startTime, GetTime()) * 1e-3
1373                  << " secs" << endl;
1374
1375        return merged;
1376}
1377
1378bool VspKdViewCellsManager::ViewCellsConstructed() const
1379{
1380        return mVspKdTree->GetRoot() != NULL;
1381}
1382
1383
1384ViewCell *VspKdViewCellsManager::GenerateViewCell(Mesh *mesh) const
1385{
1386        return new VspKdViewCell(mesh);
1387}
1388
1389int VspKdViewCellsManager::PostProcess(const ObjectContainer &objects,
1390                                                                           const VssRayContainer &rays)
1391{
1392        if (!ViewCellsConstructed())
1393                return 0;
1394
1395        // recalculate stats
1396        EvaluateViewCellsStats();
1397
1398        return 0;
1399}
1400
1401
1402AxisAlignedBox3 VspKdViewCellsManager::GetSceneBbox() const
1403{
1404        return mVspKdTree->GetBBox(mVspKdTree->GetRoot());
1405}
1406
1407
1408void VspKdViewCellsManager::ExportLeaves(const ObjectContainer &objects,
1409                                                                                 const VssRayContainer &sampleRays)
1410{
1411        if (!ViewCellsConstructed())
1412                return;
1413
1414        //-- export leaf building blocks
1415        Exporter *exporter = Exporter::GetExporter("vspkdtree.x3d");
1416        if (!exporter)
1417                return;
1418
1419        //exporter->SetWireframe();
1420        //exporter->ExportVspKdTree(*mVspKdTree, mVspKdTree->GetStatistics().maxPvsSize);
1421        exporter->ExportVspKdTree(*mVspKdTree);
1422
1423        if (mExportGeometry)
1424                exporter->ExportGeometry(objects);
1425
1426        if (mExportRays)
1427        {
1428                const float prob = (float)mVisualizationSamples
1429                        / ((float)sampleRays.size() + Limits::Small);
1430
1431                exporter->SetWireframe();
1432
1433                //-- collect uniformly distributed rays
1434                VssRayContainer rays;
1435
1436                for (int i = 0; i < sampleRays.size(); ++ i)
1437                {
1438                        if (RandomValue(0,1) < prob)
1439                                rays.push_back(sampleRays[i]);
1440                }
1441                exporter->ExportRays(rays, RgbColor(1, 0, 0));
1442        }
1443
1444        delete exporter;
1445}
1446
1447void VspKdViewCellsManager::Visualize(const ObjectContainer &objects,
1448                                                                          const VssRayContainer &sampleRays)
1449{
1450        if (!ViewCellsConstructed())
1451                return;
1452       
1453        //-- export single view cells
1454        for (int i = 0; i < 10; ++ i)
1455        {
1456                char s[64];
1457                sprintf(s, "vsp_viewcell%04d.x3d", i);
1458                Exporter *exporter = Exporter::GetExporter(s);
1459                const int idx =
1460                        (int)RandomValue(0.0, (Real)((int)mViewCells.size() - 1));
1461
1462                VspKdViewCell *vc = dynamic_cast<VspKdViewCell *>(mViewCells[idx]);
1463
1464                cout << "Output view cell " << i << " with pvs size " << vc->GetPvs().GetSize() << endl;
1465                Debug << "Output view cell " << i << " with pvs size " << vc->GetPvs().GetSize() << endl;
1466                //-- export geometry
1467                Material m;
1468                m.mDiffuseColor = RgbColor(0, 1, 1);
1469                               
1470                exporter->SetForcedMaterial(m);
1471                exporter->SetWireframe();
1472
1473                ExportVcGeometry(exporter, vc);
1474
1475                //-- export stored rays
1476                if (mExportRays)
1477                {
1478                        vector<VspKdLeaf *>::const_iterator it,
1479                                it_end = vc->mLeaves.end();
1480
1481                        for (it = vc->mLeaves.begin(); it != it_end; ++ it)
1482                        {
1483                                VspKdLeaf *leaf = *it;
1484                                AxisAlignedBox3 box = mVspKdTree->GetBBox(leaf);
1485
1486                                VssRayContainer vssRays;
1487
1488                                VssRayContainer castRays;
1489                                VssRayContainer initRays;
1490
1491                                leaf->GetRays(vssRays);
1492
1493                                VssRayContainer::const_iterator it, it_end = vssRays.end();
1494                                const float prop = 200.0f / (float)vssRays.size();
1495
1496                                for (it = vssRays.begin(); it != it_end; ++ it)
1497                                {
1498                                        if (Random(1) < prop)
1499                                                if ((*it)->mTerminationObject == NULL)
1500                                                        castRays.push_back(*it);
1501                                                else
1502                                                        initRays.push_back(*it);
1503                                }
1504
1505                                exporter->ExportRays(castRays, RgbColor(1, 0, 0));
1506                                exporter->ExportRays(initRays, RgbColor(0, 1, 0));
1507                        }
1508                }
1509
1510                //-- output PVS of view cell
1511                m.mDiffuseColor = RgbColor(1, 0, 0);
1512                exporter->SetForcedMaterial(m);
1513
1514                Intersectable::NewMail();
1515
1516                ObjectPvsMap::const_iterator it,
1517                        it_end = vc->GetPvs().mEntries.end();
1518
1519                exporter->SetFilled();
1520
1521                for (it = vc->GetPvs().mEntries.begin(); it != it_end; ++ it)
1522                {
1523                        Intersectable *intersect = (*it).first;
1524
1525                        if (!intersect->Mailed())
1526                        {
1527                                Material m = RandomMaterial();
1528                                exporter->SetForcedMaterial(m);
1529
1530                                exporter->ExportIntersectable(intersect);
1531                                intersect->Mail();
1532                        }                       
1533                }
1534
1535                delete exporter;
1536        }
1537
1538        //-- export final view cells
1539        Exporter *exporter = Exporter::GetExporter("vspkdtree_merged.x3d");
1540       
1541        //if (exportGeometry) exporter->SetWireframe();
1542        //else exporter->SetFilled();
1543
1544        ExportViewCells(exporter);
1545
1546        if (mExportGeometry)
1547        {
1548                exporter->SetFilled();
1549                exporter->ExportGeometry(objects);
1550        }
1551
1552        if (mExportRays)
1553        {
1554                const float prob = (float)mVisualizationSamples
1555                        / ((float)sampleRays.size() + Limits::Small);
1556               
1557                exporter->SetWireframe();
1558                       
1559                VssRayContainer rays;
1560               
1561                for (int i = 0; i < sampleRays.size(); ++ i)
1562                {
1563                  if (RandomValue(0,1) < prob)
1564                        rays.push_back(sampleRays[i]);
1565                }
1566                exporter->ExportRays(rays, RgbColor(1, 0, 0)); 
1567        }
1568
1569        delete exporter;
1570}
1571
1572int VspKdViewCellsManager::GetType() const
1573{
1574        return VSP_KD;
1575}
1576
1577
1578int VspKdViewCellsManager::CastLineSegment(const Vector3 &origin,
1579                                                                                   const Vector3 &termination,
1580                                                                                   ViewCellContainer &viewcells)
1581{
1582        return mVspKdTree->CastLineSegment(origin, termination, viewcells);
1583}
1584
1585
1586void VspKdViewCellsManager::ExportColor(Exporter *exporter,
1587                                                                                ViewCell *vc) const
1588{
1589        if (mColorCode == 0) // Random color
1590                return;
1591       
1592        float importance = 0;
1593
1594        switch (mColorCode)
1595        {
1596        case 1: // pvs
1597                {
1598                        importance = (float)vc->GetPvs().GetSize() /
1599                                (float)mViewCellsStats.maxPvs;
1600                }
1601                break;
1602        case 2: // merges
1603                {
1604            VspKdViewCell *vspKdVc = dynamic_cast<VspKdViewCell *>(vc);
1605
1606                        importance = (float)vspKdVc->mLeaves.size() /
1607                                (float)mViewCellsStats.maxLeaves;
1608                }
1609                break;
1610        case 3: // merged tree depth difference
1611                {
1612                        //importance = (float)GetMaxTreeDiff(vc) /
1613                        //      (float)(mVspBspTree->GetStatistics().maxDepth * 2);
1614                }
1615                break;
1616        default:
1617                break;
1618        }
1619
1620        Material m;
1621        m.mDiffuseColor.b = 1.0f;
1622        m.mDiffuseColor.r = importance;
1623        m.mDiffuseColor.g = 1.0f - m.mDiffuseColor.r;
1624        //Debug << "importance: " << importance << endl;
1625        exporter->SetForcedMaterial(m);
1626}
1627
1628
1629void VspKdViewCellsManager::ExportVcGeometry(Exporter *exporter,
1630                                                                                   ViewCell *vc) const
1631{
1632        VspKdViewCell *kdVc = dynamic_cast<VspKdViewCell *>(vc);
1633        vector<VspKdLeaf *>::const_iterator it, it_end = kdVc->mLeaves.end();
1634
1635        Mesh m;
1636        for (it = kdVc->mLeaves.begin(); it != it_end; ++ it)
1637        {
1638                mVspKdTree->GetBBox(*it).AddBoxToMesh(&m);
1639        }
1640
1641        exporter->ExportMesh(&m);
1642}
1643
1644
1645/************************************************************************/
1646/*                 VspBspViewCellsManager implementation                */
1647/************************************************************************/
1648
1649
1650VspBspViewCellsManager::VspBspViewCellsManager(VspBspTree *vspBspTree,
1651                                                                                           int constructionSamples):
1652ViewCellsManager(constructionSamples),
1653mVspBspTree(vspBspTree)
1654{
1655        mVspBspTree->SetViewCellsManager(this);
1656}
1657
1658
1659VspBspViewCellsManager::~VspBspViewCellsManager()
1660{
1661}
1662
1663
1664float VspBspViewCellsManager::GetProbability(ViewCell *viewCell)
1665{
1666#if 0
1667        return GetArea(viewCell) / GetSceneBbox().SurfaceArea();
1668#else
1669        return GetArea(viewCell) / GetAccVcArea();
1670#endif
1671}
1672
1673
1674void VspBspViewCellsManager::CollectViewCells()
1675{
1676        mVspBspTree->CollectViewCells(mViewCells);
1677}
1678
1679
1680float VspBspViewCellsManager::GetRendercost(ViewCell *viewCell,
1681                                                                                        float objRendercost) const
1682{
1683        return viewCell->GetPvs().GetSize() * objRendercost;
1684}
1685
1686
1687AxisAlignedBox3 VspBspViewCellsManager::GetSceneBbox() const
1688{
1689        return mVspBspTree->GetBoundingBox();
1690}
1691
1692
1693bool VspBspViewCellsManager::ViewCellsConstructed() const
1694{
1695        return mVspBspTree->GetRoot() != NULL;
1696}
1697
1698
1699ViewCell *VspBspViewCellsManager::GenerateViewCell(Mesh *mesh) const
1700{
1701        return new BspViewCell(mesh);
1702}
1703
1704int VspBspViewCellsManager::Construct(const ObjectContainer &objects,
1705                                                                          const VssRayContainer &rays)
1706{
1707        // if view cells were already constructed
1708        if (ViewCellsConstructed())
1709                return 0;
1710
1711        int sampleContributions = 0;
1712       
1713        VssRayContainer constructionRays;
1714        VssRayContainer savedRays;
1715
1716        GetRaySets(rays, mConstructionSamples, constructionRays, &savedRays);
1717
1718        Debug << "construction rays: " << (int)savedRays.size() << endl;
1719        Debug << "saved rays: " << (int)constructionRays.size() << endl;
1720
1721        mVspBspTree->Construct(constructionRays, &mSceneBox);
1722       
1723        Debug << mVspBspTree->GetStatistics() << endl;
1724
1725        // collapse invalid regions
1726        cout << "collapsing invalid tree regions ... ";
1727        mVspBspTree->CollapseTree(mVspBspTree->GetRoot());
1728        cout << "finished" << endl;
1729        cout << "reseting view cell stats ... ";
1730        ResetViewCells();
1731        cout << "finished" << endl;
1732       
1733        Debug << "\nView cells after construction:\n" << mViewCellsStats << endl;
1734
1735        if (1) // export initial view cells
1736        {
1737                cout << "exporting initial view cells (=leaves) ... ";
1738                Exporter *exporter = Exporter::GetExporter("view_cells.x3d");
1739       
1740                if (exporter)
1741                {
1742                        //exporter->SetWireframe();
1743                        exporter->SetFilled();
1744                        ExportViewCells(exporter);
1745
1746                        //if (mExportRays)
1747                        //      exporter->ExportRays(postProcessRays, RgbColor(1, 1, 0));
1748                       
1749                        if (mExportGeometry)
1750                                exporter->ExportGeometry(objects);
1751                       
1752                        delete exporter;
1753                }
1754                cout << "finished" << endl;
1755        }
1756
1757        long startTime = GetTime();
1758        cout << "Computing remaining ray contributions ... ";
1759        // recast rest of rays
1760        ComputeSampleContributions(savedRays);
1761        cout << "finished" << endl;
1762
1763        Debug << "Computed remaining ray contribution in " << TimeDiff(startTime, GetTime()) * 1e-3
1764                  << " secs" << endl;
1765
1766        cout << "construction finished" << endl;
1767        return sampleContributions;
1768}
1769
1770
1771// matt TODO: remove
1772int VspBspViewCellsManager::MergeViewCells(const VssRayContainer &rays) const
1773{
1774        vector<BspIntersection>::const_iterator iit;
1775        vector<BspRay *>bspRays;
1776        int merged = 0;
1777
1778        mVspBspTree->ConstructBspRays(bspRays, rays);
1779
1780        for (int i = 0; i < (int)bspRays.size(); ++ i)
1781        {
1782                BspRay *ray = bspRays[i];
1783         
1784                // traverse leaves stored in the rays and compare and merge consecutive
1785                // leaves (i.e., the neighbors in the tree)
1786                if (ray->intersections.size() < 2)
1787                        continue;
1788         
1789                iit = ray->intersections.begin();
1790
1791                BspLeaf *previousLeaf = (*iit).mLeaf;
1792                ++ iit;
1793               
1794                for (; iit != ray->intersections.end(); ++ iit)
1795                {
1796                        BspLeaf *leaf = (*iit).mLeaf;
1797
1798                        if (ShouldMerge(leaf, previousLeaf))
1799                        {                       
1800                                mVspBspTree->MergeViewCells(leaf, previousLeaf);
1801                                ++ merged;
1802                        }
1803                        previousLeaf = leaf;
1804                }
1805        }
1806        CLEAR_CONTAINER(bspRays);
1807
1808        return merged;
1809}
1810       
1811
1812int VspBspViewCellsManager::PostProcess(const ObjectContainer &objects,
1813                                                                                const VssRayContainer &rays)
1814{
1815        if (!ViewCellsConstructed())
1816        {
1817                Debug << "view cells not constructed" << endl;
1818                return 0;
1819        }
1820
1821        //-- post processing of bsp view cells
1822    int vcSize = 0;
1823        int pvsSize = 0;
1824
1825        VssRayContainer postProcessRays;
1826        GetRaySets(rays, mPostProcessSamples, postProcessRays);
1827
1828        Debug << "post processing using " << (int)postProcessRays.size() << " samples" << endl;
1829        EvaluateViewCellsStats();
1830        Debug << "\noriginal view cell partition:\n" << mViewCellsStats << endl << endl;
1831
1832        mRenderer->RenderScene();
1833        SimulationStatistics ss;
1834        dynamic_cast<RenderSimulator *>(mRenderer)->GetStatistics(ss);
1835    Debug << ss << endl;
1836
1837        //-- merge or subdivide view cells
1838        int merged = 0;
1839       
1840        cout << "starting merge using " << mPostProcessSamples << " samples ... ";
1841        long startTime = GetTime();
1842
1843        merged = mVspBspTree->MergeViewCells(postProcessRays);
1844
1845        //-- stats and visualizations
1846        cout << "finished" << endl;
1847        cout << "merged " << merged << " view cells in "
1848                 << TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl;
1849
1850        Debug << "Postprocessing: Merged " << merged << " view cells in "
1851                  << TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl << endl;
1852       
1853        cout << "reseting view cell stats ... ";
1854        ResetViewCells();
1855        cout << "finished" << endl;
1856
1857        //BspLeaf::NewMail();
1858        if (1) // export merged view cells
1859        {
1860                Exporter *exporter = Exporter::GetExporter("merged_view_cells.x3d");
1861                Debug << "\nView cells after merge:\n" << mViewCellsStats << endl;
1862
1863                cout << "exporting view cells after merge ... ";
1864
1865                if (exporter)
1866                {
1867                        //exporter->SetWireframe();
1868                        exporter->SetFilled();
1869                        ExportViewCells(exporter);
1870
1871                        if (mExportGeometry)
1872                        {
1873                                Material m;
1874                                m.mDiffuseColor = RgbColor(0, 1, 0);
1875                                exporter->SetForcedMaterial(m);
1876                                exporter->SetFilled();
1877
1878                                exporter->ExportGeometry(objects);
1879                        }
1880
1881                        delete exporter;
1882                }
1883                cout << "finished" << endl;
1884        }
1885
1886        Debug << "render time before refine:" << endl;
1887        mRenderer->RenderScene();
1888        dynamic_cast<RenderSimulator *>(mRenderer)->GetStatistics(ss);
1889    Debug << ss << endl;
1890
1891        cout << "Refining the merged view cells ... ";
1892        startTime = GetTime();
1893
1894        // refining the merged view cells
1895        const int refined = mVspBspTree->RefineViewCells(rays);
1896
1897        //-- stats and visualizations
1898        cout << "finished" << endl;
1899        cout << "refined " << refined << " view cells in "
1900                 << TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl;
1901
1902        Debug << "Postprocessing: refined " << refined << " view cells in "
1903                  << TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl << endl;
1904       
1905        // collapse sibling leaves that share the same view cell
1906        mVspBspTree->CollapseTree(mVspBspTree->GetRoot());
1907        // reset view cells and stats
1908        ResetViewCells();
1909
1910        return merged;
1911}
1912
1913
1914int VspBspViewCellsManager::GetType() const
1915{
1916        return VSP_BSP;
1917}
1918
1919
1920bool VspBspViewCellsManager::GetViewPoint(Vector3 &viewPoint) const
1921{
1922        if (!ViewCellsConstructed())
1923                return ViewCellsManager::GetViewPoint(viewPoint);
1924
1925        // TODO: set reasonable limit
1926        const int limit = 20;
1927
1928        for (int i = 0; i < limit; ++ i)
1929        {
1930                viewPoint = mSceneBox.GetRandomPoint();
1931                if (mVspBspTree->ViewPointValid(viewPoint))
1932                {
1933                        return true;
1934                }
1935        }
1936        Debug << "failed to find valid view point, taking " << viewPoint << endl;
1937        return false;
1938}
1939
1940
1941bool VspBspViewCellsManager::ViewPointValid(const Vector3 &viewPoint) const
1942{
1943        return mSceneBox.IsInside(viewPoint) &&
1944                   mVspBspTree->ViewPointValid(viewPoint);
1945}
1946
1947
1948void VspBspViewCellsManager::Visualize(const ObjectContainer &objects,
1949                                                                           const VssRayContainer &sampleRays)
1950{
1951        if (!ViewCellsConstructed())
1952                return;
1953
1954        VssRayContainer visRays;
1955        GetRaySets(sampleRays, mVisualizationSamples, visRays);
1956
1957        if (1) // export view cells
1958        {
1959                cout << "exporting view cells after post process ... ";
1960                Exporter *exporter = Exporter::GetExporter("final_view_cells.x3d");
1961
1962                if (exporter)
1963                {
1964                        if (mExportGeometry)
1965                                exporter->ExportGeometry(objects);
1966
1967                        // export rays
1968                        if (mExportRays)
1969                        {
1970                                exporter->ExportRays(visRays, RgbColor(0, 1, 0));
1971                        }
1972
1973                        ExportViewCells(exporter);
1974                        delete exporter;
1975                }
1976               
1977                cout << "finished" << endl;
1978        }       
1979
1980        //-- visualization of the BSP splits
1981        bool exportSplits = false;
1982        environment->GetBoolValue("VspBspTree.Visualization.exportSplits", exportSplits);
1983       
1984        if (exportSplits)
1985        {
1986                cout << "exporting splits ... ";
1987                ExportSplits(objects, visRays);
1988                cout << "finished" << endl;
1989        }
1990
1991        // export single view cells
1992        ExportBspPvs(objects, visRays);
1993}
1994       
1995
1996void VspBspViewCellsManager::ExportSplits(const ObjectContainer &objects,
1997                                                                                  const VssRayContainer &rays)
1998{
1999        Exporter *exporter = Exporter::GetExporter("bsp_splits.x3d");
2000
2001        if (exporter)
2002        {       
2003                Material m;
2004                m.mDiffuseColor = RgbColor(1, 0, 0);
2005                exporter->SetForcedMaterial(m);
2006                exporter->SetWireframe();
2007               
2008                exporter->ExportBspSplits(*mVspBspTree, true);
2009
2010                // take forced material, else big scenes cannot be viewed
2011                m.mDiffuseColor = RgbColor(0, 1, 0);
2012                exporter->SetForcedMaterial(m);
2013                exporter->SetFilled();
2014
2015                exporter->ResetForcedMaterial();
2016               
2017                // export rays
2018                if (mExportRays)
2019                        exporter->ExportRays(rays, RgbColor(1, 1, 0));
2020       
2021                if (mExportGeometry)
2022                        exporter->ExportGeometry(objects);
2023
2024                delete exporter;
2025        }
2026}
2027
2028void VspBspViewCellsManager::ExportBspPvs(const ObjectContainer &objects,
2029                                                                                  const VssRayContainer &rays)
2030{
2031        const int leafOut = 10;
2032       
2033        ViewCell::NewMail();
2034       
2035        cout << "visualization using " << mVisualizationSamples << " samples" << endl;
2036        Debug << "\nOutput view cells: " << endl;
2037       
2038        // sort view cells to visualize the largest view cells
2039#if 0
2040        stable_sort(mViewCells.begin(), mViewCells.end(), vc_gt);
2041#endif
2042        int limit = min(leafOut, (int)mViewCells.size());
2043
2044#if 1
2045        //-- some rays for output
2046        vector<BspRay *> bspRays;
2047        mVspBspTree->ConstructBspRays(bspRays, rays);
2048
2049        const int raysOut = min((int)bspRays.size(), mVisualizationSamples);
2050#endif
2051
2052        for (int i = 0; i < limit; ++ i)
2053        {
2054                cout << "creating output for view cell " << i << " ... ";
2055               
2056                VssRayContainer vcRays;
2057                Intersectable::NewMail();
2058#if 0
2059                BspViewCell *vc = dynamic_cast<BspViewCell *>(mViewCells[i]);
2060#else
2061                BspViewCell *vc = dynamic_cast<BspViewCell *>
2062                        (mViewCells[Random((int)mViewCells.size())]);
2063#endif
2064
2065#if 1
2066                // check whether we can add the current ray to the output rays
2067                for (int k = 0; k < raysOut; ++ k)
2068                {
2069                        BspRay *ray = bspRays[k];
2070                        for     (int j = 0; j < (int)ray->intersections.size(); ++ j)
2071                        {
2072                                BspLeaf *leaf = ray->intersections[j].mLeaf;
2073                                if (vc == leaf->GetViewCell())
2074                                        vcRays.push_back(ray->vssRay);
2075                        }
2076                }
2077#endif
2078                //bspLeaves[j]->Mail();
2079                char s[64]; sprintf(s, "bsp-pvs%04d.x3d", i);
2080                Exporter *exporter = Exporter::GetExporter(s);
2081                exporter->SetWireframe();
2082
2083                Material m;//= RandomMaterial();
2084                m.mDiffuseColor = RgbColor(0, 1, 0);
2085                exporter->SetForcedMaterial(m);
2086
2087                ExportVcGeometry(exporter, vc);
2088                       
2089                               
2090                Debug << i << ": pvs size=" << (int)vc->GetPvs().GetSize()
2091                          << ", piercing rays=" << (int)vcRays.size()
2092                          << ", leaves=" << (int)vc->mLeaves.size() << endl;
2093               
2094                //-- export rays piercing this view cell
2095#if 1
2096                exporter->ExportRays(vcRays, RgbColor(0, 1, 0));
2097#endif
2098#if 0
2099                vector<BspLeaf *>::const_iterator lit, lit_end = vc->mLeaves.end();
2100
2101                for (lit = vc->mLeaves.begin(); lit != lit_end; ++ lit)
2102                        exporter->ExportRays((*lit)->mVssRays);
2103#endif
2104                m.mDiffuseColor = RgbColor(1, 0, 0);
2105                exporter->SetForcedMaterial(m);
2106
2107                ObjectPvsMap::const_iterator it,
2108                        it_end = vc->GetPvs().mEntries.end();
2109
2110                exporter->SetFilled();
2111
2112                // output PVS of view cell
2113                for (it = vc->GetPvs().mEntries.begin(); it != it_end; ++ it)
2114                {
2115                        Intersectable *intersect = (*it).first;
2116
2117                        if (!intersect->Mailed())
2118                        {
2119                                Material m = RandomMaterial();
2120                                exporter->SetForcedMaterial(m);
2121
2122                                exporter->ExportIntersectable(intersect);
2123                                intersect->Mail();
2124                        }                       
2125                }
2126                               
2127                DEL_PTR(exporter);
2128                cout << "finished" << endl;
2129        }
2130
2131#if 1
2132        CLEAR_CONTAINER(bspRays);
2133#endif
2134        Debug << endl;
2135}
2136
2137
2138bool VspBspViewCellsManager::ShouldMerge(BspLeaf *front, BspLeaf *back) const
2139{
2140        ViewCell *fvc = front->GetViewCell();
2141        ViewCell *bvc = back->GetViewCell();
2142
2143        if (fvc == bvc)
2144                return false;
2145
2146        const int fdiff = fvc->GetPvs().Diff(bvc->GetPvs());
2147
2148        if (fvc->GetPvs().GetSize() + fdiff < mMaxPvs)
2149        {
2150                if ((fvc->GetPvs().GetSize() < mMinPvs) ||     
2151                        (bvc->GetPvs().GetSize() < mMinPvs) ||
2152                        ((fdiff < mMinPvsDif) &&
2153                         (bvc->GetPvs().Diff(fvc->GetPvs()) < mMinPvsDif)))
2154                {
2155                        return true;
2156                }
2157        }
2158       
2159        return false;
2160}
2161
2162
2163int VspBspViewCellsManager::CastLineSegment(const Vector3 &origin,
2164                                                                                        const Vector3 &termination,
2165                                                                                        ViewCellContainer &viewcells)
2166{
2167        return mVspBspTree->CastLineSegment(origin, termination, viewcells);
2168}
2169
2170
2171void VspBspViewCellsManager::ExportColor(Exporter *exporter,
2172                                                                                 ViewCell *vc) const
2173{
2174        if (mColorCode == 0) // Random color
2175                return;
2176       
2177        float importance = 0;
2178
2179        switch (mColorCode)
2180        {
2181        case 1: // pvs
2182                {
2183                        importance = (float)vc->GetPvs().GetSize() /
2184                                (float)mViewCellsStats.maxPvs;
2185                }
2186                break;
2187        case 2: // merges
2188                {
2189            BspViewCell *bspVc = dynamic_cast<BspViewCell *>(vc);
2190
2191                        importance = (float)bspVc->mLeaves.size() /
2192                                (float)mViewCellsStats.maxLeaves;
2193                }
2194                break;
2195        case 3: // merge tree differene
2196                {
2197                        importance = (float)GetMaxTreeDiff(vc) /
2198                                (float)(mVspBspTree->GetStatistics().maxDepth * 2);
2199                }
2200                break;
2201        default:
2202                break;
2203        }
2204
2205        Material m;
2206        m.mDiffuseColor.b = 1.0f;
2207        m.mDiffuseColor.r = importance;
2208        m.mDiffuseColor.g = 1.0f - m.mDiffuseColor.r;
2209        //Debug << "importance: " << importance << endl;
2210        exporter->SetForcedMaterial(m);
2211}
2212
2213
2214void VspBspViewCellsManager::ExportVcGeometry(Exporter *exporter,
2215                                                                                          ViewCell *vc) const
2216{
2217#if 1
2218        BspNodeGeometry geom;
2219        mVspBspTree->
2220                ConstructGeometry(dynamic_cast<BspViewCell *>(vc), geom.mPolys);
2221        exporter->ExportPolygons(geom.mPolys);
2222#else
2223       
2224        Material m2;
2225        m2.mDiffuseColor.b = 0.3f + Random(0.7f);
2226        m2.mDiffuseColor.r = 0.0f;//0.3f + Random(0.7f);
2227        m2.mDiffuseColor.g = 0.3f + Random(0.7f);
2228        Material m;
2229        m.mDiffuseColor.b = 0.0f;
2230        m.mDiffuseColor.r = 1.0f;
2231        m.mDiffuseColor.g = 0.0f;
2232
2233        BspViewCell *bspVc = dynamic_cast<BspViewCell *>(vc);
2234        vector<BspLeaf *>::const_iterator it, it_end = bspVc->mLeaves.end();
2235
2236        for (it = bspVc->mLeaves.begin(); it != it_end; ++ it)
2237        {
2238                if ((*it)->Mailed())
2239                        exporter->SetForcedMaterial(m);
2240                else
2241                        exporter->SetForcedMaterial(m2);
2242                        //exporter->ResetForcedMaterial();
2243                BspNodeGeometry geom;
2244                mVspBspTree->ConstructGeometry(*it, geom);
2245                exporter->ExportPolygons(geom.mPolys);
2246        }
2247#endif
2248}
2249
2250
2251int VspBspViewCellsManager::GetMaxTreeDiff(ViewCell *vc) const
2252{
2253        BspViewCell *bspVc = dynamic_cast<BspViewCell *>(vc);
2254
2255        int maxDist = 0;
2256        // compute max height difference
2257        for (int i = 0; i < (int)bspVc->mLeaves.size(); ++ i)
2258                for (int j = 0; j < (int)bspVc->mLeaves.size(); ++ j)
2259        {
2260                BspLeaf *leaf = bspVc->mLeaves[i];
2261
2262                if (i != j)
2263                {
2264                        BspLeaf *leaf2 = bspVc->mLeaves[j];
2265                        int dist = mVspBspTree->TreeDistance(leaf, leaf2);
2266                        if (dist > maxDist)
2267                                maxDist = dist;
2268                }
2269        }
2270
2271        return maxDist;
2272}
Note: See TracBrowser for help on using the repository browser.