source: GTP/trunk/Lib/Vis/Preprocessing/src/BitVectorPvs.h @ 2206

#ifndef __BITVECTORPVS_H
#define __BITVECTORPVS_H

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


namespace GtpVisibilityPreprocessor {

// specialisation of vector<bool>
typedef vector<bool> bit_vector;


/** Iterator over a bitvector pvs.
*/
template<typename T, typename S>
class BitVectorPvsIterator
{
public:
        
        BitVectorPvsIterator<T, S>(const typename bit_vector::const_iterator &itBegin,
                                                           const typename bit_vector::const_iterator &itEnd
                                                           //,const int lastElement
                                                           ):
        mItCurrent(itBegin), mItEnd(itEnd), mDistance(0)//, mLastElement
        {
        }

        bool HasMoreEntries() const 
        {
                // find next element in bit vector
                // warning: has to do traversal each time
                typename bit_vector::const_iterator itNext = mItCurrent;

                for (;(itNext != mItEnd) && !(*itNext); ++ itNext);

                return (itNext != mItEnd);
        }

        T Next(S &pdf)
        {
                return Next();
        }
        
        T Next()
        {
                // hack: create new pvs entry
                for (; !(*mItCurrent); ++ mItCurrent, ++ mDistance);

                T sample = sObjects[mDistance];

                ++ mDistance;
                ++ mItCurrent;

                return sample;
        }

        
        // vector of objects corresponding to pvs entries
        static vector<T> sObjects;

private:

        typename bit_vector::const_iterator mItCurrent;
        //typename bit_vector::const_iterator mItNext;
        typename bit_vector::const_iterator mItEnd;
        
        // note: store distance explicitly because I 
        // don't know how efficient
        // std::distance is on specialisation of vector<bool>
        int mDistance;
};


/** Pvs implemented as bitvector
*/
template<typename T, typename S>
class BitVectorPvs//: public PvsBase<T>
{
        template<typename T, typename S> friend class BitVectorPvsIterator;

public:

        BitVectorPvs();
        //virtual ~HashPvs() {};

        int GetSize() const;
        bool Empty() const;

        /** 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();

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

        bool IsDirty() const;

        bool RequiresResort() const;

        /** Finds sample in PVS.
        */
        bool Find(T sample);

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

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

        static void Merge(BitVectorPvs<T, S> &mergedPvs, 
                                          const BitVectorPvs<T, S> &a, 
                                          const BitVectorPvs<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 BitVectorPvs<T, S> &a)
        {
                cerr << "bitvector: merge in place not implemented yet" << endl;
        }

        bool RequiresResortLog() const
        {
                return false;
        }

        void Reserve(const int n) 
        { 
                mEntries.reserve(n);
        }

        /** Sort pvs entries assume that the pvs contains unique entries
        */
        void SimpleSort()
        {
                // not necessary
        }

        int SubtractPvs(const BitVectorPvs<T, S> &pvs)
        {
                cerr << "not yet implemented" << endl;
                return 0;
        }

        /** Compute continuous PVS difference 
        */
        void ComputeContinuousPvsDifference(BitVectorPvs<T, S> &pvs, 
                                                                                float &pvsReduction,
                                                                                float &pvsEnlargement)
        {
                cerr << "not yet implemented" << endl;
        }


        static void SetPvsSize(const int pvsSize) { sPvsSize = pvsSize; };
        
protected:

        /// hash table of PVS entries
        bit_vector mEntries; 

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

public:
        static int sPvsSize;
};


template <typename T, typename S>
BitVectorPvs<T, S>::BitVectorPvs()
{
        // initialize bit vector
        mEntries.reserve(sPvsSize);
        mEntries.resize(sPvsSize);

        // set pvs entries to false
        Clear();
}


template <typename T, typename S>
bool BitVectorPvs<T, S>::Find(T sample)
{
        return mEntries[sample->GetId()];
}


template <typename T, typename S>
int BitVectorPvs<T, S>::GetSize() const
{
        int size = 0;
        bit_vector::const_iterator bit, bit_end = mEntries.end();

        for (bit = mEntries.begin(); bit != bit_end; ++ bit)
        {
                if (*bit) ++ size;
        }

        return size;
}


template <typename T, typename S>
bool BitVectorPvs<T, S>::Empty() const
{
        bit_vector::const_iterator bit, bit_end = mEntries.end();

        for (bit = mEntries.begin(); bit != bit_end; ++ bit)
        {
                if (*bit) return false;
        }

        return true;
}


template <typename T, typename S>
float BitVectorPvs<T, S>::AddSample(T sample, const float pdf)
{
        if (Find(sample))
                return 0.0f;
        
        mEntries[sample->GetId()] = true;

        return 1.0f;
}
        

template <typename T, typename S>
void BitVectorPvs<T, S>::AddSampleDirty(T sample, const float pdf)
{
        if (!Find(sample))
        {
                mEntries[sample->GetId()] = true;
        }
}


template <typename T, typename S>
bool BitVectorPvs<T, S>::AddSampleDirtyCheck(T sample, 
                                                                                const float pdf)
{
        if (Find(sample))
                return false;
        
        mEntries[sample->GetId()] = true;
        return true;
}


template <typename T, typename S>
void BitVectorPvs<T, S>::Sort()
{
}


template <typename T, typename S>
void BitVectorPvs<T, S>::Clear(const bool trim = true)
{
        bit_vector::iterator bit, bit_end = mEntries.end();
        for (bit = mEntries.begin(); bit != bit_end; ++ bit)
        {
                (*bit) = false;
        }
}


template <typename T, typename S>
bool BitVectorPvs<T, S>::IsDirty() const
{
        return false;
}


template <typename T, typename S>
bool BitVectorPvs<T, S>::RequiresResort() const
{
        return false;
}


template <typename T, typename S>
typename BitVectorPvsIterator<T, S> BitVectorPvs<T, S>::GetIterator() const
{
        BitVectorPvsIterator<T, S> pit(mEntries.begin(), mEntries.end());

        return pit;
}


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


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


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

        ComputeContinuousPvsDifference(pvs,     pvsReduction, pvsEnlargement);

        return pvsReduction + pvsEnlargement;
}


template <typename T, typename S>
bool BitVectorPvs<T, S>::GetSampleContribution(T sample,
                                                                          const float pdf,
                                                                          float &contribution) 
{
        const bool entryFound = Find(sample);

        if (entryFound)  
        {
                contribution = 0.0f;
                return false;
        }
        else 
        {
                contribution = 1.0f;
                return true;
        }
}


template <typename T, typename S>
void BitVectorPvs<T, S>::Merge(BitVectorPvs<T, S> &mergedPvs, 
                                                           const BitVectorPvs<T, S> &a, 
                                                           const BitVectorPvs<T, S> &b)
{
        bit_vector::iterator bit, bit_end = mergedPvs.mEntries.end();
        bit_vector::const_iterator bitA =  a.mEntries.begin(), bitB = b.mEntries.begin();

        for (bit = mergedPvs.mEntries.begin(); bit != bit_end; ++ bit, ++ bitA, ++ bitB)
        {
        (*bit) = (*bitA) | (*bitB);
        }
}


template<typename T, typename S>
int BitVectorPvs<T, S>::sPvsSize = 0;

template<typename T, typename S>
vector<T> BitVectorPvsIterator<T, S>::sObjects;

}

#endif