Changeset 286 for trunk/VUT/GtpVisibilityPreprocessor

Timestamp:

09/16/05 19:24:10 (19 years ago)

Author:

mattausch

Message:

 

Location:

trunk/VUT/GtpVisibilityPreprocessor

Files:

• scripts/default.env (modified) (2 diffs)
• src/Polygon3.cpp (modified) (1 diff)
• src/Polygon3.h (modified) (3 diffs)
• src/ViewCellBsp.cpp (modified) (20 diffs)
• src/ViewCellBsp.h (modified) (9 diffs)
• src/main.cpp (modified) (1 diff)

trunk/VUT/GtpVisibilityPreprocessor/scripts/default.env

@@ -8 +8 @@
 #       filename glasgow1.x3d
 #       filename vienna.x3d
-        filename ../data/atlanta/atlanta2.x3d
+        filename ../data/vienna/vienna-simple.x3d
+#       filename ../data/vienna/viewcells-25-sel.x3d
+#       filename ../data/atlanta/atlanta2.x3d
 #       filename ../data/soda/soda.dat
 #       filename ../data/soda/soda5.dat
 #       viewcells ../data/atlanta/atlanta_viewcells_large.x3d
 #viewcells ../data/atlanta/atlanta_viewcells_large2.x3d
-#       viewcells ../data/vienna/viewcells-25-sel.x3d
-        viewcells ../data/vienna/viewcells-25.x3d
+        viewcells ../data/vienna/viewcells-25-sel.x3d
+#       viewcells ../data/vienna/viewcells-25.x3d
 #       viewcells ../data/vienna/viewcells-large-sel.x3d
 }
@@ -68 +70 @@
         splitPlaneStrategy combined
 #       constructionMethod rays
-        constructionMethod viewCells
-#       constructionMethod sceneGeometry
+#       constructionMethod viewCells
+        constructionMethod sceneGeometry
         maxCandidates 25
         maxViewCells 999999
         Termination {
-                maxPolygons 0
-                maxDepth 3000
+                maxPolygons 3
+                maxDepth 30
         }
 }

trunk/VUT/GtpVisibilityPreprocessor/src/Polygon3.cpp

@@ -2 +2 @@
 #include "Mesh.h"
 #include "ViewCellBsp.h" // TODO: erase this
+#include "Intersectable.h"
+
 // tolerance value for side relation
 #define SIDE_TOLERANCE 0.002f // TODO: Test different values
 
-Polygon3::Polygon3(): mMaterial(NULL)
+Polygon3::Polygon3(): mMaterial(NULL), mParent(NULL)
 {}
 
-Polygon3::Polygon3(const VertexContainer &vertices): mVertices(vertices), mMaterial(NULL)
+Polygon3::Polygon3(const VertexContainer &vertices): mVertices(vertices), mMaterial(NULL), mParent(NULL)
 {}
 
-Polygon3::Polygon3(Face *face, Mesh *parent)
+Polygon3::Polygon3(Intersectable *parent): mMaterial(NULL), mParent(parent)
+{
+}
+Polygon3::Polygon3(Face *face, Mesh *parentMesh)
 {       
         VertexIndexContainer::iterator it = face->mVertexIndices.begin();
         for (; it != face->mVertexIndices.end();  ++it)
         {
-                mVertices.push_back(parent->mVertices[*it]);
-                mMaterial = parent->mMaterial;
+                mVertices.push_back(parentMesh->mVertices[*it]);
+                mMaterial = parentMesh->mMaterial;
                 
-                //Debug << parent->mVertices[*it] << endl;
+                //Debug << parentMesh->mVertices[*it] << endl;
         }
 }

trunk/VUT/GtpVisibilityPreprocessor/src/Polygon3.h

@@ -13 +13 @@
 class Plane3;
 class Face;
-
+class Intersectable;
 
 /** Class representing a general planar polygon in 3d.
@@ -22 +22 @@
         Polygon3();
         Polygon3(const VertexContainer &vertices);
+        Polygon3(Intersectable *parent);
 
         /** Copies all the vertices of the face.
         */
-        Polygon3(Face *face, Mesh *parent);
+        Polygon3(Face *face, Mesh *parentMesh);
         
         /** Returns supporting plane of this polygon.
@@ -65 +66 @@
         /// we can also store materials with polygons
         Material *mMaterial;
-
-        static int mLeastSplitTable[4];
-        static int mBalancedTreeTable[4];
+        
+        /// pointer to the intersectable this polygon is derived from
+        Intersectable *mParent;
 };
 

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp

@@ -39 +39 @@
 /****************************************************************/
 
