
///////////////////////////////////////////////////////////////////////////////
//
// File   : Asura_Frustum.cpp
// Author : Andy Tate
// Date   : 12-Sep-2005
//
// Copyright (C) 2005 Rebellion, All Rights Reserved.
//
///////////////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////////////////
// Include files...
////////////////////////////////////////////////////////////////////////////////

#include "Core/Asura.h"

// This file's header...
#include "Rendering/Asura_Frustum.h"

// Asura independent header-files...
#include "Rendering/Asura_Render.h"

// Asura platform header-files...


////////////////////////////////////////////////////////////////////////////////
// Constant declarations...
////////////////////////////////////////////////////////////////////////////////


////////////////////////////////////////////////////////////////////////////////
// Static variable declarations...
////////////////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////////////////
// Private functions...
////////////////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////////////////
// Function     : Asura_Frustum::GenerateVertices
// Author       : Andy Tate
// Date         : 29-Nov-2006
////////////////////////////////////////////////////////////////////////////////

void Asura_Frustum::GenerateVertices (Asura_Vector_3* pxVertices) const
{
	const float		fWidthAtNearPlane	= m_fNearPlane * m_fTanHalfHorFOV;
	const float		fHeightAtNearPlane	= m_fNearPlane * m_fTanHalfVerFOV;
	const float		fWidthAtFarPlane	= m_fFarPlane * m_fTanHalfHorFOV;
	const float		fHeightAtFarPlane	= m_fFarPlane * m_fTanHalfVerFOV;

	// Calculate the vertices...
	for (u_int u = 0; u < 4; u++, pxVertices++)
	{
		const float	fNearX	= (0 == (u & 1)) ? fWidthAtNearPlane : -fWidthAtNearPlane;
		const float	fNearY	= (0 == (u & 2)) ? fHeightAtNearPlane : -fHeightAtNearPlane;
		const float	fFarX	= (0 == (u & 1)) ? fWidthAtFarPlane : -fWidthAtFarPlane;
		const float	fFarY	= (0 == (u & 2)) ? fHeightAtFarPlane : -fHeightAtFarPlane;

		// Set the near and far vertices...
		pxVertices [0][0]	= fNearX;
		pxVertices [0][1]	= fNearY;
		pxVertices [0][2]	= m_fNearPlane;

		pxVertices [4][0]	= fFarX;
		pxVertices [4][1]	= fFarY;
		pxVertices [4][2]	= m_fFarPlane;
	}
}

/// End of function 'Asura_Frustum::GenerateVertices'. ///



////////////////////////////////////////////////////////////////////////////////
// Function     : Asura_Frustum::GenerateVertices
// Author       : Andy Tate
// Date         : 29-Nov-2006
////////////////////////////////////////////////////////////////////////////////

void Asura_Frustum::GenerateVertices (Asura_Vector_3* pxVertices,
									  const Asura_Vector_3& xPosition,
									  const Asura_Matrix_3x3& xOrientation) const
{
	GenerateVertices(pxVertices);

	for(u_int u = 0; u < MAX_VERTICES; u++, pxVertices++)
	{
		*pxVertices	= (pxVertices[0] * xOrientation) + xPosition;
	}
}

/// End of function 'Asura_Frustum::GenerateVertices'. ///



////////////////////////////////////////////////////////////////////////////////
// Function     : Asura_Frustum::GenerateVertices
// Author       : Andy Tate
// Date         : 29-Nov-2006
////////////////////////////////////////////////////////////////////////////////

void Asura_Frustum::GenerateVertices (Asura_Vector_3* pxVertices,
									  const Asura_Vector_3& xPosition,
									  const Asura_Quat& xOrientation) const
{
	GenerateVertices(pxVertices);

	for(u_int u = 0; u < MAX_VERTICES; u++, pxVertices++)
	{
		pxVertices[0] = xOrientation.RotateVector(pxVertices[0]);
		pxVertices[0]	+= xPosition;
	}
}

/// End of function 'Asura_Frustum::GenerateVertices'. ///



////////////////////////////////////////////////////////////////////////////////
// Protected functions...
////////////////////////////////////////////////////////////////////////////////


////////////////////////////////////////////////////////////////////////////////
// Public functions...
////////////////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////////////////
// Function     : Asura_Frustum::SetForDistance
// Author       : Andy Tate
// Date         : 12-Sep-2005
//
// Description  : Initialises the frustum based on settings at a given distance.
//
// Parameters   : The near and far-plane distances along with the distance at 
//				  which the width and height are those specified.
//
// Return value : None.
////////////////////////////////////////////////////////////////////////////////

