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

#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():
mRenderer(NULL),
mConstructionSamples(0),
mPostProcessSamples(0),
mVisualizationSamples(0),
mTotalAreaValid(false),
mTotalArea(0.0f)
{
        mSceneBox.Initialize();
        ParseEnvironment();
}

ViewCellsManager::ViewCellsManager(int constructionSamples):
mConstructionSamples(constructionSamples),
mRenderer(NULL),
mPostProcessSamples(0),
mVisualizationSamples(0)
{
        mSceneBox.Initialize();
        ParseEnvironment();
}

void ViewCellsManager::ParseEnvironment()
{
        // post processing stuff
        environment->GetIntValue("ViewCells.PostProcess.minPvsDif", mMinPvsDif);
        environment->GetIntValue("ViewCells.PostProcess.minPvs", mMinPvs);
        environment->GetIntValue("ViewCells.PostProcess.maxPvs", mMaxPvs);

        environment->GetBoolValue("ViewCells.Visualization.exportRays", mExportRays);
        environment->GetBoolValue("ViewCells.Visualization.exportGeometry", mExportGeometry);

        char buf[50];
        
        environment->GetStringValue("ViewCells.Visualization.colorCode", buf);
        
        if (strcmp(buf, "PVS") == 0)
                mColorCode = 1;
        else if (strcmp(buf, "MergedLeaves") == 0)
                mColorCode = 2;
        else if (strcmp(buf, "MergedTreeDiff") == 0)
                mColorCode = 3;
        else
                mColorCode = 0;

        Debug << "colorCode: " << mColorCode << endl;
}


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

        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;
}


bool ViewCellsManager::GetViewPoint(Vector3 &viewPoint) const
{
        viewPoint = mSceneBox.GetRandomPoint();

        return true;
}


bool ViewCellsManager::ViewPointValid(const Vector3 &viewPoint) const
{
        return mSceneBox.IsInside(viewPoint);
}

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::EvaluateViewCellsStats()
{
        mViewCellsStats.Reset();

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

        for (it = mViewCells.begin(); it != it_end; ++ it)
        {
                (*it)->UpdateViewCellsStats(mViewCellsStats);
        }
}


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


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


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


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;
}


void ViewCellsManager::SetRenderer(Renderer *renderer)
{
        mRenderer = renderer;
}


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::SetViewSpaceBox(const AxisAlignedBox3 &box)
{
        mSceneBox = box;
}


void ViewCellsManager::ResetViewCells()
{
        mViewCells.clear();
        CollectViewCells();
        mViewCellsStats.Reset();
        EvaluateViewCellsStats();

        mTotalAreaValid = false;
}


void ViewCellsManager::ComputeSampleContributions(VssRay &ray)
{



  ViewCellContainer viewcells;
                
  ray.mPvsContribution = 0;
  ray.mRelativePvsContribution = 0.0f;

  // matt TODO: remove this!!
  Ray hray(ray);
  float tmin = 0, tmax = 1.0;
  
  //hray.Init(ray.GetOrigin(), ray.GetDir(), Ray::LINE_SEGMENT);
  if (!GetSceneBbox().GetRaySegment(hray, tmin, tmax) || (tmin > tmax))
        return;
  
  Vector3 origin = hray.Extrap(tmin);
  Vector3 termination = hray.Extrap(tmax);
  
  CastLineSegment(origin,
                                  termination,
                                  viewcells);
  
  // copy viewcells memory efficiently
  const bool storeViewcells = false;
  if (storeViewcells) {
        ray.mViewCells.reserve(viewcells.size());
        ray.mViewCells = viewcells;
  }
  
  ViewCellContainer::const_iterator it = viewcells.begin();

  bool addInPlace = false;

  if (addInPlace) {
        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;
        }
  } else {
    for (; it != viewcells.end(); ++it) {       
          ViewCell *viewcell = *it;
          // if ray not outside of view space
          float contribution;
          if (viewcell->GetPvs().GetSampleContribution(ray.mTerminationObject,
                                                                                                   contribution
                                                                                                   ))
                ray.mPvsContribution++;
          
          ray.mRelativePvsContribution += contribution;
        }

        for (it = viewcells.begin(); it != viewcells.end(); ++it) {     
          ViewCell *viewcell = *it;
          // if ray not outside of view space
          viewcell->GetPvs().AddSample(ray.mTerminationObject);
        }
  }
}


