Changeset 224 for trunk

Timestamp:

08/09/05 18:39:28 (19 years ago)

Author:

mattausch

Message:

added stuff for bsp tree

Location:

trunk/VUT/GtpVisibilityPreprocessor/src

Files:

• Intersectable.h (modified) (1 diff)
• ViewCell.h (modified) (3 diffs)
• ViewCellBsp.cpp (modified) (10 diffs)
• ViewCellBsp.h (modified) (7 diffs)

trunk/VUT/GtpVisibilityPreprocessor/src/Intersectable.h

@@ -13 +13 @@
   KdPvs mKdPvs;
   
-  enum { MESH_INSTANCE, TRANSFORMED_MESH_INSTANCE, SPHERE };
+  enum { MESH_INSTANCE, TRANSFORMED_MESH_INSTANCE, SPHERE, VIEWCELL };
   
   Intersectable():mailbox(0) {}

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCell.h

@@ -1 +1 @@
 #ifndef _ViewCell_H__
 #define _ViewCell_H__
+
+#include "Intersectable.h"
 
 class Mesh;
@@ -11 +13 @@
         View cell represented as a mesh
 */
-class ViewCell
+class ViewCell: public Intersectable
 {
 public:
@@ -28 +30 @@
         BspPvs *GetPVS() {return mPvs;}
 
+        AxisAlignedBox3 GetBox()  {return mMesh->mBox;}
+  
+        int CastRay(Ray &ray) {return 0;}
+  
+        bool IsConvex() {return mMesh->mIsConvex;}
+        bool IsWatertight() {return mMesh->mIsWatertight;}
+        float IntersectionComplexity() {return mMesh->mFaces.size();}
+
+        int Type() const { return VIEWCELL; }
+
+        void GetRandomSurfacePoint(Vector3 &point, Vector3 &normal) {point = Vector3(0,0,0);};
+
 protected:
 

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp

@@ -6 +6 @@
 #include <stack>
 
+#define DEL_PTR(ptr) while (0) {if (ptr) {delete (ptr); (ptr) = NULL;}}
+
 //namespace GtpVisibilityPreprocessor {
 /****************************************************************/
@@ -15 +17 @@
 }
 
+BspInterior *BspNode::GetParent() 
+{ 
+        return mParent; 
+}
 /****************************************************************/
 /*              class BspInterior implementation                */
@@ -61 +67 @@
 }
 
-
 /****************************************************************/
 /*                  class BspLeaf implementation                */
@@ -84 +89 @@
 /****************************************************************/
 
-BspTree::BspTree(ViewCell *cell) 
-{
-        mRootCell = cell;
-        mRoot = new BspLeaf(mRootCell);
-}
-
-  
-void BspTree::Subdivide()
+BspTree::BspTree(const ViewCellContainer &viewCells): 
+mMaxPolys(0), mMaxDepth(0), mRoot(NULL)
+{
+        //mRootCell = cell;
+        Subdivide(viewCells);
+}
+
+BspTree::BspTree(const ObjectContainer &objects, int maxPolys, int maxDepth):
+mMaxPolys(maxPolys), mMaxDepth(maxDepth)
+{
+        mRoot = new BspLeaf();
+
+        Subdivide(objects);
+}
+ 
+BspTree::~BspTree()
+{
+        std::stack<BspNode *> tStack;
+
+        tStack.push(mRoot);
+
+        while (!tStack.empty())
+        {
+                BspNode *node = tStack.top();
+
+            tStack.pop();
+        
+                if (!node->IsLeaf())
+                {
+                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
+
+                        // push the children on the stack (there are always two children)
+                        interior->GetBack()->mParent = NULL;
+                        interior->GetFront()->mParent = NULL;
+
+                        tStack.push(interior->GetBack());
+                        tStack.push(interior->GetFront());
+                }
+
+                delete node;
+                node = NULL;
+        }
+}
+
+
+void BspTree::InsertViewCell(ViewCell *viewCell)
 {
         BspNode *currentNode = mRoot;
@@ -103 +146 @@
         {
             BspTraversalData data = tStack.top();
+
             tStack.pop();
     
@@ -112 +156 @@
                         BspNode *node = SubdivideNode(dynamic_cast<BspLeaf *>(data.mNode),
                                                                                   data.mParent,
-                                                                                  &data.mViewCell,
+                                                                                  data.mPolys,
                                                                               data.mDepth,
                                                                                   backPolys,
@@ -122 +166 @@
 
                                 // 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));
+                                //tStack.push(BspTraversalData(interior->GetBack(), interior, backPolys, data.mDepth + 1));
+                                //tStack.push(BspTraversalData(interior->GetFront(), interior, frontPolys, data.mDepth + 1));
                         }
                 }
@@ -129 +173 @@
 }
 
