Changeset 1740

Timestamp:

11/10/06 22:15:56 (18 years ago)

Author:

mattausch

Message:

exchanged pvs implementation: using vectors instead of maps

Location:

GTP/trunk/Lib/Vis/Preprocessing/src

Files:

• HierarchyManager.cpp (modified) (1 diff)
• OspTree.cpp (modified) (4 diffs)
• Preprocessor.cpp (modified) (10 diffs)
• Preprocessor.h (modified) (2 diffs)
• Pvs.cpp (modified) (1 diff)
• Pvs.h (modified) (23 diffs)
• TestPreprocessor.vcproj (modified) (1 diff)
• ViewCell.cpp (modified) (19 diffs)
• ViewCellsManager.cpp (modified) (22 diffs)
• ViewCellsManager.h (modified) (3 diffs)

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

@@ -1845 +1845 @@
                 for (oit = pvs.mEntries.begin(); oit != oit_end; ++ oit)
                 {
-                        BvhIntersectable *intersect = dynamic_cast<BvhIntersectable *>((*oit).first);
+                        BvhIntersectable *intersect = dynamic_cast<BvhIntersectable *>((*oit).mObject);
 
                         BvhLeaf *leaf = intersect->GetItem();

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

@@ -2175 +2175 @@
                         {
                                 ViewCell *vc = *vit;
-                                PvsData *vdata = vc->GetPvs().Find(obj);
+                                /*PvsData *vdata = vc->GetPvs().Find(obj);
 
                                 if (!vdata)
@@ -2183 +2183 @@
                                 }
 
-/*                              MailablePvsData *vdata = obj->mViewCellPvs.Find(vc);
+                                MailablePvsData *vdata = obj->mViewCellPvs.Find(vc);
 
                                 if (!vdata || !vdata->Mailed())
@@ -2256 +2256 @@
                 {
                         ViewCell *vc = *vit;
-                        PvsData *vdata = vc->GetPvs().Find(obj);
+                        /*PvsData *vdata = vc->GetPvs().Find(obj);
 
                         if (!vdata)
@@ -2262 +2262 @@
                                 vc->GetPvs().AddSample(obj, 1);
                                 rc += vc->GetVolume();
-                                //prop += vc->GetVolume();
                         }
+                        */
                 }
         }

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

@@ -127 +127 @@
 mBspTree(NULL),
 mVspBspTree(NULL),
-mHierarchyManager(NULL),
 mViewCellsManager(NULL),
 mRenderSimulator(NULL),
@@ -186 +185 @@
         cout << "Deleting kd tree...\n";
         DEL_PTR(mKdTree);
-        cout << "done.\n";
-
-        cout << "Deleting hierarchy manager...\n";
-        DEL_PTR(mHierarchyManager);
         cout << "done.\n";
 
@@ -630 +625 @@
         if (mLoadViewCells)
         {       
-          Environment::GetSingleton()->GetStringValue("ViewCells.filename", buf);
-          cout << "loading view cells from " << buf << endl<<flush;
-          
-         mViewCellsManager = ViewCellsManager::LoadViewCells(buf, &mObjects, true, NULL);
-
-         cout << "view cells loaded." << endl<<flush;
-         
-          if (!mViewCellsManager)
-          {
-                  return false;
-          }
+                Environment::GetSingleton()->GetStringValue("ViewCells.filename", buf);
+                cout << "loading view cells from " << buf << endl<<flush;
+
+                mViewCellsManager = ViewCellsManager::LoadViewCells(buf, &mObjects, true, NULL);
+
+                cout << "view cells loaded." << endl<<flush;
+
+                if (!mViewCellsManager)
+                {
+                        return false;
+                }
         }
         else
@@ -646 +641 @@
                 // parse type of view cell container
                 Environment::GetSingleton()->GetStringValue("ViewCells.type", buf);             
-            mViewCellsManager = CreateViewCellsManager(buf);
+                mViewCellsManager = CreateViewCellsManager(buf);
 
                 // default view space is the extent of the scene
                 AxisAlignedBox3 viewSpaceBox;
-                        
+
                 if (mUseViewSpaceBox)
                 {
@@ -675 +670 @@
                 char vcGeomFilename[100];
                 Environment::GetSingleton()->GetStringValue("ViewCells.geometryFilename", vcGeomFilename);
-                
+
                 if (loadVcGeometry)
                 {
@@ -691 +686 @@
                 }
         }
-        
+
         ////////
         //-- evaluation of render cost heuristics
@@ -699 +694 @@
         Environment::GetSingleton()->GetFloatValue("Simulation.vcOverhead", vcOverhead);
         Environment::GetSingleton()->GetFloatValue("Simulation.moveSpeed", moveSpeed);
-        
+
         mRenderSimulator = 
                 new RenderSimulator(mViewCellsManager, objRenderCost, vcOverhead, moveSpeed);
 
         mViewCellsManager->SetRenderer(mRenderSimulator);
-        
+
         if (mUseGlRenderer || mUseGlDebugger)
-          {
+        {
                 // NOTE: render texture should be power of 2 and square
                 // renderer must be initialised
@@ -712 +707 @@
                 //              renderer = new GlRendererBuffer(1024, 768, mSceneGraph, mViewCellsManager, mKdTree);
                 //              renderer->makeCurrent();
-                
-          }
+
+        }
 
         mViewCellsManager->SetPreprocessor(this);
@@ -733 +728 @@
 
 
-HierarchyManager *Preprocessor::CreateHierarchyManager(const char *name)
-{
-        HierarchyManager *hierarchyManager;
-
-        if (strcmp(name, "osp") == 0)
-        {
-                Debug << "hierarchy manager: osp" << endl;
-                // HACK for testing if per kd evaluation works!!
-                const bool ishack = false;
-                if (ishack)
-                        hierarchyManager = new HierarchyManager(mKdTree);
-                else
-                        hierarchyManager = new HierarchyManager(HierarchyManager::KD_BASED_OBJ_SUBDIV);
-        }
-        else if (strcmp(name, "bvh") == 0)
-        {
-                Debug << "hierarchy manager: bvh" << endl;
-                hierarchyManager = new HierarchyManager(HierarchyManager::BV_BASED_OBJ_SUBDIV);
-        }
-        else // only view space partition
-        {
-                Debug << "hierarchy manager: obj" << endl;
-                hierarchyManager = new HierarchyManager(HierarchyManager::NO_OBJ_SUBDIV);
-        }
-
-        return hierarchyManager;
-}
-
-
 ViewCellsManager *Preprocessor::CreateViewCellsManager(const char *name)
 {
@@ -790 +756 @@
                 Environment::GetSingleton()->GetStringValue("Hierarchy.type", buf);     
 
-                mHierarchyManager = CreateHierarchyManager(buf);
-                mViewCellsManager = new VspOspViewCellsManager(vcTree, mHierarchyManager);
+                mViewCellsManager = new VspOspViewCellsManager(vcTree, buf);
         }
         else if (strcmp(name, "sceneDependent") == 0) //TODO

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

