/*****************************************************************************
 * $Id: game_pony_water.cc,v 1.33 2006/08/10 03:18:59 devel Exp $
 * @file
 * @author	Jim E. Brooks  http://www.jimbrooks.org
 * @brief	Water objects.
 * @remarks @verbatim
 * Bodies of water are generated starting with the top-level Water object.
 * Every quadrant has its own Water object.
 *
 * A Lake is rendered by a Lake object that is generated from a LakeBasis object.
 * The LakeBasis class generates an array of "tiles" in which a tile is a byte
 * that indicates if and how much water is over a correlating square in world space.
 * The tile scheme was motivated by the requirement of good fog quality
 * (prior prototype code rendered huge circular polygons for lakes but
 * fog quality was too poor).  Rendering lakes using quads would result in
 * a blocky appearance, so a form of anti-aliasing is done which tries to smooth
 * gaps between quads using triangles.  The tiles adjacent (4 cardinal directions)
 * to a water tile is examined.
 *
 * The tiles[] array of the LakeBasis class is constructed by randomly making
 * a set of points (in world space) that are equi-distance from the previous
 * and following point.  Then the points are "radiated" over tile space.
 * For every tile, if it is inside the radius of any point, then that tile
 * is marked as being under water.
 * @endverbatim
 *//*
 * LEGAL:	COPYRIGHT (C) 2004 JIM E. BROOKS
 *          THIS SOURCE CODE IS RELEASED UNDER THE TERMS
 *          OF THE GNU GENERAL PUBLIC LICENSE (GPL).
 *****************************************************************************/

#define GAME_PONY_WATER_CC 1
#include "game_pony_common.hh"
#include "game_pony_water.hh"
#include "gfx_random.hh"

////////////////////////////////////////////////////////////////////////////////
////////////////////////////////  Water  ///////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////

/*****************************************************************************
 * Top-level constructor of bodies of water.
 *****************************************************************************/
Water::Water( QuadrantPtrc q )
:   Special(q),
	mLakeDlist(Dlist<Lake>::KEEP) // Quadrant::Shrink() will delete objects
{
	// Make bodies of waters in non-edge quadrants (see comments in eng_world.cc).
	if (    ! gWorld.IfEdgeQuadrant( q )
         && ! gWorldParm.mTerrain.mDesert
         && gWorldParm.mWater.mDensity > 0.05 )
	{
		MakeLakes( q );
	}

	FinalConstruction();
	DEBUG_CODE( CheckObjectCtor(); )
}
Water::~Water()
{
	DEBUG_CODE( CheckObjectDtor(); )
}

/*****************************************************************************
 * Make lakes.
 *****************************************************************************/
void
Water::MakeLakes( QuadrantPtrc q )
{
CHECK_TYPESIG( q, TYPESIG_QUADRANT );

	// Iterate thru subdivisions of the quadrant and randomly
	// select one to have a lake according to lake density.
	const fp inc = Min<fp>( WORLD(5000.0), gWorld.GetQuadrantEdge() / 20 );
	const fp qx1 = q->GetCube().x1;
	const fp qx2 = q->GetCube().x2;
	const fp qz1 = q->GetCube().z1;
	const fp qz2 = q->GetCube().z2;
	for ( fp x = qx1; x < qx2; x += inc )
	{
	for ( fp z = qz1; z < qz2; z += inc )
		{
			if ( random_f() > gWorldParm.mWater.mDensity ) continue;

			// Randomly create basis parameters for a lake.
			LakeBasis* lb = new LakeBasis( q, this, x+random_f(inc), z+random_f(inc) );

			// Create a lake object from acceptable basis parameters.
			// Reject if:
			// - basis parameters are invalid
			// - too close to initial viewpoint
			// - over another body of water
			// - overlaps another quadrant
			if (    lb->mValid
	             && ! gWorld.TooCloseToInitialViewpoint( lb->mPosrad )
	             && ! IfOverWater(                       lb->mPosrad )
	             && q->IfInside( lb->mPosrad ) )
			{
				mLakeDlist.Append( new Lake( q, lb ) ); // Lake object will delete lb
			}
			else
			{
				delete lb;
			}
		}
	}
}

