Changeset 294

Timestamp:

09/20/05 02:39:50 (19 years ago)

Author:

mattausch

Message:

vertical splitr criterium

Location:

trunk/VUT/GtpVisibilityPreprocessor

Files:

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

trunk/VUT/GtpVisibilityPreprocessor/scripts/default.env

@@ -65 +65 @@
 
 BspTree {
-#       splitPlaneStrategy leastSplits
-        splitPlaneStrategy balancedTree
-#       splitPlaneStrategy nextPolygon
-#       splitPlaneStrategy combined
+        splitPlaneStrategy 14
 #       constructionMethod rays
         constructionMethod viewCells

trunk/VUT/GtpVisibilityPreprocessor/src/Polygon3.cpp

@@ -61 +61 @@
                                 //-- plane - line intersection
                                 Vector3 splitPt = partition->FindIntersection(ptA, ptB);
-                                Debug << "fpg " << splitPt << " side " << partition->Side(splitPt, SIDE_TOLERANCE) << 
-                                        "\nptA " << ptA << " side " << sideA << "\nptB " << ptB << " side " << sideB << " " << Distance(ptB, splitPt) << endl;
+                        
                                 if (!foundSplit || (SqrDistance(splitPt, prevSplitPt) > SIDE_TOLERANCE_SQRD))
                                 {
@@ -81 +80 @@
                                 //-- plane - line intersection
                                 Vector3 splitPt = partition->FindIntersection(ptA, ptB);
-                        //      if (foundSplit) Debug << "back split pt " << splitPt << " prev " << prevSplitPt << endl;
+                        
                                 if (!foundSplit || (SqrDistance(splitPt, prevSplitPt) > SIDE_TOLERANCE_SQRD))
                                 {
-                                        //Debug << "add back split vertex " << splitPt << endl;
                                         // add vertex to both polygons
                                         front->mVertices.push_back(splitPt);
@@ -91 +89 @@
                                         foundSplit = true;
                                         prevSplitPt = splitPt;
-                                }//else Debug << "reject back split vertex " << splitPt << endl;        
+                                }       
                         }
                         back->mVertices.push_back(ptB);
@@ -125 +123 @@
         bool onFrontSide = false;
         bool onBackSide = false;
+        // threshold for coincident classification
+        const float dot_thres = 0.99f;
 
         int count = 0;
