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

Timestamp:

02/03/06 23:02:07 (18 years ago)

Author:

mattausch

Message:

changed shuffling (but does not work yet...)

File:

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

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCell.cpp

@@ -279 +279 @@
 
 
+void ViewCellInterior::RemoveChildLink(ViewCell *l)
+{
+        // erase leaf from old view cell
+        ViewCellContainer::iterator it = mChildren.begin();
+
+        for (; (*it) != l; ++ it);
+        if (it == mChildren.end())
+                Debug << "error" << endl;
+        else
+                mChildren.erase(it);
+}
 
 /************************************************************************/
@@ -335 +346 @@
         environment->GetIntValue("ViewCells.PostProcess.minViewCells", mMergeMinViewCells);
         environment->GetFloatValue("ViewCells.PostProcess.maxCostRatio", mMergeMaxCostRatio);
-        
+        environment->GetBoolValue("ViewCells.PostProcess.refine", mRefineViewCells);    
+
 
         Debug << "========= view cell tree options ================\n";
@@ -341 +353 @@
         Debug << "max cost ratio: " << mMergeMaxCostRatio << endl;
         Debug << "max memory: " << mMaxMemory << endl;
+        Debug << "refining view cells: " << mRefineViewCells << endl;
 
         MergeCandidate::sRenderCostWeight = mRenderCostWeight;
@@ -504 +517 @@
         cout << "actual merge starts now ... " << endl;
         
-        //ResetMergeQueue();
 
         //-- use priority queue to merge leaf pairs
@@ -535 +547 @@
                         const int numMergedViewCells = UpdateActiveViewCells(activeViewCells);
                 
-                        // recompute priorities => reset render cost
-                    ResetMergeQueue();
+                        // refines the view cells
+                        // then priorities are recomputed
+                        // and the candidates are put back into merge queue
+                        if (mRefineViewCells)
+                                RefineViewCells(rays, objects);
+                        else
+                                ResetMergeQueue();
 
                         
@@ -645 +662 @@
 
         UpdateActiveViewCells(activeViewCells);
-        ResetMergeQueue();
+
+        // refine view cells and reset costs
+        if (mRefineViewCells)
+                RefineViewCells(rays, objects);
+        else
+                ResetMergeQueue();
 
         // create a root node if the merge was not done till root level,
@@ -652 +674 @@
         {
                 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;
+                /*for (int i = 0;  i < activeViewCells.size(); ++ i){
+                        Debug << "parent " << activeViewCells[i]->GetParent() << endl;
+                        Debug << "viewcell " << activeViewCells[i] << endl;*/
                 }
                 ViewCellInterior *root = mViewCellsManager->MergeViewCells(activeViewCells);
@@ -845 +867 @@
 
 // TODO: should be done in view cells manager
