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

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

#define SAMPLE_AFTER_SUBDIVISION 1
#define TEST_EMPTY_VIEW_CELLS 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());
        }
};

typedef priority_queue<ViewCell *, vector<ViewCell *>, myless<vector<ViewCell *>::value_type> > FilterQueue;



ViewCellsManager::ViewCellsManager():
mRenderer(NULL),
mInitialSamples(0),
mConstructionSamples(0),
mPostProcessSamples(0),
mVisualizationSamples(0),
mTotalAreaValid(false),
mTotalArea(0.0f),
mViewCellsFinished(false),
mMaxPvsSize(9999999),
mMinPvsSize(0), // one means only empty view cells are invalid
mMaxPvsRatio(1.0)
{
        mViewSpaceBox.Initialize();
        ParseEnvironment();

        mViewCellsTree = new ViewCellsTree(this);
}


void ViewCellsManager::ParseEnvironment()
{
        // visualization stuff
        environment->GetBoolValue("ViewCells.Visualization.exportRays", mExportRays);
        environment->GetBoolValue("ViewCells.Visualization.exportGeometry", mExportGeometry);
        environment->GetFloatValue("ViewCells.maxPvsRatio", mMaxPvsRatio);
        
        bool emptyViewCells = false;
        environment->GetBoolValue("ViewCells.pruneEmptyViewCells", emptyViewCells);
        mMinPvsSize = emptyViewCells ? 1 : 0;

        environment->GetBoolValue("ViewCells.processOnlyValidViewCells", mOnlyValidViewCells);

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

        environment->GetIntValue("ViewCells.Visualization.samples", mVisualizationSamples);

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

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

        
        if (strcmp(buf, "box") == 0)
                mSamplingType = Preprocessor::SPATIAL_BOX_BASED_DISTRIBUTION;
        else if (strcmp(buf, "directional") == 0)
                mSamplingType = Preprocessor::DIRECTION_BASED_DISTRIBUTION;
        else 
        {
                Debug << "error! wrong sampling type" << endl;
                exit(0);
        }

        environment->GetStringValue("ViewCells.Visualization.colorCode", buf);

        if (strcmp(buf, "PVS") == 0)
                mColorCode = 1;
        else if (strcmp(buf, "MergedLeaves") == 0)
                mColorCode = 2;
        else if (strcmp(buf, "MergedTreeDiff") == 0)
                mColorCode = 3;
        else
                mColorCode = 0;


        Debug << "***********View Cells options ****************" << endl;
        Debug << "color code: " << mColorCode << endl;

        Debug << "export rays: " << mExportRays << endl;
        Debug << "export geometry: " << mExportGeometry << endl;
        Debug << "max pvs ratio: " << mMaxPvsRatio << endl;
        
        Debug << "prune empty view cells: " << emptyViewCells << 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: " << 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 << "show visualization: " << mShowVisualization << endl;
        Debug << "filter width: " << mFilterWidth << endl;

        Debug << endl;
}


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

        if (!ViewCellsTreeConstructed())
                CLEAR_CONTAINER(mViewCells);
        else
                DEL_PTR(mViewCellsTree);

        CLEAR_CONTAINER(mMeshContainer);
}


void ViewCellsManager::CollectEmptyViewCells()
{
        mEmptyViewCells.clear();
        ViewCellContainer leaves;
        mViewCellsTree->CollectLeaves(mViewCellsTree->GetRoot(), leaves);

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

        cout << "collecting empty view cells" << endl;
        
        for (it = leaves.begin(); it != it_end; ++ it)
        {
                if ((*it)->GetPvs().Empty())
                {
                        mEmptyViewCells.push_back(*it);
                }
        }
        Debug << "empty view cells found: " << (int)mEmptyViewCells.size() << endl;
}


void ViewCellsManager::TestEmptyViewCells(const ObjectContainer &obj)
{
        ViewCellContainer::const_iterator it, it_end = mEmptyViewCells.end();

        char buf[50];
        int i = 0;
        for (it = mEmptyViewCells.begin(); it != it_end; ++ it)
        {
                if (!(*it)->GetPvs().Empty())
                {
                        sprintf(buf, "empty-viewcells-%09d.x3d", i/*(*it)->GetId()*/);
                        Exporter *exporter = Exporter::GetExporter(buf);
                        
                        if (exporter && i < 20)
                        {
                                Ray *pray = (*it)->mPiercingRays[0];
                                Debug << "view cell " << (*it)->GetId() << " not empty, pvs: " << (*it)->GetPvs().GetSize() << " " << (int)pray->intersections.size() << endl;

                                exporter->ExportRays((*it)->mPiercingRays);
                                                        
                                exporter->SetFilled();
                                exporter->SetForcedMaterial(RgbColor(0,0,1));

                                for (int j = 0; j < (int)pray->intersections.size(); ++ j)
                                {
                                        if (pray->intersections[j].mObject)
                                                exporter->ExportIntersectable(pray->intersections[j].mObject);
                                }

                                //exporter->SetWireframe();
                                exporter->SetForcedMaterial(RgbColor(0,1,0));
                                exporter->ExportGeometry(obj);

                                exporter->SetFilled();

                                exporter->SetForcedMaterial(RgbColor(1,0,0));
                                ExportViewCellGeometry(exporter, *it);

                                delete exporter;                
                        }

                
                        ++ i;
                }
        }
        Debug << "\nSampled " << i << " new view cells (" << " of " << (int)mEmptyViewCells.size() << ")" << endl << endl;
}


int ViewCellsManager::CastPassSamples(const int samplesPerPass, 
                                                                          const int sampleType, 
                                                                          VssRayContainer &passSamples) const
{
        SimpleRayContainer simpleRays;

        preprocessor->GenerateRays(samplesPerPass,
                                                           sampleType,
                                                           simpleRays);

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

        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)
                {
                        //(*it)->Unref();
                        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;

        cout << "view cell construction: casting " << mInitialSamples << " initial samples ... ";
        //-- construction rays => we use uniform samples for this
        CastPassSamples(mInitialSamples, 
                                        mSamplingType,
                                        initialSamples);
        
        cout << "finished" << endl;

        
        // construct view cells
        const int numInitialSamples = 
                ConstructSubdivision(preprocessor->mObjects, initialSamples);

        numSamples += numInitialSamples;

        // rays can be passed or deleted
        disposeRays(initialSamples, outRays);
        
        cout << "testing filter ... ";

        TestFilter(preprocessor->mObjects);

        cout << "finished" << endl;

        // -- stats after contruction
        ResetViewCells();

        Debug << "\nView cells after initial sampling:\n" << mCurrentViewCellsStats << endl;

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

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

                        ExportViewCellsForViz(exporter);

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

        //-- guided rays are used for further sampling
        const int n = mConstructionSamples; //+initialSamples;

        // should we use directional samples?
        bool dirSamples = (mSamplingType == Preprocessor::DIRECTION_BASED_DISTRIBUTION);

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

                const int samplingType = mSamplingType;
                        /*dirSamples ? 
                                                Preprocessor::DIRECTION_BASED_DISTRIBUTION :
                                                Preprocessor::SPATIAL_BOX_BASED_DISTRIBUTION;*/

                if (0)
                        dirSamples = !dirSamples; // toggle sampling method

                numSamples += CastPassSamples(mSamplesPerPass, 
                                                                          samplingType,
                                                                          constructionSamples);

                cout << "finished" << endl;

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

                // TODO: leak?
                if (SAMPLE_AFTER_SUBDIVISION)
                        ComputeSampleContributions(constructionSamples, true, false);
                cout << "finished" << endl;


                disposeRays(constructionSamples, outRays);

                cout << "total samples: " << numSamples << endl;
        }
        

        //-- post processing
        VssRayContainer postProcessSamples;

        //-- construction rays 
        CastPassSamples(mPostProcessSamples,
                                        mSamplingType, 
                                        postProcessSamples);


        // stats before post processing (i.e., merge)
        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;



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


        // store view cells for postprocessing
        const bool storeViewCells = true;


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

        // merge the view cells
        PostProcess(preprocessor->mObjects, postProcessSamples);

        // only for testing
        if (TEST_EMPTY_VIEW_CELLS)
                CollectEmptyViewCells();


        //-- visualization
        if (mShowVisualization)
        {
                VssRayContainer visualizationSamples;

                //-- construction rays => we use uniform samples for this
                CastPassSamples(mVisualizationSamples,
                                            Preprocessor::DIRECTION_BASED_DISTRIBUTION, 
                                                visualizationSamples);

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

                // different visualizations
                Visualize(preprocessor->mObjects, visualizationSamples);

                disposeRays(visualizationSamples, outRays);
        }

        if (mEvaluateViewCells)
        {
                EvalViewCellPartition(preprocessor);
        }
        
        if (0)
        {
                ViewCellContainer leaves;
                mViewCellsTree->CollectLeaves(mViewCellsTree->GetRoot(), leaves);
                mViewCellsTree->ResetPvs();
                VssRayContainer dummyRays;
                CastPassSamples(mInitialSamples, mSamplingType, dummyRays);
        
                //ComputeSampleContributions(initialSamples, true, false);
                ComputeSampleContributions(dummyRays, true, false);

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

                for (it = leaves.begin(); it != it_end; ++ it)
                {
                        mViewCellsTree->PropagatePvs(*it);
                }

                mViewCellsTree->ExportStats("dummy.log");
        }

        return numSamples;
}


