/// <summary>
/// The root of an octree that uses CollisionTreeNode objects instead of OctreeNodes
/// to create spatial organization for optimizing collision detection. 
/// </summary>
public class CollisionTree : Octree
{
	/*
	 * CLASS PROPERTIES
	 */
	/// <summary>
	/// The last recurse id used for element searches.
	/// This is used for preventing duplicates from occuring. 
	/// </summary>
	private uint searchCount;
	/// <summary>
	/// the root node as a collision tree node
	/// </summary>
	CollisionTreeNode collisionRoot;

	/*
	 * CONSTRUCTOR
	 */
	/// <summary>
	/// constructor for a new collision octree
	/// </summary>
	/// <param name="newGame">the game object</param>
	/// <param name="box">the top level collision box that  contains the entire tree</param>
	/// <param name="newElems">the array of collideable elements to be organized by the 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 CollisionTree(TwelveCylinderGame newGame, string newName, Bounds box,
						CollideableElement[] newElems, uint maxDepth, float minLeafVolume)
		: base(newGame, newName, box)
	{
		DateTime start = DateTime.Now;

		//array of all true
		bool[] allTrue = new bool[newElems.Length];
		for (int i = 0; i < allTrue.Length; i++)
			allTrue[i] = true;

		treeDepth = GetNewMaxDepth(box.Volume, minLeafVolume, maxDepth);
		//recursively create tree node hierarchy
		collisionRoot = new CollisionTreeNode(this, null, curGame, box, allTrue, newElems, 0, treeDepth);
		root = collisionRoot;
		//random tree color
		root.TreeColor = curGame.RandomGenerator.GetNextPalletteColor();
		updateTreeData();

		searchCount = 0;

		DateTime end = DateTime.Now;
		//printTreeData(end - start);
	}

	/*
	 * COLLIDEABLE ELEMENT LISTS
	 */
	/// <summary>
	/// adds a new collideable element to the collision tree
	/// </summary>
	/// <param name="newElem">the element to add to the tree</param>
	public void AddElement(CollideableElement newElem)
	{
		collisionRoot.AddElement(newElem);
	}

	/// <summary>
	/// removes the specified collideable element from the collision tree
	/// </summary>
	/// <param name="elem">the element to remove from the tree</param>
	public void RemoveElement(CollideableElement xElem)
	{
		collisionRoot.RemoveElement(xElem);
	}

	/// <summary>
	/// updates which tree nodes the element is in
	/// </summary>
	/// <param name="elem">an element that may already be in the tree</param>
	public void UpdateElement(CollideableElement elem)
	{
		elem.RemoveFromAllNodes();
		collisionRoot.AddElement(elem);
	}

	/// <summary>
	/// gets the collideable elements that intersect
	/// with the specified bounding box
	/// </summary>
	/// <param name="testBox">a box to test for collisions</param>
	/// <param name="elements">the output list of collideable elements</param>
	public void GetElements(Bounds testBox, ref List<CollideableElement> elements)
	{
		collisionRoot.GetElements(testBox, ref elements, searchCount++);
	}

	/// <summary>
	/// gets all collideable elements currently in the tree
	/// </summary>
	/// <param name="elements">the output list of elements</param>
	public void GetAllElements(ref List<CollideableElement> elements)
	{
		collisionRoot.GetAllElements(ref elements, searchCount++);
	}

	/*
	 * BOX INTERSECT
	 */
	/// <summary>
	/// Find the first (if any) collision between the specified moving
	/// collision box and the collideable elements in this tree.
	/// </summary>
	/// <param name=" boxData">the box to check for collisions defined in the world coordinate system</param>
	/// <param name="collisionDistance">output distance from starting position to collision point</param>
	/// <param name="collisionPosition">output position at which the collision occured</param>
	/// <param name="collisionNormal">output normal of the surface that the box collided with</param>
	/// <returns>returns true if an intersection occured</returns>
	public bool BoxIntersect(MovingBoxData boxData, out float collisionDistance,
							out Vector3 collisionPosition, out Vector3 collisionNormal)
	{
		//default output of no interesection
		collisionDistance = boxData.OffsetLength;
		collisionPosition = boxData.WorldEnd;
		collisionNormal = Vector3.Zero;

		//get the list of collideable elements that the box may have collided with
		List<CollideableElement> elems = new List<CollideableElement>();
		collisionRoot.GetElements(boxData.ColliderVolume, ref elems, searchCount++);

		bool collided = false;
		float distance;
		Vector3 position;
		Vector3 normal;

		//check for collision between moving box and collideable elements
		foreach (CollideableElement elem in elems)
		{
			if (elem.BoxIntersect(boxData, out distance, out position, out normal))
			{
				//intersection found
				if (distance < collisionDistance)
				{
					//current intersect distance is less than previous
					collisionDistance = distance;
					collisionPosition = position;
					collisionNormal = normal;
					collided = true;
				}
			}
		}

		return collided;
	}
}