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

Timestamp:

06/18/06 03:47:06 (18 years ago)

Author:

mattausch

Message:

worked on view-object space partition
fixed some loading bugs
fixeds some exporting bugs using line segments
enabling other methods for view space sampling in ViewCellsManager? OBJECT_DIRECTION_BASED_DISTRIBUTION)
added class interface for a sampling strategy

File:

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

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

@@ -16 +16 @@
 #include "ViewCellsManager.h"
 #include "Beam.h"
+#include "KdTree.h"
+
 
 namespace GtpVisibilityPreprocessor {
@@ -381 +383 @@
 
 
-void VspTree::Construct(const VssRayContainer &sampleRays,
-                                                   AxisAlignedBox3 *forcedBoundingBox)
+void VspTree::PrepareConstruction(const VssRayContainer &sampleRays,
+                                                                  AxisAlignedBox3 *forcedBoundingBox) 
 {
         mVspStats.nodes = 1;
-        mBox.Initialize();      // initialise BSP tree bounding box
+        mBoundingBox.Initialize();      // initialise vsp tree bounding box
 
         if (forcedBoundingBox)
-                mBox = *forcedBoundingBox;
-        
-        PolygonContainer polys;
-        RayInfoContainer *rays = new RayInfoContainer();
-
+                mBoundingBox = *forcedBoundingBox;
+        
         VssRayContainer::const_iterator rit, rit_end = sampleRays.end();
 
-        long startTime = GetTime();
-
-        cout << "Extracting polygons from rays ... ";
-
         Intersectable::NewMail();
 
-        int numObj = 0;
-
-        //-- store rays
+        //-- compute bounding box
         for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
         {
                 VssRay *ray = *rit;
 
-                float minT, maxT;
-
-                static Ray hray;
-                hray.Init(*ray);
-
-                // TODO: not very efficient to implictly cast between rays types
-                if (mBox.GetRaySegment(hray, minT, maxT))
-                {
-                        float len = ray->Length();
-
-                        if (!len)
-                                len = Limits::Small;
-
-                        rays->push_back(RayInfo(ray, minT / len, maxT / len));
-                }
-        }
-
-        mTermMinProbability *= mBox.GetVolume();
-
+                // compute bounding box of view space
+                if (!forcedBoundingBox)
+                {
+                        mBoundingBox.Include(ray->GetTermination());
+                        mBoundingBox.Include(ray->GetOrigin());
+                }
+        }
+
+        mTermMinProbability *= mBoundingBox.GetVolume();
         mGlobalCostMisses = 0;
-
-        cout << "finished" << endl;
-
-        // use split cost priority queue
-        Construct(rays);
+}
+
+
+void VspTree::AddSubdivisionStats(const int viewCells,
+                                                                  const float renderCostDecr,
+                                                                  const float splitCandidateCost,
+                                                                  const float totalRenderCost,
+                                                                         const float avgRenderCost)
+{
+        mSubdivisionStats 
+                        << "#ViewCells\n" << viewCells << endl
+                        << "#RenderCostDecrease\n" << renderCostDecr << endl 
+                        << "#SplitCandidateCost\n" << splitCandidateCost << endl
+                        << "#TotalRenderCost\n" << totalRenderCost << endl
+                        << "#AvgRenderCost\n" << avgRenderCost << endl;
 }
 
