Index: GTP/trunk/Lib/Vis/OnlineCullingCHC/OGRE/include/OgreKdTree.h
===================================================================
--- GTP/trunk/Lib/Vis/OnlineCullingCHC/OGRE/include/OgreKdTree.h	(revision 1163)
+++ GTP/trunk/Lib/Vis/OnlineCullingCHC/OGRE/include/OgreKdTree.h	(revision 1163)
@@ -0,0 +1,414 @@
+/*
+-----------------------------------------------------------------------------
+This source file is part of the GameTools Project
+http://www.gametools.org
+
+Author: Martin Szydlowski
+-----------------------------------------------------------------------------
+*/
+
+#ifndef _OgreKdTree_H__
+#define _OgreKdTree_H__
+
+#include <OgreAxisAlignedBox.h>
+#include <OgreWireBoundingBox.h>
+#include <OgrePlane.h>
+#include <OgreVector3.h>
+
+#include <OgreRoot.h>
+
+#include <stack>
+
+namespace Ogre
+{
+	class KdRenderable;
+	struct SplitInfo;
+
+	class PlaneEvent
+	{
+	public:
+		enum Type
+		{
+			PET_END,
+			PET_ON,
+			PET_START
+		};
+
+		enum Dimension
+		{
+			PED_X,
+			PED_Y,
+			PED_Z
+		};
+
+		enum Side
+		{
+			PES_LEFT = 0x01,
+			PES_RIGHT = 0x02,
+			PES_BOTH = PES_LEFT | PES_RIGHT
+		};
+
+		PlaneEvent(): mRenderable(0), mPosition(Vector3()), mDimension(PED_X), mType(PET_ON)
+		{ };
+
+		PlaneEvent(KdRenderable *rend, const Vector3& pos, PlaneEvent::Dimension dim, PlaneEvent::Type type):
+			mRenderable(rend), mPosition(pos), mDimension(dim), mType(type) 
+		{ };
+
+		~PlaneEvent() {};
+
+		// the less operator for plane events
+		// first sort by position, then by dimension and finally by type
+		bool operator < (const PlaneEvent& e) const
+		{
+			if(mPosition[mDimension] < e.mPosition[e.mDimension])
+			{
+				return true;
+			}
+
+			if(mPosition[mDimension] == e.mPosition[e.mDimension])
+			{
+				if (mDimension < e.mDimension)
+				{
+					return true;
+				}
+				if (mDimension == e.mDimension)
+				{
+					if (mType < e.mType)
+					{
+						return true;
+					}
+				}
+			}
+
+			return false;
+		};
+
+		// the equals operator for tree events
+		bool operator == (const PlaneEvent& e) const
+		{
+			return	(mPosition[mDimension] == e.mPosition[e.mDimension]) &&
+				(mDimension == e.mDimension) &&
+				(mType == e.mType);
+		};
+
+		bool equalsType(const PlaneEvent& e, PlaneEvent::Type t)
+		{
+			return	(mPosition[mDimension] == e.mPosition[e.mDimension]) &&
+				(mDimension == e.mDimension) &&
+				(mType == t);
+		};
+
+		void classify(const PlaneEvent& e, PlaneEvent::Side side);
+
+		PlaneEvent clip(AxisAlignedBox& box, PlaneEvent::Dimension dim);
+
+		Plane * getSplitPlane() const
+		{
+			Vector3 normal(0,0,0);
+			normal[mDimension] = 1;
+			return new Plane(normal, mPosition);
+		}
+
+		KdRenderable * getRenderable() const //??
+		{
+			return mRenderable;
+		};
+
+		PlaneEvent::Dimension getDimension() const //??
+		{
+			return mDimension;
+		};
+
+		// DEBUG
+		String print();
+	protected:
+		// event info
+		KdRenderable *			mRenderable;
+		Vector3					mPosition;
+		PlaneEvent::Dimension	mDimension;
+		PlaneEvent::Type		mType;
+
+		// ------------------------------------------------------------------------------//
+		// functions to determine the cost of splitting the node parent with the plane
+		// represented by this event
+		// TODO discuss if these functions really belong here, OO & SE - wise
+		// pros: convenient, don't have to pass internal data to the outside
+		// cons: SplitInfo ... 
+	public:
+		// compute "global" surface area heuristic (SAH) for the plane represented by this event
+		// use only with priority queue build method
+		void pqSAH(Real globalSA, Real parentSA, int nLeft, int nPlane, int nRight, AxisAlignedBox& parentBox, SplitInfo& split);
+		static Real pqSplitCost(Real p, Real pl, Real pr, int nLeft, int nRight, Real mu);
+
+		// compute the surface area heuristic (SAH) for the plane represented by this event
+		void SAH(const AxisAlignedBox& parent, int nLeft, int nPlane, int nRight, SplitInfo& split);
+		// the variables determining the cost of a branch traversal (KT) and a leaf intersection (KI)
+		static Real KT;
+		static Real KI;
+		// helper functions
+		static Real splitCost(Real pl, Real pr, int nLeft, int nRight);
+		static Real splitCost(Real pl, Real pr, int nLeft, int nRight, Real mu);
+		static Real surfaceArea(const AxisAlignedBox& box);
+		static Real lookupPenalty(Real p);
+	protected:
+		Real splitBox(const AxisAlignedBox& parent, AxisAlignedBox& left, AxisAlignedBox& right);
+	};
+
+	// Holds all the important information on a split
+	struct SplitInfo
+	{
+		AxisAlignedBox bleft;
+		AxisAlignedBox bright;
+		int nleft;
+		int nright;
+		Real cost;
+		PlaneEvent::Side side;
+		PlaneEvent event;
+
+		// DEBUG
+		String print();
+	};
+
+	typedef std::list<PlaneEvent> PlaneEventList;
+	typedef std::list<KdRenderable *> KdRenderableList;
+	
+	class KdTree
+	{
+	protected:
+		class Branch;
+		class Leaf;
+
+		class Node
+		{
+		public:
+			Node(int level, AxisAlignedBox& aabb, Branch * parent):
+			mLevel(level),
+			mAABB(aabb),
+			mParent(parent),
+			mWBB(0)
+			{ };
+
+			virtual ~Node()
+			{
+				delete mWBB;
+			};
+
+			virtual bool isLeaf() const = 0;
+			virtual bool isEmpty() const = 0;
+			
+			// consider using typesafe callback functions
+			//virtual void cbInsert(KdTree * caller, KdRenderable * rend) = 0;
+
+			WireBoundingBox * getWireBoundingBox()
+			{
+				if (mWBB == 0)
+					mWBB = new WireBoundingBox();
+
+				mWBB->setupBoundingBox(mAABB);
+				
+#ifdef KDTREE_DEBUG
+				int level = -1;
+				bool boxes = false;
+				if (Root::getSingleton()._getCurrentSceneManager()->getOption("HighlightLevel",&level))
+				{
+					if (mLevel == level)
+					{
+						//mWBB->setMaterial("BaseGreenNoLighting");
+						mWBB->setMaterial("aabbHiLite");
+						return mWBB;
+					}
+					else
+					{
+						mWBB->setMaterial("BaseWhiteNoLighting");
+						if (Root::getSingleton()._getCurrentSceneManager()->getOption("ShowAllBoxes", &boxes))
+						{
+							if (boxes)
+								return mWBB;
+							else
+								return 0;
+						}
+					}
+				}
+#else
+				mWBB->setMaterial("BaseWhiteNoLighting");
+#endif // KDTREE_DEBUG
+				return mWBB;
+
+			}
+
+			Branch * mParent;
+			int mLevel;
+			AxisAlignedBox mAABB;
+		protected:
+			WireBoundingBox * mWBB;
+		};
+
+		class Branch : public Node
+		{
+		public:
+			Branch(int level, AxisAlignedBox& aabb, Branch * parent, Plane * splitplane, PlaneEvent::Side side):
+				Node(level, aabb, parent), 
+				mSplitPlane(splitplane), 
+				mLeft(0), 
+				mRight(0),
+				mPlaneSide(side)
+			{ };
+
+			virtual ~Branch()
+			{
+				delete mLeft;
+				delete mRight;
+				delete mSplitPlane;
+			};
+
+			virtual bool isLeaf() const { return false; };
+
+			virtual bool isEmpty() const { return (mLeft == 0 && mRight == 0); }
+			
+			Node * mLeft;
+			Node * mRight;
+			Plane  * mSplitPlane;
+			PlaneEvent::Side mPlaneSide;
+		};
+
+		class Leaf : public Node
+		{
+		public:
+			Leaf(int level, AxisAlignedBox& aabb, Branch * parent):
+			  Node(level, aabb, parent) 
+			{};
+
+			virtual ~Leaf();
+
+			virtual bool isLeaf() const { return true; };
+
+			virtual bool isEmpty() const { return mKdRenderables.empty(); };
+
+			virtual void remove(KdRenderable * rend)
+			{
+				mKdRenderables.remove(rend);
+				//mKdRenderables.erase(find(mKdRenderables.begin(), mKdRenderables.end(), rend));
+			};
+
+			virtual void insert(KdRenderable * rend)
+			{
+				mKdRenderables.push_back(rend);
+			};
+
+			KdRenderableList mKdRenderables;
+		};
+
+		struct SplitCandidate
+		{
+			SplitCandidate(PlaneEventList * e, int n, AxisAlignedBox& a, KdTree::Branch * p, Real c, Real d, SplitInfo * b, PlaneEvent::Side s):
+				events(e), nObjects(n), aabb(a), parent(p), cost(c), decrease(d), best(b), side(s) { };
+
+			bool operator < (const SplitCandidate& rhs) const
+			{
+				return decrease < rhs.decrease;
+			};
+
+			void operator = (const SplitCandidate& rhs)
+			{
+				decrease = rhs.decrease;
+				cost = rhs.cost;
+				nObjects = rhs.nObjects;
+				side = rhs.side;
+				aabb = rhs.aabb;
+				events = rhs.events;
+				parent = rhs.parent;
+				best = rhs.best;
+			};
+
+			// DEBUG
+			String print();
+
+			Real decrease;
+			Real cost;
+			int nObjects;
+			PlaneEvent::Side side;
+			AxisAlignedBox aabb;
+			PlaneEventList * events;
+			KdTree::Branch * parent;
+			SplitInfo * best;
+		};
+
+		//typedef std::stack<SplitCandidate> SplitCandidatePQ;
+		typedef std::priority_queue<SplitCandidate> SplitCandidatePQ;
+
+	public:
+		typedef KdTree::Leaf * LeafPtr;
+		typedef std::set<LeafPtr> LeafSet;
+
+		enum BuildMethod
+		{
+			KDBM_RECURSIVE,
+			KDBM_PRIORITYQUEUE
+		};
+		
+		KdTree(int maxdepth);
+		virtual ~KdTree();
+
+		// DEBUG
+		void KdTree::dump();
+		void KdTree::calcCost();
+
+		// insert a new scene node into an existing kd-tree
+		void insert(KdRenderable * rend);
+		// remove a scene node from the tree
+		void remove(KdRenderable * rend);
+		// function to initialize a kd-tree based on the contents of the scene
+		void build(KdRenderable * sceneRoot);
+
+		// test visibility of objects and add to render	queue
+		void queueVisibleObjects(Camera* cam, RenderQueue* queue, bool onlyShadowCasters, bool showBoxes = false);
+
+		// self-explanatory ...
+		int getMaxDepth() { return mMaxDepth; };
+		AxisAlignedBox getBox() { if (mKdRoot) return mKdRoot->mAABB; else return AxisAlignedBox(); };
+		void setBuildMethod(BuildMethod bm) { mBuildMethod = bm; }
+	protected:
+		// recursive insert funciton
+		void recInsert(KdTree::Node * node, KdRenderable * rend);
+		// helper functions for insert
+		void recInsertNew(KdTree::Branch * parent, PlaneEvent::Side side, KdRenderable * rend);
+		void splitBox(const KdTree::Branch& parent, AxisAlignedBox& left, AxisAlignedBox& right);
+		void rebuildSubtree(KdTree::Node * node, KdRenderable * rend);
+		// build scene from a list of nodes rather than a hierarchy
+		KdTree::Node * buildFromList(KdRenderableList& nodelist, KdTree::Branch * parent, AxisAlignedBox& aabb);
+		void addRendToList(KdTree::Node * node, KdRenderableList& nodelist);
+
+		// recursively delete empty nodes
+		void recDelete(KdTree::Node * node);
+
+		// find the best plane for node division
+		SplitInfo * pqFindPlane(PlaneEventList * events, int nObjects, AxisAlignedBox& aabb, Real globalSA);
+
+		// priority queue based build function
+		KdTree::Node * pqBuild(PlaneEventList& events, int nObjects, AxisAlignedBox& aabb, KdTree::Branch * parent);
+		// recursive build function
+		KdTree::Node * recBuild(PlaneEventList& events, int nObjects, AxisAlignedBox& aabb, KdTree::Branch * parent);
+
+		// recursive rendering function
+		void recQueueVisibleObjects(KdTree::Node * node, unsigned long currentFrame, Camera* cam, RenderQueue* queue, bool onlyShadowCasters, bool showBoxes);
+
+		// the root node of the kdtree
+		KdTree::Node * mKdRoot;
+		// Maximum depth of the tree
+		int mMaxDepth;
+
+		// how to build the tree
+		BuildMethod mBuildMethod;
+
+		// logfile for tree creation
+		Log * mBuildLog;
+
+		// DEBUG
+		void KdTree::dump(KdTree::Node * node);
+		Real KdTree::calcCost(KdTree::Node * node, Real vs);
+	}; // class KdTree
+
+} // namespace Ogre
+
+#endif // _OgreKdTree_H__
Index: GTP/trunk/Lib/Vis/OnlineCullingCHC/OGRE/include/OgreKdRenderable.h
===================================================================
--- GTP/trunk/Lib/Vis/OnlineCullingCHC/OGRE/include/OgreKdRenderable.h	(revision 1163)
+++ GTP/trunk/Lib/Vis/OnlineCullingCHC/OGRE/include/OgreKdRenderable.h	(revision 1163)
@@ -0,0 +1,125 @@
+/*
+-----------------------------------------------------------------------------
+This source file is part of the GameTools Project
+http://www.gametools.org
+
+Author: Martin Szydlowski
+-----------------------------------------------------------------------------
+*/
+
+#ifndef _OgreKdRenderable_H__
+#define _OgreKdRenderable_H__
+
+#include "OgreKdTree.h"
+
+namespace Ogre
+{
+
+	// interface which must be implemented by all objects which desire to be
+	// placed in the kd-tree
+	class KdRenderable
+	{
+	public:
+		KdRenderable():mSide(PlaneEvent::PES_BOTH), mClassified(false), mLastQueued(0), mKdTree(0) {};
+		virtual ~KdRenderable()
+		{
+			if (mKdTree)
+				mKdTree->remove(this);
+		}
+
+		// gather the information required for the creation of the kd-tree
+		virtual void computeScene(PlaneEventList& events, AxisAlignedBox& aabb, int& nObjects, bool includeChildren = true) = 0;
+
+		// put all objects this element holds in the renedering queue
+		virtual void queueObjects(Camera* cam, RenderQueue* queue, bool onlyShadowCasters) = 0;
+
+		// return a bounding box enclosing all objects
+		virtual AxisAlignedBox getBoundingBox() const = 0;
+
+		// TODO: reconsider getters/setters !!!
+		inline bool isClassified()
+		{
+			return mClassified;
+		};
+		inline void setClassified(bool q)
+		{
+			mClassified = q;
+		};
+
+		inline PlaneEvent::Side getSide()
+		{
+			return mSide;
+		};
+		inline void setSide(PlaneEvent::Side s)
+		{
+			mSide = s;
+		};
+
+		// funcions for attachment/detachment of renderables to/from the kd-tree
+		inline bool isAttached()
+		{
+			return mLeaves.size() != 0;
+		};
+		// the following functions should work in O(log N)
+		inline bool isAttached(KdTree::LeafPtr leaf)
+		{
+			return mLeaves.find(leaf) != mLeaves.end();
+		};
+		inline bool attachTo(KdTree::LeafPtr leaf, KdTree * kdTree)
+		{
+			if (mKdTree == 0 || mKdTree == kdTree)
+				mKdTree = kdTree;
+			else
+				return false;
+
+			KdTree::LeafSet::_Pairib p = mLeaves.insert(leaf);
+			return p.second;
+		};
+		inline bool detachFrom(KdTree::LeafPtr leaf)
+		{
+			bool success = (mLeaves.erase(leaf) == 1);
+			if (mLeaves.size() == 0)
+				mKdTree = 0;
+
+			return success;
+		};
+
+		inline bool isQueued(unsigned long currentFrame, Camera * currentCam)
+		{
+			if (mLastQueued == currentFrame && mLastCam == currentCam)
+			{
+				return true;
+			}
+			else
+			{
+				mLastQueued = currentFrame;
+				mLastCam = currentCam;
+				return false;
+			}
+		};
+
+		KdTree::LeafSet& getLeaves()
+		{
+			return mLeaves;
+		};
+
+	protected:
+		// number of the frame in which this renderable was last queued for rendering
+		unsigned long mLastQueued;
+		// the camera for which this renderable was last queued for rendering
+		Camera * mLastCam;
+		
+		// kdtree to which this renderable is attached
+		KdTree * mKdTree;
+		// kdtree leaves which overlap this renderable
+		KdTree::LeafSet mLeaves;
+
+		// Flag for the SAH determining the "cheaper" side of the split plane
+		PlaneEvent::Side mSide;
+		// Flag for the SAH which marks if this renderable was already placed in the list after a split
+		bool mClassified;
+	}; // class KdRenderable
+
+} // namespace Ogre
+
+#endif // _OgreKdRenderable_H__
Index: GTP/trunk/Lib/Vis/OnlineCullingCHC/OGRE/include/OgreKdTreeSceneManager.h
===================================================================
--- GTP/trunk/Lib/Vis/OnlineCullingCHC/OGRE/include/OgreKdTreeSceneManager.h	(revision 1163)
+++ GTP/trunk/Lib/Vis/OnlineCullingCHC/OGRE/include/OgreKdTreeSceneManager.h	(revision 1163)
@@ -0,0 +1,89 @@
+/*
+-----------------------------------------------------------------------------
+This source file is part of the GameTools Project
+http://www.gametools.org
+
+Author: Martin Szydlowski
+-----------------------------------------------------------------------------
+*/
+
+#ifndef _KdTreeSceneManager_H__
+#define _KdTreeSceneManager_H__
+
+#include <OgreSceneManager.h>
+#include "OgreKdTree.h"
+
+namespace Ogre
+{
+	class KdTreeSceneNode;
+	class WireBoundingBox;
+	typedef std::list < WireBoundingBox * > WBBList;
+
+	class KdTreeSceneManager : public SceneManager
+	{
+	public:
+		KdTreeSceneManager(const String& name);
+		//KdTreeSceneManager(const String& name, int maxdepth);
+		~KdTreeSceneManager(void);
+
+		virtual const String& getTypeName(void) const;
+		virtual SceneNode* createSceneNode(void);
+		virtual SceneNode* createSceneNode(const String& name);
+		void init( int maxdepth );
+		void walkTree(KdTree * node, Camera *cam);
+
+		virtual void _findVisibleObjects(Camera *cam, bool onlyShadowCasters);
+
+		virtual void setShowBoxes(bool showboxes);
+		virtual bool getShowBoxes(void) const;
+
+		virtual void _updateNode(KdTreeSceneNode *node); // TODO: 
+
+		virtual bool setOption(const String& strKey, const void* pValue);
+		virtual bool getOption(const String& strKey, void* pDestValue);
+
+		virtual void clearScene()
+		{
+			// DEBUG must happen before scene is cleared
+			// might be a solution to detach problem
+			//if (mKdTree)
+			//	mKdTree->dump();
+			
+			OGRE_DELETE(mKdTree);
+
+			SceneManager::clearScene();
+		}
+	protected:
+
+		int mMaxDepth;
+
+		KdTree *mKdTree;
+
+		bool mShowBoxes;
+
+		KdTree::BuildMethod mBuildMethod;
+#ifdef KDTREE_DEBUG
+		int mHighlighLevel;
+		bool mShowAllBoxes;
+#endif
+	};
+
+
+
+	/// Factory for KdTreeSceneManager
+	class KdTreeSceneManagerFactory : public SceneManagerFactory
+	{
+	protected:
+		void initMetaData(void) const;
+	public:
+		KdTreeSceneManagerFactory(void) {};
+		~KdTreeSceneManagerFactory(void) {};
+		/// Factory type name
+		static const String FACTORY_TYPE_NAME;
+		SceneManager* createInstance(const String& instanceName);
+		void destroyInstance(SceneManager* instance);
+	};
+
+} // namespace Ogre
+
+#endif // _KdTreeSceneManager_H__
Index: GTP/trunk/Lib/Vis/OnlineCullingCHC/OGRE/include/OgreKdTreeSceneNode.h
===================================================================
--- GTP/trunk/Lib/Vis/OnlineCullingCHC/OGRE/include/OgreKdTreeSceneNode.h	(revision 1163)
+++ GTP/trunk/Lib/Vis/OnlineCullingCHC/OGRE/include/OgreKdTreeSceneNode.h	(revision 1163)
@@ -0,0 +1,55 @@
+/*
+-----------------------------------------------------------------------------
+This source file is part of the GameTools Project
+http://www.gametools.org
+
+Author: Martin Szydlowski
+-----------------------------------------------------------------------------
+*/
+
+#ifndef _OgreKdTreeSceneNode_H__
+#define _OgreKdTreeSceneNode_H__
+
+#include <OgreSceneNode.h>
+#include "OgreKdRenderable.h"
+
+namespace Ogre
+{
+
+	class KdTreeSceneNode : public SceneNode, public KdRenderable
+	{
+	public:
+		KdTreeSceneNode(SceneManager *creator):
+		  SceneNode(creator) {};
+
+		KdTreeSceneNode(SceneManager *creator, const String& name):
+		  SceneNode(creator, name) {};
+
+		~KdTreeSceneNode() {};
+
+		// calculate all-enclosing AABB, similar to _updateBounds()
+		void forceComputeAABB(AxisAlignedBox& aabb); // OBSOLETE !!
+
+		// gather info for kd-tree creation
+		virtual void computeScene(PlaneEventList& events, AxisAlignedBox& aabb, int& nObjects, bool includeChildren = true);
+
+		// add all contained objects to render queue
+		virtual void queueObjects(Camera* cam, RenderQueue* queue, bool onlyShadowCasters);
+
+		// return a bounding box enclosing all objects
+		virtual AxisAlignedBox getBoundingBox() const;
+
+		//virtual void _findVisibleObjects(Camera* cam, RenderQueue* queue, 
+		//	bool includeChildren = true, bool displayNodes = false, bool onlyShadowCasters = false);
+
+		// DEBUG
+		String dumpToString();
+	protected:
+		virtual void _updateBounds(void);
+
+		//AxisAlignedBox mLocalAABB;
+	};
+
+} // namespace Ogre
+
+#endif // _OgreKdTreeSceneNode_H__
Index: GTP/trunk/Lib/Vis/OnlineCullingCHC/OGRE/scripts/Plugin_VisibilitySceneManager.vcproj
===================================================================
--- GTP/trunk/Lib/Vis/OnlineCullingCHC/OGRE/scripts/Plugin_VisibilitySceneManager.vcproj	(revision 1159)
+++ GTP/trunk/Lib/Vis/OnlineCullingCHC/OGRE/scripts/Plugin_VisibilitySceneManager.vcproj	(revision 1163)
@@ -21,5 +21,5 @@
 				Optimization="0"
 				AdditionalIncludeDirectories="&quot;$(OGRE_PATH)\PlugIns\OctreeSceneManager\include&quot;;&quot;$(OGRE_PATH)\Samples\Common\include&quot;;&quot;$(OGRE_PATH)\Dependencies\include\CEGUI&quot;;&quot;$(OGRE_PATH)\Samples\Common\CEGUIRenderer\include&quot;;&quot;$(OGRE_PATH)\OgreMain\include&quot;;&quot;$(OGRE_PATH)\Dependencies\include&quot;;..\include;..\..\..\OnlineCullingCHC\include;..\..\..\Preprocessing\src"
