Changeset 1006 for GTP/trunk/Lib/Vis/Preprocessing/src/VspOspTree.cpp

Timestamp:

06/09/06 01:26:46 (18 years ago)

Author:

mattausch

Message:

started viewspace-objectspace subdivision
removed memory leaks

File:

• GTP/trunk/Lib/Vis/Preprocessing/src/VspOspTree.cpp (modified) (64 diffs)

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

@@ -4 +4 @@
 
 #include "Plane3.h"
-#include "VspBspTree.h"
+#include "VspOspTree.h"
 #include "Mesh.h"
 #include "common.h"
@@ -25 +25 @@
 //-- static members
 
-
-int VspBspTree::sFrontId = 0;
-int VspBspTree::sBackId = 0;
-int VspBspTree::sFrontAndBackId = 0;
-
-typedef pair<BspNode *, BspNodeGeometry *> bspNodePair;
+int VspOspTree::sFrontId = 0;
+int VspOspTree::sBackId = 0;
+int VspOspTree::sFrontAndBackId = 0;
+
 
 
@@ -51 +49 @@
 
 /******************************************************************************/
-/*                       class VspBspTree implementation                      */
+/*                       class VspOspTree implementation                      */
 /******************************************************************************/
 
 
-VspBspTree::VspBspTree(Environment *env):
+VspOspTree::VspOspTree():
 mRoot(NULL),
-mUseAreaForPvs(false),
-mCostNormalizer(Limits::Small),
-mViewCellsManager(NULL),
 mOutOfBoundsCell(NULL),
 mStoreRays(false),
-mRenderCostWeight(0.5),
 mUseRandomAxis(false),
 mTimeStamp(1)
 {
         bool randomize = false;
-        env->GetBoolValue("VspBspTree.Construction.randomize", randomize);
+        Environment::GetSingleton()->GetBoolValue("VspOspTree.Construction.randomize", randomize);
         if (randomize)
                 Randomize(); // initialise random generator for heuristics
 
         //-- termination criteria for autopartition
-        env->GetIntValue("VspBspTree.Termination.maxDepth", mTermMaxDepth);
-        env->GetIntValue("VspBspTree.Termination.minPvs", mTermMinPvs);
-        env->GetIntValue("VspBspTree.Termination.minRays", mTermMinRays);
-        env->GetFloatValue("VspBspTree.Termination.minProbability", mTermMinProbability);
-        env->GetFloatValue("VspBspTree.Termination.maxRayContribution", mTermMaxRayContribution);
-        env->GetFloatValue("VspBspTree.Termination.minAccRayLenght", mTermMinAccRayLength);
-        env->GetFloatValue("VspBspTree.Termination.maxCostRatio", mTermMaxCostRatio);
-        env->GetIntValue("VspBspTree.Termination.missTolerance", mTermMissTolerance);
-        env->GetIntValue("VspBspTree.Termination.maxViewCells", mMaxViewCells);
+        Environment::GetSingleton()->GetIntValue("VspOspTree.Termination.maxDepth", mTermMaxDepth);
+        Environment::GetSingleton()->GetIntValue("VspOspTree.Termination.minPvs", mTermMinPvs);
+        Environment::GetSingleton()->GetIntValue("VspOspTree.Termination.minRays", mTermMinRays);
+        Environment::GetSingleton()->GetFloatValue("VspOspTree.Termination.minProbability", mTermMinProbability);
+        Environment::GetSingleton()->GetFloatValue("VspOspTree.Termination.maxRayContribution", mTermMaxRayContribution);
+        Environment::GetSingleton()->GetFloatValue("VspOspTree.Termination.maxCostRatio", mTermMaxCostRatio);
+        Environment::GetSingleton()->GetIntValue("VspOspTree.Termination.missTolerance", mTermMissTolerance);
+        Environment::GetSingleton()->GetIntValue("VspOspTree.Termination.maxViewCells", mMaxViewCells);
 
         //-- max cost ratio for early tree termination
-        env->GetFloatValue("VspBspTree.Termination.maxCostRatio", mTermMaxCostRatio);
-
-        env->GetFloatValue("VspBspTree.Termination.minGlobalCostRatio", mTermMinGlobalCostRatio);
-        env->GetIntValue("VspBspTree.Termination.globalCostMissTolerance", mTermGlobalCostMissTolerance);
+        Environment::GetSingleton()->GetFloatValue("VspOspTree.Termination.maxCostRatio", mTermMaxCostRatio);
+
+        Environment::GetSingleton()->GetFloatValue("VspOspTree.Termination.minGlobalCostRatio", mTermMinGlobalCostRatio);
+        Environment::GetSingleton()->GetIntValue("VspOspTree.Termination.globalCostMissTolerance", mTermGlobalCostMissTolerance);
 
         // HACK//mTermMinPolygons = 25;
 
         //-- factors for bsp tree split plane heuristics
-        env->GetFloatValue("VspBspTree.Factor.pvs", mPvsFactor);
-        env->GetFloatValue("VspBspTree.Termination.ct_div_ci", mCtDivCi);
-
+        Environment::GetSingleton()->GetFloatValue("VspOspTree.Termination.ct_div_ci", mCtDivCi);
 
         //-- partition criteria
-        env->GetIntValue("VspBspTree.maxPolyCandidates", mMaxPolyCandidates);
-        env->GetIntValue("VspBspTree.maxRayCandidates", mMaxRayCandidates);
-        env->GetIntValue("VspBspTree.splitPlaneStrategy", mSplitPlaneStrategy);
-
-        env->GetFloatValue("VspBspTree.Construction.epsilon", mEpsilon);
-        env->GetIntValue("VspBspTree.maxTests", mMaxTests);
+        Environment::GetSingleton()->GetFloatValue("VspOspTree.Construction.epsilon", mEpsilon);
 
         // if only the driving axis is used for axis aligned split
-        env->GetBoolValue("VspBspTree.splitUseOnlyDrivingAxis", mOnlyDrivingAxis);
-        
-        //-- termination criteria for axis aligned split
-        env->GetFloatValue("VspBspTree.Termination.AxisAligned.maxRayContribution", 
-                                                                mTermMaxRayContriForAxisAligned);
-        env->GetIntValue("VspBspTree.Termination.AxisAligned.minRays",
-                                                         mTermMinRaysForAxisAligned);
-
-        //env->GetFloatValue("VspBspTree.maxTotalMemory", mMaxTotalMemory);
-        env->GetFloatValue("VspBspTree.maxStaticMemory", mMaxMemory);
-
-        env->GetFloatValue("VspBspTree.Construction.renderCostWeight", mRenderCostWeight);
-        env->GetBoolValue("VspBspTree.usePolygonSplitIfAvailable", mUsePolygonSplitIfAvailable);
-
-        env->GetBoolValue("VspBspTree.useCostHeuristics", mUseCostHeuristics);
-        env->GetBoolValue("VspBspTree.useSplitCostQueue", mUseSplitCostQueue);
-        env->GetBoolValue("VspBspTree.simulateOctree", mCirculatingAxis);
-        env->GetBoolValue("VspBspTree.useRandomAxis", mUseRandomAxis);
-        env->GetIntValue("VspBspTree.nodePriorityQueueType", mNodePriorityQueueType);
-
-        env->GetBoolValue("ViewCells.PostProcess.emptyViewCellsMerge", mEmptyViewCellsMergeAllowed);
+        Environment::GetSingleton()->GetBoolValue("VspOspTree.splitUseOnlyDrivingAxis", mOnlyDrivingAxis);
+        
+        //Environment::GetSingleton()->GetFloatValue("VspOspTree.maxTotalMemory", mMaxTotalMemory);
+        Environment::GetSingleton()->GetFloatValue("VspOspTree.maxStaticMemory", mMaxMemory);
+
+        Environment::GetSingleton()->GetBoolValue("VspOspTree.useCostHeuristics", mUseCostHeuristics);
+        Environment::GetSingleton()->GetBoolValue("VspOspTree.simulateOctree", mCirculatingAxis);
+        Environment::GetSingleton()->GetBoolValue("VspOspTree.useRandomAxis", mUseRandomAxis);
+        Environment::GetSingleton()->GetIntValue("VspOspTree.nodePriorityQueueType", mNodePriorityQueueType);
         
         char subdivisionStatsLog[100];
-        env->GetStringValue("VspBspTree.subdivisionStats", subdivisionStatsLog);
+        Environment::GetSingleton()->GetStringValue("VspOspTree.subdivisionStats", subdivisionStatsLog);
         mSubdivisionStats.open(subdivisionStatsLog);
 
-        env->GetFloatValue("VspBspTree.Construction.minBand", mMinBand);
-        env->GetFloatValue("VspBspTree.Construction.maxBand", mMaxBand);
-        env->GetBoolValue("VspBspTree.Construction.useDrivingAxisForMaxCost", mUseDrivingAxisForMaxCost);
+        Environment::GetSingleton()->GetFloatValue("VspOspTree.Construction.minBand", mMinBand);
+        Environment::GetSingleton()->GetFloatValue("VspOspTree.Construction.maxBand", mMaxBand);
+        
 
         //-- debug output
@@ -145 +119 @@
         Debug << "miss tolerance: " << mTermMissTolerance << endl;
         Debug << "max view cells: " << mMaxViewCells << endl;
-        Debug << "max polygon candidates: " << mMaxPolyCandidates << endl;
-        //Debug << "max plane candidates: " << mMaxRayCandidates << endl;
         Debug << "randomize: " << randomize << endl;
 
-        Debug << "using area for pvs: " << mUseAreaForPvs << endl;
-        Debug << "render cost weight: " << mRenderCostWeight << endl;
         Debug << "min global cost ratio: " << mTermMinGlobalCostRatio << endl;
         Debug << "global cost miss tolerance: " << mTermGlobalCostMissTolerance << endl;
         Debug << "only driving axis: " << mOnlyDrivingAxis << endl;
         Debug << "max memory: " << mMaxMemory << endl;
-        Debug << "use poly split if available: " << mUsePolygonSplitIfAvailable << endl;
         Debug << "use cost heuristics: " << mUseCostHeuristics << endl;
-        Debug << "use split cost queue: " << mUseSplitCostQueue << endl;
         Debug << "subdivision stats log: " << subdivisionStatsLog << endl;
         Debug << "use random axis: " << mUseRandomAxis << endl;
         Debug << "priority queue type: " << mNodePriorityQueueType << endl;
-        Debug << "empty view cells merge: " << mEmptyViewCellsMergeAllowed << endl;
         Debug << "circulating axis: " << mCirculatingAxis << endl;
         Debug << "minband: " << mMinBand << endl;
         Debug << "maxband: " << mMaxBand << endl;
-        Debug << "use driving axis for max cost: " << mUseDrivingAxisForMaxCost << endl;
-
-        Debug << "Split plane strategy: ";
-
-        if (mSplitPlaneStrategy & RANDOM_POLYGON)
-        {
-                Debug << "random polygon ";
-        }
-        if (mSplitPlaneStrategy & AXIS_ALIGNED)
-        {
-                Debug << "axis aligned ";
-        }
-        if (mSplitPlaneStrategy & LEAST_RAY_SPLITS)
-        {
-                mCostNormalizer += mLeastRaySplitsFactor;
-                Debug << "least ray splits ";
-        }
-        if (mSplitPlaneStrategy & BALANCED_RAYS)
-        {
-                mCostNormalizer += mBalancedRaysFactor;
-                Debug << "balanced rays ";
-        }
-        if (mSplitPlaneStrategy & PVS)
-        {
-                mCostNormalizer += mPvsFactor;
-                Debug << "pvs";
-        }
-
+        
 
         mSplitCandidates = new vector<SortableEntry>;
@@ -199 +139 @@
 }
 
