source: GTP/trunk/Lib/Vis/Preprocessing/src/ViewCellsManager.cpp @ 1966

#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 "HierarchyManager.h"
#include "Exporter.h"
#include "VspBspTree.h"
#include "ViewCellsParser.h"
#include "Beam.h"
#include "VssPreprocessor.h"
#include "RssPreprocessor.h"
#include "BoundingBoxConverter.h"
#include "GlRenderer.h"
#include "ResourceManager.h"
#include "IntersectableWrapper.h"
#include "VspTree.h"
#include "OspTree.h"
#include "BvHierarchy.h"
#include "SamplingStrategy.h"
#include "SceneGraph.h"


// $$JB HACK
#define KD_PVS_AREA (1e-5f)

#define USE_RAY_LENGTH_AS_CONTRIBUTION 0
#define DIST_WEIGHTED_CONTRIBUTION 0
#define SUM_RAY_CONTRIBUTIONS 1
#define AVG_RAY_CONTRIBUTIONS 0
#define CONTRIBUTION_RELATIVE_TO_PVS_SIZE 0
#define PVS_ADD_DIRTY 1

namespace GtpVisibilityPreprocessor {


// HACK
const static bool SAMPLE_AFTER_SUBDIVISION = true;
//const static bool CLAMP_TO_BOX = false;
const static bool CLAMP_TO_BOX = true;


int ViewCellsManager::sRenderCostEvaluationType = 0;


template <typename T> class myless
{
public:
        //bool operator() (HierarchyNode *v1, HierarchyNode *v2) const
        bool operator() (T v1, T v2) const
        {
                return (v1->GetMergeCost() < v2->GetMergeCost());
        }
};


ViewCellsManager::ViewCellsManager(ViewCellsTree *viewCellsTree):
mRenderer(NULL),
mInitialSamples(0),
mConstructionSamples(0),
mPostProcessSamples(0),
mVisualizationSamples(0),
mTotalAreaValid(false),
mTotalArea(0.0f),
mViewCellsFinished(false),
mMaxPvsSize(9999999),
mMinPvsSize(0),
mMaxPvsRatio(1.0),
mViewCellPvsIsUpdated(false),
mPreprocessor(NULL),
mViewCellsTree(viewCellsTree),
mUsePredefinedViewCells(false)
{
        mViewSpaceBox.Initialize();
        ParseEnvironment();

        mViewCellsTree->SetViewCellsManager(this);
}


int ViewCellsManager::CastPassSamples2(const int samplesPerPass, 
                                                                           VssRayContainer &passSamples) const
{
        long startTime = GetTime();

        SimpleRayContainer simpleRays;
        
        simpleRays.reserve(samplesPerPass);
        passSamples.reserve(samplesPerPass * 2); // always creates double rays

        // create one third of each type
        int castRays = 0;

        mMixtureDistribution->GenerateSamples(mSamplesPerPass, simpleRays);

        cout << "generated " << (int)simpleRays.size() << " samples in " 
                 << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;

        startTime = GetTime();

        // shoot simple ray and add it to importance samples
        mPreprocessor->CastRays(simpleRays, passSamples, true);

    cout << "cast " <<  samplesPerPass << " samples in " 
                 << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;

        mMixtureDistribution->ComputeContributions(passSamples);

        return (int)passSamples.size();
}


void ViewCellsManager::ParseEnvironment()
{
        // visualization stuff
        Environment::GetSingleton()->GetBoolValue("ViewCells.Visualization.exportRays", mExportRays);
        Environment::GetSingleton()->GetBoolValue("ViewCells.Visualization.exportGeometry", mExportGeometry);
        Environment::GetSingleton()->GetFloatValue("ViewCells.maxPvsRatio", mMaxPvsRatio);
        
        Environment::GetSingleton()->GetBoolValue("ViewCells.processOnlyValidViewCells", mOnlyValidViewCells);

        Environment::GetSingleton()->GetIntValue("ViewCells.Construction.samples", mConstructionSamples);
        Environment::GetSingleton()->GetIntValue("ViewCells.PostProcess.samples", mPostProcessSamples);
        Environment::GetSingleton()->GetBoolValue("ViewCells.PostProcess.useRaysForMerge", mUseRaysForMerge);

        Environment::GetSingleton()->GetIntValue("ViewCells.Visualization.samples", mVisualizationSamples);

        Environment::GetSingleton()->GetIntValue("ViewCells.Construction.samplesPerPass", mSamplesPerPass);
        Environment::GetSingleton()->GetBoolValue("ViewCells.exportToFile", mExportViewCells);
        
        Environment::GetSingleton()->GetIntValue("ViewCells.active", mNumActiveViewCells);
        Environment::GetSingleton()->GetBoolValue("ViewCells.PostProcess.compress", mCompressViewCells);
        Environment::GetSingleton()->GetBoolValue("ViewCells.Visualization.useClipPlane", mUseClipPlaneForViz);
        Environment::GetSingleton()->GetBoolValue("ViewCells.PostProcess.merge", mMergeViewCells);
        Environment::GetSingleton()->GetBoolValue("ViewCells.evaluateViewCells", mEvaluateViewCells);
        Environment::GetSingleton()->GetBoolValue("ViewCells.showVisualization", mShowVisualization);
        Environment::GetSingleton()->GetIntValue("ViewCells.Filter.maxSize", mMaxFilterSize);
        Environment::GetSingleton()->GetFloatValue("ViewCells.Filter.width", mFilterWidth);
        Environment::GetSingleton()->GetIntValue("ViewCells.renderCostEvaluationType", sRenderCostEvaluationType);

        Environment::GetSingleton()->GetBoolValue("ViewCells.exportBboxesForPvs", mExportBboxesForPvs);
        Environment::GetSingleton()->GetBoolValue("ViewCells.exportPvs", mExportPvs);

        Environment::GetSingleton()->GetBoolValue("ViewCells.useKdPvs", mUseKdPvs);

        char buf[100];
        Environment::GetSingleton()->GetStringValue("ViewCells.samplingType", buf);

        // mix of sampling strategies
        if (0)
        {
                mStrategies.push_back(SamplingStrategy::OBJECT_DIRECTION_BASED_DISTRIBUTION);
        }
        else
        {
                /*mStrategies.push_back(SamplingStrategy::OBJECT_BASED_DISTRIBUTION);
                mStrategies.push_back(SamplingStrategy::REVERSE_VIEWSPACE_BORDER_BASED_DISTRIBUTION);
                mStrategies.push_back(SamplingStrategy::REVERSE_OBJECT_BASED_DISTRIBUTION);
                */
        
                mStrategies.push_back(SamplingStrategy::SPATIAL_BOX_BASED_DISTRIBUTION);
        }
                
    Debug << "casting strategies: ";
        for (int i = 0; i < (int)mStrategies.size(); ++ i)
                Debug << mStrategies[i] << " ";
        Debug << endl;

        // now decode distribution string
        char buff[1024];
        Environment::GetSingleton()->GetStringValue("RssPreprocessor.distributions", buff);

        mMixtureDistribution = new MixtureDistribution(*mPreprocessor);
        mMixtureDistribution->Construct(buff);


        // sampling type for view cells construction samples
        if (strcmp(buf, "object") == 0)
        {
                mSamplingType = SamplingStrategy::OBJECT_BASED_DISTRIBUTION;
        }
        else if (strcmp(buf, "box") == 0)
        {
                mSamplingType = SamplingStrategy::SPATIAL_BOX_BASED_DISTRIBUTION;
        }
        else if (strcmp(buf, "directional") == 0)
        {
                mSamplingType = SamplingStrategy::DIRECTION_BASED_DISTRIBUTION;
        }
        else if (strcmp(buf, "object_directional") == 0)
        {
                mSamplingType = SamplingStrategy::OBJECT_DIRECTION_BASED_DISTRIBUTION;
        }
        else if (strcmp(buf, "reverse_object") == 0)
        {
                mSamplingType = SamplingStrategy::REVERSE_OBJECT_BASED_DISTRIBUTION;
        }
        /*else if (strcmp(buf, "interior") == 0)
        {
                mSamplingType = Preprocessor::OBJECTS_INTERIOR_DISTRIBUTION;
        }*/
        else
        {
                Debug << "error! wrong sampling type" << endl;
                exit(0);
        }

        // sampling type for evaluation samples
        Environment::GetSingleton()->GetStringValue("ViewCells.Evaluation.samplingType", buf);
        
        if (strcmp(buf, "object") == 0)
        {
                mEvaluationSamplingType = SamplingStrategy::OBJECT_BASED_DISTRIBUTION;
        }
        else if (strcmp(buf, "box") == 0)
        {
                mEvaluationSamplingType = SamplingStrategy::SPATIAL_BOX_BASED_DISTRIBUTION;
        }
        else if (strcmp(buf, "directional") == 0)
        {
                mEvaluationSamplingType = SamplingStrategy::DIRECTION_BASED_DISTRIBUTION;
        }
        else if (strcmp(buf, "object_directional") == 0)
        {
                mEvaluationSamplingType = SamplingStrategy::OBJECT_DIRECTION_BASED_DISTRIBUTION;
        }
        else if (strcmp(buf, "reverse_object") == 0)
        {
                mEvaluationSamplingType = SamplingStrategy::REVERSE_OBJECT_BASED_DISTRIBUTION;
        }
        /*else if (strcmp(buf, "interior") == 0)
        {
                mEvaluationSamplingType = SamplingStrategy::OBJECTS_INTERIOR_DISTRIBUTION;
        }*/
        else
        {
                mEvaluationSamplingType = -1;
                Debug << "error! wrong sampling type" << endl;
                exit(0);
        }

        Environment::GetSingleton()->GetStringValue("ViewCells.renderCostEvaluationType", buf);
        
        if (strcmp(buf, "perobject") == 0)
        {
                sRenderCostEvaluationType = ViewCellsManager::PER_OBJECT;
        }
        else if (strcmp(buf, "pertriangle") == 0)
        {
                sRenderCostEvaluationType = ViewCellsManager::PER_TRIANGLE;
        }
        else 
        {
                Debug << "error! wrong sampling type" << endl;
                exit(0);
        }

    Environment::GetSingleton()->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 << "************ View Cells Manager options ***************" << endl;
        Debug << "color code: " << mColorCode << endl;

        Debug << "export rays: " << mExportRays << endl;
        Debug << "export geometry: " << mExportGeometry << endl;
        Debug << "max pvs ratio: " << mMaxPvsRatio << endl;
        
        Debug << "process only valid view cells: " << mOnlyValidViewCells << endl;
        Debug << "construction samples: " << mConstructionSamples << endl;
        Debug << "post process samples: " << mPostProcessSamples << endl;
        Debug << "post process use rays for merge: " << mUseRaysForMerge << endl;
        Debug << "visualization samples: " << mVisualizationSamples << endl;
        Debug << "construction samples per pass: " << mSamplesPerPass << endl;
        Debug << "export to file: " << mExportViewCells << endl;
        
        Debug << "active view cells: " << mNumActiveViewCells << endl;
        Debug << "post process compress: " << mCompressViewCells << endl;
        Debug << "visualization use clipPlane: " << mUseClipPlaneForViz << endl; 
        Debug << "post process merge: " << mMergeViewCells << endl;
        Debug << "evaluate view cells: " << mEvaluateViewCells << endl;
        Debug << "sampling type: " << mSamplingType << endl;
        Debug << "render cost evaluation type: " << sRenderCostEvaluationType << endl;
        Debug << "evaluation sampling type: " << mEvaluationSamplingType << endl;
        Debug << "show visualization: " << mShowVisualization << endl;
        Debug << "filter width: " << mFilterWidth << endl;
        Debug << "sample after subdivision: " << SAMPLE_AFTER_SUBDIVISION << endl;

        Debug << "export bounding boxes: " << mExportBboxesForPvs << endl;
        Debug << "export pvs for view cells: " << mExportPvs << endl;
        Debug << "use kd pvs " << mUseKdPvs << endl;
        Debug << endl;
}


ViewCellsManager::~ViewCellsManager()
{
        // HACK: if view cells tree does not 
        // handle view cells, we have to do it here
        // question: rather create view cells resource manager?
        if (!ViewCellsTreeConstructed())
        {
                CLEAR_CONTAINER(mViewCells);
        }
        else
        {
                DEL_PTR(mViewCellsTree);
        }

        DEL_PTR(mMixtureDistribution);
}


Intersectable *
ViewCellsManager::GetIntersectable(const VssRay &ray, const bool isTermination) const
{
        if (mUseKdPvs)
        {
                float area = GetPreprocessor()->mKdTree->GetBox().SurfaceArea()*KD_PVS_AREA;
                KdNode *node = GetPreprocessor()->mKdTree->GetNode(isTermination ?
                                                                                                                 ray.mTermination : ray.mOrigin,
                                                                                                                 area);
        return GetPreprocessor()->mKdTree->GetOrCreateKdIntersectable(node);
        }
        else
        {
                return isTermination ? ray.mTerminationObject : ray.mOriginObject;
        }
}


void
ViewCellsManager::CollectObjects(const AxisAlignedBox3 &box, ObjectContainer &objects)
{
  GetPreprocessor()->mKdTree->CollectObjects(box, objects);
}

AxisAlignedBox3 ViewCellsManager::GetViewCellBox(ViewCell *vc)
{
  Mesh *m = vc->GetMesh();
  
  if (m) 
  {
          m->ComputeBoundingBox();
          return m->mBox;
  }

  AxisAlignedBox3 box;
  box.Initialize();
  
  if (!vc->IsLeaf()) {
        ViewCellInterior *vci = (ViewCellInterior *) vc;
        
        ViewCellContainer::iterator it = vci->mChildren.begin();
        for (; it != vci->mChildren.end(); ++it) {
          box.Include(GetViewCellBox(*it));
        }
  }
  
  return box;
}


int ViewCellsManager::CastPassSamples(const int samplesPerPass, 
                                                                          const vector<int> &strategies,
                                                                          VssRayContainer &passSamples
                                                                          ) const
{
        long startTime = GetTime();

        SimpleRayContainer simpleRays;
        
        simpleRays.reserve(samplesPerPass);
        passSamples.reserve(samplesPerPass * 2); // always creates double rays

        // create one third of each type
        int castRays = 0;
        
        const int numRaysPerPass = samplesPerPass / (int)strategies.size();
        vector<int>::const_iterator iit, iit_end = strategies.end();

        for (iit = strategies.begin(); iit != iit_end; ++ iit)
        {
                const int stype = *iit;
                const int newRays = 
                        mPreprocessor->GenerateRays(numRaysPerPass, stype, simpleRays);

                cout << "cast " << newRays << " rays of strategy " << stype << endl;
                castRays += newRays;
        }

        cout << "generated " << samplesPerPass << " samples in " 
                 << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;

        startTime = GetTime();

        // shoot simple ray and add it to importance samples
        mPreprocessor->CastRays(simpleRays, passSamples, true);
        cout << "cast " <<  samplesPerPass << " samples in " 
                 << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;

        return (int)passSamples.size();
}


/// helper function which destroys rays or copies them into the output ray container
inline void disposeRays(VssRayContainer &rays, VssRayContainer *outRays)
{
        cout << "disposing samples ... ";
        long startTime = GetTime();
        int n = (int)rays.size();

        if (outRays)
        {
                VssRayContainer::const_iterator it, it_end = rays.end();
                for (it = rays.begin(); it != it_end; ++ it)
                {
                        outRays->push_back(*it);
                }
        }
        else
        {
                VssRayContainer::const_iterator it, it_end = rays.end();
                for (it = rays.begin(); it != it_end; ++ it)
                {
                        if (!(*it)->IsActive())
                                delete (*it);
                }
        }

        cout << "finished" << endl;
        Debug << "disposed " << n << " samples in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
}


int ViewCellsManager::Construct(Preprocessor *preprocessor, VssRayContainer *outRays)
{
        int numSamples = 0;

        SimpleRayContainer simpleRays;
        VssRayContainer initialSamples;

        // store pointer to preprocessor for further use during construction
        mPreprocessor = preprocessor;
        

        ///////////////////////////////////////////////////////
        //-- Initial sampling for the construction of the view cell hierarchy. 
        //-- We use uniform sampling / box based sampling.
        
        long startTime = GetTime();
        cout << "view cell construction: casting " << mInitialSamples << " initial samples ... " << endl;

        // cast initial samples
        
        // mix of sampling strategies
        vector<int>dummy;
        //dummy.push_back(SamplingStrategy::OBJECT_BASED_DISTRIBUTION);
        //dummy.push_back(SamplingStrategy::SPATIAL_BOX_BASED_DISTRIBUTION);
        //dummy.push_back(SamplingStrategy::REVERSE_OBJECT_BASED_DISTRIBUTION);

        CastPassSamples(mInitialSamples, mStrategies, initialSamples);

        cout << "finished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;

        // construct view cells
        ConstructSubdivision(preprocessor->mObjects, initialSamples);

        // initial samples count for overall samples ...
        numSamples += mInitialSamples;

        // rays can be passed or deleted
        disposeRays(initialSamples, outRays);

        cout << "time needed for initial construction: "
                 << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;

        Debug << "time needed for initial construction: "
                  << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;

        // collect view cells and compute statistics
        ResetViewCells();


        ///////////////////
        //-- Initial hierarchy construction finished.
        //-- We can do some stats and visualization
        
        if (0)
        {
                //-- export initial view cell partition
                Debug << "\nView cells after initial sampling:\n" << mCurrentViewCellsStats << endl;

                const string filename("viewcells.wrl");
                Exporter *exporter = Exporter::GetExporter(filename.c_str());
        
                if (exporter)
                {
                        cout << "exporting initial view cells (=leaves) to " << filename.c_str() << " ... ";

                        if (mExportGeometry)
                        {
                                exporter->ExportGeometry(preprocessor->mObjects);
                        }

                        exporter->SetWireframe();
                        ExportViewCellsForViz(exporter, NULL, mColorCode, GetClipPlane());

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


        //////////////////////
        //-- Cast some more sampling after initial construction.
        //-- The additional rays can be used to gain
        //-- some more information before the bottom-up merge
        //-- note: guided rays could be used for this task

        // time spent after construction of the initial partition
        startTime = GetTime();
        const int n = mConstructionSamples; //+initialSamples;

        while (numSamples < n)
        {
                cout << "casting " << mSamplesPerPass << " samples of " << n << " ... ";
                Debug << "casting " << mSamplesPerPass << " samples of " << n << " ... ";

                VssRayContainer constructionSamples;

                // cast new samples
                numSamples += CastPassSamples(mSamplesPerPass, 
                                                                          mStrategies,
                                                                          constructionSamples);

                cout << "finished" << endl;
                cout << "computing sample contribution for " << (int)constructionSamples.size() << " samples ... ";

                // computes sample contribution of cast rays TODO: leak?
                if (SAMPLE_AFTER_SUBDIVISION)
                        ComputeSampleContributions(constructionSamples, true, false);

                cout << "finished" << endl;

                disposeRays(constructionSamples, outRays);
                cout << "total samples: " << numSamples << endl;
        }

        if (0)
        {
                ///////////////
                //-- Get stats after the additional sampling step
                //-- and before the bottom-up merge step

                EvaluateViewCellsStats();
                Debug << "\noriginal view cell partition before post process:\n" 
                          << mCurrentViewCellsStats << endl;
        
                mRenderer->RenderScene();
                SimulationStatistics ss;
                dynamic_cast<RenderSimulator *>(mRenderer)->GetStatistics(ss);

                Debug << ss << endl;
        }

        ////////////////////
        //-- post processing of the initial construction
        //-- We can bottom-up merge the view cells in this step
        //-- We can additionally cast some post processing sample rays.
        //-- These rays can be used to store the view cells with the rays

        VssRayContainer postProcessSamples;
        cout << "casting " << mPostProcessSamples << " post processing samples ... ";
        
        CastPassSamples(mPostProcessSamples, mStrategies, postProcessSamples);

        cout << "finished" << endl;
        cout << "starting post processing and visualization" << endl;

        // store view cells with rays for post processing?
        const bool storeViewCells = true;

        if (SAMPLE_AFTER_SUBDIVISION)
                ComputeSampleContributions(postProcessSamples, true, storeViewCells);

        PostProcess(preprocessor->mObjects, postProcessSamples);

        const float secs = TimeDiff(startTime, GetTime()) * 1e-3f;
        cout << "post processing (=merge) finished in " << secs << " secs" << endl;

        Debug << "post processing time: " << secs << endl;
        disposeRays(postProcessSamples, outRays);


        ////////////////
        //-- Evaluation of the resulting view cell partition. 
        //-- We cast a number of new samples and measure the render cost

        if (mEvaluateViewCells)
        {
                EvalViewCellPartition();
        }
        
        /////////////////
        //-- Show some visualizations

        if (mShowVisualization)
        {
                if (0)
                {
                        mStrategies.clear();
                        mStrategies.push_back(SamplingStrategy::VIEWCELL_BORDER_BASED_DISTRIBUTION);
                }

                ///////////////
                //-- visualization rays, e.g., to show some samples in the scene
                
                VssRayContainer visSamples;
                int numSamples = CastPassSamples(mVisualizationSamples,
                                                                                 mStrategies, 
                                                                                 visSamples);

                if (SAMPLE_AFTER_SUBDIVISION)
                        ComputeSampleContributions(visSamples, true, storeViewCells);

                // various visualizations
                Visualize(preprocessor->mObjects, visSamples);

                disposeRays(visSamples, outRays);
        }

        // recalculate view cells
        EvaluateViewCellsStats();

        if (1) CompressViewCells();

        // write view cells to disc
        if (mExportViewCells)
        {
                char filename[100];

                Environment::GetSingleton()->GetStringValue("ViewCells.filename", filename);
                ExportViewCells(filename, mExportPvs, mPreprocessor->mObjects);
        }

        return numSamples;
}


AxisAlignedPlane *ViewCellsManager::GetClipPlane()
{
        return mUseClipPlaneForViz ? &mClipPlaneForViz : NULL;
}


void ViewCellsManager::EvalViewCellHistogram(const string filename, 
                                                                                         const int nViewCells)
{
        std::ofstream outstream;
        outstream.open(filename.c_str());

        ViewCellContainer viewCells;
        // $$ JB hack - the collect best viewcells does not work?
#if 1
        mViewCellsTree->CollectBestViewCellSet(viewCells, nViewCells);
#else
        viewCells = mViewCells;
#endif

        float maxRenderCost, minRenderCost;

        // sort by render cost
        sort(viewCells.begin(), viewCells.end(), ViewCell::SmallerRenderCost);

        minRenderCost = viewCells.front()->GetRenderCost();
        maxRenderCost = viewCells.back()->GetRenderCost();

        Debug << "histogram min rc: " << minRenderCost << " max rc: " << maxRenderCost << endl;

    int histoIntervals;
        Environment::GetSingleton()->GetIntValue("Preprocessor.histogram.intervals", histoIntervals);
        const int intervals = min(histoIntervals, (int)viewCells.size());

        int histoMaxVal;
        Environment::GetSingleton()->GetIntValue("Preprocessor.histogram.maxValue", histoMaxVal);
        maxRenderCost = min((float)histoMaxVal, maxRenderCost);

        
        const float range = maxRenderCost - minRenderCost;
        const float stepSize = range / (float)intervals;

        float currentRenderCost = minRenderCost;//(int)ceil(minRenderCost);

        const float totalRenderCost = mViewCellsTree->GetRoot()->GetRenderCost();
        const float totalVol = GetViewSpaceBox().GetVolume();
        //const float totalVol = mViewCellsTree->GetRoot()->GetVolume();

        int j = 0;
        int i = 0;
        
        ViewCellContainer::const_iterator it = viewCells.begin(), it_end = viewCells.end();             

        // count for integral
        float volSum = 0;
        int smallerCostSum = 0;
        
        // note can skip computations for view cells already 
        // evaluated and delete them from vector ...
    while (1)
        {
                // count for histogram value
                float volDif = 0;
                int smallerCostDif = 0;

                while ((i < (int)viewCells.size()) && (viewCells[i]->GetRenderCost() < currentRenderCost))
                {
                        volSum += viewCells[i]->GetVolume();
                        volDif += viewCells[i]->GetVolume();

                        ++ i;
                        ++ smallerCostSum;
                        ++ smallerCostDif;
                }
                
                if ((i >= (int)viewCells.size()) || (currentRenderCost >= maxRenderCost))
                        break;
                
                const float rcRatio = currentRenderCost / maxRenderCost;
                const float volRatioSum = volSum / totalVol;
                const float volRatioDif = volDif / totalVol;

                outstream << "#Pass\n" << j ++ << endl;
                outstream << "#RenderCostRatio\n" << rcRatio << endl;
                outstream << "#WeightedCost\n" << currentRenderCost / totalVol << endl;
                outstream << "#ViewCellsDif\n" << smallerCostDif << endl;
                outstream << "#ViewCellsSum\n" << smallerCostSum << endl;       
                outstream << "#VolumeDif\n" << volRatioDif << endl << endl;
                outstream << "#VolumeSum\n" << volRatioSum << endl << endl;

                // increase current render cost
                currentRenderCost += stepSize;
        }

        outstream.close();
}


ViewCellsManager *ViewCellsManager::LoadViewCells(const string &filename, 
                                                                                                  ObjectContainer *objects,
                                                                                                  bool finalizeViewCells,
                                                                                                  BoundingBoxConverter *bconverter)
                                                                                                 
{
        ViewCellsParser parser;
        ViewCellsManager *vm = NULL;

        const long startTime = GetTime();
        bool success = parser.ParseViewCellsFile(filename, &vm, objects, bconverter);

        cout<<"viewcells parsed "<<endl<<flush;
        
        if (success)
        {
                //vm->ResetViewCells();
                //hack
                vm->mViewCells.clear();
                ViewCellContainer leaves;
                vm->mViewCellsTree->CollectLeaves(vm->mViewCellsTree->GetRoot(), leaves);

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

                for (it = leaves.begin(); it != it_end; ++ it)
                {
                        vm->mViewCells.push_back(*it);
                }
                vm->mViewCellsFinished = true;
                vm->mMaxPvsSize = (int)objects->size();

                if (finalizeViewCells)
                {
                        // create the meshes and compute volumes
                        vm->FinalizeViewCells(true);
                        // vm->mViewCellsTree->AssignRandomColors();
                }

                Debug << (int)vm->mViewCells.size() << " view cells loaded in "
                          << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
        }
        else
        {
                Debug << "Error: loading view cells failed!" << endl;
                DEL_PTR(vm);
        }

        return vm;
}


bool VspBspViewCellsManager::ExportViewCells(const string filename, 
                                                                                         const bool exportPvs, 
                                                                                         const ObjectContainer &objects)
{
        if (!ViewCellsConstructed() || !ViewCellsTreeConstructed())
        {
                return false;
        }

        cout << "exporting view cells to xml ... ";

        OUT_STREAM stream(filename.c_str());

        // for output we need unique ids for each view cell
        CreateUniqueViewCellIds();

        stream << "<?xml version=\"1.0\" encoding=\"UTF-8\"?>"<<endl;
        stream << "<VisibilitySolution>" << endl;

        if (exportPvs) 
        {
                //-- export bounding boxes
                stream << "<BoundingBoxes>" << endl;

                if (mUseKdPvs)
                {
                        vector<KdIntersectable *>::iterator kit, kit_end = GetPreprocessor()->mKdTree->mKdIntersectables.end();

                        int id = 0;
                        for (kit = GetPreprocessor()->mKdTree->mKdIntersectables.begin(); kit != kit_end; ++ kit, ++ id)
                        {
                                Intersectable *obj = *kit;
                                const AxisAlignedBox3 box = obj->GetBox();
                  
                                obj->SetId(id);
        
                                stream << "<BoundingBox" << " id=\"" << id << "\""
                                           << " min=\"" << box.Min().x << " " << box.Min().y << " " << box.Min().z << "\""
                                           << " max=\"" << box.Max().x << " " << box.Max().y << " " << box.Max().z << "\" />" << endl;
                        }
                }
                else
                {
                        ObjectContainer::const_iterator oit, oit_end = objects.end();
                
                        for (oit = objects.begin(); oit != oit_end; ++ oit)
                        {
                                const AxisAlignedBox3 box = (*oit)->GetBox();

                                ////////////
                                //-- the bounding boxes

                                stream << "<BoundingBox" << " id=\"" << (*oit)->GetId() << "\""
                                           << " min=\"" << box.Min().x << " " << box.Min().y << " " << box.Min().z << "\""
                                           << " max=\"" << box.Max().x << " " << box.Max().y << " " << box.Max().z << "\" />" << endl;
                        }
                }

                stream << "</BoundingBoxes>" << endl;
        }

        
        /////////////
        //-- export the view cells and the pvs

        const int numViewCells = mCurrentViewCellsStats.viewCells;
        stream << "<ViewCells number=\"" << numViewCells << "\" >" << endl;

        mViewCellsTree->Export(stream, exportPvs);

        stream << "</ViewCells>" << endl;


        //////////
        //-- export the view space hierarchy
        
        stream << "<ViewSpaceHierarchy type=\"bsp\""
                   << " min=\"" << mViewSpaceBox.Min().x << " " << mViewSpaceBox.Min().y << " " << mViewSpaceBox.Min().z << "\""
                   << " max=\"" << mViewSpaceBox.Max().x << " " << mViewSpaceBox.Max().y << " " << mViewSpaceBox.Max().z << "\">" << endl;

        mVspBspTree->Export(stream);
        stream << "</ViewSpaceHierarchy>" << endl;

        stream << "</VisibilitySolution>" << endl;

        stream.close();
        cout << "finished" << endl;

        return true;
}


void ViewCellsManager::EvalViewCellHistogramForPvsSize(const string filename, 
                                                                                                           const int nViewCells)
{
        std::ofstream outstream;
        outstream.open(filename.c_str());

        ViewCellContainer viewCells;
        
        // $$ JB hack - the collect best viewcells does not work?
#if 0
        mViewCellsTree->CollectBestViewCellSet(viewCells, nViewCells);
#else
        viewCells = mViewCells;
#endif
        ViewCellContainer::iterator it = viewCells.begin(), it_end = viewCells.end();           
        for (; it != it_end; ++it) 
        {
                if (1)
                        (*it)->UpdatePvsCost();
                else
                        (*it)->SetPvsCost((float)(*it)->GetFilteredPvsSize());
        }

        float maxPvs, maxVal, minVal;
        
        // sort by pvs size
        sort(viewCells.begin(), viewCells.end(), ViewCell::SmallerPvs);

        maxPvs = viewCells.back()->GetPvsCost();
        minVal = 0;

        // hack: normalize pvs size
        int histoMaxVal;
        Environment::GetSingleton()->GetIntValue("Preprocessor.histogram.maxValue", histoMaxVal);
        maxVal = max((float)histoMaxVal, maxPvs);
                
        Debug << "histogram minpvssize: " << minVal << " maxpvssize: " << maxVal 
                << " real maxpvs " << maxPvs << endl;

        int histoIntervals;
        Environment::GetSingleton()->GetIntValue("Preprocessor.histogram.intervals", histoIntervals);
        const int intervals = min(histoIntervals, (int)viewCells.size());

        const float range = maxVal - minVal;
        int stepSize = (int)(range / intervals);

        // set step size to avoid endless loop
        if (!stepSize) stepSize = 1;
        
        Debug << "intervals " << histoIntervals << endl;
        Debug << "stepsize: " << stepSize << endl;
        cout << "intervals " << histoIntervals << endl;
        cout << "stepsize: " << stepSize << endl;

        const float totalRenderCost = mViewCellsTree->GetRoot()->GetRenderCost();
        const float totalVol = GetViewSpaceBox().GetVolume();

        float currentPvs = minVal;
        
        int i = 0;
        int j = 0;
        float volSum = 0;
        int smallerSum = 0;

        it = viewCells.begin();
        
        for (int j = 0; j < intervals; ++ j)
        {
                float volDif = 0;
                int smallerDif = 0;

                while ((i < (int)viewCells.size()) && 
                           (viewCells[i]->GetPvsCost() < currentPvs))
                {
                        volDif += viewCells[i]->GetVolume();
                        volSum += viewCells[i]->GetVolume();

                        ++ i;
                        ++ smallerDif;
                        ++ smallerSum;
                }
                
                //              if (0 && (i < (int)viewCells.size()))
                //                Debug << "new pvs cost increase: " << mViewCellsTree->GetPvsCost(viewCells[i]) 
                //                              << " " << currentPvs << endl;
                
                const float volRatioDif = volDif / totalVol;
                const float volRatioSum = volSum / totalVol;

                outstream << "#Pass\n" << j << endl;
                outstream << "#Pvs\n" << currentPvs << endl;
                outstream << "#ViewCellsDif\n" << smallerDif << endl;
                outstream << "#ViewCellsSum\n" << smallerSum << endl;   
                outstream << "#VolumeDif\n" << volRatioDif << endl << endl;
                outstream << "#VolumeSum\n" << volRatioSum << endl << endl;
        
                //-- increase current pvs size to define next interval
                currentPvs += stepSize;
        }

        outstream.close();
}


void ViewCellsManager::EvalViewCellHistogramForPvsSize(const string filename, 
                                                                                                           ViewCellContainer &viewCells)
{
        std::ofstream outstream;
        outstream.open(filename.c_str());

        float maxPvs, maxVal, minVal;
        
        // sort by pvs size
        sort(viewCells.begin(), viewCells.end(), ViewCell::SmallerPvs);

        maxPvs = viewCells.back()->GetPvsCost();
        minVal = 0;

        // hack: normalize pvs size
        int histoMaxVal;
        Environment::GetSingleton()->GetIntValue("Preprocessor.histogram.maxValue", histoMaxVal);
        maxVal = max((float)histoMaxVal, maxPvs);
                
        Debug << "histogram minpvssize: " << minVal << " maxpvssize: " << maxVal 
                << " real maxpvs " << maxPvs << endl;

        int histoIntervals;
        Environment::GetSingleton()->GetIntValue("Preprocessor.histogram.intervals", histoIntervals);
        const int intervals = min(histoIntervals, (int)viewCells.size());

        const float range = maxVal - minVal;
        int stepSize = (int)(range / intervals);

        // set step size to avoid endless loop
        if (!stepSize) stepSize = 1;
        
        Debug << "intervals " << histoIntervals << endl;
        Debug << "stepsize: " << stepSize << endl;
        cout << "intervals " << histoIntervals << endl;
        cout << "stepsize: " << stepSize << endl;

        const float totalRenderCost = mViewCellsTree->GetRoot()->GetRenderCost();
        const float totalVol = GetViewSpaceBox().GetVolume();

        float currentPvs = minVal;
        
        int i = 0;
        int j = 0;
        float volSum = 0;
        int smallerSum = 0;

        //ViewCellContainer::const_iterator it = viewCells.begin(), it_end = viewCells.end();   
        
        for (int j = 0; j < intervals; ++ j)
        {
                float volDif = 0;
                int smallerDif = 0;

                while ((i < (int)viewCells.size()) && 
                           (viewCells[i]->GetPvsCost() < currentPvs))
                {
                        volDif += viewCells[i]->GetVolume();
                        volSum += viewCells[i]->GetVolume();

                        ++ i;
                        ++ smallerDif;
                        ++ smallerSum;
                }
                
                //              if (0 && (i < (int)viewCells.size()))
                //                Debug << "new pvs cost increase: " << mViewCellsTree->GetPvsCost(viewCells[i]) 
                //                              << " " << currentPvs << endl;
                
                const float volRatioDif = volDif / totalVol;
                const float volRatioSum = volSum / totalVol;

                outstream << "#Pass\n" << j << endl;
                outstream << "#Pvs\n" << currentPvs << endl;
                outstream << "#ViewCellsDif\n" << smallerDif << endl;
                outstream << "#ViewCellsSum\n" << smallerSum << endl;   
                outstream << "#VolumeDif\n" << volRatioDif << endl << endl;
                outstream << "#VolumeSum\n" << volRatioSum << endl << endl;
        
                //-- increase current pvs size to define next interval
                currentPvs += stepSize;
        }

        outstream.close();
}


bool ViewCellsManager::GetExportPvs() const 
{
        return mExportPvs;
}


void ViewCellsManager::ResetPvs()
{
        if (ViewCellsTreeConstructed())
        {
                mViewCellsTree->ResetPvs();
        }
        else
        {
                cout << "view cells tree not constructed" << endl;
        }
}


void ViewCellsManager::ExportStats(const string &fileName)
{
        mViewCellsTree->ExportStats(fileName);
}


void ViewCellsManager::EvalViewCellPartition()
{
        int samplesPerPass;
        int numSamples;
        int castSamples = 0;
        char str[64]; 
        int oldSamples = 0;

        int samplesForStats;

        Environment::GetSingleton()->GetIntValue("ViewCells.Evaluation.samplesPerPass", samplesPerPass);
        Environment::GetSingleton()->GetIntValue("ViewCells.Evaluation.samplesForStats", samplesForStats);
        Environment::GetSingleton()->GetIntValue("ViewCells.Evaluation.samples", numSamples);

        char statsPrefix[100];
        Environment::GetSingleton()->GetStringValue("ViewCells.Evaluation.statsPrefix", statsPrefix);

        Debug << "view cell evaluation samples per pass: " << samplesPerPass << endl;
        Debug << "view cell evaluation samples: " << numSamples << endl;
        Debug << "view cell stats prefix: " << statsPrefix << endl;

        cout << "reseting pvs ... ";
                
        const bool startFromZero = true;

        // reset pvs and start over from zero
        if (startFromZero)
        {
                mViewCellsTree->ResetPvs();
        }
        else // start from current sampless
        {
                // statistics before casting more samples
                cout << "compute new statistics ... ";
                sprintf(str, "-%09d-eval.log", castSamples);
                string fName = string(statsPrefix) + string(str);

                mViewCellsTree->ExportStats(fName);
                cout << "finished" << endl;
        }

        cout << "finished" << endl;
    cout << "Evaluating view cell partition ... " << endl;

        while (castSamples < numSamples)
        {               
                ///////////////
                //-- we have to use uniform sampling strategy for construction rays

                VssRayContainer evaluationSamples;
                const int samplingType = mEvaluationSamplingType;

                long startTime = GetTime();

                cout << "casting " << samplesPerPass << " samples ... ";
                Debug << "casting " << samplesPerPass << " samples ... ";

                CastPassSamples(samplesPerPass, mStrategies, evaluationSamples);
                
                castSamples += samplesPerPass;

                Real timeDiff = TimeDiff(startTime, GetTime());
                
                cout << "finished in " << timeDiff * 1e-3f << " secs" << endl;
                cout << "computing sample contributions of " << (int)evaluationSamples.size()  << " samples ... ";
                
                Debug << "finished in " << timeDiff * 1e-3f << " secs" << endl;
                Debug << "computing sample contributions of " << (int)evaluationSamples.size()  << " samples ... ";

                startTime = GetTime();

                ComputeSampleContributions(evaluationSamples, true, false);

                timeDiff = TimeDiff(startTime, GetTime());
                cout << "finished in " << timeDiff * 1e-3 << " secs" << endl;
                Debug << "finished in " << timeDiff * 1e-3 << " secs" << endl;

                if ((castSamples >= samplesForStats + oldSamples) || (castSamples >= numSamples))
                {
                        oldSamples += samplesForStats;

                        ///////////
                        //-- output stats

                        sprintf(str, "-%09d-eval.log", castSamples);
                        string fileName = string(statsPrefix) + string(str);

                        ///////////////
                        //-- propagate pvs or pvs size information

                        startTime = GetTime();
                        ObjectPvs pvs;

                        cout << "updating pvs for evaluation ... " << endl;

                        UpdatePvsForEvaluation(mViewCellsTree->GetRoot(), pvs);

                        timeDiff = TimeDiff(startTime, GetTime());
                        cout << "finished updating the pvs in " << timeDiff * 1e-3 << " secs" << endl;
                        Debug << "pvs evaluated in " << timeDiff * 1e-3 << " secs" << endl;
                
                        startTime = GetTime();
                        cout << "compute new statistics ... " << endl;

                        ExportStats(fileName);

                        timeDiff = TimeDiff(startTime, GetTime());
                        cout << "finished in " << timeDiff * 1e-3 << " secs" << endl;
                        Debug << "statistis computed in " << timeDiff * 1e-3 << " secs" << endl;
                }

                disposeRays(evaluationSamples, NULL);
        }
        

        ////////////
        //-- histogram

        const int numLeaves = mViewCellsTree->GetNumInitialViewCells(mViewCellsTree->GetRoot());
        bool useHisto;
        int histoStepSize;

        Environment::GetSingleton()->GetBoolValue("ViewCells.Evaluation.histogram", useHisto);
        Environment::GetSingleton()->GetIntValue("ViewCells.Evaluation.histoStepSize", histoStepSize);

        if (useHisto)
        {
                // evaluate view cells in a histogram           
                char s[64];

                for (int pass = histoStepSize; pass <= numLeaves; pass += histoStepSize)
                {
                        string filename;

                        cout << "computing histogram for " << pass << " view cells" << endl;
#if 0
                        //-- evaluate histogram for render cost
                        sprintf(s, "-%09d-histo.log", pass);
                        filename = string(statsPrefix) + string(s);

                        EvalViewCellHistogram(filename, pass);

#endif
                        //////////////////////////////////////////
            //-- evaluate histogram for pvs size

                        cout << "computing pvs histogram for " << pass << " view cells" << endl;

                        sprintf(s, "-%09d-histo-pvs.log", pass);
                        filename = string(statsPrefix) + string(s);

                        EvalViewCellHistogramForPvsSize(filename, pass);
                }
        }
}


inline float EvalMergeCost(ViewCell *root, ViewCell *candidate)
{
        return root->GetPvs().GetPvsHomogenity(candidate->GetPvs());
}


/// Returns index of the best view cells of the neighborhood
static int GetBestViewCellIdx(ViewCell *root, const ViewCellContainer &neighborhood)
{
        int bestViewCellIdx = 0;

        float mergeCost = Limits::Infinity;
        int i = 0;

        ViewCellContainer::const_iterator vit, vit_end = neighborhood.end();

        for (vit = neighborhood.begin(); vit != vit_end; ++ vit, ++ i)
        {
                const float mc = EvalMergeCost(root, *vit);
                
                if (mc < mergeCost)
                {
                        mergeCost = mc;
                        bestViewCellIdx = i;
                }
        }

        return bestViewCellIdx;
}


void ViewCellsManager::SetMaxFilterSize(const int size) 
{
        mMaxFilterSize = size;
}


float ViewCellsManager::EvalRenderCost(Intersectable *obj) //const
{
        switch (sRenderCostEvaluationType)
        {
        case PER_OBJECT:
                return 1.0f;
        
        case PER_TRIANGLE:
                {
                        return (float)obj->NumberOfFaces();
                }
        default:
                cout << "default" << endl;
                return 1.0f;
        }

        // should not come here
        return 0.0f;
}


ViewCell *ViewCellsManager::ConstructLocalMergeTree(ViewCell *currentViewCell, 
                                                                                                        const ViewCellContainer &viewCells)
{
        ViewCell *root = currentViewCell;
        ViewCellContainer neighborhood = viewCells;

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

        const int n = min(mMaxFilterSize, (int)neighborhood.size());
        
        /////////////////
        //-- use priority queue to merge leaf pairs
        
        for (int nMergedViewCells = 0; nMergedViewCells < n; ++ nMergedViewCells)
        {
                const int bestViewCellIdx = GetBestViewCellIdx(root, neighborhood);
                
                ViewCell *bestViewCell = neighborhood[bestViewCellIdx];
        
                // remove from vector
                swap(neighborhood[bestViewCellIdx], neighborhood.back());
                neighborhood.pop_back();
        
                if (!bestViewCell || !root)
            cout << "warning!!" << endl;
                
                // create new root of the hierarchy
                root = MergeViewCells(root, bestViewCell);
        }

        return root;    
}


struct SortableViewCellEntry {

        SortableViewCellEntry() {}
        SortableViewCellEntry(const float v, ViewCell *cell):mValue(v), mViewCell(cell) {}

        float mValue;
        ViewCell *mViewCell;

        friend bool operator<(const SortableViewCellEntry &a, const SortableViewCellEntry &b) {
                return a.mValue < b.mValue;
        }
};


ViewCell * ViewCellsManager::ConstructLocalMergeTree2(ViewCell *currentViewCell, 
                                                                                                          const ViewCellContainer &viewCells)
{
  
  vector<SortableViewCellEntry> neighborhood(viewCells.size());
  int i, j;
  for (i = 0, j = 0; i < viewCells.size(); i++) {
        if (viewCells[i] != currentViewCell) 
          neighborhood[j++] = SortableViewCellEntry(
                                                                                                EvalMergeCost(currentViewCell, viewCells[i]),
                                                                                                viewCells[i]);
  }
  neighborhood.resize(j);
  
  sort(neighborhood.begin(), neighborhood.end());
  
  ViewCell *root = currentViewCell;
  
  vector<SortableViewCellEntry>::const_iterator it, it_end = neighborhood.end();
  
  const int n = min(mMaxFilterSize, (int)neighborhood.size());
  //-- use priority queue to merge leaf pairs
  
  //cout << "neighborhood: " << neighborhood.size() << endl;
  for (int nMergedViewCells = 0; nMergedViewCells < n; ++ nMergedViewCells)
  {
          ViewCell *bestViewCell = neighborhood[nMergedViewCells].mViewCell;
          //cout <<nMergedViewCells<<":"<<"homogenity=" <<neighborhood[nMergedViewCells].mValue<<endl;
          // create new root of the hierarchy
          root = MergeViewCells(root, bestViewCell);
          // set negative cost so that this view cell gets deleted
          root->SetMergeCost(-1.0f);
  }
  
  return root;  
}

void
ViewCellsManager::DeleteLocalMergeTree(ViewCell *vc
                                                                           ) const
{
        if (!vc->IsLeaf() && vc->GetMergeCost() < 0.0f) 
        {       
                ViewCellInterior *vci = (ViewCellInterior *) vc;
                ViewCellContainer::const_iterator it, it_end = vci->mChildren.end();

        for (it = vci->mChildren.begin(); it != it_end; ++ it)
                        DeleteLocalMergeTree(*it);
                
                vci->mChildren.clear();
                
                delete vci;
  }
}


bool ViewCellsManager::CheckValidity(ViewCell *vc,
                                                                         int minPvsSize,
                                                                         int maxPvsSize) const
{

        if ((vc->GetPvs().EvalPvsCost() > maxPvsSize) ||
                (vc->GetPvs().EvalPvsCost() < minPvsSize))
        {
                return false;
        }

        return true;
}


int ViewCellsManager::ComputeBoxIntersections(const AxisAlignedBox3 &box, 
                                                                                          ViewCellContainer &viewCells) const
{
        return 0;
};


AxisAlignedBox3 ViewCellsManager::GetFilterBBox(const Vector3 &viewPoint, 
                                                                                                const float width) const
{
  float w = Magnitude(mViewSpaceBox.Size())*width;
  Vector3 min = viewPoint - w * 0.5f;
  Vector3 max = viewPoint + w * 0.5f;
  
  return AxisAlignedBox3(min, max);
}


void ViewCellsManager::GetPrVS(const Vector3 &viewPoint,
                                                           PrVs &prvs,
                                                           const float filterWidth)
{
  ViewCell *currentViewCell = GetViewCell(viewPoint);

  if (mMaxFilterSize < 1) {
        prvs.mViewCell = currentViewCell;
        return;
  }
  
  const AxisAlignedBox3 box = GetFilterBBox(viewPoint, filterWidth);
  
  if (currentViewCell) 
        {
          ViewCellContainer viewCells;
          ComputeBoxIntersections(box, viewCells);
          
          ViewCell *root = ConstructLocalMergeTree2(currentViewCell, viewCells);
          prvs.mViewCell = root;
          
        } 
  else
        {
          prvs.mViewCell = NULL;
          //prvs.mPvs = root->GetPvs();
        }
}


bool ViewCellsManager::ViewCellsTreeConstructed() const
{
    return (mViewCellsTree && mViewCellsTree->GetRoot());
}


void ViewCellsManager::SetValidity(ViewCell *vc,
                                                                   int minPvs,
                                                                   int maxPvs) const
{
        vc->SetValid(CheckValidity(vc, minPvs, maxPvs));
}


void
ViewCellsManager::SetValidity(
                                                          int minPvsSize,
                                                          int maxPvsSize) const
{
        ViewCellContainer::const_iterator it, it_end = mViewCells.end();


        for (it = mViewCells.begin(); it != it_end; ++ it) 
        {
                SetValidity(*it, minPvsSize, maxPvsSize);
        }
}

void
ViewCellsManager::SetValidityPercentage(
                                                                                const float minValid,
                                                                                const float maxValid
                                                                                )
{
  ObjectPvs dummyPvs;
  // update pvs sizes
  for (int i = 0; i < (int)mViewCells.size(); ++ i) {
        UpdatePvsForEvaluation(mViewCells[i], dummyPvs);
  }
  
  sort(mViewCells.begin(), mViewCells.end(), ViewCell::SmallerPvs);
  
  int start = (int)(mViewCells.size() * minValid);
  int end = (int)(mViewCells.size() * maxValid);
  
  for (int i = 0; i < (int)mViewCells.size(); ++ i)
        {
          //      cout<<"pvs:"<<mViewCells[i]->GetCachedPvsCost()<<endl;
          mViewCells[i]->SetValid(i >= start && i <= end);
        }
}


int ViewCellsManager::CountValidViewcells() const
{
        ViewCellContainer::const_iterator it, it_end = mViewCells.end();
        int valid = 0;

        for (it = mViewCells.begin(); it != it_end; ++ it) 
        {       
                if ((*it)->GetValid())
                        ++ valid;
        }

        return valid;
}


bool ViewCellsManager::LoadViewCellsGeometry(const string filename, 
                                                                                         const bool extrudeBaseTriangles)
{
        /// we use predefined view cells from now on
        mUsePredefinedViewCells = true;
        X3dParser parser;
        
        if (extrudeBaseTriangles)
        {
                Environment::GetSingleton()->GetFloatValue("ViewCells.height", parser.mViewCellHeight);
                const bool success = parser.ParseFile(filename, *this);

                if (!success)
                        return false;
        }
        else
        {
                // hack: use standard mesh loading
                // create temporary scene graph for loading the view cells geometry
                // note: delete the meshes as they are created two times for transformed mesh instances.
                SceneGraphNode *root = new SceneGraphNode();
                const bool success = parser.ParseFile(filename, root, true);
                
                if (!success)
                {
                        DEL_PTR(root);
                        return false;
                }

                ObjectContainer::const_iterator oit, oit_end = root->mGeometry.end();
                
                for (oit = root->mGeometry.begin(); oit != oit_end; ++ oit)
                {
                        Mesh *mesh;
                        if ((*oit)->Type() == Intersectable::TRANSFORMED_MESH_INSTANCE)
                        {
                                TransformedMeshInstance *mit = dynamic_cast<TransformedMeshInstance *>(*oit);
                                mesh = MeshManager::GetSingleton()->CreateResource();
                                mit->GetTransformedMesh(*mesh);
                        }
                        else if ((*oit)->Type() == Intersectable::MESH_INSTANCE)
                        {
                                MeshInstance *mit = dynamic_cast<MeshInstance *>(*oit);
                                mesh = mit->GetMesh();
                        }
                        mesh->ComputeBoundingBox();
                        mViewCells.push_back(GenerateViewCell(mesh));
                }

                DEL_PTR(root);
        }

        // set view space box to bounding box of the view cells
        AxisAlignedBox3 bbox;
        bbox.Initialize();
        ViewCellContainer::iterator it = mViewCells.begin(), it_end = mViewCells.end();

        for (; it != it_end; ++ it) 
        {
                bbox.Include((*it)->GetMesh()->mBox);
        }

        SetViewSpaceBox(bbox);
        cout << "view space box: " << bbox << endl;
        cout << "generated " << (int)mViewCells.size() << " view cells using the geometry " << filename << endl;

        return true;
}


bool ViewCellsManager::GetViewPoint(Vector3 &viewPoint) const
{
  viewPoint = mViewSpaceBox.GetRandomPoint();
  return true;
}

bool ViewCellsManager::GetViewPoint(Vector3 &viewPoint, const Vector3 &params) const
{
  viewPoint = mViewSpaceBox.GetRandomPoint(params);
  return true;
}


float ViewCellsManager::GetViewSpaceVolume()
{
        return mViewSpaceBox.GetVolume() * (2.0f * sqr((float)M_PI));
}


bool ViewCellsManager::ViewPointValid(const Vector3 &viewPoint) const
{
        if (!ViewCellsConstructed())
        {
                return mViewSpaceBox.IsInside(viewPoint);
        }
        else 
        {
                if (!mViewSpaceBox.IsInside(viewPoint))
                        return false;

                ViewCell *viewcell = GetViewCell(viewPoint);

                if (!viewcell || !viewcell->GetValid())
                        return false;
        }

        return true;
}


float
ViewCellsManager::ComputeSampleContributions(const VssRayContainer &rays,
                                                                                         const bool addRays,
                                                                                         const bool storeViewCells)
{
  float sum = 0.0f;

  VssRayContainer::const_iterator it, it_end = rays.end();
  
  for (it = rays.begin(); it != it_end; ++ it) 
        {
          if (!ViewCellsConstructed()) {
                // view cells not yet constructed
                // just take the lenghts of the rays as contributions
                if ((*it)->mTerminationObject)
                  sum += (*it)->Length();
          } else {
                sum += ComputeSampleContribution(*(*it), addRays, storeViewCells);
          }
        }

  return sum;
}


void ViewCellsManager::EvaluateViewCellsStats()
{
        mCurrentViewCellsStats.Reset();
        ViewCellContainer::const_iterator it, it_end = mViewCells.end();

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


void ViewCellsManager::EvaluateRenderStatistics(float &totalRenderCost,
                                                                                                float &expectedRenderCost, 
                                                                                                float &deviation,
                                                                                                float &variance,
                                                                                                float &totalCost,
                                                                                                float &avgRenderCost)
{
        ////////////
        //-- compute expected value

        totalRenderCost = 0;
        totalCost = 0;

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

        for (it = mViewCells.begin(); it != it_end; ++ it)
        {
                ViewCell *vc = *it;
                totalRenderCost += vc->GetPvs().EvalPvsCost() * vc->GetVolume();
                totalCost += (int)vc->GetPvs().EvalPvsCost();
        }

        // normalize with view space box
        totalRenderCost /= mViewSpaceBox.GetVolume();
        expectedRenderCost = totalRenderCost / (float)mViewCells.size();
        avgRenderCost = totalCost / (float)mViewCells.size();


        ///////////
        //-- compute standard defiation

        variance = 0;
        deviation = 0;

        for (it = mViewCells.begin(); it != it_end; ++ it)
        {
                ViewCell *vc = *it;

                float renderCost = vc->GetPvs().EvalPvsCost() * vc->GetVolume();
                float dev;

                if (1)
                        dev = fabs(avgRenderCost - (float)vc->GetPvs().EvalPvsCost());
                else
                        dev = fabs(expectedRenderCost - renderCost);

                deviation += dev;
                variance += dev * dev;
        }

        variance /= (float)mViewCells.size();
        deviation /= (float)mViewCells.size();
}


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


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


void ViewCellsManager::CompressViewCells()
{
        if (!(ViewCellsTreeConstructed() && mCompressViewCells))
                return;

        ////////////
        //-- compression
        
        int pvsEntries = mViewCellsTree->CountStoredPvsEntries(mViewCellsTree->GetRoot());

        cout << "number of entries before compress: " << pvsEntries << endl;
        Debug << "number of entries before compress: " << pvsEntries << endl;

        mViewCellsTree->SetViewCellsStorage(ViewCellsTree::COMPRESSED);

        pvsEntries = mViewCellsTree->CountStoredPvsEntries(mViewCellsTree->GetRoot());

        Debug << "number of entries after compress: " << pvsEntries << endl;
        cout << "number of entries after compress: " << pvsEntries << endl;
}


ViewCell *ViewCellsManager::ExtrudeViewCell(const Triangle3 &baseTri,
                                                                                        const float height) const
{
        // one mesh per view cell
        Mesh *mesh = MeshManager::GetSingleton()->CreateResource();

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

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

        // do we have to preprocess this mesh (we don't want to trace view cells!)?
        mesh->ComputeBoundingBox();
        
        return GenerateViewCell(mesh);
}


void ViewCellsManager::FinalizeViewCells(const bool createMesh)
{
        ViewCellContainer::const_iterator it, it_end = mViewCells.end();

        // volume and area of the view cells are recomputed 
        // a view cell mesh is created
        for (it = mViewCells.begin(); it != it_end; ++ it)
        {
                Finalize(*it, createMesh);
        }

        mViewCellsTree->AssignRandomColors();

        mTotalAreaValid = false;
}


void ViewCellsManager::Finalize(ViewCell *viewCell, const bool createMesh)
{
        // implemented in subclasses
}


/** fast way of merging 2 view cells.
*/
ViewCellInterior *ViewCellsManager::MergeViewCells(ViewCell *left, ViewCell *right) const
{
        // generate parent view cell
        ViewCellInterior *vc = new ViewCellInterior();

        vc->GetPvs().Clear();
        ObjectPvs::Merge(vc->GetPvs(), left->GetPvs(), right->GetPvs());

        // set only links to child (not from child to parent, maybe not wished!!)
        vc->mChildren.push_back(left);
        vc->mChildren.push_back(right);

        // update pvs size
        UpdateScalarPvsSize(vc, vc->GetPvs().EvalPvsCost(), vc->GetPvs().GetSize());

        return vc;
}


ViewCellInterior *ViewCellsManager::MergeViewCells(ViewCellContainer &children) const
{
        ViewCellInterior *vc = new ViewCellInterior();
        ViewCellContainer::const_iterator it, it_end = children.end();

        for (it = children.begin(); it != it_end; ++ it)
        {
                vc->GetPvs().MergeInPlace((*it)->GetPvs());
        
                vc->mChildren.push_back(*it);
        }

        return vc;
}


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


ViewCellsTree *ViewCellsManager::GetViewCellsTree()
{
        return mViewCellsTree;
}


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


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


void ViewCellsManager::SetInitialSamples(const int initialSamples)
{
        mInitialSamples = initialSamples;
}


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::UpdatePvs()
{
  if (mViewCellPvsIsUpdated || !ViewCellsTreeConstructed())
        return;
  
  mViewCellPvsIsUpdated = true;
  
  ViewCellContainer leaves;
  mViewCellsTree->CollectLeaves(mViewCellsTree->GetRoot(), leaves);
  
  ViewCellContainer::const_iterator it, it_end = leaves.end();
  
  for (it = leaves.begin(); it != it_end; ++ it)
        {
          mViewCellsTree->PropagatePvs(*it);
        }
}


void ViewCellsManager::GetPvsStatistics(PvsStatistics &stat)
{
  // update pvs of view cells tree if necessary
  UpdatePvs();
  
  ViewCellContainer::const_iterator it = mViewCells.begin();
  
  stat.viewcells = 0;
  stat.minPvs = 100000000;
  stat.maxPvs = 0;
  stat.avgPvs = 0.0f;
  stat.avgFilteredPvs = 0.0f;
  stat.avgFilterContribution = 0.0f;
  stat.avgFilterRadius = 0;
  stat.avgFilterRatio = 0;
  stat.avgRelPvsIncrease = 0.0f;
  stat.devRelPvsIncrease = 0.0f;
  
  if (mPerViewCellStat.size() != mViewCells.size()) {
        // reset the pvs size array after the first call to this routine
        mPerViewCellStat.resize(mViewCells.size());
        for (int i=0; i < mPerViewCellStat.size(); i++) {
          mPerViewCellStat[i].pvsSize = 0.0f;
          mPerViewCellStat[i].relPvsIncrease = 0.0f;
        }
  }
  int i;
  bool evaluateFilter;
  Environment::GetSingleton()->GetBoolValue("Preprocessor.evaluateFilter", evaluateFilter);

  for (i=0; it != mViewCells.end(); ++ it, i++) 
        {
          ViewCell *viewcell = *it;
          if (viewcell->GetValid()) {
                const float pvsCost = mViewCellsTree->GetPvsCost(viewcell);
                
                if (pvsCost < stat.minPvs)
                  stat.minPvs = pvsCost;
                if (pvsCost > stat.maxPvs)
                  stat.maxPvs = pvsCost;
                
                stat.avgPvs += pvsCost;


                if (mPerViewCellStat[i].pvsSize > 0.0f)
                  mPerViewCellStat[i].relPvsIncrease = (pvsCost - mPerViewCellStat[i].pvsSize)/mPerViewCellStat[i].pvsSize;
                
                stat.avgRelPvsIncrease += mPerViewCellStat[i].relPvsIncrease;
                
                // update the pvs size
                mPerViewCellStat[i].pvsSize = pvsCost;
                
                
                
                if (evaluateFilter) {
                  ObjectPvs filteredPvs;
                  PvsFilterStatistics fstat = ApplyFilter2(viewcell,
                                                                                                   false,
                                                                                                   1.0f,
                                                                                                   filteredPvs);
                  
                  float filteredCost = filteredPvs.EvalPvsCost();
                  stat.avgFilteredPvs += filteredCost;
                  stat.avgFilterContribution += filteredCost - pvsCost;
                  
                  stat.avgFilterRadius += fstat.mAvgFilterRadius;
                  int sum = fstat.mGlobalFilterCount + fstat.mLocalFilterCount;
                  if (sum) {
                        stat.avgFilterRatio += fstat.mLocalFilterCount /
                          (float) sum;
                  }
                  
                } else {
                  stat.avgFilteredPvs += pvsCost;
                  stat.avgFilterContribution += 0;
                }
                
                ++ stat.viewcells;
          }
        }

  
  
  if (stat.viewcells) {
        stat.avgPvs/=stat.viewcells;
        stat.avgFilteredPvs/=stat.viewcells;
        stat.avgFilterContribution/=stat.viewcells;
        stat.avgFilterRadius/=stat.viewcells;
        stat.avgFilterRatio/=stat.viewcells; 
        stat.avgRelPvsIncrease/=stat.viewcells;

        // evaluate std deviation of relPvsIncrease
        float sum=0.0f;
        for (i=0; i < stat.viewcells; i++) {
          sum += sqr(mPerViewCellStat[i].relPvsIncrease - stat.avgRelPvsIncrease);
        }
        stat.devRelPvsIncrease = sqrt(sum/stat.viewcells);
  }
  
}


void ViewCellsManager::PrintPvsStatistics(ostream &s)
{
  s<<"############# Viewcell PVS STAT ##################\n";
  PvsStatistics pvsStat;
  GetPvsStatistics(pvsStat);
  s<<"#AVG_PVS\n"<<pvsStat.avgPvs<<endl;
  s<<"#AVG_FILTERED_PVS\n"<<pvsStat.avgFilteredPvs<<endl;
  s<<"#AVG_FILTER_CONTRIBUTION\n"<<pvsStat.avgFilterContribution<<endl;
  s<<"#AVG_FILTER_RADIUS\n"<<pvsStat.avgFilterRadius<<endl;
  s<<"#AVG_FILTER_RATIO\n"<<pvsStat.avgFilterRatio<<endl;
  s<<"#MAX_PVS\n"<<pvsStat.maxPvs<<endl;
  s<<"#MIN_PVS\n"<<pvsStat.minPvs<<endl;
  s<<"#AVG_REL_PVS_INCREASE\n"<<pvsStat.avgRelPvsIncrease<<endl;
  s<<"#DEV_REL_PVS_INCREASE\n"<<pvsStat.devRelPvsIncrease<<endl;
}


int ViewCellsManager::CastBeam(Beam &beam)
{
        return 0;
}


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


void ViewCellsManager::SetViewSpaceBox(const AxisAlignedBox3 &box)
{
        mViewSpaceBox = box;
        
        // hack: create clip plane relative to new view space box
        CreateClipPlane();
        // the total area of the view space has changed
        mTotalAreaValid = false;
}


void ViewCellsManager::CreateClipPlane()
{
        int axis = 0;
        float pos;
        bool orientation;
        Vector3 absPos;

        Environment::GetSingleton()->GetFloatValue("ViewCells.Visualization.clipPlanePos", pos);
        Environment::GetSingleton()->GetIntValue("ViewCells.Visualization.clipPlaneAxis", axis);

        if (axis < 0) 
        {
                axis = -axis;
                orientation = false;
                absPos = mViewSpaceBox.Max() -  mViewSpaceBox.Size() * pos;
        }
        else
        {
                orientation = true;
                absPos = mViewSpaceBox.Min() +  mViewSpaceBox.Size() * pos;
        }

        mClipPlaneForViz = AxisAlignedPlane(axis, absPos[axis]);
        mClipPlaneForViz.mOrientation = orientation;
}


AxisAlignedBox3 ViewCellsManager::GetViewSpaceBox() const
{
        return mViewSpaceBox;
}


void ViewCellsManager::ResetViewCells()
{
        // recollect view cells
        mViewCells.clear();
        CollectViewCells();
        
        // stats are computed once more
        EvaluateViewCellsStats();

        // has to be recomputed
        mTotalAreaValid = false;
}


int ViewCellsManager::GetMaxPvsSize() const
{
        return mMaxPvsSize;
}


int ViewCellsManager::GetMinPvsSize() const
{
        return mMinPvsSize;
}



float ViewCellsManager::GetMaxPvsRatio() const
{
        return mMaxPvsRatio;
}


inline static void AddSampleToPvs(ObjectPvs &pvs, 
                                                                  Intersectable *obj, 
                                                                  const float pdf)
{
#if PVS_ADD_DIRTY
        pvs.AddSampleDirtyCheck(obj, pdf);

        if (pvs.RequiresResort()) 
        {
                pvs.SimpleSort();
        }
#else
        pvs.AddSample(obj, pdf);
#endif
}


void ViewCellsManager::ComputeViewCellContribution(ViewCell *viewCell,
                                                                                                   VssRay &ray, 
                                                                                                   Intersectable *obj,
                                                                                                   const Vector3 &pt,
                                                                                                   const bool addRays)
{
  // check if we are outside of view space
        if (!obj || !viewCell->GetValid())
                return;
        
        // if ray not outside of view space
        float relContribution = 0.0f;
        float absContribution = 0.0f;
        
        if (obj) 
          {
                // todo: maybe not correct for kd node pvs
                if (addRays) {
                  float pdf = viewCell->GetPvs().AddSampleDirtyCheck(obj, ray.mPdf);
                  if (pdf == ray.mPdf) {
                        absContribution = 1.0f;
                        if (viewCell->GetPvs().RequiresResort()) 
                          viewCell->GetPvs().SimpleSort();
                  }
                          } else {
                                if (viewCell->GetPvs().GetSampleContribution(
                                                                                                                         obj,
                                                                                                                         ray.mPdf,
                                                                                                                         relContribution))
                                  absContribution = 1.0f;
                          }
                // $$ clear the relative contribution as it is currently not correct anyway
                relContribution = 0.0f;
                
                if (absContribution == 1.0f) {
                  ++ ray.mPvsContribution;
                  relContribution = 1.0f;
                  
                  
#if CONTRIBUTION_RELATIVE_TO_PVS_SIZE
                  relContribution /= viewcell->GetPvs().GetSize();
#endif
                  
#if DIST_WEIGHTED_CONTRIBUTION 
                  // recalculate the contribution - weight the 1.0f contribution by the sqr distance to the
                  // object-> a new contribution in the proximity of the viewcell has a larger weight!
                  relContribution /= SqrDistance(GetViewCellBox(viewcell).Center(),
                                                                                 ray.mTermination);
                  
#endif
                }
                
#if SUM_RAY_CONTRIBUTIONS || AVG_RAY_CONTRIBUTIONS
                ray.mRelativePvsContribution += relContribution;
#else
                // recalculate relative contribution - use max of Rel Contribution
                if (ray.mRelativePvsContribution < relContribution)
                  ray.mRelativePvsContribution = relContribution;
#endif
          }
        
}


float
ViewCellsManager::ComputeSampleContribution(VssRay &ray,
                                                                                        const bool addRays,
                                                                                        const bool storeViewCells)
{
        ray.mPvsContribution = 0;
        ray.mRelativePvsContribution = 0.0f;

        if (!ray.mTerminationObject)
                return 0.0f;

        ViewCellContainer viewCells;

        static Ray hray;
        hray.Init(ray);

        float tmin = 0, tmax = 1.0;

        if (!GetViewSpaceBox().GetRaySegment(hray, tmin, tmax) || (tmin > tmax)) {
          //      cerr<<"ray outside view space box\n";
          return 0;
        }

        Vector3 origin = hray.Extrap(tmin);
        Vector3 termination = hray.Extrap(tmax);

        ViewCell::NewMail();

        // traverse the view space subdivision
        CastLineSegment(origin, termination, viewCells);

        
        if (storeViewCells)
        {       
          // copy viewcells memory efficiently
#if VSS_STORE_VIEWCELLS
          ray.mViewCells.reserve(viewCells.size());
          ray.mViewCells = viewCells;
#else
          cerr<<"Vss store viewcells not supported."<<endl;
          exit(1);
#endif
        }

        // optain pvs entry (can be different from hit object)
        Intersectable *terminationObj = GetIntersectable(ray, true);

        ViewCellContainer::const_iterator it = viewCells.begin();

        for (; it != viewCells.end(); ++ it) 
        {
                ComputeViewCellContribution(*it, 
                                                                        ray, 
                                                                        terminationObj, 
                                                                        ray.mTermination, 
                                                                        addRays);
        }

#if AVG_RAY_CONTRIBUTIONS
        ray.mRelativePvsContribution /= (float)viewCells.size();
#endif
  
#if USE_RAY_LENGTH_AS_CONTRIBUTION
        float c = 0.0f;
        if (terminationObj) 
          c = ray.Length();
        ray.mRelativePvsContribution = ray.mPvsContribution = c;
        return c;
#else
        return ABS_CONTRIBUTION_WEIGHT*ray.mPvsContribution +
          (1.0f - ABS_CONTRIBUTION_WEIGHT)*ray.mRelativePvsContribution;
#endif
}


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::GetRendercost(ViewCell *viewCell) const
{
        return (float)mViewCellsTree->GetPvsCost(viewCell);
}


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


void ViewCellsManager::CreateUniqueViewCellIds()
{
        if (ViewCellsTreeConstructed())
        {
                mViewCellsTree->CreateUniqueViewCellsIds();
        }
        else // no view cells tree, handle view cells "myself"
        {
                int i = 0;
                ViewCellContainer::const_iterator vit, vit_end = mViewCells.end();
                for (vit = mViewCells.begin(); vit != vit_end; ++ vit)
                {
                        if ((*vit)->GetId() != OUT_OF_BOUNDS_ID) 
                        {
                                mViewCells[i]->SetId(i ++);
                        }
                }
        }
}


void ViewCellsManager::ExportViewCellsForViz(Exporter *exporter,
                                                                                         const AxisAlignedBox3 *sceneBox,
                                                                                         const bool colorCode,
                                                                                         const AxisAlignedPlane *clipPlane
                                                                                         ) const
{
        ViewCellContainer::const_iterator it, it_end = mViewCells.end();

        for (it = mViewCells.begin(); it != it_end; ++ it)
        {
                if (!mOnlyValidViewCells || (*it)->GetValid())
                {
                        ExportColor(exporter, *it, colorCode);  
                        ExportViewCellGeometry(exporter, *it, sceneBox, clipPlane);
                }
        }
}


void ViewCellsManager::CreateViewCellMeshes()
{
        // convert to meshes
        ViewCellContainer::const_iterator it, it_end = mViewCells.end();

        for (it = mViewCells.begin(); it != it_end; ++ it)
        {
                if (!(*it)->GetMesh())
                {
                        CreateMesh(*it);
                }
        }
}


bool ViewCellsManager::ExportViewCells(const string filename, 
                                                                           const bool exportPvs, 
                                                                           const ObjectContainer &objects)
{
        return false;
}


void ViewCellsManager::CollectViewCells(const int n) 
{
        mNumActiveViewCells = n;
        mViewCells.clear();
        // implemented in subclasses
        CollectViewCells();
}


void ViewCellsManager::SetViewCellActive(ViewCell *vc) const
{
        ViewCellContainer leaves;
        // sets the pointers to the currently active view cells
        mViewCellsTree->CollectLeaves(vc, leaves);

        ViewCellContainer::const_iterator lit, lit_end = leaves.end();
        for (lit = leaves.begin(); lit != lit_end; ++ lit)
        {
                dynamic_cast<ViewCellLeaf *>(*lit)->SetActiveViewCell(vc);
        }
}


void ViewCellsManager::SetViewCellsActive()
{
        // collect leaf view cells and set the pointers to 
        // the currently active view cells
        ViewCellContainer::const_iterator it, it_end = mViewCells.end();

        for (it = mViewCells.begin(); it != it_end; ++ it)
        {
                SetViewCellActive(*it);
        }
}


int ViewCellsManager::GetMaxFilterSize() const
{
        return mMaxFilterSize;  
}


static const bool USE_ASCII = true;


bool ViewCellsManager::ExportBoundingBoxes(const string filename, 
                                                                                   const ObjectContainer &objects) const
{
        ObjectContainer::const_iterator it, it_end = objects.end();
        
        if (USE_ASCII)
        {
                ofstream boxesOut(filename.c_str());
                if (!boxesOut.is_open())
                        return false;

                for (it = objects.begin(); it != it_end; ++ it)
                {
                        MeshInstance *mi = dynamic_cast<MeshInstance *>(*it);
                        const AxisAlignedBox3 box = mi->GetBox();

                        boxesOut << mi->GetId() << " " 
                                         << box.Min().x << " " 
                                         << box.Min().y << " " 
                                         << box.Min().z << " " 
                                         << box.Max().x << " " 
                                         << box.Max().y << " " 
                     << box.Max().z << endl;    
                }

                boxesOut.close();
        }
        else
        {
                ofstream boxesOut(filename.c_str(), ios::binary);

                if (!boxesOut.is_open())
                        return false;

                for (it = objects.begin(); it != it_end; ++ it)
                {       
                        MeshInstance *mi = dynamic_cast<MeshInstance *>(*it);
                        const AxisAlignedBox3 box = mi->GetBox();
                        Vector3 bmin = box.Min();
                        Vector3 bmax = box.Max();
                        int id = mi->GetId();

                        boxesOut.write(reinterpret_cast<char *>(&id), sizeof(int));
                        boxesOut.write(reinterpret_cast<char *>(&bmin), sizeof(Vector3));
                        boxesOut.write(reinterpret_cast<char *>(&bmax), sizeof(Vector3));
                }
                
                boxesOut.close();
        }

        return true;
}


bool ViewCellsManager::LoadBoundingBoxes(const string filename, 
                                                                                 IndexedBoundingBoxContainer &boxes) const
{
        Vector3 bmin, bmax;
        int id;

        if (USE_ASCII)
        {
                ifstream boxesIn(filename.c_str());
                
                if (!boxesIn.is_open())
                {
                        cout << "failed to open file " << filename << endl;
                        return false;
                }

                string buf;
                while (!(getline(boxesIn, buf)).eof())
                {
                        sscanf(buf.c_str(), "%d %f %f %f %f %f %f", 
                                   &id, &bmin.x, &bmin.y, &bmin.z,
                                   &bmax.x, &bmax.y, &bmax.z);
                
                        AxisAlignedBox3 box(bmin, bmax);
                        //      MeshInstance *mi = new MeshInstance();
                        // HACK: set bounding box to new box
                        //mi->mBox = box;

                        boxes.push_back(IndexedBoundingBox(id, box));
                }

                boxesIn.close();
        }
        else
        {
                ifstream boxesIn(filename.c_str(), ios::binary);

                if (!boxesIn.is_open())
                        return false;

                while (1)
                {
                        boxesIn.read(reinterpret_cast<char *>(&id), sizeof(Vector3));
                        boxesIn.read(reinterpret_cast<char *>(&bmin), sizeof(Vector3));
                        boxesIn.read(reinterpret_cast<char *>(&bmax), sizeof(Vector3));
                        
                        if (boxesIn.eof())
                                break;

                        
                        AxisAlignedBox3 box(bmin, bmax);
                        MeshInstance *mi = new MeshInstance(NULL);

                        // HACK: set bounding box to new box
                        //mi->mBox = box;
                        //boxes.push_back(mi);
                        boxes.push_back(IndexedBoundingBox(id, box));
                }

                boxesIn.close();
        }

        return true;
}


float ViewCellsManager::GetFilterWidth() 
{
        return mFilterWidth;
}


float ViewCellsManager::GetAbsFilterWidth() 
{
        return Magnitude(mViewSpaceBox.Size()) * mFilterWidth;
}


void ViewCellsManager::UpdateScalarPvsSize(ViewCell *vc, 
                                                                                   const float pvsCost, 
                                                                                   const int entriesInPvs) const
{
        vc->mPvsCost = pvsCost;
        vc->mEntriesInPvs = entriesInPvs;

        vc->mPvsSizeValid = true;
}


void
ViewCellsManager::ApplyFilter(ViewCell *viewCell,
                                                          KdTree *kdTree,
                                                          const float viewSpaceFilterSize,
                                                          const float spatialFilterSize,
                                                          ObjectPvs &pvs
                                                          )
{
  // extend the pvs of the viewcell by pvs of its neighbors
  // and apply spatial filter by including all neighbors of the objects
  // in the pvs

  // get all viewcells intersecting the viewSpaceFilterBox
  // and compute the pvs union
  
  //Vector3 center = viewCell->GetBox().Center();
  //  Vector3 center = m->mBox.Center();

        //  AxisAlignedBox3 box(center - Vector3(viewSpaceFilterSize/2),
        //                                        center + Vector3(viewSpaceFilterSize/2));
        if (!ViewCellsConstructed())
                return;

        if (viewSpaceFilterSize >= 0.0f) {

                const bool usePrVS = false;

                if (!usePrVS) {
                        AxisAlignedBox3 box = GetViewCellBox(viewCell);
                        box.Enlarge(Vector3(viewSpaceFilterSize/2));

                        ViewCellContainer viewCells;
                        ComputeBoxIntersections(box, viewCells);

                        //  cout<<"box="<<box<<endl;
                        ViewCellContainer::const_iterator it = viewCells.begin(), it_end = viewCells.end();

                        for (; it != it_end; ++ it) 
                        {
                                ObjectPvs interPvs;
                                //cout<<"v"<<i<<" pvs="<<(*it)->GetPvs().mEntries.size()<<endl;
                                ObjectPvs::Merge(interPvs, pvs, (*it)->GetPvs());

                                pvs = interPvs;
                        }
                } else 
                {
                        PrVs prvs;
                        AxisAlignedBox3 box = GetViewCellBox(viewCell);

                        //  mViewCellsManager->SetMaxFilterSize(1);
                        GetPrVS(box.Center(), prvs, viewSpaceFilterSize);
                        pvs = prvs.mViewCell->GetPvs();
                        DeleteLocalMergeTree(prvs.mViewCell);
                }
        } 
        else
        {
                pvs = viewCell->GetPvs();
        }

        if (spatialFilterSize >=0.0f)
                ApplySpatialFilter(kdTree, spatialFilterSize, pvs);

}



void
ViewCellsManager::ApplyFilter(KdTree *kdTree,
                                                          const float relViewSpaceFilterSize,
                                                          const float relSpatialFilterSize
                                                          )
{

        if (!ViewCellsConstructed())
                return;

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

        ObjectPvs *newPvs;
        newPvs = new ObjectPvs[mViewCells.size()];

        float viewSpaceFilterSize = Magnitude(mViewSpaceBox.Size())*relViewSpaceFilterSize;
        float spatialFilterSize = Magnitude(kdTree->GetBox().Size())*relSpatialFilterSize;
        
        int i;
        for (i=0, it = mViewCells.begin(); it != it_end; ++ it, ++ i) {
          ApplyFilter(*it,
                                  kdTree,
                                  viewSpaceFilterSize,
                                  spatialFilterSize,
                                  newPvs[i]
                                  );
        }
        
        // now replace all pvss
        for (i = 0, it = mViewCells.begin(); it != it_end; ++ it, ++ i) {
          
          ObjectPvs &pvs = (*it)->GetPvs();
          pvs.Clear();
          pvs = newPvs[i];
          newPvs[i].Clear();
        }

        delete [] newPvs;
}


void
ViewCellsManager::ApplySpatialFilter(
                                                                         KdTree *kdTree,
                                                                         const float spatialFilterSize,
                                                                         ObjectPvs &pvs
                                                                         )
{
  // now compute a new Pvs by including also objects intersecting the 
  // extended boxes of visible objects
  Intersectable::NewMail();

  ObjectPvsIterator pit = pvs.GetIterator();

  while (pit.HasMoreEntries())
  {             
          ObjectPvsEntry entry = pit.Next();
  
          Intersectable *object = entry.mObject;
      object->Mail();
  }

  ObjectPvs nPvs;
  int nPvsSize = 0;
  
  ObjectPvsIterator pit2 = pvs.GetIterator();

  while (pit2.HasMoreEntries())
  {             
          // now go through the pvs again
          ObjectPvsEntry entry = pit2.Next();
          Intersectable *object = entry.mObject;

          //    Vector3 center = object->GetBox().Center();
          //    AxisAlignedBox3 box(center - Vector3(spatialFilterSize/2),
          //                                            center + Vector3(spatialFilterSize/2));

          AxisAlignedBox3 box = object->GetBox();
          box.Enlarge(Vector3(spatialFilterSize/2));

          ObjectContainer objects;

          // $$ warning collect objects takes only unmailed ones!
          kdTree->CollectObjects(box, objects);
          //    cout<<"collected objects="<<objects.size()<<endl;
          ObjectContainer::const_iterator noi = objects.begin();
          for (; noi != objects.end(); ++ noi) 
          {
                  Intersectable *o = *noi;
                 
                  // $$ JB warning: pdfs are not correct at this point!   
                  nPvs.AddSample(o, Limits::Small);
                  nPvsSize ++;
          }
  }

  // cout<<"nPvs size = "<<nPvsSize<<endl;
  pvs.MergeInPlace(nPvs);
}


void ViewCellsManager::MergeViewCellsRecursivly(ObjectPvs &pvs, 
                                                                                                const ViewCellContainer &viewCells) const
{
        MergeViewCellsRecursivly(pvs, viewCells, 0, (int)viewCells.size() - 1);
}


void ViewCellsManager::MergeViewCellsRecursivly(ObjectPvs &pvs, 
                                                                                                const ViewCellContainer &viewCells, 
                                                                                                const int leftIdx, 
                                                                                                const int rightIdx) const
{
        if (leftIdx == rightIdx)
        {
                pvs = viewCells[leftIdx]->GetPvs();
        }
        else
        {
                const int midSplit = (leftIdx + rightIdx) / 2;
        
                ObjectPvs leftPvs, rightPvs;
                MergeViewCellsRecursivly(leftPvs, viewCells, leftIdx, midSplit);
                MergeViewCellsRecursivly(rightPvs, viewCells, midSplit, rightIdx);

        ObjectPvs::Merge(pvs, leftPvs, rightPvs);
        }
}


PvsFilterStatistics
ViewCellsManager::ApplyFilter2(ViewCell *viewCell,
                                                           const bool useViewSpaceFilter,
                                                           const float filterSize,
                                                           ObjectPvs &pvs,
                                                           vector<AxisAlignedBox3> *filteredBoxes
                                                           )
{
  //cout<<"y";
  PvsFilterStatistics stats;

  AxisAlignedBox3 vbox = GetViewCellBox(viewCell);
  Vector3 center = vbox.Center();
  // copy the PVS
  Intersectable::NewMail();
  ObjectPvs basePvs = viewCell->GetPvs();
  ObjectPvsIterator pit = basePvs.GetIterator();

  pvs.Reserve(viewCell->GetFilteredPvsSize());

  if (!mUseKdPvs)
  {
          // first mark all objects from this pvs
          while (pit.HasMoreEntries())  
          {
                  ObjectPvsEntry entry = pit.Next();
                  Intersectable *object = entry.mObject;
                  object->Mail();
          }
  }
  
  int pvsSize = 0;
  int nPvsSize = 0;
  float samples = (float)basePvs.GetSamples();
  
  Debug<<"f #s="<<samples<<"  pvs size = "<<basePvs.GetSize();
  //  cout<<"Filter size = "<<filterSize<<endl;
  //  cout<<"vbox = "<<vbox<<endl;
  //  cout<<"center = "<<center<<endl;


   // Minimal number of local samples to take into account
   // the local sampling density.
   // The size of the filter is a minimum of the conservative
   // local sampling density estimate (#rays intersecting teh viewcell and
   // the object)
   // and gobal estimate for the view cell
   // (total #rays intersecting the viewcell)
  int minLocalSamples = 2;
  
  float viewCellRadius = 0.5f*Magnitude(vbox.Diagonal());
  
  // now compute the filter box around the current viewCell
  
  if (useViewSpaceFilter) {
        //      float radius = Max(viewCellRadius/100.0f, avgRadius - viewCellRadius);
        float radius = viewCellRadius/100.0f;
        vbox.Enlarge(radius);
        cout<<"vbox = "<<vbox<<endl;
        ViewCellContainer viewCells;
        ComputeBoxIntersections(vbox, viewCells);
        
        ViewCellContainer::const_iterator it = viewCells.begin(),
          it_end = viewCells.end();
        int i = 0;
        for (i=0; it != it_end; ++ it, ++ i)
          if ((*it) != viewCell) {
                //cout<<"v"<<i<<" pvs="<<(*it)->GetPvs().mEntries.size()<<endl;
                basePvs.MergeInPlace((*it)->GetPvs());
          }
        
        // update samples and globalC
        samples = (float)pvs.GetSamples();
        //      cout<<"neighboring viewcells = "<<i-1<<endl;
        //      cout<<"Samples' = "<<samples<<endl;
  }
  
  // Minimal number of samples so that filtering takes place
#define MIN_SAMPLES  50
  
  if (samples > MIN_SAMPLES) {
        float globalC = 2.0f*filterSize/sqrt(samples);
        
        pit = basePvs.GetIterator();
        
        ObjectContainer objects;
        
        while (pit.HasMoreEntries()) {          
          ObjectPvsEntry entry = pit.Next();
          
          Intersectable *object = entry.mObject;
          // compute filter size based on the distance and the numebr of samples
          AxisAlignedBox3 box = object->GetBox();
          
          float distance = Distance(center, box.Center());
          float globalRadius = distance*globalC;
          
          int objectSamples = (int)entry.mData.mSumPdf;
          float localRadius = MAX_FLOAT;
          
          localRadius = filterSize*0.5f*Magnitude(box.Diagonal())/
                sqrt((float)objectSamples);
          
          //      cout<<"os="<<objectSamples<<" lr="<<localRadius<<" gr="<<globalRadius<<endl;
          
          // now compute the filter size
          float radius;
          
#if 0
          if (objectSamples <= 1) {
                if (localRadius > globalRadius) {
                  radius = 0.5flRadius;
                  stats.mLocalFilterCount++;
                } else {
                  radius = globalRadius;
                  stats.mGlobalFilterCount++;
                }
          } else {
                radius = localRadius;
                stats.mLocalFilterCount++;
          }
#else
          radius = 0.5f*globalRadius + 0.5f*localRadius;

          if (localRadius > globalRadius) 
                stats.mLocalFilterCount++;
          else
                stats.mGlobalFilterCount++;
#endif
          
          stats.mAvgFilterRadius += radius;
          
          // cout<<"box = "<<box<<endl;
          //    cout<<"distance = "<<distance<<endl;
          //    cout<<"radiues = "<<radius<<endl;
          
          box.Enlarge(Vector3(radius));

          if (filteredBoxes)
                filteredBoxes->push_back(box);

          objects.clear();
          // $$ warning collect objects takes only unmailed ones!
          CollectObjects(box, objects);
          //    cout<<"collected objects="<<objects.size()<<endl;
          ObjectContainer::const_iterator noi = objects.begin();
          for (; noi != objects.end(); ++ noi) {
                Intersectable *o = *noi;
                // $$ JB warning: pdfs are not correct at this point!     
                pvs.AddSampleDirty(o, Limits::Small);
          }
        }
        stats.mAvgFilterRadius /= (stats.mLocalFilterCount + stats.mGlobalFilterCount);
  }
  
  Debug<<" nPvs size = "<<pvs.GetSize()<<endl;
  
  if (!mUseKdPvs)
  {
          // copy the base pvs to the new pvs
          pit = basePvs.GetIterator();
          while (pit.HasMoreEntries()) 
          {             
                  ObjectPvsEntry entry = pit.Next();
                  pvs.AddSampleDirty(entry.mObject, entry.mData.mSumPdf);
          }
  }
  
  pvs.SimpleSort();
  viewCell->SetFilteredPvsSize(pvs.GetSize());
  
  Intersectable::NewMail();
  return stats;
}



void ViewCellsManager::ExportColor(Exporter *exporter, 
                                                                   ViewCell *vc, 
                                                                   bool colorCode) const
{
        const bool vcValid = CheckValidity(vc, mMinPvsSize, mMaxPvsSize);

        float importance = 0;
        static Material m;
        //cout << "color code: " << colorCode << endl;
        switch (mColorCode)
        {
        case 0: // Random
                {
                        if (vcValid)
                        {
                                m.mDiffuseColor.r = 0.2f + RandomValue(0.0f, 0.8f);
                                m.mDiffuseColor.g = 0.2f + RandomValue(0.0f, 0.8f);
                                m.mDiffuseColor.b = 0.2f + RandomValue(0.0f, 0.8f);
                        }
                        else
                        {
                                m.mDiffuseColor.r = 0.0f;
                                m.mDiffuseColor.g = 1.0f;
                                m.mDiffuseColor.b = 0.0f;
                        }

                        exporter->SetForcedMaterial(m);
                        return;
                }
                
        case 1: // pvs
                {
                        if (mCurrentViewCellsStats.maxPvs)
                        {
                                importance = (float)mViewCellsTree->GetPvsCost(vc) / 
                                                         (float)mCurrentViewCellsStats.maxPvs;
                        }
                }
                break;
        case 2: // merges
                {
            const int lSize = mViewCellsTree->GetNumInitialViewCells(vc);
                        importance = (float)lSize / (float)mCurrentViewCellsStats.maxLeaves;
                }
                break;
#if 0
        case 3: // merge tree differene
                {
                        importance = (float)GetMaxTreeDiff(vc) /
                                (float)(mVspBspTree->GetStatistics().maxDepth * 2);

                }
                break;
#endif
        default:
                break;
        }

        // special color code for invalid view cells
        m.mDiffuseColor.r = importance;
        m.mDiffuseColor.b = 1.0f;//vcValid ? 0.0f : 1.0f;
        m.mDiffuseColor.g = 1.0f - importance;

        //Debug << "importance: " << importance << endl;
        exporter->SetForcedMaterial(m);
}


void ViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays, 
                                                                                          vector<MergeCandidate> &candidates)
{
        // implemented in subclasses
}


void ViewCellsManager::UpdatePvsForEvaluation()
{
        ObjectPvs objPvs;
        UpdatePvsForEvaluation(mViewCellsTree->GetRoot(), objPvs);
}

void ViewCellsManager::UpdatePvsForEvaluation(ViewCell *root, ObjectPvs &pvs)
{
        // terminate traversal
        if (root->IsLeaf())
        { 
                //cout << "updating leaf" << endl;
                // we assume that pvs is explicitly stored in leaves
                pvs = root->GetPvs();
                UpdateScalarPvsSize(root, pvs.EvalPvsCost(), pvs.GetSize());
                return;
        }

        ////////////////
        //-- interior node => propagate pvs up the tree

        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(root);

        // reset interior pvs
        interior->GetPvs().Clear();
        // reset recursive pvs
        pvs.Clear();

        // pvss of child nodes
        vector<ObjectPvs> pvsList;
        pvsList.resize((int)interior->mChildren.size());

        ViewCellContainer::const_iterator vit, vit_end = interior->mChildren.end();
        
        int i = 0;

        for (vit = interior->mChildren.begin(); vit != vit_end; ++ vit, ++ i)
        {
                //////////////////
                //-- recursivly compute child pvss
                UpdatePvsForEvaluation(*vit, pvsList[i]/*objPvs*/);
        }

#if 1
        Intersectable::NewMail();

        //-- faster way of computing pvs:
        //-- construct merged pvs by adding
        //-- and only those of the next pvs which were not mailed.
        //-- note: sumpdf is not correct!!

        vector<ObjectPvs>::iterator oit = pvsList.begin();

        for (vit = interior->mChildren.begin(); vit != vit_end; ++ vit, ++ oit)
        {
                ObjectPvsIterator pit = (*oit).GetIterator();
                
                // first mark all object from this pvs
                while (pit.HasMoreEntries())
                {               
                        ObjectPvsEntry entry = pit.Next();

                        Intersectable *intersect = entry.mObject;

                        if (!intersect->Mailed())
                        { 
                                pvs.AddSample(intersect, entry.mData.mSumPdf);
                                intersect->Mail();
                        }
                }
        }

        // store pvs in this node
        if (mViewCellsTree->ViewCellsStorage() == ViewCellsTree::PVS_IN_INTERIORS)
        {
                interior->SetPvs(pvs);
        }
        
        // set new pvs size
        UpdateScalarPvsSize(interior, pvs.EvalPvsCost(), pvs.GetSize());
        
#else 
        // really merge cells: slow put sumPdf is correct
        viewCellInterior->GetPvs().Merge(backVc->GetPvs());
        viewCellInterior->GetPvs().Merge(frontVc->GetPvs());
#endif
}



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


BspViewCellsManager::BspViewCellsManager(ViewCellsTree *vcTree, BspTree *bspTree):
ViewCellsManager(vcTree), mBspTree(bspTree)
{
        Environment::GetSingleton()->GetIntValue("BspTree.Construction.samples", mInitialSamples);

        mBspTree->SetViewCellsManager(this);
        mBspTree->SetViewCellsTree(mViewCellsTree);
}


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


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


int BspViewCellsManager::ConstructSubdivision(const ObjectContainer &objects,
                                                                                          const VssRayContainer &rays)
{
        // if view cells were already constructed, we can finish
        if (ViewCellsConstructed())
                return 0;

        int sampleContributions = 0;

        // construct view cells using the collected samples
        RayContainer constructionRays;
        VssRayContainer savedRays;

        // choose a a number of rays based on the ratio of cast rays / requested rays
        const int limit = min(mInitialSamples, (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 (!mUsePredefinedViewCells)
        {
                // no view cells loaded
                mBspTree->Construct(objects, constructionRays, &mViewSpaceBox);
                // collect final view cells
                mBspTree->CollectViewCells(mViewCells);
        }
        else
        {       
                // use predefined view cells geometry => 
                // contruct bsp hierarchy over them
                mBspTree->Construct(mViewCells);
        }

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

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

        // recast rest of the rays
        if (SAMPLE_AFTER_SUBDIVISION)
                ComputeSampleContributions(savedRays, true, false);

        // real meshes are contructed at this stage
        if (0)
        {
                cout << "finalizing view cells ... ";
                FinalizeViewCells(true);
                cout << "finished" << endl;     
        }

        return sampleContributions;
}


void BspViewCellsManager::CollectViewCells()
{       
        if (!ViewCellsTreeConstructed())
        {       // view cells tree constructed  
                mBspTree->CollectViewCells(mViewCells);
        }
        else 
        {       // we can use the view cells tree hierarchy to get the right set
                mViewCellsTree->CollectBestViewCellSet(mViewCells, mNumActiveViewCells);
        }
}


float BspViewCellsManager::GetProbability(ViewCell *viewCell)
{
        if (1)
                return GetVolume(viewCell) / GetViewSpaceBox().GetVolume();
        else
                // compute view cell area as subsititute for probability
                return GetArea(viewCell) / GetAccVcArea();
}



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


void ViewCellsManager::ExportMergedViewCells(const ObjectContainer &objects)
{
        // save color code
        const int savedColorCode = mColorCode;

        Exporter *exporter;

#if 0
        // export merged view cells
        mColorCode = 0; // use random colors

        exporter = Exporter::GetExporter("merged_view_cells.wrl");

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

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

                exporter->SetFilled();
                ExportViewCellsForViz(exporter, NULL, mColorCode, GetClipPlane());

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

        // export merged view cells using pvs color coding
        exporter = Exporter::GetExporter("merged_view_cells_pvs.wrl");
        cout << "exporting view cells after merge (pvs size) ... ";     

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

                exporter->SetFilled();
                mColorCode = 1;

                ExportViewCellsForViz(exporter, NULL,  mColorCode, GetClipPlane());

                delete exporter;
        }
        cout << "finished" << endl;
        
        mColorCode = savedColorCode;
}


int BspViewCellsManager::PostProcess(const ObjectContainer &objects,
                                                                         const VssRayContainer &rays)
{
        if (!ViewCellsConstructed())
        {
                Debug << "view cells not constructed" << endl;
                return 0;
        }
        
        // view cells already finished before post processing step,
        // i.e., because they were loaded from disc
        if (mViewCellsFinished)
        {
                FinalizeViewCells(true);
                EvaluateViewCellsStats();

                return 0;
        }

        //////////////////
        //-- merge leaves of the view cell hierarchy    
        
        cout << "starting post processing using " << mPostProcessSamples << " samples ... ";
        long startTime = GetTime();
        
        VssRayContainer postProcessRays;
        GetRaySets(rays, mPostProcessSamples, postProcessRays);

        if (mMergeViewCells)
        {
                cout << "constructing visibility based merge tree" << endl;
                mViewCellsTree->ConstructMergeTree(rays, objects);
        }
        else
        {
                cout << "constructing spatial merge tree" << endl;
                ViewCell *root;
                // the spatial merge tree is difficult to build for 
                // this type of construction, as view cells cover several
                // leaves => create dummy tree which is only 2 levels deep
                if (mUsePredefinedViewCells) 
                {
                        root = ConstructDummyMergeTree(mBspTree->GetRoot());
                }
                else
                {
                        // create spatial merge hierarchy
                        root = ConstructSpatialMergeTree(mBspTree->GetRoot());
                }
                
                mViewCellsTree->SetRoot(root);

                // recompute pvs in the whole hierarchy
                ObjectPvs pvs;
                UpdatePvsForEvaluation(root, pvs);
        }

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

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

        
        ////////////////////////
        //-- visualization and statistics after merge

        if (1)
        {
                char mstats[100];
                Environment::GetSingleton()->GetStringValue("ViewCells.mergeStats", mstats);
                mViewCellsTree->ExportStats(mstats);
        }

        // recompute view cells and stats
        ResetViewCells();
        Debug << "\nView cells after merge:\n" << mCurrentViewCellsStats << endl;

        //  visualization of the view cells
        if (1) ExportMergedViewCells(objects);

        // compute final meshes and volume / area
        if (1) FinalizeViewCells(true);
        
        return 0;
}


BspViewCellsManager::~BspViewCellsManager()
{
}


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


void BspViewCellsManager::Visualize(const ObjectContainer &objects,
                                                                        const VssRayContainer &sampleRays)
{
        if (!ViewCellsConstructed())
                return;
        
        const int savedColorCode = mColorCode;
        
        if (1) // export final view cells
        {
                mColorCode = 1; // hack color code
                Exporter *exporter = Exporter::GetExporter("final_view_cells.wrl");
        
                cout << "exporting view cells after merge (pvs size) ... ";     

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

                        ExportViewCellsForViz(exporter, NULL, mColorCode, GetClipPlane());
                        delete exporter;
                }
                cout << "finished" << endl;
        }

        // reset color code
        mColorCode = savedColorCode;


        //////////////////
        //-- visualization of the BSP splits

        bool exportSplits = false;
        Environment::GetSingleton()->GetBoolValue("BspTree.Visualization.exportSplits", exportSplits);

        if (exportSplits)
        {
                cout << "exporting splits ... ";
                ExportSplits(objects);
                cout << "finished" << endl;
        }

        int leafOut;
        Environment::GetSingleton()->GetIntValue("ViewCells.Visualization.maxOutput", leafOut);
        const int raysOut = 100;
        ExportSingleViewCells(objects, leafOut, false, true, false, raysOut, "");
}


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

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

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

                delete exporter;
        }
}


void BspViewCellsManager::ExportSingleViewCells(const ObjectContainer &objects,
                                                                                                const int maxViewCells,
                                                                                                const bool sortViewCells,
                                                                                                const bool exportPvs,
                                                                                                const bool exportRays,
                                                                                                const int maxRays,
                                                                                                const string prefix,
                                                                                                VssRayContainer *visRays)
{
        if (sortViewCells)
        {       // sort view cells to visualize the largest view cells
                sort(mViewCells.begin(), mViewCells.end(), ViewCell::LargerRenderCost);
        }

        //////////
        //-- some view cells for output

        ViewCell::NewMail();
        const int limit = min(maxViewCells, (int)mViewCells.size());
        
        for (int i = 0; i < limit; ++ i)
        {
                const int idx = sortViewCells ? (int)RandomValue(0, (float)mViewCells.size() - 0.5f) : i;
                ViewCell *vc = mViewCells[idx];

                if (vc->Mailed() || vc->GetId() == OUT_OF_BOUNDS_ID)
                        continue;

                vc->Mail();

                ObjectPvs pvs;
                mViewCellsTree->GetPvs(vc, pvs);

                char s[64]; sprintf(s, "%sviewcell-%04d.wrl", prefix.c_str(), i);
                Exporter *exporter = Exporter::GetExporter(s);
                
                cout << "view cell " << idx << ": pvs cost=" << (int)mViewCellsTree->GetPvsCost(vc) << endl;

                if (exportRays)
                {
                        ////////////
                        //-- export rays piercing this view cell

                        // use rays stored with the view cells
                        VssRayContainer vcRays, vcRays2, vcRays3;
            VssRayContainer collectRays;

                        // collect initial view cells
                        ViewCellContainer leaves;
                        mViewCellsTree->CollectLeaves(vc, leaves);

                        ViewCellContainer::const_iterator vit, vit_end = leaves.end();
                for (vit = leaves.begin(); vit != vit_end; ++ vit)
                        {       
                                // prepare some rays for output
                                VssRayContainer::const_iterator rit, rit_end = (*vit)->GetOrCreateRays()->end();
                                for (rit = (*vit)->GetOrCreateRays()->begin(); rit != rit_end; ++ rit)
                                {
                                        collectRays.push_back(*rit);
                                }
                        }

                        const int raysOut = min((int)collectRays.size(), maxRays);

                        // prepare some rays for output
                        VssRayContainer::const_iterator rit, rit_end = collectRays.end();
                        for (rit = collectRays.begin(); rit != rit_end; ++ rit)
                        {
                                const float p = RandomValue(0.0f, (float)collectRays.size());
                                if (p < raysOut)
                                {
                                        if ((*rit)->mFlags & VssRay::BorderSample)
                                        {
                                                vcRays.push_back(*rit);
                                        }
                                        else if ((*rit)->mFlags & VssRay::ReverseSample)
                                        {
                                                vcRays2.push_back(*rit);
                                        }
                                        else
                                        {
                                                vcRays3.push_back(*rit);
                                        }       
                                }
                        }

                        exporter->ExportRays(vcRays, RgbColor(1, 0, 0));
                        exporter->ExportRays(vcRays2, RgbColor(0, 1, 0));
                        exporter->ExportRays(vcRays3, RgbColor(1, 1, 1));
                }
                
                ////////////////
                //-- export view cell geometry

                exporter->SetWireframe();

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

                ExportViewCellGeometry(exporter, vc, NULL, NULL);
                exporter->SetFilled();

                if (exportPvs)
                {
                        Intersectable::NewMail();
                        ObjectPvsIterator pit = pvs.GetIterator();

                        while (pit.HasMoreEntries())
                        {               
                                ObjectPvsEntry entry = pit.Next();

                // output PVS of view cell
                                Intersectable *intersect = entry.mObject;
                                
                                if (!intersect->Mailed())
                                {
                                        intersect->Mail();

                                        m = RandomMaterial();
                                        exporter->SetForcedMaterial(m);
                                        exporter->ExportIntersectable(intersect);
                                }
                        }
                        cout << endl;
                }
                
                DEL_PTR(exporter);
                cout << "finished" << endl;
        }
}


void BspViewCellsManager::TestSubdivision()
{
        ViewCellContainer leaves;
        mViewCellsTree->CollectLeaves(mViewCellsTree->GetRoot(), leaves);

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

        const float vol = mViewSpaceBox.GetVolume();
        float subdivVol = 0;
        float newVol = 0;

        for (it = leaves.begin(); it != it_end; ++ it)
        {
                BspNodeGeometry geom;
                mBspTree->ConstructGeometry(*it, geom);

                const float lVol = geom.GetVolume();
                newVol += lVol;
                subdivVol += (*it)->GetVolume();

                const float thres = 0.9f;
                if ((lVol < ((*it)->GetVolume() * thres)) ||
                        (lVol * thres > ((*it)->GetVolume())))
                        Debug << "warning: " << lVol << " " << (*it)->GetVolume() << endl;
        }
        
        Debug << "exact volume: " << vol << endl;
        Debug << "subdivision volume: " << subdivVol << endl;
        Debug << "new volume: " << newVol << endl;
}


void BspViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
                                                                                                 ViewCell *vc,
                                                                                                 const AxisAlignedBox3 *sceneBox,
                                                                                                 const AxisAlignedPlane *clipPlane
                                                                                                 ) const
{
        if (clipPlane)
        {
                const Plane3 plane = clipPlane->GetPlane();

                ViewCellContainer leaves;
                mViewCellsTree->CollectLeaves(vc, leaves);
                ViewCellContainer::const_iterator it, it_end = leaves.end();

                for (it = leaves.begin(); it != it_end; ++ it)
                {
                        BspNodeGeometry geom;
                        BspNodeGeometry front;
                        BspNodeGeometry back;

                        mBspTree->ConstructGeometry(*it, geom);

                        const float eps = 0.0001f;
                        const int cf = geom.Side(plane, eps);

                        if (cf == -1)
                        {
                                exporter->ExportPolygons(geom.GetPolys());
                        }
                        else if (cf == 0)
                        {
                                geom.SplitGeometry(front,
                                                                   back,
                                                                   plane,
                                                                   mViewSpaceBox, 
                                                                   eps);

                                if (back.Valid())
                                {
                                        exporter->ExportPolygons(back.GetPolys());
                                }                       
                        }
                }
        }
        else
        {
                // export mesh if available
                // TODO: some bug here?
                if (1 && vc->GetMesh())
                {
                        exporter->ExportMesh(vc->GetMesh());
                }
                else
                {
                        BspNodeGeometry geom;
                        mBspTree->ConstructGeometry(vc, geom);
                        exporter->ExportPolygons(geom.GetPolys());
                }
        }
}


