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

Timestamp:

07/10/06 01:57:41 (18 years ago)

Author:

mattausch

Message:

 

File:

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

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

@@ -22 +22 @@
 
 #define USE_FIXEDPOINT_T 0
-
+#define COUNT_OBJECTS 1
 
 //-- static members
-
-int VspTree::sFrontId = 0;
-int VspTree::sBackId = 0;
-int VspTree::sFrontAndBackId = 0;
 
 VspTree *VspTree::VspSplitCandidate::sVspTree = NULL;
@@ -379 +375 @@
 
         Debug << "******* VSP options ******** " << endl;
+
     Debug << "max depth: " << mTermMaxDepth << endl;
         Debug << "min PVS: " << mTermMinPvs << endl;
@@ -399 +396 @@
         Debug << "minband: " << mMinBand << endl;
         Debug << "maxband: " << mMaxBand << endl;
-        Debug << "pvs count method: " << mPvsCountMethod << endl;
-
+
+        if (mPvsCountMethod == 0)
+                Debug << "pvs count method: per object" << endl;
+        else
+                Debug << "pvs count method: per kd node" << endl;
 
         mSplitCandidates = new vector<SortableEntry>;
@@ -504 +504 @@
 bool VspTree::LocalTerminationCriteriaMet(const VspTraversalData &data) const
 {
-        return
-#if TODO
-                (((int)data.mRays->size() <= mTermMinRays) ||
-                 (data.mPvs <= mTermMinPvs)   ||
-                 (data.mProbability <= mTermMinProbability) ||
-                 (data.GetAvgRayContribution() > mTermMaxRayContribution) ||
-                 (data.mDepth >= mTermMaxDepth));
-#else
-                false;
-#endif
+        return(
+                ((int)data.mRays->size() <= mTermMinRays) ||
+                (data.mPvs <= mTermMinPvs)   ||
+                (data.mProbability <= mTermMinProbability) ||
+                (data.GetAvgRayContribution() > mTermMaxRayContribution) ||
+                (data.mDepth >= mTermMaxDepth)
+                );
+                
 }
 
@@ -519 +517 @@
 bool VspTree::GlobalTerminationCriteriaMet(const VspTraversalData &data) const
 {
-        return
-#if TODO
-                (mOutOfMemory || 
+        return (
+//              mOutOfMemory || 
                 (mVspStats.Leaves() >= mMaxViewCells) || 
-                (mGlobalCostMisses >= mTermGlobalCostMissTolerance));
-#else
-                (mVspStats.Leaves() >= mMaxViewCells) ;         
-#endif
+        (mGlobalCostMisses >= mTermGlobalCostMissTolerance) 
+                );              
 }
 
@@ -729 +724 @@
         // and setup child links
         interior->SetupChildLinks(new VspLeaf(interior), new VspLeaf(interior));
+        
         // add bounding box
         interior->SetBoundingBox(tData.mBoundingBox);
+
+        // set front and back leaf
+        frontData.mNode = interior->GetFront();
+        backData.mNode = interior->GetBack();
 
         interior->mTimeStamp = mTimeStamp ++;
@@ -915 +915 @@
                         node->mCounter = 1;
 
-                        //Debug << "here5 "<<(int)node->mObjects.size() <<" "<< node->mMultipleObjects.size()<< " " <<(int)node->mObjects.size() - node->mMultipleObjects.size()<<endl;
                         // add objects without the objects which are in several kd leaves
                         pvsSize += (int)(node->mObjects.size() - node->mMultipleObjects.size());
@@ -933 +932 @@
                         if (!object->Mailed())
                         {
-                                //Debug << "here233: " << object->mKdLeaves.size() << endl;
                                 object->Mail();
                                 object->mCounter = 1;
@@ -1322 +1320 @@
                 sAxis = box.Size().DrivingAxis();
         }
