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

#include "ViewCellsManager.h"
#include "RenderSimulator.h"
#include "Mesh.h"
#include "Triangle3.h"
#include "ViewCell.h"
#include "Environment.h"
#include "X3dParser.h"
#include "ViewCellBsp.h"
#include "KdTree.h"
#include "VspKdTree.h"
#include "Exporter.h"
#include "VspBspTree.h"


ViewCellsManager::ViewCellsManager():
mRenderSimulator(NULL),
mConstructionSamples(0),
mPostProcessSamples(0),
mVisualizationSamples(0),
mTotalAreaValid(false),
mTotalArea(0.0f)
{
        // post processing stuff
        environment->GetIntValue("ViewCells.PostProcessing.minPvsDif", mMinPvsDif);
        environment->GetIntValue("ViewCells.PostProcessing.minPvs", mMinPvs);
        environment->GetIntValue("ViewCells.PostProcessing.maxPvs", mMaxPvs);
}

ViewCellsManager::ViewCellsManager(int constructionSamples):
mConstructionSamples(constructionSamples),
mRenderSimulator(NULL),
mPostProcessSamples(0),
mVisualizationSamples(0)
{
        // post processing stuff
        environment->GetIntValue("ViewCells.PostProcessing.minPvsDif", mMinPvsDif);
        environment->GetIntValue("ViewCells.PostProcessing.minPvs", mMinPvs);
        environment->GetIntValue("ViewCells.PostProcessing.maxPvs", mMaxPvs);
}

ViewCellsManager::~ViewCellsManager()
{
        DEL_PTR(mRenderSimulator);

        CLEAR_CONTAINER(mViewCells);
}

bool ViewCellsManager::LoadViewCells(const string filename)
{
        X3dParser parser;
        
        environment->GetFloatValue("ViewCells.height", parser.mViewCellHeight);
        
        bool success = parser.ParseFile(filename, *this);
        Debug << (int)mViewCells.size() << " view cells loaded" << endl;

        return success;
}

void ViewCellsManager::ComputeSampleContributions(const VssRayContainer &rays)
{
        // view cells not yet constructed
        if (!ViewCellsConstructed())
                return;
  
        VssRayContainer::const_iterator it, it_end = rays.end();
        
        for (it = rays.begin(); it != it_end; ++ it) 
        {
                ComputeSampleContributions(*(*it));
        }
}

void ViewCellsManager::AddViewCell(ViewCell *viewCell)
{
        mViewCells.push_back(viewCell);
}

void ViewCellsManager::DeriveViewCells(const ObjectContainer &objects, 
                                                                           ViewCellContainer &viewCells, 
                                                                           const int maxViewCells) const
{
        // maximal max viewcells
        int limit = maxViewCells > 0 ? 
                Min((int)objects.size(), maxViewCells) : (int)objects.size();

        for (int i = 0; i < limit; ++ i)
        {
                Intersectable *object = objects[i];
                
                // extract the mesh instances
                if (object->Type() == Intersectable::MESH_INSTANCE)
                {
                        MeshInstance *inst = dynamic_cast<MeshInstance *>(object);

                        ViewCell *viewCell = GenerateViewCell(inst->GetMesh());
                        viewCells.push_back(viewCell);
                }
                //TODO: transformed meshes
        }
}

ViewCell *ViewCellsManager::ExtrudeViewCell(const Triangle3 &baseTri, 
                                                                                        const float height) const
{
        // one mesh per view cell
        Mesh *mesh = new Mesh();
        
        //-- construct prism

        // bottom 
        mesh->mFaces.push_back(new Face(2,1,0));
        // top
    mesh->mFaces.push_back(new Face(3,4,5));
        // sides
        mesh->mFaces.push_back(new Face(1, 4, 3, 0));
        mesh->mFaces.push_back(new Face(2, 5, 4, 1));
        mesh->mFaces.push_back(new Face(3, 5, 2, 0));

        //--- extrude new vertices for top of prism
        Vector3 triNorm = baseTri.GetNormal();

        Triangle3 topTri;       

        // add base vertices and calculate top vertices
        for (int i = 0; i < 3; ++ i)
                mesh->mVertices.push_back(baseTri.mVertices[i]);
        
        // add top vertices     
        for (int i = 0; i < 3; ++ i)
                mesh->mVertices.push_back(baseTri.mVertices[i] + height * triNorm);
        
        mesh->Preprocess();

        return GenerateViewCell(mesh);
}

ViewCell *ViewCellsManager::MergeViewCells(ViewCell &front, ViewCell &back) const
{
        // generate merged view cell
        ViewCell *vc = GenerateViewCell();

        // merge pvs
        vc->GetPvs().Merge(front.GetPvs(), back.GetPvs());

        //-- merge ray sets
        stable_sort(front.mPiercingRays.begin(), front.mPiercingRays.end());
        stable_sort(back.mPiercingRays.begin(), back.mPiercingRays.end());

        std::merge(front.mPiercingRays.begin(), front.mPiercingRays.end(),
                           back.mPiercingRays.begin(), back.mPiercingRays.end(), 
                           vc->mPiercingRays.begin());

        return vc;
}


ViewCell *ViewCellsManager::GenerateViewCell(Mesh *mesh) const
{
        return new ViewCell(mesh);
}


void ViewCellsManager::SetVisualizationSamples(const int visSamples)
{
        mVisualizationSamples = visSamples;
}

void ViewCellsManager::SetConstructionSamples(const int constructionSamples)
{
        mConstructionSamples = constructionSamples;
}

void ViewCellsManager::SetPostProcessSamples(const int postProcessSamples)
{
        mPostProcessSamples = postProcessSamples;
}

int ViewCellsManager::GetVisualizationSamples() const
{
        return mVisualizationSamples;
}

int ViewCellsManager::GetConstructionSamples() const
{
        return mConstructionSamples;
}

int ViewCellsManager::GetPostProcessSamples() const
{
        return mPostProcessSamples;
}

void
ViewCellsManager::GetPvsStatistics(PvsStatistics &stat)
{
  ViewCellContainer::const_iterator it = mViewCells.begin();
  stat.viewcells = 0;
  stat.minPvs = 100000000;
  stat.maxPvs = 0;
  stat.avgPvs = 0.0f;

  for (; it != mViewCells.end(); ++it) {
        ViewCell *viewcell = *it;
        int pvsSize = viewcell->GetPvs().GetSize();
        if ( pvsSize < stat.minPvs)
          stat.minPvs = pvsSize;
        if (pvsSize > stat.maxPvs)
          stat.maxPvs = pvsSize;
        stat.avgPvs += pvsSize;
        stat.viewcells++;
  }
  if (stat.viewcells)
        stat.avgPvs/=stat.viewcells;
}

void
ViewCellsManager::PrintPvsStatistics(ostream &s)
{
  s<<"############# Viewcell PVS STAT ##################\n";
  PvsStatistics pvsStat;
  GetPvsStatistics(pvsStat);
  s<<"#AVG_PVS\n"<<pvsStat.avgPvs<<endl;
  s<<"#MAX_PVS\n"<<pvsStat.maxPvs<<endl;
  s<<"#MIN_PVS\n"<<pvsStat.minPvs<<endl;
}

ViewCellContainer &ViewCellsManager::GetViewCells()
{
        return mViewCells;
}