@@ -131 +131 @@
         {
                 int side = plane.Side(*it, SIDE_TOLERANCE);
-                //Debug << "side: " << side << " " << plane.Distance(*it) << endl;
-
+                
                 if (side > 0)
                         onFrontSide = true;
@@ -147 +146 @@
                 {
                         // Decide if plane and surface normal are same
-                        if (DotProd(plane.mNormal, GetSupportingPlane().mNormal) > 0.99)
+                        if (DotProd(plane.mNormal, GetSupportingPlane().mNormal) > dot_thres)
                                 return COINCIDENT; // plane and polygon are coincident
                         else 
@@ -164 +163 @@
 
         // Decide if plane and surface normal are same
-        if (DotProd(plane.mNormal, GetSupportingPlane().mNormal) > float(1.0 - 1.0e-5))
+        if (DotProd(plane.mNormal, GetSupportingPlane().mNormal) > dot_thres)
                 return COINCIDENT; // plane and polygon are coincident
         else 

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp

@@ -13 +13 @@
 #include "Exporter.h"
 
-#define INITIAL_COST 999999// unreachable high initial cost for heuristic evaluation
-
 int BspTree::sTermMaxPolygons = 10;
 int BspTree::sTermMaxDepth = 20;
@@ -24 +22 @@
         contribution for a balanced tree.
 */
-int BspTree::sLeastSplitsTable[4] = {0, 0, 1, 0};
+float BspTree::sLeastSplitsTable[] = {0, 0, 1, 0};
 /** Evaluates split plane classification with respect to the plane's 
         contribution for a minimum number splits in the tree.
 */
-int BspTree::sBalancedTreeTable[4] = {-1, 1, 0, 0};
-
-const int FACTOR_BALANCE = 1;
-const int FACTOR_LEAST_SPLITS = 1;
+float BspTree::sBalancedTreeTable[] = {-1, 1, 0, 0};
 
 //int counter = 0;
-//bool BspTree::displayDebug = false;
+
 /****************************************************************/
 /*                  class BspNode implementation                */
@@ -151 +146 @@
         Polygon3 *splitPoly = NULL;
 #ifdef _Debug
-        Debug << "Splitting polygons of node " << this << " with plane " << mPlane << endl;
+        Debug << "splitting polygons of node " << this << " with plane " << mPlane << endl;
 #endif
         while (!polys->empty())
@@ -183 +178 @@
                                 front_piece = new Polygon3(poly->mParent);
                                 back_piece = new Polygon3(poly->mParent);
-Debug << "*************\n";
-Debug << "initial poly\n" << *poly << endl;
+
                                 //-- split polygon into front and back part
                                 poly->Split(&mPlane, front_piece, back_piece);
 
                                 ++ splits; // increase number of splits
-                        
-                                if (front_piece->mVertices.size() >= 3) // check if polygon still valid 
+                                // check if polygon still valid 
+                                if (front_piece->mVertices.size() >= 3)
                                         frontPolys->push_back(front_piece);
-                                else{
-                                        Debug << "poly\n" << *poly << "split front piece not valid\n" << *front_piece << endl;
-                                        DEL_PTR(front_piece);}
+                                else
+                                        DEL_PTR(front_piece);
+                                // check if polygon still valid
+                                if (back_piece->mVertices.size() >= 3)
+                                        backPolys->push_back(back_piece);
+                                else                            
+                                        DEL_PTR(back_piece);
                                 
-                                if (back_piece->mVertices.size() >= 3) // check if polygon still valid
-                                        backPolys->push_back(back_piece);
-                                else{
-                                        Debug << "poly\n" << *poly << "split back piece not valid\n" << *back_piece << endl;
-                                        DEL_PTR(back_piece);}
-                                
-Debug << "*************\n";
 #ifdef _DEBUG
                                 Debug << "split " << *poly << endl << *front_piece << endl << *back_piece << endl;
@@ -214 +205 @@
                 }
         }
-        //Debug << "inside: " << inside << endl;
 }
 
@@ -258 +248 @@
 mTermMaxDepth(0), 
 mRoot(NULL), 
+mVerticalAxis(Vector3(0, 0, 1)),
 //mStorePolys(true)
 mStorePolys(false)
@@ -570 +561 @@
 
         Debug << "**** Finished tree construction ****\n";
-        Debug << "BSP tree contruction time: "<< TimeDiff(startTime, GetTime())*1e-3 << "s" << endl;
+        Debug << "BSP tree contruction time: " << TimeDiff(startTime, GetTime())*1e-3 << "s" << endl;
 }
 
@@ -594 +585 @@
                         leaf->SetViewCell(viewCell);
                         viewCells->push_back(viewCell);
-                        Debug << "creating new viewcell" << endl;
+                        // Debug << "creating new viewcell" << endl;
                 }
                 //-- add viewcell stored in split polygon
@@ -602 +593 @@
                                 Debug << "ERROR: leaf already has view cell " << endl;//leaf->mViewCellIdx << endl;
 
-                        //leaf->mViewCellIdx = counter;
-                        Debug << "insert view cell " << tData.mViewCell << endl;
-
+                        //leaf->mViewCellIdx = counter; Debug << "insert view cell " << tData.mViewCell << endl;
                         leaf->SetViewCell(dynamic_cast<ViewCell *>(tData.mViewCell));
                 }
@@ -627 +616 @@
                                                                                   &coincident);
 
-        if ((backPolys->size() == 0) && (coincident.size() > 1)) 
-        {
-                Debug << "WARNING: size " << (int)coincident.size() << " at depth " << tData.mDepth << ", #back polys: " << (int)backPolys->size() << ", #front polys: " << (int)frontPolys->size() << endl;
-                for (int i=0; i<coincident.size(); ++i)
-                        Debug << "coincident poly " << i << ", vc: " << coincident[i]->mParent << "\n" << *coincident[i] << 
-                        "dotprod: " << DotProd(coincident[i]->GetSupportingPlane().mNormal, interior->GetPlane()->mNormal) << endl;
-        }
-        //Debug << "coincident size: " << coincident.size() << endl;
-
-        // get view cell associated with the first split polygon
+        // view cell associated with the first split polygon
         ViewCell *viewCell = (coincident.size() > 0) ? 
                                         dynamic_cast<ViewCell *>(coincident.front()->mParent) : NULL;
