Changeset 582 for trunk/VUT/GtpVisibilityPreprocessor/src/ViewCell.cpp

Timestamp:

02/02/06 19:16:39 (18 years ago)

Author:

mattausch

Message:

fixed bug in mergueue to find root of merge and sort out doube view cells

File:

• trunk/VUT/GtpVisibilityPreprocessor/src/ViewCell.cpp (modified) (35 diffs)

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCell.cpp

@@ -308 +308 @@
 {
         environment->GetBoolValue("ViewCells.Visualization.exportMergedViewCells", mExportMergedViewCells);
+        environment->GetFloatValue("ViewCells.maxStaticMemory", mMaxMemory);
 
         //-- merge options
@@ -314 +315 @@
         environment->GetFloatValue("ViewCells.PostProcess.maxCostRatio", mMergeMaxCostRatio);
         
+
+        Debug << "========= view cell tree options ================\n";
+        Debug << "minimum view cells: " << mMergeMinViewCells << endl;
+        Debug << "max cost ratio: " << mMergeMaxCostRatio << endl;
+        Debug << "max memory: " << mMaxMemory << endl;
+
         MergeCandidate::sRenderCostWeight = mRenderCostWeight;
 
         mStats.open("mergeStats.log");
+}
+
+
+// return memory usage in MB
+float ViewCellsTree::GetMemUsage() const
+{
+        return 0;
+                /*(sizeof(ViewCellsTree) +
+                 mBspStats.Leaves() * sizeof(BspLeaf) +
+                 mBspStats.Interior() * sizeof(BspInterior) +
+                 mBspStats.accumRays * sizeof(RayInfo)) / (1024.0f * 1024.0f);*/
 }
 