-        //sAxis = 2;
+        
         for (int axis = 0; axis < 3; ++ axis)
         {
                 if (!useSpecialAxis || (axis == sAxis))
                 {
-                        //-- place split plane using heuristics
-
                         if (mUseCostHeuristics)
                         {
+                                //-- place split plane using heuristics
                                 nCostRatio[axis] =
                                         EvalLocalCostHeuristics(*tData.mRays,
@@ -1338 +1335 @@
                                                                                         nPosition[axis]);                       
                         }
-                        else //-- split plane position is spatial median
-                        {
+                        else
+                        {
+                                //-- split plane position is spatial median
+
                                 nPosition[axis] = (box.Min()[axis] + box.Max()[axis]) * 0.5f;
 
@@ -2545 +2544 @@
 mTimeStamp(1)
 {
-#if TODO
+
         bool randomize = false;
         Environment::GetSingleton()->GetBoolValue("VspTree.Construction.randomize", randomize);
@@ -2552 +2551 @@
 
         //-- termination criteria for autopartition
-        Environment::GetSingleton()->GetIntValue("VspTree.Termination.maxDepth", mTermMaxDepth);
-        Environment::GetSingleton()->GetIntValue("VspTree.Termination.minPvs", mTermMinPvs);
-        Environment::GetSingleton()->GetIntValue("VspTree.Termination.minRays", mTermMinRays);
-        Environment::GetSingleton()->GetFloatValue("VspTree.Termination.minProbability", mTermMinProbability);
-        Environment::GetSingleton()->GetFloatValue("VspTree.Termination.maxRayContribution", mTermMaxRayContribution);
-        
-        Environment::GetSingleton()->GetIntValue("VspTree.Termination.missTolerance", mTermMissTolerance);
-        Environment::GetSingleton()->GetIntValue("VspTree.Termination.maxViewCells", mMaxViewCells);
-
+        Environment::GetSingleton()->GetIntValue("OspTree.Termination.maxDepth", mTermMaxDepth);
+        Environment::GetSingleton()->GetIntValue("OspTree.Termination.maxLeaves", mTermMaxLeaves);
+        Environment::GetSingleton()->GetIntValue("OspTree.Termination.minObjects", mTermMinObjects);
+        Environment::GetSingleton()->GetFloatValue("OspTree.Termination.minProbability", mTermMinProbability);
+        
+        Environment::GetSingleton()->GetIntValue("OspTree.Termination.missTolerance", mTermMissTolerance);
+        
         //-- max cost ratio for early tree termination
-        Environment::GetSingleton()->GetFloatValue("VspTree.Termination.maxCostRatio", mTermMaxCostRatio);
-
-        Environment::GetSingleton()->GetFloatValue("VspTree.Termination.minGlobalCostRatio", mTermMinGlobalCostRatio);
-        Environment::GetSingleton()->GetIntValue("VspTree.Termination.globalCostMissTolerance", mTermGlobalCostMissTolerance);
-
-        // HACK//mTermMinPolygons = 25;
+        Environment::GetSingleton()->GetFloatValue("OspTree.Termination.maxCostRatio", mTermMaxCostRatio);
+
+        Environment::GetSingleton()->GetFloatValue("OspTree.Termination.minGlobalCostRatio", mTermMinGlobalCostRatio);
+        Environment::GetSingleton()->GetIntValue("OspTree.Termination.globalCostMissTolerance", mTermGlobalCostMissTolerance);
+
 
         //-- factors for bsp tree split plane heuristics
-        Environment::GetSingleton()->GetFloatValue("VspTree.Termination.ct_div_ci", mCtDivCi);
+        Environment::GetSingleton()->GetFloatValue("OspTree.Termination.ct_div_ci", mCtDivCi);
 
         //-- partition criteria
-        Environment::GetSingleton()->GetFloatValue("VspTree.Construction.epsilon", mEpsilon);
+        Environment::GetSingleton()->GetFloatValue("OspTree.Construction.epsilon", mEpsilon);
 
         // if only the driving axis is used for axis aligned split
-        Environment::GetSingleton()->GetBoolValue("VspTree.splitUseOnlyDrivingAxis", mOnlyDrivingAxis);
-        
-        //Environment::GetSingleton()->GetFloatValue("VspTree.maxTotalMemory", mMaxTotalMemory);
-        Environment::GetSingleton()->GetFloatValue("VspTree.maxStaticMemory", mMaxMemory);
-
-        Environment::GetSingleton()->GetBoolValue("VspTree.useCostHeuristics", mUseCostHeuristics);
-        Environment::GetSingleton()->GetBoolValue("VspTree.simulateOctree", mCirculatingAxis);
+        Environment::GetSingleton()->GetBoolValue("OspTree.splitUseOnlyDrivingAxis", mOnlyDrivingAxis);
+        
+        Environment::GetSingleton()->GetFloatValue("OspTree.maxStaticMemory", mMaxMemory);
+
+        Environment::GetSingleton()->GetBoolValue("OspTree.useCostHeuristics", mUseCostHeuristics);
 
 
         char subdivisionStatsLog[100];
-        Environment::GetSingleton()->GetStringValue("VspTree.subdivisionStats", subdivisionStatsLog);
+        Environment::GetSingleton()->GetStringValue("OspTree.subdivisionStats", subdivisionStatsLog);
         mSubdivisionStats.open(subdivisionStatsLog);
 
-        Environment::GetSingleton()->GetFloatValue("VspTree.Construction.minBand", mMinBand);
-        Environment::GetSingleton()->GetFloatValue("VspTree.Construction.maxBand", mMaxBand);
-        
-        mSplitBorder = 0.1f;
+        Environment::GetSingleton()->GetFloatValue("OspTree.Construction.splitBorder", mSplitBorder);
+        //mSplitBorder = 0.1f;
 
 
@@ -2598 +2590 @@
 
         Debug << "******* OSP options ******** " << endl;
+
     Debug << "max depth: " << mTermMaxDepth << endl;
-        Debug << "min PVS: " << mTermMinPvs << endl;
         Debug << "min probabiliy: " << mTermMinProbability << endl;
-        Debug << "min rays: " << mTermMinRays << endl;
-        Debug << "max ray contri: " << mTermMaxRayContribution << endl;
+        Debug << "min objects: " << mTermMinObjects << endl;
         Debug << "max cost ratio: " << mTermMaxCostRatio << endl;
         Debug << "miss tolerance: " << mTermMissTolerance << endl;
-        Debug << "max view cells: " << mMaxViewCells << endl;
+        Debug << "max leaves: " << mTermMaxLeaves << endl;
+
         Debug << "randomize: " << randomize << endl;
 
@@ -2615 +2607 @@
         Debug << "subdivision stats log: " << subdivisionStatsLog << endl;
         
-        Debug << "circulating axis: " << mCirculatingAxis << endl;
-        Debug << "minband: " << mMinBand << endl;
-        Debug << "maxband: " << mMaxBand << endl;
-        
+        Debug << "split borders: " << mSplitBorder << endl;
+
 
         mSplitCandidates = new vector<SortableEntry>;
 
         Debug << endl;
-#endif
 }
 
@@ -2630 +2619 @@
 void OspTree::SplitObjects(const AxisAlignedPlane & splitPlane,
                                                    const ObjectContainer &objects,
-                                                   ObjectContainer &back,
-                                                   ObjectContainer &front)
+                                                   ObjectContainer &front,
+                                                   ObjectContainer &back)
 {
         ObjectContainer::const_iterator oit, oit_end = objects.end();
@@ -2645 +2634 @@
                 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,
+        }
+
+        mOspStats.objectRefs -= (int)objects.size();
+        mOspStats.objectRefs += (int)back.size() + (int)front.size();
+}
+
+
+KdInterior *OspTree::SubdivideNode(
+                                                                   KdLeaf *leaf,
                                                                    const AxisAlignedPlane &splitPlane,
                                                                    const AxisAlignedBox3 &box,
-                                                                   AxisAlignedBox3 &backBBox,
-                                                                   AxisAlignedBox3 &frontBBox)
-{
-#if TODO
-    mSpatialStat.nodes += 2;
-        mSpatialStat.splits[axis];
-#endif
+                                                                   OspTraversalData &frontData,
+                                                                   OspTraversalData &backData
+                                                                   )
+{
+    mOspStats.nodes += 2;
 
         // add the new nodes to the tree
@@ -2674 +2661 @@
         node->mBox = box;
 
-    backBBox = box;
-        frontBBox = box;
+        backData.mBoundingBox = box;
+        frontData.mBoundingBox = box;
   
         // first count ray sides
@@ -2681 +2668 @@
         int objectsFront = 0;
   
-        backBBox.SetMax(axis, position);
-        frontBBox.SetMin(axis, position);
+        backData.mBoundingBox.SetMax(axis, position);
+        frontData.mBoundingBox.SetMin(axis, position);
 
         ObjectContainer::const_iterator mi, mi_end = leaf->mObjects.end();
@@ -2701 +2688 @@
         KdLeaf *front = new KdLeaf(node, objectsFront);
 
+        /////////////
+        //-- create front and back leaf
+
+        KdInterior *parent = leaf->mParent;
+
         // replace a link from node's parent
-        if (leaf->mParent)
-                leaf->mParent->ReplaceChildLink(leaf, node);
+        if (parent)
+        {
+                parent->ReplaceChildLink(leaf, node);
+                node->mParent = parent;
+        }
+        else // new root
+        {
+                mRoot = node;
+        }
 
         // and setup child links
         node->SetupChildLinks(back, front);
 
-        SplitObjects(splitPlane, leaf->mObjects, back->mObjects, front->mObjects);
+        SplitObjects(splitPlane, leaf->mObjects, front->mObjects, back->mObjects);
 
         ProcessLeafObjects(back, leaf);
     ProcessLeafObjects(front, leaf);
   
+        backData.mNode = back;
+        frontData.mNode = front;
+
         //delete leaf;
         return node;
@@ -2721 +2723 @@
                                                    OspSplitCandidate &splitCandidate,
                                                    const bool globalCriteriaMet)
-{
+{Debug << "here11" << endl;
         OspTraversalData &tData = splitCandidate.mParentData;
-
+Debug << "here993" << endl;
         KdNode *newNode = tData.mNode;
 
+Debug << "here996" << endl;
         if (!LocalTerminationCriteriaMet(tData) && !globalCriteriaMet)
         {       
                 OspTraversalData tFrontData;
                 OspTraversalData tBackData;
-
+Debug << "here3" << endl;
                 //-- continue subdivision
                 
@@ -2739 +2742 @@
                                                                 splitPlane, 
                                                                 tData.mBoundingBox, 
-                                                                tFrontData.mBoundingBox, 
-                                                                tBackData.mBoundingBox);
+                                                                tFrontData, 
+                                                                tBackData);
         
                 const int maxCostMisses = splitCandidate.mMaxCostMisses;
@@ -2752 +2755 @@
                 OspSplitCandidate *backCandidate = new OspSplitCandidate(tBackData);
 
+                Debug << "here 54 " << tFrontData.mNode << " " <<  tBackData.mNode << endl;
+
                 EvalSplitCandidate(*frontCandidate);
                 EvalSplitCandidate(*backCandidate);
@@ -2766 +2771 @@
         if (newNode->IsLeaf())
         {
-                //KdLeaf *leaf = dynamic_cast<KdLeaf *>(newNode);
                 EvaluateLeafStats(tData);               
         }
-
+        Debug << "here888 "<< endl;
         //-- cleanup
         tData.Clear();
-        
+        Debug << "here876"<< endl;
         return newNode;
 }
@@ -2782 +2786 @@
         float backProb;
         
-        KdLeaf *leaf = dynamic_cast<KdLeaf *>(splitCandidate.mParentData.mNode);
-
         // compute locally best split plane
         const bool success = 
                 SelectSplitPlane(splitCandidate.mParentData, splitCandidate.mSplitPlane, frontProb, backProb);
 
-        //TODO
+        const float priority = EvalRenderCostDecrease(splitCandidate.mSplitPlane, splitCandidate.mParentData);
         // compute global decrease in render cost
-        splitCandidate.SetPriority(EvalRenderCostDecrease(splitCandidate.mSplitPlane, splitCandidate.mParentData));
-        splitCandidate.mMaxCostMisses = success ? splitCandidate.mParentData.mMaxCostMisses : splitCandidate.mParentData.mMaxCostMisses + 1;
+        splitCandidate.SetPriority(priority);
+
+        splitCandidate.mMaxCostMisses = 
+                success ? splitCandidate.mParentData.mMaxCostMisses : splitCandidate.mParentData.mMaxCostMisses + 1;
 }
 
@@ -2798 +2802 @@
 {
         // matt: TODO
-        return true;
-    /*          (((int)data.mRays->size() <= mTermMinRays) ||
-                 (data.mPvs <= mTermMinPvs)   ||
-                 (data.mProbability <= mTermMinProbability) ||
-                 (data.GetAvgRayContribution() > mTermMaxRayContribution) ||
-                 (data.mDepth >= mTermMaxDepth));*/
+        return ( 
+                //(data.mNode->mObjects.size() < mTermMinObjects) ||
+                //(data.mProbability <= mTermMinProbability) ||
+                (data.mDepth >= mTermMaxDepth)
+                 );
 }
 
@@ -2810 +2813 @@
 {
         // matt: TODO
-        return true;
-                /*(mOutOfMemory || 
-                (mVspStats.Leaves() >= mMaxViewCells) || 
-                (mGlobalCostMisses >= mTermGlobalCostMissTolerance));*/
+        Debug << "here888 " << mTermMaxLeaves << " " << mOspStats.Leaves() << endl;
+        return (
+                (mOspStats.Leaves() >= mTermMaxLeaves)
+                //mOutOfMemory || 
+                //(mGlobalCostMisses >= mTermGlobalCostMissTolerance)
+                );
 }
 
@@ -2819 +2824 @@
 void OspTree::EvaluateLeafStats(const OspTraversalData &data)
 {
-#if TODO
         // the node became a leaf -> evaluate stats for leafs
-        VspLeaf *leaf = dynamic_cast<VspLeaf *>(data.mNode);
-
-        if (data.mPvs > mVspStats.maxPvs)
-        {
-                mVspStats.maxPvs = data.mPvs;
-        }
-
-        mVspStats.pvs += data.mPvs;
-
-        if (data.mDepth < mVspStats.minDepth)
-        {
-                mVspStats.minDepth = data.mDepth;
+        KdLeaf *leaf = data.mNode;
+
+        if (data.mPvs > mOspStats.maxPvs)
+        {
+                mOspStats.maxPvs = data.mPvs;
+        }
+
+        mOspStats.pvs += data.mPvs;
+
+        if (data.mDepth < mOspStats.minDepth)
+        {
+                mOspStats.minDepth = data.mDepth;
         }
         
         if (data.mDepth >= mTermMaxDepth)
         {
-        ++ mVspStats.maxDepthNodes;
+        ++ mOspStats.maxDepthNodes;
                 //Debug << "new max depth: " << mVspStats.maxDepthNodes << endl;
         }
 
-        // accumulate rays to compute rays /  leaf
-        mVspStats.accumRays += (int)data.mRays->size();
-
-        if (data.mPvs < mTermMinPvs)
-                ++ mVspStats.minPvsNodes;
-
-        if ((int)data.mRays->size() < mTermMinRays)
-                ++ mVspStats.minRaysNodes;
-
-        if (data.GetAvgRayContribution() > mTermMaxRayContribution)
-                ++ mVspStats.maxRayContribNodes;
+//      if (data.mPvs < mTermMinPvs)
+//              ++ mOspStats.minPvsNodes;
 
         if (data.mProbability <= mTermMinProbability)
-                ++ mVspStats.minProbabilityNodes;
+                ++ mOspStats.minProbabilityNodes;
         
         // accumulate depth to compute average depth
-        mVspStats.accumDepth += data.mDepth;
-
-        ++ mCreatedViewCells;
+        mOspStats.accumDepth += data.mDepth;
+
+        ++ mCreatedLeaves;
 
 #ifdef _DEBUG
         Debug << "BSP stats: "
                   << "Depth: " << data.mDepth << " (max: " << mTermMaxDepth << "), "
-                  << "PVS: " << data.mPvs << " (min: " << mTermMinPvs << "), "
-                  << "Area: " << data.mProbability << " (min: " << mTermMinProbability << "), "
-                  << "#rays: " << (int)data.mRays->size() << " (max: " << mTermMinRays << "), "
-                  << "#pvs: " << leaf->GetViewCell()->GetPvs().GetSize() << "), "
-                  << "#avg ray contrib (pvs): " << (float)data.mPvs / (float)data.mRays->size() << endl;
-#endif
-
+                 // << "PVS: " << data.mPvs << " (min: " << mTermMinPvs << "), "
+                  << "Prob: " << data.mProbability << " (min: " << mTermMinProbability << "), "
+                  << "#pvs: " << data.mPvs << ")\n";
 #endif
 }
@@ -2879 +2870 @@
                                                                            const int axis,
                                                                            float &position,
-                                                                           int &objectsBack,
-                                                                           int &objectsFront)
+                                                                           int &objectsFront,
+                                                                           int &objectsBack)
 {
         
@@ -2889 +2880 @@
         // C = ct_div_ci  + (ol + or)/queries
         
-        int pvsSize = PrepareHeuristics(node->mObjects);;
+        int pvsSize = PrepareHeuristics(node->mObjects);
         int pvsl = 0, pvsr = pvsSize;
   
@@ -3009 +3000 @@
 int OspTree::PrepareHeuristics(Intersectable *object)
 {
+#if COUNT_OBJECTS
+        return 1;
+#else
         ViewCellPvsMap::const_iterator vit, vit_end = object->mViewCellPvs.mEntries.end();
         
@@ -3030 +3024 @@
 
         return pvsSize;
+#endif
 }
 
@@ -3073 +3068 @@
 
 
+void OspTree::SetViewCellsManager(ViewCellsManager *vcm)
+{
+        mViewCellsManager = vcm;
+}
+
+
+AxisAlignedBox3 OspTree::GetBoundingBox() const
+{
+        return mBoundingBox;
+}
+
+
 void OspTree::RemoveContriFromPvs(Intersectable *object, int &pvs) const
 {
+#if COUNT_OBJECTS
+        -- pvs;
+#else
         ViewCellPvsMap::const_iterator vit, vit_end = object->mViewCellPvs.mEntries.end();
         
@@ -3086 +3096 @@
                 }
         }