@@ -700 +680 @@
 
         // simple strategy: just take next polygon
-        if (sSplitPlaneStrategy == NEXT_POLYGON)
+        if (sSplitPlaneStrategy & NEXT_POLYGON)
         {
                 return polys->front()->GetSupportingPlane();
         }
         
+    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);
@@ -711 +702 @@
 Plane3 BspTree::SelectPlaneHeuristics(PolygonContainer *polygons, int maxTests) const
 {
-        int lowestCost = INITIAL_COST;
+        float lowestCost = MAX_FLOAT;
         int bestPlaneIdx = 0;
         
@@ -718 +709 @@
         for (int i = 0; i < limit; ++ i)
         {
-                int candidateIdx = Random((int)polygons->size()); // TODO:  avoid testing same plane 2 times
+                int candidateIdx = Random((int)polygons->size()); // TODO: avoid testing same plane 2 times
                 Plane3 candidatePlane = (*polygons)[candidateIdx]->GetSupportingPlane();
                 
                 // evaluate current candidate
-                int candidateCost = EvalSplitPlane(polygons, candidatePlane);
+                float candidateCost = EvalSplitPlane(polygons, candidatePlane);
                         
                 if (candidateCost < lowestCost)
@@ -728 +719 @@
                         bestPlaneIdx = candidateIdx;
                         lowestCost = candidateCost;
-                        //Debug << "new plane cost " << lowestCost << endl;
                 }
         }
@@ -736 +726 @@
 }
 