void Asura_Frustum::SetForDistance (const float fNearPlane,
									const float fFarPlane,
									const float fDistance,
									const float fWidth,
									const float fHeight)
{
	// Copy the data...
	m_fNearPlane		= fNearPlane;
	m_fFarPlane			= fFarPlane;

	m_fTanHalfHorFOV	= (fWidth * 0.5f) / fDistance;
	m_fTanHalfVerFOV	= (fHeight * 0.5f) / fDistance;
}

/// End of function 'Asura_Frustum::SetForDistance'. ///



////////////////////////////////////////////////////////////////////////////////
// Function     : Asura_Frustum::SetForFOV
// Author       : Andy Tate
// Date         : 29-Nov-2006
////////////////////////////////////////////////////////////////////////////////

void Asura_Frustum::SetForFOV (const float fNearPlane,
							   const float fFarPlane,
							   const float fTanHalfHorFOV,
							   const float fTanHalfVerFOV)
{
	// Copy the data...
	m_fNearPlane		= fNearPlane;
	m_fFarPlane			= fFarPlane;

	m_fTanHalfHorFOV	= fTanHalfHorFOV;
	m_fTanHalfVerFOV	= fTanHalfVerFOV;
}

/// End of function 'Asura_Frustum::SetForFOV'. ///



////////////////////////////////////////////////////////////////////////////////
// Function     : Asura_Frustum::SetForSphere
// Author       : Andy Tate
// Date         : 13-Sep-2005
//
// Description  : Initialises the frustum based on settings for a given sphere.
//
// Parameters   : The near and far-plane distances along with the distance to the 
//				  sphere's centre and it's radius.
//
// Return value : None.
////////////////////////////////////////////////////////////////////////////////

void Asura_Frustum::SetForSphere (const float fNearPlane,
								  const float fFarPlane,
								  const float fDistance,
								  const float fRadius)
{
	const float			fSinAlpha	= fRadius / fDistance;
	const Asura_Angle	xAlpha		= Asura_Maths::ArcSine (fSinAlpha);
	const float			fCosAlpha	= Asura_Maths::Cosine (xAlpha);
	const float			fDz			= fRadius * fSinAlpha;
	const float			fDx			= fRadius * fCosAlpha;
	const float			fWidth		= fDx * 2.0f;
	const float			fHeight		= fDx * 2.0f;

	// Set the frustum...
	SetForDistance	(fNearPlane, fFarPlane, fDistance - fDz, fWidth, fHeight);
}

/// End of function 'Asura_Frustum::SetForSphere'. ///



////////////////////////////////////////////////////////////////////////////////
// Function     : Asura_Frustum::Contains
// Author       : Andy Tate
// Date         : 29-Nov-2006
////////////////////////////////////////////////////////////////////////////////

bool Asura_Frustum::Contains (const Asura_Vector_3 &xPosition) const
{
	const float	fZ	= xPosition[2];

	// Are we inside the near/far planes...
	if((fZ >= m_fNearPlane) && (fZ <= m_fFarPlane))
	{
		const float	fOneOverZ	= 1.0f / fZ;
		const float	fX			= Asura_Maths::Abs(xPosition[0]);
		const float	fTanHor		= fX * fOneOverZ;
		const bool	bInsideHor	= (fTanHor <= m_fTanHalfHorFOV);

		// Are we inside horizontally?
		if(bInsideHor)
		{
			const float	fY			= Asura_Maths::Abs(xPosition[1]);
			const float	fTanVer		= fY * fOneOverZ;
			const bool	bInsideVer	= (fTanVer <= m_fTanHalfVerFOV);

			// What about vertically?
			return(bInsideVer);
		}
		else
		{
			return(false);
		}
	}
	else
	{
		return(false);
	}
}

/// End of function 'Asura_Frustum::Contains'. ///



////////////////////////////////////////////////////////////////////////////////
// Function     : Asura_Frustum::Intersects
// Author       : Andy Tate
// Date         : 4-Dec-2006
////////////////////////////////////////////////////////////////////////////////

