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

Timestamp:

01/27/06 16:27:22 (18 years ago)

Author:

mattausch

Message:

started to include variance into the measures

File:

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

trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.cpp

@@ -29 +29 @@
 const float VspBspTree::sBalancedRaysTable[] = {1, -1, 0, 0, 0};
 
-int BspMergeCandidate::sMaxPvsSize = 0;
+ViewCellsManager *BspMergeCandidate::sViewCellsManager = NULL;
+//int BspMergeCandidate::sMaxPvsSize = 0;
 //int BspMergeCandidate::sMinPvsSize = 0;
 
@@ -37 +38 @@
 
 float BspMergeCandidate::sOverallCost = 0;
+float BspMergeCandidate::sExpectedCost = 0;
+float BspMergeCandidate::sVariance = 0;
+float BspMergeCandidate::sRenderCostWeight = 0.5f;
 bool BspMergeCandidate::sUseArea = false;
-
-
-int BspMergeCandidate::sUpperPvsLimit = 120;
-int BspMergeCandidate::sLowerPvsLimit = 5;
-
-
-
-/********************************************************************/
-/*                  class VspBspTree implementation                 */
-/********************************************************************/
+int BspMergeCandidate::sNumViewCells = 0;
+
+//int upperPvsLimit = 120;
+//int lowerPvsLimit = 5;
+
+
+
+// pvs penalty can be different from pvs size
+inline float EvalPvsPenalty(const int pvs, 
+                                                        const int lower,
+                                                        const int upper)
+{
+        // clamp to minmax values
+        if (pvs < lower)
+                return (float)lower;
+        if (pvs > upper)
+                return (float)upper;
+
+        return (float)pvs;
+}
+
+
+// penalty for pvs durint merge
+inline float EvalPvsPenaltyForMerge(const int pvs, 
+                                                                        const int lower,
+                                                                        const int upper)
+{
+        // clamp to minmax values
+        if (pvs < lower)
+                return (float)lower;
+        if (pvs > upper)
+                return (float)upper;
+
+        return (float)pvs;
+}
+
+
+/**********************************************************************/
+/*                  class VspBspTree implementation                   */
+/**********************************************************************/
 
 
@@ -192 +226 @@
         DEL_PTR(mSplitCandidates);
 }
