/*****************************************************************************
 * $Id: eng_collision.cc,v 1.122 2006/10/10 04:14:55 devel Exp $
 * @file
 * @author	Jim E. Brooks  http://www.jimbrooks.org
 * @brief	Collision detection.
 * @remarks
 * @verbatim
 *
 * Creating Detector objects:
 * --------------------------
 *
 * Constructing a Detector object requires an ObjectMesh object
 * to be fully-constructed.  Therefore, a Detector must be created
 * at the end of the ObjectMesh constuctor using the new operator.
 *
 * Detectors link themselves into a list instead of Objects storing
 * Detector pointers into Object members.  So the following code
 * which appears egregious is really intentional:
 *
 * ObjectMesh::ObjectMesh( QuadrantPtrConst q )
 * {
 *     new DetectorRadius( this );  // indeed, its pointer isn't stored
 * } 
 *
 * Collision-detection tests:
 * --------------------------
 *
 * The collision-detection uses 3 different algorithms with increasing precision
 * and computation expense.  The first two are approximate and the third/final
 * is considered exact.
 *
 * The first collision-detection test involves measuring the distance a Dyna object
 * is from this object and compares the distance against the object's radius.
 * This first test is quick but might be very imprecise depending on the object's shape.
 *
 * The second collision-detection test uses an algorithm that conceptually
 * divides a 3D object into rectangular slices and constructs a rectangle to enclose
 * each slice (slices are stacked vertically in the world Y axis).  A simple comparison
 * of 2D min/max (X,Z) pairs of the slice (correlating to the dyna's Y altitude)
 * versus the dyna's X,Z offset indicates if a Dyna object has moved inside
 * of any slice (which would indicate a collision).
 * Example of how a hill would be sliced:
 *                        ____
 *                  _____|____|____          ^ +Y (world)
 *             ____|_______________|_____    |
 *            |__________________________|   |
 *
 * The third/final collision-detection test is considered exact.
 * It tests if a Dyna has passed thru a polygon and is computationally expensive.
 * @endverbatim
 *//*
 * LEGAL:	COPYRIGHT (C) 2004 JIM E. BROOKS
 *          THIS SOURCE CODE IS RELEASED UNDER THE TERMS
 *          OF THE GNU GENERAL PUBLIC LICENSE (GPL).
 *****************************************************************************/

#define ENG_COLLISION_CC 1
#include "eng.hh"
#include "eng_collision.hh"
#include "gfx_misc.hh"

/*****************************************************************************
 * Construct a collision-detection object for a 3D object.
 * @pre		Object's radius was calculated.
 * @param	obj
 *          Owner.
 * @param	owner.GetRadius() (implicit)
 *			Can be approximate but should not be under-measured.
 * @param	owner.GetPosition() (implicit)
 *			The center of the object in world coords.
 * @param	owner.GetWorldVertexs() (implicit)
 *			Array of world vertexes of this object.
 *****************************************************************************/
DetectorRadius::DetectorRadius( ObjectMesh& obj )
    : Parent(obj)
{
CHECK_TYPESIG( &obj, TYPESIG_OBJECT );
ASSERT_OR_RETURN( obj.GetRadius() > 0 );

	// Prepare the first (rough) test that is based on distance and radius.
	fp r = obj.GetRadius();
	mRadiusSquare = r * r;

	// Link this Detector object to the quadrant's list of Detector objects.
	obj.SetDetector( obj.GetQuadrant()->AddDetector( this ) );
}

/*****************************************************************************
 * Construct a collision-detection object for a 3D object.
 * @pre		Object's radius was calculated.
 * @param	obj
 *          Owner.
 * @param	minY, maxY
 *			The lowest and highest world Y coords of this object.
 * @param	owner.GetRadius() (implicit)
 *			Can be approximate but should not be under-measured.
 * @param	owner.GetPosition() (implicit)
 *			The center of the object in world coords.
 * @param	owner.GetWorldVertexs() (implicit)
 *			Array of world vertexes of this object.
 *****************************************************************************/