bool Asura_Frustum::Intersects(const Asura_Vector_3 &xPosition,
							   const float fRadius) const
{
	const float	fZ	= xPosition[2];

	// Are we inside the near/far planes...
	if(((fZ + fRadius) >= m_fNearPlane) && ((fZ - fRadius) <= m_fFarPlane))
	{
		const float	fOneOverZ	= 1.0f / fZ;
		float		fX			= Asura_Maths::Abs(xPosition[0]);
		float		fTanHor		= fX * fOneOverZ;

		bool		bInsideHor;
		
		if(fTanHor <= m_fTanHalfHorFOV)
		{
			bInsideHor	= true;
		}
		else
		{
			const float	fC		= fRadius / Asura_Maths::Sqrt(1 + (m_fTanHalfHorFOV * m_fTanHalfHorFOV));
			const float	fNewZ	= fZ + (m_fTanHalfHorFOV * fC);

			////////////////////////////////////////////////////////////////////////////////
			// Frustum to sphere intersection code, done on the horizontal and vertical
			// axes separately (this example is for the x axis).
			//
			// Where:
			// ~~~~~~
			// - 'P' is the centre-position of the sphere
			// - 'R' is the radius of the sphere
			// - 'a' is the angle for the appropriate FOV
			//
			//    --        \       |            tan(a)
			//    ^        /|\      |           \-------
			//    |       / |a\     |            \     |
			//    z   R  /  |  \    |             \    |
			//    |     /   |   \   |     AND      \   | 1
			//    v    /a   |    \  |               \  |
			//    --  +------     \a|                \a|
			//       P             \|                 \|
			//        |<-x->|       +                  +
			//
			// When:
			// ~~~~~ (x * x) + (z * z) = (R * R)
			// and
			//       tan(a) = z/x   =>  z = x * tan(a)
			//
			// =>  (x * x) + ((x * tan(a)) * (x * tan(a)) = (R * R)
			//
			// =>  (x * x) * (1 + (tan(a) * tan(a)) = (R * R)
			//
			//                      (R * R)
			// =>  (x * x) = ----------------------
			//               (1 + (tan(a) * tan(a))
			//
			//                  R
			// =>  x = --------------------------
			//           /----------------------|
			//         \/ (1 + (tan(a) * tan(a))
			////////////////////////////////////////////////////////////////////////////////
			fX			-= fC;
			fTanHor		 = fX / fNewZ;
			bInsideHor	 = (fTanHor <= m_fTanHalfHorFOV);
		}

		// Are we inside horizontally?
		if(bInsideHor)
		{
			float	fY		= Asura_Maths::Abs(xPosition[1]);
			float	fTanVer	= fY * fOneOverZ;

			bool	bInsideVer;

			if(fTanVer <= m_fTanHalfVerFOV)
			{
				bInsideVer	= true;
			}
			else
			{
				const float	fC		= fRadius / Asura_Maths::Sqrt(1 + (m_fTanHalfVerFOV * m_fTanHalfVerFOV));
				const float	fNewZ	= fZ + (m_fTanHalfVerFOV * fC);

				// And repeat test for Y...
				fY			-= fC;
				fTanVer		 = fY / fNewZ;
				bInsideVer	 = (fTanVer <= m_fTanHalfVerFOV);
			}

			// What about vertically?
			return(bInsideVer);
		}
		else
		{
			return(false);
		}
	}
	else
	{
		return(false);
	}
}

/// End of function 'Asura_Frustum::Intersects'. ///



////////////////////////////////////////////////////////////////////////////////
// Function     : Asura_Frustum::Intersects
// Author       : Andy Tate
// Date         : 29-Nov-2006
////////////////////////////////////////////////////////////////////////////////

bool Asura_Frustum::Intersects (const Asura_Frustum& xFrustum,
								const Asura_Vector_3& xPosition,
								const Asura_Quat& xOrientation) const
{
	Asura_Vector_3	xOtherCentre;

	const float		fOtherRadius	= xFrustum.GetBoundingSphere(xOtherCentre, xOrientation, xPosition);

	if(Intersects(xOtherCentre, fOtherRadius))
	{
		// Bounding-sphere intersects this frustum...

		////////////////////////////////////////////////////////////////////////////////
		// ART - 05/12/2006 - This needs a full frustum-frustum intersection test
		// here, but we don't have the time to do this at the moment.
		////////////////////////////////////////////////////////////////////////////////
		return(true);
	}
	else
	{
		return(false);
	}
}

/// End of function 'Asura_Frustum::Intersects'. ///



////////////////////////////////////////////////////////////////////////////////
// Function     : Asura_Frustum::Intersects
// Author       : Andy Tate
// Date         : 29-Nov-2006
////////////////////////////////////////////////////////////////////////////////

bool Asura_Frustum::Intersects (const Asura_Frustum& xFrustum,
								const Asura_Vector_3& xPosition,
								const Asura_Matrix_3x3& xOrientation) const
{
	Asura_Quat	xQuat;

	xQuat.FromMatrix(xOrientation);
	return(Intersects(xFrustum, xPosition, xQuat));
}

