source: GTP/trunk/Lib/Vis/Preprocessing/src/Pvs.h @ 2530

#ifndef __VERBOSEPVS_H
#define __VERBOSEPVS_H

#include <vector>
#include "common.h"
#include <math.h>
#include "PvsBase.h"



namespace GtpVisibilityPreprocessor {


/** Iterator over the pvs.
*/
template<typename T, typename S>
class PvsIterator
{
public:
        PvsIterator<T, S>(){}
        PvsIterator<T, S>(const typename vector<PvsEntry<T, S> >::const_iterator &itCurrent,
                                          const typename vector<PvsEntry<T, S> >::const_iterator &itEnd):
        mItCurrent(itCurrent), mItEnd(itEnd)
        {
        }

        inline bool HasMoreEntries() const { return (mItCurrent != mItEnd);     }

        inline T Next(S &pdf) {
                pdf = (*mItCurrent).mData;
                return (*(mItCurrent ++)).mObject;
        }

        inline T Next() { return (*(mItCurrent ++)).mObject; }


private:
        
        typename vector<PvsEntry<T, S> >::const_iterator mItCurrent;
        typename vector<PvsEntry<T, S> >::const_iterator mItEnd;
};


/** Template class representing the Potentially Visible Set (PVS) 
        mainly from a view cell, but also e.g., from objects.
*/
template<typename T, typename S>
class VerbosePvs
{
        template<typename T, typename S> friend class PvsIterator;

public:

        VerbosePvs(): mSamples(0), mEntries(), mLastSorted(0), mQueriesSinceSort(0) 
        {}

        /** creates pvs and initializes it with the given entries. 
                Assumes that entries are sorted.
        */
        VerbosePvs(const vector<PvsEntry<T, S> > &samples);
        virtual ~VerbosePvs() {};

        /** Compresses PVS lossless or lossy.
        */
        int Compress() { return 0; }
        
        inline int GetSize() const { return (int)mEntries.size(); }
        
        inline bool Empty() const { return mEntries.empty(); }

        inline void Reserve(const int n) { mEntries.reserve(n); }
        /** Normalize the visibility of entries in order to get 
                comparable results.
        */
        void NormalizeMaximum();
        /** Merges pvs of a into this pvs.
                Warning: very slow!
        */
        void MergeInPlace(const VerbosePvs<T, S> &a);
        /** Difference of pvs to pvs b.
        @returns number of different entries.
        */
        int Diff(const VerbosePvs<T, S> &b);
        /** 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 vector<PvsEntry<T, S> >::iterator &it,
                          const bool checkDirty = true);

        bool GetSampleContribution(T sample, const float pdf, float &contribution);
        /** Adds sample to PVS.
                @returns contribution of sample (0 or 1)
        */
        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, 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);
        /** Sort pvs entries. This should always be called after a
                sequence of AddSampleDirty calls 
        */
        void Sort();
        /** Sort pvs entries assume that the pvs contains unique entries
        */
        void SimpleSort();
        /** Adds sample to PVS.
                @returns PvsData
        */
        typename std::vector<PvsEntry<T, S> >::iterator 
                AddSample2(T sample, const float pdf);
        /** Subtracts one pvs from another one.
                WARNING: could contains bugs
                @returns new pvs size
        */
        int SubtractPvs(const VerbosePvs<T, S> &pvs);

        /** Returns PVS data, i.e., how often it was seen from the view cell, 
                and the object itsef.
        */
        void GetData(const int index, T &entry, S &data);

        /** Collects the PVS entries and returns them in the vector.
        */
        void CollectEntries(std::vector<T> &entries);

        /** Removes sample from PVS if reference count is zero.
        @param visibleSamples number of references to be removed
        */
        bool RemoveSample(T sample, const float pdf);

        /** Compute continuous PVS difference 
        */
        void ComputeContinuousPvsDifference(VerbosePvs<T, S> &pvs, 
                                                                                float &pvsReduction,
                                                                                float &pvsEnlargement);

        /** Clears the pvs.
        */
        void Clear(const bool trim = true);
        /** Trim the vector containing the pvs.
        */
        void Trim();

        static int GetEntrySizeByte(); 
        static float GetEntrySize();

        /** Compute continuous PVS difference 
        */
        float GetPvsHomogenity(VerbosePvs<T, S> &pvs);