+
 
 int VspBspTree::AddMeshToPolygons(Mesh *mesh,
@@ -1070 +1105 @@
 #endif
 
+        
         const float newCost = pvsBack * pBack + pvsFront * pFront;
         const float oldCost = (float)pvsSize * pOverall + Limits::Small;
@@ -1388 +1424 @@
                 if (1)
                 {
-                        const float oldCost = pOverall * (float)totalPvs + Limits::Small;
-                        cost += mPvsFactor * (pvsFront * pFront + pvsBack * pBack) / oldCost;
+                        const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize();
+                        const int upperPvsLimit = mViewCellsManager->GetMaxPvsSize();
+                        
+                        const float penaltyOld = EvalPvsPenalty(totalPvs, lowerPvsLimit, upperPvsLimit);
+            
+                        const float penaltyFront = EvalPvsPenalty(pvsFront, lowerPvsLimit, upperPvsLimit);
+                        const float penaltyBack = EvalPvsPenalty(pvsBack, lowerPvsLimit, upperPvsLimit);
+                        
+                        const float oldCost = pOverall * (float)penaltyOld + Limits::Small;
+                        cost += mPvsFactor * (penaltyFront * pFront + penaltyBack * pBack) / oldCost;
+
                 }
                 else
@@ -2673 +2718 @@
                 leaf->mPvs = new ObjectPvs(leaf->GetViewCell()->GetPvs());
 
-                BspMergeCandidate::sOverallCost += 
-                        leaf->mProbability * leaf->mPvs->GetSize();
-
+                //const float rc = leaf->mProbability * (float)leaf->mPvs->GetSize();
+                //BspMergeCandidate::sOverallCost += rc;
+                
                 // the same leaves must not be part of two merge candidates
                 leaf->Mail();
@@ -2741 +2786 @@
                                 new ObjectPvs(leaf->GetViewCell()->GetPvs());
 
-                        BspMergeCandidate::sOverallCost += 
-                                leaf->mProbability * leaf->mPvs->GetSize();
+                        //BspMergeCandidate::sOverallCost += 
+                        //      leaf->mProbability * leaf->mPvs->GetSize();
                         
                         ++ numLeaves;
@@ -2767 +2812 @@
                                         new ObjectPvs(leaf->GetViewCell()->GetPvs());
                                 
-                                BspMergeCandidate::sOverallCost += 
-                                        leaf->mProbability * leaf->mPvs->GetSize();
+                                //BspMergeCandidate::sOverallCost += 
+                                //      leaf->mProbability * leaf->mPvs->GetSize();
 
                                 ++ numLeaves;
@@ -2872 +2917 @@
 
 
+#if 1
 int VspBspTree::MergeViewCells(const VssRayContainer &rays, const ObjectContainer &objects)
 {
-        BspMergeCandidate::sMaxPvsSize = mViewCellsManager->GetMaxPvsSize();
-        //BspMergeCandidate::sMinPvsSize = mViewCellsManager->GetMinPvsSize();
+        BspMergeCandidate::sViewCellsManager = mViewCellsManager;
         BspMergeCandidate::sUseArea = mUseAreaForPvs;
 
+
+        //-- compute statistics values of initial view cells
+        mViewCellsManager->EvaluateRenderStatistics(BspMergeCandidate::sOverallCost, 
+                                                                                                BspMergeCandidate::sExpectedCost,
+                                                                                                BspMergeCandidate::sVariance);
+
+
+        //BspMergeCandidate::sExpectedCost = 
+        //      BspMergeCandidate::sOverallCost / BspMergeCandidate::sNumViewCells;
+
+
+        ViewCellsManager::PvsStatistics pvsStats;
+        mViewCellsManager->GetPvsStatistics(pvsStats);
+
+        static float expectedValue = pvsStats.avgPvs;
+        
         // the current view cells are kept in this container
         ViewCellContainer viewCells;
@@ -2885 +2946 @@
                 CollectViewCells(mRoot, true, viewCells, true);
         }
+
+
         ViewCell::NewMail();
 
@@ -2890 +2953 @@
         mergeStats.Start();
         
-        //BspMergeCandidate::sOverallCost = mBox.SurfaceArea() * mBspStats.maxPvs;
         long startTime = GetTime();
 
@@ -2912 +2974 @@
         startTime = GetTime();
 
+        // frequency stats are updated
+        const int statsOut = 100;
+
+        // number of view cells withouth the invalid ones
+        BspMergeCandidate::sNumViewCells = mBspStats.Leaves() - mBspStats.invalidLeaves;
+
+        // passes are needed for statistics, because we don't want to record
+        // every merge
+        const int maxMergesPerPass = 100;
+        int pass = 0;
+
+        // maximal ratio of old expected render cost to expected render
+        // when the the render queue has to be reset.
+        const float ercMaxRatio = 0.7f;
+        
+        cout << "actual merge starts now ... " << endl;
+
+        
+        
+        //-- use priority queue to merge leaf pairs
+
+
+        while (!mMergeQueue.empty() && 
+                   (BspMergeCandidate::sNumViewCells > mMergeMinViewCells) &&
+                   (mMergeQueue.top().GetMergeCost() < mMergeMaxCostRatio * BspMergeCandidate::sOverallCost))
+        {
+
+                int mergedPerPass = 0;
+                const float oldExpectedCost = BspMergeCandidate::sExpectedCost;
+                
+//#ifdef _DEBUG
+                Debug << "abs mergecost: " << mMergeQueue.top().GetMergeCost() << " rel mergecost: "
+                          << mMergeQueue.top().GetMergeCost() / BspMergeCandidate::sOverallCost 
+                          << " max ratio: " << mMergeMaxCostRatio << endl
+                          << " expected value: " << oldExpectedCost << endl;
+//#endif
+
+                while (!mMergeQueue.empty() && 
+                           (BspMergeCandidate::sNumViewCells > mMergeMinViewCells) &&
+                           (ercMaxRatio > oldExpectedCost / BspMergeCandidate::sExpectedCost) &&
+                           (mMergeQueue.top().GetMergeCost() < mMergeMaxCostRatio * BspMergeCandidate::sOverallCost) &&
+                           (maxMergesPerPass < mergedPerPass));
+                {
+                                Debug << "erc max ratio" << ercMaxRatio << endl;
+
+                                BspMergeCandidate mc = mMergeQueue.top();
+                                mMergeQueue.pop();
+
+                                // both view cells equal!
+                                if (mc.GetLeaf1()->GetViewCell() == mc.GetLeaf2()->GetViewCell())
+                                        continue;
+
+                                if (mc.Valid())
+                                {
+                                        ViewCell::NewMail();
+                                        const float currentMergeCost = mc.GetMergeCost();
+
+                                        MergeViewCells(mc.GetLeaf1(), mc.GetLeaf2());
+                                        
+                                        -- BspMergeCandidate::sNumViewCells;
+                                        ++ mergeStats.merged;
+                                        ++ mergedPerPass;
+
+                                        // increase absolute merge cost
+                                        BspMergeCandidate::sOverallCost += mc.GetRenderCost();
+                                        BspMergeCandidate::sVariance = mc.GetVarianceIncr();
+
+                                        BspMergeCandidate::sExpectedCost = 
+                                                BspMergeCandidate::sOverallCost / (float)BspMergeCandidate::sNumViewCells;
+
+                                        // stats
+                                        if (mc.GetLeaf1()->IsSibling(mc.GetLeaf2()))
+                                                ++ mergeStats.siblings;
+
+                                        if (0)
+                                        {
+                                                const int dist = 
+                                                        TreeDistance(mc.GetLeaf1(), mc.GetLeaf2());
+                                                if (dist > mergeStats.maxTreeDist)
+                                                        mergeStats.maxTreeDist = dist;
+                                                mergeStats.accTreeDist += dist;
+                                        }
+
+                                        if ((mergeStats.merged % statsOut) == 0)
+                                        {
+                                                cout << "merged " << mergeStats.merged << " view cells" << endl;
+
+                                                mStats 
+                                                        << "#Pass\n" << pass << endl
+                                                        << "#Merged\n" << mergeStats.merged << endl 
+                                                        << "#Viewcells\n" << BspMergeCandidate::sNumViewCells << endl 
+                                                        << "#OverallCost\n" << BspMergeCandidate::sOverallCost << endl
+                                                        << "#CurrentCost\n" << currentMergeCost << endl
+                                                        << "#RelativeCost\n" << currentMergeCost / BspMergeCandidate::sOverallCost << endl
+                                                        << "#CurrentPvs\n" << mc.GetLeaf1()->GetViewCell()->GetPvs().GetSize() << endl
+                                                        << "#MergedSiblings\n" << mergeStats.siblings << endl
+                                                        << "#AvgTreeDist\n" << mergeStats.AvgTreeDist() << endl
+                                                        << "#ExpectedCost\n" << BspMergeCandidate::sExpectedCost << endl
+                                                        << "#RatioExpectedCost\n" << oldExpectedCost / BspMergeCandidate::sExpectedCost << endl
+                                                        << "#variance\n" << BspMergeCandidate::sVariance << endl;
+
+                                                if (mExportMergedViewCells)
+                                                        ExportMergedViewCells(viewCells, objects, BspMergeCandidate::sNumViewCells);
+                                        }
+                                }
+                                else
+                                { 
+
+                                        // merge candidate not valid, because one of the leaves was already
+                                        // merged with another one => validate and reinsert into queue
+                                        mc.SetValid();
+                                        mMergeQueue.push(mc);
+                                }
+                }
+        
+
+                ++ pass;
+        }
+
+        mergeStats.overallCost = BspMergeCandidate::sOverallCost;
+
+        mergeStats.mergeTime = TimeDiff(startTime, GetTime());
+        mergeStats.Stop();
+
+        Debug << mergeStats << endl << endl;
+        
+        // delete the view cells which were already merged
+        CLEAR_CONTAINER(mOldViewCells);
+        
+
+        //TODO: should return sample contributions?
+        return mergeStats.merged;
+}
+
+#else
+
+int VspBspTree::MergeViewCells(const VssRayContainer &rays, const ObjectContainer &objects)
+{
+        BspMergeCandidate::sViewCellsManager = mViewCellsManager;
+        BspMergeCandidate::sUseArea = mUseAreaForPvs;
+
+        ViewCellsManager::PvsStatistics pvsStats;
+        mViewCellsManager->GetPvsStatistics(pvsStats);
+
+        static float expectedValue = pvsStats.avgPvs;
+        // the current view cells are kept in this container
+        ViewCellContainer viewCells;
+        if (mExportMergedViewCells)
+        {
+                ViewCell::NewMail();
+                CollectViewCells(mRoot, true, viewCells, true);
+        }
+        ViewCell::NewMail();
+
+        MergeStatistics mergeStats;
+        mergeStats.Start();
+        
+        //BspMergeCandidate::sOverallCost = mBox.SurfaceArea() * mBspStats.maxPvs;
+        long startTime = GetTime();
+
+        cout << "collecting merge candidates ... " << endl;
+        
+        if (mUseRaysForMerge)
+        {
+                mergeStats.nodes = CollectMergeCandidates(rays);
+        }
+        else
+        {
+                vector<BspLeaf *> leaves;
+                CollectLeaves(leaves);
+                mergeStats.nodes = CollectMergeCandidates(leaves);
+        }
+        
+        cout << "fininshed collecting candidates" << endl;
+
+        mergeStats.collectTime = TimeDiff(startTime, GetTime());
+        mergeStats.candidates = (int)mMergeQueue.size();
+        startTime = GetTime();
+
+        
         // number of view cells withouth the invalid ones
         int nViewCells = mBspStats.Leaves() - mBspStats.invalidLeaves;
-        
-        
-        // pass is needed for statistics. the last n passes are
-        // recorded
-        const int maxPasses = 1000;
-        const int nextPass = 50;
-
-        int pass = max(nViewCells - mMergeMinViewCells - maxPasses, 0);
-        
+        BspMergeCandidate::sExpectedCost = BspMergeCandidate::sOverallCost / (float)nViewCells;
+
+        // passes are needed for statistics, because we don't want to record
+        // every merge
+        const int mergesPerPass = 100;
+        
+        int nextPass = 0;
+    int pass = 0;
+        
+        
+        Debug << "stats: " << nextStats << " " << statsIncr << endl;
         cout << "actual merge starts now ... " << endl;
 
@@ -2939 +3183 @@
                 mMergeQueue.pop();
 
+
                 // both view cells equal!
                 if (mc.GetLeaf1()->GetViewCell() == mc.GetLeaf2()->GetViewCell())
@@ -2966 +3211 @@
                                         ++ mergeStats.siblings;
 
+                                if (0)
                                 const int dist = 
                                         TreeDistance(mc.GetLeaf1(), mc.GetLeaf2());
@@ -2972 +3218 @@
                                 mergeStats.accTreeDist += dist;
 
-                                if ((mergeStats.merged == pass) || (nViewCells == mMergeMinViewCells))
+                                if ((mergeStats.merged == nextPass) || (nViewCells == mMergeMinViewCells))
                                 {
-                                        pass += nextPass;
+                                        nextPass += mergesPerPass;
+
                                         mStats 
                                                 << "#Pass\n" << pass ++ << endl
@@ -2987 +3234 @@
 
                                                 if (mExportMergedViewCells)
-                                                        ExportMergedViewCells(viewCells, objects, nViewCells);   
+                                                        ExportMergedViewCells(viewCells, objects, nViewCells);
                                 }
                         }