+#endif
 }
 
@@ -3093 +3104 @@
         ViewCellPvsMap::const_iterator vit, vit_end = object->mViewCellPvs.mEntries.end();
 
+#if COUNT_OBJECTS
+        ++ pvs;
+#else
         for (vit = object->mViewCellPvs.mEntries.begin(); vit != vit_end; ++ vit)
         {
@@ -3103 +3117 @@
                 }
         }
+#endif
 }
 
@@ -3127 +3142 @@
         }
 
-/*
-        //sAxis = 2;
+        // -- evaluate split cost for all three axis
         for (int axis = 0; axis < 3; ++ axis)
         {
                 if (!mOnlyDrivingAxis || (axis == sAxis))
                 {
-                        //-- place split plane using heuristics
-
-                        if (mUseCostHeuristics)
-                        {
+                        if (1 || mUseCostHeuristics)
+                        {
+                                //-- place split plane using heuristics
+                                int objectsFront, objectsBack;
+
                                 nCostRatio[axis] =
-                                        EvalLocalCostHeuristics(*tData.mRays,
-                                                                                        box,
-                                                                                        tData.mPvs,
-                                                                                        axis,
-                                                                                        nPosition[axis]);                       
-                        }
-                        else //-- split plane position is spatial median
-                        {
+                                        EvalLocalCostHeuristics(tData.mNode,
+                                                                           tData.mBoundingBox,
+                                                                           axis,
+                                                                           nPosition[axis],
+                                                                           objectsFront,
+                                                                           objectsBack);                        
+                        }
+                        /*      else 
+                        {
+                                //-- split plane position is spatial median
+
                                 nPosition[axis] = (box.Min()[axis] + box.Max()[axis]) * 0.5f;
 
@@ -3154 +3172 @@
                                                                                                           nProbFront[axis], 
                                                                                                           nProbBack[axis]);
-                        }
+                        }*/
                                                 
                         if (bestAxis == -1)
