/*
 * Picker.cs
 * Authors: Mike Dapiran, 
 * Copyright (c) 2007-2008 Cornell University

 This program is free software; you can redistribute it and/or
 modify it under the terms of the GNU General Public License
 as published by the Free Software Foundation; either version 2
 of the License, or (at your option) any later version.

 This program is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 GNU General Public License for more details.

 You should have received a copy of the GNU General Public License
 along with this program; if not, write to the Free Software
 Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
*/

/*This file is heavily based on an example from the XNA creators site entitled "Picking
 * with Triangle Accuracy
 */

using System;
using System.Collections.Generic;
using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Graphics;
using tAC_Engine.Graphics.Entities;

namespace tAC_Engine
{
	/// <summary>
	/// This class assists in setting calculating what has been selected via mouse click in a 3 dimensional plane
	/// </summary>
	public static class Picker
	{
		#region Conversion Calculations

		/// <summary>
		/// Calculates a world space ray starting at the camera's "eye" and pointing in 
		/// the direction of the cursor. Viewport.Unproject is used to accomplish this. 
		/// see the accompanying documentation for more explanation of the math behind 
		/// this function.
		/// </summary>
		/// <param name="Position">The position that was clicked on</param>
		/// <param name="projectionMatrix">The current projection matrix</param>
		/// <param name="viewMatrix">The current view matrix</param>
		/// <param name="currentViewport">The current viewport</param>
		/// <returns>A ray that goes from the position on screen to the intersection point in the world</returns>
		public static Ray CalculateCursorRay(Vector2 Position, Matrix projectionMatrix, Matrix viewMatrix, Viewport currentViewport)
		{
			// create 2 positions in screenspace using the cursor position. 0 is as
			// close as possible to the camera, 1 is as far away as possible.
			Vector3 nearSource = new Vector3(Position, 0f);
			Vector3 farSource = new Vector3(Position, 1f);

			// use Viewport.Unproject to tell what those two screen space positions
			// would be in world space. we'll need the projection matrix and view
			// matrix, which we have saved as member variables. We also need a world
			// matrix, which can just be identity.
			Vector3 nearPoint = currentViewport.Unproject(nearSource,
				projectionMatrix, viewMatrix, Matrix.Identity);

			Vector3 farPoint = currentViewport.Unproject(farSource,
				projectionMatrix, viewMatrix, Matrix.Identity);

			// find the direction vector that goes from the nearPoint to the farPoint
			// and normalize it....
			Vector3 direction = farPoint - nearPoint;
			direction.Normalize();

			// and then create a new ray using nearPoint as the source.
			return new Ray(nearPoint, direction);
		}

		/// <summary>
		/// This helper function takes a BoundingSphere and a transform matrix, and
		/// returns a transformed version of that BoundingSphere.
		/// </summary>
		/// <param name="sphere">the BoundingSphere to transform</param>
		/// <param name="transform">how to transform the BoundingSphere.</param>
		/// <returns>the transformed BoundingSphere/</returns>
		private static BoundingSphere TransformBoundingSphere(BoundingSphere sphere, Matrix transform)
		{
			BoundingSphere transformedSphere;

			// the transform can contain different scales on the x, y, and z components.
			// this has the effect of stretching and squishing our bounding sphere along
			// different axes. Obviously, this is no good: a bounding sphere has to be a
			// SPHERE. so, the transformed sphere's radius must be the maximum of the 
			// scaled x, y, and z radii.

			// to calculate how the transform matrix will affect the x, y, and z
			// components of the sphere, we'll create a vector3 with x y and z equal
			// to the sphere's radius...
			Vector3 scale3 = new Vector3(sphere.Radius, sphere.Radius, sphere.Radius);

			// then transform that vector using the transform matrix. we use
			// TransformNormal because we don't want to take translation into account.
			scale3 = Vector3.TransformNormal(scale3, transform);

			// scale3 contains the x, y, and z radii of a squished and stretched sphere.
			// we'll set the finished sphere's radius to the maximum of the x y and z
			// radii, creating a sphere that is large enough to contain the original 
			// squished sphere.
			transformedSphere.Radius = Math.Max(scale3.X, Math.Max(scale3.Y, scale3.Z));

			// transforming the center of the sphere is much easier. we can just use 
			// Vector3.Transform to transform the center vector. notice that we're using
			// Transform instead of TransformNormal because in this case we DO want to 
			// take translation into account.
			transformedSphere.Center = Vector3.Transform(sphere.Center, transform);


			return transformedSphere;
		}

