Changeset 1789 for GTP/trunk/Lib/Vis/Preprocessing/src/Pvs.h

Timestamp:

11/25/06 00:19:18 (18 years ago)

Author:

mattausch

Message:

 

File:

• GTP/trunk/Lib/Vis/Preprocessing/src/Pvs.h (modified) (23 diffs)

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

@@ -32 +32 @@
         template<typename T, typename S>
         friend int operator< (const PvsEntry<T, S> &a, const PvsEntry<T, S> &b);
+        template<typename T, typename S>
+        friend int operator== (const PvsEntry<T, S> &a, const PvsEntry<T, S> &b);
 };
 
@@ -39 +41 @@
 {
         return a.mObject < b.mObject;
+} 
+
+template<typename T, typename S>
+int operator== (const PvsEntry<T, S> &a, const PvsEntry<T, S> &b)
+{
+        return a.mObject == b.mObject;
 } 
 
@@ -51 +59 @@
 };
 
+template<typename T, typename S>
+int equalSample (const PvsEntry<T, S> &a, const PvsEntry<T, S> &b)
+{
+        return a.mObject == b.mObject;
+} 
 
 /** Information stored with a PVS entry. Consists of the number
@@ -189 +202 @@
 
         /** Finds sample in PVS.
+                @param checkDirty if dirty part of the pvs should be checked for entry 
+                        (warning: linear runtime in dirty part)
                 @returns iterator on the sample.
         */
-        typename vector<PvsEntry<T, S> >::iterator Find(T sample);
+        typename vector<PvsEntry<T, S> >::iterator Find(T sample, const bool checkDirty = true);
 
         bool GetSampleContribution(T sample, const float pdf, float &contribution);
@@ -199 +214 @@
                 @returns true if sample was not already in PVS.
         */