-BspNode::BspNode(): mParent(NULL), mPolygons(NULL),mViewCellIdx(0)
+BspNode::BspNode(): mParent(NULL), mPolygons(NULL)//,mViewCellIdx(0)
 {}
 
-BspNode::BspNode(BspInterior *parent): mParent(parent), mPolygons(NULL),mViewCellIdx(0)
+BspNode::BspNode(BspInterior *parent): mParent(parent), mPolygons(NULL)//,mViewCellIdx(0)
 {}
 
@@ -144 +144 @@
 }
 
-bool BspInterior::SplitPolygons(PolygonContainer *polys, 
-                                                                PolygonContainer *frontPolys, 
-                                                                PolygonContainer *backPolys, 
-                                                                PolygonContainer *coincident, 
-                                                                int &splits, bool storePolys)
-{
+Polygon3 *BspInterior::SplitPolygons(PolygonContainer *polys, 
+                                                                        PolygonContainer *frontPolys, 
+                                                                        PolygonContainer *backPolys, 
+                                                                        int &splits, bool storePolys)
+{
+        Polygon3 *splitPoly = NULL;
 #ifdef _Debug
         if (BspTree::displayDebug)Debug << "Splitting polygons of node " << this << " with plane " << mPlane << endl;
@@ -169 +169 @@
                 {
                         case Polygon3::COINCIDENT:
+                                //Debug << "coincident" << endl;        
                                 // same surface normal
                                 if (DotProd(mPlane.mNormal, poly->GetSupportingPlane().mNormal) > 0)
                                 {
-                                        coincident->push_back(poly);
+                                        if (!splitPoly) // store the split polygon if there is none
+                                                splitPoly = poly;
+                                        else //  discard it otherwise
+                                                ProcessPolygon(poly, storePolys);
+
                                         break;
-                                }
-                                //if (BspTree::displayDebug)    Debug << "coincident" << endl;                          
+                                }                                                       
                                 
                         case Polygon3::FRONT_SIDE:      
-                                //if (BspTree::displayDebug)Debug << "front" << endl;
+                                //Debug << "front" << endl;
                                 frontPolys->push_back(poly);
                                 break;
                         case Polygon3::BACK_SIDE:
-                                //if (BspTree::displayDebug)Debug << "back" << endl;
+                                //Debug << "back" << endl;
                                 backPolys->push_back(poly);
                                 break;
                         case Polygon3::SPLIT:
-                                front_piece = new Polygon3(poly->GetParent());
-                                back_piece = new Polygon3(poly->GetParent());
+                                front_piece = new Polygon3(poly->mParent);
+                                back_piece = new Polygon3(poly->mParent);
 
                                 //-- split polygon
@@ -196 +200 @@
 
 #ifdef _DEBUG
-                                if (BspTree::displayDebug)Debug << "split " << *poly << endl << *front_piece << endl << *back_piece << endl;
+                                Debug << "split " << *poly << endl << *front_piece << endl << *back_piece << endl;
 #endif
                                 ProcessPolygon(poly, storePolys);
@@ -207 +211 @@
         }
         //if (BspTree::displayDebug) Debug << "inside: " << inside << endl;
-        // contains nothing
-        delete polys;
+        
+        delete polys; // contains nothing
+        return splitPoly;
 }
 
@@ -252 +257 @@
 mTermMaxDepth(0), 
 mRoot(NULL), 
-mIsIncremential(false),
 //mStorePolys(true)
 mStorePolys(false)
@@ -354 +358 @@
 
 
-void BspTree::InsertViewCell(ViewCell *viewCell)
+/*void BspTree::InsertViewCell(ViewCell *viewCell)
 {       
         std::stack<BspTraversalData> tStack;
@@ -384 +388 @@
                                 PolygonContainer *frontPolys = new PolygonContainer();
                                 PolygonContainer *backPolys = new PolygonContainer();
-                                PolygonContainer *coincident = new PolygonContainer();
+                                Polygon3 *coincident = NULL;
 
                                 int splits = 0;
@@ -400 +404 @@
 
                                 // push the children on the stack
-                                tStack.push(BspTraversalData(interior->GetFront(), frontPolys, tData.mDepth + 1));
-                                tStack.push(BspTraversalData(interior->GetBack(), backPolys, tData.mDepth + 1));
+                                tStack.push(BspTraversalData(interior->GetFront(), frontPolys, tData.mDepth + 1, NULL));
+                                tStack.push(BspTraversalData(interior->GetBack(), backPolys, tData.mDepth + 1, coincident));
                         
                         }
@@ -420 +424 @@
                 }
         }
-}
+}*/
 
 void BspTree::InitTree(int maxPolygons, int maxDepth)