DetectorAll::DetectorAll( ObjectMesh& obj, fp minY, fp maxY )
    : Parent(obj)
{
CHECK_TYPESIG( &obj, TYPESIG_OBJECT );
ASSERT( maxY > minY );
    mEnabled = false;  // in case of return-if-error

	// Prepare the second (finer) collision detection test
	// that is based on rectangular slices.
	mSliceCnt	= 15;
	mSlices		= new RectXZ[mSliceCnt];
	mSlicesMinY = minY;         // bottom Y of stack of slices
	mSlicesMaxY = maxY;         // top Y
    mPolygonInterior = NULL;    // lazy allocation

	// Build an array of structs that define each rectangular slice (XZ).
	fp y    = minY;
	fp yInc = (maxY-minY)/mSliceCnt;
	const WorldVertex* v    = obj.GetWorldVertexs();
	const uint         vcnt = obj.GetVertexCnt();
	ASSERT_OR_RETURN( v && vcnt > 0 );

	// In case a slice doesn't contain a vertex.
	RectXZ rectDefault;
	rectDefault.mMinX = rectDefault.mMinZ = FLOAT_LARGE;
	rectDefault.mMaxX = rectDefault.mMaxZ = FLOAT_SMALL;

	for ( uint s = 0; s < mSliceCnt; ++s )
	{
		// y2 is next higher floor (so to speak).
		fp y2 = y + yInc;
		mSlices[s].mMinX = mSlices[s].mMinZ = FLOAT_LARGE;
		mSlices[s].mMaxX = mSlices[s].mMaxZ = FLOAT_SMALL;

		// For each vertex.
		for ( uint i = 0; i < vcnt; ++i )
		{
			// Skip if the Y coord of this vertex is above/below this rectangular slice.
			if ( v[i].y >= y && v[i].y <= y2 )
			{
				// Accumulate 2D min:max pairs of this rectangular slice.
				mSlices[s].Grow( v[i].x, v[i].z );
			}

			rectDefault.Grow( v[i].x, v[i].z );
		}

		y = y2; // upwards
	}

	// FLOAT_SMALL/LARGE are so small/large and cause so much precision loss
	// that testing with !=/== (even with constants) will fail!

	// Some slices might not contain any vertex in which case
	// some corners of the slice's rectangle were really assigned.
	// Correct using a default rectangle that encloses all slices.
	ASSERT( ! FEQ_FLOAT_LARGE( rectDefault.mMinX ) );
	ASSERT( ! FEQ_FLOAT_LARGE( rectDefault.mMinZ ) );
	ASSERT( ! FEQ_FLOAT_SMALL( rectDefault.mMaxX ) );
	ASSERT( ! FEQ_FLOAT_SMALL( rectDefault.mMaxZ ) );
	for ( uint s = 0; s < mSliceCnt; ++s )
	{
		if ( FEQ_FLOAT_LARGE(mSlices[s].mMinX) ) mSlices[s].mMinX = rectDefault.mMinX;
		if ( FEQ_FLOAT_LARGE(mSlices[s].mMinZ) ) mSlices[s].mMinZ = rectDefault.mMinZ;
		if ( FEQ_FLOAT_SMALL(mSlices[s].mMaxX) ) mSlices[s].mMaxX = rectDefault.mMaxX;
		if ( FEQ_FLOAT_SMALL(mSlices[s].mMaxZ) ) mSlices[s].mMaxZ = rectDefault.mMaxZ;
	}

	// Slightly expand the slices for accurate collision-detection by the slice method.
	// Some expansion is also necessary to give the third test (polygon interior test)
	// the opportunity to detect a polygon-facing transition.
	for ( uint s = 0; s < mSliceCnt; ++s )
	{
		const fp marginFactor = 0.15;
		fp xMargin = (mSlices[s].mMaxX - mSlices[s].mMinX) * marginFactor;
		fp zMargin = (mSlices[s].mMaxZ - mSlices[s].mMinZ) * marginFactor;
		mSlices[s].mMinX -= xMargin;
		mSlices[s].mMaxX += xMargin;
		mSlices[s].mMinZ -= zMargin;
		mSlices[s].mMaxZ += zMargin;
	}

    mEnabled = true;  // ok
}
DetectorAll::~DetectorAll()
{
	DELETE_ARR_NULL( mSlices );
	DELETE_NULL( mPolygonInterior );
}