@@ -387 +405 @@
                                                                           const ObjectContainer &objects)
 {
-        // number of view cells equals the number of leaves 
-        // (without the invalid ones )
-        //mNumViewCells = mBspStats.Leaves();//- mBspStats.invalidLeaves;
-        mNumViewCells = (int)mViewCellsManager->GetViewCells().size();
+        mNumActiveViewCells = (int)mViewCellsManager->GetViewCells().size();
 
         float variance = 0;
@@ -432 +447 @@
         // view cell manager. They will change with
         // subsequent merges
-        ViewCellContainer &viewCells = mViewCellsManager->GetViewCells();
+        ViewCellContainer &activeViewCells = mViewCellsManager->GetViewCells();
 
 
@@ -455 +470 @@
         float realExpectedCost = mExpectedCost;
         float realAvgRenderCost = mAvgRenderCost;
-        int realNumViewCells = mNumViewCells;
+        int realNumActiveViewCells = mNumActiveViewCells;
         
         // maximal ratio of old expected render cost to expected render
@@ -461 +476 @@
         float avgCostMaxDeviation;
         int maxMergesPerPass;
-        int numActiveViewCells = 0;
+        int numMergedViewCells = 0;
 
         environment->GetIntValue("ViewCells.PostProcess.maxMergesPerPass", maxMergesPerPass);
@@ -472 +487 @@
         //-- use priority queue to merge leaf pairs
 
-        while (!mMergeQueue.empty() && (realNumViewCells > mMergeMinViewCells))
+        while (!mMergeQueue.empty())// && (realNumActiveViewCells > mMergeMinViewCells))
         {
                 //-- reset merge queue if the ratio of current expected cost / real expected cost
@@ -495 +510 @@
                         mExpectedCost = realExpectedCost;
                         mAvgRenderCost = realAvgRenderCost;
-                        mNumViewCells = realNumViewCells;
+                        mNumActiveViewCells = realNumActiveViewCells;
                         
-                        const int numActiveViewCells = UpdateMergedViewCells(viewCells);
-
+                        const int numMergedViewCells = UpdateActiveViewCells(activeViewCells);
+                
+                        // recompute priorities => reset render cost
                     ResetMergeQueue();
 
@@ -509 +525 @@
                         if (mExportMergedViewCells)
                         {
-                                ExportMergedViewCells(viewCells, objects, numActiveViewCells);
+                                ExportMergedViewCells(activeViewCells, objects, numMergedViewCells);
                         }
                 }
@@ -524 +540 @@
                 mMergeQueue.pop();
         
-                // both view cells equal!
+                // both view cells equal
+                // NOTE: do I really still need this? probably cannot happen!!
                 if (mc.mLeftViewCell == mc.mRightViewCell)
                         continue;
@@ -532 +549 @@
                         ViewCell::NewMail();
                                                 
-                        -- realNumViewCells;
+                        -- realNumActiveViewCells;
                         ++ mergeStats.merged;
                         ++ mergedPerPass;
@@ -547 +564 @@
                         mDeviation += mc.GetDeviationIncr();
                                                 
-                        realExpectedCost = totalCost / (float)realNumViewCells;
+                        realExpectedCost = totalCost / (float)realNumActiveViewCells;
                         
                         const float currentMergeCost = mc.GetMergeCost();
@@ -557 +574 @@
 
                         totalPvs += pvsDiff;
+
                         // set timestamp
                         mergedVc->SetTimeStamp(mergeStats.merged);
 
-                        realAvgRenderCost = (float)totalPvs / (float)realNumViewCells;
+                        realAvgRenderCost = (float)totalPvs / (float)realNumActiveViewCells;
 #if VC_HISTORY
                         if (mc.mLeftViewCell->IsSibling(mc.mRightViewCell))
@@ -566 +584 @@
 #endif
                         if (((mergeStats.merged % statsOut) == 0) || 
-                                (realNumViewCells == mMergeMinViewCells))
+                                (realNumActiveViewCells == mMergeMinViewCells))
                         {
                                 cout << "merged " << mergeStats.merged << " view cells" << endl;
@@ -573 +591 @@
                                         << "#Pass\n" << pass << endl
                                         << "#Merged\n" << mergeStats.merged << endl 
-                                        << "#Viewcells\n" << realNumViewCells << endl 
+                                        << "#Viewcells\n" << realNumActiveViewCells << endl 
                                         << "#CurrentCost\n" << currentMergeCost << endl
                                         << "#RelativeCost\n" << currentMergeCost / mOverallCost << endl
@@ -584 +602 @@
                                         << "#AvgRenderCost\n" << mAvgRenderCost << endl
                                         << "#expectedCostRatio\n" << mExpectedCost / realExpectedCost << endl
-                                        << "#Deviation\n" << mDeviation / (float)realNumViewCells << endl
+                                        << "#Deviation\n" << mDeviation / (float)realNumActiveViewCells << endl
                                         << "#TotalDeviation\n" << mDeviation<< endl;
                         }
@@ -592 +610 @@
                         // merge candidate not valid, because one of the leaves was already
                         // merged with another one => validate and reinsert into queue
-                        SetMergeCandidateValid(mc);
-                        mMergeQueue.push(mc);
+                        if (ValidateMergeCandidate(mc))
+                        {
+                                EvalMergeCost(mc);
+                                mMergeQueue.push(mc);
+                        }
                 }
         }
@@ -600 +621 @@
         mExpectedCost = realExpectedCost;
         mAvgRenderCost = realAvgRenderCost;
-        mNumViewCells = realNumViewCells;
-
-        UpdateMergedViewCells(viewCells);
+        mNumActiveViewCells = realNumActiveViewCells;
+
+        UpdateActiveViewCells(activeViewCells);
         ResetMergeQueue();
-
 
         // create a root node if the merge was not done till root level,
         // else take the single node as new root
