Changeset 472

Timestamp:

12/19/05 18:57:00 (18 years ago)

Author:

mattausch

Message:

added priority queue to vspbsptree

Location:

trunk/VUT/GtpVisibilityPreprocessor

Files:

• scripts/default.env (modified) (2 diffs)
• src/Environment.cpp (modified) (5 diffs)
• src/ViewCellBsp.cpp (modified) (5 diffs)
• src/ViewCellBsp.h (modified) (3 diffs)
• src/VspBspTree.cpp (modified) (24 diffs)
• src/VspBspTree.h (modified) (12 diffs)
• src/VspKdTree.cpp (modified) (20 diffs)
• src/VspKdTree.h (modified) (9 diffs)

trunk/VUT/GtpVisibilityPreprocessor/scripts/default.env

@@ -289 +289 @@
                 minRays                 500
                 minSize                 0.1
-                maxCostRatio            999.0
+                maxCostRatio            0.9
+                missTolerance           4
                 maxRayContribution      0.2
         }
@@ -345 +346 @@
         Termination {
                 # parameters used for autopartition
-                minRays 100
-                minPolygons -1
-                maxDepth 30
-                minPvs 100
-                minArea 0.01
-                maxRayContribution 0.005
-                #maxAccRayLength 100
+                minRays                 100
+                minPolygons             -1
+                maxDepth                30
+                minPvs                  100
+                minArea                 0.01
+                maxRayContribution      0.005
+                maxCostRatio            0.9
+                missTolerance           4
+                #maxAccRayLength        100
                 
                 # used for pvs criterium

trunk/VUT/GtpVisibilityPreprocessor/src/Environment.cpp

@@ -139 +139 @@
     return;
 
-  numParams = strlen(optParams) + 1;
+  numParams = (int)strlen(optParams) + 1;
   optionalParams = new char[numParams];
   strcpy(optionalParams, optParams);
@@ -390 +390 @@
   if (options[i].value != NULL) {
     // option was explicitly specified
-    value = strtod(options[i].value, NULL);
+    value = (Real)strtod(options[i].value, NULL);
   } else {
     // option was not read, so use the default
-    value = strtod(options[i].defaultValue, NULL);
+    value = (Real)strtod(options[i].defaultValue, NULL);
   }
   return true;
@@ -1315 +1315 @@
                  "100");
 
-  RegisterOption("BspTree.Termination.AxisAligned.maxCostRatio",
+  RegisterOption("BspTree.Termination.maxCostRatio",
                  optFloat,
                  "-bsp_term_axis_aligned_max_cost_ratio=",
@@ -1512 +1512 @@
                 "false");
 
+        RegisterOption("VspKdTree.Termination.maxCostRatio",
+                optFloat,
+                "-vsp_kd_term_max_cost_ratio=",
+                "1.5");
+
+        RegisterOption("VspKdTree.Termination.missTolerance",
+                 optInt,
+                 "-vsp_kd_term_miss_tolerance=",
+                 "4");
 
         /************************************************************************************/
@@ -1663 +1672 @@
                         "1.5");
 