		#endregion

		#region Intersection Checks

		/// <summary>
		/// Checks whether a ray intersects a model. This method needs to access
		/// the model vertex data, so the model must have been built using the
		/// custom TrianglePickingProcessor provided as part of this sample.
		/// Returns the distance along the ray to the point of intersection, or null
		/// if there is no intersection.
		/// </summary>
		/// <param name="ray">The ray that is being check for collision</param>
		/// <param name="model">The model that is being check for collision</param>
		/// <param name="insideBoundingBox">Whether or not the ray goes inside the bounding box</param>
		/// <param name="vertex1">The first vertex point of the triangle</param>
		/// <param name="vertex2">The second vertex point of the triangle</param>
		/// <param name="vertex3">The third vertex point of the triangle</param>
		/// <param name="pointInWorldSpace">The point at which the ray intersects the model</param>
		/// <returns>The result of the ray intersection calculation
		/// Null if no collision is detected, otherwise gives the length of the ray</returns>
		public static float? RayIntersectsModel(Ray ray, EntityModel model,
										 out bool insideBoundingBox,
										 out Vector3 vertex1, out Vector3 vertex2,
										 out Vector3 vertex3, out Vector3? pointInWorldSpace)
		{
			pointInWorldSpace = null;
			vertex1 = vertex2 = vertex3 = Vector3.Zero;

			// The input ray is in world space, but our model data is stored in object
			// space. We would normally have to transform all the model data by the
			// modelTransform matrix, moving it into world space before we test it
			// against the ray. That transform can be slow if there are a lot of
			// triangles in the model, however, so instead we do the opposite.
			// Transforming our ray by the inverse modelTransform moves it into object
			// space, where we can test it directly against our model data. Since there
			// is only one ray but typically many triangles, doing things this way
			// around can be much faster.

			Matrix inverseTransform = Matrix.Invert(model.TransformationMatrix);

			ray.Position = Vector3.Transform(ray.Position, inverseTransform);
			ray.Direction = Vector3.TransformNormal(ray.Direction, inverseTransform);

			// Look up our custom collision data from the Tag property of the model.
			Dictionary<string, object> tagData = (Dictionary<string, object>)model.Model.Tag;

			if (tagData == null)
			{
				throw new InvalidOperationException(
					"Model.Tag is not set correctly. Make sure your model " +
					"was built using the custom TrianglePickingProcessor.");
			}

			// Start off with a fast bounding box test.
			BoundingBox boundingBox = (BoundingBox)tagData["BoundingBox"];
			if (boundingBox.Intersects(ray) == null)
			{
				// If the ray does not intersect the bounding box, we cannot
				// possibly have picked this model, so there is no need to even
				// bother looking at the individual triangle data.
				insideBoundingBox = false;

				return null;
			}
			// The bounding box test passed, so we need to do a full
			// triangle picking test.
			insideBoundingBox = true;

			// Keep track of the closest triangle we found so far,
			// so we can always return the closest one.
			float? closestIntersection = null;

			// Loop over the vertex data, 3 at a time (3 vertices = 1 triangle).
			Vector3[] vertices = (Vector3[])tagData["Vertices"];

			for (int i = 0; i < vertices.Length; i += 3)
			{
				// Perform a ray to triangle intersection test.
				float? intersection;

				RayIntersectsTriangle(ref ray,
				                      ref vertices[i],
				                      ref vertices[i + 1],
				                      ref vertices[i + 2],
				                      out intersection);

				// Does the ray intersect this triangle?
				if (intersection != null)
				{
					// If so, is it closer than any other previous triangle?
					if ((closestIntersection == null) ||
					    (intersection < closestIntersection))
					{
						// Store the distance to this triangle.
						closestIntersection = intersection;

						// Transform the three vertex positions into world space,
						// and store them into the output vertex parameters.
						Matrix transformationMatrix = model.TransformationMatrix;
						Vector3.Transform(ref vertices[i],
						                  ref transformationMatrix, out vertex1);

						Vector3.Transform(ref vertices[i + 1],
						                  ref transformationMatrix, out vertex2);

						Vector3.Transform(ref vertices[i + 2],
						                  ref transformationMatrix, out vertex3);

						Vector3 pointInModelSpace = (Vector3)(ray.Position + (ray.Direction * closestIntersection));

						pointInWorldSpace = Vector3.Transform(pointInModelSpace, transformationMatrix);
					}
				}
			}

			return closestIntersection;
		}