-        if ((int)viewCells.size() > 1)
-        {
-                Debug << "here888" << endl;
-                ViewCellInterior *root = new ViewCellInterior();
+        if ((int)activeViewCells.size() > 1)
+        {
+                Debug << "creating root of view cell hierarchy for " << (int)activeViewCells.size() << " view cells" << endl;
+                for (int i = 0;  i < activeViewCells.size(); ++ i){
+                        Debug << "here233 " << activeViewCells[i]->GetParent() << endl;
+                        Debug << "here233 " << activeViewCells[i] << endl;
+                }
+                ViewCellInterior *root = mViewCellsManager->MergeViewCells(activeViewCells);
 
                 root->SetTimeStamp(mergeStats.merged + 1);
-
-                ViewCellContainer::const_iterator it, it_end = viewCells.end();
-                for (it = viewCells.begin(); it != it_end; ++ it)
-                        root->SetupChildLink(*it);
-
                 mRoot = root;
         }
-        else if ((int)viewCells.size() == 1)
-        {
-                Debug << "here555" << endl;
-                mRoot = viewCells[0];
+        else if ((int)activeViewCells.size() == 1)
+        {
+                Debug << "setting root of the merge history" << endl;
+                mRoot = activeViewCells[0];
         }
 
@@ -668 +687 @@
                 
                 // recalculate cost
-                SetMergeCandidateValid(mc);
-                buf.push_back(mc);                              
+                if (ValidateMergeCandidate(mc))
+                {
+                        EvalMergeCost(mc);
+                        buf.push_back(mc);                              
+                }
         }
 
@@ -684 +706 @@
 
 
-int ViewCellsTree::UpdateMergedViewCells(ViewCellContainer &viewCells)
-{
-        int numActiveViewCells = 0;
-
+int ViewCellsTree::UpdateActiveViewCells(ViewCellContainer &viewCells)
+{
+        int numMergedViewCells = 0;
+
+        Debug << "updating active vc: " << viewCells.size() << endl;
         // find all already merged view cells and remove them from view cells
+                
+        // sort out all view cells which are not active anymore, i.e., they
+        // were already part of a merge
         int i = 0;
 
+        ViewCell::NewMail();
+
         while (1)
         {
-                while (!viewCells.empty() && (!viewCells.back()->GetParent()))
+                // remove all merged view cells from end of the vector
+                while (!viewCells.empty() && (viewCells.back()->GetParent()))
                 {
                         viewCells.pop_back();
@@ -703 +732 @@
 
                 // already merged view cell, put it to end of vector
-                if (!viewCells[i]->IsRoot())
+                if (viewCells[i]->GetParent())
                         swap(viewCells[i], viewCells.back());
                 
-                ++ i;
-        }
+                viewCells[i ++]->Mail();
+        }
+
 
         // add new view cells to container only if they don't have been 
         // merged in the mean time
-        while (!mActiveViewCells.empty())
-        {
-                if (!mActiveViewCells.back()->GetParent())
-                {
-                        viewCells.push_back(mActiveViewCells.back());
-                        ++ numActiveViewCells;
-                }
-
-                mActiveViewCells.pop_back();
-        }
+        ViewCellContainer::const_iterator ait, ait_end = mMergedViewCells.end();
+        for (ait = mMergedViewCells.begin(); ait != ait_end; ++ ait)
+        {
+                ViewCell *vc = mMergedViewCells.back();
+                if (!vc->GetParent() && !vc->Mailed())
+                {
+                        vc->Mail();
+                        viewCells.push_back(vc);
+                        ++ numMergedViewCells;
+                }
+        }
+
+        mMergedViewCells.clear();
 
         // update standard deviation
@@ -737 +770 @@
 
         mDeviation /= (float)viewCells.size();
-
-        // clear the view cells which were merged
-        mInactiveViewCells.clear();
-        // remove the new view cells
-        mActiveViewCells.clear();
-
-        return numActiveViewCells;
+        
+        return numMergedViewCells;
 }
 
@@ -749 +777 @@
 void ViewCellsTree::ExportMergedViewCells(ViewCellContainer &viewCells, 
                                                                                   const ObjectContainer &objects,
-                                                                                  const int numActiveViewCells)
+                                                                                  const int numMergedViewCells)
 {
         
@@ -771 +799 @@
                         // assign special material to new view cells
                         // new view cells are on the back of container
-                        if (i ++ >= (viewCells.size() - numActiveViewCells))
+                        if (i ++ >= (viewCells.size() - numMergedViewCells))
                         {
                                 //m = RandomMaterial();
@@ -798 +826 @@
 ViewCellInterior *ViewCellsTree::MergeViewCells(ViewCell *l, ViewCell *r, int &pvsDiff) //const
 {
-        ViewCellInterior *vc = mViewCellsManager->MergeViewCells(*l, *r);
+        ViewCellInterior *vc = mViewCellsManager->MergeViewCells(l, r);
 
         // if merge was unsuccessful
@@ -817 +845 @@
 
 
-        //-- clean up old view cells
-        if (0 && !mExportMergedViewCells)
-        {
-                DEL_PTR(l);
-                DEL_PTR(r);
-        }
-        else 
-        {
-                mInactiveViewCells.push_back(l);
-                mInactiveViewCells.push_back(r);
-                
-                mActiveViewCells.push_back(vc);
-        }
+        // new view cells are stored in this vector
+        mMergedViewCells.push_back(vc);
 
         pvsDiff = vc->GetPvs().GetSize() - pvs1 - pvs2;
@@ -1018 +1035 @@
         
         return mRenderCostWeight * (renderCost1 + renderCost2) +
-                  (1.0f - mRenderCostWeight) * (dev1 + dev2) / (float)mNumViewCells;
+                  (1.0f - mRenderCostWeight) * (dev1 + dev2) / (float)mNumActiveViewCells;
 }
 
@@ -1112 +1129 @@
         {
                 const float penalty = EvalPvsPenalty(vc->GetPvs().GetSize(), lower, upper);
-                return (mAvgRenderCost - penalty) * (mAvgRenderCost - penalty) / (float)mNumViewCells;
+                return (mAvgRenderCost - penalty) * (mAvgRenderCost - penalty) / (float)mNumActiveViewCells;
         }
 
@@ -1128 +1145 @@
         {
                 const float penalty = EvalPvsPenalty(vc->GetPvs().GetSize(), lower, upper);
-                return fabs(mAvgRenderCost - penalty) / (float)mNumViewCells;
+                return fabs(mAvgRenderCost - penalty) / (float)mNumActiveViewCells;
         }
 
@@ -1153 +1170 @@
 
 
-void ViewCellsTree::SetMergeCandidateValid(MergeCandidate &mc) const
+bool ViewCellsTree::ValidateMergeCandidate(MergeCandidate &mc) const
 {
         while (mc.mLeftViewCell->mParent)
@@ -1165 +1182 @@
         }
 
-        EvalMergeCost(mc);
+        return mc.mLeftViewCell != mc.mRightViewCell;
 }
 
@@ -1210 +1227 @@
 
         if (1)
-                newDev = fabs(mAvgRenderCost - newPenalty) / (float)mNumViewCells;
+                newDev = fabs(mAvgRenderCost - newPenalty) / (float)mNumActiveViewCells;
         else
-                newDev = fabs(mExpectedCost - newCost) / (float)mNumViewCells;
+                newDev = fabs(mExpectedCost - newCost) / (float)mNumActiveViewCells;
         
         oldDev = GetDeviation(vc1) + GetDeviation(vc2);
@@ -1251 +1268 @@
         TraversalQueue tqueue;
         tqueue.push(mRoot);
-        Debug << "here34 " << numViewCells << endl;
+        
         while (!tqueue.empty())
         {
                 ViewCell *vc = tqueue.top();
-                tqueue.pop();
-                Debug << "here7 " << vc->GetTimeStamp() << endl;
-                if (vc->IsLeaf())
-                {
-                        Debug << "here6" << endl;
+                
+                // save the view cells if it is a leaf or if enough view cells have already been traversed
+                // because of the priority queue, this will be the optimal set of v
+                if (vc->IsLeaf() || ((viewCells.size() + tqueue.size()) >= numViewCells))
+                {
                         viewCells.push_back(vc);
                 }
-                else if (viewCells.size() + tqueue.size() < numViewCells)
-                {       Debug << "here4" << endl;
+                else 
+                {       
                         ViewCellInterior *interior = dynamic_cast<ViewCellInterior *>(vc);
 
@@ -1273 +1290 @@
                         }
                 }
+
+                tqueue.pop();
         }
 }
@@ -1390 +1409 @@
 bool MergeCandidate::IsValid() const
 {
-        return !(mLeftViewCell->mParent && mRightViewCell->mParent);
+        return !(mLeftViewCell->mParent || mRightViewCell->mParent);
 }