Index: GTP/trunk/Lib/Vis/OnlineCullingCHC/src/CoherentHierarchicalCullingManager2.cpp
===================================================================
--- GTP/trunk/Lib/Vis/OnlineCullingCHC/src/CoherentHierarchicalCullingManager2.cpp	(revision 2360)
+++ GTP/trunk/Lib/Vis/OnlineCullingCHC/src/CoherentHierarchicalCullingManager2.cpp	(revision 2360)
@@ -0,0 +1,327 @@
+#include "CoherentHierarchicalCullingManager2.h"
+#include "CullingLogManager.h"
+
+#include <time.h>
+#include <sstream>
+
+namespace GtpVisibility {
+
+//-----------------------------------------------------------------------
+CoherentHierarchicalCullingManager2::CoherentHierarchicalCullingManager2()
+{
+	SetAssumedVisibility(0);
+	// initialise random generator in case we use assumed visibility
+	//srand(time(NULL));
+}
+//-----------------------------------------------------------------------
+CoherentHierarchicalCullingManager2::CoherentHierarchicalCullingManager2(
+														const unsigned int assumedVisibility)
+{
+	SetAssumedVisibility(assumedVisibility);
+	// initialise random generator in case we use assumed visibility
+	//srand(time(NULL));
+}
+//-----------------------------------------------------------------------
+#if 1
+
+void CoherentHierarchicalCullingManager2::RenderScene()
+{
+	//CullingLogManager::GetSingleton()->LogMessage("chc");
+	QueryQueue queryQueue;
+	unsigned int visiblePixels = 0;
+	
+	/////////////
+	//-- PART 1: process finished occlusion queries
+
+	while (!mHierarchyInterface->GetQueue()->empty() || !queryQueue.empty())
+	{
+		bool resultAvailable = false;
+
+		const bool nodeQueueEmpty = mHierarchyInterface->GetQueue()->empty();
+		const int queryQueueSize = (int)queryQueue.size();
+		bool queryAvailable = true;
+
+		//-- only wait for result if there are no nodes to process
+		while (!queryQueue.empty() && 
+				(queryAvailable = queryQueue.front().second->GetQueryResult(visiblePixels, false)))
+		{
+			HierarchyNode *node = queryQueue.front().first;
+			queryQueue.pop();
+
+			// render nodes if queue is still idle ...
+
+			if (1&&nodeQueueEmpty)
+			{
+				std::stringstream d; d << "qu: " << queryQueueSize;
+				CullingLogManager::GetSingleton()->LogMessage(d.str());
+			}
+
+			
+			if (visiblePixels > mVisibilityThreshold)
+			{
+				// check visibility to ensure that we traverse node only once
+				// (important for interior nodes with geometry
+				if (!mHierarchyInterface->IsNodeVisible(node))
+				{
+					mHierarchyInterface->TraverseNode(node);
+				}
+
+				mHierarchyInterface->PullUpVisibility(node);
+			}
+			else
+			{	
+				mHierarchyInterface->SetNodeVisible(node, false);
+
+				++ mNumQueryCulledNodes;
+				
+				if (mVisualizeCulledNodes)
+				{
+					mHierarchyInterface->VisualizeCulledNode(node, QUERY_CULLED);
+				}
+			}
+		}
+		
+
+		if (!queryAvailable)
+		{
+			 // query not yet available => render some geometry
+			HierarchyNode *node = queryQueue.front().first;
+			
+			// check visibility to ensure that we traverse node only once
+			// (important for interior nodes with geometry
+			if (!mHierarchyInterface->IsNodeVisible(node))
+			{
+				mHierarchyInterface->SetNodeVisible(node, true);
+				mHierarchyInterface->TraverseNode(node);
+			}
+		}
+
+
+		//-- PART 2: hierarchical traversal
+		if (!mHierarchyInterface->GetQueue()->empty())
+		{
+			HierarchyNode *node = mHierarchyInterface->GetQueue()->top();
+		
+			mHierarchyInterface->GetQueue()->pop();
+				
+			bool intersects = false;
+
+			if (!mHierarchyInterface->CheckFrustumVisible(node, intersects))
+			{
+				++ mNumFrustumCulledNodes;
+
+				if (mVisualizeCulledNodes)
+				{
+					mHierarchyInterface->VisualizeCulledNode(node, FRUSTUM_CULLED);
+				}
+			}
+			//-- if node intersects near plane, skip query because wrong results possible
+			else if (intersects)
+			{
+				SkipQuery(node);
+			}
+			else
+			{
+				// identify previously visible nodes
+				bool wasVisible = mHierarchyInterface->IsNodeVisible(node) && 
+					(mHierarchyInterface->LastVisited(node) == mHierarchyInterface->GetFrameId() - 1);
+				
+				// if we assume node to be visible in this frame => skip query 
+				bool skipQuery = wasVisible && (mAssumedVisibility > 0) && 
+					DecideVisible(node) && mHierarchyInterface->HasGeometry(node);
+
+				if (skipQuery)
+				{
+					SkipQuery(node);
+					continue;
+				}
+
+                // identify nodes that we cannot skip queries for
+				// geometry not only in leaves => test for renderable geometry
+				bool issueQuery = !wasVisible || mHierarchyInterface->HasGeometry(node);
+							
+				// reset node's visibility classification
+				// set visibe if geometry in node so we only traverse once
+				mHierarchyInterface->SetNodeVisible(node, wasVisible && issueQuery);
+
+				// update node's visited flag
+				mHierarchyInterface->SetLastVisited(node, mHierarchyInterface->GetFrameId());
+				
+				// skip testing previously visible nodes without geometry
+				if (issueQuery)
+				{
+					++ mNumQueriesIssued;
+					
+					queryQueue.push(QueryPair(node, mHierarchyInterface->
+						IssueNodeOcclusionQuery(node, wasVisible)));
+				}
+				
+				// always traverse a node if it was visible
+				if (wasVisible)
+				{
+					mHierarchyInterface->TraverseNode(node);
+				}
+			}
+		}
+	}
+}
+
+#else
+
+void CoherentHierarchicalCullingManager2::RenderScene()
+{
+	//CullingLogManager::GetSingleton()->LogMessage("chc");
+	QueryQueue queryQueue;
+	unsigned int visiblePixels = 0;
+	
+	/////////////
+	//-- PART 1: process finished occlusion queries
+
+	while (!mHierarchyInterface->GetQueue()->empty() || !queryQueue.empty())
+	{
+		bool resultAvailable = false;
+
+		const bool nodeQueueEmpty = mHierarchyInterface->GetQueue()->empty();
+		const int queryQueueSize = (int)queryQueue.size();
+
+		//-- only wait for result if there are no nodes to process
+		while (!queryQueue.empty() && 
+				queryQueue.front().second->GetQueryResult(visiblePixels, 
+				nodeQueueEmpty))
+		{
+			HierarchyNode *node = queryQueue.front().first;
+			queryQueue.pop();
+
+			// render nodes if queue is still idle ...
+
+			if (1&&nodeQueueEmpty)
+			{
+				std::stringstream d; d << "qu: " << queryQueueSize;
+				CullingLogManager::GetSingleton()->LogMessage(d.str());
+			}
+
+			
+			if (visiblePixels > mVisibilityThreshold)
+			{
+				// in case geometry is in omterior node: ensure that we only traverse once
+				if (!mHierarchyInterface->IsNodeVisible(node))
+				{
+					mHierarchyInterface->TraverseNode(node);
+				}
+
+				mHierarchyInterface->PullUpVisibility(node);
+			}
+			else
+			{	
+				mHierarchyInterface->SetNodeVisible(node, false);
+
+				++ mNumQueryCulledNodes;
+				
+				if (mVisualizeCulledNodes)
+				{
+					mHierarchyInterface->VisualizeCulledNode(node, QUERY_CULLED);
+				}
+			}
+		}
+		
+		//-- PART 2: hierarchical traversal
+		if (!mHierarchyInterface->GetQueue()->empty())
+		{
+			HierarchyNode *node = mHierarchyInterface->GetQueue()->top();
+			mHierarchyInterface->GetQueue()->pop();
+				
+			bool intersects = false;
+
+			if (!mHierarchyInterface->CheckFrustumVisible(node, intersects))
+			{
+				++ mNumFrustumCulledNodes;
+
+				if (mVisualizeCulledNodes)
+				{
+					mHierarchyInterface->VisualizeCulledNode(node, FRUSTUM_CULLED);
+				}
+			}
+			//-- if node intersects near plane, skip query because wrong results possible
+			else if (intersects)
+			{
+				SkipQuery(node);
+			}
+			else
+			{
+				// identify previously visible nodes
+				bool wasVisible = mHierarchyInterface->IsNodeVisible(node) && 
+					(mHierarchyInterface->LastVisited(node) == mHierarchyInterface->GetFrameId() - 1);
+				
+				// if we assume node to be visible in this frame => skip query 
+				bool skipQuery = wasVisible && (mAssumedVisibility > 0) && 
+					DecideVisible(node) && mHierarchyInterface->HasGeometry(node);
+
+				if (skipQuery)
+				{
+					SkipQuery(node);
+					continue;
+				}
+
+                // identify nodes that we cannot skip queries for
+				// geometry not only in leaves => test for renderable geometry
+				bool issueQuery = !wasVisible || mHierarchyInterface->HasGeometry(node);
+							
+				// reset node's visibility classification
+				// set visibe if geometry in node so we only traverse once
+				mHierarchyInterface->SetNodeVisible(node, wasVisible && issueQuery);
+
+				// update node's visited flag
+				mHierarchyInterface->SetLastVisited(node, mHierarchyInterface->GetFrameId());
+				
+				// skip testing previously visible nodes without geometry
+				if (issueQuery)
+				{
+					++ mNumQueriesIssued;
+					
+					queryQueue.push(QueryPair(node, mHierarchyInterface->
+						IssueNodeOcclusionQuery(node, wasVisible)));
+				}
+				
+				// always traverse a node if it was visible
+				if (wasVisible)
+				{
+					mHierarchyInterface->TraverseNode(node);
+				}
+			}
+		}
+	}
+}
+
+#endif
+//-----------------------------------------------------------------------
+void CoherentHierarchicalCullingManager2::SetAssumedVisibility(const unsigned int assumedVisibility)
+{
+	mAssumedVisibility = assumedVisibility;
+	
+	mThreshold = 0;
+
+	if (mAssumedVisibility > 0)
+	{
+		mThreshold = RAND_MAX - RAND_MAX / mAssumedVisibility;
+		 // fix visibility
+		if (mAssumedVisibility > 100)
+			mThreshold = RAND_MAX;
+	}
+	
+}
+//-----------------------------------------------------------------------
+inline bool CoherentHierarchicalCullingManager2::DecideVisible(HierarchyNode *node) const
+{
+	return rand() < mThreshold;
+}
+//-----------------------------------------------------------------------
+inline void CoherentHierarchicalCullingManager2::SkipQuery(HierarchyNode *node) const
+{
+	// -- set node to be visible in this frame, then traverse it
+	mHierarchyInterface->SetLastVisited(node, mHierarchyInterface->GetFrameId());
+	
+	mHierarchyInterface->PullUpVisibility(node);			
+	mHierarchyInterface->TraverseNode(node);
+}
+
+} // namespace GtpVisibility
Index: GTP/trunk/Lib/Vis/OnlineCullingCHC/src/GtpVisibility.vcproj
===================================================================
--- GTP/trunk/Lib/Vis/OnlineCullingCHC/src/GtpVisibility.vcproj	(revision 2353)
+++ GTP/trunk/Lib/Vis/OnlineCullingCHC/src/GtpVisibility.vcproj	(revision 2360)
@@ -259,4 +259,7 @@
 			</File>
 			<File