void ViewCellsManager::ComputeSampleContributions(VssRay &ray)
{
        ViewCellContainer viewcells;
        
        CastLineSegment(ray.mOrigin,
                                        ray.mTermination,
                                        viewcells);
        
        ray.mPvsContribution = 0;
        ray.mRelativePvsContribution = 0.0f;
  
        ViewCellContainer::const_iterator it = viewcells.begin();
        
        for (; it != viewcells.end(); ++it) 
        {       
                ViewCell *viewcell = *it;
        
                // if ray not outside of view space
                float contribution;
                bool added = 
                        viewcell->GetPvs().AddSample(ray.mTerminationObject,
                                                                                 contribution);
                
                if (added)
                        ++ ray.mPvsContribution;
                
                ray.mRelativePvsContribution += contribution;
        }
}


void ViewCellsManager::GetRaySets(const VssRayContainer &sourceRays,
                                                                  VssRayContainer &constructionRays, 
                                                                  VssRayContainer &savedRays) const
{
        const int limit = min(mConstructionSamples, (int)sourceRays.size());

        VssRayContainer::const_iterator it, it_end = sourceRays.end();
        
        const float prop = (float)limit / ((float)sourceRays.size() + Limits::Small);

        for (it = sourceRays.begin(); it != it_end; ++ it)
        {
                if (Random(1.0f) < prop)
                        constructionRays.push_back(*it);
                else
                        savedRays.push_back(*it);
        }
}

float ViewCellsManager::GetVolume(ViewCell *viewCell) const
{
        return viewCell->GetVolume();
}



float ViewCellsManager::GetArea(ViewCell *viewCell) const
{
        return 0.0f;
}



float ViewCellsManager::GetTotalArea()
{
        // if already computed
        if (mTotalAreaValid)
                return mTotalArea;

        mTotalArea = 0;
        ViewCellContainer::const_iterator it, it_end = mViewCells.end();

        for (it = mViewCells.begin(); it != it_end; ++ it)
        mTotalArea += GetArea(*it);
        
        mTotalAreaValid = true;

        return mTotalArea;
}

void ViewCellsManager::PrintStatistics(ostream &s) const
{
        s << mViewCellsStats << endl;
}

/**********************************************************************/
/*                   BspViewCellsManager implementation               */
/**********************************************************************/

BspViewCellsManager::BspViewCellsManager(BspTree *bspTree, 
                                                                                 int constructionSamples):
ViewCellsManager(constructionSamples), 
mBspTree(bspTree)
{
}


bool BspViewCellsManager::ViewCellsConstructed() const
{
        return mBspTree->GetRoot() != NULL;
}

ViewCell *BspViewCellsManager::GenerateViewCell(Mesh *mesh) const
{
        return new BspViewCell(mesh);
}

int BspViewCellsManager::Construct(const ObjectContainer &objects, 
                                                                   const VssRayContainer &rays,
                                                                   AxisAlignedBox3 *sceneBbox)
{
        // if view cells were already constructed
        if (ViewCellsConstructed())
                return 0;

        int sampleContributions = 0;
        
        // construct view cells using the collected samples
        RayContainer constructionRays;
        VssRayContainer savedRays;

        const int limit = min(mConstructionSamples, (int)rays.size());

        VssRayContainer::const_iterator it, it_end = rays.end();

        const float prop = (float)limit / ((float)rays.size() + Limits::Small);

        for (it = rays.begin(); it != it_end; ++ it)
        {
                if (Random(1.0f) < prop)
                        constructionRays.push_back(new Ray(*(*it)));
                else
                        savedRays.push_back(*it);
        }

    if (mViewCells.empty()) 
        { 
                // no view cells loaded 
                mBspTree->Construct(objects, constructionRays);
                // collect final view cells
                mBspTree->CollectViewCells(mViewCells);
        } 
        else
        {
                mBspTree->Construct(mViewCells);
        }

        mBspTree->EvaluateViewCellsStats(mViewCellsStats);

        // destroy rays created only for construction
        CLEAR_CONTAINER(constructionRays);

        Debug << mBspTree->GetStatistics() << endl;
        
        // recast rest of the rays
        ComputeSampleContributions(savedRays);

        return sampleContributions;
}

float BspViewCellsManager::GetArea(ViewCell *viewCell) const
{
        PolygonContainer geom;

        // compute view cell area
        mBspTree->ConstructGeometry(dynamic_cast<BspViewCell *>(viewCell), geom);
        
        const float area = Polygon3::GetArea(geom);
        CLEAR_CONTAINER(geom);

        return area;
}


float BspViewCellsManager::GetProbability(ViewCell *viewCell)
{
        // compute view cell area as subsititute for probability
        return GetArea(viewCell) / mBspTree->GetBoundingBox().SurfaceArea();
        //return GetArea(viewCell) / GetTotalArea();
}

float BspViewCellsManager::GetRendercost(ViewCell *viewCell, float objRendercost) const
{
        return viewCell->GetPvs().GetSize() * objRendercost;
}


int BspViewCellsManager::CastLineSegment(const Vector3 &origin,
                                                                                 const Vector3 &termination,
                                                                                 ViewCellContainer &viewcells)
{
        return mBspTree->CastLineSegment(origin, termination, viewcells);
}


int BspViewCellsManager::PostProcess(const ObjectContainer &objects, 
                                                                         const VssRayContainer &rays)
{
        if (!ViewCellsConstructed())
        {
                Debug << "view cells not constructed" << endl;
                return 0;
        }

        //-- post processing of bsp view cells
    int vcSize = 0;
        int pvsSize = 0;

        Debug << "original view cell partition:\n" << mViewCellsStats << endl;
                
        if (1) // export view cells before merge
        {
                cout << "exporting initial view cells (=leaves) ... ";
                Exporter *exporter = Exporter::GetExporter("view_cells.x3d");
        
                if (exporter)
                {
                        exporter->SetWireframe();
                        exporter->ExportBspLeaves(*mBspTree, mViewCellsStats.maxPvs);
                        //exporter->ExportBspViewCellPartition(*mBspTree, 0);
                                
                        if (0)
                        {
                                Material m;//= RandomMaterial();
                                m.mDiffuseColor = RgbColor(0, 1, 0);
                                exporter->SetForcedMaterial(m);
                                exporter->SetWireframe();

                                exporter->ExportGeometry(objects);
                        }

                        delete exporter;
                }
                cout << "finished" << endl;

                //-- render simulation after merge
                cout << "\nevaluating bsp view cells render time after merge ... ";
  
                 mRenderSimulator->RenderScene();
                 SimulationStatistics ss;
                 mRenderSimulator->GetStatistics(ss);
         
                 cout << " finished" << endl;
                 cout << ss << endl;
                 Debug << ss << endl;

        }

        cout << "starting post processing using " << mPostProcessSamples << " samples ... ";

        long startTime = GetTime();

        // $$JB we do not have connectivity information from the ray in the moment
        // perhaps we could recast the rays or rember the cells traversed inside the
        // vssray (which would on other hand create some overhead)
        //-- merge or subdivide view cells
        int merged = 0;
#if 0

        RayContainer::const_iterator rit, rit_end = rays.end();
        vector<BspIntersection>::const_iterator iit;

        int limit = min((int)rays.size(), mPostProcessSamples);

        for (int i = 0; i < limit; ++ i)
        {  
                Ray *ray = rays[i];

                // traverse leaves stored in the rays and compare and merge consecutive
                // leaves (i.e., the neighbors in the tree)
                if (ray->bspIntersections.size() < 2)
                        continue;

                iit = ray->bspIntersections.begin();

                BspLeaf *previousLeaf = (*iit).mLeaf;
                ++ iit;
                
                for (; iit != ray->bspIntersections.end(); ++ iit)
                {
                        BspLeaf *leaf = (*iit).mLeaf;

                        if (ShouldMerge(leaf, previousLeaf))
                        {                       
                                MergeBspLeafViewCells(leaf, previousLeaf);

                                ++ merged;
                        }
                
                        previousLeaf = leaf;
                }
        }
#endif
        //-- stats and visualizations
        cout << "finished" << endl;
        cout << "merged " << merged << " view cells in "
                 << TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl;

        Debug << "Postprocessing: Merged " << merged << " view cells in "
                  << TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl;

        //-- recount pvs
        mViewCellsStats.Reset();
        mBspTree->EvaluateViewCellsStats(mViewCellsStats);

        return merged;
}