-ViewCellInterior *ViewCellsTree::MergeViewCells(ViewCell *l, ViewCell *r, int &pvsDiff) //const
+ViewCellInterior *ViewCellsTree::MergeViewCells(ViewCell *l, 
+                                                                                                ViewCell *r, 
+                                                                                                int &pvsDiff) //const
 {
         ViewCellInterior *vc = mViewCellsManager->MergeViewCells(l, r);
@@ -876 +900 @@
 
 
-
-int ViewCellsTree::RefineViewCells(const VssRayContainer &rays, const ObjectContainer &objects)
+int ViewCellsTree::RefineViewCells(const VssRayContainer &rays, 
+                                                                   const ObjectContainer &objects)
 {
         Debug << "refining " << (int)mMergeQueue.size() << " candidates " << endl;
-        
+
+        // intermediate buffer for shuffled view cells
+        vector<MergeCandidate> buf;
+        buf.reserve(mMergeQueue.size());
+                        
         // Use priority queue of remaining leaf pairs 
         // The candidates either share the same view cells or
@@ -888 +916 @@
         // leaf is made part of the other view cell. It is tested if the
         // remaining view cells are "better" than the old ones.
-        //
-        // repeat the merging test numPasses times. For example, it could be
-        // that a shuffle only makes sense if another pair was shuffled before.
-        // Therefore we keep two queues and shift the merge candidates between
-        // those two queues until numPasses is reached
-        
-        queue<MergeCandidate> queue1;
-        queue<MergeCandidate> queue2;
-
-        queue<MergeCandidate> *shuffleQueue = &queue1;
-        queue<MergeCandidate> *backQueue = &queue2;
-
-        while (!mMergeQueue.empty())
-        {
-                MergeCandidate mc = mMergeQueue.top();
-                shuffleQueue->push(mc);
-                mMergeQueue.pop();
-        }
-
-        const int numPasses = 5;
+        
+        const int numPasses = 3;
         int pass = 0;
         int passShuffled = 0;
@@ -915 +925 @@
         ViewCell::NewMail();
         
-        do
-        {
-                passShuffled = 0;
-                while (!shuffleQueue->empty())
-                {
-                        MergeCandidate mc = shuffleQueue->front();
-                        shuffleQueue->pop();
-
-                        // both view cells equal or already shuffled
-                        if ((mc.GetLeftViewCell() == mc.GetRightViewCell()) || 
-                                (GetSize(mc.GetLeftViewCell()) == 1) || 
-                                (GetSize(mc.GetRightViewCell()) == 1))
-                        {                       
-                                continue;
+        while (!mMergeQueue.empty())
+        {
+                MergeCandidate mc = mMergeQueue.top();
+                mMergeQueue.pop();
+
+                // both view cells equal or already shuffled
+                if ((mc.GetLeftViewCell() == mc.GetRightViewCell()) ||
+                        mc.GetLeftViewCell()->IsLeaf() || mc.GetRightViewCell()->IsLeaf())
+                {                       
+                        continue;
+                }
+
+                // candidate for shuffling
+                const bool wasShuffled = ShuffleLeaves(mc);
+                
+                // shuffled or put into other queue for further refine
+                if (wasShuffled)
+                {
+                        ++ passShuffled;
+
+                        if (!mc.GetLeftViewCell()->Mailed())
+                        {
+                                mc.GetLeftViewCell()->Mail();
+                                ++ shuffledViewCells;
                         }
-
-                        // candidate for shuffling
-                        const bool wasShuffled = 
-                                ShuffleLeaves(mc.GetLeftViewCell(), mc.GetRightViewCell());
-                
-                        // shuffled or put into other queue for further refine
-                        if (wasShuffled)
+                        if (!mc.GetRightViewCell()->Mailed())
                         {
-                                ++ passShuffled;
-
-                                if (!mc.GetLeftViewCell()->Mailed())
-                                {
-                                        mc.GetLeftViewCell()->Mail();
-                                        ++ shuffledViewCells;
-                                }
-                                if (!mc.GetRightViewCell()->Mailed())
-                                {
-                                        mc.GetRightViewCell()->Mail();
-                                        ++ shuffledViewCells;
-                                }
+                                mc.GetRightViewCell()->Mail();
+                                ++ shuffledViewCells;
                         }
-                        else
-                        {
-                                backQueue->push(mc);
-                        }
-                }
-
-                // now the back queue is the current shuffle queue
-                swap(shuffleQueue, backQueue);
-                shuffled += passShuffled;
-                Debug << "shuffled in pass: " << passShuffled << endl;
-        }
-        while (((++ pass) < numPasses) && passShuffled);
-
-        while (!shuffleQueue->empty())
-        {
-                shuffleQueue->pop();
-        }
+                }
+
+                // put back into intermediate vector
+                buf.push_back(mc);
+        }
+
+
+        //-- in the end, the candidates must be in the mergequeue again
+        //   with the correct cost
+
+        cout << "reset merge queue ... ";
+        
+        
+        vector<MergeCandidate>::const_iterator bit, bit_end = buf.end();
+        
+        for (bit = buf.begin(); bit != bit_end; ++ bit)
+        {    
+                MergeCandidate mc = *bit;
+                // recalculate cost
+                if (ValidateMergeCandidate(mc))
+                {
+                        EvalMergeCost(mc);
+                        mMergeQueue.push(mc);   
+                }
+        }
+
+        cout << "finished" << endl;
 
         return shuffledViewCells;
@@ -1003 +1017 @@
 
 float ViewCellsTree::EvalShuffleCost(ViewCell *leaf, 
-                                                                         ViewCell *vc1, 
-                                                                         ViewCell *vc2) const
+                                                                         ViewCellInterior *vc1, 
+                                                                         ViewCellInterior *vc2) const
 {
         //const int pvs1 = SubtractedPvsSize(vc1, leaf, *leaf->mPvs);
@@ -1061 +1075 @@
 
 void ViewCellsTree::ShuffleLeaf(ViewCell *leaf,
-                                                                ViewCell *vc1, 
-                                                                ViewCell *vc2) const
+                                                                ViewCellInterior *vc1, 
+                                                                ViewCellInterior *vc2) const
 {
         // compute new pvs and area
+        // TODO change
         vc1->GetPvs().SubtractPvs(leaf->GetPvs());
         vc2->GetPvs().AddPvs(leaf->GetPvs());
@@ -1079 +1094 @@
         }
 
-        // TODO
-#if VC_HISTORY
-        /// add to second view cell
-        vc2->mLeaves.push_back(leaf);
-
-        // erase leaf from old view cell
-        vector<BspLeaf *>::iterator it = vc1->mLeaves.begin();
-
-        for (; *it != leaf; ++ it);
-        vc1->mLeaves.erase(it);
-
-        /*vc1->GetPvs().mEntries.clear();
-        for (; it != vc1->mLeaves.end(); ++ it)
-        {
-                if (*it == leaf)
-                        vc1->mLeaves.erase(it);
-                else
-                        vc1->GetPvs().AddPvs(*(*it)->mPvs);
-        }*/
-
-        leaf->SetViewCell(vc2); // finally change view cell
-#endif
-}
-
-
-bool ViewCellsTree::ShuffleLeaves(ViewCell *l, ViewCell *r) const
+        
+        ViewCellInterior *p = dynamic_cast<ViewCellInterior *>(leaf->GetParent());
+
+        p->RemoveChildLink(leaf);
+        vc2->SetupChildLink(leaf);
+}
+
+
+bool ViewCellsTree::ShuffleLeaves(MergeCandidate &mc) const
 {
         float cost1, cost2;
 
+        ViewCellInterior *vc1 = dynamic_cast<ViewCellInterior *>(mc.GetLeftViewCell());
+        ViewCellInterior *vc2 = dynamic_cast<ViewCellInterior *>(mc.GetRightViewCell());
+
+        ViewCell *leaf1 = mc.GetInitialLeftViewCell();
+        ViewCell *leaf2 = mc.GetInitialRightViewCell();
+
         //-- first test if shuffling would decrease cost
-        cost1 = GetCostHeuristics(l);
-        cost2 = GetCostHeuristics(r);
+        cost1 = GetCostHeuristics(vc1);
+        cost2 = GetCostHeuristics(vc2);
 
         const float oldCost = cost1 + cost2;
@@ -1117 +1121 @@
         float shuffledCost2 = Limits::Infinity;
 
-        // the view cell should not be empty after the shuffle
-#if VC_HISTORY
-        shuffledCost1 = EvalShuffleCost(l, vc1, vc2);
-        /shuffledCost2 = EvalShuffleCost(r, vc2, vc1);
+        if (leaf1)
+                shuffledCost1 = EvalShuffleCost(leaf1, vc1, vc2);       
+        if (leaf2)
+                shuffledCost2 = EvalShuffleCost(leaf2, vc2, vc1);
 
         // if cost of shuffle is less than old cost => shuffle
@@ -1126 +1130 @@
                 return false;
         
-        
         if (shuffledCost1 < shuffledCost2)
         {
-                ShuffleLeaf(leaf1, vc1, vc2);
-                leaf1->Mail();
+                if (leaf1)
+                        ShuffleLeaf(leaf1, vc1, vc2);
+                mc.mInitialLeftViewCell = NULL;
         }
         else
         {
-                ShuffleLeaf(leaf2, vc2, vc1);
-                leaf2->Mail();
-        }
-#endif
+                if (leaf2)
+                        ShuffleLeaf(leaf2, vc2, vc1);
+                mc.mInitialRightViewCell = NULL;
+        }
+
         return true;
 }
@@ -1529 +1534 @@
 mDeviationIncr(0),
 mLeftViewCell(l),
-mRightViewCell(r)
+mRightViewCell(r),
+mInitialLeftViewCell(l),
+mInitialRightViewCell(r)
 {
         //EvalMergeCost();