/*****************************************************************************
 * This test applies to one quadrant (every Water object is per quadrant).
 * @return True if object is over any body of water in this Water object.
 *****************************************************************************/
bool
Water::IfOverWater( const Posrad& posrad ) const
{
	// Over any lake?
	for ( const Dlink<Lake>* dlink = mLakeDlist.ForStart();
          mLakeDlist.ForTest(dlink);
          mLakeDlist.ForNext(dlink) )
	{
		Lake* lake = dlink->mObj;
		if ( lake->IfOver( posrad ) ) return true;
	}

	return false;
}

////////////////////////////////////////////////////////////////////////////////
////////////////////////////    LakeBasis      /////////////////////////////////
////////////////////////////////////////////////////////////////////////////////

/*****************************************************************************
 * Randomly create basis parameters for a lake.
 * The basis parameters may be invalid (eg lake would overlap quadrants)
 * in which case LakeBasis.valid will be false.
 *****************************************************************************/
LakeBasis::LakeBasis( QuadrantPtrc q, const Water* water, const fp cx, const fp cz )
{
	mTileWidth						= WORLD(2000.0);
	mPointsRadius					= mTileWidth * 6;
	const fp pointsRadiusEnlarged	= mPointsRadius * 1.1;
	const fp equiDist				= mPointsRadius * 0.7;

	// Randomly create n points (in world coords at ground level),
	// in random directions equi-distant from the previous and following one.
	// A rectangle is grown that encloses the radiated points.
	// If any point, when radiated, causes the rectangle to overlap
	// the current quadrant, the point is discarded, and a retry is done.
    mPointCnt = Max( 10u, random_ui(100) );
	mPointCnt = Min( int(mPointsMax), int(mPointCnt) );
	int retries = 0; const int retriesLimit = 50;
	int i;
	for ( i = 0; i < mPointCnt; ++i )
	{
Retry:
		if ( i == 0 )
		{
			// This is the first point.  Pick a random point in current quadrant.
			mPoints[0].x = cx;
			mPoints[0].y = ALTITUDE_WATER;
			mPoints[0].z = cz;

			// Initialize rectangle struct.
			mRect.mMinX = mRect.mMinZ = FLOAT_LARGE;
			mRect.mMaxX = mRect.mMaxZ = FLOAT_SMALL;

			mPosrad.Set( 0.0, 0.0, 0.0, 0.0 );
		}
		else
		{
			// Create a new point equi-distant from the previous one
			// in any direction.
			int deg = random_ui( 360 );
			mPoints[i].x = mPoints[i-1].x + sin_deg( deg ) * equiDist;
			mPoints[i].y = mPoints[i-1].y;
			mPoints[i].z = mPoints[i-1].z - cos_deg( deg ) * equiDist;
		}

		// Save state in case of undo.
		RectXZ rectSaved   = mRect;
		Posrad posradSaved = mPosrad;

		// Grow the rectangle to enclose the set of circumscribed points.
		mRect.mMinX = Min( mRect.mMinX, mPoints[i].x - pointsRadiusEnlarged );
		mRect.mMaxX = Max( mRect.mMaxX, mPoints[i].x + pointsRadiusEnlarged );
		mRect.mMinZ = Min( mRect.mMinZ, mPoints[i].z - pointsRadiusEnlarged );
		mRect.mMaxZ = Max( mRect.mMaxZ, mPoints[i].z + pointsRadiusEnlarged );

		// Calculate approximate values for position/radius.
		// These members correlate to the center/radius members of class Fixed.
		mPosrad.x = (mRect.mMinX + mRect.mMaxX) * 0.5;
        mPosrad.y = ALTITUDE_WATER;
		mPosrad.z = (mRect.mMinZ + mRect.mMaxZ) * 0.5;
		mPosrad.mRadius = 0.6 * Max( (mRect.mMaxX - mRect.mMinX), (mRect.mMaxZ - mRect.mMinZ) );

		// Did this radiated point cause the bounding rectangle
		// to overlap into another quadrant?
		if (    ! q->IfInside( mPosrad )
             || water->IfOverWater( mPosrad ) )
		{
			// Undo changes.
			mRect   = rectSaved;
			mPosrad = posradSaved;

			// Try another random point (using same index).
			if ( i > 0  &&  retries++ < retriesLimit )
				goto Retry;
			else
				break;
		}
	}

	// Return if no points were valid.
	if ( i == 0 ) goto Fail;
	if ( i < mPointCnt ) mPointCnt = i; // in case of break

	// Compute the 2D dimensions of tile array (used later by Lake object).
	// Translate width of rectangle from world coords to tile units by division.
	mTileDimX = int((mRect.mMaxX - mRect.mMinX) / mTileWidth);
	mTileDimZ = int((mRect.mMaxZ - mRect.mMinZ) / mTileWidth);
	if ( UX(mTileDimX <= 0 || mTileDimZ <= 0) ) goto Fail;

	mValid = mPosrad.mRadius > 0.0;
	return;
Fail:
	mValid = false;
	return;
}