int BspViewCellsManager::GetType() const
{
        return BSP;
}


void BspViewCellsManager::Visualize(const ObjectContainer &objects,
                                                                        const VssRayContainer &sampleRays)
{
        if (!ViewCellsConstructed())
                return;
  
        //-- recount pvs
        ViewCellsStatistics vcStats;
        mBspTree->EvaluateViewCellsStats(vcStats);
  
        if (1) // export view cells
        {
                cout << "exporting view cells after merge ... ";
                Exporter *exporter = Exporter::GetExporter("merged_view_cells.x3d");
          
                if (exporter)
                {
                        exporter->ExportBspViewCellPartition(*mBspTree, vcStats.maxPvs);
                        //exporter->ExportBspViewCellPartition(*mBspTree, 0);
                        delete exporter;
                }
          
                cout << "finished" << endl;
        }       
  
        //-- visualization of the BSP splits
        bool exportSplits = false;
        environment->GetBoolValue("BspTree.Visualization.exportSplits", exportSplits);
  
        if (exportSplits)
        {
                cout << "exporting splits ... ";
                ExportSplits(objects, sampleRays);
                cout << "finished" << endl;
        }
  
        ExportBspPvs(objects, sampleRays);
}


inline bool vc_gt(ViewCell *a, ViewCell *b) 
{ 
        return a->GetPvs().GetSize() > b->GetPvs().GetSize();
}

void BspViewCellsManager::ExportSplits(const ObjectContainer &objects,
                                                                           const VssRayContainer &sampleRays)
{
        Exporter *exporter = Exporter::GetExporter("bsp_splits.x3d");

        if (exporter) 
        {       
                Material m; 
                m.mDiffuseColor = RgbColor(1, 0, 0);
                exporter->SetForcedMaterial(m);
                exporter->SetWireframe();
                exporter->ExportBspSplits(*mBspTree, true);

                // take forced material, else big scenes cannot be viewed
                m.mDiffuseColor = RgbColor(0, 1, 0);
                exporter->SetForcedMaterial(m);
                exporter->SetFilled();

                exporter->ResetForcedMaterial();
                
                bool exportRays = false;
                bool exportGeometry = false;

                environment->GetBoolValue("BspTree.Visualization.exportRays", exportRays);
                environment->GetBoolValue("BspTree.Visualization.exportGeometry", exportGeometry);

                // export rays
                if (exportRays)
                {
                        VssRayContainer outRays;
                  
                        int raysSize = min((int)sampleRays.size(), mVisualizationSamples);
                        for (int i = 0; i < raysSize; ++ i)
                        {
                                // only rays piercing geometry
                                outRays.push_back(sampleRays[i]);                       
                        }
                        
                        // export rays 
                        exporter->ExportRays(outRays, RgbColor(1, 1, 0));
                }
                
                if (exportGeometry)
                        exporter->ExportGeometry(objects);
                
                delete exporter;
        }
}

void BspViewCellsManager::ExportBspPvs(const ObjectContainer &objects,
                                                                           const VssRayContainer &sampleRays)
{
  const int leafOut = 10;
  
  ViewCell::NewMail();
  
  //-- some rays for output
  const int raysOut = min((int)sampleRays.size(), mVisualizationSamples);

  Debug << "Output view cells:" << endl;

  if (1)
  {
          //-- some random view cells and rays for output
          vector<BspLeaf *> bspLeaves;
          
          for (int i = 0; i < leafOut; ++ i)
                  bspLeaves.push_back(mBspTree->GetRandomLeaf());       

          for (int i = 0; i < bspLeaves.size(); ++ i)
          {
                  BspLeaf *leaf = bspLeaves[i];
                  RayContainer vcRays;
                  
                  cout << "creating output for view cell " << i << " ... ";
                  
                  // TODO matt
                  // check whether we can add the current ray to the output rays
                  /*for (int k = 0; k < raysOut; ++ k) 
                  {
                          Ray *ray = sampleRays[k];
                          
                          for (int j = 0; j < (int)ray->bspIntersections.size(); ++ j)
                          {
                                  BspLeaf *leaf2 = ray->bspIntersections[j].mLeaf;
                                  
                                  if (leaf->GetViewCell() == leaf2->GetViewCell()) 
                                  {
                                          vcRays.push_back(ray);
                                  }
                          }
                  }*/
                  
                  Intersectable::NewMail();
                  
                  BspViewCell *vc = dynamic_cast<BspViewCell *>(leaf->GetViewCell());
                  
                  //bspLeaves[j]->Mail();
                  char s[64]; sprintf(s, "bsp-pvs%04d.x3d", i);
                  
                  Exporter *exporter = Exporter::GetExporter(s);
                  exporter->SetFilled();

                  exporter->SetWireframe();
                  //exporter->SetFilled();
                  
                  Material m;//= RandomMaterial();
                  m.mDiffuseColor = RgbColor(1, 1, 0);
                  exporter->SetForcedMaterial(m);
                  
                  if (vc->GetMesh())
                          exporter->ExportViewCell(vc);
                  else
                  {
                          PolygonContainer vcGeom;
                          // export view cell geometry
                          mBspTree->ConstructGeometry(vc, vcGeom);
                          exporter->ExportPolygons(vcGeom);
                          CLEAR_CONTAINER(vcGeom);
                  }               

                  Debug << i << ": pvs size=" << (int)vc->GetPvs().GetSize() 
                                << ", piercing rays=" << (int)vcRays.size() << endl;
                  
                  // export rays piercing this view cell
                  //exporter->ExportRays(vcRays, 1000, RgbColor(0, 1, 0));      
                  
                  m.mDiffuseColor = RgbColor(1, 0, 0);
                  exporter->SetForcedMaterial(m);
                  
                  // exporter->SetWireframe();
                  exporter->SetFilled();
                  
                  ObjectPvsMap::iterator it, it_end = vc->GetPvs().mEntries.end();
                  // output PVS of view cell
                  for (it = vc->GetPvs().mEntries.begin(); it !=  it_end; ++ it) 
                  {
                          Intersectable *intersect = (*it).first;
                          if (!intersect->Mailed())
                          {
                                  exporter->ExportIntersectable(intersect);
                                  intersect->Mail();
                          }                     
                  }
                  
                  DEL_PTR(exporter);
                  cout << "finished" << endl;
          }
  }
  else
  {
          ViewCellContainer viewCells;
          RayContainer vcRays;
          
          mBspTree->CollectViewCells(viewCells);
          stable_sort(viewCells.begin(), viewCells.end(), vc_gt);
          
          const int limit = min(leafOut, (int)viewCells.size()); 
          
          for (int i = 0; i < limit; ++ i)
          {
                  cout << "creating output for view cell " << i << " ... ";
                        
                  Intersectable::NewMail();
                  BspViewCell *vc = dynamic_cast<BspViewCell *>(viewCells[i]);

                  cout << "creating output for view cell " << i << " ... ";

                  // TODO matt
                  // check whether we can add the current ray to the output rays
                  /*for (int k = 0; k < raysOut; ++ k) 
                  {
                          Ray *ray = sampleRays[k];

                          for (int j = 0; j < (int)ray->bspIntersections.size(); ++ j)
                          {
                                  BspLeaf *leaf = ray->bspIntersections[j].mLeaf;

                                  if (vc == leaf->GetViewCell()) 
                                          vcRays.push_back(ray);
                          }
                  }*/

                  //bspLeaves[j]->Mail();
                  char s[64]; sprintf(s, "bsp-pvs%04d.x3d", i);

                  Exporter *exporter = Exporter::GetExporter(s);        
                  exporter->SetWireframe();

                  Material m;//= RandomMaterial();
                  m.mDiffuseColor = RgbColor(0, 1, 0);
                  exporter->SetForcedMaterial(m);

                  if (vc->GetMesh())
                          exporter->ExportViewCell(vc);
                  else
                  {
                          PolygonContainer cell;
                          // export view cell
                          mBspTree->ConstructGeometry(vc, cell);
                          exporter->ExportPolygons(cell);
                          CLEAR_CONTAINER(cell);
                  }
                  Debug << i << ": pvs size=" << (int)vc->GetPvs().GetSize() 
                            << ", piercing rays=" << (int)vcRays.size() << endl;

                  // export rays piercing this view cell
                  exporter->ExportRays(vcRays, 1000, RgbColor(0, 1, 0));
        
                  m.mDiffuseColor = RgbColor(1, 0, 0);
                  exporter->SetForcedMaterial(m);

                  ObjectPvsMap::const_iterator it, it_end = vc->GetPvs().mEntries.end();

                  // output PVS of view cell
                  for (it = vc->GetPvs().mEntries.begin(); it != it_end; ++ it) 
                  {
                          Intersectable *intersect = (*it).first;

                          if (!intersect->Mailed())
                          {
                                  Material m = RandomMaterial();
                                  exporter->SetForcedMaterial(m);

                                  exporter->ExportIntersectable(intersect);
                        
                                  intersect->Mail();
                          }                     
                  }
                                
                  DEL_PTR(exporter);
                  cout << "finished" << endl;
          }
  }
}


