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

#ifndef __PVS_H
#define __PVS_H

#include <map>
#include <vector>

namespace GtpVisibilityPreprocessor {

class KdNode;
class BspNode;
class Ray;
class Intersectable;
class ViewCellKdNode;

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.
*/

template<typename T> 
struct PvsData {
  //  int mVisibleSamples;
  // sum of probability density of visible sample rays
  float mSumPdf;
  PvsData<T>() {}
  PvsData<T>(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>
class Pvs
{
public:
  Pvs(): /*mSamples(0), */mEntries() {}
  
  //int mSamples;
  
  /** 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> &a);
  
  /** Difference of pvs to pvs b.
          @returns number of different entries.
  */
  int Diff(const Pvs<T> &b);
  
  /** Finds sample in PVS.
          @returns sample if found, NULL otherwise.
  */
  PvsData<T> *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 one pvs to another one.
          @returns new pvs size
  */
  int AddPvs(const Pvs<T> &pvs);

  /** Subtracts one pvs from another one.
  WARNING: could contains bugs
          @returns new pvs size
  */
  int SubtractPvs(const Pvs<T> &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, PvsData<T> &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 visibleSampels number of references to be removed
  */
  bool RemoveSample(T sample, const float pdf);

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

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

  /** Compute continuous PVS difference */
  float GetPvsHomogenity(Pvs<T> &pvs) {
        float 
          pvsReduction,
          pvsEnlargement;
        
        ComputeContinuousPvsDifference(pvs,
                                                                   pvsReduction,
                                                                   pvsEnlargement);
        
        return pvsReduction + pvsEnlargement;
  }

                                          
                                          
  /// Map of PVS entries
  std::map<T, PvsData<T>, LtSample<T> > mEntries;
};



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

*/
template <typename T>
void
Pvs<T>::ComputeContinuousPvsDifference(Pvs<T> &b,
                                                                           float &pvsReduction,
                                                                           float &pvsEnlargement)
{
        pvsReduction = 0.0f;
        pvsEnlargement = 0.0f;
  // Uses sum of log differences, which corresponds to entropy
  std::map<T, PvsData<T>, LtSample<T> >::iterator it;
  
  for (it = b.mEntries.begin(); 
          it != b.mEntries.end(); ++ it) {
        float bSumPdf = (*it).second.mSumPdf;
        float aSumPdf = 0.0f;
        PvsData<T> *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 {
          PvsData<T> *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>
int Pvs<T>::Diff(const Pvs<T> &b)
{
        int dif = 0;

        std::map<T, PvsData<T>, LtSample<T> >::const_iterator it;

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

        return dif;
}

template <typename T>
void Pvs<T>::Merge(const Pvs<T> &a)
{
        std::map<T, PvsData<T>, LtSample<T> >::const_iterator it;

        for (it = a.mEntries.begin(); it != a.mEntries.end(); ++ it)
        {
                PvsData<T> *data = Find((*it).first);
                
                if (data)
                        data->mSumPdf += (*it).second.mSumPdf;
                else
                        mEntries.insert(*it);
        }
}

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


template <typename T>
PvsData<T> *Pvs<T>::Find(T sample)
{
  std::map<T, PvsData<T>, LtSample<T> >::iterator i = mEntries.find(sample);
  if (i != mEntries.end()) {
    return &(*i).second;
  } else
    return NULL;
}

template <typename T>
void Pvs<T>::GetData(const int index,
                                         T &entry,
                                         PvsData<T> &data)
{
  std::map<T, PvsData<T>, LtSample<T> >::iterator i = mEntries.begin();
  for (int k = 0; k != index && i != mEntries.end(); i++, k++);

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

template <typename T>
float
Pvs<T>::AddSample(T sample, const float pdf)
{
  PvsData<T> *data = Find(sample);
  
  if (data)  {
        data->mSumPdf+=pdf;
        return data->mSumPdf;
  }
  else {
        mEntries[sample] = PvsData<T>(pdf);
        return pdf;
  }
}

template <typename T>
bool
Pvs<T>::AddSample(T sample,
                                  const float pdf,
                                  float &contribution)
{
  PvsData<T> *data = Find(sample);
  
  if (data)  {
        data->mSumPdf+=pdf;
        contribution = pdf/data->mSumPdf;
        return false;
  }
  else {
        mEntries[sample] = PvsData<T>(pdf);
        contribution = 1.0f;
        return true;
  }
}

template <typename T>
bool
Pvs<T>::GetSampleContribution(T sample,
                                                          const float pdf,
                                                          float &contribution) 
{
  PvsData<T> *data = Find(sample);
  
  if (data)  {
        contribution = pdf/(data->mSumPdf + pdf);
        return false;
  }
  else {
        contribution = 1.0f;
        return true;
  }
}

template <typename T>
bool Pvs<T>::RemoveSample(T sample,
                                                  const float pdf)
{
  std::map<T, PvsData<T>, LtSample<T> >::
        iterator it = mEntries.find(sample);
  
  if (it == mEntries.end())
        return false;
  
  PvsData<T> *data = &(*it).second;
  
  data->mSumPdf -= pdf;
  if (data->mSumPdf <= 0.0f)
        mEntries.erase(it);
  
  return true;
}

template <typename T>
int Pvs<T>::AddPvs(const Pvs<T> &pvs)
{
  std::map<T, PvsData<T>, LtSample<T> >::
        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);
  
  return GetSize();
}
 
template <typename T>
int Pvs<T>::SubtractPvs(const Pvs<T> &pvs)
{
  std::map<T, PvsData<T>, LtSample<T> >::
        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);
  
  return GetSize();
}

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


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

typedef std::map<KdNode *, PvsData<KdNode *>, LtSample<KdNode *> > KdPvsMap;
typedef std::map<Intersectable *, PvsData<Intersectable *>, LtSample<Intersectable *> > ObjectPvsMap;
typedef PvsData<Intersectable *> ObjectPvsData;
typedef PvsData<KdNode *> KdPvsData;

typedef Pvs<Intersectable *> ObjectPvs;

}

#endif