Changeset 654 for GTP/trunk/Lib/Vis/Preprocessing/src/VspBspTree.cpp

Timestamp:

02/19/06 20:15:02 (18 years ago)

Author:

mattausch

Message:

removed bug in split queue

File:

• GTP/trunk/Lib/Vis/Preprocessing/src/VspBspTree.cpp (modified) (24 diffs)

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

@@ -91 +91 @@
         environment->GetFloatValue("VspBspTree.Termination.maxCostRatio", mTermMaxCostRatio);
 
-        // HACK
-        mTermMinPolygons = 25;
+        environment->GetFloatValue("VspBspTree.Termination.minGlobalCostRatio", mTermMinGlobalCostRatio);
+        environment->GetIntValue("VspBspTree.Termination.globalCostMissTolerance", mTermGlobalCostMissTolerance);
+
+        // HACK//mTermMinPolygons = 25;
 
         //-- factors for bsp tree split plane heuristics
@@ -389 +391 @@
         mBspStats.polys = (int)polys.size();
 
+        mGlobalCostMisses = 0;
+
         cout << "finished" << endl;
 
@@ -395 +399 @@
                   << TimeDiff(startTime, GetTime())*1e-3 << " secs" << endl << endl;
 
-        Construct(polys, rays);
+        if (0)
+                ConstructWithSplitQueue(polys, rays);
+        else
+                Construct(polys, rays);
 
         // clean up polygons
@@ -496 +503 @@
                                   << TimeDiff(startTime, GetTime())*1e-3 << "s" << endl;
 
