//
// Asura_LOS.cpp
//
// Created by Kevin Lea - 12/06/2001 10:59:31
// 
// Copyright (C) 2001 Rebellion, All Rights Reserved.
//

#include "Core/Asura.h"

#include "Core/Asura_LOS.h"

#include "Animation/Asura_AnimationAttachment.h"
#include "Core/Asura_MaterialFlags.h"
#include "Core/Asura_Timers.h"
#include "Debugging/Asura_Assert.h"
#include "Debugging/Asura_Logfile.h"
#include "Entity/Asura_Entity.h"
#include "Interface/Asura_CommandConsole.h"
#include "Mesh/Asura_Mesh.h"
#include "Rendering/Asura_Module.h"
#include "Physics/Asura_Physics_Environment.h"


#ifdef ASURA_SUPPORT_LOS_FUDGE
float Asura_LOS::s_fLOSFudge = 0.0f;
#endif

#ifdef ASURA_LOS_TRACK_CALLS
struct LOSCallData
{
    u_int         uCallType;
    Asura_Hash_ID uFilenameHash;
    const char*   szFilename;
    Asura_Hash_ID uExtraDescHash;
    const char*   szExtraDesc;
    u_int         uLine;
    u_int         uCount;
};

static const char* szLOS_CALLS_LOGFILE = "logfiles\\LOS_Calls.txt";
static const u_int uMAX_DISTINCT_LOS_CALLS_TO_TRACK = 32;

static LOSCallData g_axLOSCallData[uMAX_DISTINCT_LOS_CALLS_TO_TRACK];
static u_int g_uNumDistinctLOSCalls = 0;
static bool g_bWriteLOSCallDataNextFrame = false;
static bool g_bWriteLOSCallDataEveryFrame = false;
static float g_fWriteLOSCallDataRandomly = 0.0f; // Chance per frame of writing a log. Obviously framerate-dependent.
#endif // #ifdef ASURA_LOS_TRACK_CALLS

/////////////////////////
// RayIntersectsSphere //
/////////////////////////
bool Asura_Maths::RayIntersectsSphere(const Asura_Vector_3& alpha, const Asura_Vector_3& beta, const Asura_Vector_3& centre, float radius, float *pfFirstIntersectDist/*=NULL*/, bool bTreatAsHollow /*=false*/)
{
#ifdef ASURA_SUPPORT_LOS_FUDGE
	radius += Asura_LOS::s_fLOSFudge;
#endif
	
	Asura_Vector_3 l = centre-alpha;
	float d = l*beta;

	float lsquared =l*l;
	float rsquared = radius*radius;

	if (d<0 && lsquared>rsquared) return false;

	float msquared = lsquared - d*d;

	if (msquared>rsquared) return false;

	if (!pfFirstIntersectDist)
		return true;
	float q = Asura_Maths::Sqrt(rsquared - msquared);
	if (lsquared > rsquared)
		*pfFirstIntersectDist = d - q;
	else
		*pfFirstIntersectDist = bTreatAsHollow ? (d + q) : 0.0f;
	// Note :	The above line means that the distance to intersection is zero if we start inside the sphere,
	//			as opposed to giving the actual intersection point.aw.
	// Note 2 : Changed to allow the distance to the intersection to be found if the sphere is being treated as hollow. RAR 20/06/2007
	return true;
}