+        RegisterOption("VspBspTree.Termination.maxCostRatio",
+                optFloat,
+                "-vsp_bsp_term_max_cost_ratio=",
+                "1.5");
+
+        RegisterOption("VspBspTree.Termination.missTolerance",
+                 optInt,
+                 "-vsp_bsp_term_miss_tolerance=",
+                 "4");
 
         RegisterOption("VspBspTree.Termination.AxisAligned.ct_div_ci",

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp

@@ -195 +195 @@
 
         //-- termination criteria for axis aligned split
-        environment->GetFloatValue("BspTree.Termination.AxisAligned.ct_div_ci", mAaCtDivCi);
-        environment->GetFloatValue("BspTree.Termination.AxisAligned.maxCostRatio", mMaxCostRatio);
+        environment->GetFloatValue("BspTree.Termination.AxisAligned.ct_div_ci", mAxisAlignedCtDivCi);
+        environment->GetFloatValue("BspTree.Termination.maxCostRatio", mMaxCostRatio);
         environment->GetIntValue("BspTree.Termination.AxisAligned.minPolys", 
                                                          mTermMinPolysForAxisAligned);
@@ -406 +406 @@
 void BspTree::InsertPolygons(PolygonContainer *polys)
 {       
-        std::stack<BspTraversalData> tStack;
+        BspTraversalStack tStack;
 
         // traverse existing tree or create new tree
@@ -710 +710 @@
 void BspTree::Construct(PolygonContainer *polys, BoundedRayContainer *rays)
 {
-        std::stack<BspTraversalData> tStack;
+        BspTraversalStack tStack;
 
         mRoot = new BspLeaf();
@@ -1042 +1042 @@
                         rbox.SetMin(axis, (*ci).value);
 
-                        float sum = objectsLeft * lbox.SurfaceArea() + 
-                                                objectsRight * rbox.SurfaceArea();
+                        const float sum = objectsLeft * lbox.SurfaceArea() + 
+                                                          objectsRight * rbox.SurfaceArea();
       
                         if (sum < minSum) 
@@ -1056 +1056 @@
         }
   
-        float oldCost = (float)polys.size();
-        float newCost = mAaCtDivCi + minSum / boxArea;
-        float ratio = newCost / oldCost;
+        const float oldCost = (float)polys.size();
+        const float newCost = mAxisAlignedCtDivCi + minSum / boxArea;
+        const float ratio = newCost / oldCost;
 
 

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.h

@@ -346 +346 @@
         
         typedef std::stack<BspTraversalData> BspTraversalStack;
+        //typedef std::priority_queue<BspTraversalData> BspTraversalStack;
 
         /** Default constructor creating an empty tree.
@@ -353 +354 @@
         ~BspTree();
 
-        
+        /** Returns detailed statistics of the BSP tree.
+        */
         const BspTreeStatistics &GetStatistics() const; 
   
@@ -797 +799 @@
 
         /// axis aligned split criteria
-        float mAaCtDivCi;
+        float mAxisAlignedCtDivCi;
         float mSplitBorder;
         float mMaxCostRatio;

trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.cpp

@@ -37 +37 @@
 VspBspTree::VspBspTree(): 
 mRoot(NULL),
-mPvsUseArea(true)
+mPvsUseArea(true),
+mNumCriteria(0)
 {
         mRootCell = new BspViewCell();
@@ -50 +51 @@
         environment->GetFloatValue("VspBspTree.Termination.maxRayContribution", mTermMaxRayContribution);
         environment->GetFloatValue("VspBspTree.Termination.minAccRayLenght", mTermMinAccRayLength);
+        environment->GetFloatValue("VspBspTree.Termination.maxCostRatio", mTermMaxCostRatio);
+        environment->GetIntValue("VspBspTree.Termination.missTolerance", mTermMissTolerance);
 
         //-- factors for bsp tree split plane heuristics
@@ -57 +60 @@
 
         //-- termination criteria for axis aligned split
-        environment->GetFloatValue("VspBspTree.Termination.AxisAligned.ct_div_ci", mAaCtDivCi);
-        environment->GetFloatValue("VspBspTree.Termination.AxisAligned.maxCostRatio", mMaxCostRatio);
+        environment->GetFloatValue("VspBspTree.Termination.AxisAligned.ct_div_ci", mAxisAlignedCtDivCi);
+        environment->GetFloatValue("VspBspTree.Termination.maxCostRatio", mTermMaxCostRatio);
         
         environment->GetIntValue("VspBspTree.Termination.AxisAligned.minRays", 
@@ -67 +70 @@
         environment->GetIntValue("VspBspTree.maxRayCandidates", mMaxRayCandidates);
         environment->GetIntValue("VspBspTree.splitPlaneStrategy", mSplitPlaneStrategy);
-        environment->GetFloatValue("VspBspTree.AxisAligned.splitBorder", mSplitBorder);
+        environment->GetFloatValue("VspBspTree.AxisAligned.splitBorder", mAxisAlignedSplitBorder);
 
         environment->GetFloatValue("VspBspTree.Construction.epsilon", mEpsilon);
@@ -82 +85 @@
         if (mSplitPlaneStrategy & RANDOM_POLYGON)
                 Debug << "random polygon ";
+
         if (mSplitPlaneStrategy & AXIS_ALIGNED)
+        {
+                ++ mNumCriteria;
                 Debug << "axis aligned ";
+        }
         if (mSplitPlaneStrategy & LEAST_RAY_SPLITS)
+        {
+                ++ mNumCriteria;
                 Debug << "least ray splits ";
+        }
         if (mSplitPlaneStrategy & BALANCED_RAYS)
+        {
+                ++ mNumCriteria;
                 Debug << "balanced rays ";
+        }
         if (mSplitPlaneStrategy & PVS)
+        {
+                ++ mNumCriteria;
                 Debug << "pvs";
+        }
 
         Debug << endl;
@@ -261 +277 @@
 void VspBspTree::Construct(const PolygonContainer &polys, RayInfoContainer *rays)
 {
-        std::stack<VspBspTraversalData> tStack;
+        VspBspTraversalStack tStack;
 
         mRoot = new BspLeaf();
@@ -338 +354 @@
                 EvaluateLeafStats(tData);
         
-                //-- clean up
-                
+                //-- clean up   
                 DEL_PTR(tData.mPolygons);
                 DEL_PTR(tData.mRays);
@@ -361 +376 @@
 
         // create new interior node and two leaf nodes
-        BspInterior *interior = 
-                SubdivideNode(tData, tFrontData, tBackData, coincident);
-
+        BspNode *newNode = SubdivideNode(tData, tFrontData, tBackData, coincident);
+
+        // subdivide further
+        if (!newNode->IsLeaf())
+        {
+                BspInterior *interior = dynamic_cast<BspInterior *>(newNode);
+                
 #ifdef _DEBUG   
 //      if (frontPolys->empty() && backPolys->empty() && (coincident.size() > 2))
@@ -371 +390 @@
 #endif
 
-        // push the children on the stack
-        tStack.push(tFrontData);
-        tStack.push(tBackData);
+                // push the children on the stack
+                tStack.push(tFrontData);
+                tStack.push(tBackData);
+
+                // delete old leaf node
+                DEL_PTR(tData.mNode);   
+        }
 
         // cleanup
-        DEL_PTR(tData.mNode);   
-
         DEL_PTR(tData.mPolygons);
         DEL_PTR(tData.mRays);
         DEL_PTR(tData.mGeometry);
 
-        return interior;
-}
-
-BspInterior *VspBspTree::SubdivideNode(VspBspTraversalData &tData,
-                                                                           VspBspTraversalData &frontData,
-                                                                           VspBspTraversalData &backData,
-                                                                           PolygonContainer &coincident)
+        return newNode;
+}
+
+BspNode *VspBspTree::SubdivideNode(VspBspTraversalData &tData,
+                                                                   VspBspTraversalData &frontData,
+                                                                   VspBspTraversalData &backData,
+                                                                   PolygonContainer &coincident)
 {
         mStat.nodes += 2;
@@ -394 +415 @@
         BspLeaf *leaf = dynamic_cast<BspLeaf *>(tData.mNode);
         
+        int maxCostMisses = tData.mMaxCostMisses;
+
         // select subdivision plane
-        BspInterior *interior = new BspInterior(SelectPlane(leaf, tData)); 
+        Plane3 splitPlane;
+        if (!SelectPlane(splitPlane, leaf, tData))
+        {
+                ++ maxCostMisses;
+
+                if (maxCostMisses >= mTermMissTolerance)
+            return leaf;
+        }
+
+        // subdivide further
+        BspInterior *interior = new BspInterior(splitPlane); 
 
 #ifdef _DEBUG
@@ -414 +447 @@
                                                                   coincident);
 
-    // compute pvs
+    
+        //-- set left and right traversal data
+        frontData.mMaxCostMisses = maxCostMisses;
+        backData.mMaxCostMisses = maxCostMisses;
+
+        // compute pvs
         frontData.mPvs = ComputePvsSize(*frontData.mRays);
         backData.mPvs = ComputePvsSize(*backData.mRays);
@@ -426 +464 @@
                                                                            mBox,
                                                                            mEpsilon);
-        
-                
-                frontData.mArea = frontData.mGeometry->GetArea();
-                backData.mArea = backData.mGeometry->GetArea();
+                        
+                // area is normalized with view space area
+                frontData.mArea = frontData.mGeometry->GetArea() / mBox.SurfaceArea();
+                backData.mArea = backData.mGeometry->GetArea() / mBox.SurfaceArea();
         }
 
@@ -543 +581 @@
         float boxArea = box.SurfaceArea();
   
-        float minBand = minBox + mSplitBorder * (maxBox - minBox);
-        float maxBand = minBox + (1.0f - mSplitBorder) * (maxBox - minBox);
+        float minBand = minBox + mAxisAlignedSplitBorder * (maxBox - minBox);
+        float maxBand = minBox + (1.0f - mAxisAlignedSplitBorder) * (maxBox - minBox);
         
         float minSum = 1e20f;
@@ -584 +622 @@
         }
   
