Changeset 239

Timestamp:

08/16/05 00:08:53 (19 years ago)

Author:

mattausch

Message:

removed debug stuff. viewcell insertion working

Location:

trunk/VUT/GtpVisibilityPreprocessor

Files:

• scripts/default.env (modified) (1 diff)
• src/Plane3.h (modified) (1 diff)
• src/Polygon3.cpp (modified) (7 diffs)
• src/ViewCell.cpp (modified) (2 diffs)
• src/ViewCell.h (modified) (1 diff)
• src/ViewCellBsp.cpp (modified) (22 diffs)
• src/ViewCellBsp.h (modified) (1 diff)

trunk/VUT/GtpVisibilityPreprocessor/scripts/default.env

@@ -62 +62 @@
         splitPlaneStrategy balancedTree
 #       splitPlaneStrategy nextPolygon
-#       constructionMethod viewCells
-        constructionMethod sceneGeometry
+        constructionMethod viewCells
+#       constructionMethod sceneGeometry
         maxCandidates 20
-        maxViewCells 100
+        maxViewCells 10
         Termination {
                 maxPolygons 4

trunk/VUT/GtpVisibilityPreprocessor/src/Plane3.h

@@ -49 +49 @@
           if (signum(dv) != 0)
           {
-                  u = - Distance(a) / dv;
-                  Debug << "t: " << u << ", b - a: " << v << ", norm: " << mNormal << ", dist(a): " << - Distance(a) << ", dv: " << dv << endl;
-                  if (coplanar) (*coplanar) = false;
+                  u = - Distance(a) / dv; // NOTE: could be done more efficiently
+                  //Debug << "t: " << u << ", b - a: " << v << ", norm: " << mNormal << ", dist(a): " << - Distance(a) << ", dv: " << dv << endl;
+                  if (coplanar) 
+                          (*coplanar) = false;
           }
-          else {
-                  if (coplanar) (*coplanar) = true;       
+          else if (coplanar) 
+          {
+                  (*coplanar) = true;     
           }
-          if (t) (*t) = u;
-          Debug << "result of intersection with A: " << a << ", B: " << b << ":\n" << (a + u * b - u * a) << "\n" << (a + u*v) << "\n\n";
-          
+
+          if (t) 
+                  (*t) = u;
+                  
           return a + u * b - u * a; // NOTE: gives better precision than calclulating a + u * v
           //return a + (u * v);

trunk/VUT/GtpVisibilityPreprocessor/src/Polygon3.cpp

@@ -14 +14 @@
         VertexIndexContainer::const_iterator it;
 
-        Debug << "Creating polygon:\n";
-
         for (it = face->mVertexIndices.begin(); it != face->mVertexIndices.end(); ++ it)
         {
@@ -25 +23 @@
 Plane3 Polygon3::GetSupportingPlane() const
 {
-        Debug << "creating plane using vertices: " << mVertices[0] << mVertices[1] << mVertices[2] << endl;
         Vector3 v1 = mVertices[0] - mVertices[1];
-                Vector3 v2 = mVertices[2] - mVertices[1];
-        Debug << "plane has vectors " <<  v1 << v2  << endl;
+        Vector3 v2 = mVertices[2] - mVertices[1];
+#ifdef _DEBUG
+        Debug << "plane spanned by " <<  v1 << ", " << v2  << endl;
+#endif
         return Plane3(mVertices[0], mVertices[1], mVertices[2]);
 }
@@ -52 +51 @@
         VertexContainer::const_iterator it;
 
-        Debug << "\n\nvertex A: " << ptA << ", side A: " << sideA << " (" << partition->Distance(ptA) << ")";
-
         // find line - plane intersections
         for (it = mVertices.begin(); it != mVertices.end(); ++ it)
@@ -59 +56 @@
                 Vector3 ptB = (*it);
                 int sideB = partition->Side(ptB, SIDE_TOLERANCE);
-                Debug << " <=> vertex B: " << ptB << ", side B: " << sideB << " (" << partition->Distance(ptB) << ")\n\n";
-
+        
                 // vertices on different sides => split
             if (sideB > 0)
@@ -71 +67 @@
                                 // add vertex to both polygons
                                 front->mVertices.push_back(splitPt);
-                                back->mVertices.push_back(splitPt); Debug << "front and back polygon + " << splitPt << endl;
+                                back->mVertices.push_back(splitPt);
                         
                                 ++ splits;
                         }
-                        front->mVertices.push_back(ptB); Debug << "front polygon + " << ptB << endl;
+                        front->mVertices.push_back(ptB);
                 }
                 else if (sideB < 0)
@@ -86 +82 @@
                                 // add vertex to both polygons
                                 front->mVertices.push_back(splitPt);
-                                back->mVertices.push_back(splitPt); Debug << "front and back polygon + " << splitPt << endl;
+                                back->mVertices.push_back(splitPt);
 
                                 ++ splits;
                         }
