Changeset 297 for trunk

Timestamp:

09/26/05 02:00:42 (19 years ago)

Author:

mattausch

Message:

added bsp split plane criteria

Location:

trunk/VUT/GtpVisibilityPreprocessor

Files:

• scripts/default.env (modified) (2 diffs)
• src/Environment.cpp (modified) (1 diff)
• src/Polygon3.cpp (modified) (3 diffs)
• src/Preprocessor.cpp (modified) (3 diffs)
• src/Preprocessor.h (modified) (1 diff)
• src/ViewCellBsp.cpp (modified) (19 diffs)
• src/ViewCellBsp.h (modified) (7 diffs)
• src/main.cpp (modified) (1 diff)

trunk/VUT/GtpVisibilityPreprocessor/scripts/default.env

@@ -65 +65 @@
 
 BspTree {
-        splitPlaneStrategy 14
+        # next polygon         = 1
+        # axis aligned         = 2
+        # least splits         = 4
+        # balanced polygons    = 8
+        # balanced view cells  = 16
+        # largest polygon area = 32
+        # vertical axis        = 64
+        
+        # least splits + balanced polygons
+        #splitPlaneStrategy 12
+        # axis aligned + vertical axis
+        #splitPlaneStrategy 66
+        # axis aligned + balanced view cells
+        #splitPlaneStrategy 18
+        # largest polygon area
+        #splitPlaneStrategy 32
+        splitPlaneStrategy 72
 #       constructionMethod rays
         constructionMethod viewCells
@@ -72 +88 @@
         maxViewCells 999999
         Termination {
+                maxPolysForAxisAligned 50
                 maxPolygons 0
                 maxDepth 100

trunk/VUT/GtpVisibilityPreprocessor/src/Environment.cpp

@@ -1161 +1161 @@
                  "5");
   
+  RegisterOption("BspTree.Termination.maxPolysForAxisAligned",
+                 optInt,
+                 "-bsp_term_max_polygons=",
+                 "50");
+
   RegisterOption("BspTree.Termination.maxDepth",
                  optInt,

trunk/VUT/GtpVisibilityPreprocessor/src/Polygon3.cpp

@@ -124 +124 @@
         bool onFrontSide = false;
         bool onBackSide = false;
-        // threshold for coincident classification
-        const float dot_thres = 0.99f;
-
+        
         int count = 0;
         // find possible line-plane intersections
@@ -145 +143 @@
                 // 3 vertices enough to decide coincident
                 else if (((++ count) >= 3) && !onFrontSide && !onBackSide) 
-                {
-                        // Decide if plane and surface normal are same
-                        if (DotProd(plane.mNormal, GetSupportingPlane().mNormal) > dot_thres)
-                                return COINCIDENT; // plane and polygon are coincident
-                        else 
-                                return FRONT_SIDE;
-                }
+                        return COINCIDENT; 
         }
 
@@ -163 +155 @@
         }
 
-        // Decide if plane and surface normal are same
-        if (DotProd(plane.mNormal, GetSupportingPlane().mNormal) > dot_thres)
-                return COINCIDENT; // plane and polygon are coincident
-        else 
-                return FRONT_SIDE;
+        return COINCIDENT; // plane and polygon are coincident
 }
 

trunk/VUT/GtpVisibilityPreprocessor/src/Preprocessor.cpp

@@ -9 +9 @@
 Preprocessor::Preprocessor():
 mKdTree(NULL),
-mBspTree(NULL)
+mBspTree(NULL),
+mRootViewCell(NULL)
 {
 }
@@ -18 +19 @@
   DEL_PTR(mBspTree);
   DEL_PTR(mKdTree);
+  DEL_PTR(mRootViewCell);
 }
 
@@ -87 +89 @@
 {
         DEL_PTR(mBspTree);
-        mBspTree = new BspTree();
+        DEL_PTR(mRootViewCell);
+        mRootViewCell = new ViewCell();
+        mBspTree = new BspTree(mRootViewCell);
 
         ObjectContainer objects;

trunk/VUT/GtpVisibilityPreprocessor/src/Preprocessor.h

@@ -105 +105 @@
   /// BSP tree representing the viewcells
   BspTree *mBspTree;
+
+  /// the root view cell of the bsp tree
+  ViewCell *mRootViewCell;
 };
 

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp

@@ -18 +18 @@
 int BspTree::sSplitPlaneStrategy = NEXT_POLYGON; 
 int BspTree::sConstructionMethod = VIEW_CELLS;