void ViewCellsManager::EvalViewCellPartition(Preprocessor *preprocessor)
{
        int samplesPerPass;
        int numSamples;
        int castSamples = 0;

        char s[64]; 

        environment->GetIntValue("ViewCells.Evaluation.samplesPerPass", samplesPerPass);
        environment->GetIntValue("ViewCells.Evaluation.samples", numSamples);

        char statsPrefix[100];
        environment->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;

        //VssRayContainer outRays;
        // should directional sampling be used?
        bool dirSamples = mSamplingType == Preprocessor::DIRECTION_BASED_DISTRIBUTION;

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

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

        bool startFromZero = true;

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

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

        while (castSamples < numSamples)
        {
                VssRayContainer evaluationSamples;

                const int samplingType = mSamplingType;
                /*      dirSamples ? 
                                                Preprocessor::DIRECTION_BASED_DISTRIBUTION :
                                                Preprocessor::SPATIAL_BOX_BASED_DISTRIBUTION;
                */
                //-- construction rays => we use uniform samples for this
                CastPassSamples(samplesPerPass, samplingType, evaluationSamples);
                
                castSamples += samplesPerPass;

                cout << "casting " << (int)evaluationSamples.size() << " samples " << endl;

                ComputeSampleContributions(evaluationSamples, true, false);

                cout << "compute new statistics ... ";

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

                for (it = leaves.begin(); it != it_end; ++ it)
                {
                        mViewCellsTree->PropagatePvs(*it);
                }

                // output stats
                sprintf(s, "-%09d-eval.log", castSamples);
                string fileName = string(statsPrefix) + string(s);

                mViewCellsTree->ExportStats(fileName);

                cout << "finished" << endl;
        
                disposeRays(evaluationSamples, NULL);
        }

        // find empty view cells bug
        if (TEST_EMPTY_VIEW_CELLS)
                TestEmptyViewCells(preprocessor->mObjects);
}

/*
int ViewCellsManager::ConstructLocalMergeTree(vector<LocalMergeCandidate> candidates)
                                                                                         
{
        while(!candidates.empty())
        {
                MergeCandidate mc = candidates.back();
                candidates.pop_back();
                EvalMergeCost(mc);
                mergeQueue.push(mc);
        }

        ViewCell::NewMail();

        
        long startTime = GetTime();

        mergeStats.candidates = (int)mMergeQueue.size();

        // passes are needed for statistics, because we don't want to record
        // every merge
        int pass = 0;
        int mergedPerPass = 0;
        float realExpectedCost = mExpectedCost;
        float realAvgRenderCost = mAvgRenderCost;
        int realNumActiveViewCells = mNumActiveViewCells;
        
         reset.

        int numMergedViewCells = 0;

        environment->GetIntValue("ViewCells.PostProcess.maxMergesPerPass", maxMergesPerPass);
        environment->GetFloatValue("ViewCells.PostProcess.avgCostMaxDeviation", avgCostMaxDeviation);

        cout << "actual merge starts now ... " << endl;

        //-- use priority queue to merge leaf pairs

        //const float maxAvgCost = 350;
        while (!mMergeQueue.empty())//NumActiveViewCells > mMergeMinViewCells))
        {
                //-- reset merge queue if the ratio of current expected cost / real expected cost
                //   too small or after a given number of merges
                if ((mergedPerPass > maxMergesPerPass) ||
                        (avgCostMaxDeviation > mAvgRenderCost / realAvgRenderCost))
                {
                        // adjust render cost
                        ++ pass;

                        mergedPerPass = 0;
                        mExpectedCost = realExpectedCost;
                                        
                        
                
                        // refines the view cells
                        // then priorities are recomputed
                        // and the candidates are put back into merge queue
                        if (mRefineViewCells)
                                RefineViewCells(rays, objects);
                        else
                                ResetMergeQueue();

                        Debug << "Values after reset: "  
                                  << " erc: " << mExpectedCost 
                                  << " avg: " << mAvgRenderCost 
                                  << " dev: " << mDeviation << endl;

                        if (mExportMergedViewCells)
                        {
                                ExportMergedViewCells(activeViewCells, objects, numMergedViewCells);
                        }
                }


                MergeCandidate mc = mMergeQueue.top();
                mMergeQueue.pop();
        
                // both view cells equal
                // NOTE: do I really still need this? probably cannot happen!!
                if (mc.mLeftViewCell == mc.mRightViewCell)
                        continue;

                if (mc.IsValid())
                {
                        ViewCell::NewMail();

                        //-- update statistical values
                        -- realNumActiveViewCells;
                        ++ mergeStats.merged;
                        ++ mergedPerPass;

                        const float renderCostIncr = mc.GetRenderCost();
                        const float mergeCostIncr = mc.GetMergeCost();

                        totalRenderCost += renderCostIncr;
                        mDeviation += mc.GetDeviationIncr();
                        
                        
                        // merge the view cells of leaf1 and leaf2
                        int pvsDiff;
                        ViewCellInterior *mergedVc = 
                                MergeViewCells(mc.mLeftViewCell, mc.mRightViewCell, pvsDiff);


                        // total render cost and deviation has changed
                        // real expected cost will be larger than expected cost used for the
                        // cost heuristics, but cannot recompute costs on each increase of the 
                        // expected cost
                        totalPvs += pvsDiff;
                        realExpectedCost = totalRenderCost / (float)realNumActiveViewCells;
                        realAvgRenderCost = (float)totalPvs / (float)realNumActiveViewCells;
        
                        // set merge cost to this node
                        mergedVc->SetMergeCost(totalRenderCost);

                        //if (mViewCellsManager->EqualToSpatialNode(mergedVc))
                        //      ++ mergeStats.siblings;
                        mergedVc->SetCost(realExpectedCost);

                        if ((mergeStats.merged % statsOut) == 0)
                                cout << "merged " << mergeStats.merged << " view cells" << endl;

                }
                else
                { 
                        // merge candidate not valid, because one of the leaves was already
                        // merged with another one => validate and reinsert into queue
                        if (ValidateMergeCandidate(mc))
                        {
                                EvalMergeCost(mc);
                                mMergeQueue.push(mc);
                        }
                }
                
        }

        
        // adjust stats and reset queue one final time
        mExpectedCost = realExpectedCost;
        mAvgRenderCost = realAvgRenderCost;
        mNumActiveViewCells = realNumActiveViewCells;

        UpdateActiveViewCells(activeViewCells);

        
        // refine view cells and reset costs
        if (mRefineViewCells)
                RefineViewCells(rays, objects);
        else
                ResetMergeQueue();

        // create a root node if the merge was not done till root level,
        // else take the single node as new root
        if ((int)activeViewCells.size() > 1)
        {
                Debug << "creating root of view cell hierarchy for " 
                          << (int)activeViewCells.size() << " view cells" << endl;
                
                ViewCellInterior *root = mViewCellsManager->MergeViewCells(activeViewCells);
                root->SetMergeCost(totalRenderCost);
                // $$JB keep this 0 temporarilly
                root->SetCost(0.0f);

                mRoot = root;
        }
        else if ((int)activeViewCells.size() == 1)
        {
                Debug << "setting root of the merge history" << endl;
                mRoot = activeViewCells[0];
        }

        //-- empty merge queue just in case
        while (!mMergeQueue.empty())
        {
                mMergeQueue.pop();
        }

        // TODO delete because makes no sense here
        mergeStats.expectedRenderCost = realExpectedCost;
        mergeStats.deviation = mDeviation;

        // we want to optimize this heuristics
        mergeStats.heuristics = 
                mDeviation * (1.0f - mRenderCostWeight) + 
                mExpectedCost * mRenderCostWeight;

        mergeStats.mergeTime = TimeDiff(startTime, GetTime());
        mergeStats.Stop();
        Debug << mergeStats << endl << endl;

        // assign colors for the view cells so that at least one is always consistent
        AssignRandomColors();
        
        //TODO: should return sample contributions?
        return mergeStats.merged;
}
*/

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

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

  return true;
}