-VspBspTree::VspBspTree():
-mRoot(NULL),
-mUseAreaForPvs(false),
-mCostNormalizer(Limits::Small),
-mViewCellsManager(NULL),
-mOutOfBoundsCell(NULL),
-mStoreRays(false),
-mRenderCostWeight(0.5),
-mUseRandomAxis(false),
-mTimeStamp(1),
-mEpsilon(1e-6f)
-{
-}
-
-BspViewCell *VspBspTree::GetOutOfBoundsCell()
+
+BspViewCell *VspOspTree::GetOutOfBoundsCell()
 {
         return mOutOfBoundsCell;
@@ -219 +146 @@
 
 
-BspViewCell *VspBspTree::GetOrCreateOutOfBoundsCell()
+BspViewCell *VspOspTree::GetOrCreateOutOfBoundsCell()
 {
         if (!mOutOfBoundsCell)
@@ -232 +159 @@
 
 
-const BspTreeStatistics &VspBspTree::GetStatistics() const
+const BspTreeStatistics &VspOspTree::GetStatistics() const
 {
         return mBspStats;
@@ -238 +165 @@
 
 
-VspBspTree::~VspBspTree()
+VspOspTree::~VspOspTree()
 {
         DEL_PTR(mRoot);
@@ -244 +171 @@
 }
 
-
-int VspBspTree::AddMeshToPolygons(Mesh *mesh,
-                                                                  PolygonContainer &polys,
-                                                                  MeshInstance *parent)
-{
-        FaceContainer::const_iterator fi;
-
-        // copy the face data to polygons
-        for (fi = mesh->mFaces.begin(); fi != mesh->mFaces.end(); ++ fi)
-        {
-                Polygon3 *poly = new Polygon3((*fi), mesh);
-
-                if (poly->Valid(mEpsilon))
-                {
-                        poly->mParent = parent; // set parent intersectable
-                        polys.push_back(poly);
-                }
-                else
-                        DEL_PTR(poly);
-        }
-        return (int)mesh->mFaces.size();
-}
-
-
-int VspBspTree::AddToPolygonSoup(const ViewCellContainer &viewCells,
-                                                                 PolygonContainer &polys,
-                                                                 int maxObjects)
-{
-        int limit = (maxObjects > 0) ?
-                Min((int)viewCells.size(), maxObjects) : (int)viewCells.size();
-
-        int polysSize = 0;
-
-        for (int i = 0; i < limit; ++ i)
-        {
-                if (viewCells[i]->GetMesh()) // copy the mesh data to polygons
-                {
-                        mBox.Include(viewCells[i]->GetBox()); // add to BSP tree aabb
-                        polysSize +=
-                                AddMeshToPolygons(viewCells[i]->GetMesh(),
-                                                                  polys,
-                                                                  viewCells[i]);
-                }
-        }
-
-        return polysSize;
-}
-
-
-int VspBspTree::AddToPolygonSoup(const ObjectContainer &objects,
-                                                                 PolygonContainer &polys,
-                                                                 int maxObjects)
-{
-        int limit = (maxObjects > 0) ?
-                Min((int)objects.size(), maxObjects) : (int)objects.size();
-
-        for (int i = 0; i < limit; ++i)
-        {
-                Intersectable *object = objects[i];//*it;
-                Mesh *mesh = NULL;
-
-                switch (object->Type()) // extract the meshes
-                {
-                case Intersectable::MESH_INSTANCE:
-                        mesh = dynamic_cast<MeshInstance *>(object)->GetMesh();
-                        break;
-                case Intersectable::VIEW_CELL:
-                        mesh = dynamic_cast<ViewCell *>(object)->GetMesh();
-                        break;
-                case Intersectable::TRANSFORMED_MESH_INSTANCE:
-                        {
-                                TransformedMeshInstance *mi = dynamic_cast<TransformedMeshInstance *>(object);
-
-                                if (!mi->GetMesh())
-                                        break;
-
-                                mesh = new Mesh(*mi->GetMesh());
-
-                                Matrix4x4 m;
-                                mi->GetWorldTransform(m);
-
-                                mesh->ApplyTransformation(m);
-
-                break;
-                        }
-                default:
-                        Debug << "intersectable type not supported" << endl;
-                        break;
-                }
-
-        if (mesh) // copy the mesh data to polygons
-                {
-                        mBox.Include(object->GetBox()); // add to BSP tree aabb
-                        AddMeshToPolygons(mesh, polys, NULL);
-
-                        // cleanup
-                        if (object->Type() == Intersectable::TRANSFORMED_MESH_INSTANCE)
-                                DEL_PTR(mesh);
-                }
-        }
-
-        return (int)polys.size();
-}
-
-
-void VspBspTree::Construct(const VssRayContainer &sampleRays,
+void VspOspTree::Construct(const VssRayContainer &sampleRays,
                                                    AxisAlignedBox3 *forcedBoundingBox)
 {
@@ -371 +193 @@
         int numObj = 0;
 
-        //-- extract polygons intersected by the rays
-        for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
-        {
-                VssRay *ray = *rit;
-
-                if ((mBox.IsInside(ray->mTermination) || !forcedBoundingBox) &&
-                        ray->mTerminationObject && 
-                        !ray->mTerminationObject->Mailed())
-                {
-                        ray->mTerminationObject->Mail();
-                        MeshInstance *obj = dynamic_cast<MeshInstance *>(ray->mTerminationObject);
-                        AddMeshToPolygons(obj->GetMesh(), polys, obj);
-                        ++ numObj;
-
-                        //-- compute bounding box
-                        if (!forcedBoundingBox)
-                                mBox.Include(ray->mTermination);
-                }
-
-                if ((mBox.IsInside(ray->mOrigin) || !forcedBoundingBox) &&
-                        ray->mOriginObject && 
-                        !ray->mOriginObject->Mailed())
-                {
-                        ray->mOriginObject->Mail();
-                        MeshInstance *obj = dynamic_cast<MeshInstance *>(ray->mOriginObject);
-                        AddMeshToPolygons(obj->GetMesh(), polys, obj);
-                        ++ numObj;
-
-                        //-- compute bounding box
-                        if (!forcedBoundingBox)
-                                mBox.Include(ray->mOrigin);
-                }
-        }
-        
-        Debug << "maximal pvs (i.e., pvs still considered as valid) : " 
-                  << mViewCellsManager->GetMaxPvsSize() << endl;
-
         //-- store rays
         for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
@@ -430 +215 @@
         }
 
-        // normalize
-        if (mUseAreaForPvs)
-                mTermMinProbability *= mBox.SurfaceArea(); 
-        else 
-                mTermMinProbability *= mBox.GetVolume();
-
-        // throw out unnecessary polygons
-        PreprocessPolygons(polys);
-
-        mBspStats.polys = (int)polys.size();
+        mTermMinProbability *= mBox.GetVolume();
+
         mGlobalCostMisses = 0;
 
         cout << "finished" << endl;
 
-        Debug << "\nPolygon extraction: " << (int)polys.size() << " polys extracted from "
-                  << (int)sampleRays.size() << " rays in "
-                  << TimeDiff(startTime, GetTime())*1e-3 << " secs" << endl << endl;
-
         // use split cost priority queue
-        if (mUseSplitCostQueue)
-        {
-                ConstructWithSplitQueue(polys, rays);
-        }
-        else
-        {
-                Construct(polys, rays);
-        }
-
-        // clean up polygons
-        CLEAR_CONTAINER(polys);
+        Construct(rays);
 }
 
 
 // TODO: return memory usage in MB
-float VspBspTree::GetMemUsage() const
+float VspOspTree::GetMemUsage() const
 {
         return (float)
-                 (sizeof(VspBspTree) + 
+                 (sizeof(VspOspTree) + 
                   mBspStats.Leaves() * sizeof(BspLeaf) + 
                   mCreatedViewCells * sizeof(BspViewCell) +
@@ -476 +239 @@
 
 
-
-void VspBspTree::Construct(const PolygonContainer &polys, RayInfoContainer *rays)
-{
-        VspBspTraversalQueue tQueue;
+void VspOspTree::Construct(RayInfoContainer *rays)
+{
+        VspOspSplitQueue tQueue;
 
         mRoot = new BspLeaf();
 
-        // constrruct root node geometry
-        BspNodeGeometry *geom = new BspNodeGeometry();
-        ConstructGeometry(mRoot, *geom);
-
-        const float prop = mUseAreaForPvs ? geom->GetArea() : geom->GetVolume();
-
-        VspBspTraversalData tData(mRoot,
-                                                          new PolygonContainer(polys),
+        const float prop = mBox.GetVolume();
+
+        VspOspTraversalData tData(mRoot,
                                                           0,
                                                           rays,
                               ComputePvsSize(*rays),
                                                           prop,
-                                                          geom);
-
-        EvalPriority(tData);
-
-
-        // first node is kd node, i.e. an axis aligned box
-        if (1)
-        tData.mIsKdNode = true;
-        else
-                tData.mIsKdNode = false;
-
-        tQueue.push(tData);
-
-
-        mTotalCost = tData.mPvs * tData.mProbability / mBox.GetVolume();
-        mTotalPvsSize = tData.mPvs;
-        
-        mSubdivisionStats 
-                        << "#ViewCells\n1" <<  endl
-                        << "#RenderCostDecrease\n0" << endl 
-                        << "#TotalRenderCost\n" << mTotalCost << endl
-                        << "#AvgRenderCost\n" << mTotalPvsSize << endl;
-
-        Debug << "total cost: " << mTotalCost << endl;
-        
-        
-        mBspStats.Start();
-        cout << "Constructing vsp bsp tree ... \n";
-
-        long startTime = GetTime();     
-        int nLeaves = 500;
-        int nViewCells = 500;
-
-        // used for intermediate time measurements and progress
-        long interTime = GetTime();     
-
-        mOutOfMemory = false;
-
-        mCreatedViewCells = 0;
-        
-        while (!tQueue.empty())
-        {
-                tData = tQueue.top();
-            tQueue.pop();               
-
-                if (0 && !mOutOfMemory)
-                {
-                        float mem = GetMemUsage();
-
-                        if (mem > mMaxMemory)
-                        {
-                                mOutOfMemory = true;
-                                Debug << "memory limit reached: " << mem << endl;
-                        }
-                }
-
-                // subdivide leaf node
-                BspNode *r = Subdivide(tQueue, tData);
-
-                if (r == mRoot)
-                        Debug << "VSP BSP tree construction time spent at root: "
-                                  << TimeDiff(startTime, GetTime())*1e-3 << "s" << endl;
-
-                if (mBspStats.Leaves() >= nLeaves)
-                {
-                        nLeaves += 500;
-
-                        cout << "leaves=" << mBspStats.Leaves() << endl;
-                        Debug << "needed "
-                                  << TimeDiff(interTime, GetTime())*1e-3 
-                                  << " secs to create 500 view cells" << endl;
-                        interTime = GetTime();
-                }
-
-                if (mCreatedViewCells >= nViewCells)
-                {
-                        nViewCells += 500;
-
-                        cout << "generated " << mCreatedViewCells << " viewcells" << endl;
-                }
-        }
-
-        Debug << "Used Memory: " << GetMemUsage() << " MB" << endl << endl;
-        cout << "finished\n";
-
-        mBspStats.Stop();
-}
-
-
-
-void VspBspTree::ConstructWithSplitQueue(const PolygonContainer &polys, 
-                                                                                          RayInfoContainer *rays)
-{
-        VspBspSplitQueue tQueue;
-
-        mRoot = new BspLeaf();
-
-        // constrruct root node geometry
-        BspNodeGeometry *geom = new BspNodeGeometry();
-        ConstructGeometry(mRoot, *geom);
-
-        const float prop = mUseAreaForPvs ? geom->GetArea() : geom->GetVolume();
-
-        VspBspTraversalData tData(mRoot,
-                                                          new PolygonContainer(polys),
-                                                          0,
-                                                          rays,
-                              ComputePvsSize(*rays),
-                                                          prop,
-                                                          geom);
+                                                          mBox);
 
 
         // compute first split candidate
-        VspBspSplitCandidate splitCandidate;
+        VspOspSplitCandidate splitCandidate;
         EvalSplitCandidate(tData, splitCandidate);
 
@@ -697 +345 @@
 
 
-bool VspBspTree::LocalTerminationCriteriaMet(const VspBspTraversalData &data) const
+bool VspOspTree::LocalTerminationCriteriaMet(const VspOspTraversalData &data) const
 {
         return
@@ -708 +356 @@
 
 
-bool VspBspTree::GlobalTerminationCriteriaMet(const VspBspTraversalData &data) const
+bool VspOspTree::GlobalTerminationCriteriaMet(const VspOspTraversalData &data) const
 {
         return
@@ -718 +366 @@
 
 
-
-BspNode *VspBspTree::Subdivide(VspBspTraversalQueue &tQueue,
-                                                           VspBspTraversalData &tData)
-{
-        BspNode *newNode = tData.mNode;
-
-        if (!LocalTerminationCriteriaMet(tData) && !GlobalTerminationCriteriaMet(tData))
-        {
-                PolygonContainer coincident;
-
-                VspBspTraversalData tFrontData;
-                VspBspTraversalData tBackData;
-
-                // create new interior node and two leaf nodes
-                // or return leaf as it is (if maxCostRatio missed)
-                int splitAxis;
-                bool splitFurther = true;
-                int maxCostMisses = tData.mMaxCostMisses;
-                
-                Plane3 splitPlane;
-                BspLeaf *leaf = dynamic_cast<BspLeaf *>(tData.mNode);
-                
-                // choose next split plane
-                if (!SelectPlane(splitPlane, leaf, tData, tFrontData, tBackData, splitAxis))
-                {
-                        ++ maxCostMisses;
-
-                        if (maxCostMisses > mTermMissTolerance)
-                        {
-                                // terminate branch because of max cost
-                                ++ mBspStats.maxCostNodes;
-                                splitFurther = false;
-                        }
-                }
-        
-                // if this a valid split => subdivide this node further
-                if (splitFurther) //-- continue subdivision
-                {
-                        newNode = SubdivideNode(splitPlane, tData, tFrontData, tBackData, coincident);
-
-                        if (splitAxis < 3)
-                                ++ mBspStats.splits[splitAxis];
-                        else
-                                ++ mBspStats.polySplits;
-
-                        // if it was a kd node (i.e., a box) and the split axis is axis aligned, it is still a kd node
-                        tFrontData.mIsKdNode = tBackData.mIsKdNode = (tData.mIsKdNode && (splitAxis < 3));
-                        tFrontData.mAxis = tBackData.mAxis = splitAxis;
-
-                        // how often was max cost ratio missed in this branch?
-                        tFrontData.mMaxCostMisses = maxCostMisses;
-                        tBackData.mMaxCostMisses = maxCostMisses;
-
-                        EvalPriority(tFrontData);
-                        EvalPriority(tBackData);
-
-                        // evaluate subdivision stats
-                        if (1)
-                        {
-                                float cFront = (float)tFrontData.mPvs * tFrontData.mProbability;
-                                float cBack = (float)tBackData.mPvs * tBackData.mProbability;
-                                float cData = (float)tData.mPvs * tData.mProbability;;
-
-                float costDecr = (cFront + cBack - cData) / mBox.GetVolume();
-
-                                mTotalCost += costDecr;
-                                mTotalPvsSize += tFrontData.mPvs + tBackData.mPvs - tData.mPvs;
-
-                                mSubdivisionStats 
-                                                << "#ViewCells\n" << mBspStats.Leaves() << endl
-                                                << "#RenderCostDecrease\n" << -costDecr << endl 
-                                                << "#TotalRenderCost\n" << mTotalCost << endl
-                                                << "#AvgRenderCost\n" << (float)mTotalPvsSize / (float)mBspStats.Leaves() << endl;
-                        }
-
-                        // push the children on the stack
-                        tQueue.push(tFrontData);
-                        tQueue.push(tBackData);
-
-                        // delete old leaf node
-                        DEL_PTR(tData.mNode);
-                }
-        }
-
-        //-- terminate traversal and create new view cell
-        if (newNode->IsLeaf())
-        {
-                BspLeaf *leaf = dynamic_cast<BspLeaf *>(newNode);
-                BspViewCell *viewCell = new BspViewCell();
-                
-                leaf->SetViewCell(viewCell);
-        
-                //-- update pvs
-                int conSamp = 0;
-                float sampCon = 0.0f;
-                AddToPvs(leaf, *tData.mRays, sampCon, conSamp);
-
-                // update scalar pvs size lookup
-                mViewCellsManager->SetScalarPvsSize(viewCell, viewCell->GetPvs().GetSize());
-        
-
-                mBspStats.contributingSamples += conSamp;
-                mBspStats.sampleContributions +=(int) sampCon;
-
-                //-- store additional info
-                if (mStoreRays)
-                {
-                        RayInfoContainer::const_iterator it, it_end = tData.mRays->end();
-                        for (it = tData.mRays->begin(); it != it_end; ++ it)
-                        {
-                                (*it).mRay->Ref();                      
-                                leaf->mVssRays.push_back((*it).mRay);
-                        }
-                }
-
-                // should I check here?
-                if (0 && !mViewCellsManager->CheckValidity(viewCell, 0, mViewCellsManager->GetMaxPvsSize()))
-                {
-                        viewCell->SetValid(false);
-                        leaf->SetTreeValid(false);
-                        PropagateUpValidity(leaf);
-
-                        ++ mBspStats.invalidLeaves;
-                }
-                
-        viewCell->mLeaf = leaf;
-
-                if (mUseAreaForPvs)
-                        viewCell->SetArea(tData.mProbability);
-                else
-                        viewCell->SetVolume(tData.mProbability);
-
-                leaf->mProbability = tData.mProbability;
-
-                EvaluateLeafStats(tData);               
-        }
-
-        //-- cleanup
-        tData.Clear();
-
-        return newNode;
-}
-
 // subdivide using a split plane queue
-BspNode *VspBspTree::Subdivide(VspBspSplitQueue &tQueue,
-                                                           VspBspSplitCandidate &splitCandidate)
-{
-        VspBspTraversalData &tData = splitCandidate.mParentData;
+BspNode *VspOspTree::Subdivide(VspOspSplitQueue &tQueue,
+                                                           VspOspSplitCandidate &splitCandidate)
+{
+        VspOspTraversalData &tData = splitCandidate.mParentData;
 
         BspNode *newNode = tData.mNode;
@@ -871 +376 @@
         if (!LocalTerminationCriteriaMet(tData) && !GlobalTerminationCriteriaMet(tData))
         {       
-                PolygonContainer coincident;
-
-                VspBspTraversalData tFrontData;
-                VspBspTraversalData tBackData;
+                VspOspTraversalData tFrontData;
+                VspOspTraversalData tBackData;
 
                 //-- continue subdivision
                 
                 // create new interior node and two leaf node
-                const Plane3 splitPlane = splitCandidate.mSplitPlane;
+                //TODO
+                const Plane3 splitPlane;// = splitCandidate.mSplitPlane;
                                 
-                newNode = SubdivideNode(splitPlane, tData, tFrontData, tBackData, coincident);
-        
-                const int splitAxis = splitCandidate.mSplitAxis;
+                newNode = SubdivideNode(splitPlane, tData, tFrontData, tBackData);
+        
                 const int maxCostMisses = splitCandidate.mMaxCostMisses;
 
-                if (splitAxis < 3)
-                        ++ mBspStats.splits[splitAxis];
-                else
-                        ++ mBspStats.polySplits;
-
-                tFrontData.mIsKdNode = tBackData.mIsKdNode = (tData.mIsKdNode && (splitAxis < 3));
-                tFrontData.mAxis = tBackData.mAxis = splitAxis;
 
                 // how often was max cost ratio missed in this branch?
@@ -922 +418 @@
         
                 //-- push the new split candidates on the stack
-                VspBspSplitCandidate frontCandidate;
-                VspBspSplitCandidate backCandidate;
+                VspOspSplitCandidate frontCandidate;
+                VspOspSplitCandidate backCandidate;
 
                 EvalSplitCandidate(tFrontData, frontCandidate);
@@ -969 +465 @@
                 viewCell->mLeaf = leaf;
 
-                if (mUseAreaForPvs)
-                        viewCell->SetArea(tData.mProbability);
-                else
-                        viewCell->SetVolume(tData.mProbability);
-
+                viewCell->SetVolume(tData.mProbability);
         leaf->mProbability = tData.mProbability;
 
@@ -986 +478 @@
 
 
-void VspBspTree::EvalPriority(VspBspTraversalData &tData) const
-{
-    switch (mNodePriorityQueueType) 
-        {
-        case BREATH_FIRST:
-                tData.mPriority = (float)-tData.mDepth;
-                break;
-        case DEPTH_FIRST:
-                tData.mPriority = (float)tData.mDepth;
-                break;
-        default:
-                tData.mPriority = tData.mPvs * tData.mProbability;
-                //Debug << "priority: " << tData.mPriority << endl;
-                break;
-        }
-}
-
-
-void VspBspTree::EvalSplitCandidate(VspBspTraversalData &tData,
-                                                                        VspBspSplitCandidate &splitData)
-{
-        VspBspTraversalData frontData;
-        VspBspTraversalData backData;
+void VspOspTree::EvalSplitCandidate(VspOspTraversalData &tData,
+                                                                        VspOspSplitCandidate &splitData)
+{
+        VspOspTraversalData frontData;
+        VspOspTraversalData backData;
 
         BspLeaf *leaf = dynamic_cast<BspLeaf *>(tData.mNode);
 
         // compute locally best split plane
-    bool success = SelectPlane(splitData.mSplitPlane, leaf, tData, 
-                                                           frontData, backData, splitData.mSplitAxis);
-
-        // TODO: reuse
-        DEL_PTR(frontData.mGeometry);
-        DEL_PTR(backData.mGeometry);
-        
+        // TODO
+    const bool success =0;/// SelectPlane(splitData.mSplitPlane, tData, 
+//                                                                       frontData, backData);
+        //TODO
         // compute global decrease in render cost
-        splitData.mRenderCost = EvalRenderCostDecrease(splitData.mSplitPlane, tData);
+        splitData.mRenderCost = 0;//EvalRenderCostDecrease(splitData.mSplitPlane, tData);
         splitData.mParentData = tData;
         splitData.mMaxCostMisses = success ? tData.mMaxCostMisses : tData.mMaxCostMisses + 1;
@@ -1027 +498 @@
 
 
-BspInterior *VspBspTree::SubdivideNode(const Plane3 &splitPlane,
-                                                                           VspBspTraversalData &tData,
-                                                                           VspBspTraversalData &frontData,
-                                                                           VspBspTraversalData &backData,
-                                                                           PolygonContainer &coincident)
+BspInterior *VspOspTree::SubdivideNode(const Plane3 &splitPlane,
+                                                                           VspOspTraversalData &tData,
+                                                                           VspOspTraversalData &frontData,
+                                                                           VspOspTraversalData &backData)
 {
         BspLeaf *leaf = dynamic_cast<BspLeaf *>(tData.mNode);
@@ -1037 +507 @@
         //-- the front and back traversal data is filled with the new values
         frontData.mDepth = tData.mDepth + 1;
-        frontData.mPolygons = new PolygonContainer();
         frontData.mRays = new RayInfoContainer();
         
         backData.mDepth = tData.mDepth + 1;
-        backData.mPolygons = new PolygonContainer();
         backData.mRays = new RayInfoContainer();
         
@@ -1059 +527 @@
         
         // if geometry was not already computed
-        if (!frontData.mGeometry && !backData.mGeometry)
-        {
-                frontData.mGeometry = new BspNodeGeometry();
-                backData.mGeometry = new BspNodeGeometry();
-
-                tData.mGeometry->SplitGeometry(*frontData.mGeometry,
-                                                                           *backData.mGeometry,
-                                                                           splitPlane,
-                                                                           mBox,
-                                                                           //0.0f);
-                                                                           mEpsilon);
-                
-                if (mUseAreaForPvs)
-                {
-                        frontData.mProbability = frontData.mGeometry->GetArea();
-                        backData.mProbability = backData.mGeometry->GetArea();
-                }
-                else
-                {
-                        frontData.mProbability = frontData.mGeometry->GetVolume();
-                        backData.mProbability = tData.mProbability - frontData.mProbability;
-
-                        // should never come here: wrong volume !!!
-                        if (0)
-                        {
-                                if (frontData.mProbability < -0.00001)
-                                        Debug << "fatal error f: " << frontData.mProbability << endl;
-                                if (backData.mProbability < -0.00001)
-                                        Debug << "fatal error b: " << backData.mProbability << endl;
-
-                                // clamp because of precision issues
-                                if (frontData.mProbability < 0) frontData.mProbability = 0;
-                                if (backData.mProbability < 0) backData.mProbability = 0;
-                        }
-                }
-        }
-
-        
-    // subdivide polygons
-        SplitPolygons(splitPlane,
-                                  *tData.mPolygons,
-                      *frontData.mPolygons,
-                                  *backData.mPolygons,
-                                  coincident);
-
-
-
-        ///////////////////////////////////////
+        // TODO
+
+#if TODO
+        tData.mBoundingBox.Split(splitPlane.mAxis, splitPlane.mPosition, 
+                                                         frontData.mBoundingBox, backData.mBoundingBox);
+
+#endif
+
+        frontData.mProbability = frontData.mBoundingBox.GetVolume();
+        backData.mProbability = tData.mProbability - frontData.mProbability;
+
+        
+    ///////////////////////////////////////////
         // subdivide further
 
@@ -1149 +582 @@
         interior->mTimeStamp = mTimeStamp ++;
         
-
-        //DEL_PTR(leaf);
         return interior;
 }
 
 
-void VspBspTree::AddToPvs(BspLeaf *leaf,
+void VspOspTree::AddToPvs(BspLeaf *leaf,
                                                   const RayInfoContainer &rays,
                                                   float &sampleContributions,
@@ -1200 +631 @@
 
 
-void VspBspTree::SortSplitCandidates(const RayInfoContainer &rays, 
+void VspOspTree::SortSplitCandidates(const RayInfoContainer &rays, 
                                                                          const int axis, 
                                                                          float minBand, 
@@ -1251 +682 @@
 
 
-float VspBspTree::BestCostRatioHeuristics(const RayInfoContainer &rays,
+float VspOspTree::BestCostRatioHeuristics(const RayInfoContainer &rays,
                                                                                   const AxisAlignedBox3 &box,
                                                                                   const int pvsSize,
@@ -1413 +844 @@
         if (splitPlaneFound)
         {
-                ratio = mPvsFactor * newRenderCost / (oldRenderCost + Limits::Small);
+                ratio = newRenderCost / (oldRenderCost + Limits::Small);
         }
         //if (axis != 1)
@@ -1423 +854 @@
 
 
-float VspBspTree::SelectAxisAlignedPlane(Plane3 &plane,
-                                                                                 const VspBspTraversalData &tData,
-                                                                                 int &axis,
-                                                                                 BspNodeGeometry **frontGeom,
-                                                                                 BspNodeGeometry **backGeom,
-                                                                                 float &pFront,
-                                                                                 float &pBack,
-                                                                                 const bool isKdNode)
+float VspOspTree::SelectPlane(const VspOspTraversalData &tData,
+                                                          AxisAlignedPlane &plane,
+                                                          float &pFront,
+                                                          float &pBack)
 {
         float nPosition[3];
@@ -1437 +864 @@
         float nProbBack[3];
 
-        BspNodeGeometry *nFrontGeom[3];
-        BspNodeGeometry *nBackGeom[3];
-
-        // set to NULL, so I can find out which gemetry was stored
-        for (int i = 0; i < 3; ++ i)
-        {
-                nFrontGeom[i] = NULL;
-                nBackGeom[i] = NULL;
-        }
-
         // create bounding box of node geometry
-        AxisAlignedBox3 box;
-                
-        //TODO: for kd split geometry already is box => only take minmax vertices
-        if (1)
-        {
-                // get bounding box from geometry
-                tData.mGeometry->GetBoundingBox(box);
-        }
-        else
-        {
-                box.Initialize();
-                RayInfoContainer::const_iterator ri, ri_end = tData.mRays->end();
-
-                for(ri = tData.mRays->begin(); ri < ri_end; ++ ri)
-                        box.Include((*ri).ExtrapTermination());
-        }
-
+        AxisAlignedBox3 box = tData.mBoundingBox;
+                
         int sAxis = 0;
-        int bestAxis;
-
-        // if max cost ratio is exceeded, take split along longest axis instead
-        const float maxCostRatioForArbitraryAxis = 0.9f;
-
-        if (mUseDrivingAxisForMaxCost)
-                bestAxis = box.Size().DrivingAxis();
-        else
-                bestAxis = -1;
+        int bestAxis = -1;
 
 #if 0
@@ -1493 +887 @@
                 sAxis = box.Size().DrivingAxis();
 
-                
-        //Debug << "use special axis: " << useSpecialAxis << endl;
-        //Debug << "axis: " << sAxis << " drivingaxis: " << box.Size().DrivingAxis();
-
-        for (axis = 0; axis < 3 ; ++ axis)
+
+        for (int axis = 0; axis < 3 ; ++ axis)
         {
                 if (!useSpecialAxis || (axis == sAxis))
@@ -1512 +903 @@
                                                                                         nPosition[axis]);                       
                         }
-                        
-                        //-- split plane position is spatial median
-
-
-                        // also use median split if cost ratio very low as
-                        // there are not enough visibility cues
-                        //if (!mUseCostHeuristics || (nCostRatio[axis] > maxCostRatioForHeur))
-                        else 
-                        {
-
+                        else //-- split plane position is spatial median
+                        {
                                 nPosition[axis] = (box.Min()[axis] + box.Max()[axis]) * 0.5f;
-                                Vector3 normal(0,0,0); normal[axis] = 1.0f;
-
-                                // allows faster split because we have axis aligned kd tree boxes
-                                if (isKdNode)
-                                {
-                                        nCostRatio[axis] = EvalAxisAlignedSplitCost(tData,
-                                                                                                                                box,
-                                                                                                                                axis,
-                                                                                                                                nPosition[axis],
-                                                                                                                                nProbFront[axis], 
-                                                                                                                                nProbBack[axis]);
-                                        
-                                        Vector3 pos;
-                                        
-                                        // create back geometry from box
-                                        // NOTE: the geometry is saved when possible
-                                        pos = box.Max(); pos[axis] = nPosition[axis];
-                                        AxisAlignedBox3 bBox(box.Min(), pos);
-                                        PolygonContainer fPolys;
-                                        bBox.ExtractPolys(fPolys);
-
-                                        nBackGeom[axis] = new BspNodeGeometry(fPolys);
-        
-                                        //-- create front geometry from box
-                                        pos = box.Min(); pos[axis] = nPosition[axis];
-                                        AxisAlignedBox3 fBox(pos, box.Max());
-
-                                        PolygonContainer bPolys;
-                                        fBox.ExtractPolys(bPolys);
-                                        nFrontGeom[axis] = new BspNodeGeometry(bPolys);
-                                }
-                                else
-                                {
-                                        nFrontGeom[axis] = new BspNodeGeometry();
-                                        nBackGeom[axis] = new BspNodeGeometry();
-
-                                        nCostRatio[axis] = 
-                                                EvalSplitPlaneCost(Plane3(normal, nPosition[axis]), 
-                                                                                   tData, *nFrontGeom[axis], *nBackGeom[axis],
-                                                                                   nProbFront[axis], nProbBack[axis]);
-                                }
+
+                                nCostRatio[axis] = EvalSplitCost(tData,
+                                                                                                 box,
+                                                                                                 axis,
+                                                                                                 nPosition[axis],
+                                                                                                 nProbFront[axis], 
+                                                                                                 nProbBack[axis]);
                         }
                                                 
-                        
-                        if (mUseDrivingAxisForMaxCost)
-                        {
-                                // we take longest axis split if cost ratio exceeds threshold
-                                if (nCostRatio[axis] < min(maxCostRatioForArbitraryAxis, nCostRatio[bestAxis]))
-                                {
-                                        bestAxis = axis;
-                                }
-                                else if (nCostRatio[axis] < nCostRatio[bestAxis])
-                                        Debug << "taking split along longest axis (" << bestAxis << ") instead of  (" << axis << ")" << endl;
-                                
-                        }
-                        else
-                        {
-                                if (bestAxis == -1)
-                                {
-                                        bestAxis = axis;
-                                }
-                                else if (nCostRatio[axis] < nCostRatio[bestAxis])
-                                {
-                                        bestAxis = axis;
-                                }
+                        if (bestAxis == -1)
+                        {
+                                bestAxis = axis;
+                        }
+                        else if (nCostRatio[axis] < nCostRatio[bestAxis])
+                        {
+                                bestAxis = axis;
                         } 
                 }
@@ -1593 +927 @@
 
         //-- assign values
-        axis = bestAxis;
+        plane.mAxis = bestAxis;
         pFront = nProbFront[bestAxis];
         pBack = nProbBack[bestAxis];
 
-        // assign best split nodes geometry 
-        *frontGeom = nFrontGeom[bestAxis];
-        *backGeom = nBackGeom[bestAxis];
-
-        // and delete other geometry
-        DEL_PTR(nFrontGeom[(bestAxis + 1) % 3]);
-        DEL_PTR(nBackGeom[(bestAxis + 2) % 3]);
-
-        //-- split plane
-    Vector3 normal(0,0,0); normal[bestAxis] = 1;
-        plane = Plane3(normal, nPosition[bestAxis]);
-
-        //Debug << "best axis: " << bestAxis << " pos " << nPosition[bestAxis] << endl;
-        //Debug << "!!!!!!!!!!!!!!" << endl;
+        //-- split plane position
+    plane.mPosition = nPosition[bestAxis];
+
         return nCostRatio[bestAxis];
 }
 
 
-bool VspBspTree::SelectPlane(Plane3 &bestPlane,
-                                                         BspLeaf *leaf,
-                                                         VspBspTraversalData &data,                                                      
-                                                         VspBspTraversalData &frontData,
-                                                         VspBspTraversalData &backData,
-                                                         int &splitAxis)
-{
-        // HACK matt: subdivide regularily to certain depth
-        if (data.mDepth < 0)    
-        {
-                cout << "d: " << data.mDepth << endl;
-                // return axis aligned split
-                AxisAlignedBox3 box;
-                box.Initialize();
-        
-                // create bounding box of region
-                data.mGeometry->GetBoundingBox(box);
-        
-                const int axis = box.Size().DrivingAxis();
-                const Vector3 position = (box.Min()[axis] + box.Max()[axis]) * 0.5f;
-
-                Vector3 norm(0,0,0); norm[axis] = 1.0f;
-                bestPlane = Plane3(norm, position);
-                splitAxis = axis;
-                return true;
-        }
-
-        // simplest strategy: just take next polygon
-        if (mSplitPlaneStrategy & RANDOM_POLYGON)
-        {
-        if (!data.mPolygons->empty())
-                {
-                        const int randIdx = 
-                                (int)RandomValue(0, (Real)((int)data.mPolygons->size() - 1));
-                        Polygon3 *nextPoly = (*data.mPolygons)[randIdx];
-
-                        bestPlane = nextPoly->GetSupportingPlane();
-                        return true;
-                }
-        }
-
-        //-- use heuristics to find appropriate plane
-
-        // intermediate plane
-        Plane3 plane;
-        float lowestCost = MAX_FLOAT;
-        
-        // decides if the first few splits should be only axisAligned
-        const bool onlyAxisAligned  = 
-                (mSplitPlaneStrategy & AXIS_ALIGNED) &&
-                ((int)data.mRays->size() > mTermMinRaysForAxisAligned) &&
-                ((int)data.GetAvgRayContribution() < mTermMaxRayContriForAxisAligned);
-        
-        const int limit = onlyAxisAligned ? 0 : 
-                Min((int)data.mPolygons->size(), mMaxPolyCandidates);
-
-        float candidateCost;
-
-        int maxIdx = (int)data.mPolygons->size();
-
-        for (int i = 0; i < limit; ++ i)
-        {
-                // the already taken candidates are stored behind maxIdx
-                // => assure that no index is taken twice
-                const int candidateIdx = (int)RandomValue(0, (Real)(-- maxIdx));
-                Polygon3 *poly = (*data.mPolygons)[candidateIdx];
-
-                // swap candidate to the end to avoid testing same plane
-                std::swap((*data.mPolygons)[maxIdx], (*data.mPolygons)[candidateIdx]);
-                //Polygon3 *poly = (*data.mPolygons)[(int)RandomValue(0, (int)polys.size() - 1)];
-
-                // evaluate current candidate
-                BspNodeGeometry fGeom, bGeom;
-                float fArea, bArea;
-                plane = poly->GetSupportingPlane();
-                candidateCost = EvalSplitPlaneCost(plane, data, fGeom, bGeom, fArea, bArea);
-                
-                if (candidateCost < lowestCost)
-                {
-                        bestPlane = plane;
-                        lowestCost = candidateCost;
-                }
-        }
-
-        //-- evaluate axis aligned splits
-        int axis;
-        BspNodeGeometry *fGeom, *bGeom;
-        float pFront, pBack;
-
-        candidateCost = 99999999.0f;
-
-        // option: axis aligned split only if no polygon available
-        if (!mUsePolygonSplitIfAvailable || data.mPolygons->empty())
-        {
-                candidateCost = SelectAxisAlignedPlane(plane, 
-                                                                                           data, 
-                                                                                           axis,
-                                                                                           &fGeom, 
-                                                                                           &bGeom, 
-                                                                                           pFront, 
-                                                                                           pBack,
-                                                                                           data.mIsKdNode);      
-        }
-
-        splitAxis = 3;
-
-        if (candidateCost < lowestCost)
-        {       
-                bestPlane = plane;
-                lowestCost = candidateCost;
-                splitAxis = axis;
-        
-                // assign already computed values
-                // we can do this because we always save the
-                // computed values from the axis aligned splits         
-
-                if (fGeom && bGeom)
-                {
-                        frontData.mGeometry = fGeom;
-                        backData.mGeometry = bGeom;
-        
-                        frontData.mProbability = pFront;
-                        backData.mProbability = pBack;
-                }
-        }
-        else
-        {
-                DEL_PTR(fGeom);
-                DEL_PTR(bGeom);
-        }
-    
-#ifdef _DEBUG
-        Debug << "plane lowest cost: " << lowestCost << endl;
-#endif
-
-        // exeeded relative max cost ratio
-        if (lowestCost > mTermMaxCostRatio)
-        {
-                return false;
-        }
-
-        return true;
-}
-
-
-Plane3 VspBspTree::ChooseCandidatePlane(const RayInfoContainer &rays) const
-{
-        const int candidateIdx = (int)RandomValue(0, (Real)((int)rays.size() - 1));
-
-        const Vector3 minPt = rays[candidateIdx].ExtrapOrigin();
-        const Vector3 maxPt = rays[candidateIdx].ExtrapTermination();
-
-        const Vector3 pt = (maxPt + minPt) * 0.5;
-        const Vector3 normal = Normalize(rays[candidateIdx].mRay->GetDir());
-
-        return Plane3(normal, pt);
-}
-
-
-Plane3 VspBspTree::ChooseCandidatePlane2(const RayInfoContainer &rays) const
-{
-        Vector3 pt[3];
-
-        int idx[3];
-        int cmaxT = 0;
-        int cminT = 0;
-        bool chooseMin = false;
-
-        for (int j = 0; j < 3; ++ j)
-        {
-                idx[j] = (int)RandomValue(0, (Real)((int)rays.size() * 2 - 1));
-
-                if (idx[j] >= (int)rays.size())
-                {
-                        idx[j] -= (int)rays.size();
-
-                        chooseMin = (cminT < 2);
-                }
-                else
-                        chooseMin = (cmaxT < 2);
-
-                RayInfo rayInf = rays[idx[j]];
-                pt[j] = chooseMin ? rayInf.ExtrapOrigin() : rayInf.ExtrapTermination();
-        }
-
-        return Plane3(pt[0], pt[1], pt[2]);
-}
-
-
-Plane3 VspBspTree::ChooseCandidatePlane3(const RayInfoContainer &rays) const
-{
-        Vector3 pt[3];
-
-        int idx1 = (int)RandomValue(0, (Real)((int)rays.size() - 1));
-        int idx2 = (int)RandomValue(0, (Real)((int)rays.size() - 1));
-
-        // check if rays different
-        if (idx1 == idx2)
-                idx2 = (idx2 + 1) % (int)rays.size();
-
-        const RayInfo ray1 = rays[idx1];
-        const RayInfo ray2 = rays[idx2];
-
-        // normal vector of the plane parallel to both lines
-        const Vector3 norm = Normalize(CrossProd(ray1.mRay->GetDir(), ray2.mRay->GetDir()));
-
-        // vector from line 1 to line 2
-        const Vector3 vd = ray2.ExtrapOrigin() - ray1.ExtrapOrigin();
-
-        // project vector on normal to get distance
-        const float dist = DotProd(vd, norm);
-
-        // point on plane lies halfway between the two planes
-        const Vector3 planePt = ray1.ExtrapOrigin() + norm * dist * 0.5;
-
-        return Plane3(norm, planePt);
-}
-
-
-inline void VspBspTree::GenerateUniqueIdsForPvs()
+inline void VspOspTree::GenerateUniqueIdsForPvs()
 {
         Intersectable::NewMail(); sBackId = Intersectable::sMailId;
@@ -1842 +946 @@
 
 
-float VspBspTree::EvalRenderCostDecrease(const Plane3 &candidatePlane,
-                                                                                 const VspBspTraversalData &data) const
+float VspOspTree::EvalRenderCostDecrease(const Plane3 &candidatePlane,
+                                                                                 const VspOspTraversalData &data) const
 {
         float pvsFront = 0;
@@ -1874 +978 @@
         BspNodeGeometry geomFront;
         BspNodeGeometry geomBack;
-
-        // construct child geometry with regard to the candidate split plane
-        data.mGeometry->SplitGeometry(geomFront,
-                                                                  geomBack,
-                                                                  candidatePlane,
-                                                                  mBox,
-                                                                  //0.0f);
-                                                                  mEpsilon);
-
-        if (!mUseAreaForPvs) // use front and back cell areas to approximate volume
-        {
-                pFront = geomFront.GetVolume();
-                pBack = pOverall - pFront;
-
-                // something is wrong with the volume
-                if ((pFront < 0.0) || (pBack < 0.0))
-                {
-                        Debug << "ERROR in volume:\n"
-                                  << "volume f :" << pFront << " b: " << pBack << " p: " << pOverall 
-                                  << ", real volume f: " << pFront << " b: " << geomBack.GetVolume()
-                                  << ", #polygons f: " << geomFront.Size() << " b: " << geomBack.Size() << " p: " << data.mGeometry->Size() << endl;
-                }
-        }
-        else
-        {
-                pFront = geomFront.GetArea();
-                pBack = geomBack.GetArea();
-        }
-        
+        
+        pFront = geomFront.GetVolume();
+        pBack = pOverall - pFront;
+
+                
 
         // -- pvs rendering heuristics
@@ -1921 +1001 @@
 
 #if 1
-        // take render cost of node into account
+        // take render cost of node into account to avoid being stuck in a local minimum
         const float normalizedOldRenderCost = oldRenderCost / mBox.GetVolume();
-        //Debug << "rendercostdecr: " << 0.99f * renderCostDecrease << " old render cost: " << 0.01f * normalizedOldRenderCost << endl;
-        //return 0.5f * renderCostDecrease + 0.5f * normalizedOldRenderCost;
         return 0.99f * renderCostDecrease + 0.01f * normalizedOldRenderCost;
 #else
@@ -1932 +1010 @@
 
 
-float VspBspTree::EvalSplitPlaneCost(const Plane3 &candidatePlane,
-                                                                         const VspBspTraversalData &data,
-                                                                         BspNodeGeometry &geomFront,
-                                                                         BspNodeGeometry &geomBack,
-                                                                         float &pFront,
-                                                                         float &pBack) const
-{
-        float cost = 0;
-
-        float totalPvs = 0;
-        float pvsFront = 0;
-        float pvsBack = 0;
-        
-        // probability that view point lies in back / front node
-        float pOverall = 0;
-        pFront = 0;
-        pBack = 0;
-
-
-        int limit;
-        bool useRand;
-
-        // create unique ids for pvs heuristics
-        GenerateUniqueIdsForPvs();
-
-        // choose test rays randomly if too much
-        if ((int)data.mRays->size() > mMaxTests)
-        {
-                useRand = true;
-                limit = mMaxTests;
-        }
-        else
-        {
-                useRand = false;
-                limit = (int)data.mRays->size();
-        }
-        
-        for (int i = 0; i < limit; ++ i)
-        {
-                const int testIdx = useRand ? 
-                        (int)RandomValue(0, (Real)((int)data.mRays->size() - 1)) : i;
-                RayInfo rayInf = (*data.mRays)[testIdx];
-
-                float t;
-                VssRay *ray = rayInf.mRay;
-                const int cf = rayInf.ComputeRayIntersection(candidatePlane, t);
-
-                // find front and back pvs for origing and termination object
-                AddObjToPvs(ray->mTerminationObject, cf, pvsFront, pvsBack, totalPvs);
-                AddObjToPvs(ray->mOriginObject, cf, pvsFront, pvsBack, totalPvs);
-        }
-
-        // construct child geometry with regard to the candidate split plane
-        bool splitSuccessFull = data.mGeometry->SplitGeometry(geomFront,
-                                                                                                                  geomBack,
-                                                                                                                  candidatePlane,
-                                                                                                                  mBox,
-                                                                                                                  //0.0f);
-                                                                                                                  mEpsilon);
-
-        pOverall = data.mProbability;
-
-        if (!mUseAreaForPvs) // use front and back cell areas to approximate volume
-        {
-                pFront = geomFront.GetVolume();
-                pBack = pOverall - pFront;
-                
-                // HACK: precision issues possible for unbalanced split => don't take this split!
-                if (1 && 
-                        (!splitSuccessFull || (pFront <= 0) || (pBack <= 0) || 
-                        !geomFront.Valid() || !geomBack.Valid()))
-                {
-                        //Debug << "error f: " << pFront << " b: " << pBack << endl;
-                        // high penalty for this split
-                        return 99999.9f;
-                }
-        }
-        else
-        {
-                pFront = geomFront.GetArea();
-                pBack = geomBack.GetArea();
-        }
-        
-
-        // -- pvs rendering heuristics
-        const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize();
-        const int upperPvsLimit = mViewCellsManager->GetMaxPvsSize();
-
-        // only render cost heuristics or combined with standard deviation
-        const float penaltyOld = EvalPvsPenalty((int)totalPvs, lowerPvsLimit, upperPvsLimit);
-    const float penaltyFront = EvalPvsPenalty((int)pvsFront, lowerPvsLimit, upperPvsLimit);
-        const float penaltyBack = EvalPvsPenalty((int)pvsBack, lowerPvsLimit, upperPvsLimit);
-                        
-        const float oldRenderCost = pOverall * penaltyOld;
-        const float newRenderCost = penaltyFront * pFront + penaltyBack * pBack;
-
-        float oldCost, newCost;
-
-        // only render cost
-        if (1)
-        {
-                oldCost = oldRenderCost;
-                newCost = newRenderCost;
-        }
-        else // also considering standard deviation
-        {
-                // standard deviation is difference of back and front pvs
-                const float expectedCost = 0.5f * (penaltyFront + penaltyBack);
-
-                const float newDeviation = 0.5f * 
-                        fabs(penaltyFront - expectedCost) + fabs(penaltyBack - expectedCost);
-
-                const float oldDeviation = penaltyOld;
-
-                newCost = mRenderCostWeight * newRenderCost + (1.0f - mRenderCostWeight) * newDeviation;
-                oldCost = mRenderCostWeight * oldRenderCost + (1.0f - mRenderCostWeight) * oldDeviation;
-        }
-
-        cost += mPvsFactor * newCost / (oldCost + Limits::Small);
-                
-
-#ifdef _DEBUG
-        Debug << "totalpvs: " << data.mPvs << " ptotal: " << pOverall
-                  << " frontpvs: " << pvsFront << " pFront: " << pFront
-                  << " backpvs: " << pvsBack << " pBack: " << pBack << endl << endl;
-        Debug << "cost: " << cost << endl;
-#endif
-
-        return cost;
-}
-
-
-int VspBspTree::ComputeBoxIntersections(const AxisAlignedBox3 &box, 
-                                                                                ViewCellContainer &viewCells) const
-{
-        stack<bspNodePair> nodeStack;
-        BspNodeGeometry *rgeom = new BspNodeGeometry();
-
-        ConstructGeometry(mRoot, *rgeom);
-
-        nodeStack.push(bspNodePair(mRoot, rgeom));
-  
-        ViewCell::NewMail();
-
-        while (!nodeStack.empty()) 
-        {
-                BspNode *node = nodeStack.top().first;
-                BspNodeGeometry *geom = nodeStack.top().second;
-                nodeStack.pop();
-
-                const int side = geom->ComputeIntersection(box);
-                
-                switch (side)
-                {
-                case -1:
-                        // node geometry is contained in box
-                        CollectViewCells(node, true, viewCells, true);
-                        break;
-
-                case 0:
-                        if (node->IsLeaf())
-                        {
-                                BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
-                        
-                                if (!leaf->GetViewCell()->Mailed() && leaf->TreeValid())
-                                {
-                                        leaf->GetViewCell()->Mail();
-                                        viewCells.push_back(leaf->GetViewCell());
-                                }
-                        }
-                        else 
-                        {
-                                BspInterior *interior = dynamic_cast<BspInterior *>(node);
-                        
-                                BspNode *first = interior->GetFront();
-                                BspNode *second = interior->GetBack();
-            
-                                BspNodeGeometry *firstGeom = new BspNodeGeometry();
-                                BspNodeGeometry *secondGeom = new BspNodeGeometry();
-
-                                geom->SplitGeometry(*firstGeom,
-                                                                        *secondGeom,
-                                                                        interior->GetPlane(),
-                                                                        mBox,
-                                                                        //0.0000001f);
-                                                                        mEpsilon);
-
-                                nodeStack.push(bspNodePair(first, firstGeom));
-                                nodeStack.push(bspNodePair(second, secondGeom));
-                        }
-                        
-                        break;
-                default:
-                        // default: cull
-                        break;
-                }
-                
-                DEL_PTR(geom);
-                
-        }
-
-        return (int)viewCells.size();
-}
-
-
-float VspBspTree::EvalAxisAlignedSplitCost(const VspBspTraversalData &data,
-                                                                                   const AxisAlignedBox3 &box,
-                                                                                   const int axis,
-                                                                                   const float &position,                                                                                 
-                                                                                   float &pFront,
-                                                                                   float &pBack) const
+
+float VspOspTree::EvalSplitCost(const VspOspTraversalData &data,
+                                                                const AxisAlignedBox3 &box,
+                                                                const int axis,
+                                                                const float &position,                                                                            
+                                                                float &pFront,
+                                                                float &pBack) const
 {
         float pvsTotal = 0;
@@ -2158 +1032 @@
         for(rit = data.mRays->begin(); rit != rit_end; ++ rit)
         {
-                //if (!(*rit).mRay->IsActive()) continue;
-
                 // determine the side of this ray with respect to the plane
                 float t;
@@ -2175 +1047 @@
                 
         pOverall = data.mProbability;
-
-        if (!mUseAreaForPvs)
-        {   // volume
-                pBack = pFront = pOverall * 0.5f;
-                
-#if 0
-                // box length substitute for probability
-                const float minBox = box.Min(axis);
-                const float maxBox = box.Max(axis);
-
-                pBack = position - minBox;
-                pFront = maxBox - position;
-                pOverall = maxBox - minBox;
-#endif
-        }
-        else //-- area substitute for probability
-        {
-                const int axis2 = (axis + 1) % 3;
-                const int axis3 = (axis + 2) % 3;
-
-                const float faceArea = 
-                        (box.Max(axis2) - box.Min(axis2)) *
-                        (box.Max(axis3) - box.Min(axis3));
-
-                pBack = pFront = pOverall * 0.5f + faceArea;
-        }
-
+        pBack = pFront = pOverall * 0.5f;
+        
+        
 #ifdef _DEBUG
         Debug << axis << " " << pvsSize << " " << pvsBack << " " << pvsFront << endl;
@@ -2215 +1063 @@
 
 
-void VspBspTree::AddObjToPvs(Intersectable *obj,
+void VspOspTree::AddObjToPvs(Intersectable *obj,
                                                          const int cf,
                                                          float &frontPvs,
@@ -2268 +1116 @@
 
 
-void VspBspTree::CollectLeaves(vector<BspLeaf *> &leaves, 
+void VspOspTree::CollectLeaves(vector<BspLeaf *> &leaves, 
                                                            const bool onlyUnmailed,
                                                            const int maxPvsSize) const
@@ -2302 +1150 @@
 
 
-AxisAlignedBox3 VspBspTree::GetBoundingBox() const
+AxisAlignedBox3 VspOspTree::GetBoundingBox() const
 {
         return mBox;
@@ -2308 +1156 @@
 
 
-BspNode *VspBspTree::GetRoot() const
+BspNode *VspOspTree::GetRoot() const
 {
         return mRoot;
@@ -2314 +1162 @@
 
 
-void VspBspTree::EvaluateLeafStats(const VspBspTraversalData &data)
+void VspOspTree::EvaluateLeafStats(const VspOspTraversalData &data)
 {
         // the node became a leaf -> evaluate stats for leafs
@@ -2370 +1218 @@
 
 
-int VspBspTree::CastRay(Ray &ray)
+int VspOspTree::CastRay(Ray &ray)
 {
         int hits = 0;
@@ -2439 +1287 @@
                         if (!leaf->GetViewCell()->Mailed())
                         {
-                                //ray.bspIntersections.push_back(Ray::VspBspIntersection(maxt, leaf));
+                                //ray.bspIntersections.push_back(Ray::VspOspIntersection(maxt, leaf));
                                 leaf->GetViewCell()->Mail();
                                 ++ hits;
@@ -2468 +1316 @@
 
 
-void VspBspTree::CollectViewCells(ViewCellContainer &viewCells, bool onlyValid) const
+void VspOspTree::CollectViewCells(ViewCellContainer &viewCells, bool onlyValid) const
 {
         ViewCell::NewMail();
@@ -2476 +1324 @@
 
 
-void VspBspTree::CollapseViewCells()
+void VspOspTree::CollapseViewCells()
 {
 // TODO
@@ -2531 +1379 @@
 
 
-void VspBspTree::CollectRays(VssRayContainer &rays)
+void VspOspTree::CollectRays(VssRayContainer &rays)
 {
         vector<BspLeaf *> leaves;
@@ -2548 +1396 @@
 
 
-void VspBspTree::ValidateTree()
+void VspOspTree::ValidateTree()
 {
         stack<BspNode *> nodeStack;
@@ -2591 +1439 @@
 
 
-void VspBspTree::CollectViewCells(BspNode *root,
+void VspOspTree::CollectViewCells(BspNode *root,
                                                                   bool onlyValid,
                                                                   ViewCellContainer &viewCells,
@@ -2635 +1483 @@
 
 
-void VspBspTree::PreprocessPolygons(PolygonContainer &polys)
-{
-        // preprocess: throw out polygons coincident to the view space box (not needed)
-        PolygonContainer boxPolys;
-        mBox.ExtractPolys(boxPolys);
-        vector<Plane3> boxPlanes;
-
-        PolygonContainer::iterator pit, pit_end = boxPolys.end();
-
-        // extract planes of box
-        // TODO: can be done more elegantly than first extracting polygons
-        // and take their planes
-        for (pit = boxPolys.begin(); pit != pit_end; ++ pit)
-        {
-                boxPlanes.push_back((*pit)->GetSupportingPlane());
-        }
-
-        pit_end = polys.end();
-
-        for (pit = polys.begin(); pit != pit_end; ++ pit)
-        {
-                vector<Plane3>::const_iterator bit, bit_end = boxPlanes.end();
-                
-                for (bit = boxPlanes.begin(); (bit != bit_end) && (*pit); ++ bit)
-                {
-                        const int cf = (*pit)->ClassifyPlane(*bit, mEpsilon);
-
-                        if (cf == Polygon3::COINCIDENT)
-                        {
-                                DEL_PTR(*pit);
-                                //Debug << "coincident!!" << endl;
-                        }
-                }
-        }
-
-        // remove deleted entries
-        for (int i = 0; i < (int)polys.size(); ++ i)
-        {
-                while (!polys[i] && (i < (int)polys.size()))
-                {
-                        swap(polys[i], polys.back());
-                        polys.pop_back();
-                }
-        }
-}
-
-
-float VspBspTree::AccumulatedRayLength(const RayInfoContainer &rays) const
-{
-        float len = 0;
-
-        RayInfoContainer::const_iterator it, it_end = rays.end();
-
-        for (it = rays.begin(); it != it_end; ++ it)
-                len += (*it).SegmentLength();
-
-        return len;
-}
-
-
-int VspBspTree::SplitRays(const Plane3 &plane,
+int VspOspTree::SplitRays(const Plane3 &plane,
                                                   RayInfoContainer &rays,
                                                   RayInfoContainer &frontRays,
@@ -2725 +1513 @@
                         {
                                 //-- split ray
-                                //   test if start point behind or in front of plane
+                                //-- test if start point behind or in front of plane
                                 const int side = plane.Side(bRay.ExtrapOrigin());
 
@@ -2750 +1538 @@
 
 
-void VspBspTree::ExtractHalfSpaces(BspNode *n, vector<Plane3> &halfSpaces) const
-{
-        BspNode *lastNode;
-
-        do
-        {
-                lastNode = n;
-
-                // want to get planes defining geometry of this node => don't take
-                // split plane of node itself
-                n = n->GetParent();
-
-                if (n)
-                {
-                        BspInterior *interior = dynamic_cast<BspInterior *>(n);
-                        Plane3 halfSpace = dynamic_cast<BspInterior *>(interior)->GetPlane();
-
-            if (interior->GetBack() != lastNode)
-                                halfSpace.ReverseOrientation();
-
-                        halfSpaces.push_back(halfSpace);
-                }
-        }
-        while (n);
-}
-
-
-void VspBspTree::ConstructGeometry(BspNode *n,
-                                                                   BspNodeGeometry &geom) const
-{
-        vector<Plane3> halfSpaces;
-        ExtractHalfSpaces(n, halfSpaces);
-
-        PolygonContainer candidatePolys;
-        vector<Plane3> candidatePlanes;
-
-        vector<Plane3>::const_iterator pit, pit_end = halfSpaces.end();
-
-        // bounded planes are added to the polygons
-        for (pit = halfSpaces.begin(); pit != pit_end; ++ pit)
-        {
-                Polygon3 *p = GetBoundingBox().CrossSection(*pit);
-
-                if (p->Valid(mEpsilon))
-                {
-                        candidatePolys.push_back(p);
-                        candidatePlanes.push_back(*pit);
-                }
-        }
-
-        // add faces of bounding box (also could be faces of the cell)
-        for (int i = 0; i < 6; ++ i)
-        {
-                VertexContainer vertices;
-
-                for (int j = 0; j < 4; ++ j)
-                        vertices.push_back(mBox.GetFace(i).mVertices[j]);
-
-                Polygon3 *poly = new Polygon3(vertices);
-
-                candidatePolys.push_back(poly);
-                candidatePlanes.push_back(poly->GetSupportingPlane());
-        }
-
-        for (int i = 0; i < (int)candidatePolys.size(); ++ i)
-        {
-                // polygon is split by all other planes
-                for (int j = 0; (j < (int)halfSpaces.size()) && candidatePolys[i]; ++ j)
-                {
-                        if (i == j) // polygon and plane are coincident
-                                continue;
-
-                        VertexContainer splitPts;
-                        Polygon3 *frontPoly, *backPoly;
-
-                        const int cf =
-                                candidatePolys[i]->ClassifyPlane(halfSpaces[j],
-                                                                                                 mEpsilon);
-
-                        switch (cf)
-                        {
-                                case Polygon3::SPLIT:
-                                        frontPoly = new Polygon3();
-                                        backPoly = new Polygon3();
-
-                                        candidatePolys[i]->Split(halfSpaces[j],
-                                                                                         *frontPoly,
-                                                                                         *backPoly,
-                                                                                         mEpsilon);
-
-                                        DEL_PTR(candidatePolys[i]);
-
-                                        if (backPoly->Valid(mEpsilon))
-                                                candidatePolys[i] = backPoly;
-                                        else
-                                                DEL_PTR(backPoly);
-
-                                        // outside, don't need this
-                                        DEL_PTR(frontPoly);
-                                        break;
-                                // polygon outside of halfspace
-                                case Polygon3::FRONT_SIDE:
-                                        DEL_PTR(candidatePolys[i]);
-                                        break;
-                                // just take polygon as it is
-                                case Polygon3::BACK_SIDE:
-                                case Polygon3::COINCIDENT:
-                                default:
-                                        break;
-                        }
-                }
-
-                if (candidatePolys[i])
-                {
-                        geom.Add(candidatePolys[i], candidatePlanes[i]);
-                        //      geom.mPolys.push_back(candidates[i]);
-                }
-        }
-}
-
-
-void VspBspTree::ConstructGeometry(ViewCell *vc, 
-                                                                   BspNodeGeometry &vcGeom) const
-{
-        ViewCellContainer leaves;
-        
-        mViewCellsTree->CollectLeaves(vc, leaves);
-
-        ViewCellContainer::const_iterator it, it_end = leaves.end();
-
-        for (it = leaves.begin(); it != it_end; ++ it)
-        {
-                BspLeaf *l = dynamic_cast<BspViewCell *>(*it)->mLeaf;
-                
-                ConstructGeometry(l, vcGeom);
-        }
-}
-
-
-int VspBspTree::FindNeighbors(BspNode *n, vector<BspLeaf *> &neighbors,
+int VspOspTree::FindNeighbors(BspNode *n, vector<BspLeaf *> &neighbors,
                                                           const bool onlyUnmailed) const
 {
-        stack<bspNodePair> nodeStack;
-        
-        BspNodeGeometry nodeGeom;
-        ConstructGeometry(n, nodeGeom);
-//      const float eps = 0.5f;
-        const float eps = 0.01f;
-        // split planes from the root to this node
-        // needed to verify that we found neighbor leaf
-        // TODO: really needed?
-        vector<Plane3> halfSpaces;
-        ExtractHalfSpaces(n, halfSpaces);
-
-
-        BspNodeGeometry *rgeom = new BspNodeGeometry();
-        ConstructGeometry(mRoot, *rgeom);
-
-        nodeStack.push(bspNodePair(mRoot, rgeom));
-
-        while (!nodeStack.empty())
-        {
-                BspNode *node = nodeStack.top().first;
-                BspNodeGeometry *geom = nodeStack.top().second;
-        
-                nodeStack.pop();
-
-                if (node->IsLeaf())
-                {
-                        // test if this leaf is in valid view space
-                        if (node->TreeValid() &&
-                                (node != n) && 
-                                (!onlyUnmailed || !node->Mailed()))
-                        {
-                                bool isAdjacent = true;
-
-                                if (1)
-                                {
-                                        // test all planes of current node if still adjacent
-                                        for (int i = 0; (i < halfSpaces.size()) && isAdjacent; ++ i)
-                                        {
-                                                const int cf =
-                                                        Polygon3::ClassifyPlane(geom->GetPolys(),
-                                                                                                        halfSpaces[i],
-                                                                                                        eps);
-
-                                                if (cf == Polygon3::FRONT_SIDE)
-                                                {
-                                                        isAdjacent = false;
-                                                }
-                                        }
-                                }
-                                else
-                                {
-                                        // TODO: why is this wrong??
-                                        // test all planes of current node if still adjacent
-                                        for (int i = 0; (i < nodeGeom.Size()) && isAdjacent; ++ i)
-                                        {
-                                                Polygon3 *poly = nodeGeom.GetPolys()[i];
-
-                                                const int cf =
-                                                        Polygon3::ClassifyPlane(geom->GetPolys(),
-                                                                                                        poly->GetSupportingPlane(),
-                                                                                                        eps);
-
-                                                if (cf == Polygon3::FRONT_SIDE)
-                                                {
-                                                        isAdjacent = false;
-                                                }
-                                        }
-                                }
-                                // neighbor was found
-                                if (isAdjacent)
-                                {       
-                                        neighbors.push_back(dynamic_cast<BspLeaf *>(node));
-                                }
-                        }
-                }
-                else
-                {
-                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
-
-                        const int cf = Polygon3::ClassifyPlane(nodeGeom.GetPolys(),
-                                                                                                   interior->GetPlane(),
-                                                                                                   eps);
-                        
-                        BspNode *front = interior->GetFront();
-                        BspNode *back = interior->GetBack();
-            
-                        BspNodeGeometry *fGeom = new BspNodeGeometry();
-                        BspNodeGeometry *bGeom = new BspNodeGeometry();
-
-                        geom->SplitGeometry(*fGeom,
-                                                                *bGeom,
-                                                                interior->GetPlane(),
-                                                                mBox,
-                                                                //0.0000001f);
-                                                                eps);
-                
-                        if (cf == Polygon3::BACK_SIDE)
-                        {
-                                nodeStack.push(bspNodePair(interior->GetBack(), bGeom));
-                                DEL_PTR(fGeom);
-                        }
-                        else
-                        {
-                                if (cf == Polygon3::FRONT_SIDE)
-                                {
-                                        nodeStack.push(bspNodePair(interior->GetFront(), fGeom));
-                                        DEL_PTR(bGeom);
-                                }
-                                else
-                                {       // random decision
-                                        nodeStack.push(bspNodePair(front, fGeom));
-                                        nodeStack.push(bspNodePair(back, bGeom));
-                                }
-                        }
-                }
-        
-                DEL_PTR(geom);
-        }
-
-        return (int)neighbors.size();
-}
-
-
-
-int VspBspTree::FindApproximateNeighbors(BspNode *n, 
-                                                                                 vector<BspLeaf *> &neighbors,
-                                                                                 const bool onlyUnmailed) const
-{
-        stack<bspNodePair> nodeStack;
-        
-        BspNodeGeometry nodeGeom;
-        ConstructGeometry(n, nodeGeom);
-        
-        float eps = 0.01f;
-        // split planes from the root to this node
-        // needed to verify that we found neighbor leaf
-        // TODO: really needed?
-        vector<Plane3> halfSpaces;
-        ExtractHalfSpaces(n, halfSpaces);
-
-
-        BspNodeGeometry *rgeom = new BspNodeGeometry();
-        ConstructGeometry(mRoot, *rgeom);
-
-        nodeStack.push(bspNodePair(mRoot, rgeom));
-
-        while (!nodeStack.empty())
-        {
-                BspNode *node = nodeStack.top().first;
-                BspNodeGeometry *geom = nodeStack.top().second;
-        
-                nodeStack.pop();
-
-                if (node->IsLeaf())
-                {
-                        // test if this leaf is in valid view space
-                        if (node->TreeValid() &&
-                                (node != n) && 
-                                (!onlyUnmailed || !node->Mailed()))
-                        {
-                                bool isAdjacent = true;
-
-                                // neighbor was found
-                                if (isAdjacent)
-                                {       
-                                        neighbors.push_back(dynamic_cast<BspLeaf *>(node));
-                                }
-                        }
-                }
-                else
-                {
-                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
-
-                        const int cf = Polygon3::ClassifyPlane(nodeGeom.GetPolys(),
-                                                                                                   interior->GetPlane(),
-                                                                                                   eps);
-                        
-                        BspNode *front = interior->GetFront();
-                        BspNode *back = interior->GetBack();
-            
-                        BspNodeGeometry *fGeom = new BspNodeGeometry();
-                        BspNodeGeometry *bGeom = new BspNodeGeometry();
-
-                        geom->SplitGeometry(*fGeom,
-                                                                *bGeom,
-                                                                interior->GetPlane(),
-                                                                mBox,
-                                                                //0.0000001f);
-                                                                eps);
-                
-                        if (cf == Polygon3::BACK_SIDE)
-                        {
-                                nodeStack.push(bspNodePair(interior->GetBack(), bGeom));
-                                DEL_PTR(fGeom);
-                                }
-                        else
-                        {
-                                if (cf == Polygon3::FRONT_SIDE)
-                                {
-                                        nodeStack.push(bspNodePair(interior->GetFront(), fGeom));
-                                        DEL_PTR(bGeom);
-                                }
-                                else
-                                {       // random decision
-                                        nodeStack.push(bspNodePair(front, fGeom));
-                                        nodeStack.push(bspNodePair(back, bGeom));
-                                }
-                        }
-                }
-        
-                DEL_PTR(geom);
-        }
-
-        return (int)neighbors.size();
-}
-
-
-
-BspLeaf *VspBspTree::GetRandomLeaf(const Plane3 &halfspace)
-{
+        // TODO
+        return 0;
+}
+
+
+BspLeaf *VspOspTree::GetRandomLeaf(const Plane3 &halfspace)
+{
+#if TODO
     stack<BspNode *> nodeStack;
         nodeStack.push(mRoot);
@@ -3157 +1593 @@
                 }
         }
-
+#endif
         return NULL;
 }
 
 
-BspLeaf *VspBspTree::GetRandomLeaf(const bool onlyUnmailed)
+BspLeaf *VspOspTree::GetRandomLeaf(const bool onlyUnmailed)
 {
         stack<BspNode *> nodeStack;
@@ -3198 +1634 @@
 
 
-int VspBspTree::ComputePvsSize(const RayInfoContainer &rays) const
+int VspOspTree::ComputePvsSize(const RayInfoContainer &rays) const
 {
         int pvsSize = 0;
@@ -3232 +1668 @@
 
 
-float VspBspTree::GetEpsilon() const
+float VspOspTree::GetEpsilon() const
 {
         return mEpsilon;
@@ -3238 +1674 @@
 
 
-int VspBspTree::SplitPolygons(const Plane3 &plane,
-                                                          PolygonContainer &polys,
-                                                          PolygonContainer &frontPolys,
-                                                          PolygonContainer &backPolys,
-                                                          PolygonContainer &coincident) const
-{
-        int splits = 0;
-
-        PolygonContainer::const_iterator it, it_end = polys.end();
-
-        for (it = polys.begin(); it != polys.end(); ++ it)      
-        {
-                Polygon3 *poly = *it;
-
-                // classify polygon
-                const int cf = poly->ClassifyPlane(plane, mEpsilon);
-
-                switch (cf)
-                {
-                        case Polygon3::COINCIDENT:
-                                coincident.push_back(poly);
-                                break;
-                        case Polygon3::FRONT_SIDE:
-                                frontPolys.push_back(poly);
-                                break;
-                        case Polygon3::BACK_SIDE:
-                                backPolys.push_back(poly);
-                                break;
-                        case Polygon3::SPLIT:
-                                backPolys.push_back(poly);
-                                frontPolys.push_back(poly);
-                                ++ splits;
-                                break;
-                        default:
-                Debug << "SHOULD NEVER COME HERE\n";
-                                break;
-                }
-        }
-
-        return splits;
-}
-
-
-int VspBspTree::CastLineSegment(const Vector3 &origin,
+
+int VspOspTree::CastLineSegment(const Vector3 &origin,
                                                                 const Vector3 &termination,
                                                                 ViewCellContainer &viewcells)
@@ -3387 +1781 @@
 
 
-
-int VspBspTree::TreeDistance(BspNode *n1, BspNode *n2) const
-{
-        std::deque<BspNode *> path1;
-        BspNode *p1 = n1;
-
-        // create path from node 1 to root
-        while (p1)
-        {
-                if (p1 == n2) // second node on path
-                        return (int)path1.size();
-
-                path1.push_front(p1);
-                p1 = p1->GetParent();
-        }
-
-        int depth = n2->GetDepth();
-        int d = depth;
-
-        BspNode *p2 = n2;
-
-        // compare with same depth
-        while (1)
-        {
-                if ((d < (int)path1.size()) && (p2 == path1[d]))
-                        return (depth - d) + ((int)path1.size() - 1 - d);
-
-                -- d;
-                p2 = p2->GetParent();
-        }
-
-        return 0; // never come here
-}
-
-
-BspNode *VspBspTree::CollapseTree(BspNode *node, int &collapsed)
+BspNode *VspOspTree::CollapseTree(BspNode *node, int &collapsed)
 {
 // TODO
@@ -3464 +1823 @@
 
 
-int VspBspTree::CollapseTree()
+int VspOspTree::CollapseTree()
 {
         int collapsed = 0;
@@ -3478 +1837 @@
 
 
-void VspBspTree::RepairViewCellsLeafLists()
+void VspOspTree::RepairViewCellsLeafLists()
 {
 // TODO
@@ -3521 +1880 @@
 
 
-typedef pair<BspNode *, BspNodeGeometry *> bspNodePair;
-
-
-int VspBspTree::CastBeam(Beam &beam)
-{
-    stack<bspNodePair> nodeStack;
-        BspNodeGeometry *rgeom = new BspNodeGeometry();
-        ConstructGeometry(mRoot, *rgeom);
-
-        nodeStack.push(bspNodePair(mRoot, rgeom));
-  
-        ViewCell::NewMail();
-
-        while (!nodeStack.empty()) 
-        {
-                BspNode *node = nodeStack.top().first;
-                BspNodeGeometry *geom = nodeStack.top().second;
-                nodeStack.pop();
-                
-                AxisAlignedBox3 box;
-                geom->GetBoundingBox(box);
-
-                const int side = beam.ComputeIntersection(box);
-                
-                switch (side) 
-                {
-                case -1:
-                        CollectViewCells(node, true, beam.mViewCells, true);
-                        break;
-                case 0:
-                        
-                        if (node->IsLeaf())
-                        {
-                                BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
-                        
-                                if (!leaf->GetViewCell()->Mailed() && leaf->TreeValid())
-                                {
-                                        leaf->GetViewCell()->Mail();
-                                        beam.mViewCells.push_back(leaf->GetViewCell());
-                                }
-                        }
-                        else 
-                        {
-                                BspInterior *interior = dynamic_cast<BspInterior *>(node);
-                        
-                                BspNode *first = interior->GetFront();
-                                BspNode *second = interior->GetBack();
-            
-                                BspNodeGeometry *firstGeom = new BspNodeGeometry();
-                                BspNodeGeometry *secondGeom = new BspNodeGeometry();
-
-                                geom->SplitGeometry(*firstGeom,
-                                                                        *secondGeom,
-                                                                        interior->GetPlane(),
-                                                                        mBox,
-                                                                        //0.0000001f);
-                                                                        mEpsilon);
-
-                                // decide on the order of the nodes
-                                if (DotProd(beam.mPlanes[0].mNormal, 
-                                        interior->GetPlane().mNormal) > 0)
-                                {
-                                        swap(first, second);
-                                        swap(firstGeom, secondGeom);
-                                }
-
-                                nodeStack.push(bspNodePair(first, firstGeom));
-                                nodeStack.push(bspNodePair(second, secondGeom));
-                        }
-                        
-                        break;
-                default:
-                        // default: cull
-                        break;
-                }
-                
-                DEL_PTR(geom);
-                
-        }
-
-        return (int)beam.mViewCells.size();
-}
-
-
-void VspBspTree::SetViewCellsManager(ViewCellsManager *vcm)
-{
-        mViewCellsManager = vcm;
-}
-
-
-int VspBspTree::CollectMergeCandidates(const vector<BspLeaf *> leaves,
-                                                                           vector<MergeCandidate> &candidates)
-{
-        BspLeaf::NewMail();
-        
-        vector<BspLeaf *>::const_iterator it, it_end = leaves.end();
-
-        int numCandidates = 0;
-
-        // find merge candidates and push them into queue
-        for (it = leaves.begin(); it != it_end; ++ it)
-        {
-                BspLeaf *leaf = *it;
-                
-                // the same leaves must not be part of two merge candidates
-                leaf->Mail();
-                
-                vector<BspLeaf *> neighbors;
-                
-                // appoximate neighbor search has slightl relaxed constraints
-                if (1)
-                        FindNeighbors(leaf, neighbors, true);
-                else
-                        FindApproximateNeighbors(leaf, neighbors, true);
-
-                vector<BspLeaf *>::const_iterator nit, nit_end = neighbors.end();
-
-                // TODO: test if at least one ray goes from one leaf to the other
-                for (nit = neighbors.begin(); nit != nit_end; ++ nit)
-                {
-                        if ((*nit)->GetViewCell() != leaf->GetViewCell())
-                        {
-                                MergeCandidate mc(leaf->GetViewCell(), (*nit)->GetViewCell());
-
-                                // dont't merge view cells if they are empty and not front and back leaf of the same parent
-                                // in the tree?
-                                if (mEmptyViewCellsMergeAllowed ||
-                                        !leaf->GetViewCell()->GetPvs().Empty() || 
-                                        !(*nit)->GetViewCell()->GetPvs().Empty() ||
-                    leaf->IsSibling(*nit))
-                                {
-                                        candidates.push_back(mc);
-                                }
-
-                                ++ numCandidates;
-                                if ((numCandidates % 1000) == 0)
-                                {
-                                        cout << "collected " << numCandidates << " merge candidates" << endl;
-                                }
-                        }
-                }
-        }
-
-        Debug << "merge queue: " << (int)candidates.size() << endl;
-        Debug << "leaves in queue: " << numCandidates << endl;
-        
-
-        return (int)leaves.size();
-}
-
-
-int VspBspTree::CollectMergeCandidates(const VssRayContainer &rays, 
-                                                                           vector<MergeCandidate> &candidates)
-{
-        ViewCell::NewMail();
-        long startTime = GetTime();
-        
-        map<BspLeaf *, vector<BspLeaf*> > neighborMap;
-        ViewCellContainer::const_iterator iit;
-
-        int numLeaves = 0;
-        
-        BspLeaf::NewMail();
-
-        for (int i = 0; i < (int)rays.size(); ++ i)
-        {  
-                VssRay *ray = rays[i];
-        
-                // traverse leaves stored in the rays and compare and 
-                // merge consecutive leaves (i.e., the neighbors in the tree)
-                if (ray->mViewCells.size() < 2)
-                        continue;
-//TODO viewcellhierarchy
-                iit = ray->mViewCells.begin();
-                BspViewCell *bspVc = dynamic_cast<BspViewCell *>(*(iit ++));
-                BspLeaf *leaf = bspVc->mLeaf;
-                
-                // traverse intersections 
-                // consecutive leaves are neighbors => add them to queue
-                for (; iit != ray->mViewCells.end(); ++ iit)
-                {
-                        // next pair
-                        BspLeaf *prevLeaf = leaf;
-                        bspVc = dynamic_cast<BspViewCell *>(*iit);
-            leaf = bspVc->mLeaf;
-
-                        // view space not valid or same view cell
-                        if (!leaf->TreeValid() || !prevLeaf->TreeValid() ||
-                                (leaf->GetViewCell() == prevLeaf->GetViewCell()))
-                                continue;
-
-                vector<BspLeaf *> &neighbors = neighborMap[leaf];
-                        
-                        bool found = false;
-
-                        // both leaves inserted in queue already =>
-                        // look if double pair already exists
-                        if (leaf->Mailed() && prevLeaf->Mailed())
-                        {
-                                vector<BspLeaf *>::const_iterator it, it_end = neighbors.end();
-                                
-                for (it = neighbors.begin(); !found && (it != it_end); ++ it)
-                                        if (*it == prevLeaf)
-                                                found = true; // already in queue
-                        }
-                
-                        if (!found)
-                        {
-                                // this pair is not in map yet
-                                // => insert into the neighbor map and the queue
-                                neighbors.push_back(prevLeaf);
-                                neighborMap[prevLeaf].push_back(leaf);
-
-                                leaf->Mail();
-                                prevLeaf->Mail();
-                
-                                MergeCandidate mc(leaf->GetViewCell(), prevLeaf->GetViewCell());
-                                
-                                candidates.push_back(mc);
-
-                                if (((int)candidates.size() % 1000) == 0)
-                                {
-                                        cout << "collected " << (int)candidates.size() << " merge candidates" << endl;
-                                }
-                        }
-        }
-        }
-
-        Debug << "neighbormap size: " << (int)neighborMap.size() << endl;
-        Debug << "merge queue: " << (int)candidates.size() << endl;
-        Debug << "leaves in queue: " << numLeaves << endl;
-
-
-        //-- collect the leaves which haven't been found by ray casting
-        if (0)
-        {
-                cout << "finding additional merge candidates using geometry" << endl;
-                vector<BspLeaf *> leaves;
-                CollectLeaves(leaves, true);
-                Debug << "found " << (int)leaves.size() << " new leaves" << endl << endl;
-                CollectMergeCandidates(leaves, candidates);
-        }
-
-        return numLeaves;
-}
-
-
-
-
-ViewCell *VspBspTree::GetViewCell(const Vector3 &point, const bool active)
+
+ViewCell *VspOspTree::GetViewCell(const Vector3 &point, const bool active)
 {
         if (mRoot == NULL)
@@ -3809 +1920 @@
 
 
-bool VspBspTree::ViewPointValid(const Vector3 &viewPoint) const
+bool VspOspTree::ViewPointValid(const Vector3 &viewPoint) const
 {
         BspNode *node = mRoot;
@@ -3839 +1950 @@
 
 
-void VspBspTree::PropagateUpValidity(BspNode *node)
+void VspOspTree::PropagateUpValidity(BspNode *node)
 {
         const bool isValid = node->TreeValid();
@@ -3868 +1979 @@
 
 #if ZIPPED_VIEWCELLS
-bool VspBspTree::Export(ogzstream &stream)
+bool VspOspTree::Export(ogzstream &stream)
 #else
-bool VspBspTree::Export(ofstream &stream)
+bool VspOspTree::Export(ofstream &stream)
 #endif
 {
@@ -3878 +1989 @@
 }
 
+
 #if ZIPPED_VIEWCELLS
-void VspBspTree::ExportNode(BspNode *node, ogzstream &stream)
+void VspOspTree::ExportNode(BspNode *node, ogzstream &stream)
 #else
-void VspBspTree::ExportNode(BspNode *node, ofstream &stream)
+void VspOspTree::ExportNode(BspNode *node, ofstream &stream)
 #endif
 {