Changeset 195 for trunk

Timestamp:

08/04/05 19:53:48 (19 years ago)

Author:

mattausch

Message:

added bsp tree stuff

Location:

trunk/VUT/GtpVisibilityPreprocessor/src

Files:

• ViewCellBSP.h (modified) (4 diffs)
• ViewCellBsp.cpp (modified) (5 diffs)

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBSP.h

@@ -2 +2 @@
 #define _ViewCellBsp_H__
 
+#include "Mesh.h"
 class ViewCell;
 class Plane3;
-class Mesh;
+//class Mesh;
 
 //namespace GtpVisibilityPreprocessor {
@@ -10 +11 @@
 class BSPInterior;
 
-/**
-        BSPNode abstract class serving for interior and leaf node implementation
-*/
-class BSPNode 
-{
-public:
-        /** Determines whether this node is a leaf or not
-        @return true if leaf
-    */
-    virtual bool IsLeaf() const = 0;
+
+  /**
+     BSPNode abstract class serving for interior and leaf node implementation
+  */
+  class BSPNode 
+  {
+  public:
+          /** Determines whether this node is a leaf or not
+          @return true if leaf
+          */
+          virtual bool IsLeaf() const = 0;
     
-    /** Determines whether this node is a root
-        @return true if root
-    */
-    virtual bool IsRoot() const;
+          /** Determines whether this node is a root
+          @return true if root
+          */
+          virtual bool IsRoot() const;
 
-        protected:
+  protected:
 
-                void SplitPoly(Plane3 *plane, Mesh *viewcell);
-
-    /// parent of this node
-    BSPInterior *mParent;
+          /// parent of this node
+          BSPInterior *mParent;
   };
 
   /** BSP interior node implementation */
   class BSPInterior : public BSPNode 
-  {    
-    /** @return false since it is an interior node */
-    bool IsLeaf() const;
+  {   
+  public:
+          /** @return false since it is an interior node */
+          bool IsLeaf() const;
+
+          BSPNode *GetBack() {return mBack;}
+          BSPNode *GetFront() {return mFront;}
+
+          void ReplaceChildLink(BSPNode *oldChild, BSPNode *newChild);
+          void SetupChildLinks(BSPNode *b, BSPNode *f);
 
   protected:
-    /// Splitting plane corresponding to this node
-    Plane3 mPlane;
-    /// back node
-    BSPNode *mBack;
-    /// front node
-    BSPNode *mFront;
+                
+          /// Splitting plane corresponding to this node
+          Plane3 mPlane;
+          /// back node
+          BSPNode *mBack;
+          /// front node
+          BSPNode *mFront;
   };
   
@@ -54 +62 @@
   {
   public:
-        BSPLeaf(ViewCell *viewCell = NULL);
+          BSPLeaf(ViewCell *viewCell = NULL);
     
-        /** @return true since it is an interior node */
-    bool IsLeaf() const;
+          /** @return true since it is an interior node */
+          bool IsLeaf() const;
 
   protected:
-    /// polygonal representation of this viewcell
-    /// if NULL this note does not correspond to feasible viewcell
-    ViewCell *mViewCell;
+   
+          /// polygonal representation of this viewcell
+          /// if NULL this note does not correspond to feasible viewcell
+          ViewCell *mViewCell;
   };
   
@@ -69 +78 @@
   {
   public:
-    /** Constructor takes a pointer to the cell corresponding to the whole
-        viewspace */
-    BSPTree(ViewCell *cell);
+          struct BSPTraversalData
+          {  
+                  BSPNode *mNode;
+                  BSPInterior *mParent;
+
+                  Mesh mViewCell;
+                  int mDepth;
+                      
+                  BSPTraversalData() {}
+                  BSPTraversalData(BSPNode *n, BSPInterior *p, const Mesh &m, const int d): 
+                  mNode(n), mParent(p), mViewCell(m), mDepth(d) {}
+      };
+         
+          /** Constructor takes a pointer to the cell corresponding to the whole
+          viewspace */
+          BSPTree(ViewCell *cell);
         
   protected:
-    /// Pointer to the root of the tree
-    BSPNode *mRoot;
-    /// Pointer to the root cell of the viewspace */
-        ViewCell *mRootCell;
+           
+          Plane3 *SelectPlane(Mesh *viewcell);
+           void Subdivide();
+           
+           BSPNode *SubdivideNode(BSPLeaf *leaf, BSPInterior *parent, 
+                                                         Mesh *viewCell, const int depth, 
+                                                         Mesh &frontPolys, Mesh &backPolys);
+
+          /// Pointer to the root of the tree
+          BSPNode *mRoot;
+          /// Pointer to the root cell of the viewspace
+          ViewCell *mRootCell;
   };
   

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp

@@ -3 +3 @@
 #include "Mesh.h"
 
-class ViewCell;
-
+#include "ViewCell.h"
+#include <stack>
 //namespace GtpVisibilityPreprocessor {
-
+/****************************************************************/
+/*                  class BSPNode implementation                */
+/****************************************************************/
 bool BSPNode::IsRoot() const 
 {
@@ -12 +14 @@
 }
 
-void BSPNode::SplitPoly(Plane3 *plane, Mesh *viewcell)
-{
-}
+/****************************************************************/
+/*              class BSPInterior implementation                */
+/****************************************************************/
 
 bool BSPInterior::IsLeaf() const
@@ -20 +22 @@
         return false; 
 }
+
+void BSPInterior::ReplaceChildLink(BSPNode *oldChild, BSPNode *newChild) 
+{
+        if (mBack == oldChild)
+        {
+                mBack = newChild;
+        }
+    else
+        {
+                mFront = newChild;
+        }
+}
+
+void BSPInterior::SetupChildLinks(BSPNode *b, BSPNode *f) 
+{
+    mBack = b;
+    mFront = f;
+}
+
+/****************************************************************/
+/*                  class BSPLeaf implementation                */
+/****************************************************************/
 
 BSPLeaf::BSPLeaf(ViewCell *viewCell): mViewCell(viewCell) 
@@ -30 +54 @@
 }
 
