/*****************************************************************************
 * $Id: mod_pony_terrain.cc,v 1.1 2006/11/24 21:56:58 devel Exp $
 * @file
 * @author	Jim E. Brooks  http://www.jimbrooks.org
 * @brief	Terrain renderer.
 *//*
 * LEGAL:	COPYRIGHT (C) 2004 JIM E. BROOKS
 *          THIS SOURCE CODE IS RELEASED UNDER THE TERMS
 *          OF THE GNU GENERAL PUBLIC LICENSE (GPL).
 *****************************************************************************/

#define MOD_PONY_TERRAIN_CC 1
#include "mod_pony_common.hh"
#include "mod_pony_terrain.hh"
#include "mod_pony_water.hh"
#include "mod_pony_world.hh"
#include "gfx_random.hh"

static int sFogQuality;
static const RGBA  sRgbaVerdantTerrain	( 0.100, 0.400, 0.100, 1.0 );
static const RGBA  sRgbaVerdantHill		( 0.100, 0.410, 0.100, 1.0 );
static const RGBA  sRgbaDesertTerrain	( 0.640, 0.560, 0.440, 1.0 );
static const RGBA  sRgbaDesertHill		( 0.560, 0.480, 0.360, 1.0 );
static const RGBA* pRgbaTerrain			= &sRgbaVerdantTerrain;
static const RGBA* pRgbaHill			= &sRgbaVerdantHill;

////////////////////////////////////////////////////////////////////////////////
////////////////////////////////  Terrain  /////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////

uint Terrain::msFrameDrawn = FRAME_CNT_INVALID;
bool Terrain::mInit;

/*****************************************************************************
 * Constructor.
 *****************************************************************************/
Terrain::Terrain( QuadrantPtrConst q, SafePtr<Water> water )
:	Omni(q)
{
    // Initialize static vars only once.
    if ( ! mInit++ ) InitStatics();

    // Skip quadrants in the sky.
    if ( (q->GetTuple())[YY] == 0 )
    {
    	// Make rolling hills (as independent objects)
    	// unless this is an edge quadrant (see comments in eng_world.cc).
    	if ( gWorldParm.mHill.mDensity > 0  && ! gWorld.IfEdgeQuadrant( q ) )
            MakeRollingHills( q, water );

    	// Make trees.
    	MakeTrees( q, water );
    }

	DEBUG_CODE( CheckObjectCtor(); )
}
Terrain::~Terrain()
{
	DEBUG_CODE( CheckObjectDtor(); )
}
void
Terrain::InitStatics( void )
{
	if ( ! sFogQuality ) sFogQuality = 2;

	// Color parameters.
	if ( gWorldParm.mTerrain.mDesert )
	{
		pRgbaTerrain = &sRgbaDesertTerrain;
		pRgbaHill    = &sRgbaDesertHill;
	}
	else
	{
		pRgbaTerrain = &sRgbaVerdantTerrain;
		pRgbaHill    = &sRgbaVerdantHill;
	}

	// Hills/mountain parameters.
	switch ( gWorldParm.mTerrain.mMountains )
	{
		case eTerrainParmMountains_ROLLING_HILLS:
		gWorldParm.mHill.mHeight     = WORLD(100);
		gWorldParm.mHill.mWidth1Rand = WORLD(1000);
		gWorldParm.mHill.mWidth1Base = WORLD(500);
		gWorldParm.mHill.mWidth2Rand = WORLD(1000);
		gWorldParm.mHill.mWidth2Base = WORLD(500);
		gWorldParm.mHill.mHillsQuadrantBase = MAX(40,gWorldParm.mHill.mHillsQuadrantBase);
		gWorldParm.mHill.mHillsQuadrantRand = MAX(40,gWorldParm.mHill.mHillsQuadrantRand);
		break;

		case eTerrainParmMountains_NORMAL: default:
		gWorldParm.mHill.mHeight     = WORLD(600);
		gWorldParm.mHill.mWidth1Rand = WORLD(3000);
		gWorldParm.mHill.mWidth1Base = WORLD(1700);
		gWorldParm.mHill.mWidth2Rand = WORLD(1500);
		gWorldParm.mHill.mWidth2Base = WORLD(1350);
		gWorldParm.mHill.mHillsQuadrantBase = MAX(30,gWorldParm.mHill.mHillsQuadrantBase);
		gWorldParm.mHill.mHillsQuadrantRand = MAX(30,gWorldParm.mHill.mHillsQuadrantRand);
		break;

		case eTerrainParmMountains_HUGE:
		gWorldParm.mHill.mHeight     = WORLD(8000);
		gWorldParm.mHill.mWidth1Rand = WORLD(4000);
		gWorldParm.mHill.mWidth1Base = WORLD(7000);
		gWorldParm.mHill.mWidth2Rand = WORLD(4000);
		gWorldParm.mHill.mWidth2Base = WORLD(7000);
		gWorldParm.mHill.mHillsQuadrantBase = MAX(20,gWorldParm.mHill.mHillsQuadrantBase);
		gWorldParm.mHill.mHillsQuadrantRand = MAX(20,gWorldParm.mHill.mHillsQuadrantRand);
		break;
	}
	if ( gEng.GetSpeed() == eSpeed_FASTEST )
	{
		gWorldParm.mHill.mHillsQuadrantBase /= 2;
		gWorldParm.mHill.mHillsQuadrantRand /= 2;
	}
	if ( gModule.mCmdarg.mHillDensity )
	{
		gWorldParm.mHill.mHillsQuadrantBase = int(float(gWorldParm.mHill.mHillsQuadrantBase) * gWorldParm.mHill.mDensity);
		gWorldParm.mHill.mHillsQuadrantRand = int(float(gWorldParm.mHill.mHillsQuadrantRand) * gWorldParm.mHill.mDensity);
	}
	gWorldParm.mHill.mHillsQuadrantBase = int(gWorldParm.mObjRatio * gWorldParm.mHill.mHillsQuadrantBase);
	gWorldParm.mHill.mHillsQuadrantRand = int(gWorldParm.mObjRatio * gWorldParm.mHill.mHillsQuadrantRand);

	// Tree parameters.
	// -tree-density 0.0 is equivalent to -no-trees.
	if ( gEng.IfAtLeastLodUser( eLodUser_HIGH ) )
		gWorldParm.mTree.mDensity = 3.0;
	if ( gEng.IfAtLeastLodUser( eLodUser_MAX ) )
		gWorldParm.mTree.mDensity = 5.0;
	if ( gWorldParm.mTree.mDensity < 0.01 && ! gModule.mCmdarg.mTreeDensity )
		gWorldParm.mTree.mDensity = 1.0; // default
}

