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

Timestamp:

09/13/05 18:31:48 (19 years ago)

Author:

mattausch

Message:

did bsp stuff

File:

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

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp

@@ -17 +17 @@
 int BspTree::sTermMaxPolygons = 10;
 int BspTree::sTermMaxDepth = 20;
+int BspTree::sMaxCandidates = 10;
 int BspTree::sSplitPlaneStrategy = NEXT_POLYGON; 
-int BspTree::sMaxCandidates = 10;
 int BspTree::sConstructionMethod = VIEW_CELLS;
 
@@ -30 +30 @@
 int BspTree::sBalancedTreeTable[4] = {-1, 1, 0, 0};
 
-int counter = 0;
 /****************************************************************/
 /*                  class BspNode implementation                */
@@ -36 +35 @@
 
 BspNode::BspNode(): mParent(NULL), mPolygons(NULL)
-{
-}
+{}
 
 BspNode::BspNode(BspInterior *parent): mParent(parent), mPolygons(NULL)
@@ -50 +48 @@
         }
 }
+
 bool BspNode::IsRoot() const 
 {
@@ -145 +144 @@
                                                                 int &splits, bool storePolys)
 {
-#ifdef _Debug
+//#ifdef _Debug
         Debug << "Splitting polygons of node " << this << " with plane " << mPlane << endl;
-#endif
+//#endif
         bool inside = false;
 
@@ -156 +155 @@
 
                 // test if split is neccessary
-                int result = poly->ClassifyPlane(mPlane);
-
+                int classification = poly->ClassifyPlane(mPlane);
+
+                //Debug << "polygon plane: " << poly->GetSupportingPlane() << endl;
                 Polygon3 *front_piece = NULL;
                 Polygon3 *back_piece = NULL;
                 
-                switch (result)
+                switch (classification)
                 {
                         case Polygon3::COINCIDENT:
@@ -169 +169 @@
                                         inside = (DotProd(mPlane.mNormal, poly->GetSupportingPlane().mNormal) > 0);
                                         
-                                //Debug << "coincident" << endl;
+                                Debug << "coincident" << endl;
                                 // discard polygons or saves them in node
                                 ProcessPolygon(poly, storePolys);
                                 break;
                         case Polygon3::FRONT_SIDE:
-                                //Debug << "front" << endl;
+                                Debug << "front" << endl;
                                 frontPolys->push_back(poly);
                                 break;
                         case Polygon3::BACK_SIDE:
                                 inside = true;
-                                //Debug << "back" << endl;
+                                Debug << "back" << endl;
                                 backPolys->push_back(poly);
                                 break;
                         case Polygon3::SPLIT:
                                 inside = true;
-                                //Debug << "split" << endl;
+                                Debug << "split " << poly << endl;
 
                                 front_piece = new Polygon3();
@@ -279 +279 @@
         app << "#N_NODES ( Number of nodes )\n" << nodes << "\n";
 
+        app << "#N_LEAVES ( Number of interior nodes )\n" << Interior() << "\n";
+
         app << "#N_LEAVES ( Number of leaves )\n" << Leaves() << "\n";
 
-        app << "#N_SPLITS ( Number of splits)\n" << splits << "\n";
+        app << "#N_SPLITS ( Number of splits )\n" << splits << "\n";
 
         app << "#N_RAYREFS ( Number of rayRefs )\n" <<
@@ -307 +309 @@
         maxDepthNodes * 100 / (double)Leaves() << endl;
 
-        app << "#N_PMAXDEPTH ( Maximal reached depth )\n" << maxDepth <<endl;
-
-        app << "#N_ADDED_RAYREFS  (Number of dynamically added ray references )\n"<<
-        addedRayRefs<<endl;
-
-        app << "#N_REMOVED_RAYREFS  (Number of dynamically removed ray references )\n"<<
-        removedRayRefs<<endl;
-
-        //  app << setprecision(4);
-
-        //  app << "#N_CTIME  ( Construction time [s] )\n"
-        //      << Time() << " \n";
-
+        app << "#N_PMAXDEPTH ( Maximal reached depth )\n" << maxDepth << endl;
+
+        app << "#N_PMINDEPTH ( Minimal reached depth )\n" << minDepth << endl;
+
+        app << "#AVGEPTH ( average depth )\n" << AvgDepth() << endl;
+
+        app << "#N_ADDED_RAYREFS  ( Number of dynamically added ray references )\n"<<
+        addedRayRefs << endl;
+
+        app << "#N_REMOVED_RAYREFS  ( Number of dynamically removed ray references )\n" <<
+        removedRayRefs << endl;
+
+        app << "#N_INPUT_POLYGONS (number of input polygons )\n" <<
+                polys << endl;
+
+        app << "#N_ROUTPUT_INPUT_POLYGONS ( ratio polygons after subdivision / input polygons )\n" <<
+                 (polys + splits) / (double)polys << endl;
+        
         app << "===== END OF BspTree statistics ==========\n";
 }
@@ -356 +363 @@
 
         // extract polygons that guide the split process
-        AddMesh2Polygons(viewCell->GetMesh(), *polys);
+        mStat.polys += AddMesh2Polygons(viewCell->GetMesh(), *polys);
         mBox.Include(viewCell->GetBox()); // add to BSP aabb
 
@@ -382 +389 @@
                                 int splits = 0;
                 
+                                Debug << "Splitting poly, YEAHH\n";
                                 // split viecell polygons with respect to split plane
                                 bool inside = interior->SplitPolygons(tData.mPolygons, frontPolys, backPolys, splits, mStorePolys);
@@ -399 +407 @@
                 else // reached leaf => subdivide current viewcell
                 {
+                        if (tData.mPolygons->size() > 0)
+                                Debug << "WARNING (should not come here): polygon size: " << tData.mPolygons->size() << " inside: " << tData.mIsInside  << endl;
+
                         BspNode *root = Subdivide(tStack, tData, viewCell);             
 
-            // tree empty => new root
-                        if (!mRoot)
+                        //if (!root->IsLeaf())
+                        //      Debug << "WARNING should NOT have subdivided further\n";
+         
+                        if (!mRoot) // tree empty => new root
                                 mRoot = root;
                 }
         }
