Changeset 302 for trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp

Timestamp:

09/29/05 18:42:04 (19 years ago)

Author:

mattausch

Message:

added surface area heuristic for bsp

File:

• trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp (modified) (8 diffs)

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp

@@ -19 +19 @@
 int BspTree::sConstructionMethod = VIEW_CELLS;
 int BspTree::sTermMaxPolysForAxisAligned = 50;
+
+float BspTree::sCt_div_ci = 1.0f;
+float BspTree::sSplitBorder = 1.0f;
+float BspTree::sMaxCostRatio = 0.9;
 
 //-- factors for bsp tree split plane heuristics
@@ -581 +585 @@
         if ((tData.mPolygons->size() <= sTermMaxPolygons) || (tData.mDepth >= sTermMaxDepth))
         {
-#ifdef _DEBUG
+//#ifdef _DEBUG
                 Debug << "subdivision terminated at depth " << tData.mDepth << ", #polys: " << (int)tData.mPolygons->size() << endl;
-#endif
+//#endif
 
                 EvaluateLeafStats(tData);
@@ -691 +695 @@
 
         // add the new nodes to the tree + select subdivision plane
-        BspInterior *interior = new BspInterior(SelectPlane(*polys)); 
+        BspInterior *interior = new BspInterior(SelectPlane(leaf, *polys)); 
 
 #ifdef _DEBUG
@@ -719 +723 @@
 }
 