void BspViewCellsManager::CreateMesh(ViewCell *vc)
{
        // note: should previous mesh be deleted (via mesh manager?)
        BspNodeGeometry geom;
        mBspTree->ConstructGeometry(vc, geom);

        Mesh *mesh = MeshManager::GetSingleton()->CreateResource();

        IncludeNodeGeomInMesh(geom, *mesh);
        vc->SetMesh(mesh);
}


void BspViewCellsManager::Finalize(ViewCell *viewCell, 
                                                                   const bool createMesh)
{
        float area = 0;
        float volume = 0;

        ViewCellContainer leaves;
        mViewCellsTree->CollectLeaves(viewCell, leaves);

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

    for (it = leaves.begin(); it != it_end; ++ it)
        {
                BspNodeGeometry geom;

                mBspTree->ConstructGeometry(*it, geom);

                const float lVol = geom.GetVolume();
                const float lArea = geom.GetArea();

                area += lArea;
                volume += lVol;
        
                CreateMesh(*it);
        }

        viewCell->SetVolume(volume);
        viewCell->SetArea(area);
}


ViewCell *BspViewCellsManager::GetViewCell(const Vector3 &point, const bool active) const
{
        if (!ViewCellsConstructed())
        {
                return NULL;
        }
        if (!mViewSpaceBox.IsInside(point))
        {
                return NULL;
        }
        return mBspTree->GetViewCell(point);
}


void BspViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays, 
                                                                                                 vector<MergeCandidate> &candidates)
{
        cout << "collecting merge candidates ... " << endl;

        if (mUseRaysForMerge)
        {
                mBspTree->CollectMergeCandidates(rays, candidates);
        }
        else
        {
                vector<BspLeaf *> leaves;
                mBspTree->CollectLeaves(leaves);
                mBspTree->CollectMergeCandidates(leaves, candidates);
        }

        cout << "fininshed collecting candidates" << endl;
}



bool BspViewCellsManager::ExportViewCells(const string filename, 
                                                                                  const bool exportPvs, 
                                                                                  const ObjectContainer &objects)
{
        if (!ViewCellsConstructed() || !ViewCellsTreeConstructed())
        {
                return false;
        }

        cout << "exporting view cells to xml ... ";

        OUT_STREAM stream(filename.c_str());

        // for output we need unique ids for each view cell
        CreateUniqueViewCellIds();

        stream << "<?xml version=\"1.0\" encoding=\"UTF-8\"?>"<<endl;
        stream << "<VisibilitySolution>" << endl;

        if (exportPvs) 
        {
                //////////
                //-- export bounding boxes: they are used to identify the objects from the pvs and
                //-- assign them to the entities in the rendering engine

                stream << "<BoundingBoxes>" << endl;
                ObjectContainer::const_iterator oit, oit_end = objects.end();

                for (oit = objects.begin(); oit != oit_end; ++ oit)
                {
                        const AxisAlignedBox3 box = (*oit)->GetBox();
                        
                        stream << "<BoundingBox" << " id=\"" << (*oit)->GetId() << "\""
                                   << " min=\"" << box.Min().x << " " << box.Min().y << " " << box.Min().z << "\""
                                   << " max=\"" << box.Max().x << " " << box.Max().y << " " << box.Max().z << "\" />" << endl;
                }

                stream << "</BoundingBoxes>" << endl;
        }

        ///////////
        //-- export the view cells and the pvs

        const int numViewCells = mCurrentViewCellsStats.viewCells;
        stream << "<ViewCells number=\"" << numViewCells << "\" >" << endl;

        mViewCellsTree->Export(stream, exportPvs);
        
        stream << "</ViewCells>" << endl;

        /////////////
        //-- export the view space hierarchy
        stream << "<ViewSpaceHierarchy type=\"bsp\""
                   << " min=\"" << mViewSpaceBox.Min().x << " " << mViewSpaceBox.Min().y << " " << mViewSpaceBox.Min().z << "\""
                   << " max=\"" << mViewSpaceBox.Max().x << " " << mViewSpaceBox.Max().y << " " << mViewSpaceBox.Max().z << "\">" << endl;

        mBspTree->Export(stream);

        // end tags
        stream << "</ViewSpaceHierarchy>" << endl;
        stream << "</VisibilitySolution>" << endl;

        stream.close();
        cout << "finished" << endl;

        return true;
}