@@ -138 +138 @@
         */
         ViewCellsManager *CreateViewCellsManager(const char *name);
-        /** Returns a hierarchy manager of the given name.
-        */
-        HierarchyManager *CreateHierarchyManager(const char *name);
 
         GlRendererBuffer *GetRenderer();
@@ -160 +157 @@
         /// View space partition bsp tree
         VspBspTree *mVspBspTree;
-        /// Hierarchy manager handling view space and object space partition
-        HierarchyManager *mHierarchyManager;
         /// BSP tree representing the viewcells
         BspTree *mBspTree;

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

@@ -143 +143 @@
         for (it = mEntries.begin(); it != it_end; ++ it)
         {
-                Intersectable *obj = (*it).first;
+                Intersectable *obj = (*it).mObject;
         
                 switch (obj->Type())

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

@@ -15 +15 @@
 
 
-template<typename T>
-struct LtSample 
-{
-    bool operator()(const T a, const T b) const
+/** Information stored with a PVS entry. Consists of the number
+        the object was seen from the view cell.
+*/
+template<typename T, typename S>
+class PvsEntry 
+{
+public:
+
+        PvsEntry(T sample, const S &data): mObject(sample), mData(data) {}
+
+        T mObject;
+        S mData;
+
+        template<typename T, typename S>
+        friend int operator< (const PvsEntry<T, S> &a, const PvsEntry<T, S> &b);
+};
+
+
+template<typename T, typename S>
+int operator< (const PvsEntry<T, S> &a, const PvsEntry<T, S> &b)
+{
+        return a.mObject < b.mObject;
+} 
+
+
+template<typename T, typename S>
+struct LtSample
+{
+    bool operator()(const PvsEntry<T, S> &a, const PvsEntry<T, S> &b) const
     {
-                return a < b;
+                return a.mObject < b.mObject;
         } 
 };
+
 
 /** Information stored with a PVS entry. Consists of the number
@@ -29 +55 @@
 class PvsData {
 public:
+        PvsData() {}
+        PvsData(const float sumPdf):
+        mSumPdf(sumPdf) {}
+        
+        // $$JB in order to return meaningfull values
+        // it assumes that the sum pdf has been normalized somehow!!!
+        inline float GetVisibility() 
+        { 
+                return mSumPdf; 
+        }
+
         /// sum of probability density of visible sample rays
         float mSumPdf;
-
-        PvsData() {}
-        PvsData(const float sumPdf):
+};
+
+
+class MailablePvsData 
+{
+public:
+        // sum of probability density of visible sample rays
+        float mSumPdf;
+        int mCounter;
+
+        MailablePvsData() {}
+        MailablePvsData(const float sumPdf):
         mSumPdf(sumPdf) {}
 
@@ -42 +88 @@
                 return mSumPdf; 
         }
-};
-
-
-class MailablePvsData 
-{
+
         ////////////////////////////
         //  Mailing stuff
-protected:
-        int mMailbox;
-
-public:
+
         // last mail id -> warning not thread safe!
         // both mailId and mailbox should be unique for each thread!!!
@@ -58 +97 @@
         static int sReservedMailboxes;
 
-
         static void NewMail(const int reserve = 1) {
                 sMailId += sReservedMailboxes;
@@ -71 +109 @@
 
         int IncMail() { return ++ mMailbox - sMailId; }
+        
         //////////////////////////////////////////
 
-        // sum of probability density of visible sample rays
-        float mSumPdf;
-        int mCounter;
-
-        MailablePvsData() {}
-        MailablePvsData(const float sumPdf):
-        mSumPdf(sumPdf) {}
-
-        // $$JB in order to return meaningfull values
-        // it assumes that the sum pdf has been normalized somehow!!!
-        float GetVisibility() 
-        { 
-                return mSumPdf; 
-        }
-};
+protected:
+
+        int mMailbox;
+
+};
+
+
 template<typename T, typename S>
-        class Iterator
-        {
-                //template<typename T, typename S> friend Pvs<T, S>;
-        private:
-                std::vector<std::pair<T, S> >::iterator mIt;
-                //vector<pair<T, S> >::iterator mItEnd;
-        };
+class PvsIterator
+{
+private:
+        typename vector<PvsEntry<T, S> >::iterator mItCurrent;
+        typename vector<PvsEntry<T, S> >::iterator mItEnd;
+};
+
+
 /** Template class representing the Potentially Visible Set (PVS) 
         mainly from a view cell, but also e.g., from objects.
@@ -102 +134 @@
 class Pvs
 {
+        template<typename T, typename S>
+        friend class PvsIterator;
+
 public:
-//vector<pair<T, S> >::iterator mItEnd;
-        
-
-        template<typename T, typename S>
-        class ConstIterator
-        {
-        //      template<typename T, typename S> friend Pvs<T, S>;
-        private:
-                //vector<pair<T, S> >::const_iterator mIt;
-                //vector<pair<T, S> >::const_iteator mItEnd;
-        };
-
-  Pvs(): mSamples(0), mEntries() {}
-  
-
+
+        Pvs(): mSamples(0), mEntries() {}
+
+        Pvs(const vector<PvsEntry<T, S> > &samples);
         //virtual ~Pvs();
 
@@ -126 +150 @@
         bool Empty() const {return mEntries.empty();}
 
-        /** Normalize the visibility of entries in order to get comparable
-                results 
+        /** Normalize the visibility of entries in order to get 
+                comparable results.
         */
         void NormalizeMaximum();
 
         /** Merges pvs of a into this pvs.
-        */
-        void Merge(const Pvs<T, S> &a);
+                Warning: very slow!
+        */
+        void MergeInPlace(const Pvs<T, S> &a);
 
         /** Difference of pvs to pvs b.
@@ -141 +166 @@
 
         /** Finds sample in PVS.
-                @returns sample if found, NULL otherwise.
-        */
-        S *Find(T sample);
+                @returns iterator on the sample.
+        */
+        typename vector<PvsEntry<T, S> >::iterator Find(T sample);
 
         bool GetSampleContribution(T sample, const float pdf, float &contribution);
@@ -157 +182 @@
         */
         float AddSample(T sample, const float pdf);
+        
+        /** Adds sample to PVS.
+                @returns contribution of sample (0 or 1)
+        */
+        float AddSamples(const vector<PvsEntry<T, S> > &samples);
 
         /** Adds sample to PVS.
                 @returns PvsData
         */
-        S *AddSample2(T sample, const float pdf);
-
-        /** Adds one pvs to another one.
-                @returns new pvs size
-        */
-        int AddPvs(const Pvs<T, S> &pvs);
+        typename std::vector<PvsEntry<T, S> >::iterator AddSample2(T sample, const float pdf);
 
         /** Subtracts one pvs from another one.
@@ -173 +198 @@
         */
         int SubtractPvs(const Pvs<T, S> &pvs);
+
         /** Returns PVS data, i.e., how often it was seen from the view cell, 
                 and the object itsef.
@@ -189 +215 @@
         /** Compute continuous PVS difference 
         */
-        void ComputeContinuousPvsDifference(Pvs<T, S> &pvs,
-                float &pvsReduction,
-                float &pvsEnlargement);
-
+        void ComputeContinuousPvsDifference(Pvs<T, S> &pvs, 
+                                                                                float &pvsReduction,
+                                                                                float &pvsEnlargement);
 
         /** Clears the pvs.
@@ -201 +226 @@
         static float GetEntrySize();
 
-        /** Compute continuous PVS difference */
-        float GetPvsHomogenity(Pvs<T, S> &pvs) {
-                float pvsReduction, pvsEnlargement;
-
-                ComputeContinuousPvsDifference(pvs,
-                        pvsReduction,
-                        pvsEnlargement);
-
-                return pvsReduction + pvsEnlargement;
-        }
-
-        int Size() { return mEntries.size(); }
-
-        //vector<pair<T, S> >::const_iterator &GetConstIterator() const { return mEntries.begin(); }
-        //vector<pair<T, S> >::iterator &GetIterator() { return mEntries.begin(); }
+        /** Compute continuous PVS difference 
+        */
+        float GetPvsHomogenity(Pvs<T, S> &pvs);
+
+        static void Merge(Pvs<T, S> &mergedPvs, const Pvs<T, S> &a, const Pvs<T, S> &b);
 
 //protected:
 
         /// vector of PVS entries
-        vector<pair<T, S> > mEntries; 
+        vector<PvsEntry<T, S> > mEntries; 
         
         /// Number of samples used to create the PVS
@@ -227 +242 @@
 
 
+template <typename T, typename S>
+Pvs<T, S>::Pvs(const vector<PvsEntry<T, S> > &samples)
+{
+        mEntries.reserve(samples.size());
+        mEntries = samples;
+}
+
 
 /**
@@ -236 +258 @@
 void
 Pvs<T, S>::ComputeContinuousPvsDifference(Pvs<T, S> &b,
-                                                                           float &pvsReduction,
-                                                                           float &pvsEnlargement)
+                                                                                  float &pvsReduction,
+                                                                                  float &pvsEnlargement)
 {
         pvsReduction = 0.0f;
         pvsEnlargement = 0.0f;
+
         // Uses sum of log differences, which corresponds to entropy
-        std::vector<pair<T, S> >::iterator it;
+        std::vector<PvsEntry<T, S> >::iterator it;
 
         for (it = b.mEntries.begin(); it != b.mEntries.end(); ++ it) 
         {
-                float bSumPdf = (*it).second.mSumPdf;
+                float bSumPdf = (*it).mData.mSumPdf;
                 float aSumPdf = 0.0f;
-                S *data = Find((*it).first);            
-
-                if (data) 
+
+                vector<PvsEntry<T, S> >::iterator oit = Find((*it).mObject);            
+
+                const bool entryFound = (it != mEntries.end()) && ((*it).mObject == (*oit).mObject);
+
+                if (entryFound)
                 {
-                        aSumPdf = data->mSumPdf;
+                        aSumPdf = (*it).mData.mSumPdf;
+
                         // mark this entry as processed to avoid double counting
-                        data->mSumPdf = -aSumPdf;
+                        (*it).mData.mSumPdf = -aSumPdf;
                 }
 
 #if 0
-                float diff = bSumPdf - aSumPdf;
+                const float diff = bSumPdf - aSumPdf;
 
                 if (diff > 0.0f) {
@@ -266 +293 @@
                 }
 #else
-                if (!data)
+                if (!entryFound)
                         pvsEnlargement += 1.0f;
 #endif
         }
 
-        for (it = mEntries.begin(); it != mEntries.end(); ++ it) {
-                float aSumPdf = (*it).second.mSumPdf;
+        for (it = mEntries.begin(); it != mEntries.end(); ++ it) 
+        {
+                float aSumPdf = (*it).mData.mSumPdf;
                 float bSumPdf = 0.0f;
                 if (aSumPdf < 0.0f) {
+                
                         // this entry was already accounted for!
                         // just revert it back
-                        (*it).second.mSumPdf = -aSumPdf;
+                        (*it).mData.mSumPdf = -aSumPdf;
                 } else {
-                        S *data = b.Find((*it).first);
-                        if (data) {
-                                bSumPdf = data->mSumPdf;
+                        vector<PvsEntry<T, S> >::iterator oit = b.Find((*it).mObject);
+
+                        const bool entryFound = (it != mEntries.end()) && ((*it).mObject == (*oit).mObject);
+                        
+                        if (entryFound) {
+                                bSumPdf = (*oit).mData.mSumPdf;
                         }
 #if 0
-                        float diff = bSumPdf - aSumPdf;
+                        const float diff = bSumPdf - aSumPdf;
 
                         if (diff > 0.0f) {
@@ -293 +325 @@
 
 #else
-                        if (!data) 
+                        if (!entryFound) 
                                 pvsReduction += 1.0f;
 #endif
@@ -306 +338 @@
         int dif = 0;
 
-        std::vector<pair<T, S> >::const_iterator it;
+        std::vector<PvsEntry<T, S> >::const_iterator it;
 
         for (it = b.mEntries.begin(); it != b.mEntries.end(); ++ it)
         {
-                S data = Find((*it).first);             
-                if (!data) ++ dif;
+                std::vector<PvsEntry<T, S> >::const_iterator bit = Find((*it).first);           
+                if (bit == mEntries.end()) ++ dif;
         }
 
@@ -317 +349 @@
 }
 
-template <typename T, typename S> void Pvs<T, S>::Merge(const Pvs<T, S> &a)
-{
-#if TODO
+
+template <typename T, typename S> 
+void Pvs<T, S>::MergeInPlace(const Pvs<T, S> &a)
+{
+    const int samples = mSamples + a.mSamples;
+
+        ObjectPvs interPvs;
+        
+        Merge(interPvs, *this, a);
+        
+        mEntries.reserve(interPvs.GetSize());
+        mEntries = interPvs.mEntries;
+
+        mSamples = samples;
+}
+
+
+template <typename T, typename S>
+void Pvs<T, S>::Merge(Pvs<T, S> &mergedPvs, const Pvs<T, S> &a, const Pvs<T, S> &b)
+{
+        std::vector<PvsEntry<T, S> >::const_iterator ait = a.mEntries.begin(), ait_end = a.mEntries.end();
+        std::vector<PvsEntry<T, S> >::const_iterator bit = b.mEntries.begin(), bit_end = b.mEntries.end();
+
+        while (1)
+        {
+                for (; (ait != ait_end) && ((*ait).mObject < (*bit).mObject); ++ ait)
+                {
+                        if ((*ait).mObject != (*bit).mObject)
+                                mergedPvs.mEntries.push_back(*ait);
+                }
+
+                for (; (bit != bit_end) && ((ait == ait_end) || ((*bit).mObject <= (*bit).mObject)); ++ bit)
+                {
+                        if ((*ait).mObject == (*bit).mObject)
+                        {
+                                PvsData newData((*ait).mData.mSumPdf + (*bit).mData.mSumPdf);
+                                PvsEntry<T, S> entry((*ait).mObject, newData);
+                                mergedPvs.mEntries.push_back(entry);
+                        }
+                        else
+                        {
+                                mergedPvs.mEntries.push_back(*bit);
+                        }
+                }
+        }
+}
+
+
+/*template <typename T, typename S> void Pvs<T, S>::QuickMerge(const Pvs<T, S> &a)
+{
         const int samples = mSamples + a.mSamples;
 
-        std::vector<pair<T, S>> >::const_iterator it;
-
-        for (it = a.mEntries.begin(); it != a.mEntries.end(); ++ it)
-        {
-                AddSample((*it).first, (*it).second.mSumPdf);
+        std::vector<PvsEntry<T, S>> >::const_iterator it;
+
+        for (it = mEntries.begin(); it != mEntries.end(); ++ it)
+        {
+                it->first->Mail();
+        }
+
+    for (it = a.mEntries.begin(); it != a.mEntries.end(); ++ it)
+        {
+                if (!it->first->Mailed())
+                {
+                        mEntries.push_back(*it);
+                }
         }
 
         mSamples = samples;
-#endif
-}
+}*/
 
 
@@ -341 +427 @@
 
 template <typename T, typename S> 
-S *Pvs<T, S>::Find(T sample)
-{
-#if TODO
-  std::vector<pair<T, S>, LtSample<T> >::iterator i = mEntries.find(sample);
-
-  if (i != mEntries.end()) 
-  {
-          return &(*i).second;
-  } 
-  else
-  {
-          return NULL;
-  }
-#else
-return NULL;
-#endif
-}
-
-template <typename T, typename S>
-void Pvs<T, S>::GetData(const int index,
-                                         T &entry,
-                                         S &data)
-{
-        std::vector<pair<T, S> >::iterator i = mEntries.begin();
+typename std::vector<PvsEntry<T, S> >::iterator Pvs<T, S>::Find(T sample)
+{
+        PvsEntry<T, S> dummy(sample, PvsData());
+        vector<PvsEntry<T, S> >::iterator it = lower_bound(mEntries.begin(), mEntries.end(), dummy);
+                                
+        return it;
+}
+
+
+template <typename T, typename S>
+void Pvs<T, S>::GetData(const int index, T &entry, S &data)
+{
+        std::vector<PvsEntry<T, S> >::iterator i = mEntries.begin();
         for (int k = 0; k != index && i != mEntries.end(); ++ i, ++ k);
 
@@ -373 +448 @@
 
 template <typename T, typename S>
-float
-Pvs<T, S>::AddSample(T sample, const float pdf)
-{
-#if TODO
+float Pvs<T, S>::AddSample(T sample, const float pdf)
+{
         ++ mSamples;
-        S *data = Find(sample);
-
-        if (data)  
-        {
+        std::vector<PvsEntry<T, S> >::iterator it = Find(sample);
+
+        if ((it != mEntries.end()) && ((*it).mObject == sample))
+        {
+                S &data = (*it).mData;
+                data.mSumPdf += pdf;
+
+                return data.mSumPdf;
+        }
+        else 
+        {
+                PvsEntry<T, S> entry(sample, pdf);
+                
+                mEntries.insert(it, entry);
+                return pdf;
+        }
+}
+
+
+template <typename T, typename S>
+typename vector< PvsEntry<T, S> >::iterator Pvs<T, S>::AddSample2(T sample, const float pdf)
+{
+        ++ mSamples;
+        std::vector<PvsEntry<T, S> >::iterator it = Find(sample);
+
+        if ((it != mEntries.end()) && ((*it).first == T))
+        {
+                S &data = (*it).second;
                 data->mSumPdf += pdf;
-                return data->mSumPdf;
         }
         else 
         {
-                mEntries[sample] = S(pdf);
-                return pdf;
-        }
-#else
-return 0;
-#endif
-}
-
-
-template <typename T, typename S>
-S * Pvs<T, S>::AddSample2(T sample, const float pdf)
-{
-  mSamples++;
-  S *data = Find(sample);
-  
-  if (data)  
-        {
-          data->mSumPdf += pdf;
-        }
-  else 
-        {
-          mEntries[sample] = S(pdf);
-          data = Find(sample);
-        }
-  
-  return data;
-}
+                PvsEntry<T, S> entry(sample, pdf);
+                mEntries.insert(it, entry);
+        }
+
+        return it;
+}
+
 
 template <typename T, typename S> 
 bool Pvs<T, S>::AddSample(T sample,
-                                  const float pdf,
-                                  float &contribution)
+                                                  const float pdf,
+                                                  float &contribution)
 {
         ++ mSamples;
-    S *data = Find(sample);
-#if TODO
-        if (data)  
-        {
-                data->mSumPdf += pdf;
-                contribution = pdf / data->mSumPdf;
+
+        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 {
-                mEntries[sample] = S(pdf);
+        else 
+        {
+                PvsEntry<T, S> entry(sample, pdf);
+
+                mEntries.insert(it, entry);
+                contribution = 1.0f;
+
+                return true;
+        }
+}
+
+
+template <typename T, typename S>
+bool Pvs<T, S>::GetSampleContribution(T sample,
+                                                                          const float pdf,
+                                                                          float &contribution) 
+{
+        std::vector<PvsEntry<T, S> >::iterator it = Find(sample);
+
+        if (it != mEntries.end() && ((*it).mObject == sample))  
+        {
+                S &data = (*it).mData;
+                contribution = pdf / (data.mSumPdf + pdf);
+                return false;
+        }
+        else 
+        {
                 contribution = 1.0f;
                 return true;
         }
-#else
+}
+
+
+template <typename T, typename S>
+bool Pvs<T, S>::RemoveSample(T sample, const float pdf)
+{
+        -- mSamples;
+
+        std::vector<PvsEntry<T, S> >::iterator it = Find(sample);
+
+        if (it == mEntries.end())
+                return false;
+
+        S &data = (*it).mData;
+
+        data.mSumPdf -= pdf;
+
+        if (data.mSumPdf <= 0.0f)
+        {
+                mEntries.erase(it);
+        }
+
         return true;
-#endif
-}
-
-template <typename T, typename S>
-bool
-Pvs<T, S>::GetSampleContribution(T sample,
-                                                                 const float pdf,
-                                                                 float &contribution) 
-{
-  S *data = Find(sample);
-  
-  if (data)  {
-        contribution = pdf / (data->mSumPdf + pdf);
-        return false;
-  }
-  else {
-        contribution = 1.0f;
-        return true;
-  }
-}
-
-template <typename T, typename S>
-bool Pvs<T, S>::RemoveSample(T sample,
-                                                         const float pdf)
-{
-  -- mSamples;
-#if TODO
-  std::vector<pair<T, S> >::iterator it = mEntries.find(sample);
-  
-  if (it == mEntries.end())
-        return false;
-  
-  S *data = &(*it).second;
-  
-  data->mSumPdf -= pdf;
-
-  if (data->mSumPdf <= 0.0f)
-  {
-          mEntries.erase(it);
-  }
-#endif
-  return true;
-}
-
-template <typename T, typename S>
-int Pvs<T, S>::AddPvs(const Pvs<T, S> &pvs)
-{
-  int samples = mSamples + pvs.mSamples;
-  std::vector<pair<T, S> >::
-        const_iterator it, it_end = pvs.mEntries.end();
-  
-  float contri;
-  // output PVS of view cell
-  for (it = pvs.mEntries.begin(); it != it_end; ++ it)
-  {     
-          AddSample((*it).first, (*it).second.mSumPdf, contri);
-  }
-
-  mSamples = samples;
-
-  return GetSize();
-}
- 
+}
+
+
 template <typename T, typename S>
 int Pvs<T, S>::SubtractPvs(const Pvs<T, S> &pvs)
 {
         const int samples = mSamples - pvs.mSamples;
-#if TODO
-        std::vector<pair<T, S> >::
+
+        std::vector<PvsEntry<T, S> >::
                 const_iterator it, it_end = pvs.mEntries.end();
 
         // output PVS of view cell
         for (it = pvs.mEntries.begin(); it != it_end; ++ it) 
-                RemoveSample((*it).first, (*it).second.mSumPdf);
+                RemoveSample((*it).mObject, (*it).mData.mSumPdf);
 
         mSamples = samples;
-#endif
+
         return GetSize();
 }
 
+
 template <typename T, typename S>
 void Pvs<T, S>::CollectEntries(std::vector<T> &entries)
 {
-        std::vector<pair<T, S> >::
+        std::vector<PvsEntry<T, S> >::
                 const_iterator it, it_end = mEntries.end();
 
@@ -527 +594 @@
 }
 
+
 template <typename T, typename S>
 void Pvs<T, S>::NormalizeMaximum()
 {
-  std::vector<pair<T, S> >::
-        const_iterator it, it_end = mEntries.end();
-
-  float maxPdfSum = -1.0f;
-
-  // output PVS of view cell
-  for (it = mEntries.begin(); it != it_end; ++ it) {
-        float sum = (*it)->second.sumPdf;
-        if (sum > maxSum)
-          maxSum = sum;
-  }
-
-  maxSum = 1.0f / maxSum;
-
-  for (it = mEntries.begin(); it != it_end; ++ it) {
-        (*it)->second.sumPdf *= maxSum;
-  }
-  
+        std::vector<PvsEntry<T, S> >::
+                const_iterator it, it_end = mEntries.end();
+
+        float maxPdfSum = -1.0f;
+
+        // output PVS of view cell
+        for (it = mEntries.begin(); it != it_end; ++ it) {
+                float sum = (*it)->second.sumPdf;
+                if (sum > maxSum)
+                        maxSum = sum;
+        }
+
+        maxSum = 1.0f / maxSum;
+
+        for (it = mEntries.begin(); it != it_end; ++ it) {
+                (*it)->second.sumPdf *= maxSum;
+        }
+
 }
 
@@ -562 +630 @@
 {
         return sizeof(T) + sizeof(S);
+}
+
+
+template <typename T, typename S>
+float Pvs<T, S>::GetPvsHomogenity(Pvs<T, S> &pvs) 
+{
+        float pvsReduction, pvsEnlargement;
+
+        ComputeContinuousPvsDifference(pvs,     pvsReduction, pvsEnlargement);
+
+        return pvsReduction + pvsEnlargement;
 }
 
@@ -590 +669 @@
 //-- typedefs
 
-//typedef std::map<KdNode *, PvsData, LtSample<KdNode *> > KdPvsMap;
-//typedef std::map<Intersectable *, PvsData, LtSample<Intersectable *> > ObjectPvsEntries;
-//typedef std::map<ViewCell *, MailablePvsData, LtSample<ViewCell *> > ViewCellPvsEntries;
-
-
-typedef std::vector<pair<Intersectable *, PvsData> > ObjectPvsEntries;
-
+typedef std::vector<PvsEntry<Intersectable *, PvsData> > ObjectPvsEntries;
 typedef Pvs<ViewCell *, MailablePvsData> ViewCellPvs;
 

GTP/trunk/Lib/Vis/Preprocessing/src/TestPreprocessor.vcproj

@@ -206 +206 @@
                                 Name="VCLinkerTool"
                                 AdditionalDependencies="xerces-c_2.lib glew32.lib zdll.lib zziplib.lib devil.lib glut32.lib OpenGL32.Lib glu32.lib Preprocessor.lib RTScene.lib RTWorld.lib QtCore4.lib qtmain.lib QtOpenGL4.lib Qt3Support4.lib QtTest4.lib QtGui4.lib QtGlRenderer.lib"
-                                OutputFile="../bin/release/Preprocessor2.exe"
+                                OutputFile="../bin/release/Preprocessor.exe"
                                 LinkIncremental="1"
                                 AdditionalLibraryDirectories="..\src\GL;..\lib\release;..\..\Preprocessing\lib\release;..\..\..\..\..\..\NonGTP\Boost\lib;..\..\..\..\..\..\NonGTP\Xerces\xercesc\lib;..\..\..\..\..\..\NonGTP\Zlib\lib;..\..\..\..\..\..\NonGTP\Devil\lib;..\MultiLevelRayTracing\RTScene\Release;..\MultiLevelRayTracing\RTWorld\Release;"$(QTDIR)\lib";.\QtGlRenderer\Release"

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

@@ -64 +64 @@
         for (it = vc->GetPvs().mEntries.begin(); it != it_end; ++ it)
         {
-                if (!(*it).first->Mailed())
-                {
-                        (*it).first->Mail();
+                if (!(*it).mObject->Mailed())
+                {
+                        (*it).mObject->Mail();
                         ++ count;
                 }
@@ -88 +88 @@
         for (it = pvs1.mEntries.begin(); it != it_end; ++ it)
         {
-                (*it).first->Mail();
+                (*it).mObject->Mail();
         }
 
@@ -96 +96 @@
         for (it = pvs2.mEntries.begin(); it != it_end; ++ it)
         {
-                Intersectable *obj = (*it).first;
+                Intersectable *obj = (*it).mObject;
                 if (!obj->Mailed())
                         ++ pvs;
@@ -837 +837 @@
         for (it = pvs1.mEntries.begin(); it != it_end; ++ it)
         {
-                Intersectable *obj = (*it).first;
+                Intersectable *obj = (*it).mObject;
 
                 obj->Mail();
@@ -848 +848 @@
         for (it = pvs2.mEntries.begin(); it != it_end; ++ it)
         {
-                Intersectable *obj = (*it).first;
+                Intersectable *obj = (*it).mObject;
 
                 // test if object already considered    
@@ -1152 +1152 @@
 inline int AddedPvsSize(ObjectPvs pvs1, const ObjectPvs &pvs2)
 {
-        return pvs1.AddPvs(pvs2);
+        ObjectPvs interPvs;
+        ObjectPvs::Merge(interPvs, pvs1, pvs2);
+
+        return (int)interPvs.GetSize();
 }
 
@@ -1242 +1245 @@
         // TODO change
         vc1->GetPvs().SubtractPvs(leaf->GetPvs());
-        vc2->GetPvs().AddPvs(leaf->GetPvs());
-        
+        
+        ObjectPvs interPvs;
+        ObjectPvs::Merge(interPvs, vc2->GetPvs(), leaf->GetPvs());
+        vc2->SetPvs(interPvs);
+
         if (mUseAreaForPvs)
         {
@@ -1651 +1657 @@
                 for (oit = vc->GetPvs().mEntries.begin(); oit != oit_end; ++ oit)
                 {
-                        Intersectable *obj = (*oit).first;
+                        Intersectable *obj = (*oit).mObject;
                         if ((cit == interior->mChildren.begin()) && !obj->Mailed())
                                 obj->Mail();
@@ -1673 +1679 @@
                 for (oit = vc->GetPvs().mEntries.begin(); oit != oit_end; ++ oit)
                 {               
-                        if ((*oit).first->Mailed((int)interior->mChildren.size()))
+                        if ((*oit).mObject->Mailed((int)interior->mChildren.size()))
                         {       
-                                interior->GetPvs().AddSample((*oit).first, (*oit).second.mSumPdf);
+                                interior->GetPvs().AddSample((*oit).mObject, (*oit).mData.mSumPdf);
                         }
                 }
@@ -1688 +1694 @@
                 for (cit = interior->mChildren.begin(); cit != cit_end; ++ cit)
                 {
-                        if (!(*cit)->GetPvs().RemoveSample((*oit).first, Limits::Infinity))
+                        if (!(*cit)->GetPvs().RemoveSample((*oit).mObject, Limits::Infinity))
                         {
                                 Debug << "should not come here!" << endl;
@@ -1717 +1723 @@
         {
                 root = root->GetParent();
-                pvs.AddPvs(root->GetPvs());
+                pvs.MergeInPlace(root->GetPvs());
         }
 
@@ -1730 +1736 @@
 
                 // add newly found pvs to merged pvs
-                pvs.AddPvs(vc->GetPvs());
+                ObjectPvs interPvs;
+                pvs.MergeInPlace(vc->GetPvs());
 
                 if (!vc->IsLeaf()) // interior cells: go down to leaf level
@@ -1779 +1786 @@
                 for (oit = (*it)->GetPvs().mEntries.begin(); oit != oit_end; ++ oit)
                 {
-                        Intersectable *intersect = (*oit).first;
+                        Intersectable *intersect = (*oit).mObject;
 
                         if (!intersect->Mailed())
                         {
                                 intersect->Mail();
-                                newPvs.AddSample(intersect, (*oit).second.mSumPdf);
+                                newPvs.AddSample(intersect, (*oit).mData.mSumPdf);
                         }
                 }
@@ -1829 +1836 @@
                 for (oit = (*it)->GetPvs().mEntries.begin(); oit != oit_end; ++ oit)
                 {
-                        Intersectable *intersect = (*oit).first;
+                        Intersectable *intersect = (*oit).mObject;
 
                         if (!intersect->Mailed())
@@ -2050 +2057 @@
 
 
-void ViewCellsTree::PropagatePvs(ViewCell *vc)
+void ViewCellsTree::PropagatePvs(ViewCell *root)
 {       
-        ViewCell *viewCell = vc;
+        ViewCell *viewCell = root;
 
         // propagate pvs up
         while (viewCell->GetParent())
         {
-                viewCell->GetParent()->GetPvs().Merge(vc->GetPvs());
+                ObjectPvs mergedPvs;
+                viewCell->GetParent()->GetPvs().MergeInPlace(root->GetPvs());
+
                 viewCell = viewCell->GetParent();
         }
 
-        if (vc->IsLeaf())
+        if (root->IsLeaf())
                 return;
 
         // propagate pvs to the leaves
         stack<ViewCell *> tstack;
-        tstack.push(vc);
+        tstack.push(root);
 
         while (!tstack.empty())
@@ -2073 +2082 @@
                 tstack.pop();
 
-                if (viewCell != vc)
-                {
-                        viewCell->GetPvs().Merge(vc->GetPvs());
+                if (viewCell != root)
+                {
+                        viewCell->GetPvs().MergeInPlace(root->GetPvs());
                 }
 
@@ -2105 +2114 @@
                 tqueue.pop();
 
-                // save the view cells if it is a leaf or if enough view cells have already been traversed
-                // because of the priority queue, this will be the optimal set of v
+                // save the view cells if it is a leaf or if enough view cells 
+                // have already been traversed because of the priority queue, 
+                // this will be the optimal set of v
                 if (!vc->IsLeaf()) 
                 {       
@@ -2343 +2353 @@
         for (it = viewCell->GetPvs().mEntries.begin(); it != it_end; ++ it)
         {
-                Intersectable *obj = (*it).first;
+                Intersectable *obj = (*it).mObject;
                 // hack: just output full pvs
                 if (obj->Type() == Intersectable::BVH_INTERSECTABLE)
@@ -2359 +2369 @@
                 else
                 {
-                        stream << (*it).first->GetId() << " ";
+                        stream << (*it).mObject->GetId() << " ";
                 }
         }

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

@@ -1647 +1647 @@
 
         vc->GetPvs().Clear();
-        vc->GetPvs() = left->GetPvs();
-
-        // merge pvs of right cell
-        vc->GetPvs().Merge(right->GetPvs());
+        ObjectPvs::Merge(vc->GetPvs(), left->GetPvs(), right->GetPvs());
 
         // set only links to child (not from child to parent, maybe not wished!!)
@@ -1666 +1663 @@
 {
         ViewCellInterior *vc = new ViewCellInterior();
-
         ViewCellContainer::const_iterator it, it_end = children.end();
 
         for (it = children.begin(); it != it_end; ++ it)
         {
-                // merge pvs
-                vc->GetPvs().Merge((*it)->GetPvs());
+                vc->GetPvs().MergeInPlace((*it)->GetPvs());
+        
                 vc->mChildren.push_back(*it);
         }
@@ -2399 +2395 @@
                         ViewCellContainer::const_iterator it = viewCells.begin(), it_end = viewCells.end();
 
-                        int i;
-                        for (i=0; it != it_end; ++ it, ++ i) {
+                        for (; it != it_end; ++ it) 
+                        {
+                                ObjectPvs interPvs;
                                 //cout<<"v"<<i<<" pvs="<<(*it)->GetPvs().mEntries.size()<<endl;
-                                pvs.Merge((*it)->GetPvs());
+                                ObjectPvs::Merge(interPvs, pvs, (*it)->GetPvs());
+
+                                pvs = interPvs;
                         }
-                } else {
+                } else 
+                {
                         PrVs prvs;
                         AxisAlignedBox3 box = GetViewCellBox(viewCell);
@@ -2413 +2413 @@
                         DeleteLocalMergeTree(prvs.mViewCell);
                 }
-        } else
+        } 
+        else
+        {
                 pvs = viewCell->GetPvs();
+        }
 
         if (spatialFilterSize >=0.0f)
@@ -2479 +2482 @@
   for (oi = pvs.mEntries.begin(); oi != pvs.mEntries.end(); ++ oi) 
         {
-          Intersectable *object = (*oi).first;
+          Intersectable *object = (*oi).mObject;
       object->Mail();
         }
@@ -2487 +2490 @@
   // now go through the pvs again
   for (oi = pvs.mEntries.begin(); oi != pvs.mEntries.end(); ++oi) {
-        Intersectable *object = (*oi).first;
+        Intersectable *object = (*oi).mObject;
 
         //      Vector3 center = object->GetBox().Center();
@@ -2511 +2514 @@
   }
   //  cout<<"nPvs size = "<<nPvsSize<<endl;
-  pvs.Merge(nPvs);
+
+  pvs.MergeInPlace(nPvs);
 }
 
@@ -2530 +2534 @@
   // first mark all object from this pvs
   for (oi = pvs.mEntries.begin(); oi != pvs.mEntries.end(); ++ oi) {
-        Intersectable *object = (*oi).first;
+        Intersectable *object = (*oi).mObject;
         object->Mail();
   }
@@ -2551 +2555 @@
   float sumRadius = 0.0f;
   for (oi = pvs.mEntries.begin(); oi != pvs.mEntries.end(); ++oi, pvsSize++) {
-        Intersectable *object = (*oi).first;
+        Intersectable *object = (*oi).mObject;
         // compute filter size based on the distance and the numebr of samples
         AxisAlignedBox3 box = object->GetBox();
@@ -2558 +2562 @@
         float globalRadius = distance*globalC;
 
-        int objectSamples = (int)(*oi).second.mSumPdf;
+        int objectSamples = (int)(*oi).mData.mSumPdf;
         float localRadius = MAX_FLOAT;
         
@@ -2591 +2595 @@
           if ((*it) != viewCell) {
                 //cout<<"v"<<i<<" pvs="<<(*it)->GetPvs().mEntries.size()<<endl;
-                pvs.Merge((*it)->GetPvs());
+                  pvs.MergeInPlace((*it)->GetPvs());
           }
 
@@ -2602 +2606 @@
   
   for (oi = pvs.mEntries.begin(); oi != pvs.mEntries.end(); ++oi) {
-        Intersectable *object = (*oi).first;
+        Intersectable *object = (*oi).mObject;
         // compute filter size based on the distance and the numebr of samples
         AxisAlignedBox3 box = object->GetBox();
@@ -2610 +2614 @@
 
         
-        int objectSamples = (int)(*oi).second.mSumPdf;
+        int objectSamples = (int)(*oi).mData.mSumPdf;
         float localRadius = MAX_FLOAT;
         if (objectSamples > MIN_LOCAL_SAMPLES)
@@ -2639 +2643 @@
   }
   cout<<"nPvs size = "<<nPvsSize<<endl;
-  pvs.Merge(nPvs);
+  
+  pvs.MergeInPlace(nPvs);
+
   Intersectable::NewMail();
 }
@@ -2784 +2790 @@
                 for (pit = (*oit).mEntries.begin(); pit != pit_end; ++ pit)
                 {
-                        Intersectable *intersect = (*pit).first;
+                        Intersectable *intersect = (*pit).mObject;
 
                         if (!intersect->Mailed())
                         {
-                                pvs.AddSample(intersect, (*pit).second.mSumPdf);
+                                pvs.AddSample(intersect, (*pit).mData.mSumPdf);
                                 intersect->Mail();
                         }
@@ -3273 +3279 @@
                         for (oit = pvs.mEntries.begin(); oit != oit_end; ++ oit)
                         {               
-                                Intersectable *intersect = (*oit).first;
+                                Intersectable *intersect = (*oit).mObject;
                                 
                                 if (!intersect->Mailed())
@@ -3773 +3779 @@
                         for (it = vc->GetPvs().mEntries.begin(); it != it_end; ++ it)
                         {
-                                Intersectable *intersect = (*it).first;
+                                Intersectable *intersect = (*it).mObject;
                                 if (!intersect->Mailed())
                                 {
@@ -4622 +4628 @@
                         for (oit = pvs.mEntries.begin(); oit != oit_end; ++ oit)
                         {               
-                                Intersectable *intersect = (*oit).first;
+                                Intersectable *intersect = (*oit).mObject;
                                 
                                 if (!intersect->Mailed())
@@ -4745 +4751 @@
                 else
                 {
-                        (*it).second.Merge(sample.mPvs);
+                        (*it).second.MergeInPlace(sample.mPvs);
                 }
         }
@@ -4980 +4986 @@
 
 
+VspOspViewCellsManager::VspOspViewCellsManager(ViewCellsTree *vcTree, const string &hierarchyType)
+: ViewCellsManager(vcTree)
+{
+        Environment::GetSingleton()->GetIntValue("Hierarchy.Construction.samples", mInitialSamples);
+
+        mHierarchyManager = CreateHierarchyManager(hierarchyType);
+        mHierarchyManager->SetViewCellsManager(this);
+        mHierarchyManager->SetViewCellsTree(mViewCellsTree);
+}
+
+
 VspOspViewCellsManager::VspOspViewCellsManager(ViewCellsTree *vcTree, HierarchyManager *hm)
 : ViewCellsManager(vcTree), mHierarchyManager(hm)
@@ -4990 +5007 @@
 
 
+HierarchyManager *VspOspViewCellsManager::CreateHierarchyManager(const string &hierarchyType)
+{
+        HierarchyManager *hierarchyManager;
+
+        if (strcmp(hierarchyType.c_str(), "osp") == 0)
+        {
+                Debug << "hierarchy manager: osp" << endl;
+                hierarchyManager = new HierarchyManager(HierarchyManager::KD_BASED_OBJ_SUBDIV);
+        }
+        else if (strcmp(hierarchyType.c_str(), "bvh") == 0)
+        {
+                Debug << "hierarchy manager: bvh" << endl;
+                hierarchyManager = new HierarchyManager(HierarchyManager::BV_BASED_OBJ_SUBDIV);
+        }
+        else // only view space partition
+        {
+                Debug << "hierarchy manager: obj" << endl;
+                hierarchyManager = new HierarchyManager(HierarchyManager::NO_OBJ_SUBDIV);
+        }
+
+        return hierarchyManager;
+}
+
+
 VspOspViewCellsManager::~VspOspViewCellsManager()
 {
+        DEL_PTR(mHierarchyManager);
 }
 
@@ -5453 +5495 @@
                         for (oit = pvs.mEntries.begin(); oit != oit_end; ++ oit)
                         {               
-                                Intersectable *intersect = (*oit).first;
+                                Intersectable *intersect = (*oit).mObject;
                                 if (!intersect->Mailed())
                                 {

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

@@ -1047 +1047 @@
 class VspOspViewCellsManager: public ViewCellsManager
 {
-
+        friend class ViewCellsParseHandlers;
 public:
 
-        VspOspViewCellsManager(ViewCellsTree *vcTree, HierarchyManager *hm);
+        VspOspViewCellsManager(ViewCellsTree *vcTree, const string &hierarchyType);
         
         ~VspOspViewCellsManager();
@@ -1120 +1120 @@
 protected:
 
+        VspOspViewCellsManager(ViewCellsTree *vcTree, HierarchyManager *hm);
+        
 #if 1//TEST_EVALUATION
         virtual void EvalViewCellPartition();
@@ -1148 +1150 @@
         void ExportPvs(const ObjectContainer &objects, const VssRayContainer &rays);
 
+        /** Returns a hierarchy manager of the given name.
+        */
+        static HierarchyManager *CreateHierarchyManager(const string &name);
+
         //void ExportStats(const string &mergeStats);