////////////////////////////////////////////////////////////////////////////////
/////////////////////////////////  Lake  ///////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////

/*****************************************************************************
 * Construct/destruct a lake object.
 *****************************************************************************/
Lake::Lake( QuadrantPtrc q, LakeBasis* lb )
	: Parent(q)
{
	// Lazy construction -- construction is deferred to Get*().
	mLb			 = lb;
	mTiles 		 = NULL;
    SetPosition( Position( lb->mPosrad.x,
                           lb->mPosrad.y,
                           lb->mPosrad.z) );
//	SetRadius( lb->mPosrad.mRadius ); // rely on CalcRadius()
	GAME_STATS_CODE( ++gGame.mStats.mLakes; )
	FinalConstruction();
	DEBUG_CODE( CheckObjectCtor(); )
}
Lake::~Lake()
{
	delete mLb;
	delete [] mTiles;
	GAME_STATS_CODE( --gGame.mStats.mLakes; )
	DEBUG_CODE( CheckObjectDtor(); )
}

/*****************************************************************************
 * See Object::CalcRadius().
 *****************************************************************************/
void
Lake::CalcRadius( void )
{
	// Vertexs for visibility test.
	mWorldVertexsVisiTest[0].x = mLb->mRect.mMinX;
	mWorldVertexsVisiTest[0].y = ALTITUDE_WATER;
	mWorldVertexsVisiTest[0].z = mLb->mRect.mMinZ;

	mWorldVertexsVisiTest[1].x = mLb->mRect.mMinX;
	mWorldVertexsVisiTest[1].y = ALTITUDE_WATER;
	mWorldVertexsVisiTest[1].z = mLb->mRect.mMaxZ;

	mWorldVertexsVisiTest[2].x = mLb->mRect.mMaxX;
	mWorldVertexsVisiTest[2].y = ALTITUDE_WATER;
	mWorldVertexsVisiTest[2].z = mLb->mRect.mMinZ;

	mWorldVertexsVisiTest[3].x = mLb->mRect.mMaxX;
	mWorldVertexsVisiTest[3].y = ALTITUDE_WATER;
	mWorldVertexsVisiTest[3].z = mLb->mRect.mMaxZ;

	Object::CalcRadius( 4, mWorldVertexsVisiTest );
}

/*****************************************************************************
 * A lake is approximated as a grid of tiles (a tile is 2D square in world space).
 * Water is over any tile that is within distance of the points
 * (the set of points were randomly made by LakeBasis).
 *****************************************************************************/
void
Lake::MakeTiles( void )
{
	// From the lake basis struct, allocate an array of tiles.
	// Each element is a byte indicating whether water is over it or not.
	mTiles = new uint8[ mLb->mTileDimX * mLb->mTileDimZ ];
	WorldVertex v; v.y = 0.0;
	int i, x, z;
	for ( i = x = 0; x < mLb->mTileDimX; ++x )
	{
		v.x = mLb->mRect.mMinX + x*mLb->mTileWidth;
		for ( z = 0; z < mLb->mTileDimZ; ++z )
		{
			// Compute this tile's world vertex.
		 // v.x (outer loop)
			v.z = mLb->mRect.mMinZ + z*mLb->mTileWidth;

			// Is water over this tile?
			mTiles[i] = IsWaterOverTile( &v );

			++i;
		}
	}
	SmoothTiles();
}