/// End of function 'Asura_Frustum::Intersects'. ///



////////////////////////////////////////////////////////////////////////////////
// Function     : Asura_Frustum::GetBoundingBox
// Author       : Andy Tate
// Date         : 29-Nov-2006
////////////////////////////////////////////////////////////////////////////////

void Asura_Frustum::GetBoundingBox (Asura_Bounding_Box& xBoundingBox,
									const Asura_Matrix_3x3& xOrientation,
									const Asura_Vector_3& xPosition) const
{
	Asura_Vector_3	axVertices [MAX_VERTICES];

	xBoundingBox.Reset();
	GenerateVertices(axVertices, xPosition, xOrientation);

	for (u_int v = 0; v < MAX_VERTICES; v++)
	{
		xBoundingBox.Set(axVertices[v]);
	}
}

/// End of function 'Asura_Frustum::GetBoundingBox'. ///



////////////////////////////////////////////////////////////////////////////////
// Function     : Asura_Frustum::GetBoundingBox
// Author       : Andy Tate
// Date         : 29-Nov-2006
////////////////////////////////////////////////////////////////////////////////

void Asura_Frustum::GetBoundingBox (Asura_Bounding_Box& xBoundingBox,
									const Asura_Quat& xOrientation,
									const Asura_Vector_3& xPosition) const
{
	Asura_Vector_3	axVertices [MAX_VERTICES];

	xBoundingBox.Reset();
	GenerateVertices(axVertices, xPosition, xOrientation);

	for (u_int v = 0; v < MAX_VERTICES; v++)
	{
		xBoundingBox.Set(axVertices[v]);
	}
}

/// End of function 'Asura_Frustum::GetBoundingBox'. ///



////////////////////////////////////////////////////////////////////////////////
// Function     : Asura_Frustum::GetBoundingSphere
// Author       : Andy Tate
// Date         : 29-Nov-2006
////////////////////////////////////////////////////////////////////////////////

float Asura_Frustum::GetBoundingSphere (Asura_Vector_3& xCentre) const
{
	Asura_Vector_3	axVertices [MAX_VERTICES];
	Asura_Vector_3	xDifference;

	////////////////////////////////////////////////////////////////////////////////
	// ART - 05/12/2006 - Only need top-left-near and top-left-far vertices,
	// this will need optimising at some later date.
	////////////////////////////////////////////////////////////////////////////////

	// Generate ALL vertices...
	GenerateVertices(axVertices);

	////////////////////////////////////////////////////////////////////////////////
	// Need to calculate the centre of the frustum such that the radius of our 
	// bounding-sphere sweeps through all 8 vertices.
	//
	//           Far +---------------------/ ---
	//                \                   / ^ ^
	//                 \                 / z2 |
	//                  \       C       /   v |
	//                   \      +      / ---- |
	//                    \           /    ^  D
	//                     \         /     |  |
	//                      \       /      z1 |
	//                       \     /       |  |
	//                        \   /        v  v
	//                    Near +-/ -------------
	//
	// Where:
	// ~~~~~~  (xf * xf) + (yf * yf) + (z2 * z2) = (xn * xn) + (yn * yn) + (z1 * z1)
	// and
	//         z1 + z2 = D
	//
	// => (xf * xf) + (yf * yf) - (xn * xn) - (yn * yn) = (z1 * z1) - ((D - z1) * (D - z1))
	//
	// => (xf * xf) + (yf * yf) - (xn * xn) - (yn * yn) = (2 * D * z1) - (D * D)
	//
	//         (D * D) + (xf * xf) + (yf * yf) - (xn * xn) - (yn * yn)
	// => z1 = -------------------------------------------------------
	//                                (2 * D)
	////////////////////////////////////////////////////////////////////////////////
	{
		const float	fDepth	= m_fFarPlane - m_fNearPlane;
		const float	fNearX	= axVertices[TOP_LEFT_NEAR][0];
		const float	fNearY	= axVertices[TOP_LEFT_NEAR][1];
		const float	fFarX	= axVertices[TOP_LEFT_FAR][0];
		const float	fFarY	= axVertices[TOP_LEFT_FAR][1];
		const float	fZ1		= ((fDepth * fDepth) + (fFarX * fFarX) + (fFarY * fFarY) - (fNearX * fNearX) - (fNearY * fNearY)) / (2.0f * fDepth);

		if ( m_fNearPlane + fZ1 < m_fFarPlane )
		{
			// Calculate the centre...
			xCentre[0]	= 0.0f;
			xCentre[1]	= 0.0f;
			xCentre[2]	= m_fNearPlane + fZ1;

			// ...and the radius...
			xDifference	= xCentre - axVertices[TOP_LEFT_FAR];
			return(xDifference.Magnitude());
		}
		else
		{
			// For wider FOV's the smallest bounding sphere is centered on the far plane.

			xCentre[0] = 0.0f;
			xCentre[1] = 0.0f;
			xCentre[2] = m_fFarPlane;

			xDifference	= axVertices[TOP_LEFT_FAR] - axVertices[BOTTOM_RIGHT_FAR];
			return xDifference.Magnitude()/2.0f; 
		}
	}
	
	
}