bool BspViewCellsManager::MergeBspLeafViewCells(BspLeaf *front, BspLeaf *back) const
{
        BspViewCell *viewCell = 
                dynamic_cast<BspViewCell *>(MergeViewCells(*front->GetViewCell(), *back->GetViewCell()));
        
        if (!viewCell)
                return false;

        //-- change pointer to view cells of all leaves associated with the previous view cells
        BspViewCell *fVc = front->GetViewCell();
        BspViewCell *bVc = back->GetViewCell();

        vector<BspLeaf *> fLeaves = fVc->mLeaves;
        vector<BspLeaf *> bLeaves = bVc->mLeaves;

        vector<BspLeaf *>::const_iterator it;
        
        for (it = fLeaves.begin(); it != fLeaves.end(); ++ it)
        {
                (*it)->SetViewCell(viewCell);
                viewCell->mLeaves.push_back(*it);
        }
        for (it = bLeaves.begin(); it != bLeaves.end(); ++ it)
        {
                (*it)->SetViewCell(viewCell);
                viewCell->mLeaves.push_back(*it);
        }
        
        DEL_PTR(fVc);
        DEL_PTR(bVc);

        return true;
}

bool BspViewCellsManager::ShouldMerge(BspLeaf *front, BspLeaf *back) const
{
        ViewCell *fvc = front->GetViewCell();
        ViewCell *bvc = back->GetViewCell();

        if ((fvc == mBspTree->GetRootCell()) || (bvc == mBspTree->GetRootCell()) || (fvc == bvc))
                return false;

        int fdiff = fvc->GetPvs().Diff(bvc->GetPvs());

        if (fvc->GetPvs().GetSize() + fdiff < mMaxPvs)
        {
                if ((fvc->GetPvs().GetSize() < mMinPvs) ||      
                        (bvc->GetPvs().GetSize() < mMinPvs) ||
                        ((fdiff < mMinPvsDif) && (bvc->GetPvs().Diff(fvc->GetPvs()) < mMinPvsDif)))
                {
                        return true;
                }
        }
        
        return false;
}



/**********************************************************************/
/*                   KdViewCellsManager implementation               */
/**********************************************************************/

KdViewCellsManager::KdViewCellsManager(KdTree *kdTree):
ViewCellsManager(), mKdTree(kdTree), mKdPvsDepth(100)
{
}

float KdViewCellsManager::GetProbability(ViewCell *viewCell)
{
        // compute view cell area as subsititute for probability
        AxisAlignedBox3 box = mKdTree->GetBox(mKdTree->GetRoot());

        return GetArea(viewCell) / box.SurfaceArea();
        //return GetArea(viewCell) / GetTotalArea();
}


float KdViewCellsManager::GetRendercost(ViewCell *viewCell, float objRendercost) const
{
        return viewCell->GetPvs().GetSize() * objRendercost;
}

int KdViewCellsManager::Construct(const ObjectContainer &objects, 
                                                                  const VssRayContainer &rays,
                                                                  AxisAlignedBox3 *sceneBbox)
{
        // if view cells already constructed
        if (ViewCellsConstructed())
                return 0;

        mKdTree->Construct();

        // create the view cells
        mKdTree->CreateAndCollectViewCells(mViewCells);
        //mKdTree->EvaluateViewCellsStats(mViewCellsStats);

        return 0;
}

bool KdViewCellsManager::ViewCellsConstructed() const
{
        return mKdTree->GetRoot() != NULL;
}

int KdViewCellsManager::PostProcess(const ObjectContainer &objects, 
                                                                        const VssRayContainer &rays)
{
        return 0;
}

