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

#ifndef __VERBOSEPVS_H
#define __VERBOSEPVS_H

#include <vector>
#include "common.h"
#include <math.h>
//#include "PvsBB.h"
#include "PvsBase.h"
#include "ObjectPvs.h"


namespace GtpVisibilityPreprocessor {

inline int operator< (PvsEntry<Intersectable*, PvsData> const &a,
                      PvsEntry<Intersectable*, PvsData> const &b)
{
  return a.mObject < b.mObject;
} 

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


template <typename T, typename S>
void VerbosePvs<T, S>::Sort()
{
        typename vector<PvsEntry<T, S> >::iterator it = mEntries.begin() + mLastSorted;
        typename vector<PvsEntry<T, S> >::iterator it_end = mEntries.end();

        // throw out double entries
        typename 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());
        typename 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
        typename 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;

                typename 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 
                {
                        typename 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;

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

        for (it = b.mEntries.begin(); it != b.mEntries.end(); ++ it)
        {
                typename 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)
{
        typename std::vector<PvsEntry<T, S> >::const_iterator ait = 
                a.mEntries.begin(), ait_end = a.mEntries.end();
        typename 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)
{
        typename std::vector<PvsEntry<T, S> >::const_iterator ait = aBegin;
        typename 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
        typename 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) 
        {
            typename 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)
{
        typename 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;
        
        typename 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;
        
        typename 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;

        typename 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) 
{
        typename 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;
        
        typename 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;

        typename 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)
{
        typename 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()
{
        typename 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 > maxPdfSum)
                        maxPdfSum = sum;
        }

        maxPdfSum = 1.0f / maxPdfSum;

        for (it = mEntries.begin(); it != it_end; ++ it) {
                (*it)->second.sumPdf *= maxPdfSum;
        }
}


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>
PvsIterator<T, S> VerbosePvs<T, S>::GetIterator() const
{
        PvsIterator<T, S> pit(mEntries.begin(), mEntries.end());
        return pit;
}

}

#endif