Context Navigation

← Previous Changeset
Next Changeset →

Changeset 1021

Timestamp:

06/19/06 16:14:40 (18 years ago)

Author:

mattausch

Message:

added view cells manager for vsposptree

Location:

GTP/trunk/Lib/Vis/Preprocessing/src

Files:

: 7 edited

Preprocessor.cpp (modified) (1 diff)
SamplingStrategy.cpp (modified) (2 diffs)
SamplingStrategy.h (modified) (2 diffs)
ViewCellsManager.cpp (modified) (10 diffs)
ViewCellsManager.h (modified) (13 diffs)
VspOspTree.cpp (modified) (5 diffs)
VspOspTree.h (modified) (2 diffs)

Legend:

: Unmodified
: Added
: Removed

GTP/trunk/Lib/Vis/Preprocessing/src/Preprocessor.cpp

-                      r1020
+                      r1021
         case SPATIAL_BOX_BASED_DISTRIBUTION:
                 return new SpatialBoxBasedDistribution(*this);
         case OBJECTS_INTERIOR_DISTRIBUTION:
                 return new ObjectsInteriorDistribution(*this);
+        //case OBJECTS_INTERIOR_DISTRIBUTION:
+        //      return new ObjectsInteriorDistribution(*this);
         default: // no valid strategy
                 return NULL;

GTP/trunk/Lib/Vis/Preprocessing/src/SamplingStrategy.cpp

r1020	r1021
142	142	}
143	143
144
	144	/*
145	145	bool ObjectsInteriorDistribution::GenerateSample(SimpleRay &ray) const
146	146	{
…	…
170	170
171	171	return true;
172		}
	172	}*/
173	173
174	174	}

GTP/trunk/Lib/Vis/Preprocessing/src/SamplingStrategy.h

-                      r1020
+                      r1021
         for sampling the inside of a colon.
 */
 class ObjectsInteriorDistribution: public SamplingStrategy
+/*class ObjectsInteriorDistribution: public SamplingStrategy
+{
  public:
 …
          virtual bool GenerateSample(SimpleRay &ray) const;
 };
+*/
 };

GTP/trunk/Lib/Vis/Preprocessing/src/ViewCellsManager.cpp

-                      r1020
+                      r1021
+        }
         Debug << "empty view cells found: " << (int)mEmptyViewCells.size() << endl;
+}
+bool ViewCellsManager::EqualToSpatialNode(ViewCell *viewCell) const
+{
+        return false;
+}
 …