void KdViewCellsManager::Visualize(const ObjectContainer &objects,
                                                                   const VssRayContainer &sampleRays)
{
        if (!ViewCellsConstructed())
                return;

        // using view cells instead of the kd PVS of objects
        const bool useViewCells = true;
        bool exportRays = false;

        int limit = min(mVisualizationSamples, (int)sampleRays.size());
        const int pvsOut = min((int)objects.size(), 10);
        VssRayContainer *rays = new VssRayContainer[pvsOut];

  //$$ JB
//#if 0

        if (useViewCells)
        {
                const int leafOut = 10;
                
                ViewCell::NewMail();
  
                //-- some rays for output
                const int raysOut = min((int)sampleRays.size(), mVisualizationSamples);
                Debug << "visualization using " << raysOut << " samples" << endl;

                //-- some random view cells and rays for output
                vector<KdLeaf *> kdLeaves;
                
                for (int i = 0; i < leafOut; ++ i)
                        kdLeaves.push_back(dynamic_cast<KdLeaf *>(mKdTree->GetRandomLeaf()));
                
                for (int i = 0; i < kdLeaves.size(); ++ i)
                {
                        KdLeaf *leaf = kdLeaves[i];
                        RayContainer vcRays;
                        
                        cout << "creating output for view cell " << i << " ... ";
                        
                        // check whether we can add the current ray to the output rays
                        /*for (int k = 0; k < raysOut; ++ k) 
                        {
                                Ray *ray = sampleRays[k];
                                
                                for (int j = 0; j < (int)ray->bspIntersections.size(); ++ j)
                                {
                                        BspLeaf *leaf2 = ray->bspIntersections[j].mLeaf;
                                        
                                        if (leaf->GetViewCell() == leaf2->GetViewCell()) 
                                        {
                                                vcRays.push_back(ray);
                                        }
                                }
                        }*/
                        
                        Intersectable::NewMail();
                        
                        ViewCell *vc = leaf->mViewCell;
                        
                        //bspLeaves[j]->Mail();
                        char s[64]; sprintf(s, "kd-pvs%04d.x3d", i);
                        
                        Exporter *exporter = Exporter::GetExporter(s);
                        exporter->SetFilled();

                        exporter->SetWireframe();
                        //exporter->SetFilled();
                        
                        Material m;//= RandomMaterial();
                        m.mDiffuseColor = RgbColor(1, 1, 0);
                        exporter->SetForcedMaterial(m);
                        
                        AxisAlignedBox3 box = mKdTree->GetBox(leaf);
                        exporter->ExportBox(box);

                        Debug << i << ": pvs size=" << (int)vc->GetPvs().GetSize() 
                                << ", piercing rays=" << (int)vcRays.size() << endl;
                        
                        // export rays piercing this view cell
                        exporter->ExportRays(vcRays, 1000, RgbColor(0, 1, 0));  
                        
                        m.mDiffuseColor = RgbColor(1, 0, 0);
                        exporter->SetForcedMaterial(m);
                        
                        // exporter->SetWireframe();
                        exporter->SetFilled();
                        
                        ObjectPvsMap::iterator it, it_end = vc->GetPvs().mEntries.end();
                        // output PVS of view cell
                        for (it = vc->GetPvs().mEntries.begin(); it !=  it_end; ++ it) 
                        {
                                Intersectable *intersect = (*it).first;
                                if (!intersect->Mailed())
                                {
                                        exporter->ExportIntersectable(intersect);
                                        intersect->Mail();
                                }                       
                        }
                        
                        DEL_PTR(exporter);
                        cout << "finished" << endl;
                }

                DEL_PTR(rays);
        }
        else // using kd PVS of objects
        {
                for (int i = 0; i < limit; ++ i)
                {
                        VssRay *ray = sampleRays[i];
                
                        // check whether we can add this to the rays
                        for (int j = 0; j < pvsOut; j++) 
                        {
                                if (objects[j] == ray->mTerminationObject)
                                {
                                        rays[j].push_back(ray);
                                }
                        }
                }

                if (exportRays) 
                {
                        Exporter *exporter = NULL;
                        exporter = Exporter::GetExporter("sample-rays.x3d");
                        exporter->SetWireframe();
                        exporter->ExportKdTree(*mKdTree);
                
                        for (i=0; i < pvsOut; i++) 
                                exporter->ExportRays(rays[i], RgbColor(1, 0, 0));

                        exporter->SetFilled();
                
                        delete exporter;
                }

                for (int k=0; k < pvsOut; k++) 
                {
                        Intersectable *object = objects[k];
                        char s[64];     
                        sprintf(s, "sample-pvs%04d.x3d", k);

                        Exporter *exporter = Exporter::GetExporter(s);
                        exporter->SetWireframe();
                
                        KdPvsMap::iterator i = object->mKdPvs.mEntries.begin();
                        Intersectable::NewMail();
                        
                        // avoid adding the object to the list
                        object->Mail();
                        ObjectContainer visibleObjects;
            
                        for (; i != object->mKdPvs.mEntries.end(); i++) 
                        {
                                KdNode *node = (*i).first;
                                exporter->ExportBox(mKdTree->GetBox(node));
                
                                mKdTree->CollectObjects(node, visibleObjects);
                        }
                
                        exporter->ExportRays(rays[k],  RgbColor(0, 1, 0));
                        exporter->SetFilled();
                        
                        for (int j = 0; j < visibleObjects.size(); j++)
                                exporter->ExportIntersectable(visibleObjects[j]);
                        
                        Material m;
                        m.mDiffuseColor = RgbColor(1, 0, 0);
                        exporter->SetForcedMaterial(m);
                        exporter->ExportIntersectable(object);
                
                        delete exporter;
                }
        }               
}


int KdViewCellsManager::GetType() const
{
        return ViewCellsManager::KD;
}



KdNode *KdViewCellsManager::GetNodeForPvs(KdLeaf *leaf)
{
        KdNode *node = leaf;

        while (node->mParent && node->mDepth > mKdPvsDepth)
                node = node->mParent;
        return node;
}

int KdViewCellsManager::CastLineSegment(const Vector3 &origin,
                                                                                const Vector3 &termination,
                                                                                ViewCellContainer &viewcells)
{
        return mKdTree->CastLineSegment(origin, termination, viewcells);
}



/**********************************************************************/
/*                   VspKdViewCellsManager implementation             */
/**********************************************************************/

VspKdViewCellsManager::VspKdViewCellsManager(VspKdTree *vspKdTree, 
                                                                                         int constructionSamples):
ViewCellsManager(constructionSamples), 
mVspKdTree(vspKdTree)
{
        mVspKdTree->SetViewCellsManager(this);
}

float VspKdViewCellsManager::GetProbability(ViewCell *viewCell)
{
        // volume or area substitutes for view point probability
        AxisAlignedBox3 box = mVspKdTree->GetBBox(mVspKdTree->GetRoot());

        return GetArea(viewCell) / box.SurfaceArea();
        //return GetArea(viewCell) / GetTotalArea();
}


float VspKdViewCellsManager::GetRendercost(ViewCell *viewCell, float objRendercost) const
{
        return viewCell->GetPvs().GetSize() * objRendercost;
}


int VspKdViewCellsManager::Construct(const ObjectContainer &objects, 
                                                                         const VssRayContainer &rays,
                                                                         AxisAlignedBox3 *sceneBbox)
{
        // if view cells already constructed
        if (ViewCellsConstructed())
                return 0;
                
        VssRayContainer constructionRays;
        VssRayContainer savedRays;

        GetRaySets(rays, constructionRays, savedRays);
        
        Debug << "constructing vsp kd tree using " 
                  << (int)constructionRays.size() << " samples" << endl;

        mVspKdTree->Construct(constructionRays, sceneBbox);
        mVspKdTree->CollectViewCells(mViewCells);
        //mVspBspTree->EvaluateViewCellsStats(mViewCellsStats);

        Debug << mVspKdTree->GetStatistics() << endl;

        // finally merge kd leaf building blocks to view cells
        const int merged = mVspKdTree->MergeLeaves();

        // recast rest of rays
        ComputeSampleContributions(savedRays);

        return merged;
}

bool VspKdViewCellsManager::ViewCellsConstructed() const
{
        return mVspKdTree->GetRoot() != NULL;
}


ViewCell *VspKdViewCellsManager::GenerateViewCell(Mesh *mesh) const
{
        return new VspKdViewCell(mesh);
}

