Changeset 654

Timestamp:

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

Author:

mattausch

Message:

removed bug in split queue

Location:

GTP/trunk/Lib/Vis

Files:

• Preprocessing/scripts/default.env (modified) (9 diffs)
• Preprocessing/src/Environment.cpp (modified) (1 diff)
• Preprocessing/src/ViewCellsParser.cpp (modified) (5 diffs)
• Preprocessing/src/VspBspTree.cpp (modified) (24 diffs)
• Preprocessing/src/VspBspTree.h (modified) (4 diffs)
• Preprocessing/src/VssPreprocessor.cpp (modified) (1 diff)
• shared/scripts/GtpVisibility.suo (modified) (previous)

GTP/trunk/Lib/Vis/Preprocessing/scripts/default.env

@@ -13 +13 @@
 #;../data/vienna/vienna-plane.x3d
 #       filename ../data/vienna/viewcells-25-sel.x3d
-#       filename ../data/atlanta/atlanta2.x3d
+        filename ../data/atlanta/atlanta2.x3d
 #       filename ../data/soda/soda.dat
-        filename ../data/soda/soda5.dat
+#       filename ../data/soda/soda5.dat
 }
 
@@ -25 +25 @@
         type vss
 #       type rss
-        detectEmptyViewSpace true
+        detectEmptyViewSpace false
 }
 
@@ -36 +36 @@
         loadInitialSamples  false
         storeInitialSamples false
-        useViewSpaceBox true
+        useViewSpaceBox false
 #       testBeamSampling true
 }
@@ -184 +184 @@
         maxStaticMemory 40
 
-        exportToFile false
-        loadFromFile true
+        exportToFile true
+        loadFromFile false
 
         #type kdTree
@@ -213 +213 @@
                 useRaysForMerge false
                 refine false
-                compress true
-                merge false
+                compress false
+                merge true
         }
 
@@ -288 +288 @@
 VspBspTree {
         Construction {
-                samples 50000
+                samples 300000
                 epsilon 0.0005
                 randomize false
@@ -301 +301 @@
         # pvs                  = 1024
         
-        splitPlaneStrategy 1024
+        splitPlaneStrategy 1026
         
         # maximal candidates for split planes
@@ -330 +330 @@
                 maxCostRatio            1.8
                 missTolerance           6
-                
-                maxViewCells            100
+                globalCostMissTolerance 4
+                minGlobalCostRatio      0.0000001
+                maxViewCells            40000
         
                 # used for pvs criterium
@@ -420 +421 @@
                 minProbability 0.00001
                 maxRayContribution 9999
-                maxViewCells    1000
+                maxViewCells    10000
 
                 # used for pvs criterium

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

@@ -1811 +1811 @@
 /************************************************************************************/
 
+        RegisterOption("VspBspTree.Termination.minGlobalCostRatio",
+                                        optFloat,
+                                        "vsp_bsp_term_min_global_cost_ratio",
+                                        "0.0001");
+
+        RegisterOption("VspBspTree.Termination.globalCostMissTolerance",
+                                        optInt,
+                                        "vsp_bsp_term_global_cost_miss_tolerance",
+                                        "4");
 
         RegisterOption("VspBspTree.Termination.minPolygons",

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

@@ -414 +414 @@
                 }
         }
-Debug << "here22" << endl;
+
         
         if (viewCellId >= 0) // valid view cell
@@ -427 +427 @@
                 BspViewCell *viewCell = dynamic_cast<BspViewCell *>(*vit);
 
-                Debug << "here44" << endl;
-
+        
                 if (viewCell->GetId() == viewCellId)
                 {
@@ -447 +446 @@
                         mVspBspTree->PropagateUpValidity(leaf);
                 }
-        }Debug << "here33" << endl;
+        }
 }
 
@@ -496 +495 @@
 void ViewCellsParseHandlers::StartViewCellLeaf(AttributeList& attributes)
 {
-        Debug << "here111" << endl;
         BspViewCell *viewCell = new BspViewCell();
 
@@ -518 +516 @@
 void ViewCellsParseHandlers::StartViewCellInterior(AttributeList& attributes)
 {
-        Debug << "here222" << endl;
         ViewCellInterior* interior = new ViewCellInterior();
         

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) &&

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

@@ -64 +64 @@
                 /// if this node is a kd-node (i.e., boundaries are axis aligned
                 bool mIsKdNode;
+
+
 #if OCTREE_HACK // OCTREE HACK
                 int mAxis;
@@ -398 +400 @@
                                                                  const VspBspTraversalData &data) const;
 
-        void ConstructWithSplitQueueQueue(const PolygonContainer &polys, RayInfoContainer *rays);
+        void ConstructWithSplitQueue(const PolygonContainer &polys, RayInfoContainer *rays);
 
 
@@ -585 +587 @@
         /** Returns true if tree can be terminated.
         */
-        inline bool TerminationCriteriaMet(const VspBspTraversalData &data) const;
+        inline bool LocalTerminationCriteriaMet(const VspBspTraversalData &data) const;
+
+        inline bool GlobalTerminationCriteriaMet(const VspBspTraversalData &data) const;
 
         /** Computes accumulated ray lenght of this rays.
@@ -706 +710 @@
         int mTermMinPolygons;
 
+        float mTermMinGlobalCostRatio;
+        int mTermGlobalCostMissTolerance;
+
+        int mGlobalCostMisses;
+
         //-- termination criteria for axis aligned split
 

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

@@ -531 +531 @@
   if (mUseViewSpaceBox)
   {
-          if (1)
+          if (0)
+          {
                   mViewSpaceBox = box;
+          }
           else
           {