/*****************************************************************************
 * Draw terrain object.
 * Other objects (such as rolling hills) constructed by the Terrain class
 * aren't drawn by this function, rather, their own Draw() methods will.
 *****************************************************************************/
void
Terrain::Draw( void )
{
	if ( ! IfOmniDrawnThisFrame() )
	{
		DrawFlatLand();
	}
}

/*****************************************************************************
 * Draw underlying flat land.
 * The vertexs of the grid are always computed relative to the viewpoint
 * (the grid continually surrounds the eye).
 *
 * @remarks Historical comment (applied to obsolete Voodoo 3 and Rage 128):
 * This innocuous function has a tremendous affect on OpenGL performance.
 * Drawing fine grids can drag fps down to near 10 but drawing huge grids
 * can reach up to 150 fps (fog quality will suffer however).
 *****************************************************************************/
void
Terrain::DrawFlatLand( void )
{
	// (This example diagram is of a 5x5 Locus.  Locus geometry varies.)
	//
	// Draw enough land to cover 5x5 quadrants.
	// The reason for 5x5 is that the sky cylinder overlaps 5x5 quadrants
	// in order to fully enclose the 3x3 locus.
	//
	// orig:*------+------+------+------+------+
	//		|     +|------|------|------|+     |
	//		|    / |      |      |      | \    |
	//		+------+======+======+======+------+
	//		|   |  ||     |      |     ||  |   |
	//		|   |  ||     |      |     ||  |   |
	//		+------+------+------+------+------+
	//		|   |  ||     |  .   |     ||  |   |
	//		|   |  ||     | eye  |     ||  |   |
	//		+------+------+------+------+------+
	//		|   |  ||     |      |     ||  |   |
	//		|   |  ||     |      |     ||  |   |
	//		+------+======+======+======+------+
	//		|    \ |      |      |      | /    |
	//		|     +|------|------|------|+     |
	//		+------+------+------+------+------+
	//

    const fp            quadrantEdge = gWorld.GetQuadrantEdge();
    const fp            locusEdge = gWorld.mLocus.GetEdge(XX) * 1.25;  // some overdraw so land/sky stays connected
    const fp            locusEdgeHalf = locusEdge / 2.0;

	fp					inc      = quadrantEdge;
	static Texture2Ptr	texture  = gEng.GetTexture( gWorldParm.mTerrain.mDesert ? "desert1.tga" : "grass1.tga" );
	const fp			ox       = Truncate(ABS(gEng.mEye.mCm[Ox]),quadrantEdge) - locusEdgeHalf + quadrantEdge;
	const fp			oz       = Truncate(ABS(gEng.mEye.mCm[Oz]),quadrantEdge) - locusEdgeHalf + quadrantEdge;
	const fp			toofar   = locusEdgeHalf;
	const fp			xzWidth  = locusEdge;
	int					xzCnt    = 0;
	WorldVertex			vw( 0.0, ALTITUDE_LAND, 0.0 );
	const WorldVertex	center( ABS(gEng.mEye.mCm[Ox]), ABS(gEng.mEye.mCm[Oy]), ABS(gEng.mEye.mCm[Oz]) );

	// Draw large untextured quads or draw small textures quads unless too high.
	MODULE_STATS_CODE( int statsTextureInc = 0; )
	if ( gEng.mEye.IfAboveAltitude( MAX_ALTITUDE_DETAIL ) || gEng.IfMinLodUser() )
	{
        // Lower LOD.
		texture->Disable();
		MODULE_STATS_CODE( statsTextureInc = 0; )
	}
	else
	{
        // Higher LOD.
		texture->Enable();
		MODULE_STATS_CODE( statsTextureInc = 1; )

		// Smaller tiles compensate for texture magnification filter losing detail of grass texture.
		if ( gEng.IfAtLeastLodUser( eLodUser_MAX ) )
			inc = Min( WORLD(2000.0), quadrantEdge / 16.0 );
		else if ( gEng.IfAtLeastLodUser( eLodUser_HIGH ) )
			inc = Min( WORLD(4000.0), quadrantEdge / 8.0 );
		else if ( gEng.IfAtLeastLodUser( eLodUser_MID ) )
			inc = Min( WORLD(8000.0), quadrantEdge / 4.0 );
	}

	// Calculate eye vertexs.
	int			elems = int(xzWidth/inc * xzWidth/inc) << 1;
	EyeVertex*	ev      = gEng.mTempArrayEyeVertex.Get( elems );
	int8*		evFlags = gEng.mTempArrayInt8.Get(      elems ); // non-zero if transformed
	int			vi = 0;
	fp			x, z;
	for ( x = 0.0; x < xzWidth+inc; x += inc )
	{
		xzCnt = 0;
		for ( z = 0.0; z < xzWidth+inc; z += inc )
		{
			vw.x = ox + x;
			vw.z = oz + z;
			if ( ABS(vw.x-center.x) < toofar
              && ABS(vw.z-center.z) < toofar )
			{
				TRANSFORM_VERTEX( ev[vi], vw );
				evFlags[vi] = IS_Z_FACING(ev[vi].z) ? 1 : -1;
			}
			else
			{
				evFlags[vi] = 0;
			}
			++vi;
			++xzCnt;
		}
	}

	// Draw land tiles.
	int	xi   = 0;
	int flip = 0;
	GFX_RGBA( *pRgbaTerrain );
	GFX_BEGIN( GP_QUADS, texture );
	for ( x = 0.0; x < xzWidth; x += inc ) // < not <=
	{
		int j  = xi * xzCnt;
		int j2 = j + xzCnt;
		for ( z = 0.0; z < xzWidth; z += inc )
		{
            // Draw tile if all of its 4 vertexs were transformed
            // unless all 4 are behind.
            if (    (evFlags[j] && evFlags[j+1] && evFlags[j2] && evFlags[j2+1])
                 && (evFlags[j] +  evFlags[j+1] +  evFlags[j2] +  evFlags[j2+1] != -4) )
			{
				EyeVertex ev2[4];
				ev2[0] = ev[j];
				ev2[1] = ev[j+1];
				ev2[2] = ev[j2+1];
				ev2[3] = ev[j2];
		        if ( gEng.TestViewport( ev2, 4, Engine::eTestFacing_DO ) )
				{                               
					const fp tn = 32;
					if ( flip++ & 1 )	// "flips" tries to avoid visual repeated patterns in textures
					{
						texture->Map(  0,  0 ); GFX_VERTEXV( &ev2[0] );
						texture->Map( tn,  0 ); GFX_VERTEXV( &ev2[1] );
						texture->Map( tn, tn ); GFX_VERTEXV( &ev2[2] );
						texture->Map(  0, tn ); GFX_VERTEXV( &ev2[3] );
					}
					else
					{
						texture->Map( tn,  0 ); GFX_VERTEXV( &ev2[0] );
						texture->Map( tn, tn ); GFX_VERTEXV( &ev2[1] );
						texture->Map(  0, tn ); GFX_VERTEXV( &ev2[2] );
						texture->Map(  0,  0 ); GFX_VERTEXV( &ev2[3] );
					}
					MODULE_STATS_CODE( ++gModule.mStats.mLandQuadsDrawn; )
					MODULE_STATS_CODE( gModule.mStats.mLandQuadsDrawnTextured += statsTextureInc; )
				}
			}
			++j; ++j2;
		}
		++xi;
	}
	GFX_END( texture );
}

