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

Timestamp:

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

Author:

mattausch

Message:

added bsp split plane criteria

File:

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

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