context: using System;
  using UnityEngine;
  using System.Collections.Generic;
  using Pathfinding;
  using Pathfinding.Voxels;
  
  namespace Pathfinding
  {
  	/** Axis Aligned Bounding Box Tree.
  	 * Holds a bounding box tree of triangles.\n
  	 * \b Performance: Insertion - Practically O(1) - About 0.003 ms
  	 * \astarpro
  	 */
  	public class RecastBBTree
  	{
  		public RecastBBTreeBox root;
  		
  		/*public NNInfo Query (Vector3 p) {
  			
  			RecastBBTreeBox c = root;
  			
  			if (c == null) {
  				return new NNInfo();
  			}
  			
  			NNInfo nnInfo = new NNInfo ();
  			
  			SearchBox (c,p, constraint, ref nnInfo);
  			
  			nnInfo.UpdateInfo ();
  			
  			return nnInfo;
  		}*/
  		
  		/** Queries the tree for the best node, searching within a circle around \a p with the specified radius.
  		  * Will fill in both the constrained node and the not constrained node in the NNInfo.
  		  * 
  		  * \see QueryClosest
  		  */
  		/*public NNInfo QueryCircle (Vector3 p, float radius) {
  			BBTreeBox c = root;
  			
  			if (c == null) {
  				return new NNInfo();
  			}
  			
  #if ASTARDEBUG
  			Vector3 prev = new Vector3 (1,0,0)*radius+p;
  			for (double i=0;i< Math.PI*2; i += Math.PI/50.0) {
  				Vector3 cpos = new Vector3 ((float)Math.Cos (i),0,(float)Math.Sin (i))*radius+p;
  				Debug.DrawLine (prev,cpos,Color.yellow);
  				prev = cpos;
  			}
  #endif
  			
  			NNInfo nnInfo = new NNInfo (null);
  			
  			SearchBoxCircle (c,p, radius, constraint, ref nnInfo);
  			
  			nnInfo.UpdateInfo ();
  			
  			return nnInfo;
  		}*/
  		
  		/** Queries the tree for the closest node to \a p constrained by the NNConstraint.
  		  * Note that this function will, unlike QueryCircle, only fill in the constrained node.
  		  * If you want a node not constrained by any NNConstraint, do an additional search with constraint = NNConstraint.None
  		  * 
  		  * \see QueryCircle
  		  */
  		/*public NNInfo QueryClosest (Vector3 p, out float distance) {
  			distance = float.PositiveInfinity;
  			return QueryClosest (p, constraint, ref distance, new NNInfo (null));
  		}*/
  		
  		/** Queries the tree for the closest node to \a p constrained by the NNConstraint trying to improve an existing solution.
  		  * Note that this function will, unlike QueryCircle, only fill in the constrained node.
  		  * If you want a node not constrained by any NNConstraint, do an additional search with constraint = NNConstraint.None
  		  * 
  		  * This search will start from the \a previous NNInfo and improve it if possible.
  		  * Even if the search fails on this call, the solution will never be worse than \a previous.
  		  * 
  		  * 
  		  * \param distance The best distance for the \a previous solution. Will be updated with the best distance
  		  * after this search. Will be positive infinity if no node could be found.
  		  * Set to positive infinity if there was no previous solution.
  		  * 
  		  * 
  		  * \see QueryCircle
  		  */
  		public void QueryInBounds (Rect bounds, List<RecastMeshObj> buffer) {
  			RecastBBTreeBox c = root;
  			
  			if (c == null) return;
  			
  			QueryBoxInBounds (c, bounds, buffer);
  		}
  		
  		public void QueryBoxInBounds (RecastBBTreeBox box, Rect bounds, List<RecastMeshObj> boxes) {
  			
  			if (box.mesh != null) {
  				//Leaf node
  				if (RectIntersectsRect (box.rect,bounds)) {
  					//Update the NNInfo
  					
  #if ASTARDEBUG
  					Debug.DrawLine ((Vector3)box.node.GetVertex(1) + Vector3.up*0.2f,(Vector3)box.node.GetVertex(2) + Vector3.up*0.2f,Color.red);
  					Debug.DrawLine ((Vector3)box.node.GetVertex(0) + Vector3.up*0.2f,(Vector3)box.node.GetVertex(1) + Vector3.up*0.2f,Color.red);
  					Debug.DrawLine ((Vector3)box.node.GetVertex(2) + Vector3.up*0.2f,(Vector3)box.node.GetVertex(0) + Vector3.up*0.2f,Color.red);
  #endif
  					
  					boxes.Add (box.mesh);
  				} else {
  #if ASTARDEBUG
  					Debug.DrawLine ((Vector3)box.node.GetVertex(0),(Vector3)box.node.GetVertex(1),Color.blue);
  					Debug.DrawLine ((Vector3)box.node.GetVertex(1),(Vector3)box.node.GetVertex(2),Color.blue);
  					Debug.DrawLine ((Vector3)box.node.GetVertex(2),(Vector3)box.node.GetVertex(0),Color.blue);
  #endif
  				}
  			} else {
  				
  	#if ASTARDEBUG
  				Debug.DrawLine (new Vector3 (box.rect.xMin,0,box.rect.yMin),new Vector3 (box.rect.xMax,0,box.rect.yMin),Color.white);
  				Debug.DrawLine (new Vector3 (box.rect.xMin,0,box.rect.yMax),new Vector3 (box.rect.xMax,0,box.rect.yMax),Color.white);
  				Debug.DrawLine (new Vector3 (box.rect.xMin,0,box.rect.yMin),new Vector3 (box.rect.xMin,0,box.rect.yMax),Color.white);
  				Debug.DrawLine (new Vector3 (box.rect.xMax,0,box.rect.yMin),new Vector3 (box.rect.xMax,0,box.rect.yMax),Color.white);
  	#endif
  				
  				//Search children
  				if (RectIntersectsRect (box.c1.rect,bounds)) {
  					QueryBoxInBounds (box.c1, bounds, boxes);
  				}
  				
  				if (RectIntersectsRect (box.c2.rect,bounds)) {
  					QueryBoxInBounds (box.c2, bounds, boxes);
  				}
  			}
  		}
  		
  		/*public void SearchBoxCircle (BBTreeBox box, Vector3 p, float radius, NNConstraint constraint, ref NNInfo nnInfo) {//, int intendentLevel = 0) {
  			
  			if (box.node != null) {
  				//Leaf node
  				if (NodeIntersectsCircle (box.node,p,radius)) {
  					//Update the NNInfo
  					
  #if ASTARDEBUG
  					Debug.DrawLine ((Vector3)box.node.GetVertex(0),(Vector3)box.node.GetVertex(1),Color.red);
  					Debug.DrawLine ((Vector3)box.node.GetVertex(1),(Vector3)box.node.GetVertex(2),Color.red);
  					Debug.DrawLine ((Vector3)box.node.GetVertex(2),(Vector3)box.node.GetVertex(0),Color.red);
  #endif
  					
  					Vector3 closest = box.node.ClosestPointOnNode (p);//NavMeshGraph.ClosestPointOnNode (box.node,graph.vertices,p);
  					float dist = (closest-p).sqrMagnitude;
  					
  					if (nnInfo.node == null) {
  						nnInfo.node = box.node;
  						nnInfo.clampedPosition = closest;
  					} else if (dist < (nnInfo.clampedPosition - p).sqrMagnitude) {
  						nnInfo.node = box.node;
  						nnInfo.clampedPosition = closest;
  					}
  					if (constraint.Suitable (box.node)) {
  						if (nnInfo.constrainedNode == null) {
  							nnInfo.constrainedNode = box.node;
  							nnInfo.constClampedPosition = closest;
  						} else if (dist < (nnInfo.constClampedPosition - p).sqrMagnitude) {
  							nnInfo.constrainedNode = box.node;
  							nnInfo.constClampedPosition = closest;
  						}
  					}
  				} else {
  #if ASTARDEBUG
  					Debug.DrawLine ((Vector3)box.node.GetVertex(0),(Vector3)box.node.GetVertex(1),Color.blue);
  					Debug.DrawLine ((Vector3)box.node.GetVertex(1),(Vector3)box.node.GetVertex(2),Color.blue);
  					Debug.DrawLine ((Vector3)box.node.GetVertex(2),(Vector3)box.node.GetVertex(0),Color.blue);
  #endif
  				}
  				return;
  			}
  			
  #if ASTARDEBUG
  			Debug.DrawLine (new Vector3 (box.rect.xMin,0,box.rect.yMin),new Vector3 (box.rect.xMax,0,box.rect.yMin),Color.white);
  			Debug.DrawLine (new Vector3 (box.rect.xMin,0,box.rect.yMax),new Vector3 (box.rect.xMax,0,box.rect.yMax),Color.white);
  			Debug.DrawLine (new Vector3 (box.rect.xMin,0,box.rect.yMin),new Vector3 (box.rect.xMin,0,box.rect.yMax),Color.white);
  			Debug.DrawLine (new Vector3 (box.rect.xMax,0,box.rect.yMin),new Vector3 (box.rect.xMax,0,box.rect.yMax),Color.white);
  #endif
  			
  			//Search children
  			if (RectIntersectsCircle (box.c1.rect,p,radius)) {
  				SearchBoxCircle (box.c1,p, radius, ref nnInfo);
  			}
  			
  			if (RectIntersectsCircle (box.c2.rect,p,radius)) {
  				SearchBoxCircle (box.c2,p, radius, ref nnInfo);
  			}
  		}*/
  		
  		/*public void SearchBox (BBTreeBox box, Vector3 p, NNConstraint constraint, ref NNInfo nnInfo) {//, int intendentLevel = 0) {
  			
  
gt: 			if (box.node != null) {