Changeset 574 for trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.cpp

Timestamp:

01/25/06 01:44:46 (18 years ago)

Author:

mattausch

Message:

finished function for view cell construction
removed bsp rays from vspbspmanager

File:

• trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.cpp (modified) (27 diffs)

trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.cpp

@@ -178 +178 @@
 const BspTreeStatistics &VspBspTree::GetStatistics() const
 {
-        return mStat;
+        return mBspStats;
 }
 
@@ -273 +273 @@
                                                    AxisAlignedBox3 *forcedBoundingBox)
 {
-        mStat.nodes = 1;
+        mBspStats.nodes = 1;
         mBox.Initialize();      // initialise BSP tree bounding box
 
@@ -353 +353 @@
                 mTermMinProbability *= mBox.GetVolume();
 
-        mStat.polys = (int)polys.size();
+        mBspStats.polys = (int)polys.size();
 
         cout << "finished" << endl;
@@ -373 +373 @@
         return
                 (sizeof(VspBspTree) +
-                 mStat.Leaves() * sizeof(BspLeaf) +
-                 mStat.Interior() * sizeof(BspInterior) +
-                 mStat.accumRays * sizeof(RayInfo)) / (1024.0f * 1024.0f);
+                 mBspStats.Leaves() * sizeof(BspLeaf) +
+                 mBspStats.Interior() * sizeof(BspInterior) +
+                 mBspStats.accumRays * sizeof(RayInfo)) / (1024.0f * 1024.0f);
 }
 
@@ -405 +405 @@
         tStack.push(tData);
 
-        mStat.Start();
+        mBspStats.Start();
         cout << "Contructing vsp bsp tree ... \n";
 
@@ -439 +439 @@
                                   << TimeDiff(startTime, GetTime())*1e-3 << "s" << endl;
 
-                if (mStat.Leaves() >= nleaves)
+                if (mBspStats.Leaves() >= nleaves)
                 {
                         nleaves += 500;
                                 
-                        cout << "leaves=" << mStat.Leaves() << endl;
+                        cout << "leaves=" << mBspStats.Leaves() << endl;
                         Debug << "needed "
                           << TimeDiff(interTime, GetTime())*1e-3 << " secs to create 500 leaves" << endl;
@@ -453 +453 @@
         cout << "finished\n";
 
-        mStat.Stop();
+        mBspStats.Stop();
 }
 
@@ -463 +463 @@
                  (data.mPvs <= mTermMinPvs)   ||
                  (data.mProbability <= mTermMinProbability) ||
-                 (mStat.Leaves() >= mMaxViewCells) ||
+                 (mBspStats.Leaves() >= mMaxViewCells) ||
                  (data.GetAvgRayContribution() > mTermMaxRayContribution) ||
                  (data.mDepth >= mTermMaxDepth));
@@ -509 +509 @@
                 AddToPvs(leaf, *tData.mRays, sampCon, conSamp);
 
-                mStat.contributingSamples += conSamp;
-                mStat.sampleContributions +=(int) sampCon;
+                mBspStats.contributingSamples += conSamp;
+                mBspStats.sampleContributions +=(int) sampCon;
 
                 //-- store additional info
@@ -526 +526 @@
                         PropagateUpValidity(leaf);
 
-                        ++ mStat.invalidLeaves;
+                        ++ mBspStats.invalidLeaves;
                 }
                 
@@ -572 +572 @@
                 {
                         // terminate branch because of max cost
-                        ++ mStat.maxCostNodes;
+                        ++ mBspStats.maxCostNodes;
             return leaf;
                 }
         }
 
-        mStat.nodes += 2;
+        mBspStats.nodes += 2;
 
         //-- subdivide further
@@ -1160 +1160 @@
                 
                 //! error also computed if cost ratio is missed
-                ++ mStat.splits[axis];
+                ++ mBspStats.splits[axis];
                 isAxisAlignedSplit = true;
         }
@@ -1509 +1509 @@
 
         // store maximal and minimal depth
-        if (data.mDepth > mStat.maxDepth)
-                mStat.maxDepth = data.mDepth;
-
-        if (data.mPvs > mStat.maxPvs)
-                mStat.maxPvs = data.mPvs;
-        
-        if (data.mDepth < mStat.minDepth)
-                mStat.minDepth = data.mDepth;
+        if (data.mDepth > mBspStats.maxDepth)
+                mBspStats.maxDepth = data.mDepth;
+
+        if (data.mPvs > mBspStats.maxPvs)
+                mBspStats.maxPvs = data.mPvs;
+        
+        if (data.mDepth < mBspStats.minDepth)
+                mBspStats.minDepth = data.mDepth;
 
         if (data.mDepth >= mTermMaxDepth)
-                ++ mStat.maxDepthNodes;
+                ++ mBspStats.maxDepthNodes;
         // accumulate rays to compute rays /  leaf
-        mStat.accumRays += (int)data.mRays->size();
+        mBspStats.accumRays += (int)data.mRays->size();
 
         if (data.mPvs < mTermMinPvs)