AxisAlignedBox3 ViewCellsManager::GetFilterBBox(const Vector3 &viewPoint, 
                                                                                                const float width) const
{
        Vector3 min = viewPoint - width * 0.5f;
        Vector3 max = viewPoint + width * 0.5;

        return AxisAlignedBox3(min, max);
}


void ViewCellsManager::GetPrVS(const Vector3 &viewPoint, PrVs &prvs)
{
        const AxisAlignedBox3 box = GetFilterBBox(viewPoint, mFilterWidth);

        ViewCellContainer viewCells;
        ComputeBoxIntersections(box, viewCells);

                
}


bool ViewCellsManager::ViewCellsTreeConstructed() const
{
        return 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
                                                                                )
{
  sort(mViewCells.begin(), mViewCells.end(), ViewCell::SmallerPvs);

  int start = mViewCells.size()*minValid;
  int end = mViewCells.size()*maxValid;

  for (int i=0; i < mViewCells.size(); i++)
        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)
{
        X3dParser parser;

        environment->GetFloatValue("ViewCells.height", parser.mViewCellHeight);

        bool success = parser.ParseFile(filename, *this);
        Debug << (int)mViewCells.size() << " view cells loaded" << endl;

        return success;
}


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

        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
                                                                                         )
{
  // view cells not yet constructed
  if (!ViewCellsConstructed())
        return 0.0f;

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

  float sum = 0.0f;
  for (it = rays.begin(); it != it_end; ++ it) 
  {
          sum += ComputeSampleContributions(*(*it), addRays, storeViewCells);
          //ComputeSampleContributions(*(*it), addRays);
          //    sum += (*it)->mPvsContribution;
  }

  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,
                                                                                                int &totalPvs,
                                                                                                float &avgRenderCost)
{
        ViewCellContainer::const_iterator it, it_end = mViewCells.end();


        //-- compute expected value

        totalRenderCost = 0;
        totalPvs = 0;

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

        // normalize with view space box
        totalRenderCost /= mViewSpaceBox.GetVolume();
        expectedRenderCost = totalRenderCost / (float)mViewCells.size();
        avgRenderCost = totalPvs / (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().GetSize() * vc->GetVolume();
                float dev;

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

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

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



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


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


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


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

        for (int i = 0; i < limit; ++ i)
        {
                Intersectable *object = objects[i];

                // extract the mesh instances
                if (object->Type() == Intersectable::MESH_INSTANCE)
                {
                        MeshInstance *inst = dynamic_cast<MeshInstance *>(object);

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


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

        //-- construct prism

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

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

        Triangle3 topTri;

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

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

        mesh->Preprocess();

        return GenerateViewCell(mesh);
}


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

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

        mTotalAreaValid = false;
}


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


ViewCellInterior *ViewCellsManager::MergeViewCells(ViewCell *left, ViewCell *right) const
{
        // generate parent view cell
        ViewCellInterior *vc = new ViewCellInterior();//GenerateViewCell();

        vc->GetPvs() = left->GetPvs();
        // merge pvs
        vc->GetPvs().Merge(right->GetPvs());

        //-- merge ray sets
        if (0)
        {
                stable_sort(left->mPiercingRays.begin(), left->mPiercingRays.end());
                stable_sort(right->mPiercingRays.begin(), right->mPiercingRays.end());

                std::merge(left->mPiercingRays.begin(), left->mPiercingRays.end(),
                                   right->mPiercingRays.begin(), right->mPiercingRays.end(),
                                   vc->mPiercingRays.begin());
        }


        vc->SetupChildLink(left);
        vc->SetupChildLink(right);


        return vc;
}


ViewCellInterior *ViewCellsManager::MergeViewCells(ViewCellContainer &children) const
{
        ViewCellInterior *vc = new ViewCellInterior();//GenerateViewCell();

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

        for (it = children.begin(); it != it_end; ++ it)
        {
                // merge pvs
                vc->GetPvs().Merge((*it)->GetPvs());

                vc->SetupChildLink(*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::GetPvsStatistics(PvsStatistics &stat)
{
  ViewCellContainer::const_iterator it = mViewCells.begin();
  stat.viewcells = 0;
  stat.minPvs = 100000000;
  stat.maxPvs = 0;
  stat.avgPvs = 0.0f;

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


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


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


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


void ViewCellsManager::SetViewSpaceBox(const AxisAlignedBox3 &box)
{
        mViewSpaceBox = box;

        CreateClipPlane();
        
        mTotalAreaValid = false;
}


void ViewCellsManager::CreateClipPlane()
{
        int axis = 0;
        float pos;

        environment->GetFloatValue("ViewCells.Visualization.clipPlanePos", pos);

        Vector3 point = mViewSpaceBox.Min() +  mViewSpaceBox.Size() * pos;

        if (mUseClipPlaneForViz)
        environment->GetIntValue("ViewCells.Visualization.clipPlaneAxis", axis);

        Vector3 normal(0,0,0);
        normal[axis] = 1;

        mClipPlane = Plane3(normal, point);
}


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


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

        // has to be recomputed
        mTotalAreaValid = false;
}


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


void
ViewCellsManager::AddSampleContributions(const VssRayContainer &rays)
{
  if (!ViewCellsConstructed())
        return;

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

  for (it = rays.begin(); it != it_end; ++ it) {
        AddSampleContributions(*(*it));
  }
}


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



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


void
ViewCellsManager::AddSampleContributions(VssRay &ray)
{
  // assumes viewcells have been stored...
  ViewCellContainer *viewcells = &ray.mViewCells;
  ViewCellContainer::const_iterator it;
  for (it = viewcells->begin(); it != viewcells->end(); ++it) {
        ViewCell *viewcell = *it;
        if (viewcell->GetValid()) {
          // if ray not outside of view space
          viewcell->GetPvs().AddSample(ray.mTerminationObject, ray.mPdf);
        }
  }
}


float ViewCellsManager::ComputeSampleContributions(VssRay &ray,
                                                                                                   const bool addRays,
                                                                                                   const bool storeViewCells)
{
        ViewCellContainer viewcells;

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

        static Ray hray;
        hray.Init(ray);
        //hray.mFlags |= Ray::CULL_BACKFACES;
        //Ray hray(ray);

        float tmin = 0, tmax = 1.0;

        if (!GetViewSpaceBox().GetRaySegment(hray, tmin, tmax) || (tmin > tmax))
                return 0;

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

        CastLineSegment(origin, termination, viewcells);

        // copy viewcells memory efficiently
        //const bool storeViewcells = !addRays;

        if (storeViewCells)
        {
                ray.mViewCells.reserve(viewcells.size());
                ray.mViewCells = viewcells;
        }

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

        for (; it != viewcells.end(); ++ it) 
        {
                ViewCell *viewcell = *it;

                if (viewcell->GetValid()) 
                {
                        // HACK
                        if (TEST_EMPTY_VIEW_CELLS)
                                for (int i = 0; i < mEmptyViewCells.size(); ++i)
                                {
                                        if (viewcell == mEmptyViewCells[i])
                                        {
                                                viewcell->mPiercingRays.push_back(new Ray(ray));
                                                Debug << "empty view cell ray found: " << ray.mOriginObject << ", " << ray.mTerminationObject << endl;
                                        }
                                }

                        // if ray not outside of view space
                        float contribution;
                        if (ray.mTerminationObject &&
                                viewcell->GetPvs().GetSampleContribution(ray.mTerminationObject,
                                                                                                                 ray.mPdf,
                                                                                                                 contribution))
                        {
                                ++ ray.mPvsContribution;
                                ray.mRelativePvsContribution += contribution;
                        }
                        if (ray.mOriginObject && 
                                viewcell->GetPvs().GetSampleContribution(ray.mOriginObject,
                                                                                                                 ray.mPdf,
                                                                                                                 contribution))
                        {
                                ++ ray.mPvsContribution;
                                ray.mRelativePvsContribution += contribution;
                        }
                }
        }

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

        return ray.mRelativePvsContribution;
}


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, float objRendercost) const
{
        return mViewCellsTree->GetPvsSize(viewCell) * objRendercost;
}


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
                for (int i = 0; i < (int)mViewCells.size(); ++ i)
                        mViewCells[i]->SetId(i);
}


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

        for (it = mViewCells.begin(); it != it_end; ++ it)
        {
                if (!mOnlyValidViewCells || (*it)->GetValid())
                {
                        ExportColor(exporter, *it);             
                        ExportViewCellGeometry(exporter, *it, 
                                mUseClipPlaneForViz ? &mClipPlane : NULL);
                }
        }
}


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)
{
        return false;
}


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


void ViewCellsManager::SetViewCellsActive()
{
        ++ ViewCell::sLastUpdated;
        ViewCellContainer::const_iterator it, it_end = mViewCells.end();
        for (it = mViewCells.begin(); it != it_end; ++ it)
        {
                (*it)->SetActive();
        }
}

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


BspViewCellsManager::BspViewCellsManager(BspTree *bspTree):
ViewCellsManager(), mBspTree(bspTree)
{
        environment->GetIntValue("BspTree.Construction.samples", mInitialSamples);
        mBspTree->SetViewCellsManager(this);
        mBspTree->mViewCellsTree = 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
        if (ViewCellsConstructed())
                return 0;

        int sampleContributions = 0;

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

        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 (mViewCells.empty())
        {
                // no view cells loaded
                mBspTree->Construct(objects, constructionRays, &mViewSpaceBox);
                // collect final view cells
                mBspTree->CollectViewCells(mViewCells);
        }
        else
        {
                mBspTree->Construct(mViewCells);
        }

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

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

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

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

        return sampleContributions;
}


void BspViewCellsManager::CollectViewCells()
{
        // view cells tree constructed
        if (!ViewCellsTreeConstructed())
        {               
                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)
{
        // compute view cell area as subsititute for probability
        if (1)
                return GetVolume(viewCell) / GetViewSpaceBox().GetVolume();
        else
                return GetArea(viewCell) / GetAccVcArea();
}



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


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

                return 0;
        }

        //-- post processing of bsp view cells

    int vcSize = 0;
        int pvsSize = 0;

        //-- merge view cells
        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;
                // create spatial merge hierarchy
                mViewCellsTree->SetRoot(ConstructSpatialMergeTree(mBspTree->GetRoot()));
        }

        // export statistics after merge
        if (1)
        {
                char mstats[100];
                environment->GetStringValue("ViewCells.mergeStats", mstats);
                mViewCellsTree->ExportStats(mstats);
        }

        //-- stats and visualizations
        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
    // reset view cells and stats
        ResetViewCells();
        Debug << "\nView cells after merge:\n" << mCurrentViewCellsStats << endl;


        int savedColorCode  = mColorCode;
        
        //BspLeaf::NewMail();
        if (1) // export merged view cells
        {
                mColorCode = 0;
                
                Exporter *exporter = Exporter::GetExporter("merged_view_cells.x3d");
                

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

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

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


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

        if (1) // export merged view cells
        {
                mColorCode = 1;

                Exporter *exporter = Exporter::GetExporter("merged_view_cells_pvs.x3d");
        
                cout << "exporting view cells after merge (pvs size) ... ";     

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

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

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

        
        // only for testing
        TestSubdivision();

        mColorCode = savedColorCode;

        FinalizeViewCells(true);
        
        // write view cells to disc
        if (mExportViewCells)
        {
                char buff[100];
                environment->GetStringValue("ViewCells.filename", buff);
                string vcFilename(buff);

                ExportViewCells(buff);
        }

        return 0;
}


BspViewCellsManager::~BspViewCellsManager()
{
}


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


void BspViewCellsManager::Visualize(const ObjectContainer &objects,
                                                                        const VssRayContainer &sampleRays)
{
        if (!ViewCellsConstructed())
                return;
        
        int savedColorCode = mColorCode;

        
        
        if (1) // export final view cells
        {
                mColorCode = 1;

                Exporter *exporter = Exporter::GetExporter("final_view_cells.x3d");
        
                cout << "exporting view cells after merge (pvs size) ... ";     

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

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

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

        mColorCode = savedColorCode;

        //-- visualization of the BSP splits
        bool exportSplits = false;
        environment->GetBoolValue("BspTree.Visualization.exportSplits", exportSplits);

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

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


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


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

        if (exporter)
        {
                //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::ExportBspPvs(const ObjectContainer &objects)
{
        const int leafOut = 10;

        ViewCell::NewMail();

        //-- some rays for output
        const int raysOut = min((int)mBspRays.size(), mVisualizationSamples);

        cout << "visualization using " << mVisualizationSamples << " samples" << endl;
        Debug << "\nOutput view cells: " << endl;

        // sort view cells to get largest view cells
        if (0)
                stable_sort(mViewCells.begin(), mViewCells.end(), vc_gt);

        int limit = min(leafOut, (int)mViewCells.size());

        for (int i = 0; i < limit; ++ i)
        {
                cout << "creating output for view cell " << i << " ... ";
                VssRayContainer vcRays;
                Intersectable::NewMail();
                ViewCell *vc;

                if (0)
                        vc = mViewCells[i];
                else
                        vc = mViewCells[Random((int)mViewCells.size())];

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

                if(0)
                {
                        // check whether we can add the current ray to the output rays
                        for (int k = 0; k < raysOut; ++ k)
                        {
                                BspRay *ray = mBspRays[k];
                                for     (int j = 0; j < (int)ray->intersections.size(); ++ j)
                                {
                                        BspLeaf *leaf = ray->intersections[j].mLeaf;
                                        if (vc == leaf->GetViewCell())
                                                vcRays.push_back(ray->vssRay);
                                }
                        }
                }

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

                Exporter *exporter = Exporter::GetExporter(s);

                exporter->SetWireframe();

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

                ExportViewCellGeometry(exporter, vc);
                
                // export rays piercing this view cell
                exporter->ExportRays(vcRays, RgbColor(0, 1, 0));

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

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

                exporter->SetFilled();

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

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

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

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

        Debug << endl;
}


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

        float importance = 0;
        static Material m;

        switch (mColorCode)
        {
        case 0: // Random
                {
                        if (vcValid)
                        {
                                m.mDiffuseColor.r = 0.5f + RandomValue(0.0f, 0.5f);
                                m.mDiffuseColor.g = 0.5f + RandomValue(0.0f, 0.5f);
                                m.mDiffuseColor.b = 0.5f + RandomValue(0.0f, 0.5f);
                        }
                        else
                        {
                                m.mDiffuseColor.r = 0.0f;
                                m.mDiffuseColor.g = 1.0f;
                                m.mDiffuseColor.b = 0.0f;
                        }

                        exporter->SetForcedMaterial(m);
                        return;
                }
                
        case 1: // pvs
                {
                        importance = (float)vc->GetPvs().GetSize() /
                                (float)mCurrentViewCellsStats.maxPvs;

                }
                break;
        case 2: // merges
                {
            int lSize = mViewCellsTree->GetSize(vc);
                        importance = (float)lSize / (float)mCurrentViewCellsStats.maxLeaves;
                }
                //break;
        case 3: // merge tree differene
                {
                        // TODO
                        //importance = (float)GetMaxTreeDiff(vc) /
                        //      (float)(mVspBspTree->GetStatistics().maxDepth * 2);

                }
                break;
        default:
                break;
        }

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

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


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;
                BspLeaf *leaf = dynamic_cast<BspViewCell *>(*it)->mLeaf;
                mBspTree->ConstructGeometry(leaf, geom);

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

                float thres = 0.9;
                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 Plane3 *clipPlane) const
{
        if (vc->GetMesh())
        {
                exporter->ExportMesh(vc->GetMesh());
                return;
        }

        BspNodeGeometry geom;
        mBspTree->ConstructGeometry(vc, geom);

        if (clipPlane)
        {
                const int cf = Polygon3::ClassifyPlane(geom.GetPolys(), *clipPlane, 0.0001f);

                if (cf == Polygon3::BACK_SIDE)
                {
                        exporter->ExportPolygons(geom.GetPolys());
                }
                else if (cf == Polygon3::SPLIT)
                {
                        BspNodeGeometry front;
                        BspNodeGeometry back;

                        geom.SplitGeometry(front,
                                                           back,
                                                           *clipPlane,
                                                           mViewSpaceBox, 
                                                           0.0001f);

                        if (back.Valid())
                                exporter->ExportPolygons(back.GetPolys());
                }
        }
        else
        {
                exporter->ExportPolygons(geom.GetPolys());
        }
}


void BspViewCellsManager::CreateMesh(ViewCell *vc)
{
        if (vc->GetMesh())
                delete vc->GetMesh();

        BspNodeGeometry geom;
        
        mBspTree->ConstructGeometry(vc, geom);

        Mesh *mesh = new Mesh();
        geom.AddToMesh(*mesh);
        vc->SetMesh(mesh);
        mMeshContainer.push_back(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;
                BspLeaf *leaf = dynamic_cast<BspViewCell *>(*it)->mLeaf;
                mBspTree->ConstructGeometry(leaf, geom);

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

                //(*it)->SetVolume(vol);
                //(*it)->SetArea(area);

                area += lArea;
                volume += lVol;

        CreateMesh(*it);
        }

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


ViewCell *BspViewCellsManager::GetViewCell(const Vector3 &point) const
{
        if (!mBspTree)
                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)
{
        cout << "exporting view cells to xml ... ";
        std::ofstream stream;

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


        stream.open(filename.c_str());
        stream << "<?xml version=\"1.0\" encoding=\"UTF-8\"?>"<<endl;
        stream << "<Visibility_Solution>" << endl;

        //-- the view space bounding box
        stream << "<ViewSpaceBox" 
                   << " min=\"" << mViewSpaceBox.Min().x << " " << mViewSpaceBox.Min().y << " " << mViewSpaceBox.Min().z << "\""
                   << " max=\"" << mViewSpaceBox.Max().x << " " << mViewSpaceBox.Max().y << " " << mViewSpaceBox.Max().z << "\" />" << endl;

        //-- the type of the view cells hierarchy
        //stream << "<Hierarchy name=\"bspTree\" />" << endl;
        stream << "<Hierarchy name=\"vspBspTree\" />" << endl; // write vsp bsp here because can use same tree and is bug free
        //-- load the view cells itself, i.e., the ids and the pvs
        stream << "<ViewCells>" << endl;

#if 0
        
        ViewCellContainer::const_iterator it, it_end = mViewCells.end();
                
        for (it = mViewCells.begin(); it != it_end; ++ it)
                ExportViewCell(*it, stream);
#else
        mViewCellsTree->Export(stream);
#endif

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

        //-- load the hierarchy
        stream << "<Hierarchy>" << endl;
        mBspTree->Export(stream);
        stream << endl << "</Hierarchy>" << endl;

        stream << "</Visibility_Solution>" << endl;
        stream.close();

        cout << "finished" << endl;

        return true;
}


void BspViewCellsManager::AddCurrentViewCellsToHierarchy()
{
        ViewCellContainer::const_iterator it, it_end = mViewCells.end();
        for (it = mViewCells.begin(); it != it_end; ++ it)
        {
                ViewCell *vc = *it;
                ViewCellContainer leaves;
                mViewCellsTree->CollectLeaves(vc, leaves);
                
                ViewCellContainer::const_iterator lit, lit_end = leaves.end();

                for (lit = leaves.begin(); lit != lit_end; ++ lit)
                {
                        BspViewCell *bspVc = dynamic_cast<BspViewCell *>(*lit);
                        bspVc->mLeaf->SetViewCell(vc);
                }
        }
}


ViewCell *BspViewCellsManager::ConstructSpatialMergeTree(BspNode *root)
{
        if (root->IsLeaf())
        {
                ViewCell *viewCell = dynamic_cast<BspLeaf *>(root)->GetViewCell();

                viewCell->SetMergeCost(0.0f);

                return viewCell;
        }
        
        BspInterior *interior = dynamic_cast<BspInterior *>(root);
        ViewCellInterior *viewCellInterior = new ViewCellInterior();
                
        float mergeCost = 1.0f / (float)root->mTimeStamp;
        //Debug << "timestamp: " << root->mTimeStamp;
        //Debug << "merge cost: " << mergeCost << endl;

        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(frontVc);
        viewCellInterior->SetupChildLink(backVc);


        viewCellInterior->GetPvs().Merge(backVc->GetPvs());
        viewCellInterior->GetPvs().Merge(frontVc->GetPvs());

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

        viewCellInterior->SetVolume(volume);

        return viewCellInterior;
}


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



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


float KdViewCellsManager::GetProbability(ViewCell *viewCell)
{
        // compute view cell area / volume as subsititute for probability
        if (0)
                return GetArea(viewCell) / 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::Visualize(const ObjectContainer &objects,
                                                                   const VssRayContainer &sampleRays)
{
        if (!ViewCellsConstructed())
                return;

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

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

        if (useViewCells)
        {
                const int leafOut = 10;

                ViewCell::NewMail();

                //-- some rays for output
                const int raysOut = min((int)sampleRays.size(), mVisualizationSamples);
                Debug << "visualization using " << raysOut << " samples" << endl;

                //-- some random view cells and rays for output
                vector<KdLeaf *> kdLeaves;

                for (int i = 0; i < leafOut; ++ i)
                        kdLeaves.push_back(dynamic_cast<KdLeaf *>(mKdTree->GetRandomLeaf()));

                for (int i = 0; i < kdLeaves.size(); ++ i)
                {
                        KdLeaf *leaf = kdLeaves[i];
                        RayContainer vcRays;

                        cout << "creating output for view cell " << i << " ... ";
#if 0
                        // check whether we can add the current ray to the output rays
                        for (int k = 0; k < raysOut; ++ k)
                        {
                                Ray *ray = sampleRays[k];

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

                                        if (leaf->GetViewCell() == leaf2->GetViewCell())
                                        {
                                                vcRays.push_back(ray);
                                        }
                                }
                        }
#endif
                        Intersectable::NewMail();

                        ViewCell *vc = leaf->mViewCell;

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

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

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

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

                        AxisAlignedBox3 box = mKdTree->GetBox(leaf);
                        exporter->ExportBox(box);

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

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

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

                        ObjectPvsMap::iterator it, it_end = vc->GetPvs().mEntries.end();
                        // output PVS of view cell
                        for (it = vc->GetPvs().mEntries.begin(); it !=  it_end; ++ it)
                        {
                                Intersectable *intersect = (*it).first;
                                if (!intersect->Mailed())
                                {
                                        exporter->ExportIntersectable(intersect);
                                        intersect->Mail();
                                }
                        }

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

                DEL_PTR(rays);
        }
        else // using kd PVS of objects
        {
                for (int i = 0; i < limit; ++ i)
                {
                        VssRay *ray = sampleRays[i];

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

                if (exportRays)
                {
                        Exporter *exporter = NULL;
                        exporter = Exporter::GetExporter("sample-rays.x3d");
                        exporter->SetWireframe();
                        exporter->ExportKdTree(*mKdTree);

                        for (i=0; i < pvsOut; i++)
                                exporter->ExportRays(rays[i], RgbColor(1, 0, 0));

                        exporter->SetFilled();

                        delete exporter;
                }

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

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

                        KdPvsMap::iterator i = object->mKdPvs.mEntries.begin();
                        Intersectable::NewMail();

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

                        for (; i != object->mKdPvs.mEntries.end(); i++)
                        {
                                KdNode *node = (*i).first;
                                exporter->ExportBox(mKdTree->GetBox(node));

                                mKdTree->CollectObjects(node, visibleObjects);
                        }

                        exporter->ExportRays(rays[k],  RgbColor(0, 1, 0));
                        exporter->SetFilled();

                        for (int j = 0; j < visibleObjects.size(); j++)
                                exporter->ExportIntersectable(visibleObjects[j]);

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

                        delete exporter;
                }
        }
}


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


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


void KdViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
                                                                                                ViewCell *vc,
                                                                                                const Plane3 *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->mLeaf));
        }
}


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
}


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


VspKdViewCellsManager::VspKdViewCellsManager(VspKdTree *vspKdTree):
ViewCellsManager(), mVspKdTree(vspKdTree)
{
        environment->GetIntValue("VspKdTree.Construction.samples", mInitialSamples);
        mVspKdTree->SetViewCellsManager(this);
}

float VspKdViewCellsManager::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 VspKdViewCellsManager::CollectViewCells()
{
        mVspKdTree->CollectViewCells(mViewCells);
}


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

        VssRayContainer constructionRays;
        VssRayContainer savedRays;

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

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

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

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

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

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

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

        // evaluale view cell stats
        ResetViewCells();

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

        long startTime = GetTime();

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

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

        return merged;
}

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


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

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

        // recalculate stats
        EvaluateViewCellsStats();

        return 0;
}


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

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

        if (mExportGeometry)
                exporter->ExportGeometry(objects);
        
        //exporter->SetWireframe();
        //exporter->ExportVspKdTree(*mVspKdTree, mVspKdTree->GetStatistics().maxPvsSize);
        exporter->ExportVspKdTree(*mVspKdTree);

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

                exporter->SetWireframe();

                //-- collect uniformly distributed rays
                VssRayContainer rays;

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

        delete exporter;
}

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

        //-- export single view cells
        for (int i = 0; i < 10; ++ i)
        {
                char s[64];
                sprintf(s, "vsp_viewcell%04d.x3d", i);
                Exporter *exporter = Exporter::GetExporter(s);
                const int idx =
                        (int)RandomValue(0.0, (Real)((int)mViewCells.size() - 1));

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

                //-- export geometry
                Material m;
                m.mDiffuseColor = RgbColor(0, 1, 1);

                exporter->SetForcedMaterial(m);
                exporter->SetWireframe();

                ExportViewCellGeometry(exporter, vc);

                //-- export stored rays
                
                if (mExportRays)
                {
                        ViewCellContainer leaves;
                        mViewCellsTree->CollectLeaves(vc, leaves);

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

                        for (it = leaves.begin(); it != it_end; ++ it)
                        {
                                VspKdViewCell *vspKdVc = dynamic_cast<VspKdViewCell *>(*it);
                                VspKdLeaf *leaf = vspKdVc->mLeaf;
                                AxisAlignedBox3 box = mVspKdTree->GetBBox(leaf);

                                VssRayContainer vssRays;

                                VssRayContainer castRays;
                                VssRayContainer initRays;

                                leaf->GetRays(vssRays);

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

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

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

                Intersectable::NewMail();

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

                exporter->SetFilled();

                for (it = vc->GetPvs().mEntries.begin(); it != it_end; ++ it)
                {
                        Intersectable *intersect = (*it).first;

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

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

                delete exporter;
        }

        //-- export final view cells
        Exporter *exporter = Exporter::GetExporter("vspkdtree_merged.x3d");

        //if (exportGeometry) exporter->SetWireframe();
        //else exporter->SetFilled();

        ExportViewCellsForViz(exporter);

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

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

                exporter->SetWireframe();

                VssRayContainer rays;

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

        delete exporter;
}

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


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


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

        float importance = 0;

        switch (mColorCode)
        {
        case 1: // pvs
                {
                        importance = (float)vc->GetPvs().GetSize() /
                                (float)mCurrentViewCellsStats.maxPvs;
                }
                break;
        case 2: // merged leaves
                {
                int lSize = mViewCellsTree->GetSize(vc);
                        importance = (float)lSize /
                                (float)mCurrentViewCellsStats.maxLeaves;
                }
                break;
        case 3: // merged tree depth difference
                {
                        //importance = (float)GetMaxTreeDiff(vc) /
                        //      (float)(mVspBspTree->GetStatistics().maxDepth * 2);
                }
                break;
        default:
                break;
        }

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


void VspKdViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
                                                                                                   ViewCell *vc,
                                                                                                   const Plane3 *clipPlane) const
{
        VspKdViewCell *kdVc = dynamic_cast<VspKdViewCell *>(vc);

        Mesh m;

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

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

        for (it = leaves.begin(); it != it_end; ++ it)
        {
                VspKdLeaf *l = dynamic_cast<VspKdViewCell *>(*it)->mLeaf;
                mVspKdTree->GetBBox(l).AddBoxToMesh(&m);
        }

        exporter->ExportMesh(&m);
}


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


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


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


VspBspViewCellsManager::VspBspViewCellsManager(VspBspTree *vspBspTree):
ViewCellsManager(), mVspBspTree(vspBspTree)
{
        environment->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);
        }
}


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)
{
        // 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: " << (int)constructionRays.size() << endl;
        Debug << "saved rays: " << (int)savedRays.size() << endl;

        mMaxPvsSize = (int)(mMaxPvsRatio * (float)objects.size());

        //TODO: remove
        if (1)
                mVspBspTree->Construct(constructionRays, &mViewSpaceBox);
        else
                mVspBspTree->Construct(rays, &mViewSpaceBox);

        // collapse invalid regions
        cout << "collapsing invalid tree regions ... ";
        long startTime = GetTime();
        int collapsedLeaves = mVspBspTree->CollapseTree();
        Debug << "collapsed in " << TimeDiff(startTime, GetTime()) * 1e-3 
                  << " seconds" << endl;

    cout << "finished" << endl;

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

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


        startTime = GetTime();

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

        // recast rest of rays
        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;

        return sampleContributions;
}


