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

#ifndef __PVS_H
#define __PVS_H

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

namespace GtpVisibilityPreprocessor {

class KdNode;
class BspNode;
class Ray;
class Intersectable;
class ViewCell;


template<typename T>
struct LtSample 
{
    bool operator()(const T a, const T b) const
    {
                return a < b;
        } 
};

/** Information stored with a PVS entry. Consists of the number
        the object was seen from the view cell.
*/
class PvsData {
public:
        /// sum of probability density of visible sample rays
        float mSumPdf;

        PvsData() {}
        PvsData(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; 
        }
};


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

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

/** 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 Pvs
{
public:
//vector<pair<T, S> >::iterator mItEnd;
        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;
        };

        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() {}
  

        //virtual ~Pvs();

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

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

        /** Difference of pvs to pvs b.
                @returns number of different entries.
        */
        int Diff(const Pvs<T, S> &b);

        /** Finds sample in PVS.
                @returns sample if found, NULL otherwise.
        */
        S *Find(T sample);

        bool GetSampleContribution(T sample, const float pdf, float &contribution);

        /** Adds sample to PVS. 
                @contribution contribution of sample (0 or 1)
                @returns true if sample was not already in PVS.
        */
        bool AddSample(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.
                @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);

        /** Subtracts one pvs from another one.
                WARNING: could contains bugs
                @returns new pvs size
        */
        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.
        */
        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(Pvs<T, S> &pvs,
                float &pvsReduction,
                float &pvsEnlargement);


        /** Clears the pvs.
        */
        void Clear();

        static int GetEntrySizeByte(); 
        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(); }

//protected:

        /// vector of PVS entries
        vector<pair<T, S> > mEntries; 
        
        /// Number of samples used to create the PVS
        int mSamples;
};



/**
   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
Pvs<T, S>::ComputeContinuousPvsDifference(Pvs<T, S> &b,
                                                                           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;

        for (it = b.mEntries.begin(); it != b.mEntries.end(); ++ it) 
        {
                float bSumPdf = (*it).second.mSumPdf;
                float aSumPdf = 0.0f;
                S *data = Find((*it).first);            

                if (data) 
                {
                        aSumPdf = data->mSumPdf;
                        // mark this entry as processed to avoid double counting
                        data->mSumPdf = -aSumPdf;
                }

#if 0
                float diff = bSumPdf - aSumPdf;

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

        for (it = mEntries.begin(); it != mEntries.end(); ++ it) {
                float aSumPdf = (*it).second.mSumPdf;
                float bSumPdf = 0.0f;
                if (aSumPdf < 0.0f) {
                        // this entry was already accounted for!
                        // just revert it back
                        (*it).second.mSumPdf = -aSumPdf;
                } else {
                        S *data = b.Find((*it).first);
                        if (data) {
                                bSumPdf = data->mSumPdf;
                        }
#if 0
                        float diff = bSumPdf - aSumPdf;

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

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


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

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

        for (it = b.mEntries.begin(); it != b.mEntries.end(); ++ it)
        {
                S data = Find((*it).first);             
                if (!data) ++ dif;
        }

        return dif;
}

template <typename T, typename S> void Pvs<T, S>::Merge(const Pvs<T, S> &a)
{
#if TODO
        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);
        }

        mSamples = samples;
#endif
}


template <typename T, typename S> void Pvs<T, S>::Clear()
{
        mEntries.clear();
}


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();
        for (int k = 0; k != index && i != mEntries.end(); ++ i, ++ k);

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


template <typename T, typename S>
float
Pvs<T, S>::AddSample(T sample, const float pdf)
{
#if TODO
        ++ mSamples;
        S *data = Find(sample);

        if (data)  
        {
                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;
}

template <typename T, typename S> 
bool Pvs<T, S>::AddSample(T sample,
                                  const float pdf,
                                  float &contribution)
{
        ++ mSamples;
    S *data = Find(sample);
#if TODO
        if (data)  
        {
                data->mSumPdf += pdf;
                contribution = pdf / data->mSumPdf;
                return false;
        }
        else {
                mEntries[sample] = S(pdf);
                contribution = 1.0f;
                return true;
        }
#else
        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> >::
                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);

        mSamples = samples;
#endif
        return GetSize();
}

template <typename T, typename S>
void Pvs<T, S>::CollectEntries(std::vector<T> &entries)
{
        std::vector<pair<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 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;
  }
  
}


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


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


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

/** Class instantiating the Pvs template for kd tree nodes.
*/
class KdPvs: public Pvs<KdNode *, PvsData>
{
public:
        int Compress();
};


class ObjectPvs: public Pvs<Intersectable *, PvsData>
{
public:
        /** Counts object int the pvs. Different to method "GetSize", not
                only the raw container size is returned,
                but the individual contributions of the entries are summed up.
        */
        float EvalPvsCost() const;
};


////////////
//-- 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 Pvs<ViewCell *, MailablePvsData> ViewCellPvs;

}

#endif