Changeset 2116 for GTP/trunk/Lib/Vis/Preprocessing/src/HashPvs.h

Timestamp:

02/15/07 00:35:41 (17 years ago)

Author:

mattausch

Message:

implemented hashpvs

File:

• GTP/trunk/Lib/Vis/Preprocessing/src/HashPvs.h (modified) (8 diffs)

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

@@ -2 +2 @@
 #define __HASHPVS_H
 
-#include <hash_map>
-#include <vector>
+//#include <hash_map>
+#include <hash_set>
 #include "common.h"
 #include <math.h>
@@ -13 +13 @@
 namespace GtpVisibilityPreprocessor {
 
-class KdNode;
-class BspNode;
-class Ray;
-class Intersectable;
-class ViewCell;
+
+template<typename T>
+struct my_hash_compare
+{
+   enum
+   {
+      bucket_size = 4,
+      min_buckets = 80
+   };
+
+   size_t operator()(T a) const
+   {
+      size_t h = (size_t)(a->GetId());// % 2000;
+      //for (; *s; ++s)
+      //   h = 5 * h + *s;
+      return h;
+   }
+
+   bool operator()(T a, T b) const
+   {
+      return a < b;
+   }
+};
+
+/*
+template<typename T>
+struct gt
+{
+        bool operator() (T s1, T s2) const
+        {
+                return s1 > s2;
+        }
+};
+*/
+//#define HASH_SET stdext::hash_set<T, stdext::hash_compare<T, gt<T> > >
+#define HASH_SET stdext::hash_set<T, my_hash_compare<T> >
+
+/** Iterator over a hash pvs.
+*/
+template<typename T, typename S>
+class HashPvsIterator
+{
+public:
+        
+        HashPvsIterator<T, S>() {}
+
+        HashPvsIterator<T, S>(const typename HASH_SET::const_iterator &itCurrent,
+                                                  const typename HASH_SET::const_iterator &itEnd):
+        mItCurrent(itCurrent), mItEnd(itEnd)
+        {
+        }
+
+        bool HasMoreEntries() const 
+        {
+                return (mItCurrent != mItEnd);
+        }
+
+        PvsEntry<T, S> Next()
+        {
+                // hack: create new pvs entry
+                return PvsEntry<T, S>(*(mItCurrent) ++, S(0.0));
+        }
+        
+private:
+        typename HASH_SET::const_iterator mItCurrent;
+        typename HASH_SET::const_iterator mItEnd;
+};
 
 
@@ -23 +85 @@
         mainly from a view cell, but also e.g., from objects.
 */
-template<typename T>
-class HashPvs: public PvsBase<T>
-{
-        template<typename T>
-                friend class PvsIterator2;
+template<typename T, typename S>
+class HashPvs//: public PvsBase<T>
+{
+        template<typename T, typename S> friend class HashPvsIterator;
 
 public:
 
+        //HashPvs(): mEntries((Intersectable *)100) {};
         HashPvs() {};
         //virtual ~HashPvs() {};
@@ -40 +102 @@
                 @returns contribution of sample (0 or 1)
         */
-        float AddSample(T sample);
+        float AddSample(T sample, const float pdf);
 
         /** Adds sample to PVS without checking for presence of the sample
                 warning: pvs remains unsorted!
         */
-        void AddSampleDirty(T sample);
+        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);
+        bool AddSampleDirtyCheck(T sample, const float pdf);
 
         /** Sort pvs entries - this should always be called after a
@@ -61 +123 @@
         void Clear(const bool trim = true);
 
-        //static void Merge(PvsBase &mergedPvs, const PvsBase &a, const PvsBase &b);
-
         bool IsDirty() const;
 
         bool RequiresResort() const;
 
-        //typename PvsIterator<T> GetIterator() const;
-
+        /** 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 if found, else the place where 
+                it would be added in the sorted vector.
+        */
+        bool Find(T sample, typename HASH_SET::iterator &it);
+
+        typename HashPvsIterator<T, S> GetIterator() const;
+
+        /** Compute continuous PVS difference 
+        */
+        float GetPvsHomogenity(HashPvs<T, S> &pvs);
+
+        static void Merge(HashPvs<T, S> &mergedPvs, 
+                                          const HashPvs<T, S> &a, 
+                                          const HashPvs<T, S> &b);
+
+        static int GetEntrySizeByte(); 
+        static float GetEntrySize();
+
+        bool GetSampleContribution(T sample,
+                                                   const float pdf,
+                                                           float &contribution);
+
+        int GetSamples() const
+        {
+                return mSamples;
+        }
+
+        void MergeInPlace(const HashPvs<T, S> &a)
+        {
+                cerr << "not implemented yet" << endl;
+        }
+
+        bool RequiresResortLog() const
+        {
+                return false;
+        }
+
+        void Reserve(const int n) 
+        { 
+                // not necessary
+        }
+
+        /** Sort pvs entries assume that the pvs contains unique entries
+        */
+        void SimpleSort()
+        {
+                // not necessary
+        }
+
+        int SubtractPvs(const HashPvs<T, S> &pvs)
+        {
+                cerr << "not yet implemented" << endl;
+                return 0;
+        }
+
+        /** Compute continuous PVS difference 
+        */
+        void ComputeContinuousPvsDifference(HashPvs<T, S> &pvs, 
+                                                                                float &pvsReduction,
+                                                                                float &pvsEnlargement)
+        {
+                cerr << "not yet implemented" << endl;
+        }
 protected:
 
-        /// vector of PVS entries
-        vector<T> mEntries; 
+        /// hash table of PVS entries
+        HASH_SET mEntries; 
 
         /// Number of samples used to create the PVS
@@ -79 +203 @@
 
 
-template <typename T>
-int HashPvs<T>::GetSize() const
-{
-        return 0;
-}
-
-
-template <typename T>
-bool HashPvs<T>::Empty() const
+template <typename T, typename S>
+bool HashPvs<T, S>::Find(T sample, typename HASH_SET::iterator &it)
+{
+        it = mEntries.find(sample);
+
+        // already in map
+        return (it != mEntries.end());
+}
+
+
+template <typename T, typename S>
+int HashPvs<T, S>::GetSize() const
+{
+        return (int)mEntries.size();
+}
+
+
+template <typename T, typename S>
+bool HashPvs<T, S>::Empty() const
+{
+        return mEntries.empty();
+}
+
+
+template <typename T, typename S>
+float HashPvs<T, S>::AddSample(T sample, const float pdf)
+{
+        HASH_SET::iterator it;
+
+        if (Find(sample, it))
+                return 0.0f;
+        
+        mEntries.insert(sample);
+        return 1.0f;
+}
+        
+
+template <typename T, typename S>
+void HashPvs<T, S>::AddSampleDirty(T sample, const float pdf)
+{
+        HASH_SET::iterator it;
+
+        // not yet in map
+        if (!Find(sample, it))
+        {
+                mEntries.insert(sample);        
+        }
+}
+
+
+template <typename T, typename S>
+bool HashPvs<T, S>::AddSampleDirtyCheck(T sample, 
+                                                                                const float pdf)
+{
+        HASH_SET::iterator it;
+
+        // already in map
+        if (Find(sample, it))
+                return false;
+        
+        mEntries.insert(sample);
+        return true;
+}
+
+
+template <typename T, typename S>
+void HashPvs<T, S>::Sort()
+{
+}
+
+
+template <typename T, typename S>
+void HashPvs<T, S>::Clear(const bool trim = true)
+{
+        mEntries.clear();
+}
+
+
+template <typename T, typename S>
+bool HashPvs<T, S>::IsDirty() const
 {
         return false;
@@ -93 +288 @@
 
 
-template <typename T>
-float HashPvs<T>::AddSample(T sample)
-{
-        return 0;
-}
-        
-
-template <typename T>
-void HashPvs<T>::AddSampleDirty(T sample)
-{
-}
-
-
-template <typename T>
-bool HashPvs<T>::AddSampleDirtyCheck(T sample)
+template <typename T, typename S>
+bool HashPvs<T, S>::RequiresResort() const
 {
         return false;
@@ -113 +295 @@
 
 
-template <typename T>
-void HashPvs<T>::Sort()
-{
-}
-
-
-template <typename T>
-void HashPvs<T>::Clear(const bool trim = true)
-{
-}
-
-
-template <typename T>
-bool HashPvs<T>::IsDirty() const
-{
-        return false;
-}
-
-
-template <typename T>
-bool HashPvs<T>::RequiresResort() const
-{
-        return false;
-}
-
-//typename PvsIterator<T> GetIterator() const;
+template <typename T, typename S>
+typename HashPvsIterator<T, S> HashPvs<T, S>::GetIterator() const
+{
+        HashPvsIterator<T, S> pit(mEntries.begin(), mEntries.end());
+
+        return pit;
+}
+
+
+template <typename T, typename S>
+float HashPvs<T, S>::GetEntrySize()
+{
+        return (float)(sizeof(T)) / float(1024 * 1024);
+}
+
+
+template <typename T, typename S>
+int HashPvs<T, S>::GetEntrySizeByte()
+{
+        return sizeof(T);
+}
+
+
+template <typename T, typename S>
+float HashPvs<T, S>::GetPvsHomogenity(HashPvs<T, S> &pvs) 
+{
+        float pvsReduction, pvsEnlargement;
+
+        ComputeContinuousPvsDifference(pvs,     pvsReduction, pvsEnlargement);
+
+        return pvsReduction + pvsEnlargement;
+}
+
+
+template <typename T, typename S>
+bool HashPvs<T, S>::GetSampleContribution(T sample,
+                                                                          const float pdf,
+                                                                          float &contribution) 
+{
+        HASH_SET::iterator it;
+        const bool entryFound = Find(sample, it);
+
+        if (entryFound)  
+        {
+                contribution = 0.0f;
+                return false;
+        }
+        else 
+        {
+                contribution = 1.0f;
+                return true;
+        }
+}
+
+
+template <typename T, typename S>
+void HashPvs<T, S>::Merge(HashPvs<T, S> &mergedPvs, 
+                                                  const HashPvs<T, S> &a, 
+                                                  const HashPvs<T, S> &b)
+{
+        HASH_SET::const_iterator ait, ait_end = a.mEntries.end();
+
+        for (ait = a.mEntries.begin(); ait != ait_end; ++ ait)
+        {
+                mergedPvs.AddSample(*ait, 1.0f);
+        }
+
+        HASH_SET::const_iterator bit, bit_end = b.mEntries.end();
+
+        for (bit = b.mEntries.begin(); bit != bit_end; ++ bit)
+        {
+                mergedPvs.AddSample(*bit, 1.0f);
+        }
+
+        //cerr << "not implemented" << endl; 
+}
 
 }