+}
 bool ViewCellsManager::CheckValidity(ViewCell *vc,
                                                                          int minPvsSize,
 …
-bool ViewCellsManager::EqualToSpatialNode(ViewCell *viewCell) const
+{
-        return false;
+}
 int ViewCellsManager::ComputeBoxIntersections(const AxisAlignedBox3 &box,
                                                                                           ViewCellContainer &viewCells) const
 …
         return 0;
 };
 AxisAlignedBox3 ViewCellsManager::GetFilterBBox(const Vector3 &viewPoint,
 …
+/**********************************************************************/
+/*                 BspViewCellsManager implementation                 */
+/**********************************************************************/
+BspViewCellsManager::BspViewCellsManager(BspTree *bspTree):
+ViewCellsManager(), mBspTree(bspTree)
+{
+        Environment::GetSingleton()->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);
+        // real meshes are contructed at this stage
+        if (0)
+        {
+                cout << "finalizing view cells ... ";
+                FinalizeViewCells(true);
+                cout << "finished" << endl;
+        }
+        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
+                ViewCell *root = ConstructSpatialMergeTree(mBspTree->GetRoot());
+                mViewCellsTree->SetRoot(root);
+                // compute pvs
+                ObjectPvs pvs;
+                UpdatePvsForEvaluation(root, pvs);
+        }
+        // export statistics after merge
+        if (1)
+        {
+                char mstats[100];
+                Environment::GetSingleton()->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.wrl");
+                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 using pvs color coding
+        {
+                mColorCode = 1;
+                Exporter *exporter = Exporter::GetExporter("merged_view_cells_pvs.wrl");
+                cout << "exporting view cells after merge (pvs size) ... ";
+                if (exporter)
+                {
+                        //exporter->SetWireframe();
+                        //exporter->SetForcedMaterial(RandomMaterial());
+                        if (mExportGeometry)
+                                exporter->ExportGeometry(objects);
+                        //exporter->SetWireframe();
+                        exporter->SetFilled();
+                        ExportViewCellsForViz(exporter);
+                        delete exporter;
+                }
+                cout << "finished" << endl;
+        }
+        // only for testing
+        TestSubdivision();
+        mColorCode = savedColorCode;
+        // compute final meshes and volume / area
+        if (1) FinalizeViewCells(true);
+        // write view cells to disc
+        if (mExportViewCells)
+        {
+                char filename[100];
+                Environment::GetSingleton()->GetStringValue("ViewCells.filename", filename);
+                ExportViewCells(filename, mExportPvs, objects);
+        }
+        // export bounding boxes
+        if (0 && mExportBboxesForPvs)
+        {
+                char filename[100];
+                Environment::GetSingleton()->GetStringValue("ViewCells.boxesFilename", filename);
+                ExportBoundingBoxes(filename, objects);
+        }
+        return 0;
+}
+BspViewCellsManager::~BspViewCellsManager()
+{
+}
+int BspViewCellsManager::GetType() const
+{
+        return BSP;
+}
+void BspViewCellsManager::Visualize(const ObjectContainer &objects,
+                                                                        const VssRayContainer &sampleRays)
+{
+void
+ViewCellsManager::ApplyFilter(ViewCell *viewCell,
+                                                          KdTree *kdTree,
+                                                          const float viewSpaceFilterSize,
+                                                          const float spatialFilterSize,
+                                                          ObjectPvs &pvs
+                                                          )
+{
+  // extend the pvs of the viewcell by pvs of its neighbors
+  // and apply spatial filter by including all neighbors of the objects
+  // in the pvs
+  // get all viewcells intersecting the viewSpaceFilterBox
+  // and compute the pvs union
+  //Vector3 center = viewCell->GetBox().Center();
+  //  Vector3 center = m->mBox.Center();
+  //  AxisAlignedBox3 box(center - Vector3(viewSpaceFilterSize/2),
+  //                                      center + Vector3(viewSpaceFilterSize/2));
         if (!ViewCellsConstructed())
                 return;
+        int savedColorCode = mColorCode;
+        if (1) // export final view cells
+        {
+                mColorCode = 1; // hack color code
+                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->SetFilled();
+                        const bool b = mUseClipPlaneForViz;
+                        mUseClipPlaneForViz = false;
+                        ExportViewCellsForViz(exporter);
+                        mUseClipPlaneForViz = b;
+                        delete exporter;
+                }
+                cout << "finished" << endl;
+        }
+        mColorCode = savedColorCode;
+        //-- visualization of the BSP splits
+        bool exportSplits = false;
+        Environment::GetSingleton()->GetBoolValue("BspTree.Visualization.exportSplits", exportSplits);
+        if (exportSplits)
+        {
+                cout << "exporting splits ... ";
+                ExportSplits(objects);
+                cout << "finished" << endl;
+        }
+        // export single view cells
+        ExportBspPvs(objects);
+}
+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 in order to find the largest view cells
+        if (0)
+                stable_sort(mViewCells.begin(), mViewCells.end(), ViewCell::SmallerPvs);
+        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->GetNumInitialViewCells(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.9f;
+                if ((lVol < ((*it)->GetVolume() * thres)) ||
+                        (lVol * thres > ((*it)->GetVolume())))
+                        Debug << "warning: " << lVol << " " << (*it)->GetVolume() << endl;
+        }
+        Debug << "exact volume: " << vol << endl;
+        Debug << "subdivision volume: " << subdivVol << endl;
+        Debug << "new volume: " << newVol << endl;
+}
+void BspViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
+                                                                                                 ViewCell *vc,
+                                                                                                 const 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;
+                        mBspTree->ConstructGeometry(leaf, geom);
+                        const float eps = 0.00000001f;
+                        const int cf = geom.Side(*clipPlane, eps);
+                        if (cf == -1)
+                        {
+                                exporter->ExportPolygons(geom.GetPolys());
+                        }
+                        else if (cf == 0)
+                        {
+                                geom.SplitGeometry(front,
+                                                                   back,
+                                                                   *clipPlane,
+                                                                   mViewSpaceBox,
+                                                                   eps);
+                                //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;
+                mBspTree->ConstructGeometry(vc, geom);
+                exporter->ExportPolygons(geom.GetPolys());
+        }
+}
+void BspViewCellsManager::CreateMesh(ViewCell *vc)
+{
+        // delete previous mesh
+        ///DEL_PTR(vc->GetMesh());
+        BspNodeGeometry geom;
+        mBspTree->ConstructGeometry(vc, geom);
+        Mesh *mesh = MeshManager::GetSingleton()->CreateResource();
+        IncludeNodeGeomInMesh(geom, *mesh);
+        vc->SetMesh(mesh);
+}
+void BspViewCellsManager::Finalize(ViewCell *viewCell,
+                                                                   const bool createMesh)
+{
+        float area = 0;
+        float volume = 0;
+        ViewCellContainer leaves;
+        mViewCellsTree->CollectLeaves(viewCell, leaves);
+        ViewCellContainer::const_iterator it, it_end = leaves.end();
+    for (it = leaves.begin(); it != it_end; ++ it)
+        {
+                BspNodeGeometry geom;
+                BspLeaf *leaf = dynamic_cast<BspViewCell *>(*it)->mLeaf;
+                mBspTree->ConstructGeometry(leaf, geom);
+                const float lVol = geom.GetVolume();
+                const 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 bool active) 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, const bool exportPvs, const ObjectContainer &objects)
+{
+#if STILL_HAS_TODO
+        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 << "<VisibilitySolution>" << 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
+        // NOTE: load in vsp bsp here because bsp and vsp bsp can use same tree and vsp bsp is bug free
+        stream << "<Hierarchy name=\"vspBspTree\" >" << endl;
+        //-- load the view cells itself, i.e., the ids and the pvs
+        stream << "<ViewCells>" << endl;
+        mViewCellsTree->Export(stream, exportPvs);
+        stream << "</ViewCells>" << endl;
+        //-- load the hierarchy
+        stream << "<Hierarchy>" << endl;
+        mBspTree->Export(stream);
+        stream << endl << "</Hierarchy>" << endl;
+        stream << "</VisibilitySolution>" << endl;
+        stream.close();
+        cout << "finished" << endl;
+#endif
+        return true;
+}
+ViewCell *BspViewCellsManager::ConstructSpatialMergeTree(BspNode *root)
+{
+        // terminate recursion
+        if (root->IsLeaf())
+        {
+                BspLeaf *leaf = dynamic_cast<BspLeaf *>(root);
+                leaf->GetViewCell()->SetMergeCost(0.0f);
+                return leaf->GetViewCell();
+        }
+        BspInterior *interior = dynamic_cast<BspInterior *>(root);
+        ViewCellInterior *viewCellInterior = new ViewCellInterior();
+        // evaluate merge cost for priority traversal
+        float mergeCost = 1.0f / (float)root->mTimeStamp;
+        viewCellInterior->SetMergeCost(mergeCost);
+        float volume = 0;
+        BspNode *front = interior->GetFront();
+        BspNode *back = interior->GetBack();
+        //-- recursivly compute child hierarchies
+        ViewCell *backVc = ConstructSpatialMergeTree(back);
+        ViewCell *frontVc = ConstructSpatialMergeTree(front);
+        viewCellInterior->SetupChildLink(backVc);
+        viewCellInterior->SetupChildLink(frontVc);
+        volume += backVc->GetVolume();
+        volume += frontVc->GetVolume();
+        viewCellInterior->SetVolume(volume);
+        return viewCellInterior;
+}
+void BspViewCellsManager::UpdatePvsForEvaluation(ViewCell *root, ObjectPvs &pvs)
+{
+        // terminate traversal
+        if (root->IsLeaf())
+        {
+                pvs = root->GetPvs();
+                SetScalarPvsSize(root, pvs.GetSize());
+                return;
+        }
+        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(root);
+        ViewCellContainer::const_iterator vit, vit_end = interior->mChildren.end();
+        vector<ObjectPvs> pvsList;
+        for (vit = interior->mChildren.begin(); vit != vit_end; ++ vit)
+        {
+                ObjectPvs objPvs;
+                //-- recursivly compute child pvss
+                UpdatePvsForEvaluation(*vit, objPvs);
+                // store pvs in vector
+                pvsList.push_back(objPvs);
+        }
+#if 1
+        Intersectable::NewMail();
+        //-- faster way of computing pvs:
+        //   construct merged pvs by adding
+        //   and only those of the next pvs which were not mailed.
+        //   note: sumpdf is not correct!!
+        vector<ObjectPvs>::iterator oit = pvsList.begin();
+        for (vit = interior->mChildren.begin(); vit != vit_end; ++ vit, ++ oit)
+        {
+        ObjectPvsMap::iterator pit, pit_end = (*oit).mEntries.end();
+                for (pit = (*oit).mEntries.begin(); pit != pit_end; ++ pit)
+                {
+                        Intersectable *intersect = (*pit).first;
+                        if (!intersect->Mailed())
+                        {
+                                pvs.AddSample(intersect, (*pit).second.mSumPdf);
+                                intersect->Mail();
+                        }
+                }
+        }
+        // store pvs in this node
+        if (mViewCellsTree->ViewCellsStorage() == ViewCellsTree::PVS_IN_INTERIORS)
+        {
+                interior->SetPvs(pvs);
+        }
+        // set new pvs size
+    SetScalarPvsSize(interior, pvs.GetSize());
+#else
+        // really merge cells: slow put sumpdf is correct
+        ViewCellInterior *viewCellInterior = new ViewCellInterior();
+        viewCellInterior->GetPvs().Merge(backVc->GetPvs());
+        viewCellInterior->GetPvs().Merge(frontVc->GetPvs());
+#endif
+}
+/************************************************************************/
+/*                   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 (viewSpaceFilterSize >= 0.0f) {
+  bool usePrVS = false;
+  if (!usePrVS) {
+        AxisAlignedBox3 box = GetViewCellBox(viewCell);
+        box.Enlarge(Vector3(viewSpaceFilterSize/2));
+        ViewCellContainer viewCells;
+        ComputeBoxIntersections(box, viewCells);
+  //  cout<<"box="<<box<<endl;
+        ViewCellContainer::const_iterator it = viewCells.begin(), it_end = viewCells.end();
+        int i;
+        for (i=0; it != it_end; ++ it, ++ i) {
+                //cout<<"v"<<i<<" pvs="<<(*it)->GetPvs().mEntries.size()<<endl;
+          pvs.Merge((*it)->GetPvs());
+        }
+  } else {
+        PrVs prvs;
+        AxisAlignedBox3 box = GetViewCellBox(viewCell);
+        //  mViewCellsManager->SetMaxFilterSize(1);
+        GetPrVS(box.Center(), prvs, viewSpaceFilterSize);
+        pvs = prvs.mViewCell->GetPvs();
+        DeleteLocalMergeTree(prvs.mViewCell);
+  }
+  } else
+        pvs = viewCell->GetPvs();
+  if (spatialFilterSize >=0.0f)
+        ApplySpatialFilter(kdTree, spatialFilterSize, pvs);
+}
+void
+ViewCellsManager::ApplyFilter(KdTree *kdTree,
+                                                          const float relViewSpaceFilterSize,
+                                                          const float relSpatialFilterSize
+                                                          )
+{
         if (!ViewCellsConstructed())
                 return;
+        // 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
+}
+/**************************************************************************/
+/*                   VspBspViewCellsManager implementation                */
+/**************************************************************************/
+VspBspViewCellsManager::VspBspViewCellsManager(VspBspTree *vspBspTree):
+ViewCellsManager(), mVspBspTree(vspBspTree)
+{
+        Environment::GetSingleton()->GetIntValue("VspBspTree.Construction.samples", mInitialSamples);
+        mVspBspTree->SetViewCellsManager(this);
+        mVspBspTree->mViewCellsTree = mViewCellsTree;
+}
+VspBspViewCellsManager::~VspBspViewCellsManager()
+{
+}
+float VspBspViewCellsManager::GetProbability(ViewCell *viewCell)
+{
+        if (0 && mVspBspTree->mUseAreaForPvs)
+                return GetArea(viewCell) / GetAccVcArea();
+        else
+                return GetVolume(viewCell) / mViewSpaceBox.GetVolume();
+}
+void VspBspViewCellsManager::CollectViewCells()
+{
+        // view cells tree constructed
+        if (!ViewCellsTreeConstructed())
+        {
+                mVspBspTree->CollectViewCells(mViewCells, false);
+        }
+        else
+        {       // we can use the view cells tree hierarchy to get the right set
+                mViewCellsTree->CollectBestViewCellSet(mViewCells, mNumActiveViewCells);
+        }
+}
+bool VspBspViewCellsManager::ViewCellsConstructed() const
+{
+        return mVspBspTree->GetRoot() != NULL;
+}
+ViewCell *VspBspViewCellsManager::GenerateViewCell(Mesh *mesh) const
+{
+        return new BspViewCell(mesh);
+}
+int VspBspViewCellsManager::ConstructSubdivision(const ObjectContainer &objects,
+                                                                                                 const VssRayContainer &rays)
+{
+        mMaxPvsSize = (int)(mMaxPvsRatio * (float)objects.size());
+        // if view cells were already constructed
+        if (ViewCellsConstructed())
+                return 0;
+        int sampleContributions = 0;
+        VssRayContainer sampleRays;
+        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;
+        long startTime;
+        if (1)
+                mVspBspTree->Construct(constructionRays, &mViewSpaceBox);
+        else
+                mVspBspTree->Construct(rays, &mViewSpaceBox);
+        // collapse invalid regions
+        cout << "collapsing invalid tree regions ... ";
+        startTime = GetTime();
+        const 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;
+        // real meshes are contructed at this stage
+        if (0)
+        {
+                cout << "finalizing view cells ... ";
+                FinalizeViewCells(true);
+                cout << "finished" << endl;
+        }
+        return sampleContributions;
+}
+void VspBspViewCellsManager::MergeViewCells(const VssRayContainer &rays,
+                                                                                        const ObjectContainer &objects)
+{
+    int vcSize = 0;
+        int pvsSize = 0;
+        //-- merge view cells
+        cout << "starting merge using " << mPostProcessSamples << " samples ... " << endl;
+        long startTime = GetTime();
+        if (mMergeViewCells)
+        {
+                // TODO: should be done BEFORE the ray casting
+                // compute tree by merging the nodes based on cost heuristics
+                mViewCellsTree->ConstructMergeTree(rays, objects);
+        }
+        else
+        {
+                // compute tree by merging the nodes of the spatial hierarchy
+                ViewCell *root = ConstructSpatialMergeTree(mVspBspTree->GetRoot());
+                mViewCellsTree->SetRoot(root);
+                // compute pvs
+                ObjectPvs pvs;
+                UpdatePvsForEvaluation(root, pvs);
+        }
+        if (1)
+        {
+                char mstats[100];
+                ObjectPvs pvs;
+                Environment::GetSingleton()->GetStringValue("ViewCells.mergeStats", mstats);
+                mViewCellsTree->ExportStats(mstats);
+        }
+        //-- 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.wrl");
+                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.wrl");
+                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
+        int minPvs, maxPvs;
+        if (0)
+        {
+                minPvs = mMinPvsSize;
+                maxPvs = mMaxPvsSize;
+        }
+        else
+        {
+                minPvs = mPruneEmptyViewCells ? 1 : 0;
+                maxPvs = mMaxPvsSize;
+        }
+        Debug << "setting validity, min: " << minPvs << " max: " << maxPvs << endl;
+        cout << "setting validity, min: " << minPvs << " max: " << maxPvs << endl;
+        SetValidity(minPvs, maxPvs);
+        // update valid view space according to valid view cells
+        if (0) mVspBspTree->ValidateTree();
+        // area has to be recomputed
+        mTotalAreaValid = false;
+        VssRayContainer postProcessRays;
+        GetRaySets(rays, mPostProcessSamples, postProcessRays);
+        Debug << "post processing using " << (int)postProcessRays.size() << " samples" << endl;
+        // 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 debugging purpose: test if the subdivision is valid
+        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);
+  ViewCellContainer::const_iterator it, it_end = mViewCells.end();
+  ObjectPvs *newPvs;
+  newPvs = new ObjectPvs[mViewCells.size()];
+  float viewSpaceFilterSize = Magnitude(mViewSpaceBox.Size())*relViewSpaceFilterSize;
+  float spatialFilterSize = Magnitude(kdTree->GetBox().Size())*relSpatialFilterSize;
+        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->SetViewCellsStorage(ViewCellsTree::COMPRESSED);
+                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();
+        // compute final meshes and volume / area
+        if (1) FinalizeViewCells(true);
+        // write view cells to disc
+        if (mExportViewCells)
+        {
+                char filename[100];
+                Environment::GetSingleton()->GetStringValue("ViewCells.filename", filename);
+                ExportViewCells(filename, mExportPvs, objects);
+        }
+        // export bounding boxes
+        if (mExportBboxesForPvs)
+        {
+                char filename[100];
+                Environment::GetSingleton()->GetStringValue("ViewCells.boxesFilename", filename);
+                ExportBoundingBoxes(filename, objects);
+        }
+        return 0;
+}
+int VspBspViewCellsManager::GetType() const
+{
+        return VSP_BSP;
+}
+ViewCell *VspBspViewCellsManager::ConstructSpatialMergeTree(BspNode *root)
+{
+        // terminate recursion
+        if (root->IsLeaf())
+        {
+                BspLeaf *leaf = dynamic_cast<BspLeaf *>(root);
+                leaf->GetViewCell()->SetMergeCost(0.0f);
+                return leaf->GetViewCell();
+        }
+        BspInterior *interior = dynamic_cast<BspInterior *>(root);
+        ViewCellInterior *viewCellInterior = new ViewCellInterior();
+        // evaluate merge cost for priority traversal
+        float mergeCost = 1.0f / (float)root->mTimeStamp;
+        viewCellInterior->SetMergeCost(mergeCost);
+        float volume = 0;
+        BspNode *front = interior->GetFront();
+        BspNode *back = interior->GetBack();
+        ObjectPvs frontPvs, backPvs;
+        //-- recursivly compute child hierarchies
+        ViewCell *backVc = ConstructSpatialMergeTree(back);
+        ViewCell *frontVc = ConstructSpatialMergeTree(front);
+        viewCellInterior->SetupChildLink(backVc);
+        viewCellInterior->SetupChildLink(frontVc);
+        volume += backVc->GetVolume();
+        volume += frontVc->GetVolume();
+        viewCellInterior->SetVolume(volume);
+        return viewCellInterior;
+}
+void VspBspViewCellsManager::UpdatePvsForEvaluation(ViewCell *root, ObjectPvs &pvs)
+{
+        // terminate traversal
+        if (root->IsLeaf())
+        {
+                pvs = root->GetPvs();
+                SetScalarPvsSize(root, root->GetPvs().GetSize());
+                return;
+        }
+        //-- interior node => propagate pvs up
+        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(root);
+        interior->GetPvs().Clear();
+  int i;
+  for (i=0, it = mViewCells.begin(); it != it_end; ++ it, ++ i) {
+        ApplyFilter(*it,
+                                kdTree,
+                                viewSpaceFilterSize,
+                                spatialFilterSize,
+                                newPvs[i]
+                                );
+  }
+  // now replace all pvss
+  for (i = 0, it = mViewCells.begin(); it != it_end; ++ it, ++ i) {
+        ObjectPvs &pvs = (*it)->GetPvs();
         pvs.Clear();
+        vector<ObjectPvs> pvsList;
+        ViewCellContainer::const_iterator vit, vit_end = interior->mChildren.end();
+        for (vit = interior->mChildren.begin(); vit != vit_end; ++ vit)
+        {
+                ObjectPvs objPvs;
+                //-- recursivly compute child pvss
+                UpdatePvsForEvaluation(*vit, objPvs);
+                // store pvs in vector
+                pvsList.push_back(objPvs);
+        }
+#if 1
+        Intersectable::NewMail();
+        //-- faster way of computing pvs:
+        //   construct merged pvs by adding
+        //   and only those of the next pvs which were not mailed.
+        //   note: sumpdf is not correct!!
+        vector<ObjectPvs>::iterator oit = pvsList.begin();
+        for (vit = interior->mChildren.begin(); vit != vit_end; ++ vit, ++ oit)
+        {
+            ObjectPvsMap::iterator pit, pit_end = (*oit).mEntries.end();
+                for (pit = (*oit).mEntries.begin(); pit != pit_end; ++ pit)
+                {
+                        Intersectable *intersect = (*pit).first;
+                        if (!intersect->Mailed())
+                        {
+                                pvs.AddSample(intersect, (*pit).second.mSumPdf);
+                                intersect->Mail();
+                        }
+                }
+        }
+        // store pvs in this node
+        if (mViewCellsTree->ViewCellsStorage() == ViewCellsTree::PVS_IN_INTERIORS)
+        {
+                interior->SetPvs(pvs);
+        }
+        // set new pvs size
+        SetScalarPvsSize(interior, pvs.GetSize());
+#else
+        // really merge cells: slow put sumpdf is correct
+        viewCellInterior->GetPvs().Merge(backVc->GetPvs());
+        viewCellInterior->GetPvs().Merge(frontVc->GetPvs());
+#endif
+}
+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);
+        //-- export view cells
+        if (1)
+        {       // hack pvs
+                const int savedColorCode = mColorCode;
+                mColorCode = 1;
+                Exporter *exporter = Exporter::GetExporter("final_view_cells.wrl");
+                if (exporter)
+                {
+                        cout << "exporting view cells after post process ... ";
+                        if (0)
+                        {
+                                // export view space box
+                                exporter->SetWireframe();
+                                exporter->ExportBox(mViewSpaceBox);
+                                exporter->SetFilled();
+                        }
+                        if (mExportGeometry)
+                        {
+                                exporter->ExportGeometry(objects);
+                        }
+                        // export rays
+                        if (1 && mExportRays)
+                        {
+                                exporter->ExportRays(visRays, RgbColor(0, 1, 0));
+                        }
+                        //exporter->SetFilled();
+                        // HACK: export without clip plane
+                        const bool b = mUseClipPlaneForViz;
+                        mUseClipPlaneForViz = false;
+                        ExportViewCellsForViz(exporter);
+                        mUseClipPlaneForViz = b;
+                        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::GetSingleton()->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)
+{
+        int leafOut;
+        Environment::GetSingleton()->GetIntValue("ViewCells.Visualization.maxOutput", leafOut);
+        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(), ViewCell::SmallerPvs);
+                stable_sort(mViewCells.begin(), mViewCells.end(), ViewCell::LargerRenderCost);
+        }
+        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)];
+                ObjectPvs pvs;
+                mViewCellsTree->GetPvs(vc, pvs);
+                //bspLeaves[j]->Mail();
+                char s[64]; sprintf(s, "bsp-pvs%04d.wrl", i);
+                Exporter *exporter = Exporter::GetExporter(s);
+                Debug << i << ": pvs size=" << (int)mViewCellsTree->GetPvsSize(vc) << endl;
+                //-- export the sample rays
+                if (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));
+                        }
+                }
+                //-- export view cell geometry
+                exporter->SetWireframe();
+                Material m;//= RandomMaterial();
+                m.mDiffuseColor = RgbColor(0, 1, 0);
+                exporter->SetForcedMaterial(m);
+                ExportViewCellGeometry(exporter, vc);
+                exporter->SetFilled();
+                //-- export pvs
+                if (1)
+                {
+                        ObjectPvsMap::const_iterator oit,
+                                oit_end = pvs.mEntries.end();
+                        Intersectable::NewMail();
+                        // output PVS of view cell
+                        for (oit = pvs.mEntries.begin(); oit != oit_end; ++ oit)
+                        {
+                                Intersectable *intersect = (*oit).first;
+                                if (!intersect->Mailed())
+                                {
+                                        m = RandomMaterial();
+                                        exporter->SetForcedMaterial(m);
+                                        exporter->ExportIntersectable(intersect);
+                                        intersect->Mail();
+                                }
+                        }
+                }
+                if (0)
+                {   // export scene geometry
+                        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
+        pvs = newPvs[i];
+        newPvs[i].Clear();
+  }
+  delete [] newPvs;
+}
+void
+ViewCellsManager::ApplySpatialFilter(
+                                                                         KdTree *kdTree,
+                                                                         const float spatialFilterSize,
+                                                                         ObjectPvs &pvs
+                                                                         )
+{
+  // now compute a new Pvs by including also objects intersecting the
+  // extended boxes of visible objects
+  Intersectable::NewMail();
+  std::map<Intersectable *,
+        PvsData<Intersectable *>,
+        LtSample<Intersectable *> >::const_iterator oi;
+  for (oi = pvs.mEntries.begin(); oi != pvs.mEntries.end(); ++oi) {
+        Intersectable *object = (*oi).first;
+        object->Mail();
+  }
+  ObjectPvs nPvs;
+  int nPvsSize=0;
+  // now go through the pvs again
+  for (oi = pvs.mEntries.begin(); oi != pvs.mEntries.end(); ++oi) {
+        Intersectable *object = (*oi).first;
+        //      Vector3 center = object->GetBox().Center();
+        //      AxisAlignedBox3 box(center - Vector3(spatialFilterSize/2),
+        //                                              center + Vector3(spatialFilterSize/2));
+        AxisAlignedBox3 box = object->GetBox();
+        box.Enlarge(Vector3(spatialFilterSize/2));
+        ObjectContainer objects;
+        // $$ warning collect objects takes only unmailed ones!
+        kdTree->CollectObjects(box,
+                                                   objects);
+        //      cout<<"collected objects="<<objects.size()<<endl;
+        ObjectContainer::const_iterator noi = objects.begin();
+        for (; noi != objects.end(); ++noi) {
+          Intersectable *o = *noi;
+          // $$ JB warning: pdfs are not correct at this point!
+          nPvs.AddSample(o, Limits::Small);
+          nPvsSize++;
+        }
+  }
+  //  cout<<"nPvs size = "<<nPvsSize<<endl;
+  pvs.Merge(nPvs);
+}
+void ViewCellsManager::ExportColor(Exporter *exporter, ViewCell *vc) const
+{
         const bool vcValid = CheckValidity(vc, mMinPvsSize, mMaxPvsSize);
 …
         case 2: // merges
+                {
             int lSize = mViewCellsTree->GetNumInitialViewCells(vc);
+            const int lSize = mViewCellsTree->GetNumInitialViewCells(vc);
                         importance = (float)lSize / (float)mCurrentViewCellsStats.maxLeaves;
+                }
                 break;
+#if 0
         case 3: // merge tree differene
+                {
 …
+                }
                 break;
+#endif
         default:
                 break;
 …
         //Debug << "importance: " << importance << endl;
         exporter->SetForcedMaterial(m);
+}
+/**********************************************************************/
+/*                 BspViewCellsManager implementation                 */
+/**********************************************************************/
+BspViewCellsManager::BspViewCellsManager(BspTree *bspTree):
+ViewCellsManager(), mBspTree(bspTree)
+{
+        Environment::GetSingleton()->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);
+        // real meshes are contructed at this stage
+        if (0)
+        {
+                cout << "finalizing view cells ... ";
+                FinalizeViewCells(true);
+                cout << "finished" << endl;
+        }
+        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
+                ViewCell *root = ConstructSpatialMergeTree(mBspTree->GetRoot());
+                mViewCellsTree->SetRoot(root);
+                // compute pvs
+                ObjectPvs pvs;
+                UpdatePvsForEvaluation(root, pvs);
+        }
+        // export statistics after merge
+        if (1)
+        {
+                char mstats[100];
+                Environment::GetSingleton()->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.wrl");
+                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 using pvs color coding
+        {
+                mColorCode = 1;
+                Exporter *exporter = Exporter::GetExporter("merged_view_cells_pvs.wrl");
+                cout << "exporting view cells after merge (pvs size) ... ";
+                if (exporter)
+                {
+                        //exporter->SetWireframe();
+                        //exporter->SetForcedMaterial(RandomMaterial());
+                        if (mExportGeometry)
+                                exporter->ExportGeometry(objects);
+                        //exporter->SetWireframe();
+                        exporter->SetFilled();
+                        ExportViewCellsForViz(exporter);
+                        delete exporter;
+                }
+                cout << "finished" << endl;
+        }
+        // only for testing
+        TestSubdivision();
+        mColorCode = savedColorCode;
+        // compute final meshes and volume / area
+        if (1) FinalizeViewCells(true);
+        // write view cells to disc
+        if (mExportViewCells)
+        {
+                char filename[100];
+                Environment::GetSingleton()->GetStringValue("ViewCells.filename", filename);
+                ExportViewCells(filename, mExportPvs, objects);
+        }
+        // export bounding boxes
+        if (0 && mExportBboxesForPvs)
+        {
+                char filename[100];
+                Environment::GetSingleton()->GetStringValue("ViewCells.boxesFilename", filename);
+                ExportBoundingBoxes(filename, objects);
+        }
+        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; // hack color code
+                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->SetFilled();
+                        const bool b = mUseClipPlaneForViz;
+                        mUseClipPlaneForViz = false;
+                        ExportViewCellsForViz(exporter);
+                        mUseClipPlaneForViz = b;
+                        delete exporter;
+                }
+                cout << "finished" << endl;
+        }
+        mColorCode = savedColorCode;
+        //-- visualization of the BSP splits
+        bool exportSplits = false;
+        Environment::GetSingleton()->GetBoolValue("BspTree.Visualization.exportSplits", exportSplits);
+        if (exportSplits)
+        {
+                cout << "exporting splits ... ";
+                ExportSplits(objects);
+                cout << "finished" << endl;
+        }
+        // export single view cells
+        ExportBspPvs(objects);
+}
+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 in order to find the largest view cells
+        if (0)
+                stable_sort(mViewCells.begin(), mViewCells.end(), ViewCell::SmallerPvs);
+        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::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.9f;
+                if ((lVol < ((*it)->GetVolume() * thres)) ||
+                        (lVol * thres > ((*it)->GetVolume())))
+                        Debug << "warning: " << lVol << " " << (*it)->GetVolume() << endl;
+        }
+        Debug << "exact volume: " << vol << endl;
+        Debug << "subdivision volume: " << subdivVol << endl;
+        Debug << "new volume: " << newVol << endl;
+}
+void BspViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
+                                                                                                 ViewCell *vc,
+                                                                                                 const 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;
+                        mBspTree->ConstructGeometry(leaf, geom);
+                        const float eps = 0.00000001f;
+                        const int cf = geom.Side(*clipPlane, eps);
+                        if (cf == -1)
+                        {
+                                exporter->ExportPolygons(geom.GetPolys());
+                        }
+                        else if (cf == 0)
+                        {
+                                geom.SplitGeometry(front,
+                                                                   back,
+                                                                   *clipPlane,
+                                                                   mViewSpaceBox,
+                                                                   eps);
+                                //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;
+                mBspTree->ConstructGeometry(vc, geom);
+                exporter->ExportPolygons(geom.GetPolys());
+        }
+}
+void BspViewCellsManager::CreateMesh(ViewCell *vc)
+{
+        // delete previous mesh
+        ///DEL_PTR(vc->GetMesh());
+        BspNodeGeometry geom;
+        mBspTree->ConstructGeometry(vc, geom);
+        Mesh *mesh = MeshManager::GetSingleton()->CreateResource();
+        IncludeNodeGeomInMesh(geom, *mesh);
+        vc->SetMesh(mesh);
+}
+void BspViewCellsManager::Finalize(ViewCell *viewCell,
+                                                                   const bool createMesh)
+{
+        float area = 0;
+        float volume = 0;
+        ViewCellContainer leaves;
+        mViewCellsTree->CollectLeaves(viewCell, leaves);
+        ViewCellContainer::const_iterator it, it_end = leaves.end();
+    for (it = leaves.begin(); it != it_end; ++ it)
+        {
+                BspNodeGeometry geom;
+                BspLeaf *leaf = dynamic_cast<BspViewCell *>(*it)->mLeaf;
+                mBspTree->ConstructGeometry(leaf, geom);
+                const float lVol = geom.GetVolume();
+                const 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 bool active) const
+{
+        if (!ViewCellsConstructed())
+                return NULL;
+        if (!mViewSpaceBox.IsInside(point))
+                return NULL;
+        return mBspTree->GetViewCell(point);
+}
+void BspViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays,
+                                                                                                 vector<MergeCandidate> &candidates)
+{
+        cout << "collecting merge candidates ... " << endl;
+        if (mUseRaysForMerge)
+        {
+                mBspTree->CollectMergeCandidates(rays, candidates);
+        }
+        else
+        {
+                vector<BspLeaf *> leaves;
+                mBspTree->CollectLeaves(leaves);
+                mBspTree->CollectMergeCandidates(leaves, candidates);
+        }
+        cout << "fininshed collecting candidates" << endl;
+}
+bool BspViewCellsManager::ExportViewCells(const string filename, const bool exportPvs, const ObjectContainer &objects)
+{
+#if STILL_HAS_TODO
+        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 << "<VisibilitySolution>" << 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
+        // NOTE: load in vsp bsp here because bsp and vsp bsp can use same tree and vsp bsp is bug free
+        stream << "<Hierarchy name=\"vspBspTree\" >" << endl;
+        //-- load the view cells itself, i.e., the ids and the pvs
+        stream << "<ViewCells>" << endl;
+        mViewCellsTree->Export(stream, exportPvs);
+        stream << "</ViewCells>" << endl;
+        //-- load the hierarchy
+        stream << "<Hierarchy>" << endl;
+        mBspTree->Export(stream);
+        stream << endl << "</Hierarchy>" << endl;
+        stream << "</VisibilitySolution>" << endl;
+        stream.close();
+        cout << "finished" << endl;
+#endif
+        return true;
+}
+ViewCell *BspViewCellsManager::ConstructSpatialMergeTree(BspNode *root)
+{
+        // terminate recursion
+        if (root->IsLeaf())
+        {
+                BspLeaf *leaf = dynamic_cast<BspLeaf *>(root);
+                leaf->GetViewCell()->SetMergeCost(0.0f);
+                return leaf->GetViewCell();
+        }
+        BspInterior *interior = dynamic_cast<BspInterior *>(root);
+        ViewCellInterior *viewCellInterior = new ViewCellInterior();
+        // evaluate merge cost for priority traversal
+        float mergeCost = 1.0f / (float)root->mTimeStamp;
+        viewCellInterior->SetMergeCost(mergeCost);
+        float volume = 0;
+        BspNode *front = interior->GetFront();
+        BspNode *back = interior->GetBack();
+        //-- recursivly compute child hierarchies
+        ViewCell *backVc = ConstructSpatialMergeTree(back);
+        ViewCell *frontVc = ConstructSpatialMergeTree(front);
+        viewCellInterior->SetupChildLink(backVc);
+        viewCellInterior->SetupChildLink(frontVc);
+        volume += backVc->GetVolume();
+        volume += frontVc->GetVolume();
+        viewCellInterior->SetVolume(volume);
+        return viewCellInterior;
+}
+void BspViewCellsManager::UpdatePvsForEvaluation(ViewCell *root, ObjectPvs &pvs)
+{
+        // terminate traversal
+        if (root->IsLeaf())
+        {
+                pvs = root->GetPvs();
+                SetScalarPvsSize(root, pvs.GetSize());
+                return;
+        }
+        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(root);
+        ViewCellContainer::const_iterator vit, vit_end = interior->mChildren.end();
+        vector<ObjectPvs> pvsList;
+        for (vit = interior->mChildren.begin(); vit != vit_end; ++ vit)
+        {
+                ObjectPvs objPvs;
+                //-- recursivly compute child pvss
+                UpdatePvsForEvaluation(*vit, objPvs);
+                // store pvs in vector
+                pvsList.push_back(objPvs);
+        }
+#if 1
+        Intersectable::NewMail();
+        //-- faster way of computing pvs:
+        //   construct merged pvs by adding
+        //   and only those of the next pvs which were not mailed.
+        //   note: sumpdf is not correct!!
+        vector<ObjectPvs>::iterator oit = pvsList.begin();
+        for (vit = interior->mChildren.begin(); vit != vit_end; ++ vit, ++ oit)
+        {
+        ObjectPvsMap::iterator pit, pit_end = (*oit).mEntries.end();
+                for (pit = (*oit).mEntries.begin(); pit != pit_end; ++ pit)
+                {
+                        Intersectable *intersect = (*pit).first;
+                        if (!intersect->Mailed())
+                        {
+                                pvs.AddSample(intersect, (*pit).second.mSumPdf);
+                                intersect->Mail();
+                        }
+                }
+        }
+        // store pvs in this node
+        if (mViewCellsTree->ViewCellsStorage() == ViewCellsTree::PVS_IN_INTERIORS)
+        {
+                interior->SetPvs(pvs);
+        }
+        // set new pvs size
+    SetScalarPvsSize(interior, pvs.GetSize());
+#else
+        // really merge cells: slow nut sumpdf is correct
+        ViewCellInterior *viewCellInterior = new ViewCellInterior();
+        viewCellInterior->GetPvs().Merge(backVc->GetPvs());
+        viewCellInterior->GetPvs().Merge(frontVc->GetPvs());
+#endif
+}
+/************************************************************************/
+/*                   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;
+                }
+        }
+}
+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
+}
+/**************************************************************************/
+/*                   VspBspViewCellsManager implementation                */
+/**************************************************************************/
+VspBspViewCellsManager::VspBspViewCellsManager(VspBspTree *vspBspTree):
+ViewCellsManager(), mVspBspTree(vspBspTree)
+{
+        Environment::GetSingleton()->GetIntValue("VspBspTree.Construction.samples", mInitialSamples);
+        mVspBspTree->SetViewCellsManager(this);
+        mVspBspTree->mViewCellsTree = mViewCellsTree;
+}
+VspBspViewCellsManager::~VspBspViewCellsManager()
+{
+}
+float VspBspViewCellsManager::GetProbability(ViewCell *viewCell)
+{
+        if (0 && mVspBspTree->mUseAreaForPvs)
+                return GetArea(viewCell) / GetAccVcArea();
+        else
+                return GetVolume(viewCell) / mViewSpaceBox.GetVolume();
+}
+void VspBspViewCellsManager::CollectViewCells()
+{
+        // view cells tree constructed
+        if (!ViewCellsTreeConstructed())
+        {
+                mVspBspTree->CollectViewCells(mViewCells, false);
+        }
+        else
+        {       // we can use the view cells tree hierarchy to get the right set
+                mViewCellsTree->CollectBestViewCellSet(mViewCells, mNumActiveViewCells);
+        }
+}
+void VspBspViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays,
+                                                                                                        vector<MergeCandidate> &candidates)
+{
+        cout << "collecting merge candidates ... " << endl;
+        if (mUseRaysForMerge)
+        {
+                mVspBspTree->CollectMergeCandidates(rays, candidates);
+        }
+        else
+        {
+                vector<BspLeaf *> leaves;
+                mVspBspTree->CollectLeaves(leaves);
+                mVspBspTree->CollectMergeCandidates(leaves, candidates);
+        }
+        cout << "fininshed collecting candidates" << endl;
+}
+bool VspBspViewCellsManager::ViewCellsConstructed() const
+{
+        return mVspBspTree->GetRoot() != NULL;
+}
+ViewCell *VspBspViewCellsManager::GenerateViewCell(Mesh *mesh) const
+{
+        return new BspViewCell(mesh);
+}
+int VspBspViewCellsManager::ConstructSubdivision(const ObjectContainer &objects,
+                                                                                                 const VssRayContainer &rays)
+{
+        mMaxPvsSize = (int)(mMaxPvsRatio * (float)objects.size());
+        // if view cells were already constructed
+        if (ViewCellsConstructed())
+                return 0;
+        int sampleContributions = 0;
+        VssRayContainer sampleRays;
+        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;
+        long startTime;
+        if (1)
+                mVspBspTree->Construct(constructionRays, &mViewSpaceBox);
+        else
+                mVspBspTree->Construct(rays, &mViewSpaceBox);
+        // collapse invalid regions
+        cout << "collapsing invalid tree regions ... ";
+        startTime = GetTime();
+        const 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;
+        // real meshes are contructed at this stage
+        if (0)
+        {
+                cout << "finalizing view cells ... ";
+                FinalizeViewCells(true);
+                cout << "finished" << endl;
+        }
+        return sampleContributions;
+}
+void VspBspViewCellsManager::MergeViewCells(const VssRayContainer &rays,
+                                                                                        const ObjectContainer &objects)
+{
+    int vcSize = 0;
+        int pvsSize = 0;
+        //-- merge view cells
+        cout << "starting merge using " << mPostProcessSamples << " samples ... " << endl;
+        long startTime = GetTime();
+        if (mMergeViewCells)
+        {
+                // TODO: should be done BEFORE the ray casting
+                // compute tree by merging the nodes based on cost heuristics
+                mViewCellsTree->ConstructMergeTree(rays, objects);
+        }
+        else
+        {
+                // compute tree by merging the nodes of the spatial hierarchy
+                ViewCell *root = ConstructSpatialMergeTree(mVspBspTree->GetRoot());
+                mViewCellsTree->SetRoot(root);
+                // compute pvs
+                ObjectPvs pvs;
+                UpdatePvsForEvaluation(root, pvs);
+        }
+        if (1)
+        {
+                char mstats[100];
+                ObjectPvs pvs;
+                Environment::GetSingleton()->GetStringValue("ViewCells.mergeStats", mstats);
+                mViewCellsTree->ExportStats(mstats);
+        }
+        //-- 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.wrl");
+                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.wrl");
+                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
+        int minPvs, maxPvs;
+        if (0)
+        {
+                minPvs = mMinPvsSize;
+                maxPvs = mMaxPvsSize;
+        }
+        else
+        {
+                minPvs = mPruneEmptyViewCells ? 1 : 0;
+                maxPvs = mMaxPvsSize;
+        }
+        Debug << "setting validity, min: " << minPvs << " max: " << maxPvs << endl;
+        cout << "setting validity, min: " << minPvs << " max: " << maxPvs << endl;
+        SetValidity(minPvs, maxPvs);
+        // update valid view space according to valid view cells
+        if (0) mVspBspTree->ValidateTree();
+        // area has to be recomputed
+        mTotalAreaValid = false;
+        VssRayContainer postProcessRays;
+        GetRaySets(rays, mPostProcessSamples, postProcessRays);
+        Debug << "post processing using " << (int)postProcessRays.size() << " samples" << endl;
+        // 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 debugging purpose: test if the subdivision is valid
+        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->SetViewCellsStorage(ViewCellsTree::COMPRESSED);
+                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();
+        // compute final meshes and volume / area
+        if (1) FinalizeViewCells(true);
+        // write view cells to disc
+        if (mExportViewCells)
+        {
+                char filename[100];
+                Environment::GetSingleton()->GetStringValue("ViewCells.filename", filename);
+                ExportViewCells(filename, mExportPvs, objects);
+        }
+        // export bounding boxes
+        if (mExportBboxesForPvs)
+        {
+                char filename[100];
+                Environment::GetSingleton()->GetStringValue("ViewCells.boxesFilename", filename);
+                ExportBoundingBoxes(filename, objects);
+        }
+        return 0;
+}
+int VspBspViewCellsManager::GetType() const
+{
+        return VSP_BSP;
+}
+ViewCell *VspBspViewCellsManager::ConstructSpatialMergeTree(BspNode *root)
+{
+        // terminate recursion
+        if (root->IsLeaf())
+        {
+                BspLeaf *leaf = dynamic_cast<BspLeaf *>(root);
+                leaf->GetViewCell()->SetMergeCost(0.0f);
+                return leaf->GetViewCell();
+        }
+        BspInterior *interior = dynamic_cast<BspInterior *>(root);
+        ViewCellInterior *viewCellInterior = new ViewCellInterior();
+        // evaluate merge cost for priority traversal
+        float mergeCost = 1.0f / (float)root->mTimeStamp;
+        viewCellInterior->SetMergeCost(mergeCost);
+        float volume = 0;
+        BspNode *front = interior->GetFront();
+        BspNode *back = interior->GetBack();
+        ObjectPvs frontPvs, backPvs;
+        //-- recursivly compute child hierarchies
+        ViewCell *backVc = ConstructSpatialMergeTree(back);
+        ViewCell *frontVc = ConstructSpatialMergeTree(front);
+        viewCellInterior->SetupChildLink(backVc);
+        viewCellInterior->SetupChildLink(frontVc);
+        volume += backVc->GetVolume();
+        volume += frontVc->GetVolume();
+        viewCellInterior->SetVolume(volume);
+        return viewCellInterior;
+}
+void VspBspViewCellsManager::UpdatePvsForEvaluation(ViewCell *root, ObjectPvs &pvs)
+{
+        // terminate traversal
+        if (root->IsLeaf())
+        {
+                pvs = root->GetPvs();
+                SetScalarPvsSize(root, root->GetPvs().GetSize());
+                return;
+        }
+        //-- interior node => propagate pvs up
+        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(root);
+        interior->GetPvs().Clear();
+        pvs.Clear();
+        vector<ObjectPvs> pvsList;
+        ViewCellContainer::const_iterator vit, vit_end = interior->mChildren.end();
+        for (vit = interior->mChildren.begin(); vit != vit_end; ++ vit)
+        {
+                ObjectPvs objPvs;
+                //-- recursivly compute child pvss
+                UpdatePvsForEvaluation(*vit, objPvs);
+                // store pvs in vector
+                pvsList.push_back(objPvs);
+        }
+#if 1
+        Intersectable::NewMail();
+        //-- faster way of computing pvs:
+        //   construct merged pvs by adding
+        //   and only those of the next pvs which were not mailed.
+        //   note: sumpdf is not correct!!
+        vector<ObjectPvs>::iterator oit = pvsList.begin();
+        for (vit = interior->mChildren.begin(); vit != vit_end; ++ vit, ++ oit)
+        {
+            ObjectPvsMap::iterator pit, pit_end = (*oit).mEntries.end();
+                for (pit = (*oit).mEntries.begin(); pit != pit_end; ++ pit)
+                {
+                        Intersectable *intersect = (*pit).first;
+                        if (!intersect->Mailed())
+                        {
+                                pvs.AddSample(intersect, (*pit).second.mSumPdf);
+                                intersect->Mail();
+                        }
+                }
+        }
+        // store pvs in this node
+        if (mViewCellsTree->ViewCellsStorage() == ViewCellsTree::PVS_IN_INTERIORS)
+        {
+                interior->SetPvs(pvs);
+        }
+        // set new pvs size
+        SetScalarPvsSize(interior, pvs.GetSize());
+#else
+        // really merge cells: slow but sumpdf is correct
+        viewCellInterior->GetPvs().Merge(backVc->GetPvs());
+        viewCellInterior->GetPvs().Merge(frontVc->GetPvs());
+#endif
+}
+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);
+        //-- export view cells
+        if (1)
+        {       // hack pvs
+                const int savedColorCode = mColorCode;
+                mColorCode = 1;
+                Exporter *exporter = Exporter::GetExporter("final_view_cells.wrl");
+                if (exporter)
+                {
+                        cout << "exporting view cells after post process ... ";
+                        if (0)
+                        {
+                                // export view space box
+                                exporter->SetWireframe();
+                                exporter->ExportBox(mViewSpaceBox);
+                                exporter->SetFilled();
+                        }
+                        if (mExportGeometry)
+                        {
+                                exporter->ExportGeometry(objects);
+                        }
+                        // export rays
+                        if (1 && mExportRays)
+                        {
+                                exporter->ExportRays(visRays, RgbColor(0, 1, 0));
+                        }
+                        //exporter->SetFilled();
+                        // HACK: export without clip plane
+                        const bool b = mUseClipPlaneForViz;
+                        mUseClipPlaneForViz = false;
+                        ExportViewCellsForViz(exporter);
+                        mUseClipPlaneForViz = b;
+                        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::GetSingleton()->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)
+{
+        int leafOut;
+        Environment::GetSingleton()->GetIntValue("ViewCells.Visualization.maxOutput", leafOut);
+        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(), ViewCell::SmallerPvs);
+                stable_sort(mViewCells.begin(), mViewCells.end(), ViewCell::LargerRenderCost);
+        }
+        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)];
+                ObjectPvs pvs;
+                mViewCellsTree->GetPvs(vc, pvs);
+                //bspLeaves[j]->Mail();
+                char s[64]; sprintf(s, "bsp-pvs%04d.wrl", i);
+                Exporter *exporter = Exporter::GetExporter(s);
+                Debug << i << ": pvs size=" << (int)mViewCellsTree->GetPvsSize(vc) << endl;
+                //-- export the sample rays
+                if (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));
+                        }
+                }
+                //-- export view cell geometry
+                exporter->SetWireframe();
+                Material m;//= RandomMaterial();
+                m.mDiffuseColor = RgbColor(0, 1, 0);
+                exporter->SetForcedMaterial(m);
+                ExportViewCellGeometry(exporter, vc);
+                exporter->SetFilled();
+                //-- export pvs
+                if (1)
+                {
+                        ObjectPvsMap::const_iterator oit,
+                                oit_end = pvs.mEntries.end();
+                        Intersectable::NewMail();
+                        // output PVS of view cell
+                        for (oit = pvs.mEntries.begin(); oit != oit_end; ++ oit)
+                        {
+                                Intersectable *intersect = (*oit).first;
+                                if (!intersect->Mailed())
+                                {
+                                        m = RandomMaterial();
+                                        exporter->SetForcedMaterial(m);
+                                        exporter->ExportIntersectable(intersect);
+                                        intersect->Mail();
+                                }
+                        }
+                }
+                if (0)
+                {   // export scene geometry
+                        m.mDiffuseColor = RgbColor(1, 0, 0);
+                        exporter->SetForcedMaterial(m);
+                        exporter->ExportGeometry(objects);
+                }
+                DEL_PTR(exporter);
+                cout << "finished" << endl;
+        }
+        Debug << endl;
+}
+void VspBspViewCellsManager::TestFilter(const ObjectContainer &objects)
+{
+        Exporter *exporter = Exporter::GetExporter("filter.x3d");
+        Vector3 bsize = mViewSpaceBox.Size();
+        const Vector3 viewPoint(mViewSpaceBox.Center());
+        float w = Magnitude(mViewSpaceBox.Size()) * mFilterWidth;
+        const Vector3 width = Vector3(w);
+        PrVs testPrVs;
+        if (exporter)
+        {
+                ViewCellContainer viewCells;
+        const AxisAlignedBox3 tbox = GetFilterBBox(viewPoint, mFilterWidth);
+                GetPrVS(viewPoint, testPrVs, GetFilterWidth());
+                exporter->SetWireframe();
+                exporter->SetForcedMaterial(RgbColor(1,1,1));
+                exporter->ExportBox(tbox);
+                exporter->SetFilled();
+                exporter->SetForcedMaterial(RgbColor(0,1,0));
+                ExportViewCellGeometry(exporter, GetViewCell(viewPoint));
+                //exporter->ResetForcedMaterial();
+                exporter->SetForcedMaterial(RgbColor(0,0,1));
+                ExportViewCellGeometry(exporter, testPrVs.mViewCell);
+        exporter->SetForcedMaterial(RgbColor(1,0,0));
+                exporter->ExportGeometry(objects);
+                delete exporter;
+        }
+}
+int VspBspViewCellsManager::ComputeBoxIntersections(const AxisAlignedBox3 &box,
+                                                                                                        ViewCellContainer &viewCells) const
+{
+        return mVspBspTree->ComputeBoxIntersections(box, viewCells);
+}
+int VspBspViewCellsManager::CastLineSegment(const Vector3 &origin,
+                                                                                        const Vector3 &termination,
+                                                                                        ViewCellContainer &viewcells)
+{
+        return mVspBspTree->CastLineSegment(origin, termination, viewcells);
+}
 …
 ViewCell *VspBspViewCellsManager::GetViewCell(const Vector3 &point, const bool active) const