/// End of function 'Asura_Frustum::GetBoundingSphere'. ///



////////////////////////////////////////////////////////////////////////////////
// Function     : Asura_Frustum::GetBoundingSphere
// Author       : Andy Tate
// Date         : 29-Nov-2006
////////////////////////////////////////////////////////////////////////////////

float Asura_Frustum::GetBoundingSphere (Asura_Vector_3& xCentre,
										const Asura_Matrix_3x3& xOrientation,
										const Asura_Vector_3& xPosition) const
{
	const float	fRadius	= GetBoundingSphere(xCentre);

	// Transform the centre...
	xCentre	= (xCentre * xOrientation) + xPosition;

	// Return the radius...
	return(fRadius);
}

/// End of function 'Asura_Frustum::GetBoundingSphere'. ///



////////////////////////////////////////////////////////////////////////////////
// Function     : Asura_Frustum::GetBoundingSphere
// Author       : Andy Tate
// Date         : 29-Nov-2006
////////////////////////////////////////////////////////////////////////////////

float Asura_Frustum::GetBoundingSphere (Asura_Vector_3& xCentre,
										const Asura_Quat& xOrientation,
										const Asura_Vector_3& xPosition) const
{
	const float	fRadius	= GetBoundingSphere(xCentre);

	// Transform the centre...
	xCentre = xOrientation.RotateVector(xCentre);
	xCentre	+= xPosition;

	// Return the radius...
	return(fRadius);
}

/// End of function 'Asura_Frustum::GetBoundingSphere'. ///



////////////////////////////////////////////////////////////////////////////////
// Function     : Asura_Frustum::GetClosestVertex
// Author       : Andy Tate
// Date         : 29-Nov-2006
////////////////////////////////////////////////////////////////////////////////

void Asura_Frustum::GetClosestVertex (const Asura_Vector_3 &xTo,
									  Asura_Vector_3 &xClosestVertex) const
{
	float			fClosestDistanceSquared	= Asura_Maths::LargeFloat;
	u_int			uClosestIndex			= 0;

	Asura_Vector_3	axVertices [MAX_VERTICES];

	GenerateVertices(axVertices);

	for (u_int u = 0; u < MAX_VERTICES; u++)
	{
		const Asura_Vector_3	xDifference(axVertices[u] - xTo);
		const float				fDistanceSquared	= xDifference.MagnitudeSquared();

		if(fClosestDistanceSquared > fDistanceSquared)
		{
			fClosestDistanceSquared	= fDistanceSquared;
			uClosestIndex			= u;
		}
	}

	xClosestVertex	= axVertices[uClosestIndex];
}

/// End of function 'Asura_Frustum::GetClosestVertex'. ///



////////////////////////////////////////////////////////////////////////////////
// Function     : Asura_Frustum::GetHorizontalFOVInDegrees
// Author       : Andy Tate
// Date         : 12-Sep-2005
////////////////////////////////////////////////////////////////////////////////

float Asura_Frustum::GetHorizontalFOVInDegrees (void) const
{
	Asura_Angle	xAngle	= Asura_Maths::ArcTangent (m_fTanHalfHorFOV, 1.0f);

	// Return the angle...
	return	(2.0f * Asura_Maths::RadToDeg(xAngle));
}

/// End of function 'Asura_Frustum::GetHorizontalFOVInDegrees'. ///



////////////////////////////////////////////////////////////////////////////////
// Function     : Asura_Frustum::GetVerticalFOVInDegrees
// Author       : Andy Tate
// Date         : 12-Sep-2005
////////////////////////////////////////////////////////////////////////////////

float Asura_Frustum::GetVerticalFOVInDegrees (void) const
{
	Asura_Angle	xAngle	= Asura_Maths::ArcTangent (m_fTanHalfVerFOV, 1.0f);

	// Return the angle...
	return	(2.0f * Asura_Maths::RadToDeg(xAngle));
}

/// End of function 'Asura_Frustum::GetVerticalFOVInDegrees'. ///


/// End of file. ///