@@ -449 +442 @@
 
 
-void VspTree::Construct(RayInfoContainer *rays)
-{
-#if TODO
-        VspSplitQueue tQueue;
-        /// create new vsp tree
-        mRoot = new VspLeaf();
-        /// we use the overall probability as normalizer
-        const float prop = mBox.GetVolume();
-
-        VspTraversalData tData(mRoot,
-                                                  0,
-                                                  rays,
-                          ComputePvsSize(*rays),
-                                                  prop,
-                                                  mBox);
-
-
-        // compute first split candidate
-        VspSplitCandidate splitCandidate;
-        EvalSplitCandidate(tData, splitCandidate);
-
-        tQueue.push(splitCandidate);
-
-        mTotalCost = tData.mPvs * tData.mProbability / mBox.GetVolume();
-        mTotalPvsSize = tData.mPvs;
-        
-        mSubdivisionStats 
-                        << "#ViewCells\n1\n" <<  endl
-                        << "#RenderCostDecrease\n0\n" << endl 
-                        << "#SplitCandidateCost\n0\n" << endl
-                        << "#TotalRenderCost\n" << mTotalCost << endl
-                        << "#AvgRenderCost\n" << mTotalPvsSize << endl;
-
-        Debug << "total cost: " << mTotalCost << endl;
-        
-        
-        mVspStats.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())
-        {
-                splitCandidate = tQueue.top();
-            tQueue.pop();               
-
-                // cost ratio of cost decrease / totalCost
-                float costRatio = splitCandidate.GetCost() / mTotalCost;
-
-                //Debug << "cost ratio: " << costRatio << endl;
-
-                if (costRatio < mTermMinGlobalCostRatio)
-                        ++ mGlobalCostMisses;
-                
-                if (0 && !mOutOfMemory)
-                {
-                        float mem = GetMemUsage();
-
-                        if (mem > mMaxMemory)
-                        {
-                                mOutOfMemory = true;
-                                Debug << "memory limit reached: " << mem << endl;
-                        }
-                }
-
-                // subdivide leaf node
-                VspNode *r = Subdivide(tQueue, splitCandidate);
-
-                if (r == mRoot)
-                        Debug << "VSP BSP tree construction time spent at root: "
-                                  << TimeDiff(startTime, GetTime())*1e-3 << "s" << endl;
-
-                if (mVspStats.Leaves() >= nLeaves)
-                {
-                        nLeaves += 500;
-
-                        cout << "leaves=" << mVspStats.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";
-
-        mVspStats.Stop();
-#endif
-}
-
-
 bool VspTree::LocalTerminationCriteriaMet(const VspTraversalData &data) const
 {
@@ -577 +462 @@
 
 
-// subdivide using a split plane queue
 VspNode *VspTree::Subdivide(SplitQueue &tQueue,
-                                                        VspSplitCandidate &splitCandidate)
+                                                        VspSplitCandidate &splitCandidate,
+                                                        const bool globalCriteriaMet)
 {
         VspTraversalData &tData = splitCandidate.mParentData;
@@ -585 +470 @@
         VspNode *newNode = tData.mNode;
 
-        if (!LocalTerminationCriteriaMet(tData) && !GlobalTerminationCriteriaMet(tData))
+        if (!LocalTerminationCriteriaMet(tData) && !globalCriteriaMet)
         {       
                 VspTraversalData tFrontData;
@@ -594 +479 @@
                 // create new interior node and two leaf node
                 const AxisAlignedPlane splitPlane = splitCandidate.mSplitPlane;
-
                 newNode = SubdivideNode(splitPlane, tData, tFrontData, tBackData);
         
@@ -604 +488 @@
                 tBackData.mMaxCostMisses = maxCostMisses;
                         
-                
+                //-- statistics
                 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();
+                        const float cFront = (float)tFrontData.mPvs * tFrontData.mProbability;
+                        const float cBack = (float)tBackData.mPvs * tBackData.mProbability;
+                        const float cData = (float)tData.mPvs * tData.mProbability;
+        
+                        const float costDecr = 
+                                (cFront + cBack - cData) / mBoundingBox.GetVolume();
 
                         mTotalCost += costDecr;
                         mTotalPvsSize += tFrontData.mPvs + tBackData.mPvs - tData.mPvs;
 
-                        mSubdivisionStats 
-                                        << "#ViewCells\n" << mVspStats.Leaves() << endl
-                                        << "#RenderCostDecrease\n" << -costDecr << endl
-                                        << "#SplitCandidateCost\n" << splitCandidate.GetPriority() << endl
-                                        << "#TotalRenderCost\n" << mTotalCost << endl
-                                        << "#AvgRenderCost\n" << (float)mTotalPvsSize / (float)mVspStats.Leaves() << endl;
-                }
-
-        
-                //-- push the new split candidates on the stack
-                VspSplitCandidate frontCandidate;
-                VspSplitCandidate backCandidate;
-
-                EvalSplitCandidate(tFrontData, frontCandidate);
-                EvalSplitCandidate(tBackData, backCandidate);
-#if TODO
+                        AddSubdivisionStats(mVspStats.Leaves(),
+                                                                -costDecr,
+                                                                splitCandidate.GetPriority(),
+                                                                mTotalCost,
+                                                                (float)mTotalPvsSize / (float)mVspStats.Leaves());
+                }
+
+        
+                //-- push the new split candidates on the queue
+                VspSplitCandidate *frontCandidate = new VspSplitCandidate();
+                VspSplitCandidate *backCandidate = new VspSplitCandidate();
+
+                EvalSplitCandidate(tFrontData, *frontCandidate);
+                EvalSplitCandidate(tBackData, *backCandidate);
+
                 tQueue.push(frontCandidate);
                 tQueue.push(backCandidate);
-#endif
+
                 // delete old leaf node
                 DEL_PTR(tData.mNode);
@@ -646 +528 @@
         {
                 VspLeaf *leaf = dynamic_cast<VspLeaf *>(newNode);
+        
                 VspViewCell *viewCell = new VspViewCell();
-
         leaf->SetViewCell(viewCell);
                 
@@ -671 +553 @@
                         }
                 }
