/// <summary>
/// This class stores the root of an octree spatial subdivision. It serves as
/// an encapsulator to create, update, render and manipulate the octree. 
/// </summary>
public class Octree : SceneItem
{
	/// <summary>
	/// primitive shader for drawing the octree boxes
	/// </summary>
	protected ShaderCustom primitiveShader;
	/// <summary>
	/// the root (top) level node of the octree
	/// </summary>
	protected OctreeNode root;
	/// <summary>
	/// the hierarchical depth of octree
	/// nodes to draw during a render call
	/// </summary>
	protected uint treeDisplayDepth;
	/// <summary>
	/// the depth of the octree
	/// </summary>
	protected uint treeDepth;
	/// <summary>
	/// the volume of the smallest
	/// leaf nodes in the tree
	/// </summary>
	protected float leafVolume;
	/// <summary>
	/// the color used to render the
	/// boundaries of the octree
	/// </summary>
	protected Color treeColor;
	/// <summary>
	/// the number of leaf nodes in the tree
	/// </summary>
	protected int leafNodeCount;

	/*
	 * CONSTRUCTORS
	 */
	/// <summary>
	/// constructor for an octree with parameters for controlling automatic subdivision
	/// </summary>
	/// <param name="newGame">the game object</param>
	/// <param name="newName">a name for this octree</param>
	/// <param name="box">the top level box that contains the entire tree</param>
	/// <param name="maxDepth">the maximum depth to divide the tree</param>
	/// <param name="minLeafVolume">a threshold that will prevent the trees leaf nodes
	/// from being subdivided smaller than this volume, or zero to ignore this feature.</param>
	public Octree(TwelveCylinderGame newGame, string newName, Bounds box, uint maxDepth, float minLeafVolume)
		: base(newName, NodeType.SceneItem, true, newGame)
	{
		DateTime start = DateTime.Now;
		leafNodeCount = 0;
		//determine maximum tree depth
		treeDepth = GetNewMaxDepth(box.Volume, minLeafVolume, maxDepth);

		root = new OctreeNode(this, null, curGame, box, 0, treeDepth);
		init();
		DateTime end = DateTime.Now;
		//printTreeData(end - start);
	}

	//additional constructors omitted

	/// <summary>
	/// init common parameters for the tree
	/// </summary>
	private void init()
	{
		treeColor = Color.White;
		this.Visible = false;
		treeDisplayDepth = 0;
		if (curGame != null)
			primitiveShader = curGame.ShaderManager.Primitive3DShader;
	}

	/// <summary>
	/// prints info about the new octree to the log file
	/// </summary>
	/// <param name="time">the time span used to create the tree definition</param>
	protected virtual void printTreeData(TimeSpan time)
	{
		curGame.Log(this.Name + "   Max depth: " + treeDepth);
		curGame.Log("Creation Time: " + time.TotalMilliseconds + " ms");
		curGame.Log("leaf volume: " + leafVolume);
	}

	public override void unload(bool disposeResources)
	{
		base.unload(disposeResources);

		if (root != null)
			root.unload(disposeResources);
		if (primitiveShader != null)
			primitiveShader.unload(disposeResources);
		root = null;
		primitiveShader = null;
	}

	/*
	 * METHODS
	 */
	/// <summary>
	/// callback to add a leaf node to this tree
	/// </summary>
	/// <returns></returns>
	public virtual int addLeafNode(OctreeNode leaf)
	{
		return leafNodeCount++;
	}

	/// <summary>
	/// gets a list of octree leaf nodes which intersect with 
	/// the specified bounding box
	/// </summary>
	/// <param name="b">a bounding box to test</param>
	/// <returns>a list of octree leaf nodes</returns>
	public virtual List<OctreeNode> GetIntersectedLeafNodes(Bounds b)
	{
		List<OctreeNode> leafNodes = new List<OctreeNode>(12);
		root.GetIntersectedLeafNodes(b, ref leafNodes);
		return leafNodes;
	}

	/// <summary>
	/// Recursive function to find the octree leaf node
	/// that contains the specified world position.
	/// </summary>
	/// <param name="worldPos">a world space coordinate</param>
	/// <returns>the containing leaf node</returns>
	public virtual OctreeNode GetContainingLeaf(Vector3 worldPos)
	{
		return root.getContainingLeaf(worldPos);
	}

	/// <summary>
	/// Calculates the maximum tree depth that should be subdivied to.
	/// This is calculated from a minimum leaf volume and an arbitrary
	/// maximum depth value.
	/// </summary>
	/// <param name="topVolume">the volume of the top level bounds of the tree</param>
	/// <param name="minLeafVolume">the minimum leaf volume</param>
	/// <param name="maxDepth">the maximum depth of the tree</param>
	/// <returns>the new maximum depth of the tree</returns>
	protected uint GetNewMaxDepth(float topVolume, float minLeafVolume, uint maxDepth)
	{
		uint newTreeDepth = 0;
		float newLeafVolume = topVolume;
		if (minLeafVolume > 0)
		{
			while (true)
			{
				newLeafVolume /= 8;
				newTreeDepth++;

				//reached arbitrary maximum
				if(newTreeDepth == maxDepth)
					break;
				if (newLeafVolume < minLeafVolume)
				{
					//back one step
					newLeafVolume *= 8;
					newTreeDepth--;
					break;
				}
			}
		}
		else
		{
			//negative volume indicates to ignore
			newTreeDepth = maxDepth;
		}
		//limit to 0
		if(newTreeDepth < 0)
			newTreeDepth = 0;

		return newTreeDepth;
	}

	/// <summary>
	/// calculates the tree depth and leaf volume
	/// properties from the current tree hierarchy
	/// </summary>
	protected virtual void updateTreeData()
	{
		treeDepth = root.getMaximumDepth();
		leafVolume = root.Box.Volume / (float)Math.Pow(OctreeNode.NUM_TREE_CHILDREN, treeDepth);
	}

	//encapsulators omitted

	/*
	 * UPDATE & RENDER
	 */
	public override void update(GameTime gameTime, TwelveCylinder.GameCamera.Camera curCam, Matrix projMatrix, Matrix viewProj)
	{
		base.update(gameTime, curCam, projMatrix, viewProj);
		//update shader if visibility is on
		if (this.Visible)
			primitiveShader.WVP = viewProj;
		//update the tree nodes
		root.update(gameTime, curCam, projMatrix, viewProj);
	}

	/// <summary>
	/// renders the bounds of the branches of this octree
	/// </summary>
	/// <param name="rm"></param>
	public override void Render(TwelveCylinder.StageManagement.RenderMode rm)
	{
		if (curGame == null || primitiveShader == null ||
								!primitiveShader.EffectLoaded)
			return; //not capable of rendering

		//sets vertex decleration to VertexPositionColor
		curGame.beginPrimitiveVertexDecleration();

		//use single pass primitive shader
		primitiveShader.Begin();
		primitiveShader.BeginPass(0);

		RenderTreeBounds();

		primitiveShader.EndPass(0);
		primitiveShader.End();
	}

	protected virtual void RenderTreeBounds()
	{
		root.DrawTreeBounds(treeDisplayDepth);
	}
}