/*
-----------------------------------------------------------------------------
This source file is part of the GameTools Project
http://www.gametools.org

Author: Martin Szydlowski
-----------------------------------------------------------------------------
*/

#include <OgreCamera.h>
#include <OgreSubEntity.h>
#include <OgreMaterialManager.h>
#include <OgreLogManager.h>
#include <OgreStringConverter.h>

#include "OgreKdTreeSceneManager.h"
#include "OgreKdTreeSceneNode.h"
#include "OgreKdTree.h"

#include <OgreMeshInstance.h>
#include <OgreBoundingBoxConverter.h>
#include <OgreTypeConverter.h>
#include <VisibilityEnvironment.h>
#include "OgreVisibilityOptionsManager.h"

namespace Ogre
{

KdTreeSceneManager::KdTreeSceneManager(const String& name, GtpVisibility::VisibilityManager *vm):
SceneManager(name), 
mVisibilityManager(vm), 
mKdTree(0), 
mMaxDepth(KDTREE_MAX_DEPTH),
mShowBoxes(false),
mHiLiteLevel(0),
mShowAllBoxes(false),
mEnhancedVisiblity(true),
mBuildMethod(KdTree::KDBM_RECURSIVE),
mRenderMethod(KdTree::KDRM_INTERNAL),
mShowVisualization(false),
mRenderNodesForViz(false),
mRenderNodesContentForViz(false),
mVisualizeCulledNodes(false),
mLeavePassesInQueue(0),
mDelayRenderTransparents(true),
mUseDepthPass(false),
mIsDepthPassPhase(false),
mUseItemBuffer(false),
mIsItemBufferPhase(false),
mCurrentEntityId(1),
mEnableDepthWrite(true),
mSkipTransparents(false),
mRenderTransparentsForItemBuffer(true),
mExecuteVertexProgramForAllPasses(false),
mIsHierarchicalCulling(false),
mDeleteQueueAfterRendering(true),
mViewCellsLoaded(false),
mUseViewCells(false),
mUseVisibilityFilter(false),
mViewCellsManager(0),
mElementaryViewCell(0),
mCurrentViewCell(0)
{
	// Replace root node with my node
	OGRE_DELETE(mSceneRoot);
	mSceneRoot = new KdTreeSceneNode(this, "root node");
	mSceneRoot->_notifyRootNode();

	// init heirarchy interface
	mHierarchyInterface = new KdTreeHierarchyInterface(this, mDestRenderSystem);
}

KdTreeSceneManager::~KdTreeSceneManager(void)
{
	delete mHierarchyInterface;
	delete mKdTree;
}

void KdTreeSceneManager::clearScene()
{
	// DEBUG
	//if (mKdTree)
	//	mKdTree->dump();

	// must happen before actual scene is cleared
	OGRE_DELETE(mKdTree);

	SceneManager::clearScene();
}


const String& KdTreeSceneManager::getTypeName(void) const
{
	return KdTreeSceneManagerFactory::FACTORY_TYPE_NAME;
}

void KdTreeSceneManager::setShowBoxes(bool showboxes)
{
	mShowBoxes = showboxes;
}

bool KdTreeSceneManager::getShowBoxes(void) const
{
	return mShowBoxes;
}

bool KdTreeSceneManager::setOption(const String& strKey, const void* pValue)
{
	// change max depth of the kdtree
	// rebuild the tree if already exists
	if (strKey == "KdTreeMaxDepth")
	{
		int maxdepth = *static_cast<const int *>(pValue);

		// no negative depth, plz!
		if (maxdepth < 0)
		{
			return false;
		}
		else
		{
			mMaxDepth = maxdepth;
			if (mHiLiteLevel > mMaxDepth)
				mHiLiteLevel = mMaxDepth;
			return true;
		}
		return true;
	}
	else if (strKey == "KT")
	{
		Real kt = *static_cast<const Real *>(pValue);
		if (kt > 0)
		{
			PlaneEvent::KT = kt;
			return true;
		}
		else
		{
			return false;
		}
	}
	else if (strKey == "KI")
	{
		Real ki = *static_cast<const Real *>(pValue);
		if (ki > 0)
		{
			PlaneEvent::KI = ki;
			return true;
		}
		else
		{
			return false;
		}
	}
	else if (strKey == "RebuildKdTree")
	{
		OGRE_DELETE(mKdTree);
		mKdTree = new KdTree(mMaxDepth, mBuildMethod, mHiLiteLevel, mShowAllBoxes, mShowNodes);
		mKdTree->build(static_cast<KdTreeSceneNode *>(mSceneRoot));
		mKdTree->setEnhancedVis(mEnhancedVisiblity);
		return true;
	}
	else if (strKey == "EnhancedVisibility")
	{
		bool enh = *static_cast<const bool *>(pValue);
		mEnhancedVisiblity = enh;
		if (mKdTree)
			mKdTree->setEnhancedVis(mEnhancedVisiblity);
		//setEnhancedVis(enh);
		return true;
	}
	else if (strKey == "BuildMethod")
	{
		KdTree::BuildMethod bm = *static_cast<const KdTree::BuildMethod *>(pValue);
		if (bm == KdTree::KDBM_RECURSIVE || bm == KdTree::KDBM_PRIORITYQUEUE)
		{
			mBuildMethod = bm;
			return true;
		}
		else
		{
			return false;
		}
	}
	else if (strKey == "RenderMethod")
	{
		KdTree::RenderMethod rm = *static_cast<const KdTree::RenderMethod *>(pValue);
		if (rm == KdTree::KDRM_INTERNAL)
		{
			mRenderMethod = rm;
			return true;
		}
		else if (rm == KdTree::KDRM_GTP_VFC)
		{
			mRenderMethod = rm;
			int cmt = GtpVisibility::VisibilityEnvironment::FRUSTUM_CULLING;
			return VisibilityOptionsManager(mVisibilityManager, mHierarchyInterface)
				.setOption("Algorithm", &cmt);
		}
		else if (rm == KdTree::KDRM_GTP_SWC)
		{
			mRenderMethod = rm;
			int cmt = GtpVisibility::VisibilityEnvironment::STOP_AND_WAIT_CULLING;
			return VisibilityOptionsManager(mVisibilityManager, mHierarchyInterface)
				.setOption("Algorithm", &cmt);
		}
		else if (rm == KdTree::KDRM_GTP_CHC)
		{
			mRenderMethod = rm;
			int cmt = GtpVisibility::VisibilityEnvironment::COHERENT_HIERARCHICAL_CULLING;
			return VisibilityOptionsManager(mVisibilityManager, mHierarchyInterface)
				.setOption("Algorithm", &cmt);
		}
		else
		{
			return false;
		}
	}
	// little hack in case someone uses "Algorithm" option from VisOptMan directly
	else if (strKey == "Algorithm")
	{
		bool success = VisibilityOptionsManager(mVisibilityManager, mHierarchyInterface)
			.setOption(strKey, pValue);
		// change setting only if change in VisOptMan was successful
		if (success)
		{
			int val = *static_cast<const int *>(pValue);
			if (val == GtpVisibility::VisibilityEnvironment::FRUSTUM_CULLING)
				mRenderMethod = KdTree::KDRM_GTP_VFC;
			else if (val == GtpVisibility::VisibilityEnvironment::STOP_AND_WAIT_CULLING)
				mRenderMethod = KdTree::KDRM_GTP_SWC;
			else if (val == GtpVisibility::VisibilityEnvironment::COHERENT_HIERARCHICAL_CULLING)
				mRenderMethod = KdTree::KDRM_GTP_CHC;
			// default, should never happen
			else
				mRenderMethod = KdTree::KDRM_INTERNAL;
		}
		else
		{
			mRenderMethod = KdTree::KDRM_INTERNAL;
		}
		return success;
	}
	else if (strKey == "ShowKdTree")
	{
		bool sk = *static_cast<const bool *>(pValue);
		mShowBoxes = sk;
		return true;
	}
	else if (strKey == "HiLiteLevel")
	{
		int hl = *static_cast<const int *>(pValue);
		if (hl >= 0 && hl <= mMaxDepth)
		{
			mHiLiteLevel = hl;
			if (mKdTree)
				mKdTree->setHiLiteLevel(mHiLiteLevel);
			return true;
		}
		else
		{
			return false;
		}
	}
	else if (strKey == "ShowAllBoxes")
	{
		bool sa = *static_cast<const bool *>(pValue);
		mShowAllBoxes = sa;
		if (mKdTree)
			mKdTree->setShowAllBoxes(mShowAllBoxes);
		return true;
	}
	else if (strKey == "ShowNodes")
	{
		bool sn = *static_cast<const bool *>(pValue);
		mShowNodes = sn;
		if (mKdTree)
			mKdTree->setShowNodes(mShowNodes);
		return true;
	}
	// options for CHC
	else if (strKey == "UseDepthPass")
	{
		mUseDepthPass = (*static_cast<const bool *>(pValue));
		return true;
	}
	else if (strKey == "PrepareVisualization")
	{
		mShowVisualization = (*static_cast<const bool *>(pValue));
		return true;
	}
	else if (strKey == "RenderNodesForViz")
	{
		mRenderNodesForViz = (*static_cast<const bool *>(pValue));
		return true;
	}
	else if (strKey == "RenderNodesContentForViz")
	{
		mRenderNodesContentForViz = (*static_cast<const bool *>(pValue));
		return true;
	}
	else if (strKey == "SkyBoxEnabled")
	{
		mSkyBoxEnabled = (*static_cast<const bool *>(pValue));
		return true;
	}
	else if (strKey == "SkyPlaneEnabled")
	{
		mSkyPlaneEnabled = (*static_cast<const bool *>(pValue));
		return true;
	}
	else if (strKey == "SkyDomeEnabled")
	{
		mSkyDomeEnabled = (*static_cast<const bool *>(pValue));
		return true;
	}
	else if (strKey == "VisualizeCulledNodes")
	{
		mVisualizeCulledNodes = (*static_cast<const bool *>(pValue));
		return true;
	}
	else if (strKey == "DelayRenderTransparents")
	{
		mDelayRenderTransparents = (*static_cast<const bool *>(pValue));
		return true;
	}

	else if (strKey == "DepthWrite")
	{
		mEnableDepthWrite = (*static_cast<const bool *>(pValue));
		return true;
	}
	else if (strKey == "UseItemBuffer")
	{
		mUseItemBuffer = (*static_cast<const bool *>(pValue));
		return true;
	}
	else if (strKey == "ExecuteVertexProgramForAllPasses")
	{ 
		mExecuteVertexProgramForAllPasses  = (*static_cast<const bool *>(pValue));
		return true;
	}
	else if (strKey == "RenderTransparentsForItemBuffer")
	{ 
		mRenderTransparentsForItemBuffer  = (*static_cast<const bool *>(pValue));
		return true;
	}
	else if (strKey == "DeleteRenderQueue")
	{
		mDeleteQueueAfterRendering = (*static_cast<const bool *>(pValue));
		return true;
	}
	// options for viewcells
	else if (strKey == "LoadViewCells")
	{ 
		if (!mViewCellsLoaded)
		{
			String filename(static_cast<const char *>(pValue));
			mViewCellsLoaded = LoadViewCells(filename);	
		}

		return mViewCellsLoaded;
	}
	else if (strKey == "UseViewCells")
	{ 
		if (mViewCellsLoaded)
		{
			mUseViewCells = *static_cast<const bool *>(pValue);

			// reset view cell
			OGRE_DELETE(mCurrentViewCell);

			if (mUseViewCells)
				mCurrentViewCell = mViewCellsManager->GenerateViewCell();

			mElementaryViewCell = NULL;

			// if using view cells, all objects are set to false initially
			SetObjectsVisible(!mUseViewCells);

			return true;
		}
		else
		{
			return false;
		}

	}
	else if (strKey == "UseVisibilityFilter")
	{
		if (mViewCellsLoaded)
		{
			mUseVisibilityFilter = *static_cast<const bool *>(pValue);
			// set null =>recomputation of the pvs
			mElementaryViewCell = NULL;
			return true;
		}
		else
		{
			return false;
		}
	}

	return VisibilityOptionsManager(mVisibilityManager, mHierarchyInterface)
		.setOption(strKey, pValue) || SceneManager::setOption(strKey, pValue);
}

bool KdTreeSceneManager::getOption(const String& strKey, void* pDestValue)
{
	if (strKey == "KdTreeMaxDepth")
	{
		*static_cast<int *>(pDestValue) = mMaxDepth;
		return true;
	}
	else if (strKey == "KT")
	{
		*static_cast<Real *>(pDestValue) = PlaneEvent::KT;
		return true;
	}
	else if (strKey == "KI")
	{
		*static_cast<Real *>(pDestValue) = PlaneEvent::KI;
		return true;
	}
	else if (strKey == "EnhancedVisibility")
	{
		if (mKdTree)
			*static_cast<bool *>(pDestValue) = mKdTree->getEnhancedVis();
		else
			*static_cast<bool *>(pDestValue) = mEnhancedVisiblity;
		return true;
	}
	else if (strKey == "BuildMethod")
	{
		*static_cast<KdTree::BuildMethod *>(pDestValue) = mBuildMethod;
		return true;
	}
	else if (strKey == "RenderMethod")
	{
		*static_cast<KdTree::RenderMethod *>(pDestValue) = mRenderMethod;
		return true;
	}
	else if (strKey == "ShowKdTree")
	{
		*static_cast<bool *>(pDestValue) = mShowBoxes;
		return true;
	}	
	else if (strKey == "HiLiteLevel")
	{
		*static_cast<int *>(pDestValue) = mHiLiteLevel;
		return true;
	}
	else if (strKey == "ShowAllBoxes")
	{
		*static_cast<bool *>(pDestValue) = mShowAllBoxes;
		return true;
	}
	else if (strKey == "ShowNodes")
	{
		*static_cast<bool *>(pDestValue) = mShowNodes;
		return true;
	}
	// vis options
	else if (strKey == "NumFrustumCulledNodes")
	{
		if (mRenderMethod == KdTree::KDRM_INTERNAL)
		{
			unsigned int numnodes = 0;
			if (mKdTree)
				numnodes = mKdTree->getFramesStats().mFrustumCulledNodes;

			* static_cast<unsigned int *>(pDestValue) = (unsigned int)numnodes;
			return true;
		}
		// otherwise let fall through to VisibilityOptionsManager
	}
	else if (strKey == "NumQueryCulledNodes")
	{
		if (mRenderMethod == KdTree::KDRM_INTERNAL)
		{
			* static_cast<unsigned int *>(pDestValue) = 0;
			return true;
		}
		// otherwise let fall through to VisibilityOptionsManager
	}
	else if (strKey == "NumHierarchyNodes")
	{
		unsigned int numnodes = 0;
		if (mKdTree)
			numnodes = mKdTree->getTreeStats().mNumNodes;

		* static_cast<unsigned int *>(pDestValue) = (unsigned int)numnodes;
		return true;
	}
	else if (strKey == "NumRenderedNodes")
	{
		if (mRenderMethod == KdTree::KDRM_INTERNAL)
		{
			unsigned int numnodes = 0;
			if (mKdTree)
				numnodes = mKdTree->getFramesStats().mRenderedNodes;

			* static_cast<unsigned int *>(pDestValue) = (unsigned int)numnodes;
			return true;
		}
		// otherwise let fall through to VisibilityOptionsManager
	}
	else if (strKey == "NumQueriesIssued")
	{
		if (mRenderMethod == KdTree::KDRM_INTERNAL)
		{
			* static_cast<unsigned int *>(pDestValue) = 0;
			return true;
		}
		// otherwise let fall through to VisibilityOptionsManager
	}
	else if (strKey == "NumTraversedNodes")
	{
		if (mRenderMethod == KdTree::KDRM_INTERNAL)
		{
			unsigned int numnodes = 0;
			if (mKdTree)
				numnodes = mKdTree->getFramesStats().mTraversedNodes;

			* static_cast<unsigned int *>(pDestValue) = (unsigned int)numnodes;
			return true;
		}
		// otherwise let fall through to VisibilityOptionsManager
	}
	else if (strKey == "VisibilityManager")
	{
		* static_cast<GtpVisibility::VisibilityManager **>(pDestValue) = 
			(GtpVisibility::VisibilityManager *)mVisibilityManager;
		return true;
	}
	else if (strKey == "HierarchInterface")
	{
		* static_cast<GtpVisibility::HierarchyInterface **>(pDestValue) = 
			(GtpVisibility::HierarchyInterface *)mHierarchyInterface;
		return true;
	}
	// view cell options

	else if (strKey == "UseViewCells")
	{ 
		*static_cast<bool *>(pDestValue) = mUseViewCells;
		return mViewCellsLoaded;
	}
	else if (strKey == "UseVisibilityFilter")
	{
		*static_cast<bool *>(pDestValue) = mUseVisibilityFilter;
		return mViewCellsLoaded;
	}

	return VisibilityOptionsManager(mVisibilityManager, mHierarchyInterface)
		.getOption(strKey, pDestValue) || SceneManager::getOption(strKey, pDestValue);
}

bool KdTreeSceneManager::getOptionKeys(StringVector &refKeys)
{
	refKeys.push_back("Algorithm");
	refKeys.push_back("BuildMethod");
	refKeys.push_back("DelayRenderTransparents");
	refKeys.push_back("DeleteRenderQueue");
	refKeys.push_back("DepthWrite");
	refKeys.push_back("EnhancedVisibility");
	refKeys.push_back("ExecuteVertexProgramForAllPasses");
	refKeys.push_back("HiLiteLevel");
	refKeys.push_back("HierarchInterface");
	refKeys.push_back("KI");
	refKeys.push_back("KT");
	refKeys.push_back("KdTreeMaxDepth");
	refKeys.push_back("LoadViewCells");
	refKeys.push_back("NumHierarchyNodes");
	refKeys.push_back("PrepareVisualization");
	refKeys.push_back("RebuildKdTree");
	refKeys.push_back("RenderMethod");
	refKeys.push_back("RenderNodesContentForViz");
	refKeys.push_back("RenderNodesForViz");
	refKeys.push_back("RenderTransparentsForItemBuffer");
	refKeys.push_back("ShowAllBoxes");
	refKeys.push_back("ShowKdTree");
	refKeys.push_back("ShowNodes");
	refKeys.push_back("SkyBoxEnabled");
	refKeys.push_back("SkyDomeEnabled");
	refKeys.push_back("SkyPlaneEnabled");
	refKeys.push_back("UseDepthPass");
	refKeys.push_back("UseItemBuffer");
	refKeys.push_back("UseViewCells");
	refKeys.push_back("UseVisibilityFilter");
	refKeys.push_back("VisibilityManager");
	refKeys.push_back("VisualizeCulledNodes");
	return VisibilityOptionsManager(mVisibilityManager, mHierarchyInterface)
		.getOptionKeys(refKeys);
}

bool KdTreeSceneManager::getOptionValues(const String & key, StringVector &refValueList)
{
	return SceneManager::getOptionValues(key, refValueList);
}

void KdTreeSceneManager::setVisibilityManager(GtpVisibility::VisibilityManager *visManager)
{
	mVisibilityManager = visManager;
}

GtpVisibility::VisibilityManager * KdTreeSceneManager::getVisibilityManager()
{
	return mVisibilityManager;
}

GtpVisibility::VisibilityManager * KdTreeSceneManager::GetVisibilityManager()
{
	return mVisibilityManager;
}

KdTreeHierarchyInterface * KdTreeSceneManager::GetHierarchyInterface()
{
	return mHierarchyInterface;
}

Camera* KdTreeSceneManager::createCamera(const String& name)
{
	// Check name not used
	if (mCameras.find(name) != mCameras.end())
	{
		OGRE_EXCEPT(
			Exception::ERR_DUPLICATE_ITEM,
			"A camera with the name " + name + " already exists",
			"SceneManager::createCamera" );
	}

	Camera *c = new KdTreeCamera(name, this);
	mCameras.insert(CameraList::value_type(name, c));

	return c;
}

SceneNode* KdTreeSceneManager::createSceneNode(void)
{
	SceneNode* sn = new KdTreeSceneNode(this);
	assert(mSceneNodes.find(sn->getName()) == mSceneNodes.end());
	mSceneNodes[sn->getName()] = sn;
	return sn;
}

SceneNode* KdTreeSceneManager::createSceneNode(const String& name)
{
	// Check name not used
	if (mSceneNodes.find(name) != mSceneNodes.end())
	{
		OGRE_EXCEPT(
			Exception::ERR_DUPLICATE_ITEM,
			"A scene node with the name " + name + " already exists",
			"KdTreeSceneManager::createSceneNode" );
	}

	SceneNode* sn = new KdTreeSceneNode(this, name);
	mSceneNodes[sn->getName()] = sn;
	return sn;
}

Entity * KdTreeSceneManager::createEntity(const String& entityName, const String& meshName)
{
	Entity *ent = SceneManager::createEntity(entityName, meshName);
#ifdef GTP_VISIBILITY_MODIFIED_OGRE
	for (int i = 0; i < (int)ent->getNumSubEntities(); ++i)
	{
		ent->getSubEntity(i)->setId(mCurrentEntityId);
	}

	// increase counter of entity id values
	++ mCurrentEntityId;
#endif
	return ent;
}

// make sure it's called only for non-empty nodes .. avoids one uneccessary funciton call
void KdTreeSceneManager::_updateNode(KdTreeSceneNode *node)
{
	//LogManager::getSingleton().logMessage("### _updateNode called for " + node->getName());

	/* Rebuild kdtree when it was wiped out
		* Usually this happens only before the first frame
		* The initial AABB shall enclose all objects present
		* in the scene at the time of construction
		* TODO: find a more appropriate place for it,
		* e.g., before the first render call
		* teh stupid thing is I can't find any other place so far ...
		*/
	if (!mKdTree)
	{
		mKdTree = new KdTree(mMaxDepth, mBuildMethod);
		mKdTree->build(static_cast<KdTreeSceneNode *>(mSceneRoot));
		mKdTree->setEnhancedVis(mEnhancedVisiblity);
	}

	// if the node is in the tree and _updateNode was called, then the node was moved/rotated/resized/wahtever
	if (node->isAttached())
	{
		// TEST: perfomance when adding & removing for every frame
		//mKdTree->remove(node);
		//mKdTree->insert(node);
	}
	// there's a new node in town ... 
	else
	{			
		// inserting single nodes yields sub-optimal results
		// rebuilding tree takes too long
		// "What now?", spoke Zeus ...

		//mKdTree->insert(node);
		
		//delete mKdTree;
		//mKdTree = new KdTree(mMaxDepth);
		//mKdTree->build(static_cast<KdTreeSceneNode *>(mSceneRoot));
	}

}

void KdTreeSceneManager::_updateSceneGraph(Camera* cam)
{
	mVisibilityManager->GetCullingManager()->SetHierarchyInterface(mHierarchyInterface);
	mHierarchyInterface->SetRenderSystem(mDestRenderSystem);

	SceneManager::_updateSceneGraph(cam);
}

void KdTreeSceneManager::_findVisibleObjects(Camera *cam, bool onlyShadowCasters)
{
	if (mRenderMethod == KdTree::KDRM_INTERNAL)
	{
		getRenderQueue()->clear(mDeleteQueueAfterRendering);
		if (mShowVisualization)
		{
			PrepareVisualization(cam);
		}
		else
		{
			mVisibleNodes.clear();
			if (mKdTree)
			{
				// determine visibility
				mKdTree->queueVisibleObjects(KDCAMPTR_CAST(cam), getRenderQueue(), onlyShadowCasters, mShowBoxes, mVisibleNodes);
				// apply view cell pvs
				updatePvs(cam);
			}
		}
	}
	else
	{
		//-- show visible scene nodes and octree bounding boxes from last frame
		if (mShowVisualization)
		{
			PrepareVisualization(cam);
		}
		else 
		{	
			// for hierarchical culling, we interleave identification 
			// and rendering of objects in _renderVisibibleObjects

			// for the shadow pass we use only standard rendering
			// because of low occlusion
			if (mShadowTechnique == SHADOWTYPE_TEXTURE_MODULATIVE && 
				mIlluminationStage == IRS_RENDER_TO_TEXTURE)
			{
				getRenderQueue()->clear();
				if (mKdTree)
					mKdTree->queueVisibleObjects(KDCAMPTR_CAST(cam), getRenderQueue(), onlyShadowCasters, mShowBoxes, mVisibleNodes);
			}

			// only shadow casters will be rendered in shadow texture pass
			if (0) mHierarchyInterface->SetOnlyShadowCasters(onlyShadowCasters);


			//-- apply view cell pvs -
			updatePvs(cam);
		}
		mVisibleNodes.clear();	
	}
}

void KdTreeSceneManager::_renderVisibleObjects()
{
	if (mRenderMethod == KdTree::KDRM_INTERNAL)
	{
		SceneManager::_renderVisibleObjects();
	}
	else
	{
		InitDepthPass(); 	  // create material for depth pass
		InitItemBufferPass(); // create material for item buffer pass

		// save ambient light to reset later
		ColourValue savedAmbient = mAmbientLight;

		//-- apply standard rendering for some modes (e.g., visualization, shadow pass)

		if (mShowVisualization ||
			(mShadowTechnique == SHADOWTYPE_TEXTURE_MODULATIVE && 
			mIlluminationStage == IRS_RENDER_TO_TEXTURE))
		{	
			IlluminationRenderStage savedStage = mIlluminationStage; 

			if (mShowVisualization) 
			{
				// disable illumination stage to prevent rendering shadows
				mIlluminationStage = IRS_NONE;
			}

			// standard rendering for shadow maps because of performance
			SceneManager::_renderVisibleObjects();

			mIlluminationStage = savedStage;
		}
		else //-- the hierarchical culling algorithm
		{
			// this is also called in TerrainSceneManager: really necessary?
			//mDestRenderSystem -> setLightingEnabled(false);

			// don't render backgrounds for item buffer
			if (mUseItemBuffer)
			{
				clearSpecialCaseRenderQueues();
				getRenderQueue()->clear();
			}

			//-- hierarchical culling

			// the objects of different layers (e.g., background, scene, 
			// overlay) must be identified and rendered one after another

			//-- render all early skies
			clearSpecialCaseRenderQueues();
			addSpecialCaseRenderQueue(RENDER_QUEUE_BACKGROUND);
			addSpecialCaseRenderQueue(RENDER_QUEUE_SKIES_EARLY);
			setSpecialCaseRenderQueueMode(SceneManager::SCRQM_INCLUDE);

			SceneManager::_renderVisibleObjects();

#ifdef GTP_VISIBILITY_MODIFIED_OGRE
			// delete previously rendered content
			_deleteRenderedQueueGroups();
#endif

			//-- prepare queue for visible objects (i.e., all but overlay and skies late)
			clearSpecialCaseRenderQueues();
			addSpecialCaseRenderQueue(RENDER_QUEUE_SKIES_LATE);
			addSpecialCaseRenderQueue(RENDER_QUEUE_OVERLAY);

			// exclude this queues from hierarchical rendering
			setSpecialCaseRenderQueueMode(SceneManager::SCRQM_EXCLUDE);


			// set all necessary parameters for 
			// hierarchical visibility culling and rendering
			InitVisibilityCulling(mCameraInProgress);


			/** 
			* the hierarchical culling algorithm
			* for depth pass: we just find objects and update depth buffer
			* for "delayed" rendering: we render some passes afterwards
			* e.g., transparents, because they need front-to-back sorting
			**/

			mVisibilityManager->ApplyVisibilityCulling();

			// delete remaining renderables from queue:
			// all which are not in mLeavePassesInQueue
#ifdef GTP_VISIBILITY_MODIFIED_OGRE
			_deleteRenderedQueueGroups(mLeavePassesInQueue);
#endif

			//-- reset parameters
			mIsDepthPassPhase = false;
			mIsItemBufferPhase = false;
			mSkipTransparents = false;
			mIsHierarchicalCulling = false;

			mLeavePassesInQueue = 0;

			// add visible nodes found by the visibility culling algorithm
			if (mUseDepthPass)
			{
				KdTree::NodeList::const_iterator it, end = mVisibleNodes.end();
				for (it = mVisibleNodes.begin(); it != end; it++)
				{
					(*it)->queueVisibleObjects(mHierarchyInterface->GetFrameId(), mCameraInProgress,
						getRenderQueue(), false, mShowBoxes);
				}
			}

			//-- now we can render all remaining queue objects
			//-- used for depth pass, transparents, overlay
			clearSpecialCaseRenderQueues();

			SceneManager::_renderVisibleObjects();
		} // hierarchical culling


		// reset ambient light
		setAmbientLight(savedAmbient);


		// almost same effect as below
		getRenderQueue()->clear(mDeleteQueueAfterRendering);

		//if (!mDeleteQueueAfterRendering)
		//	getRenderQueue()->clear(true); // finally clear render queue
		//else
		//	OGRE_DELETE(mRenderQueue); // HACK: should rather only be cleared ...

		if (0) WriteLog(); // write out stats
	}
}


void KdTreeSceneManager::_renderNode(KdTree::NodePtr node, Camera * cam, 
									 bool onlyShadowCasters, int leavePassesInQueue)
{
	RenderQueueGroup *currentGroup = 
		getRenderQueue()->getQueueGroup(getRenderQueue()->getDefaultQueueGroup());
	currentGroup->clear(leavePassesInQueue);

	node->queueVisibleObjects(mHierarchyInterface->GetFrameId(), cam, getRenderQueue(),
		onlyShadowCasters, mShowBoxes);
	mVisibleNodes.push_back(node);

	_renderQueueGroupObjects(currentGroup, QueuedRenderableCollection::OM_PASS_GROUP);
}

//-----------------------------------------------------------------------
const Pass *KdTreeSceneManager::_setPass(const Pass* pass, bool evenIfSuppressed)
{
	if (mRenderMethod == KdTree::KDRM_INTERNAL)
	{
		return SceneManager::_setPass(pass);
	}

	// TODO: setting vertex program is not efficient
	//Pass *usedPass = ((mIsDepthPassPhase && !pass->hasVertexProgram()) ? mDepthPass : pass); 

	// set depth fill pass if we currently do not make an aabb occlusion query
	const bool useDepthPass = 
		(mIsDepthPassPhase && !mHierarchyInterface->IsBoundingBoxQuery());

	const IlluminationRenderStage savedStage = mIlluminationStage; 

	// set illumination stage to NONE so no shadow material is used 
	// for depth pass or for occlusion query
	if (mIsDepthPassPhase || mHierarchyInterface->IsBoundingBoxQuery())
	{
		mIlluminationStage = IRS_NONE;
	}

	// --- set vertex program of current pass in order to set correct depth
	if (mExecuteVertexProgramForAllPasses && 
		mIsDepthPassPhase && 
		pass->hasVertexProgram())
	{
		// add vertex program of current pass to depth pass
		mDepthPass->setVertexProgram(pass->getVertexProgramName());

		if (mDepthPass->hasVertexProgram())
		{
			const GpuProgramPtr& prg = mDepthPass->getVertexProgram();
			// Load this program if not done already
			if (!prg->isLoaded())
				prg->load();
			// Copy params
			mDepthPass->setVertexProgramParameters(pass->getVertexProgramParameters());
		}
	}
	else if (mDepthPass->hasVertexProgram()) // reset vertex program
	{
		mDepthPass->setVertexProgram("");
	}

	const Pass *usedPass = useDepthPass ? mDepthPass : pass;

	// save old depth write: needed for item buffer
	const bool IsDepthWrite = usedPass->getDepthWriteEnabled();

	// global option which enables / disables depth writes
	if (!mEnableDepthWrite)
	{
		//	usedPass->setDepthWriteEnabled(false);
	}
	//else if (mIsItemBufferPass) {usedPass = mItemBufferPass;}


	//-- set actual pass here
	const Pass *result = SceneManager::_setPass(usedPass);


	// reset depth write
	if (!mEnableDepthWrite)
	{
		//	usedPass->setDepthWriteEnabled(IsDepthWrite);
	}

	// reset illumination stage
	mIlluminationStage = savedStage;

	return result;
}
//-----------------------------------------------------------------------
void KdTreeSceneManager::renderBasicQueueGroupObjects(RenderQueueGroup* pGroup,
													  QueuedRenderableCollection::OrganisationMode om)
{
	// Basic render loop
	// Iterate through priorities
	RenderQueueGroup::PriorityMapIterator groupIt = pGroup->getIterator();

	while (groupIt.hasMoreElements())
	{
		RenderPriorityGroup* pPriorityGrp = groupIt.getNext();

		// Sort the queue first
		pPriorityGrp->sort(mCameraInProgress);

		// Do solids
		renderObjects(pPriorityGrp->getSolidsBasic(), om, true);

		// for correct rendering, transparents must be rendered after hierarchical culling
		// => do nothing

		// Do transparents (always descending)
		if (mRenderMethod == KdTree::KDRM_INTERNAL || !mSkipTransparents)
		{
			renderObjects(pPriorityGrp->getTransparents(), 
				QueuedRenderableCollection::OM_SORT_DESCENDING, true);
		}


	}// for each priority
}
//-----------------------------------------------------------------------
bool KdTreeSceneManager::validatePassForRendering(Pass* pass)
{
	if (mRenderMethod == KdTree::KDRM_INTERNAL)
	{
		return SceneManager::validatePassForRendering(pass);
	}

	// skip all but first pass if we are doing the depth pass
	if ((mIsDepthPassPhase || mIsItemBufferPhase) && (pass->getIndex() > 0))
	{
		return false;
	}
	// all but first pass
	/*else if ((!mIsDepthPassPhase || mIsItemBufferPhase) && (pass->getIndex() != 0))
	{
	return false;
	}*/

	return SceneManager::validatePassForRendering(pass);
}
//-----------------------------------------------------------------------
void KdTreeSceneManager::_renderQueueGroupObjects(RenderQueueGroup* pGroup, 
												  QueuedRenderableCollection::OrganisationMode om)
{
	if (mRenderMethod == KdTree::KDRM_INTERNAL || !mIsItemBufferPhase)
	{
		SceneManager::_renderQueueGroupObjects(pGroup, om);
		return;
	}
#ifdef  ITEM_BUFFER
	//-- item buffer
	//-- item buffer: render objects using false colors

	// Iterate through priorities
	RenderQueueGroup::PriorityMapIterator groupIt = pGroup->getIterator();

	while (groupIt.hasMoreElements())
	{
		RenderItemBuffer(groupIt.getNext());
	}
#endif // ITEM_BUFFER
}
//-----------------------------------------------------------------------
void KdTreeSceneManager::renderAdditiveStencilShadowedQueueGroupObjects(
	RenderQueueGroup* pGroup, QueuedRenderableCollection::OrganisationMode om)
{
	// only render solid passes during hierarchical culling
	if (mIsHierarchicalCulling)
	{
		RenderQueueGroup::PriorityMapIterator groupIt = pGroup->getIterator();
		LightList lightList;

		while (groupIt.hasMoreElements())
		{
			RenderPriorityGroup* pPriorityGrp = groupIt.getNext();

			// Sort the queue first
			pPriorityGrp->sort(mCameraInProgress);

			// Clear light list
			lightList.clear();

			// Render all the ambient passes first, no light iteration, no lights
			/*** msz: no more IRS_AMBIENT, see OgreSceneManager.h ***/
			// mIlluminationStage = IRS_AMBIENT;

			SceneManager::renderObjects(pPriorityGrp->getSolidsBasic(), om, false, &lightList);
			// Also render any objects which have receive shadows disabled
			SceneManager::renderObjects(pPriorityGrp->getSolidsNoShadowReceive(), om, true);
		}
	}
	else // render the rest of the passes
	{
		SceneManager::renderAdditiveStencilShadowedQueueGroupObjects(pGroup, om);
	}
}
//-----------------------------------------------------------------------
void KdTreeSceneManager::renderModulativeStencilShadowedQueueGroupObjects(
	RenderQueueGroup* pGroup, QueuedRenderableCollection::OrganisationMode om)
{
	if (mIsHierarchicalCulling)
	{
		// Iterate through priorities
		RenderQueueGroup::PriorityMapIterator groupIt = pGroup->getIterator();

		while (groupIt.hasMoreElements())
		{
			RenderPriorityGroup* pPriorityGrp = groupIt.getNext();

			// Sort the queue first
			pPriorityGrp->sort(mCameraInProgress);

			// Do (shadowable) solids
			SceneManager::renderObjects(pPriorityGrp->getSolidsBasic(), om, true);
		}
	}
	else
	{
		SceneManager::renderModulativeStencilShadowedQueueGroupObjects(pGroup, om);
	}
}
//-----------------------------------------------------------------------
void KdTreeSceneManager::InitDepthPass()
{
	MaterialPtr depthMat = MaterialManager::getSingleton().getByName("Visibility/DepthPass");

	if (depthMat.isNull())
	{
		depthMat = MaterialManager::getSingleton().create(
			"Visibility/DepthPass",
			ResourceGroupManager::DEFAULT_RESOURCE_GROUP_NAME);

		mDepthPass = depthMat->getTechnique(0)->getPass(0);
		mDepthPass->setColourWriteEnabled(false);
		mDepthPass->setDepthWriteEnabled(true);
		mDepthPass->setLightingEnabled(false);
	}
	else
	{
		mDepthPass = depthMat->getTechnique(0)->getPass(0);
	}
}
//-----------------------------------------------------------------------
void KdTreeSceneManager::InitItemBufferPass()
{
	MaterialPtr itemBufferMat = MaterialManager::getSingleton().
		getByName("Visibility/ItemBufferPass");

	if (itemBufferMat.isNull())
	{
		// Init
		itemBufferMat = MaterialManager::getSingleton().create("Visibility/ItemBufferPass",
			ResourceGroupManager::DEFAULT_RESOURCE_GROUP_NAME);

		mItemBufferPass = itemBufferMat->getTechnique(0)->getPass(0);
		mItemBufferPass->setColourWriteEnabled(true);
		mItemBufferPass->setDepthWriteEnabled(true);
		mItemBufferPass->setLightingEnabled(true);
		//mItemBufferPass->setLightingEnabled(false);
	}
	else
	{
		mItemBufferPass = itemBufferMat->getTechnique(0)->getPass(0);
	}
	//mItemBufferPass->setAmbient(1, 1, 0);
}
//-----------------------------------------------------------------------
void KdTreeSceneManager::PrepareVisualization(Camera *cam)
{
	// add player camera for visualization purpose
	try 
	{
		Camera *c;
		if ((c = getCamera("PlayerCam")) != NULL)
		{
			getRenderQueue()->addRenderable(c);
		}   
	}
	catch (...)
	{
		// ignore
	}

	if (mRenderNodesForViz || mRenderNodesContentForViz)
	{
		RenderQueue * queue = getRenderQueue();
		unsigned long frameid = 0;

		if (mRenderMethod == KdTree::KDRM_INTERNAL)
			frameid = Root::getSingleton().getCurrentFrameNumber();
		else
			frameid = mHierarchyInterface->GetFrameId();

		for (KdTree::NodeList::iterator it = mVisibleNodes.begin(); it != mVisibleNodes.end(); ++it)
		{
			if (mRenderNodesForViz && (*it)->isLeaf())
			{
				WireBoundingBox * wirebox = (*it)->getWireBoundingBox();
				wirebox->setMaterial("KdTree/BoxViz");
				getRenderQueue()->addRenderable(wirebox);
			}
			// add renderables itself
			if (mRenderNodesContentForViz) 
			{
				(*it)->queueVisibleObjects(frameid, cam, queue, false, false);
			}
		}
	}	
}
//-----------------------------------------------------------------------
void KdTreeSceneManager::InitVisibilityCulling(Camera *cam)
{
	// reset culling manager stats
	mVisibilityManager->GetCullingManager()->InitFrame(mVisualizeCulledNodes);

	// set depth pass flag before rendering
	mIsDepthPassPhase = mUseDepthPass;

	mIsHierarchicalCulling = true; // during hierarchical culling

	// item buffer needs full ambient lighting to use item colors as unique id
	if (mUseItemBuffer) 
	{
		mIsItemBufferPhase = true;
		setAmbientLight(ColourValue(1,1,1,1));
	}


	// set passes which are stored in render queue 
	// for rendering AFTER hierarchical culling, i.e., passes which need 
	// a special rendering order

	mLeavePassesInQueue = 0;

	// if we have the depth pass or use an item buffer, no passes are left in the queue
	if (1 && !mUseDepthPass && !mUseItemBuffer)
	{
		if (mShadowTechnique == SHADOWTYPE_STENCIL_ADDITIVE)
		{
			// TODO: remove this pass because it should be processed during hierarchical culling
			//mLeavePassesInQueue |= RenderPriorityGroup::SOLID_PASSES_NOSHADOW;

			mLeavePassesInQueue |= RenderPriorityGroup::SOLID_PASSES_DECAL;
			mLeavePassesInQueue |= RenderPriorityGroup::SOLID_PASSES_DIFFUSE_SPECULAR;
			mLeavePassesInQueue |= RenderPriorityGroup::TRANSPARENT_PASSES;

			// just render ambient passes
			/*** msz: no more IRS_AMBIENT, see OgreSceneManager.h ***/
			// mIlluminationStage = IRS_AMBIENT; 
			//getRenderQueue()->setSplitPassesByLightingType(true);
		}

		if (mShadowTechnique == SHADOWTYPE_STENCIL_MODULATIVE)
		{
			mLeavePassesInQueue |= RenderPriorityGroup::SOLID_PASSES_NOSHADOW;
			mLeavePassesInQueue |= RenderPriorityGroup::TRANSPARENT_PASSES;
		}

		// transparents should be rendered after hierarchical culling to 
		// provide front-to-back ordering
		if (mDelayRenderTransparents)
		{
			mLeavePassesInQueue |= RenderPriorityGroup::TRANSPARENT_PASSES;
		}
	}

	// skip rendering transparents during the hierarchical culling
	// (because they will be rendered afterwards)
	mSkipTransparents = 
		(mIsDepthPassPhase || (mLeavePassesInQueue & RenderPriorityGroup::TRANSPARENT_PASSES));

	// -- initialise interface for rendering traversal of the hierarchy
	mHierarchyInterface->SetHierarchyRoot(mKdTree->getRoot());

	// possible two cameras (one for culling, one for rendering)
	mHierarchyInterface->InitTraversal(mCameraInProgress, 
		/*mCullCamera ? getCamera("CullCamera") : */NULL,
		mLeavePassesInQueue);

}

//-------------------------------------------------------------------------
void KdTreeSceneManager::SetObjectsVisible(const bool visible)
{
	GtpVisibilityPreprocessor::ObjectContainer::iterator it, it_end = mObjects.end();

	for (it = mObjects.begin(); it != it_end; ++ it)
	{
		OgreMeshInstance *omi = static_cast<OgreMeshInstance *>(*it);
		Entity *ent = omi->GetEntity();

		ent->setVisible(visible);
	}
}
//-----------------------------------------------------------------------
bool KdTreeSceneManager::LoadViewCells(const String &filename)
{
	// objects are set to invisible initially
	SetObjectsVisible(false);

	const string bboxesFilename = mVisibilityManager->GetVisibilityEnvironment()->getViewCellsFileName();

	// converter between view cell ids and Ogre entites 
	GtpVisibilityPreprocessor::IndexedBoundingBoxContainer iboxes;
	KdTreeBoundingBoxConverter bconverter(this);

	// load the view cells assigning the found objects to the pvss
	mViewCellsManager = 
		GtpVisibilityPreprocessor::ViewCellsManager::
			LoadViewCells(filename, mObjects, false, &bconverter);

	return (mViewCellsManager != NULL);
}
//-------------------------------------------------------------------------
void KdTreeSceneManager::applyViewCellPvs(GtpVisibilityPreprocessor::ViewCell *vc, 
													const bool load)
{	
	if (!vc) 
	{	
		// set everything visible for savety

		// NOTE: should not happen, rather apply view cell 
		// representing unbounded space then
		SetObjectsVisible(true);

		return;
	}

	//////////
	//-- set PVS of view cell visible

	GtpVisibilityPreprocessor::ObjectPvsIterator pit = vc->GetPvs().GetIterator();

	while (pit.HasMoreEntries())
	{		
		GtpVisibilityPreprocessor::Intersectable *entry = pit.Next();

		if (entry)
		{
			OgreMeshInstance *omi = static_cast<OgreMeshInstance *>(entry);
			omi->GetEntity()->setVisible(load);
		}
	}
}
//-------------------------------------------------------------------------
void KdTreeSceneManager::updatePvs(Camera *cam)
{
	if (!(mViewCellsLoaded && mUseViewCells))
		return;

	const GtpVisibilityPreprocessor::Vector3 viewPoint = 
		OgreTypeConverter::ConvertFromOgre(cam->getDerivedPosition());

	GtpVisibilityPreprocessor::ViewCell *newElementary = 
		mViewCellsManager->GetViewCell(viewPoint);

	// elementary view cell did not change => apply same pvs
	if (mElementaryViewCell == newElementary)
		return;

	mElementaryViewCell = newElementary;
	//LogManager::getSingleton().logMessage("unloading");
	//-- unload old pvs
	applyViewCellPvs(mCurrentViewCell, false);


	//-- the new view cell

	GtpVisibilityPreprocessor::ViewCell *viewCell;


	if (mUseVisibilityFilter)
	{
		//-- compute new filtered cell
		GtpVisibilityPreprocessor::PrVs prvs;
		mViewCellsManager->GetPrVS(viewPoint, prvs, 5);
		viewCell = prvs.mViewCell;
	}
	else
	{
		viewCell = newElementary;
	}
	//LogManager::getSingleton().logMessage("loading");
	//-- load new pvs
	applyViewCellPvs(viewCell, true);

	// store pvs
	mCurrentViewCell->SetPvs(viewCell->GetPvs());

	// delete merge tree of filtered view cell
	if (mUseVisibilityFilter)
		mViewCellsManager->DeleteLocalMergeTree(viewCell);
}

//-----------------------------------------------------------------------
void KdTreeSceneManager::WriteLog()
{
	std::stringstream d;

	d << "Depth pass: " << StringConverter::toString(mUseDepthPass) << ", "
		<< "Delay transparents: " << StringConverter::toString(mDelayRenderTransparents) << ", "
		<< "Use optimization: " << StringConverter::toString(mHierarchyInterface->GetTestGeometryForVisibleLeaves()) << ", "
		<< "Algorithm type: " << mVisibilityManager->GetCullingManagerType() << ", "
		<< "Hierarchy nodes: " << (mKdTree ? mKdTree->getTreeStats().mNumNodes : 0) << ", " 
		<< "Traversed nodes: " << mHierarchyInterface->GetNumTraversedNodes() << ", "
		<< "Rendered nodes: " << mHierarchyInterface->GetNumRenderedNodes() << ", "
		<< "Query culled nodes: " << mVisibilityManager->GetCullingManager()->GetNumQueryCulledNodes() << ", "
		<< "Frustum culled nodes: " << mVisibilityManager->GetCullingManager()->GetNumFrustumCulledNodes() << ", "
		<< "Queries issued: " << mVisibilityManager->GetCullingManager()->GetNumQueriesIssued() << ", "
		<< "Found objects: " << (int)mVisibleNodes.size() << "\n"
		;

	LogManager::getSingleton().logMessage(d.str());
}

/************************************************************************/
/* Factory for KdTreeSceneManager                                       */
/************************************************************************/
//-----------------------------------------------------------------------
//-----------------------------------------------------------------------
const String KdTreeSceneManagerFactory::FACTORY_TYPE_NAME = "KdTreeSceneManager";
//-----------------------------------------------------------------------
void KdTreeSceneManagerFactory::initMetaData(void) const
{
	mMetaData.typeName = FACTORY_TYPE_NAME;
	mMetaData.description = "Scene manager that organises the scene based on a kd-tree";
	mMetaData.sceneTypeMask = 0xFFFF; // support all types of scenes (hopefully)
	mMetaData.worldGeometrySupported = false;
}
//-----------------------------------------------------------------------
SceneManager* KdTreeSceneManagerFactory::createInstance(
	const String& instanceName)
{
	return new KdTreeSceneManager(instanceName, visManager);
}
//-----------------------------------------------------------------------
void KdTreeSceneManagerFactory::destroyInstance(SceneManager* instance)
{
	delete instance;
}

} // namespace Ogre