Changeset 360

Timestamp:

10/28/05 18:13:22 (19 years ago)

Author:

mattausch

Message:

added findneighbours method

Location:

trunk/VUT

Files:

• GtpVisibilityPreprocessor/src/Exporter.h (modified) (2 diffs)
• GtpVisibilityPreprocessor/src/Polygon3.cpp (modified) (1 diff)
• GtpVisibilityPreprocessor/src/Polygon3.h (modified) (1 diff)
• GtpVisibilityPreprocessor/src/SamplingPreprocessor.cpp (modified) (1 diff)
• GtpVisibilityPreprocessor/src/ViewCellBsp.cpp (modified) (7 diffs)
• GtpVisibilityPreprocessor/src/ViewCellBsp.h (modified) (3 diffs)
• GtpVisibilityPreprocessor/src/X3dExporter.cpp (modified) (4 diffs)
• GtpVisibilityPreprocessor/src/X3dExporter.h (modified) (1 diff)
• scripts/GtpVisibility.suo (modified) (previous)

trunk/VUT/GtpVisibilityPreprocessor/src/Exporter.h

@@ -15 +15 @@
 class AxisAlignedBox3;
 class Intersectable;
+class BspLeaf;
 
 class Exporter
@@ -70 +71 @@
   virtual void 
   ExportBspSplits(const BspTree &tree) = 0;
+  virtual void
+  ExportLeavesGeometry(const BspTree &tree, const vector<BspLeaf *> &leaves) = 0;
         
   void SetExportRayDensity(const bool d) { mExportRayDensity = d; }

trunk/VUT/GtpVisibilityPreprocessor/src/Polygon3.cpp

@@ -375 +375 @@
         }
 }
+
+int Polygon3::ClassifyPlane(const PolygonContainer &polys, const Plane3 &plane)
+{
+        PolygonContainer::const_iterator it;
+
+        bool onFrontSide = false;
+        bool onBackSide = false;
+        
+        int count = 0;
+
+        // find possible line-plane intersections
+        for (it = polys.begin(); it != polys.end(); ++ it)
+        {
+        int cf = (*it)->ClassifyPlane(plane);
+                
+        if (cf == FRONT_SIDE)
+                        onFrontSide = true;
+                else if (cf == BACK_SIDE)
+                        onBackSide = true;
+                
+                //TODO: check if split goes through vertex
+                if ((cf == SPLIT) || (onFrontSide && onBackSide)) // split 
+                {
+                        return SPLIT;
+                }
+        }
+
+        if (onBackSide)
+        {
+                return BACK_SIDE;
+        }
+        else if (onFrontSide)
+        {
+                return FRONT_SIDE;
+        }
+        
+        return COINCIDENT; // plane and polygon are coincident
+}

trunk/VUT/GtpVisibilityPreprocessor/src/Polygon3.h

@@ -95 +95 @@
         int CastRay(const Ray &ray, float &t, const float nearestT);
 
+        /** Classify polygons with respect to the plane.
+            @returns one of BACK_SIDE, FRONT_SIDE, SPLIT, COINCIDENT
+        */
+        static int ClassifyPlane(const PolygonContainer &polys, const Plane3 &plane);
+
         /// vertices are connected in counterclockwise order.
         VertexContainer mVertices;

trunk/VUT/GtpVisibilityPreprocessor/src/SamplingPreprocessor.cpp

@@ -617 +617 @@
           if (exportSplits)
                   ExportSplits(objects);