-                ++ mStat.minPvsNodes;
+                ++ mBspStats.minPvsNodes;
 
         if ((int)data.mRays->size() < mTermMinRays)
-                ++ mStat.minRaysNodes;
+                ++ mBspStats.minRaysNodes;
 
         if (data.GetAvgRayContribution() > mTermMaxRayContribution)
-                ++ mStat.maxRayContribNodes;
+                ++ mBspStats.maxRayContribNodes;
 
         if (data.mProbability <= mTermMinProbability)
-                ++ mStat.minProbabilityNodes;
+                ++ mBspStats.minProbabilityNodes;
         
         // accumulate depth to compute average depth
-        mStat.accumDepth += data.mDepth;
+        mBspStats.accumDepth += data.mDepth;
 
 #ifdef _DEBUG
@@ -1655 +1655 @@
 
 
-void VspBspTree::ValidateTree()
+void VspBspTree::CollapseViewCells()
 {
         stack<BspNode *> nodeStack;
@@ -1664 +1664 @@
         nodeStack.push(mRoot);
         
-        const bool addToUnbounded = false;
-
         while (!nodeStack.empty()) 
         {
@@ -1672 +1670 @@
                 
                 if (node->IsLeaf())
-                {
-                        BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
-
-                        if (!addToUnbounded && node->TreeValid())
+        {
+                        BspViewCell *viewCell = dynamic_cast<BspLeaf *>(node)->GetViewCell();
+
+                        if (!viewCell->GetValid())
                         {
                                 BspViewCell *viewCell = dynamic_cast<BspLeaf *>(node)->GetViewCell();
                         
-                                if (!mViewCellsManager->CheckValidity(viewCell,
-                                                                                                          mViewCellsManager->GetMinPvsSize(), 
-                                                                                                          mViewCellsManager->GetMaxPvsSize()))
+                                vector<BspLeaf *>::const_iterator it, it_end = viewCell->mLeaves.end();
+                                for (it = viewCell->mLeaves.begin();it != it_end; ++ it)
                                 {
-                                        vector<BspLeaf *>::const_iterator it, it_end = viewCell->mLeaves.end();
-                                        for (it = viewCell->mLeaves.begin();it != it_end; ++ it)
-                                        {
-                                                BspLeaf *l = *it;
-                                                
-                                                l->SetTreeValid(false);
-                                                PropagateUpValidity(l);
-                                                
-                                                if (addToUnbounded)
-                                                        l->SetViewCell(GetOrCreateOutOfBoundsCell());
-
-                                                ++ mStat.invalidLeaves;
-                                        }
-
-                                        // add to unbounded view cell or set to invalid
-                                        if (addToUnbounded)
-                                        {
-                                                GetOrCreateOutOfBoundsCell()->GetPvs().AddPvs(viewCell->GetPvs());
-                                                DEL_PTR(viewCell);
-                                        }
-                                        else
-                                        {
-                                                viewCell->SetValid(false);
-                                        }
+                                        BspLeaf *l = *it;
+                                        l->SetViewCell(GetOrCreateOutOfBoundsCell());
+                                        ++ mBspStats.invalidLeaves;
                                 }
+
+                                // add to unbounded view cell
+                                GetOrCreateOutOfBoundsCell()->GetPvs().AddPvs(viewCell->GetPvs());
+                                DEL_PTR(viewCell);
                         }
                 }
@@ -1719 +1699 @@
         }
 
-        Debug << "invalid leaves: " << mStat.invalidLeaves << endl;
-}
+        Debug << "invalid leaves: " << mBspStats.invalidLeaves << endl;
+}
+
+
+void VspBspTree::ValidateTree()
+{
+        stack<BspNode *> nodeStack;
+
+        if (!mRoot)
+                return;
+
+        nodeStack.push(mRoot);
+        
+        mBspStats.invalidLeaves = 0;
+        while (!nodeStack.empty()) 
+        {
+                BspNode *node = nodeStack.top();
+                nodeStack.pop();
+                
+                if (node->IsLeaf())
+                {
+                        BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
+
+                        if (!leaf->GetViewCell()->GetValid())
+                                ++ mBspStats.invalidLeaves;
+
+                        // validity flags don't match => repair
+                        if (leaf->GetViewCell()->GetValid() != leaf->TreeValid())
+                        {
+                                leaf->SetTreeValid(leaf->GetViewCell()->GetValid());
+                                PropagateUpValidity(leaf);
+                        }
+                }
+                else
+                {
+                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
+                
+                        nodeStack.push(interior->GetFront());
+                        nodeStack.push(interior->GetBack());
+                }
+        }
+
+        Debug << "invalid leaves: " << mBspStats.invalidLeaves << endl;
+}
+
 
 
@@ -1784 +1807 @@
         int splits = 0;
 
