Changeset 234

Timestamp:

08/10/05 18:07:51 (19 years ago)

Author:

mattausch

Message:

added bsp tree stuff

Files:

• branches/VUT/0.3/scripts/GtpVisibility.suo (modified) (previous)
• tags/VUT/0.3/scripts/GtpVisibility.suo (modified) (previous)
• trunk/VUT/GtpVisibilityPreprocessor/scripts/Preprocessor.vcproj (modified) (1 diff)
• trunk/VUT/GtpVisibilityPreprocessor/src/Preprocessor.cpp (modified) (3 diffs)
• trunk/VUT/GtpVisibilityPreprocessor/src/Preprocessor.h (modified) (3 diffs)
• trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp (modified) (8 diffs)
• trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.h (modified) (3 diffs)
• trunk/VUT/GtpVisibilityPreprocessor/src/main.cpp (modified) (1 diff)
• trunk/VUT/scripts/GtpVisibility.suo (modified) (previous)

trunk/VUT/GtpVisibilityPreprocessor/scripts/Preprocessor.vcproj

@@ -63 +63 @@
                                 Name="VCCLCompilerTool"
                                 AdditionalIncludeDirectories="..\support;..\support\devil\include;..\support\zlib\include;"$(QTDIR)\include";"$(QTDIR)\include\Qt";..\include"
-                                PreprocessorDefinitions="WIN32;NDEBUG;_LIB"
+                                PreprocessorDefinitions="WIN32;NDEBUG;_LIB;DEST_BSP_VIEWCELLS"
                                 RuntimeLibrary="2"
                                 RuntimeTypeInfo="TRUE"

trunk/VUT/GtpVisibilityPreprocessor/src/Preprocessor.cpp

@@ -18 +18 @@
 Preprocessor::GenerateViewcells()
 {
+        ObjectContainer objects;
+        mSceneGraph->CollectObjects(&objects);
+        //mBspTree = new BspTree(objects);
   
-  return true;
+        return true;
 }
 
@@ -60 +63 @@
 }
 
+bool
+Preprocessor::BuildBspTree()
+{
+  
+  return true;
+}
+
+
 
 void
@@ -67 +78 @@
 }
 
+void
+Preprocessor::BspTreeStatistics(ostream &s)
+{
+//  s<<mBspTree->GetStatistics();
+}
 
 bool

trunk/VUT/GtpVisibilityPreprocessor/src/Preprocessor.h

@@ -60 +60 @@
   virtual bool BuildKdTree();
   
+   /** Build the BSP tree of currently loaded occluders/occludees/viewcells. The construction
+      is driven by the environment settings, which also sais which of the three types of
+      entities should be used to drive the heuristical construction (only occluders by default)
+  */
+  virtual bool BuildBspTree();
+
   /** Compute visibility method. This method has to be reimplemented by the actual
       Preprocessor implementation (e.g. SamplingPreprocessor, ExactPreprocessor,
@@ -75 +81 @@
   
   virtual void KdTreeStatistics(ostream &s);
-  
+  virtual void BspTreeStatistics(ostream &s);
+
   /// scene graph loaded from file
   SceneGraph *mSceneGraph;
@@ -90 +97 @@
   ViewCellContainer mViewcells;
   
-  
+  BspTree * mBspTree;
   
 };

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp

@@ -247 +247 @@
 
 BspTree::BspTree(const ViewCellContainer &viewCells): 
-mMaxPolys(0), mMaxDepth(0), mRoot(NULL)
+mMaxPolys(0), mMaxDepth(999999), mRoot(NULL) // null => until we stripped all polygons
 {
         //mRootCell = cell;
@@ -298 +298 @@
         CopyMesh2Polygon(viewCell->GetMesh(), polys);
 
-        tStack.push(BspTraversalData(mRoot, NULL, &polys, 0, viewCell));
+        tStack.push(BspTraversalData(mRoot, NULL, &polys, 0));
 
         while (!tStack.empty())
@@ -318 +318 @@
 
                         // push the children on the stack
-                        if (frontPolys->size() > 0)
+                        if (frontPolys->size() > 0) // if polygons on this side of bsp tree
                                 tStack.push(BspTraversalData(interior->GetFront(), interior->GetParent(), frontPolys, tData.mDepth + 1));
                         else
                                 delete frontPolys;
 
-                        if (backPolys > 0)
-                                tStack.push(BspTraversalData(interior->GetBack(), interior->GetParent(), backPolys, tData.mDepth + 1)); // TODO: really need to keep viewcell??
+                        if (backPolys > 0) // if polygons on this side of bsp tree
+                                tStack.push(BspTraversalData(interior->GetBack(), interior->GetParent(), backPolys, tData.mDepth + 1));
                         else
                                 delete backPolys;
@@ -330 +330 @@
                 else // reached leaf and must split
                 {
-                        BuildTree(tStack, tData);
-                }
-        }
-/*      BspNode *currentNode = mRoot;
-  
-        std::stack<BspTraversalData> tStack;
-        //  stack<STraversalData> tStack;
-
-        //tStack.push(tdata);
-
-        while (!tStack.empty()) 
-        {
-            BspTraversalData data = tStack.top();
-
-            tStack.pop();
-    
-                Mesh backPolys;
-                Mesh frontPolys;
-
-                if (data.mNode->IsLeaf()) // if we have a leaf => subdivide
-                {
-                        BspNode *node = SubdivideNode(dynamic_cast<BspLeaf *>(data.mNode),
-                                                                                  data.mParent,
-                                                                                  data.mPolys,
-                                                                              data.mDepth,
-                                                                                  data.viewCell,
-                                                                                  backPolys,
-                                                                                  frontPolys);
-        
-                        if (!node->IsLeaf()) // node was subdivided
-                        {
-                                BspInterior *interior = dynamic_cast<BspInterior *>(node);
-
-                                // push the children on the stack (there are always two children)
-                                //tStack.push(BspTraversalData(interior->GetBack(), interior, backPolys, data.mDepth + 1));
-                                //tStack.push(BspTraversalData(interior->GetFront(), interior, frontPolys, data.mDepth + 1));
-                        }
-                }
-        }*/
+                        BuildTree(tStack, tData, NULL);
+                }
+        }
 }
 