ViewCell *BspViewCellsManager::ConstructDummyMergeTree(BspNode *root)
{
        ViewCellInterior *vcRoot = new ViewCellInterior();
                
        // evaluate merge cost for priority traversal
        const float mergeCost =  -(float)root->mTimeStamp;
        vcRoot->SetMergeCost(mergeCost);

        float volume = 0;
        vector<BspLeaf *> leaves;
        mBspTree->CollectLeaves(leaves);
        vector<BspLeaf *>::const_iterator lit, lit_end = leaves.end();
        ViewCell::NewMail();

        for (lit = leaves.begin(); lit != lit_end; ++ lit)
        {
                BspLeaf *leaf = *lit;
                ViewCell *vc = leaf->GetViewCell();

                if (!vc->Mailed())
                {
                        vc->Mail();
                        vc->SetMergeCost(0.0f);
                        vcRoot->SetupChildLink(vc);

                        volume += vc->GetVolume();
                        volume += vc->GetVolume();      
                        vcRoot->SetVolume(volume);
                }
        }
        
        return vcRoot;
}


ViewCell *BspViewCellsManager::ConstructSpatialMergeTree(BspNode *root)
{
        // terminate recursion
        if (root->IsLeaf())
        {
                BspLeaf *leaf = dynamic_cast<BspLeaf *>(root);
                leaf->GetViewCell()->SetMergeCost(0.0f);
                return leaf->GetViewCell();
        }
        
        BspInterior *interior = dynamic_cast<BspInterior *>(root);
        ViewCellInterior *viewCellInterior = new ViewCellInterior();
                
        // evaluate merge cost for priority traversal
        const float mergeCost = -(float)root->mTimeStamp;
        viewCellInterior->SetMergeCost(mergeCost);

        float volume = 0;
        
        BspNode *front = interior->GetFront();
        BspNode *back = interior->GetBack();


        ////////////
        //-- recursivly compute child hierarchies

        ViewCell *backVc = ConstructSpatialMergeTree(back);
        ViewCell *frontVc = ConstructSpatialMergeTree(front);

        viewCellInterior->SetupChildLink(backVc);
        viewCellInterior->SetupChildLink(frontVc);

        volume += backVc->GetVolume();
        volume += frontVc->GetVolume(); 

        viewCellInterior->SetVolume(volume);

        return viewCellInterior;
}


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



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


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




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