void VspBspViewCellsManager::MergeViewCells(const VssRayContainer &rays,
                                                                                        const ObjectContainer &objects)
{
        //-- post processing of bsp view cells
    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
                mViewCellsTree->ConstructMergeTree(rays, objects);
        }
        else
        {
                mViewCellsTree->SetRoot(ConstructSpatialMergeTree(mVspBspTree->GetRoot()));
        }

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

        //-- stats and visualizations
        cout << "finished merging" << 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;
        

        int savedColorCode = mColorCode;
        
        // get currently active view cell set
        ResetViewCells();
        Debug << "\nView cells after merge:\n" << mCurrentViewCellsStats << endl;

        //BspLeaf::NewMail();
        if (1) // export merged view cells
        {
                mColorCode = 0;
                Exporter *exporter = Exporter::GetExporter("merged_view_cells.x3d");
                
                cout << "exporting view cells after merge ... ";

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

                        ExportViewCellsForViz(exporter);

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

                                exporter->ExportGeometry(objects);
                        }

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

        if (1) // export merged view cells using pvs coding
        {
                mColorCode = 1;

                Exporter *exporter = Exporter::GetExporter("merged_view_cells_pvs.x3d");
        
                cout << "exporting view cells after merge (pvs size) ... ";     

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

                        ExportViewCellsForViz(exporter);

                        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;

}