@@ -3014 +3261 @@
         return mergeStats.merged;
 }
+#endif
 
 
@@ -3467 +3715 @@
 
 
-/************************************************************************/
-/*                BspMergeCandidate implementation                      */
-/************************************************************************/
+/**************************************************************************/
+/*                  BspMergeCandidate implementation                      */
+/**************************************************************************/
 
 
 BspMergeCandidate::BspMergeCandidate(BspLeaf *l1, BspLeaf *l2):
-mMergeCost(0),
+mRenderCost(0),
+mVarianceIncr(0),
 mLeaf1(l1),
 mLeaf2(l2),
@@ -3483 +3732 @@
 
 
-float BspMergeCandidate::GetCost(ViewCell *vc) const
+float BspMergeCandidate::GetRenderCost(ViewCell *vc) const
 {
         if (sUseArea)
@@ -3495 +3744 @@
 {
         BspViewCell *vc = mLeaf1->GetViewCell();
-        return GetCost(vc);
+
+        return GetRenderCost(vc);
 }
 
@@ -3502 +3752 @@
 {
         BspViewCell *vc = mLeaf2->GetViewCell();
-        return GetCost(vc);
+
+        return GetRenderCost(vc);
 }
 
@@ -3533 +3784 @@
 
 
-inline float BspMergeCandidate::EvalPvsPenalty(int pvs) const
-{
-        // clamp to minmax values
-        if (pvs > sUpperPvsLimit)
-                return (float)sUpperPvsLimit;
-        if (pvs < sLowerPvsLimit)
-                return (float)sLowerPvsLimit;
-
-        return (float)pvs;
-}
-
 
 void BspMergeCandidate::EvalMergeCost()
@@ -3551 +3791 @@
         BspViewCell *vc2 = mLeaf2->GetViewCell();
 
-        //const int diff1 = vc1->GetPvs().Diff(vc2->GetPvs());
-        //const int newPvs = diff1 + vc1->GetPvs().GetSize();
         const int newPvs = ComputeMergedPvsSize(vc1->GetPvs(), vc2->GetPvs());
-        const float f = EvalPvsPenalty(newPvs);
+        const float newPenalty = 
+                EvalPvsPenalty(newPvs, 
+                                           sViewCellsManager->GetMinPvsSize(),
+                                           sViewCellsManager->GetMaxPvsSize());
 
         //-- compute ratio of old cost
@@ -3566 +3807 @@
 
 
-        if (newPvs > sMaxPvsSize) // strong penalty if pvs size too large
-        {
-                mMergeCost = 1e15;
+        if (newPvs > sViewCellsManager->GetMaxPvsSize()) // strong penalty if pvs size too large
+        {
+                mRenderCost = 1e15;
         }
         else
         {
-                mMergeCost = newCost - oldCost;
-        }
+                mRenderCost = newCost - oldCost;
+        }
+
+        // merge cost also takes variance into account
+
+        const float oldVar1 = GetLeaf1Variance();
+        const float oldVar2 = GetLeaf2Variance();
+
+        const float newVar = (sExpectedCost - mRenderCost) * (sExpectedCost - mRenderCost);
+
+        mVarianceIncr = (newVar - oldVar1 - oldVar2) / sNumViewCells;
+        //mMergeCost = mRenderCost + fabs(newPenalty - BspMergeCandidate::sExpectedCost) ;
 }
 
