Index: trunk/VUT/OcclusionCullingSceneManager/include/OgreOcclusionCullingTerrainSceneTraverser.h
===================================================================
--- trunk/VUT/OcclusionCullingSceneManager/include/OgreOcclusionCullingTerrainSceneTraverser.h	(revision 35)
+++ trunk/VUT/OcclusionCullingSceneManager/include/OgreOcclusionCullingTerrainSceneTraverser.h	(revision 35)
@@ -0,0 +1,158 @@
+#ifndef _OcclusionCullingSceneTraverser_H__
+#define _OcclusionCullingSceneTraverser_H__
+
+#include "OgreSceneNode.h"
+#include "OgreSceneManager.h"
+#include "OgrePrerequisites.h"
+#include "OgreSolidHalfBoundingBox.h"
+#include "OgreCamera.h"
+#include "OgreRenderSystem.h"
+#include <queue>
+
+using namespace std;
+
+namespace Ogre {
+	/**
+		This class implements the compare operator for the priority queue.
+		a lower distance has a higher value in the queue
+	*/
+	template <typename T> class myless
+	{
+	public:
+		myless(Camera *cam) { mCamera = cam; }
+		//bool operator() (HierarchyNode *v1, HierarchyNode *v2) const
+		bool operator() (T v1, T v2) const
+		{
+			return v1->getSquaredViewDepth(mCamera) > v2->getSquaredViewDepth(mCamera);
+		}
+	private:
+		Camera *mCamera;
+	};
+
+	typedef pair<SceneNode *, HardwareOcclusionQuery *> query_pair;
+	typedef priority_queue<SceneNode *, vector<SceneNode *>, myless<vector<SceneNode *>::value_type> > PriorityQueue;
+	typedef queue<query_pair> QueryQueue;
+	/**
+		Class which implements a scene mangager which uses occlusion queries for culling occluded objects
+	*/
+	class OcclusionCullingSceneTraverser
+	{
+	public:
+		/** Construction taking the current scene manager and the current rendersystem as argument
+		@param sm current scene manager
+		@param rsys current render system 
+		*/
+		OcclusionCullingSceneTraverser(SceneManager *sm, RenderSystem *rsys);
+		~OcclusionCullingSceneTraverser();
+	
+		enum {RENDER_CULL_FRUSTUM, RENDER_STOP_AND_WAIT, RENDER_COHERENT, NUM_RENDERMODES};
+		
+		/** Renders the scene with the specified algorithm
+			@comment 
+			The algorithm type can be set with the parameter "Algorithm" and setOption.
+
+			The algorithm is one of:
+			RENDER_CULL_FRUSTUM: renders the scene with view frustum culling only
+			RENDER_STOP_AND_WAIT: renders the scene with the hierarchical stop and wait algorithm
+			RENDER_COHERENT: renders the scene with the coherent hierarchical algorithm
+			
+			@param cam current camera
+			@param root root of hierarchy 
+		*/
+		void renderScene( Camera *cam, SceneNode *root );
+	
+		
+		/** Sets the given option for the scene traverser.
+			       @remarks
+			Options are:
+			"Algorithm", int *;			
+		*/
+		bool setOption( const String &, const void * );
+		/** Gets the given option for the scene traverser.
+	        @remarks
+		    See setOption
+		*/
+		bool getOption( const String &, void * );
+		bool getOptionKeys( StringVector &refKeys );
+		
+		/** Sets pointer to the current scene manager.
+		@param the scene manager */
+		void setSceneManager( SceneManager *sm );
+		
+		/** Sets pointer to the current render system 
+		@param the rendersystem */
+		void setRenderSystem( RenderSystem *rsys );
+		
+		/** Doing some necessary preprocessing.
+		@comment e.g., initialises occlusion queries */
+		void preprocess( void );
+
+		/** Sets the current number of scene nodes in the scene.
+		@param num number of scene nodes
+		*/
+		void setNumSceneNodes(int num );
+
+	protected:
+		/** query mode (= without color) or RENDER_MODE */
+		enum {MODE_QUERY, MODE_RENDER};
+		/** returns true if node is leaf of the hierarchy */
+		bool isLeaf( SceneNode *node );
+		//HACK
+		//unsigned int countSceneNodes(SceneNode *node);
+		void traverseNode( Camera *cam, SceneNode *node );
+		/** Renders current scene node 
+		@param cam current camera
+		@param node current scene node to be rendered
+		*/
+		void renderSceneNode( Camera *cam, SceneNode *node);
+		/** Sets rendering mode, e.g. query mode or render mode*/
+		void setRenderingMode( int mode );
+		/** Renders the scene with view frustum culling only. */
+		void renderCullFrustum( Camera *cam );
+		/** Renders the scene with the hierarchical stop and wait algorithm. */
+		void renderStopAndWait( Camera *cam );
+		/** Renders the scene with the coherent hierarchical algorithm and the query queye. */
+		void renderCoherentWithQueue( Camera *cam );
+		/** Issue a occlusion query for this node. */
+		HardwareOcclusionQuery *issueOcclusionQuery( SceneNode *node, bool wasVisible );
+		/** Pulls up the visibility from the child nodes. */
+		void pullUpVisibility( SceneNode *node );
+		/** delete all previously defined occlusion queries */
+		void deleteQueries();
+		/** Renders bounding box of specified node.
+		@param the scene node contained in the bounding box to be rendered
+		*/
+		void renderBoundingBox( SceneNode *node );
+		/** Returns one half of the bounding box.
+		@param the half of the bouding box
+		*/
+		SolidHalfBoundingBox *getSolidHalfBoundingBox( int half );
+
+		// we use a priority queue rather than a renderstack
+		PriorityQueue *mDistanceQueue; 
+		
+		std::vector<HardwareOcclusionQuery *> mOcclusionQueries;
+		// two halfes of a aabb
+		SolidHalfBoundingBox *mHalfBoundingBox[2];	
+
+		int mCurrentAlgorithm;
+
+		unsigned int mFrameId;
+		unsigned int mVisibilityThreshold;
+		
+		SceneManager *mSceneManager;
+		RenderSystem *mRenderSystem;
+
+		int mCurrentTestIdx;
+		int mQueryMode;
+
+		//--- statistics
+		unsigned int mNumSceneNodes;
+		unsigned int mNumTraversedNodes;
+		unsigned int mNumQueryCulledNodes;
+		unsigned int mNumFrustumCulledNodes;
+		unsigned int mNumRenderedGeometry;
+	};
+
+}
+#endif // OCCLUSIONCULLINGSCENEMANAGER_H
Index: trunk/VUT/OcclusionCullingSceneManager/src/OgreOcclusionCullingTerrainSceneTraverser.cpp
===================================================================
--- trunk/VUT/OcclusionCullingSceneManager/src/OgreOcclusionCullingTerrainSceneTraverser.cpp	(revision 35)
+++ trunk/VUT/OcclusionCullingSceneManager/src/OgreOcclusionCullingTerrainSceneTraverser.cpp	(revision 35)
@@ -0,0 +1,416 @@
+#include "OgreOcclusionCullingSceneTraverser.h"
+#include "OgreMath.h"
+#include "OgreIteratorWrappers.h"
+#include "OgreCamera.h"
+#include "OgreHardwareOcclusionQuery.h"
+//#include "OgreWireBoundingBox.h"
+#include "OgreSolidHalfBoundingBox.h"
+
+
+#include <windows.h>
+
+namespace Ogre {
+	
+	//-----------------------------------------------------------------------
+	OcclusionCullingSceneTraverser::OcclusionCullingSceneTraverser(SceneManager *sm, RenderSystem *rsys): 
+	mFrameId(1), mDistanceQueue(NULL), mVisibilityThreshold(0), mCurrentTestIdx(0),
+	mQueryMode(MODE_RENDER), mNumSceneNodes(0), mCurrentAlgorithm(RENDER_COHERENT),
+	mNumTraversedNodes(0), mNumQueryCulledNodes(0), mNumFrustumCulledNodes(0), 
+	mNumRenderedGeometry(0), mSceneManager(sm), mRenderSystem(rsys)
+	{		
+		mHalfBoundingBox[0] = mHalfBoundingBox[1] = 0;
+	}
+	//-----------------------------------------------------------------------
+	OcclusionCullingSceneTraverser::~OcclusionCullingSceneTraverser()
+	{		
+		if(mHalfBoundingBox[0]) delete mHalfBoundingBox[0];
+		if(mHalfBoundingBox[1]) delete mHalfBoundingBox[1];
+
+		deleteQueries();
+		//SceneManager::~SceneManager();
+	}
+	//-----------------------------------------------------------------------
+	void OcclusionCullingSceneTraverser::renderScene( Camera *cam, SceneNode *root )
+	{
+		mNumTraversedNodes = 0;
+		mNumQueryCulledNodes = 0;
+		mNumFrustumCulledNodes = 0;
+		mNumRenderedGeometry = 0;
+		
+		mDistanceQueue = new PriorityQueue(myless<SceneNode *>(cam));
+		mDistanceQueue->push(root);
+		mCurrentTestIdx = 0;
+
+		mCurrentAlgorithm = RENDER_CULL_FRUSTUM;
+		switch(mCurrentAlgorithm)
+		{
+			case RENDER_CULL_FRUSTUM:
+				renderCullFrustum(cam);
+		        break;
+			case RENDER_STOP_AND_WAIT:
+				renderStopAndWait(cam);
+				break;
+			case RENDER_COHERENT:
+				renderCoherentWithQueue(cam);
+				break;
+			default:
+				renderCullFrustum(cam);
+				break;
+		}	
+		
+		delete mDistanceQueue;
+
+		mFrameId ++;
+	}
+	//-----------------------------------------------------------------------
+	void OcclusionCullingSceneTraverser::renderCoherentWithQueue(Camera *cam)
+	{
+		QueryQueue queryQueue;
+
+		//-- PART 1: process finished occlusion queries
+		while(!mDistanceQueue->empty() || !queryQueue.empty())
+		{
+			while(!queryQueue.empty() && 
+				  ((queryQueue.front().second)->resultAvailable() || mDistanceQueue->empty()))
+			{
+				SceneNode *node = queryQueue.front().first;
+				HardwareOcclusionQuery *query = queryQueue.front().second;
+
+				queryQueue.pop();
+			
+				// wait until result available
+				unsigned int visiblePixels;
+				query->pullOcclusionQuery(&visiblePixels);
+
+				if(visiblePixels > mVisibilityThreshold)
+				{
+					pullUpVisibility(node);
+					traverseNode(cam, node);
+				}
+				else
+				{
+					mNumQueryCulledNodes ++;
+				}
+			}	
+
+			//-- PART 2: hierarchical traversal
+			if(!mDistanceQueue->empty())
+			{
+				SceneNode *node = mDistanceQueue->top();
+				mDistanceQueue->pop();
+	
+				if(cam->isVisible(node->_getWorldAABB()))
+				{
+					// identify previously visible nodes
+					bool wasVisible = node->isNodeVisible() && (node->lastVisited() == mFrameId - 1);
+					
+					// identify nodes that we cannot skip queries for
+					bool leafOrWasInvisible = !wasVisible || isLeaf(node);
+
+					// reset node's visibility classification 
+					node->setNodeVisible(false);
+
+					// update node's visited flag
+					node->setLastVisited(mFrameId);
+				
+					// skip testing previously visible interior nodes
+					if(leafOrWasInvisible)
+					{
+						HardwareOcclusionQuery *query = issueOcclusionQuery(node, wasVisible);
+						queryQueue.push(query_pair(node, query));
+					}
+					
+					// always traverse a node if it was visible
+					if(wasVisible)
+					{
+						traverseNode(cam, node);
+					}
+				}
+				else
+				{
+					mNumFrustumCulledNodes ++;
+				}
+			}
+		}
+	}
+	//-----------------------------------------------------------------------
+	void OcclusionCullingSceneTraverser::renderCullFrustum(Camera *cam)
+	{
+		while(!mDistanceQueue->empty())
+		{
+			SceneNode *node = mDistanceQueue->top();
+			mDistanceQueue->pop();
+	
+			// interesting for visualization purpose
+			node->setNodeVisible(false);
+				
+			if(!cam->isVisible(node->_getWorldAABB()))
+			{
+				// update node's visited flag 
+				node->setLastVisited(mFrameId);
+				node->setNodeVisible(true);
+				traverseNode(cam, node);
+			}
+			//else
+				if(cam->isVisible(node->_getWorldAABB()))
+				{
+					mNumQueryCulledNodes ++;
+				}else
+			{			
+				mNumFrustumCulledNodes ++;
+			}
+		}
+	}	
+	//-----------------------------------------------------------------------
+	void OcclusionCullingSceneTraverser::renderStopAndWait(Camera *cam)
+	{
+		while(!mDistanceQueue->empty())
+		{
+			SceneNode *node = mDistanceQueue->top();
+			mDistanceQueue->pop();
+		
+			// interesting for the visualization
+			node->setNodeVisible(false);
+			node->setLastVisited(mFrameId);
+
+			if(cam->isVisible(node->_getWorldAABB()))
+			{
+				HardwareOcclusionQuery *query = issueOcclusionQuery(node, false);
+				
+				unsigned int visiblePixels;
+				// wait if result not available
+				query->pullOcclusionQuery(&visiblePixels);
+				
+				// node visible
+				if(visiblePixels > mVisibilityThreshold)
+				{
+					traverseNode(cam, node);
+				}
+				else
+				{
+					mNumQueryCulledNodes ++;
+				}
+			}
+			else
+			{
+				mNumFrustumCulledNodes ++;
+			}
+		}
+	}
+	//-----------------------------------------------------------------------
+	HardwareOcclusionQuery *OcclusionCullingSceneTraverser::issueOcclusionQuery( SceneNode *node, bool wasVisible )
+	{
+		// change state so the bounding box gets not actually rendered on the screen
+		setRenderingMode(MODE_QUERY);
+
+		// get next available test id
+		HardwareOcclusionQuery *query = mOcclusionQueries[mCurrentTestIdx++];
+		
+		query->beginOcclusionQuery();
+				
+		renderBoundingBox(node);
+
+		query->endOcclusionQuery();
+
+		return query;
+	}
+	//-----------------------------------------------------------------------
+	void OcclusionCullingSceneTraverser::setRenderingMode( int mode )
+	{	
+		// avoid unnecessary state changes
+		if(mode != mQueryMode)
+		{
+			bool enabled = (mode == MODE_RENDER);
+			
+			mRenderSystem->_setColourBufferWriteEnabled(enabled, 
+				enabled, enabled, enabled);
+			mRenderSystem->_setDepthBufferWriteEnabled(enabled);
+			mRenderSystem->setLightingEnabled(enabled);
+
+			mQueryMode = mode;
+		}
+	}
+	//-----------------------------------------------------------------------
+	void OcclusionCullingSceneTraverser::traverseNode( Camera *cam, SceneNode *node )
+	{
+		mNumTraversedNodes ++;
+		
+		if(node->numAttachedObjects() > 0)
+		{
+			renderSceneNode(cam, node);
+		}
+
+		// internal node: add children to priority queue for further processing
+		Node::ChildNodeIterator it = node->getChildIterator();
+					
+		while (it.hasMoreElements())			
+		{ 
+			SceneNode* sceneChild = static_cast<SceneNode*>(it.getNext());
+			mDistanceQueue->push(sceneChild);
+		}
+	}
+	//-----------------------------------------------------------------------
+	void OcclusionCullingSceneTraverser::renderSceneNode( Camera *cam, SceneNode *node )
+	{
+		setRenderingMode(MODE_RENDER);
+		
+		//HACK (too slow)
+		mSceneManager->_renderSceneNode(cam, node);
+		//MessageBox( NULL, "myplugin registered", "this is my plugin", MB_OK | MB_ICONERROR | MB_TASKMODAL);
+	}
+	//-----------------------------------------------------------------------
+	void OcclusionCullingSceneTraverser::preprocess( void )
+	{
+		//-- initialise occlusion queries.
+		deleteQueries();
+		
+		for(unsigned int i=0; i < mNumSceneNodes; i++)
+		{
+			mOcclusionQueries.push_back(mRenderSystem->createHardwareOcclusionQuery());
+		}	
+	}
+	//-----------------------------------------------------------------------
+	void OcclusionCullingSceneTraverser::setSceneManager( SceneManager *sm )
+	{
+		mSceneManager = sm;
+	}
+	//-----------------------------------------------------------------------
+	void OcclusionCullingSceneTraverser::setRenderSystem( RenderSystem *rsys )
+	{
+		mRenderSystem = rsys;
+	}
+	//-----------------------------------------------------------------------
+	/*unsigned int OcclusionCullingSceneManager::countSceneNodes(SceneNode *node)
+	{
+		unsigned int result = 1;
+		
+		Node::ChildNodeIterator it = node->getChildIterator();
+		
+		while (it.hasMoreElements())
+		{ 
+			SceneNode* sceneChild = static_cast<SceneNode*>(it.getNext());
+			result += countSceneNodes(sceneChild);
+        }
+
+		return result;
+	}*/
+	//-----------------------------------------------------------------------
+	bool OcclusionCullingSceneTraverser::isLeaf( SceneNode *node )
+	{
+		return (node->numChildren() == 0);
+	}
+	//-----------------------------------------------------------------------
+	void OcclusionCullingSceneTraverser::pullUpVisibility( SceneNode *node )
+	{
+		while(node && !node->isNodeVisible())
+		{
+			node->setNodeVisible(true);
+			node = static_cast<SceneNode *>(node->getParent());
+		}
+	}
+	//-----------------------------------------------------------------------
+	void OcclusionCullingSceneTraverser::deleteQueries( void )
+	{
+		for(unsigned int i=0; i < mNumSceneNodes; i++)
+			delete mOcclusionQueries[i];
+
+		mOcclusionQueries.clear();
+	}
+	//-----------------------------------------------------------------------
+	void OcclusionCullingSceneTraverser::renderBoundingBox( SceneNode *node )
+	{
+		// Render two halfes of the bounding box (using triangle fans)
+		for(int half = 0; half < 2; half ++)
+		{
+			SolidHalfBoundingBox *box = getSolidHalfBoundingBox(half);
+			
+			box->setupBoundingBox(node->_getWorldAABB());
+
+			static RenderOperation ro;
+			mSceneManager->useRenderableViewProjMode(box);
+			box->getRenderOperation(ro);
+			ro.srcRenderable = box; 
+			mRenderSystem->_render(ro);
+
+			//mSceneManager->renderSingleObject(getSolidHalfBoundingBox(half), 
+			//	getSolidHalfBoundingBox(half)->getTechnique()->getPass(0), false);
+		}
+	}
+	//-----------------------------------------------------------------------
+	SolidHalfBoundingBox *OcclusionCullingSceneTraverser::getSolidHalfBoundingBox( int half )
+	{
+		if(!mHalfBoundingBox[half])
+			mHalfBoundingBox[half] = new SolidHalfBoundingBox(half == 1);
+
+		return mHalfBoundingBox[half];	
+	}
+	//-----------------------------------------------------------------------
+	bool OcclusionCullingSceneTraverser::setOption( const String & key, const void * val )
+	{
+		if ( key == "Algorithm" )
+		{
+			mCurrentAlgorithm = * static_cast < const int * > ( val );
+			return true;
+		}
+		if ( key == "Threshold" )
+		{
+			mVisibilityThreshold = * static_cast < const int * > ( val );
+			return true;
+		}
+
+		return false;
+	}
+	//-----------------------------------------------------------------------
+	bool OcclusionCullingSceneTraverser::getOption( const String & key, void *val )
+	{
+		if ( key == "Algorithm" )
+		{
+			* static_cast < int * > ( val ) = mCurrentAlgorithm;
+			return true;
+		}
+		if ( key == "Threshold" )
+		{
+			* static_cast < unsigned int * > ( val ) = mVisibilityThreshold;
+			return true;
+		}
+		if ( key == "NumSceneNodes" )
+		{
+			* static_cast < unsigned int * > ( val ) = mNumSceneNodes;
+			return true;
+		}
+		if ( key == "NumTraversedNodes" )
+		{
+			* static_cast < unsigned int * > ( val ) = mNumTraversedNodes;
+			return true;
+		}
+		if ( key == "NumQueryCulledNodes" )
+		{
+			* static_cast < unsigned int * > ( val ) = mNumQueryCulledNodes;
+			return true;
+		}
+		if ( key == "NumFrustumCulledNodes" )
+		{
+			* static_cast < unsigned int * > ( val ) = mNumFrustumCulledNodes;
+			return true;
+		}
+		return false;
+	}
+	//-----------------------------------------------------------------------
+	bool OcclusionCullingSceneTraverser::getOptionKeys( StringVector & refKeys )
+	{
+		refKeys.push_back( "Algorithm" );
+		refKeys.push_back( "Threshold" );
+		refKeys.push_back( "NumSceneNodes" );
+		refKeys.push_back( "NumTraversedNodes" );
+		refKeys.push_back( "NumQueryCulledNodes" );
+		refKeys.push_back( "NumFrustumCulledNodes" );
+		//refKeys.push_back( "mNumRenderedGeometry" );
+
+		return true;
+	}
+	//-----------------------------------------------------------------------
+	void OcclusionCullingSceneTraverser::setNumSceneNodes(int num)
+	{
+		mNumSceneNodes = num;
+	}
+}	