        static void Merge(VerbosePvs<T, S> &mergedPvs, 
                                          const VerbosePvs<T, S> &a, 
                                          const VerbosePvs<T, S> &b);

        inline int GetSamples() const { return mSamples; }

        /** If there is an unsorted part in the pvs.
        */
        bool IsDirty() const { return mLastSorted < mEntries.size(); }

        /** If this pvs requires a resort to stay efficient.
        */
        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 n = mEntries.size();
                const int dirtySize = n - mLastSorted;

                const double 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;
        }

        /** If this pvs requires a resort to stay efficient.
        */
        bool RequiresResortLog() 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 > 4 * (int)(log((double)mEntries.size()) / log(2.0));
        }

        inline int GetLastSorted() const { return mLastSorted; }

        typename PvsIterator<T, S> GetIterator() const;

protected:

        /** Merge pvs 1 from begin iterator to end iterator with
                pvs 2 from begin iterator to end iterator.
        */
        static void Merge(VerbosePvs<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);


        //////////////////////////////

        /// vector of PVS entries
        vector<PvsEntry<T, S> > mEntries; 

        /// Number of samples used to create the PVS
        int mSamples;

        /// Last sorted entry in the pvs (important for find and merge)
        int mLastSorted;

        int mQueriesSinceSort;
};


template <typename T, typename S>
VerbosePvs<T, S>::VerbosePvs(const vector<PvsEntry<T, S> > &samples)
{
        mEntries.reserve(samples.size());
        mEntries = samples;
        mLastSorted = 0;
        mSamples = samples.size();
}


template <typename T, typename S>
void VerbosePvs<T, S>::Sort()
{
        vector<PvsEntry<T, S> >::iterator it = mEntries.begin() + mLastSorted;
        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);
        
        // now merge sorted ranges
        ObjectPvs newPvs;
        Merge(newPvs, 
                  mEntries.begin(),
                  it, 
                  it,
                  newEnd, 
                  mSamples,
                  0);
        
        mEntries = newPvs.mEntries;
        mLastSorted = (int)mEntries.size();
        mQueriesSinceSort = 0;
}

template <typename T, typename S>
void VerbosePvs<T, S>::SimpleSort()
{
        //  sort(mEntries.begin(), mEntries.end());
        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;
}


/**
   Compute continuous PVS difference of 'b' with respect to the base PVS (*this).
   Provides separatelly PVS reduction from PVS enlargement.

*/
template <typename T, typename S>
void
VerbosePvs<T, S>::ComputeContinuousPvsDifference(VerbosePvs<T, S> &b,
                                                                                  float &pvsReduction,
                                                                                  float &pvsEnlargement)
{
        pvsReduction = 0.0f;
        pvsEnlargement = 0.0f;

        // Uses sum of log differences, which corresponds to entropy
        vector<PvsEntry<T, S> >::iterator it;

        for (it = b.mEntries.begin(); it != b.mEntries.end(); ++ it) 
        {
                float bSumPdf = (*it).mData.mSumPdf;
                float aSumPdf = 0.0f;

                vector<PvsEntry<T, S> >::iterator oit;
                const bool entryFound = Find((*it).mObject, oit);               

                if (entryFound)
                {
                        aSumPdf = (*it).mData.mSumPdf;

                        // mark this entry as processed to avoid double counting
                        (*it).mData.mSumPdf = -aSumPdf;
                }

#if 0
                const float diff = bSumPdf - aSumPdf;

                if (diff > 0.0f) 
                {
                        pvsEnlargement += diff;
                } 
                else 
                {
                        pvsReduction += -diff;
                }
#else
                if (!entryFound)
                {
                        pvsEnlargement += 1.0f;
                }
#endif
        }

        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).mData.mSumPdf = -aSumPdf;
                } 
                else 
                {
                        vector<PvsEntry<T, S> >::iterator oit;
                
                        const bool entryFound = b.Find((*it).mObject, oit);
                                                
                        if (entryFound) {
                                bSumPdf = (*oit).mData.mSumPdf;
                        }
#if 0
                        const float diff = bSumPdf - aSumPdf;

                        if (diff > 0.0f) {
                                pvsEnlargement += diff;
                        } else {
                                pvsReduction += -diff;
                        }

#else
                        if (!entryFound) 
                                pvsReduction += 1.0f;
#endif
                }
        }
}