/*****************************************************************************
 * Make rolling hills objects.
 * Basically, two sets of half-sine waves that intersect.
 * Rolling hills are randomly placed and constructed by two degrees that
 * increment from -90 to +90.  The degrees are passed to cos() and thereby one
 * degree controls the X slope and the other the Z slope to make a rolling hill.
 *****************************************************************************/
void
Terrain::MakeRollingHills( QuadrantPtrConst q, SafePtr<Water> water )
{
CHECK_TYPESIG( q, TYPESIG_QUADRANT );

    // Just exclude hills from center quadrant
    // which is a reliable way to avoid placing hills over runway.
    // TODO: Replace this by a generalized method to avoid overlapping objects.
    if ( q == gWorld.GetCenterQuadrant() )
        return;

	int objects = gWorldParm.mHill.mHillsQuadrantBase + random_ui(gWorldParm.mHill.mHillsQuadrantRand);
	for ( int i = 0; i < objects; ++i )
	{
		int width1 = random_ui(gWorldParm.mHill.mWidth1Rand) + gWorldParm.mHill.mWidth1Base;
		int width2 = random_ui(gWorldParm.mHill.mWidth2Rand) + gWorldParm.mHill.mWidth2Base;
		Position posRandom; q->RandomPosition( posRandom );
		const fp radius = MAX(width1,width2);
		Posrad posrad( posRandom, radius );
		posrad.y = GROUND_LEVEL;		// don't want trees floating in mid-air

		// Reject (most of the time) if over a body of water.
		// Conversely, some of the time, make an island.
		if (    water->IfOverWater( posrad )
             && random_f() > gWorldParm.mWater.mIslandDensity )
			continue;

		// Reject if object would overlap quadrants.
		if ( ! q->IfInsideXZ( posrad ) )
            continue;

		new RollingHill( q, posrad, width1, width2 );
	}
}

/*****************************************************************************
 * Make one tree.  Reject if it's too close to initial viewpoint.
 *****************************************************************************/