bool VspBspViewCellsManager::EqualToSpatialNode(ViewCell *viewCell) const
{
        return GetSpatialNode(viewCell) != NULL;
}


BspNode *VspBspViewCellsManager::GetSpatialNode(ViewCell *viewCell) const
{
        if (!viewCell->IsLeaf())
        {
                BspViewCell *bspVc = dynamic_cast<BspViewCell *>(viewCell);

                return bspVc->mLeaf;
        }
        else
        {
                ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(viewCell);

                // cannot be node of binary tree
                if (interior->mChildren.size() != 2)
                        return NULL;

                ViewCell *left = interior->mChildren[0];
                ViewCell *right = interior->mChildren[1];

                BspNode *leftNode = GetSpatialNode(left);
                BspNode *rightNode = GetSpatialNode(right);

                if (leftNode && rightNode && leftNode->IsSibling(rightNode))
                {
                        return leftNode->GetParent(); 
                }
        }

        return NULL;
}


void VspBspViewCellsManager::RefineViewCells(const VssRayContainer &rays,
                                                                                         const ObjectContainer &objects)
{
        Debug << "render time before refine:" << endl;
        mRenderer->RenderScene();
        SimulationStatistics ss;
        dynamic_cast<RenderSimulator *>(mRenderer)->GetStatistics(ss);
    Debug << ss << endl;

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

        // 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
        SetValidity(mMinPvsSize, mMaxPvsSize); 
        // update valid view space according to valid view cells
        mVspBspTree->ValidateTree();

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

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


        // should maybe be done here to allow merge working with area or volume
        // and to correct the rendering statistics
        if (0)
        {
                FinalizeViewCells(false);
        }

        //-- merge the individual view cells
        MergeViewCells(postProcessRays, objects);
        
        // only for testing
        TestSubdivision();

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


        //-- render simulation after merge + refine
        
        cout << "\nevaluating bsp view cells render time before compress ... ";
        dynamic_cast<RenderSimulator *>(mRenderer)->RenderScene();
        SimulationStatistics ss;
        dynamic_cast<RenderSimulator *>(mRenderer)->GetStatistics(ss);
  

        cout << " finished" << endl;
        cout << ss << endl;
        Debug << ss << endl;


        //-- compression

        if (ViewCellsTreeConstructed() && mCompressViewCells)
        {
                int pvsEntries = mViewCellsTree->GetNumPvsEntries(mViewCellsTree->GetRoot());
                Debug << "number of entries before compress: " << pvsEntries << endl;

                mViewCellsTree->CompressViewCellsPvs();

                pvsEntries = mViewCellsTree->GetNumPvsEntries(mViewCellsTree->GetRoot());
                Debug << "number of entries after compress: " << pvsEntries << endl;
        }


        // collapse sibling leaves that share the same view cell
        if (0)
                mVspBspTree->CollapseTree();

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

        // real meshes are only contructed only at this stage
        FinalizeViewCells(true);

        // write view cells to disc
        if (mExportViewCells)
        {
                char buff[100];
                environment->GetStringValue("ViewCells.filename", buff);
                string vcFilename(buff);

                ExportViewCells(buff);
        }

        return 0;
}


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


