Changeset 225 for trunk/VUT

Timestamp:

08/10/05 01:50:13 (19 years ago)

Author:

mattausch

Message:

updated bsp trees

Location:

trunk/VUT/GtpVisibilityPreprocessor

Files:

• include/ViewCellBsp.h (modified) (3 diffs)
• scripts/Preprocessor.vcproj (modified) (1 diff)
• src/Plane3.h (modified) (1 diff)
• src/ViewCellBsp.cpp (modified) (12 diffs)
• src/ViewCellBsp.h (modified) (7 diffs)

trunk/VUT/GtpVisibilityPreprocessor/include/ViewCellBsp.h

@@ -29 +29 @@
   protected:
 
-          void SplitPoly(Plane3 *plane, Mesh *viewcell);
-
           /// parent of this node
           BspInterior *mParent;
@@ -38 +36 @@
   class BspInterior : public BspNode 
   {    
-        /** @return false since it is an interior node */
-        bool IsLeaf() const;
-
-        protected:
-        /// Splitting plane corresponding to this node
-        Plane3 mPlane;
-        /// back node
-        BspNode *mBack;
-        /// front node
-        BspNode *mFront;
+          /** @return false since it is an interior node */
+          bool IsLeaf() const;
+  
+  protected:
+          /// Splitting plane corresponding to this node
+          Plane3 mPlane;
+          /// back node
+          BspNode *mBack;
+          /// front node
+          BspNode *mFront;
   };
   
   
-  /** BSP leaf node implementation */
+  /** BSP leaf node implementation.
+  */
   class BspLeaf : public BspNode 
   {
@@ -65 +64 @@
   };
   
-  /** Implementation of the ViewCell BSP tree */
+  /** Implementation of the ViewCell BSP tree.
+  */
   class BspTree 
   {

trunk/VUT/GtpVisibilityPreprocessor/scripts/Preprocessor.vcproj

@@ -217 +217 @@
                         </File>
                         <File
+                                RelativePath="..\src\Rectangle3.cpp">
+                        </File>
+                        <File
                                 RelativePath="..\src\Rectangle3.h">
                         </File>

trunk/VUT/GtpVisibilityPreprocessor/src/Plane3.h

@@ -41 +41 @@
                            float *t = NULL,
                            bool *coplanar = NULL
-                           ) const;
+                           ) const {return Vector3(0,0,0);} // TODO
 
   friend bool

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp

@@ -86 +86 @@
 
 /****************************************************************/
+/*                  class Polygon implementation                */
+/****************************************************************/
+
+Polygon::Polygon()
+{}
+
+Polygon::Polygon(const VertexContainer &vertices): mVertices(vertices) 
+{}
+
+Polygon::Polygon(Face *face, Mesh *parent)
+{
+        VertexIndexContainer::const_iterator it;
+
+        for (it = face->mVertexIndices.begin(); it != face->mVertexIndices.end(); ++ it)
+        {
+                mVertices.push_back(parent->mVertices[*it]);
+        }
+}
+
+Plane3 Polygon::GetSupportingPlane()
+{
+        return Plane3(mVertices[0], mVertices[1], mVertices[2]);
+}
+
+void Polygon::DeletePolygons(PolygonQueue *polys)
+{
+        // don't need to store polygon information = delete polygons
+        while(!polys->empty())
+        {
+                Polygon *poly = polys->front();
+                polys->pop();
+                DEL_PTR(poly);
+        }
+
+}
+
+void Polygon::Split(Plane3 *partition, Polygon *front, Polygon *back)
+{
+        Vector3 ptA = mVertices[mVertices.size() - 1];;
+        
+        int sideA = partition->Side(ptA);
+        
+        VertexContainer::const_iterator it;
+
+        // find line - plane intersections
+        for (it = mVertices.begin(); it != mVertices.end(); ++ it)
+        {
+                Vector3 ptB = (*it);
+                int sideB = partition->Side(ptB);
+
+                // vertices on different sides => split
+                if ((sideA != 0) && (sideB != 0) && (sideA != sideB)) 
+                {
+                        Vector3 v = ptB - ptA; // line from A to B
+                        float dv = DotProd(partition->mNormal, v);
+                        float t = 0;
+                        
+                        if (dv)
+                        {
+                                t = - partition->Distance(ptA) / dv;
+                        }
+                }
+                if (sideB >= 0)
+                {
+                        back->mVertices.push_back(ptB);
+                }
+                else if (sideB <= 0)
+                {
+                        front->mVertices.push_back(ptB);
+                }
+
+                ptA = ptB;
+                sideA = sideB;
+        }
+}
+
+int Polygon::Side(Plane3 *plane)
+{
+        VertexContainer::const_iterator it;
+
+        bool onFrontSide = false;
+        bool onBackSide = false;
+
+        // find line - plane intersections
+        for (it = mVertices.begin(); it != mVertices.end(); ++ it)
+        {
+                int side = plane->Side(*it);
+                
+                if (side > 0)
+                {
+                        onFrontSide = true;
+                }
+                else if (side < 0)
+                {
+                        onBackSide = true;
+                }
+
+                if (onFrontSide && onBackSide) // splits
+                        return SPLIT;
+        }
+
+        if (onBackSide)
+        {
+                return BACK_SIDE;
+        }
+        else if (onFrontSide)
+        {
+                return FRONT_SIDE;
+        }
+
+        return COINCIDENT;
+}
+
+/****************************************************************/
 /*                  class BspTree implementation                */
 /****************************************************************/