@@ -415 +379 @@
         Copy2PolygonSoup(objects, *polys);
 
-        BspTraversalData tData(mRoot, mRoot->GetParent(), polys, 0, NULL);
+        BspTraversalData tData(mRoot, mRoot->GetParent(), polys, 0);
         tStack.push(tData);
 
@@ -428 +392 @@
 }
 
-void BspTree::BuildTree(BspTraversalStack &tStack, BspTraversalData &currentData)
+void BspTree::BuildTree(BspTraversalStack &tStack, BspTraversalData &currentData, ViewCell *viewCell)
 {
         PolygonQueue *backPolys = new PolygonQueue();
@@ -437 +401 @@
                                                                   currentData.mPolys,
                                                                   currentData.mDepth,
-                                                                  currentData.mViewCell,
+                                                                  viewCell,
                                                                   backPolys,
                                                                   frontPolys);
@@ -446 +410 @@
 
                 // push the children on the stack (there are always two children)
-                tStack.push(BspTraversalData(interior->GetBack(), interior, backPolys, currentData.mDepth + 1, NULL));
-                tStack.push(BspTraversalData(interior->GetFront(), interior, frontPolys, currentData.mDepth + 1, currentData.mViewCell));
+                tStack.push(BspTraversalData(interior->GetBack(), interior, backPolys, currentData.mDepth + 1));
+                tStack.push(BspTraversalData(interior->GetFront(), interior, frontPolys, currentData.mDepth + 1));
         }
 }

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.h

@@ -17 +17 @@
 
 typedef std::queue<Polygon *> PolygonQueue;
+
+class BspTreeStatistics // TODO: should have common superclass with KdTreeStatistics
+{
+public:
+  // total number of nodes
+  int nodes;
+  // totals number of rays
+  int rays;
+  // total number of query domains
+  int queryDomains;
+  // total number of ray references
+  int rayRefs;
+  // refs in non empty leafs
+  int rayRefsNonZeroQuery;
+  // total number of query references
+  int objectRefs;
+  // nodes with zero queries
+  int zeroQueryNodes;
+  // max depth nodes
+  int maxDepthNodes;
+  // max number of rays per node
+  int maxObjectRefs;
+  // number of dynamically added ray refs
+  int addedRayRefs;
+  // number of dynamically removed ray refs
+  int removedRayRefs;
+  
+  // Constructor
+  BspTreeStatistics() 
+  {
+    Reset();
+  }
+
+  int Nodes() const {return nodes;}
+  int Interior() const { return nodes/2; }
+  int Leaves() const { return (nodes/2) + 1; }
+
+  void Reset() 
+  {
+          nodes = 0;
+
+          rays = queryDomains = 0;
+          rayRefs = rayRefsNonZeroQuery = objectRefs = 0;
+          zeroQueryNodes = 0;
+      maxDepthNodes = 0;
+      //minCostNodes = 0;
+          maxObjectRefs = 0;
+          addedRayRefs = removedRayRefs = 0;
+  }
+
+  void
+  Print(ostream &app) const;
+
+  friend ostream &operator<<(ostream &s, const BspTreeStatistics &stat) {
+    stat.Print(s);
+    return s;
+  }
+  
+};
 
 /**
@@ -179 +238 @@
         /** Builds a new extension of the tree.
         */
-        void BuildTree(BspTraversalStack &tStack, BspTraversalData &currentData);
+        void BuildTree(BspTraversalStack &tStack, BspTraversalData &currentData, ViewCell *viewCell = NULL);
 
         /** Selects a splitting plane from the given polygons. 
@@ -232 +291 @@
         /// maximal depth
         int mMaxDepth;
+
+        BspTreeStatistics mStat;
 };
 

trunk/VUT/GtpVisibilityPreprocessor/src/main.cpp

@@ -30 +30 @@
   p->KdTreeStatistics(cout);
 
+#ifdef DEST_BSP_VIEWCELLS
+  p->GenerateViewcells();
+  p->BspTreeStatistics(cout);
+#endif
+
   //  p->mSceneGraph->Export("soda.x3d");
   if (0) {