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

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