-float BspTree::sLeastSplitsFactor = 1.0f
-float BspTree::sBalancedTreeFactor = 2.0f;
-float BspTree::sVerticalFactor = 50.0f // very important criterium for 2.5d scenes
+int BspTree::sTermMaxPolysForAxisAligned = 50;
+
+//-- factors for bsp tree split plane heuristics
+float BspTree::sLeastSplitsFactor = 1.0f;
+float BspTree::sBalancedPolysFactor = 2.0f;
+float BspTree::sBalancedViewCellsFactor = 2.0f;
+float BspTree::sVerticalSplitsFactor = 1.0f; // very important criterium for 2.5d scenes
 
 
@@ -30 +34 @@
         contribution for a minimum number splits in the tree.
 */
-float BspTree::sBalancedTreeTable[] = {-1, 1, 0, 0};
+float BspTree::sBalancedPolysTable[] = {-1, 1, 0, 0};
 
 //int counter = 0;
@@ -187 +191 @@
 
                                 ++ splits; // increase number of splits
-                                // check if polygon still valid 
+
+                                // check if polygons still valid 
                                 if (front_piece->mVertices.size() >= 3)
                                         frontPolys->push_back(front_piece);
                                 else
                                         DEL_PTR(front_piece);
-                                // check if polygon still valid
+                                
                                 if (back_piece->mVertices.size() >= 3)
                                         backPolys->push_back(back_piece);
@@ -248 +253 @@
 /****************************************************************/
 
-BspTree::BspTree(): 
+BspTree::BspTree(ViewCell *viewCell): 
 mRoot(NULL), 
-mVerticalAxis(Vector3(0, 0, 1)),
+mViewCell(viewCell),
 //mStorePolys(true)
 mStorePolys(false)
@@ -369 +374 @@
         BspNode *firstNode = mRoot ? mRoot : new BspLeaf();
 
-        tStack.push(BspTraversalData(firstNode, polys, 0, NULL));
+        tStack.push(BspTraversalData(firstNode, polys, 0, mViewCell));
 
         while (!tStack.empty())
@@ -398 +403 @@
                                                                                 mStorePolys);
                                 
-                                // get view cell associated with the split polygon
-                                ViewCell *viewCell = (coincident.size() > 0) ? 
-                                        dynamic_cast<ViewCell *>(coincident.front()->mParent) : NULL;
+                                // extract view cells associated with the split polygons
+                                ViewCell *frontViewCell = mViewCell;
+                                ViewCell *backViewCell = mViewCell;
+        
+                                if (!viewCells)
+                                {
+                                        ExtractViewCells(&backViewCell,
+                                                                         &frontViewCell,
+                                                                         coincident, 
+                                                                         interior->mPlane, 
+                                                                         frontPolys->empty(), 
+                                                                         backPolys->empty());
+                                }
+
+                                // don't need coincident polygons anymore
                                 interior->ProcessPolygons(&coincident, mStorePolys);
 
@@ -407 +424 @@
 
                                 // push the children on the stack
-                                tStack.push(BspTraversalData(interior->GetFront(), frontPolys, tData.mDepth + 1, NULL));
-                                tStack.push(BspTraversalData(interior->GetBack(), backPolys, tData.mDepth + 1, viewCell));
+                                tStack.push(BspTraversalData(interior->GetFront(), frontPolys, tData.mDepth + 1, frontViewCell));
+                                tStack.push(BspTraversalData(interior->GetBack(), backPolys, tData.mDepth + 1, backViewCell));
                         }
 
@@ -533 +550 @@
         std::stack<BspTraversalData> tStack;
         
-        BspTraversalData tData(new BspLeaf(), polys, 0, NULL);
+        BspTraversalData tData(new BspLeaf(), polys, 0, mViewCell);
 
         tStack.push(tData);
@@ -563 +580 @@
         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);
@@ -580 +597 @@
                 }
                 //-- add viewcell stored in split polygon
-                else if (tData.mViewCell)
+                else
                 {
                         if (leaf->GetViewCell())
@@ -586 +603 @@
 
                         //leaf->mViewCellIdx = counter; Debug << "insert view cell " << tData.mViewCell << endl;
-                        leaf->SetViewCell(dynamic_cast<ViewCell *>(tData.mViewCell));
+                        leaf->SetViewCell(tData.mViewCell);
                 }
         
@@ -608 +625 @@
                                                                                   &coincident);
 