-        float oldCost = (float)polys.size();
-        float newCost = mAaCtDivCi + minSum / boxArea;
-        float ratio = newCost / oldCost;
+        const float oldCost = (float)polys.size();
+        const float newCost = mAxisAlignedCtDivCi + minSum / boxArea;
+        const float ratio = newCost / oldCost;
 
 
@@ -615 +653 @@
         {
                 float p = 0;
-                float r = BestCostRatio(polys, box, i, p, objectsBack, objectsFront);
+                const float r = BestCostRatio(polys, box, i, p, objectsBack, objectsFront);
                 
                 if (r < costRatio)
@@ -625 +663 @@
         }
         
-        if (costRatio >= mMaxCostRatio)
+        if (costRatio >= mTermMaxCostRatio)
                 return false;
 
@@ -634 +672 @@
 }
 
-Plane3 VspBspTree::SelectPlane(BspLeaf *leaf, VspBspTraversalData &data)
+bool VspBspTree::SelectPlane(Plane3 &plane, 
+                                                         BspLeaf *leaf, 
+                                                         VspBspTraversalData &data)
 {
         if ((mSplitPlaneStrategy & AXIS_ALIGNED) &&
                 ((int)data.mRays->size() > mTermMinRaysForAxisAligned))
-        {
-                Plane3 plane;
-                if (SelectAxisAlignedPlane(plane, *data.mPolygons)) // TODO: should be rays
-                        return plane;
+        {       // TODO: candidates should be rays
+                return SelectAxisAlignedPlane(plane, *data.mPolygons); 
         }
 
@@ -651 +689 @@
                         const int randIdx = Random((int)data.mPolygons->size());
                         Polygon3 *nextPoly = (*data.mPolygons)[randIdx];
-                        return nextPoly->GetSupportingPlane();
+
+                        plane = nextPoly->GetSupportingPlane();
+                        return true;
                 }
                 else
@@ -665 +705 @@
                         const Vector3 normal = (*data.mRays)[candidateIdx].mRay->GetDir();
                         
-                        return Plane3(normal, pt);
-                }
-
-                return Plane3();
+                        plane = Plane3(normal, pt);
+                        return true;
+                }
+
+                return false;
         }
 
         // use heuristics to find appropriate plane