ViewCell *VspBspViewCellsManager::ConstructSpatialMergeTree(BspNode *root)
{
        if (root->IsLeaf())
        {
                ViewCell *viewCell = dynamic_cast<BspLeaf *>(root)->GetViewCell();

                viewCell->SetMergeCost(0.0f);

                return viewCell;
        }
        
        BspInterior *interior = dynamic_cast<BspInterior *>(root);
        ViewCellInterior *viewCellInterior = new ViewCellInterior();
                
        float mergeCost = 1.0f / (float)root->mTimeStamp;
        //Debug << "timestamp: " << root->mTimeStamp;
        //Debug << "merge cost: " << mergeCost << endl;

        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(frontVc);
        viewCellInterior->SetupChildLink(backVc);


        viewCellInterior->GetPvs().Merge(backVc->GetPvs());
        viewCellInterior->GetPvs().Merge(frontVc->GetPvs());

        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 view cells
        {       // hack pvs
                int savedColorCode = mColorCode;
                mColorCode = 0;
                Exporter *exporter = Exporter::GetExporter("final_view_cells.x3d");
                
                if (exporter)
                {
                        cout << "exporting view cells after post process ... ";

                        if (0)
                        {
                                exporter->SetWireframe();
                                exporter->ExportBox(mViewSpaceBox);
                                exporter->SetFilled();
                        }

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

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

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

                mColorCode = savedColorCode;
        }

        if (0)
        {
                cout << "exporting depth map ... ";

                Exporter *exporter = Exporter::GetExporter("depth_map.x3d");
                if (exporter)
                {
                        if (1)
                        {
                                exporter->SetWireframe();
                                exporter->ExportBox(mViewSpaceBox);
                                exporter->SetFilled();
                        }

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

                        const int maxDepth = mVspBspTree->mBspStats.maxDepth;

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

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

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

                                ViewCellContainer::const_iterator lit, lit_end = leaves.end();

                                for (lit = leaves.begin(); lit != lit_end; ++ lit)
                                {
                                        BspLeaf *leaf = dynamic_cast<BspViewCell *>(*lit)->mLeaf;

                                        Material m; 

                                        float relDepth = (float)leaf->GetDepth() / (float)maxDepth;
                                        m.mDiffuseColor.r = relDepth;
                                        m.mDiffuseColor.g = 0.0f;
                                        m.mDiffuseColor.b = 1.0f - relDepth;

                    exporter->SetForcedMaterial(m);
                                

                                        BspNodeGeometry geom;
                                        mVspBspTree->ConstructGeometry(leaf, geom);
                                        exporter->ExportPolygons(geom.GetPolys());
                                }
                        }

                        delete exporter;
                }


                cout << "finished" << endl;
        }

        //-- visualization of the BSP splits
        bool exportSplits = false;
        environment->GetBoolValue("VspBspTree.Visualization.exportSplits", exportSplits);

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

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


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

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

                exporter->ExportBspSplits(*mVspBspTree, true);

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

                exporter->ResetForcedMaterial();

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

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

                delete exporter;
        }
}