-        // view cell associated with the first split polygon
-        ViewCell *viewCell = (coincident.size() > 0) ? 
-                                        dynamic_cast<ViewCell *>(coincident.front()->mParent) : NULL;
+        //-- extract view cells from coincident polygons according to plane normal
+        ViewCell *frontViewCell = mViewCell;
+        ViewCell *backViewCell = mViewCell;
+        
+    if (!viewCells)
+        {
+                ExtractViewCells(&backViewCell,
+                                                 &frontViewCell,
+                                                 coincident, 
+                                                 interior->mPlane, 
+                                                 frontPolys->empty(), 
+                                                 backPolys->empty());
+        }
+    
+        // don't need coincident polygons anymore
         interior->ProcessPolygons(&coincident, mStorePolys);
 
         // push the children on the stack
         // split polygon is only needed in the back leaf
-        tStack.push(BspTraversalData(interior->GetFront(), frontPolys, tData.mDepth + 1, NULL));
-        tStack.push(BspTraversalData(interior->GetBack(), backPolys, tData.mDepth + 1, viewCell));
+        tStack.push(BspTraversalData(interior->GetFront(), frontPolys, tData.mDepth + 1, frontViewCell));
+        tStack.push(BspTraversalData(interior->GetBack(), backPolys, tData.mDepth + 1, backViewCell));
 
         // cleanup
@@ -625 +654 @@
 }
 
+void BspTree::ExtractViewCells(ViewCell **backViewCell, 
+                                                           ViewCell **frontViewCell,
+                                                           const PolygonContainer &coincident,
+                                                           const Plane3 splitPlane, 
+                                                           const bool extractFront, 
+                                                           const bool extractBack) const
+{
+        bool foundFront = !extractFront, foundBack = !extractBack;
+
+        PolygonContainer::const_iterator it, it_end = coincident.end();
+
+        for (it = coincident.begin(); !(foundFront && foundBack) && 
+                (it < coincident.end()); ++it)
+        {
+                if (DotProd((*it)->GetSupportingPlane().mNormal, splitPlane.mNormal > 0))
+                {
+                        *backViewCell = dynamic_cast<ViewCell *>((*it)->mParent);
+                        foundBack = true;
+                }
+                else
+                {
+                        *frontViewCell = dynamic_cast<ViewCell *>((*it)->mParent);
+                        foundFront = true;
+                }
+        }
+}
 
 BspInterior *BspTree::SubdivideNode(BspLeaf *leaf, 
@@ -671 +726 @@
         }
 
-        // simple strategy: just take next polygon
-        if (sSplitPlaneStrategy & NEXT_POLYGON)
-        {
-                return polys.front()->GetSupportingPlane();
-        }
-        
-        if (sSplitPlaneStrategy & AXIS_ALIGNED)
+        if ((sSplitPlaneStrategy & AXIS_ALIGNED) &&
+                ((int)polys.size() > sTermMaxPolysForAxisAligned))
         {
                 AxisAlignedBox3 box;
                 box.Initialize();
         
+                // todo: area subdivision
                 Polygon3::IncludeInBox(polys, box);
         
@@ -690 +741 @@
 
                 return Plane3(norm, pt);
+        }
+
+        // simplest strategy: just take next polygon
+        if (sSplitPlaneStrategy & NEXT_POLYGON)
+        {
+                return polys.front()->GetSupportingPlane();
         }
 
@@ -729 +786 @@
                 }
         }
-        //Debug << "Plane lowest cost: " << lowestCost << endl;
+        Debug << "Plane lowest cost: " << lowestCost << endl;
         
         return polys[bestPlaneIdx]->GetSupportingPlane();