-                if (mBspStats.Leaves() == nLeaves)
+                if (mBspStats.Leaves() >= nLeaves)
                 {
                         nLeaves += 500;
@@ -523 +530 @@
 
 
-void VspBspTree::ConstructWithSplitQueueQueue(const PolygonContainer &polys, 
+void VspBspTree::ConstructWithSplitQueue(const PolygonContainer &polys, 
                                                                                           RayInfoContainer *rays)
 {
@@ -551 +558 @@
         tQueue.push(splitCandidate);
 
-
         mTotalCost = tData.mPvs * tData.mProbability / mBox.GetVolume();
         mTotalPvsSize = tData.mPvs;
@@ -558 +564 @@
                         << "#ViewCells\n1\n" <<  endl
                         << "#RenderCostDecrease\n0\n" << endl 
+                        << "#dummy\n0\n" << endl
                         << "#TotalRenderCost\n" << mTotalCost << endl
                         << "#AvgRenderCost\n" << mTotalPvsSize << endl;
@@ -583 +590 @@
             tQueue.pop();               
 
+                // cost ratio of cost decrease / totalCost
+                float costRatio = splitCandidate.GetCost() / mTotalCost;
+
+                Debug << "cost ratio: " << costRatio << endl;
+
+                if (costRatio < mTermMinGlobalCostRatio)
+                {Debug << "here1 cost ratio: " << costRatio << " max " << mTermMinGlobalCostRatio << endl;
+                        ++ mGlobalCostMisses;
+                }
                 if (0 && !mOutOfMemory)
                 {
@@ -601 +617 @@
                                   << TimeDiff(startTime, GetTime())*1e-3 << "s" << endl;
 
-                if (mBspStats.Leaves() == nLeaves)
+                if (mBspStats.Leaves() >= nLeaves)
                 {
                         nLeaves += 500;
@@ -627 +643 @@
 
 
-bool VspBspTree::TerminationCriteriaMet(const VspBspTraversalData &data) const
+bool VspBspTree::LocalTerminationCriteriaMet(const VspBspTraversalData &data) const
 {
         return
@@ -633 +649 @@
                  (data.mPvs <= mTermMinPvs)   ||
                  (data.mProbability <= mTermMinProbability) ||
-                 (mBspStats.Leaves() >= mMaxViewCells) ||
-#if 0
-                 (((int)data.mPolygons->size() <= mTermMinPolygons) && !data.mPolygons->empty())||
-#endif
                  (data.GetAvgRayContribution() > mTermMaxRayContribution) ||
                  (data.mDepth >= mTermMaxDepth));
@@ -642 +654 @@
 
 
+bool VspBspTree::GlobalTerminationCriteriaMet(const VspBspTraversalData &data) const
+{
+        return
+                (mOutOfMemory 
+                || (mBspStats.Leaves() >= mMaxViewCells) 
+                || (mGlobalCostMisses >= mTermGlobalCostMissTolerance)
+                 );
+}
+
+
+
 BspNode *VspBspTree::Subdivide(VspBspTraversalQueue &tQueue,
                                                            VspBspTraversalData &tData)
@@ -647 +670 @@
         BspNode *newNode = tData.mNode;
 
-        if (!mOutOfMemory && !TerminationCriteriaMet(tData))
+        if (!LocalTerminationCriteriaMet(tData) && !GlobalTerminationCriteriaMet(tData))
         {
                 PolygonContainer coincident;
@@ -786 +809 @@
         BspNode *newNode = tData.mNode;
 
-        if (!mOutOfMemory && !TerminationCriteriaMet(tData))
+        if (!LocalTerminationCriteriaMet(tData) && !GlobalTerminationCriteriaMet(tData))
         {
                 PolygonContainer coincident;
@@ -801 +824 @@
                 // create new interior node and two leaf node
                 const Plane3 splitPlane = splitCandidate.mSplitPlane;
-                        
+                                
                 newNode = SubdivideNode(splitPlane, tData, tFrontData, tBackData, coincident);
-
+                
 #if 0 // TODO
-                        if (splitAxis < 3)
-                                ++ mBspStats.splits[splitAxis];
-                        else
-                                ++ mBspStats.polySplits;
-
-                        tFrontData.mIsKdNode = tBackData.mIsKdNode = (tData.mIsKdNode && splitAxis < 3);
-                        // how often was max cost ratio missed in this branch?
-                        tFrontData.mMaxCostMisses = maxCostMisses;
-                        tBackData.mMaxCostMisses = maxCostMisses;
+                if (splitAxis < 3)
+                        ++ mBspStats.splits[splitAxis];
+                else
+                        ++ mBspStats.polySplits;
+
+                tFrontData.mIsKdNode = tBackData.mIsKdNode = (tData.mIsKdNode && splitAxis < 3);
+                // how often was max cost ratio missed in this branch?
+                tFrontData.mMaxCostMisses = maxCostMisses;
+                tBackData.mMaxCostMisses = maxCostMisses;
+
 #endif
                 if (1)
@@ -829 +853 @@
                         mSubdivisionStats 
                                         << "#ViewCells\n" << mBspStats.Leaves() << endl
-                                        << "#RenderCostDecrease\n" << -costDecr << endl 
+                                        << "#RenderCostDecrease\n" << -costDecr << endl
+                                        << "#dummy\n" << splitCandidate.GetCost() << endl
                                         << "#TotalRenderCost\n" << mTotalCost << endl
                                         << "#AvgRenderCost\n" << (float)mTotalPvsSize / (float)mBspStats.Leaves() << endl;
@@ -838 +863 @@
                 VspBspSplitCandidate backCandidate;
 
-                EvalSplitCandidate(tData, frontCandidate);
-                EvalSplitCandidate(tData, backCandidate);
-
+                EvalSplitCandidate(tFrontData, frontCandidate);
+                EvalSplitCandidate(tBackData, backCandidate);
+        
                 tQueue.push(frontCandidate);
                 tQueue.push(backCandidate);
@@ -847 +872 @@
                 DEL_PTR(tData.mNode);
         }
+
 
         //-- terminate traversal and create new view cell
@@ -904 +930 @@
 
         BspLeaf *leaf = dynamic_cast<BspLeaf *>(tData.mNode);
+
+        // compute locally best split plane
         SelectPlane(splitData.mSplitPlane, leaf, tData, frontData, backData, splitAxis);
 
@@ -910 +938 @@
         DEL_PTR(backData.mGeometry);
         
+        // compute global decrease in render cost
         splitData.mRenderCost = EvalRenderCostDecrease(splitData.mSplitPlane, tData);
         splitData.mParentData = tData;
@@ -966 +995 @@
                 {
                         frontData.mProbability = frontData.mGeometry->GetVolume();
-                        backData.mProbability =  tData.mProbability - frontData.mProbability;
+                        backData.mProbability = tData.mProbability - frontData.mProbability;
                 }
         }
@@ -1590 +1619 @@
         int pvsFront = 0;
         int pvsBack = 0;
-        int totalPvs = data.mPvs;
+        int totalPvs = 0;
 
         // probability that view point lies in back / front node
@@ -1649 +1678 @@
         const float newRenderCost = penaltyFront * pFront + penaltyBack * pBack;
 
-        return oldRenderCost - newRenderCost;
+        //Debug << "decrease: " << oldRenderCost - newRenderCost << endl;
+        return (oldRenderCost - newRenderCost) / mBox.GetVolume();
 }
 
@@ -1860 +1890 @@
         if (!obj)
                 return;
-        
+        // new object
         if ((obj->mMailbox != sFrontId) &&
                 (obj->mMailbox != sBackId) &&