static Tree*
TerrainMakeTree( QuadrantPtrConst q, SafePtr<Water> water, fp x, fp z, const string& speciesName="" );
static Tree*
TerrainMakeTree( QuadrantPtrConst q, SafePtr<Water> water, fp x, fp z, const string& speciesName )
{
	Posrad posrad( x, GROUND_LEVEL, z, WORLD(100.0) );
	if (    ! gWorld.TooCloseToInitialViewpoint( posrad )
         && ! water->IfOverWater( posrad )
         && q->IfInsideXZ( posrad ) )
    {
        return new Tree( q, posrad, speciesName );
    }
	return NULL;
}

/*****************************************************************************
 * Make tree objects.
 * Trees are randomly placed.
 *****************************************************************************/
void
Terrain::MakeTrees( QuadrantPtrConst q, SafePtr<Water> water )
{
	if ( UX(gWorldParm.mTree.mDisable) )
		return;

	// Unlimited amount of trees could use 100s of MB.
	const int clusterCnt = int(gWorldParm.mObjRatio * 30 * gWorldParm.mTree.mDensity);
	const int treeLimit  = int(gWorldParm.mObjRatio * Min<fp>(5000 * gWorldParm.mTree.mDensity,20000.0) );
	int		  treesMade  = 0;

	// Make human-planted rectangular groves of trees.
	if ( EX( ! gWorldParm.mTerrain.mDesert ) )
	{
		int groveCnt = int(gWorldParm.mObjRatio * (25 + random_ui( 10 )));
		for ( int grove = 0; grove < groveCnt; ++grove )
		{
			Position posRandom; q->RandomPosition( posRandom );
			const int groveWidth = 10 + random_ui( 5 );
			const fp space = WORLD(85);
			for ( int x = 0; x < groveWidth; ++x )
			for ( int z = 0; z < groveWidth; ++z )
			{
				TerrainMakeTree( q, water,
	                             posRandom.x + x*space,
	                             posRandom.z + z*space,
	                             "treeOrange1" );
			}
		}
	}

	// Randomly distribute lone trees.
    const uint loneTreeCnt = int(gWorldParm.mObjRatio * 70 * gWorldParm.mTree.mDensity);
	for ( uint i = 0; i < loneTreeCnt; ++i )
	{
		Position posRandom; q->RandomPosition( posRandom );
		TerrainMakeTree( q, water, posRandom.x, posRandom.z );
	}

	// Make random clusters of trees.
	// Each cluster is a wide area sub-divided into ObjectGroups containing trees
	// to increase the opportunity of bypassing groups of trees that aren't visible.
	const int  groupSqrt		= 8;
	const fp   groupWidth		= WORLD(1200.0);
	const fp   groupDensity		= 1.5 * gWorldParm.mTree.mDensity;
	const fp   groupTreesMax	= int(gWorldParm.mObjRatio * 80 * gWorldParm.mTree.mDensity);
	for ( int cluster = 0; cluster < clusterCnt; ++cluster )
	{
		// Iterate thru a square, gradually increase tree density gradually near the center.
		for ( int groupX = 0; groupX < groupSqrt; ++groupX )
		for ( int groupZ = 0; groupZ < groupSqrt; ++groupZ )
		{
			ObjectGroup* group = new ObjectGroup( q, true );	// true=small
			Position posObjectGroup;
			q->RandomPosition( posObjectGroup ); // ObjectGroup::AddObject() will adjust position

			// Higher tree density for groups near the center.
			fp treeCnt = 0;
			treeCnt += groupDensity * ((groupSqrt>>1) - ABS(groupX - (groupSqrt>>1)));
			treeCnt += groupDensity * ((groupSqrt>>1) - ABS(groupZ - (groupSqrt>>1)));
			treeCnt = gWorldParm.mObjRatio * MIN(treeCnt,groupTreesMax);
			for ( int iTree = 0; iTree < treeCnt; ++iTree )
			{
				Position posTree;
				posTree.x = posObjectGroup.x + groupX * groupWidth + random_f(groupWidth);
				posTree.y = posObjectGroup.y;
				posTree.z = posObjectGroup.z + groupZ * groupWidth + random_f(groupWidth);
				if ( q->IfInsideXZ( posTree ) )
				{
					Tree* tree = TerrainMakeTree( q, water, posTree.x, posTree.z );
					if ( tree )
					{
						group->AddObject( tree );
						if ( treesMade++ > treeLimit ) return;
					}
				}
			}

			// Delete group if it has no objects.
			if ( group->IfEmpty() ) DELETE_NULL( group );
		}
	}
}

/*****************************************************************************
 * @return Distance between object and viewplane.
 *****************************************************************************/
fp
Terrain::GetDistance( void )
{
	// Draw Terrain before Sky.
	return Parent::GetDistance() - WORLD(5000.0);
}

////////////////////////////////////////////////////////////////////////////////
////////////////////////////    RollingHill     ////////////////////////////////
////////////////////////////////////////////////////////////////////////////////

RollingHill::RollingHillMesh	RollingHill::mMesh[eLodObj_LEVELS];
bool							RollingHill::mMadeMesh;

/*****************************************************************************
 * Construct/destruct a rolling hill object.
 *****************************************************************************/