int KdViewCellsManager::ConstructSubdivision(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, true, false);

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

        return 0;
}


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


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


void KdViewCellsManager::ExportSingleViewCells(const ObjectContainer &objects,
                                                                                           const int maxViewCells,
                                                                                           const bool sortViewCells,
                                                                                           const bool exportPvs,
                                                                                           const bool exportRays,
                                                                                           const int maxRays,
                                                                                           const string prefix,
                                                                                           VssRayContainer *visRays)
{
        // TODO
}


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;
                        char str[64]; sprintf(str, "viewcell%04d.wrl", i);

                        Exporter *exporter = Exporter::GetExporter(str);
                        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);

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

                        ObjectPvsIterator pit = vc->GetPvs().GetIterator();
                        
                        while (pit.HasMoreEntries())
                        {               
                                ObjectPvsEntry entry = pit.Next();
                                
                                //-- output PVS of view cell
                                Intersectable *intersect = entry.mObject;
                                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 (int 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 str[64]; sprintf(str, "viewcell%04d.wrl", k);

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

                        // matt: no kd pvs
                        /*
                        KdPvsMap::iterator kit = object->mKdPvs.mEntries.begin();
                        Intersectable::NewMail();

                        // avoid adding the object to the list
                        object->Mail();
                        ObjectContainer visibleObjects;

                        for (; kit != object->mKdPvs.mEntries.end(); i++)
                        {
                                KdNode *node = (*kit).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;
                }
        }
}


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


void KdViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
                                                                                                ViewCell *vc,
                                                                                                const AxisAlignedBox3 *sceneBox,
                                                                                                const AxisAlignedPlane *clipPlane
                                                                                                ) const
{
        ViewCellContainer leaves;
        mViewCellsTree->CollectLeaves(vc, leaves);
        ViewCellContainer::const_iterator it, it_end = leaves.end();

        for (it = leaves.begin(); it != it_end; ++ it)
        {
                KdViewCell *kdVc = dynamic_cast<KdViewCell *>(*it);
                exporter->ExportBox(mKdTree->GetBox(kdVc->mLeaves[0]));
        }
}


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


void KdViewCellsManager::CreateMesh(ViewCell *vc)
{
        // TODO
}



void KdViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays, 
                                                                                                vector<MergeCandidate> &candidates)
{
        // TODO
}



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


VspBspViewCellsManager::VspBspViewCellsManager(ViewCellsTree *vcTree, VspBspTree *vspBspTree):
ViewCellsManager(vcTree), mVspBspTree(vspBspTree)
{
        Environment::GetSingleton()->GetIntValue("VspBspTree.Construction.samples", mInitialSamples);
        mVspBspTree->SetViewCellsManager(this);
        mVspBspTree->mViewCellsTree = mViewCellsTree;
}


VspBspViewCellsManager::~VspBspViewCellsManager()
{
}


float VspBspViewCellsManager::GetProbability(ViewCell *viewCell)
{
        if (0 && mVspBspTree->mUseAreaForPvs)
                return GetArea(viewCell) / GetAccVcArea();
        else
                return GetVolume(viewCell) / mViewSpaceBox.GetVolume();
}


void VspBspViewCellsManager::CollectViewCells()
{
        // view cells tree constructed?
        if (!ViewCellsTreeConstructed())
        {
                mVspBspTree->CollectViewCells(mViewCells, false);
        }
        else 
        {       
                // we can use the view cells tree hierarchy to get the right set
                mViewCellsTree->CollectBestViewCellSet(mViewCells, mNumActiveViewCells);
        }
}


void VspBspViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays, 
                                                                                                        vector<MergeCandidate> &candidates)
{       
        cout << "collecting merge candidates ... " << endl;

        if (mUseRaysForMerge)
        {
                mVspBspTree->CollectMergeCandidates(rays, candidates);
        }
        else
        {
                vector<BspLeaf *> leaves;
                mVspBspTree->CollectLeaves(leaves);
        
                mVspBspTree->CollectMergeCandidates(leaves, candidates);
        }

        cout << "fininshed collecting candidates" << endl;
}


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


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


int VspBspViewCellsManager::ConstructSubdivision(const ObjectContainer &objects,
                                                                                                 const VssRayContainer &rays)
{
        mMaxPvsSize = (int)(mMaxPvsRatio * (float)objects.size());

        // if view cells were already constructed
        if (ViewCellsConstructed())
        {
                return 0;
        }

        int sampleContributions = 0;
        VssRayContainer sampleRays;

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

        Debug << "samples used for vsp bsp subdivision: " << mInitialSamples 
                  << ", actual rays: " << (int)rays.size() << endl;

        VssRayContainer savedRays;

        if (SAMPLE_AFTER_SUBDIVISION)
        {
                VssRayContainer constructionRays;
                
                GetRaySets(rays, mInitialSamples, constructionRays, &savedRays);

                Debug << "rays used for initial construction: " << (int)constructionRays.size() << endl;
                Debug << "rays saved for later use: " << (int)savedRays.size() << endl;
        
                mVspBspTree->Construct(constructionRays, &mViewSpaceBox);
        }
        else
        {
                Debug << "rays used for initial construction: " << (int)rays.size() << endl;
                mVspBspTree->Construct(rays, &mViewSpaceBox);
        }

        // collapse invalid regions
        cout << "collapsing invalid tree regions ... ";
        long startTime = GetTime();

        const int collapsedLeaves = mVspBspTree->CollapseTree();
        Debug << "collapsed in " << TimeDiff(startTime, GetTime()) * 1e-3 
                  << " seconds" << endl;

    cout << "finished" << endl;

        /////////////////
        //-- stats after construction

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

        ResetViewCells();
        Debug << "\nView cells after construction:\n" << mCurrentViewCellsStats << endl;


        //////////////////////
        //-- recast the rest of the rays

        startTime = GetTime();

        cout << "Computing remaining ray contributions ... ";

        if (SAMPLE_AFTER_SUBDIVISION)
                ComputeSampleContributions(savedRays, true, false);

        cout << "finished" << endl;

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

        cout << "construction finished" << endl;

        if (0)
        {       ////////
                //-- real meshes are contructed at this stage

                cout << "finalizing view cells ... ";
                FinalizeViewCells(true);
                cout << "finished" << endl;
        }

        return sampleContributions;
}


void VspBspViewCellsManager::MergeViewCells(const VssRayContainer &rays,
                                                                                        const ObjectContainer &objects)
{
    int vcSize = 0;
        int pvsSize = 0;

        //-- merge view cells
        cout << "starting merge using " << mPostProcessSamples << " samples ... " << endl;
        long startTime = GetTime();


        if (mMergeViewCells)
        {
                // TODO: should be done BEFORE the ray casting
                // compute tree by merging the nodes based on cost heuristics
                mViewCellsTree->ConstructMergeTree(rays, objects);
        }
        else
        {
                // compute tree by merging the nodes of the spatial hierarchy
                ViewCell *root = ConstructSpatialMergeTree(mVspBspTree->GetRoot());
                mViewCellsTree->SetRoot(root);

                // compute pvs
                ObjectPvs pvs;
                UpdatePvsForEvaluation(root, pvs);
        }

        if (1)
        {
                char mstats[100];
                ObjectPvs pvs;

                Environment::GetSingleton()->GetStringValue("ViewCells.mergeStats", mstats);
                mViewCellsTree->ExportStats(mstats);
        }

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

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

        //////////////////
        //-- stats and visualizations

        int savedColorCode = mColorCode;
        
        // get currently active view cell set
        ResetViewCells();
        Debug << "\nView cells after merge:\n" << mCurrentViewCellsStats << endl;
        
        if (mShowVisualization) // export merged view cells
        {
                mColorCode = 0;
                Exporter *exporter = Exporter::GetExporter("merged_view_cells.wrl");
                
                cout << "exporting view cells after merge ... ";

                if (exporter)
                {
                        if (0)
                                exporter->SetWireframe();
                        else
                                exporter->SetFilled();

                        ExportViewCellsForViz(exporter, NULL, mColorCode, GetClipPlane());

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

                                exporter->ExportGeometry(objects);
                        }

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

        if (mShowVisualization) 
        {
                // use pvs size for color coding
                mColorCode = 1;
                Exporter *exporter = Exporter::GetExporter("merged_view_cells_pvs.wrl");

                cout << "exporting view cells after merge (pvs size) ... ";     

                if (exporter)
                {
                        exporter->SetFilled();

                        ExportViewCellsForViz(exporter, NULL, mColorCode, GetClipPlane());

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

                                exporter->ExportGeometry(objects);
                        }

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

        mColorCode = savedColorCode;
}


void VspBspViewCellsManager::RefineViewCells(const VssRayContainer &rays,
                                                                                         const ObjectContainer &objects)
{
        mRenderer->RenderScene();

        SimulationStatistics ss;
        dynamic_cast<RenderSimulator *>(mRenderer)->GetStatistics(ss);
    Debug << "render time before refine\n\n" << ss << endl;

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

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

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


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

        // view cells already finished before post processing step 
        // (i.e. because they were loaded)
        if (mViewCellsFinished)
        {
                FinalizeViewCells(true);
                EvaluateViewCellsStats();

                return 0;
        }

        // check if new view cells turned invalid
        int minPvs, maxPvs;

        if (0)
        {
                minPvs = mMinPvsSize;
                maxPvs = mMaxPvsSize;
        }
        else
        {
                // problem matt: why did I start here from zero?
                minPvs = 0;
                maxPvs = mMaxPvsSize;
        }

        Debug << "setting validity, min: " << minPvs << " max: " << maxPvs << endl;
        cout << "setting validity, min: " << minPvs << " max: " << maxPvs << endl;
        
        SetValidity(minPvs, maxPvs); 

        // update valid view space according to valid view cells
        if (0) mVspBspTree->ValidateTree();

        // area has to be recomputed
        mTotalAreaValid = false;
        VssRayContainer postProcessRays;
        GetRaySets(rays, mPostProcessSamples, postProcessRays);

        Debug << "post processing using " << (int)postProcessRays.size() << " samples" << endl;

        //////////
        //-- merge neighbouring view cells
        MergeViewCells(postProcessRays, objects);
        
        // refines the merged view cells
        if (0) RefineViewCells(postProcessRays, objects);


        ///////////
        //-- render simulation after merge + refine

        cout << "\nview cells partition render time before compress" << endl << endl;;
        dynamic_cast<RenderSimulator *>(mRenderer)->RenderScene();
        SimulationStatistics ss;
        dynamic_cast<RenderSimulator *>(mRenderer)->GetStatistics(ss);
        cout << ss << endl;
        
        if (0) CompressViewCells();
        
        // collapse sibling leaves that share the same view cell
        if (0) mVspBspTree->CollapseTree();

        // recompute view cell list and statistics
        ResetViewCells();

        // compute final meshes and volume / area
        if (1) FinalizeViewCells(true);

        return 0;
}


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


ViewCell *VspBspViewCellsManager::ConstructSpatialMergeTree(BspNode *root)
{
        // terminate recursion
        if (root->IsLeaf())
        {
                BspLeaf *leaf = dynamic_cast<BspLeaf *>(root);
                leaf->GetViewCell()->SetMergeCost(0.0f);
                return leaf->GetViewCell();
        }
        
        
        BspInterior *interior = dynamic_cast<BspInterior *>(root);
        ViewCellInterior *viewCellInterior = new ViewCellInterior();
                
        // evaluate merge cost for priority traversal
        float mergeCost = 1.0f / (float)root->mTimeStamp;
        viewCellInterior->SetMergeCost(mergeCost);

        float volume = 0;
        
        BspNode *front = interior->GetFront();
        BspNode *back = interior->GetBack();


        ObjectPvs frontPvs, backPvs;

        //-- recursivly compute child hierarchies
        ViewCell *backVc = ConstructSpatialMergeTree(back);
        ViewCell *frontVc = ConstructSpatialMergeTree(front);


        viewCellInterior->SetupChildLink(backVc);
        viewCellInterior->SetupChildLink(frontVc);

        volume += backVc->GetVolume();
        volume += frontVc->GetVolume(); 

        viewCellInterior->SetVolume(volume);

        return viewCellInterior;
}


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 = mViewSpaceBox.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
{
        // $$JB -> implemented in viewcellsmanager (slower, but allows dynamic
        // validy update in preprocessor for all managers)
        return ViewCellsManager::ViewPointValid(viewPoint);

        //      return mViewSpaceBox.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 final view cell partition

                Exporter *exporter = Exporter::GetExporter("final_view_cells.wrl");
                
                if (exporter)
                {
                        cout << "exporting view cells after post process ... ";
                        if (0)
                        {       // export view space box
                                exporter->SetWireframe();
                                exporter->ExportBox(mViewSpaceBox);
                                exporter->SetFilled();
                        }

                        Material m; 
                        m.mDiffuseColor.r = 0.0f;
                        m.mDiffuseColor.g = 0.5f;
                        m.mDiffuseColor.b = 0.5f;

            exporter->SetForcedMaterial(m);

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

                        if (0 && mExportRays)
                        {
                                exporter->ExportRays(visRays, RgbColor(1, 0, 0));
                        }
                        ExportViewCellsForViz(exporter, NULL, mColorCode, GetClipPlane());

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

        ////////////////
        //-- visualization of the BSP splits

        bool exportSplits = false;
        Environment::GetSingleton()->GetBoolValue("VspBspTree.Visualization.exportSplits", exportSplits);

        if (exportSplits)
        {
                cout << "exporting splits ... ";
                ExportSplits(objects, visRays);
                cout << "finished" << endl;
        }

        ////////
        //-- export single view cells
        
        int leafOut;
        Environment::GetSingleton()->GetIntValue("ViewCells.Visualization.maxOutput", leafOut);
        const int raysOut = 100;
        
        ExportSingleViewCells(objects, leafOut, false, true, false, raysOut, "");
}


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::ExportSingleViewCells(const ObjectContainer &objects,
                                                                                                   const int maxViewCells,
                                                                                                   const bool sortViewCells,
                                                                                                   const bool exportPvs,
                                                                                                   const bool exportRays,
                                                                                                   const int maxRays,
                                                                                                   const string prefix,
                                                                                                   VssRayContainer *visRays)
{       
        if (sortViewCells)
        {
                // sort view cells to visualize the largest view cells
                sort(mViewCells.begin(), mViewCells.end(), ViewCell::LargerRenderCost);
        }

        //////////
        //-- some view cells for output

        ViewCell::NewMail();
        const int limit = min(maxViewCells, (int)mViewCells.size());
        
        for (int i = 0; i < limit; ++ i)
        {
                cout << "creating output for view cell " << i << " ... ";

                ViewCell *vc = sortViewCells ? // largest view cell pvs first?
                        mViewCells[(int)RandomValue(0, (float)mViewCells.size() - 0.5f)] : mViewCells[i];

                if (vc->Mailed() || vc->GetId() == OUT_OF_BOUNDS_ID)
                        continue;

                vc->Mail();

                ObjectPvs pvs;
                mViewCellsTree->GetPvs(vc, pvs);

                char s[64]; sprintf(s, "%sviewcell%04d.wrl", prefix.c_str(), i);
                Exporter *exporter = Exporter::GetExporter(s);
                
                const float pvsCost = mViewCellsTree->GetPvsCost(vc);
                cout << "view cell " << vc->GetId() << ": pvs cost=" << pvsCost << endl;

                if (exportRays)
                {
                        ////////////
                        //-- export rays piercing this view cell

                        // take rays stored with the view cells during subdivision
                        VssRayContainer vcRays;
            VssRayContainer collectRays;

                        // collect initial view cells
                        ViewCellContainer leaves;
                        mViewCellsTree->CollectLeaves(vc, leaves);

                        ViewCellContainer::const_iterator vit, vit_end = leaves.end();
                for (vit = leaves.begin(); vit != vit_end; ++ vit)
                        {       
                                BspLeaf *vcLeaf = dynamic_cast<BspViewCell *>(*vit)->mLeaves[0];
                                VssRayContainer::const_iterator rit, rit_end = vcLeaf->mVssRays.end();

                                for (rit = vcLeaf->mVssRays.begin(); rit != rit_end; ++ rit)
                                {
                                        collectRays.push_back(*rit);
                                }
                        }

                        const int raysOut = min((int)collectRays.size(), maxRays);
                
                        // prepare some rays for output
                        VssRayContainer::const_iterator rit, rit_end = collectRays.end();
                        for (rit = collectRays.begin(); rit != rit_end; ++ rit)
                        {
                                const float p = RandomValue(0.0f, (float)collectRays.size());
                        
                                if (p < raysOut)
                                {
                                        vcRays.push_back(*rit);
                                }
                        }

                        exporter->ExportRays(vcRays, RgbColor(1, 1, 1));
                }
                
                ////////////////
                //-- export view cell geometry

                exporter->SetWireframe();

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

                ExportViewCellGeometry(exporter, vc, NULL, NULL);
                exporter->SetFilled();

                if (exportPvs)
                {
                        Intersectable::NewMail();

                        ObjectPvsIterator pit = pvs.GetIterator();

                        cout << endl;

                        // output PVS of view cell
                        while (pit.HasMoreEntries())
                        {
                                ObjectPvsEntry entry = pit.Next();              
                                Intersectable *intersect = entry.mObject;
                                
                                if (!intersect->Mailed())
                                {
                                        intersect->Mail();

                                        m = RandomMaterial();
                                        exporter->SetForcedMaterial(m);
                                        exporter->ExportIntersectable(intersect);
                                }
                        }
                        cout << endl;
                }
                
                DEL_PTR(exporter);
                cout << "finished" << endl;
        }
}


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

        Vector3 bsize = mViewSpaceBox.Size();
        const Vector3 viewPoint(mViewSpaceBox.Center());
        float w = Magnitude(mViewSpaceBox.Size()) * mFilterWidth;
        const Vector3 width = Vector3(w);
        
        PrVs testPrVs;
        
        if (exporter)
        {
                ViewCellContainer viewCells;
        
        const AxisAlignedBox3 tbox = GetFilterBBox(viewPoint, mFilterWidth);

                GetPrVS(viewPoint, testPrVs, GetFilterWidth());

                exporter->SetWireframe();

                exporter->SetForcedMaterial(RgbColor(1,1,1));
                exporter->ExportBox(tbox);
                
                exporter->SetFilled();

                exporter->SetForcedMaterial(RgbColor(0,1,0));
                ExportViewCellGeometry(exporter, GetViewCell(viewPoint), NULL, NULL);

                //exporter->ResetForcedMaterial();
                exporter->SetForcedMaterial(RgbColor(0,0,1));
                ExportViewCellGeometry(exporter, testPrVs.mViewCell, NULL, NULL);

        exporter->SetForcedMaterial(RgbColor(1,0,0));
                exporter->ExportGeometry(objects);

                delete exporter;
        }
}


int VspBspViewCellsManager::ComputeBoxIntersections(const AxisAlignedBox3 &box, 
                                                                                                        ViewCellContainer &viewCells) const
{
        return mVspBspTree->ComputeBoxIntersections(box, viewCells);
}


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


void VspBspViewCellsManager::VisualizeWithFromPointQueries()
{
        int numSamples;
        
        Environment::GetSingleton()->GetIntValue("RenderSampler.samples", numSamples);
        cout << "samples" << numSamples << endl;

        vector<RenderCostSample> samples;
  
        if (!mPreprocessor->GetRenderer())
                return;

        //start the view point queries
        long startTime = GetTime();
        cout << "starting sampling of render cost ... ";
        
        mPreprocessor->GetRenderer()->SampleRenderCost(numSamples, samples, true);

        cout << "finished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;


        // for each sample:
        //    find view cells associated with the samples
        //    store the sample pvs with the pvs associated with the view cell
        //
        // for each view cell:
        //    compute difference point sampled pvs - view cell pvs
        //    export geometry with color coded pvs difference
        
    std::map<ViewCell *, ObjectPvs> sampleMap;

        vector<RenderCostSample>::const_iterator rit, rit_end = samples.end();

        for (rit = samples.begin(); rit != rit_end; ++ rit)
        {
                RenderCostSample sample = *rit;
        
                ViewCell *vc = GetViewCell(sample.mPosition);

                std::map<ViewCell *, ObjectPvs>::iterator it = sampleMap.find(vc);

                if (it == sampleMap.end())
                {
                        sampleMap[vc] = sample.mPvs;
                }
                else
                {
                        (*it).second.MergeInPlace(sample.mPvs);
                }
        }

        // visualize the view cells
        std::map<ViewCell *, ObjectPvs>::const_iterator vit, vit_end = sampleMap.end();

        Material m;//= RandomMaterial();

        for (vit = sampleMap.begin(); vit != vit_end; ++ vit)
        {
                ViewCell *vc = (*vit).first;
                
                const int pvsVc = mViewCellsTree->GetPvsEntries(vc);
                const int pvsPtSamples = (*vit).second.GetSize();

        m.mDiffuseColor.r = (float) (pvsVc - pvsPtSamples);
                m.mDiffuseColor.b = 1.0f;
                //exporter->SetForcedMaterial(m);
                //ExportViewCellGeometry(exporter, vc, mClipPlaneForViz);

                /*      // counting the pvss
                for (rit = samples.begin(); rit != rit_end; ++ rit)
                {
                        RenderCostSample sample = *rit;
                        ViewCell *vc = GetViewCell(sample.mPosition);

                        AxisAlignedBox3 box(sample.mPosition - Vector3(1, 1, 1), sample.mPosition + Vector3(1, 1, 1));
                        Mesh *hMesh = CreateMeshFromBox(box);

                        DEL_PTR(hMesh);
                }
                */
        }
}


void VspBspViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
                                                                                                        ViewCell *vc,
                                                                                                        const AxisAlignedBox3 *sceneBox,
                                                                                                        const AxisAlignedPlane *clipPlane
                                                                                                        ) const
{
        if (clipPlane)
        {
                const Plane3 plane = clipPlane->GetPlane();

                ViewCellContainer leaves;
                mViewCellsTree->CollectLeaves(vc, leaves);
                ViewCellContainer::const_iterator it, it_end = leaves.end();

                for (it = leaves.begin(); it != it_end; ++ it)
                {
                        BspNodeGeometry geom;
                        BspNodeGeometry front;
                        BspNodeGeometry back;

                        mVspBspTree->ConstructGeometry(*it, geom);

                        const float eps = 0.0001f;
                        const int cf = geom.Side(plane, eps);

                        if (cf == -1)
                        {
                                exporter->ExportPolygons(geom.GetPolys());
                        }
                        else if (cf == 0)
                        {
                                geom.SplitGeometry(front,
                                                                   back,
                                                                   plane,
                                                                   mViewSpaceBox, 
                                                                   eps);

                                if (back.Valid())
                                {
                                        exporter->ExportPolygons(back.GetPolys());
                                }                       
                        }
                }
        }
        else
        {
                // export mesh if available
                // TODO: some bug here?
                if (1 && vc->GetMesh())
                {
                        exporter->ExportMesh(vc->GetMesh());
                }
                else
                {
                        BspNodeGeometry geom;
                        mVspBspTree->ConstructGeometry(vc, geom);
                        exporter->ExportPolygons(geom.GetPolys());
                }
        }
}