@@ -741 +798 @@
 float BspTree::EvalSplitPlane(const PolygonContainer &polys, const Plane3 &candidatePlane) const
 {
-        float sumBalanced = 0, sumLeastSplits = 0, verticalAxis = 0;
+        float sumBalancedPolys = 0;
+        float sumBalancedViewCells = 0;
+        float sumLeastSplits = 0;
+        float verticalAxis = 0;
         
         if (sSplitPlaneStrategy & VERTICAL_AXIS)
         {
-                Vector3 thinAxis(0,0,0); thinAxis[mBox.size().ThinAxis()] = 1.0f;
-                // want to minimize this dot product
-                verticalAxis = DotProd(candidatePlane.mNormal, thinAxis);
-                
-        //drivingAxis = (candidatePlane.mNormal.DrivingAxis() == mBox.Size().DrivingAxis()) ? 99.0f : 0.0f;
-        }
-        if ((sSplitPlaneStrategy & BALANCED_TREE) || (sSplitPlaneStrategy & LEAST_SPLITS))
+                Vector3 tinyAxis(0,0,0); tinyAxis[mBox.Size().TinyAxis()] = 1.0f;
+                // want to put a penalty on the dot product between the "tiny" vertical axis
+                // and the split plane axis
+                verticalAxis = fabs(DotProd(candidatePlane.mNormal, tinyAxis)) * (float)polys.size();
+        }
+        //-- strategies where the effect of the split plane on the polygons is tested
+        if ((sSplitPlaneStrategy & BALANCED_POLYS)      || 
+                (sSplitPlaneStrategy & LEAST_SPLITS)        ||
+                (sSplitPlaneStrategy & LARGEST_POLY_AREA))
         {
                 PolygonContainer::const_iterator it, it_end = polys.end();
@@ -759 +821 @@
                         int classification = (*it)->ClassifyPlane(candidatePlane);
 
-                        if (sSplitPlaneStrategy & BALANCED_TREE)
-                                sumBalanced += sBalancedTreeTable[classification];
-        
+                        if (sSplitPlaneStrategy & BALANCED_POLYS)
+                                sumBalancedPolys += sBalancedPolysTable[classification];
+                                
                         if (sSplitPlaneStrategy & LEAST_SPLITS)
                                 sumLeastSplits += sLeastSplitsTable[classification];
                 }
         }
+        
+        if (sSplitPlaneStrategy & BALANCED_VIEW_CELLS)
+        {
+                // store view cells
+                ObjectContainer frontViewCells;
+                ObjectContainer backViewCells;
+
+                PolygonContainer::const_iterator it, it_end = polys.end();
+                
+                for (it = polys.begin(); it != it_end; ++ it)
+                {
+                        int classification = (*it)->ClassifyPlane(candidatePlane);
+                        Intersectable *viewCell = (*it)->mParent;
+                        
+                        if (viewCell && (classification == Polygon3::FRONT_SIDE))
+                                frontViewCells.push_back(viewCell);
+                        else if (viewCell && (classification == Polygon3::BACK_SIDE))
+                                backViewCells.push_back(viewCell);
+                }
+
+                // count number of unique view cells
+                sort(frontViewCells.begin(), frontViewCells.end());
+                sort(backViewCells.begin(), backViewCells.end());
+
+                ObjectContainer::const_iterator frontIt, frontIt_end = frontViewCells.end();
+                
+                Intersectable *intersect = NULL;
+                // increase counter for view cells in front of plane
+        for (frontIt = frontViewCells.begin(); frontIt != frontIt_end; ++frontIt)
+                {
+                        if (*frontIt != intersect)
+                        {
+                                intersect = *frontIt;
+                                sumBalancedViewCells += 1;
+                        }
+                }
+
+                ObjectContainer::const_iterator backIt, backIt_end = backViewCells.end();
+                intersect = NULL;
+                // decrease counter for view cells on back side of plane
+        for (backIt = backViewCells.begin(); backIt != backIt_end; ++backIt)
+                {
+                        if (*backIt != intersect)
+                        {
+                                intersect = *backIt;
+                                sumBalancedViewCells -= 1;
+                        }
+                }
+        }
 
         // return linear combination of the sums
-        return sBalancedFactor * fabs(sumBalanced) + sLeastSplitsFactor * sumLeastSplits + sVerticalFactor * dotProd;
+        return sBalancedPolysFactor * fabs(sumBalancedPolys) + 
+                   sBalancedViewCellsFactor * fabs(sumBalancedViewCells) +
+                   sLeastSplitsFactor * sumLeastSplits + 
+                   sVerticalSplitsFactor * verticalAxis;
 }
 
@@ -775 +889 @@
         environment->GetIntValue("BspTree.Termination.maxDepth", sTermMaxDepth);
         environment->GetIntValue("BspTree.Termination.maxPolygons", sTermMaxPolygons);
+        environment->GetIntValue("BspTree.Termination.maxPolysForAxisAligned", 
+                                                         sTermMaxPolysForAxisAligned);
         environment->GetIntValue("BspTree.maxCandidates", sMaxCandidates);
         environment->GetIntValue("BspTree.splitPlaneStrategy", sSplitPlaneStrategy);
 
-        Debug << "BSP max depth: " << sTermMaxDepth << endl;
+    Debug << "BSP max depth: " << sTermMaxDepth << endl;
         Debug << "BSP max polys: " << sTermMaxPolygons << endl;
         Debug << "BSP max candidates: " << sMaxCandidates << endl;