-Plane3 BspTree::SelectPlane(Mesh *polys)
+void BspTree::Subdivide(const ViewCellContainer &viewCells)
+{
+}
+
+void BspTree::Copy2PolygonSoup(const ObjectContainer &objects, Mesh &mesh)
+{
+        ObjectContainer::const_iterator it, it_end = objects.end();
+
+        for (it = objects.begin(); it != it_end; ++ it)
+        {
+                FaceContainer::const_iterator fi;
+                Intersectable *object = *it;
+
+                // extract the mesh instances
+                if (object->Type() == Intersectable::MESH_INSTANCE)
+                {
+                        MeshInstance *inst = dynamic_cast<MeshInstance *>(object);
+
+                        Mesh *polys = inst->GetMesh();
+
+                        // copy the face data
+                        for (fi = polys->mFaces.begin(); fi != polys->mFaces.end(); ++ fi)
+                        {
+                                Face *face = new Face((*fi)->mVertexIndices);
+                                mesh.AddFace(face);
+                        }
+                }
+        }
+}
+
+void BspTree::Subdivide(const ObjectContainer &objects)
+{
+        std::stack<BspTraversalData> tStack;
+        Mesh polys;
+        
+        // copy mesh instance polygons into one big polygon soup
+        Copy2PolygonSoup(objects, polys);
+
+        BspTraversalData tdata(mRoot, mRoot->GetParent(), &polys, 0);
+        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.mPolys,
+                                                                      data.mDepth,
+                                                                          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));
+                }
+        }
+}
+
+Plane3 BspTree::SelectPlane(Mesh *polys) 
 {
         // TODO: more sophisticated criteria
@@ -136 +248 @@
 
 BspNode *BspTree::SubdivideNode(BspLeaf *leaf, BspInterior *parent, 
-                                                                Mesh *viewCell, const int depth, 
+                                                                Mesh *polys, const int depth, 
                                                                 Mesh &frontPolys, Mesh &backPolys)
 {
-        ViewCell *viewCell = leaf->GetViewCell();
-
-        // terminate traversal if no more faces in mesh or outside
-        if (!viewCell || (viewCell->mFaces.size() == 0))
-        {
+        // terminate traversal if no more faces in mesh
+        if ((polys->mFaces.size() <= mMaxPolys) || (depth >= mMaxDepth))
+        {
+                // don't need to store polygon information
+                polys->mFaces->clear(); // HACK: faces were deleted before
+                DEL_PTR(polys); // we can savely delete mesh
+
                 return leaf;
         }
+
         // add the new nodes to the tree + select subdivision plane
-        BspInterior *node = new BspInterior(SelectPlane(viewCell)); 
+        BspInterior *node = new BspInterior(SelectPlane(polys)); 
 
         FaceContainer::const_iterator fi;
 
-        for (fi = viewCell->mFaces.begin(); fi != viewCell->mFaces.end(); ++ fi)
-        {
-                int  result = node->GetPlane()->Side();
-                Mesh *front_piece, *back_piece;
+        for (fi = polys->mFaces.begin(); fi != polys->mFaces.end(); ++ fi)
+        {
+                Face *face = (*fi);
+
+                int  result = 0;// = node->GetPlane()->Side(node->GetPlane());
+
+                Face *front_piece, *back_piece;
 
                 switch (result)
                 {
                         case 1:
-                                frontPolys.AddFace(poly);
+                                frontPolys.AddFace(face);
                                 break;
                         case -1:
-                                backPolys.AddFace(poly);
+                                backPolys.AddFace(face);
                                 break;
                         case 0:
-                                //Split_Polygon (poly, tree->partition, front_piece, back_piece);
+                                //Split_Polygon (face, tree->partition, front_piece, back_piece);
                                 backPolys.AddFace(back_piece);
                                 frontPolys.AddFace(front_piece);
+
+                                // face not needed anymore
+                                DEL_PTR(face);
+
                                 break;
-                        default;
-                                brak;
-                }
-        }
+                        default:
+                                break;
+                }
+        }
+
         // backside of convex view cell polygon => outside
-        BspLeaf *back = new BspLeaf(NULL);
-        BspLeaf *front = new BspLeaf(viewCell);
+        BspLeaf *back = new BspLeaf();
+        BspLeaf *front = new BspLeaf();
 
         // replace a link from node's parent
@@ -185 +308 @@
         // and setup child links
         node->SetupChildLinks(back, front);
-  
-        delete leaf;
+
+        // don't need to store polygon information
+        polys->mFaces->clear(); // HACK: faces were deleted before
+        DEL_PTR(polys); // we can savely delete mesh
+
+        DEL_PTR(leaf);
+
         return node;
 }

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.h

@@ -3 +3 @@
 
 #include "Mesh.h"
+#include "Containers.h"
+
+
 class ViewCell;
 class Plane3;
@@ -8 +11 @@
 
 //namespace GtpVisibilityPreprocessor {
-  
+class BspTree;  
 class BspInterior;
 
@@ -17 +20 @@
   class BspNode 
   {
+          friend BspTree;
+
   public:
           /** Determines whether this node is a leaf or not
@@ -28 +33 @@
           virtual bool IsRoot() const;
 
+          /** Returns parent node.
+          */
+          BspInterior *GetParent();
+          
   protected:
 
@@ -34 +43 @@
   };
 
-  /** BSP interior node implementation */
+  /** BSP interior node implementation 
+  */
   class BspInterior : public BspNode 
-  {   
+  {
   public:
-          BspInterior(Plane3 plane): mPlane(plane) {}
-          /** @return false since it is an interior node */
+          /** Standard contructor taking split plane as argument.
+          */
+          BspInterior(Plane3 plane);
+          /** @return false since it is an interior node 
+          */
           bool IsLeaf() const;
 
-          BspNode *GetBack() {return mBack;}
-          BspNode *GetFront() {return mFront;}
+          BspNode *GetBack();
+          BspNode *GetFront();
 
           Plane3 *GetPlane();
@@ -78 +91 @@
   };
   
-  /** Implementation of the ViewCell BSP tree */
+  /** Implementation of the ViewCell BSP tree. */
   class BspTree 
   {
@@ -84 +97 @@
           struct BspTraversalData
           {  
+                  /// the current node
                   BspNode *mNode;
+                  /// parent of current node
                   BspInterior *mParent;
-
-                  Mesh mViewCell;
+                  /// polygonal data for splitting
+                  Mesh *mPolys;
+                  /// current depth
                   int mDepth;
                       
                   BspTraversalData() {}
-                  BspTraversalData(BspNode *n, BspInterior *p, const Mesh &m, const int d): 
-                  mNode(n), mParent(p), mViewCell(m), mDepth(d) {}
+                  
+                  BspTraversalData(BspNode *node, BspInterior *parent, Mesh *polys, const int depth): 
+                  mNode(node), mParent(parent), mPolys(polys), mDepth(depth) {}
       };
          
-          /** Constructor takes a pointer to the cell corresponding to the whole
-          viewspace */
-          BspTree(ViewCell *cell);
-        
+          /** Constructs BSP tree from list of view cells.
+          */ 
+          BspTree(const ViewCellContainer &viewCells);
+          /** Constructs BSP tree from list of objects.
+                  @param object list of intersectables
+                  @param maxPolys maximal allowed number of polygons
+                  @param maxDepth maximal allowed BSP tree depth
+          */
+          BspTree(const ObjectContainer &objects, int maxPolys, int maxDepth);
+  
+          ~BspTree();
+
   protected:
-          /** Selects a splitting plane from the given polygons. */
+          /** Selects a splitting plane from the given polygons. 
+          */
           Plane3 SelectPlane(Mesh *polys);
 
-          void Subdivide();
+          /** Filters next viewcell down the tree and inserts it into the appropriate leaves
+                  (i.e., possibly more than one leaf).
+          */
+          void InsertViewCell(ViewCell *viewCell);
+
+          /** Subdivides tree according to the given list of viewcells.
+          */
+          void Subdivide(const ViewCellContainer &viewCells);
+          /** Subdivides tree according to the given list of objects.
+          */
+          void Subdivide(const ObjectContainer &objects);
            
+          /** Subdivides leaf.
+                  @param leaf the leaf to be subdivided
+                  @param parent the parent node of this leaf
+                  @param polys the input polygons
+                  @param depth the current tree depth
+                  @param frontPolys the polygons of the front child node as a result from splitting
+                  @param backPolys the polygons of the back child node as a result from splitting
+          */
           BspNode *SubdivideNode(BspLeaf *leaf, BspInterior *parent, 
-                                                         Mesh *viewCell, const int depth, 
+                                                         Mesh *polys, const int depth, 
                                                          Mesh &frontPolys, Mesh &backPolys);
+
+          /** Extracts the mesh instances of the objects and copies them into the mesh.
+          */
+          static void Copy2PolygonSoup(const ObjectContainer &objects, Mesh &mesh);
+
 
           /// Pointer to the root of the tree
           BspNode *mRoot;
           /// Pointer to the root cell of the viewspace
-          ViewCell *mRootCell;
+          // ViewCell *mRootCell;
+          /// maximal number of polygons allowed in leaf
+          int mMaxPolys;
+          /// maximal depth
+          int mMaxDepth;
   };