Changeset 264 for trunk/VUT/GtpVisibilityPreprocessor/src

Timestamp:

09/12/05 18:24:44 (19 years ago)

Author:

mattausch

Message:

debugged bsp stuff

Location:

trunk/VUT/GtpVisibilityPreprocessor/src

Files:

• Polygon3.cpp (modified) (2 diffs)
• Preprocessor.cpp (modified) (1 diff)
• ViewCell.cpp (modified) (1 diff)
• ViewCellBsp.cpp (modified) (18 diffs)
• ViewCellBsp.h (modified) (7 diffs)
• X3dExporter.cpp (modified) (1 diff)
• main.cpp (modified) (2 diffs)

trunk/VUT/GtpVisibilityPreprocessor/src/Polygon3.cpp

@@ -11 +11 @@
 
 Polygon3::Polygon3(Face *face, Mesh *parent)
-{
-        VertexIndexContainer::reverse_iterator it = face->mVertexIndices.rbegin();
-
-        for (; it != face->mVertexIndices.rend();  ++it)
+{       
+        VertexIndexContainer::iterator it = face->mVertexIndices.begin();
+        for (; it != face->mVertexIndices.end();  ++it)
         {
                 mVertices.push_back(parent->mVertices[*it]);
@@ -123 +122 @@
                         onBackSide = true;
                 }
-
-                if (onFrontSide && onBackSide) // split //TODO: check if through vvertex
+                //TODO: check if split goes through vertex
+                if (onFrontSide && onBackSide) // split 
                 {
                         return SPLIT;

trunk/VUT/GtpVisibilityPreprocessor/src/Preprocessor.cpp

@@ -152 +152 @@
 
         if (bsptree) {
-                exporter->SetWireframe();
+                //exporter->SetWireframe();
                 exporter->ExportBspTree(*mBspTree);
         }

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCell.cpp

@@ -91 +91 @@
 
         // bottom 
-        mesh->mFaces.push_back(new Face(0,1,2));
+        mesh->mFaces.push_back(new Face(2,1,0));
         // top
-    mesh->mFaces.push_back(new Face(5,4,3));
+    mesh->mFaces.push_back(new Face(3,4,5));
         // sides
-        mesh->mFaces.push_back(new Face(0, 3, 4, 1));
-        mesh->mFaces.push_back(new Face(1, 4, 5, 2));
-        mesh->mFaces.push_back(new Face(0, 2, 5, 3));
-
+        mesh->mFaces.push_back(new Face(1, 4, 3, 0));
+        mesh->mFaces.push_back(new Face(2, 5, 4, 1));
+        mesh->mFaces.push_back(new Face(3, 5, 2, 0));
 
         //--- extrude new vertices for top of prism

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp

@@ -30 +30 @@
 int BspTree::sBalancedTreeTable[4] = {-1, 1, 0, 0};
 
+int counter = 0;
 /****************************************************************/
 /*                  class BspNode implementation                */
 /****************************************************************/
 
-BspNode::BspNode(): mParent(NULL)
+BspNode::BspNode(): mParent(NULL), mPolygons(NULL)
+{
+}
+
+BspNode::BspNode(BspInterior *parent): mParent(parent), mPolygons(NULL)
 {}
 
-BspNode::BspNode(BspInterior *parent): mParent(parent)
-{}
-
-
+BspNode::~BspNode()
+{
+        if (mPolygons)
+        {
+                CLEAR_CONTAINER(*mPolygons);
+                DEL_PTR(mPolygons);
+        }
+}
 bool BspNode::IsRoot() const 
 {
@@ -58 +67 @@
 PolygonContainer *BspNode::GetPolygons()
 {
-        return &mPolygons;
-}
-
-void BspNode::AddPolygons(PolygonContainer *polys)
-{
-        while (!polys->empty())
-        {
-                mPolygons.push_back(polys->back());
-                polys->pop_back();
-        }
+        if (!mPolygons)
+                mPolygons = new PolygonContainer();
+
+        return mPolygons;
+}
+
+void BspNode::ProcessPolygons(PolygonContainer *polys, bool storePolys)
+{
+        if (storePolys)
+        {
+                while (!polys->empty())
+                {
+                        GetPolygons()->push_back(polys->back());
+                        polys->pop_back();
+                }
+        }
+        else CLEAR_CONTAINER(*polys);
+
+        delete polys;
 }
 
@@ -103 +121 @@
 {
         if (mBack == oldChild)
-        {
                 mBack = newChild;
-        }
-    else
-        {
+        else
                 mFront = newChild;
-        }
 }
 
@@ -118 +132 @@
 }
 
-void BspInterior::ProcessPolygon(Polygon3 *poly, bool storePolys)
+void BspInterior::ProcessPolygon(Polygon3 *poly, const bool storePolys)
 {
         if (storePolys) 
-                mPolygons.push_back(poly);
+                GetPolygons()->push_back(poly);
         else
                 delete poly;
 }
 
-void BspInterior::SplitPolygons(PolygonContainer *polys, 
+bool BspInterior::SplitPolygons(PolygonContainer *polys, 
                                                                 PolygonContainer *frontPolys, 
                                                                 PolygonContainer *backPolys, 
                                                                 int &splits, bool storePolys)
 {
+#ifdef _Debug
+        Debug << "Splitting polygons of node " << this << " with plane " << mPlane << endl;
+#endif
+        bool inside = false;
+
         while (!polys->empty())
         {
@@ -141 +160 @@
                 Polygon3 *front_piece = NULL;
                 Polygon3 *back_piece = NULL;
-
+                
                 switch (result)
                 {
                         case Polygon3::COINCIDENT:
+
+                                if (!inside)
+                                        // same surface normal
+                                        inside = (DotProd(mPlane.mNormal, poly->GetSupportingPlane().mNormal) > 0);
+                                        
+                                //Debug << "coincident" << endl;
                                 // discard polygons or saves them in node
                                 ProcessPolygon(poly, storePolys);
                                 break;
                         case Polygon3::FRONT_SIDE:
+                                //Debug << "front" << endl;
                                 frontPolys->push_back(poly);
                                 break;
                         case Polygon3::BACK_SIDE:
+                                inside = true;
+                                //Debug << "back" << endl;
                                 backPolys->push_back(poly);
                                 break;
                         case Polygon3::SPLIT:
+                                inside = true;
+                                //Debug << "split" << endl;
+
                                 front_piece = new Polygon3();
                                 back_piece = new Polygon3();
@@ -179 +210 @@
         // contains nothing
         delete polys;
+
+        return inside;
 }
 
@@ -188 +221 @@
 }
 
-BspLeaf::BspLeaf(ViewCell *viewCell): mViewCell(viewCell) 
+BspLeaf::BspLeaf(ViewCell *viewCell): mViewCell(viewCell)
 {
 }
@@ -195 +228 @@
 {}
 
+BspLeaf::BspLeaf(BspInterior *parent, ViewCell *viewCell): 
+BspNode(parent), mViewCell(viewCell)
+{
+}
 ViewCell *BspLeaf::GetViewCell()
 {
@@ -219 +256 @@
 mRoot(NULL), 
 mIsIncremential(false),
-mStorePolys(true)
+mStorePolys(false)
 {
         Randomize(); // initialise random generator for heuristics
@@ -298 +335 @@
             tStack.pop();
         
-                /// if we stored the polygons
-                CLEAR_CONTAINER(node->mPolygons);
-
                 if (!node->IsLeaf())
                 {
@@ -318 +352 @@
 {       
         std::stack<BspTraversalData> tStack;
-                Debug << "getting polygons" << endl; Debug.flush();
+        
         PolygonContainer *polys = new PolygonContainer();
 
@@ -328 +362 @@
         BspNode *firstNode = mRoot ? mRoot : new BspLeaf();
 
-        tStack.push(BspTraversalData(firstNode, NULL, polys, 0));
-
-        Debug << "starting traversal" << endl; Debug.flush();
+        tStack.push(BspTraversalData(firstNode, polys, 0, true));
+
         while (!tStack.empty())
         {
-                Debug << "new traversal step" << endl; Debug.flush();
-                
                 // filter polygons donw the tree
                 BspTraversalData tData = tStack.top();
             tStack.pop();
                         
-                Debug << "popped stack" << endl; Debug.flush();
-                if (!tData.mNode)
-                        Debug << "ERROR NO NODE\n"; Debug.flush();
                 if (!tData.mNode->IsLeaf())
                 {
-                        Debug << "no leaf" << endl; Debug.flush();
                         BspInterior *interior = dynamic_cast<BspInterior *>(tData.mNode);
 
                         //-- filter view cell polygons down the tree until a leaf is reached
-                        PolygonContainer *frontPolys = new PolygonContainer();
-                        PolygonContainer *backPolys = new PolygonContainer();
-
-                        int splits = 0;
-                
                         if ((int)tData.mPolygons->size() > 0)
                         {
-                                Debug << "traversing down tree" << endl; Debug.flush();
+                                PolygonContainer *frontPolys = new PolygonContainer();
+                                PolygonContainer *backPolys = new PolygonContainer();
+
+                                int splits = 0;
+                
                                 // split viecell polygons with respect to split plane
-                                interior->SplitPolygons(tData.mPolygons, frontPolys, backPolys, splits, mStorePolys);
-                                Debug << "polygon splitted" << endl; Debug.flush();
+                                bool inside = interior->SplitPolygons(tData.mPolygons, frontPolys, backPolys, splits, mStorePolys);
                                 //Debug << "Reached level " << tData.mDepth << " bk: " << backPolys->size() << " frnt: " << frontPolys->size() << endl;
                                 mStat.splits += splits;
 
                                 // push the children on the stack
-                                tStack.push(BspTraversalData(interior->GetFront(), interior->GetParent(), 
-                                                        frontPolys, tData.mDepth + 1));
-                        
-                                tStack.push(BspTraversalData(interior->GetBack(), interior->GetParent(), 
-                                                        backPolys, tData.mDepth + 1));
+                                tStack.push(BspTraversalData(interior->GetFront(), frontPolys, tData.mDepth + 1, false));
+                                tStack.push(BspTraversalData(interior->GetBack(), backPolys, tData.mDepth + 1, inside));
                         
                         }
-                        else
+                        else // stop traversal
                         {
-                                Debug << "deleting data" << endl; Debug.flush();
                                 DEL_PTR(tData.mPolygons);
-                                Debug << "deleted data" << endl; Debug.flush();
                         }
                 }
                 else // reached leaf => subdivide current viewcell
                 {
-                        Debug << "reached leaf" << endl; Debug.flush();
                         BspNode *root = Subdivide(tStack, tData, viewCell);             
 
             // tree empty => new root
                         if (!mRoot)
-                                mRoot = root;           
-                        Debug << "subdivision done" << endl; Debug.flush();
-                }
-                Debug << "ended one traversal step" << endl; Debug.flush();
+                                mRoot = root;
+                }
         }
         Debug << "ended traversal" << endl; Debug.flush();
@@ -495 +512 @@
         mStorePolys = savedStorePolys;
 
-        int counter = 0;
+        counter = 0;
 
         Debug << "\n**** Started view cells insertion ****\n\n";
@@ -502 +519 @@
                 Debug << "*** Inserting view cell " << counter << " ***" << endl;
                 InsertViewCell(*it);
-                Debug << "*** view cell " << ++ counter << " inserted ***" << endl;
+                counter ++;
         }
         Debug << "**** finished view cells insertion ****" << endl; Debug.flush();
@@ -533 +550 @@
         std::stack<BspTraversalData> tStack;
         
-        BspTraversalData tData(new BspLeaf(), NULL, polys, 0);
+        BspTraversalData tData(new BspLeaf(), polys, 0, true);
 
         tStack.push(tData);
@@ -555 +572 @@
 
 
-BspNode * BspTree::Subdivide(BspTraversalStack &tStack, 
-                                                         BspTraversalData &tData, 
-                                                         ViewCell *viewCell)
-{
-        Debug << "subdividing" << endl; Debug.flush();
+BspNode *BspTree::Subdivide(BspTraversalStack &tStack, BspTraversalData &tData, 
+                                                        ViewCell *viewCell)
+{
+        //-- terminate traversal  
+        if (((tData.mPolygons->size() <= mTermMaxPolygons) || (tData.mDepth >= mTermMaxDepth))
+                // if there is another view cell associated with this leaf => subdivide further
+                && !(viewCell && tData.mIsInside && dynamic_cast<BspLeaf *>(tData.mNode)->GetViewCell()))
+        {
+#ifdef _DEBUG
+        Debug << "terminate subdivision, size " << (int)tData.mPolygons->size() << ", depth " << tData.mDepth << endl;
+#endif
+
+                EvaluateLeafStats(tData);
+
+            // add view cell if inside object) 
+                if (viewCell && tData.mIsInside) 
+                        // || (tData.mGeometry->size() > 0) // or if there is still geometry left 
+                {
+                        BspLeaf *leaf = dynamic_cast<BspLeaf *>(tData.mNode);
+
+#ifdef _DEBUG
+                        if (leaf->GetViewCell())
+                                Debug << "ERROR: leaf already has view cell" << endl;
+
+                        Debug << "**** Inserted view cell ****" << endl;
+#endif
+                        leaf->SetViewCell(viewCell);
+                }
+
+                // add or delete remaining polygons
+                tData.mNode->ProcessPolygons(tData.mPolygons, mStorePolys);
+
+                return tData.mNode;
+        }
+
+        //-- create new subdivided node
         PolygonContainer *backPolys = new PolygonContainer();
         PolygonContainer *frontPolys = new PolygonContainer();
 
-        BspNode *node = SubdivideNode(dynamic_cast<BspLeaf *>(tData.mNode),
-                                                                  tData.mParent,
-                                                                  tData.mPolygons,
-                                                                  tData.mDepth,
-                                                                  frontPolys,
-                                                                  backPolys);
-
-        if (!node->IsLeaf()) // node was subdivided
-        {
-                Debug << "node was subdivided" << endl; Debug.flush();
-                BspInterior *interior = dynamic_cast<BspInterior *>(node);
-
-                // push the children on the stack (there are always two children)
-                tStack.push(BspTraversalData(interior->GetBack(), interior, backPolys, tData.mDepth + 1));
-                tStack.push(BspTraversalData(interior->GetFront(), interior, frontPolys, tData.mDepth + 1));
-        }
-        else // traversal terminates
-        {
-                Debug << "eval stats" << endl; Debug.flush();
-                EvaluateLeafStats(tData);
-
-        BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
-
-                // add view cell if in negative halfspace (== inside object) 
-                // or if there is still geometry left
-                if (viewCell && 
-                        (!node->GetParent() || (node == node->GetParent()->GetBack()) || 
-                         (tData.mPolygons->size() > 0)))
-                {
-                        Debug << "** view cell inserted **\n";
-                        leaf->SetViewCell(viewCell);
-                }
-
-                Debug << "storing or deleting polygons: " << mStorePolys << endl; Debug.flush();
-                // add or delete remaining polygons
-                if (mStorePolys)
-                        leaf->AddPolygons(tData.mPolygons);
-                else
-                        CLEAR_CONTAINER(*tData.mPolygons);
-
-                DEL_PTR(tData.mPolygons);
-                Debug << "deleted polygon container" << endl; Debug.flush();
-        }
-
-        return node;
-}
-
-
-BspNode *BspTree::SubdivideNode(BspLeaf *leaf, 
-                                                                BspInterior *parent, 
-                                                                PolygonContainer *polys, 
-                                                                const int depth, 
-                                                                PolygonContainer *frontPolys, 
-                                                                PolygonContainer *backPolys)
-{
-        if (leaf->GetViewCell() && (polys->size() == 0))
-                Debug << "error: no distinct view cells!!!!!!!!!!!\n";
-        
-        // terminate traversal  
-        if (//!leaf->GetViewCell() && 
-                ((polys->size() <= mTermMaxPolygons) || (depth >= mTermMaxDepth)))
-        {Debug << "subdividing node termination" << endl; Debug.flush();
-                return leaf;
-        }
-
-         mStat.nodes += 2;
+        bool inside = false;
+
+        BspInterior *interior = SubdivideNode(dynamic_cast<BspLeaf *>(tData.mNode),
+                                                                                  tData.mPolygons,
+                                                                                  frontPolys,
+                                                                                  backPolys, inside);
+
+        // push the children on the stack (there are always two children)
+        tStack.push(BspTraversalData(interior->GetBack(), backPolys, tData.mDepth + 1, inside));
+        tStack.push(BspTraversalData(interior->GetFront(), frontPolys, tData.mDepth + 1, false));
+
+        return interior;
+}
+
+
+BspInterior *BspTree::SubdivideNode(BspLeaf *leaf, 
+                                                                        PolygonContainer *polys, 
+                                                                        PolygonContainer *frontPolys, 
+                                                                        PolygonContainer *backPolys, bool &inside)
+{
+        mStat.nodes += 2;
 
         // add the new nodes to the tree + select subdivision plane
-        BspInterior *node = new BspInterior(SelectPlane(polys)); 
+        BspInterior *interior = new BspInterior(SelectPlane(polys)); 
 
 #ifdef _DEBUG
-        Debug << node << endl;
+        Debug << interior << endl;
 #endif
 
@@ -640 +643 @@
         int splits = 0;
                 
-        Debug << "splipoly" << endl; Debug.flush();
-        node->SplitPolygons(polys, frontPolys, backPolys, splits, mStorePolys);
+        inside = interior->SplitPolygons(polys, frontPolys, backPolys, splits, mStorePolys);
         
         mStat.splits += splits;
 
-        // two new leaves
-        BspLeaf *back = new BspLeaf(node);
-        BspLeaf *front = new BspLeaf(node);
+        BspInterior *parent = leaf->GetParent();
 
         // replace a link from node's parent
         if (parent)
-                parent->ReplaceChildLink(leaf, node);
-        
+        {
+                parent->ReplaceChildLink(leaf, interior);
+                interior->SetParent(parent);
+        }
+
         // and setup child links
-        node->SetupChildLinks(back, front);
-        
-        DEL_PTR(leaf); // leaf not member of tree anymore
-        
-        return node;
+        interior->SetupChildLinks(new BspLeaf(interior, leaf->mViewCell), new BspLeaf(interior));
+        
+        delete leaf; // leaf not member of tree anymore
+
+        return interior;
 }
 
@@ -715 +718 @@
                 int classification = (*it)->ClassifyPlane(candidatePlane);
                 
-                if ((sSplitPlaneStrategy == BALANCED_TREE) || (sSplitPlaneStrategy == COMBINED))
+                if ((sSplitPlaneStrategy == COMBINED) || (sSplitPlaneStrategy == BALANCED_TREE))
                 {
                         sum += sBalancedTreeTable[classification];
                 }
                 
-                if ((sSplitPlaneStrategy == LEAST_SPLITS) || (sSplitPlaneStrategy == COMBINED))
+                if ((sSplitPlaneStrategy == COMBINED) ||(sSplitPlaneStrategy == LEAST_SPLITS))
                 {
                         sum2 += sLeastSplitsTable[classification];

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.h

@@ -107 +107 @@
 public:
         BspNode();
+        virtual ~BspNode();
         BspNode(BspInterior *parent);
 
@@ -126 +127 @@
         void SetParent(BspInterior *parent);
 
+        /** Returns pointer to polygons.
+        */
         PolygonContainer *GetPolygons();
 
-        /** Adds polygons to node.
-        */
-        void AddPolygons(PolygonContainer *polys);
-
 protected:
+
+        /** Adds or discards polygons according to storePolys.
+        */
+        void ProcessPolygons(PolygonContainer *polys, const bool storePolys);
+
 
         /// parent of this node
         BspInterior *mParent;
 
-        PolygonContainer mPolygons;
+        /// store polygons created during BSP splits
+        PolygonContainer *mPolygons;
 };
 
@@ -165 +170 @@
                 @param backPolys returns the polygons in the back of the split plane
                 @param splits number of splits
-        */
-        void SplitPolygons(PolygonContainer *polys, PolygonContainer *frontPolys, 
+                @returns true if one or more polygons are inside of the split plane
+        */
+        bool SplitPolygons(PolygonContainer *polys, PolygonContainer *frontPolys, 
                                            PolygonContainer *backPolys, int &splits, bool storePolys = false);
 
@@ -181 +187 @@
                 @param storePolys if the polygons should be stored or discarded
         */
-        void ProcessPolygon(Polygon3 *poly, bool storePolys);
+        void ProcessPolygon(Polygon3 *poly, const bool storePolys);
 
         /// Splitting plane corresponding to this node
@@ -201 +207 @@
         BspLeaf(ViewCell *viewCell);
         BspLeaf(BspInterior *parent);
+        BspLeaf(BspInterior *parent, ViewCell *viewCell);
 
         /** @return true since it is an interior node 
@@ -231 +238 @@
                 /// the current node
                 BspNode *mNode;
-                /// parent of current node
-                BspInterior *mParent;
                 /// polygonal data for splitting
                 PolygonContainer *mPolygons;
                 /// current depth
                 int mDepth;
-                
+                /// if the node is an inside or outside node with respect to the parent plane
+                bool mIsInside;
                 BspTraversalData() {}
                 
-                BspTraversalData(BspNode *node, BspInterior *parent, PolygonContainer *polys, const int depth): 
-                mNode(node), mParent(parent), mPolygons(polys), mDepth(depth) {}
+                BspTraversalData(BspNode *node, PolygonContainer *polys, const int depth, const bool inside): 
+                mNode(node), mPolygons(polys), mDepth(depth), mIsInside(inside) {}
     };
 
@@ -341 +347 @@
         /** Subdivide 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, 
-                                                   PolygonContainer *polys, 
-                                                   const int depth, 
-                                                   PolygonContainer *frontPolys, 
-                                                   PolygonContainer *backPolys);
+                @param if the polygons are outside or inside with respect to the interior node plane
+                @returns the root of the subdivision
+        */
+        BspInterior *SubdivideNode(BspLeaf *leaf, 
+                                                           PolygonContainer *polys, 
+                                                           PolygonContainer *frontPolys, 
+                                                           PolygonContainer *backPolys, bool &inside);
 
         /** Filters polygons down the tree.

trunk/VUT/GtpVisibilityPreprocessor/src/X3dExporter.cpp

@@ -387 +387 @@
 
         AxisAlignedBox3 box = tree.GetBoundingBox();
+        bool savedWireframe = mWireframe;
+
+        SetWireframe();
         ExportBox(box);
-         
+        
+        if (!savedWireframe)
+                SetFilled();
+
         while (!tStack.empty()) 
         {

trunk/VUT/GtpVisibilityPreprocessor/src/main.cpp

@@ -7 +7 @@
 #include "Camera.h"
 #include "MeshKdTree.h"
+#include "Exporter.h"
 
 #define USE_EXE_PATH false
@@ -35 +36 @@
   environment->GetStringValue("Scene.viewcells", buff);
 
-  string vcFileName(buff);
+  string vcFilename(buff);
 
   // if BSP tree construction method needs predefined view cells
   if (BspTree::sConstructionMethod == BspTree::VIEW_CELLS)
   {
-          if (vcFileName != "")
-          p->LoadViewCells(vcFileName);
+          if (vcFilename != "")
+          {
+          p->LoadViewCells(vcFilename);
+                  Exporter *exporter = Exporter::GetExporter("viewcells.x3d");
+                  if (exporter) 
+                  {
+                          exporter->ExportViewCells(&p->mViewCells);
+                          delete exporter;
+                  }
+          }
           else
                   p->GenerateViewCells();