Changeset 1571

Timestamp:

10/05/06 11:15:50 (18 years ago)

Author:

mattausch

Message:

 

Location:

GTP/trunk/Lib/Vis/Preprocessing/src

Files:

• BvHierarchy.cpp (modified) (1 diff)
• GvsPreprocessor.cpp (modified) (12 diffs)
• Polygon3.cpp (modified) (1 diff)
• ViewCellsManager.cpp (modified) (8 diffs)
• ViewCellsManager.h (modified) (1 diff)
• VrmlExporter.cpp (modified) (3 diffs)
• VspTree.cpp (modified) (1 diff)
• VssRay.h (modified) (1 diff)

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

@@ -527 +527 @@
                 (0
                 || (mBvhStats.Leaves() >= mTermMaxLeaves)
+                // does not make much sense for interleaved vsp / osp partition
                 //|| (mBvhStats.mGlobalCostMisses >= mTermGlobalCostMissTolerance)
                 //|| mOutOfMemory 
                 );
 
-        if (1 && terminationCriteriaMet)
+        if (0 && terminationCriteriaMet)
         {
                 Debug << "bvh global termination criteria met:" << endl;

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

@@ -65 +65 @@
         {
                 VssRay *newRay = ReverseSampling(currentRay, hitTriangle, oldRay);
+                newRay->mFlags |= VssRay::ReverseSample;
+                cout << "here9444 " << (int) newRay->mFlags << endl;
                 // ray is not pushed into the queue => can delete ray
                 if (!HandleRay(newRay))
@@ -78 +80 @@
 bool GvsPreprocessor::HandleRay(VssRay *vssRay)
 {
+        cout << "\nhere12 " << (int)vssRay->mFlags << endl;
         const bool storeRaysForViz = true;
         mViewCellsManager->ComputeSampleContribution(*vssRay, true, storeRaysForViz);
@@ -84 +87 @@
         if (vssRay->mPvsContribution > 0)
         {
-                //cout << " h " << mSampleContriPerPass << " " << mSamplesPerPass << " " << mTotalSamples << endl;
                 mRayQueue.push(vssRay);
 
@@ -92 +94 @@
                         for (vit = vssRay->mViewCells.begin(); vit != vit_end; ++ vit)
                         {
-                                (*vit)->mVssRays.push_back(new VssRay(*vssRay));
+                                VssRay *nray = new VssRay(*vssRay);
+                                nray->mFlags = vssRay->mFlags;
+                                (*vit)->mVssRays.push_back(nray);
+nray->mFlags = 10;
+                                cout << "\nhere58 " << (int)nray->mFlags << "  " << (int)vssRay->mFlags << endl;
                         }
                 }
@@ -196 +202 @@
                 // cast ray into the new subdivision point
                 VssRay *newRay = mRayCaster->CastRay(sray, mViewCellsManager->GetViewSpaceBox(), false);
-                //cout << "\np1: " << p1 << "\np : " <<  p << "\np2: " << p2 << endl;
+                
                 if (!newRay) return 0;
-
+newRay->mFlags |= VssRay::BorderSample;
                 const bool enqueued = HandleRay(newRay);
                 
@@ -265 +271 @@
         const int n = (int)enlargedTriangle.size();
         int castRays = (int)vssRays.size();
+
+        VssRayContainer::const_iterator rit, rit_end = vssRays.end();
+        for (rit = vssRays.begin(); rit != rit_end; ++ rit)
+        {
+                (*rit)->mFlags |= VssRay::BorderSample;
+                cout << "here390 " << (int) (*rit)->mFlags << endl;
+        }
+
 #if 1
     // recursivly subdivide each edge
@@ -307 +321 @@
                                                                                  const VssRay &oldRay)
 {
-        ++ mReverseSamples;
-
         //-- The plane p = (xp, hit(x), hit(xold)) is intersected
         //-- with the newly found triangle (xold is the previous ray from
@@ -324 +336 @@
         const Vector3 newOrigin = newDir * -5000.0f;
 
+        ++ mReverseSamples;
+
         return new VssRay(currentRay);
 }
@@ -344 +358 @@
 
         //Debug << "generated " <<  numSamples << " samples in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
-
         return (int)samples.size();
 }
@@ -353 +366 @@
         // add samples to ray queue
         VssRayContainer::const_iterator vit, vit_end = samples.end();
-        
-        for (vit = samples.begin(); vit != vit_end; ++ vit)
+                for (vit = samples.begin(); vit != vit_end; ++ vit)
         {
                 HandleRay(*vit);
@@ -422 +434 @@
                 cout << "finished view cell construction" << endl;
         }
-        else if (1)
+        else if (0)
         {       
                 //-- load view cells from file
@@ -450 +462 @@
                         << "#GvsRuns\n" << mGvsPass << endl;
 
-
                 mViewCellsManager->PrintPvsStatistics(mStats);
 
                 char str[64]; sprintf(str, "tmp/pass%04d-", mPass);
                 
-                // visualization
-                const bool exportRays = true;
-                const bool exportPvs = true;
-                mViewCellsManager->ExportSingleViewCells(mObjects, 10, false, exportPvs, exportRays, 100, str);
+        // visualization
+                if (mSampleContriPerPass > 0)
+                {
+                        const bool exportRays = true;
+                        const bool exportPvs = true;
+
+                        mViewCellsManager->ExportSingleViewCells(mObjects, 10, false, exportPvs, exportRays, 1000, str);
+                }
+
                 // remove pass samples
                 ViewCellContainer::const_iterator vit, vit_end = mViewCellsManager->GetViewCells().end();
-
                 for (vit = mViewCellsManager->GetViewCells().begin(); vit != vit_end; ++ vit)
                 {

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

@@ -266 +266 @@
 bool Polygon3::Valid(const float epsilon) const
 {
-        if (mVertices.size() < 3)
+        if ((int)mVertices.size() < 3)
                 return false;
 

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

@@ -1975 +1975 @@
 void ViewCellsManager::ExportViewCellsForViz(Exporter *exporter,
                                                                                          const AxisAlignedBox3 *sceneBox,
-                                                                                         const AxisAlignedPlane *clipPlane
+                                                                                         const AxisAlignedPlane *clipPlane,
+                                                                                         const bool colorCode
                                                                                          ) const
 {
@@ -1984 +1985 @@
                 if (!mOnlyValidViewCells || (*it)->GetValid())
                 {
-                        ExportColor(exporter, *it);     
+                        ExportColor(exporter, *it, colorCode);  
                         ExportViewCellGeometry(exporter, *it, sceneBox, clipPlane);
                 }
@@ -2351 +2352 @@
 
 
-void ViewCellsManager::ExportColor(Exporter *exporter, ViewCell *vc) const
+void ViewCellsManager::ExportColor(Exporter *exporter, 
+                                                                   ViewCell *vc, 
+                                                                   bool colorCode) const
 {
         const bool vcValid = CheckValidity(vc, mMinPvsSize, mMaxPvsSize);
@@ -2891 +2894 @@
                 mViewCellsTree->GetPvs(vc, pvs);
 
+                char s[64]; sprintf(s, "%sviewcell-%04d.wrl", prefix.c_str(), i);
+                Exporter *exporter = Exporter::GetExporter(s);
+                
+                cout << "view cell " << idx << ": pvs size=" << (int)mViewCellsTree->GetPvsSize(vc) << endl;
+
+                if (exportRays)
+                {
+                        ////////////
+                        //-- export rays piercing this view cell
+
+                        // use rays stored with the view cells
+                        VssRayContainer vcRays, vcRays2, vcRays3;
+            VssRayContainer collectRays;
+
+                        // collect initial view cells
+                        ViewCellContainer leaves;
+                        mViewCellsTree->CollectLeaves(vc, leaves);
+
+                        ViewCellContainer::const_iterator vit, vit_end = leaves.end();
+                for (vit = leaves.begin(); vit != vit_end; ++ vit)
+                        {       
+                                // prepare some rays for output
+                                VssRayContainer::const_iterator rit, rit_end = (*vit)->mVssRays.end();
+                                for (rit = (*vit)->mVssRays.begin(); rit != rit_end; ++ rit)
+                                {
+                                        collectRays.push_back(*rit);
+                                }
+                        }
+
+                        const int raysOut = min((int)collectRays.size(), maxRays);
+
+                        // prepare some rays for output
+                        VssRayContainer::const_iterator rit, rit_end = collectRays.end();
+                        for (rit = collectRays.begin(); rit != rit_end; ++ rit)
+                        {
+                                const float p = RandomValue(0.0f, (float)collectRays.size());
+                                if (p < raysOut)
+                                {
+                                        cout << "here42 " << (int)(*rit)->mFlags << endl;
+                                        if ((*rit)->mFlags & VssRay::BorderSample)
+                                                vcRays.push_back(*rit);
+                                        else if ((*rit)->mFlags & VssRay::ReverseSample)
+                                                vcRays2.push_back(*rit);
+                                        else
+                                                vcRays3.push_back(*rit);
+                                                
+                                }
+                        }
+
+                        exporter->ExportRays(vcRays, RgbColor(1, 0, 0));
+                        exporter->ExportRays(vcRays2, RgbColor(0, 1, 0));
+                        exporter->ExportRays(vcRays3, RgbColor(1, 1, 1));
+                }
+                
+                ////////////////
+                //-- export view cell geometry
+
+                exporter->SetWireframe();
+
+                Material m;//= RandomMaterial();
+                m.mDiffuseColor = RgbColor(0, 1, 0);
+                exporter->SetForcedMaterial(m);
+
+                ExportViewCellGeometry(exporter, vc, NULL, NULL);
+                exporter->SetFilled();
+
+                if (exportPvs)
+                {
+                        Intersectable::NewMail();
+                        ObjectPvsMap::const_iterator oit, oit_end = pvs.mEntries.end();
+                        
+                        // output PVS of view cell
+                        for (oit = pvs.mEntries.begin(); oit != oit_end; ++ oit)
+                        {               
+                                Intersectable *intersect = (*oit).first;
+                                
+                                if (!intersect->Mailed())
+                                {
+                                        intersect->Mail();
+
+                                        m = RandomMaterial();
+                                        exporter->SetForcedMaterial(m);
+                                        exporter->ExportIntersectable(intersect);
+                                }
+                        }
+                        cout << endl;
+                }
+                
+                DEL_PTR(exporter);
+                cout << "finished" << endl;
+        }
+}
+
+
+void BspViewCellsManager::TestSubdivision()
+{
+        ViewCellContainer leaves;
+        mViewCellsTree->CollectLeaves(mViewCellsTree->GetRoot(), leaves);
+
+        ViewCellContainer::const_iterator it, it_end = leaves.end();
+
+        const float vol = mViewSpaceBox.GetVolume();
+        float subdivVol = 0;
+        float newVol = 0;
+
+        for (it = leaves.begin(); it != it_end; ++ it)
+        {
+                BspNodeGeometry geom;
+                mBspTree->ConstructGeometry(*it, geom);
+
+                const float lVol = geom.GetVolume();
+                newVol += lVol;
+                subdivVol += (*it)->GetVolume();
+
+                const float thres = 0.9f;
+                if ((lVol < ((*it)->GetVolume() * thres)) ||
+                        (lVol * thres > ((*it)->GetVolume())))
+                        Debug << "warning: " << lVol << " " << (*it)->GetVolume() << endl;
+        }
+        
+        Debug << "exact volume: " << vol << endl;
+        Debug << "subdivision volume: " << subdivVol << endl;
+        Debug << "new volume: " << newVol << endl;
+}
+
+
+void BspViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
+                                                                                                 ViewCell *vc,
+                                                                                                 const AxisAlignedBox3 *sceneBox,
+                                                                                                 const AxisAlignedPlane *clipPlane
+                                                                                                 ) const
+{
+        if (clipPlane)
+        {
+                const Plane3 plane = clipPlane->GetPlane();
+
+                ViewCellContainer leaves;
+                mViewCellsTree->CollectLeaves(vc, leaves);
+                ViewCellContainer::const_iterator it, it_end = leaves.end();
+
+                for (it = leaves.begin(); it != it_end; ++ it)
+                {
+                        BspNodeGeometry geom;
+                        BspNodeGeometry front;
+                        BspNodeGeometry back;
+
+                        mBspTree->ConstructGeometry(*it, geom);
+
+                        const float eps = 0.0001f;
+                        const int cf = geom.Side(plane, eps);
+
+                        if (cf == -1)
+                        {
+                                exporter->ExportPolygons(geom.GetPolys());
+                        }
+                        else if (cf == 0)
+                        {
+                                geom.SplitGeometry(front,
+                                                                   back,
+                                                                   plane,
+                                                                   mViewSpaceBox, 
+                                                                   eps);
+
+                                if (back.Valid())
+                                {
+                                        exporter->ExportPolygons(back.GetPolys());
+                                }                       
+                        }
+                }
+        }
+        else
+        {
+                // export mesh if available
+                // TODO: some bug here?
+                if (1 && vc->GetMesh())
+                {
+                        exporter->ExportMesh(vc->GetMesh());
+                }
+                else
+                {
+                        BspNodeGeometry geom;
+                        mBspTree->ConstructGeometry(vc, geom);
+                        exporter->ExportPolygons(geom.GetPolys());
+                }
+        }
+}
+
+
+void BspViewCellsManager::CreateMesh(ViewCell *vc)
+{
+        // note: should previous mesh be deleted (via mesh manager?)
+        BspNodeGeometry geom;
+        mBspTree->ConstructGeometry(vc, geom);
+
+        Mesh *mesh = MeshManager::GetSingleton()->CreateResource();
+
+        IncludeNodeGeomInMesh(geom, *mesh);
+        vc->SetMesh(mesh);
+}
+
+
+void BspViewCellsManager::Finalize(ViewCell *viewCell, 
+                                                                   const bool createMesh)
+{
+        float area = 0;
+        float volume = 0;
+
+        ViewCellContainer leaves;
+        mViewCellsTree->CollectLeaves(viewCell, leaves);
+
+        ViewCellContainer::const_iterator it, it_end = leaves.end();
+
+    for (it = leaves.begin(); it != it_end; ++ it)
+        {
+                BspNodeGeometry geom;
+
+                mBspTree->ConstructGeometry(*it, geom);
+
+                const float lVol = geom.GetVolume();
+                const float lArea = geom.GetArea();
+
+                area += lArea;
+                volume += lVol;
+        
+                CreateMesh(*it);
+        }
+
+        viewCell->SetVolume(volume);
+        viewCell->SetArea(area);
+}
+
+
+ViewCell *BspViewCellsManager::GetViewCell(const Vector3 &point, const bool active) const
+{
+        if (!ViewCellsConstructed())
+        {
+                return NULL;
+        }
+        if (!mViewSpaceBox.IsInside(point))
+        {
+                return NULL;
+        }
+        return mBspTree->GetViewCell(point);
+}
+
+
+void BspViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays, 
+                                                                                                 vector<MergeCandidate> &candidates)
+{
+        cout << "collecting merge candidates ... " << endl;
+
+        if (mUseRaysForMerge)
+        {
+                mBspTree->CollectMergeCandidates(rays, candidates);
+        }
+        else
+        {
+                vector<BspLeaf *> leaves;
+                mBspTree->CollectLeaves(leaves);
+                mBspTree->CollectMergeCandidates(leaves, candidates);
+        }
+
+        cout << "fininshed collecting candidates" << endl;
+}
+
+
+
+bool BspViewCellsManager::ExportViewCells(const string filename, 
+                                                                                  const bool exportPvs, 
+                                                                                  const ObjectContainer &objects)
+{
+        if (!ViewCellsConstructed() || !ViewCellsTreeConstructed())
+        {
+                return false;
+        }
+
+        cout << "exporting view cells to xml ... ";
+
+        OUT_STREAM stream(filename.c_str());
+
+        // for output we need unique ids for each view cell
+        CreateUniqueViewCellIds();
+
+        stream << "<?xml version=\"1.0\" encoding=\"UTF-8\"?>"<<endl;
+        stream << "<VisibilitySolution>" << endl;
+
+        if (exportPvs) 
+        {
+                //////////
+                //-- export bounding boxes: they are used to identify the objects from the pvs and
+                //-- assign them to the entities in the rendering engine
+
+                stream << "<BoundingBoxes>" << endl;
+                ObjectContainer::const_iterator oit, oit_end = objects.end();
+
+                for (oit = objects.begin(); oit != oit_end; ++ oit)
+                {
+                        const AxisAlignedBox3 box = (*oit)->GetBox();
+                        
+                        stream << "<BoundingBox" << " id=\"" << (*oit)->GetId() << "\""
+                                   << " min=\"" << box.Min().x << " " << box.Min().y << " " << box.Min().z << "\""
+                                   << " max=\"" << box.Max().x << " " << box.Max().y << " " << box.Max().z << "\" />" << endl;
+                }
+
+                stream << "</BoundingBoxes>" << endl;
+        }
+
+        ///////////
+        //-- export the view cells and the pvs
+
+        const int numViewCells = mCurrentViewCellsStats.viewCells;
+        stream << "<ViewCells number=\"" << numViewCells << "\" >" << endl;
+
+        mViewCellsTree->Export(stream, exportPvs);
+        
+        stream << "</ViewCells>" << endl;
+
+        /////////////
+        //-- export the view space hierarchy
+        stream << "<ViewSpaceHierarchy type=\"bsp\""
+                   << " min=\"" << mViewSpaceBox.Min().x << " " << mViewSpaceBox.Min().y << " " << mViewSpaceBox.Min().z << "\""
+                   << " max=\"" << mViewSpaceBox.Max().x << " " << mViewSpaceBox.Max().y << " " << mViewSpaceBox.Max().z << "\">" << endl;
+
+        mBspTree->Export(stream);
+
+        // end tags
+        stream << "</ViewSpaceHierarchy>" << endl;
+        stream << "</VisibilitySolution>" << endl;
+
+        stream.close();
+        cout << "finished" << endl;
+
+        return true;
+}
+
+
+ViewCell *BspViewCellsManager::ConstructDummyMergeTree(BspNode *root)
+{
+        ViewCellInterior *vcRoot = new ViewCellInterior();
+                
+        // evaluate merge cost for priority traversal
+        const float mergeCost = 1.0f / (float)root->mTimeStamp;
+        vcRoot->SetMergeCost(mergeCost);
+
+        float volume = 0;
+        vector<BspLeaf *> leaves;
+        mBspTree->CollectLeaves(leaves);
+        vector<BspLeaf *>::const_iterator lit, lit_end = leaves.end();
+        ViewCell::NewMail();
+
+        for (lit = leaves.begin(); lit != lit_end; ++ lit)
+        {
+                BspLeaf *leaf = *lit;
+                ViewCell *vc = leaf->GetViewCell();
+
+                if (!vc->Mailed())
+                {
+                        vc->Mail();
+                        vc->SetMergeCost(0.0f);
+                        vcRoot->SetupChildLink(vc);
+
+                        volume += vc->GetVolume();
+                        volume += vc->GetVolume();      
+                        vcRoot->SetVolume(volume);
+                }
+        }
+        
+        return vcRoot;
+}
+
+
+ViewCell *BspViewCellsManager::ConstructSpatialMergeTree(BspNode *root)
+{
+        // terminate recursion
+        if (root->IsLeaf())
+        {
+                BspLeaf *leaf = dynamic_cast<BspLeaf *>(root);
+                leaf->GetViewCell()->SetMergeCost(0.0f);
+                return leaf->GetViewCell();
+        }
+        
+        BspInterior *interior = dynamic_cast<BspInterior *>(root);
+        ViewCellInterior *viewCellInterior = new ViewCellInterior();
+                
+        // evaluate merge cost for priority traversal
+        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;
+}
+
+
+/************************************************************************/
+/*                   KdViewCellsManager implementation                  */
+/************************************************************************/
+
+
+
+KdViewCellsManager::KdViewCellsManager(ViewCellsTree *vcTree, KdTree *kdTree):
+ViewCellsManager(vcTree), mKdTree(kdTree), mKdPvsDepth(100)
+{
+}
+
+
+float KdViewCellsManager::GetProbability(ViewCell *viewCell)
+{
+        // compute view cell area / volume as subsititute for probability
+        if (0)
+                return GetArea(viewCell) / GetViewSpaceBox().SurfaceArea();
+        else
+                return GetVolume(viewCell) / GetViewSpaceBox().GetVolume();
+}
+
+
+
+
+void KdViewCellsManager::CollectViewCells()
+{
+        //mKdTree->CollectViewCells(mViewCells); TODO
+}
+
+
+int KdViewCellsManager::ConstructSubdivision(const ObjectContainer &objects,
+                                                                  const VssRayContainer &rays)
+{
+        // if view cells already constructed
+        if (ViewCellsConstructed())
+                return 0;
+
+        mKdTree->Construct();
+
+        mTotalAreaValid = false;
+        // create the view cells
+        mKdTree->CreateAndCollectViewCells(mViewCells);
+        // cast rays
+        ComputeSampleContributions(rays, true, false);
+
+        EvaluateViewCellsStats();
+        Debug << "\nView cells after construction:\n" << mCurrentViewCellsStats << endl;
+
+        return 0;
+}
+
+
+bool KdViewCellsManager::ViewCellsConstructed() const
+{
+        return mKdTree->GetRoot() != NULL;
+}
+
+
+int KdViewCellsManager::PostProcess(const ObjectContainer &objects,
+                                                                        const VssRayContainer &rays)
+{
+        return 0;
+}
+
+
+void KdViewCellsManager::ExportSingleViewCells(const ObjectContainer &objects,
+                                                                                           const int maxViewCells,
+                                                                                           const bool sortViewCells,
+                                                                                           const bool exportPvs,
+                                                                                           const bool exportRays,
+                                                                                           const int maxRays,
+                                                                                           const string prefix,
+                                                                                           VssRayContainer *visRays)
+{
+        // TODO
+}
+
+
+void KdViewCellsManager::Visualize(const ObjectContainer &objects,
+                                                                   const VssRayContainer &sampleRays)
+{
+        if (!ViewCellsConstructed())
+                return;
+
+        // using view cells instead of the kd PVS of objects
+        const bool useViewCells = true;
+        bool exportRays = false;
+
+        int limit = min(mVisualizationSamples, (int)sampleRays.size());
+        const int pvsOut = min((int)objects.size(), 10);
+        VssRayContainer *rays = new VssRayContainer[pvsOut];
+
+        if (useViewCells)
+        {
+                const int leafOut = 10;
+
+                ViewCell::NewMail();
+
+                //-- some rays for output
+                const int raysOut = min((int)sampleRays.size(), mVisualizationSamples);
+                Debug << "visualization using " << raysOut << " samples" << endl;
+
+                //-- some random view cells and rays for output
+                vector<KdLeaf *> kdLeaves;
+
+                for (int i = 0; i < leafOut; ++ i)
+                        kdLeaves.push_back(dynamic_cast<KdLeaf *>(mKdTree->GetRandomLeaf()));
+
+                for (int i = 0; i < kdLeaves.size(); ++ i)
+                {
+                        KdLeaf *leaf = kdLeaves[i];
+                        RayContainer vcRays;
+
+                        cout << "creating output for view cell " << i << " ... ";
+#if 0
+                        // check whether we can add the current ray to the output rays
+                        for (int k = 0; k < raysOut; ++ k)
+                        {
+                                Ray *ray = sampleRays[k];
+
+                                for (int j = 0; j < (int)ray->bspIntersections.size(); ++ j)
+                                {
+                                        BspLeaf *leaf2 = ray->bspIntersections[j].mLeaf;
+
+                                        if (leaf->GetViewCell() == leaf2->GetViewCell())
+                                        {
+                                                vcRays.push_back(ray);
+                                        }
+                                }
+                        }
+#endif
+                        Intersectable::NewMail();
+
+                        ViewCell *vc = leaf->mViewCell;
+                        char str[64]; sprintf(str, "viewcell%04d.wrl", i);
+
+                        Exporter *exporter = Exporter::GetExporter(str);
+                        exporter->SetFilled();
+
+                        exporter->SetWireframe();
+                        //exporter->SetFilled();
+
+                        Material m;//= RandomMaterial();
+                        m.mDiffuseColor = RgbColor(1, 1, 0);
+                        exporter->SetForcedMaterial(m);
+
+                        AxisAlignedBox3 box = mKdTree->GetBox(leaf);
+                        exporter->ExportBox(box);
+
+                        // export rays piercing this view cell
+                        exporter->ExportRays(vcRays, 1000, RgbColor(0, 1, 0));
+
+                        m.mDiffuseColor = RgbColor(1, 0, 0);
+                        exporter->SetForcedMaterial(m);
+
+                        // exporter->SetWireframe();
+                        exporter->SetFilled();
+
+                        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 str[64]; sprintf(str, "viewcell%04d.wrl", i);
+
+                        Exporter *exporter = Exporter::GetExporter(str);
+                        exporter->SetWireframe();
+
+                        KdPvsMap::iterator kit = object->mKdPvs.mEntries.begin();
+                        Intersectable::NewMail();
+
+                        // avoid adding the object to the list
+                        object->Mail();
+                        ObjectContainer visibleObjects;
+
+                        for (; kit != object->mKdPvs.mEntries.end(); i++)
+                        {
+                                KdNode *node = (*kit).first;
+                                exporter->ExportBox(mKdTree->GetBox(node));
+
+                                mKdTree->CollectObjects(node, visibleObjects);
+                        }
+
+                        exporter->ExportRays(rays[k],  RgbColor(0, 1, 0));
+                        exporter->SetFilled();
+
+                        for (int j = 0; j < visibleObjects.size(); j++)
+                                exporter->ExportIntersectable(visibleObjects[j]);
+
+                        Material m;
+                        m.mDiffuseColor = RgbColor(1, 0, 0);
+                        exporter->SetForcedMaterial(m);
+                        exporter->ExportIntersectable(object);
+
+                        delete exporter;
+                }
+        }
+}
+
+
+ViewCell *KdViewCellsManager::GenerateViewCell(Mesh *mesh) const
+{
+        return new KdViewCell(mesh);
+}
+
+
+void KdViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
+                                                                                                ViewCell *vc,
+                                                                                                const AxisAlignedBox3 *sceneBox,
+                                                                                                const AxisAlignedPlane *clipPlane
+                                                                                                ) const
+{
+        ViewCellContainer leaves;
+        mViewCellsTree->CollectLeaves(vc, leaves);
+        ViewCellContainer::const_iterator it, it_end = leaves.end();
+
+        for (it = leaves.begin(); it != it_end; ++ it)
+        {
+                KdViewCell *kdVc = dynamic_cast<KdViewCell *>(*it);
+                exporter->ExportBox(mKdTree->GetBox(kdVc->mLeaves[0]));
+        }
+}
+
+
+int KdViewCellsManager::GetType() const
+{
+        return ViewCellsManager::KD;
+}
+
+
+
+KdNode *KdViewCellsManager::GetNodeForPvs(KdLeaf *leaf)
+{
+        KdNode *node = leaf;
+
+        while (node->mParent && node->mDepth > mKdPvsDepth)
+                node = node->mParent;
+
+        return node;
+}
+
+int KdViewCellsManager::CastLineSegment(const Vector3 &origin,
+                                                                                const Vector3 &termination,
+                                                                                ViewCellContainer &viewcells)
+{
+        return mKdTree->CastLineSegment(origin, termination, viewcells);
+}
+
+
+void KdViewCellsManager::CreateMesh(ViewCell *vc)
+{
+        // TODO
+}
+
+
+
+void KdViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays, 
+                                                                                                vector<MergeCandidate> &candidates)
+{
+        // TODO
+}
+
+
+
+/**************************************************************************/
+/*                   VspBspViewCellsManager implementation                */
+/**************************************************************************/
+
+
+VspBspViewCellsManager::VspBspViewCellsManager(ViewCellsTree *vcTree, VspBspTree *vspBspTree):
+ViewCellsManager(vcTree), mVspBspTree(vspBspTree)
+{
+        Environment::GetSingleton()->GetIntValue("VspBspTree.Construction.samples", mInitialSamples);
+        mVspBspTree->SetViewCellsManager(this);
+        mVspBspTree->mViewCellsTree = mViewCellsTree;
+}
+
+
+VspBspViewCellsManager::~VspBspViewCellsManager()
+{
+}
+
+
+float VspBspViewCellsManager::GetProbability(ViewCell *viewCell)
+{
+        if (0 && mVspBspTree->mUseAreaForPvs)
+                return GetArea(viewCell) / GetAccVcArea();
+        else
+                return GetVolume(viewCell) / mViewSpaceBox.GetVolume();
+}
+
+
+void VspBspViewCellsManager::CollectViewCells()
+{
+        // view cells tree constructed?
+        if (!ViewCellsTreeConstructed())
+        {
+                mVspBspTree->CollectViewCells(mViewCells, false);
+        }
+        else 
+        {       
+                // we can use the view cells tree hierarchy to get the right set
+                mViewCellsTree->CollectBestViewCellSet(mViewCells, mNumActiveViewCells);
+        }
+}
+
+
+void VspBspViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays, 
+                                                                                                        vector<MergeCandidate> &candidates)
+{       
+        cout << "collecting merge candidates ... " << endl;
+
+        if (mUseRaysForMerge)
+        {
+                mVspBspTree->CollectMergeCandidates(rays, candidates);
+        }
+        else
+        {
+                vector<BspLeaf *> leaves;
+                mVspBspTree->CollectLeaves(leaves);
+        
+                mVspBspTree->CollectMergeCandidates(leaves, candidates);
+        }
+
+        cout << "fininshed collecting candidates" << endl;
+}
+
+
+bool VspBspViewCellsManager::ViewCellsConstructed() const
+{
+        return mVspBspTree->GetRoot() != NULL;
+}
+
+
+ViewCell *VspBspViewCellsManager::GenerateViewCell(Mesh *mesh) const
+{
+        return new BspViewCell(mesh);
+}
+
+
+int VspBspViewCellsManager::ConstructSubdivision(const ObjectContainer &objects,
+                                                                                                 const VssRayContainer &rays)
+{
+        mMaxPvsSize = (int)(mMaxPvsRatio * (float)objects.size());
+
+        // if view cells were already constructed
+        if (ViewCellsConstructed())
+        {
+                return 0;
+        }
+
+        int sampleContributions = 0;
+        VssRayContainer sampleRays;
+
+        const int limit = min(mInitialSamples, (int)rays.size());
+
+        Debug << "samples used for vsp bsp subdivision: " << mInitialSamples 
+                  << ", actual rays: " << (int)rays.size() << endl;
+
+        VssRayContainer savedRays;
+
+        if (SAMPLE_AFTER_SUBDIVISION)
+        {
+                VssRayContainer constructionRays;
+                
+                GetRaySets(rays, mInitialSamples, constructionRays, &savedRays);
+
+                Debug << "rays used for initial construction: " << (int)constructionRays.size() << endl;
+                Debug << "rays saved for later use: " << (int)savedRays.size() << endl;
+        
+                mVspBspTree->Construct(constructionRays, &mViewSpaceBox);
+        }
+        else
+        {
+                Debug << "rays used for initial construction: " << (int)rays.size() << endl;
+                mVspBspTree->Construct(rays, &mViewSpaceBox);
+        }
+
+        // collapse invalid regions
+        cout << "collapsing invalid tree regions ... ";
+        long startTime = GetTime();
+
+        const int collapsedLeaves = mVspBspTree->CollapseTree();
+        Debug << "collapsed in " << TimeDiff(startTime, GetTime()) * 1e-3 
+                  << " seconds" << endl;
+
+    cout << "finished" << endl;
+
+        /////////////////
+        //-- stats after construction
+
+        Debug << mVspBspTree->GetStatistics() << endl;
+
+        ResetViewCells();
+        Debug << "\nView cells after construction:\n" << mCurrentViewCellsStats << endl;
+
+
+        //////////////////////
+        //-- recast the rest of the rays
+
+        startTime = GetTime();
+
+        cout << "Computing remaining ray contributions ... ";
+
+        if (SAMPLE_AFTER_SUBDIVISION)
+                ComputeSampleContributions(savedRays, true, false);
+
+        cout << "finished" << endl;
+
+        Debug << "Computed remaining ray contribution in " << TimeDiff(startTime, GetTime()) * 1e-3
+                  << " secs" << endl;
+
+        cout << "construction finished" << endl;
+
+        if (0)
+        {       ////////
+                //-- real meshes are contructed at this stage
+                cout << "finalizing view cells ... ";
+                FinalizeViewCells(true);
+                cout << "finished" << endl;
+        }
+
+        return sampleContributions;
+}
+
+
+void VspBspViewCellsManager::MergeViewCells(const VssRayContainer &rays,
+                                                                                        const ObjectContainer &objects)
+{
+    int vcSize = 0;
+        int pvsSize = 0;
+
+        //-- merge view cells
+        cout << "starting merge using " << mPostProcessSamples << " samples ... " << endl;
+        long startTime = GetTime();
+
+
+        if (mMergeViewCells)
+        {
+                // TODO: should be done BEFORE the ray casting
+                // compute tree by merging the nodes based on cost heuristics
+                mViewCellsTree->ConstructMergeTree(rays, objects);
+        }
+        else
+        {
+                // compute tree by merging the nodes of the spatial hierarchy
+                ViewCell *root = ConstructSpatialMergeTree(mVspBspTree->GetRoot());
+                mViewCellsTree->SetRoot(root);
+
+                // compute pvs
+                ObjectPvs pvs;
+                UpdatePvsForEvaluation(root, pvs);
+        }
+
+        if (1)
+        {
+                char mstats[100];
+                ObjectPvs pvs;
+
+                Environment::GetSingleton()->GetStringValue("ViewCells.mergeStats", mstats);
+                mViewCellsTree->ExportStats(mstats);
+        }
+
+        cout << "merged view cells in "
+                 << TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl;
+
+        Debug << "Postprocessing: Merged view cells in "
+                  << TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl << endl;
+        
+
+        //////////////////
+        //-- stats and visualizations
+
+        int savedColorCode = mColorCode;
+        
+        // get currently active view cell set
+        ResetViewCells();
+        Debug << "\nView cells after merge:\n" << mCurrentViewCellsStats << endl;
+        
+        if (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, NULL, GetClipPlane());
+
+                        if (mExportGeometry)
+                        {
+                                Material m;
+                                m.mDiffuseColor = RgbColor(0, 1, 0);
+                                exporter->SetForcedMaterial(m);
+                                exporter->SetFilled();
+
+                                exporter->ExportGeometry(objects);
+                        }
+
+                        delete exporter;
+                }
+                cout << "finished" << endl;
+        }
+
+        if (1) 
+        {
+                // use pvs size for color coding
+                mColorCode = 1;
+                Exporter *exporter = Exporter::GetExporter("merged_view_cells_pvs.wrl");
+
+                cout << "exporting view cells after merge (pvs size) ... ";     
+
+                if (exporter)
+                {
+                        exporter->SetFilled();
+
+                        ExportViewCellsForViz(exporter, NULL, GetClipPlane());
+
+                        if (mExportGeometry)
+                        {
+                                Material m;
+                                m.mDiffuseColor = RgbColor(0, 1, 0);
+                                exporter->SetForcedMaterial(m);
+                                exporter->SetFilled();
+
+                                exporter->ExportGeometry(objects);
+                        }
+
+                        delete exporter;
+                }
+                cout << "finished" << endl;
+        }
+
+        mColorCode = savedColorCode;
+
+}
+
+
+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->mLeaves[0];
+        }
+        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)
+{
+        mRenderer->RenderScene();
+        SimulationStatistics ss;
+        dynamic_cast<RenderSimulator *>(mRenderer)->GetStatistics(ss);
+    Debug << "render time before refine\n\n" << ss << endl;
+
+        const long startTime = GetTime();
+        cout << "Refining the merged view cells ... ";
+
+        // refining the merged view cells
+        const int refined = mViewCellsTree->RefineViewCells(rays, objects);
+
+        //-- stats and visualizations
+        cout << "finished" << endl;
+        cout << "refined " << refined << " view cells in "
+                 << TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl;
+
+        Debug << "Postprocessing: refined " << refined << " view cells in "
+                  << TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl << endl;
+}
+
+
+int VspBspViewCellsManager::PostProcess(const ObjectContainer &objects,
+                                                                                const VssRayContainer &rays)
+{
+        if (!ViewCellsConstructed())
+        {
+                Debug << "postprocess error: no view cells constructed" << endl;
+                return 0;
+        }
+
+        // view cells already finished before post processing step 
+        // (i.e. because they were loaded)
+        if (mViewCellsFinished)
+        {
+                FinalizeViewCells(true);
+                EvaluateViewCellsStats();
+
+                return 0;
+        }
+
+        // check if new view cells turned invalid
+        int minPvs, maxPvs;
+
+        if (0)
+        {
+                minPvs = mMinPvsSize;
+                maxPvs = mMaxPvsSize;
+        }
+        else
+        {
+                // problem matt: why did I start here from zero?
+                minPvs = 0;
+                maxPvs = mMaxPvsSize;
+        }
+
+        Debug << "setting validity, min: " << minPvs << " max: " << maxPvs << endl;
+        cout << "setting validity, min: " << minPvs << " max: " << maxPvs << endl;
+        
+        SetValidity(minPvs, maxPvs); 
+
+        // update valid view space according to valid view cells
+        if (0) mVspBspTree->ValidateTree();
+
+        // area has to be recomputed
+        mTotalAreaValid = false;
+        VssRayContainer postProcessRays;
+        GetRaySets(rays, mPostProcessSamples, postProcessRays);
+
+        Debug << "post processing using " << (int)postProcessRays.size() << " samples" << endl;
+
+        // 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);
+        
+        // refines the merged view cells
+        if (0) RefineViewCells(postProcessRays, objects);
+
+
+        ///////////
+        //-- render simulation after merge + refine
+
+        cout << "\nview cells partition render time before compress" << endl << endl;;
+        dynamic_cast<RenderSimulator *>(mRenderer)->RenderScene();
+        SimulationStatistics ss;
+        dynamic_cast<RenderSimulator *>(mRenderer)->GetStatistics(ss);
+        cout << ss << endl;
+        
+
+        ////////////
+        //-- compression
+
+        if (ViewCellsTreeConstructed() && mCompressViewCells)
+        {
+                int pvsEntries = mViewCellsTree->GetStoredPvsEntriesNum(mViewCellsTree->GetRoot());
+                Debug << "number of entries before compress: " << pvsEntries << endl;
+
+                mViewCellsTree->SetViewCellsStorage(ViewCellsTree::COMPRESSED);
+
+                pvsEntries = mViewCellsTree->GetStoredPvsEntriesNum(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 (1 && mExportViewCells)
+        {
+                char filename[100];
+                Environment::GetSingleton()->GetStringValue("ViewCells.filename", filename);
+                ExportViewCells(filename, mExportPvs, 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;
+}
+
+
+bool VspBspViewCellsManager::GetViewPoint(Vector3 &viewPoint) const
+{
+        if (!ViewCellsConstructed())
+                return ViewCellsManager::GetViewPoint(viewPoint);
+
+        // TODO: set reasonable limit
+        const int limit = 20;
+
+        for (int i = 0; i < limit; ++ i)
+        {
+                viewPoint = mViewSpaceBox.GetRandomPoint();
+                if (mVspBspTree->ViewPointValid(viewPoint))
+                {
+                        return true;
+                }
+        }
+
+        Debug << "failed to find valid view point, taking " << viewPoint << endl;
+        return false;
+}
+
+
+bool VspBspViewCellsManager::ViewPointValid(const Vector3 &viewPoint) const
+{
+        // $$JB -> implemented in viewcellsmanager (slower, but allows dynamic
+        // validy update in preprocessor for all managers)
+        return ViewCellsManager::ViewPointValid(viewPoint);
+
+        //      return mViewSpaceBox.IsInside(viewPoint) &&
+        //                 mVspBspTree->ViewPointValid(viewPoint);
+}
+
+
+void VspBspViewCellsManager::Visualize(const ObjectContainer &objects,
+                                                                           const VssRayContainer &sampleRays)
+{
+        if (!ViewCellsConstructed())
+                return;
+
+        VssRayContainer visRays;
+        GetRaySets(sampleRays, mVisualizationSamples, visRays);
+        
+        if (1) 
+        {       
+                //////////////////
+                //-- export final view cell partition
+
+                Exporter *exporter = Exporter::GetExporter("final_view_cells.wrl");
+                
+                if (exporter)
+                {
+                        cout << "exporting view cells after post process ... ";
+                        if (0)
+                        {       // export view space box
+                                exporter->SetWireframe();
+                                exporter->ExportBox(mViewSpaceBox);
+                                exporter->SetFilled();
+                        }
+
+                        Material m; 
+                        m.mDiffuseColor.r = 0.0f;
+                        m.mDiffuseColor.g = 0.5f;
+                        m.mDiffuseColor.b = 0.5f;
+
+            exporter->SetForcedMaterial(m);
+
+                        if (1 && mExportGeometry)
+                        {
+                                exporter->ExportGeometry(objects);
+                        }
+
+                        if (0 && mExportRays)
+                        {
+                                exporter->ExportRays(visRays, RgbColor(1, 0, 0));
+                        }
+                        ExportViewCellsForViz(exporter, NULL, GetClipPlane());
+
+                        delete exporter;
+                        cout << "finished" << endl;
+                }
+        }
+
+        ////////////////
+        //-- visualization of the BSP splits
+
+        bool exportSplits = false;
+        Environment::GetSingleton()->GetBoolValue("VspBspTree.Visualization.exportSplits", exportSplits);
+
+        if (exportSplits)
+        {
+                cout << "exporting splits ... ";
+                ExportSplits(objects, visRays);
+                cout << "finished" << endl;
+        }
+
+        ////////
+        //-- export single view cells
+        
+        int leafOut;
+        Environment::GetSingleton()->GetIntValue("ViewCells.Visualization.maxOutput", leafOut);
+        const int raysOut = 100;
+        
+        ExportSingleViewCells(objects, leafOut, false, true, false, raysOut, "");
+}
+
+
+void VspBspViewCellsManager::ExportSplits(const ObjectContainer &objects,
+                                                                                  const VssRayContainer &rays)
+{
+        Exporter *exporter = Exporter::GetExporter("bsp_splits.x3d");
+
+        if (exporter)
+        {
+                Material m;
+                m.mDiffuseColor = RgbColor(1, 0, 0);
+                exporter->SetForcedMaterial(m);
+                exporter->SetWireframe();
+
+                exporter->ExportBspSplits(*mVspBspTree, true);
+
+                // take forced material, else big scenes cannot be viewed
+                m.mDiffuseColor = RgbColor(0, 1, 0);
+                exporter->SetForcedMaterial(m);
+                exporter->SetFilled();
+
+                exporter->ResetForcedMaterial();
+
+                // export rays
+                if (mExportRays)
+                {
+                        exporter->ExportRays(rays, RgbColor(1, 1, 0));
+                }
+
+                if (mExportGeometry)
+                {
+                        exporter->ExportGeometry(objects);
+                }
+                delete exporter;
+        }
+}
+
+
+void VspBspViewCellsManager::ExportSingleViewCells(const ObjectContainer &objects,
+                                                                                                   const int maxViewCells,
+                                                                                                   const bool sortViewCells,
+                                                                                                   const bool exportPvs,
+                                                                                                   const bool exportRays,
+                                                                                                   const int maxRays,
+                                                                                                   const string prefix,
+                                                                                                   VssRayContainer *visRays)
+{       
+        if (sortViewCells)
+        {
+                // sort view cells to visualize the largest view cells
+                stable_sort(mViewCells.begin(), mViewCells.end(), ViewCell::LargerRenderCost);
+        }
+
+        //////////
+        //-- some view cells for output
+
+        ViewCell::NewMail();
+        const int limit = min(maxViewCells, (int)mViewCells.size());
+        
+        for (int i = 0; i < limit; ++ i)
+        {
+                cout << "creating output for view cell " << i << " ... ";
+
+                ViewCell *vc = sortViewCells ? // largest view cell pvs first?
+                        mViewCells[(int)RandomValue(0, (float)mViewCells.size() - 0.5f)] : mViewCells[i];
+
+                if (vc->Mailed() || vc->GetId() == OUT_OF_BOUNDS_ID)
+                        continue;
+
+                vc->Mail();
+
+                ObjectPvs pvs;
+                mViewCellsTree->GetPvs(vc, pvs);
+
                 char s[64]; sprintf(s, "%sviewcell%04d.wrl", prefix.c_str(), i);
                 Exporter *exporter = Exporter::GetExporter(s);
                 
-                cout << "view cell " << idx << ": pvs size=" << (int)mViewCellsTree->GetPvsSize(vc) << endl;
+                const int pvsSize = (int)mViewCellsTree->GetPvsSize(vc);
+                cout << "view cell " << vc->GetId() << ": pvs size=" << pvsSize << endl;
 
                 if (exportRays)
@@ -2922 +4323 @@
 
                         const int raysOut = min((int)collectRays.size(), maxRays);
-cout << "here500 " << raysOut << endl;
+                
                         // prepare some rays for output
                         VssRayContainer::const_iterator rit, rit_end = collectRays.end();
@@ -2934 +4335 @@
                                 }
                         }
+
                         exporter->ExportRays(vcRays, RgbColor(1, 1, 1));
                 }
@@ -2963 +4365 @@
                                 {
                                         intersect->Mail();
+
                                         m = RandomMaterial();
                                         exporter->SetForcedMaterial(m);
                                         exporter->ExportIntersectable(intersect);
-                                        cout << " i: " << intersect;
-                                }
-                        }
-                        cout << endl;
-                }
-                
-                DEL_PTR(exporter);
-                cout << "finished" << endl;
-        }
-}
-
-
-void BspViewCellsManager::TestSubdivision()
-{
-        ViewCellContainer leaves;
-        mViewCellsTree->CollectLeaves(mViewCellsTree->GetRoot(), leaves);
-
-        ViewCellContainer::const_iterator it, it_end = leaves.end();
-
-        const float vol = mViewSpaceBox.GetVolume();
-        float subdivVol = 0;
-        float newVol = 0;
-
-        for (it = leaves.begin(); it != it_end; ++ it)
-        {
-                BspNodeGeometry geom;
-                mBspTree->ConstructGeometry(*it, geom);
-
-                const float lVol = geom.GetVolume();
-                newVol += lVol;
-                subdivVol += (*it)->GetVolume();
-
-                const float thres = 0.9f;
-                if ((lVol < ((*it)->GetVolume() * thres)) ||
-                        (lVol * thres > ((*it)->GetVolume())))
-                        Debug << "warning: " << lVol << " " << (*it)->GetVolume() << endl;
-        }
-        
-        Debug << "exact volume: " << vol << endl;
-        Debug << "subdivision volume: " << subdivVol << endl;
-        Debug << "new volume: " << newVol << endl;
-}
-
-
-void BspViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
-                                                                                                 ViewCell *vc,
-                                                                                                 const AxisAlignedBox3 *sceneBox,
-                                                                                                 const AxisAlignedPlane *clipPlane
-                                                                                                 ) const
-{
-        if (clipPlane)
-        {
-                const Plane3 plane = clipPlane->GetPlane();
-
-                ViewCellContainer leaves;
-                mViewCellsTree->CollectLeaves(vc, leaves);
-                ViewCellContainer::const_iterator it, it_end = leaves.end();
-
-                for (it = leaves.begin(); it != it_end; ++ it)
-                {
-                        BspNodeGeometry geom;
-                        BspNodeGeometry front;
-                        BspNodeGeometry back;
-
-                        mBspTree->ConstructGeometry(*it, geom);
-
-                        const float eps = 0.0001f;
-                        const int cf = geom.Side(plane, eps);
-
-                        if (cf == -1)
-                        {
-                                exporter->ExportPolygons(geom.GetPolys());
-                        }
-                        else if (cf == 0)
-                        {
-                                geom.SplitGeometry(front,
-                                                                   back,
-                                                                   plane,
-                                                                   mViewSpaceBox, 
-                                                                   eps);
-
-                                if (back.Valid())
-                                {
-                                        exporter->ExportPolygons(back.GetPolys());
-                                }                       
-                        }
-                }
-        }
-        else
-        {
-                // export mesh if available
-                // TODO: some bug here?
-                if (1 && vc->GetMesh())
-                {
-                        exporter->ExportMesh(vc->GetMesh());
-                }
-                else
-                {
-                        BspNodeGeometry geom;
-                        mBspTree->ConstructGeometry(vc, geom);
-                        exporter->ExportPolygons(geom.GetPolys());
-                }
-        }
-}
-
-
-void BspViewCellsManager::CreateMesh(ViewCell *vc)
-{
-        // note: should previous mesh be deleted (via mesh manager?)
-        BspNodeGeometry geom;
-        mBspTree->ConstructGeometry(vc, geom);
-
-        Mesh *mesh = MeshManager::GetSingleton()->CreateResource();
-
-        IncludeNodeGeomInMesh(geom, *mesh);
-        vc->SetMesh(mesh);
-}
-
-
-void BspViewCellsManager::Finalize(ViewCell *viewCell, 
-                                                                   const bool createMesh)
-{
-        float area = 0;
-        float volume = 0;
-
-        ViewCellContainer leaves;
-        mViewCellsTree->CollectLeaves(viewCell, leaves);
-
-        ViewCellContainer::const_iterator it, it_end = leaves.end();
-
-    for (it = leaves.begin(); it != it_end; ++ it)
-        {
-                BspNodeGeometry geom;
-
-                mBspTree->ConstructGeometry(*it, geom);
-
-                const float lVol = geom.GetVolume();
-                const float lArea = geom.GetArea();
-
-                area += lArea;
-                volume += lVol;
-        
-                CreateMesh(*it);
-        }
-
-        viewCell->SetVolume(volume);
-        viewCell->SetArea(area);
-}
-
-
-ViewCell *BspViewCellsManager::GetViewCell(const Vector3 &point, const bool active) const
-{
-        if (!ViewCellsConstructed())
-        {
-                return NULL;
-        }
-        if (!mViewSpaceBox.IsInside(point))
-        {
-                return NULL;
-        }
-        return mBspTree->GetViewCell(point);
-}
-
-
-void BspViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays, 
-                                                                                                 vector<MergeCandidate> &candidates)
-{
-        cout << "collecting merge candidates ... " << endl;
-
-        if (mUseRaysForMerge)
-        {
-                mBspTree->CollectMergeCandidates(rays, candidates);
-        }
-        else
-        {
-                vector<BspLeaf *> leaves;
-                mBspTree->CollectLeaves(leaves);
-                mBspTree->CollectMergeCandidates(leaves, candidates);
-        }
-
-        cout << "fininshed collecting candidates" << endl;
-}
-
-
-
-bool BspViewCellsManager::ExportViewCells(const string filename, 
-                                                                                  const bool exportPvs, 
-                                                                                  const ObjectContainer &objects)
-{
-        if (!ViewCellsConstructed() || !ViewCellsTreeConstructed())
-        {
-                return false;
-        }
-
-        cout << "exporting view cells to xml ... ";
-
-        OUT_STREAM stream(filename.c_str());
-
-        // for output we need unique ids for each view cell
-        CreateUniqueViewCellIds();
-
-        stream << "<?xml version=\"1.0\" encoding=\"UTF-8\"?>"<<endl;
-        stream << "<VisibilitySolution>" << endl;
-
-        if (exportPvs) 
-        {
-                //////////
-                //-- export bounding boxes: they are used to identify the objects from the pvs and
-                //-- assign them to the entities in the rendering engine
-
-                stream << "<BoundingBoxes>" << endl;
-                ObjectContainer::const_iterator oit, oit_end = objects.end();
-
-                for (oit = objects.begin(); oit != oit_end; ++ oit)
-                {
-                        const AxisAlignedBox3 box = (*oit)->GetBox();
-                        
-                        stream << "<BoundingBox" << " id=\"" << (*oit)->GetId() << "\""
-                                   << " min=\"" << box.Min().x << " " << box.Min().y << " " << box.Min().z << "\""
-                                   << " max=\"" << box.Max().x << " " << box.Max().y << " " << box.Max().z << "\" />" << endl;
-                }
-
-                stream << "</BoundingBoxes>" << endl;
-        }
-
-        ///////////
-        //-- export the view cells and the pvs
-
-        const int numViewCells = mCurrentViewCellsStats.viewCells;
-        stream << "<ViewCells number=\"" << numViewCells << "\" >" << endl;
-
-        mViewCellsTree->Export(stream, exportPvs);
-        
-        stream << "</ViewCells>" << endl;
-
-        /////////////
-        //-- export the view space hierarchy
-        stream << "<ViewSpaceHierarchy type=\"bsp\""
-                   << " min=\"" << mViewSpaceBox.Min().x << " " << mViewSpaceBox.Min().y << " " << mViewSpaceBox.Min().z << "\""
-                   << " max=\"" << mViewSpaceBox.Max().x << " " << mViewSpaceBox.Max().y << " " << mViewSpaceBox.Max().z << "\">" << endl;
-
-        mBspTree->Export(stream);
-
-        // end tags
-        stream << "</ViewSpaceHierarchy>" << endl;
-        stream << "</VisibilitySolution>" << endl;
-
-        stream.close();
-        cout << "finished" << endl;
-
-        return true;
-}
-
-
-ViewCell *BspViewCellsManager::ConstructDummyMergeTree(BspNode *root)
-{
-        ViewCellInterior *vcRoot = new ViewCellInterior();
-                
-        // evaluate merge cost for priority traversal
-        const float mergeCost = 1.0f / (float)root->mTimeStamp;
-        vcRoot->SetMergeCost(mergeCost);
-
-        float volume = 0;
-        vector<BspLeaf *> leaves;
-        mBspTree->CollectLeaves(leaves);
-        vector<BspLeaf *>::const_iterator lit, lit_end = leaves.end();
-        ViewCell::NewMail();
-
-        for (lit = leaves.begin(); lit != lit_end; ++ lit)
-        {
-                BspLeaf *leaf = *lit;
-                ViewCell *vc = leaf->GetViewCell();
-
-                if (!vc->Mailed())
-                {
-                        vc->Mail();
-                        vc->SetMergeCost(0.0f);
-                        vcRoot->SetupChildLink(vc);
-
-                        volume += vc->GetVolume();
-                        volume += vc->GetVolume();      
-                        vcRoot->SetVolume(volume);
-                }
-        }
-        
-        return vcRoot;
-}
-
-
-ViewCell *BspViewCellsManager::ConstructSpatialMergeTree(BspNode *root)
-{
-        // terminate recursion
-        if (root->IsLeaf())
-        {
-                BspLeaf *leaf = dynamic_cast<BspLeaf *>(root);
-                leaf->GetViewCell()->SetMergeCost(0.0f);
-                return leaf->GetViewCell();
-        }
-        
-        BspInterior *interior = dynamic_cast<BspInterior *>(root);
-        ViewCellInterior *viewCellInterior = new ViewCellInterior();
-                
-        // evaluate merge cost for priority traversal
-        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;
-}
-
-
-/************************************************************************/
-/*                   KdViewCellsManager implementation                  */
-/************************************************************************/
-
-
-
-KdViewCellsManager::KdViewCellsManager(ViewCellsTree *vcTree, KdTree *kdTree):
-ViewCellsManager(vcTree), mKdTree(kdTree), mKdPvsDepth(100)
-{
-}
-
-
-float KdViewCellsManager::GetProbability(ViewCell *viewCell)
-{
-        // compute view cell area / volume as subsititute for probability
-        if (0)
-                return GetArea(viewCell) / GetViewSpaceBox().SurfaceArea();
-        else
-                return GetVolume(viewCell) / GetViewSpaceBox().GetVolume();
-}
-
-
-
-
-void KdViewCellsManager::CollectViewCells()
-{
-        //mKdTree->CollectViewCells(mViewCells); TODO
-}
-
-
-int KdViewCellsManager::ConstructSubdivision(const ObjectContainer &objects,
-                                                                  const VssRayContainer &rays)
-{
-        // if view cells already constructed
-        if (ViewCellsConstructed())
-                return 0;
-
-        mKdTree->Construct();
-
-        mTotalAreaValid = false;
-        // create the view cells
-        mKdTree->CreateAndCollectViewCells(mViewCells);
-        // cast rays
-        ComputeSampleContributions(rays, true, false);
-
-        EvaluateViewCellsStats();
-        Debug << "\nView cells after construction:\n" << mCurrentViewCellsStats << endl;
-
-        return 0;
-}
-
-
-bool KdViewCellsManager::ViewCellsConstructed() const
-{
-        return mKdTree->GetRoot() != NULL;
-}
-
-
-int KdViewCellsManager::PostProcess(const ObjectContainer &objects,
-                                                                        const VssRayContainer &rays)
-{
-        return 0;
-}
-
-
-void KdViewCellsManager::ExportSingleViewCells(const ObjectContainer &objects,
-                                                                                           const int maxViewCells,
-                                                                                           const bool sortViewCells,
-                                                                                           const bool exportPvs,
-                                                                                           const bool exportRays,
-                                                                                           const int maxRays,
-                                                                                           const string prefix,
-                                                                                           VssRayContainer *visRays)
-{
-        // TODO
-}
-
-
-void KdViewCellsManager::Visualize(const ObjectContainer &objects,
-                                                                   const VssRayContainer &sampleRays)
-{
-        if (!ViewCellsConstructed())
-                return;
-
-        // using view cells instead of the kd PVS of objects
-        const bool useViewCells = true;
-        bool exportRays = false;
-
-        int limit = min(mVisualizationSamples, (int)sampleRays.size());
-        const int pvsOut = min((int)objects.size(), 10);
-        VssRayContainer *rays = new VssRayContainer[pvsOut];
-
-        if (useViewCells)
-        {
-                const int leafOut = 10;
-
-                ViewCell::NewMail();
-
-                //-- some rays for output
-                const int raysOut = min((int)sampleRays.size(), mVisualizationSamples);
-                Debug << "visualization using " << raysOut << " samples" << endl;
-
-                //-- some random view cells and rays for output
-                vector<KdLeaf *> kdLeaves;
-
-                for (int i = 0; i < leafOut; ++ i)
-                        kdLeaves.push_back(dynamic_cast<KdLeaf *>(mKdTree->GetRandomLeaf()));
-
-                for (int i = 0; i < kdLeaves.size(); ++ i)
-                {
-                        KdLeaf *leaf = kdLeaves[i];
-                        RayContainer vcRays;
-
-                        cout << "creating output for view cell " << i << " ... ";
-#if 0
-                        // check whether we can add the current ray to the output rays
-                        for (int k = 0; k < raysOut; ++ k)
-                        {
-                                Ray *ray = sampleRays[k];
-
-                                for (int j = 0; j < (int)ray->bspIntersections.size(); ++ j)
-                                {
-                                        BspLeaf *leaf2 = ray->bspIntersections[j].mLeaf;
-
-                                        if (leaf->GetViewCell() == leaf2->GetViewCell())
-                                        {
-                                                vcRays.push_back(ray);
-                                        }
-                                }
-                        }
-#endif
-                        Intersectable::NewMail();
-
-                        ViewCell *vc = leaf->mViewCell;
-                        char str[64]; sprintf(str, "viewcell%04d.wrl", i);
-
-                        Exporter *exporter = Exporter::GetExporter(str);
-                        exporter->SetFilled();
-
-                        exporter->SetWireframe();
-                        //exporter->SetFilled();
-
-                        Material m;//= RandomMaterial();
-                        m.mDiffuseColor = RgbColor(1, 1, 0);
-                        exporter->SetForcedMaterial(m);
-
-                        AxisAlignedBox3 box = mKdTree->GetBox(leaf);
-                        exporter->ExportBox(box);
-
-                        // export rays piercing this view cell
-                        exporter->ExportRays(vcRays, 1000, RgbColor(0, 1, 0));
-
-                        m.mDiffuseColor = RgbColor(1, 0, 0);
-                        exporter->SetForcedMaterial(m);
-
-                        // exporter->SetWireframe();
-                        exporter->SetFilled();
-
-                        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 str[64]; sprintf(str, "viewcell%04d.wrl", i);
-
-                        Exporter *exporter = Exporter::GetExporter(str);
-                        exporter->SetWireframe();
-
-                        KdPvsMap::iterator kit = object->mKdPvs.mEntries.begin();
-                        Intersectable::NewMail();
-
-                        // avoid adding the object to the list
-                        object->Mail();
-                        ObjectContainer visibleObjects;
-
-                        for (; kit != object->mKdPvs.mEntries.end(); i++)
-                        {
-                                KdNode *node = (*kit).first;
-                                exporter->ExportBox(mKdTree->GetBox(node));
-
-                                mKdTree->CollectObjects(node, visibleObjects);
-                        }
-
-                        exporter->ExportRays(rays[k],  RgbColor(0, 1, 0));
-                        exporter->SetFilled();
-
-                        for (int j = 0; j < visibleObjects.size(); j++)
-                                exporter->ExportIntersectable(visibleObjects[j]);
-
-                        Material m;
-                        m.mDiffuseColor = RgbColor(1, 0, 0);
-                        exporter->SetForcedMaterial(m);
-                        exporter->ExportIntersectable(object);
-
-                        delete exporter;
-                }
-        }
-}
-
-
-ViewCell *KdViewCellsManager::GenerateViewCell(Mesh *mesh) const
-{
-        return new KdViewCell(mesh);
-}
-
-
-void KdViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
-                                                                                                ViewCell *vc,
-                                                                                                const AxisAlignedBox3 *sceneBox,
-                                                                                                const AxisAlignedPlane *clipPlane
-                                                                                                ) const
-{
-        ViewCellContainer leaves;
-        mViewCellsTree->CollectLeaves(vc, leaves);
-        ViewCellContainer::const_iterator it, it_end = leaves.end();
-
-        for (it = leaves.begin(); it != it_end; ++ it)
-        {
-                KdViewCell *kdVc = dynamic_cast<KdViewCell *>(*it);
-                exporter->ExportBox(mKdTree->GetBox(kdVc->mLeaves[0]));
-        }
-}
-
-
-int KdViewCellsManager::GetType() const
-{
-        return ViewCellsManager::KD;
-}
-
-
-
-KdNode *KdViewCellsManager::GetNodeForPvs(KdLeaf *leaf)
-{
-        KdNode *node = leaf;
-
-        while (node->mParent && node->mDepth > mKdPvsDepth)
-                node = node->mParent;
-
-        return node;
-}
-
-int KdViewCellsManager::CastLineSegment(const Vector3 &origin,
-                                                                                const Vector3 &termination,
-                                                                                ViewCellContainer &viewcells)
-{
-        return mKdTree->CastLineSegment(origin, termination, viewcells);
-}
-
-
-void KdViewCellsManager::CreateMesh(ViewCell *vc)
-{
-        // TODO
-}
-
-
-
-void KdViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays, 
-                                                                                                vector<MergeCandidate> &candidates)
-{
-        // TODO
-}
-
-
-
-/**************************************************************************/
-/*                   VspBspViewCellsManager implementation                */
-/**************************************************************************/
-
-
-VspBspViewCellsManager::VspBspViewCellsManager(ViewCellsTree *vcTree, VspBspTree *vspBspTree):
-ViewCellsManager(vcTree), mVspBspTree(vspBspTree)
-{
-        Environment::GetSingleton()->GetIntValue("VspBspTree.Construction.samples", mInitialSamples);
-        mVspBspTree->SetViewCellsManager(this);
-        mVspBspTree->mViewCellsTree = mViewCellsTree;
-}
-
-
-VspBspViewCellsManager::~VspBspViewCellsManager()
-{
-}
-
-
-float VspBspViewCellsManager::GetProbability(ViewCell *viewCell)
-{
-        if (0 && mVspBspTree->mUseAreaForPvs)
-                return GetArea(viewCell) / GetAccVcArea();
-        else
-                return GetVolume(viewCell) / mViewSpaceBox.GetVolume();
-}
-
-
-void VspBspViewCellsManager::CollectViewCells()
-{
-        // view cells tree constructed?
-        if (!ViewCellsTreeConstructed())
-        {
-                mVspBspTree->CollectViewCells(mViewCells, false);
-        }
-        else 
-        {       
-                // we can use the view cells tree hierarchy to get the right set
-                mViewCellsTree->CollectBestViewCellSet(mViewCells, mNumActiveViewCells);
-        }
-}
-
-
-void VspBspViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays, 
-                                                                                                        vector<MergeCandidate> &candidates)
-{       
-        cout << "collecting merge candidates ... " << endl;
-
-        if (mUseRaysForMerge)
-        {
-                mVspBspTree->CollectMergeCandidates(rays, candidates);
-        }
-        else
-        {
-                vector<BspLeaf *> leaves;
-                mVspBspTree->CollectLeaves(leaves);
-        
-                mVspBspTree->CollectMergeCandidates(leaves, candidates);
-        }
-
-        cout << "fininshed collecting candidates" << endl;
-}
-
-
-bool VspBspViewCellsManager::ViewCellsConstructed() const
-{
-        return mVspBspTree->GetRoot() != NULL;
-}
-
-
-ViewCell *VspBspViewCellsManager::GenerateViewCell(Mesh *mesh) const
-{
-        return new BspViewCell(mesh);
-}
-
-
-int VspBspViewCellsManager::ConstructSubdivision(const ObjectContainer &objects,
-                                                                                                 const VssRayContainer &rays)
-{
-        mMaxPvsSize = (int)(mMaxPvsRatio * (float)objects.size());
-
-        // if view cells were already constructed
-        if (ViewCellsConstructed())
-        {
-                return 0;
-        }
-
-        int sampleContributions = 0;
-        VssRayContainer sampleRays;
-
-        const int limit = min(mInitialSamples, (int)rays.size());
-
-        Debug << "samples used for vsp bsp subdivision: " << mInitialSamples 
-                  << ", actual rays: " << (int)rays.size() << endl;
-
-        VssRayContainer savedRays;
-
-        if (SAMPLE_AFTER_SUBDIVISION)
-        {
-                VssRayContainer constructionRays;
-                
-                GetRaySets(rays, mInitialSamples, constructionRays, &savedRays);
-
-                Debug << "rays used for initial construction: " << (int)constructionRays.size() << endl;
-                Debug << "rays saved for later use: " << (int)savedRays.size() << endl;
-        
-                mVspBspTree->Construct(constructionRays, &mViewSpaceBox);
-        }
-        else
-        {
-                Debug << "rays used for initial construction: " << (int)rays.size() << endl;
-                mVspBspTree->Construct(rays, &mViewSpaceBox);
-        }
-
-        // collapse invalid regions
-        cout << "collapsing invalid tree regions ... ";
-        long startTime = GetTime();
-
-        const int collapsedLeaves = mVspBspTree->CollapseTree();
-        Debug << "collapsed in " << TimeDiff(startTime, GetTime()) * 1e-3 
-                  << " seconds" << endl;
-
-    cout << "finished" << endl;
-
-        /////////////////
-        //-- stats after construction
-
-        Debug << mVspBspTree->GetStatistics() << endl;
-
-        ResetViewCells();
-        Debug << "\nView cells after construction:\n" << mCurrentViewCellsStats << endl;
-
-
-        //////////////////////
-        //-- recast the rest of the rays
-
-        startTime = GetTime();
-
-        cout << "Computing remaining ray contributions ... ";
-
-        if (SAMPLE_AFTER_SUBDIVISION)
-                ComputeSampleContributions(savedRays, true, false);
-
-        cout << "finished" << endl;
-
-        Debug << "Computed remaining ray contribution in " << TimeDiff(startTime, GetTime()) * 1e-3
-                  << " secs" << endl;
-
-        cout << "construction finished" << endl;
-
-        if (0)
-        {       ////////
-                //-- real meshes are contructed at this stage
-                cout << "finalizing view cells ... ";
-                FinalizeViewCells(true);
-                cout << "finished" << endl;
-        }
-
-        return sampleContributions;
-}
-
-
-void VspBspViewCellsManager::MergeViewCells(const VssRayContainer &rays,
-                                                                                        const ObjectContainer &objects)
-{
-    int vcSize = 0;
-        int pvsSize = 0;
-
-        //-- merge view cells
-        cout << "starting merge using " << mPostProcessSamples << " samples ... " << endl;
-        long startTime = GetTime();
-
-
-        if (mMergeViewCells)
-        {
-                // TODO: should be done BEFORE the ray casting
-                // compute tree by merging the nodes based on cost heuristics
-                mViewCellsTree->ConstructMergeTree(rays, objects);
-        }
-        else
-        {
-                // compute tree by merging the nodes of the spatial hierarchy
-                ViewCell *root = ConstructSpatialMergeTree(mVspBspTree->GetRoot());
-                mViewCellsTree->SetRoot(root);
-
-                // compute pvs
-                ObjectPvs pvs;
-                UpdatePvsForEvaluation(root, pvs);
-        }
-
-        if (1)
-        {
-                char mstats[100];
-                ObjectPvs pvs;
-
-                Environment::GetSingleton()->GetStringValue("ViewCells.mergeStats", mstats);
-                mViewCellsTree->ExportStats(mstats);
-        }
-
-        cout << "merged view cells in "
-                 << TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl;
-
-        Debug << "Postprocessing: Merged view cells in "
-                  << TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl << endl;
-        
-
-        //////////////////
-        //-- stats and visualizations
-
-        int savedColorCode = mColorCode;
-        
-        // get currently active view cell set
-        ResetViewCells();
-        Debug << "\nView cells after merge:\n" << mCurrentViewCellsStats << endl;
-        
-        if (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, NULL, GetClipPlane());
-
-                        if (mExportGeometry)
-                        {
-                                Material m;
-                                m.mDiffuseColor = RgbColor(0, 1, 0);
-                                exporter->SetForcedMaterial(m);
-                                exporter->SetFilled();
-
-                                exporter->ExportGeometry(objects);
-                        }
-
-                        delete exporter;
-                }
-                cout << "finished" << endl;
-        }
-
-        if (1) 
-        {
-                // use pvs size for color coding
-                mColorCode = 1;
-                Exporter *exporter = Exporter::GetExporter("merged_view_cells_pvs.wrl");
-
-                cout << "exporting view cells after merge (pvs size) ... ";     
-
-                if (exporter)
-                {
-                        exporter->SetFilled();
-
-                        ExportViewCellsForViz(exporter, NULL, GetClipPlane());
-
-                        if (mExportGeometry)
-                        {
-                                Material m;
-                                m.mDiffuseColor = RgbColor(0, 1, 0);
-                                exporter->SetForcedMaterial(m);
-                                exporter->SetFilled();
-
-                                exporter->ExportGeometry(objects);
-                        }
-
-                        delete exporter;
-                }
-                cout << "finished" << endl;
-        }
-
-        mColorCode = savedColorCode;
-
-}
-
-
-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->mLeaves[0];
-        }
-        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)
-{
-        mRenderer->RenderScene();
-        SimulationStatistics ss;
-        dynamic_cast<RenderSimulator *>(mRenderer)->GetStatistics(ss);
-    Debug << "render time before refine\n\n" << ss << endl;
-
-        const long startTime = GetTime();
-        cout << "Refining the merged view cells ... ";
-
-        // refining the merged view cells
-        const int refined = mViewCellsTree->RefineViewCells(rays, objects);
-
-        //-- stats and visualizations
-        cout << "finished" << endl;
-        cout << "refined " << refined << " view cells in "
-                 << TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl;
-
-        Debug << "Postprocessing: refined " << refined << " view cells in "
-                  << TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl << endl;
-}
-
-
-int VspBspViewCellsManager::PostProcess(const ObjectContainer &objects,
-                                                                                const VssRayContainer &rays)
-{
-        if (!ViewCellsConstructed())
-        {
-                Debug << "postprocess error: no view cells constructed" << endl;
-                return 0;
-        }
-
-        // view cells already finished before post processing step 
-        // (i.e. because they were loaded)
-        if (mViewCellsFinished)
-        {
-                FinalizeViewCells(true);
-                EvaluateViewCellsStats();
-
-                return 0;
-        }
-
-        // check if new view cells turned invalid
-        int minPvs, maxPvs;
-
-        if (0)
-        {
-                minPvs = mMinPvsSize;
-                maxPvs = mMaxPvsSize;
-        }
-        else
-        {
-                // problem matt: why did I start here from zero?
-                minPvs = 0;
-                maxPvs = mMaxPvsSize;
-        }
-
-        Debug << "setting validity, min: " << minPvs << " max: " << maxPvs << endl;
-        cout << "setting validity, min: " << minPvs << " max: " << maxPvs << endl;
-        
-        SetValidity(minPvs, maxPvs); 
-
-        // update valid view space according to valid view cells
-        if (0) mVspBspTree->ValidateTree();
-
-        // area has to be recomputed
-        mTotalAreaValid = false;
-        VssRayContainer postProcessRays;
-        GetRaySets(rays, mPostProcessSamples, postProcessRays);
-
-        Debug << "post processing using " << (int)postProcessRays.size() << " samples" << endl;
-
-        // 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);
-        
-        // refines the merged view cells
-        if (0) RefineViewCells(postProcessRays, objects);
-
-
-        ///////////
-        //-- render simulation after merge + refine
-
-        cout << "\nview cells partition render time before compress" << endl << endl;;
-        dynamic_cast<RenderSimulator *>(mRenderer)->RenderScene();
-        SimulationStatistics ss;
-        dynamic_cast<RenderSimulator *>(mRenderer)->GetStatistics(ss);
-        cout << ss << endl;
-        
-
-        ////////////
-        //-- compression
-
-        if (ViewCellsTreeConstructed() && mCompressViewCells)
-        {
-                int pvsEntries = mViewCellsTree->GetStoredPvsEntriesNum(mViewCellsTree->GetRoot());
-                Debug << "number of entries before compress: " << pvsEntries << endl;
-
-                mViewCellsTree->SetViewCellsStorage(ViewCellsTree::COMPRESSED);
-
-                pvsEntries = mViewCellsTree->GetStoredPvsEntriesNum(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 (1 && mExportViewCells)
-        {
-                char filename[100];
-                Environment::GetSingleton()->GetStringValue("ViewCells.filename", filename);
-                ExportViewCells(filename, mExportPvs, 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;
-}
-
-
-bool VspBspViewCellsManager::GetViewPoint(Vector3 &viewPoint) const
-{
-        if (!ViewCellsConstructed())
-                return ViewCellsManager::GetViewPoint(viewPoint);
-
-        // TODO: set reasonable limit
-        const int limit = 20;
-
-        for (int i = 0; i < limit; ++ i)
-        {
-                viewPoint = mViewSpaceBox.GetRandomPoint();
-                if (mVspBspTree->ViewPointValid(viewPoint))
-                {
-                        return true;
-                }
-        }
-
-        Debug << "failed to find valid view point, taking " << viewPoint << endl;
-        return false;
-}
-
-
-bool VspBspViewCellsManager::ViewPointValid(const Vector3 &viewPoint) const
-{
-        // $$JB -> implemented in viewcellsmanager (slower, but allows dynamic
-        // validy update in preprocessor for all managers)
-        return ViewCellsManager::ViewPointValid(viewPoint);
-
-        //      return mViewSpaceBox.IsInside(viewPoint) &&
-        //                 mVspBspTree->ViewPointValid(viewPoint);
-}
-
-
-void VspBspViewCellsManager::Visualize(const ObjectContainer &objects,
-                                                                           const VssRayContainer &sampleRays)
-{
-        if (!ViewCellsConstructed())
-                return;
-
-        VssRayContainer visRays;
-        GetRaySets(sampleRays, mVisualizationSamples, visRays);
-        
-        if (1) 
-        {       
-                //////////////////
-                //-- export final view cell partition
-
-                Exporter *exporter = Exporter::GetExporter("final_view_cells.wrl");
-                
-                if (exporter)
-                {
-                        cout << "exporting view cells after post process ... ";
-                        if (0)
-                        {       // export view space box
-                                exporter->SetWireframe();
-                                exporter->ExportBox(mViewSpaceBox);
-                                exporter->SetFilled();
-                        }
-
-                        Material m; 
-                        m.mDiffuseColor.r = 0.0f;
-                        m.mDiffuseColor.g = 0.5f;
-                        m.mDiffuseColor.b = 0.5f;
-
-            exporter->SetForcedMaterial(m);
-
-                        if (1 && mExportGeometry)
-                        {
-                                exporter->ExportGeometry(objects);
-                        }
-
-                        if (0 && mExportRays)
-                        {
-                                exporter->ExportRays(visRays, RgbColor(1, 0, 0));
-                        }
-                        ExportViewCellsForViz(exporter, NULL, GetClipPlane());
-
-                        delete exporter;
-                        cout << "finished" << endl;
-                }
-        }
-
-        ////////////////
-        //-- visualization of the BSP splits
-
-        bool exportSplits = false;
-        Environment::GetSingleton()->GetBoolValue("VspBspTree.Visualization.exportSplits", exportSplits);
-
-        if (exportSplits)
-        {
-                cout << "exporting splits ... ";
-                ExportSplits(objects, visRays);
-                cout << "finished" << endl;
-        }
-
-        ////////
-        //-- export single view cells
-        
-        int leafOut;
-        Environment::GetSingleton()->GetIntValue("ViewCells.Visualization.maxOutput", leafOut);
-        const int raysOut = 100;
-        
-        ExportSingleViewCells(objects, leafOut, false, true, false, raysOut, "");
-}
-
-
-void VspBspViewCellsManager::ExportSplits(const ObjectContainer &objects,
-                                                                                  const VssRayContainer &rays)
-{
-        Exporter *exporter = Exporter::GetExporter("bsp_splits.x3d");
-
-        if (exporter)
-        {
-                Material m;
-                m.mDiffuseColor = RgbColor(1, 0, 0);
-                exporter->SetForcedMaterial(m);
-                exporter->SetWireframe();
-
-                exporter->ExportBspSplits(*mVspBspTree, true);
-
-                // take forced material, else big scenes cannot be viewed
-                m.mDiffuseColor = RgbColor(0, 1, 0);
-                exporter->SetForcedMaterial(m);
-                exporter->SetFilled();
-
-                exporter->ResetForcedMaterial();
-
-                // export rays
-                if (mExportRays)
-                {
-                        exporter->ExportRays(rays, RgbColor(1, 1, 0));
-                }
-
-                if (mExportGeometry)
-                {
-                        exporter->ExportGeometry(objects);
-                }
-                delete exporter;
-        }
-}
-
-
-void VspBspViewCellsManager::ExportSingleViewCells(const ObjectContainer &objects,
-                                                                                                   const int maxViewCells,
-                                                                                                   const bool sortViewCells,
-                                                                                                   const bool exportPvs,
-                                                                                                   const bool exportRays,
-                                                                                                   const int maxRays,
-                                                                                                   const string prefix,
-                                                                                                   VssRayContainer *visRays)
-{       
-        if (sortViewCells)
-        {
-                // sort view cells to visualize the largest view cells
-                stable_sort(mViewCells.begin(), mViewCells.end(), ViewCell::LargerRenderCost);
-        }
-
-        //////////
-        //-- some view cells for output
-
-        ViewCell::NewMail();
-        const int limit = min(maxViewCells, (int)mViewCells.size());
-        
-        for (int i = 0; i < limit; ++ i)
-        {
-                cout << "creating output for view cell " << i << " ... ";
-
-                ViewCell *vc = sortViewCells ? // largest view cell pvs first?
-                        mViewCells[(int)RandomValue(0, (float)mViewCells.size() - 0.5f)] : mViewCells[i];
-
-                if (vc->Mailed() || vc->GetId() == OUT_OF_BOUNDS_ID)
-                        continue;
-
-                vc->Mail();
-
-                ObjectPvs pvs;
-                mViewCellsTree->GetPvs(vc, pvs);
-
-                char s[64]; sprintf(s, "%sviewcell%04d.wrl", prefix.c_str(), i);
-                Exporter *exporter = Exporter::GetExporter(s);
-                
-                cout << "view cell " << vc->GetId() << ": pvs size=" << (int)mViewCellsTree->GetPvsSize(vc) << endl;
-
-                if (exportRays)
-                {
-                        ////////////
-                        //-- export rays piercing this view cell
-
-                        // take rays stored with the view cells during subdivision
-                        VssRayContainer vcRays;
-            VssRayContainer collectRays;
-
-                        // collect initial view cells
-                        ViewCellContainer leaves;
-                        mViewCellsTree->CollectLeaves(vc, leaves);
-
-                        ViewCellContainer::const_iterator vit, vit_end = leaves.end();
-                for (vit = leaves.begin(); vit != vit_end; ++ vit)
-                        {       
-                                BspLeaf *vcLeaf = dynamic_cast<BspViewCell *>(*vit)->mLeaves[0];
-                                VssRayContainer::const_iterator rit, rit_end = vcLeaf->mVssRays.end();
-
-                                for (rit = vcLeaf->mVssRays.begin(); rit != rit_end; ++ rit)
-                                {
-                                        collectRays.push_back(*rit);
-                                }
-                        }
-
-                        const int raysOut = min((int)collectRays.size(), maxRays);
-                        cout << "here500 " << raysOut << endl;
-                        // prepare some rays for output
-                        VssRayContainer::const_iterator rit, rit_end = collectRays.end();
-                        for (rit = collectRays.begin(); rit != rit_end; ++ rit)
-                        {
-                                const float p = RandomValue(0.0f, (float)collectRays.size());
-                        
-                                if (p < raysOut)
-                                {
-                                        vcRays.push_back(*rit);
-                                }
-                        }
-
-                        exporter->ExportRays(vcRays, RgbColor(1, 1, 1));
-                }
-                
-                ////////////////
-                //-- export view cell geometry
-
-                exporter->SetWireframe();
-
-                Material m;//= RandomMaterial();
-                m.mDiffuseColor = RgbColor(0, 1, 0);
-                exporter->SetForcedMaterial(m);
-
-                ExportViewCellGeometry(exporter, vc, NULL, NULL);
-                exporter->SetFilled();
-
-                if (exportPvs)
-                {
-                        Intersectable::NewMail();
-
-                        ObjectPvsMap::const_iterator oit, oit_end = pvs.mEntries.end();
-                        cout << endl;
-                        // output PVS of view cell
-                        for (oit = pvs.mEntries.begin(); oit != oit_end; ++ oit)
-                        {               
-                                Intersectable *intersect = (*oit).first;
-                                
-                                if (!intersect->Mailed())
-                                {
-                                        intersect->Mail();
-                                        m = RandomMaterial();
-                                        exporter->SetForcedMaterial(m);
-                                        exporter->ExportIntersectable(intersect);
-                                        cout << " i: " << intersect;
                                 }
                         }
@@ -5562 +5573 @@
 }
 
+//#define TEST_EVALUATION
 
 #if TEST_EVALUATION

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

@@ -586 +586 @@
                 Exporter *exporter, 
                 const AxisAlignedBox3 *box,
-                const AxisAlignedPlane *clipPlane = NULL) const;
+                const AxisAlignedPlane *clipPlane = NULL,
+                const bool colorCode = 0) const;
 
         /** Sets exporter color.
         */
-        virtual void ExportColor(Exporter *exporter, ViewCell *vc) const;
+        virtual void ExportColor(Exporter *exporter, ViewCell *vc, const bool colorCode) const;
         
         /** Creates meshes from the view cells.

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

@@ -107 +107 @@
         stream << "}" << endl; // end material
         stream << "}" << endl; // end appearance
-
         stream << "geometry IndexedLineSet { coordIndex [" << endl;
 
@@ -120 +119 @@
 
         stream << "]" << endl;
-
         stream << "coord Coordinate { point [" << endl;
 
@@ -152 +150 @@
         stream << "}" << endl;
         stream << "}" << endl;
-        //stream << "}" << endl;
 
         return true;

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

@@ -599 +599 @@
                 // || mOutOfMemory
                 || (mVspStats.Leaves() >= mMaxViewCells)
-      //  || (mVspStats.mGlobalCostMisses >= mTermGlobalCostMissTolerance) 
+                // does not really make sense because cost termination already in hierarchy
+                // || (mVspStats.mGlobalCostMisses >= mTermGlobalCostMissTolerance) 
                 );
 
-        if (1 && terminationCriteriaMet)
+        if (0 && terminationCriteriaMet)
         {
                 Debug << "vsp global termination criteria met:" << endl;

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

@@ -24 +24 @@
     FPosDirZ = 4,    // the direction of ray in Z-axis is positive
         BorderSample = 8,// if this ray is an adaptive border ray
-        ReverserRay = 16 // if this ray is a reverse sample
+        ReverseSample = 16  // if this ray is a reverse sample
   };