/*****************************************************************************
 * @return True if a dynamic object has (probably) collided into this object.
 * Or false (with more certainly) if no collision.
 *****************************************************************************/
bool
DetectorRadius::Collided( Dyna& dyna )
{
	if ( UX( ! gEng.IfCollisions() ) )  // must be prior to checks (special case)
		return false;

CHECK_TYPESIG( &mOwner, TYPESIG_OBJECT );
CHECK_TYPESIG( &dyna,   TYPESIG_DYNA );
ASSERT( mValid );

	// If this object is indestructible.
	if ( UX( ! mEnabled ) )
		return false;

	// First test (approximate) by distance/radius.
	if ( EX( ! DetectByRadius( dyna )) )
		return false;

    // Probable collision.
    return true;
}
bool
DetectorAll::Collided( Dyna& dyna )
{
    // A test that returns false is considered certain.
    // A true test is considered as possible-but-to-be-determined-by-a-more-precise-test.

	// First test (approximate) by distance/radius.
    if ( EX( ! DetectorRadius::Collided(dyna) ) )
        return false;

	// Second test (approximate) by rectangular slices.
	if ( EX( ! DetectBySlices(dyna) ) )
		return false;

	// Third test (precise) by polygon interior testing.
	return DetectByPolygonInterior( dyna );
}

/*****************************************************************************
 * @return True if a dynamic object has collided into this object.
 * This is an approximate test based on comparing radius and distance.
 *****************************************************************************/
bool
DetectorRadius::DetectByRadius( Dyna& dyna )
{
CHECK_TYPESIG( &mOwner, TYPESIG_OBJECT );
CHECK_TYPESIG( &dyna,   TYPESIG_DYNA );

	// Calculate the distance between the objects.
	// For speed, skip calculating the square root of distance^2.
	// This optimization is what the radiusSquare member is for.
	fp xd, yd, zd, distanceSquare;
	const Position center = mOwner.GetPosition();
	xd = center.x - dyna.mCm[Ox];
	yd = center.y - dyna.mCm[Oy];
	zd = center.z - dyna.mCm[Oz];
	distanceSquare = xd*xd + yd*yd + zd*zd; // distance^2
	const fp dynaRadius = dyna.GetRadius();
	return distanceSquare < (mRadiusSquare + SQUARE(dynaRadius));
}

/*****************************************************************************
 * @return True if a dynamic object has collided into this object.
 * This is an approximate test based on rectangular slices.
 *****************************************************************************/
bool
DetectorAll::DetectBySlices( Dyna& dyna )
{
CHECK_TYPESIG( mSlices, TYPESIG_LIB_RECTXZ );
CHECK_TYPESIG( &mOwner, TYPESIG_OBJECT );
CHECK_TYPESIG( &dyna,   TYPESIG_DYNA );

	// Does the altitude of the dyna object correlate to any rectangular slice?
	if ( dyna.mCm[Oy] < mSlicesMinY || dyna.mCm[Oy] >= mSlicesMaxY )
		return false;

	// Correlate Dyna's altitude (world Y) to a rectangular slice.
	const fp sliceHeight = (mSlicesMaxY - mSlicesMinY) / mSliceCnt;
	uint s = int((dyna.mCm[Oy] - mSlicesMinY) / sliceHeight);
ASSERT_OR_RETURN_VAL( s < mSliceCnt, false );

	// Return true if the dyna's (X,Z) is inside the rectangular slice.
	return mSlices[s].IfInside( dyna.mCm[Ox], dyna.mCm[Oz] );
}

/*****************************************************************************
 * @return True if a dynamic object has collided into this object.
 * This is a precise test that detects when the Dyna has passed thru a polygon
 * of another object.
 * @remarks Documented at doc/collisionDetectionPolygon/collisionDetectionPolygon_2dSquares.html
 *****************************************************************************/