-				PreprocessorDefinitions="WIN32;_DEBUG;_WINDOWS;_USRDLL;PLUGIN_OCCLUSIONCULLINGSCENEMANAGER_EXPORTS;GTP_VISIBILITY_MODIFIED_OGRE"
+				PreprocessorDefinitions="WIN32;_DEBUG;_WINDOWS;_USRDLL;PLUGIN_OCCLUSIONCULLINGSCENEMANAGER_EXPORTS;GTP_VISIBILITY_MODIFIED_OGRE;KDTREE_DEBUG"
 				MinimalRebuild="TRUE"
 				BasicRuntimeChecks="3"
@@ -30,5 +30,5 @@
 				WarningLevel="3"
 				Detect64BitPortabilityProblems="TRUE"
-				DebugInformationFormat="4"/>
+				DebugInformationFormat="3"/>
 			<Tool
 				Name="VCCustomBuildTool"/>
@@ -36,10 +36,10 @@
 				Name="VCLinkerTool"
 				IgnoreImportLibrary="TRUE"
-				AdditionalDependencies="OgreMain_d.lib CEGUIBase_d.lib OgreGUIRenderer_d.lib Plugin_OctreeSceneManager.lib GtpVisibility.lib zdll.lib zziplibd.lib Preprocessor.lib devil.lib glut32.lib xerces-c_2.lib OpenGL32.Lib glu32.lib cg.lib cgGL.lib glew32.lib qtmain.lib QtOpenGLd4.lib QtCored4.lib QtGuid4.lib Qt3Supportd4.lib QAxContainer.lib"
+				AdditionalDependencies="OgreMain_d.lib CEGUIBase_d.lib OgreGUIRenderer_d.lib Plugin_OctreeSceneManager.lib GtpVisibility.lib zdll.lib zziplibd.lib Preprocessor.lib devil.lib glut32.lib xerces-c_2D.lib OpenGL32.Lib glu32.lib cg.lib cgGL.lib glew32.lib"
 				OutputFile="$(OutDir)/Plugin_VisibilitySceneManager.dll"
 				Version="0.99"
 				LinkIncremental="1"
 				SuppressStartupBanner="TRUE"
