Changeset 286 for trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp

Timestamp:

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

Author:

mattausch

Message:

 

File:

• trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp (modified) (20 diffs)

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;