void VspBspViewCellsManager::ExportBspPvs(const ObjectContainer &objects,
                                                                                  const VssRayContainer &rays)
{
        const int leafOut = 20;

        ViewCell::NewMail();

        cout << "visualization using " << (int)rays.size() << " samples" << endl;
        Debug << "visualization using " << (int)rays.size() << " samples" << endl;
        Debug << "\nOutput view cells: " << endl;

        const bool sortViewCells = true;

        // sort view cells to visualize the largest view cells
        if (sortViewCells)
                stable_sort(mViewCells.begin(), mViewCells.end(), vc_gt);
        
        int limit = min(leafOut, (int)mViewCells.size());

        int raysOut = 0;

        //-- some rays for output
        for (int i = 0; i < limit; ++ i)
        {
                cout << "creating output for view cell " << i << " ... ";

                ViewCell *vc;
        
                if (sortViewCells) // largest view cell pvs first
                        vc = mViewCells[i];
                else
                        vc = mViewCells[(int)RandomValue(0, (float)mViewCells.size() - 1)];

                //bspLeaves[j]->Mail();
                char s[64]; sprintf(s, "bsp-pvs%04d.x3d", i);
                Exporter *exporter = Exporter::GetExporter(s);
                
                Debug << i << ": pvs size=" << (int)mViewCellsTree->GetPvsSize(vc) << endl;

                if (1 || mExportRays)
                {
                        // output rays stored with the view cells during subdivision
                        if (0)
                        {
                                VssRayContainer vcRays;
                VssRayContainer collectRays;

                                raysOut = min((int)rays.size(), 100);

                                // 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)
                                {
                                        BspLeaf *vcLeaf = dynamic_cast<BspViewCell *>(*vit)->mLeaf;
                                
                                        VssRayContainer::const_iterator rit, rit_end = vcLeaf->mVssRays.end();

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

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

                                for (rit = collectRays.begin(); rit != rit_end; ++ rit)
                                {
                                        float p = RandomValue(0.0f, (float)collectRays.size());
                        
                                        if (p < raysOut)
                                                vcRays.push_back(*rit);
                                }
                                //-- export rays piercing this view cell
                                exporter->ExportRays(vcRays, RgbColor(1, 1, 1));
                        }
                
                        // associate new rays with output view cell
                        if (1)
                        {
                                VssRayContainer vcRays;
                                raysOut = min((int)rays.size(), mVisualizationSamples);
                                // check whether we can add the current ray to the output rays
                                for (int k = 0; k < raysOut; ++ k)
                                {
                                        VssRay *ray = rays[k];
                                        for     (int j = 0; j < (int)ray->mViewCells.size(); ++ j)
                                        {
                                                ViewCell *rayvc = ray->mViewCells[j];
        
                                                if (rayvc == vc)
                                                        vcRays.push_back(ray);
                                        }
                                }       
                                
                                //-- export rays piercing this view cell
                                exporter->ExportRays(vcRays, RgbColor(1, 1, 0));
                        }

                }
                

                exporter->SetWireframe();

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

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


                if (1)
                {
                        ObjectPvsMap::const_iterator oit,
                                oit_end = vc->GetPvs().mEntries.end();


                        exporter->SetFilled();

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

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

                                        exporter->ExportIntersectable(intersect);
                                        intersect->Mail();
                                }
                        }
                }
                else
                {
                        m.mDiffuseColor = RgbColor(1, 0, 0);
                        exporter->SetForcedMaterial(m);

                        exporter->ExportGeometry(objects);
                }

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

        Debug << endl;
}


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::ExportColor(Exporter *exporter,
                                                                                 ViewCell *vc) const
{
        const bool vcValid = CheckValidity(vc, mMinPvsSize, mMaxPvsSize);

        float importance = 0;
        static Material m;

        switch (mColorCode)
        {
        case 0: // Random
                {
                        if (vcValid)
                        {
                                m.mDiffuseColor.r = 0.5f + RandomValue(0.0f, 0.5f);
                                m.mDiffuseColor.g = 0.5f + RandomValue(0.0f, 0.5f);
                                m.mDiffuseColor.b = 0.5f + RandomValue(0.f, 0.5f);
                        }
                        else
                        {
                                m.mDiffuseColor.r = 0.0f;
                                m.mDiffuseColor.g = 1.0f;
                                m.mDiffuseColor.b = 0.0f;
                        }

                        exporter->SetForcedMaterial(m);
                        return;
                }
                
        case 1: // pvs
                {
                        importance = (float)vc->GetPvs().GetSize() /
                                (float)mCurrentViewCellsStats.maxPvs;

                }
                break;
        case 2: // merges
                {
            int lSize = mViewCellsTree->GetSize(vc);
                        importance = (float)lSize / (float)mCurrentViewCellsStats.maxLeaves;
                }
                break;
        case 3: // merge tree differene
                {
                        importance = (float)GetMaxTreeDiff(vc) /
                                (float)(mVspBspTree->GetStatistics().maxDepth * 2);

                }
                break;
        default:
                break;
        }

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

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


void VspBspViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
                                                    ViewCell *vc,
                                                                                                        const Plane3 *clipPlane) const
{
        if (vc->GetMesh())
        {
                exporter->ExportMesh(vc->GetMesh());
        
                return;
        }

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

                        BspLeaf *leaf = dynamic_cast<BspViewCell *>(*it)->mLeaf;
                        mVspBspTree->ConstructGeometry(leaf, geom);

                        const int cf = Polygon3::ClassifyPlane(geom.GetPolys(), *clipPlane, 0.00000001f);

                        if (cf == Polygon3::BACK_SIDE)
                        {
                                exporter->ExportPolygons(geom.GetPolys());
                        }
                        else if (cf == Polygon3::SPLIT)
                        {
                                geom.SplitGeometry(front,
                                                                   back,
                                                                   *clipPlane,
                                                                   mViewSpaceBox, 
                                                                   0.00000001f);
        
                                //Debug << "geo size: " << geom.Size() << endl;
                                //Debug << "size b: " << back.Size() << " f: " << front.Size() << endl;
                                if (back.Valid())
                                {
                                        exporter->ExportPolygons(back.GetPolys());
                                }
                        
                        }
                }
        }
        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])->mLeaf;

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

        return maxDist;
}


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

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

        return mVspBspTree->GetViewCell(point);
}