-
-                // should I check here?
+                
                 viewCell->mLeaf = leaf;
 
@@ -678 +559 @@
         leaf->mProbability = tData.mProbability;
 
-                EvaluateLeafStats(tData);               
+                // finally evaluate stats until this leaf
+                EvaluateLeafStats(tData);
         }
 
         //-- cleanup
         tData.Clear();
-
+        
         return newNode;
 }
@@ -691 +573 @@
                                                                  VspSplitCandidate &splitData)
 {
-        VspTraversalData frontData;
-        VspTraversalData backData;
-
+        float frontProb;
+        float backtProb;
+        
         VspLeaf *leaf = dynamic_cast<VspLeaf *>(tData.mNode);
-
+        
         // compute locally best split plane
         const bool success = 
                 SelectPlane(tData, splitData.mSplitPlane,
-                                        frontData.mProbability, backData.mProbability);
+                                        frontProb, backtProb);
 
         //TODO
@@ -789 +671 @@
         return interior;
 }
-
-/*
-KdNode *VspOpsTree::SubdivideSpatialNode(KdLeaf *leaf,
-                                                                                 const AxisAlignedPlane &splitPlane,
-                                                                                 const AxisAlignedBox3 &box,
-                                                                                 AxisAlignedBox3 &backBBox,
-                                                                                 AxisAlignedBox3 &frontBBox)
-{
-        float position;
-
-#if TODO
-    mSpatialStat.nodes += 2;
-        mSpatialStat.splits[axis];
-#endif
-
-        // add the new nodes to the tree
-        KdInterior *node = new KdInterior(leaf->mParent);
-
-        node->mAxis = splitPlane.mAxis;
-        node->mPosition = splitPlane.mPosition;
-        node->mBox = box;
-
-    backBBox = box;
-        frontBBox = box;
-  
-        // first count ray sides
-        int objectsBack = 0;
-        int objectsFront = 0;
-  
-        backBBox.SetMax(axis, position);
-        frontBBox.SetMin(axis, position);
-
-        SplitObjects(leaf->m
-        ObjectContainer::const_iterator mi, mi_end = leaf->mObjects.end();
-
-        for ( mi = leaf->mObjects.begin(); mi != mi_end; ++ mi) 
-        {
-                // determine the side of this ray with respect to the plane
-                AxisAlignedBox3 box = (*mi)->GetBox();
-                
-                if (box.Max(axis) > position ) 
-                        ++ objectsFront;
-    
-                if (box.Min(axis) < position )
-      objectsBack++;
-  }
-
-  
-  KdLeaf *back = new KdLeaf(node, objectsBack);
-  KdLeaf *front = new KdLeaf(node, objectsFront);
-
-  // replace a link from node's parent
-  if (  leaf->mParent )
-    leaf->mParent->ReplaceChildLink(leaf, node);
-
-  // and setup child links
-  node->SetupChildLinks(back, front);
-  
-  for (mi = leaf->mObjects.begin();
-       mi != leaf->mObjects.end();
-       mi++) {
-    // determine the side of this ray with respect to the plane
-    AxisAlignedBox3 box = (*mi)->GetBox();
-
-    if (box.Max(axis) >= position )
-      front->mObjects.push_back(*mi);
-    
-    if (box.Min(axis) < position )
-      back->mObjects.push_back(*mi);
-    
-    mStat.objectRefs -= (int)leaf->mObjects.size();
-    mStat.objectRefs += objectsBack + objectsFront;
-  }
-  
-  delete leaf;
-  return node;
-}
-*/
-
 
 
@@ -1267 +1070 @@
                 
 
-        // -- pvs rendering heuristics
+        //-- 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(totalPvs, lowerPvsLimit, upperPvsLimit);
-    const float penaltyFront = EvalPvsPenalty(pvsFront, lowerPvsLimit, upperPvsLimit);
-        const float penaltyBack = EvalPvsPenalty(pvsBack, lowerPvsLimit, upperPvsLimit);
+        //-- 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;
@@ -1280 +1083 @@
 
         //Debug << "decrease: " << oldRenderCost - newRenderCost << endl;