+{
         if (!mVspBspTree)
+        if (!ViewCellsConstructed())
                 return NULL;
 …
+}
+void
+ViewCellsManager::ApplySpatialFilter(
+                                                                         KdTree *kdTree,
+                                                                         const float spatialFilterSize,
+                                                                         ObjectPvs &pvs
+                                                                         )
+{
+  // now compute a new Pvs by including also objects intersecting the extended boxes of
+  // visible objects
+  Intersectable::NewMail();
+/**************************************************************************/
+/*                   VspBspViewCellsManager implementation                */
+/**************************************************************************/
+VspOspViewCellsManager::VspOspViewCellsManager(VspTree *vspTree, OspTree *ospTree):
+ViewCellsManager(), mVspTree(vspTree), mOspTree(ospTree)
+{
+        Environment::GetSingleton()->GetIntValue("VspBspTree.Construction.samples", mInitialSamples);
+        mVspTree->SetViewCellsManager(this);
+        mVspTree->mViewCellsTree = mViewCellsTree;
+}
+VspOspViewCellsManager::~VspOspViewCellsManager()
+{
+}
+float VspOspViewCellsManager::GetProbability(ViewCell *viewCell)
+{
+        return GetVolume(viewCell) / mViewSpaceBox.GetVolume();
+}
+void VspOspViewCellsManager::CollectViewCells()
+{
+        // view cells tree constructed
+        if (!ViewCellsTreeConstructed())
+        {
+                mVspTree->CollectViewCells(mViewCells, false);
+        }
+        else
+        {       // we can use the view cells tree hierarchy to get the right set
+                mViewCellsTree->CollectBestViewCellSet(mViewCells, mNumActiveViewCells);
+        }
+}
+bool VspOspViewCellsManager::ViewCellsConstructed() const
+{
+        return mVspTree->GetRoot() != NULL;
+}
+ViewCell *VspOspViewCellsManager::GenerateViewCell(Mesh *mesh) const
+{
+        return new VspViewCell(mesh);
+}
+int VspOspViewCellsManager::ConstructSubdivision(const ObjectContainer &objects,
+                                                                                                 const VssRayContainer &rays)
+{
+        mMaxPvsSize = (int)(mMaxPvsRatio * (float)objects.size());
+        // 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;
+        long startTime;
+#if TODO
+        if (1)
+                mVspTree->Construct(constructionRays, &mViewSpaceBox);
+        else
+                mVspTree->Construct(rays, &mViewSpaceBox);
+#endif
+        // collapse invalid regions
+        cout << "collapsing invalid tree regions ... ";
+        startTime = GetTime();
+        const int collapsedLeaves = mVspTree->CollapseTree();
+        Debug << "collapsed in " << TimeDiff(startTime, GetTime()) * 1e-3
+                  << " seconds" << endl;
+    cout << "finished" << endl;
+        //-- stats
+        Debug << mVspTree->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;
+        // real meshes are contructed at this stage
+        if (0)
+        {
+                cout << "finalizing view cells ... ";
+                FinalizeViewCells(true);
+                cout << "finished" << endl;
+        }
+        return sampleContributions;
+}
+int VspOspViewCellsManager::PostProcess(const ObjectContainer &objects,
+                                                                                const VssRayContainer &rays)
+{
+        if (!ViewCellsConstructed())
+        {
+                Debug << "postprocess error: no view cells constructed" << endl;
+                return 0;
+        }
+        // view cells already finished before post processing step
+        // (i.e. because they were loaded)
+        if (mViewCellsFinished)
+        {
+                FinalizeViewCells(true);
+                EvaluateViewCellsStats();
+                return 0;
+        }
+        // check if new view cells turned invalid
+        int minPvs, maxPvs;
+        if (0)
+        {
+                minPvs = mMinPvsSize;
+                maxPvs = mMaxPvsSize;
+        }
+        else
+        {
+                minPvs = mPruneEmptyViewCells ? 1 : 0;
+                maxPvs = mMaxPvsSize;
+        }
+        Debug << "setting validity, min: " << minPvs << " max: " << maxPvs << endl;
+        cout << "setting validity, min: " << minPvs << " max: " << maxPvs << endl;
+        SetValidity(minPvs, maxPvs);
+        // area 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);
+        // compute tree by merging the nodes of the spatial hierarchy
+        ViewCell *root = ConstructSpatialMergeTree(mVspTree->GetRoot());
+        mViewCellsTree->SetRoot(root);
+        // compute pvs
+        ObjectPvs pvs;
+        UpdatePvsForEvaluation(root, pvs);
+        //-- 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);
+  std::map<Intersectable *,
+        PvsData<Intersectable *>,
+        LtSample<Intersectable *> >::const_iterator oi;
+  for (oi = pvs.mEntries.begin(); oi != pvs.mEntries.end(); ++oi) {
+        Intersectable *object = (*oi).first;
+        object->Mail();
+  }
+  ObjectPvs nPvs;
+  int nPvsSize=0;
+  // now go through the pvs again
+  for (oi = pvs.mEntries.begin(); oi != pvs.mEntries.end(); ++oi) {
+        Intersectable *object = (*oi).first;
+        //      Vector3 center = object->GetBox().Center();
+        //      AxisAlignedBox3 box(center - Vector3(spatialFilterSize/2),
+        //                                              center + Vector3(spatialFilterSize/2));
+        AxisAlignedBox3 box = object->GetBox();
+        box.Enlarge(Vector3(spatialFilterSize/2));
+        ObjectContainer objects;
+        // $$ warning collect objects takes only unmailed ones!
+        kdTree->CollectObjects(box,
+                                                   objects);
+        //      cout<<"collected objects="<<objects.size()<<endl;
+        ObjectContainer::const_iterator noi = objects.begin();
+        for (; noi != objects.end(); ++noi) {
+          Intersectable *o = *noi;
+          // $$ JB warning: pdfs are not correct at this point!
+          nPvs.AddSample(o, Limits::Small);
+          nPvsSize++;
+        }
+  }
+  //  cout<<"nPvs size = "<<nPvsSize<<endl;
+  pvs.Merge(nPvs);
+}
+void
+ViewCellsManager::ApplyFilter(ViewCell *viewCell,
+                                                          KdTree *kdTree,
+                                                          const float viewSpaceFilterSize,
+                                                          const float spatialFilterSize,
+                                                          ObjectPvs &pvs
+                                                          )
+{
+  // extend the pvs of the viewcell by pvs of its neighbors
+  // and apply spatial filter by including all neighbors of the objects
+  // in the pvs
+  // get all viewcells intersecting the viewSpaceFilterBox
+  // and compute the pvs union
+  //Vector3 center = viewCell->GetBox().Center();
+  //  Vector3 center = m->mBox.Center();
+  //  AxisAlignedBox3 box(center - Vector3(viewSpaceFilterSize/2),
+  //                                      center + Vector3(viewSpaceFilterSize/2));
+        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->SetViewCellsStorage(ViewCellsTree::COMPRESSED);
+                pvsEntries = mViewCellsTree->GetNumPvsEntries(mViewCellsTree->GetRoot());
+                Debug << "number of entries after compress: " << pvsEntries << endl;
+        }
+        // compute final meshes and volume / area
+        if (1) FinalizeViewCells(true);
+        // write view cells to disc
+        if (mExportViewCells)
+        {
+                char filename[100];
+                Environment::GetSingleton()->GetStringValue("ViewCells.filename", filename);
+                ExportViewCells(filename, mExportPvs, objects);
+        }
+        return 0;
+}
+int VspOspViewCellsManager::GetType() const
+{
+        return VSP_OSP;
+}
+ViewCell *VspOspViewCellsManager::ConstructSpatialMergeTree(VspNode *root)
+{
+        // terminate recursion
+        if (root->IsLeaf())
+        {
+                VspLeaf *leaf = dynamic_cast<VspLeaf *>(root);
+                leaf->GetViewCell()->SetMergeCost(0.0f);
+                return leaf->GetViewCell();
+        }
+        VspInterior *interior = dynamic_cast<VspInterior *>(root);
+        ViewCellInterior *viewCellInterior = new ViewCellInterior();
+        // evaluate merge cost for priority traversal
+        float mergeCost = 1.0f / (float)root->mTimeStamp;
+        viewCellInterior->SetMergeCost(mergeCost);
+        float volume = 0;
+        VspNode *front = interior->GetFront();
+        VspNode *back = interior->GetBack();
+        ObjectPvs frontPvs, backPvs;
+        //-- recursivly compute child hierarchies
+        ViewCell *backVc = ConstructSpatialMergeTree(back);
+        ViewCell *frontVc = ConstructSpatialMergeTree(front);
+        viewCellInterior->SetupChildLink(backVc);
+        viewCellInterior->SetupChildLink(frontVc);
+        volume += backVc->GetVolume();
+        volume += frontVc->GetVolume();
+        viewCellInterior->SetVolume(volume);
+        return viewCellInterior;
+}
+void VspOspViewCellsManager::UpdatePvsForEvaluation(ViewCell *root, ObjectPvs &pvs)
+{
+        // terminate traversal
+        if (root->IsLeaf())
+        {
+                pvs = root->GetPvs();
+                SetScalarPvsSize(root, root->GetPvs().GetSize());
+                return;
+        }
+        //-- interior node => propagate pvs up
+        ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(root);
+        interior->GetPvs().Clear();
+        pvs.Clear();
+        vector<ObjectPvs> pvsList;
+        ViewCellContainer::const_iterator vit, vit_end = interior->mChildren.end();
+        for (vit = interior->mChildren.begin(); vit != vit_end; ++ vit)
+        {
+                ObjectPvs objPvs;
+                //-- recursivly compute child pvss
+                UpdatePvsForEvaluation(*vit, objPvs);
+                // store pvs in vector
+                pvsList.push_back(objPvs);
+        }
+#if 1
+        Intersectable::NewMail();
+        //-- faster way of computing pvs:
+        //   construct merged pvs by adding
+        //   and only those of the next pvs which were not mailed.
+        //   note: sumpdf is not correct!!
+        vector<ObjectPvs>::iterator oit = pvsList.begin();
+        for (vit = interior->mChildren.begin(); vit != vit_end; ++ vit, ++ oit)
+        {
+            ObjectPvsMap::iterator pit, pit_end = (*oit).mEntries.end();
+                for (pit = (*oit).mEntries.begin(); pit != pit_end; ++ pit)
+                {
+                        Intersectable *intersect = (*pit).first;
+                        if (!intersect->Mailed())
+                        {
+                                pvs.AddSample(intersect, (*pit).second.mSumPdf);
+                                intersect->Mail();
+                        }
+                }
+        }
+        // store pvs in this node
+        if (mViewCellsTree->ViewCellsStorage() == ViewCellsTree::PVS_IN_INTERIORS)
+        {
+                interior->SetPvs(pvs);
+        }
+        // set new pvs size
+        SetScalarPvsSize(interior, pvs.GetSize());
+#else
+        // really merge cells: slow put sumpdf is correct
+        viewCellInterior->GetPvs().Merge(backVc->GetPvs());
+        viewCellInterior->GetPvs().Merge(frontVc->GetPvs());
+#endif
+}
+bool VspOspViewCellsManager::GetViewPoint(Vector3 &viewPoint) const
+{
+        if (!ViewCellsConstructed())
+                return ViewCellsManager::GetViewPoint(viewPoint);
+        // TODO: set reasonable limit
+        const int limit = 20;
+        for (int i = 0; i < limit; ++ i)
+        {
+                viewPoint = mViewSpaceBox.GetRandomPoint();
+                if (mVspTree->ViewPointValid(viewPoint))
+                {
+                        return true;
+                }
+        }
+        Debug << "failed to find valid view point, taking " << viewPoint << endl;
+        return false;
+}
+bool VspOspViewCellsManager::ViewPointValid(const Vector3 &viewPoint) const
+{
+  // $$JB -> implemented in viewcellsmanager (slower, but allows dynamic
+  // validy update in preprocessor for all managers)
+  return ViewCellsManager::ViewPointValid(viewPoint);
+  //    return mViewSpaceBox.IsInside(viewPoint) &&
+  //               mVspBspTree->ViewPointValid(viewPoint);
+}
+void VspOspViewCellsManager::Visualize(const ObjectContainer &objects,
+                                                                           const VssRayContainer &sampleRays)
+{
         if (!ViewCellsConstructed())
                 return;
+        if (viewSpaceFilterSize >= 0.0f) {
+  bool usePrVS = false;
+  if (!usePrVS) {
+        AxisAlignedBox3 box = GetViewCellBox(viewCell);
+        box.Enlarge(Vector3(viewSpaceFilterSize/2));
+        ViewCellContainer viewCells;
+        ComputeBoxIntersections(box, viewCells);
+  //  cout<<"box="<<box<<endl;
+        ViewCellContainer::const_iterator it = viewCells.begin(), it_end = viewCells.end();
+        int i;
+        for (i=0; it != it_end; ++ it, ++ i) {
+                //cout<<"v"<<i<<" pvs="<<(*it)->GetPvs().mEntries.size()<<endl;
+          pvs.Merge((*it)->GetPvs());
+        }
+  } else {
+        PrVs prvs;
+        AxisAlignedBox3 box = GetViewCellBox(viewCell);
+        //  mViewCellsManager->SetMaxFilterSize(1);
+        GetPrVS(box.Center(), prvs, viewSpaceFilterSize);
+        pvs = prvs.mViewCell->GetPvs();
+        DeleteLocalMergeTree(prvs.mViewCell);
+  }
+  } else
+        pvs = viewCell->GetPvs();
+  if (spatialFilterSize >=0.0f)
+        ApplySpatialFilter(kdTree, spatialFilterSize, pvs);
+}
+void
+ViewCellsManager::ApplyFilter(KdTree *kdTree,
+                                                          const float relViewSpaceFilterSize,
+                                                          const float relSpatialFilterSize
+                                                          )
+{
+#if TODO
+        VssRayContainer visRays;
+        GetRaySets(sampleRays, mVisualizationSamples, visRays);
+        //-- export view cells
+        if (1)
+        {       // hack pvs
+                const int savedColorCode = mColorCode;
+                mColorCode = 1;
+                Exporter *exporter = Exporter::GetExporter("final_view_cells.wrl");
+                if (exporter)
+                {
+                        cout << "exporting view cells after post process ... ";
+                        if (0)
+                        {
+                                // export view space box
+                                exporter->SetWireframe();
+                                exporter->ExportBox(mViewSpaceBox);
+                                exporter->SetFilled();
+                        }
+                        if (mExportGeometry)
+                        {
+                                exporter->ExportGeometry(objects);
+                        }
+                        // export rays
+                        if (1 && mExportRays)
+                        {
+                                exporter->ExportRays(visRays, RgbColor(0, 1, 0));
+                        }
+                        //exporter->SetFilled();
+                        // HACK: export without clip plane
+                        const bool b = mUseClipPlaneForViz;
+                        mUseClipPlaneForViz = false;
+                        ExportViewCellsForViz(exporter);
+                        mUseClipPlaneForViz = b;
+                        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::GetSingleton()->GetBoolValue("VspBspTree.Visualization.exportSplits", exportSplits);
+        if (exportSplits)
+        {
+                cout << "exporting splits ... ";
+                ExportSplits(objects, visRays);
+                cout << "finished" << endl;
+        }
+        //-- export single view cells
+        ExportBspPvs(objects, visRays);
+#endif
+}
+void VspOspViewCellsManager::ExportBspPvs(const ObjectContainer &objects,
+                                                                                  const VssRayContainer &rays)
+{
+        int leafOut;
+        Environment::GetSingleton()->GetIntValue("ViewCells.Visualization.maxOutput", leafOut);
+        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(), ViewCell::SmallerPvs);
+                stable_sort(mViewCells.begin(), mViewCells.end(), ViewCell::LargerRenderCost);
+        }
+        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)];
+                ObjectPvs pvs;
+                mViewCellsTree->GetPvs(vc, pvs);
+                //bspLeaves[j]->Mail();
+                char s[64]; sprintf(s, "bsp-pvs%04d.wrl", i);
+                Exporter *exporter = Exporter::GetExporter(s);
+                Debug << i << ": pvs size=" << (int)mViewCellsTree->GetPvsSize(vc) << endl;
+                //-- export the sample rays
+                if (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));
+                        }
+                }
+                //-- export view cell geometry
+                exporter->SetWireframe();
+                Material m;//= RandomMaterial();
+                m.mDiffuseColor = RgbColor(0, 1, 0);
+                exporter->SetForcedMaterial(m);
+                ExportViewCellGeometry(exporter, vc);
+                exporter->SetFilled();
+                //-- export pvs
+                if (1)
+                {
+                        ObjectPvsMap::const_iterator oit,
+                                oit_end = pvs.mEntries.end();
+                        Intersectable::NewMail();
+                        // output PVS of view cell
+                        for (oit = pvs.mEntries.begin(); oit != oit_end; ++ oit)
+                        {
+                                Intersectable *intersect = (*oit).first;
+                                if (!intersect->Mailed())
+                                {
+                                        m = RandomMaterial();
+                                        exporter->SetForcedMaterial(m);
+                                        exporter->ExportIntersectable(intersect);
+                                        intersect->Mail();
+                                }
+                        }
+                }
+                if (0)
+                {   // export scene geometry
+                        m.mDiffuseColor = RgbColor(1, 0, 0);
+                        exporter->SetForcedMaterial(m);
+                        exporter->ExportGeometry(objects);
+                }
+                DEL_PTR(exporter);
+                cout << "finished" << endl;
+        }
+        Debug << endl;
+}
+int VspOspViewCellsManager::ComputeBoxIntersections(const AxisAlignedBox3 &box,
+                                                                                                        ViewCellContainer &viewCells) const
+{
+        return mVspTree->ComputeBoxIntersections(box, viewCells);
+}
+int VspOspViewCellsManager::CastLineSegment(const Vector3 &origin,
+                                                                                        const Vector3 &termination,
+                                                                                        ViewCellContainer &viewcells)
+{
+        return mVspTree->CastLineSegment(origin, termination, viewcells);
+}
+void VspOspViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
+                                                    ViewCell *vc,
+                                                                                                        const Plane3 *clipPlane) const
+{
+        // matt: TODO
+}
+bool VspOspViewCellsManager::ExportViewCells(const string filename,
+                                                                                         const bool exportPvs,
+                                                                                         const ObjectContainer &objects)
+{
+        if (!ViewCellsConstructed() || !ViewCellsTreeConstructed())
+                return false;
+        cout << "exporting view cells to xml ... ";
+#if ZIPPED_VIEWCELLS
+        ogzstream stream(filename.c_str());
+#else
+        std::ofstream stream(filename.c_str());
+#endif
+        // for output we need unique ids for each view cell
+        CreateUniqueViewCellIds();
+        stream << "<?xml version=\"1.0\" encoding=\"UTF-8\"?>"<<endl;
+        stream << "<VisibilitySolution>" << 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;
+        //-- export bounding boxes
+        stream << "<BoundingBoxes>" << endl;
+        ObjectContainer::const_iterator oit, oit_end = objects.end();
+        for (oit = objects.begin(); oit != oit_end; ++ oit)
+        {
+                        MeshInstance *mi = dynamic_cast<MeshInstance *>(*oit);
+                        const AxisAlignedBox3 box = mi->GetBox();
+                        //-- the bounding boxes
+                        stream << "<BoundingBox" << " id=\"" << mi->GetId() << "\""
+                                   << " min=\"" << box.Min().x << " " << box.Min().y << " " << box.Min().z << "\""
+                                   << " max=\"" << box.Max().x << " " << box.Max().y << " " << box.Max().z << "\" />" << endl;
+        }
+        stream << "</BoundingBoxes>" << endl;
+        //-- export the view cells and the pvs
+        stream << "<HierarchyType name=\"vspBspTree\" />" << endl;
+        const int numViewCells = mCurrentViewCellsStats.viewCells;
+        stream << "<ViewCells number=\"" << numViewCells << "\" >" << endl;
+        mViewCellsTree->Export(stream, exportPvs);
+        stream << "</ViewCells>" << endl;
+        //-- export the spatial hierarchy
+        // the type of the view cells hierarchy
+        stream << "<Hierarchy>" << endl;
+        mVspTree->Export(stream);
+        stream << endl << "</Hierarchy>" << endl;
+        stream << "</VisibilitySolution>" << endl;
+        stream.close();
+        cout << "finished" << endl;
+        return true;
+}
+ViewCell *VspOspViewCellsManager::GetViewCell(const Vector3 &point, const bool active) const
+{
         if (!ViewCellsConstructed())
+                return;
+  ViewCellContainer::const_iterator it, it_end = mViewCells.end();
+  ObjectPvs *newPvs;
+  newPvs = new ObjectPvs[mViewCells.size()];
+  float viewSpaceFilterSize = Magnitude(mViewSpaceBox.Size())*relViewSpaceFilterSize;
+  float spatialFilterSize = Magnitude(kdTree->GetBox().Size())*relSpatialFilterSize;
+  int i;
+  for (i=0, it = mViewCells.begin(); it != it_end; ++ it, ++ i) {
+        ApplyFilter(*it,
+                                kdTree,
+                                viewSpaceFilterSize,
+                                spatialFilterSize,
+                                newPvs[i]
+                                );
+  }
+  // now replace all pvss
+  for (i = 0, it = mViewCells.begin(); it != it_end; ++ it, ++ i) {
+        ObjectPvs &pvs = (*it)->GetPvs();
+        pvs.Clear();
+        pvs = newPvs[i];
+        newPvs[i].Clear();
+  }
+  delete [] newPvs;
+}
+void VspBspViewCellsManager::TestFilter(const ObjectContainer &objects)
+{
+        Exporter *exporter = Exporter::GetExporter("filter.x3d");
+        Vector3 bsize = mViewSpaceBox.Size();
+        const Vector3 viewPoint(mViewSpaceBox.Center());
+        float w = Magnitude(mViewSpaceBox.Size()) * mFilterWidth;
+        const Vector3 width = Vector3(w);
+        PrVs testPrVs;
+        if (exporter)
+        {
+                ViewCellContainer viewCells;
+        const AxisAlignedBox3 tbox = GetFilterBBox(viewPoint, mFilterWidth);
+                GetPrVS(viewPoint, testPrVs, GetFilterWidth());
+                exporter->SetWireframe();
+                exporter->SetForcedMaterial(RgbColor(1,1,1));
+                exporter->ExportBox(tbox);
+                exporter->SetFilled();
+                exporter->SetForcedMaterial(RgbColor(0,1,0));
+                ExportViewCellGeometry(exporter, GetViewCell(viewPoint));
+                //exporter->ResetForcedMaterial();
+                exporter->SetForcedMaterial(RgbColor(0,0,1));
+                ExportViewCellGeometry(exporter, testPrVs.mViewCell);
+        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;
+                return NULL;
+        if (!mViewSpaceBox.IsInside(point))
+          return NULL;
+        return mVspTree->GetViewCell(point, active);
+}
+void VspOspViewCellsManager::CreateMesh(ViewCell *vc)
+{
+        // matt: TODO
+        Mesh *mesh = MeshManager::GetSingleton()->CreateResource();
+        vc->SetMesh(mesh);
+}
+int VspOspViewCellsManager::CastBeam(Beam &beam)
+{
+        // matt: TODO
+        return 0;
+}
+void VspOspViewCellsManager::Finalize(ViewCell *viewCell,
+                                                                          const bool createMesh)
+{
+#if TODO
+        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);
+                const float lVol = geom.GetVolume();
+                const float lArea = geom.GetArea();
+                //(*it)->SetVolume(vol);
+                //(*it)->SetArea(area);
+                area += lArea;
+                volume += lVol;
+        CreateMesh(*it);
+        }
+        viewCell->SetVolume(volume);
+        viewCell->SetArea(area);
+#endif
+}
+void VspOspViewCellsManager::PrepareLoadedViewCells()
+{
+        // TODO
+}