-int BspTree::EvalSplitPlane(PolygonContainer *polygons, const Plane3 &candidatePlane) const
+float BspTree::EvalSplitPlane(PolygonContainer *polygons, const Plane3 &candidatePlane) const
 {
         PolygonContainer::const_iterator it;
 
-        int sumBalanced = 0, sumLeastSplits = 0;
+        float sumBalanced = 0, sumLeastSplits = 0;
 
         for (it = polygons->begin(); it != polygons->end(); ++ it)
@@ -746 +736 @@
                 int classification = (*it)->ClassifyPlane(candidatePlane);
                 
-                if ((sSplitPlaneStrategy == COMBINED) || (sSplitPlaneStrategy == BALANCED_TREE))
+                if (sSplitPlaneStrategy & BALANCED_TREE)
                 {
                         sumBalanced += sBalancedTreeTable[classification];
                 }
                 
-                if ((sSplitPlaneStrategy == COMBINED) || (sSplitPlaneStrategy == LEAST_SPLITS))
+                if (sSplitPlaneStrategy & LEAST_SPLITS)
                 {
                         sumLeastSplits += sLeastSplitsTable[classification];
@@ -758 +748 @@
 
         // return linear combination of both sums
-        return FACTOR_BALANCE * abs(sumBalanced) + FACTOR_LEAST_SPLITS *abs(sumLeastSplits);
+        return fabs(sumBalanced) + fabs(sumLeastSplits);
 }
 
@@ -766 +756 @@
         environment->GetIntValue("BspTree.Termination.maxPolygons", sTermMaxPolygons);
         environment->GetIntValue("BspTree.maxCandidates", sMaxCandidates);
+        environment->GetIntValue("BspTree.splitPlaneStrategy", sSplitPlaneStrategy);
 
         Debug << "BSP max depth: " << sTermMaxDepth << endl;
         Debug << "BSP max polys: " << sTermMaxPolygons << endl;
         Debug << "BSP max candidates: " << sMaxCandidates << endl;
-
-        //-- extract strategy to choose the next split plane
-        char splitPlaneStrategyStr[60];
-
-        environment->GetStringValue("BspTree.splitPlaneStrategy", splitPlaneStrategyStr);
-        
-        sSplitPlaneStrategy = BspTree::NEXT_POLYGON;
-        
-        if (strcmp(splitPlaneStrategyStr, "nextPolygon") == 0)
-                sSplitPlaneStrategy = BspTree::NEXT_POLYGON;
-        else if (strcmp(splitPlaneStrategyStr, "leastSplits") == 0)
-                sSplitPlaneStrategy = BspTree::LEAST_SPLITS;
-        else if (strcmp(splitPlaneStrategyStr, "balancedTree") == 0)
-                sSplitPlaneStrategy = BspTree::BALANCED_TREE;
-        else if (strcmp(splitPlaneStrategyStr, "combined") == 0)
-                sSplitPlaneStrategy = BspTree::COMBINED;
-        else 
-        {
-                cerr << "Wrong BSP split plane strategy " << splitPlaneStrategyStr << endl;
-                exit(1);
-    }
-
-        Debug << "Split plane heuristic: " << splitPlaneStrategyStr << endl;
 
         //-- parse BSP tree construction method

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.h

@@ -344 +344 @@
 
         /** Evaluates the contribution of the candidate split plane.
-        */
-        int EvalSplitPlane(PolygonContainer *polygons, const Plane3 &candidatePlane) const;
+                @returns the cost of the candidate split plane
+        */
+        float EvalSplitPlane(PolygonContainer *polygons, const Plane3 &candidatePlane) const;
 
         /** Evaluates tree stats in the BSP tree leafs.
@@ -442 +443 @@
 
         /// Strategies for choosing next split plane.
-        enum {NEXT_POLYGON, LEAST_SPLITS, BALANCED_TREE, COMBINED};
+        enum {NEXT_POLYGON = 0, 
+                  LEAST_SPLITS = 2, 
+                  BALANCED_TREE = 4, 
+                  VERTICAL_AXIS = 8, 
+                  AXIS_ALIGNED = 16};
 
         /// box around the whole view domain
         AxisAlignedBox3 mBox;
 
-                /// if view cell calculation is incremential
-        bool mIsIncremential;
-
         /// if polygons should be stored in the tree
         bool mStorePolys;
 
+        /// vertical axis of scene
+        Vector3 mVerticalAxis;
 public:
         /// Parses the environment and stores the global BSP tree parameters
@@ -472 +476 @@
                 contribution for a balanced tree.
         */
-        static int sLeastSplitsTable[4];
+        static float sLeastSplitsTable[4];
         /** Evaluates split plane classification with respect to the plane's 
                 contribution for a minimum number splits in the tree.
         */
-        static int sBalancedTreeTable[4];
+        static float sBalancedTreeTable[4];
 };
 

trunk/VUT/GtpVisibilityPreprocessor/src/X3dParser.cpp

@@ -517 +517 @@
                 Mesh *mesh = mViewCells->back()->GetMesh();
 #ifdef _DEBUG
-                Debug << "Viewcell :" 
+                Debug << "Viewcell: " 
                           << mesh->mVertices[0] << " " << mesh->mVertices[1] << " " << mesh->mVertices[2] << " " 
                           << mesh->mVertices[3] << " " << mesh->mVertices[4] << " " << mesh->mVertices[5] << "\n";

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 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");
 
   ViewCellContainer::iterator vc_compl_it;
   ViewCellContainer vc_compl(p->mViewCells.size() + X3dExporter::foundViewCells.size());
-
-  Debug << "here1" << endl;
+  
   sort(p->mViewCells.begin(), p->mViewCells.end());
-  Debug << "here2.5 " << X3dExporter::foundViewCells.size() << endl;
-  
   vc_compl_it = set_difference(p->mViewCells.begin(), p->mViewCells.end(), 
                                  X3dExporter::foundViewCells.begin(), X3dExporter::foundViewCells.end(),
                                  vc_compl.begin());
-
-  Debug << "here2" << endl;
- 
   vc_compl.erase(vc_compl_it, vc_compl.end());
   
-  Debug << "Complementary view cells: " << vc_compl.size() << endl;
 
   if (exporter) 
@@ -79 +71 @@
           exporter->ExportViewCells(&vc_compl); // export view cells
           delete exporter;
-  }Debug << "here4" << endl;
+  }
 
 #endif