void VspBspViewCellsManager::CreateMesh(ViewCell *vc)
{
        if (vc->GetMesh())
                delete vc->GetMesh();

        
        BspNodeGeometry geom;

        mVspBspTree->ConstructGeometry(vc, geom);
        
        Mesh *mesh = new Mesh();
        geom.AddToMesh(*mesh);
        vc->SetMesh(mesh);
        mMeshContainer.push_back(mesh);
}


ViewCellsManager *ViewCellsManager::LoadViewCells(const string filename, 
                                                                                                  ObjectContainer *objects)
{
        ViewCellsParser parser;

        ViewCellsManager *vm = NULL;

        if (parser.ParseFile(filename, &vm, objects))
        {
                //vm->PrepareLoadedViewCells();
                vm->ResetViewCells();

                vm->mViewCellsFinished = true;
                vm->mMaxPvsSize = (int)objects->size();

                vm->FinalizeViewCells(true);

                vm->mViewCellsTree->AssignRandomColors();
                Debug << (int)vm->mViewCells.size() << " view cells loaded" << endl;
        }
        else
        {
                Debug << "failed loading view cells" << endl;
                DEL_PTR(vm);
        }


        return vm;
}


inline bool ilt(Intersectable *obj1, Intersectable *obj2)
{
        return obj1->mId < obj2->mId;
}


bool VspBspViewCellsManager::ExportViewCells(const string filename)
{
        cout << "exporting view cells to xml ... ";
        std::ofstream stream;

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

        stream.open(filename.c_str());
        stream << "<?xml version=\"1.0\" encoding=\"UTF-8\"?>"<<endl;
        stream << "<Visibility_Solution>" << endl;

        //-- the view space bounding box
        stream << "<ViewSpaceBox" 
                   << " min=\"" << mViewSpaceBox.Min().x << " " << mViewSpaceBox.Min().y << " " << mViewSpaceBox.Min().z << "\""
                   << " max=\"" << mViewSpaceBox.Max().x << " " << mViewSpaceBox.Max().y << " " << mViewSpaceBox.Max().z << "\" />" << endl;

        //-- the type of the view cells hierarchy
        stream << "<Hierarchy name=\"vspBspTree\" />" << endl;

        //-- load the view cells itself, i.e., the ids and the pvs
        stream << "<ViewCells>" << endl;
        
#if 0
        
        ViewCellContainer::const_iterator it, it_end = mViewCells.end();
                
        for (it = mViewCells.begin(); it != it_end; ++ it)
                ExportViewCell(*it, stream);
#else
        mViewCellsTree->Export(stream);
#endif

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

        //-- load the hierarchy
        stream << "<Hierarchy>" << endl;
        mVspBspTree->Export(stream);
        stream << endl << "</Hierarchy>" << endl;

        stream << "</Visibility_Solution>" << endl;
        stream.close();

        cout << "finished" << endl;

        return true;
}


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;
                BspLeaf *leaf = dynamic_cast<BspViewCell *>(*it)->mLeaf;
                mVspBspTree->ConstructGeometry(leaf, geom);

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

                //(*it)->SetVolume(vol);
                //(*it)->SetArea(area);

                area += lArea;
                volume += lVol;

        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;
                BspLeaf *leaf = dynamic_cast<BspViewCell *>(*it)->mLeaf;
                mVspBspTree->ConstructGeometry(leaf, geom);

                const float lVol = geom.GetVolume();
                
                newVol += lVol;
                subdivVol += (*it)->GetVolume();
                
                float thres = 0.9;
                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();
}


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

        if (exporter)
        {
                AxisAlignedBox3 testBox = mViewSpaceBox;
                Vector3 bsize = mViewSpaceBox.Size();

                testBox.Enlarge(Vector3(-bsize[0] * 0.3, 0, -bsize[2] * 0.4));
                
                ViewCellContainer viewCells;
        
                mVspBspTree->ComputeBoxIntersections(testBox, viewCells);
                cout << "view cells: " << viewCells.size() << endl;
                
                exporter->SetWireframe();

                exporter->SetForcedMaterial(RgbColor(1,1,1));
                exporter->ExportBox(testBox);
                
                exporter->SetFilled();
                exporter->ResetForcedMaterial();
        for (int i = 0; i < viewCells.size(); ++ i)
                {
                        BspNodeGeometry geom;
                                
                        mVspBspTree->ConstructGeometry(viewCells[i], geom);
                        exporter->ExportPolygons(geom.GetPolys());
                }               

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

                delete exporter;
        }
}


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


void VspBspViewCellsManager::AddCurrentViewCellsToHierarchy()
{
        ViewCellContainer::const_iterator it, it_end = mViewCells.end();
        for (it = mViewCells.begin(); it != it_end; ++ it)
        {
        }
}

//////////////////////////////////
ViewCellsManager *ViewCellsManagerFactory::Create(const string mName)
{
        //TODO
        return NULL;// new VspBspViewCellsManager();
}