GTP/trunk/Lib/Vis/Preprocessing/src/ViewCellsManager.h

-                      r1006
+                      r1021
 class MergeCandidate;
 class BoundingBoxConverter;
+class VspTree;
+class OspTree;
+class VspNode;
 …
         /// view cell container types
         enum {BSP, KD, VSP_KD, VSP_BSP};
+        enum {BSP, KD, VSP_KD, VSP_BSP, VSP_OSP};
         /// render cost evaluation type
 …
         void CollectViewCells(const int n);
-        /** Returns true if this (logical) view cell is equal to a spatial node.
-        */
-        virtual bool EqualToSpatialNode(ViewCell *viewCell) const;
         /** Sets current view cells set to active, i.e., the sampling is done in this view cell set.
         */
 …
+        /** Returns true if this view cell is equivalent to a node of the spatial hierarchy.
+        */
+        virtual bool EqualToSpatialNode(ViewCell *viewCell) const;
 protected:
         /** Exports bounding boxes as xml stream
 …
         /** Sets exporter color.
         */
         virtual void ExportColor(Exporter *exporter, ViewCell *vc) const = 0;
+        virtual void ExportColor(Exporter *exporter, ViewCell *vc) const;
         /** Returns volume of the view space.
 …
         /// if rays should be used to collect merge candidates
         bool mUseRaysForMerge;
         /// if there should be an additional merge step after the subdivision
         bool mMergeViewCells;
 …
 protected:
         void CollectViewCells();
-        void ExportColor(Exporter *exporter, ViewCell *vc) const;
         /// the BSP tree.
 …
         KdNode *GetNodeForPvs(KdLeaf *leaf);
-        void ExportColor(Exporter *exporter, ViewCell *vc) const;
         /// the BSP tree.
 …
         BspNode *GetSpatialNode(ViewCell *viewCell) const;
         /** Merges the view cells.
+        /** Merges view cells according to some criteria
         */
         void MergeViewCells(const VssRayContainer &rays,
 …
-        void ExportColor(Exporter *exporter, ViewCell *vc) const;
         /** Prepare view cells for use after loading them from disc.
         */
 …
         void EvalFromPointQueries();
+        /** Exports visualization of the BSP splits.
+        */
+        void ExportSplits(const ObjectContainer &objects,
+                                          const VssRayContainer &rays);
+        /** Exports visualization of the BSP PVS.
+        */
+        void ExportBspPvs(const ObjectContainer &objects,
+                                          const VssRayContainer &rays);
         /// the view space partition BSP tree.
 …
 private:
+        /** Exports visualization of the BSP splits.
+        */
+        void ExportSplits(const ObjectContainer &objects,
+                                          const VssRayContainer &rays);
+        /** test if subdivision is valid in terms of volume / area.
+        */
+        void TestSubdivision();
+};
+/**
+        Manages different higher order operations on the view cells.
+*/
+class VspOspViewCellsManager: public ViewCellsManager
+{
+public:
+        VspOspViewCellsManager(VspTree *tree, OspTree *ospTree);
+        ~VspOspViewCellsManager();
+        int ConstructSubdivision(const ObjectContainer &objects,
+                                                         const VssRayContainer &rays);
+        int PostProcess(const ObjectContainer &objects,
+                                        const VssRayContainer &rays);
+        void Visualize(const ObjectContainer &objects,
+                                   const VssRayContainer &sampleRays);
+        int GetType() const;
+        ViewCell *GenerateViewCell(Mesh *mesh = NULL) const;
+        bool ViewCellsConstructed() const;
+        int CastLineSegment(const Vector3 &origin,
+                                                const Vector3 &termination,
+                                                ViewCellContainer &viewcells);
+        float GetProbability(ViewCell *viewCell);
+        ViewCell *GetViewCell(const Vector3 &point, const bool active = false) const;
+        bool GetViewPoint(Vector3 &viewPoint) const;
+        bool ViewPointValid(const Vector3 &viewPoint) const;
+        void CreateMesh(ViewCell *vc);
+        bool ExportViewCells(const string filename, const bool exportPvs, const ObjectContainer &objects);
+        int CastBeam(Beam &beam);
+        void ExportViewCellGeometry(Exporter *exporter,
+                                                                ViewCell *vc,
+                                                                const Plane3 *clipPlane = NULL) const;
+        void Finalize(ViewCell *viewCell, const bool createMesh);
+protected:
+        int ComputeBoxIntersections(const AxisAlignedBox3 &box, ViewCellContainer &viewCells) const;
+        void CollectViewCells();
+        /** Prepare view cells for use after loading them from disc.
+        */
+        void PrepareLoadedViewCells();
+        /** Constructs merge hierarchy which corresponds to the spatial hierarchy.
+        */
+        ViewCell *ConstructSpatialMergeTree(VspNode *root);
+        void UpdatePvsForEvaluation(ViewCell *root, ObjectPvs &pvs);
         /** Exports visualization of the BSP PVS.
 …
                                           const VssRayContainer &rays);
+        /** test if subdivision is valid in terms of volume / area.
+        */
+        void TestSubdivision();
+        /// the view space partition tree.
+        VspTree *mVspTree;
+        OspTree *mOspTree;
 };