+				RelativePath=".\CoherentHierarchicalCullingManager2.cpp">
+			</File>
+			<File
 				RelativePath=".\CullingLogManager.cpp">
 			</File>
@@ -266,4 +269,7 @@
 			<File
 				RelativePath="..\src\DummyPreprocessingManager.cpp">
+			</File>
+			<File
+				RelativePath=".\FlexibleHeap.h">
 			</File>
 			<File
@@ -301,4 +307,7 @@
 			<File
 				RelativePath="..\include\CoherentHierarchicalCullingManager.h">
+			</File>
+			<File
+				RelativePath="..\include\CoherentHierarchicalCullingManager2.h">
 			</File>
 			<File
Index: GTP/trunk/Lib/Vis/OnlineCullingCHC/src/FlexibleHeap.h
===================================================================
--- GTP/trunk/Lib/Vis/OnlineCullingCHC/src/FlexibleHeap.h	(revision 2360)
+++ GTP/trunk/Lib/Vis/OnlineCullingCHC/src/FlexibleHeap.h	(revision 2360)
@@ -0,0 +1,231 @@
+#ifndef FLEXIBLEHEAP_H
+#define FLEXIBLEHEAP_H
+
+#include <vector>
+
+
+namespace GtpVisibility {
+
+const static int NOT_IN_HEAP = -100;
+
+/** This class implements an element for a heap.
+	Classes using the heap should be inherited from this class.
+*/
+class Heapable
+{
+public:
+	Heapable(): mPriority(0) { NotInHeap(); SetPriority(0.0f); }
+
+	inline bool IsInHeap() { return mPosition != NOT_IN_HEAP; }
+	inline void NotInHeap() { mPosition = NOT_IN_HEAP; }
+	inline int GetHeapPos() { return mPosition; }
+	inline void SetHeapPos(const int t) { mPosition = t; }
+
+	inline void  SetPriority(const float k) { mPriority = k; }
+	virtual float GetPriority() const = 0;
+
+protected:
+
+	float mPriority;
+	int mPosition;
+};
+
+
+/** This class implements a flexible heap for
+	use as a priority queue.
+
+	Unlike the stl priority_queue, the class allows access to all 
+	elements. It implements efficient insertion routines and remove routines
+	of arbitrary elements.
+*/
+template<typename T>
+class FlexibleHeap
+{
+public:
+	FlexibleHeap() { }
+	FlexibleHeap(const unsigned int n): mBuffer(n) { }
+
+	void Push(T t) { Push(t, t->GetPriority()); }
+	void Push(T t, const float priority);
+	bool Update(T t) { return Update(t, t->GetPriority()); }
+	bool Update(T t, const float priority);
+
+	unsigned int Size() const { return (unsigned int)mBuffer.size(); }
+	bool Empty() const {return mBuffer.empty(); }
+	T Item(const unsigned int i) { return mBuffer[i]; }
+	const T Item(const unsigned int i) const { return mBuffer[i]; }
+	T Pop();
+	T Top() const { return (mBuffer.empty() ? (T)NULL : mBuffer.front()); }
+	/** Erases the element from the heap.
+	*/
+	T Erase(T);
+
+protected:
+
+	void Place(T x, const unsigned int i);
+	void Swap(const unsigned int i, const unsigned int j);
+
+	unsigned int Parent(const unsigned int i) const { return (i - 1) / 2; }
+	unsigned int Left(const unsigned int i) const { return 2 * i + 1; }
+	unsigned int Right(const unsigned int i) const { return 2 * i + 2; }
+
+	void UpHeap(const unsigned int i);
+	void DownHeap(const unsigned int i);
+
+	std::vector<T> mBuffer;
+};
+
+
+/*****************************************************************************/
+/*                         MyHeap implementation                             *
+/*****************************************************************************/
+
+template <typename T>
+inline void FlexibleHeap<T>::Place(T x, const unsigned int i)
+{
+	mBuffer[i] = x;
+	x->SetHeapPos(i);
+}
+
+
+template <typename T>
+void FlexibleHeap<T>::Swap(const unsigned int i, const unsigned int j)
+{
+	T tmp = mBuffer[i];
+
+	Place(mBuffer[j], i);
+	Place(tmp, j);
+}
+
+
+template <typename T>
+void FlexibleHeap<T>::UpHeap(const unsigned int i)
+{
+	T moving = mBuffer[i];
+	unsigned int index = i;
+	unsigned int p = Parent(i);
+
+	while ((index > 0) && (moving->GetPriority() > mBuffer[p]->GetPriority()))
+	{
+		Place(mBuffer[p], index);
+		index = p;
+		p = Parent(p);
+	}
+
+	if (index != i)
+	{
+		Place(moving, index);
+	}
+}
+
+template <typename T>
+void FlexibleHeap<T>::DownHeap(const unsigned int i)
+{
+	T moving = mBuffer[i];
+
+	unsigned int index = i;
+	unsigned int l = Left(i);
+	unsigned int r = Right(i);
+	unsigned int largest;
+
+	while (l < (int)mBuffer.size())
+	{
+		if ((r < (unsigned int)mBuffer.size()) && (mBuffer[l]->GetPriority() < mBuffer[r]->GetPriority()))
+			largest = r;
+		else 
+			largest = l;
+
+		if (moving->GetPriority() < mBuffer[largest]->GetPriority())
+		{
+			Place(mBuffer[largest], index);
+			index = largest;
+			l = Left(index);
+			r = Right(index);
+		}
+		else
+		{
+			break;
+		}
+	}
+
+	if (index != i)
+	{
+		Place(moving, index);
+	}
+}
+
+
+template <typename T>
+void FlexibleHeap<T>::Push(T t, const float v)
+{
+	t->SetPriority(v);
+
+	unsigned int i = (unsigned int)mBuffer.size();
+
+	t->SetHeapPos(i);
+	mBuffer.push_back(t);
+
+	UpHeap(i);
+}
+
+template <typename T>
+bool FlexibleHeap<T>::Update(T t, const float v)
+{
+	if (t->IsInHeap())
+		return false;
+
+	t->SetPriority(v);
+
+	const unsigned int i = t->GetHeapPos();
+
+	if ((i > 0) && (v > mBuffer[Parent(i)]->GetPriority()))
+		UpHeap(i);
+	else
+		DownHeap(i);
+
+	return true;
+}
+
+template <typename T>
+T FlexibleHeap<T>::Pop()
+{
+	if (mBuffer.empty()) 
+		return NULL;
+
+	Swap(0, (int)mBuffer.size() - 1);
+
+	T dead = mBuffer.back();
+	mBuffer.pop_back();
+
+	DownHeap(0);
+	dead->NotInHeap();
+
+	return dead;
+}
+
+
+template <typename T>
+T FlexibleHeap<T>::Erase(T t)
+{
+	if (!t->IsInHeap()) 
+		return (T)NULL;
+
+	const int i = t->GetHeapPos();
+
+	Swap(i, (int)mBuffer.size() - 1);
+	
+	mBuffer.pop_back();
+	t->NotInHeap();
+
+	if (mBuffer[i]->GetPriority() < t->GetPriority())
+		DownHeap(i);
+	else
+		UpHeap(i);
+
+	return t;
+}
+
+}
+
+// FLEXIBLEHEAP_H
+#endif
