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

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

void ViewCellsManager::InitRenderSimulator()
{
        float objRenderCost = 0, vcOverhead = 0, moveSpeed = 0;

        environment->GetFloatValue("Simulation.objRenderCost",objRenderCost);
        environment->GetFloatValue("Simulation.vcOverhead", vcOverhead);
        environment->GetFloatValue("Simulation.moveSpeed", moveSpeed);

        mRenderSimulator->SetObjectRenderCost(objRenderCost);
        mRenderSimulator->SetVcOverhead(vcOverhead);
        mRenderSimulator->SetMoveSpeed(moveSpeed);
}

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 RayContainer &rays, 
                                                                                                  const bool castRays,
                                                                                                  int &sampleContributions,
                                                                                                  int &contributingSamples)
{
        // view cells not yet constructed
        if (!ViewCellsConstructed())
                return;

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

    for (it = rays.begin(); it != it_end; ++ it)
        {
                sampleContributions += ComputeSampleContributions(*(*it), castRays);
                contributingSamples += sampleContributions > 0;
        }
}

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

SimulationStatistics ViewCellsManager::SimulateRendering() const
{
        if (!ViewCellsConstructed())
                return SimulationStatistics();

        return mRenderSimulator->SimulateRendering();
}

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

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

BspViewCellsManager::BspViewCellsManager(BspTree *bspTree, int constructionSamples):
ViewCellsManager(constructionSamples), 
mBspTree(bspTree)
{
   mRenderSimulator = new BspRenderSimulator(bspTree);
   InitRenderSimulator();
}

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;

        Debug << "Constructing bsp view cells" << endl;

        int sampleContributions = 0;
        
        RayContainer sampleRays;

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

    for (int i = 0; i < limit; ++ i)
                sampleRays.push_back(new Ray(*rays[i]));

        if (mViewCells.empty()) // no view cells loaded
                mBspTree->Construct(objects, sampleRays);
        else
                mBspTree->Construct(mViewCells);

        Debug << mBspTree->GetStatistics() << endl;
        
        return sampleContributions;
}

int BspViewCellsManager::ComputeSampleContributions(Ray &ray, const bool castRay)
{
        // view cells not yet constructed
        if (!ViewCellsConstructed())
                return 0;

        int contributingSamples = 0;

        if (castRay)
                mBspTree->CastRay(ray);
        
        //if (mBspTree->bspIntersections.empty()) return 0;

        Intersectable *tObject = 
                !ray.intersections.empty() ? ray.intersections[0].mObject : NULL;

        Intersectable *sObject = ray.sourceObject.mObject;

        if (sObject || tObject)
        {
                // object can be seen from the view cell => add to view cell pvs
                for (int j = 0; j < (int)ray.bspIntersections.size(); ++ j)
                {       
                        BspLeaf *leaf = ray.bspIntersections[j].mLeaf;
                
                        // if ray not outside of view space
                        if (leaf->GetViewCell() != mBspTree->GetRootCell())
                        {
                                if (sObject)
                                {
                                        contributingSamples += 
                                                leaf->GetViewCell()->GetPvs().AddSample(sObject);
                                }

                                if (tObject)
                                {
                                        contributingSamples += 
                                                leaf->GetViewCell()->GetPvs().AddSample(tObject);
                                }
                        }
                }
        }

        // rays passing through this viewcell
        if (0)
                for (int j = 1; j < ((int)ray.bspIntersections.size() - 1); ++ j) 
                {
                        BspLeaf *leaf = ray.bspIntersections[j].mLeaf;

                        if (leaf->GetViewCell() != mBspTree->GetRootCell())
                                leaf->GetViewCell()->
                                        AddPassingRay(ray, contributingSamples ? 1 : 0);
                }

        return contributingSamples;
}

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


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

        BspViewCellsStatistics stat;
        mBspTree->EvaluateViewCellsStats(stat);
        Debug << "original view cell partition:\n" << stat << endl;
                
        if (1) // export view cells
        {
                cout << "exporting initial view cells (=leaves) ... ";
                Exporter *exporter = Exporter::GetExporter("view_cells.x3d");
        
                if (exporter)
                {
                        exporter->SetWireframe();
                        exporter->ExportBspLeaves(*mBspTree, stat.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;
        }

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


        //-- merge or subdivide view cells
        int merged = 0;

        RayContainer::const_iterator rit, rit_end = rays.end();
        vector<Ray::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;
                }
        }

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

        return merged;
}

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


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

        //-- recount pvs
        BspViewCellsStatistics 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 RayContainer &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();
                
                // export rays
                if (0)
                {
                        RayContainer outRays;
                
                        int raysSize = min((int)sampleRays.size(), mVisualizationSamples);

                        for (int i = 0; i < raysSize; ++ i)
                        {
                                // only rays piercing geometry
                                if (!sampleRays[i]->intersections.empty())
                                        outRays.push_back(sampleRays[i]);
                        }
                        
                        // export rays 
                        exporter->ExportRays(outRays, 1000, RgbColor(1, 1, 0));
                }

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

                delete exporter;
        }
}