void ViewCellsManager::GetRaySets(const VssRayContainer &sourceRays,
                                                                  const int maxSize,
                                                                  VssRayContainer &usedRays, 
                                                                  VssRayContainer *savedRays) const
{
        const int limit = min(maxSize, (int)sourceRays.size());
        const float prop = (float)limit / ((float)sourceRays.size() + Limits::Small);

        VssRayContainer::const_iterator it, it_end = sourceRays.end();
        for (it = sourceRays.begin(); it != it_end; ++ it)
        {
                if (Random(1.0f) < prop)
                        usedRays.push_back(*it);
                else if (savedRays)
                        savedRays->push_back(*it);
        }
}


float ViewCellsManager::GetAccVcArea()
{
        // 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)
        {
                //Debug << "area: " << GetArea(*it);
        mTotalArea += GetArea(*it);
        }

        mTotalAreaValid = true;

        return mTotalArea;
}


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


void ViewCellsManager::ExportViewCells(Exporter *exporter) const
{
        ViewCellContainer::const_iterator it, it_end = mViewCells.end();

        for (it = mViewCells.begin(); it != it_end; ++ it)
        {
                ExportColor(exporter, *it);
                ExportVcGeometry(exporter, *it);
        }
}


/**********************************************************************/
/*                   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)
{
        // 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);
        }

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

        Debug << mBspTree->GetStatistics() << endl;
        
        EvaluateViewCellsStats();
        Debug << "\nView cells after construction:\n" << mViewCellsStats << endl;

        // recast rest of the rays
        ComputeSampleContributions(savedRays);

        return sampleContributions;
}

void BspViewCellsManager::CollectViewCells()
{
        mBspTree->CollectViewCells(mViewCells);
}

float BspViewCellsManager::GetProbability(ViewCell *viewCell)
{
        // compute view cell area as subsititute for probability
#if 0
        return GetArea(viewCell) / GetSceneBbox().SurfaceArea();
#else
        return GetArea(viewCell) / GetAccVcArea();
#endif
}
  

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


AxisAlignedBox3 BspViewCellsManager::GetSceneBbox() const
{
        return mBspTree->GetBoundingBox();
}


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;

        EvaluateViewCellsStats();
        Debug << "\noriginal view cell partition:\n" << mViewCellsStats << endl;

        mRenderer->RenderScene();
        SimulationStatistics ss;
        dynamic_cast<RenderSimulator *>(mRenderer)->GetStatistics(ss);

    Debug << ss << 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();
                        ExportViewCells(exporter);
                                
                        if (mExportGeometry)
                        {
                                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 remember 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;
        CLEAR_CONTAINER(mBspRays);
        ConstructBspRays(rays, mPostProcessSamples);
        
        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))
                        {                       
                                MergeBspLeafViewCells(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" 
                  << "using " << (int)mBspRays.size() << " samples" << endl << endl;
        
        CLEAR_CONTAINER(mBspRays);

        // reset view cells and stats
        ResetViewCells();

        return merged;
}


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


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


void BspViewCellsManager::Visualize(const ObjectContainer &objects,
                                                                        const VssRayContainer &sampleRays)
{
        if (!ViewCellsConstructed())
                return;
        CLEAR_CONTAINER(mBspRays);
        ConstructBspRays(sampleRays, mVisualizationSamples);
        
        if (1) // export view cells
        {
                cout << "exporting view cells after merge ... ";
                Exporter *exporter = Exporter::GetExporter("merged_view_cells.x3d");

                if (exporter)
                {
                        ExportViewCells(exporter);
                        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);
}


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


void BspViewCellsManager::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(*mBspTree, true);

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

                exporter->SetFilled();
                                
                // 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 (mExportGeometry)
                        exporter->ExportGeometry(objects);

                delete exporter;
        }
}


void BspViewCellsManager::ExportBspPvs(const ObjectContainer &objects)
{
        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;
        
        // sort view cells to get largest view cells
#if 0
        stable_sort(mViewCells.begin(), mViewCells.end(), vc_gt);
#endif
        int limit = min(leafOut, (int)mViewCells.size()); 
                
        for (int i = 0; i < limit; ++ i)
        {
                cout << "creating output for view cell " << i << " ... ";
                VssRayContainer vcRays;
                Intersectable::NewMail();
#if 0
                BspViewCell *vc = dynamic_cast<BspViewCell *>(mViewCells[i]);
#else
                BspViewCell *vc = dynamic_cast<BspViewCell *>(mViewCells[Random((int)mViewCells.size())]);
#endif
                cout << "creating output for view cell " << i << " ... ";

#if 0
                // 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);
                        }
                }
#endif
                //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
                        mBspTree->ConstructGeometry(vc, vcGeom);
                        exporter->ExportPolygons(vcGeom);
                        CLEAR_CONTAINER(vcGeom);
                }
                        
                Debug << i << ": pvs size=" << (int)vc->GetPvs().GetSize() 
                          << ", piercing rays=" << (int)vcRays.size()
                          << ", leaves=" << (int)vc->mLeaves.size() << endl;

                        
                // export rays piercing this view cell
#if 0
                exporter->ExportRays(vcRays, RgbColor(0, 1, 0));
#else
                vector<BspLeaf *>::const_iterator lit, lit_end = vc->mLeaves.end();
                for (lit = vc->mLeaves.begin(); lit != lit_end; ++ lit)
                        exporter->ExportRays((*lit)->mVssRays);
#endif
                m.mDiffuseColor = RgbColor(1, 0, 0);
                exporter->SetForcedMaterial(m);

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

                exporter->SetFilled();

                // 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 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;
}


void BspViewCellsManager::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;

                // cast line segment to get intersections with bsp leaves
                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);
        }
}


void BspViewCellsManager::ExportColor(Exporter *exporter, 
                                                                          ViewCell *vc) const
{
        if (mColorCode == 0) // Random color
        {
                exporter->ResetForcedMaterial();
                return;
        }

        float importance = 0;

        switch (mColorCode)
        {
        case 1: // pvs
                {
                        importance = (float)vc->GetPvs().GetSize() / 
                                (float)mViewCellsStats.maxPvs;
                }
                break;
        case 2: // merges
                {
                        BspViewCell *bspVc = dynamic_cast<BspViewCell *>(vc);

                        importance = (float)bspVc->mLeaves.size() / 
                                (float)mViewCellsStats.maxLeaves;
                }
                break;
        case 3: // merge tree differene
                {
                        // TODO
                }
                break;
        default:
                break;
        }

        Material m;
        m.mDiffuseColor.b = 1.0f;
        m.mDiffuseColor.r = importance;
        m.mDiffuseColor.g = 1.0f - m.mDiffuseColor.r;
        
        exporter->SetForcedMaterial(m);
}

void BspViewCellsManager::ExportVcGeometry(Exporter *exporter, 
                                                                                 ViewCell *vc) const
{
        if (vc->GetMesh())
                exporter->ExportViewCell(vc);
        else
        {
                PolygonContainer cell;
                mBspTree->ConstructGeometry(
                        dynamic_cast<BspViewCell *>(vc), cell);
                exporter->ExportPolygons(cell);
        }
}

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

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

float KdViewCellsManager::GetProbability(ViewCell *viewCell)
{
        // compute view cell area / volume as subsititute for probability
#if 0
        return GetArea(viewCell) / GetSceneBbox().SurfaceArea();
#endif
#if 1
        return GetArea(viewCell) / GetAccVcArea();
#endif
#if 0
        return GetVolume(viewCell) / GetSceneBbox().GetVolume();
#endif
}


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


AxisAlignedBox3 KdViewCellsManager::GetSceneBbox() const
{
        return mKdTree->GetBox();
}

void KdViewCellsManager::CollectViewCells()
{
        //mKdTree->CollectViewCells(mViewCells); TODO
}

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

        mKdTree->Construct();

        mTotalAreaValid = false;
        // create the view cells
        mKdTree->CreateAndCollectViewCells(mViewCells);
        
        // cast rays
        ComputeSampleContributions(rays);

        EvaluateViewCellsStats();
        Debug << "\nView cells after construction:\n" << mViewCellsStats << endl;

        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];

        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 << " ... ";
#if 0                   
                        // 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);
                                        }
                                }
                        }
#endif                  
                        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;
                }
        }               
}


void KdViewCellsManager::ExportColor(Exporter *exporter,
                                                                         ViewCell *vc) const
{
        // TODO
}


void KdViewCellsManager::ExportVcGeometry(Exporter *exporter, 
                                                                                  ViewCell *vc) const
{
        KdViewCell *kdVc = dynamic_cast<KdViewCell *>(vc);
        vector<KdLeaf *>::const_iterator it, it_end = kdVc->mLeaves.end();

        for (it = kdVc->mLeaves.begin(); it != it_end; ++ it)
                exporter->ExportBox(mKdTree->GetBox(*it));
}


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
#if 0
        return GetArea(viewCell) / GetSceneBbox().SurfaceArea();
#else
        return GetArea(viewCell) / GetAccVcArea();
#endif
}


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

void VspKdViewCellsManager::CollectViewCells()
{
        mVspKdTree->CollectViewCells(mViewCells);
}

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

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

        mVspKdTree->Construct(constructionRays, &mSceneBox);
        Debug << mVspKdTree->GetStatistics() << endl;

        // export leaf building blocks
        ExportLeaves(objects, rays);

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

        // collapse siblings belonging to the same view cell
        mVspKdTree->CollapseTree();

        // collapse siblings belonging to the same view cell
        mVspKdTree->RefineViewCells(rays);

        // evaluale view cell stats
        ResetViewCells();

        Debug << "\nView cells after construction:\n" << mViewCellsStats << endl;

        long startTime = GetTime();
        // recast rest of rays
        ComputeSampleContributions(savedRays);
        
        Debug << "Computed remaining ray contribution in " << TimeDiff(startTime, GetTime()) * 1e-3 
                  << " secs" << endl;

        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;

        // recalculate stats
        EvaluateViewCellsStats();

        return 0;
}


AxisAlignedBox3 VspKdViewCellsManager::GetSceneBbox() const
{
        return mVspKdTree->GetBBox(mVspKdTree->GetRoot());
}


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

        //-- export leaf building blocks
        Exporter *exporter = Exporter::GetExporter("vspkdtree.x3d"); 
        if (!exporter)
                return;

        //exporter->SetWireframe();
        //exporter->ExportVspKdTree(*mVspKdTree, mVspKdTree->GetStatistics().maxPvsSize);
        exporter->ExportVspKdTree(*mVspKdTree);

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

        if (mExportRays) 
        {
                const float prob = (float)mVisualizationSamples 
                        / ((float)sampleRays.size() + Limits::Small);

                exporter->SetWireframe();

                //-- collect uniformly distributed rays
                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;
}

void VspKdViewCellsManager::Visualize(const ObjectContainer &objects,
                                                                          const VssRayContainer &sampleRays)
{
        if (!ViewCellsConstructed())
                return;
        
        //-- export single view cells
        for (int i = 0; i < 10; ++ i)
        {
                char s[64];
                sprintf(s, "vsp_viewcell%04d.x3d", i);
                Exporter *exporter = Exporter::GetExporter(s);
                const int idx = 
                        (int)RandomValue(0.0, (Real)((int)mViewCells.size() - 1));

                VspKdViewCell *vc = dynamic_cast<VspKdViewCell *>(mViewCells[idx]); 

                cout << "Output view cell " << i << " with pvs size " << vc->GetPvs().GetSize() << endl;
                Debug << "Output view cell " << i << " with pvs size " << vc->GetPvs().GetSize() << endl;
                //-- export geometry
                Material m;
                m.mDiffuseColor = RgbColor(0, 1, 1);
                                
                exporter->SetForcedMaterial(m);
                exporter->SetWireframe();

                ExportVcGeometry(exporter, vc);

                //-- export stored rays
                if (mExportRays)
                {
                        vector<VspKdLeaf *>::const_iterator it, 
                                it_end = vc->mLeaves.end();

                        for (it = vc->mLeaves.begin(); it != it_end; ++ it)
                        {
                                VspKdLeaf *leaf = *it;
                                AxisAlignedBox3 box = mVspKdTree->GetBBox(leaf);

                                VssRayContainer vssRays;

                                VssRayContainer castRays;
                                VssRayContainer initRays;

                                leaf->GetRays(vssRays);

                                VssRayContainer::const_iterator it, it_end = vssRays.end();
                                const float prop = 200.0f / (float)vssRays.size();

                                for (it = vssRays.begin(); it != it_end; ++ it)
                                {
                                        if (Random(1) < prop)
                                                if ((*it)->mTerminationObject == NULL)
                                                        castRays.push_back(*it);
                                                else 
                                                        initRays.push_back(*it);
                                }

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

                //-- output PVS of view cell
                m.mDiffuseColor = RgbColor(1, 0, 0);
                exporter->SetForcedMaterial(m);

                Intersectable::NewMail();

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

                exporter->SetFilled();

                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();
                        }                       
                }

                delete exporter;
        }

        //-- export final view cells
        Exporter *exporter = Exporter::GetExporter("vspkdtree_merged.x3d"); 
        
        //if (exportGeometry) exporter->SetWireframe();
        //else exporter->SetFilled();

        ExportViewCells(exporter);

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

        if (mExportRays) 
        {
                const float prob = (float)mVisualizationSamples 
                        / ((float)sampleRays.size() + Limits::Small);
                
                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);
}


void VspKdViewCellsManager::ExportColor(Exporter *exporter,
                                                                                ViewCell *vc) const
{
        if (mColorCode == 0) // Random color
                return;
        
        float importance = 0;

        switch (mColorCode)
        {
        case 1: // pvs
                {
                        importance = (float)vc->GetPvs().GetSize() / 
                                (float)mViewCellsStats.maxPvs;
                }
                break;
        case 2: // merges
                {
            VspKdViewCell *vspKdVc = dynamic_cast<VspKdViewCell *>(vc);

                        importance = (float)vspKdVc->mLeaves.size() / 
                                (float)mViewCellsStats.maxLeaves;
                }
                break;
        case 3: // merged tree depth difference
                {
                        //importance = (float)GetMaxTreeDiff(vc) / 
                        //      (float)(mVspBspTree->GetStatistics().maxDepth * 2);
                }
                break;
        default:
                break;
        }

        Material m;
        m.mDiffuseColor.b = 1.0f;
        m.mDiffuseColor.r = importance;
        m.mDiffuseColor.g = 1.0f - m.mDiffuseColor.r;
        //Debug << "importance: " << importance << endl;
        exporter->SetForcedMaterial(m);
}


void VspKdViewCellsManager::ExportVcGeometry(Exporter *exporter, 
                                                                                   ViewCell *vc) const
{
        VspKdViewCell *kdVc = dynamic_cast<VspKdViewCell *>(vc);
        vector<VspKdLeaf *>::const_iterator it, it_end = kdVc->mLeaves.end();

        Mesh m;
        for (it = kdVc->mLeaves.begin(); it != it_end; ++ it)
        {
                mVspKdTree->GetBBox(*it).AddBoxToMesh(&m);
        }

        exporter->ExportMesh(&m);
}


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


VspBspViewCellsManager::VspBspViewCellsManager(VspBspTree *vspBspTree, 
                                                                                           int constructionSamples):
ViewCellsManager(constructionSamples), 
mVspBspTree(vspBspTree)
{
        mVspBspTree->SetViewCellsManager(this);
}


VspBspViewCellsManager::~VspBspViewCellsManager()
{
}


float VspBspViewCellsManager::GetProbability(ViewCell *viewCell)
{
#if 0
        return GetArea(viewCell) / GetSceneBbox().SurfaceArea();
#else
        return GetArea(viewCell) / GetAccVcArea();
#endif
}


void VspBspViewCellsManager::CollectViewCells()
{
        mVspBspTree->CollectViewCells(mViewCells);
}


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


AxisAlignedBox3 VspBspViewCellsManager::GetSceneBbox() const
{
        return mVspBspTree->GetBoundingBox();
}


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)
{
  // if view cells were already constructed
  if (ViewCellsConstructed())
        return 0;
  
  Debug << "Constructing bsp view cells" << endl;
  
  int sampleContributions = 0;
  
  VssRayContainer sampleRays;
  
  int limit = min (mConstructionSamples, (int)rays.size());

        
        VssRayContainer constructionRays;
        VssRayContainer savedRays;

        GetRaySets(rays, mConstructionSamples, constructionRays, &savedRays);

        Debug << "construction rays: " << (int)savedRays.size() << endl;
        Debug << "saved rays: " << (int)constructionRays.size() << endl;

        mVspBspTree->Construct(constructionRays, &mSceneBox);
        
        Debug << mVspBspTree->GetStatistics() << endl;

        // collapse invalid regions
        cout << "collapsing invalid tree regions ... ";
        long startTime = GetTime();
        mVspBspTree->CollapseTree(); 
        Debug << "tree collapsed in " << TimeDiff(startTime, GetTime()) * 1e-3 << " seconds" << endl;
    cout << "finished" << endl;
        
        cout << "reseting view cell stats ... ";
        ResetViewCells();
        cout << "finished" << endl;
        
        Debug << "\nView cells after construction:\n" << mViewCellsStats << endl;

        if (1) // export initial view cells
        {
                cout << "exporting initial view cells (=leaves) ... ";
                Exporter *exporter = Exporter::GetExporter("view_cells.x3d");
        
                if (exporter)
                {
                        //exporter->SetWireframe();
                        exporter->SetFilled();
                        ExportViewCells(exporter);

                        if (0 && mExportRays)
                                exporter->ExportRays(rays, RgbColor(1, 1, 1));
                        
                        if (mExportGeometry)
                                exporter->ExportGeometry(objects);
                        
                        delete exporter;
                }
                cout << "finished" << endl;
        }

        startTime = GetTime();
        cout << "Computing remaining ray contributions ... ";
        // recast rest of rays
        ComputeSampleContributions(savedRays);
        cout << "finished" << endl;

        Debug << "Computed remaining ray contribution in " << TimeDiff(startTime, GetTime()) * 1e-3 
                  << " secs" << endl;

        cout << "construction finished" << endl;
        return sampleContributions;
}


// matt TODO: remove
int VspBspViewCellsManager::MergeViewCells(const VssRayContainer &rays) const
{
        vector<BspIntersection>::const_iterator iit;
        vector<BspRay *>bspRays;
        int merged = 0;

        mVspBspTree->ConstructBspRays(bspRays, rays);

        for (int i = 0; i < (int)bspRays.size(); ++ i)
        {
                BspRay *ray = bspRays[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))
                        {                       
                                mVspBspTree->MergeViewCells(leaf, previousLeaf);
                                ++ merged;
                        }
                        previousLeaf = leaf;
                }
        }
        CLEAR_CONTAINER(bspRays);

        return merged;
}
        

int VspBspViewCellsManager::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;

        VssRayContainer postProcessRays;
        GetRaySets(rays, mPostProcessSamples, postProcessRays);

        Debug << "post processing using " << (int)postProcessRays.size() << " samples" << endl;
        EvaluateViewCellsStats();
        Debug << "\noriginal view cell partition:\n" << mViewCellsStats << endl << endl;

        mRenderer->RenderScene();
        SimulationStatistics ss;
        dynamic_cast<RenderSimulator *>(mRenderer)->GetStatistics(ss);
    Debug << ss << endl;

        //-- merge or subdivide view cells
        int merged = 0;
        
        cout << "starting merge using " << mPostProcessSamples << " samples ... ";
        long startTime = GetTime();

        merged = mVspBspTree->MergeViewCells(postProcessRays);

        //-- 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;
        
        cout << "reseting view cell stats ... ";
        ResetViewCells();
        cout << "finished" << endl;

        //BspLeaf::NewMail();
        if (1) // export merged view cells
        {
                Exporter *exporter = Exporter::GetExporter("merged_view_cells.x3d");
                Debug << "\nView cells after merge:\n" << mViewCellsStats << endl;

                cout << "exporting view cells after merge ... ";

                if (exporter)
                {
                        //exporter->SetWireframe();
                        exporter->SetFilled();
                        ExportViewCells(exporter);

                        if (mExportGeometry)
                        {
                                Material m;
                                m.mDiffuseColor = RgbColor(0, 1, 0);
                                exporter->SetForcedMaterial(m);
                                exporter->SetFilled();

                                exporter->ExportGeometry(objects);
                        }

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

        Debug << "render time before refine:" << endl;
        mRenderer->RenderScene();
        dynamic_cast<RenderSimulator *>(mRenderer)->GetStatistics(ss);
    Debug << ss << endl;

        cout << "Refining the merged view cells ... ";
        startTime = GetTime();

        // refining the merged view cells
        const int refined = mVspBspTree->RefineViewCells(rays);

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

        Debug << "Postprocessing: refined " << refined << " view cells in "
                  << TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl << endl;
        
        // collapse sibling leaves that share the same view cell
        mVspBspTree->CollapseTree();

        // reset view cells and stats
        ResetViewCells();

        return merged;
}


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


bool VspBspViewCellsManager::GetViewPoint(Vector3 &viewPoint) const
{
        if (!ViewCellsConstructed())
                return ViewCellsManager::GetViewPoint(viewPoint);

        // TODO: set reasonable limit
        const int limit = 20;

        for (int i = 0; i < limit; ++ i)
        {
                viewPoint = mSceneBox.GetRandomPoint();
                if (mVspBspTree->ViewPointValid(viewPoint))
                {
                        return true;
                }
        }
        Debug << "failed to find valid view point, taking " << viewPoint << endl;
        return false;
}


bool VspBspViewCellsManager::ViewPointValid(const Vector3 &viewPoint) const
{
        return mSceneBox.IsInside(viewPoint) && 
                   mVspBspTree->ViewPointValid(viewPoint);
}


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

        VssRayContainer visRays;
        GetRaySets(sampleRays, mVisualizationSamples, visRays);

        if (1) // export view cells
        {
                cout << "exporting view cells after post process ... ";
                Exporter *exporter = Exporter::GetExporter("final_view_cells.x3d");

                if (exporter)
                {
                        if (mExportGeometry)
                                exporter->ExportGeometry(objects);

                        // export rays
                        if (mExportRays)
                        {
                                exporter->ExportRays(visRays, RgbColor(0, 1, 0));
                        }

                        ExportViewCells(exporter);
                        delete exporter;
                }
                
                cout << "finished" << endl;
        }       

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

        // export single view cells
        ExportBspPvs(objects, visRays);
}
        

void VspBspViewCellsManager::ExportSplits(const ObjectContainer &objects,
                                                                                  const VssRayContainer &rays)
{
        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 (mExportRays)
                        exporter->ExportRays(rays, RgbColor(1, 1, 0));
        
                if (mExportGeometry)
                        exporter->ExportGeometry(objects);

                delete exporter;
        }
}

void VspBspViewCellsManager::ExportBspPvs(const ObjectContainer &objects,
                                                                                  const VssRayContainer &rays)
{
        const int leafOut = 10;
        
        ViewCell::NewMail();
        
        cout << "visualization using " << mVisualizationSamples << " samples" << endl;
        Debug << "\nOutput view cells: " << endl;
        
        // sort view cells to visualize the largest view cells
#if 0
        stable_sort(mViewCells.begin(), mViewCells.end(), vc_gt);
#endif
        int limit = min(leafOut, (int)mViewCells.size()); 

#if 1
        //-- some rays for output
        vector<BspRay *> bspRays;
        mVspBspTree->ConstructBspRays(bspRays, rays);

        const int raysOut = min((int)bspRays.size(), mVisualizationSamples);
#endif

        for (int i = 0; i < limit; ++ i)
        {
                cout << "creating output for view cell " << i << " ... ";
                
                VssRayContainer vcRays;
                Intersectable::NewMail();
#if 0
                BspViewCell *vc = dynamic_cast<BspViewCell *>(mViewCells[i]);
#else
                BspViewCell *vc = dynamic_cast<BspViewCell *>
                        (mViewCells[Random((int)mViewCells.size())]);
#endif

#if 1
                // check whether we can add the current ray to the output rays
                for (int k = 0; k < raysOut; ++ k) 
                {
                        BspRay *ray = bspRays[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);
                        }
                }
#endif
                //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);

                ExportVcGeometry(exporter, vc); 
                        
                                
                Debug << i << ": pvs size=" << (int)vc->GetPvs().GetSize() 
                          << ", piercing rays=" << (int)vcRays.size()
                          << ", leaves=" << (int)vc->mLeaves.size() << endl;
                
                //-- export rays piercing this view cell
#if 1
                exporter->ExportRays(vcRays, RgbColor(1, 1, 1));
#endif
#if 0
                vector<BspLeaf *>::const_iterator lit, lit_end = vc->mLeaves.end();

                for (lit = vc->mLeaves.begin(); lit != lit_end; ++ lit)
                        exporter->ExportRays((*lit)->mVssRays);
#endif
                m.mDiffuseColor = RgbColor(1, 0, 0);
                exporter->SetForcedMaterial(m);

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

                exporter->SetFilled();

                // 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;
        }

#if 1
        CLEAR_CONTAINER(bspRays);
#endif
        Debug << endl;
}


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

        if (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);
}


void VspBspViewCellsManager::ExportColor(Exporter *exporter, 
                                                                                 ViewCell *vc) const
{
        if (mColorCode == 0) // Random color
                return;
        
        float importance = 0;

        switch (mColorCode)
        {
        case 1: // pvs
                {
                        importance = (float)vc->GetPvs().GetSize() / 
                                (float)mViewCellsStats.maxPvs;
                }
                break;
        case 2: // merges
                {
            BspViewCell *bspVc = dynamic_cast<BspViewCell *>(vc);

                        importance = (float)bspVc->mLeaves.size() / 
                                (float)mViewCellsStats.maxLeaves;
                }
                break;
        case 3: // merge tree differene
                {
                        importance = (float)GetMaxTreeDiff(vc) / 
                                (float)(mVspBspTree->GetStatistics().maxDepth * 2);
                }
                break;
        default:
                break;
        }

        Material m;
        m.mDiffuseColor.b = 1.0f;
        m.mDiffuseColor.r = importance;
        m.mDiffuseColor.g = 1.0f - m.mDiffuseColor.r;
        //Debug << "importance: " << importance << endl;
        exporter->SetForcedMaterial(m);
}


void VspBspViewCellsManager::ExportVcGeometry(Exporter *exporter, 
                                                                                          ViewCell *vc) const
{
#if 1
        BspNodeGeometry geom;
        mVspBspTree->
                ConstructGeometry(dynamic_cast<BspViewCell *>(vc), geom.mPolys);
        exporter->ExportPolygons(geom.mPolys);
#else
        
        Material m2;
        m2.mDiffuseColor.b = 0.3f + Random(0.7f);
        m2.mDiffuseColor.r = 0.0f;//0.3f + Random(0.7f);
        m2.mDiffuseColor.g = 0.3f + Random(0.7f);
        Material m;
        m.mDiffuseColor.b = 0.0f;
        m.mDiffuseColor.r = 1.0f;
        m.mDiffuseColor.g = 0.0f;

        BspViewCell *bspVc = dynamic_cast<BspViewCell *>(vc);
        vector<BspLeaf *>::const_iterator it, it_end = bspVc->mLeaves.end();

        for (it = bspVc->mLeaves.begin(); it != it_end; ++ it)
        {
                if ((*it)->Mailed())
                        exporter->SetForcedMaterial(m);
                else
                        exporter->SetForcedMaterial(m2);
                        //exporter->ResetForcedMaterial();
                BspNodeGeometry geom;
                mVspBspTree->ConstructGeometry(*it, geom);
                exporter->ExportPolygons(geom.mPolys);
        }
#endif
}


int VspBspViewCellsManager::GetMaxTreeDiff(ViewCell *vc) const
{
        BspViewCell *bspVc = dynamic_cast<BspViewCell *>(vc);

        int maxDist = 0;
        // compute max height difference
        for (int i = 0; i < (int)bspVc->mLeaves.size(); ++ i)
                for (int j = 0; j < (int)bspVc->mLeaves.size(); ++ j)
        {
                BspLeaf *leaf = bspVc->mLeaves[i];

                if (i != j)
                {
                        BspLeaf *leaf2 = bspVc->mLeaves[j];
                        int dist = mVspBspTree->TreeDistance(leaf, leaf2);
                        if (dist > maxDist)
                                maxDist = dist;
                }
        }
        return maxDist;
}




ViewCell *
VspBspViewCellsManager::GetViewCell(const Vector3 &point)
{
  if (!mVspBspTree)
        return NULL;
  return mVspBspTree->GetViewCell(point);
}