Index: GTP/trunk/Lib/Vis/Preprocessing/src/Pvs.h
===================================================================
--- GTP/trunk/Lib/Vis/Preprocessing/src/Pvs.h	(revision 1739)
+++ GTP/trunk/Lib/Vis/Preprocessing/src/Pvs.h	(revision 1740)
@@ -15,12 +15,38 @@
 
 
-template<typename T>
-struct LtSample 
-{
-    bool operator()(const T a, const T b) const
+/** Information stored with a PVS entry. Consists of the number
+	the object was seen from the view cell.
+*/
+template<typename T, typename S>
+class PvsEntry 
+{
+public:
+
+	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>
+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 < b;
+		return a.mObject < b.mObject;
 	} 
 };
+
 
 /** Information stored with a PVS entry. Consists of the number
@@ -29,9 +55,29 @@
 class 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;
-
-	PvsData() {}
-	PvsData(const float sumPdf):
+};
+
+
+class MailablePvsData 
+{
+public:
+	// sum of probability density of visible sample rays
+	float mSumPdf;
+	int mCounter;
+
+	MailablePvsData() {}
+	MailablePvsData(const float sumPdf):
 	mSumPdf(sumPdf) {}
 
@@ -42,15 +88,8 @@
 		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!!!
@@ -58,5 +97,4 @@
 	static int sReservedMailboxes;
 
-
 	static void NewMail(const int reserve = 1) {
 		sMailId += sReservedMailboxes;
@@ -71,29 +109,23 @@
 
 	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; 
-	}
-};
+protected:
+
+	int mMailbox;
+
+};
+
+
 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;
-	};
+class PvsIterator
+{
+private:
+	typename vector<PvsEntry<T, S> >::iterator mItCurrent;
+	typename vector<PvsEntry<T, S> >::iterator mItEnd;
+};
+
+
 /** Template class representing the Potentially Visible Set (PVS) 
 	mainly from a view cell, but also e.g., from objects.
@@ -102,20 +134,12 @@
 class Pvs
 {
+	template<typename T, typename S>
+	friend class PvsIterator;
+
 public:
-//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() {}
-  
-
+
+	Pvs(): mSamples(0), mEntries() {}
+
+	Pvs(const vector<PvsEntry<T, S> > &samples);
 	//virtual ~Pvs();
 
@@ -126,12 +150,13 @@
 	bool Empty() const {return mEntries.empty();}
 
-	/** Normalize the visibility of entries in order to get comparable
-		results 
+	/** 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);
+		Warning: very slow!
+	*/
+	void MergeInPlace(const Pvs<T, S> &a);
 
 	/** Difference of pvs to pvs b.
@@ -141,7 +166,7 @@
 
 	/** Finds sample in PVS.
-		@returns sample if found, NULL otherwise.
-	*/
-	S *Find(T sample);
+		@returns iterator on the sample.
+	*/
+	typename vector<PvsEntry<T, S> >::iterator Find(T sample);
 
 	bool GetSampleContribution(T sample, const float pdf, float &contribution);
@@ -157,14 +182,14 @@
 	*/
 	float AddSample(T sample, const float pdf);
+	
+	/** Adds sample to PVS.
+		@returns contribution of sample (0 or 1)
+	*/
+	float AddSamples(const vector<PvsEntry<T, S> > &samples);
 
 	/** 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);
+	typename std::vector<PvsEntry<T, S> >::iterator AddSample2(T sample, const float pdf);
 
 	/** Subtracts one pvs from another one.
@@ -173,4 +198,5 @@
 	*/
 	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.
@@ -189,8 +215,7 @@
 	/** Compute continuous PVS difference 
 	*/
