/// <summary>
		/// Determine whether a ray (origin, dir) is intersecting a segment AB.
		/// </summary>
		/// <param name="origin">The origin of the ray.</param>
		/// <param name="dir">The direction of the ray.</param>
		/// <param name="a">The endpoint A of segment AB.</param>
		/// <param name="b">The endpoint B of segment AB.</param>
		/// <param name="t">The parameter t</param>
		/// <returns>A value indicating whether the ray is intersecting with the segment.</returns>
		public static bool RaySegment(Vector3 origin, Vector3 dir, Vector3 a, Vector3 b, out float t)
		{
			//default if not intersectng
			t = 0;

			Vector3 v = b - a;
			Vector3 w = origin - a;

			float d;

			Vector3Extensions.PerpDotXZ(ref dir, ref v, out d);
			d *= -1;
			if (Math.Abs(d) < 1e-6f)
				return false;

			d = 1.0f / d;
			Vector3Extensions.PerpDotXZ(ref v, ref w, out t);
			t *= -d;
			if (t < 0 || t > 1)
				return false;

			float s;
			Vector3Extensions.PerpDotXZ(ref dir, ref w, out s);
			s *= -d;
			if (s < 0 || s > 1)
				return false;

			return true;
		}

		/// <summary>
		/// Rasterizes several triangles at once from an indexed array with per-triangle area flags.
		/// </summary>
		/// <param name="verts">An array of vertices.</param>
		/// <param name="inds">An array of indices.</param>
		/// <param name="vertOffset">An offset into the vertex array.</param>
		/// <param name="vertStride">The number of array elements that make up a vertex. A value of 0 is interpreted as tightly-packed data (one Vector3 per vertex).</param>
		/// <param name="indexOffset">An offset into the index array.</param>
		/// <param name="triCount">The number of triangles to rasterize.</param>
		/// <param name="areas">An array of area flags, one for each triangle.</param>
		public void RasterizeTrianglesIndexedWithAreas(Vector3[] verts, int[] inds, int vertOffset, int vertStride, int indexOffset, int triCount, Area[] areas)
		{
			int indexEnd = triCount * 3 + indexOffset;

			if (verts == null)
				throw new ArgumentNullException("verts");

			if (inds == null)
				throw new ArgumentNullException("inds");

			if (indexEnd > inds.Length)
				throw new ArgumentOutOfRangeException("indexCount", "The specified index offset and length end outside the provided index array.");

			if (vertOffset < 0)
				throw new ArgumentOutOfRangeException("vertOffset", "vertOffset must be greater than or equal to 0.");

			if (vertStride < 0)
				throw new ArgumentOutOfRangeException("vertStride", "vertStride must be greater than or equal to 0.");
			else if (vertStride == 0)
				vertStride = 1;

			if (areas.Length < triCount)
				throw new ArgumentException("There must be at least as many AreaFlags as there are triangles.", "areas");

			for (int i = indexOffset, j = 0; i < indexEnd; i += 3, j++)
			{
				int indA = inds[i] * vertStride + vertOffset;
				int indB = inds[i + 1] * vertStride + vertOffset;
				int indC = inds[i + 2] * vertStride + vertOffset;

				RasterizeTriangle(ref verts[indA], ref verts[indB], ref verts[indC], areas[j]);
			}
		}

		/// <summary>
		/// Initializes a new instance of the <see cref="SharpNav.ContourVertex"/> struct.
		/// </summary>
		/// <param name="vec">The array of X,Y,Z coordinates.</param>
		/// <param name="region">The Region ID.</param>
		public ContourVertex(Vector3 vec, RegionId region)
		{
			this.X = (int)vec.X;
			this.Y = (int)vec.Y;
			this.Z = (int)vec.Z;
			this.RegionId = region;
		}

        protected override void ComponentsCreatedHandler(object sender, EventArgs e)
        {
            base.ComponentsCreatedHandler(sender, e);

            TerrainRenderComponent terrainRenderComponent = Owner.GetComponent<TerrainRenderComponent>(ComponentType.Render);
            if (terrainRenderComponent == null)
                throw new LevelManifestException("TerrainCollisionComponent expect to be accompanied by a TerrainRenderComponent.");

            float[,] heightVals = terrainRenderComponent.Heights;

            XnaVector3 originShift = new XnaVector3(terrainRenderComponent.TerrainAsset.XZScale * (terrainRenderComponent.TerrainAsset.VertexCountAlongXAxis - 1) * 0.5f,
                0.0f,
                terrainRenderComponent.TerrainAsset.XZScale * (terrainRenderComponent.TerrainAsset.VertexCountAlongZAxis - 1) * 0.5f);

            AffineTransform terrainTransform = new BEPUutilities.AffineTransform(
                new BEPUutilities.Vector3(terrainRenderComponent.TerrainAsset.XZScale, 1.0f, terrainRenderComponent.TerrainAsset.XZScale),
                BepuConverter.Convert(mTransformComponent.Orientation),
                BepuConverter.Convert(mTransformComponent.Translation - originShift));

            mSimTerrain = new BepuTerrain(heightVals, terrainTransform);
            mSimTerrain.Material.Bounciness = 0.60f;
            mSimTerrain.Material.StaticFriction = 1.0f;
            mSimTerrain.Material.KineticFriction = 1.0f;
            mSimTerrain.Tag = Owner.Id;
        }

        public virtual float GetCost(Vector3 a, Vector3 b,
			NavPolyId prevRef, NavTile prevTile, NavPoly prevPoly,
			NavPolyId curRef, NavTile curTile, NavPoly curPoly,
			NavPolyId nextRef, NavTile nextTile, NavPoly nextPoly)
        {
            return (a - b).Length() * areaCost[(int)curPoly.Area.Id];
        }

 public DungeonRoom(Vector3 size, Vector3 position)
 {
     this.size = size;
     this.position = position;
     entries = new List<Tuple<int, int>>();
     loaded = false;
 }

		/// <summary>
		/// Find the 3D distance between a point (x, y, z) and a segment PQ
		/// </summary>
		/// <param name="pt">The coordinate of the point.</param>
		/// <param name="p">The coordinate of point P in the segment PQ.</param>
		/// <param name="q">The coordinate of point Q in the segment PQ.</param>
		/// <returns>The distance between the point and the segment.</returns>
		internal static float PointToSegmentSquared(ref Vector3 pt, ref Vector3 p, ref Vector3 q)
		{
			//distance from P to Q
			Vector3 pq = q - p;

			//disance from P to the lone point
			float dx = pt.X - p.X;
			float dy = pt.Y - p.Y;
			float dz = pt.Z - p.Z;

			float segmentMagnitudeSquared = pq.LengthSquared();
			float t = pq.X * dx + pq.Y * dy + pq.Z * dz;

			if (segmentMagnitudeSquared > 0)
				t /= segmentMagnitudeSquared;

			//keep t between 0 and 1
			if (t < 0)
				t = 0;
			else if (t > 1)
				t = 1;

			dx = p.X + t * pq.X - pt.X;
			dy = p.Y + t * pq.Y - pt.Y;
			dz = p.Z + t * pq.Z - pt.Z;

			return dx * dx + dy * dy + dz * dz;
		}

        internal static bool AlmostEqual(ref Vector3 a, ref Vector3 b, float threshold)
        {
            float threshSq = threshold * threshold;
            float distSq = (b - a).LengthSquared();

            return distSq < threshold;
        }