-                 
+        
+          Exporter *exporter = Exporter::GetExporter("viewCells.x3d");
+
+          if (exporter)
+          {
+          //exporter->ExportLeavesGeometry(mBspTree, leaves);           
+
+                  delete exporter;
+          }
+
           for (int j = 0; j < pvsViewCells.size(); ++ j)
           {

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp

@@ -39 +39 @@
 
 bool BspTree::sStoreSplitPolys = false;
+
+int BspNode::mailID = 1;
 
 /** Evaluates split plane classification with respect to the plane's 
@@ -492 +494 @@
         {
                 Polygon3 *poly = new Polygon3((*fi), mesh);
-                poly->mParent = parent; // set parent intersectable
-                polys.push_back(poly);
+                
+                if (poly->Valid())
+                {
+                        poly->mParent = parent; // set parent intersectable
+                        polys.push_back(poly);
+                }
+                else
+                        DEL_PTR(poly);
         }
         return (int)mesh->mFaces.size();
@@ -512 +520 @@
                 {
                         mBox.Include(viewCells[i]->GetBox()); // add to BSP tree aabb
-                        polysSize += AddMeshToPolygons(viewCells[i]->GetMesh(), 
-                                                                                   polys, viewCells[i]);
+                        polysSize += AddMeshToPolygons(viewCells[i]->GetMesh(), polys, viewCells[i]);
                 }
         }
@@ -1678 +1685 @@
         return splits;
 }
-/*
-void BspTree::ExtractSplitPlanes(BspNode *n, vector<Plane *> planes)
+
+void BspTree::ExtractSplitPlanes(BspNode *n, vector<Plane3 *> planes, vector<bool> sides) const
 {
         while (!n->IsRoot())
         {
                 if (!n->IsLeaf())
-                        planes.push_back(dynamic_cast<BspInterior *>(n)->GetPlane();
+                        planes.push_back(dynamic_cast<BspInterior *>(n)->GetPlane());
+
+                sides.push_back(n->GetParent()->mFront == n);
 
                 n = n->GetParent();
@@ -1690 +1699 @@
 }
 
-void BspTree::ExtractGeometry(BspNode *n, PolygonContainer &polys)
-{
-        vector<Plane *> planes;
-        ExtractSplitPlanes(n, planes);
-
-                while (!tStack.empty())
-        {
-                // filter polygons donw the tree
-                BspSplitData tData = tStack.top();
-            tStack.pop();       
-                
-                if (!tData.mNode->IsLeaf())
-                {
-                        BspInterior *interior = dynamic_cast<BspInterior *>(tData.mNode);
-                        if (tData.mNode != tree.GetRoot())
-                                tData.mSides.push_back(tData.mIsFront); // add current side
-
-                        // bounded plane is added to the polygons
-                        Polygon3 *planePoly = tree.GetBoundingBox().CrossSection(*interior->GetPlane());
-                
-                        // do all the splits with the previous planes
-                        for (int i = 0; i < (int)tData.mPlanes.size(); ++i)
+void BspTree::ConstructGeometry(BspNode *n, PolygonContainer &cell) const
+{
+        stack<BspNode *> tStack;
+
+        vector<Plane3 *> planes;
+        vector<bool> sides;
+
+        ExtractSplitPlanes(n, planes, sides);
+
+        PolygonContainer candidatePolys;
+
+        // bounded plane is added to the polygons
+        for (int i = 0; i < (int)planes.size(); ++ i)
+        {
+                candidatePolys.push_back(GetBoundingBox().CrossSection(*planes[i]));
+        }
+
+        for (int i = 0; i < 6; ++ i)
+        {
+                VertexContainer vertices;
+        
+                for (int j = 0; j < 4; ++ j)
+                        vertices.push_back(mBox.GetFace(i).mVertices[j]);
+
+                candidatePolys.push_back(new Polygon3(vertices));
+        }
+
+        for (int i = 0; i < (int)candidatePolys.size(); ++ i)
+        {
+                bool inside = true;
+
+                // polygon is split with all other planes
+                for (int j = 0; (j < planes.size()) && inside; ++ j)
+                {
+                        Plane3 *plane = planes[j];
+
+                        if (i == j) // same plane
+                                continue;
+
+                        VertexContainer splitPts;
+                        Polygon3 *frontPoly, *backPoly;
+
+                        int cf = candidatePolys[i]->ClassifyPlane(*plane);
+                        
+                        // split new polygon with all previous planes
+                        switch(cf)
                         {
-                                VertexContainer splitPts;
-                                Polygon3 *frontPoly = new Polygon3();
-                                Polygon3 *backPoly = new Polygon3();
-
-                                if (planePoly->ClassifyPlane(*tData.mPlanes[i]) == Polygon3::SPLIT)
-                                {
-                                        planePoly->Split(*tData.mPlanes[i], *frontPoly, *backPoly, splitPts);
-                                        DEL_PTR(planePoly);
-
-                                        if(tData.mSides[i] == true)
+                                case Polygon3::SPLIT:
+                                        frontPoly = new Polygon3();
+                                        backPoly = new Polygon3();
+
+                                        candidatePolys[i]->Split(*plane, *frontPoly, *backPoly, splitPts);
+                                        DEL_PTR(candidatePolys[i]);
+
+                                        if(sides[j] == true)
                                         {
-                                                planePoly = frontPoly;
+                                                candidatePolys[i] = frontPoly;
                                                 DEL_PTR(backPoly);
                                         }
                                         else
                                         {
-                                                planePoly = backPoly;
+                                                candidatePolys[i] = backPoly;
                                                 DEL_PTR(frontPoly);
                                         }
-                                }
+                                        break;
+
+                                case Polygon3::BACK_SIDE:
+                                        if (sides[i]) 
+                                                inside = false;
+                                        break;
+                                case Polygon3::FRONT_SIDE:
+                                        if (!sides[i])
+                                                inside = false;
+                                        break;
+                                default:
+                                        break;
                         }
-
-                        tData.mPlanes.push_back(interior->GetPlane()); // add plane to split planes
-
-                        if (planePoly->Valid())
-                                polys.push_back(planePoly);
-                        else
-                        {
-                                //Debug << "polygon not valid: " << *planePoly << " size: " << (int)planePoly->mVertices.size() << endl;
-                                DEL_PTR(planePoly);
-                        }
-                        // push the children on the stack
-                        tStack.push(BspSplitData(interior->GetFront(), tData.mPlanes, tData.mSides, true));
-                        tStack.push(BspSplitData(interior->GetBack(), tData.mPlanes, tData.mSides, false));
-                }
-        }       
-        ExportPolygons(polys);
-        CLEAR_CONTAINER(polys);
+                }
+                
+                if (inside)
+                        cell.push_back(candidatePolys[i]);
+                else
+                        DEL_PTR(candidatePolys[i]);
+        }
 }
 
 int BspTree::FindNeighbors(BspNode *n, vector<BspNode *> &neighbors, bool onlyUnmailed)
 {
+        PolygonContainer cell;
+
+        ConstructGeometry(n, cell);
+
         stack<BspNode *> nodeStack;
         nodeStack.push(mRoot);
-
-        AxisAlignedBox3 box = GetBox(n);
 
         while (!nodeStack.empty()) 
@@ -1772 +1806 @@
                 else 
                 {
-                        KdInterior *interior = (KdInterior *)node;
-                        
-                        if (interior->mPosition > box.Max(interior->mAxis))
+                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
+        
+                        const int cf = Polygon3::ClassifyPlane(cell, interior->mPlane);
+
+                        if (cf == Polygon3::FRONT_SIDE)
                                 nodeStack.push(interior->mBack);
                         else
-                                if (interior->mPosition < box.Min(interior->mAxis))
+                                if (cf == Polygon3::BACK_SIDE)
                                         nodeStack.push(interior->mFront);
                                 else 
@@ -1788 +1824 @@
         
         }
-        return neighbors.size();
-}*/
+        return (int)neighbors.size();
+}

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.h