		/// <summary>
		/// Checks whether a ray intersects a triangle. This uses the algorithm
		/// developed by Tomas Moller and Ben Trumbore, which was published in the
		/// Journal of Graphics Tools, volume 2, "Fast, Minimum Storage Ray-Triangle
		/// Intersection".
		/// 
		/// This method is implemented using the pass-by-reference versions of the
		/// XNA math functions. Using these overloads is generally not recommended,
		/// because they make the code less readable than the normal pass-by-value
		/// versions. This method can be called very frequently in a tight inner loop,
		/// however, so in this particular case the performance benefits from passing
		/// everything by reference outweigh the loss of readability.
		/// </summary>
		/// <param name="ray">The ray that is being check for collision</param>
		/// <param name="vertex1">The first vertex point of the triangle</param>
		/// <param name="vertex2">The second vertex point of the triangle</param>
		/// <param name="vertex3">The third vertex point of the triangle</param>
		/// <param name="result">The result of the ray intersection calculation
		/// Null if no collision is detected, otherwise gives the length of the ray</param>
		public static void RayIntersectsTriangle(ref Ray ray,
										  ref Vector3 vertex1,
										  ref Vector3 vertex2,
										  ref Vector3 vertex3, out float? result)
		{
			// Compute vectors along two edges of the triangle.
			Vector3 edge1, edge2;

			Vector3.Subtract(ref vertex2, ref vertex1, out edge1);
			Vector3.Subtract(ref vertex3, ref vertex1, out edge2);

			// Compute the determinant.
			Vector3 directionCrossEdge2;
			Vector3.Cross(ref ray.Direction, ref edge2, out directionCrossEdge2);

			float determinant;
			Vector3.Dot(ref edge1, ref directionCrossEdge2, out determinant);

			// If the ray is parallel to the triangle plane, there is no collision.
			if (determinant > -float.Epsilon && determinant < float.Epsilon)
			{
				result = null;
				return;
			}

			float inverseDeterminant = 1.0f / determinant;

			// Calculate the U parameter of the intersection point.
			Vector3 distanceVector;
			Vector3.Subtract(ref ray.Position, ref vertex1, out distanceVector);

			float triangleU;
			Vector3.Dot(ref distanceVector, ref directionCrossEdge2, out triangleU);
			triangleU *= inverseDeterminant;

			// Make sure it is inside the triangle.
			if (triangleU < 0 || triangleU > 1)
			{
				result = null;
				return;
			}

			// Calculate the V parameter of the intersection point.
			Vector3 distanceCrossEdge1;
			Vector3.Cross(ref distanceVector, ref edge1, out distanceCrossEdge1);

			float triangleV;
			Vector3.Dot(ref ray.Direction, ref distanceCrossEdge1, out triangleV);
			triangleV *= inverseDeterminant;

			// Make sure it is inside the triangle.
			if (triangleV < 0 || triangleU + triangleV > 1)
			{
				result = null;
				return;
			}

			// Compute the distance along the ray to the triangle.
			float rayDistance;
			Vector3.Dot(ref edge2, ref distanceCrossEdge1, out rayDistance);
			rayDistance *= inverseDeterminant;

			// Is the triangle behind the ray origin?
			if (rayDistance < 0)
			{
				result = null;
				return;
			}

			result = rayDistance;
		}

		#endregion
	}
}