-                        back->mVertices.push_back(ptB); Debug << "back polygon + " << ptB << endl;
+                        back->mVertices.push_back(ptB);
                 }
                 else
@@ -96 +92 @@
                         // vertex on plane => add vertex to both polygons
                         front->mVertices.push_back(ptB);
-                        back->mVertices.push_back(ptB); Debug << "front and back polygon + " << ptB << endl;
+                        back->mVertices.push_back(ptB); 
                 }
         
                 ptA = ptB;
                 sideA = sideB;
-                Debug << "vertex A: " << ptA << ", side A: " << sideA << " (" << partition->Distance(ptA) << ")";
         }
-        Debug << "\n*********************\n";
 }
 

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCell.cpp

@@ -41 +41 @@
 float ViewCell::IntersectionComplexity() 
 {
-        return mMesh->mFaces.size();
+        return (float)mMesh->mFaces.size();
 }
 
@@ -56 +56 @@
 void ViewCell::DeriveViewCells(const ObjectContainer &objects, 
                                                            ViewCellContainer &viewCells, 
-                                                           const int max)
+                                                           const int maxViewCells)
 {
         // maximal max viewcells
-        int n = max > 0 ? std::min((int)objects.size(), max) : (int)objects.size();
+        int limit = maxViewCells > 0 ? std::min((int)objects.size(), maxViewCells) : (int)objects.size();
 
-        for (int i = 0; i < n; ++i)
+        for (int i = 0; i < limit; ++i)
         {
                 Intersectable *object = objects[i];

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCell.h

@@ -46 +46 @@
                 @param objects the intersectables the viewcells are derived from
                 @param viewCells the viewcells are returned in this container
-                @param if >0, indicates the maximim number of viewcells that will be created
+                @param maxViewCells if > 0, indicates the maximim number of viewcells that will be created
         */
         static void DeriveViewCells(const ObjectContainer &objects, 
                                                                 ViewCellContainer &viewCells, 
-                                                                const int max);
+                                                                const int maxViewCells);
 protected:
 

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp

@@ -11 +11 @@
 #include <iomanip>
 
+#define INITIAL_TEST_VAL 999999// unreachable high initial value for heuristic evaluation
+
 int BspTree::sTermMaxPolygons = 10;
 int BspTree::sTermMaxDepth = 20;
@@ -96 +98 @@
         {
                 Polygon3 *poly = polys->back();
-
                 polys->pop_back();
 
-                Debug << (*poly);
-
+                // test if split is neccessary
                 int result = poly->ClassifyPlane(mPlane);
 
@@ -109 +109 @@
                 {
                         case Polygon3::COINCIDENT:
-                                Debug << "coincident\n";
                                 break; // do nothing
                         case Polygon3::FRONT_SIDE:
-                                Debug << "front\n";
                                 frontPolys->push_back(poly);
                                 break;
                         case Polygon3::BACK_SIDE:
-                                Debug << "back\n";
                                 backPolys->push_back(poly);
                                 break;
@@ -123 +120 @@
                                 back_piece = new Polygon3();
 
-                                Debug << "\n\n**************SPLIT***************\n";
-                                Debug << "Split plane: " << mPlane << "\noriginal " << (*poly) << endl;
-
                                 //-- split polygon
                                 poly->Split(&mPlane, front_piece, back_piece, splits);
-                        
-                                Debug << "new front " << (*front_piece) << endl;
-                                Debug << "new back " << (*back_piece) << endl;
 
                                 frontPolys->push_back(front_piece);
                                 backPolys->push_back(back_piece);
                                 
+#ifdef _DEBUG
+                                Debug << "split " << poly << endl << front << endl << back << endl;
+#endif
                                 // don't need polygon anymore
                                 DEL_PTR(poly);
@@ -169 +163 @@
 /****************************************************************/
 
-BspTree::BspTree(): mTermMaxPolygons(0), mTermMaxDepth(0)
-{
-        mRoot = new BspLeaf();
+BspTree::BspTree(): mTermMaxPolygons(0), mTermMaxDepth(0), mRoot(NULL)
+{
         Randomize(); // initialise random generator for heuristics
 }
@@ -267 +260 @@
 
 void BspTree::InsertViewCell(ViewCell *viewCell)
-{
-        Debug << "Inserting view cells\n";
+{       
         std::stack<BspTraversalData> tStack;
         
@@ -275 +267 @@
         CopyMesh2Polygons(viewCell->GetMesh(), polys);
 
-        tStack.push(BspTraversalData(mRoot, NULL, &polys, 0));
+        BspNode *firstNode = mRoot ? mRoot : new BspLeaf(); // traverse tree or create new one
+
+        tStack.push(BspTraversalData(firstNode, NULL, &polys, 0));
 
         while (!tStack.empty())
@@ -283 +277 @@
 
             tStack.pop();
-        
+                                
         if (!tData.mNode->IsLeaf())
                 {
                         BspInterior *interior = dynamic_cast<BspInterior *>(tData.mNode);
 
-                        // filter polygons down the tree.
+                        //-- filter view cell polygons down the tree until a leaf is reached
                         PolygonContainer *frontPolys = new PolygonContainer();
                         PolygonContainer *backPolys = new PolygonContainer();
 
                         int splits = 0;
+                        // split viecell polygons with respect to split plane
                         interior->SplitPolygons(tData.mPolygons, frontPolys, backPolys, splits);
                         mStat.splits += splits;
@@ -309 +304 @@
                                 delete backPolys;
                 }
-                else // reached leaf => subdivide
-                {
-                        Subdivide(tStack, tData, NULL);
+                else // reached leaf => subdivide current viewcell
+                {
+                        BspNode *root = Subdivide(tStack, tData, NULL);
+
+                        if (!mRoot) // take as root if there is none yet
+                                mRoot = root;                           
                 }
         }
@@ -349 +347 @@
         ObjectContainer::const_iterator it, it_end = objects.end();
 
-        int limit = maxPolys != 0 ? min((int)objects.size(), maxPolys) : (int)objects.size();
-
-        //for (it = objects.begin(); it != it_end; ++ it)
+        int limit = (maxPolys > 0) ? min((int)objects.size(), maxPolys) : (int)objects.size();
+
         for (int i = 0; i < limit; ++i)
         {
@@ -376 +373 @@
         }
 
-        Debug << "number of polygons: " << polys.size() << endl;
+        Debug << "Number of polygons: " << polys.size() << endl;
 }
 
@@ -394 +391 @@
         Copy2PolygonSoup(objects, *polys, 100);
 
-        BspTraversalData tData(mRoot, mRoot->GetParent(), polys, 0);
+        BspTraversalData tData(new BspLeaf(), mRoot->GetParent(), polys, 0);
+
         tStack.push(tData);
 
@@ -401 +399 @@
                 tData = tStack.top();
             tStack.pop();
-                
-                Subdivide(tStack, tData);
-        }
-}
-
-void BspTree::Subdivide(BspTraversalStack &tStack, BspTraversalData &tData, ViewCell *viewCell)
-{
-        //Debug << "Subdividing node\n";
+
+                // subdivide leaf node
+                BspNode *root = Subdivide(tStack, tData);
+
+                if (!mRoot)
+                        mRoot = root;
+        }
+}
+
+BspNode * BspTree::Subdivide(BspTraversalStack &tStack, BspTraversalData &tData, ViewCell *viewCell)
+{
         PolygonContainer *backPolys = new PolygonContainer();
         PolygonContainer *frontPolys = new PolygonContainer();
-int polySize = tData.mPolygons->size();
+
         BspNode *node = SubdivideNode(dynamic_cast<BspLeaf *>(tData.mNode),
                                                                   tData.mParent,
@@ -419 +420 @@
                                                                   frontPolys,
                                                                   backPolys);
-Debug << "Level " << tData.mDepth << ", all: " << polySize << ", front: " << frontPolys->size() << ", back: " << backPolys->size() << endl;
+
         if (!node->IsLeaf()) // node was subdivided
         {
@@ -434 +435 @@
                 Polygon3::DeletePolygons(tData.mPolygons);
         }
+
+        return node;
 }
 
 Plane3 BspTree::SelectPlane(PolygonContainer *polygons)  const
 {
-        // most simple strategy: just take next polygon
+        // simple strategy: just take next polygon
         if (sSplitPlaneStrategy == NEXT_POLYGON)
         {
-                Debug << "simple plane selection\n";
                 return polygons->front()->GetSupportingPlane();
         }
@@ -450 +452 @@
 Plane3 BspTree::SelectPlaneHeuristics(PolygonContainer *polygons, int maxTests) const
 {
-        Debug << "selecting plane heuristics\n";
-
-        int bestValue = 999999;
-
+        int bestValue = INITIAL_TEST_VAL;
         Plane3 *bestPlane = NULL;
         
@@ -462 +461 @@
                 int candidateIdx = Random((int)polygons->size());
                 Plane3 candidatePlane = (*polygons)[candidateIdx]->GetSupportingPlane();
-                Debug << "choosing new candidate: " << limit << endl;
+                
                 // evaluate current candidate
                 int candidateValue = EvalSplitPlane(polygons, candidatePlane);
@@ -470 +469 @@
                         bestPlane = &candidatePlane;
                         bestValue = candidateValue;
-                        Debug << "new plane value " << bestValue << endl;
-                }
-        }
-        Debug << "%%%%%%%%%%found value: " << bestValue << endl;
+                        //Debug << "new plane value " << bestValue << endl;
+                }
+        }
                 
         return *bestPlane;