-	void ComputeContinuousPvsDifference(Pvs<T, S> &pvs,
-		float &pvsReduction,
-		float &pvsEnlargement);
-
+	void ComputeContinuousPvsDifference(Pvs<T, S> &pvs, 
+										float &pvsReduction,
+										float &pvsEnlargement);
 
 	/** Clears the pvs.
@@ -201,24 +226,14 @@
 	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(); }
+	/** Compute continuous PVS difference 
+	*/
+	float GetPvsHomogenity(Pvs<T, S> &pvs);
+
+	static void Merge(Pvs<T, S> &mergedPvs, const Pvs<T, S> &a, const Pvs<T, S> &b);
 
 //protected:
 
 	/// vector of PVS entries
-	vector<pair<T, S> > mEntries; 
+	vector<PvsEntry<T, S> > mEntries; 
 	
 	/// Number of samples used to create the PVS
@@ -227,4 +242,11 @@
 
 
+template <typename T, typename S>
+Pvs<T, S>::Pvs(const vector<PvsEntry<T, S> > &samples)
+{
+	mEntries.reserve(samples.size());
+	mEntries = samples;
+}
+
 
 /**
@@ -236,27 +258,32 @@
 void
 Pvs<T, S>::ComputeContinuousPvsDifference(Pvs<T, S> &b,
-									   float &pvsReduction,
-									   float &pvsEnlargement)
+										  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;
+	std::vector<PvsEntry<T, S> >::iterator it;
 
 	for (it = b.mEntries.begin(); it != b.mEntries.end(); ++ it) 
 	{
-		float bSumPdf = (*it).second.mSumPdf;
+		float bSumPdf = (*it).mData.mSumPdf;
 		float aSumPdf = 0.0f;
-		S *data = Find((*it).first);		
-
-		if (data) 
+
+		vector<PvsEntry<T, S> >::iterator oit = Find((*it).mObject);		
+
+		const bool entryFound = (it != mEntries.end()) && ((*it).mObject == (*oit).mObject);
+
+		if (entryFound)
 		{
-			aSumPdf = data->mSumPdf;
+			aSumPdf = (*it).mData.mSumPdf;
+
 			// mark this entry as processed to avoid double counting
-			data->mSumPdf = -aSumPdf;
+			(*it).mData.mSumPdf = -aSumPdf;
 		}
 
 #if 0
-		float diff = bSumPdf - aSumPdf;
+		const float diff = bSumPdf - aSumPdf;
 
 		if (diff > 0.0f) {
@@ -266,23 +293,28 @@
 		}
 #else
-		if (!data)
+		if (!entryFound)
 			pvsEnlargement += 1.0f;
 #endif
 	}
 
-	for (it = mEntries.begin(); it != mEntries.end(); ++ it) {
-		float aSumPdf = (*it).second.mSumPdf;
+	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).second.mSumPdf = -aSumPdf;
+			(*it).mData.mSumPdf = -aSumPdf;
 		} else {
-			S *data = b.Find((*it).first);
-			if (data) {
-				bSumPdf = data->mSumPdf;
+			vector<PvsEntry<T, S> >::iterator oit = b.Find((*it).mObject);
+
+			const bool entryFound = (it != mEntries.end()) && ((*it).mObject == (*oit).mObject);
+			
+			if (entryFound) {
+				bSumPdf = (*oit).mData.mSumPdf;
 			}
 #if 0
-			float diff = bSumPdf - aSumPdf;
+			const float diff = bSumPdf - aSumPdf;
 
 			if (diff > 0.0f) {
@@ -293,5 +325,5 @@
 
 #else
-			if (!data) 
+			if (!entryFound) 
 				pvsReduction += 1.0f;
 #endif
@@ -306,10 +338,10 @@
 	int dif = 0;
 
-	std::vector<pair<T, S> >::const_iterator it;
+	std::vector<PvsEntry<T, S> >::const_iterator it;
 
 	for (it = b.mEntries.begin(); it != b.mEntries.end(); ++ it)
 	{
-		S data = Find((*it).first);		
-		if (!data) ++ dif;
+		std::vector<PvsEntry<T, S> >::const_iterator bit = Find((*it).first);		
+		if (bit == mEntries.end()) ++ dif;
 	}
 
@@ -317,19 +349,73 @@
 }
 
-template <typename T, typename S> void Pvs<T, S>::Merge(const Pvs<T, S> &a)
-{
-#if TODO
+
+template <typename T, typename S> 
+void Pvs<T, S>::MergeInPlace(const Pvs<T, S> &a)
+{
+    const int samples = mSamples + a.mSamples;
+
+	ObjectPvs interPvs;
+	
+	Merge(interPvs, *this, a);
+	
+	mEntries.reserve(interPvs.GetSize());
+	mEntries = interPvs.mEntries;
+
+	mSamples = samples;
+}
+
+
+template <typename T, typename S>
+void Pvs<T, S>::Merge(Pvs<T, S> &mergedPvs, const Pvs<T, S> &a, const Pvs<T, S> &b)
+{
+	std::vector<PvsEntry<T, S> >::const_iterator ait = a.mEntries.begin(), ait_end = a.mEntries.end();
+	std::vector<PvsEntry<T, S> >::const_iterator bit = b.mEntries.begin(), bit_end = b.mEntries.end();
+
+	while (1)
+	{
+		for (; (ait != ait_end) && ((*ait).mObject < (*bit).mObject); ++ ait)
+		{
+			if ((*ait).mObject != (*bit).mObject)
+				mergedPvs.mEntries.push_back(*ait);
+		}
+
+		for (; (bit != bit_end) && ((ait == ait_end) || ((*bit).mObject <= (*bit).mObject)); ++ bit)
+		{
+			if ((*ait).mObject == (*bit).mObject)
+			{
+				PvsData newData((*ait).mData.mSumPdf + (*bit).mData.mSumPdf);
+				PvsEntry<T, S> entry((*ait).mObject, newData);
+				mergedPvs.mEntries.push_back(entry);
+			}
+			else
+			{
+				mergedPvs.mEntries.push_back(*bit);
+			}
+		}
+	}
+}
+
+
+/*template <typename T, typename S> void Pvs<T, S>::QuickMerge(const Pvs<T, S> &a)
+{
 	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);
+	std::vector<PvsEntry<T, S>> >::const_iterator it;
+
+	for (it = mEntries.begin(); it != mEntries.end(); ++ it)
+	{
+		it->first->Mail();
+	}
+
+    for (it = a.mEntries.begin(); it != a.mEntries.end(); ++ it)
+	{
+		if (!it->first->Mailed())
+		{
+			mEntries.push_back(*it);
+		}
 	}
 
 	mSamples = samples;
-#endif
-}
+}*/
 
 
@@ -341,28 +427,17 @@
 
 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();