@@ -128 +242 @@
                 }
 
-                delete node;
-                node = NULL;
+                DEL_PTR(node);
         }
 }
@@ -136 +249 @@
 void BspTree::InsertViewCell(ViewCell *viewCell)
 {
-        BspNode *currentNode = mRoot;
+        std::stack<BspTraversalData> tStack;
+        
+        PolygonQueue polys;
+        // copy polygon information to guide the split process
+        CopyMesh2Polygon(viewCell->GetMesh(), polys);
+
+        tStack.push(BspTraversalData(mRoot, NULL, &polys, 0));
+
+        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());
+                }
+
+                DEL_PTR(node);*/
+        }
+/*      BspNode *currentNode = mRoot;
   
         std::stack<BspTraversalData> tStack;
@@ -170 +311 @@
                         }
                 }
-        }
+        }*/
 }
 
@@ -177 +318 @@
 }
 
-void BspTree::Copy2PolygonSoup(const ObjectContainer &objects, Mesh &mesh)
+void BspTree::CopyMesh2Polygon(Mesh *mesh, PolygonQueue &polys)
+{
+        FaceContainer::const_iterator fi;
+        // copy the face data to polygons
+        for (fi = mesh->mFaces.begin(); fi != mesh->mFaces.end(); ++ fi)
+        {
+                Polygon *poly = new Polygon((*fi), mesh);
+                polys.push(poly);
+        }
+}
+
+void BspTree::Copy2PolygonSoup(const ObjectContainer &objects, PolygonQueue &polys)
 {
         ObjectContainer::const_iterator it, it_end = objects.end();
@@ -183 +335 @@
         for (it = objects.begin(); it != it_end; ++ it)
         {
-                FaceContainer::const_iterator fi;
                 Intersectable *object = *it;
 
@@ -191 +342 @@
                         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);
-                        }
+                        Mesh *mesh = inst->GetMesh();
+
+                        // copy the mesh data to polygons
+                        CopyMesh2Polygon(mesh, polys);
                 }
         }
