Changeset 472 for trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.cpp

Timestamp:

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

Author:

mattausch

Message:

added priority queue to vspbsptree

File:

• trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.cpp (modified) (24 diffs)

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);
 }