bool
DetectorAll::DetectByPolygonInterior( Dyna& dyna )
{
	// Because of the possibility of multiple views, state is saved per-view across frames.

	// To conserve memory, only allocate a PolygonInterior object when needed.
	if ( UX(mPolygonInterior == NULL) )
    {
        mPolygonInterior = new PolygonInterior( mOwner.GetPolygonCnt() );
    }

	// Get/update frame numbers.
	const uint viewNum = VIEW_NUM();
	const uint framePrev = mPolygonInterior->GetFrame( viewNum );
	const uint frameCurr = gEng.mView.GetViewFrameCnt();
	mPolygonInterior->SetFrame( viewNum, frameCurr );

	// For the arrays of polygon-facing bools, swap the current and previous arrays,
	// compute the current.
	mPolygonInterior->SwapArrays( viewNum );

	// The test of the Dyna-facing-polygon-then-not-facing condition can only be
	// tested the second time this function is called during two consecutive frames.
	// Otherwise, the previous boolean array is invalid as it doesn't pertain
	// to the previous consecutive frame.
	const bool testPolygonFacing = (framePrev + 1 == frameCurr);

	// Compute the current array of polygon-facing booleans.
	// For each polygon.
	const WorldVertex* wv	   = mOwner.GetWorldVertexs();
    const Normal*      normals = mOwner.GetWorldNormals();
	uint i = 0;
	const Dlist<Polygon>& dlist = mOwner.GetPolygonList().GetDlist();
	for ( const Dlink<Polygon>* dlink = dlist.ForStart();
          dlist.ForTest(dlink);
          dlist.ForNext(dlink),++i )
	{
		// Test if the Dyna is facing this polygon.
		// Translate the Dyna into the polygon's normal space.
		// In normal space, calculate the dot product between
		// the translated Dyna and the normal vector.
		const Vix& vixNormOrig = normals[i].mVixNormOrig;
		const NormalVertex dynaNorm( dyna.mCm[Ox] - wv[vixNormOrig].x,
	                                 dyna.mCm[Oy] - wv[vixNormOrig].y,
                                     dyna.mCm[Oz] - wv[vixNormOrig].z );
		const fp dotProduct = DotProduct( normals[i].mNorm, dynaNorm );

		// Remember in the current boolean array if the Dyna is facing this polygon.
		mPolygonInterior->SetFacingCurr( viewNum, i, dotProduct < 0 );

		if ( testPolygonFacing )
		{
			// Condition 1 of 2:
			// A collision might have occurred if the Dyna was facing the polygon
			// in the previous frame but isn't facing in this frame.
			if (      mPolygonInterior->GetFacingPrev( viewNum, i )    // if was facing--
	             && ! mPolygonInterior->GetFacingCurr( viewNum, i ) )  // --and not isn't
			{
				// Begin the polygon interior test: the Dyna did collide into this polygon
				// if the Dyna's origin is inside the interior of this polygon.
				const Polygon* const polygon = dlink->mObj;
				CHECK_TYPESIG( polygon, TYPESIG_POLYGON );

				// For each vertex of this polygon.
				static Rect<fp> rect( 0, 0, 0, 0 );
				const Vix* vixArr = polygon->GetVixArr();
				const uint vixCnt = polygon->GetVixCnt();
				for ( uint vixArrIdx = 0; vixArrIdx < vixCnt; ++vixArrIdx )
				{
					// Transform (X,Y) of this polygon's vertex
					// into the Dyna's local space (Z unnecessary).
					const Vix vix = vixArr[vixArrIdx];
					const Matrix& m = dyna.mCm;
					const fp x = wv[vix].x - m[Ox];
					const fp y = wv[vix].y - m[Oy];
					const fp z = wv[vix].z - m[Oz];
					const fp x2 = RotX( x, y, z, m );
					const fp y2 = RotY( x, y, z, m );

					// Accumulate a 2D rectangle consisting of min/max (X,Y) pairs.
					if ( vixArrIdx == 0 )
					{
						rect.x1 = rect.x2 = x2;
						rect.y1 = rect.y2 = y2;
					}
					else
						rect.Grow( x2, y2 );
				}

				// Condition 2 of 2:
				// A collision occurred if the 2D rectangle encloses the Dyna's origin
				// (ie, the Dyna's origin is inside the interior of the 2D rectangle).
				if (    rect.x1 < 0 && rect.y1 < 0
                     && rect.x2 > 0 && rect.y2 > 0 )
					return true;
			}
		}
	}

	return false;
}