@@ -433 +437 @@
 
 
-int BspTree::AddMesh2Polygons(Mesh *mesh, PolygonContainer &polys)
+int BspTree::AddMesh2Polygons(Mesh *mesh, PolygonContainer &polys, Intersectable *parent)
 {
         FaceContainer::const_iterator fi;
@@ -442 +446 @@
         {
                 Polygon3 *poly = new Polygon3((*fi), mesh);
+                poly->mParent = parent; // set parent intersectable
                 polys.push_back(poly);
                 //if (displayDebug)Debug << *poly << endl;
-                polysNum ++;
+                ++ polysNum;
         }
         return polysNum;
@@ -458 +463 @@
                 {
                         mBox.Include(viewCells[i]->GetBox()); // add to BSP tree aabb
-                        AddMesh2Polygons(viewCells[i]->GetMesh(), polys);
+                        AddMesh2Polygons(viewCells[i]->GetMesh(), polys, viewCells[i]);
                 }
         }
@@ -507 +512 @@
         InitTree(sTermMaxPolygons, sTermMaxDepth);
 
-    bool savedStorePolys = mStorePolys;
-
-        // tree is completely constructed once before 
-        // view cells are inserted one after another => 
-        // global tree optimization possible
-        if (!mIsIncremential) // todo: not incremential does not work
-        {
-                // copy view cell meshes into one big polygon soup
-                PolygonContainer *polys = new PolygonContainer();
-                Copy2PolygonSoup(viewCells, *polys);
-
-                // polygons are stored only during view cell insertion
-                mStorePolys = false;
-
-                // construct tree from viewcell polygons
-                Construct(polys);
-                //Export("bsp.x3d");
-        }
-        
-        //-- insert all viewcells one after another
-        ViewCellContainer::const_iterator it;
-
-        mStorePolys = savedStorePolys;
-        mStat.polys = 0;
-        mStat.splits = 0;
-        mStat.accumDepth = 0;
-
-        long startTime = GetTime();
-//displayDebug = true;
-        counter = 0;
-        Debug << "**** Starting view cell insertion ****" << endl;
-        for (it = viewCells.begin(); it != viewCells.end(); ++ it)
-        {
-                //if ((counter == 12) || (counter == 14)){
-                //Debug << "** inserting view cell " << counter << " **" << endl;
-                InsertViewCell(*it);
-        //}     counter ++;
-        }
-
-        Debug << "**** Finished view cell insertion ****" << endl;
-        Debug << "insertion time: "<< TimeDiff(startTime, GetTime())*1e-3 << "s" << endl;
+        // copy view cell meshes into one big polygon soup
+        PolygonContainer *polys = new PolygonContainer();
+        Copy2PolygonSoup(viewCells, *polys);
+
+        // construct tree from viewcell polygons
+        Construct(polys);
+        //Export("bsp.x3d");
 }
 
@@ -574 +545 @@
         std::stack<BspTraversalData> tStack;
         
-        BspTraversalData tData(new BspLeaf(), polys, 0, true, viewCells);
+        BspTraversalData tData(new BspLeaf(), polys, 0, NULL);
 
         tStack.push(tData);
@@ -585 +556 @@
             tStack.pop();
 
-                //TODO
-                ViewCell *viewCell = NULL;
-
-        /*if (viewCells) // generate new view cell in leaf
-                {
-                        viewCell = new ViewCell();
-                        viewCells->push_back(viewCell);
-                }*/
-
                 // subdivide leaf node
-                BspNode *root = Subdivide(tStack, tData, viewCell);
+                BspNode *root = Subdivide(tStack, tData, viewCells);
 
                 // empty tree => new root corresponding to unbounded space