-        return SelectPlaneHeuristics(leaf, data); 
-}
-
-Plane3 VspBspTree::SelectPlaneHeuristics(BspLeaf *leaf, VspBspTraversalData &data)
+        return SelectPlaneHeuristics(plane, leaf, data); 
+}
+
+bool VspBspTree::SelectPlaneHeuristics(Plane3 &bestPlane, 
+                                                                           BspLeaf *leaf, 
+                                                                           VspBspTraversalData &data)
 {
         float lowestCost = MAX_FLOAT;
-        Plane3 bestPlane;
+        // intermediate plane
         Plane3 plane;
 
-        int limit = Min((int)data.mPolygons->size(), mMaxPolyCandidates);
-        
+        const int limit = Min((int)data.mPolygons->size(), mMaxPolyCandidates);
         int candidateIdx = limit;
         
@@ -774 +816 @@
         }       
 
+        // cost ratio miss
+        if (lowestCost > mTermMaxCostRatio)
+                return false;
+
 #ifdef _DEBUG
         Debug << "plane lowest cost: " << lowestCost << endl;
 #endif
-        return bestPlane;
+
+        return true;
 }
 
@@ -802 +849 @@
                                                                  const VspBspTraversalData &data)
 {
-        float val = 0;
+        float cost = 0;
 
         float sumBalancedRays = 0;
@@ -933 +980 @@
 
         const float raysSize = (float)data.mRays->size() + Limits::Small;
-
+        
         if (mSplitPlaneStrategy & LEAST_RAY_SPLITS)
-                val += mLeastRaySplitsFactor * sumRaySplits / raysSize;
+                cost += mLeastRaySplitsFactor * sumRaySplits / raysSize;
 
         if (mSplitPlaneStrategy & BALANCED_RAYS)
-                val += mBalancedRaysFactor * fabs(sumBalancedRays) /  raysSize;
-
-        const float denom = pOverall * (float)data.mPvs * 2.0f + Limits::Small;
-
+                cost += mBalancedRaysFactor * fabs(sumBalancedRays) /  raysSize;
+        
+        // pvs criterium
         if (mSplitPlaneStrategy & PVS)
         {
-                val += mPvsFactor * (frontPvs * pFront + (backPvs * pBack)) / denom;
+                const float oldCost = pOverall * (float)data.mPvs + Limits::Small;
+
+                cost += mPvsFactor * (frontPvs * pFront + (backPvs * pBack)) / oldCost;
 
                 // give penalty to unbalanced split
@@ -950 +998 @@
                 if (((pFront * 0.2 + Limits::Small) > pBack) || 
                         (pFront < (pBack * 0.2 + Limits::Small)))
-                        val += 0.5;
+                        cost += 0.5;
         }
 
@@ -958 +1006 @@
 //                << " backpvs: " << backPvs << " pBack: " << pBack << endl << endl;
 #endif
-        return val;
+
+        // normalize by number of criteria
+        return cost / (float)(mNumCriteria + Limits::Small);
 }
 

trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.h

@@ -10 +10 @@
 #include "RayInfo.h"
 #include "ViewCellBsp.h"
-#include "ViewCell.h"
 
 class ViewCell;
@@ -51 +50 @@
                 /// current depth
                 int mDepth;
-                
                 /// rays piercing this node
                 RayInfoContainer *mRays;
@@ -58 +56 @@
                 /// geometry of node as induced by planes
                 BspNodeGeometry *mGeometry;
-                
                 /// pvs size
                 int mPvs;
-                
+                /// how often this branch has missed the max-cost ratio
+                int mMaxCostMisses;
                 /** Returns average ray contribution.
                 */
@@ -77 +75 @@
                 mPvs(0),
                 mArea(0.0),
-                mGeometry(NULL)
+                mGeometry(NULL),
+                mMaxCostMisses(0)
                 {}
                 
@@ -93 +92 @@
                 mPvs(pvs),
                 mArea(area),
-                mGeometry(geom)
+                mGeometry(geom),
+                mMaxCostMisses(0)
                 {}
 
@@ -106 +106 @@
                 mPvs(0),
                 mArea(0),
-                mGeometry(geom)
+                mGeometry(geom),
+                mMaxCostMisses(0)
                 {}
+
+                friend bool operator<(const VspBspTraversalData &a, const VspBspTraversalData &b)
+                {
+#if 0
+                        return a.mPvs * a.mArea < b.mPvs * b.mArea;
+#endif
+#if 1
+                        return a.mPvs * (int)a.mRays->size() < b.mPvs * (int)b.mRays->size();
+#endif
+#if 0
+                        return a.mPvs < b.mPvs;
+#endif
+#if 0
+                        return 
+                                a.mPvs / (float)(a.mRays->size() + Limits::Small())
+                                >
+                                b.mPvs / (float)(b.mRays->size() + Limits::Small());
+#endif
+#if 0
+                        return a.mPvs * (int)a.mRays->size() <  b.mPvs * (int)b.mRays->size();
+#endif
+                }
     };
         
-        typedef std::stack<VspBspTraversalData> VspBspTraversalStack;
+        typedef std::priority_queue<VspBspTraversalData> VspBspTraversalStack;
+        //typedef std::stack<VspBspTraversalData> VspBspTraversalStack;
 
         /** Default constructor creating an empty tree.
@@ -257 +281 @@
 
         /** Selects the best possible splitting plane. 
+                @param plane returns the split plane
                 @param leaf the leaf to be split
                 @param polys the polygon list on which the split decition is based
                 @param rays ray container on which selection may be based
                 @note the polygons can be reordered in the process
-                @returns the split plane
-        */
-        Plane3 SelectPlane(BspLeaf *leaf, 
-                                           VspBspTraversalData &data);
-
+                @returns true if the cost of the split is under maxCostRatio
+
+        */
+        bool SelectPlane(Plane3 &plane, 
+                                         BspLeaf *leaf, 
+                                         VspBspTraversalData &data);
         
         /** Strategies where the effect of the split plane is tested
@@ -274 +300 @@
         float SplitPlaneCost(const Plane3 &candidatePlane, 
                                                  const VspBspTraversalData &data);
-
 
 
@@ -291 +316 @@
         */
 