// ReSharper restore NotAccessedField.Global
// ReSharper restore MemberCanBePrivate.Global

        public VertexPositionTextureNormalBinormalTangent(Vector3 position, Vector2 textureCoordinate, Vector3 normal, Vector3 binormal, Vector3 tangent)
        {
            Position = position.ToXNA();
            TextureCoordinate = textureCoordinate.ToXNA();
            Normal = normal.ToXNA();
            Binormal = binormal.ToXNA();
            Tangent = tangent.ToXNA();
        }

		/// <summary>
		/// Calculates the component-wise maximum of two vectors.
		/// </summary>
		/// <param name="left">A vector.</param>
		/// <param name="right">Another vector.</param>
		/// <param name="result">The component-wise maximum of the two vectors.</param>
		internal static void ComponentMax(ref Vector3 left, ref Vector3 right, out Vector3 result)
		{
#if OPENTK || STANDALONE
			Vector3.ComponentMax(ref left, ref right, out result);
#elif UNITY3D
			result = Vector3.Min(left, right);
#else
			Vector3.Max(ref left, ref right, out result);
#endif
		}

        /// <summary>
        /// Add a new circle to the array
        /// </summary>
        /// <param name="pos">The position</param>
        /// <param name="rad">The radius</param>
        /// <param name="vel">The velocity</param>
        /// <param name="dvel">The desired velocity</param>
        public void AddCircle(Vector3 pos, float rad, Vector3 vel, Vector3 dvel)
        {
            if (numCircles >= maxCircles)
                return;

            circles[numCircles].Position = pos;
            circles[numCircles].Radius = rad;
            circles[numCircles].Vel = vel;
            circles[numCircles].DesiredVel = dvel;
            numCircles++;
        }

 internal static void ProjectPoly(Vector3 axis, Vector3[] poly, int npoly, out float rmin, out float rmax)
 {
     Vector3Extensions.Dot2D(ref axis, ref poly[0], out rmin);
     Vector3Extensions.Dot2D(ref axis, ref poly[0], out rmax);
     for (int i = 1; i < npoly; i++)
     {
         float d;
         Vector3Extensions.Dot2D(ref axis, ref poly[i], out d);
         rmin = Math.Min(rmin, d);
         rmax = Math.Max(rmax, d);
     }
 }

		/// <summary>
		/// Initializes a new instance of the <see cref="Crowd" /> class.
		/// </summary>
		/// <param name="maxAgents">The maximum agents allowed</param>
		/// <param name="maxAgentRadius">The maximum radius for an agent</param>
		/// <param name="navMesh">The navigation mesh</param>
		public Crowd(int maxAgents, float maxAgentRadius, ref TiledNavMesh navMesh)
		{
			this.maxAgents = maxAgents;
			this.maxAgentRadius = maxAgentRadius;

			this.ext = new Vector3(maxAgentRadius * 2.0f, maxAgentRadius * 1.5f, maxAgentRadius * 2.0f);

			//initialize proximity grid
			this.grid = new ProximityGrid<Agent>(maxAgents * 4, maxAgentRadius * 3);

			//allocate obstacle avoidance query
			this.obstacleQuery = new ObstacleAvoidanceQuery(6, 8);

			//initialize obstancle query params
			this.obstacleQueryParams = new ObstacleAvoidanceQuery.ObstacleAvoidanceParams[AgentMaxObstacleAvoidanceParams];
			for (int i = 0; i < this.obstacleQueryParams.Length; i++)
			{
				this.obstacleQueryParams[i].VelBias = 0.4f;
				this.obstacleQueryParams[i].WeightDesVel = 2.0f;
				this.obstacleQueryParams[i].WeightCurVel = 0.75f;
				this.obstacleQueryParams[i].WeightSide = 0.75f;
				this.obstacleQueryParams[i].WeightToi = 2.5f;
				this.obstacleQueryParams[i].HorizTime = 2.5f;
				this.obstacleQueryParams[i].GridSize = 33;
				this.obstacleQueryParams[i].AdaptiveDivs = 7;
				this.obstacleQueryParams[i].AdaptiveRings = 2;
				this.obstacleQueryParams[i].AdaptiveDepth = 5;
			}

			//allocate temp buffer for merging paths
			this.maxPathResult = 256;
			this.pathResult = new PolyId[this.maxPathResult];

			this.pathq = new PathQueue(maxPathResult, 4096, ref navMesh);

			this.agents = new Agent[maxAgents];
			this.activeAgents = new Agent[maxAgents];
			this.agentAnims = new AgentAnimation[maxAgents];

			for (int i = 0; i < maxAgents; i++)
			{
				this.agents[i] = new Agent(maxPathResult);
			}

			for (int i = 0; i < maxAgents; i++)
			{
				this.agentAnims[i].Active = false;
			}

			//allocate nav mesh query
			this.navQuery = new NavMeshQuery(navMesh, 512);
		}

		public void PointInPoly_ExternalPoint_Success()
		{
			Vector3 pt = new Vector3(-1.0f, 0.0f, -1.0f);

			Vector3[] poly = new Vector3[3];
			poly[0] = new Vector3(0.0f, 0.0f, 1.0f);
			poly[1] = new Vector3(-1.0f, 0.0f, 0.0f);
			poly[2] = new Vector3(1.0f, 0.0f, 0.0f);

			bool isInPoly = Containment.PointInPoly(pt, poly, poly.Length);

			Assert.IsFalse(isInPoly);
		}

		public void SegmentSegment2D_without_float_false()
		{
			//the Segment 1
			Vector3 a = new Vector3(0, 0, 0);
			Vector3 b = new Vector3(1, 0, 1);

			//the segment 2
			Vector3 p = new Vector3(1, 0, 0);
			Vector3 q = new Vector3(2, 0, 1);
			bool f = Intersection.SegmentSegment2D(ref a, ref b, ref p, ref q);
			Assert.IsFalse(f);

		}

		public void PointToSegment2DSquared_Vectors_Success()
		{
			//the point
			Vector3 pt = new Vector3(0, 0, 0);

			//the segment
			Vector3 p = new Vector3(0, 0, 1);
			Vector3 q = new Vector3(1, 0, 0);

			float dist = Distance.PointToSegment2DSquared(ref pt, ref p, ref q);

			//safe floating value comparison
			Assert.AreEqual(dist + float.Epsilon, 0.5f);
		}

		public void PointToTriangle_CenterPointDist_Success()
		{
			//Point
			Vector3 p = new Vector3(0.5f, 0.5f, 0.5f);

			//Triangle
			Vector3 a = new Vector3(0, 0, 1);
			Vector3 b = new Vector3(-1, 0, 0);
			Vector3 c = new Vector3(1, 0, 0);

			float dist = Distance.PointToTriangle(p, a, b, c);

			Assert.AreEqual(dist + float.Epsilon, 0.5f);
		}

		public void SegmentSegment2D_with_float_success()
		{
			//the Segment 1
			Vector3 a = new Vector3(0, 0, 0);
			Vector3 b = new Vector3(1, 0, 1);

			//the segment 2
			Vector3 p = new Vector3(0, 0, 1);
			Vector3 q = new Vector3(1, 0, 0);
			float m;
			float n;
			bool f = Intersection.SegmentSegment2D(ref a, ref b, ref p, ref q, out m, out n);
			Assert.IsTrue(f);

		}

		/// <summary>
		/// Iterates over an array of <see cref="Vector3"/> with a specified offset, stride, and length.
		/// </summary>
		/// <param name="vertices">An array of vertices.</param>
		/// <param name="vertOffset">The index of the first vertex to be enumerated.</param>
		/// <param name="vertStride">The distance between the start of two triangles. A value of 0 means the data is tightly packed.</param>
		/// <param name="triCount">The number of triangles to enumerate.</param>
		/// <returns>An enumerable collection of triangles.</returns>
		public static IEnumerable<Triangle3> FromVector3(Vector3[] vertices, int vertOffset, int vertStride, int triCount)
		{
			Triangle3 tri;

			if (vertStride == 0)
				vertStride = 3;

			for (int i = 0; i < triCount; i++)
			{
				tri.A = vertices[i * vertStride + vertOffset];
				tri.B = vertices[i * vertStride + vertOffset + 1];
				tri.C = vertices[i * vertStride + vertOffset + 2];

				yield return tri;
			}
		}

		/// <summary>
		/// Determines whether a point is inside a polygon.
		/// </summary>
		/// <param name="pt">A point.</param>
		/// <param name="verts">A set of vertices that define a polygon.</param>
		/// <param name="nverts">The number of vertices to use from <c>verts</c>.</param>
		/// <returns>A value indicating whether the point is contained within the polygon.</returns>
		internal static bool PointInPoly(Vector3 pt, Vector3[] verts, int nverts)
		{
			bool c = false;

			for (int i = 0, j = nverts - 1; i < nverts; j = i++)
			{
				Vector3 vi = verts[i];
				Vector3 vj = verts[j];
				if (((vi.Z > pt.Z) != (vj.Z > pt.Z)) &&
					(pt.X < (vj.X - vi.X) * (pt.Z - vi.Z) / (vj.Z - vi.Z) + vi.X))
				{
					c = !c;
				}
			}

			return c;
		}