-        Debug << "ended traversal" << endl; Debug.flush();
 }
 
@@ -420 +432 @@
 
 
-void BspTree::AddMesh2Polygons(Mesh *mesh, PolygonContainer &polys)
+int BspTree::AddMesh2Polygons(Mesh *mesh, PolygonContainer &polys)
 {
         FaceContainer::const_iterator fi;
-        
+        int polysNum = 0;
+
         // copy the face data to polygons
         for (fi = mesh->mFaces.begin(); fi != mesh->mFaces.end(); ++ fi)
@@ -429 +442 @@
                 Polygon3 *poly = new Polygon3((*fi), mesh);
                 polys.push_back(poly);
-        }
-}
-
-void BspTree::Copy2PolygonSoup(const ViewCellContainer &viewCells, PolygonContainer &polys, int maxObjects)
+                polysNum ++;
+        }
+        return polysNum;
+}
+
+int BspTree::Copy2PolygonSoup(const ViewCellContainer &viewCells, PolygonContainer &polys, int maxObjects)
 {
         int limit = (maxObjects > 0) ? Min((int)viewCells.size(), maxObjects) : (int)viewCells.size();
@@ -444 +459 @@
                 }
         }
-}
-
-void BspTree::Copy2PolygonSoup(const ObjectContainer &objects, PolygonContainer &polys, int maxObjects)
+
+        return (int)polys.size();
+}
+
+int BspTree::Copy2PolygonSoup(const ObjectContainer &objects, PolygonContainer &polys, int maxObjects)
 {
         int limit = (maxObjects > 0) ? Min((int)objects.size(), maxObjects) : (int)objects.size();
@@ -475 +492 @@
         }
 
-        Debug << "Number of polygons: " << (int)polys.size() << ", BSP root box: " << mBox << endl;
+        return (int)polys.size();
 }
 
@@ -511 +528 @@
 
         mStorePolys = savedStorePolys;
-
-        counter = 0;
-
-        Debug << "\n**** Started view cells insertion ****\n\n";
+        mStat.polys = 0;
+        mStat.splits = 0;
+        //int counter = 0;
+        
+        long startTime = GetTime();
+        Debug << "**** Starting view cell insertion ****" << endl;
         for (it = viewCells.begin(); it != viewCells.end(); ++ it)
         {
-                Debug << "*** Inserting view cell " << counter << " ***" << endl;
+                //Debug << "*** Inserting view cell " << counter ++ << " ***" << endl;
                 InsertViewCell(*it);
-                counter ++;
-        }
-        Debug << "**** finished view cells insertion ****" << endl; Debug.flush();
+        }
+        Debug << "**** Finished view cell insertion ****" << endl;
+        Debug << "insertion time: "<< TimeDiff(startTime, GetTime())*1e-3 << "s" << endl;
 }
 