RollingHill::RollingHill( QuadrantPtrConst q, const Position& pos, int width1, int width2 )
:   Parent(q,pos)
{
	SetLodObj( eLodObj_MIN );

	// Initialize statics once.
	if ( ! mMadeMesh )
	{
		MakeMesh();
		mMadeMesh = true;
    }

	// Need to make copies of polygon lists in ObjectPoly.
	for ( int lod = 0; lod < eLodObj_LEVELS; ++lod )
	{
		PolygonList& polygonList = GetPolygonList( (eLodObj)lod );
		polygonList = *mMesh[lod].mPolygonList;
	}

	// Lazy construction -- construction is deferred to Get*().
    SetPosition( pos );
	mWidth1  = width1;
	mWidth2  = width2;
	mJaggedPeak = random_ui(10) <= 3;

	// Estimate height of this hill and compare it to the tallest
	// which is used to place the craft over hills in demo mode.
	fp ratio = fp(width1) / fp(width2);
	fp height = gWorldParm.mHill.mHeight * ratio;
	gWorldParm.mHill.mTallest = MAX( gWorldParm.mHill.mTallest, height );

    // Randomly make trees on top of hills.
    MakeTrees();

	MODULE_STATS_CODE( ++gModule.mStats.mHills; )
	FinalConstruction();
	DEBUG_CODE( CheckObjectCtor(); )
}
void
RollingHill::FinalConstruction( void )
{
	// Make a Detector object as a Craft could collide into a hill.
	Cube<fp> cube;
	CalcRadiusAdjustPosition( GetVertexCnt(), GetWorldVertexs(), cube );
	new DetectorAll( *this, cube.y1, cube.y2 );  // indeed, pointer isn't stored
}
RollingHill::~RollingHill()
{
	// ~Object() deletes Detector.
	// ~ObjectPoly() deletes copies of polygon lists.
	MODULE_STATS_CODE( --gModule.mStats.mHills; )
	DEBUG_CODE( CheckObjectDtor(); )
}

/*****************************************************************************
 * Make meshes for each LOD.
 *****************************************************************************/
void
RollingHill::MakeMesh( void )
{
	for ( uint lod = 0; lod < eLodObj_LEVELS; ++lod )
	{
		// Finer degree increments as LOD increases.
		static const int degIncLod[eLodObj_LEVELS] = { 30, 15, 10 };
		const int degInc        = lod < ELEMS(degIncLod) ? degIncLod[lod] : degIncLod[eLodObj_MAX];
		const int vertexCntSqrt = 180/degInc + 1;
		const int vertexCnt     = SQUARE( vertexCntSqrt );
		ASSERT( lod < ELEMS(mMesh) );
		mMesh[lod].mDeg1inc = mMesh[lod].mDeg2inc = degInc;
		mMesh[lod].mVertexCntSqrt                 = vertexCntSqrt;
		mMesh[lod].mVertexCnt	                  = vertexCnt;
		mMesh[lod].mPolygonList                   = MakePolygonList( (eLodObj)lod, vertexCntSqrt, vertexCnt );
	}
}

/*****************************************************************************
 * Make a set of polygon lists for each LOD.
 *****************************************************************************/
PolygonList*
RollingHill::MakePolygonList( eLodObj lod, const int vertexCntSqrt, const int vertexCnt )
{
	// New PolygonList.
	PolygonList* polygonList = new PolygonList;

	// All polygons have the same attributes.
	static Texture2Ptr texture = gEng.GetTexture( "grass1.tga" );
	PolygonAttribs polygonAttribs( *pRgbaHill, texture, 3 );
	polygonAttribs.AddTexCoordsTriangle();

	//
	//	0____1    Two polygons (triangles) are constructed at a time.
	//  |\   |
	//	| \  |
	//	|  \ |          Z
	//	|   \|          |
	//	+----+          |
	//  2    3          +-- X
	//

	static Vix vix[4]; // static to shutup gcc 4
	for ( int x = 0; x < vertexCntSqrt-1; ++x )
	for ( int z = 0; z < vertexCntSqrt-1; ++z )
	{
		vix[0] = vertexCntSqrt * (x  ) + z;
		vix[1] = vertexCntSqrt * (x+1) + z;
		vix[2] = vertexCntSqrt * (x  ) + z+1;
		vix[3] = vertexCntSqrt * (x+1) + z+1;

		// triangle (0,2,3)
		Polygon* polygon = polygonList->AddPolygon( &polygonAttribs, 3 );
		polygon->AddVix( vix[0] );
		polygon->AddVix( vix[3] );
		polygon->AddVix( vix[2] );

		// triangle (0,3,1)
		polygon = polygonList->AddPolygon( &polygonAttribs, 3 );
		polygon->AddVix( vix[0] );
		polygon->AddVix( vix[1] );
		polygon->AddVix( vix[3] );
	}
	ASSERT( vix[3] < vertexCnt ); // vix[3] was the largest

	polygonList->Optimize( vertexCnt );

	return polygonList;
}

/*****************************************************************************
 * Make trees on hill.
 * Trees are placed on the hill's geometery at its max LOD which is why
 * trees aren't drawn when the hill is at a lower LOD.
 * A hill's trees are drawn if the hill is drawn, and after the hill is drawn.
 * A RollingHill has a list of Trees which are placed into shadow quadrants.
 *****************************************************************************/