/*****************************************************************************
 * This is a form of anti-aliasing.  If the tiles were drawn otherwise,
 * they would appear blockly.  Scan thru the tile array for rectangular
 * empty tiles situated near gaps.  Depending on the adjacent water tiles,
 * change the tile byte to be drawn as either a water-color triangle or square.
 *****************************************************************************/
void
Lake::SmoothTiles( void )
{
	int i, x, z;
	for ( i = x = 0; x < mLb->mTileDimX; ++x )
	{
		for ( z = 0; z < mLb->mTileDimZ; ++z )
		{
			if ( mTiles[i] == eLakeTile_DRY )
			{
				// Should this dry tile be converted to a water tile?
				// Answer depends on the tiles adjacent to it.
				uint bits; uint adjacentWater = ExamineAdjacentTiles( &bits, x, z );
				if ( adjacentWater == 2 )			// turn into a full water tile
					mTiles[i] = eLakeTile_TRIANGLE | bits;
				else if ( adjacentWater == 3 )		// turn into a triangular water tile
					mTiles[i] = eLakeTile_FULL_ANTIALIAS;
			}

			++i;
		}
	}
}

/*****************************************************************************
 * Return count/bits indicating adjacent tiles.
 * Adjacent in the 4 cardinal directions (not diagonal).
 *****************************************************************************/
uint
Lake::ExamineAdjacentTiles( uint* bits/*OUT*/, int x, int z  )
{
	*bits = 0;
	uint cnt = 0;
	uint b;
	b = GetTile( x-1, z   ); cnt += b; *bits |= b<<0;
	b = GetTile( x+1, z   ); cnt += b; *bits |= b<<1;
	b = GetTile( x  , z-1 ); cnt += b; *bits |= b<<2;
	b = GetTile( x  , z+1 ); cnt += b; *bits |= b<<3;
	return cnt;
}

/*****************************************************************************
 * This method is very specialized for ExamineAdjacentTiles().
 * Returns: 1 if tile is an original full water tile
 *          0 else
 *****************************************************************************/
uint
Lake::GetTile( int x, int z )
{
	if ( EX(    uint(x) < uint(mLb->mTileDimX)	// catches negative values
             && uint(z) < uint(mLb->mTileDimZ) ) )
	{
		int i = x*mLb->mTileDimZ + z;
		return mTiles[i] == eLakeTile_FULL; // true only if original full tile
	}
	else
		return 0;
}

/*****************************************************************************
 * Returns LAKE_TILE_FULL (1) if water is over any tile of this lake, else 0.
 *****************************************************************************/
int
Lake::IsWaterOverTile( const WorldVertex* v )
{
	fp radius2 = SQUARE(mLb->mPointsRadius);
	for ( int i = 0; i < mLb->mPointCnt; ++i )
	{
		fp dist2 = DistanceSquared( mLb->mPoints[i], *v );
		if ( dist2 < radius2 ) return eLakeTile_FULL; // 1
	}
	return eLakeTile_DRY; // 0
}

/*****************************************************************************
 * Return true if another object is over this one.
 *****************************************************************************/
bool
Lake::IfOver( const Posrad& posrad )
{
	RectXZ rect( posrad );
	return mLb->mRect.IfOverlaps( rect );
}

/*****************************************************************************
 * Draw a lake object.
 *****************************************************************************/