int VspKdViewCellsManager::PostProcess(const ObjectContainer &objects, 
                                                                           const VssRayContainer &rays)
{
        if (!ViewCellsConstructed())
                return 0;

        return 0;
}

void VspKdViewCellsManager::Visualize(const ObjectContainer &objects,
                                                                          const VssRayContainer &sampleRays)
{
        bool exportRays = false;
        bool exportGeometry = false;

        environment->GetBoolValue("VspKdTree.Visualization.exportRays", exportRays);
        environment->GetBoolValue("VspKdTree.Visualization.exportGeometry", exportGeometry);

        if (!ViewCellsConstructed())
                return;

        //-- export tree leaves
        if (1)
        {
                Exporter *exporter = Exporter::GetExporter("vspkdtree.x3d"); 
                //exporter->SetWireframe();
                //exporter->ExportVspKdTree(*mVspKdTree, mVspKdTree->GetStatistics().maxPvsSize);
                exporter->ExportVspKdTree(*mVspKdTree);

                if (1) 
                        exporter->ExportGeometry(objects);

                if (exportRays) 
                  {
                        int raysSize = 2000;
                        float prob = raysSize / (float)sampleRays.size();
                
                        exporter->SetWireframe();
                        
                        VssRayContainer rays;
                
                        for (int i = 0; i < sampleRays.size(); ++ i)
                        {
                                if (RandomValue(0,1) < prob)
                                        rays.push_back(sampleRays[i]);
                        }

                        exporter->ExportRays(rays, RgbColor(1, 0, 0));
                }

                delete exporter;
        }

        //-- export single leaves
        if (1)
        {
                vector<VspKdLeaf *> leafContainer;
                mVspKdTree->CollectLeaves(leafContainer);

                for (int i = 0; i < 10; ++ i)
                {
                        char s[64];
                        sprintf(s, "vsp_leaves%04d.x3d", i);
                        Exporter *exporter = Exporter::GetExporter(s);

                        // export geometry
                        VspKdLeaf *leaf = leafContainer[(int)RandomValue(0.0, (Real)((int)leafContainer.size() - 1))]; 
                        AxisAlignedBox3 box = mVspKdTree->GetBBox(leaf);

                        Material m;
                        m.mDiffuseColor = RgbColor(0, 1, 1);
                        exporter->SetForcedMaterial(m);
                        exporter->SetWireframe();
                        exporter->ExportBox(box);

                        //-- export stored rays
                        VssRayContainer vssRays;
                        leaf->GetRays(vssRays);

                        VssRayContainer rays;
                        VssRayContainer::const_iterator it, it_end = vssRays.end();

                        for (it = vssRays.begin(); it != it_end; ++ it)
                                rays.push_back(*it);
                        
                        exporter->ExportRays(rays, RgbColor(1, 0, 0));

                        //-- export stored PVS
                        ObjectContainer pvsObj;
                        leaf->ExtractPvs(pvsObj);
                                
                        exporter->ExportGeometry(pvsObj);

                        delete exporter;
                }                       
        }

        //-- export final view cells
        Exporter *exporter = Exporter::GetExporter("vspkdtree_merged.x3d"); 
        exporter->SetWireframe();
        //exporter->ExportVspKdTreeViewCells(*mVspKdTree, vcStats.maxPvs);
        exporter->ExportVspKdTreeViewCells(*mVspKdTree);

        if (1) 
        {
                exporter->SetFilled();
                exporter->ExportGeometry(objects);
        }

        if (exportRays) 
        {
                int raysSize = 2000;
                float prob = raysSize / (float)sampleRays.size();
                
                exporter->SetWireframe();
                        
                VssRayContainer rays;
                
                for (int i = 0; i < sampleRays.size(); ++ i)
                {
                  if (RandomValue(0,1) < prob)
                        rays.push_back(sampleRays[i]);
                }
                exporter->ExportRays(rays, RgbColor(1, 0, 0));
        }

        delete exporter;
}

int VspKdViewCellsManager::GetType() const
{
        return VSP_KD;
}


int VspKdViewCellsManager::CastLineSegment(const Vector3 &origin,
                                                                                   const Vector3 &termination,
                                                                                   ViewCellContainer &viewcells)
{
        return mVspKdTree->CastLineSegment(origin, termination, viewcells);
}

/**********************************************************************/
/*                 VspBspViewCellsManager implementation              */
/**********************************************************************/

VspBspViewCellsManager::VspBspViewCellsManager(VspBspTree *vspBspTree, 
                                                                                           int constructionSamples):
ViewCellsManager(constructionSamples), 
mVspBspTree(vspBspTree)
{
}

VspBspViewCellsManager::~VspBspViewCellsManager()
{
        CLEAR_CONTAINER(mBspRays);
}

float VspBspViewCellsManager::GetProbability(ViewCell *viewCell)
{
        return GetArea(viewCell) / mVspBspTree->GetBoundingBox().SurfaceArea();
        //return GetArea(viewCell) / GetTotalArea();
}

float VspBspViewCellsManager::GetArea(ViewCell *viewCell) const
{
        PolygonContainer geom;

        // compute view cell area
        mVspBspTree->ConstructGeometry(dynamic_cast<BspViewCell *>(viewCell), geom);
        
        const float area = Polygon3::GetArea(geom);
        CLEAR_CONTAINER(geom);

        return area;
}

float VspBspViewCellsManager::GetRendercost(ViewCell *viewCell, float objRendercost) const
{
        return viewCell->GetPvs().GetSize() * objRendercost;
}


bool VspBspViewCellsManager::ViewCellsConstructed() const
{
        return mVspBspTree->GetRoot() != NULL;
}


ViewCell *VspBspViewCellsManager::GenerateViewCell(Mesh *mesh) const
{
        return new BspViewCell(mesh);
}

int VspBspViewCellsManager::Construct(const ObjectContainer &objects, 
                                                                          const VssRayContainer &rays,
                                                                          AxisAlignedBox3 *sceneBbox)
{
        // if view cells were already constructed
        if (ViewCellsConstructed())
                return 0;

        int sampleContributions = 0;
        
        VssRayContainer constructionRays;
        VssRayContainer savedRays;

        GetRaySets(rays, constructionRays, savedRays);
        
        mVspBspTree->Construct(constructionRays);
        mVspBspTree->CollectViewCells(mViewCells);
        mVspBspTree->EvaluateViewCellsStats(mViewCellsStats);
        
        Debug << mVspBspTree->GetStatistics() << endl;
        
        // recast rest of rays
        ComputeSampleContributions(savedRays);

        return sampleContributions;
}


void VspBspViewCellsManager::ConstructBspRays(const VssRayContainer &rays,
                                                                                          const int numSamples)
{
        VssRayContainer::const_iterator it, it_end = rays.end();

        for (it = rays.begin(); it != rays.end() && mBspRays.size() < numSamples; ++ it)
        {
                VssRay *vssRay = *it;
                BspRay *ray = new BspRay(vssRay);

                ViewCellContainer viewCells;

                CastLineSegment(vssRay->mTermination, vssRay->mOrigin, viewCells);

                ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
                
                for (vit = viewCells.begin(); vit != vit_end; ++ vit)
                {
                        BspViewCell *vc = dynamic_cast<BspViewCell *>(*vit);
                        ray->intersections.push_back(BspIntersection(0, vc->mLeaves[0]));
                }

                mBspRays.push_back(ray);
        }
}