void
RollingHill::MakeTrees( void )
{
	if ( gWorldParm.mTree.mDisable ) return;

   	// Place trees using the hill's max LOD geometry.
    const eLodObj lod = eLodObj_MAX;
    SetLodObj( lod );  // subtle for GetWorldVertexs()
    const int vertexCntSqrt         = mMesh[lod].mVertexCntSqrt;
    const int vertexCnt             = GetVertexCnt();
    const WorldVertex* worldVertexs = GetWorldVertexs();

	for ( int i = 0; i < int(40*gWorldParm.mTree.mDensity); ++i )
	{
		const int n = 6;
		int vi;
		if ( random_ui(10) > 6 )
        {
			// Place near top of hill.
			vi = vertexCnt/2 + (random_ui(n)-n/2) + ((random_ui(n)-n/2)*vertexCntSqrt);
        }
		else
        {
			// Place anywhere on hill.
			vi = random_ui( vertexCnt-1 );
        }
		vi = Min(vertexCnt-1,vi); // keep random vertex index within range
ASSERT( vi >= 0 && vi < vertexCnt );

		// Don't place trees on huge mountains as doing so in unrealistic
		// but another reason is that some trees appear to float in midair.
		// The interpolation code below doesn't fully solve the problem.
        if ( IfHugeMountain( worldVertexs ) && IfHillTop( vi ) ) continue;

		// Place the tree at a random point between two vertexes
		// If a tree were placed directly on a vertex it would be aligned
		// with other trees resulting in a synthetic appearance.
        const int vi2 = vi + vertexCntSqrt;
        if ( vi2 >= vertexCnt ) continue;
        fp  r  = random_f( 1.0 );
        fp  xo = r * (worldVertexs[vi2].x - worldVertexs[vi].x);
        fp  yo = r * (worldVertexs[vi2].y - worldVertexs[vi].y);
        fp  zo = r * (worldVertexs[vi2].z - worldVertexs[vi].z);
        Position pos2( worldVertexs[vi].x + xo,
                       worldVertexs[vi].y + yo - WORLD(5.0), // lower so trunk touches ground
                       worldVertexs[vi].z + zo);

        // Append Tree to this hill's list of Trees.
   		Tree* tree = new Tree( GetQuadrant()->GetShadow(), pos2 );
        mTreeDlist.Append( tree );
	}
}

/*****************************************************************************
 * Get a cached object or reconstruct it.
 *****************************************************************************/
const WorldVertex*
RollingHill::GetWorldVertexs( void )
{
	// In the cache?
	WorldVertex* worldVertexs = GetCacheWorldVertex();	// per LOD
	if ( worldVertexs != NULL ) return worldVertexs;

	// Per LOD.
	const int vertexCnt = GetVertexCnt();
	const int deg1inc   = mMesh[GetLodObj()].mDeg1inc;
	const int deg2inc   = mMesh[GetLodObj()].mDeg2inc;
 
	// No, make and cache them.
	worldVertexs = new WorldVertex[vertexCnt+1];
	PutCacheWorldVertex( worldVertexs );
	int			i;
	int			deg1, deg2;
	const fp	ratio = fp(mWidth1) / fp(mWidth2);
    const Position pos = GetPosition();

	// Construct world vertexs.
	for ( deg1 = -90, i=0; deg1 <= 90; deg1 += deg1inc )
	{
		fp sin1 = sin_deg(deg1);
		fp cos1 = cos_deg(deg1);
		fp cos1abs_x_ratio_height = ABS(cos1) * ratio * gWorldParm.mHill.mHeight;
		fp sin1_x_width1		  = sin1 * mWidth1;
        fp round2 = (1.0 + cos_deg(ABS(deg1))*0.8); // factor to round the base of hill
        round2 *= 0.75; // oval shape rather than round
		for ( deg2 = -90; deg2 <= 90; deg2 += deg2inc )
		{
			// Calc a vertex of the hill in world coords.
			fp sin2 = sin_deg(deg2);
			fp cos2 = cos_deg(deg2);
            fp round1 = (1.0 + cos_deg(ABS(deg2))*0.8);
			WorldVertex& v = worldVertexs[i];
CHECK_TYPESIG( &v, TYPESIG_LIB_VERTEX_WORLD );

			// Make hill slope angular (otherwise too round).
            fp angularSlope1, angularSlope2;
			if ( gWorldParm.mTerrain.mMountains != eTerrainParmMountains_HUGE )
			{
				const fp factor = 1.0 / 60.0 * 0.8;
	            angularSlope1 = Max<fp>(1.0,ABS(fp(deg1)*factor));
				angularSlope2 = Max<fp>(1.0,ABS(fp(deg2)*factor));
			}
			else
			{
				const fp factor = 1.0 / 60.0 * 0.6;
	            angularSlope1 = Max<fp>(0.6,ABS(fp(deg1)*factor));
				angularSlope2 = Max<fp>(0.6,ABS(fp(deg2)*factor));
			}

			v.x = pos.x + sin1_x_width1  * round1 * angularSlope1;
			v.z = pos.z + sin2 * mWidth2 * round2 * angularSlope2;
			v.y = cos2 * cos1abs_x_ratio_height;
			if ( UX(mJaggedPeak  &&  ABS(deg2) < 20  &&  ABS(deg1) < 20 ) )
			{
               v.y += sin_deg( ABS(deg2) * (90.0/10.0) ) * gWorldParm.mHill.mHeight * 0.12;
			}
			v.y = MAX(v.y, GROUND_LEVEL);
			gWorldParm.mHill.mTallest = MAX( gWorldParm.mHill.mTallest, v.y );
ASSERT( i < vertexCnt );
			++i;
		}
	}

	return worldVertexs;
}