@@ -129 +129 @@
         void ProcessPolygons(PolygonContainer *polys, const bool storePolys);
 
+        static int mailID;
+        int mailbox;
+  
+        void Mail() { mailbox = mailID; }
+        static void NewMail() { mailID++; }
+        bool Mailed() const { return mailbox == mailID; }
+
 //int mViewCellIdx;
 protected:
@@ -356 +363 @@
         BspTreeStatistics &GetStat();
 
+        /** finds neighbouring leaves of this tree node.
+        */
+        int FindNeighbors(BspNode *n, vector<BspNode *> &neighbors, bool onlyUnmailed);
+
+        /** Extracts geometry associated with the split plane leading to this node.
+        */
+        void ConstructGeometry(BspNode *n, PolygonContainer &polys) const;
+
 protected:
 
@@ -585 +600 @@
                                   RayContainer &backRays);
 
+
+        /** Extracts the split planes representing the space bounded by node n.
+        */
+        void ExtractSplitPlanes(BspNode *n, vector<Plane3 *> planes, vector<bool> sides) const;
+
         /// Pointer to the root of the tree
         BspNode *mRoot;

trunk/VUT/GtpVisibilityPreprocessor/src/X3dExporter.cpp

@@ -687 +687 @@
 };
 
+void X3dExporter::ExportLeavesGeometry(const BspTree &tree, const vector<BspLeaf *> &leaves)
+{
+        vector<BspLeaf *>::const_iterator it, it_end = leaves.end();
+
+        for (it = leaves.begin(); it != it_end; ++ it)
+        {
+                PolygonContainer cell;
+                tree.ConstructGeometry(*it, cell);
+                
+                ExportPolygons(cell);
+
+                CLEAR_CONTAINER(cell);
+        }
+}
+
 void X3dExporter::ExportBspSplits(const BspTree &tree)
 {
@@ -705 +720 @@
                 {
                         BspInterior *interior = dynamic_cast<BspInterior *>(tData.mNode);
+
                         if (tData.mNode != tree.GetRoot())
-                                tData.mSides.push_back(tData.mIsFront); // add current side
+                                tData.mSides.push_back(tData.mIsFront); // add current side of split plane
 
                         // bounded plane is added to the polygons
@@ -712 +728 @@
                 
                         // do all the splits with the previous planes
-                        for (int i = 0; i < (int)tData.mPlanes.size(); ++i)
+                        for (int i = 0; i < (int)tData.mPlanes.size(); ++ i)
                         {
                                 VertexContainer splitPts;
-                                Polygon3 *frontPoly = new Polygon3();
-                                Polygon3 *backPoly = new Polygon3();
-
+                                
                                 if (planePoly->ClassifyPlane(*tData.mPlanes[i]) == Polygon3::SPLIT)
                                 {
+                                        Polygon3 *frontPoly = new Polygon3();
+                                        Polygon3 *backPoly = new Polygon3();
+
                                         planePoly->Split(*tData.mPlanes[i], *frontPoly, *backPoly, splitPts);
                                         DEL_PTR(planePoly);
@@ -741 +758 @@
                                 polys.push_back(planePoly);
                         else
-                        {
-                                //Debug << "polygon not valid: " << *planePoly << " size: " << (int)planePoly->mVertices.size() << endl;
                                 DEL_PTR(planePoly);
-                        }
+                        
                         // push the children on the stack
                         tStack.push(BspSplitData(interior->GetFront(), tData.mPlanes, tData.mSides, true));

trunk/VUT/GtpVisibilityPreprocessor/src/X3dExporter.h

@@ -76 +76 @@
   ExportBspSplits(const BspTree &tree);
 
+  virtual void
+  ExportLeavesGeometry(const BspTree &tree, const vector<BspLeaf *> &leaves);
+
   bool
   ExportRays(const RayContainer &rays,