@@ -3589 +3840 @@
 
 
-BspLeaf *BspMergeCandidate::GetLeaf1()
+BspLeaf *BspMergeCandidate::GetLeaf1() const
 {
         return mLeaf1;
@@ -3595 +3846 @@
 
 
-BspLeaf *BspMergeCandidate::GetLeaf2()
+BspLeaf *BspMergeCandidate::GetLeaf2() const
 {
         return mLeaf2;
@@ -3611 +3862 @@
 float BspMergeCandidate::GetMergeCost() const
 {
-        return mMergeCost;
+        return mRenderCost * sRenderCostWeight + mVarianceIncr * (1.0f - sRenderCostWeight);
+}
+
+
+float BspMergeCandidate::GetRenderCost() const
+{
+        return mRenderCost;
+}
+
+
+float BspMergeCandidate::GetVarianceIncr() const
+{
+        return mVarianceIncr;
+}
+
+float BspMergeCandidate::GetLeaf1Variance() const
+{
+        const float leafCost = GetLeaf1Cost();
+        
+        return (sExpectedCost - leafCost) * (sExpectedCost - leafCost);
+}
+
+
+float BspMergeCandidate::GetLeaf2Variance() const
+{
+        const float leafCost = GetLeaf2Cost();
+        
+        return (sExpectedCost - leafCost) * (sExpectedCost - leafCost);
 }