@@ -533 +552 @@
         
         // copy mesh instance polygons into one big polygon soup
-        Copy2PolygonSoup(objects, *polys, sMaxCandidates);
+        mStat.polys = Copy2PolygonSoup(objects, *polys, sMaxCandidates);
 
         // construct tree from polygon soup
@@ -546 +565 @@
 }
 
-void BspTree::Construct(PolygonContainer *polys)
+void BspTree::Construct(PolygonContainer *polys, ViewCellContainer *viewCells)
 {
         std::stack<BspTraversalData> tStack;
@@ -554 +573 @@
         tStack.push(tData);
 
+        long startTime = GetTime();
         Debug << "**** Contructing tree using objects ****\n";
         while (!tStack.empty()) 
@@ -559 +579 @@
                 tData = tStack.top();
             tStack.pop();
-        
+
+                ViewCell *viewCell = NULL;
+
+        if (viewCells) // generate new view cell in leaf
+                {
+                        viewCell = new ViewCell();
+                        viewCells->push_back(viewCell);
+                }
+
                 // subdivide leaf node
-                BspNode *root = Subdivide(tStack, tData);
+                BspNode *root = Subdivide(tStack, tData, viewCell);
 
                 // empty tree => new root corresponding to unbounded space
@@ -568 +596 @@
         }
 
-        Debug << "**** tree construction finished ****\n";
+        Debug << "**** Finished tree construction ****\n";
+        Debug << "BSP tree contruction time: "<< TimeDiff(startTime, GetTime())*1e-3 << "s" << endl;
 }
 