GTP/trunk/Lib/Vis/Preprocessing/src/VspOspTree.cpp

-                      r1020
+                      r1021
+void VspTreeStatistics::Print(ostream &app) const
+{
+#if TODO
+        app << "===== BspTree statistics ===============\n";
+        app << setprecision(4);
+        app << "#N_CTIME  ( Construction time [s] )\n" << Time() << " \n";
+        app << "#N_NODES ( Number of nodes )\n" << nodes << "\n";
+        app << "#N_INTERIORS ( Number of interior nodes )\n" << Interior() << "\n";
+        app << "#N_LEAVES ( Number of leaves )\n" << Leaves() << "\n";
+        app << "#N_POLYSPLITS ( Number of polygon splits )\n" << polySplits << "\n";
+        app << "#AXIS_ALIGNED_SPLITS (number of axis aligned splits)\n" << splits[0] + splits[1] + splits[2] << endl;
+        app << "#N_SPLITS ( Number of splits in axes x y z)\n";
+        for (int i = 0; i < 3; ++ i)
+                app << splits[i] << " ";
+        app << endl;
+        app << "#N_PMAXDEPTHLEAVES ( Percentage of leaves at maximum depth )\n"
+                <<      maxDepthNodes * 100 / (double)Leaves() << endl;
+        app << "#N_PMINPVSLEAVES  ( Percentage of leaves with mininimal PVS )\n"
+                << minPvsNodes * 100 / (double)Leaves() << endl;
+        app << "#N_PMINRAYSLEAVES  ( Percentage of leaves with minimal number of rays)\n"
+                << minRaysNodes * 100 / (double)Leaves() << endl;
+        app << "#N_MAXCOSTNODES  ( Percentage of leaves with terminated because of max cost ratio )\n"
+                << maxCostNodes * 100 / (double)Leaves() << endl;
+        app << "#N_PMINPROBABILITYLEAVES  ( Percentage of leaves with mininum probability )\n"
+                << minProbabilityNodes * 100 / (double)Leaves() << endl;
+        app << "#N_PMAXRAYCONTRIBLEAVES  ( Percentage of leaves with maximal ray contribution )\n"
+                <<      maxRayContribNodes * 100 / (double)Leaves() << endl;
+        app << "#N_PMAXDEPTH ( Maximal reached depth )\n" << maxDepth << endl;
+        app << "#N_PMINDEPTH ( Minimal reached depth )\n" << minDepth << endl;
+        app << "#AVGDEPTH ( average depth )\n" << AvgDepth() << endl;
+        app << "#N_INPUTPOLYGONS (number of input polygons )\n" << polys << endl;
+        app << "#N_INVALIDLEAVES (number of invalid leaves )\n" << invalidLeaves << endl;
+        app << "#N_RAYS (number of rays / leaf)\n" << AvgRays() << endl;
+        //app << "#N_PVS: " << pvs << endl;
+        app << "#N_ROUTPUT_INPUT_POLYGONS ( ratio polygons after subdivision / input polygons )\n" <<
+                 (polys + polySplits) / (double)polys << endl;
+        app << "===== END OF BspTree statistics ==========\n";
+#endif
+}
 /******************************************************************/
 /*                  class VspNode implementation                  */
 …