void BspViewCellsManager::ExportBspPvs(const ObjectContainer &objects,
                                                                           const RayContainer &sampleRays)
{
        const int leafOut = 10;
        
        ViewCell::NewMail();

        //-- some rays for output
        const int raysOut = min((int)sampleRays.size(), mVisualizationSamples);
        Debug << "visualization using " << raysOut << " samples" << 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 << " ... ";

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

                        ViewCellPvsMap::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);

                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 << " ... ";
                        // 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);

                        ViewCellPvsMap::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 view cells of all leaves associated with the
        // previous view cells

        BspViewCell *fVc = front->GetViewCell();
        BspViewCell *bVc = back->GetViewCell();

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

        vector<BspLeaf *>::const_iterator it;
        
        for (it = fLeaves.begin(); it != fLeaves.end(); ++ it)
        {
                (*it)->SetViewCell(viewCell);
                viewCell->mBspLeaves.push_back(*it);
        }
        for (it = bLeaves.begin(); it != bLeaves.end(); ++ it)
        {
                (*it)->SetViewCell(viewCell);
                viewCell->mBspLeaves.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)
{
   mRenderSimulator = new KdRenderSimulator(mKdTree);
   InitRenderSimulator();
}

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

        Debug << "Constructing bsp view cells" << endl;
        
        mKdTree->Construct();

        return 0;
}

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

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

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

        const int pvsOut = min((int)objects.size(), 10);

        int limit = min(mVisualizationSamples, (int)sampleRays.size());

        RayContainer *rays = new RayContainer[pvsOut];

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

                if (!ray->intersections.empty()) 
                {
                        // check whether we can add this to the rays
                        for (int j = 0; j < pvsOut; j++) 
                        {
                                if (objects[j] == ray->intersections[0].mObject) 
                                {
                                        rays[j].push_back(ray);
                                }
                        }
                }
        }

        bool exportRays = false;
        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], 1000, 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], 1000, 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;
        }
        DEL_PTR(rays);
}

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

int KdViewCellsManager::ComputeSampleContributions(Ray &ray, const bool castRay)
{
        // view cells not yet constructed
        if (!ViewCellsConstructed())
                return 0;

        if (castRay)
                mKdTree->CastRay(ray);

        if (ray.kdLeaves.empty())
                return 0;

        Intersectable *tObject =
                !ray.intersections.empty() ? ray.intersections[0].mObject : NULL;

        Intersectable *sObject =
                ray.sourceObject.mObject;

        int contributingSamples = 0;
        
        int objects = 0;

        if (sObject)
                objects++;
        if (tObject)
                objects++;

        for (int j = 1; j < ((int)ray.kdLeaves.size() - 1); ++ j) 
        {
                ray.kdLeaves[j]->AddPassingRay2(ray, objects,
                                                                                (int)ray.kdLeaves.size());
        }

        if (!objects)
                return 0;
        
        for (int j=0; j < ray.kdLeaves.size(); j++) 
        {
                KdNode *node = GetNodeForPvs(ray.kdLeaves[j]);

                if (sObject)
                        contributingSamples += sObject->mKdPvs.AddSample(node);
                if (tObject)
                        contributingSamples += tObject->mKdPvs.AddSample(node);
        }

        return contributingSamples;
}


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

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



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