/*****************************************************************************
 * Draw a rolling hill object.
 *****************************************************************************/
void
RollingHill::Draw( void )
{
	// Return if not visible.
	int width = VisibleStored();  // holds result of render loop calling RollingHill::Visible()
	if ( width < 30 ) return;

	// Set LOD for this object according to its distance.
	fp distVisible = VisibleDistanceStored();
	eLodObj lod = eLodObj_MAX;
	if ( distVisible > WORLD(50000.0) )
		lod = eLodObj_MIN;
	else if ( distVisible > WORLD(30000.0) )
		lod = eLodObj_MID;
	SetLodObj( lod );

	// Draw.  Texture polygons unless too high/far.
	if (    gEng.mEye.IfAboveAltitude(gWorldParm.mHill.mTallest)
         || distVisible > WORLD(30000.0 ) )
	{
		static DrawParm drawParm( eDraw_NO_TEXTURE );
		GetPolygonList().Draw( this, drawParm );
	}
	else
	{
		GetPolygonList().Draw( this );
	}

    // Draw trees on hill.
    DrawTrees();

	MODULE_STATS_CODE( ++gModule.mStats.mHillsDrawn; )
}

/*****************************************************************************
 * Draw trees on hill.
 *****************************************************************************/
void
RollingHill::DrawTrees( void )
{
    // Tree were placed on the geometry of the hill at its max LOD.
    // Therefore, don't draw trees at other LODs.
    if ( GetLodObj() == eLodObj_MAX )
    {
        // Draw trees on hill.
        for ( const Dlink<Object>* dlink = mTreeDlist.ForStart();
              mTreeDlist.ForTest(dlink);
              mTreeDlist.ForNext(dlink) )
        {
            Object* tree = dlink->mObj;
            tree->Draw();
        }
    }
}

/*****************************************************************************
 * Return true if a vertex is approximately on the hilltop.
 *****************************************************************************/
bool
RollingHill::IfHillTop( int vi )
{
	// Let middle 20% (in either X or Z) be considered the hilltop.
	int vertexCntSqrt = mMesh[GetLodObj()].mVertexCntSqrt;
	int x;
	int lo = int(vertexCntSqrt * 0.40);
    int hi = int(vertexCntSqrt * 0.60);
    x = vi / vertexCntSqrt;
    if ( EX(x < lo || x > hi) ) return false;
	x = vi % vertexCntSqrt;
    if ( EX(x < lo || x > hi) ) return false;
	return true;
}

/*****************************************************************************
 * Return true if mountain is huge.
 *****************************************************************************/
bool
RollingHill::IfHugeMountain( const WorldVertex* v )
{
	return   gWorldParm.mTerrain.mMountains == eTerrainParmMountains_HUGE
          && GetHilltopVertex(v)->y > WORLD(1000);
}

////////////////////////////////////////////////////////////////////////////////
///////////////////////////////    Tree     ////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////

Tree::TreeSpecies		Tree::mSpecies[TREE_SPECIES_MAX];
uint					Tree::mSpeciesCnt;
std::map<string,uint>	Tree::mSpeciesName;
WorldVertex				Tree::mWorldVertexs[TREE_VERTEX_CNT];

/*****************************************************************************
 * Tree constructor.
 * @param	q
 * @param	pos
 *			pos.y should be the bottom/base of the Tree.
 *          The Tree class will internally adjust the position to its center
 *          as required by Object::Visible().
 * @param	speciesName
 *			Tree species can be specified (default is to randomly select a species).
 *****************************************************************************/