-        BspInterior *SubdivideNode(VspBspTraversalData &tData,
-                                                           VspBspTraversalData &frontData,
-                                                           VspBspTraversalData &backData,
-                                                           PolygonContainer &coincident);
+        BspNode *SubdivideNode(VspBspTraversalData &tData,
+                                                   VspBspTraversalData &frontData,
+                                                   VspBspTraversalData &backData,
+                                                   PolygonContainer &coincident);
 
         /** Selects the split plane in order to construct a tree with
                 certain characteristics (e.g., balanced tree, least splits, 
                 2.5d aligned)
+                @param bestPlane returns the split plane
                 @param polygons container of polygons
                 @param rays bundle of rays on which the split can be based
-        */
-        Plane3 SelectPlaneHeuristics(BspLeaf *leaf,
-                                                                 VspBspTraversalData &data);
+
+                @returns true if the overall cost is under maxCostRatio
+        */
+        bool SelectPlaneHeuristics(Plane3 &bestPlane, 
+                                                           BspLeaf *leaf, 
+                                                           VspBspTraversalData &data);
 
         /** Extracts the meshes of the objects and adds them to polygons. 
@@ -476 +505 @@
         float mTermMinAccRayLength;
 
-
         /// strategy to get the best split plane
         int mSplitPlaneStrategy;
@@ -487 +515 @@
 
         //-- axis aligned split criteria
-        float mAaCtDivCi;
-        float mSplitBorder;
-        float mMaxCostRatio;
+        float mAxisAlignedCtDivCi;
+        /// spezifies the split border of the axis aligned split
+        float mAxisAlignedSplitBorder;
+
+        /// maximal acceptable cost ratio
+        float mTermMaxCostRatio;
+        /// tolerance value indicating how often the max cost ratio can be failed
+        int mTermMissTolerance;
 
         //-- factors guiding the split plane heuristics
@@ -498 +531 @@
         /// if area or accumulated ray lenght should be used for PVS heuristics
         bool mPvsUseArea;
-
+        /// tolerance for polygon split
         float mEpsilon;
-
+        /// maximal number of test rays used to evaluate candidate split plane
         int mMaxTests;
+        /// number of different bsp split plane criteria
+        int mNumCriteria;
 
 private:

trunk/VUT/GtpVisibilityPreprocessor/src/VspKdTree.cpp

@@ -31 +31 @@
 int VspKdLeaf::sMailId = 0;
 int MergeCandidate::sMaxPvsSize = 150;
-
-
+float MergeCandidate::sOverallCost = Limits::Small;
 #define USE_FIXEDPOINT_T 0
 
@@ -184 +183 @@
 
 
-VspKdLeaf::VspKdLeaf(VspKdInterior *p,  const int nRays):
-VspKdNode(p), mRays(), mPvsSize(0), mValidPvs(false), mViewCell(NULL)
+VspKdLeaf::VspKdLeaf(VspKdInterior *p, 
+                                         const int nRays, 
+                                         const int maxCostMisses):
+VspKdNode(p), mRays(), mPvsSize(0), mValidPvs(false), mViewCell(NULL),
+mMaxCostMisses(maxCostMisses)
 {
         mRays.reserve(nRays);
@@ -193 +195 @@
 {
 }
+
+
+int VspKdLeaf::GetMaxCostMisses()
+{
+        return mMaxCostMisses;
+}
+
 
 int VspKdLeaf::Type() const
@@ -343 +352 @@
         environment->GetFloatValue("VspKdTree.Termination.minSize", mTermMinSize);
 
+        environment->GetIntValue("VspKdTree.Termination.missTolerance", mTermMissTolerance);
+
         mTermMinSize = sqr(mTermMinSize);
 
@@ -356 +367 @@
         //environment->GetIntValue("ViewCells.maxViewCells", mMaxViewCells);
 
-        environment->GetIntValue("VspKdTree.PostProcess.minViewCells", mMinViewCells);
-        environment->GetFloatValue("VspKdTree.PostProcess.maxCostRatio", mMaxCostRatio);
+        environment->GetIntValue("VspKdTree.PostProcess.minViewCells", mMergeMinViewCells);
+        environment->GetFloatValue("VspKdTree.PostProcess.maxCostRatio", mMergeMaxCostRatio);
         environment->GetIntValue("VspKdTree.PostProcess.maxPvsSize",
                                                          MergeCandidate::sMaxPvsSize);
@@ -615 +626 @@
                 tStack.pop();
 
-                VspKdNode *node = SubdivideNode((VspKdLeaf *) data.mNode,
-                                                                                        data.mBox, backBox,     frontBox);
+                VspKdNode *node = SubdivideNode(dynamic_cast<VspKdLeaf *>(data.mNode),
+                                                                                data.mBox, backBox,     frontBox);
                 if (result == NULL)
                         result = node;
@@ -663 +674 @@
         else if (splitType == ESplitHeuristic)
         {
-                        costRatio = BestCostRatioHeuristic(leaf,
-                                                                                           axis,
-                                                                                           position,
-                                                                                           raysBack,
-                                                                                           raysFront,
-                                                                                           pvsBack,
-                                                                                           pvsFront);
+                costRatio = BestCostRatioHeuristic(leaf,
+                                                                                   axis,
+                                                                                   position,
+                                                                                   raysBack,
+                                                                                   raysFront,
+                                                                                   pvsBack,
+                                                                                   pvsFront);
         }
         else
@@ -1022 +1033 @@
 
 VspKdNode *VspKdTree::SubdivideNode(VspKdLeaf *leaf,
-                                                                                const AxisAlignedBox3 &box,
-                                                                                AxisAlignedBox3 &backBBox,
-                                                                                AxisAlignedBox3 &frontBBox)
+                                                                        const AxisAlignedBox3 &box,
+                                                                        AxisAlignedBox3 &backBBox,
+                                                                        AxisAlignedBox3 &frontBBox)
 {
         if (TerminationCriteriaMet(leaf, box))
@@ -1050 +1061 @@
         //Debug << "rays back=" << raysBack << " rays front=" << raysFront << " pvs back=" << pvsBack << " pvs front=" <<       pvsFront << endl;
 
+        int maxCostMisses = leaf->GetMaxCostMisses();
+
         if (axis == -1)
         {
-                return leaf;
+                ++ maxCostMisses;
+
+                if (maxCostMisses >= mTermMissTolerance)
+                        return leaf;
         }
 
@@ -1068 +1084 @@
         frontBBox = box;
 
-        VspKdLeaf *back = new VspKdLeaf(node, raysBack);
+        VspKdLeaf *back = new VspKdLeaf(node, raysBack, maxCostMisses);
         back->SetPvsSize(pvsBack);
-        VspKdLeaf *front = new VspKdLeaf(node, raysFront);
+        VspKdLeaf *front = new VspKdLeaf(node, raysFront, maxCostMisses);
         front->SetPvsSize(pvsFront);
 
@@ -1488 +1504 @@
                 else
                 {
-                        tstack.push(((VspKdInterior *)node)->GetFront());
-                        tstack.push(((VspKdInterior *)node)->GetBack());
+                        tstack.push(dynamic_cast<VspKdInterior *>(node)->GetFront());
+                        tstack.push(dynamic_cast<VspKdInterior *>(node)->GetBack());
                 }
         }
@@ -1499 +1515 @@
 
         if (newLeaf->mParent)
+        {
                 newLeaf->mParent->ReplaceChildLink(sroot, newLeaf);
-
+        }
         tstack.push(sroot);
 
@@ -2078 +2095 @@
 bool VspKdTree::MergeViewCells(VspKdLeaf *l1, VspKdLeaf *l2)
 {
-        //-- change pointer to view cells of all leaves associated with the previous view cells
+        //-- change pointer to view cells of all leaves associated 
+        //-- with the previous view cells
         VspKdViewCell *fVc = l1->GetViewCell();
         VspKdViewCell *bVc = l2->GetViewCell();
@@ -2156 +2174 @@
 
                         for (nit = neighbors.begin(); nit != nit_end; ++ nit)
-                                mergeQueue.push(MergeCandidate(leaf, *nit));
+                        {
+                                MergeCandidate mc = MergeCandidate(leaf, *nit);
+                                mergeQueue.push(mc);
+
+                                MergeCandidate::sOverallCost += mc.GetLeaf1Cost();
+                                MergeCandidate::sOverallCost += mc.GetLeaf2Cost();
+                        }
                 }
         }
@@ -2166 +2190 @@
         // use priority queue to merge leaves
         while (!mergeQueue.empty() &&
-                   (vcSize > mMinViewCells))// &&
-                   //(mergeQueue.top().GetMergeCost() < mMaxCostRatio))
+                   (vcSize > mMergeMinViewCells) &&
+                   (mergeQueue.top().GetMergeCost() < 
+                    mMergeMaxCostRatio / MergeCandidate::sOverallCost))
         {
                 //Debug << mergeQueue.top().GetMergeCost() << " " << mMaxCostRatio << endl;
@@ -2184 +2209 @@
                         ++ merged;
                         -- vcSize;
+                        // increase absolute merge cost
+                        MergeCandidate::sOverallCost += mc.GetMergeCost();
                 }
                 // merge candidate not valid, because one of the leaves was already
@@ -2230 +2257 @@
                         if (!viewCell->Mailed())
                         {
-                                Debug << "jhere2" << endl;
                                 viewCell->mLeaves.clear();
                                 viewCell->Mail();
@@ -2252 +2278 @@
                 return node;
 
-        Debug << "here554444" << endl;
         VspKdInterior *interior = dynamic_cast<VspKdInterior *>(node);
 
@@ -2300 +2325 @@
 }
 
+float MergeCandidate::GetLeaf1Cost() const
+{
+        VspKdViewCell *vc = mLeaf1->GetViewCell();
+        return vc->GetPvs().GetSize() * vc->GetVolume();
+}
+
+float MergeCandidate::GetLeaf2Cost() const
+{
+        VspKdViewCell *vc = mLeaf2->GetViewCell();
+        return vc->GetPvs().GetSize() * vc->GetVolume();
+}
 
 void MergeCandidate::EvalMergeCost()
@@ -2313 +2349 @@
         //-- (added size of left and right view cell times pvs size)
         //-- to new rendering cost (size of merged view cell times pvs size)
-        const float oldCost =
-                (float)vc1->GetPvs().GetSize() * vc1->GetVolume() +
-                (float)vc2->GetPvs().GetSize() * vc2->GetVolume();
-
+        const float oldCost = GetLeaf1Cost() + GetLeaf2Cost();
+        
         const float newCost =
                 (float)vcPvs * (vc1->GetVolume() + vc2->GetVolume());

trunk/VUT/GtpVisibilityPreprocessor/src/VspKdTree.h

@@ -76 +76 @@
         float GetMergeCost() const;
 
+        /** Returns cost of leaf 1.
+        */
+        float GetLeaf1Cost() const;
+        /** Returns cost of leaf 2.
+        */
+        float GetLeaf2Cost() const;
+
         /// maximal pvs size
         static int sMaxPvsSize;