+        
+        Debug << "Split plane strategy: ";
+        if (sSplitPlaneStrategy & NEXT_POLYGON)
+                Debug << "next polygon ";
+        if (sSplitPlaneStrategy & AXIS_ALIGNED)
+                Debug << "axis aligned ";
+        if (sSplitPlaneStrategy & LEAST_SPLITS)     
+                Debug << "least splits ";
+        if (sSplitPlaneStrategy & BALANCED_POLYS)
+                Debug << "balanced polygons ";
+        if (sSplitPlaneStrategy & BALANCED_VIEW_CELLS)
+                Debug << "balanced view cells ";
+        if (sSplitPlaneStrategy & LARGEST_POLY_AREA)
+                Debug << "largest polygon area ";
+        if (sSplitPlaneStrategy & VERTICAL_AXIS)
+                Debug << "vertical axis ";
+
+        Debug << endl;
 
         //-- parse BSP tree construction method

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.h

@@ -162 +162 @@
 class BspInterior : public BspNode 
 {
+        friend BspTree;
 public:
         /** Standard contructor taking split plane as argument.
@@ -275 +276 @@
 
         /** Default constructor creating an empty tree.
+                @param viewCell view cell corresponding to unbounded space
         */ 
-        BspTree();
+        BspTree(ViewCell *viewCell);
 
         ~BspTree();
@@ -427 +429 @@
         inline int GetNextCandidateIdx(const int max) const;
 
+        /** Helper function which extracts a view cell on the front and the back
+                of the split plane.
+                @param backViewCell returns view cell on the back of the split plane
+                @param frontViewCell returns a view cell on the front of the split plane
+                @param coincident container of polygons coincident to the split plane
+                @param splitPlane the split plane which decides about back and front
+                @param extractFront if a front view cell is extracted
+                @param extractBack if a back view cell is extracted
+        */
+        void ExtractViewCells(ViewCell **backViewCell, 
+                                                  ViewCell **frontViewCell,
+                                                  const PolygonContainer &coincident,
+                                                  const Plane3 splitPlane, 
+                                                  const bool extractFront, 
+                                                  const bool extractBack) const;
+        
         /// Pointer to the root of the tree
         BspNode *mRoot;
@@ -436 +454 @@
 
         /// Strategies for choosing next split plane.
-        enum {NEXT_POLYGON = 0, 
-                  LEAST_SPLITS = 2, 
-                  BALANCED_TREE = 4, 
-                  VERTICAL_AXIS = 8, 
-                  AXIS_ALIGNED = 16};
+        enum {NO_STRATEGY = 0,
+                  NEXT_POLYGON = 1, 
+                  AXIS_ALIGNED = 2,
+                  LEAST_SPLITS = 4, 
+                  BALANCED_POLYS = 8,
+                  BALANCED_VIEW_CELLS = 16,
+                  LARGEST_POLY_AREA = 32,
+                  VERTICAL_AXIS = 64
+                };
 
         /// box around the whole view domain
@@ -448 +470 @@
         bool mStorePolys;
 
-        /// vertical axis of scene
-        Vector3 mVerticalAxis;
+        /// view cell corresponding to unbounded space
+        ViewCell *mViewCell;
 
 public:
@@ -465 +487 @@
         /// BSP tree construction method
         static int sConstructionMethod;
-
+        /// maximal number of polygons where we do axis aligned splits
+        static int sTermMaxPolysForAxisAligned;
+
+        // factors to guid the split plane heuristics
         static float sLeastSplitsFactor;
-        static float sBalancedTreeFactor;
-        static float sVerticalFactor;
-
+        static float sBalancedPolysFactor;
+        static float sBalancedViewCellsFactor;
+        static float sVerticalSplitsFactor;
+        
 private:
         /** Evaluates split plane classification with respect to the plane's 
@@ -478 +504 @@
                 contribution for a minimum number splits in the tree.
         */
-        static float sBalancedTreeTable[4];
+        static float sBalancedPolysTable[4];
 };
 

trunk/VUT/GtpVisibilityPreprocessor/src/main.cpp

@@ -47 +47 @@
                   p->GenerateViewCells();
 
-         Debug << "Viewcells loaded / generated. Number of view cells: " << p->mViewCells.size() << endl;
+         Debug << "Viewcells loaded / generated. Number of view cells: " << (int)p->mViewCells.size() << endl;
   }