Tree::Tree( QuadrantPtrConst q, const Position& pos, const string& speciesName )
:   Parent(q,pos)
{
	// Fill Tree::mSpecies[] once.
	if ( UX(mSpeciesCnt == 0) )
	{
//		static const RGBA rgba( 0.9, 0.9, 0.9, 0.4 );  // non-mipmap
		static const RGBA rgba( 0.4, 0.6, 0.4, 0.7 );  // mipmap
		static fp texcoords_[] = { 1, 1,
                                   1, 0,
                                   0, 0,
                                   0, 1 };
		Texcoord8 texcoords = texcoords_;
#define FILL_SPECIES( WIDTH, HEIGHT, FLIPY, SPECIES_NAME, TEXTURE_NAME )		\
{																				\
		ASSERT( mSpeciesCnt < TREE_SPECIES_MAX );								\
		mSpecies[mSpeciesCnt].mWidth      = LOCAL(WIDTH);						\
		mSpecies[mSpeciesCnt].mWidthHalf  = LOCAL(WIDTH/2);						\
		mSpecies[mSpeciesCnt].mHeight     = LOCAL(HEIGHT);						\
		mSpecies[mSpeciesCnt].mHeightHalf = LOCAL(HEIGHT/2);					\
		texcoords[1] = 1 * FLIPY;												\
		texcoords[7] = 1 * FLIPY;												\
		mSpecies[mSpeciesCnt].mTexBiquad.Set( gEng.GetTexture( TEXTURE_NAME ),	\
                                              texcoords,						\
							                  rgba );							\
		mSpeciesName[SPECIES_NAME] = mSpeciesCnt;								\
		++mSpeciesCnt;															\
}
		if ( UX(gWorldParm.mTerrain.mDesert) )
		{
			// Desert trees.
            mSpeciesName["runway"] = 0; // alias for tree planted by runway
            FILL_SPECIES( 30,  85, -1, "treePalmSabal1", "treePalmSabal1.tga" )
            FILL_SPECIES( 30,  55, -1, "treeCactus1",    "treeCactus1.tga" )
            FILL_SPECIES( 25,  35, -1, "treeDead",       "treeDead1.tga" )
            FILL_SPECIES( 35, 100, -1, "treePine1",      "treePine1.tga" )
            FILL_SPECIES( 35, 100, -1, "treePine2",      "treePine2.tga" )
		}
		else
		{
			// Verdant trees.
			mSpeciesName["runway"] = 0;	// alias for tree planted by runway
            FILL_SPECIES( 64, 64, -1, "tree1",         "tree1.tga" )
            FILL_SPECIES( 64, 64, -1, "tree1",         "tree1.tga" ) // dup
            FILL_SPECIES( 64, 64, -1, "tree2",         "tree2.tga" )
            FILL_SPECIES( 64, 64, -1, "tree3",         "tree3.tga" )
            FILL_SPECIES( 32, 32, -1, "tree4",         "tree4.tga" )
            FILL_SPECIES( 64, 64, -1, "treePine1",     "treePine1.tga" )
            FILL_SPECIES( 64, 64, -1, "treePine2",     "treePine2.tga" )
            FILL_SPECIES( 32, 32, -1, "treeShrub1",    "treeShrub1.tga" )
            FILL_SPECIES( 32, 32, -1, "treeOrange1",   "treeOrange1.tga" )
		}
	}

	// Some species of trees are more common.
	if ( UX(gWorldParm.mTerrain.mDesert) )
	{
		// Desert trees.
		uint n = random_ui(10);
		if ( n <= 5 )
			mWhich = 1;			// cactus most common
		else if ( n <= 8 )
			mWhich = n & 2;		// palm sabal or tree4 next-most-common
		else
			mWhich = n % mSpeciesCnt;
	}
	else
	{
		// Verdant trees.
		if ( random_ui(10) <= 3 )
			mWhich = 0;
		else
			mWhich = random_ui( mSpeciesCnt-1 );
	}

	// If a tree species was specified (and ensure mWhich in bounds).
	if ( UX( ! speciesName.empty() ) )
		mWhich = mSpeciesName[speciesName]; // name-to-index
	mWhich %= mSpeciesCnt;

	// Adjust position.  The position used by the Tree class is at its center
	// but the position the caller wants is at the base (bottom) of the Tree.
	Position pos2 = pos;
	pos2.y += mSpecies[mWhich].mHeightHalf + WORLD(10);  // KLUDGE WORLD(10) to place tree at right altitude
	SetPosition( pos2 );

	MODULE_STATS_CODE( ++gModule.mStats.mTrees; )
	FinalConstruction();
	DEBUG_CODE( CheckObjectCtor(); )
}
void
Tree::FinalConstruction( void )
{
	//CalcRadiusAdjustPosition();		// skip to speed program startup
	fp radius = Max<fp>( mSpecies[mWhich].mHeightHalf, mSpecies[mWhich].mWidth * 0.5 );
	SetRadius( radius );
}
Tree::~Tree()
{
	MODULE_STATS_CODE( --gModule.mStats.mTrees; )
	DEBUG_CODE( CheckObjectDtor(); )
}

/*****************************************************************************
 * Get world vertexs.
 *****************************************************************************/
const WorldVertex*
Tree::GetWorldVertexs( void )
{
	// There are far too many trees to use a cache (evictions would cause slowdown)
	// as ordinarily would be used in a GetWorldVertexs() method.

	const Position pos = GetPosition();
	const fp& wh = mSpecies[mWhich].mWidthHalf;
	const fp& hh = mSpecies[mWhich].mHeightHalf;

	#define SET_TREE_VW( I, X, Y, Z )		\
	mWorldVertexs[I].x = pos.x + (X);		\
	mWorldVertexs[I].y = pos.y + (Y);		\
	mWorldVertexs[I].z = pos.z + (Z);

	SET_TREE_VW( 0,   0,  hh,  wh );
	SET_TREE_VW( 1, -wh,  hh,   0 );
	SET_TREE_VW( 2,   0,  hh, -wh );
	SET_TREE_VW( 3,  wh,  hh,   0 );
	SET_TREE_VW( 4,   0, -hh,  wh );
	SET_TREE_VW( 5, -wh, -hh,   0 );
	SET_TREE_VW( 6,   0, -hh, -wh );
	SET_TREE_VW( 7,  wh, -hh,   0 );

	return mWorldVertexs;
}

/*****************************************************************************
 * Draw tree.
 *****************************************************************************/
void
Tree::Draw( void )
{
	// Trees are only drawn at low-altitudes as a visual clue,
	// except trees on mountain tops.
	if (    (gEng.mEye.IfAboveAltitude( MAX_ALTITUDE_DETAIL ) && (GetPosition()).y < WORLD(100.0) )
         || ! Visible() ) // Visible() called as render loop tested visibility of tree's ObjectGroup
		return;

	// Draw both intersecting quads using the same texture.
	mSpecies[mWhich].mTexBiquad.Draw( GetWorldVertexs() );

	MODULE_STATS_CODE( ++gModule.mStats.mTreesDrawn; )
}