int VspBspViewCellsManager::PostProcess(const ObjectContainer &objects, 
                                                                                const VssRayContainer &rays)
{
        if (mBspRays.empty())
                ConstructBspRays(rays, mConstructionSamples);
        
        if (!ViewCellsConstructed())
        {
                Debug << "view cells not constructed" << endl;
                return 0;
        }

        //-- post processing of bsp view cells
    int vcSize = 0;
        int pvsSize = 0;

        Debug << "original view cell partition:\n" << mViewCellsStats << endl;
                
        if (1) // export view cells
        {
                cout << "exporting initial view cells (=leaves) ... ";
                Exporter *exporter = Exporter::GetExporter("view_cells.x3d");
        
                if (exporter)
                {
                        //exporter->SetWireframe();
                        exporter->SetFilled();
                        exporter->ExportBspViewCellPartition(*mVspBspTree, mViewCellsStats.maxPvs);
                                
                        if (0)
                        {
                                Material m;
                                m.mDiffuseColor = RgbColor(0, 1, 0);
                                exporter->SetForcedMaterial(m);
                                exporter->SetWireframe();

                                exporter->ExportGeometry(objects);
                        }

                        delete exporter;
                }
                cout << "finished" << endl;
        }

        cout << "starting post processing using " << mPostProcessSamples << " samples ... ";
                
        long startTime = GetTime();


        // $$JB we do not have connectivity information from the ray in the moment
        // perhaps we could recast the rays or rember the cells traversed inside the
        // vssray (which would on other hand create some overhead)
        //-- merge or subdivide view cells
        int merged = 0;

        vector<BspIntersection>::const_iterator iit;

        for (int i = 0; i < (int)mBspRays.size(); ++ i)
        {  
                BspRay *ray = mBspRays[i];
          
                // traverse leaves stored in the rays and compare and merge consecutive
                // leaves (i.e., the neighbors in the tree)
                if (ray->intersections.size() < 2)
                        continue;
          
                iit = ray->intersections.begin();

                BspLeaf *previousLeaf = (*iit).mLeaf;
                ++ iit;
                
                for (; iit != ray->intersections.end(); ++ iit)
                {
                        BspLeaf *leaf = (*iit).mLeaf;

                        if (ShouldMerge(leaf, previousLeaf))
                        {                       
                                MergeVspBspLeafViewCells(leaf, previousLeaf);

                                ++ merged;
                        }
                
                        previousLeaf = leaf;
                }
        }

        //-- stats and visualizations
        cout << "finished" << endl;
        cout << "merged " << merged << " view cells in "
                 << TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl;

        Debug << "Postprocessing: Merged " << merged << " view cells in "
                  << TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl << endl;
        
        // reset view cells and stats
        mViewCells.clear();
        mVspBspTree->CollectViewCells(mViewCells);
        mViewCellsStats.Reset();
        mVspBspTree->EvaluateViewCellsStats(mViewCellsStats);

        return merged;
}

int VspBspViewCellsManager::GetType() const
{
        return VSP_BSP;
}


void VspBspViewCellsManager::Visualize(const ObjectContainer &objects,
                                                                           const VssRayContainer &sampleRays)
{
        if (!ViewCellsConstructed())
                return;

        if (mBspRays.empty())
                ConstructBspRays(sampleRays, mConstructionSamples);
        
        if (1) // export view cells
        {
                cout << "exporting view cells after merge ... ";
                Exporter *exporter = Exporter::GetExporter("merged_view_cells.x3d");

                if (exporter)
                {
                        exporter->ExportBspViewCellPartition(*mVspBspTree, mViewCellsStats.maxPvs);
                        delete exporter;
                }
                
                cout << "finished" << endl;
        }       

        //-- visualization of the BSP splits
        bool exportSplits = false;
        environment->GetBoolValue("BspTree.Visualization.exportSplits", exportSplits);
        
        if (exportSplits)
        {
                cout << "exporting splits ... ";
                ExportSplits(objects);
                cout << "finished" << endl;
        }

        ExportBspPvs(objects);
}


void VspBspViewCellsManager::ExportSplits(const ObjectContainer &objects)
{
        Exporter *exporter = Exporter::GetExporter("bsp_splits.x3d");

        if (exporter) 
        {       
                Material m; 
                m.mDiffuseColor = RgbColor(1, 0, 0);
                exporter->SetForcedMaterial(m);
                exporter->SetWireframe();
                
                exporter->ExportBspSplits(*mVspBspTree, true);

                // take forced material, else big scenes cannot be viewed
                m.mDiffuseColor = RgbColor(0, 1, 0);
                exporter->SetForcedMaterial(m);
                exporter->SetFilled();

                exporter->ResetForcedMaterial();
                
                // export rays
                if (0)
                {
                        VssRayContainer outRays;
                
                        int raysSize = min((int)mBspRays.size(), mVisualizationSamples);

                        for (int i = 0; i < raysSize; ++ i)
                                // only rays piercing geometry
                                outRays.push_back(mBspRays[i]->vssRay);
                                                
                        // export rays 
                        exporter->ExportRays(outRays, RgbColor(1, 1, 0));
                }

                if (0)
                        exporter->ExportGeometry(objects);

                delete exporter;
        }
}