-        const float renderCostDecrease = (oldRenderCost - newRenderCost) / mBox.GetVolume();
+        const float renderCostDecrease = (oldRenderCost - newRenderCost) / mBoundingBox.GetVolume();
         
 
 #if 1
-        // take render cost of node into account to avoid being stuck in a local minimum
-        const float normalizedOldRenderCost = oldRenderCost / mBox.GetVolume();
+        // take render cost of node into account 
+        // otherwise danger of being stuck in a local minimum!!
+        const float normalizedOldRenderCost = oldRenderCost / mBoundingBox.GetVolume();
         return 0.99f * renderCostDecrease + 0.01f * normalizedOldRenderCost;
 #else
@@ -1434 +1238 @@
 AxisAlignedBox3 VspTree::GetBoundingBox() const
 {
-        return mBox;
+        return mBoundingBox;
 }
 
@@ -1581 +1385 @@
 void VspTree::ValidateTree()
 {
+        mVspStats.invalidLeaves = 0;
+
         stack<VspNode *> nodeStack;
 
@@ -1587 +1393 @@
 
         nodeStack.push(mRoot);
-        
-        mVspStats.invalidLeaves = 0;
+
         while (!nodeStack.empty()) 
         {
@@ -1662 +1467 @@
                 }
         }
-
 }
 
 
 int VspTree::FindNeighbors(VspLeaf *n,
-                                                          vector<VspLeaf *> &neighbors,
-                                                          const bool onlyUnmailed) const
+                                                   vector<VspLeaf *> &neighbors,
+                                                   const bool onlyUnmailed) const
 {
         stack<VspNode *> nodeStack;
-
         nodeStack.push(mRoot);
 
@@ -1946 +1749 @@
         float maxt, mint;
 
-        if (!mBox.GetRaySegment(ray, mint, maxt))
+        if (!mBoundingBox.GetRaySegment(ray, mint, maxt))
                 return 0;
 
@@ -1978 +1781 @@
                                         // cases N1,N2,N3,P5,Z2,Z3
                                         continue;
-                                } else
+                                } 
+                                else
                                 {
                                         // case N4
@@ -2020 +1824 @@
                                 ++ hits;
                         }
-
 #if 0
-                                leaf->mRays.push_back(RayInfo(new VssRay(origin, termination, NULL, NULL, 0)));
+                        leaf->mRays.push_back(RayInfo(new VssRay(origin, termination, NULL, NULL, 0)));
 #endif
                         // get the next node from the stack
@@ -2088 +1891 @@
 {
         int collapsed = 0;
-        //TODO
-#if HAS_TO_BE_REDONE
+
         (void)CollapseTree(mRoot, collapsed);
-
         // revalidate leaves
         RepairViewCellsLeafLists();
-#endif
+
         return collapsed;
 }