-        while (!rays.empty())
-        {
-                RayInfo bRay = rays.back();
-                rays.pop_back();
-
+        RayInfoContainer::const_iterator it, it_end = rays.end();
+
+        for (it = rays.begin(); it != it_end; ++ it)
+        {
+                RayInfo bRay = *it;
+                
                 VssRay *ray = bRay.mRay;
                 float t;
@@ -2213 +2237 @@
         int splits = 0;
 
-        while (!polys.empty())
-        {
-                Polygon3 *poly = polys.back();
-                polys.pop_back();
+        PolygonContainer::const_iterator it, it_end = polys.end();
+
+        for (it = polys.begin(); it != polys.end(); ++ it)      
+        {
+                Polygon3 *poly = *it;
 
                 // classify polygon
@@ -2632 +2657 @@
                 BspLeaf *leaf = *it;
                 
-                /// create leaf pvs (needed for post processing
+                /// create leaf pvs (needed for post processing)
                 leaf->mPvs = new ObjectPvs(leaf->GetViewCell()->GetPvs());
 
@@ -2674 +2699 @@
 int VspBspTree::CollectMergeCandidates(const VssRayContainer &rays)
 {
-        vector<BspRay *> bspRays;
-
         ViewCell::NewMail();
         long startTime = GetTime();
-        ConstructBspRays(bspRays, rays);
-        Debug << (int)bspRays.size() << " bsp rays constructed in " 
-                  << TimeDiff(startTime, GetTime()) * 1e-3f << " secs" << endl;
-
+        
         map<BspLeaf *, vector<BspLeaf*> > neighborMap;
-        vector<BspIntersection>::const_iterator iit;
+        ViewCellContainer::const_iterator iit;
 
         int numLeaves = 0;
@@ -2689 +2709 @@
         BspLeaf::NewMail();
 
-        for (int i = 0; i < (int)bspRays.size(); ++ i)
+        for (int i = 0; i < (int)rays.size(); ++ i)
         {  
-                BspRay *ray = bspRays[i];
+                VssRay *ray = rays[i];
         
                 // traverse leaves stored in the rays and compare and 
                 // merge consecutive leaves (i.e., the neighbors in the tree)
-                if (ray->intersections.size() < 2)
+                if (ray->mViewCells.size() < 2)
                         continue;
           
-                iit = ray->intersections.begin();
-                BspLeaf *leaf = (*(iit ++)).mLeaf;
+                iit = ray->mViewCells.begin();
+                BspViewCell *bspVc = dynamic_cast<BspViewCell *>(*(iit ++));
+                BspLeaf *leaf = bspVc->mLeaves[0];
                 
                 // create leaf pvs (needed for post processing)
@@ -2715 +2736 @@
                 // traverse intersections 
                 // consecutive leaves are neighbors => add them to queue
-                for (; iit != ray->intersections.end(); ++ iit)
+                for (; iit != ray->mViewCells.end(); ++ iit)
                 {
                         // next pair
                         BspLeaf *prevLeaf = leaf;
-            leaf = (*iit).mLeaf;
+                        bspVc = dynamic_cast<BspViewCell *>(*iit);
+            leaf = bspVc->mLeaves[0];
 
                         // view space not valid or same view cell
@@ -2781 +2803 @@
         Debug << "overall cost: " << BspMergeCandidate::sOverallCost << endl;
 
-        CLEAR_CONTAINER(bspRays);
-
         //-- collect the leaves which haven't been found by ray casting
         if (0)
@@ -2857 +2877 @@
         mergeStats.Start();
         
-        //BspMergeCandidate::sOverallCost = mBox.SurfaceArea() * mStat.maxPvs;
+        //BspMergeCandidate::sOverallCost = mBox.SurfaceArea() * mBspStats.maxPvs;
         long startTime = GetTime();
 
-        cout << "collecting merge candidates ... ";
+        cout << "collecting merge candidates ... " << endl;
         
         if (mUseRaysForMerge)
@@ -2880 +2900 @@
 
         // number of view cells withouth the invalid ones
-        int nViewCells = mStat.Leaves() - mStat.invalidLeaves;
+        int nViewCells = mBspStats.Leaves() - mBspStats.invalidLeaves;
         
         
@@ -3370 +3390 @@
 void VspBspTree::PropagateUpValidity(BspNode *node)
 {
-        while (!node->IsRoot() && node->GetParent()->TreeValid())
-        {
-                node = node->GetParent();
-                node->SetTreeValid(false);
+        const bool isValid = node->TreeValid();
+
+        // propagative up invalid flag until only invalid nodes exist over this node
+        if (!isValid)
+        {
+                while (!node->IsRoot() && node->GetParent()->TreeValid())
+                {
+                        node = node->GetParent();
+                        node->SetTreeValid(false);
+                }
+        }
+        else
+        {
+                // propagative up valid flag until one of the subtrees is invalid
+                while (!node->IsRoot() && !node->TreeValid())
+                {
+            node = node->GetParent();
+                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
+                        
+                        // the parent is valid iff both leaves are valid
+                        node->SetTreeValid(interior->GetBack()->TreeValid() && 
+                                                           interior->GetFront()->TreeValid());
+                }
         }
 }