+}
 int VspLeaf::Type() const
+{
         return Leaf;
+}
 …
+void VspTree::SetViewCellsManager(ViewCellsManager *vcm)
+{
+        mViewCellsManager = vcm;
+}
 void VspTree::ValidateTree()
+{
 …
+int VspTree::ComputeBoxIntersections(const AxisAlignedBox3 &box,
+                                                                         ViewCellContainer &viewCells) const
+{
+#if TODO
+        stack<bspNodePair> nodeStack;
+        BspNodeGeometry *rgeom = new BspNodeGeometry();
+        ConstructGeometry(mRoot, *rgeom);
+        nodeStack.push(bspNodePair(mRoot, rgeom));
+        ViewCell::NewMail();
+        while (!nodeStack.empty())
+        {
+                BspNode *node = nodeStack.top().first;
+                BspNodeGeometry *geom = nodeStack.top().second;
+                nodeStack.pop();
+                const int side = geom->ComputeIntersection(box);
+                switch (side)
+                {
+                case -1:
+                        // node geometry is contained in box
+                        CollectViewCells(node, true, viewCells, true);
+                        break;
+                case 0:
+                        if (node->IsLeaf())
+                        {
+                                BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
+                                if (!leaf->GetViewCell()->Mailed() && leaf->TreeValid())
+                                {
+                                        leaf->GetViewCell()->Mail();
+                                        viewCells.push_back(leaf->GetViewCell());
+                                }
+                        }
+                        else
+                        {
+                                BspInterior *interior = dynamic_cast<BspInterior *>(node);
+                                BspNode *first = interior->GetFront();
+                                BspNode *second = interior->GetBack();
+                                BspNodeGeometry *firstGeom = new BspNodeGeometry();
+                                BspNodeGeometry *secondGeom = new BspNodeGeometry();
+                                geom->SplitGeometry(*firstGeom,
+                                                                        *secondGeom,
+                                                                        interior->GetPlane(),
+                                                                        mBox,
+                                                                        //0.0000001f);
+                                                                        mEpsilon);
+                                nodeStack.push(bspNodePair(first, firstGeom));
+                                nodeStack.push(bspNodePair(second, secondGeom));
+                        }
+                        break;
+                default:
+                        // default: cull
+                        break;
+                }
+                DEL_PTR(geom);
+        }
+#endif
+        return (int)viewCells.size();
+}
 /*****************************************************************/
 /*                class OpsTree implementation                   */
+/*                class OspTree implementation                   */
 /*****************************************************************/
 …
+/*****************************************************************/
+/*              class HierarchyManager implementation            */
+/*****************************************************************/
+bool OspTree::LocalTerminationCriteriaMet(const OspTraversalData &data) const
+{
+        // matt: TODO
+        return true;
+    /*          (((int)data.mRays->size() <= mTermMinRays) ||
+                 (data.mPvs <= mTermMinPvs)   ||
+                 (data.mProbability <= mTermMinProbability) ||
+                 (data.GetAvgRayContribution() > mTermMaxRayContribution) ||
+                 (data.mDepth >= mTermMaxDepth));*/
+}
+bool OspTree::GlobalTerminationCriteriaMet(const OspTraversalData &data) const
+{
+        // matt: TODO
+        return true;
+                /*(mOutOfMemory ||
+                (mVspStats.Leaves() >= mMaxViewCells) ||
+                (mGlobalCostMisses >= mTermGlobalCostMissTolerance));*/
+}
+void OspTree::EvaluateLeafStats(const OspTraversalData &data)
+{
+#if TODO
+        // the node became a leaf -> evaluate stats for leafs
+        VspLeaf *leaf = dynamic_cast<VspLeaf *>(data.mNode);
+        if (data.mPvs > mVspStats.maxPvs)
+        {
+                mVspStats.maxPvs = data.mPvs;
+        }
+        mVspStats.pvs += data.mPvs;
+        if (data.mDepth < mVspStats.minDepth)
+        {
+                mVspStats.minDepth = data.mDepth;
+        }
+        if (data.mDepth >= mTermMaxDepth)
+        {
+        ++ mVspStats.maxDepthNodes;
+                //Debug << "new max depth: " << mVspStats.maxDepthNodes << endl;
+        }
+        // accumulate rays to compute rays /  leaf
+        mVspStats.accumRays += (int)data.mRays->size();
+        if (data.mPvs < mTermMinPvs)
+                ++ mVspStats.minPvsNodes;
+        if ((int)data.mRays->size() < mTermMinRays)
+                ++ mVspStats.minRaysNodes;
+        if (data.GetAvgRayContribution() > mTermMaxRayContribution)
+                ++ mVspStats.maxRayContribNodes;
+        if (data.mProbability <= mTermMinProbability)
+                ++ mVspStats.minProbabilityNodes;
+        // accumulate depth to compute average depth
+        mVspStats.accumDepth += data.mDepth;
+        ++ mCreatedViewCells;
+#ifdef _DEBUG
+        Debug << "BSP stats: "
+                  << "Depth: " << data.mDepth << " (max: " << mTermMaxDepth << "), "
+                  << "PVS: " << data.mPvs << " (min: " << mTermMinPvs << "), "
+          //              << "Area: " << data.mProbability << " (min: " << mTermMinProbability << "), "
+                  << "#rays: " << (int)data.mRays->size() << " (max: " << mTermMinRays << "), "
+                  << "#pvs: " << leaf->GetViewCell()->GetPvs().GetSize() << "=, "
+                  << "#avg ray contrib (pvs): " << (float)data.mPvs / (float)data.mRays->size() << endl;
+#endif
+#endif
+}
+/*********************************************************************/
+/*                class HierarchyManager implementation              */
+/*********************************************************************/
 HierarchyManager::HierarchyManager()

GTP/trunk/Lib/Vis/Preprocessing/src/VspOspTree.h

-                      r1020
+                      r1021
         virtual bool IsLeaf() const = 0;
         virtual int Type() const;
+        virtual int Type() const = 0;
         /** Determines whether this node is a root
 …
         bool IsLeaf() const;
                 virtual int Type() const;
+        int Type() const;
         /** Returns pointer of view cell.

Note: See TracChangeset for help on using the changeset viewer.