@@ -532 +530 @@
         if ((polys->size() <= mTermMaxPolygons) || (depth >= mTermMaxDepth))
         {
-                // Debug << polys->size() << ", " << depth << endl;             
                 return leaf;
         }
@@ -540 +537 @@
         // add the new nodes to the tree + select subdivision plane
         BspInterior *node = new BspInterior(SelectPlane(polys)); 
-        Debug << "new bspinterior: " << (*node) << endl;
+
+#ifdef _DEBUG
+        Debug << node << endl;
+#endif
         // split polygon according to current plane
         int splits = 0;
@@ -546 +546 @@
         
         node->SplitPolygons(polys, frontPolys, backPolys, splits);
-        Debug << "$$ " << polySize << " " << frontPolys->size() << " " << backPolys->size() << endl; 
+        
         mStat.splits += splits;
 
@@ -595 +595 @@
 void BspTree::EvaluateLeafStats(const BspTraversalData &data)
 {
-  // the node became a leaf -> evaluate stats for leafs
-  BspLeaf *leaf = dynamic_cast<BspLeaf *>(data.mNode);
-
-  Debug << "evaluating leaf stats\n";
-
-  if (data.mDepth >= mTermMaxDepth)
-  {
-          ++ mStat.maxDepthNodes; 
-  }
-
-  // record maximal depth
-  if (data.mDepth > mStat.maxDepth)
-          mStat.maxDepth = data.mDepth;
-
-  Debug << "BSP Traversal data. Depth: " << data.mDepth << " (max: " << mTermMaxDepth<< "), #polygons: " << 
+        // the node became a leaf -> evaluate stats for leafs
+        BspLeaf *leaf = dynamic_cast<BspLeaf *>(data.mNode);
+
+        if (data.mDepth >= mTermMaxDepth)
+        {
+                ++ mStat.maxDepthNodes;
+        }
+
+        // record maximal depth
+        if (data.mDepth > mStat.maxDepth)
+                mStat.maxDepth = data.mDepth;
+
+#ifdef _DEBUG
+        Debug << "BSP Traversal data. Depth: " << data.mDepth << " (max: " << mTermMaxDepth<< "), #polygons: " << 
           data.mPolygons->size() << " (max: " << mTermMaxPolygons << ")" << endl;
+#endif
 }
 //} // GtpVisibilityPreprocessor

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.h

@@ -254 +254 @@
                 @param tData traversal data also holding node to be subdivided
                 @param viewCell the view cell that will be represented with this part of the Bsp tree.
-        */
-        void Subdivide(BspTraversalStack &tStack, BspTraversalData &tData, ViewCell *viewCell = NULL);
+                @returns new root of the subtree
+        */
+        BspNode *Subdivide(BspTraversalStack &tStack, BspTraversalData &tData, ViewCell *viewCell = NULL);
 
         /** Selects a splitting plane.