void
Lake::Draw( void )
{
	GAME_STATS_CODE( ++gGame.mStats.mLakesDrawn; )

	// Make tiles unless made.
	if ( mTiles == NULL ) MakeTiles();

	// This table is used to draw a triangle for a tile
	// that is adjacent (cardinal) to exactly 2 water tiles
	// as a form of anti-aliasing.
	static const int triAdj2[2*8][6] =
	{
		// Three pairs.
		//  #3:z+1  #2:z-1  #1:x+1  #0:x-1
		{ 0, 0, 0, 0, 0, 0 },	// 0000		0		N/A
		{ 0, 0, 0, 0, 0, 0 },	// 0001		1		N/A
		{ 0, 0, 0, 0, 0, 0 },	// 0010		2		N/A
		{ 0, 0, 0, 0, 0, 0 },	// 0011		3		(not really used)
		{ 0, 0, 0, 0, 0, 0 },	// 0100		4		N/A
		{ 0, 0, 1, 0, 0, 1 },	// 0101		5
		{ 1, 1, 0, 0, 1, 0 },	// 0110		6
		{ 0, 0, 0, 0, 0, 0 },	// 0111		7		N/A
		{ 0, 0, 0, 0, 0, 0 },	// 1000		8		N/A
		{ 0, 0, 1, 1, 0, 1 },	// 1001		9
		{ 0, 1, 1, 1, 1, 0 },	// 1010		10
		{ 0, 0, 0, 0, 0, 0 },	// 1011		11		N/A
		{ 0, 1, 1, 0, 1, 1 },	// 1100		12		(not really used)
		{ 0, 0, 0, 0, 0, 0 },	// 1101		13		N/A
		{ 0, 0, 0, 0, 0, 0 },	// 1110		14		N/A
		{ 0, 0, 0, 0, 0, 0 },	// 1111		15		N/A
	};

	// Draw every rectangular tile.
	// Vertexs are recalculated.  This may seem slower than
	// using a vertex array but that too would require complex
	// calculating of vertex indexes, checking them for out-of-bounds,
	// and with worse case of recalculation after evicted from cache.
	// This way saves memory and is actually less complicated.
	static TexturePtr texture = gEng.GetTexture( "grass1.tga" );
	RGBA rgba( 0.100, 0.100, 0.500, 1.0 );
	GFX_RGBA( rgba );
	int i, x, z;
	WorldVertex v;
	v.y = ALTITUDE_WATER;
	for ( x = i = 0; x < mLb->mTileDimX; ++x )
	{
		for ( z = 0; z < mLb->mTileDimZ; ++z )
		{
			if ( mTiles[i] == eLakeTile_FULL || mTiles[i] == eLakeTile_FULL_ANTIALIAS )
			{
				GFX_BEGIN( GP_POLYGON, texture );

				v.x = mLb->mRect.mMinX + x*mLb->mTileWidth;
				v.z = mLb->mRect.mMinZ + z*mLb->mTileWidth;
				texture->Map( 0, 0 ); GFX_TRANSFORM_VERTEX( v );

				v.x += mLb->mTileWidth;
				texture->Map( 1, 0 ); GFX_TRANSFORM_VERTEX( v );

				v.z += mLb->mTileWidth;
				texture->Map( 1, 1 ); GFX_TRANSFORM_VERTEX( v );

				v.x -= mLb->mTileWidth;
				texture->Map( 0, 1 ); GFX_TRANSFORM_VERTEX( v );

				GFX_END( texture );
			}
			else if ( mTiles[i] & eLakeTile_TRIANGLE )
			{
				// Draw a triangle for a tile that is adjacent to 2 water tiles
				// as a form of anti-aliasing.
				GFX_BEGIN( GP_TRIANGLES, texture );
				int ti = mTiles[i] & 0xf;
				static const float texX[4+1] = { 0, 0, 1, 0, 1 };
				static const float texY[4+1] = { 0, 0, 0, 0, 1 };
				for ( int j = 0; j < 6; j += 2 )
				{
					v.x = mLb->mRect.mMinX + (x + triAdj2[ti][j  ]) * mLb->mTileWidth;
					v.z = mLb->mRect.mMinZ + (z + triAdj2[ti][j+1]) * mLb->mTileWidth;
					texture->Map( texX[j], texY[j] ); GFX_TRANSFORM_VERTEX( v );
				}
				GFX_END( texture );
			}

			++i;
		}
	}
}