+typename std::vector<PvsEntry<T, S> >::iterator Pvs<T, S>::Find(T sample)
+{
+	PvsEntry<T, S> dummy(sample, PvsData());
+	vector<PvsEntry<T, S> >::iterator it = lower_bound(mEntries.begin(), mEntries.end(), dummy);
+				
+	return it;
+}
+
+
+template <typename T, typename S>
+void Pvs<T, S>::GetData(const int index, T &entry, S &data)
+{
+	std::vector<PvsEntry<T, S> >::iterator i = mEntries.begin();
 	for (int k = 0; k != index && i != mEntries.end(); ++ i, ++ k);
 
@@ -373,151 +448,143 @@
 
 template <typename T, typename S>
-float
-Pvs<T, S>::AddSample(T sample, const float pdf)
-{
-#if TODO
+float Pvs<T, S>::AddSample(T sample, const float pdf)
+{
 	++ mSamples;
-	S *data = Find(sample);
-
-	if (data)  
-	{
+	std::vector<PvsEntry<T, S> >::iterator it = Find(sample);
+
+	if ((it != mEntries.end()) && ((*it).mObject == sample))
+	{
+		S &data = (*it).mData;
+		data.mSumPdf += pdf;
+
+		return data.mSumPdf;
+	}
+	else 
+	{
+		PvsEntry<T, S> entry(sample, pdf);
+		
+		mEntries.insert(it, entry);
+		return pdf;
+	}
+}
+
+
+template <typename T, typename S>
+typename vector< PvsEntry<T, S> >::iterator Pvs<T, S>::AddSample2(T sample, const float pdf)
+{
+	++ mSamples;
+	std::vector<PvsEntry<T, S> >::iterator it = Find(sample);
+
+	if ((it != mEntries.end()) && ((*it).first == T))
+	{
+		S &data = (*it).second;
 		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;
-}
+		PvsEntry<T, S> entry(sample, pdf);
+		mEntries.insert(it, entry);
+	}
+
+	return it;
+}
+
 
 template <typename T, typename S> 
 bool Pvs<T, S>::AddSample(T sample,
-				  const float pdf,
-				  float &contribution)
+						  const float pdf,
+						  float &contribution)
 {
 	++ mSamples;
-    S *data = Find(sample);
-#if TODO
-	if (data)  
-	{
-		data->mSumPdf += pdf;
-		contribution = pdf / data->mSumPdf;
+
+	std::vector<PvsEntry<T, S> >::iterator it = Find(sample);
+
+	if ((it != mEntries.end()) && ((*it).mObject == sample))
+	{
+		S &data = (*it).mData;
+
+		data.mSumPdf += pdf;
+		contribution = pdf / data.mSumPdf;
+
 		return false;
 	}
-	else {
-		mEntries[sample] = S(pdf);
+	else 
+	{
+		PvsEntry<T, S> entry(sample, pdf);
+
+		mEntries.insert(it, entry);
+		contribution = 1.0f;
+
+		return true;
+	}
+}
+
+
+template <typename T, typename S>
+bool Pvs<T, S>::GetSampleContribution(T sample,
+									  const float pdf,
+									  float &contribution) 
+{
+	std::vector<PvsEntry<T, S> >::iterator it = Find(sample);
+
+	if (it != mEntries.end() && ((*it).mObject == sample))  
+	{
+		S &data = (*it).mData;
+		contribution = pdf / (data.mSumPdf + pdf);
+		return false;
+	}
+	else 
+	{
 		contribution = 1.0f;
 		return true;
 	}
-#else
+}
+
+
+template <typename T, typename S>
+bool Pvs<T, S>::RemoveSample(T sample, const float pdf)
+{
+	-- mSamples;
+
+	std::vector<PvsEntry<T, S> >::iterator it = Find(sample);
+
+	if (it == mEntries.end())
+		return false;
+
+	S &data = (*it).mData;
+
+	data.mSumPdf -= pdf;
+
+	if (data.mSumPdf <= 0.0f)
+	{
+		mEntries.erase(it);
+	}
+
 	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> >::
+
+	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).first, (*it).second.mSumPdf);
+		RemoveSample((*it).mObject, (*it).mData.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> >::
+	std::vector<PvsEntry<T, S> >::
 		const_iterator it, it_end = mEntries.end();
 
@@ -527,25 +594,26 @@
 }
 
+
 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;
-  }
-  
+	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 > maxSum)
+			maxSum = sum;
+	}
+
+	maxSum = 1.0f / maxSum;
+
+	for (it = mEntries.begin(); it != it_end; ++ it) {
+		(*it)->second.sumPdf *= maxSum;
+	}
+
 }
 
@@ -562,4 +630,15 @@
 {
 	return sizeof(T) + sizeof(S);
+}
+
+
+template <typename T, typename S>
+float Pvs<T, S>::GetPvsHomogenity(Pvs<T, S> &pvs) 
+{
+	float pvsReduction, pvsEnlargement;
+
+	ComputeContinuousPvsDifference(pvs,	pvsReduction, pvsEnlargement);
+
+	return pvsReduction + pvsEnlargement;
 }
 
@@ -590,11 +669,5 @@
 //-- 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 std::vector<PvsEntry<Intersectable *, PvsData> > ObjectPvsEntries;
 typedef Pvs<ViewCell *, MailablePvsData> ViewCellPvs;
 
