Changeset 2019

Timestamp:

01/23/07 00:11:50 (17 years ago)

Author:

bittner

Message:

merge

Location:

GTP/trunk/Lib/Vis/Preprocessing/src

Files:

• Makefile (modified) (1 diff)
• Pvs.h (modified) (7 diffs)
• SamplingStrategy.cpp (modified) (1 diff)
• ViewCellsManager.cpp (modified) (2 diffs)

GTP/trunk/Lib/Vis/Preprocessing/src/Makefile

@@ -1 +1 @@
 #############################################################################
 # Makefile for building: preprocessor
-# Generated by qmake (2.00a) (Qt 4.1.2) on: po 22. I 17:10:45 2007
+# Generated by qmake (2.00a) (Qt 4.1.2) on: po 22. I 22:05:05 2007
 # Project:  preprocessor.pro
 # Template: app

GTP/trunk/Lib/Vis/Preprocessing/src/Pvs.h

@@ -5 +5 @@
 #include <vector>
 #include "common.h"
+#include <math.h>
+using namespace std;
 
 namespace GtpVisibilityPreprocessor {
@@ -171 +173 @@
 
 public:
-
-        Pvs(): mSamples(0), mEntries(), mLastSorted(0) {}
+  
+        Pvs(): mSamples(0), mEntries(), mLastSorted(0), mQueriesSinceSort(0) {}
 
         /** creates pvs and initializes it with the given entries. 
@@ -312 +314 @@
           // the last part should not be more than log of the sorted part. this
           // way we can achieve logarithmic behaviour for insertion and find
-          const int dirtySize = (int)mEntries.size() - mLastSorted;
-          return dirtySize > 500;
-          //              4*(int)(log((double)mEntries.size()) / log(2.0));
+          const int n = mEntries.size();
+          const int dirtySize = n - mLastSorted;
+
+#define LOG2E 1.442695040f
+          
+          const float logN = log((float)max(1, n))/LOG2E;
+          const float logS = log((float)max(1, mLastSorted))/LOG2E;
+          const float logD = log((float)max(1, dirtySize))/LOG2E;
+          
+          if (8*(n + 2*dirtySize*logD) <
+                  mQueriesSinceSort*((mLastSorted*logS + dirtySize*dirtySize/2)/n - logN)) {
+                //              cout<<"Q="<<mQueriesSinceSort<<" N="<<n<<" D="<<dirtySize<<endl;
+                return true;
+          }
+          return false;
         }
 
@@ -342 +356 @@
   
         /// Last sorted entry in the pvs (important for find and merge)
-        int mLastSorted;  
+        int mLastSorted;
+
+  int mQueriesSinceSort;
 };
 
@@ -367 +383 @@
         sort(it, newEnd);
         //sort(mEntries.begin(), mEntries.end());
-
+        
         // now merge sorted ranges
         ObjectPvs newPvs;
         Merge(newPvs, 
-                  mEntries.begin(), it, 
-                  it, newEnd, 
-                  mSamples, 0);
+                  mEntries.begin(),
+                  it, 
+                  it,
+                  newEnd, 
+                  mSamples,
+                  0);
         
         mEntries = newPvs.mEntries;
         mLastSorted = (int)mEntries.size();
+        mQueriesSinceSort = 0;
 }
 
@@ -382 +402 @@
 void Pvs<T, S>::SimpleSort()
 {
-  sort(mEntries.begin(), mEntries.end());
+  //  sort(mEntries.begin(), mEntries.end());
+  std::vector<PvsEntry<T, S> >::iterator it = mEntries.begin() + mLastSorted;
+  
+  sort(it, mEntries.end());
+  inplace_merge(mEntries.begin(), it, mEntries.end());
+  
   mLastSorted = (int)mEntries.size();
+  mQueriesSinceSort = 0;
 }
 
@@ -610 +636 @@
 {
   PvsEntry<T, S> dummy(sample, PvsData());
+  mQueriesSinceSort++;
   
   // only check clean part

GTP/trunk/Lib/Vis/Preprocessing/src/SamplingStrategy.cpp

@@ -548 +548 @@
   }
 
+#if 0
   pvsTimer.Entry();
   // resort pvss
   mPreprocessor.mViewCellsManager->SortViewCellPvs();
   pvsTimer.Exit();
+#endif
   
   UpdateRatios();

GTP/trunk/Lib/Vis/Preprocessing/src/ViewCellsManager.cpp

@@ -2538 +2538 @@
         ObjectPvs &pvs = (*it)->GetPvs();
         if (pvs.RequiresResortLog())
-          pvs.Sort();
+          pvs.SimpleSort();
   }
 }
@@ -2581 +2581 @@
         if (viewCell->GetPvs().RequiresResort()) 
           viewCell->GetPvs().SimpleSort();
+        
+        //        viewCell->GetPvs().SimpleSort();
 
 #if CONTRIBUTION_RELATIVE_TO_PVS_SIZE