@@ -3167 +3185 @@
         }
 
-*/
         //-- assign values
-        
+
         plane.mAxis = bestAxis;
         // split plane position
@@ -3184 +3201 @@
 float OspTree::EvalViewCellPvsIncr(Intersectable *object) const
 {
-        return 0;
+        // TODO         
+        return 1;
 }
 
@@ -3206 +3224 @@
 
         Intersectable::NewMail();
+        KdLeaf::NewMail();
         ViewCell::NewMail();
 
-        KdLeaf *leaf = dynamic_cast<KdLeaf *>(data.mNode);
+        KdLeaf *leaf = data.mNode;
         ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
 
@@ -3252 +3271 @@
 
         const float normalizedOldRenderCost = oldRenderCost / mBoundingBox.GetVolume();
+
         return factor * renderCostDecrease + (1.0f - factor) * normalizedOldRenderCost;
 }
@@ -3315 +3335 @@
 
 
-
-/*********************************************************************/
-/*                class HierarchyManager implementation              */
-/*********************************************************************/
+void OspTree::CollectLeaves(vector<KdLeaf *> &leaves) const
+{
+        stack<KdNode *> nodeStack;
+        nodeStack.push(mRoot);
+
+        while (!nodeStack.empty()) 
+        {
+                KdNode *node = nodeStack.top();
+                nodeStack.pop();
+                if (node->IsLeaf()) 
+                {
+                        KdLeaf *leaf = (KdLeaf *)node;
+                        leaves.push_back(leaf);
+                }
+                else 
+                {
+                        KdInterior *interior = (KdInterior *)node;
+                        nodeStack.push(interior->mBack);
+                        nodeStack.push(interior->mFront);
+                }
+        }
+}
+
+
+AxisAlignedBox3 OspTree::GetBBox(KdNode *node) const
+{
+        if (!node->mParent)
+                return mBoundingBox;
+
+        if (!node->IsLeaf())
+        {
+                return (dynamic_cast<KdInterior *>(node))->mBox;                
+        }
+
+        KdInterior *parent = dynamic_cast<KdInterior *>(node->mParent);
+
+        AxisAlignedBox3 box(parent->mBox);
+
+        if (parent->mFront == node)
+                box.SetMin(parent->mAxis, parent->mPosition);
+    else
+                box.SetMax(parent->mAxis, parent->mPosition);
+
+        return box;
+}
+
+
+/********************************************************************/
+/*               class HierarchyManager implementation              */
+/********************************************************************/
 
 
@@ -3330 +3396 @@
 SplitCandidate *HierarchyManager::NextSplitCandidate()
 {
-        SplitCandidate *splitCandidate = static_cast<SplitCandidate *>(mTQueue.Top());
-        //Debug << "priority: " << splitCandidate->GetPriority() << endl;
+        SplitCandidate *splitCandidate = mTQueue.Top();
+
+        Debug << "next candidate: " << splitCandidate->Type()
+                << ", priority: " << splitCandidate->GetPriority() << endl;
+
         mTQueue.Pop();
 
@@ -3415 +3484 @@
 
         // first osp traversal data
-        OspTree::OspTraversalData oData(mOspTree.mRoot,
+        OspTree::OspTraversalData oData(leaf,
                                                                         0,
-                                                                        &rays,
                                                                         pvsSize,
                                                                         prop,
@@ -3455 +3523 @@
 
 void HierarchyManager::Construct2(const VssRayContainer &sampleRays,
-                                                                 const ObjectContainer &objects,
-                                                                 AxisAlignedBox3 *forcedViewSpace)
+                                                                  const ObjectContainer &objects,
+                                                                  AxisAlignedBox3 *forcedViewSpace)
 {
         RayInfoContainer *rays = new RayInfoContainer();
@@ -3493 +3561 @@
 
         cout << "finished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
-
 
         const int pvsSize = mVspTree.ComputePvsSize(*rays);
@@ -3549 +3616 @@
 
         cout << "finished in " << TimeDiff(startTime, GetTime())*1e-3 << " secs" << endl;
-
         mVspTree.mVspStats.Stop();
-
-
+        
+        Debug << "object space" << endl;
 
         //-- object space partition
@@ -3566 +3632 @@
 
         //-- first osp traversal data
-        OspTree::OspTraversalData oData(mOspTree.mRoot,
+        OspTree::OspTraversalData oData(leaf,
                                                                         0,
-                                                                        rays,
                                                                         pvsSize,
                                                                         prop,
@@ -3580 +3645 @@
     mOspTree.EvalSplitCandidate(*oSplitCandidate);
 
-        mTQueue.Push(splitCandidate);
+        mTQueue.Push(oSplitCandidate);
 
         i = 0;
@@ -3590 +3655 @@
                         GlobalTerminationCriteriaMet(splitCandidate);
 
-                cout << "view cells: " << i ++ << endl;
+                cout << "kd nodes: " << i ++ << endl;
 
                 // cost ratio of cost decrease / totalCost
@@ -3609 +3674 @@
                 DEL_PTR(splitCandidate);
         }
-
+        
         cout << "finished in " << TimeDiff(startTime, GetTime())*1e-3 << " secs" << endl;
 }