/*
-----------------------------------------------------------------------------
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 = KDBRANCHPTR_CAST(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 = KDBRANCHPTR_CAST(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 = KDLEAFPTR_CAST(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 = KDBRANCHPTR_CAST(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, 
		KdTree::RenderMethod renderMethod, bool showBoxes)
	{
		// for now only recurse or stack render methods
		if (mKdRoot)
		{
			//if (renderMethod == KdTree::KDRM_STACK)
			//{
			//	stackQueueVisibleObjects(mKdRoot, Root::getSingleton().getCurrentFrameNumber(), 
			//		cam, queue, onlyShadowCasters, showBoxes);
			//}
			//else
			//{
				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 = KDLEAFPTR_CAST(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 = KDBRANCHPTR_CAST(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::stackQueueVisibleObjects(KdTree::Node * root, unsigned long currentFrame, Camera* cam, RenderQueue* queue, bool onlyShadowCasters, bool showBoxes)
	{
		static NodeStack nodestack;
		if (!nodestack.empty()) OGRE_EXCEPT(Exception::ERR_INTERNAL_ERROR, 
			"Stuff left in stack from previos frame", "KdTree::stackQueueVisibleObjects");

		nodestack.push(root);

		while (!nodestack.empty())
		{
			KdTree::Node * node = nodestack.top();
			nodestack.pop();

			// 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 = KDLEAFPTR_CAST(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 = KDBRANCHPTR_CAST(node);
	#ifdef KDTREE_DEBUG
					if (wbb)
						queue->addRenderable(wbb);
	#else
					if (showBoxes)
						queue->addRenderable(branch->getWireBoundingBox());
	#endif

					if (branch->mLeft)
						nodestack.push(branch->mLeft);
					if (branch->mRight)
						nodestack.push(branch->mRight);
				}
			}
		}
	}

	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 = KDLEAFPTR_CAST(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 = KDBRANCHPTR_CAST(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 = KDLEAFPTR_CAST(node);
			return (PlaneEvent::surfaceArea(node->mAABB)/vs)*PlaneEvent::KI*leaf->mKdRenderables.size();
		}
		else
		{
			KdTree::Branch * branch = KDBRANCHPTR_CAST(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();
	}

	// update the world aabb based on the contained geometry
	void KdTree::Leaf::_updateBounds()
	{
		// reset box
		mWorldAABB.setNull();

		// merge boxes from attached geometry
		KdRenderableList::iterator it = mKdRenderables.begin();
		KdRenderableList::iterator end = mKdRenderables.end();
		while (it != end)
		{
			mWorldAABB.merge((*it)->getBoundingBox());
			it++;
		}

		// update parent recursively
		if (mParent)
			mParent->_updateBounds();
	}
} // namespace Ogre