@@ -206 +353 @@
 {
         std::stack<BspTraversalData> tStack;
-        Mesh polys;
+        PolygonQueue polys;
         
         // copy mesh instance polygons into one big polygon soup
@@ -220 +367 @@
             tStack.pop();
     
-                Mesh backPolys;
-                Mesh frontPolys;
+                PolygonQueue *backPolys = new PolygonQueue();
+                PolygonQueue *frontPolys = new PolygonQueue();
 
                 BspNode *node = SubdivideNode(dynamic_cast<BspLeaf *>(data.mNode),
@@ -235 +382 @@
 
                         // 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) 
+                        tStack.push(BspTraversalData(interior->GetBack(), interior, backPolys, data.mDepth + 1));
+                        tStack.push(BspTraversalData(interior->GetFront(), interior, frontPolys, data.mDepth + 1));
+                }
+        }
+}
+
+Plane3 BspTree::SelectPlane(PolygonQueue *polyQueue) 
 {
         // TODO: more sophisticated criteria
-        return polys->GetFacePlane(0);
+        return polyQueue->front()->GetSupportingPlane();
 }
 
 BspNode *BspTree::SubdivideNode(BspLeaf *leaf, BspInterior *parent, 
-                                                                Mesh *polys, const int depth, 
-                                                                Mesh &frontPolys, Mesh &backPolys)
+                                                                PolygonQueue *polys, const int depth, 
+                                                                PolygonQueue *frontPolys, PolygonQueue *backPolys)
 {
         // 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
-
+        if ((polys->size() <= mMaxPolys) || (depth >= mMaxDepth))
+        {
+                // don't need to store polygon information = delete polygons
+                Polygon::DeletePolygons(polys);
+                
                 return leaf;
         }
@@ -264 +410 @@
         BspInterior *node = new BspInterior(SelectPlane(polys)); 
 
-        FaceContainer::const_iterator fi;
-
-        for (fi = polys->mFaces.begin(); fi != polys->mFaces.end(); ++ fi)
-        {
-                Face *face = (*fi);
+        while (!polys->empty())
+        {
+                Polygon *poly = polys->front();
+
+                polys->pop();
 
                 int  result = 0;// = node->GetPlane()->Side(node->GetPlane());
 
-                Face *front_piece, *back_piece;
+                Polygon *front_piece = NULL;
+                Polygon *back_piece = NULL;
 
                 switch (result)
                 {
-                        case 1:
-                                frontPolys.AddFace(face);
+                        case Polygon::COINCIDENT:
+                        case Polygon::FRONT_SIDE:
+                                frontPolys->push(poly);
                                 break;
-                        case -1:
-                                backPolys.AddFace(face);
+                        case Polygon::BACK_SIDE:
+                                backPolys->push(poly);
                                 break;
-                        case 0:
-                                //Split_Polygon (face, tree->partition, front_piece, back_piece);
-                                backPolys.AddFace(back_piece);
-                                frontPolys.AddFace(front_piece);
-
-                                // face not needed anymore
-                                DEL_PTR(face);
-
+                        case Polygon::SPLIT:
+                                front_piece = new Polygon();
+                                back_piece = new Polygon();
+
+                                //-- split polygon
+                poly->Split(node->GetPlane(), front_piece, back_piece);
+
+
+                                backPolys->push(back_piece);
+                                frontPolys->push(front_piece);
+
+                                // don't need polygon anymore
+                                DEL_PTR(poly);
                                 break;
                         default:
+                                frontPolys->push(poly);
                                 break;
                 }
@@ -309 +463 @@
         node->SetupChildLinks(back, front);
 
-        // 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);
 

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.h

@@ -4 +4 @@
 #include "Mesh.h"
 #include "Containers.h"
-
+#include <queue>
 
 class ViewCell;
@@ -13 +13 @@
 class BspTree;  
 class BspInterior;
-
+class Polygon;
 
   /**
@@ -91 +91 @@
   };
   
+  typedef std::queue<Polygon *> PolygonQueue;
+
+  /** Class representing a polygon.
+  */
+  class Polygon
+  {
+  public:
+          Polygon();
+          Polygon(const VertexContainer &vertices);
+
+          /** Copies all the vertices of the face.
+          */
+          Polygon(Face *face, Mesh *parent);
+         
+           /** Returns supporting plane of this polygon.
+          */
+          Plane3 GetSupportingPlane();
+
+          /** Splits polygon.
+                  @param partition the split plane
+                  @param front the front polygon
+                  @param back the back polygon
+          */
+          void Split(Plane3 *partition, Polygon *front, Polygon *back);
+
+          enum {BACK_SIDE, FRONT_SIDE, SPLIT, COINCIDENT};
+
+          /** Side of the plane where the polygon is located.
+              @returns one of BACK_SIDE, FRONT_SIDE, SPLIT, COINCIDENT
+          */
+          int Side(Plane3 *plane);
+
+          static void DeletePolygons(PolygonQueue *polys);
+
+          /// vertices are connected in counterclockwise order.
+          VertexContainer mVertices;
+  };
+
   /** Implementation of the ViewCell BSP tree. */
   class BspTree 
   {
   public:
+                  
+          /** Additional data which is passed down the BSP tree during traversal.
+          */
           struct BspTraversalData
           {  
@@ -102 +143 @@
                   BspInterior *mParent;
                   /// polygonal data for splitting
-                  Mesh *mPolys;
+                  PolygonQueue *mPolys;
                   /// current depth
                   int mDepth;
@@ -108 +149 @@
                   BspTraversalData() {}
                   
-                  BspTraversalData(BspNode *node, BspInterior *parent, Mesh *polys, const int depth): 
+                  BspTraversalData(BspNode *node, BspInterior *parent, PolygonQueue *polys, const int depth): 
                   mNode(node), mParent(parent), mPolys(polys), mDepth(depth) {}
       };
-         
+
+
           /** Constructs BSP tree from list of view cells.
           */ 
@@ -127 +169 @@
           /** Selects a splitting plane from the given polygons. 
           */
-          Plane3 SelectPlane(Mesh *polys);
+          Plane3 SelectPlane(PolygonQueue *polyQueue);
 
           /** Filters next viewcell down the tree and inserts it into the appropriate leaves
@@ -150 +192 @@
           */
           BspNode *SubdivideNode(BspLeaf *leaf, BspInterior *parent, 
-                                                         Mesh *polys, const int depth, 
-                                                         Mesh &frontPolys, Mesh &backPolys);
+                                                         PolygonQueue *polys, const int depth, 
+                                                         PolygonQueue *frontPolys, PolygonQueue *backPolys);
 
           /** Extracts the mesh instances of the objects and copies them into the mesh.
           */
-          static void Copy2PolygonSoup(const ObjectContainer &objects, Mesh &mesh);
-
+          static void Copy2PolygonSoup(const ObjectContainer &objects, PolygonQueue &polys);
+
+          static void CopyMesh2Polygon(Mesh *mesh, PolygonQueue &polys);
 
           /// Pointer to the root of the tree