template <typename T, typename S>
int VerbosePvs<T, S>::Diff(const VerbosePvs<T, S> &b)
{
        int dif = 0;

        std::vector<PvsEntry<T, S> >::const_iterator it;

        for (it = b.mEntries.begin(); it != b.mEntries.end(); ++ it)
        {
                vector<PvsEntry<T, S> >::iterator bit;
                const bool entryFound = Find((*it).first, bit);

                if (!entryFound) ++ dif;
        }

        return dif;
}


template <typename T, typename S> 
void VerbosePvs<T, S>::MergeInPlace(const VerbosePvs<T, S> &a)
{
        // early exit
        if (a.Empty())
        {
                return;
        }
        else if (Empty())
        {
                mEntries.reserve(a.GetSize());
                mEntries = a.mEntries;
                mSamples = a.mSamples;
                return;
        }

        ObjectPvs interPvs;
        
        Merge(interPvs, *this, a);
        
        mEntries.reserve(interPvs.GetSize());
        mEntries = interPvs.mEntries;
        mSamples = interPvs.mSamples;
}


template <typename T, typename S>
void VerbosePvs<T, S>::Merge(VerbosePvs<T, S> &mergedPvs, 
                                                         const VerbosePvs<T, S> &a, 
                                                         const VerbosePvs<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();
        
        Merge(mergedPvs, 
                  ait, ait_end,
                  bit, bit_end,
                  a.mSamples,
                  b.mSamples);
}


template <typename T, typename S>
void VerbosePvs<T, S>::Merge(VerbosePvs<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;
                //Intersectable *bObjOld = NULL;
        
                const PvsEntry<T, S> &aEntry = (*ait);

                for (; (bit != bEnd) && ((*bit).mObject <= (*ait).mObject); ++ bit)
                {
                        bObj = (*bit).mObject;

                        // object found => add up probabilities
                        if (bObj == aEntry.mObject)
                        {
                                PvsData newData(aEntry.mData.mSumPdf + (*bit).mData.mSumPdf);
                                PvsEntry<T, S> entry(bObj, newData);
                                mergedPvs.mEntries.push_back(entry);
                        }
                        else
                        {
                                mergedPvs.mEntries.push_back(*bit);
                        }
                }

                // only push back if objects different 
                // (equal case is handled by second loop)
                if (aObj != bObj)
                {
                        mergedPvs.mEntries.push_back(*ait);
                }
        }

        // add the rest
        for (; (bit != bEnd); ++ bit)
        {
                mergedPvs.mEntries.push_back(*bit);
        }

        mergedPvs.mSamples = aSamples + bSamples;
}


template <typename T, typename S> void VerbosePvs<T, S>::Clear(const bool trim)
{
        mEntries.clear();
        mSamples = 0;
        mLastSorted = 0;

        if (trim)
        {
                vector<PvsEntry<T,S> >().swap(mEntries);
        }
}


template <typename T, typename S> void VerbosePvs<T, S>::Trim()
{
        vector<PvsEntry<T,S> >(mEntries).swap(mEntries);
}


template <typename T, typename S> 
bool VerbosePvs<T, S>::Find(T sample,
                                         typename vector<PvsEntry<T, S> >::iterator &it,
                                         const bool checkDirty)
{
        bool found = false;
        
        PvsEntry<T, S> dummy(sample, PvsData());

        // only check clean part
        vector<PvsEntry<T, S> >::iterator sorted_end = mEntries.begin() + mLastSorted;
        mQueriesSinceSort++;

        // binary search
        it = lower_bound(mEntries.begin(), sorted_end, dummy);

        if ((it != mEntries.end()) && ((*it).mObject == sample))
                found = true;

        // sample not found yet => search further in the unsorted part
        if (!found && checkDirty) 
        {
                vector<PvsEntry<T, S> >::iterator dit, dit_end = mEntries.end();

        for (dit = sorted_end; (dit != dit_end) && ((*dit).mObject != sample); ++ dit);
        
                if (dit != dit_end)
                {
                        found = true;
                        it = dit;
                }
        }

        return found;
}


template <typename T, typename S>
void VerbosePvs<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);

        entry = (*i).first;
        data = (*i).second;
}