int VspBspViewCellsManager::GetMaxTreeDiff(ViewCell *vc) const
{
        ViewCellContainer leaves;
        mViewCellsTree->CollectLeaves(vc, leaves);

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

                        if (i != j)
                        {
                                BspLeaf *leaf2 =dynamic_cast<BspViewCell *>(leaves[j])->mLeaves[0];
                                const int dist = mVspBspTree->TreeDistance(leaf, leaf2);
                                
                                if (dist > maxDist)
                                        maxDist = dist;
                        }
                }
        }

        return maxDist;
}


ViewCell *VspBspViewCellsManager::GetViewCell(const Vector3 &point, const bool active) const
{
        if (!ViewCellsConstructed())
                return NULL;

        if (!mViewSpaceBox.IsInside(point))
          return NULL;

        return mVspBspTree->GetViewCell(point, active);
}


void VspBspViewCellsManager::CreateMesh(ViewCell *vc)
{
        BspNodeGeometry geom;
        mVspBspTree->ConstructGeometry(vc, geom);
        
        Mesh *mesh = MeshManager::GetSingleton()->CreateResource();
        IncludeNodeGeomInMesh(geom, *mesh);

        vc->SetMesh(mesh);
}


int VspBspViewCellsManager::CastBeam(Beam &beam)
{
        return mVspBspTree->CastBeam(beam);
}


void VspBspViewCellsManager::Finalize(ViewCell *viewCell, 
                                                                          const bool createMesh)
{
        float area = 0;
        float volume = 0;

        ViewCellContainer leaves;
        mViewCellsTree->CollectLeaves(viewCell, leaves);

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

    for (it = leaves.begin(); it != it_end; ++ it)
        {
                BspNodeGeometry geom;
                mVspBspTree->ConstructGeometry(*it, geom);

                const float lVol = geom.GetVolume();
                const float lArea = geom.GetArea();

                area += lArea;
                volume += lVol;

                if (createMesh)
                        CreateMesh(*it);
        }

        viewCell->SetVolume(volume);
        viewCell->SetArea(area);
}


void VspBspViewCellsManager::TestSubdivision()
{
        ViewCellContainer leaves;
        mViewCellsTree->CollectLeaves(mViewCellsTree->GetRoot(), leaves);

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

        const float vol = mViewSpaceBox.GetVolume();
        float subdivVol = 0;
        float newVol = 0;

        for (it = leaves.begin(); it != it_end; ++ it)
        {
                BspNodeGeometry geom;
                mVspBspTree->ConstructGeometry(*it, geom);

                const float lVol = geom.GetVolume();
                
                newVol += lVol;
                subdivVol += (*it)->GetVolume();
                
                float thres = 0.9f;
                if ((lVol < ((*it)->GetVolume() * thres)) || (lVol * thres > ((*it)->GetVolume())))
                        Debug << "warning: " << lVol << " " << (*it)->GetVolume() << endl;
        }
        
        Debug << "exact volume: " << vol << endl;
        Debug << "subdivision volume: " << subdivVol << endl;
        Debug << "new volume: " << newVol << endl;
}


void VspBspViewCellsManager::PrepareLoadedViewCells()
{
        // TODO: do I still need this here?
        if (0)
                mVspBspTree->RepairViewCellsLeafLists();
}



/************************************************************************/
/*                 VspOspViewCellsManager implementation                */
/************************************************************************/


VspOspViewCellsManager::VspOspViewCellsManager(ViewCellsTree *vcTree, 
                                                                                           const string &hierarchyType)
: ViewCellsManager(vcTree)
{
        Environment::GetSingleton()->GetIntValue("Hierarchy.Construction.samples", mInitialSamples);

        Environment::GetSingleton()->GetBoolValue("ViewCells.compressObjects", mCompressObjects);

        Debug << "compressing objects: " << mCompressObjects << endl;
        cout << "compressing objects: " << mCompressObjects << endl;

        mHierarchyManager = CreateHierarchyManager(hierarchyType);
        mHierarchyManager->SetViewCellsManager(this);
        mHierarchyManager->SetViewCellsTree(mViewCellsTree);
}


VspOspViewCellsManager::VspOspViewCellsManager(ViewCellsTree *vcTree, HierarchyManager *hm)
: ViewCellsManager(vcTree), mHierarchyManager(hm)
{
        Environment::GetSingleton()->GetIntValue("Hierarchy.Construction.samples", mInitialSamples);
        Environment::GetSingleton()->GetBoolValue("ViewCells.compressObjects", mCompressObjects);

        Debug << "compressing objects: " << mCompressObjects << endl;
        cout << "compressing objects: " << mCompressObjects << endl;

        mHierarchyManager->SetViewCellsManager(this);
        mHierarchyManager->SetViewCellsTree(mViewCellsTree);
}


Intersectable *
VspOspViewCellsManager::GetIntersectable(const VssRay &ray, const bool isTermination) const
{
        if (mUseKdPvs)
        {
                return ViewCellsManager::GetIntersectable(ray, isTermination);
        }
        else
        {
                return mHierarchyManager->GetIntersectable(ray, isTermination);
        }
}


HierarchyManager *VspOspViewCellsManager::CreateHierarchyManager(const string &hierarchyType)
{
        HierarchyManager *hierarchyManager;

        if (strcmp(hierarchyType.c_str(), "osp") == 0)
        {
                Debug << "hierarchy manager: osp" << endl;
                hierarchyManager = new HierarchyManager(HierarchyManager::KD_BASED_OBJ_SUBDIV);
        }
        else if (strcmp(hierarchyType.c_str(), "bvh") == 0)
        {
                Debug << "hierarchy manager: bvh" << endl;
                hierarchyManager = new HierarchyManager(HierarchyManager::BV_BASED_OBJ_SUBDIV);
        }
        else // only view space partition
        {
                Debug << "hierarchy manager: obj" << endl;
                hierarchyManager = new HierarchyManager(HierarchyManager::NO_OBJ_SUBDIV);
        }

        return hierarchyManager;
}


VspOspViewCellsManager::~VspOspViewCellsManager()
{
        DEL_PTR(mHierarchyManager);
}


float VspOspViewCellsManager::GetProbability(ViewCell *viewCell)
{
        return GetVolume(viewCell) / mViewSpaceBox.GetVolume();
}


void VspOspViewCellsManager::CollectViewCells()
{
        // view cells tree constructed
        if (!ViewCellsTreeConstructed())
        {
                mHierarchyManager->GetVspTree()->CollectViewCells(mViewCells, false);
        }
        else 
        {       // we can use the view cells tree hierarchy to get the right set
                mViewCellsTree->CollectBestViewCellSet(mViewCells, mNumActiveViewCells);
        }
}


bool VspOspViewCellsManager::ViewCellsConstructed() const
{
        return mHierarchyManager->GetVspTree()->GetRoot() != NULL;
}


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


int VspOspViewCellsManager::ConstructSubdivision(const ObjectContainer &objects,
                                                                                                 const VssRayContainer &rays)
{
        mMaxPvsSize = (int)(mMaxPvsRatio * (float)objects.size());

        // skip rest if view cells were already constructed
        if (ViewCellsConstructed())
                return 0;

        int sampleContributions = 0;
        VssRayContainer sampleRays;

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

        VssRayContainer constructionRays;
        VssRayContainer savedRays;

        Debug << "samples used for vsp bsp subdivision: " << mInitialSamples 
                  << ", actual rays: " << (int)rays.size() << endl;

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

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

        mHierarchyManager->Construct(constructionRays, objects, &mViewSpaceBox);

#if TEST_EVALUATION
        VssRayContainer::const_iterator tit, tit_end = constructionRays.end();
        for (tit = constructionRays.begin(); tit != tit_end; ++ tit)
        {
                storedRays.push_back(new VssRay(*(*tit)));
        }
#endif

        /////////////////////////
        //-- print satistics for subdivision and view cells

        Debug << endl << endl << *mHierarchyManager << endl;

        ResetViewCells();
        Debug << "\nView cells after construction:\n" << mCurrentViewCellsStats << endl;

        //////////////
        //-- recast rest of rays
        
        const long startTime = GetTime();
        cout << "Computing remaining ray contributions ... ";

        if (SAMPLE_AFTER_SUBDIVISION)
                ComputeSampleContributions(savedRays, true, false);

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

        if (0)
        {       
                // real meshes are constructed at this stage
                cout << "finalizing view cells ... ";
        FinalizeViewCells(true);
                cout << "finished" << endl;
        }

        return sampleContributions;
}


int VspOspViewCellsManager::PostProcess(const ObjectContainer &objects,
                                                                                const VssRayContainer &rays)
{
        if (!ViewCellsConstructed())
        {
                Debug << "post process error: no view cells constructed" << endl;
                return 0;
        }

        // if view cells were already constructed before post processing step 
        // (e.g., because they were loaded), we are finished
        if (mViewCellsFinished)
        {
                FinalizeViewCells(true);
                EvaluateViewCellsStats();

                return 0;
        }

        // check if new view cells turned invalid
        int minPvs, maxPvs;

        if (0)
        {
                minPvs = mMinPvsSize;
                maxPvs = mMaxPvsSize;
        }
        else
        {
                // problem matt: why did I start here from zero?
                minPvs = 0;
                maxPvs = mMaxPvsSize;
        }

        Debug << "setting validity, min: " << minPvs << " max: " << maxPvs << endl;
        cout << "setting validity, min: " << minPvs << " max: " << maxPvs << endl;
        
        SetValidity(minPvs, maxPvs); 

        
        // area is not up to date, has to be recomputed
        mTotalAreaValid = false;
        VssRayContainer postProcessRays;
        GetRaySets(rays, mPostProcessSamples, postProcessRays);

        Debug << "post processing using " << (int)postProcessRays.size() << " samples" << endl;


        // compute tree by merging the nodes of the spatial hierarchy
        ViewCell *root = ConstructSpatialMergeTree(mHierarchyManager->GetVspTree()->GetRoot());
        mViewCellsTree->SetRoot(root);

        //////////////////////////
        //-- update pvs up to the root of the hierarchy

        ObjectPvs pvs;
        UpdatePvsForEvaluation(root, pvs);


        //////////////////////
        //-- render simulation after merge + refine

        cout << "\nview cells partition render time before compress" << endl << endl;
        dynamic_cast<RenderSimulator *>(mRenderer)->RenderScene();
        SimulationStatistics ss;
        dynamic_cast<RenderSimulator *>(mRenderer)->GetStatistics(ss);
        cout << ss << endl;
        

        mHierarchyManager->CreateUniqueObjectIds();

        ///////////
        //-- compression

        if (0) CompressViewCells();

        /////////////
        //-- some tasks still to do on the view cells:
        //-- Compute meshes from view cell geometry, evaluate volume and / or area

        if (1) FinalizeViewCells(true);

        return 0;
}


int VspOspViewCellsManager::GetType() const
{
        return VSP_OSP;
}


ViewCell *VspOspViewCellsManager::ConstructSpatialMergeTree(VspNode *root)
{
        // terminate recursion
        if (root->IsLeaf())
        {
                VspLeaf *leaf = dynamic_cast<VspLeaf *>(root);
                leaf->GetViewCell()->SetMergeCost(0.0f);
                return leaf->GetViewCell();
        }
        
        VspInterior *interior = dynamic_cast<VspInterior *>(root);
        ViewCellInterior *viewCellInterior = new ViewCellInterior();
                
        // evaluate merge cost for priority traversal
        const float mergeCost = -(float)root->mTimeStamp;
        viewCellInterior->SetMergeCost(mergeCost);

        float volume = 0;
        
        VspNode *front = interior->GetFront();
        VspNode *back = interior->GetBack();

        ObjectPvs frontPvs, backPvs;

        /////////
        //-- recursivly compute child hierarchies

        ViewCell *backVc = ConstructSpatialMergeTree(back);
        ViewCell *frontVc = ConstructSpatialMergeTree(front);

        viewCellInterior->SetupChildLink(backVc);
        viewCellInterior->SetupChildLink(frontVc);

        volume += backVc->GetVolume();
        volume += frontVc->GetVolume(); 

        viewCellInterior->SetVolume(volume);

        return viewCellInterior;
}


bool VspOspViewCellsManager::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 = mViewSpaceBox.GetRandomPoint();

                if (mHierarchyManager->GetVspTree()->ViewPointValid(viewPoint))
                {
                        return true;
                }
        }

        Debug << "failed to find valid view point, taking " << viewPoint << endl;
        return false;
}


void VspOspViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
                                                                                                        ViewCell *vc,
                                                                                                        const AxisAlignedBox3 *sceneBox,
                                                                                                        const AxisAlignedPlane *clipPlane
                                                                                                        ) const
{
        ViewCellContainer leaves;
        mViewCellsTree->CollectLeaves(vc, leaves);
        ViewCellContainer::const_iterator it, it_end = leaves.end();

        Plane3 plane;
        if (clipPlane)
        {
                // arbitrary plane definition
                plane = clipPlane->GetPlane();
        }

        for (it = leaves.begin(); it != it_end; ++ it)
        {
                VspViewCell *vspVc = dynamic_cast<VspViewCell *>(*it);
                VspLeaf *l = vspVc->mLeaves[0];

                const AxisAlignedBox3 box = 
                        mHierarchyManager->GetVspTree()->GetBoundingBox(vspVc->mLeaves[0]);
                
                if (sceneBox && !Overlap(*sceneBox, box))
                        continue;

                if (clipPlane)
                {
                        if (box.Side(plane) == -1)
                        {
                                exporter->ExportBox(box);
                        }
                        else if (box.Side(plane) == 0)
                        {
                                // intersection
                                AxisAlignedBox3 fbox, bbox;
                                box.Split(clipPlane->mAxis, clipPlane->mPosition, fbox, bbox);
                                exporter->ExportBox(bbox);
                        }
                }
                else
                {
                        exporter->ExportBox(box);
                }
        }
}


bool VspOspViewCellsManager::ViewPointValid(const Vector3 &viewPoint) const
{
  // $$JB -> implemented in viewcellsmanager (slower, but allows dynamic
  // validy update in preprocessor for all managers)
  return ViewCellsManager::ViewPointValid(viewPoint);

  //    return mViewSpaceBox.IsInside(viewPoint) &&
  //               mVspTree->ViewPointValid(viewPoint);
}