-        bool AddSample(T sample, const float pdf, float &contribution);
+        //bool AddSample(T sample, const float pdf, float &contribution);
 
         /** Adds sample to PVS.
@@ -206 +221 @@
         float AddSample(T sample, const float pdf);
 
-  /** Adds sample to PVS without checking for presence of the sample
-          pvs remians unsorted!
-  */
-  void AddSampleDirty(T sample, const float pdf);
-
-  /** Sort pvs entries - this should always be called after a
-          sequence of AddSampleDirty calls */
-  void Sort();
-  
+        /** Adds sample to PVS without checking for presence of the sample
+                pvs remains unsorted!
+        */
+        void AddSampleDirty(T sample, const float pdf);
+
+        /** Adds sample dirty (on the end of the vector) but
+                first checks if sample is already in clean part of the pvs.
+        */
+        bool AddSampleDirtyCheck(T sample, const float pdf);//, float &contribution);
+
+        /** Sort pvs entries - this should always be called after a
+                sequence of AddSampleDirty calls 
+        */
+        void Sort();
+
         /** Adds sample to PVS. Assumes that the pvs is sorted
                 @returns contribution of sample (0 or 1)
@@ -266 +287 @@
         static void Merge(Pvs<T, S> &mergedPvs, const Pvs<T, S> &a, const Pvs<T, S> &b);
 
+        static void Merge(Pvs<T, S> &mergedPvs, 
+                                          const typename std::vector<PvsEntry<T, S> >::const_iterator &aBegin,
+                                          const typename std::vector<PvsEntry<T, S> >::const_iterator &aEnd,
+                                          const typename std::vector<PvsEntry<T, S> >::const_iterator &bBegin,
+                                          const typename std::vector<PvsEntry<T, S> >::const_iterator &bEnd,
+                                          const int aSamples, 
+                                          const int bSamples);
+
         int GetSamples() const
         {
                 return mSamples;
+        }
+
+
+        bool IsDirty() const
+        {
+                return mLastSorted < mEntries.size();
+        }
+
+        bool RequiresResort() const
+        {
+                // 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 > (int)(log((double)mEntries.size()) / log(2.0));
+        }
+
+
+        int GetLastSorted() const
+        {
+                return mLastSorted;
         }
 
@@ -281 +330 @@
         int mSamples;
   
-  /// Last sorted entry in the pvs (important for find and merge
-  int mLastSorted;
-  
+        /// Last sorted entry in the pvs (important for find and merge)
+        int mLastSorted;  
 };
 
@@ -293 +341 @@
         mEntries = samples;
         mLastSorted = 0;
-}
+        mSamples = samples.size();
+}
+
 
 template <typename T, typename S>
 void Pvs<T, S>::Sort()
 {
-  std::vector<PvsEntry<T, S> >::iterator it = mEntries.begin();
-  it.inc(mLastSorted);
-  sort(it, mEntries.end());
-  mLastSorted = mEntries.size() - 1;
-}
+        std::vector<PvsEntry<T, S> >::iterator it = mEntries.begin() + mLastSorted;
+        //std::vector<PvsEntry<T, S> >::const_iterator it = mEntries.begin() + mLastSorted;
+        std::vector<PvsEntry<T, S> >::iterator it_end = mEntries.end();
+
+        // throw out double entries
+        std::vector<PvsEntry<T, S> >::iterator newEnd = unique(it, it_end);
+        sort(it, newEnd);
+        //sort(mEntries.begin(), mEntries.end());
+
+        // now merge sorted ranges
+        ObjectPvs newPvs;
+        Merge(newPvs, 
+                  mEntries.begin(), it, 
+                  it, newEnd, 
+                  mSamples, 0);
+        
+        mEntries = newPvs.mEntries;
+        mLastSorted = (int)mEntries.size();
+}
+
 
 /**
@@ -436 +501 @@
         std::vector<PvsEntry<T, S> >::const_iterator bit = b.mEntries.begin(), bit_end = b.mEntries.end();
         
-        for (; (ait != ait_end); ++ ait)
+        Merge(mergedPvs, 
+                  ait, ait_end,
+                  bit, bit_end,
+                  a.mSamples,
+                  b.mSamples);
+}
+
+
+template <typename T, typename S>
+void Pvs<T, S>::Merge(Pvs<T, S> &mergedPvs, 
+                                          const typename std::vector<PvsEntry<T, S> >::const_iterator &aBegin,
+                                          const typename std::vector<PvsEntry<T, S> >::const_iterator &aEnd,
+                                          const typename std::vector<PvsEntry<T, S> >::const_iterator &bBegin,
+                                          const typename std::vector<PvsEntry<T, S> >::const_iterator &bEnd,
+                                          const int aSamples, 
+                                          const int bSamples)
+{
+        std::vector<PvsEntry<T, S> >::const_iterator ait = aBegin;
+        std::vector<PvsEntry<T, S> >::const_iterator bit = bBegin;
+        
+        for (; (ait != aEnd); ++ ait)
         {
                 Intersectable *aObj = (*ait).mObject;
                 Intersectable *bObj = NULL;
-                PvsEntry<T, S> aEntry = (*ait);
-
-                for (; (bit != bit_end) && ((*bit).mObject <= (*ait).mObject); ++ bit)
+                //Intersectable *bObjOld = NULL;
+        
+                const PvsEntry<T, S> &aEntry = (*ait);
+
+                for (; (bit != bEnd) && ((*bit).mObject <= (*ait).mObject); ++ bit)
                 {
                         bObj = (*bit).mObject;
@@ -457 +544 @@
                                 mergedPvs.mEntries.push_back(*bit);
                         }
+                        
+                        //bObjOld = bObj;
                 }
 
@@ -468 +557 @@
 
         // add the rest
-        for (; (bit != bit_end); ++ bit)
+        for (; (bit != bEnd); ++ bit)
         {
                 mergedPvs.mEntries.push_back(*bit);
         }
-        mergedPvs.mSamples = a.mSamples + b.mSamples;
+
+        mergedPvs.mSamples = aSamples + bSamples;
 }
 
@@ -480 +570 @@
         mEntries.clear();
         mSamples = 0;
+        mLastSorted = 0;
 
         if (trim)
@@ -495 +586 @@
 
 template <typename T, typename S> 
-typename std::vector<PvsEntry<T, S> >::iterator Pvs<T, S>::Find(T sample)
+typename std::vector<PvsEntry<T, S> >::iterator Pvs<T, S>::Find(T sample, const bool checkDirty)
 {
         PvsEntry<T, S> dummy(sample, PvsData());
-        vector<PvsEntry<T, S> >::iterator it = lower_bound(mEntries.begin(), mEntries.end(), dummy);
-                                
+
+        // only check clean part
+        //mLastSorted = 0;
+        vector<PvsEntry<T, S> >::iterator sorted_end = mEntries.begin() + mLastSorted;
+if (sorted_end != mEntries.end())
+cout << "not entries end!! " << endl;
+        // binary search
+        vector<PvsEntry<T, S> >::iterator it = lower_bound(mEntries.begin(), sorted_end, dummy);
+
+        // sample not found yet => search further in the unsorted part
+        if (checkDirty &&
+                ((it == mEntries.end()) || ((*it).mObject != sample)))
+        {
+                vector<PvsEntry<T, S> >::const_iterator it_end = mEntries.end();
+                for (it = sorted_end; (it != it_end) && ((*it).mObject != sample); ++ it);
+        }
+        else cout << "f ";
         return it;
 }
@@ -519 +625 @@
 {
         ++ mSamples;
+        cout << "! ";
         std::vector<PvsEntry<T, S> >::iterator it = Find(sample);
 
         if ((it != mEntries.end()) && ((*it).mObject == sample))
-        {
+        {       cout << "g";
                 S &data = (*it).mData;
                 data.mSumPdf += pdf;
@@ -528 +635 @@
         }
         else 
-        {
+        {cout << "t";
                 PvsEntry<T, S> entry(sample, pdf);
                 mEntries.insert(it, entry);
+                ++ mLastSorted;
                 return pdf;
         }
+        cout << " $";
 }
 
@@ -539 +648 @@
 void Pvs<T, S>::AddSampleDirty(T sample, const float pdf)
 {
-  ++ mSamples;
-  mEntries.push_back(PvsEntry<T, S>(sample, pdf));
+        ++ mSamples;
+        mEntries.push_back(PvsEntry<T, S>(sample, pdf));
 }
                                          
@@ -548 +657 @@
 {
         ++ mSamples;
+        
         std::vector<PvsEntry<T, S> >::iterator it = Find(sample);
 
@@ -559 +669 @@
                 PvsEntry<T, S> entry(sample, pdf);
                 mEntries.insert(it, entry);
+                ++ mLastSorted;
         }
 
@@ -565 +676 @@
 
 
-template <typename T, typename S> 
+/*template <typename T, typename S> 
 bool Pvs<T, S>::AddSample(T sample,
                                                   const float pdf,
@@ -589 +700 @@
                 mEntries.insert(it, entry);
                 contribution = 1.0f;
+                ++ mLastSorted;
+
+                return true;
+        }
+}*/
+
+
+/** Adds sample dirty (on the end of the vector) but
+        first checks if sample is already in clean part of the pvs.
+*/
+template <typename T, typename S> 
+bool Pvs<T, S>::AddSampleDirtyCheck(T sample,
+                                                                        const float pdf)
+                                                                        //,float &contribution)
+{
+        ++ mSamples;
+
+        std::vector<PvsEntry<T, S> >::iterator it = Find(sample);
+
+        if ((it != mEntries.end()) && ((*it).mObject == sample))
+        {
+                S &data = (*it).mData;
+
+                data.mSumPdf += pdf;
+                //contribution = pdf / data.mSumPdf;
+
+                return false;
+        }
+        else 
+        {
+                AddSampleDirty(sample, pdf);
+                //contribution = 1.0f;
 
                 return true;
@@ -620 +763 @@
 {
         -- mSamples;
-
+        
         std::vector<PvsEntry<T, S> >::iterator it = Find(sample);
 
@@ -633 +776 @@
         {
                 mEntries.erase(it);
+                -- mLastSorted; // wrong if sample was in tail!!
         }