template <typename T, typename S>
float VerbosePvs<T, S>::AddSample(T sample, const float pdf)
{
        ++ mSamples;
        
        vector<PvsEntry<T, S> >::iterator it;
        const bool entryFound = Find(sample, it);               

        if (entryFound)
        {       
                S &data = (*it).mData;
                data.mSumPdf += pdf;
                return data.mSumPdf;
        }
        else 
        {
                PvsEntry<T, S> entry(sample, pdf);
                mEntries.insert(it, entry);
                ++ mLastSorted;
                return pdf;
        }
}


template <typename T, typename S>
void VerbosePvs<T, S>::AddSampleDirty(T sample, const float pdf)
{
        ++ mSamples;
        mEntries.push_back(PvsEntry<T, S>(sample, pdf));
}
                                         

template <typename T, typename S>
typename vector< PvsEntry<T, S> >::iterator VerbosePvs<T, S>::AddSample2(T sample, 
                                                                                                                                  const float pdf)
{
        ++ mSamples;
        
        vector<PvsEntry<T, S> >::iterator it;
        const bool entryFound = Find(sample, it);

        if (entryFound)
        {
                S &data = (*it).second;
                data->mSumPdf += pdf;
        }
        else 
        {
                PvsEntry<T, S> entry(sample, pdf);
                mEntries.insert(it, entry);
                ++ mLastSorted;
        }

        return it;
}


template <typename T, typename S> 
bool VerbosePvs<T, S>::AddSampleDirtyCheck(T sample, const float pdf)
{
        ++ mSamples;

        vector<PvsEntry<T, S> >::iterator it;
        const bool entryFound = Find(sample, it);

        if (entryFound) 
        {
                S &data = (*it).mData;
          
                data.mSumPdf += pdf;
        return false;
        }
        else 
        {
                AddSampleDirty(sample, pdf);
                return true;
        }
}


template <typename T, typename S>
bool VerbosePvs<T, S>::GetSampleContribution(T sample,
                                                                          const float pdf,
                                                                          float &contribution) 
{
        vector<PvsEntry<T, S> >::iterator it;
        const bool entryFound = Find(sample, it);

        if (entryFound)  
        {
                S &data = (*it).mData;
                contribution = pdf / (data.mSumPdf + pdf);
                return false;
        }
        else 
        {
                contribution = 1.0f;
                return true;
        }
}


template <typename T, typename S>
bool VerbosePvs<T, S>::RemoveSample(T sample, const float pdf)
{
        -- mSamples;
        
        vector<PvsEntry<T, S> >::iterator it;
        const bool entryFound = Find(sample, it);

        if (!entryFound)
                return false;

        S &data = (*it).mData;

        data.mSumPdf -= pdf;

        if (data.mSumPdf <= 0.0f)
        {
                mEntries.erase(it);
                -- mLastSorted; // wrong if sample was in tail!!
        }

        return true;
}


template <typename T, typename S>
int VerbosePvs<T, S>::SubtractPvs(const VerbosePvs<T, S> &pvs)
{
        const int samples = mSamples - pvs.mSamples;

        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).mObject, (*it).mData.mSumPdf);

        mSamples = samples;

        return GetSize();
}


template <typename T, typename S>
void VerbosePvs<T, S>::CollectEntries(std::vector<T> &entries)
{
        std::vector<PvsEntry<T, S> >::
                const_iterator it, it_end = mEntries.end();

        // output PVS of view cell
        for (it = mEntries.begin(); it != it_end; ++ it) 
                entries.push_back((*it)->first);
}


template <typename T, typename S>
void VerbosePvs<T, S>::NormalizeMaximum()
{
        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;
        }
}


template <typename T, typename S>
float VerbosePvs<T, S>::GetEntrySize()
{
        return (float)(sizeof(T) + sizeof(S)) / float(1024 * 1024);
}


template <typename T, typename S>
int VerbosePvs<T, S>::GetEntrySizeByte()
{
        return sizeof(T) + sizeof(S);
}


template <typename T, typename S>
float VerbosePvs<T, S>::GetPvsHomogenity(VerbosePvs<T, S> &pvs) 
{
        float pvsReduction, pvsEnlargement;

        ComputeContinuousPvsDifference(pvs,     pvsReduction, pvsEnlargement);
        return pvsReduction + pvsEnlargement;
}


template <typename T, typename S>
typename PvsIterator<T, S> VerbosePvs<T, S>::GetIterator() const
{
        PvsIterator<T, S> pit(mEntries.begin(), mEntries.end());
        return pit;
}

}

#endif