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

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