-Plane3 BspTree::SelectPlane(const PolygonContainer &polys)  const
+void BspTree::SortSplitCandidates(const PolygonContainer &polys, 
+                                                                  const int axis, 
+                                                                  vector<SortableEntry> &splitCandidates) const
+{
+  splitCandidates.clear();
+  
+  int requestedSize = 2 * (int)polys.size();
+  // creates a sorted split candidates array  
+  splitCandidates.reserve(requestedSize);
+  
+  PolygonContainer::const_iterator it, it_end = polys.end();
+
+  AxisAlignedBox3 box;
+
+  // insert all queries 
+  for(it = polys.begin(); it != it_end; ++ it)
+  {
+          box.Initialize();
+          box.Include(*(*it));
+          
+          splitCandidates.push_back(SortableEntry(SortableEntry::POLY_MIN, box.Min(axis), *it));
+      splitCandidates.push_back(SortableEntry(SortableEntry::POLY_MAX, box.Max(axis), *it));
+  }
+  
+  stable_sort(splitCandidates.begin(), splitCandidates.end());
+}
+
+
+float BspTree::BestCostRatio(const PolygonContainer &polys,
+                                                         const AxisAlignedBox3 &box,
+                                                         const int axis,
+                                                         float &position,
+                                                         int &objectsBack,
+                                                         int &objectsFront) const
+{
+        vector<SortableEntry> splitCandidates;
+
+        SortSplitCandidates(polys, axis, splitCandidates);
+        
+        // go through the lists, count the number of objects left and right
+        // and evaluate the following cost funcion:
+        // C = ct_div_ci  + (ol + or)/queries
+        
+        int objectsLeft = 0, objectsRight = (int)polys.size();
+        
+        float minBox = box.Min(axis);
+        float maxBox = box.Max(axis);
+        float boxArea = box.SurfaceArea();
+  
+        float minBand = minBox + sSplitBorder * (maxBox - minBox);
+        float maxBand = minBox + (1.0f - sSplitBorder) * (maxBox - minBox);
+        
+        float minSum = 1e20f;
+        vector<SortableEntry>::const_iterator ci, ci_end = splitCandidates.end();
+
+        for(ci = splitCandidates.begin(); ci != ci_end; ++ ci) 
+        {
+                switch ((*ci).type) 
+                {
+                        case SortableEntry::POLY_MIN:
+                                ++ objectsLeft;
+                                break;
+                        case SortableEntry::POLY_MAX:
+                            -- objectsRight;
+                                break;
+                        default:
+                                break;
+                }
+                
+                if ((*ci).value > minBand && (*ci).value < maxBand) 
+                {
+                        AxisAlignedBox3 lbox = box;
+                        AxisAlignedBox3 rbox = box;
+                        lbox.SetMax(axis, (*ci).value);
+                        rbox.SetMin(axis, (*ci).value);
+
+                        float sum = objectsLeft * lbox.SurfaceArea() + 
+                                                objectsRight * rbox.SurfaceArea();
+      
+                        if (sum < minSum) 
+                        {
+                                minSum = sum;
+                                position = (*ci).value;
+
+                                objectsBack = objectsLeft;
+                                objectsFront = objectsRight;
+                        }
+                }
+        }
+  
+        float oldCost = (float)polys.size();
+        float newCost = sCt_div_ci + minSum / boxArea;
+        float ratio = newCost / oldCost;
+
+
+#if 0
+  Debug << "====================" << endl;
+  Debug << "costRatio=" << ratio << " pos=" << position<<" t=" << (position - minBox)/(maxBox - minBox)
+      << "\t o=(" << objectsBack << "," << objectsFront << ")" << endl;
+#endif
+  return ratio;
+}
+
+Plane3 BspTree::SelectPlane(BspLeaf *leaf, const PolygonContainer &polys)  const
 {
         if (polys.size() == 0)
@@ -741 +848 @@
                 Vector3 position;
 
-                for (int i=0; i < 3; i++) 
+                for (int i = 0; i < 3; ++ i) 
                 {
                         float p = 0;
-                        float r = 0;/*BestCostRatio(leaf,
-                                                                        box,
-                                                                        i,
-                                                                        p,
-                                                                        objectsBack,
-                                                                        objectsFront);*/
+                        float r = BestCostRatio(polys, box, i, p, objectsBack, objectsFront);
+                        
                         if (r < costRatio)
                         {
@@ -758 +861 @@
                 }
                 
-                //if (costRatio > mMaxCostRatio) axis = -1;
-                Vector3 norm(0,0,0); norm[axis] = 1.0f;
-                return Plane3(norm, position);
-
+                if (costRatio < sMaxCostRatio)
+                {
+                        Vector3 norm(0,0,0); norm[axis] = 1.0f;
+                        return Plane3(norm, position);
+                }
                 /*int axis = box.Size().DrivingAxis();
                 Vector3 norm(0,0,0); norm[axis] = 1;
                 Vector3 pt = (box.Min()[axis] + box.Max()[axis]) * 0.5f;*/
-                //Debug << "splitting axis aligned" << endl;
+                
                 //return Plane3(norm, pt);
         }
@@ -775 +879 @@
         }
 
-        /*if (sSplitPlaneStrategy & VERTICAL_AXIS)
-        {
-                const float dot_thres = 0.999;
-                PolygonContainer::const_iterator it, it_end = polys->end();
-                
-                for (it = polys->begin(); it != it_end; ++ it)
-                {
-                        if (DotProd((*it)->GetSupportingPlane().mNormal, mVerticalAxis) > dot_thres)
-                                return (*it)->GetSupportingPlane();
-                }
-        }*/
-        
         // use heuristics to find appropriate plane
         return SelectPlaneHeuristics(polys, sMaxCandidates);
@@ -932 +1024 @@
         environment->GetIntValue("BspTree.maxCandidates", sMaxCandidates);
         environment->GetIntValue("BspTree.splitPlaneStrategy", sSplitPlaneStrategy);
+
+        // need kdtree criteria for axis aligned split
+        environment->GetFloatValue("MeshKdTree.Termination.ct_div_ci", sCt_div_ci);
+        environment->GetFloatValue("MeshKdTree.splitBorder", sSplitBorder);
+        environment->GetFloatValue("MeshKdTree.Termination.maxCostRatio", sMaxCostRatio);
 
     Debug << "BSP max depth: " << sTermMaxDepth << endl;