@@ -2286 +2087 @@
 
 int VspTree::SplitRays(const AxisAlignedPlane &plane,
-                                                  RayInfoContainer &rays,
-                                                  RayInfoContainer &frontRays,
-                                                  RayInfoContainer &backRays) const
+                                           RayInfoContainer &rays,
+                                           RayInfoContainer &frontRays,
+                                           RayInfoContainer &backRays) const
 {
         int splits = 0;
@@ -2338 +2139 @@
 {
         if (!node->GetParent())
-                return mBox;
+                return mBoundingBox;
 
         if (!node->IsLeaf())
@@ -2358 +2159 @@
 
 
+
+/*****************************************************************/
+/*                class OpsTree implementation                   */
+/*****************************************************************/
+
+
+void OspTree::SplitObjects(const AxisAlignedPlane & splitPlane,
+                                                   const ObjectContainer &objects,
+                                                   ObjectContainer &back,
+                                                   ObjectContainer &front)
+{
+        ObjectContainer::const_iterator oit, oit_end = objects.end();
+
+    for (oit = objects.begin(); oit != oit_end; ++ oit) 
+        {
+                // determine the side of this ray with respect to the plane
+                const AxisAlignedBox3 box = (*oit)->GetBox();
+
+                if (box.Max(splitPlane.mAxis) >= splitPlane.mPosition)
+            front.push_back(*oit);
+    
+                if (box.Min(splitPlane.mAxis) < splitPlane.mPosition)
+                        back.push_back(*oit);
+#if TODO    
+                mStat.objectRefs -= (int)objects.size();
+                mStat.objectRefs += objectsBack + objectsFront;
+#endif
+        }
+}
+
+
+KdInterior *OspTree::SubdivideNode(KdLeaf *leaf,
+                                                                   const AxisAlignedPlane &splitPlane,
+                                                                   const AxisAlignedBox3 &box,
+                                                                   AxisAlignedBox3 &backBBox,
+                                                                   AxisAlignedBox3 &frontBBox)
+{
+#if TODO
+    mSpatialStat.nodes += 2;
+        mSpatialStat.splits[axis];
+#endif
+
+        // add the new nodes to the tree
+        KdInterior *node = new KdInterior(leaf->mParent);
+
+        const int axis = splitPlane.mAxis;
+        const float position = splitPlane.mPosition;
+
+        node->mAxis = axis;
+        node->mPosition = position;
+        node->mBox = box;
+
+    backBBox = box;
+        frontBBox = box;
+  
+        // first count ray sides
+        int objectsBack = 0;
+        int objectsFront = 0;
+  
+        backBBox.SetMax(axis, position);
+        frontBBox.SetMin(axis, position);
+
+        ObjectContainer::const_iterator mi, mi_end = leaf->mObjects.end();
+
+        for ( mi = leaf->mObjects.begin(); mi != mi_end; ++ mi) 
+        {
+                // determine the side of this ray with respect to the plane
+                const AxisAlignedBox3 box = (*mi)->GetBox();
+                
+                if (box.Max(axis) > position) 
+                        ++ objectsFront;
+    
+                if (box.Min(axis) < position)
+                        ++ objectsBack;
+        }
+
+        KdLeaf *back = new KdLeaf(node, objectsBack);
+        KdLeaf *front = new KdLeaf(node, objectsFront);
+
+        // replace a link from node's parent
+        if (leaf->mParent)
+                leaf->mParent->ReplaceChildLink(leaf, node);
+
+        // and setup child links
+        node->SetupChildLinks(back, front);
+
+        SplitObjects(splitPlane, leaf->mObjects, back->mObjects, front->mObjects);
+  
+        //delete leaf;
+        return node;
+}
+
+
+KdNode *OspTree::Subdivide(SplitQueue &tQueue,
+                                                   OspSplitCandidate &splitCandidate,
+                                                   const bool globalCriteriaMet)
+{
+        OspTraversalData &tData = splitCandidate.mParentData;
+
+        KdNode *newNode = tData.mNode;
+
+        if (!LocalTerminationCriteriaMet(tData) && !globalCriteriaMet)
+        {       
+                OspTraversalData tFrontData;
+                OspTraversalData tBackData;
+
+                //-- continue subdivision
+                
+                // create new interior node and two leaf node
+                const AxisAlignedPlane splitPlane = splitCandidate.mSplitPlane;
+                newNode = SubdivideNode(dynamic_cast<KdLeaf *>(newNode), 
+                                                                splitPlane, 
+                                                                tData.mBoundingBox, 
+                                                                tFrontData.mBoundingBox, 
+                                                                tBackData.mBoundingBox);
+        
+                const int maxCostMisses = splitCandidate.mMaxCostMisses;
+
+                // how often was max cost ratio missed in this branch?
+                tFrontData.mMaxCostMisses = maxCostMisses;
+                tBackData.mMaxCostMisses = maxCostMisses;
+                        
+                //-- push the new split candidates on the queue
+                OspSplitCandidate *frontCandidate = new OspSplitCandidate();
+                OspSplitCandidate *backCandidate = new OspSplitCandidate();
+
+                EvalSplitCandidate(tFrontData, *frontCandidate);
+                EvalSplitCandidate(tBackData, *backCandidate);
+
+                tQueue.push(frontCandidate);
+                tQueue.push(backCandidate);
+
+                // delete old leaf node
+                DEL_PTR(tData.mNode);
+        }
+
+
+        //-- terminate traversal
+        if (newNode->IsLeaf())
+        {
+                //KdLeaf *leaf = dynamic_cast<KdLeaf *>(newNode);
+                EvaluateLeafStats(tData);               
+        }
+
+        //-- cleanup
+        tData.Clear();
+        
+        return newNode;
+}
+
+
+void OspTree::EvalSplitCandidate(OspTraversalData &tData,
+                                                                 OspSplitCandidate &splitData)
+{
+        float frontProb;
+        float backtProb;
+        
+        KdLeaf *leaf = dynamic_cast<KdLeaf *>(tData.mNode);
+
+        // compute locally best split plane
+        const bool success = false;
+#if TODO
+        SelectPlane(tData, splitData.mSplitPlane,
+                                frontData.mProbability, backData.mProbability);
+
+        //TODO
+        // compute global decrease in render cost
+        splitData.mPriority = EvalRenderCostDecrease(splitData.mSplitPlane, tData);
+        splitData.mParentData = tData;
+        splitData.mMaxCostMisses = success ? tData.mMaxCostMisses : tData.mMaxCostMisses + 1;
+#endif
+}
+
+
 /*****************************************************************/
 /*              class HierarchyManager implementation            */
@@ -2376 +2351 @@
 
 
-void HierarchyManager::PrepareTraversal()
-{
-
-#if TODO
-        /// create new vsp tree
-        mRoot = new VspLeaf();
-        /// we use the overall probability as normalizer
-        const float prop = mBoundingBox.GetVolume();
-
-        VspTraversalData tData(mRoot,
-                                                   0,
-                                                   rays,
-                           ComputePvsSize(*rays),
-                                                   prop,
-                                                   mBoundingBox);
-
-
-        // compute first split candidates
-        VspTree::VspSplitCandidate vspSplitCandidate = new VspTree::VspSplitCandidate();
-        EvalSplitCandidate(tData, *vspSplitCandidate);
-        mTQueue.push(splitCandidate);
-
-    OspSplitCandidate ospSplitCandidate = new OspSplitCandidate();
-        EvalSplitCandidate(tData, *ospSplitCandidate);
-        mTQueue.push(ospSplitCandidate);
-
-        mTotalCost = tData.mPvs * tData.mProbability / mBox.GetVolume();
-        mTotalPvsSize = tData.mPvs;
-        
-        mSubdivisionStats 
-                        << "#ViewCells\n1\n" <<  endl
-                        << "#RenderCostDecrease\n0\n" << endl 
-                        << "#SplitCandidateCost\n0\n" << endl
-                        << "#TotalRenderCost\n" << mTotalCost << endl
-                        << "#AvgRenderCost\n" << mTotalPvsSize << endl;
-
-        Debug << "total cost: " << mTotalCost << endl;
-
-#endif
+void HierarchyManager::PrepareConstruction(const VssRayContainer &sampleRays,
+                                                                                   AxisAlignedBox3 *forcedViewSpace,
+                                                                                   RayInfoContainer &rays)
+{
+        VssRayContainer::const_iterator rit, rit_end = sampleRays.end();
+
+        long startTime = GetTime();
+
+        cout << "storing rays ... ";
+
+        Intersectable::NewMail();
+
+        mVspTree->PrepareConstruction(sampleRays, forcedViewSpace);
+
+        //-- store rays
+        for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
+        {
+                VssRay *ray = *rit;
+
+                float minT, maxT;
+
+                static Ray hray;
+                hray.Init(*ray);
+
+                // TODO: not very efficient to implictly cast between rays types
+                if (mBoundingBox.GetRaySegment(hray, minT, maxT))
+                {
+                        float len = ray->Length();
+
+                        if (!len)
+                                len = Limits::Small;
+
+                        rays.push_back(RayInfo(ray, minT / len, maxT / len));
+                }
+        }
+
+        cout << "finished" << endl;
+
+        //mOspTree->PrepareConstruction(sampleRays, forcedViewSpace, rays);
+}
+
+
+bool HierarchyManager::GlobalTerminationCriteriaMet(SplitCandidate *candidate) const
+{
+        if (candidate->Type() == SplitCandidate::VIEW_SPACE)
+        {
+                VspTree::VspSplitCandidate *sc = 
+                        dynamic_cast<VspTree::VspSplitCandidate *>(candidate);
+                
+                return mVspTree->GlobalTerminationCriteriaMet(sc->mParentData);
+        }
+
+        return true;
 }
 
@@ -2420 +2409 @@
 void HierarchyManager::Construct(const VssRayContainer &sampleRays,
                                                                  const ObjectContainer &objects,
-                                                                 AxisAlignedBox3 *forcedBoundingBox)
-{
-#if TODO
-        //-- store rays
-        for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
-        {
-                VssRay *ray = *rit;
-
-                float minT, maxT;
-
-                static Ray hray;
-                hray.Init(*ray);
-
-                // TODO: not very efficient to implictly cast between rays types
-                if (mBoundingBox.GetRaySegment(hray, minT, maxT))
-                {
-                        float len = ray->Length();
-
-                        if (!len)
-                                len = Limits::Small;
-
-                        rays->push_back(RayInfo(ray, minT / len, maxT / len));
-                }
-        }
-#endif
-}
-
-
-bool HierarchyManager::FinishedConstruction()
-{
-        return mTQueue.empty();
-}
-
-
-void HierarchyManager::Construct(RayInfoContainer *rays)
-{
-        PrepareTraversal();
+                                                                 AxisAlignedBox3 *forcedViewSpace)
+{
+        RayInfoContainer *rays = new RayInfoContainer();
+        
+        // prepare vsp and osp trees for traversal
+        PrepareConstruction(sampleRays, forcedViewSpace, *rays);
 
         mVspTree->mVspStats.Start();
-        cout << "Constructing vsp bsp tree ... \n";
-
+
+        cout << "Constructing view space / object space tree ... \n";
         const long startTime = GetTime();       
 
@@ -2467 +2425 @@
                 SplitCandidate *splitCandidate = NextSplitCandidate();
             
+                const bool globalTerminationCriteriaMet = 
+                        GlobalTerminationCriteriaMet(splitCandidate);
+
                 // cost ratio of cost decrease / totalCost
                 const float costRatio = splitCandidate->GetPriority() / mTotalCost;
-                
                 //Debug << "cost ratio: " << costRatio << endl;
 
@@ -2475 +2435 @@
                         ++ mGlobalCostMisses;
         
-                // subdivide leaf node
-                // either object space or view space
+                //-- subdivide leaf node
+                //-- either a object space or view space split
                 if (splitCandidate->Type() == SplitCandidate::VIEW_SPACE)
                 {
@@ -2482 +2442 @@
                                 dynamic_cast<VspTree::VspSplitCandidate *>(splitCandidate);
 
-                        VspNode *r = mVspTree->Subdivide(mTQueue, *sc);
-                }
-                else // object space
+                        VspNode *r = mVspTree->Subdivide(mTQueue, *sc, globalTerminationCriteriaMet);
+                }
+                else // object space split
                 {
 #if TODO
@@ -2490 +2450 @@
 #endif
                 }
-        }
-
-        cout << "finished\n";
+
+                DEL_PTR(splitCandidate);
+        }
+
+        cout << "finished in " << TimeDiff(startTime, GetTime())*1e-3 << "secs" << endl;
 
         mVspTree->mVspStats.Stop();
 }
 
-}
+
+bool HierarchyManager::FinishedConstruction()
+{
+        return mTQueue.empty();
+}
+
+
+}