+        /// overall cost used to normalize cost ratio
+        static float sOverallCost;
 
 protected:
@@ -305 +314 @@
                 @param p the parent node
                 @param nRays preallocates memory to store this number of rays
-        */
-        VspKdLeaf(VspKdInterior *p,     const int nRays);
+                @parma maxMisses how many times the max cost ratio was missed on the path to the leaf
+        */
+        VspKdLeaf(VspKdInterior *p,     const int nRays, const int maxCostMisses = 0);
         
         virtual ~VspKdLeaf();
@@ -365 +375 @@
         VspKdViewCell *GetViewCell();
 
+        /** Returns number of times the max cost ratio was missed until
+                this leaf.
+        */
+        int GetMaxCostMisses();
+
+
         ////////////////////////////////////////////
         
@@ -371 +387 @@
         static int sMailId;
 
-
+        
 protected:
 
@@ -381 +397 @@
         int mMailbox;
   
+        /// rays intersecting this leaf.
         RayInfoContainer mRays;
-        
         /// true if mPvsSize is valid => PVS does not have to be updated
         bool mValidPvs;
-
         /// the view cell associated with this leaf
         VspKdViewCell *mViewCell;
+        /// number of times the max cost ratio was missed on the way to the leaf.
+        int mMaxCostMisses;
 
 private:
@@ -453 +470 @@
                 //    TraversalData(const TraversalData &s):node(s.node), bbox(s.bbox), depth(s.depth) {}
     
-                friend bool operator<(const TraversalData &a, const TraversalData &b) 
+        friend bool operator<(const TraversalData &a, const TraversalData &b) 
                 {
                         // return a.node->queries.size() < b.node->queries.size();
@@ -743 +760 @@
         ViewCellsManager *mViewCellsManager;
 
-        /// maximal cost ratio of a merge
-        float mMaxCostRatio;
-
         /////////////////////////////
         // Construction parameters
@@ -751 +765 @@
         /// max depth of the tree
         int mTermMaxDepth;
-
         /// minimal ratio of the volume of the cell and the query volume
         float mTermMinSize;
-
         /// minimal pvs per node to still get subdivided
         int mTermMinPvs;
-
         /// minimal ray number per node to still get subdivided
         int mTermMinRays;
-        
-        /// maximal cost ration to subdivide a node
+        /// maximal acceptable cost ratio to continue subdivision
         float mTermMaxCostRatio;
-        
         /// maximal contribution per ray to subdivide the node
         float mTermMaxRayContribution;
+        /// tolerance value indicating how often the max cost ratio can be failed
+        int mTermMissTolerance;
+
+        /// maximal numbers of view cells
+        int mMaxViewCells;
+
+        /// maximal cost ratio of a merge
+        float mMergeMaxCostRatio;
+        
+        /// minimal number of view cells
+        int mMergeMinViewCells;
 
         /// if only the "driving axis", i.e., the axis with the biggest extent
@@ -771 +791 @@
         bool mOnlyDrivingAxis;
 
-        /// maximal numbers of view cells
-        int mMaxViewCells;
-
-        /// minimal number of view cells
-        int mMinViewCells;
-
         /////////////////////////////
         VspKdStatistics mStat;