+/****************************************************************/
+/*                  class BSPTree implementation                */
+/****************************************************************/
+
 BSPTree::BSPTree(ViewCell *cell) 
 {
@@ -36 +64 @@
 }
 
+  
+void BSPTree::Subdivide()
+{
+        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;
+
+                BSPNode *node = SubdivideNode(dynamic_cast<BSPLeaf *>(data.mNode),
+                                                                      data.mParent,
+                                                                          data.mDepth,
+                                                                          backPolys,
+                                                                          frontPolys);
+        
+                if (!node->IsLeaf())
+                {
+                        BSPInterior *interior = dynamic_cast<BSPInterior *>(node);
+
+                        // push the children on the stack
+                        if (interior->GetBack())
+                                tStack.push(BSPTraversalData(interior->GetBack(), interior, backPolys, data.mDepth+1));
+                        if (interior->GetFront())
+                                tStack.push(BSPTraversalData(interior->GetFront(), interior, frontPolys, data.mDepth+1));
+                }
+        }
+}
+
+Plane3 *BSPTree::SelectPlane(Mesh *viewcell)
+{
+        return viewcell->GetFacePlane(0);
+}
+
+BSPNode *BSPTree::SubdivideNode(BSPLeaf *leaf, BSPInterior *parent, 
+                                                                Mesh *viewCell, const int depth, 
+                                                                Mesh &frontPolys, Mesh &backPolys)
+{
+static int sMaxDepth = 5; // HACK
+        // terminate traversal if no more faces in mesh
+        if ((viewCell->mFaces.size() == 0) && depth > sMaxDepth)
+                return leaf;
+ 
+        // add the new nodes to the tree
+        BSPInterior *node = new BSPInterior;
+  
+        // select subdivision plane
+        node->mPlane = SelectPlane(viewCell);
+
+        FaceContainer::const_iterator fi;
+
+        for ( fi = viewCell->mFaces.begin(); fi != viewCell->mFaces.end(); ++ fi)
+        {
+        }
+  
+        BSPLeaf *back = new BSPLeaf(mRootCell);
+        BSPLeaf *front = new BSPLeaf(mRootCell);
+
+        // replace a link from node's parent
+        if (parent)
+        {
+                parent->ReplaceChildLink(leaf, node);
+        }
+
+        // and setup child links
+        node->SetupChildLinks(back, front);
+  
+        delete leaf;
+        return node;
+}
+
 //} // GtpVisibilityPreprocessor