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

Revision 489, 53.2 KB checked in by mattausch, 19 years ago (diff)

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