void VspBspViewCellsManager::ExportBspPvs(const ObjectContainer &objects)
{
        bool exportRays = false;
        bool exportGeometry = false;

        environment->GetBoolValue("VspBspTree.Visualization.exportRays", exportRays);
        environment->GetBoolValue("VspBspTree.Visualization.exportGeometry", exportGeometry);

        const int leafOut = 10;
        
        ViewCell::NewMail();

        //-- some rays for output
        const int raysOut = min((int)mBspRays.size(), mVisualizationSamples);
        cout << "visualization using " << mVisualizationSamples << " samples" << endl;
        Debug << "\nOutput view cells: " << endl;

        if (1)
        {
                //-- some random view cells and rays for output
                vector<BspLeaf *> vspBspLeaves;

                for (int i = 0; i < leafOut; ++ i)
                        vspBspLeaves.push_back(mVspBspTree->GetRandomLeaf());   
                
                for (int i = 0; i < (int)vspBspLeaves.size(); ++ i)
                {
                        VssRayContainer vcRays;
                        cout << "creating output for view cell " << i << " ... ";

                        // check whether we can add the current ray to the output rays
                        for (int k = 0; k < raysOut; ++ k) 
                        {
                                BspRay *ray = mBspRays[k];

                                for     (int j = 0; j < (int)ray->intersections.size(); ++ j)
                                {
                                        BspLeaf *leaf = ray->intersections[j].mLeaf;

                                        if (vspBspLeaves[i]->GetViewCell() == leaf->GetViewCell()) 
                                        {
                                                vcRays.push_back(ray->vssRay);
                                        }
                                }
                        }

                        Intersectable::NewMail();

                        BspViewCell *vc = dynamic_cast<BspViewCell *>
                                (vspBspLeaves[i]->GetViewCell());

                        //bspLeaves[j]->Mail();
                        char s[64]; sprintf(s, "bsp-pvs%04d.x3d", i);

                        Exporter *exporter = Exporter::GetExporter(s);
                        exporter->SetFilled();

                        ObjectPvsMap::iterator it = vc->GetPvs().mEntries.begin();

                        exporter->SetWireframe();
                        //exporter->SetFilled();

                        Material m;//= RandomMaterial();
                        m.mDiffuseColor = RgbColor(0, 1, 0);
                        exporter->SetForcedMaterial(m);

                        if (vc->GetMesh())
                                exporter->ExportViewCell(vc);
                        else
                        {
                                PolygonContainer vcGeom;

                                // export view cell geometry
                                mVspBspTree->ConstructGeometry(vc, vcGeom);
                                exporter->ExportPolygons(vcGeom);
                                CLEAR_CONTAINER(vcGeom);
                        }

                        Debug << i << ": pvs size=" << (int)vc->GetPvs().GetSize() 
                                        << ", piercing rays=" << (int)vcRays.size() << endl;

                        // export rays piercing this view cell
                        if (exportRays)
                        {
                                //exporter->ExportRays(vcRays, RgbColor(1, 0, 0));
                                exporter->ExportRays(vspBspLeaves[i]->mVssRays, RgbColor(1, 1, 1));
                        }

                        m.mDiffuseColor = RgbColor(0, 1, 1);
                        exporter->SetForcedMaterial(m);

                        //exporter->SetWireframe();
                        exporter->SetFilled();

                        // output PVS of view cell
                        for (; it != vc->GetPvs().mEntries.end(); ++ it) 
                        {
                                Intersectable *intersect = (*it).first;
                                if (!intersect->Mailed())
                                {
                                        exporter->ExportIntersectable(intersect);
                                        intersect->Mail();
                                }                       
                        }
                        Debug << "here1 exportgeom: " << exportGeometry << endl;
                        // output rest of the objects
                        if (exportGeometry)
                        {
                                Material m;//= RandomMaterial();
                                m.mDiffuseColor = RgbColor(0, 0, 1);
                                exporter->SetForcedMaterial(m);

                                for (int j = 0; j < objects.size(); ++ j)
                                        if (!objects[j]->Mailed())
                                        {
                                                exporter->SetForcedMaterial(m);
                                                exporter->ExportIntersectable(objects[j]);
                                                objects[j]->Mail();
                                        }
                        }
                        DEL_PTR(exporter);
                        cout << "finished" << endl;
                }
        }
        else
        {
                ViewCellContainer viewCells;

                mVspBspTree->CollectViewCells(viewCells);
                stable_sort(viewCells.begin(), viewCells.end(), vc_gt);

                int limit = min(leafOut, (int)viewCells.size()); 
                
                for (int i = 0; i < limit; ++ i)
                {
                        cout << "creating output for view cell " << i << " ... ";
                        VssRayContainer vcRays;
            Intersectable::NewMail();
                        BspViewCell *vc = dynamic_cast<BspViewCell *>(viewCells[i]);

                        cout << "creating output for view cell " << i << " ... ";

                        // check whether we can add the current ray to the output rays
                        for (int k = 0; k < raysOut; ++ k) 
                        {
                                BspRay *ray = mBspRays[k];

                                for     (int j = 0; j < (int)ray->intersections.size(); ++ j)
                                {
                                        BspLeaf *leaf = ray->intersections[j].mLeaf;

                                        if (vc == leaf->GetViewCell()) 
                                        {
                                                vcRays.push_back(ray->vssRay);
                                        }
                                }
                        }

                        //bspLeaves[j]->Mail();
                        char s[64]; sprintf(s, "bsp-pvs%04d.x3d", i);

                        Exporter *exporter = Exporter::GetExporter(s);
                        
                        exporter->SetWireframe();

                        Material m;//= RandomMaterial();
                        m.mDiffuseColor = RgbColor(0, 1, 0);
                        exporter->SetForcedMaterial(m);

                        if (vc->GetMesh())
                                exporter->ExportViewCell(vc);
                        else
                        {
                                PolygonContainer vcGeom;
                                // export view cell
                                mVspBspTree->ConstructGeometry(vc, vcGeom);
                                exporter->ExportPolygons(vcGeom);
                                CLEAR_CONTAINER(vcGeom);
                        }

                        
                        Debug << i << ": pvs size=" << (int)vc->GetPvs().GetSize() 
                                  << ", piercing rays=" << (int)vcRays.size() << endl;

                        
                        // export rays piercing this view cell
                        exporter->ExportRays(vcRays, RgbColor(0, 1, 0));
        
                        m.mDiffuseColor = RgbColor(1, 0, 0);
                        exporter->SetForcedMaterial(m);

                        ObjectPvsMap::const_iterator it,
                                it_end = vc->GetPvs().mEntries.end();

                        // output PVS of view cell
                        for (it = vc->GetPvs().mEntries.begin(); it != it_end; ++ it) 
                        {
                                Intersectable *intersect = (*it).first;

                                if (!intersect->Mailed())
                                {
                                        Material m = RandomMaterial();
                        
                                        exporter->SetForcedMaterial(m);

                                        exporter->ExportIntersectable(intersect);
                                        intersect->Mail();
                                }                       
                        }
                                
                        DEL_PTR(exporter);
                        cout << "finished" << endl;
                }
        }

        Debug << endl;
}


bool VspBspViewCellsManager::MergeVspBspLeafViewCells(BspLeaf *front, 
                                                                                                          BspLeaf *back) const
{
        BspViewCell *viewCell = 
                dynamic_cast<BspViewCell *>(MergeViewCells(*front->GetViewCell(), 
                                                                                                   *back->GetViewCell()));
        
        if (!viewCell)
                return false;

        // change view cells of all leaves
        // associated with the previous view cells
        BspViewCell *fVc = front->GetViewCell();
        BspViewCell *bVc = back->GetViewCell();

        vector<BspLeaf *> fLeaves = fVc->mLeaves;
        vector<BspLeaf *> bLeaves = bVc->mLeaves;

        vector<BspLeaf *>::const_iterator it;
        
        for (it = fLeaves.begin(); it != fLeaves.end(); ++ it)
        {
                (*it)->SetViewCell(viewCell);
                viewCell->mLeaves.push_back(*it);
        }
        for (it = bLeaves.begin(); it != bLeaves.end(); ++ it)
        {
                (*it)->SetViewCell(viewCell);
                viewCell->mLeaves.push_back(*it);
        }
        
        DEL_PTR(fVc);
        DEL_PTR(bVc);

        return true;
}

bool VspBspViewCellsManager::ShouldMerge(BspLeaf *front, BspLeaf *back) const
{
        ViewCell *fvc = front->GetViewCell();
        ViewCell *bvc = back->GetViewCell();

        if ((fvc == mVspBspTree->GetRootCell()) || 
                (bvc == mVspBspTree->GetRootCell()) || 
                (fvc == bvc))
                return false;

        const int fdiff = fvc->GetPvs().Diff(bvc->GetPvs());

        if (fvc->GetPvs().GetSize() + fdiff < mMaxPvs)
        {
                if ((fvc->GetPvs().GetSize() < mMinPvs) ||      
                        (bvc->GetPvs().GetSize() < mMinPvs) ||
                        ((fdiff < mMinPvsDif) && (bvc->GetPvs().Diff(fvc->GetPvs()) < mMinPvsDif)))
                {
                        return true;
                }
        }
        
        return false;
}


int VspBspViewCellsManager::CastLineSegment(const Vector3 &origin,
                                                                                        const Vector3 &termination,
                                                                                        ViewCellContainer &viewcells)
{
        return mVspBspTree->CastLineSegment(origin, termination, viewcells);
}