-				AdditionalLibraryDirectories="&quot;$(OGRE_PATH)\OgreMain\lib\$(ConfigurationName)&quot;;&quot;$(OGRE_PATH)\Dependencies\lib\$(ConfigurationName)&quot;;&quot;$(OGRE_PATH)\PlugIns\OctreeSceneManager\bin\$(ConfigurationName)&quot;;&quot;$(OGRE_PATH)\Samples\Common\CEGUIRenderer\lib&quot;;&quot;..\lib\$(ConfigurationName)&quot;;&quot;..\..\lib\$(ConfigurationName)&quot;;&quot;..\..\..\Preprocessing\lib\$(ConfigurationName)&quot;;..\..\..\Preprocessing\src\GL;..\..\..\..\..\..\..\NonGTP\Xerces\xercesc\lib;&quot;$(QTDIR)\lib&quot;;&quot;$(CG_LIB_PATH)&quot;"
+				AdditionalLibraryDirectories="&quot;$(OGRE_PATH)\OgreMain\lib\$(ConfigurationName)&quot;;&quot;$(OGRE_PATH)\Dependencies\lib\$(ConfigurationName)&quot;;&quot;$(OGRE_PATH)\PlugIns\OctreeSceneManager\bin\$(ConfigurationName)&quot;;&quot;$(OGRE_PATH)\Samples\Common\CEGUIRenderer\lib&quot;;&quot;..\lib\$(ConfigurationName)&quot;;&quot;..\..\lib\$(ConfigurationName)&quot;;&quot;..\..\..\Preprocessing\lib\$(ConfigurationName)&quot;;..\..\..\Preprocessing\src\GL;..\..\..\..\..\..\..\NonGTP\Xerces\xercesc\lib;&quot;$(CG_LIB_PATH)&quot;"
 				ModuleDefinitionFile="..\misc\OgreVisibilitySceneManager.def"
 				GenerateDebugInformation="TRUE"
@@ -89,5 +89,5 @@
 				OptimizeForProcessor="2"
 				AdditionalIncludeDirectories="&quot;$(OGRE_PATH)\PlugIns\OctreeSceneManager\include&quot;;&quot;$(OGRE_PATH)\Samples\Common\include&quot;;&quot;$(OGRE_PATH)\Dependencies\include\CEGUI&quot;;&quot;$(OGRE_PATH)\Samples\Common\CEGUIRenderer\include&quot;;&quot;$(OGRE_PATH)\OgreMain\include&quot;;&quot;$(OGRE_PATH)\Dependencies\include&quot;;..\include;..\..\..\OnlineCullingCHC\include;..\..\..\Preprocessing\src"
-				PreprocessorDefinitions="WIN32;NDEBUG;_WINDOWS;_USRDLL;GTP_VISIBILITY_MODIFIED_OGRE"
+				PreprocessorDefinitions="WIN32;NDEBUG;_WINDOWS;_USRDLL;GTP_VISIBILITY_MODIFIED_OGRE;KDTREE_DEBUG"
 				StringPooling="TRUE"
 				RuntimeLibrary="2"
@@ -104,5 +104,5 @@
 				Name="VCLinkerTool"
 				IgnoreImportLibrary="TRUE"
-				AdditionalDependencies="OgreMain.lib CEGUIBase.lib OgreGUIRenderer.lib Plugin_OctreeSceneManager.lib GtpVisibility.lib zdll.lib zziplib.lib Preprocessor.lib xerces-c_2.lib devil.lib qtmain.lib QtOpenGL4.lib QtCore4.lib QtGui4.lib Qt3Support4.lib QAxContainer.lib glut32.lib OpenGL32.Lib glu32.lib cg.lib cgGL.lib glew32.lib glew32s.lib"
+				AdditionalDependencies="OgreMain.lib CEGUIBase.lib OgreGUIRenderer.lib Plugin_OctreeSceneManager.lib GtpVisibility.lib zdll.lib zziplib.lib Preprocessor.lib xerces-c_2.lib devil.lib glut32.lib OpenGL32.Lib glu32.lib cg.lib cgGL.lib glew32.lib glew32s.lib"
 				OutputFile="$(OutDir)/Plugin_VisibilitySceneManager.dll"
 				Version="0.99"
@@ -260,4 +260,37 @@
 			</Filter>
 		</Filter>
+		<Filter
+			Name="KdTreeSceneManager"
+			Filter="">
+			<Filter
+				Name="Header Files"
+				Filter="">
+				<File
+					RelativePath="..\include\OgreKdRenderable.h">
+				</File>
+				<File
+					RelativePath="..\include\OgreKdTree.h">
+				</File>
+				<File
+					RelativePath="..\include\OgreKdTreeSceneManager.h">
+				</File>
+				<File
+					RelativePath="..\include\OgreKdTreeSceneNode.h">
+				</File>
+			</Filter>
+			<Filter
+				Name="Source Files"
+				Filter="">
+				<File
+					RelativePath="..\src\OgreKdTree.cpp">
+				</File>
+				<File
+					RelativePath="..\src\OgreKdTreeSceneManager.cpp">
+				</File>
+				<File
+					RelativePath="..\src\OgreKdTreeSceneNode.cpp">
+				</File>
+			</Filter>
+		</Filter>
 		<File
 			RelativePath=".\VTune\Plugin_VisibilitySceneManager.vpj">
Index: GTP/trunk/Lib/Vis/OnlineCullingCHC/OGRE/src/OgreKdTreeSceneManager.cpp
===================================================================
--- GTP/trunk/Lib/Vis/OnlineCullingCHC/OGRE/src/OgreKdTreeSceneManager.cpp	(revision 1163)
+++ GTP/trunk/Lib/Vis/OnlineCullingCHC/OGRE/src/OgreKdTreeSceneManager.cpp	(revision 1163)
@@ -0,0 +1,328 @@
+/*
+-----------------------------------------------------------------------------
+This source file is part of the GameTools Project
+http://www.gametools.org
+
+Author: Martin Szydlowski
+-----------------------------------------------------------------------------
+*/
+
+#include <OgreCamera.h>
+#include "OgreKdTreeSceneManager.h"
+#include "OgreKdTreeSceneNode.h"
+#include "OgreKdTree.h"
+
+#include <OgreLogManager.h>
+#include <OgreStringConverter.h>
+
+namespace Ogre
+{
+	KdTreeSceneManager::KdTreeSceneManager(const String& name):
+		SceneManager(name)
+	{
+		int maxdepth = 20;
+		mKdTree = 0;
+		init(maxdepth);
+	}
+
+	KdTreeSceneManager::~KdTreeSceneManager(void)
+	{
+		delete mKdTree;
+	}
+
+	const String& KdTreeSceneManager::getTypeName(void) const
+	{
+		return KdTreeSceneManagerFactory::FACTORY_TYPE_NAME;
+	}
+
+	void KdTreeSceneManager::init(int maxdepth)
+	{
+		// Replace root node with my node
+		OGRE_DELETE(mSceneRoot);
+
+		mSceneRoot = new KdTreeSceneNode(this, "root node");
+		mSceneRoot->_notifyRootNode();
+
+		mMaxDepth = maxdepth;
+		mShowBoxes = false;
+
+		// kill the old kd-tree if exists 
+		OGRE_DELETE(mKdTree);
+
+		mBuildMethod = KdTree::KDBM_RECURSIVE;
+		//mBuildMethod = KdTree::KDBM_PRIORITYQUEUE;
+#ifdef KDTREE_DEBUG
+		mHighlighLevel = 0;
+		mShowAllBoxes = false;
+#endif
+	}
+
+	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;
+#ifdef KDTREE_DEBUG
+				if (mHighlighLevel > mMaxDepth)
+					mHighlighLevel = mMaxDepth;
+#endif
+				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);
+			mKdTree->setBuildMethod(mBuildMethod);
+			mKdTree->build(static_cast<KdTreeSceneNode *>(mSceneRoot));
+			return true;
+		}
+#ifdef KDTREE_DEBUG
+		else if (strKey == "HighlightLevel")
+		{
+			int hl = *static_cast<const int *>(pValue);
+			if (hl >= 0 && hl <= mMaxDepth)
+			{
+				mHighlighLevel = hl;
+				return true;
+			}
+			else
+			{
+				return false;
+			}
+		}
+		else if (strKey == "ShowAllBoxes")
+		{
+			bool sa = *static_cast<const bool *>(pValue);
+			mShowAllBoxes = sa;
+			return true;
+		}
+#endif
+		else if (strKey == "BuildMethod")
+		{
+			String bm = *static_cast<const String *>(pValue);
+			if (bm == "PriorityQueue")
+			{
+				mBuildMethod = KdTree::KDBM_PRIORITYQUEUE;
+				return true;
+			}
+			else if (bm == "Recursive")
+			{
+				mBuildMethod = KdTree::KDBM_RECURSIVE;
+				return true;
+			}
+			else
+			{
+				return false;
+			}
+		}
+		else if (strKey == "ShowKdTree")
+		{
+			bool sk = *static_cast<const bool *>(pValue);
+			mShowBoxes = sk;
+			return true;
+		}
+
+		return 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;
+		}
+#ifdef KDTREE_DEBUG
+		else if (strKey == "HighlightLevel")
+		{
+			*static_cast<int *>(pDestValue) = mHighlighLevel;
+			return true;
+		}
+		else if (strKey == "ShowAllBoxes")
+		{
+			*static_cast<bool *>(pDestValue) = mShowAllBoxes;
+			return true;
+		}
+#endif
+		else if (strKey == "BuildMethod")
+		{
+			if (mBuildMethod == KdTree::KDBM_PRIORITYQUEUE)
+			{
+				*static_cast<String *>(pDestValue) = "PriorityQueue";
+			}
+			else if (mBuildMethod == KdTree::KDBM_RECURSIVE)
+			{
+				*static_cast<String *>(pDestValue) = "Recursive";
+			}
+			return true;
+		}
+		else if (strKey == "TreeBox")
+		{
+			if (mKdTree)
+				*static_cast<AxisAlignedBox *>(pDestValue) = mKdTree->getBox();
+			else
+				*static_cast<AxisAlignedBox *>(pDestValue) = AxisAlignedBox();
+		}
+
+		return SceneManager::getOption(strKey, pDestValue);
+	}
+
+	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;
+	}
+
+	// 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);
+			mKdTree->setBuildMethod(mBuildMethod);
+			mKdTree->build(static_cast<KdTreeSceneNode *>(mSceneRoot));
+		}
+
+		// 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::_findVisibleObjects(Camera *cam, bool onlyShadowCasters)
+	{
+		getRenderQueue()->clear();
+		if (mKdTree)
+			mKdTree->queueVisibleObjects(cam, getRenderQueue(), onlyShadowCasters, mShowBoxes);
+		//SceneManager::_findVisibleObjects(cam, onlyShadowCasters);
+	}
+
+	//-----------------------------------------------------------------------
+	//-----------------------------------------------------------------------
+	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 = ST_GENERIC; // support generic scenes (so far)
+		mMetaData.worldGeometrySupported = false;
+	}
+	//-----------------------------------------------------------------------
+	SceneManager* KdTreeSceneManagerFactory::createInstance(
+		const String& instanceName)
+	{
+		return new KdTreeSceneManager(instanceName);
+	}
+	//-----------------------------------------------------------------------
+	void KdTreeSceneManagerFactory::destroyInstance(SceneManager* instance)
+	{
+		delete instance;
+	}
+
+} // namespace Ogre
+
Index: GTP/trunk/Lib/Vis/OnlineCullingCHC/OGRE/src/OgreVisibilitySceneManagerDll.cpp
===================================================================
--- GTP/trunk/Lib/Vis/OnlineCullingCHC/OGRE/src/OgreVisibilitySceneManagerDll.cpp	(revision 1153)
+++ GTP/trunk/Lib/Vis/OnlineCullingCHC/OGRE/src/OgreVisibilitySceneManagerDll.cpp	(revision 1163)
@@ -26,4 +26,5 @@
 //#include <OgreVisibilityTerrainSceneManager.h>
 #include <OgreOcclusionCullingSceneManager.h>
