source: GTP/trunk/Lib/Vis/Preprocessing/src/PvsBase.h @ 2709

#ifndef __PVSBASE_H
#define __PVSBASE_H

#include "common.h"
#include "Containers.h"
#include <vector>

namespace GtpVisibilityPreprocessor {

/** Information stored with a PVS entry. Consists of the number
        the object was seen from the view cell.
*/
struct 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;
};


class MailablePvsData 
{
public:
        // 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!!!
        inline float GetVisibility() { return mSumPdf; }


        ///////////////
        //  Mailing stuff

        // last mail id -> warning not thread safe!
        // both mailId and mailbox should be unique for each thread!!!
        static int sMailId;
        static int sReservedMailboxes;

        static void NewMail(const int reserve = 1) 
        {
                sMailId += sReservedMailboxes;
                sReservedMailboxes = reserve;
        }

        void Mail() { mMailbox = sMailId; }
        bool Mailed() const { return mMailbox == sMailId; }

        void Mail(const int mailbox) { mMailbox = sMailId + mailbox; }
        bool Mailed(const int mailbox) const { return mMailbox == sMailId + mailbox; }

        int IncMail() { return ++ mMailbox - sMailId; }
        
        //////////////////////////////////////////

protected:

        int mMailbox;

};


/** Information stored with a PVS entry. Consists of the number
        the object was seen from the view cell.
*/
template<typename T, typename S>
struct PvsEntry 
{
public:

        PvsEntry(): mObject(NULL), mData(0) {}
        PvsEntry(T sample): mObject(sample), mData(0) {}
        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>
  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>
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.mObject < b.mObject;
        } 
};

template<typename T, typename S>
int equalSample (const PvsEntry<T, S> &a, const PvsEntry<T, S> &b)
{
        return a.mObject == b.mObject;
} 


/** 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; }

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

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




struct VerbosePvsStats
{
        VerbosePvsStats(): mDistanceWeightedTriangles(0), mDistanceWeightedPvs(0), mWeightedTriangles(0)
        {}

        float mDistanceWeightedTriangles;
        float mDistanceWeightedPvs;
        float mWeightedTriangles;
};


/** 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 T1, typename S1> 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);

  void Remove(typename vector<PvsEntry<T, S> >::iterator &it);

        /** 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 = (int)mEntries.size();
                const int dirtySize = n - mLastSorted;

                const double LOG2E = 1.442695040f;

                const float logN = log((float) Max(1, n))/ (float)LOG2E;
                const float logS = log((float) Max(1, mLastSorted))/ (float)LOG2E;
                const float logD = log((float) Max(1, dirtySize))/ (float)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; }

  PvsIterator<T, S> GetIterator() const;

        VerbosePvsStats mStats;

  //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;
};


}

#endif