@@ -608 +570 @@
 
 BspNode *BspTree::Subdivide(BspTraversalStack &tStack, BspTraversalData &tData, 
-                                                        ViewCell *viewCell)
+                                                        ViewCellContainer *viewCells)
 {
         //-- 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
-                if (displayDebug)Debug << "subdivision terminated at depth " << tData.mDepth << ", #polys: " << (int)tData.mPolygons->size() << endl;
+                Debug << "subdivision terminated at depth " << tData.mDepth << ", #polys: " << (int)tData.mPolygons->size() << endl;
 #endif
 
                 EvaluateLeafStats(tData);
 
-            // add view cell if inside object) 
-                if (viewCell && tData.mCoincident && (tData.mCoincident->size() > 0))) // || (tData.mGeometry->size() > 0) // or if there is still geometry left 
-                {
-                        BspLeaf *leaf = dynamic_cast<BspLeaf *>(tData.mNode);
-
+                BspLeaf *leaf = dynamic_cast<BspLeaf *>(tData.mNode);
+
+                //-- new viewcells are generated and added to each leaf
+                if (viewCells)
+                {
+                        ViewCell *viewCell = new ViewCell();
+                        leaf->SetViewCell(viewCell);
+                        viewCells->push_back(viewCell);
+                        Debug << "creating new viewcell" << endl;
+                }
+                //-- add viewcell stored in split polygon
+                else if (tData.mSplitPoly && tData.mSplitPoly->mParent)
+                {
                         if (leaf->GetViewCell())
                                 Debug << "ERROR: leaf already has view cell " << endl;//leaf->mViewCellIdx << endl;
 
-                        //leaf->mViewCellIdx = counter;
-                        //Debug << "insert view cell" << endl;
-
-                        leaf->SetViewCell(coincident[0]->GetParent());
-                }
-
+                        //leaf->mViewCellIdx = counter;Debug << "insert view cell" << endl;
+
+                        leaf->SetViewCell(dynamic_cast<ViewCell *>(tData.mSplitPoly->mParent));
+
+                        // discard split polygon
+                        tData.mNode->GetParent()->ProcessPolygon(tData.mSplitPoly, mStorePolys);
+                }
+        
                 // add or delete remaining polygons
                 tData.mNode->ProcessPolygons(tData.mPolygons, mStorePolys);
-                tData.mNode->ProcessPolygons(tData.coincident, mStorePolys);
-
+                                
                 return tData.mNode;
         }
 
-        tData.mNode->ProcessPolygons(tData.coincident, mStorePolys);
+        // discard the split polygon (not needed if traversal continues)
+        if (tData.mSplitPoly)
+                tData.mNode->GetParent()->ProcessPolygon(tData.mSplitPoly, mStorePolys);
 
         //-- create new subdivided node
         PolygonContainer *backPolys = new PolygonContainer();
         PolygonContainer *frontPolys = new PolygonContainer();
-        PolygonContainer *coincident = new PolygonContainer();
+        Polygon3 *splitPoly = NULL;
         
         BspInterior *interior = SubdivideNode(dynamic_cast<BspLeaf *>(tData.mNode),
@@ -653 +624 @@
                                                                                   frontPolys,
                                                                                   backPolys, 
-                                                                                  coincident);
+                                                                                  &splitPoly);
 
         // push the children on the stack
         // inside information is only propagated with the back leaf
-        tStack.push(BspTraversalData(interior->GetBack(), backPolys, tData.mDepth + 1, coincident));
-        tStack.push(BspTraversalData(interior->GetFront(), frontPolys, tData.mDepth + 1));
+        tStack.push(BspTraversalData(interior->GetFront(), frontPolys, tData.mDepth + 1, NULL));
+        tStack.push(BspTraversalData(interior->GetBack(), backPolys, tData.mDepth + 1, splitPoly));
 
         return interior;
@@ -667 +638 @@
                                                                         PolygonContainer *polys, 
                                                                         PolygonContainer *frontPolys,