+#include <OgreKdTreeSceneManager.h>
 
 //#include <OgreHeightmapTerrainPageSource.h>
@@ -41,4 +42,5 @@
 //VisibilityTerrainSceneManagerFactory *visibilityTerrainPlugin;
 OcclusionCullingSceneManagerFactory *occlusionCullingPlugin;
+KdTreeSceneManagerFactory *kdTreeFactory;
 
 //-----------------------------------------------------------------------
@@ -52,4 +54,5 @@
 	//visibilityTerrainPlugin = new VisibilityTerrainSceneManagerFactory(visManager);
 	occlusionCullingPlugin = new OcclusionCullingSceneManagerFactory(visManager);
+	kdTreeFactory = new KdTreeSceneManagerFactory();
 	// Construct listener manager singleton
 	new TerrainPageSourceListenerManager();
@@ -58,4 +61,5 @@
 	//Root::getSingleton().addSceneManagerFactory(visibilityTerrainPlugin);
 	Root::getSingleton().addSceneManagerFactory(occlusionCullingPlugin);
+	Root::getSingleton().addSceneManagerFactory(kdTreeFactory);
 }
 //-----------------------------------------------------------------------
@@ -64,4 +68,5 @@
 	//Root::getSingleton().removeSceneManagerFactory(visibilityTerrainPlugin);
 	Root::getSingleton().removeSceneManagerFactory(occlusionCullingPlugin);
+	Root::getSingleton().removeSceneManagerFactory(kdTreeFactory);
 	// destroy listener manager
 	delete TerrainPageSourceListenerManager::getSingletonPtr();
@@ -75,4 +80,5 @@
 	//delete visibilityTerrainPlugin;
 	delete occlusionCullingPlugin;
+	delete kdTreeFactory;
 
 	delete visManager;