VspKdViewCellsManager::VspKdViewCellsManager(VspKdTree *vspKdTree, int constructionSamples):
ViewCellsManager(constructionSamples), 
mVspKdTree(vspKdTree)
{
   mRenderSimulator = NULL; // TODO: new VspKdRenderSimulator(vspKdTree);
   InitRenderSimulator();
}

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

        mVspKdTree->Construct(rays, sceneBbox);
        return 0;
}

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

int VspKdViewCellsManager::ComputeSampleContributions(Ray &ray, const bool castRay)
{
        // view cells not yet constructed
        if (!ViewCellsConstructed())
                return 0;

        //if (castRay) // TODO

        int sampleContributions = 0;

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

                mBspTree->CastRay(*ray);
                        
                Intersectable *term = 
                        !ray->intersections.empty() ? ray->intersections[0].mObject : NULL
                        ;
                sampleContributions += 
                        AddSampleContributions(*ray, ray->sourceObject.mObject, term);
                        
        }
*/
        return sampleContributions;
}

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

        return 0;
}

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

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

                Debug << "average PVS size: " << mVspKdTree->GetAvgPvsSize() << endl;

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

                bool exportRays = true;

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

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

                delete exporter;
        }

        if (1)
        {
                vector<VspKdTreeLeaf *> 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
                        VspKdTreeLeaf *leaf = leafContainer[Random((int)leafContainer.size())]; 
                        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)
                        {
                                //if (!(*it)->mOriginObject && !(*it)->mTerminationObject)
                                        rays.push_back(*it);

                                //if (!(*it)->mOriginObject && !(*it)->mTerminationObject)
                                //      Debug << "ERR: " << (*it)->mOrigin << " " << (*it)->mTermination << endl;
                        }

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

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

                        delete exporter;
                }                       
        }
}

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


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

VspBspViewCellsManager::VspBspViewCellsManager(VspBspTree *vspBspTree, 
                                                                                           int constructionSamples):
ViewCellsManager(constructionSamples), 
mVspBspTree(vspBspTree)
{
   mRenderSimulator = NULL;// TODO new VspBspRenderSimulator(bspTree);
   //InitRenderSimulator();
}

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;

        Debug << "Constructing bsp view cells" << endl;

        int sampleContributions = 0;
        
        VssRayContainer sampleRays;

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

    for (int i = 0; i < limit; ++ i)
                sampleRays.push_back(rays[i]);

        mVspBspTree->Construct(sampleRays);
        
        Debug << mVspBspTree->GetStatistics() << endl;

        return sampleContributions;
}

