Changeset 302 for trunk

Timestamp:

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

Author:

mattausch

Message:

added surface area heuristic for bsp

Location:

trunk/VUT/GtpVisibilityPreprocessor

Files:

• scripts/default.env (modified) (2 diffs)
• src/AxisAlignedBox3.cpp (modified) (1 diff)
• src/AxisAlignedBox3.h (modified) (1 diff)
• src/ViewCellBsp.cpp (modified) (8 diffs)
• src/ViewCellBsp.h (modified) (5 diffs)
• src/main.cpp (modified) (1 diff)

trunk/VUT/GtpVisibilityPreprocessor/scripts/default.env

@@ -76 +76 @@
         #splitPlaneStrategy 12
         #axis aligned + vertical axis
-        #splitPlaneStrategy 66
+        splitPlaneStrategy 66
         # axis aligned + balanced view cells
-        splitPlaneStrategy 18
+        # splitPlaneStrategy 18
         # largest polygon area
         #splitPlaneStrategy 32
@@ -89 +89 @@
         maxViewCells 999999
         Termination {
-                maxPolysForAxisAligned 20
+                maxPolysForAxisAligned 200
                 maxPolygons 0
                 maxDepth 100

trunk/VUT/GtpVisibilityPreprocessor/src/AxisAlignedBox3.cpp

@@ -657 +657 @@
 {
   Vector3 ext = mMax - mMin;
+ 
   return 2.0 * (ext.x * ext.y +
                 ext.x * ext.z +

trunk/VUT/GtpVisibilityPreprocessor/src/AxisAlignedBox3.h

@@ -198 +198 @@
   virtual float SurfaceArea() const;
   virtual float GetVolume() const {
-    return (mMax.x -mMin.x) * (mMax.y -mMin.y) * (mMax.z - mMin.z);
+    return (mMax.x - mMin.x) * (mMax.y - mMin.y) * (mMax.z - mMin.z);
   }
 

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;

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.h

@@ -244 +244 @@
 };
 
-
 /** Implementation of the ViewCell BSP tree. */
 class BspTree 
@@ -331 +330 @@
 protected:
         
+        // --------------------------------------------------------------
+        // For sorting objects
+        // --------------------------------------------------------------
+        struct SortableEntry
+        {
+                enum {POLY_MIN, POLY_MAX};
+    
+                int type;
+                float value;
+                Polygon3 *poly;
+                SortableEntry() {}
+                SortableEntry(const int t, const float v, Polygon3 *poly): 
+                type(t), value(v), poly(poly) {}
+                
+                bool operator<(const SortableEntry &b) const 
+                {
+                        return value < b.value;
+                }  
+        };
+
         /** Constructs the tree from the given list of polygons.
                 @param viewCells if not NULL, new view cells are 
@@ -355 +374 @@
 
         /** Selects a splitting plane. 
+                @param leaf the leaf to be split
                 @param polys the polygon list on which the split decition is based
         */
-        Plane3 SelectPlane(const PolygonContainer &polys) const;
+        Plane3 SelectPlane(BspLeaf *leaf, const PolygonContainer &polys) const;
 
         /** Filters next view cell down the tree and inserts it into the appropriate leaves
@@ -445 +465 @@
                                                   const bool extractBack) const;
         
+        /** Computes best cost ratio for the suface area heuristics for axis aligned
+                splits. This heuristics minimizes the cost for ray traversal.
+                @param polys the polygons guiding the ratio computation
+                @param box the bounding box of the leaf
+                @param axis the current split axis
+                @param position returns the split position
+                @param objectsBack the number of objects in the back of the split plane
+                @param objectsFront the number of objects in the front of the split plane
+        */
+        float BestCostRatio(const PolygonContainer &polys,
+                                                const AxisAlignedBox3 &box,
+                                                const int axis,
+                                                float &position,
+                                                int &objectsBack,
+                                                int &objectsFront) const;
+        
+        /** Sorts split candidates for surface area heuristics for axis aligned splits.
+                @param polys the input for choosing split candidates
+                @param axis the current split axis
+                @param splitCandidates returns sorted list of split candidates
+        */
+        void SortSplitCandidates(const PolygonContainer &polys, 
+                                                         const int axis, 
+                                                         vector<SortableEntry> &splitCandidates) const;
+
         /// Pointer to the root of the tree
         BspNode *mRoot;
@@ -490 +535 @@
         static int sTermMaxPolysForAxisAligned;
 
+        static float sCt_div_ci;
+        static float sSplitBorder;
+        static float sMaxCostRatio;
+
         // factors to guid the split plane heuristics
         static float sLeastSplitsFactor;

trunk/VUT/GtpVisibilityPreprocessor/src/main.cpp

@@ -54 +54 @@
   p->Export("vc_bsptree.x3d", false, false, true);
 
-  //-- export the complementary view cells, i.e., the view cells not associated with leafs in the tree.
+  //-- export the complementary view cells
+  // i.e., the view cells not associated with leafs in the tree.
   Exporter *exporter = Exporter::GetExporter("viewcells_compl.x3d");