Index: GTP/trunk/Lib/Vis/OnlineCullingCHC/OGRE/src/OgreKdTreeSceneNode.cpp
===================================================================
--- GTP/trunk/Lib/Vis/OnlineCullingCHC/OGRE/src/OgreKdTreeSceneNode.cpp	(revision 1163)
+++ GTP/trunk/Lib/Vis/OnlineCullingCHC/OGRE/src/OgreKdTreeSceneNode.cpp	(revision 1163)
@@ -0,0 +1,162 @@
+/*
+-----------------------------------------------------------------------------
+This source file is part of the GameTools Project
+http://www.gametools.org
+
+Author: Martin Szydlowski
+-----------------------------------------------------------------------------
+*/
+
+#include "OgreKdTreeSceneNode.h"
+#include "OgreKdTreeSceneManager.h"
+
+#include <OgreStringConverter.h>
+
+namespace Ogre
+{
+	// TRIVIA: this function is _not_ called for nodes which did not change since the last frame
+	// only exception: the root node ... it's aabb should be null however, so we don't care
+	void KdTreeSceneNode::_updateBounds(void)
+	{
+		// Reset bounds first
+		mWorldAABB.setNull();
+
+		// Update bounds from own attached objects
+		ObjectMap::iterator i;
+		for (i = mObjectsByName.begin(); i != mObjectsByName.end(); ++i)
+		{
+			// Merge world bounds of each object
+			mWorldAABB.merge(i->second->getWorldBoundingBox(true));
+		}
+
+		if (!mWorldAABB.isNull())
+		{
+			static_cast<KdTreeSceneManager *>(mCreator)->_updateNode(this);
+		}
+	}
+
+	void KdTreeSceneNode::forceComputeAABB(AxisAlignedBox& aabb) // OBSOLETE !!
+	{
+
+		// Update bounds from own attached objects
+		ObjectMap::iterator i;
+		for (i = mObjectsByName.begin(); i != mObjectsByName.end(); ++i)
+		{
+			// Merge world bounds of each object
+			aabb.merge(i->second->getWorldBoundingBox(true));
+		}
+		// Merge with children
+		ChildNodeMap::iterator child;
+		for (child = mChildren.begin(); child != mChildren.end(); ++child)
+		{
+			KdTreeSceneNode* sceneChild = static_cast<KdTreeSceneNode*>(child->second);
+			sceneChild->forceComputeAABB(aabb);
+		}
+	}
+
+	void KdTreeSceneNode::computeScene(PlaneEventList& events, AxisAlignedBox& aabb, int& nObjects, bool includeChildren)
+	{
+		// first compute nodes AABB
+		mWorldAABB.setNull();
+		// Update bounds from own attached objects
+		ObjectMap::iterator i;
+		for (i = mObjectsByName.begin(); i != mObjectsByName.end(); ++i)
+		{
+			// Merge world bounds of each object
+			mWorldAABB.merge(i->second->getWorldBoundingBox(true));
+		}
+
+		if (!mWorldAABB.isNull())
+		{
+			// merge aabb with global AABB
+			aabb.merge(mWorldAABB);
+			// increase object count
+			nObjects++;
+
+			// generate events
+			PlaneEvent::Dimension axes[] = 
+				{PlaneEvent::PED_X, PlaneEvent::PED_Y, PlaneEvent::PED_Z};
+			Vector3 min = mWorldAABB.getMinimum();
+			Vector3 max = mWorldAABB.getMaximum();
+			//PlaneEvent * e;
+			for (int i = 0; i < 3; i++)
+			{
+				// 1-D and 2-D objects
+				if (min[i] == max[i])
+				{	
+					//e = new PlaneEvent(this, min, axes[i], PlaneEvent::PET_ON);
+					//sceneinfo.events.push_back(*e);
+					events.push_back(PlaneEvent(this, min, axes[i], PlaneEvent::PET_ON));
+				}
+				else
+				{
+					//e = new PlaneEvent(this, min, axes[i], PlaneEvent::PET_START);
+					//sceneinfo.events.push_back(*e);
+					//e = new PlaneEvent(this, max, axes[i], PlaneEvent::PET_END);
+					//sceneinfo.events.push_back(*e);
+					events.push_back(PlaneEvent(this, min, axes[i], PlaneEvent::PET_START));
+					events.push_back(PlaneEvent(this, max, axes[i], PlaneEvent::PET_END));
+				}
+			}
+		}
+
+		// Merge with children
+		if (includeChildren)
+		{
+			ChildNodeMap::iterator child;
+			for (child = mChildren.begin(); child != mChildren.end(); ++child)
+			{
+				KdTreeSceneNode* sceneChild = static_cast<KdTreeSceneNode*>(child->second);
+				sceneChild->computeScene(events, aabb, nObjects);
+			}
+		}
+	}
+
+	//void KdTreeSceneNode::_findVisibleObjects(Camera* cam, RenderQueue* queue, 
+	//	bool includeChildren, bool displayNodes, bool onlyShadowCasters)
+	void KdTreeSceneNode::queueObjects(Camera* cam, RenderQueue* queue, bool onlyShadowCasters)
+	{
+		//SceneNode::_findVisibleObjects(cam, queue, includeChildren, displayNodes, onlyShadowCasters);
+
+		// Add all entities
+		ObjectMap::iterator iobj;
+		ObjectMap::iterator iobjend = mObjectsByName.end();
+		for (iobj = mObjectsByName.begin(); iobj != iobjend; ++iobj)
+		{
+			// Tell attached objects about camera position (incase any extra processing they want to do)
+			iobj->second->_notifyCurrentCamera(cam);
+			if (!onlyShadowCasters || iobj->second->getCastShadows())
+			{
+				iobj->second->_updateRenderQueue(queue);
+			}
+		}
+
+		// Check if the bounding box should be shown.
+		// See if our flag is set or if the scene manager flag is set.
+		if (mShowBoundingBox || (mCreator && mCreator->getShowBoundingBoxes())) 
+		{ 
+			_addBoundingBoxToQueue(queue);
+		}
+	}
+
+	AxisAlignedBox KdTreeSceneNode::getBoundingBox() const
+	{
+		return mWorldAABB;
+	}
+
+	// DEBUG
+	String KdTreeSceneNode::dumpToString()
+	{
+		String objects;
+		// Add all entities
+		ObjectMap::iterator iobj = mObjectsByName.begin();
+		ObjectMap::iterator iobjend = mObjectsByName.end();
+		while (iobj != iobjend)
+		{
+			objects += " " + iobj->second->getName();
+			iobj++;
+		}
+		objects += " Attached to " + StringConverter::toString(mLeaves.size()) + " KdLeaves.";
+		return objects;
+	}
+}
Index: GTP/trunk/Lib/Vis/OnlineCullingCHC/OGRE/src/OgreKdTree.cpp
===================================================================
--- GTP/trunk/Lib/Vis/OnlineCullingCHC/OGRE/src/OgreKdTree.cpp	(revision 1163)
+++ GTP/trunk/Lib/Vis/OnlineCullingCHC/OGRE/src/OgreKdTree.cpp	(revision 1163)
@@ -0,0 +1,1421 @@
+/*
+-----------------------------------------------------------------------------
+This source file is part of the GameTools Project
+http://www.gametools.org
+
+Author: Martin Szydlowski
+-----------------------------------------------------------------------------
+*/
+
+#include <OgreCamera.h>
+#include "OgreKdTree.h"
+#include "OgreKdRenderable.h"
+#include "OgreKdTreeSceneNode.h"
+#include "OgreKdTreeSceneManager.h"
+
+#include <OgreStringConverter.h>
+#include <OgreLogManager.h>
+#include <OgreRoot.h>
+#include <OgreTimer.h>
+
+#include <OgreMaterialManager.h>
+
+#define KDTREE_LOGNAME "KdTreeBuild.log"
+
+namespace Ogre
+{
+	Real PlaneEvent::KT = 2.0;
+	Real PlaneEvent::KI = 1.0;
+
+	void PlaneEvent::classify(const PlaneEvent& e, PlaneEvent::Side side)
+	{
+		// only classify events of the same dimension
+		if (mDimension == e.mDimension)
+		{
+			if (mType == PET_END && mPosition[mDimension] <= e.mPosition[e.mDimension])
+			{
+				mRenderable->setSide(PES_LEFT);
+			}
+			else if (mType == PET_START && mPosition[mDimension] >= e.mPosition[e.mDimension])
+			{
+				mRenderable->setSide(PES_RIGHT);
+			}
+			else if (mType == PET_ON)
+			{
+				if (mPosition[mDimension] < e.mPosition[e.mDimension] ||
+					(mPosition[mDimension] == e.mPosition[e.mDimension] && side == PES_LEFT))
+				{
+					mRenderable->setSide(PES_LEFT);
+				}
+				if (mPosition[mDimension] > e.mPosition[e.mDimension] ||
+					(mPosition[mDimension] == e.mPosition[e.mDimension] && side == PES_RIGHT))
+				{
+					mRenderable->setSide(PES_RIGHT);
+				}
+			}
+		}
+	}
+
+	PlaneEvent PlaneEvent::clip(AxisAlignedBox& box, PlaneEvent::Dimension dim)
+	{
+		Vector3 newpos = mPosition, min = box.getMinimum(), max = box.getMaximum();
+		if (newpos[dim] < min[dim])
+			newpos[dim] = min[dim];
+		else if (newpos[dim] > max[dim])
+			newpos[dim] = max[dim];
+
+		return PlaneEvent(mRenderable, newpos, mDimension, mType);
+	}
+
+	void PlaneEvent::SAH(const AxisAlignedBox& parent, int nLeft, int nPlane, int nRight, SplitInfo& split)
+	{
+
+#ifdef KDTREE_DEBUG_OFF
+		Real mu = splitBox(parent, split.bleft, split.bright);
+		Real sav = surfaceArea(parent); // optimize?? called several times for the same box
+		Real savl = surfaceArea(split.bleft);
+		Real savr = surfaceArea(split.bright);
+		Real pl = savl / sav;
+		Real pr = savr / sav;
+		Real costl = splitCost(pl, pr, nLeft + nPlane, nRight, mu);
+		Real costr = splitCost(pl, pr, nLeft, nPlane + nRight, mu);
+
+		Log * log = LogManager::getSingleton().getLog(KDTREE_LOGNAME);
+		log->logMessage("SAH: SA-parent=" + StringConverter::toString(sav) + 
+			"\n\tSA-left=" + StringConverter::toString(savl) + 
+			" SA-right=" + StringConverter::toString(savr) + 
+			"\n\tp-left=" + StringConverter::toString(pl) + 
+			" p-right=" + StringConverter::toString(pr) +
+			"\n\tmu=" + StringConverter::toString(mu) +
+			"\n\tcost-left=" + StringConverter::toString(costl) +
+			" cost-right=" + StringConverter::toString(costr));
+#else
+		Real mu = splitBox(parent, split.bleft, split.bright);
+		Real sav = surfaceArea(parent); // optimize?? called several times for the same box
+		Real pl = surfaceArea(split.bleft) / sav;
+		Real pr = surfaceArea(split.bright) / sav;
+		Real costl = splitCost(pl, pr, nLeft + nPlane, nRight, mu);
+		Real costr = splitCost(pl, pr, nLeft, nPlane + nRight, mu);
+
+#endif
+		if (costl < costr)
+		{
+			split.cost = costl;
+			split.side = PES_LEFT;
+			split.nleft = nLeft + nPlane;
+			split.nright = nRight;
+		}
+		else
+		{
+			split.cost = costr;
+			split.side = PES_RIGHT;
+			split.nleft = nLeft;
+			split.nright = nPlane + nRight;
+
+		}
+		split.event = *this;
+	}
+
+	Real PlaneEvent::splitBox(const AxisAlignedBox& parent, AxisAlignedBox& left, AxisAlignedBox& right)
+	{
+		Vector3 bmin = parent.getMinimum();
+		Vector3 bmax = parent.getMaximum();
+#ifdef KDTREE_DEBUG_OFF
+		if(bmin[mDimension] > mPosition[mDimension] || bmax[mDimension] < mPosition[mDimension])
+		{
+			Log * log = LogManager::getSingleton().getLog(KDTREE_LOGNAME);
+			log->logMessage("SPLITBOX SNAFU in event " + print() +
+				"\n\tmin=" + StringConverter::toString(bmin[mDimension]) + 
+				" split=" + StringConverter::toString(mPosition[mDimension]) + 
+				" max=" + StringConverter::toString(bmax[mDimension]));
+		}
+#endif
+		// calculate the penalty for spliting the box that way
+		Real mu = lookupPenalty((mPosition[mDimension] - bmin[mDimension]) / (bmax[mDimension] - bmin[mDimension]));
+		// set corners which are the same as parent AABB
+		left.setMinimum(bmin);
+		right.setMaximum(bmax);
+		// modify "inner" corners
+		bmin[mDimension] = mPosition[mDimension];
+		bmax[mDimension] = mPosition[mDimension];
+		// set the corners on the split plane
+		left.setMaximum(bmax);
+		right.setMinimum(bmin);
+
+		return mu;
+	}
+
+	Real PlaneEvent::splitCost(Real pLeft, Real pRight, int nLeft, int nRight)
+	{
+		//assert(pLeft <= 1.0 && pRight <= 1.0);
+
+		// reward splitting off chunks of empty space
+		Real lambda = 1.0;
+		if (nLeft == 0 || nRight == 0)
+		{
+			lambda = 0.8;
+		}
+
+		// penalize splitting off small chunks
+		Real mu = 1.0;
+		if (pLeft < 0.1 || pRight < 0.1 || pLeft > 0.9 || pRight > 0.9)
+		{
+			mu = 1.5;
+		}
+		return lambda * mu * (KT + (KI * (pLeft*nLeft + pRight*nRight)));
+		
+		//return lambda * (KT + (KI * (pLeft*nLeft + pRight*nRight)));
+	}
+
+	Real PlaneEvent::splitCost(Real pLeft, Real pRight, int nLeft, int nRight, Real mu)
+	{
+		//assert(pLeft <= 1.0 && pRight <= 1.0);
+
+		// reward splitting off chunks of empty space
+		Real lambda = 1.0;
+		if (nLeft == 0 || nRight == 0)
+		{
+			lambda = 0.8;
+		}
+
+		return lambda * mu * (KT + (KI * (pLeft*nLeft + pRight*nRight)));
+	}
+
+	Real PlaneEvent::surfaceArea(const AxisAlignedBox& box)
+	{
+		Vector3 sides = box.getMaximum() - box.getMinimum();
+#ifdef KDTREE_DEBUG_OFF
+		if(sides.x < 0 || sides.y < 0 || sides.z < 0)
+		{
+			Log * log = LogManager::getSingleton().getLog(KDTREE_LOGNAME);
+			log->logMessage("AABB SNAFU: x=" + StringConverter::toString(sides.x) + 
+				" y=" + StringConverter::toString(sides.y) + " z=" + StringConverter::toString(sides.z) +
+				" BOX=" + StringConverter::toString(box.getMinimum()) + "," + StringConverter::toString(box.getMaximum()));
+		}
+#endif
+		return	2 * sides.x * sides.y +
+				2 * sides.y * sides.z +
+				2 * sides.z * sides.x;
+	}
+
+	void PlaneEvent::pqSAH(Real globalSA, Real parentSA, int nLeft, int nPlane, int nRight, AxisAlignedBox& parentBox, SplitInfo& split)
+	{
+		Real mu = splitBox(parentBox, split.bleft, split.bright);
+		Real p = parentSA / globalSA;
+		Real pl = surfaceArea(split.bleft) / globalSA;
+		Real pr = surfaceArea(split.bright) / globalSA;
+		Real costl = pqSplitCost(p, pl, pr, nLeft + nPlane, nRight, mu);
+		Real costr = pqSplitCost(p, pl, pr, nLeft, nPlane + nRight, mu);
+
+		if (costl < costr)
+		{
+			split.cost = costl;
+			split.side = PES_LEFT;
+			split.nleft = nLeft + nPlane;
+			split.nright = nRight;
+		}
+		else
+		{
+			split.cost = costr;
+			split.side = PES_RIGHT;
+			split.nleft = nLeft;
+			split.nright = nPlane + nRight;
+
+		}
+		split.event = *this;
+	}
+
+	Real PlaneEvent::pqSplitCost(Real pParent, Real pLeft, Real pRight, int nLeft, int nRight, Real mu)
+	{
+		// reward splitting off chunks of empty space
+		//Real lambda = 1.0;
+		//if (nLeft == 0 || nRight == 0)
+		//{
+		//	lambda = 0.8;
+		//}
+
+		return /* lambda * mu * */ (pParent*KT + (KI * (pLeft*nLeft + pRight*nRight)));
+	}
+
+#define PLT_SIZE 101
+
+	// lookup the penalty for placing the splitting plane near to the edge of the AABB
+	// 0.0 <= p <= 1.0, p = 0.5 means the plane divides the aabb in half
+	Real PlaneEvent::lookupPenalty(Real p)
+	{
+		// precomputed table of {x^6 + 1|0 <= x <= 1}
+		static Real mPenaltyLookupTable[PLT_SIZE];
+		static bool init_done = false;
+
+		if (!init_done)
+		{
+			Real step = 1.0  / (PLT_SIZE - 1);
+			Real x = 0.0; 
+			//LogManager::getSingleton().logMessage("### Calculating Lookup Table ###");
+			for (int i = 0; i < PLT_SIZE; i++)
+			{
+				mPenaltyLookupTable[i] = Math::Pow(x, 6) + 1.0;
+				x += step;
+				//LogManager::getSingleton().logMessage("### mPenaltyLookupTable[" + StringConverter::toString(i,3) + "]=" + StringConverter::toString(mPenaltyLookupTable[i]));
+			}
+			init_done = true;
+			//LogManager::getSingleton().logMessage("### Lookup Table Calculated ###");
+		}
+
+		// normalize p to [0,1]
+		Real x = Math::Abs(p * 2 - 1);
+		int i = Math::IFloor(x * (PLT_SIZE - 1));
+
+		return mPenaltyLookupTable[i];
+	}
+
+	// DEBUG
+	String PlaneEvent::print()
+	{
+		String dim, type;
+		if (mDimension == PED_X)
+			dim = "X";
+		if (mDimension == PED_Y)
+			dim = "Y";
+		if (mDimension == PED_Z)
+			dim = "Z";
+		if (mType == PET_END)
+			type = "END  ";
+		if (mType == PET_ON)
+			type = "ON   ";
+		if (mType == PET_START)
+			type = "START";
+		//return StringConverter::toString(mPosition[mDimension]) + " " + dim + " " + type;
+		return type + " " + dim + " " + StringConverter::toString(mPosition[mDimension]);
+	};
+
+	String SplitInfo::print()
+	{
+		String sside;
+		if (side == PlaneEvent::PES_BOTH)
+			sside = "BOTH ";
+		if (side == PlaneEvent::PES_LEFT)
+			sside = "LEFT ";
+		if (side == PlaneEvent::PES_RIGHT)
+			sside = "RIGHT";
+		return "nLeft: " + StringConverter::toString(nleft, 4) + " nRight: " + 
+			StringConverter::toString(nright, 4) + " Cost: " + StringConverter::toString(cost, 8, 9) +
+			" Side: " + sside + " Event: " + event.print() + " Leftbox: " + 
+			StringConverter::toString(bleft.getMinimum()) + ", " + 
+			StringConverter::toString(bleft.getMaximum()) + " Rightbox: " +
+			StringConverter::toString(bright.getMinimum()) + ", " + 
+			StringConverter::toString(bright.getMaximum());
+	};
+
+	String KdTree::SplitCandidate::print()
+	{		
+		String sside;
+		if (side == PlaneEvent::PES_BOTH)
+			sside = "BOTH ";
+		if (side == PlaneEvent::PES_LEFT)
+			sside = "LEFT ";
+		if (side == PlaneEvent::PES_RIGHT)
+			sside = "RIGHT";
+		return "List: " + StringConverter::toString(events->size(), 4) + " Objects: " +
+			StringConverter::toString(nObjects, 4) + " Cost: " + StringConverter::toString(cost, 8, 9) + 
+			" Decrease: " + StringConverter::toString(decrease, 8, 9) + " Side: " + sside + " Best: " +
+			best->print() +  " Box: " + StringConverter::toString(aabb.getMinimum()) + ", "
+			+ StringConverter::toString(aabb.getMaximum());
+
+	};
+
+	//----------------------------------------------------------------------------
+	//----------------------------------------------------------------------------
+	//----------------------------------------------------------------------------
+
+	KdTree::KdTree(int maxdepth): mMaxDepth(maxdepth), mKdRoot(0), mBuildMethod(KDBM_RECURSIVE), mBuildLog(0)
+	{
+#ifdef KDTREE_DEBUG
+		try
+		{
+			ColourValue cv(0.0, 1.0, 0.0);
+			MaterialPtr mp = MaterialManager::getSingleton().create("aabbHiLite","General");
+			mp->setSelfIllumination(cv);
+			mp->setDiffuse(cv);
+		}
+		catch (Ogre::Exception&)
+		{
+			// SO FUCKING DON'T CARE !!!
+		}
+#endif
+		try
+		{
+			mBuildLog = LogManager::getSingleton().getLog(KDTREE_LOGNAME);
+		}
+		catch (Exception&)
+		{		
+			mBuildLog = LogManager::getSingleton().createLog(KDTREE_LOGNAME);
+		}
+	}
+
+	KdTree::~KdTree()
+	{
+		delete mKdRoot;
+	}
+
+	void KdTree::remove(KdRenderable * rend)
+	{
+		// DEBUG
+		//LogManager::getSingleton().logMessage("-- Removing SceneNode: " + (static_cast<KdTreeSceneNode *>(rend))->getName());
+		std::queue<LeafPtr> cleanup;
+		LeafPtr leaf;
+		LeafSet ls = rend->getLeaves();
+		LeafSet::iterator it = ls.begin();
+		LeafSet::iterator end = ls.end();
+		while (it != end)
+		{
+			cleanup.push(*it);
+			it++;
+		}
+		while (!cleanup.empty())
+		{
+			leaf = cleanup.front();
+			cleanup.pop();
+			leaf->remove(rend);
+			bool gone = rend->detachFrom(leaf);
+			assert(gone && "Failed to detach leave which is abso-fuckin-lutely impossible!!!");
+			//dump();
+			recDelete(leaf);
+			//dump();
+		}
+	}
+
+	void KdTree::recDelete(KdTree::Node * node)
+	{
+		if (node == 0) // DEBUG
+		{
+			OGRE_EXCEPT(Exception::ERR_INTERNAL_ERROR,
+				"SNAFU while inserting KdRenderable into KdTree.",
+				"KdTree::recInsert" );
+			return;
+		}
+
+		if (node->isEmpty())
+		{
+			if (node == mKdRoot)
+			{
+				OGRE_DELETE(mKdRoot);
+			} 
+			else
+			{
+				KdTree::Branch * parent = node->mParent;
+				if (node == parent->mLeft)
+				{
+					OGRE_DELETE(parent->mLeft);
+				}
+				else if (node == parent->mRight)
+				{
+					OGRE_DELETE(parent->mRight);
+				}
+				recDelete(parent);
+			}
+		}
+	}
+
+	void KdTree::insert(KdRenderable * rend)
+	{
+		// make sure the tree exists
+		if (mKdRoot)
+		{
+			// make sure the renderable is inside the world bounding box
+			AxisAlignedBox aabb = rend->getBoundingBox();
+			AxisAlignedBox isect = mKdRoot->mAABB.intersection(aabb);
+			if (isect.getMinimum() == aabb.getMinimum() && isect.getMaximum() == aabb.getMaximum())
+			{
+				recInsert(mKdRoot, rend);
+			}
+			else
+			{
+				//LogManager::getSingleton().logMessage("Inserted node outside of world AABB.");
+				KdRenderableList nodelist;
+				nodelist.push_back(rend);
+				addRendToList(mKdRoot, nodelist);
+				OGRE_DELETE(mKdRoot);
+				mKdRoot = buildFromList(nodelist, 0, AxisAlignedBox());
+			}
+		}
+		// otherwise build a new one
+		else
+		{
+			build(rend);
+		}
+	}
+
+	void KdTree::recInsert(KdTree::Node * node, KdRenderable * rend)
+	{
+		if (node == 0) // DEBUG
+		{
+			OGRE_EXCEPT(Exception::ERR_INTERNAL_ERROR,
+				"SNAFU while inserting KdRenderable into KdTree.",
+				"KdTree::recInsert" );
+			return;
+		}
+
+		// rebuild the leaf/replace with subtree ...
+		if (node->isLeaf())
+		{
+			//LogManager::getSingleton().logMessage("## Replacing leaf.");
+			rebuildSubtree(node, rend);
+		}
+		else
+		{
+			KdTree::Branch * branch = static_cast<KdTree::Branch *>(node);
+			AxisAlignedBox aabb = rend->getBoundingBox();
+			Plane::Side smin = branch->mSplitPlane->getSide(aabb.getMinimum());
+			Plane::Side smax = branch->mSplitPlane->getSide(aabb.getMaximum());
+			if (smin == smax)
+			{
+				if (smax == Plane::NEGATIVE_SIDE ||
+					(smax == Plane::NO_SIDE && branch->mPlaneSide == PlaneEvent::PES_LEFT))
+				{
+					if (branch->mLeft)
+						recInsert(branch->mLeft, rend);
+					else
+						recInsertNew(branch, PlaneEvent::PES_LEFT, rend);
+				}
+				else if (smin == Plane::POSITIVE_SIDE || 
+					(smin == Plane::NO_SIDE && branch->mPlaneSide == PlaneEvent::PES_RIGHT))
+				{
+					if (branch->mRight)
+						recInsert(branch->mRight, rend);
+					else
+						recInsertNew(branch, PlaneEvent::PES_RIGHT, rend);
+				}
+			}
+			else
+			{
+				if (smin == Plane::NEGATIVE_SIDE && smax == Plane::NO_SIDE)
+				{
+					if (branch->mLeft)
+						recInsert(branch->mLeft, rend);
+					else
+						recInsertNew(branch, PlaneEvent::PES_LEFT, rend);
+				}
+				else if (smax == Plane::POSITIVE_SIDE && smin == Plane::NO_SIDE)
+				{
+					if (branch->mRight)
+						recInsert(branch->mRight, rend);
+					else
+						recInsertNew(branch, PlaneEvent::PES_RIGHT, rend);
+				}
+				else
+				{
+					// to avoid SNAFUs, rebuild whole subtree
+					//LogManager::getSingleton().logMessage("## Rebuilding subtree for insertion");
+					rebuildSubtree(node, rend);
+				}
+			}
+		}
+	}
+
+	void KdTree::recInsertNew(KdTree::Branch * parent, PlaneEvent::Side side, KdRenderable * rend)
+	{
+		//LogManager::getSingleton().logMessage("## Inserting into new subtree");
+
+		AxisAlignedBox left, rigth, aabb;
+		PlaneEventList events;
+		int nObjects;
+		
+		rend->computeScene(events, aabb, nObjects, false);
+
+		// override aabb
+		splitBox(*parent, left, rigth);
+		if (side == PlaneEvent::PES_LEFT)
+		{
+			aabb = left;
+			if (mBuildMethod == KDBM_RECURSIVE)
+				parent->mLeft = recBuild(events, nObjects, aabb, parent);
+			else if (mBuildMethod == KDBM_PRIORITYQUEUE)
+				parent->mLeft = pqBuild(events, nObjects, aabb, parent);
+			else
+			{
+				OGRE_EXCEPT(Exception::ERR_INVALIDPARAMS, 
+					"Invalid build method for the KdTree.",
+					"KdTree::buildFromList");
+				parent->mLeft = 0;
+			}
+			
+		}
+		else if (side == PlaneEvent::PES_RIGHT)
+		{
+			aabb = rigth;
+			if (mBuildMethod == KDBM_RECURSIVE)
+				parent->mRight = recBuild(events, nObjects, aabb, parent);
+			else if (mBuildMethod == KDBM_PRIORITYQUEUE)
+				parent->mRight = pqBuild(events, nObjects, aabb, parent);
+			else
+			{
+				OGRE_EXCEPT(Exception::ERR_INVALIDPARAMS, 
+					"Invalid build method for the KdTree.",
+					"KdTree::buildFromList");
+				parent->mRight = 0;
+			}
+		}
+	}
+
+	void KdTree::rebuildSubtree(KdTree::Node * node, KdRenderable * rend)
+	{
+		//LogManager::getSingleton().logMessage("## Rebuilding subtree");
+
+		AxisAlignedBox aabb = node->mAABB;
+		
+		KdRenderableList nodelist;
+		nodelist.push_back(rend);
+		addRendToList(node, nodelist);
+
+		if (node == mKdRoot)
+		{
+			OGRE_DELETE(mKdRoot);
+			mKdRoot = buildFromList(nodelist, 0, aabb);
+		}
+		else
+		{
+			KdTree::Branch * parent = static_cast<KdTree::Branch *>(node->mParent);
+
+			if (node == parent->mLeft)
+			{
+				OGRE_DELETE(parent->mLeft);
+				parent->mLeft = buildFromList(nodelist, parent, aabb);
+			}
+			else if (node == parent->mRight)
+			{
+				OGRE_DELETE(parent->mRight);
+				parent->mRight = buildFromList(nodelist, parent, aabb);
+			}
+			else
+			{
+				OGRE_EXCEPT(Exception::ERR_INTERNAL_ERROR,
+					"SNAFU while inserting KdRenderable into KdTree.",
+					"KdTree::recInsert" );
+			}
+		}
+	}
+
+	// compute both AABB then return the requested one.
+	void KdTree::splitBox(const KdTree::Branch& parent, AxisAlignedBox& left, AxisAlignedBox& right)
+	{
+		Vector3 bmin = parent.mAABB.getMinimum();
+		Vector3 bmax = parent.mAABB.getMaximum();
+		Real pos = - parent.mSplitPlane->d;
+		int dim = static_cast<int>(parent.mSplitPlane->normal.dotProduct(Vector3(0,1,2)));
+		// set corners which are the same as parent AABB
+		left.setMinimum(bmin);
+		right.setMaximum(bmax);
+		// modify "inner" corners
+		bmin[dim] = pos;
+		bmax[dim] = pos;
+		// set the corners on the split plane
+		left.setMaximum(bmax);
+		right.setMinimum(bmin);
+	}
+
+	void KdTree::addRendToList(KdTree::Node * node, KdRenderableList& nodelist)
+	{
+		if (node->isLeaf())
+		{
+			KdTree::Leaf * leaf = static_cast<KdTree::Leaf *>(node);
+			KdRenderableList::iterator it  = leaf->mKdRenderables.begin();
+			KdRenderableList::iterator end = leaf->mKdRenderables.end();
+			while (it != end)
+			{
+				nodelist.push_back(*it);
+				it++;
+			}
+		}
+		else
+		{
+			KdTree::Branch * branch = static_cast<KdTree::Branch *>(node);
+			if (branch->mLeft)
+				addRendToList(branch->mLeft, nodelist);
+			if (branch->mRight)
+				addRendToList(branch->mRight, nodelist);
+		}
+	}
+
+	void KdTree::build(KdRenderable * sceneRoot)
+	{
+		// DEBUG
+		//LogManager *lm = LogManager::getSingletonPtr();
+		Timer *timer = Root::getSingleton().getTimer();
+		unsigned long t1, t2, t3, t4;
+		//AxisAlignedBox aabb;
+		
+		// data we want to collect
+		PlaneEventList events;
+		AxisAlignedBox aabb;
+		int nObjects = 0;
+
+		t1 = timer->getMicroseconds(); // DEBUG
+		sceneRoot->computeScene(events, aabb, nObjects);
+		t2 = timer->getMicroseconds(); // DEBUG
+		events.sort();
+		t3 = timer->getMicroseconds(); // DEBUG
+
+		// <DEBUG>
+		//lm->logMessage("# of perfect splits " + StringConverter::toString(events.size()));
+		//PlaneEventList::iterator it;
+		//for (it = events.begin(); it != events.end(); it++)
+		//{
+		//	lm->logMessage(it->print());
+		//}
+		// </DEBUG>
+
+		assert(! aabb.isNull() && "Teh stubid worldAABB iz NULL ... waht now?");
+		// hack to avoid SNAFU with "2-dimensional" scene
+		aabb.merge(aabb.getMaximum()+Vector3(1,1,1));
+		aabb.merge(aabb.getMinimum()+Vector3(-1,-1,-1));
+
+		if (mBuildMethod == KDBM_RECURSIVE)
+			mKdRoot = recBuild(events, nObjects, aabb, 0);
+		else if (mBuildMethod == KDBM_PRIORITYQUEUE)
+			mKdRoot = pqBuild(events, nObjects, aabb, 0);
+		else
+		{
+			OGRE_EXCEPT(Exception::ERR_INVALIDPARAMS, 
+				"Invalid build method for the KdTree.",
+				"KdTree::build");
+			mKdRoot = 0;
+		}
+
+		t4 = timer->getMicroseconds(); // DEBUG
+
+		mBuildLog->logMessage("######## SAH Statistics ########");
+		mBuildLog->logMessage("Time for events build: " + StringConverter::toString(t2 - t1) + "µs");
+		mBuildLog->logMessage("Time for events sort: " + StringConverter::toString(t3 - t2) + "µs");
+		mBuildLog->logMessage("Time for tree build: " + StringConverter::toString(t4 - t3) + "µs");
+		mBuildLog->logMessage("Total time: " + StringConverter::toString(t4 - t1) + "µs");
+		mBuildLog->logMessage("######## SAH Statistics ########");
+		calcCost();
+	}
+
+	KdTree::Node * KdTree::buildFromList(KdRenderableList& nodelist, KdTree::Branch * parent, AxisAlignedBox& aabb)
+	{
+		// data we want to collect
+		PlaneEventList events;
+		AxisAlignedBox nodeaabb;
+		int nObjects = 0;
+
+		KdRenderableList::iterator it = nodelist.begin();
+		KdRenderableList::iterator end = nodelist.end();
+		while (it != end)
+		{
+			(*it)->computeScene(events, nodeaabb, nObjects, false);
+			it++;
+		}
+		events.sort();
+		// HACK
+		if (aabb.isNull())
+		{
+			//LogManager::getSingleton().logMessage("AABB empty, using node AABB.");
+			aabb = nodeaabb;
+		}
+
+		// this must never happen!!
+		//AxisAlignedBox isect = aabb.intersection(nodeaabb);
+		//if (isect.getMinimum() != nodeaabb.getMinimum() || isect.getMaximum() != nodeaabb.getMaximum())
+		//{
+		//	LogManager::getSingleton().logMessage("#+#+#+#+#+ SceneNodes outside of node AABB.");
+		//}
+
+		if (mBuildMethod == KDBM_RECURSIVE)
+			return recBuild(events, nObjects, aabb, parent);
+		else if (mBuildMethod == KDBM_PRIORITYQUEUE)
+			return pqBuild(events, nObjects, aabb, parent);
+		else
+		{
+			OGRE_EXCEPT(Exception::ERR_INVALIDPARAMS, 
+				"Invalid build method for the KdTree.",
+				"KdTree::buildFromList");
+			return 0;
+		}
+	}
+
+	KdTree::Node * KdTree::recBuild(PlaneEventList& events, int nObjects, AxisAlignedBox& aabb, KdTree::Branch * parent)
+	{
+		// determine the depth we are on
+		int level = 0;
+		if (parent)
+		{
+			level = parent->mLevel + 1;
+		}
+
+#ifdef KDTREE_DEBUG_OFF
+		mBuildLog->logMessage("events.size()=" + StringConverter::toString(events.size()));
+#endif
+#ifdef KDTREE_DEBUG_OFF
+		PlaneEventList::iterator xit, xbegin, xend;
+		xbegin = events.begin();
+		xend = events.end();
+		xit = xbegin;
+		while (xit != xend)
+		{
+			mBuildLog->logMessage(xit->print());
+			xit++;
+		}
+#endif
+
+		/************************************************/
+		/**************** BEGIN FINDPLANE ***************/
+		/************************************************/
+		// find optimal split plane and split node accordingly
+		const int dim = 3;
+		int pStart, pOn, pEnd;
+		int nLeft[dim], nPlane[dim], nRight[dim];
+		for (int i = 0; i < dim; i++)
+		{
+			nLeft[i] = 0; nPlane[i] = 0; nRight[i] = nObjects;
+		}
+
+		SplitInfo split, best;
+		best.cost = Math::POS_INFINITY;
+
+
+		PlaneEventList::iterator begin = events.begin();
+		PlaneEventList::iterator end = events.end();
+		PlaneEventList::iterator it = begin;
+		// try all planes to find the best one for the given set of objects
+		while (it != end)
+		{
+			PlaneEventList::iterator p = it;
+			pStart = pOn = pEnd = 0;
+			while (it != end && p->equalsType(*it, PlaneEvent::PET_END))
+			{
+				it++; pEnd++;
+			}
+			while (it != end && p->equalsType(*it, PlaneEvent::PET_ON))
+			{
+				it++; pOn++;
+			}
+			while (it != end && p->equalsType(*it, PlaneEvent::PET_START))
+			{
+				it++; pStart++;
+			}
+			int d = p->getDimension();
+			nPlane[d] = pOn; nRight[d] -= pOn; nRight[d] -= pEnd;
+			p->SAH(aabb, nLeft[d], nPlane[d], nRight[d], split);
+			if (split.cost < best.cost)
+			{
+				best = split;
+			}
+			nLeft[d] += pStart; nLeft[d] += pOn; nPlane[d] = 0;
+		}
+
+#ifdef KDTREE_DEBUG_OFF
+		Real lvol = best.bleft.volume();
+		Real rvol = best.bright.volume();
+
+		if (lvol == 0 || rvol == 0)
+		{
+			mBuildLog->logMessage("WARNING INVALID SPLIT!!!");
+			String side;
+			if (best.side == PlaneEvent::PES_LEFT)
+				side = "left";
+			else
+				side = "right";
+
+			mBuildLog->logMessage("Splitting node on level " + StringConverter::toString(level) + 
+				"\n\tcost=" + StringConverter::toString(best.cost) + " term=" + StringConverter::toString(PlaneEvent::KI*nObjects) +
+				" side=" + side +
+				"\n\tVolume: left=" + StringConverter::toString(lvol) +
+				" right=" + StringConverter::toString(rvol));
+		}
+#endif
+		/************************************************/
+		/**************** BEGIN TERMINATE ***************/
+		/************************************************/
+		// check terminating condition
+		if (best.cost > PlaneEvent::KI*nObjects || level >= mMaxDepth)
+		{
+			// Terminating condition reached, create leaf and add renderables to list
+			KdTree::Leaf * leaf = new KdTree::Leaf(level, aabb, parent);
+			KdRenderable *rend;
+			it = begin;
+			while (it != end)
+			{
+				rend = it->getRenderable();
+				rend->setClassified(false);
+				if (rend->attachTo(leaf, this))
+				{
+					leaf->insert(rend);
+					//LogManager::getSingleton().logMessage("++ Adding SceneNode: " + (static_cast<KdTreeSceneNode *>(rend))->getName());
+				}
+				it++;
+			}
+			return leaf;
+		}
+
+		/************************************************/
+		/**************** BEGIN CLASSIFY ****************/
+		/************************************************/
+		else
+		{
+			PlaneEventList eventsRight, eventsLeft;
+			it = begin;
+			// slightly redundant, since we mark each renderable up to 6 times
+			while (it != end)
+			{
+				it->getRenderable()->setSide(PlaneEvent::PES_BOTH);
+				it->getRenderable()->setClassified(false);
+				it++;
+			}
+			// now classify all renderables. do they belong to the left child, the right child or both?
+			it = begin;
+			while (it != end)
+			{
+				it->classify(best.event, best.side);
+				it++;
+			}
+			// divide the event lists
+			int nLeftS = 0, nRightS = 0, nBothS = 0;
+			it = begin;
+			while (it != end)
+			{
+				// right-only nodes get moved
+				if (it->getRenderable()->getSide() == PlaneEvent::PES_RIGHT)
+				{
+					if (!it->getRenderable()->isClassified())
+					{
+						it->getRenderable()->setClassified(true);
+						nRightS++;
+					}
+
+					eventsRight.push_back(*it);
+				}
+				// both-only nodes get copied
+				// must clip AABBs to child AABB !!!
+				else if (it->getRenderable()->getSide() == PlaneEvent::PES_BOTH)
+				{
+					if (!it->getRenderable()->isClassified())
+					{
+						it->getRenderable()->setClassified(true);
+						nBothS++;
+					}
+
+					//eventsRight.push_back(*it);
+					//eventsLeft.push_back(*it);
+					eventsRight.push_back(it->clip(best.bright, best.event.getDimension()));
+					eventsLeft.push_back(it->clip(best.bleft, best.event.getDimension()));
+				}
+				else
+				{
+					if (!it->getRenderable()->isClassified())
+					{
+						it->getRenderable()->setClassified(true);
+						nLeftS++;
+					}
+					eventsLeft.push_back(*it);
+				}
+				it++;
+			}
+
+#ifdef KDTREE_DEBUG_OFF
+			mBuildLog->logMessage("Splitting on " + best.event.print());
+			mBuildLog->logMessage("eventsLeft.size()=" + StringConverter::toString(eventsLeft.size()));
+			mBuildLog->logMessage("eventsRight.size()=" + StringConverter::toString(eventsRight.size()));
+#endif
+			KdTree::Branch * branch = new KdTree::Branch(level, aabb, parent, best.event.getSplitPlane(), best.side);
+
+			// now create the child nodes and continue recursion
+			if (eventsLeft.size() > 0)
+			{
+				branch->mLeft = recBuild(eventsLeft, nLeftS + nBothS, best.bleft, branch);
+			}
+			if (eventsRight.size() > 0)
+			{
+				branch->mRight = recBuild(eventsRight, nBothS + nRightS, best.bright, branch);
+			}
+
+			//assert(branch->mRight || branch->mLeft);
+
+			return branch;
+		}
+	}
+
+	KdTree::Node * KdTree::pqBuild(PlaneEventList& events, int nObjects, AxisAlignedBox& aabb, KdTree::Branch * parent)
+	{
+		SplitCandidatePQ pqueue;
+		Real globalTreeCost;
+		Real globalSA;
+
+		KdTree::Node * newNode = 0, * topNode = 0;
+		// init global tree cost
+		globalTreeCost = PlaneEvent::KI * nObjects;
+		globalSA = PlaneEvent::surfaceArea(aabb);
+
+		PlaneEventList * e = new PlaneEventList(events);
+
+		// inital split candidate
+		SplitInfo * best = pqFindPlane(e, nObjects, aabb, globalSA);
+		SplitCandidate splitcandidate(e, nObjects, aabb, parent, globalTreeCost, globalTreeCost - best->cost, best, PlaneEvent::PES_BOTH);
+		pqueue.push(splitcandidate);
+
+#ifdef KDTREE_DEBUG_OFF
+		//mBuildLog->logMessage("best.pevent=" + best->event.print() + 
+		//	" events.size()=" + StringConverter::toString(events.size()));
+		mBuildLog->logMessage("New split on " + splitcandidate.print());
+#endif
+
+
+		/*** BEGIN ITERATIVE BUILD ***/
+		while (!pqueue.empty())
+		{
+			SplitCandidate sc = pqueue.top();
+			pqueue.pop();
+
+			// determine the depth we are on
+			int level = 0;
+			if (sc.parent)
+			{
+				level = sc.parent->mLevel + 1;
+			}
+
+#ifdef KDTREE_DEBUG_OFF
+			//mBuildLog->logMessage("Splitting on " + sc.best->event.print() +
+			//	" sc.events.size()=" + StringConverter::toString(sc.events->size()));
+			mBuildLog->logMessage("Splitting on " + sc.print());
+#endif
+
+			/************************************************/
+			/**************** BEGIN TERMINATE ***************/
+			/************************************************/
+			// check terminating condition
+			//if (best.cost > PlaneEvent::KI*sc.nObjects || level >= mMaxDepth)
+			if (sc.decrease < 0.0 || level >= mMaxDepth)
+			{
+				// Terminating condition reached, create leaf and add renderables to list
+				KdTree::Leaf * leaf = new KdTree::Leaf(level, sc.aabb, sc.parent);
+				KdRenderable *rend;
+				PlaneEventList::iterator begin = sc.events->begin();
+				PlaneEventList::iterator end = sc.events->end();
+				PlaneEventList::iterator it = begin;
+				while (it != end)
+				{
+					rend = it->getRenderable();
+					rend->setClassified(false);
+					if (rend->attachTo(leaf, this))
+					{
+						leaf->insert(rend);
+						//LogManager::getSingleton().logMessage("++ Adding SceneNode: " + (static_cast<KdTreeSceneNode *>(rend))->getName());
+					}
+					it++;
+				}
+				newNode = leaf;
+				if (!topNode)
+					topNode = leaf;
+			}
+
+			/************************************************/
+			/**************** BEGIN CLASSIFY ****************/
+			/************************************************/
+			else
+			{
+				PlaneEventList * eventsLeft = new PlaneEventList();
+				PlaneEventList * eventsRight = new PlaneEventList();
+				PlaneEventList::iterator begin = sc.events->begin();
+				PlaneEventList::iterator end = sc.events->end();
+				PlaneEventList::iterator it = begin;
+				// slightly redundant, since we mark each renderable up to 6 times
+				while (it != end)
+				{
+#ifdef KDTREE_DEBUG_OFF
+					mBuildLog->logMessage(it->print());
+#endif
+					it->getRenderable()->setSide(PlaneEvent::PES_BOTH);
+					it->getRenderable()->setClassified(false);
+					it++;
+				}
+				// now classify all renderables. do they belong to the left child, the right child or both?
+#ifdef KDTREE_DEBUG_OFF
+				bool bla = true;
+				it = begin;
+				while (it != end)
+				{
+					it->classify(sc.best->event, sc.best->side);
+					if (*it == sc.best->event)
+					{
+						mBuildLog->logMessage("YEEPEE classified against valid event");
+						bla = false;
+					}
+					it++;
+				}
+				if (bla)
+					mBuildLog->logMessage("FUCKIT! Invalid classification");
+#else
+				it = begin;
+				while (it != end)
+				{
+					it->classify(sc.best->event, sc.best->side);
+					it++;
+				}
+#endif
+
+
+				// divide the event lists
+				int nLeftS = 0, nRightS = 0, nBothS = 0;
+				it = begin;
+				while (it != end)
+				{
+					if (it->getRenderable()->getSide() == PlaneEvent::PES_RIGHT)
+					{
+						if (!it->getRenderable()->isClassified())
+						{
+							it->getRenderable()->setClassified(true);
+							nRightS++;
+						}
+
+						eventsRight->push_back(*it);
+					}
+					else if (it->getRenderable()->getSide() == PlaneEvent::PES_BOTH)
+					{
+						if (!it->getRenderable()->isClassified())
+						{
+							it->getRenderable()->setClassified(true);
+							nBothS++;
+						}
+
+						eventsRight->push_back(it->clip(sc.best->bright, sc.best->event.getDimension()));
+						eventsLeft->push_back(it->clip(sc.best->bleft, sc.best->event.getDimension()));
+					}
+					else
+					{
+						if (!it->getRenderable()->isClassified())
+						{
+							it->getRenderable()->setClassified(true);
+							nLeftS++;
+						}
+						eventsLeft->push_back(*it);
+					}
+					it++;
+				}
+
+#ifdef KDTREE_DEBUG_OFF
+				mBuildLog->logMessage("#### Splitting node on level " + StringConverter::toString(level));
+				Plane * vplane;
+				int count = 0;
+				PlaneEventList::iterator vit, vbegin, vend;
+				vbegin = eventsLeft->begin();
+				vend = eventsLeft->end();
+				vit = vbegin;
+				while (vit != vend)
+				{
+					vplane = vit->getSplitPlane();
+					if (!sc.best.bleft.intersects(*vplane))
+					{
+						mBuildLog->logMessage("Invalid event classification! Plane: " + 
+						StringConverter::toString(vplane->normal) + ", " + StringConverter::toString(-vplane->d) +
+						" Box: |" + StringConverter::toString(sc.best.bleft.getMinimum()) + "|" +
+						StringConverter::toString(sc.best.bleft.getMaximum()) + "|");
+						count++;
+					}
+					OGRE_DELETE(vplane);
+					vit++;
+				}
+				mBuildLog->logMessage("@@@@ Number of invalid events on the left: " + 
+					StringConverter::toString(count) +
+					" Number of events on both sides: " + StringConverter::toString(nBothS));
+				count = 0;
+				vbegin = eventsRight->begin();
+				vend = eventsRight->end();
+				vit = vbegin;
+				while (vit != vend)
+				{
+					vplane = vit->getSplitPlane();
+					if (!sc.best.bright.intersects(*vplane))
+					{
+						mBuildLog->logMessage("Invalid event classification! Plane: " + 
+						StringConverter::toString(vplane->normal) + ", " + StringConverter::toString(-vplane->d) +
+						" Box: |" + StringConverter::toString(sc.best.bright.getMinimum()) + "|" +
+						StringConverter::toString(sc.best.bright.getMaximum()) + "|");
+						count++;
+					}
+					OGRE_DELETE(vplane);
+					vit++;
+				}
+				mBuildLog->logMessage("@@@@ Number of invalid events on the right: " + 
+					StringConverter::toString(count) +
+					" Number of events on both sides: " + StringConverter::toString(nBothS));
+#endif
+
+				KdTree::Branch * branch = 
+					new KdTree::Branch(level, sc.aabb, sc.parent, sc.best->event.getSplitPlane(), sc.best->side);
+
+				//Real decr = (PlaneEvent::surfaceArea(sc.aabb)/globalSA*PlaneEvent::KI*sc.nObjects) - sc.best.cost;
+				globalTreeCost -= sc.decrease;
+
+				//mBuildLog->logMessage("Splitting, cost is now " + StringConverter::toString(globalTreeCost) + "");
+
+				// now create the child nodes and continue recursion
+				if (eventsLeft->size() > 0)
+				{
+					best = pqFindPlane(eventsLeft, nLeftS + nBothS, sc.best->bleft, globalSA);
+					Real old = PlaneEvent::surfaceArea(sc.best->bleft)/globalSA*PlaneEvent::KI*(nLeftS + nBothS);
+					SplitCandidate scleft(eventsLeft, nLeftS + nBothS, sc.best->bleft, 
+						branch, old, old - best->cost, best, PlaneEvent::PES_LEFT);
+					pqueue.push(scleft);
+
+#ifdef KDTREE_DEBUG_OFF
+					//mBuildLog->logMessage("best.pevent: " + best->event.print() + 
+					//	" eventsLeft.size()=" + StringConverter::toString(eventsLeft->size()));
+					mBuildLog->logMessage("New split on " + scleft.print());
+					Plane * plane = best->event.getSplitPlane();
+					if (!sc.best->bleft.intersects(*plane))
+					{
+						mBuildLog->logMessage("Best plane outside parent box on level " + 
+							StringConverter::toString(level));
+					}
+					OGRE_DELETE(plane);
+#endif
+				}
+				if (eventsRight->size() > 0)
+				{
+					best = pqFindPlane(eventsRight, nBothS + nRightS, sc.best->bright, globalSA);
+					Real old = PlaneEvent::surfaceArea(sc.best->bright)/globalSA*PlaneEvent::KI*(nBothS + nRightS);
+					SplitCandidate scright(eventsRight, nBothS + nRightS, sc.best->bright, 
+						branch, old, old - best->cost, best, PlaneEvent::PES_RIGHT);
+					pqueue.push(scright);
+
+#ifdef KDTREE_DEBUG_OFF
+					//mBuildLog->logMessage("best.pevent: " + best->event.print() + 
+					//	" eventsRight.size()=" + StringConverter::toString(eventsRight->size()));
+					mBuildLog->logMessage("New split on " + scright.print());
+					Plane * plane = best->event.getSplitPlane();
+					if (!sc.best->bright.intersects(*plane))
+					{
+						mBuildLog->logMessage("Best plane outside parent box on level " + 
+							StringConverter::toString(level));
+					}
+					OGRE_DELETE(plane);
+#endif
+				}
+
+				newNode = branch;
+				if (!topNode)
+					topNode = branch;
+			}
+
+			// attach new node to parent
+			if (sc.parent)
+			{
+				if (sc.side == PlaneEvent::PES_LEFT)
+				{
+					sc.parent->mLeft = newNode;
+				}
+				else if (sc.side == PlaneEvent::PES_RIGHT)
+				{
+					sc.parent->mRight = newNode;
+				}
+				else
+				{
+					OGRE_EXCEPT(Exception::ERR_INTERNAL_ERROR,
+						"PQBUILD SNAFU - CHILD I AM NOT LEFT NOR RIGHT","KdTree::pqBuild");
+				}
+			}
+
+			//cleanup
+			OGRE_DELETE(sc.events);
+			OGRE_DELETE(sc.best);
+		}
+		mBuildLog->logMessage("Cost after PQBUILD " + StringConverter::toString(globalTreeCost));
+		return topNode;
+	}
+
+	SplitInfo * KdTree::pqFindPlane(PlaneEventList * events, int nObjects, AxisAlignedBox& aabb, Real globalSA)
+	{
+		static const int dim = 3;
+		int pStart, pOn, pEnd;
+		int nLeft[dim], nPlane[dim], nRight[dim];
+		for (int i = 0; i < dim; i++)
+		{
+			nLeft[i] = 0; nPlane[i] = 0; nRight[i] = nObjects;
+		}
+
+		SplitInfo split, best;
+		best.cost = Math::POS_INFINITY;
+
+		Real parentSA = PlaneEvent::surfaceArea(aabb);
+
+		PlaneEventList::iterator begin = events->begin();
+		PlaneEventList::iterator end = events->end();
+		PlaneEventList::iterator it = begin;
+		// try all planes to find the best one for the given set of objects
+		while (it != end)
+		{
+			PlaneEventList::iterator p = it;
+			pStart = pOn = pEnd = 0;
+			while (it != end && p->equalsType(*it, PlaneEvent::PET_END))
+			{
+				it++; pEnd++;
+			}
+			while (it != end && p->equalsType(*it, PlaneEvent::PET_ON))
+			{
+				it++; pOn++;
+			}
+			while (it != end && p->equalsType(*it, PlaneEvent::PET_START))
+			{
+				it++; pStart++;
+			}
+			int d = p->getDimension();
+			nPlane[d] = pOn; nRight[d] -= pOn; nRight[d] -= pEnd;
+			p->pqSAH(globalSA, parentSA, nLeft[d], nPlane[d], nRight[d], aabb, split);
+			if (split.cost < best.cost)
+			{
+				best = split;
+			}
+			nLeft[d] += pStart; nLeft[d] += pOn; nPlane[d] = 0;
+		}
+		return new SplitInfo(best);
+	}
+
+	void KdTree::queueVisibleObjects(Camera* cam, RenderQueue* queue, bool onlyShadowCasters, bool showBoxes)
+	{
+		if (mKdRoot)
+			recQueueVisibleObjects(mKdRoot, Root::getSingleton().getCurrentFrameNumber(), cam, queue, onlyShadowCasters, showBoxes);
+	}
+
+	void KdTree::recQueueVisibleObjects(KdTree::Node * node, unsigned long currentFrame, Camera* cam, RenderQueue* queue, bool onlyShadowCasters, bool showBoxes)
+	{
+		// test visibility
+		if (cam->isVisible(node->mAABB))
+		{
+#ifdef KDTREE_DEBUG
+			WireBoundingBox * wbb = 0;
+			if (showBoxes)
+				wbb = node->getWireBoundingBox();
+#endif
+
+			if (node->isLeaf())
+			{
+				KdTree::Leaf * leaf = static_cast<KdTree::Leaf *>(node);
+				KdRenderableList::iterator it  = leaf->mKdRenderables.begin();
+				KdRenderableList::iterator end = leaf->mKdRenderables.end();
+				while (it != end)
+				{			
+					if (!(*it)->isQueued(currentFrame, cam))
+					{
+						(*it)->queueObjects(cam, queue, onlyShadowCasters);
+					}
+					it++;
+				}
+#ifdef KDTREE_DEBUG
+				if (wbb)
+					queue->addRenderable(wbb);
+#else
+				if (showBoxes)
+					queue->addRenderable(leaf->getWireBoundingBox());
+#endif
+			}
+			else
+			{
+				KdTree::Branch * branch = static_cast<KdTree::Branch *>(node);
+#ifdef KDTREE_DEBUG
+				if (wbb)
+					queue->addRenderable(wbb);
+#else
+				if (showBoxes)
+					queue->addRenderable(branch->getWireBoundingBox());
+#endif
+
+				if (branch->mLeft)
+					recQueueVisibleObjects(branch->mLeft, currentFrame, cam, queue, onlyShadowCasters, showBoxes);
+				if (branch->mRight)
+					recQueueVisibleObjects(branch->mRight, currentFrame, cam, queue, onlyShadowCasters, showBoxes);
+			}
+		}
+	}
+
+	void KdTree::dump()
+	{
+		LogManager::getSingleton().logMessage("#@#@#@#@ Dumping KdTree #@#@#@#@");
+		if (mKdRoot)
+			dump(mKdRoot);
+	}
+
+	void KdTree::dump(KdTree::Node * node)
+	{
+		LogManager * log = LogManager::getSingletonPtr();
+		KdTreeSceneNode * scenenode;
+		String pad;
+		int p;
+		
+		pad = "";
+		for (p = 0; p < node->mLevel; p++)
+		{
+			pad += " ";
+		}
+
+		if (node->isLeaf())
+		{
+			KdTree::Leaf * leaf = static_cast<KdTree::Leaf *>(node);
+			KdRenderableList::iterator it  = leaf->mKdRenderables.begin();
+			KdRenderableList::iterator end = leaf->mKdRenderables.end();
+			while (it != end)
+			{
+				scenenode = dynamic_cast<KdTreeSceneNode *>(*it);
+				log->logMessage(pad + "# Leaf   level " + StringConverter::toString(node->mLevel) + 
+					" SceneNode " + scenenode->getName());
+				log->logMessage(pad + "## Objects: " + scenenode->dumpToString());
+				it++;
+			}
+		}
+		else
+		{
+			KdTree::Branch * branch = static_cast<KdTree::Branch *>(node);
+			if (branch->mLeft)
+			{
+				log->logMessage(pad + "# Branch level " + StringConverter::toString(node->mLevel) + " Left Child");
+				dump(branch->mLeft);
+			}
+			if (branch->mRight)
+			{
+				log->logMessage(pad + "# Branch level " + StringConverter::toString(node->mLevel) + " Right Child");
+				dump(branch->mRight);
+			}
+		}
+	}
+
+	void KdTree::calcCost()
+	{
+		Real cost = 0;
+		if (mKdRoot)
+			cost = calcCost(mKdRoot, PlaneEvent::surfaceArea(mKdRoot->mAABB));
+
+		//LogManager::getSingleton().logMessage("#@#@#@ One KdTree: " + StringConverter::toString(cost));
+		mBuildLog->logMessage("#@#@#@ One KdTree: " + StringConverter::toString(cost));
+	}
+
+	Real KdTree::calcCost(KdTree::Node * node, Real vs)
+	{
+		if (node == 0)
+			return 0.0;
+
+		if (node->isLeaf())
+		{
+			KdTree::Leaf * leaf = static_cast<KdTree::Leaf *>(node);
+			return (PlaneEvent::surfaceArea(node->mAABB)/vs)*PlaneEvent::KI*leaf->mKdRenderables.size();
+		}
+		else
+		{
+			KdTree::Branch * branch = static_cast<KdTree::Branch *>(node);
+			return (PlaneEvent::surfaceArea(node->mAABB)/vs)*PlaneEvent::KT + calcCost(branch->mLeft, vs) + calcCost(branch->mRight, vs);
+		}
+	}
+
+	KdTree::Leaf::~Leaf()
+	{
+		// detach all scene nodes in the case that we are rebuilding
+		// the tree but not the scene
+		KdRenderableList::iterator it = mKdRenderables.begin();
+		KdRenderableList::iterator end = mKdRenderables.end();
+		while (it != end)
+		{
+			(*it)->detachFrom(this);
+			it++;
+		}
+		mKdRenderables.clear();
+	}
+}
Index: GTP/trunk/Lib/Vis/OnlineCullingCHC/OGRE/misc/OgreKdTreeSceneManager.def
===================================================================
--- GTP/trunk/Lib/Vis/OnlineCullingCHC/OGRE/misc/OgreKdTreeSceneManager.def	(revision 1163)
+++ GTP/trunk/Lib/Vis/OnlineCullingCHC/OGRE/misc/OgreKdTreeSceneManager.def	(revision 1163)
@@ -0,0 +1,5 @@
+LIBRARY Plugin_KdTreeSceneManager
+EXPORTS	
+	dllStartPlugin
+	dllShutdownPlugin
+	dllStopPlugin