int VspBspViewCellsManager::ComputeSampleContributions(Ray &ray, const bool castRay)
{
        // view cells not yet constructed
        if (!ViewCellsConstructed())
                return 0;

        int contributingSamples = 0;

        if (castRay)
                mVspBspTree->CastRay(ray);

        Intersectable *tObject = 
                !ray.intersections.empty() ? ray.intersections[0].mObject : NULL;

        Intersectable *sObject = ray.sourceObject.mObject;

        if (sObject || tObject)
        {
                // object can be seen from the view cell => add to view cell pvs
                for (int j = 0; j < (int)ray.bspIntersections.size(); ++ j)
                {       
                        VspBspLeaf *leaf = NULL;  //TODO ray.bspIntersections[j].mLeaf;
                
                        // if ray not in unbounded space
                        if (leaf->GetViewCell() != mVspBspTree->GetRootCell())
                        {
                                if (sObject)
                                {
                                        contributingSamples += 
                                                leaf->GetViewCell()->GetPvs().AddSample(sObject);
                                }

                                if (tObject)
                                {
                                        contributingSamples += 
                                                leaf->GetViewCell()->GetPvs().AddSample(tObject);
                                }
                        }
                }
        }

        // rays passing through this viewcell
        if (0)
                for (int j = 1; j < ((int)ray.bspIntersections.size() - 1); ++ j) 
                {
                        VspBspLeaf *leaf = NULL;// TODO = ray.bspIntersections[j].mLeaf;

                        if (leaf->GetViewCell() != mVspBspTree->GetRootCell())
                                leaf->GetViewCell()->
                                        AddPassingRay(ray, contributingSamples ? 1 : 0);
                }

        return contributingSamples;
}

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


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

        VspBspViewCellsStatistics vcStats;
        mVspBspTree->EvaluateViewCellsStats(vcStats);
        Debug << "original view cell partition:\n" << vcStats << endl;
                
        if (1) // export view cells
        {
                cout << "exporting initial view cells (=leaves) ... ";
                Exporter *exporter = Exporter::GetExporter("view_cells.x3d");
        
                if (exporter)
                {
                        exporter->SetWireframe();
                        //exporter->ExportBspLeaves(*mVspBspTree, stat.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();


        //-- merge or subdivide view cells
        int merged = 0;

        RayContainer::const_iterator rit, rit_end = rays.end();
        vector<Ray::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();

                VspBspLeaf *previousLeaf = NULL;//TODO(*iit).mLeaf;
                ++ iit;
                
                for (; iit != ray->bspIntersections.end(); ++ iit)
                {
                        VspBspLeaf *leaf = NULL;//TODO(*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;

        return merged;
}

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


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

        //-- recount pvs
        VspBspViewCellsStatistics vcStats;
        mVspBspTree->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(*mVspBspTree, vcStats.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, sampleRays);
                cout << "finished" << endl;
        }

//TODO  ExportVspBspPvs(objects, sampleRays);
}


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

        if (exporter) 
        {       
                Material m; 
                m.mDiffuseColor = RgbColor(1, 0, 0);
                exporter->SetForcedMaterial(m);
                exporter->SetWireframe();
                // TODO
                //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)
                {
                        RayContainer outRays;
                
                        int raysSize = min((int)sampleRays.size(), mVisualizationSamples);

                        for (int i = 0; i < raysSize; ++ i)
                        {
                                // only rays piercing geometry
                                if (!sampleRays[i]->intersections.empty())
                                        outRays.push_back(sampleRays[i]);
                        }
                        
                        // export rays 
                        exporter->ExportRays(outRays, 1000, RgbColor(1, 1, 0));
                }

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

                delete exporter;
        }
}

void VspBspViewCellsManager::ExportBspPvs(const ObjectContainer &objects,
                                                                                  const RayContainer &sampleRays)
{
        const int leafOut = 10;
        
        ViewCell::NewMail();

        //-- some rays for output
        const int raysOut = min((int)sampleRays.size(), mVisualizationSamples);
        cout << "visualization using " << mVisualizationSamples << " samples" << endl;
        vector<Ray *> vcRays[leafOut];

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

                for (int i = 0; i < leafOut; ++ i)
                        vspBspLeaves.push_back(mVspBspTree->GetRandomLeaf());   
                
                for (int i = 0; i < (int)vspBspLeaves.size(); ++ 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) 
                        {
                                Ray *ray = sampleRays[k];

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

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

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

                        ViewCellPvsMap::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[i].size() << endl;

                        // export rays piercing this view cell
                        exporter->ExportRays(vcRays[i], 1000, RgbColor(0, 1, 0));

                        m.mDiffuseColor = RgbColor(1, 0, 0);
                        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();
                                }                       
                        }
                                
                        // output rest of the objects
                        if (0)
                        {
                                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 << " ... ";
                        
            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) 
                        {
                                Ray *ray = sampleRays[k];

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

                                        if (vc == leaf->GetViewCell()) 
                                        {
                                                vcRays[i].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 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[i].size() << endl;

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

                        ViewCellPvsMap::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 VspBspViewCellsManager::MergeVspBspLeafViewCells(VspBspLeaf *front, 
                                                                                                          VspBspLeaf *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();

        // TODO
        /*vector<VspBspLeaf *> fLeaves = fVc->mBspLeaves;
        vector<VspBspLeaf *> bLeaves = bVc->mBspLeaves;

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

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

        if ((fvc == mVspBspTree->GetRootCell()) || 
                (bvc == mVspBspTree->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;
}