//////////////////////
// RayIntersectsTri //
//////////////////////
#ifdef ASURA_SUPPORT_LOS_FUDGE
float Asura_Maths::RayIntersectsTri(const Asura_Vector_3& alpha, const Asura_Vector_3& beta, const Asura_Vector_3& _v0, const Asura_Vector_3& _v1, const Asura_Vector_3& _v2, bool& facingToward)
{
    Asura_Vector_3 v0, v1, v2;
    float fFudgeFactor = Asura_LOS::s_fLOSFudge;
    if (fFudgeFactor != 0.0f)
    {
        Asura_Vector_3 xCentroid = (_v0 + _v1 + _v2) * 0.333333f;
        Asura_Vector_3 xTemp;

        xTemp = _v0 - xCentroid;
        xTemp.Normalise();
        v0 = _v0 + (xTemp * fFudgeFactor);

        xTemp = _v1 - xCentroid;
        xTemp.Normalise();
        v1 = _v1 + (xTemp * fFudgeFactor);

        xTemp = _v2 - xCentroid;
        xTemp.Normalise();
        v2 = _v2 + (xTemp * fFudgeFactor);

		// AW - 14/07/03 - Move the polygon closer to the los origin. So that the polygon hit-test
		// behaves similar to the sphere and bounding box test.
		v0 -= beta * fFudgeFactor;
		v1 -= beta * fFudgeFactor;
		v2 -= beta * fFudgeFactor;
    }
    else
    {
        v0 = _v0;
        v1 = _v1;
        v2 = _v2;
    }
#else
float Asura_Maths::RayIntersectsTri(const Asura_Vector_3& alpha, const Asura_Vector_3& beta, const Asura_Vector_3& v0, const Asura_Vector_3& v1, const Asura_Vector_3& v2, bool& facingToward)
{
#endif
	const float epsilon = 1.0e-7f;
	Asura_Vector_3 e1 = v1-v0;
	Asura_Vector_3 e2 = v2-v0;

	Asura_Vector_3 p = beta^e2;
	//Asura_Vector_3 n = e1^e2;
	float a = e1*p;

	if (a>-epsilon && a<epsilon) return ASURA_LOS_MAX_DISTANCE;
	// if a is negative, it's facing away from the ray
	
	a = 1.0f/a; //because a can be negative, must take care of expression such as u > a && u/a > 1

	Asura_Vector_3 s = alpha-v0;
	float u = (s*p)*a;

	if (u<0.0f || u>1.0f) return ASURA_LOS_MAX_DISTANCE;

	Asura_Vector_3 q = s^e1;
	float v = (beta*q)*a;

	if (v<0.0f || u+v>1.0f) return ASURA_LOS_MAX_DISTANCE;

	float lambda = (e2*q)*a;

	if (a<0.0f) facingToward = false;
	else facingToward = true;

	return lambda;
}

float Asura_Maths::RayIntersectsTri(const Asura_AVector3& alpha, const Asura_AVector3& beta, const Asura_AVector3& v0, const Asura_AVector3& v1, const Asura_AVector3& v2, bool& facingToward)
{
	const float epsilon = 1.0e-7f;
	Asura_AVector3 e1 = v1-v0;
	Asura_AVector3 e2 = v2-v0;

	Asura_AVector3 p = beta^e2;
	//Asura_Vector_3 n = e1^e2;
	float a = e1*p;

	if (a>-epsilon && a<epsilon) return ASURA_LOS_MAX_DISTANCE;
	// if a is negative, it's facing away from the ray
	
	a = 1.0f/a; //because a can be negative, must take care of expression such as u > a && u/a > 1

	Asura_AVector3 s = alpha-v0;
	float u = (s*p)*a;

	if (u<0.0f || u>1.0f) return ASURA_LOS_MAX_DISTANCE;

	Asura_AVector3 q = s^e1;
	float v = (beta*q)*a;

	if (v<0.0f || u+v>1.0f) return ASURA_LOS_MAX_DISTANCE;

	float lambda = (e2*q)*a;

	if (a<0.0f) facingToward = false;
	else facingToward = true;

	return lambda;
}

/////////////////////////////////////////////////////////////////////////////////////////
// Asura_Maths::RayIntersectsBoundingBox:
//
// Test ray against bounding box.
//
// Input: xAlpha = origin of ray
//        xBeta  = direction of ray (should be normalised)
//        xBox   = axis aligned BB to compare against
//
// Output: Returns true if the ray hits BB or if the ray begins inside BB.
//
// If true, then it also returns:
//         pfDistance    = distance to intersection.
//         pxHitPosition = hit position.
//         pbInside      = true if ray started inside BB.
//         pxNormal      = normal at impact point, or inverse ray direction if inside.
//
// Written by KJL and modified by MGH.
//
/////////////////////////////////////////////////////////////////////////////////////////
bool Asura_Maths::RayIntersectsBoundingBox( const Asura_Vector_3& xAlpha,
											const Asura_Vector_3& xBeta,
											const Asura_Bounding_Box& xBox,
											float* pfDistance /*= 0*/,
											Asura_Vector_3* pxHitPosition /*= 0*/,
											bool *pbInside /*= 0*/,
											Asura_Vector_3* pxNormal /*= 0*/)
{
	bool bInside = true;

#ifdef ASURA_SUPPORT_LOS_FUDGE
    float fFudgeFactor = Asura_LOS::s_fLOSFudge;
	Asura_Vector_3 xMinCorner(xBox.MinX - fFudgeFactor, xBox.MinY - fFudgeFactor, xBox.MinZ - fFudgeFactor);
	Asura_Vector_3 xMaxCorner(xBox.MaxX + fFudgeFactor, xBox.MaxY + fFudgeFactor, xBox.MaxZ + fFudgeFactor);
#else
	Asura_Vector_3 xMinCorner(xBox.MinX, xBox.MinY, xBox.MinZ);
	Asura_Vector_3 xMaxCorner(xBox.MaxX, xBox.MaxY, xBox.MaxZ);
#endif

	Asura_Vector_3 xLambda(-1.0f,-1.0f,-1.0f);
	Asura_Vector_3 xIntersection;

	// KOR - 14/11/2005 - we were getting overflows when very small (denormalised) betas were passed in
	// This may cause false negatives when *just* skimming a BB, but hopefully an error of just 1e-30 should
	// make any problems negligible.
	const float fBetaEpsilon = 1.0e-30f;
	for(int i=0; i<3; i++)
	{
		if (xAlpha[i] < xMinCorner[i])
		{
			bInside = false;
			if (xBeta[i] <= fBetaEpsilon) return false;
		
			xIntersection[i] = xMinCorner[i];
			xLambda[i] = (xMinCorner[i] - xAlpha[i]) / xBeta[i];
		}
		else if (xAlpha[i] > xMaxCorner[i])
		{
			bInside = false;
			if (xBeta[i] >= -fBetaEpsilon) return false;
			
			xIntersection[i] = xMaxCorner[i];
			xLambda[i] = (xMaxCorner[i] - xAlpha[i]) / xBeta[i];	
		}
	}

	// Ray origin inside bounding box? Return as a hit.
	// (NOTE: also a hit if the ray starts on the surface of the BB.)
	if (bInside)
	{
		if (pxHitPosition) *pxHitPosition = xAlpha;
		if (pfDistance)    *pfDistance    = 0.0f;
		if (pbInside)      *pbInside      = true;
		// (AW - 11.11.2004) - Now return reversed direction. Arbitrary but better 
		// to return a valid normal than returning a zero vector.
		if (pxNormal)	   *pxNormal	  = -xBeta;
		return true;
	}

	// Find largest lambda value
	int iPlane = 0;
	if (xLambda[1] > xLambda[iPlane]) iPlane = 1;
	if (xLambda[2] > xLambda[iPlane]) iPlane = 2;

	Asura_Assert(xLambda[iPlane]>0.0f,"Impossible value");
	//if (xLambda[iPlane]<0.0f) return false; // MGH: this should be impossible, so the test is not needed.

	for (int i=0; i<3; i++)
	{
		if (i != iPlane)
		{
			xIntersection[i] = xAlpha[i] + xLambda[iPlane] * xBeta[i];
			if (xIntersection[i] < xMinCorner[i] || xIntersection[i] > xMaxCorner[i]) return false;
		}
	}

	/// We have an intersection then.
	if (pxHitPosition) *pxHitPosition = xIntersection;
	if (pfDistance)    *pfDistance    = xLambda[iPlane];
	if (pbInside)      *pbInside      = false;

	// Return the normal of the side of the BB that was hit.
	if (pxNormal)
	{
		pxNormal->Zero();

		if (xBeta[iPlane]>0.0f)
		{
			pxNormal->SetElement(iPlane, -1.0f);
		}
		else
		{
			pxNormal->SetElement(iPlane, 1.0f);
		}
	}

	return true;
}
// End of RayIntersectsBoundingBox


bool Asura_Maths::RayIntersectsBoundingBox_AllowInside( const Asura_Vector_3& xAlpha,
                                                        const Asura_Vector_3& xBeta,
                                                        const Asura_Bounding_Box& xBox,
                                                        float* pfDistance /*= 0*/,
                                                        Asura_Vector_3* pxHitPosition /*= 0*/,
                                                        bool *pbInside /*= 0*/,
                                                        Asura_Vector_3* pxNormal /*= 0*/)
{
    bool bInside = true;

#ifdef ASURA_SUPPORT_LOS_FUDGE
    float fFudgeFactor = Asura_LOS::s_fLOSFudge;
    Asura_Vector_3 xMinCorner(xBox.MinX - fFudgeFactor, xBox.MinY - fFudgeFactor, xBox.MinZ - fFudgeFactor);
    Asura_Vector_3 xMaxCorner(xBox.MaxX + fFudgeFactor, xBox.MaxY + fFudgeFactor, xBox.MaxZ + fFudgeFactor);
#else
    Asura_Vector_3 xMinCorner(xBox.MinX, xBox.MinY, xBox.MinZ);
    Asura_Vector_3 xMaxCorner(xBox.MaxX, xBox.MaxY, xBox.MaxZ);
#endif

    Asura_Vector_3 xLambda(-1.0f,-1.0f,-1.0f);
    Asura_Vector_3 xIntersection;

    // KOR - 14/11/2005 - we were getting overflows when very small (denormalised) betas were passed in
    // This may cause false negatives when *just* skimming a BB, but hopefully an error of just 1e-30 should
    // make any problems negligible.
    const float fBetaEpsilon = 1.0e-30f;
    for(int i=0; i<3; i++)
    {
        if (xAlpha[i] < xMinCorner[i])
        {
            bInside = false;
            if (xBeta[i] <= fBetaEpsilon) return false;
        
            xIntersection[i] = xMinCorner[i];
            xLambda[i] = (xMinCorner[i] - xAlpha[i]) / xBeta[i];
        }
        else if (xAlpha[i] > xMaxCorner[i])
        {
            bInside = false;
            if (xBeta[i] >= -fBetaEpsilon) return false;
            
            xIntersection[i] = xMaxCorner[i];
            xLambda[i] = (xMaxCorner[i] - xAlpha[i]) / xBeta[i];    
        }
    }

    int iPlane = 0;

    if( bInside )
    {
        for(int i=0; i<3; i++)
        {
            if( xBeta[i] > 0.0f )
            {
                xIntersection[i] = xMaxCorner[i];
                xLambda[i] = (xMaxCorner[i] - xAlpha[i]) / xBeta[i];    
            }
            else if( xBeta[i] < 0.0f )
            {
                xIntersection[i] = xMinCorner[i];
                xLambda[i] = (xMinCorner[i] - xAlpha[i]) / xBeta[i];
            }
            else
            {
                xLambda[i] = Asura_Maths::LargeFloat;
            }
        }

        // Find smallest lambda (values are all positive).
        if (xLambda[1] < xLambda[iPlane]) iPlane = 1;
        if (xLambda[2] < xLambda[iPlane]) iPlane = 2;
    }
    else
    {
        // Find largest lambda.
        if (xLambda[1] > xLambda[iPlane]) iPlane = 1;
        if (xLambda[2] > xLambda[iPlane]) iPlane = 2;
    }

    // In very specific cases our lambda value can actually be 0 here. This
    // case is eliminated by the early-out for start points inside the BB in
    // the standard RayIntersectsBoundingBox().
    Asura_Assert( (xLambda[iPlane] > 0.0f)
                  ||
                  ( (xLambda[iPlane] == 0.0f)
                    &&
                    bInside
                    &&
                    ( ((xAlpha[iPlane] == xMinCorner[iPlane]) && (xBeta[iPlane] < 0.0f))
                      ||
                      ((xAlpha[iPlane] == xMaxCorner[iPlane]) && (xBeta[iPlane] > 0.0f)) ) ),
                  "Impossible value" );

    for (int i=0; i<3; i++)
    {
        if (i != iPlane)
        {
            xIntersection[i] = xAlpha[i] + xLambda[iPlane] * xBeta[i];
            if (xIntersection[i] < xMinCorner[i] || xIntersection[i] > xMaxCorner[i]) return false;
        }
    }

    /// We have an intersection then.
    if (pxHitPosition) *pxHitPosition = xIntersection;
    if (pfDistance)    *pfDistance    = xLambda[iPlane];
    if (pbInside)      *pbInside      = bInside;

    // Return the normal of the side of the BB that was hit.
    if (pxNormal)
    {
        pxNormal->Zero();

        if (xBeta[iPlane]>0.0f)
        {
            pxNormal->SetElement(iPlane, -1.0f);
        }
        else
        {
            pxNormal->SetElement(iPlane, 1.0f);
        }
    }

    return true;
}


float Asura_Maths::GetMinDistSqdBetweenLineSegmentAndRay(const Asura_Vector_3 &xRayOrigin,
														const Asura_Vector_3 &xRayDirection,
														const Asura_Vector_3 &xLineSegmentOrigin,
														const Asura_Vector_3 &xLineSegmentVector)
{
	Asura_Vector_3 xSeparation;
	GetLeastOffsetBetweenLineSegmentAndRay(xRayOrigin, xRayDirection, xLineSegmentOrigin, xLineSegmentVector, xSeparation);
	return xSeparation.MagnitudeSquared();
}
// End of Asura_Maths::GetMinDistSqdBetweenLineSegmentAndRay()

void Asura_Maths::GetLeastOffsetBetweenLineSegmentAndRay(const Asura_Vector_3& xRayOrigin,
														const Asura_Vector_3& xRayDirection,
														const Asura_Vector_3& xLineSegmentOrigin,
														const Asura_Vector_3& xLineSegmentVector,
														Asura_Vector_3& xOffset,
														Asura_Vector_3* pxPositionOnLineSegment/* = NULL*/,
														Asura_Vector_3* pxPositionOnRay/* = NULL*/ )
{
	// (AW - 13.10.2004) - Code based on example from Essential Mathematics for Games.
	// Have tried to add descriptive names where possible, when not I am using the 
	// names from the sample code. Comments have been copied.
	Asura_Vector_3 xRayToLineSegment = xLineSegmentOrigin - xRayOrigin;
	float fLineSegmentDistanceSqd = xLineSegmentVector * xLineSegmentVector;
	float fB = xLineSegmentVector * xRayDirection;
	const float fC = 1.0f; //xRayDirection * xRayDirection;
	float fD = xLineSegmentVector * xRayToLineSegment;
	float fE = xRayDirection * xRayToLineSegment;

    float fSN;
	float fSD;
	float fTN;
	float fTD;
	float fDenom = (fLineSegmentDistanceSqd * fC) - (fB * fB);
	if (Asura_Maths::Abs(fDenom) < 0.000001f)
	{
        // clamp fSC to 0
		fSD = fC;
		fTD = fC;
		fSN = 0.0f;
		fTN = fE;
	}
	else
	{
        // clamp fSC within [0,1]
        fSD = fDenom;
		fTD = fDenom;
        fSN = (fB * fE) - (fC * fD);
        fTN = (fLineSegmentDistanceSqd * fE) - (fB * fD);
  
        // clamp fSC to 0
        if (fSN < 0.0f)
        {
            fSN = 0.0f;
            fTN = fE;
            fTD = fC;
        }
        // clamp fSC to 1
        else if (fSN > fSD)
        {
            fSN = fSD;
            fTN = fE + fB;
            fTD = fC;
        }

	}

	float fSC;
	float fTC;
    // clamp fTC within [0,+inf]
    // clamp fTC to 0
    if (fTN < 0.0f)
    {
        fTC = 0.0f;
        // clamp fSC to 0
        if ( -fD < 0.0f )
        {
            fSC = 0.0f;
        }
        // clamp fSC to 1
        else if ( -fD > fLineSegmentDistanceSqd )
        {
            fSC = 1.0f;
        }
        else
        {
            fSC = -fD / fLineSegmentDistanceSqd;
        }
    }
    else
    {
        fTC = fTN/fTD;
        fSC = fSN/fSD;
    }

	xOffset = xRayToLineSegment + (xLineSegmentVector * fSC) - (xRayDirection * fTC);
	if (pxPositionOnLineSegment)
	{
		*pxPositionOnLineSegment = xLineSegmentOrigin + (xLineSegmentVector * fSC);
	}
	if (pxPositionOnRay)
	{
		*pxPositionOnRay = xRayOrigin + (xRayDirection * fTC);
	}
}
// End of Asura_Maths::GetLeastOffsetBetweenLineSegmentAndRay()

bool Asura_Maths::RayIntersectsCylinder(const Asura_Vector_3& xRayOrigin,
										const Asura_Vector_3& xRayDirection,
										const Asura_Vector_3& xCylinderStart,
										const Asura_Vector_3& xCylinderVector,
										const float fCylinderRadius,
										float* pfDistance /* = NULL */,
										int* piHitFace /* = NULL */)
{
	// Partially adapted from ANSI C code from the article "Intersecting a Ray with a Cylinder"
	// by Joseph M. Cychosz and Warren N. Waggenspack, Jr.
	// in "Graphics Gems IV", Academic Press, 1994

	// This is quite possibly not optimal; certainly it's not a trivial problem.
	// I'd recommend doing a sphere test beforehand for early rejection.

	// First test against each cap.
	Asura_Vector_3 xNormalisedCylinderAxis = xCylinderVector;
	const float fCylinderLength = xNormalisedCylinderAxis.Normalise();

	const float fRadiusSquared = fCylinderRadius * fCylinderRadius;

	const float fRayDotCylinderAxis = xRayDirection * xNormalisedCylinderAxis;

	const Asura_Vector_3 xRayToCylinderStart = xCylinderStart - xRayOrigin;
	const float fDistanceToCylinderStartAlongAxis = xRayToCylinderStart * xNormalisedCylinderAxis;
	if(fDistanceToCylinderStartAlongAxis > 0.f)
	{
		// Ray starts above plane of start cap 
		if(fRayDotCylinderAxis < 0.f)
		{
			// Ray points away from start cap
			return false;
		}
		else
		{
			// Ray points towards start cap. Test for intersection point.
			const float fIntersectionDistance = fDistanceToCylinderStartAlongAxis / fRayDotCylinderAxis;
			const Asura_Vector_3 xIntersectionPoint = xRayOrigin + xRayDirection * fIntersectionDistance;
			const float fDistanceOnCapSquared = (xIntersectionPoint - xCylinderStart).MagnitudeSquared();
			if(fDistanceOnCapSquared <= fRadiusSquared)
			{
				if(pfDistance) { *pfDistance = fIntersectionDistance; }
				if(piHitFace) {	*piHitFace = -1; }
				return true;
			}
		}
	}

	const Asura_Vector_3 xCylinderEnd = xCylinderStart + xCylinderVector;
	const Asura_Vector_3 xRayToCylinderEnd = xCylinderEnd - xRayOrigin;
	const float fDistanceToCylinderEndAlongAxis = xRayToCylinderEnd * xNormalisedCylinderAxis;
	if(fDistanceToCylinderEndAlongAxis < 0.f)
	{
		// Ray starts above plane of end cap 
		if(fRayDotCylinderAxis > 0.f)
		{
			// Ray points away from end cap
			return false;
		}
		else
		{
			// Ray points towards end cap. Test for intersection point.
			const float fIntersectionDistance = fDistanceToCylinderEndAlongAxis / fRayDotCylinderAxis;
			const Asura_Vector_3 xIntersectionPoint = xRayOrigin + xRayDirection * fIntersectionDistance;
			const float fDistanceOnCapSquared = (xIntersectionPoint - xCylinderEnd).MagnitudeSquared();
			if(fDistanceOnCapSquared <= fRadiusSquared)
			{
				if(pfDistance) { *pfDistance = fIntersectionDistance; }
				if(piHitFace) {	*piHitFace = 1; }
				return true;
			}
		}
	}

	// Now we need to test against the cylinder.
	Asura_Vector_3 xPerpendicularDirection = xRayDirection ^ xNormalisedCylinderAxis;
	const float fPerpendicularLength = xPerpendicularDirection.Normalise();
	if(fPerpendicularLength == 0.f)
	{
		// Ray parallel to axis
		// We have already eliminated the caps, ray must be between them.
		// Either we start inside the cylinder or never hit it.
		const Asura_Vector_3 xVectorToAxis = xNormalisedCylinderAxis * fDistanceToCylinderStartAlongAxis - xRayToCylinderStart;
		const float fDistanceToAxisSquared = xVectorToAxis.MagnitudeSquared();
		if(fDistanceToAxisSquared <= fRadiusSquared)
		{
			if(pfDistance) { *pfDistance = 0.f;	}
			if(piHitFace) { *piHitFace = 0;	}
			return true;
		}
		else
		{
			return false;
		}
	}

	const float fShortestDistanceToAxis = xRayToCylinderStart * xPerpendicularDirection;
	const float fShortestDistanceToAxisSquared = fShortestDistanceToAxis * fShortestDistanceToAxis;
	if(fShortestDistanceToAxisSquared <= fRadiusSquared)
	{
		// Hit the infinite cylinder.
		// Now we need to ascertain whether the hit occurs within the caps.

		// Calculate distance to closest point on ray to axis.
		// Sorry, clumsy naming, but hard to explain succinctly.
		const Asura_Vector_3 xD1 = xRayToCylinderStart ^ xNormalisedCylinderAxis;
		const float fDistanceToClosestPoint = (xD1 * xPerpendicularDirection) / fPerpendicularLength;

		// Calculate distance along ray from closest point to cylinder surface.
		const Asura_Vector_3 xD2 = xPerpendicularDirection ^ xNormalisedCylinderAxis;
		const float fS = Asura_Maths::Abs(Asura_Maths::Sqrt(fRadiusSquared - fShortestDistanceToAxisSquared) / (xRayDirection * xD2));
		const float fFirstIntersectionDistance = fDistanceToClosestPoint - fS;
		if(fFirstIntersectionDistance < 0.f)
		{
			const float fSecondIntersectionDistance = fDistanceToClosestPoint + fS;
			// First intersection behind ray origin.
			if(fSecondIntersectionDistance < 0.f)
			{
				// Second intersection behind ray origin.
				return false;
			}
			else
			{
				// Must be inside the cylinder
				if(pfDistance) { *pfDistance = 0.f; }
				if(piHitFace) { *piHitFace = 0; }
				return true;
			}
		}
		else
		{
			const Asura_Vector_3 xIntersectionPoint = xRayOrigin + xRayDirection * fFirstIntersectionDistance;
			const Asura_Vector_3 xCylinderStartToIntersection = xIntersectionPoint - xCylinderStart;
			const float fIntersectionDistanceAlongCylinder = xCylinderStartToIntersection * xNormalisedCylinderAxis;
			if(fIntersectionDistanceAlongCylinder < 0.f || fIntersectionDistanceAlongCylinder > fCylinderLength)
			{
				return false;
			}
			if(pfDistance)
			{
				*pfDistance = fFirstIntersectionDistance;
			}
			if(piHitFace)
			{
				*piHitFace = 0;
			}
			return true;
		}
	}

	return false;
}

// unit tests need the definitions above this, but don't want to include the extra files that the actual LOS
// code is dependent on, so we want to lose this bit in the unit tests
#ifdef ASURA_MAIN

////////////////////////////////////////////////////////////////////////////////
// Asura_LOS
////////////////////////////////////////////////////////////////////////////////

// Static data
Asura_LOS_OutputData Asura_LOS::s_xData;
unsigned int         Asura_LOS::s_uLOSTestCount    = 0;
unsigned int		 Asura_LOS::s_uPolyFlagsToIgnore  = 0;
unsigned int		 Asura_LOS::s_uPolyFlagsToTestFor = UINT_MAX;

///////////////////////////
// TestAgainstEverything //
///////////////////////////
const Asura_LOS_OutputData* Asura_LOS::TestAgainstEverything(const Asura_LOS_InputData* pxInputData)
{
	// first check the environment
	TestAgainstEnvironment( pxInputData );
    
	// then check the entities, using any hit data from the environment as an upper distance limit
	Asura_Entity_System::FindEntityInLOS(pxInputData, &s_xData);

	// if we've hit an entity that's closer then clear the env hit flag
	if (s_xData.m_uHitEntity)
	{
		s_xData.m_bHitEnvironment = false;
	}

	return &s_xData;
}

////////////////////////////
// TestAgainstEnvironment //
////////////////////////////
const Asura_LOS_OutputData* Asura_LOS::TestAgainstEnvironment(const Asura_LOS_InputData* pxInputData)
{
	++s_uLOSTestCount;

	// setup output data and call LOS routine
	s_xData.Reset( pxInputData->m_fInitialMaximumRange );

	s_uPolyFlagsToIgnore  = pxInputData->m_uPolyFlagsToIgnore;
	s_uPolyFlagsToTestFor = pxInputData->m_uPolyFlagsToTestFor;

	s_xData.m_bHitEnvironment = Asura_Physics_Environment::FindPolyInLOS( pxInputData, &s_xData );

	return &s_xData;
}

///////////////////////////
// TestAgainstEntities   //
///////////////////////////
const Asura_LOS_OutputData* Asura_LOS::TestAgainstEntities(const Asura_LOS_InputData* pxInputData)
{
	++s_uLOSTestCount;

	// setup output data and call LOS routine
	s_xData.Reset( pxInputData->m_fInitialMaximumRange );

	s_uPolyFlagsToIgnore  = pxInputData->m_uPolyFlagsToIgnore;
	s_uPolyFlagsToTestFor = pxInputData->m_uPolyFlagsToTestFor;


	// Basically just a wrapper for the entity system call.
	Asura_Entity_System::FindEntityInLOS(pxInputData, &s_xData);

	return &s_xData;
}


void Asura_LOS_OutputData::Reset( float fInitialMaximumRange )
{
    m_fDistanceToIntersection = fInitialMaximumRange;
    m_uHitEntity              = 0;
    m_iHitBoneID              = -1;
    m_iHitAttachmentID        = Asura_AnimationAttachment::INVALID_ID;
    m_usPolyFlags             = 0;
    m_xNormal                 = Asura_Maths::ZeroVector3;
    m_bHitEnvironment         = false;
    m_bStartedInside          = false;

	#if defined ASURA_USE_MATERIAL_RESPONSE_SYSTEM
		m_uMaterialResponseHashID = ASURA_HASH_ID_UNSET;
	#endif
    m_sMaterialID             = ASURA_MATERIAL_NONE;

	m_uEnvironmentFaceIndex = 0;
}

void Asura_LOS_InputData::Initialise(const Asura_Vector_3& xOrigin, const Asura_Vector_3& xDirection, const Asura_Guid uEntityToIgnore)
{
	m_xOrigin = xOrigin;
	m_xDirection = xDirection;
	m_uEntityToIgnore = uEntityToIgnore;
	m_fInitialMaximumRange = ASURA_LOS_MAX_DISTANCE;
	m_uFlags = 0;
	m_uPolyFlagsToIgnore = AsuraPolygonFlag_IgnoreLOS;
	m_uPolyFlagsToTestFor = UINT_MAX;
}

void Asura_LOS_InputData::Initialise(const Asura_Vector_3& xOrigin, const Asura_Vector_3& xDirection, const Asura_Guid uEntityToIgnore, const float fMaxRange)
{
	m_xOrigin = xOrigin;
	m_xDirection = xDirection;
	m_uEntityToIgnore = uEntityToIgnore;
	m_fInitialMaximumRange = fMaxRange;
	m_uFlags = 0;
	m_uPolyFlagsToIgnore = AsuraPolygonFlag_IgnoreLOS;
	m_uPolyFlagsToTestFor = UINT_MAX;
}

void Asura_LOS_InputData::Initialise(const Asura_Vector_3& xOrigin, const Asura_Vector_3& xDirection, const Asura_Guid uEntityToIgnore, const bool bBoundingBoxOnly)
{
	m_xOrigin = xOrigin;
	m_xDirection = xDirection;
	m_uEntityToIgnore = uEntityToIgnore;
	m_fInitialMaximumRange = ASURA_LOS_MAX_DISTANCE;
	m_uFlags = 0;
	m_bBoundingBoxOnly = bBoundingBoxOnly;
	m_uPolyFlagsToIgnore = AsuraPolygonFlag_IgnoreLOS;
	m_uPolyFlagsToTestFor = UINT_MAX;
}

void Asura_LOS_InputData::Initialise(const Asura_Vector_3& xOrigin, const Asura_Vector_3& xDirection, const Asura_Guid uEntityToIgnore, const float fMaxRange, const bool bBoundingBoxOnly)
{
	m_xOrigin = xOrigin;
	m_xDirection = xDirection;
	m_uEntityToIgnore = uEntityToIgnore;
	m_fInitialMaximumRange = fMaxRange;
	m_uFlags = 0;
	m_bBoundingBoxOnly = bBoundingBoxOnly;
	m_uPolyFlagsToIgnore = AsuraPolygonFlag_IgnoreLOS;
	m_uPolyFlagsToTestFor = UINT_MAX;
}

void Asura_LOS_InputData::Initialise(const Asura_Vector_3& xOrigin, const Asura_Vector_3& xDirection, const Asura_Guid uEntityToIgnore, const float fMaxRange, const bool bBoundingBoxOnly, const u_int uFlagsToIgnore )
{
	m_xOrigin = xOrigin;
	m_xDirection = xDirection;
	m_uEntityToIgnore = uEntityToIgnore;
	m_fInitialMaximumRange = fMaxRange;
	m_uFlags = 0;
	m_bBoundingBoxOnly = bBoundingBoxOnly;
	m_uPolyFlagsToIgnore = uFlagsToIgnore;
	m_uPolyFlagsToTestFor = UINT_MAX;
}

void Asura_LOS_InputData::Initialise(const Asura_Vector_3& xOrigin, const Asura_Vector_3& xDirection, const Asura_Guid uEntityToIgnore, const float fMaxRange, const bool bBoundingBoxOnly, const u_int uFlagsToIgnore, const u_int uFlagsToTestFor )
{
	m_xOrigin = xOrigin;
	m_xDirection = xDirection;
	m_uEntityToIgnore = uEntityToIgnore;
	m_fInitialMaximumRange = fMaxRange;
	m_uFlags = 0;
	m_bBoundingBoxOnly = bBoundingBoxOnly;
	m_uPolyFlagsToIgnore = uFlagsToIgnore;
	m_uPolyFlagsToTestFor = uFlagsToTestFor;

    // (MP - 18.01.2005) Sanity check on flags-to-test-for. If they're set
    // to 0, as they were at one place in Rogue, then you'll end up not
    // actually testing against any environment polys (though most of the
    // work for the test will still be done.) If you want to just test
    // against entities or something then this should be done in some other
    // (more efficient) way.
    Asura_Assert( m_uPolyFlagsToTestFor, "" );
}


void Asura_LOS::AddCallTrackingData( u_int uCallType, const char* szFilename, u_int uLine, const char* szExtraDesc )
{
#ifdef ASURA_LOS_TRACK_CALLS

    const Asura_Hash_ID uFilenameHash  = Asura_GetHashID( szFilename );
    const Asura_Hash_ID uExtraDescHash = Asura_GetHashID( szExtraDesc );

    for( u_int u = 0; u < g_uNumDistinctLOSCalls; ++u )
    {
        LOSCallData& xData = g_axLOSCallData[u];
        if( xData.uFilenameHash == uFilenameHash && xData.uCallType == uCallType && xData.uExtraDescHash == uExtraDescHash )
        {
            ++xData.uCount;

            // In some circumstances tools will do a ton of LOS tests during
            // load, etc., so this test isn't then valid.
            #ifndef ASURA_TOOLS
            Asura_Assert( xData.uCount < 1000, "Either you're doing an insane number of LOS tests or you're not calling FlushCallTrackingData()" );
            #endif

            return;
        }
    }

    if( g_uNumDistinctLOSCalls >= uMAX_DISTINCT_LOS_CALLS_TO_TRACK )
    {
        Asura_Assert( false, "Too many distinct LOS calls this frame to track them all. Try increasing uMAX_DISTINCT_LOS_CALLS_TO_TRACK." );
    }

    LOSCallData& xNewData = g_axLOSCallData[g_uNumDistinctLOSCalls++];

    xNewData.uCallType      = uCallType;
    xNewData.uFilenameHash  = uFilenameHash;
    xNewData.szFilename     = szFilename;
    xNewData.uExtraDescHash = uExtraDescHash;
    xNewData.szExtraDesc    = szExtraDesc;
    xNewData.uLine          = uLine;
    xNewData.uCount         = 1;

#endif // #ifdef ASURA_LOS_TRACK_CALLS
}


// This function needs to be called once per frame.
void Asura_LOS::FlushCallTrackingData( void )
{
#ifdef ASURA_LOS_TRACK_CALLS

#ifdef ASURA_SUPPORT_COMMAND_CONSOLE
    // Register something in the command console, if it's not already there.
    // Leave the removal as default, ie. remove at reset, because we'll
    // probably be adding this during the game loop. We'll just re-add it
    // again at some point after the reset.
    {
        // Assume if one's missing then they all are.
        if( !Asura_CommandConsole::VarExists(L"Debug.Profile.OutputLOSCallLogOnce") )
        {
            Asura_CommandConsole::AddVar( L"Debug.Profile.OutputLOSCallLogOnce",       &g_bWriteLOSCallDataNextFrame  );
            Asura_CommandConsole::AddVar( L"Debug.Profile.OutputLOSCallLogEveryFrame", &g_bWriteLOSCallDataEveryFrame );
            Asura_CommandConsole::AddVar( L"Debug.Profile.OutputLOSCallLogRandomly",   &g_fWriteLOSCallDataRandomly   );
        }
    }
#endif

    bool bNeedToWriteLogfile = ( g_bWriteLOSCallDataNextFrame
                                 ||
                                 g_bWriteLOSCallDataEveryFrame
                                 ||
                                 (Asura_Random::GetFloat() < g_fWriteLOSCallDataRandomly) );

    if( bNeedToWriteLogfile )
    {
        if( g_uNumDistinctLOSCalls )
        {
            // First time we log during a session clear the logfile. After
            // that just append.
            static bool bNeedToClearLogfile = true;

            // Sort the calls by descending count.
            {
                LOSCallData xTempData;

                for( u_int u = 0; u < g_uNumDistinctLOSCalls; ++u )
                {
                    u_int uHighest = u;

                    for( u_int v = u + 1; v < g_uNumDistinctLOSCalls; ++v )
                    {
                        if( g_axLOSCallData[v].uCount > g_axLOSCallData[uHighest].uCount )
                        {
                            uHighest = v;
                        }
                    }

                    if( uHighest != u )
                    {
                        xTempData = g_axLOSCallData[u];
                        g_axLOSCallData[u] = g_axLOSCallData[uHighest];
                        g_axLOSCallData[uHighest] = xTempData;
                    }
                }
            }

            if( bNeedToClearLogfile )
            {
                Asura_SimpleLogfileClear( szLOS_CALLS_LOGFILE );
            }
            else
            {
                // Just add a couple of blank lines to separate the next lot.
                Asura_SimpleLogfileOutput(( szLOS_CALLS_LOGFILE, "\n\n" ));
            }

            Asura_SimpleLogfileOutput(( szLOS_CALLS_LOGFILE, "(frame number: %u)\ncount    call type    call site\n", Asura_Timers::GetFrameNumber() ));

            u_int uTotal = 0;
            for( u_int u = 0; u < g_uNumDistinctLOSCalls; ++u )
            {
                const LOSCallData& xData = g_axLOSCallData[u];
                uTotal += xData.uCount;

                Asura_SimpleLogfileOutput(( szLOS_CALLS_LOGFILE,
                                            "%5u    %9u    %s @ %u%s%s%s\n",
                                            xData.uCount,
                                            xData.uCallType,
                                            xData.szFilename,
                                            xData.uLine,
                                            (xData.szExtraDesc ? " (" : ""), (xData.szExtraDesc ? xData.szExtraDesc : ""), (xData.szExtraDesc ? ")" : "") ));
            }

            Asura_SimpleLogfileOutput(( szLOS_CALLS_LOGFILE, "(total: %u)\n", uTotal ));

#ifdef ASURA_SUPPORT_COMMAND_CONSOLE
            Asura_CommandConsole::Printf( "Call log %s to '%s'.", (bNeedToClearLogfile ? "written" : "appended"), szLOS_CALLS_LOGFILE );
#endif

            bNeedToClearLogfile = false;
        }

        g_bWriteLOSCallDataNextFrame = false;
    }

    g_uNumDistinctLOSCalls = 0;

#endif // #ifdef ASURA_LOS_TRACK_CALLS
}

#endif // ASURA_MAIN