@@ -576 +605 @@
 {
         //-- terminate traversal  
-        if (((tData.mPolygons->size() <= mTermMaxPolygons) || (tData.mDepth >= mTermMaxDepth))
+        if ((tData.mPolygons->size() <= mTermMaxPolygons) || (tData.mDepth >= mTermMaxDepth))
                 // if there is another view cell associated with this leaf => subdivide further
-                && !(viewCell && tData.mIsInside && dynamic_cast<BspLeaf *>(tData.mNode)->GetViewCell()))
+                //&& !(viewCell && tData.mIsInside && dynamic_cast<BspLeaf *>(tData.mNode)->GetViewCell()))  
         {
 #ifdef _DEBUG
-        Debug << "terminate subdivision, size " << (int)tData.mPolygons->size() << ", depth " << tData.mDepth << endl;
+                Debug << "subdivision terminated at depth " << tData.mDepth << ", #polys: " << (int)tData.mPolygons->size() << endl;
 #endif
 
@@ -587 +616 @@
 
             // add view cell if inside object) 
-                if (viewCell && tData.mIsInside) 
-                        // || (tData.mGeometry->size() > 0) // or if there is still geometry left 
+                if (viewCell && tData.mIsInside) // || (tData.mGeometry->size() > 0) // or if there is still geometry left 
                 {
                         BspLeaf *leaf = dynamic_cast<BspLeaf *>(tData.mNode);
 
-#ifdef _DEBUG
                         if (leaf->GetViewCell())
                                 Debug << "ERROR: leaf already has view cell" << endl;
 
-                        Debug << "**** Inserted view cell ****" << endl;
-#endif
                         leaf->SetViewCell(viewCell);
                 }
@@ -613 +638 @@
         bool inside = false;
 
+        Debug << "Subdividing node at depth " << tData.mDepth << endl;
         BspInterior *interior = SubdivideNode(dynamic_cast<BspLeaf *>(tData.mNode),
                                                                                   tData.mPolygons,
@@ -618 +644 @@
                                                                                   backPolys, inside);
 
-        // push the children on the stack (there are always two children)
+        // push the children on the stack
+        // inside information is only propagated with the back leaf
         tStack.push(BspTraversalData(interior->GetBack(), backPolys, tData.mDepth + 1, inside));
         tStack.push(BspTraversalData(interior->GetFront(), frontPolys, tData.mDepth + 1, false));
@@ -657 +684 @@
 
         // and setup child links
-        interior->SetupChildLinks(new BspLeaf(interior, leaf->mViewCell), new BspLeaf(interior));
+        //interior->SetupChildLinks(new BspLeaf(interior), new BspLeaf(interior, leaf->mViewCell));
+        interior->SetupChildLinks(new BspLeaf(interior), new BspLeaf(interior));
         
         delete leaf; // leaf not member of tree anymore
@@ -685 +713 @@
 {
         int lowestCost = INITIAL_COST;
-        Plane3 *bestPlane = NULL;
+        int bestPlaneIdx = 0;
         
         int limit = Min((int)polygons->size(), maxTests);
 
-        for (int i = 0; i < limit; ++i)
-        {
-                int candidateIdx = Random((int)polygons->size());
+        for (int i = 0; i < limit; ++ i)
+        {
+                int candidateIdx = Random((int)polygons->size()); // TODO:  avoid testing same plane 2 times
                 Plane3 candidatePlane = (*polygons)[candidateIdx]->GetSupportingPlane();
                 
@@ -699 +727 @@
                 if (candidateCost < lowestCost)
                 {
-                        bestPlane = &candidatePlane;
+                        bestPlaneIdx = candidateIdx;
                         lowestCost = candidateCost;
                         //Debug << "new plane cost " << lowestCost << endl;
                 }
         }
-                
-        return *bestPlane;
+        
+        if (lowestCost > 0)
+                Debug << "Split plane cost: " << lowestCost << " plane: " << (*polygons)[bestPlaneIdx]->GetSupportingPlane() << endl;
+        else
+                Debug << "no splits for plane: " << (*polygons)[bestPlaneIdx]->GetSupportingPlane() << endl;
+        return (*polygons)[bestPlaneIdx]->GetSupportingPlane();
 }
 
@@ -712 +744 @@
         PolygonContainer::const_iterator it;
 
-        int sum = 0, sum2 = 0;
-
-        for (it = polygons->begin(); it < polygons->end(); ++ it)
+        int sumBalanced = 0, sumLeastSplits = 0;
+
+        for (it = polygons->begin(); it != polygons->end(); ++ it)
         {
                 int classification = (*it)->ClassifyPlane(candidatePlane);
@@ -720 +752 @@
                 if ((sSplitPlaneStrategy == COMBINED) || (sSplitPlaneStrategy == BALANCED_TREE))
                 {
-                        sum += sBalancedTreeTable[classification];
+                        sumBalanced += sBalancedTreeTable[classification];
                 }
                 
-                if ((sSplitPlaneStrategy == COMBINED) ||(sSplitPlaneStrategy == LEAST_SPLITS))
-                {
-                        sum2 += sLeastSplitsTable[classification];
-                }
-        }
+                if ((sSplitPlaneStrategy == COMBINED) || (sSplitPlaneStrategy == LEAST_SPLITS))
+                {
+                        sumLeastSplits += sLeastSplitsTable[classification];
+                        Debug << "Adding " <<  sLeastSplitsTable[classification] << " for poly " << *it << "!";
+                }
+        }
+
+        Debug << "\n" << candidatePlane << " evaluation: " << abs(sumBalanced) + abs(sumLeastSplits) << endl;
 
         // return linear combination of both sums
-        return abs(sum) + abs(sum2);
+        return abs(sumBalanced) + abs(sumLeastSplits);
 }
 
@@ -738 +773 @@
         environment->GetIntValue("BspTree.Termination.maxPolygons", sTermMaxPolygons);
         environment->GetIntValue("BspTree.maxCandidates", sMaxCandidates);
+
+        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
@@ -758 +797 @@
     }
 
+        Debug << "Split plane heuristic: " << splitPlaneStrategyStr << endl;
+
         //-- parse BSP tree construction method
-        char constructionMethodStr[64];
+        char constructionMethodStr[60];
         
         environment->GetStringValue("BspTree.constructionMethod", constructionMethodStr);
@@ -777 +818 @@
     }
 
+        Debug << "Construction method: " << constructionMethodStr << endl;
 }
 
@@ -879 +921 @@
         }
 
-        // store maximal depth
+        // store maximal and minimal depth
         if (data.mDepth > mStat.maxDepth)
                 mStat.maxDepth = data.mDepth;
+        if (data.mDepth < mStat.minDepth)
+                mStat.minDepth = data.mDepth;
+
+        mStat.accumDepth += data.mDepth;
+
+        if (leaf->mViewCell)
+                ++ mStat.viewCellLeaves;
 
 #ifdef _DEBUG
-        Debug << "BSP Traversal data. Depth: " << data.mDepth << " (max: " << mTermMaxDepth<< "), #polygons: " << 
+        Debug << "BSP Traversal data. Depth: " << data.mDepth << " (max: " << mTermMaxDepth << "), #polygons: " << 
           data.mPolygons->size() << " (max: " << mTermMaxPolygons << ")" << endl;
 #endif