float VspOspViewCellsManager::UpdateObjectCosts()
{
        float maxRenderCost = 0;

        cout << "updating object pvs cost ... ";
        const long startTime = GetTime();

        ViewCellContainer::const_iterator vit, vit_end = mViewCells.end();

        Intersectable::NewMail();

        const float invViewSpaceVol = 1.0f / GetViewSpaceBox().GetVolume();

        for (vit = mViewCells.begin(); vit != vit_end; ++ vit)
        {
                ViewCell *vc = *vit;

                ObjectPvsIterator pit = vc->GetPvs().GetIterator();

                // output PVS of view cell
                while (pit.HasMoreEntries())
                {               
                        ObjectPvsEntry entry = pit.Next();
                                
                        BvhNode *node = dynamic_cast<BvhNode *>(entry.mObject);
                        
                        // hack!!
                        if (!node->IsLeaf())
                        {
                                cout << "error, can only do leaves" << endl;
                                return 0;
                        }
        
                        if (!node->Mailed())
                        {
                                node->Mail();
                                node->mRenderCost = 0;
                        }

                        const float rc = (float)((BvhLeaf *)node)->mObjects.size();

                        node->mRenderCost += rc * vc->GetVolume() * invViewSpaceVol;

                        if (node->mRenderCost > maxRenderCost)
                                maxRenderCost = node->mRenderCost;
                }
        }

        cout << "finished in " << TimeDiff(startTime, GetTime()) * 1e-3f << " secs" << endl;

        return maxRenderCost;
}


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

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

        ////////////
        //-- export final view cells

        Exporter *exporter = Exporter::GetExporter("final_view_cells.wrl");

        //Vector3 scale(0.9f, 0.9f, 0.9f);
        Vector3 scale(1.0f, 1.0f, 1.0f);

        if (exporter)
        {
                if (CLAMP_TO_BOX)
                {       
                        exporter->mClampToBox = true;   
                }

                EvaluateViewCellsStats();

                const long starttime = GetTime();
                cout << "exporting final view cells (after initial construction + post process) ... ";

                // matt: hack for clamping scene
                AxisAlignedBox3 bbox = mViewSpaceBox;
                bbox.Scale(scale);

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

                // hack color code (show pvs size)
                const int savedColorCode = mColorCode;

                const float maxRenderCost = UpdateObjectCosts();
                cout << "maxRenderCost: " << maxRenderCost << endl;
                mColorCode = 0; // 0 = random, 1 = export pvs

                mHierarchyManager->ExportObjectSpaceHierarchy(exporter, objects, 
                                                                                                          CLAMP_TO_BOX ? &bbox : NULL, maxRenderCost, false);
                

                //ExportViewCellsForViz(exporter, CLAMP_TO_BOX ? &bbox : NULL, mColorCode, GetClipPlane());
                ExportViewCellsForViz(exporter, NULL, mColorCode, GetClipPlane());

                delete exporter;

                cout << "finished in " << TimeDiff(starttime, GetTime()) * 1e-3f << " secs" << endl;
                mColorCode = savedColorCode;
        }

        exporter = Exporter::GetExporter("final_object_partition.wrl");

        if (exporter)
        {
                if (CLAMP_TO_BOX)
                {       
                        exporter->mClampToBox = true;   
                }

                EvaluateViewCellsStats();

                const long starttime = GetTime();
                cout << "exporting final objects (after initial construction + post process) ... ";

                // matt: hack for clamping scene
                AxisAlignedBox3 bbox = mViewSpaceBox;
                bbox.Scale(scale);

                // hack color code (show pvs size)
                const int savedColorCode = mColorCode;

                mColorCode = 1; // 0 = random, 1 = export pvs
                const float maxRenderCost = -1;

                mHierarchyManager->ExportObjectSpaceHierarchy(exporter, objects, 
                                                                                                          CLAMP_TO_BOX ? &bbox : NULL, maxRenderCost, false);
                

                //ExportViewCellsForViz(exporter, CLAMP_TO_BOX ? &bbox : NULL, mColorCode, GetClipPlane());
                ExportViewCellsForViz(exporter, NULL, mColorCode, GetClipPlane());

                delete exporter;

                cout << "finished in " << TimeDiff(starttime, GetTime()) * 1e-3f << " secs" << endl;
                mColorCode = savedColorCode;
        }

#if 0
        // export final object partition
        exporter = Exporter::GetExporter("final_object_partition.wrl");

        if (exporter)
        {
                if (CLAMP_TO_BOX)
                {       
                        exporter->mClampToBox = true;   
                }

                const long starttime = GetTime();

                // matt: hack for making visualization smaller in size
                AxisAlignedBox3 bbox = mHierarchyManager->GetObjectSpaceBox();
                bbox.Scale(scale);

                cout << "exporting object space hierarchy ... ";
                mHierarchyManager->ExportObjectSpaceHierarchy(exporter, objects, CLAMP_TO_BOX ? &bbox : NULL, -1);

                delete exporter;
                cout << "finished in " << TimeDiff(starttime, GetTime()) * 1e-3f << " secs" << endl;
        }
#endif

        // visualization of the view cells
    if (0) 
        {       
                ExportMergedViewCells(objects);
        }

        // export some view cells
        int leafOut;
        Environment::GetSingleton()->GetIntValue("ViewCells.Visualization.maxOutput", leafOut);

        const bool sortViewCells = false;
        const bool exportPvs = true;
        const bool exportRays = true;
        const int raysOut = 100;

        ExportSingleViewCells(objects, 
                                                  leafOut, 
                                                  sortViewCells, 
                                                  exportPvs, 
                                                  exportRays, 
                                                  raysOut, 
                                                  "");
}


void VspOspViewCellsManager::ExportSingleViewCells(const ObjectContainer &objects,
                                                                                                   const int maxViewCells,
                                                                                                   const bool sortViewCells,
                                                                                                   const bool exportPvs,
                                                                                                   const bool exportRays,
                                                                                                   const int maxRays,
                                                                                                   const string prefix,
                                                                                                   VssRayContainer *visRays)
{
        if (sortViewCells)
        {
                // sort view cells to visualize the view cells with highest render cost
                sort(mViewCells.begin(), mViewCells.end(), ViewCell::LargerRenderCost);
        }

        ViewCell::NewMail();
        const int limit = min(maxViewCells, (int)mViewCells.size());
        
        cout << "\nExporting " << limit << " single view cells: " << endl;
        
        for (int i = 0; i < limit; ++ i)
        {
                cout << "creating output for view cell " << i << " ... ";
                
                // largest view cell pvs first of random view cell
                ViewCell *vc = sortViewCells ? 
                        mViewCells[i] : mViewCells[(int)RandomValue(0, (float)mViewCells.size() - 1)];
                
                if (vc->Mailed()) // view cell already processed
                        continue;

                vc->Mail();

                ObjectPvs pvs;
                mViewCellsTree->GetPvs(vc, pvs);

                char s[64]; sprintf(s, "%sviewcell%04d.wrl", prefix.c_str(), i);
                Exporter *exporter = Exporter::GetExporter(s);
                
                cout << "view cell " << vc->GetId() << ": pvs cost=" << mViewCellsTree->GetPvsCost(vc) << endl;

                if (exportPvs)
                {
                        Material m;

                        Intersectable::NewMail();
                        
                        ObjectPvsIterator pit = pvs.GetIterator();

                        // output PVS of view cell
                        while (pit.HasMoreEntries())
                        {               
                                ObjectPvsEntry entry = pit.Next();
                                
                                Intersectable *intersect = entry.mObject;

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

                                        exporter->ExportIntersectable(intersect);
                                        intersect->Mail();
                                }
                        }
                }

                if (exportRays)
                {
                        ////////////
                        //-- export the sample rays

                        // output rays stored with the view cells during subdivision
                        VssRayContainer vcRays;
                        VssRayContainer collectRays;

                        // collect intial view cells
                        ViewCellContainer leaves;
                        mViewCellsTree->CollectLeaves(vc, leaves);

                        ViewCellContainer::const_iterator vit, vit_end = leaves.end();

                        for (vit = leaves.begin(); vit != vit_end; ++ vit)
                        {
                                VspLeaf *vcLeaf = dynamic_cast<VspViewCell *>(*vit)->mLeaves[0];
                                VssRayContainer::const_iterator rit, rit_end = vcLeaf->mVssRays.end();

                                for (rit = vcLeaf->mVssRays.begin(); rit != rit_end; ++ rit)
                                {
                                        collectRays.push_back(*rit);
                                }
                        }

                        const int raysOut = min((int)collectRays.size(), maxRays);

                        VssRayContainer::const_iterator rit, rit_end = collectRays.end();

                        for (rit = collectRays.begin(); rit != rit_end; ++ rit)
                        {
                                const float p = RandomValue(0.0f, (float)collectRays.size());

                                if (p < raysOut)
                                        vcRays.push_back(*rit);
                        }

                        exporter->ExportRays(vcRays, RgbColor(1, 1, 1));
                }
                
        
                /////////////////
                //-- export view cell geometry

                exporter->SetWireframe();

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

                ExportViewCellGeometry(exporter, vc, NULL, NULL);
                exporter->SetFilled();

                DEL_PTR(exporter);
                cout << "finished" << endl;
        }

        cout << endl;
}


int VspOspViewCellsManager::ComputeBoxIntersections(const AxisAlignedBox3 &box, 
                                                                                                        ViewCellContainer &viewCells) const
{
        return mHierarchyManager->GetVspTree()->ComputeBoxIntersections(box, viewCells);
}


int VspOspViewCellsManager::CastLineSegment(const Vector3 &origin,
                                                                                        const Vector3 &termination,
                                                                                        ViewCellContainer &viewcells)
{
        return mHierarchyManager->GetVspTree()->CastLineSegment(origin, termination, viewcells);
}


bool VspOspViewCellsManager::ExportViewCells(const string filename, 
                                                                                         const bool exportPvs, 
                                                                                         const ObjectContainer &objects)
{
        if (!ViewCellsConstructed() || !ViewCellsTreeConstructed())
                return false;

        const long starttime = GetTime();
        cout << "exporting view cells to xml ... ";
        
        OUT_STREAM stream(filename.c_str());

        // for output we need unique ids for each view cell
        CreateUniqueViewCellIds();

        stream << "<?xml version=\"1.0\" encoding=\"UTF-8\"?>"<<endl;
        stream << "<VisibilitySolution>" << endl;

        // §§ tmp matt: for storage cost
        if (0 && exportPvs) 
        {
        ///////////////
                //-- export bounding boxes
                //-- The bounding boxes are used to identify 
                //-- the objects in the rendering engine
                mHierarchyManager->ExportBoundingBoxes(stream, objects);
        }

        //////////////////////////
        //-- export the view cells and the pvs

        const int numViewCells = mCurrentViewCellsStats.viewCells;

        stream << "<ViewCells number=\"" << numViewCells << "\" >" << endl;
        mViewCellsTree->Export(stream, exportPvs);
        stream << "</ViewCells>" << endl;

        //////////////////////
        //-- export the view space hierarchy
        
        stream << "<ViewSpaceHierarchy type=\"vsp\""
                   << " min=\"" << mViewSpaceBox.Min().x << " " << mViewSpaceBox.Min().y << " " << mViewSpaceBox.Min().z << "\""
                   << " max=\"" << mViewSpaceBox.Max().x << " " << mViewSpaceBox.Max().y << " " << mViewSpaceBox.Max().z << "\">" << endl;

        mHierarchyManager->GetVspTree()->Export(stream);
        stream << "</ViewSpaceHierarchy>" << endl;

        //////////////////////  
        //-- export the object space partition
        
        mHierarchyManager->ExportObjectSpaceHierarchy(stream);
        
        stream << "</VisibilitySolution>" << endl;
        stream.close();
        
        cout << "finished in " << TimeDiff(starttime, GetTime()) * 1e-3 << " secs" << endl;
        return true;
}



ViewCell *VspOspViewCellsManager::GetViewCell(const Vector3 &point, 
                                                                                          const bool active) const
{
        if (!ViewCellsConstructed())
                return NULL;

        if (!mViewSpaceBox.IsInside(point))
                return NULL;

        return mHierarchyManager->GetVspTree()->GetViewCell(point, active);
}


void VspOspViewCellsManager::CreateMesh(ViewCell *vc)
{
        // matt: TODO
        Mesh *mesh = MeshManager::GetSingleton()->CreateResource();

        ViewCellContainer leaves;
        mViewCellsTree->CollectLeaves(vc, leaves);

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

    for (it = leaves.begin(); it != it_end; ++ it)
        {
                VspLeaf *leaf = dynamic_cast<VspViewCell *>(*it)->mLeaves[0];
                const AxisAlignedBox3 box = mHierarchyManager->GetVspTree()->GetBoundingBox(leaf);
        IncludeBoxInMesh(box, *mesh);
        }

        vc->SetMesh(mesh);
}


int VspOspViewCellsManager::CastBeam(Beam &beam)
{
        // matt: TODO
        return 0;
}


void VspOspViewCellsManager::Finalize(ViewCell *viewCell, const bool createMesh)
{
        float area = 0;
        float volume = 0;

        ViewCellContainer leaves;
        mViewCellsTree->CollectLeaves(viewCell, leaves);

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

    for (it = leaves.begin(); it != it_end; ++ it)
        {
                VspLeaf *leaf = dynamic_cast<VspViewCell *>(*it)->mLeaves[0];
                
                const AxisAlignedBox3 box = mHierarchyManager->GetVspTree()->GetBoundingBox(leaf);

                const float lVol = box.GetVolume();
                const float lArea = box.SurfaceArea();

                area += lArea;
                volume += lVol;

        CreateMesh(*it);
        }

        viewCell->SetVolume(volume);
        viewCell->SetArea(area);
}


void VspOspViewCellsManager::PrepareLoadedViewCells()
{
        // TODO
}


static void PrintCompressionStats(HierarchyManager *hm, const int pvsEntries)
{
        float mem = (float)pvsEntries * ObjectPvs::GetEntrySize();
                
        float fullmem = mem + 
                        (hm->GetVspTree()->GetStatistics().Leaves() * 16 + 
                         hm->mBvHierarchy->GetStatistics().Leaves() * 16) / float(1024 * 1024);

        cout << "entries: " << pvsEntries << ", mem=" << mem << ", fullmem=" << fullmem <<endl;
        Debug << "entries: " << pvsEntries << ", mem=" << mem << ", fullmem=" << fullmem <<endl;
}


void VspOspViewCellsManager::CompressViewCells()
{
        if (!(ViewCellsTreeConstructed() && mCompressViewCells))
                return;

        ////////////
        //-- compression

        int pvsEntries = mViewCellsTree->CountStoredPvsEntries(mViewCellsTree->GetRoot());

        cout << "before compression: " << endl;
        Debug << "before compression: " << endl;
        
        PrintCompressionStats(mHierarchyManager, pvsEntries);

        if (mCompressObjects)
        {
                cout << "compressing in the objects: " << endl;
                Debug << "compressing in the objects: " << endl;

                pvsEntries = mHierarchyManager->CompressObjectSpace();
        }
        else
        {
                cout << "compressing in the view space: " << endl;
                Debug << "compressing in the view space: " << endl;

                mViewCellsTree->SetViewCellsStorage(ViewCellsTree::COMPRESSED);
                pvsEntries = mViewCellsTree->CountStoredPvsEntries(mViewCellsTree->GetRoot());
        }

        PrintCompressionStats(mHierarchyManager, pvsEntries);
}


ViewCellsManager *VspOspViewCellsManager::LoadViewCells(const string &filename, 
                                                                                                                ObjectContainer *objects,
                                                                                                                const bool finalizeViewCells,
                                                                                                                BoundingBoxConverter *bconverter)
                                                                                                 
{
        ViewCellsManager *vm = 
                ViewCellsManager::LoadViewCells(filename, objects, finalizeViewCells, bconverter);
#if 0
        // insert scene objects in tree
        mOspTree->InsertObjects(mOspTree->GetRoot(), *objects);
#endif
        return vm;
}


void
VspOspViewCellsManager::CollectObjects(const AxisAlignedBox3 &box, ObjectContainer &objects)
{
  mHierarchyManager->CollectObjects(box, objects);
}


#if 1

void VspOspViewCellsManager::EvalViewCellPartition()
{
        int samplesPerPass;
        int numSamples;
        int castSamples = 0;
        int oldSamples = 0;
        int samplesForStats;
        char statsPrefix[100];
        char suffix[100];
        int splitsStepSize;

        Environment::GetSingleton()->GetIntValue("ViewCells.Evaluation.samplesPerPass", samplesPerPass);
        Environment::GetSingleton()->GetIntValue("ViewCells.Evaluation.samplesForStats", samplesForStats);
        Environment::GetSingleton()->GetIntValue("ViewCells.Evaluation.samples", numSamples);
        Environment::GetSingleton()->GetStringValue("ViewCells.Evaluation.statsPrefix", statsPrefix);
        Environment::GetSingleton()->GetIntValue("ViewCells.Evaluation.stepSize", splitsStepSize);
        
        bool useHisto;
        int histoMem;

        Environment::GetSingleton()->GetBoolValue("ViewCells.Evaluation.histogram", useHisto);
        Environment::GetSingleton()->GetIntValue("ViewCells.Evaluation.histoMem", histoMem);

        Debug << "step size: " << splitsStepSize << endl;
        Debug << "view cell evaluation samples per pass: " << samplesPerPass << endl;
        Debug << "view cell evaluation samples: " << numSamples << endl;
        Debug << "view cell stats prefix: " << statsPrefix << endl;

    cout << "reseting pvs ... ";
                
        // reset pvs and start over from zero
        mViewCellsTree->ResetPvs();
        
        cout << "finished" << endl;
    cout << "Evaluating view cell partition ... " << endl;

        vector<int> evalStrats;

        // mix of sampling strategies
        if (0)
        {
                evalStrats.push_back(SamplingStrategy::OBJECT_DIRECTION_BASED_DISTRIBUTION);
        }
        else
        {
                /*evalStrats.push_back(SamplingStrategy::OBJECT_BASED_DISTRIBUTION);
                evalStrats.push_back(SamplingStrategy::REVERSE_VIEWSPACE_BORDER_BASED_DISTRIBUTION);
                evalStrats.push_back(SamplingStrategy::REVERSE_OBJECT_BASED_DISTRIBUTION);
                */
                evalStrats.push_back(SamplingStrategy::SPATIAL_BOX_BASED_DISTRIBUTION);
        }
                        
    Debug << "casting eval strategies: ";
        for (int i = 0; i < (int)evalStrats.size(); ++ i)
                Debug << evalStrats[i] << " ";
        Debug << endl;

        cout << "casting eval strategies: ";
        for (int i = 0; i < (int)evalStrats.size(); ++ i)
                cout << evalStrats[i] << " ";
        cout << endl;

        int pass = 0;

        while (castSamples < numSamples)
        {               
                ///////////////
                //-- we have to use uniform sampling strategy for construction rays

                VssRayContainer evaluationSamples;
                const int samplingType = mEvaluationSamplingType;

                long startTime = GetTime();

                cout << "casting " << samplesPerPass << " samples ... ";
                Debug << "casting " << samplesPerPass << " samples ... ";
        
                if (1)
                {
                        CastPassSamples(samplesPerPass, evalStrats, evaluationSamples);
                }
                else
                {
                        // use mixed distributions
                        CastPassSamples2(samplesPerPass, evaluationSamples);
                }

                castSamples += samplesPerPass;

                Real timeDiff = TimeDiff(startTime, GetTime());
                
                cout << "finished in " << timeDiff * 1e-3f << " secs" << endl;
                cout << "computing sample contributions of " << (int)evaluationSamples.size()  << " samples ... ";
                
                Debug << "finished in " << timeDiff * 1e-3f << " secs" << endl;
                Debug << "computing sample contributions of " << (int)evaluationSamples.size()  << " samples ... ";

                startTime = GetTime();

                ComputeSampleContributions(evaluationSamples, true, false);

                timeDiff = TimeDiff(startTime, GetTime());
                cout << "finished in " << timeDiff * 1e-3 << " secs" << endl;
                Debug << "finished in " << timeDiff * 1e-3 << " secs" << endl;

                if ((castSamples >= samplesForStats + oldSamples) || 
                        (castSamples >= numSamples))
                {
                        oldSamples += samplesForStats;

                        ///////////
                        //-- output stats

                        sprintf(suffix, "-%09d-eval.log", castSamples);
                        const string filename = string(statsPrefix) + string(suffix);

                        startTime = GetTime();
                        
                        cout << "compute new statistics ... " << endl;

                        ofstream ofstr(filename.c_str());
                        mHierarchyManager->EvaluateSubdivision2(ofstr, splitsStepSize, false, useHisto, histoMem, pass);

                        timeDiff = TimeDiff(startTime, GetTime());
                        cout << "finished in " << timeDiff * 1e-3 << " secs" << endl;
                        cout << "*************************************" << endl;

                        Debug << "statistics computed in " << timeDiff * 1e-3 << " secs" << endl;

#if 0
                        //////////////
                        // filtered stats

                        sprintf(suffix, "-%09d-eval-filter.log", castSamples);
                        const string filename2 = string(statsPrefix) + string(suffix);

                        startTime = GetTime();
                        
                        cout << "compute new statistics for filtered pvs ... " << endl;

                        ofstream ofstr2(filename2.c_str());
                        mHierarchyManager->EvaluateSubdivision2(ofstr2, splitsStepSize, true);

                        timeDiff = TimeDiff(startTime, GetTime());
                        cout << "finished in " << timeDiff * 1e-3 << " secs" << endl;
                        cout << "*************************************" << endl;
                        Debug << "filtered statistics computed in " << timeDiff * 1e-3 << " secs" << endl;
#endif

                        // only for debugging purpose
                        if (0)
                        {
                                ViewCellContainer viewCells;
                                mViewCellsTree->CollectLeaves(mViewCellsTree->GetRoot(), viewCells);

                                ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
                                int pvsSize = 0;

                                for (vit = viewCells.begin(); vit != vit_end; ++ vit)
                                {
                                        pvsSize += (*vit)->GetPvs().GetSize();
                                }

                                cout << "debug entries: " << pvsSize << ", memcost: " 
                                         << (float)pvsSize * ObjectPvs::GetEntrySize() << endl;
                        }
                        ++ pass;
                }

                disposeRays(evaluationSamples, NULL);
        }

        ////////////
        //-- histogram
#if 1
        const int numLeaves = mViewCellsTree->GetNumInitialViewCells(mViewCellsTree->GetRoot());
        int histoStepSize;

        Environment::GetSingleton()->GetBoolValue("ViewCells.Evaluation.histogram", useHisto);
        Environment::GetSingleton()->GetIntValue("ViewCells.Evaluation.histoStepSize", histoStepSize);

        if (useHisto)
        {
                // evaluate view cells in a histogram           
                char str[64];

                // hack: just show final view cells
                int pass = (int)mViewCells.size();
                //for (int pass = histoStepSize; pass <= numLeaves; pass += histoStepSize)
                if (1)
                {
                        string filename;

                        cout << "computing histogram for " << pass << " view cells" << endl;

                        //////////////////////////////////////////
            //-- evaluate histogram for pvs size

                        cout << "computing pvs histogram for " << pass << " view cells" << endl;

                        sprintf(str, "-%09d-histo-pvs2.log", pass);
                        filename = string(statsPrefix) + string(str);

                        EvalViewCellHistogramForPvsSize(filename, pass);
                }
        }
#endif
}

#endif



}