-                                                                        PolygonContainer *coincident, 
-                                                                        PolygonContainer *backPolys, bool &inside)
+                                                                        PolygonContainer *backPolys, Polygon3 **splitPoly)
 {
         mStat.nodes += 2;
@@ -682 +652 @@
         int splits = 0;
                 
-        inside = interior->SplitPolygons(polys, frontPolys, backPolys, coincident, splits, mStorePolys);
+        *splitPoly = interior->SplitPolygons(polys, frontPolys, backPolys, splits, mStorePolys);
         
         mStat.splits += splits;

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.h

@@ -144 +144 @@
         */
         PolygonContainer *GetPolygons();
-int mViewCellIdx;
+        /** Stores polygons in node or discards them according to storePolys.
+        */
+        void ProcessPolygons(PolygonContainer *polys, const bool storePolys);
+
+//int mViewCellIdx;
 protected:
-
-        /** Adds or discards polygons according to storePolys.
-        */
-        void ProcessPolygons(PolygonContainer *polys, const bool storePolys);
-
 
         /// parent of this node
@@ -184 +183 @@
                 @param backPolys returns the polygons in the back of the split plane
                 @param splits number of splits
-                @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);
+                @returns split polygon if there is a polygon coincident to the split plane, NULL otherwise
+        */
+        Polygon3 *SplitPolygons(PolygonContainer *polys, 
+                                                        PolygonContainer *frontPolys, 
+                                                    PolygonContainer *backPolys, 
+                                                        int &splits, 
+                                                        bool storePolys = false);
+
+        /** Stores polygon in node or discards them according to storePolys.
+                @param polys the polygons
+                @param storePolys if the polygons should be stored or discarded
+        */
+        void ProcessPolygon(Polygon3 *poly, const bool storePolys);
 
         friend ostream &operator<<(ostream &s, const BspInterior &A)
@@ -194 +202 @@
         }
 
-protected:
+protected:      
         
-        /** Discards or stores polygon in node.
-                @param polys the polygons
-                @param storePolys if the polygons should be stored or discarded
-        */
-        void ProcessPolygon(Polygon3 *poly, const bool storePolys);
 
         /// Splitting plane corresponding to this node
@@ -255 +258 @@
                 /// current depth
                 int mDepth;
+                /// the polygon that drove the split plane computation
+                Polygon3 *mSplitPoly;
                 /// if the node is an inside or outside node with respect to the parent plane
-                bool mIsInside;
+                //bool mIsInside;
                 BspTraversalData() {}
                 
-                BspTraversalData(BspNode *node, PolygonContainer *polys, const int depth, const bool inside): 
-                mNode(node), mPolygons(polys), mDepth(depth), mIsInside(inside) {}
+                BspTraversalData(BspNode *node, PolygonContainer *polys, const int depth, Polygon3 *splitPoly): 
+                mNode(node), mPolygons(polys), mDepth(depth), mSplitPoly(splitPoly) {}
     };
 
@@ -345 +350 @@
             @param tStack current traversal stack
                 @param tData traversal data also holding node to be subdivided
-                @param viewCell the view cell that will be represented with this part of the Bsp tree.
+                @param viewCellContainer if not null, a new viewcell is created and stored in the container
                 @returns new root of the subtree
         */
-        BspNode *Subdivide(BspTraversalStack &tStack, BspTraversalData &tData, ViewCell *viewCell = NULL);
+        BspNode *Subdivide(BspTraversalStack &tStack, BspTraversalData &tData, ViewCellContainer *viewCells = NULL);
 
         /** Selects a splitting plane. 
@@ -358 +363 @@
                 (i.e., possibly more than one leaf).
         */
-        void InsertViewCell(ViewCell *viewCell);
+        //void InsertViewCell(ViewCell *viewCell);
         
         /** Subdivide leaf.
@@ -365 +370 @@
                 @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
-                @param if the polygons are outside or inside with respect to the interior node plane
+                @param splitPoly polygon that is coincident to the split plane, NULL if no such polygon
                 @returns the root of the subdivision
         */
@@ -371 +376 @@
                                                            PolygonContainer *polys, 
                                                            PolygonContainer *frontPolys, 
-                                                           PolygonContainer *backPolys, bool &inside);
+                                                           PolygonContainer *backPolys, Polygon3 **splitPoly);
 
         /** Filters polygons down the tree.
@@ -402 +407 @@
 
         /** Extract polygons of this mesh and add to polygon container.
+                @param mesh the mesh that drives the polygon construction
+                @param parent the parent intersectable this polygon is constructed from
                 @returns number of polygons
         */
-        int AddMesh2Polygons(Mesh *mesh, PolygonContainer &polys);
+        int AddMesh2Polygons(Mesh *mesh, PolygonContainer &polys, Intersectable *parent = NULL);
 
         /** A ray is cast possible intersecting the tree.

trunk/VUT/GtpVisibilityPreprocessor/src/main.cpp

@@ -53 +53 @@
           else
                   p->GenerateViewCells();
-
-          Debug << "Number of view cells: " << p->mViewCells.size() << endl;
   }
 
   p->BuildBspTree();
   p->BspTreeStatistics(Debug);
+  Debug << "Number of view cells: " << p->mViewCells.size() << endl;
   p->Export(filename + "-bsptree.x3d", false, false, true);