/*****************************************************************************
 * $Id: eng_world.cc,v 1.167 2006/11/17 06:31:48 devel Exp $
 * @file
 * @author	Jim E. Brooks  http://www.jimbrooks.org
 * @brief	World, Quadrant, Locus classes.
 * @verbatim
 * ---------------------------------------------------------------------------
 * If a newly-written Object doesn't appear, perhaps you should override
 * Object::Reproducible() to return false.
 * ---------------------------------------------------------------------------
 * The World class, to a large degree, is written as if the World is simply
 * a 3D cube without notions of altitude or ground (appropriate for a space sim).
 * World::mFlightSim imposes restrictions and affects interpretation of
 * altitude and edge/center quadrants.
 * - Quadrants are considered edge quadrants according to (X,Z) (ignoring Y).
 * - Center quadrant is at ground-level (y=0).
 * - Fence() imposes an altitude restriction
 *   Wrapping at X,Z is allowed but not at Y.
 * ---------------------------------------------------------------------------
 *//*
 * LEGAL:	COPYRIGHT (C) 2004 JIM E. BROOKS
 *          THIS SOURCE CODE IS RELEASED UNDER THE TERMS
 *          OF THE GNU GENERAL PUBLIC LICENSE (GPL).
 *****************************************************************************/

#define ENG_WORLD_CC 1
#include "eng.hh"
#include "eng_world.hh"
#include "gfx_random.hh"

////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////  World  /////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////

/*****************************************************************************
 * World::Make() does the actual construction.
 *****************************************************************************/
World::World( void )
{
	// Just clear flags.
    mFlightSim = true;
	mMade = mDimValid = false;
	mObjectCnt = mObjectCntMade = 0;
}

/*****************************************************************************
 * Make the world as a set of quadrants.
 * Quadrants are divisions of the simulated world ("space partitioning").
 *
 * The world is made in phases:
 * - Derived class must define Make() then should call Make1()/Make2().
 * - World::Make1() sets the dimensions of the World.
 * - Derived class can do intermediate steps.
 * - World::Make2() builds the Quadrants and the Locus.
 *
 * @param   flightSim
 *          Affects interpretation of altitude, edge/center quadrants.
 *          False would be for a hypothetical space sim.
 * @param	dimQuadrant
 *			Dimensions of the world (in quadrants).
 * @param	quadrantEdge
 *			Width of any edge of a quadrant (each edge is the same width).
 * @param	margin
 *			For when Fence() wraps a Dyna.
 * @param	dimLocus
 *			Dimensions of the Locus.  Should be smaller than dimQuadrant and
 *          each dimension should have an odd value (see Locus)
 *****************************************************************************/
void
World::Make1( bool flightSim, const Array<3>& dimQuadrant, const fp quadrantEdge, const fp margin, const Array<3>& dimLocus )
{
ASSERT( dimLocus[XX] <= dimQuadrant[XX] );  // Locus shouldn't be greater than World
ASSERT( dimLocus[YY] <= dimQuadrant[YY] );
ASSERT( dimLocus[ZZ] <= dimQuadrant[ZZ] );

	// First phase: set the world dimensions.

	mMade			= false;  // to be set by World::Make()
    mFlightSim      = flightSim;
	mObjectCnt		= 0;
	mObjectCntMade	= 0;
	SetObjectSmallDist( WORLD(15000.0) );				// default
	SetObjectLargeDist( WORLD(quadrantEdge*0.90) );		// default
    mQuadrantEdge	= quadrantEdge;
	mMargin			= margin;
	mDimQuadrant	= dimQuadrant;
	mDimWorld[XX]	= dimQuadrant[XX] * quadrantEdge;
	mDimWorld[YY]	= dimQuadrant[YY] * quadrantEdge;
	mDimWorld[ZZ]	= dimQuadrant[ZZ] * quadrantEdge;
	mDimLocus		= dimLocus;
	mCenter.x		= mDimWorld[XX] * 0.5 + quadrantEdge * 0.5;  // center of the center quadrant, order-dependent!
	mCenter.y		= mFlightSim ? GroundLevel() \
                    : mDimWorld[YY] * 0.5 + quadrantEdge * 0.5;
	mCenter.z		= mDimWorld[ZZ] * 0.5 + quadrantEdge * 0.5;
	mDimValid		= true;
}
void
World::Make2( void )
{
ASSERT( mDimValid );

	// Second phase: make the Quadrants and the locus.

	// Make mQuadrants[].
	const uint quadrantCnt = mDimQuadrant[0] * mDimQuadrant[1] * mDimQuadrant[2];
	mQuadrants.reserve( quadrantCnt );
	Array<3> t;
	for ( t[XX] = 0; t[XX] < mDimQuadrant[XX]; ++t[XX] )
	for ( t[YY] = 0; t[YY] < mDimQuadrant[YY]; ++t[YY] )
	for ( t[ZZ] = 0; t[ZZ] < mDimQuadrant[ZZ]; ++t[ZZ] )
	{
		// Quadrants are initially empty (eQuadrantState_EMPTY).
		Quadrant* q = new Quadrant( t, mQuadrantEdge, random_ui() );
		mQuadrants.push_back( q );
	}

	// Make the Locus.
	mLocus.Init( mDimLocus );
}

/*****************************************************************************
 * Destroy the world.  Code smuggled out of the Death Star's central computer.
 *****************************************************************************/
void
World::Destroy( void )
{
#if DEBUG
	// Explicitly deleting these isn't strictly necessary but doing so tests
	// the destructors and helps to suppress false Valgrind warnings.
	for ( QuadrantItr itr = mQuadrants.begin(); itr != mQuadrants.end(); ++itr )
		delete *itr;
#endif
}

/*****************************************************************************
 * Helper to invoke a callback for every object.
 *****************************************************************************/
void
World::ForEachObject( ForEachObjectCallback callback ) const
{
ASSERT( mMade );
	// For each quadrant.
	for ( ConstQuadrantItr itr = mQuadrants.begin(); itr != mQuadrants.end(); ++itr )
	{
		Quadrant* q = *itr;
CHECK_TYPESIG( q, TYPESIG_QUADRANT );
		// For each object in the quadrant's object list.
		Dlist<Object>& dlist = q->GetObjectDlist();
CHECK_TYPESIG( &dlist, TYPESIG_LIB_DLIST );
		for ( const Dlink<Object>* dlink = dlist.ForStart(); dlist.ForTest(dlink); dlist.ForNext(dlink) )
		{
CHECK_TYPESIG( dlink, TYPESIG_LIB_DLINK ); CHECK_TYPESIG( dlink->mObj, TYPESIG_OBJECT );
			Object* object = dlink->mObj;
			callback( object );
		}
	}
}

/*****************************************************************************
 * Compute a cache size based on the amount of objects created.
 *****************************************************************************/
uint
World::CacheSize( void )
{
ASSERT( mMade );
	// Find the quadrant with the greatest amount of objects,
	// multiply it by the amount of quadrants in the locus,
	// and scale it up to avoid delays caused by cache evictions.
	uint size = 0;
	for ( QuadrantItr itr = mQuadrants.begin(); itr != mQuadrants.end(); ++itr )
	{
		Quadrant* q = *itr;
CHECK_TYPESIG( q, TYPESIG_QUADRANT );
		size = Max( size, q->GetObjectCnt() );
	}
	size = size * mLocus.mQuadrants.size();
	size = uint( size * 1.25 );
#if DEBUG == 2
	size = 50;
#endif
	if ( gEng.GetSpeed() > eSpeed_NORMAL ) size <<= 1;
	// Cache sizes that are way too big will cause problems.
	return Min(10u*1000u,size);
}

/*****************************************************************************
 * Preload caches to avoid pauses in rendering.
 * This called for fast-mode (-fast).
 *****************************************************************************/
static void
PreloadCachesForEachObject( Object* obj )
{
//	obj->GetWorldVertexs();  // ObjectMesh now has this method, no longer Object
}
void
World::PreloadCaches( void )
{
ASSERT( mMade );
	*gEng.mStreamStatus << "preloading caches... \n";
	ForEachObject( PreloadCachesForEachObject );
}

/*****************************************************************************
 * Keep a Dyna within the world.
 * If it has gone past an edge, it is wrapped back to the opposite edge
 * (similar to Asteroids but in 3D).  A derived World class can override this behavior.
 * If mFlightSim, enforces an altitude ceiling instead of altitude wrapping.
 * @return True if the Dyna's Position was corrected.
 * @param	dyna
 * @param	pos (IN/OUT)
 *			Position object which might be corrected.
 *          The Dyna class calls World::Fence().
 *          World::Fence() defers to the Dyna class its position.
 *****************************************************************************/
bool
World::Fence( Dyna& dyna, Position& pos /*IN/OUT*/ )
{
    if ( mFlightSim )
    {
    	// Fence() subroutines wraps at the edges of the world.
    	// But for a flight sim, altitude (Y) should be clamped, not wrapped.
    	if ( pos.y > mDimWorld[YY] )
    	{
    		// Dyna flew too high in the (n,1,n) world.
    		// Still call base Fence() to check X,Z dimensions.
    		pos.y = mDimWorld[YY];
    		FenceSub( dyna, pos );
    		return true;
    	}
    	else if ( pos.y < 0.0 )
    	{
    		// Likewise for low altitude.
    		pos.y = 0.0;
    		FenceSub( dyna, pos );
    		return true;
    	}
    }

    // Not a flight sim or Y was inside.
    return FenceSub( dyna, pos );
}
// private subroutine
bool
World::FenceSub( Dyna& dyna/*unused*/, Position& pos /*IN/OUT*/ )
{
    // dyna arg is currently unused but may be used in future.

ASSERT( mDimValid );
ASSERT( mMade );

#define CODE_WORLD_FENCE_DIM( XYZ, XXYYZZ )				\
	if ( pos.XYZ < 0 )									\
	{													\
		pos.XYZ = mDimWorld[XXYYZZ] - mMargin;			\
		corrected = true;								\
	}													\
	else if ( pos.XYZ > mDimWorld[XXYYZZ] )				\
	{													\
		pos.XYZ = mMargin;								\
		corrected = true;								\
	}

	// Dyna::SetPosition() shouldn't be called, let Dyna class change its position.
	bool corrected = false;
	CODE_WORLD_FENCE_DIM( x, XX )
	CODE_WORLD_FENCE_DIM( y, YY )
	CODE_WORLD_FENCE_DIM( z, ZZ )
	return corrected;

#undef CODE_WORLD_FENCE_DIM
}

/*****************************************************************************
 * Truncate/wrap quadrant[x][y][z] to stay inside the world.
 *****************************************************************************/
Array<3>
World::WrapQuadrant( const Array<3>& tuple ) const
{
ASSERT( mDimValid );

	Array<3> t = tuple;

	// Truncate.
	t[XX] %= mDimQuadrant[XX];
	t[YY] %= mDimQuadrant[YY];
	t[ZZ] %= mDimQuadrant[ZZ];

	// Wrap backwards if negative.
	if ( t[XX] < 0 ) t[XX] += mDimQuadrant[XX];
	if ( t[YY] < 0 ) t[YY] += mDimQuadrant[YY];
	if ( t[ZZ] < 0 ) t[ZZ] += mDimQuadrant[ZZ];

	ASSERT( t[XX] >= 0 && t[XX] < mDimQuadrant[XX] );
	ASSERT( t[YY] >= 0 && t[YY] < mDimQuadrant[YY] );
	ASSERT( t[ZZ] >= 0 && t[ZZ] < mDimQuadrant[ZZ] );

	return t;
}

/*****************************************************************************
 * @return Flat index for mQuadrants[] equivalent to mQuadrants[x][y][z].
 * Can accept negative/invalid coords.
 *****************************************************************************/
uint
World::GetQuadrantIdx( const Array<3>& tuple ) const
{
ASSERT( mDimValid );
ASSERT( mQuadrants.size() );

	// From the tuple [x][y][z], compute a flat index to the Quadrant vector.
	Array<3> t = WrapQuadrant( tuple );
	uint idx =   t[XX] * mDimQuadrant[YY] * mDimQuadrant[ZZ]	 // think per square of a cube
               + t[YY] * mDimQuadrant[ZZ]						 // think per row of a cube
               + t[ZZ];
	ASSERT( idx < mQuadrants.size() );
	return idx;
}

/*****************************************************************************
 * @return Return flat index for mQuadrant[] that correlates to a position
 * in world space.
 * Can handle invalid coords in vertex.
 *****************************************************************************/
uint
World::GetQuadrantIdx( const Position& pos ) const
{
ASSERT( mDimValid );
ASSERT( mQuadrants.size() );

	Array<3> t;
	t[XX] = int(pos.x / mQuadrantEdge);		// all quadrant edges are equal
	t[YY] = int(pos.y / mQuadrantEdge);
	t[ZZ] = int(pos.z / mQuadrantEdge);
	uint idx = GetQuadrantIdx( t );
	ASSERT( idx < mQuadrants.size() );
	return idx;
}

/*****************************************************************************
 * @return Return tuple of quadrant (mQuadrant[x][y][z]) that correlates
 * to a position in world space.
 * Can handle invalid coords in vertex.
 *****************************************************************************/
const Array<3>&
World::GetQuadrantTuple( const Position& pos ) const
{
	QuadrantPtrConst q = GetQuadrant( pos );
	ASSERT_WORLD_QUADRANT( q );
	return q->GetTuple();
}

/*****************************************************************************
 * @return True if this is the center quadrant.
 *****************************************************************************/
bool
World::IfCenterQuadrant( QuadrantPtrConst q ) const
{
ASSERT_WORLD_QUADRANT( q );
	return q == GetCenterQuadrant();
}

/*****************************************************************************
 * @return Center quadrant.
 * For a flight sim, always return the center Quadrant at ground-level.
 *****************************************************************************/
QuadrantPtrConst
World::GetCenterQuadrant( void ) const
{
ASSERT( mDimValid );
ASSERT( mQuadrants.size() );
	Array<3> t;
	t[XX] =                  mDimQuadrant[XX] >> 1;
	t[YY] = mFlightSim ? 0 : mDimQuadrant[YY] >> 1;
	t[ZZ] =                  mDimQuadrant[ZZ] >> 1;
	QuadrantPtr q = mQuadrants[ GetQuadrantIdx(t) ];
ASSERT_WORLD_QUADRANT( q );
	return q;
}

/*****************************************************************************
 * @return True if this an edge quadrant.
 * Edge quadrants should be (mostly) empty to avoid objects magically
 * and annoyingly appearing when the viewpoint wraps around the world.
 *****************************************************************************/
bool
World::IfEdgeQuadrant( QuadrantPtrConst q ) const
{
ASSERT( mDimValid );
ASSERT_WORLD_QUADRANT( q );

	// Ignore one-quadrant-wide dimensions.
	// Otherwise, in a (n,1,n) world, every quadrant is an edge.
	#define RETURN_TRUE_IF_EDGE_QUADRANT( DIM )							\
		if (    (mDimQuadrant[DIM] > 1)									\
			 && (  (q->GetTuple()[DIM] == 0)							\
	            || (q->GetTuple()[DIM] == mDimQuadrant[DIM] - 1) ) )	\
			return true;
	RETURN_TRUE_IF_EDGE_QUADRANT( XX )
    if ( ! mFlightSim )
    {
	RETURN_TRUE_IF_EDGE_QUADRANT( YY )
    }
	RETURN_TRUE_IF_EDGE_QUADRANT( ZZ )
	return false;
}

/*****************************************************************************
 * @return True if object is inside the world.
 *****************************************************************************/
bool
World::IfInside( const Position& pos ) const
{
	return pos.x > 0 && pos.x < mDimWorld[XX]
        && pos.y > 0 && pos.y < mDimWorld[YY]
        && pos.z > 0 && pos.z < mDimWorld[ZZ];
}

/*****************************************************************************
 * Return amount of objects in the center/current quadrant.
 *****************************************************************************/
uint
World::GetObjectCntInCenterQuadrant( void ) const
{
	return gEng.mEye.GetQuadrant()->GetObjectCnt();
}

/*****************************************************************************
 * Set distances for when a small/large object is considered too distant to be visible.
 *****************************************************************************/
void
World::SetObjectSmallDist( fp dist )
{
	mObjectSmallDist  = dist;
	mObjectSmallDist2 = SQUARE(dist);
}
void
World::SetObjectLargeDist ( fp dist )
{
	mObjectLargeDist  = dist;
	mObjectLargeDist2 = SQUARE(dist);
}

/*****************************************************************************
 * In the future, this could consult some sort of terrain map (canyons, plateaus).
 *****************************************************************************/
bool
World::IfBelowGround( const Position& pos ) const
{
	return pos.y < 0;
}
bool
World::IfBelowGround( const MatrixExt& m ) const
{
	return ABS( m[Oy] ) < 0;	// absolute in case of negative Eye origin
}

/*****************************************************************************
 * @return A distance from the world's center that it's outside the world.
 *****************************************************************************/
fp
World::DistanceOutside( void ) const
{
	fp edgeGreatest = MAX( MAX( mDimWorld[XX], mDimWorld[YY] ), mDimWorld[ZZ] );
	return edgeGreatest;
}

/*****************************************************************************
 * @return Eye coordinate of frustum's far plane.
 * @remarks World has no near plane method as that value
 * depends more on the gfxsys than the world.
 *****************************************************************************/
fp
World::GetFrustumFar( void ) const
{
    // A greedy case is if the locus is very tall (locus Y edge is the max),
    // and viewpoint is at ground-level, then frustum should at least equal locus Y edge.
    const fp maxLocusEdge = MAX(MAX(mLocus.GetEdge(XX),mLocus.GetEdge(YY)),mLocus.GetEdge(ZZ));
    return maxLocusEdge;
}

////////////////////////////////////////////////////////////////////////////////
////////////////////////////////  Quadrant  ////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////

fp Quadrant::mEdge;		// all Quadrant edges are the same size

/*****************************************************************************
 * Construct a quadrant.
 * @param	tuple
 *			Tuple for mQuadrants[x,y,z].
 * @param	edge
 *			Edge of any quadrant (world coord).  Each edge is the same width.
 * @param	seed
 *			Random seed used for populating this Quadrant.
 * @param   shadow
 *			True if this is to be a shadow quadrant.
 *****************************************************************************/
Quadrant::Quadrant( const Array<3>& tuple,
                    const fp edge,
                    const uint seed,
                    bool shadow )
:
	mObjectDlist( Dlist<Object>::KEEP ),		// Keep as the global Eye can't be deleted.
	mDetectorDlist( Dlist<Detector>::KEEP )		// ~Object() deletes Detectors.
{
	// Keep this self-contained to simplify program initialization.
	SET_TYPESIG( this, TYPESIG_QUADRANT );
	mState			= eQuadrantState_EMPTY;
	// Create a shadow quadrant (unless this _is_ a shadow quadrant).
	mShadow			= shadow ? NULL : new Quadrant( tuple, edge, seed, true );
	mEdge			= edge;
	mSeed			= seed;									// this seeds random objects
	mTuple[XX]		= tuple[XX];
	mTuple[YY]		= tuple[YY];
	mTuple[ZZ]		= tuple[ZZ];
	mCube.x1		=  tuple[XX]    * edge;
	mCube.x2		= (tuple[XX]+1) * edge - 1;
	mCube.y1		=  tuple[YY]    * edge;
	mCube.y2		= (tuple[YY]+1) * edge - 1;
	mCube.z1		=  tuple[ZZ]    * edge;
	mCube.z2		= (tuple[ZZ]+1) * edge - 1;
	mPosition.Set( mCube.x1,								// order-dependent!
                   mCube.y1,
                   mCube.z1 );								// origin, equals Cube::x1,y1,z1
	mCenter.Set( mPosition.x + (mCube.x2 - mCube.x1) * 0.5,
                 mPosition.y + (mCube.y2 - mCube.y1) * 0.5,
                 mPosition.z + (mCube.z2 - mCube.z1) * 0.5 );  // order-dependent!
	mObjectCnt		= 0;
   	// QuadrantObject depends on Quadrant being constructed (can't be in ctor's init list).
    // ~Quadrant() deletes QuadrantObject indirectly by deleting Object dlist.
	mQuadrantObject	= new QuadrantObject( this );			// used for visibility tests
}

/*****************************************************************************
 * Quadrant destructor.
 *****************************************************************************/
Quadrant::~Quadrant()
{
//	if ( gExiting ) return;		// unnecessary unless a Quadrant is static

CHECK_TYPESIG(this,TYPESIG_QUADRANT);
	// Delete all Objects in this Quadrant.
	// ~Dlist() (of mObjectList) is told by Keep() to not delete Objects
	// because the global Eye (which is the only global Object) can't be deleted.
	for ( const Dlink<Object>* dlink = mObjectDlist.ForStart();
          mObjectDlist.ForTest(dlink);
          mObjectDlist.ForNext(dlink) )
	{
		Object* obj = dlink->mObj;
CHECK_TYPESIG(obj,TYPESIG_OBJECT);
		// Indeed, ~Object() will unlink itself from the same Dlist this loop
		// is iterating thru but the For*() helpers can handle it.
		if ( obj != &gEng.mEye ) delete obj;  // don't delete static Eye
	}
	DELETE_NULL( mShadow );
	//DELETE_NULL( mQuadrantObject );  // deleted by "delete obj" above
	INVALIDATE_TYPESIG( this, TYPESIG_QUADRANT );
}

/*****************************************************************************
 * Populate this Quadrant with objects.
 *****************************************************************************/
void
Quadrant::Populate( void )
{
	if ( mState != eQuadrantState_POPULATED )
	{
		gWorld.PopulateQuadrant( this );	// defer specifics to some module
		mState = eQuadrantState_POPULATED;	// afterwards
	}
}

/*****************************************************************************
 * Delete most objects in this Quadrant.
 * This conserves memory and is called when the quadrant is no longer in the locus.
 *****************************************************************************/
void
Quadrant::Shrink( void )
{
	// Already shrunk?
	if (   mState == eQuadrantState_EMPTY	// don't change state from empty to shrunk
        || mState == eQuadrantState_SHRUNK
        || gEng.GetSpeed() == eSpeed_FASTEST )
		return;

	// For each object in the quadrant's object list.
CHECK_TYPESIG( &mObjectDlist, TYPESIG_LIB_DLIST ); 
	for ( const Dlink<Object>* dlink = mObjectDlist.ForStart();
          mObjectDlist.ForTest(dlink);
          mObjectDlist.ForNext(dlink) )
	{
CHECK_TYPESIG( dlink, TYPESIG_LIB_DLINK );
CHECK_TYPESIG( dlink->mObj, TYPESIG_OBJECT );
		Object* object = dlink->mObj;
CHECK_TYPESIG(object,TYPESIG_OBJECT);
		if ( object->Reproducible() )
		{
			// This object can be reproduced (reconstructed).
			// Indeed, ~Object() will unlink itself from the same list this
			// loop is iterating on but the For*() helpers can handle it.
			delete object; DEBUG_CODE( object = NULL );
			//mObjectDlist.Unlink( dlink );	~Object() will unlink it
		}
	}

	mState = eQuadrantState_SHRUNK;
}

/*****************************************************************************
 * @return True if a Position is inside this Quadrant.
 *****************************************************************************/
bool
Quadrant::IfInside( const Position& pos ) const
{
	return mCube.IfInside( pos );
}

/*****************************************************************************
 * @return True if an object fits inside this Quadrant.
 * Returns false if it overlaps into another Quadrant(s).
 * @remarks Cube::IfInside() measures all three dimensions.
 * False would be undesirably returned for a Posrad of a Fixed object
 * at land altitude because the radius would extend below ground (Y dim).
 *****************************************************************************/
bool
Quadrant::IfInside( const Posrad& posrad ) const
{
	return mCube.IfInside( posrad );
}

/*****************************************************************************
 * Appropriate when height (Y) should be ignored.
 * For example, the area occupied by Objects is approximated by a radius.
 * The radius of a mountain, for example, extends far below ground,
 * in case IfInside(Posrad) would incorrectly return false.
 *****************************************************************************/
bool
Quadrant::IfInsideXZ( const Position& pos ) const
{
    return IfInsideXZ( Posrad(pos,0.0) );
}
bool
Quadrant::IfInsideXZ( const Posrad& posrad ) const
{
	return    posrad.x - posrad.mRadius >= mCube.x1
	       && posrad.x + posrad.mRadius <= mCube.x2
	       && posrad.z - posrad.mRadius >= mCube.z1
           && posrad.z + posrad.mRadius <= mCube.z2;
}

/*****************************************************************************
 * Quadrant::DynaMoved() must be called after a Dyna object is moved
 * in case it has moved from one Quadrant into another.
 * Movement can occur by translation, changing position, or changing matrix.
 *****************************************************************************/
void
Quadrant::DynaMoved( Dyna& dyna )
{
CHECK_TYPESIG( &dyna, TYPESIG_OBJECT );
	DynaMoved( dyna, dyna.GetPosition() );
}
void
Quadrant::DynaMoved( Dyna& dyna, const Position& pos )
{
ASSERT( gWorld.IfMade() );
CHECK_TYPESIG( &dyna, TYPESIG_OBJECT );

	// Is Dyna outside this quadrant?
	if ( ! mCube.IfInside( pos ) )
	{
		// Give this object to the quadrant the object has entered.
		QuadrantPtrConst taker = gWorld.GetQuadrant( pos );
CHECK_TYPESIG(taker,TYPESIG_QUADRANT);
		taker->Take( dyna, this );

        // Broadcast this event.  Since a Dyna may have moved into the Locus,
        // it could have disrupted the pile of sorted objects.
        gEngineEvent.mDynaChangeQuadrant.Broadcast( &dyna );
	}
}

/*****************************************************************************
 * Take an object from another Quadrant.
 * A consequence of moving a Dyna object across quadrants.
 *****************************************************************************/
void
Quadrant::Take( Object& object, QuadrantPtrConst giver )
{
ASSERT( gWorld.IfMade() );
CHECK_TYPESIG( &object, TYPESIG_OBJECT );
CHECK_TYPESIG( giver, TYPESIG_QUADRANT );

	// Unlink object out of giver's quadrant.
	giver->RemoveObject( object.GetLink() );

	// Link object into this quadrant.
	object.SetLink( AddObject( &object ) );

	// Migrate this object's Detector object (if it has one).
	object.MoveDetector( giver, this );

	// Update object's quadrant pointer.
	object.SetQuadrant( this );
}
// Although this is an ObjectMesh method, it's part of the implementation of Quadrant::Take().
void
ObjectMesh::MoveDetector( QuadrantPtrConst giver, QuadrantPtrConst taker )
{
CHECK_TYPESIG( giver, TYPESIG_QUADRANT );
CHECK_TYPESIG( taker, TYPESIG_QUADRANT );

	if ( mLinkDetector != NULL )
	{
CHECK_TYPESIG( mLinkDetector, TYPESIG_LIB_DLINK );
		Detector* detector = mLinkDetector->mObj;
		giver->RemoveDetector( mLinkDetector );
		mLinkDetector = taker->AddDetector( detector );
	}
}

/*****************************************************************************
 * Add/remove object to this Quadrant.
 *****************************************************************************/
Dlink<Object>*
Quadrant::AddObject( Object* obj )
{
CHECK_TYPESIG(obj,TYPESIG_OBJECT);
CHECK_TYPESIG(&mObjectDlist,TYPESIG_LIB_DLIST);

	++mObjectCnt;
	return mObjectDlist.Append( obj );
}
void
Quadrant::RemoveObject( Dlink<Object>* dlink )
{
CHECK_TYPESIG(dlink,TYPESIG_LIB_DLINK);
CHECK_TYPESIG(&mObjectDlist,TYPESIG_LIB_DLIST);

	--mObjectCnt;
	mObjectDlist.Unlink( dlink );
}

/*****************************************************************************
 * Add/remove a Detector to this Quadrant.
 *****************************************************************************/
Dlink<Detector>*
Quadrant::AddDetector( Detector* detector )
{
CHECK_TYPESIG(&mDetectorDlist,TYPESIG_LIB_DLIST);

	return mDetectorDlist.Append( detector );
}
// Does not free the unlinked object (caller should free it).
void
Quadrant::RemoveDetector( Dlink<Detector>* dlink )
{
CHECK_TYPESIG(dlink,TYPESIG_LIB_DLINK);
CHECK_TYPESIG(&mDetectorDlist,TYPESIG_LIB_DLIST);

	mDetectorDlist.Unlink( dlink );
}

/*****************************************************************************
 * @return True if Quadrant is visible (approximation).
 * This is used for speed to skip rendering most Objects in rear-facing Quadrants.
 * @remarks In a 3x1x3 Locus, up to 8 Quadrants can normally be visible.
 * Eg, when the Eye is nearly at one of the corners of the center Quadrant,
 * all Quadrants except the one at the corner are facing.
 *****************************************************************************/
bool
Quadrant::IfVisible( void ) const
{
CHECK_TYPESIG( mQuadrantObject, TYPESIG_OBJECT );

	return mQuadrantObject->Visible();
}

/*****************************************************************************
 * Return a random position in this Quadrant.
 *****************************************************************************/
void
Quadrant::RandomPosition( Position& pos ) const
{
	pos.x = mCube.x1 + random_f( mEdge );
	pos.y = mCube.y1 + random_f( mEdge );
	pos.z = mCube.z1 + random_f( mEdge );
}

/*****************************************************************************
 * Return amount of objects in this quadrant.
 *****************************************************************************/
uint
Quadrant::GetObjectCnt( void ) const
{
	// If this quadrant has a shadow, include the shadow's count.
	// Shadow quadrants are used by ObjectGroup.
	if ( mShadow != NULL )
		return mObjectCnt + mShadow->mObjectCnt;
	else
		return mObjectCnt;	// either quadrant has no shadow or is a shadow
}

/*****************************************************************************
 * Output Quadrant to stream.
 *****************************************************************************/
ostream&
operator<<( ostream& strm, const Quadrant& o )
{
	strm << "quadrant["
         << o.GetTuple()[XX] << ','
         << o.GetTuple()[YY] << ','
         << o.GetTuple()[ZZ] << ']' << ' ';
	switch ( o.GetState() )
	{
		case eQuadrantState_EMPTY:
		strm << "EMPTY ";
		break;

		case eQuadrantState_SHRUNK:
		strm << "SHRUNK ";
		break;

		case eQuadrantState_POPULATED:
		strm << "POPULATED ";
		break;

		default:
		strm << "INVALID "; ASSERT(0);
		break;
	}
    strm << endl << "  "
         << "seed=" << o.mSeed << ' '
         << "pos=" << o.GetPosition() << ' '
         << endl << "  "
         << "cube= " << o.GetCube() << ' ' << endl;
	return strm;
}

////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////  Locus  /////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////

/*****************************************************************************
 * An overhead view a 3x3x1 locus of quadrants.
 * @verbatim
 *	 +------+------+------+
 *	 |      |      |      |
 *	 |      |      |      |
 *	 +------+------+------+
 *	 |      |  .   |      |
 *	 |      | eye  |      |
 *	 +------+------+------+
 *	 |      |      |      |
 *	 |      |      |      |
 *	 +------+------+------+
 * @endverbatim
 *****************************************************************************/

/*****************************************************************************
 * Locus constructor.
 * @param	dim
 *			Dimensions must have odd values (see comments at Locus class).
 *****************************************************************************/
Locus::Locus( void )
{
    DEBUG_CODE( mValid = false; )
}
// Call once.
void
Locus::Init( const Array<3>& dim )
{
ASSERT_RUN_ONCE

	mDim = dim;
	mDim[XX] |= 1;		// ensure odd values
	mDim[YY] |= 1;
	mDim[ZZ] |= 1;
	mDimHalf[XX] = mDim[XX] >> 1;
	mDimHalf[YY] = mDim[YY] >> 1;
	mDimHalf[ZZ] = mDim[ZZ] >> 1;
	mCenterTuple = mDimHalf;		// equivalent

    DEBUG_CODE( mValid = true; )
}
Locus::~Locus()
{
    DEBUG_CODE( mValid = false; )
}

/*****************************************************************************
 * Update the locus of quadrants to the position of the viewpoint.
 * To conserve memory, quadrants are shrunk where the locus has moved away from.
 * A quadrant is shrunk by deleting objects that can be easily reconstructed.
 * When the locus is moved over shrunk quadrants, Quadrant::Populate()
 * is called to reconstruct the delete objects.
 *****************************************************************************/
// Move Locus to where the Eye is.
void
Locus::Update( void )
{
ASSERT( mValid );
ASSERT( gEng.mEye.mInitialized );

	// Bypass if Eye is still in the same Quadrant.
	static QuadrantPtr prevQuadrant;
	if ( prevQuadrant != gEng.mEye.GetQuadrant() )
	{
		prevQuadrant = gEng.mEye.GetQuadrant();
CHECK_TYPESIG(prevQuadrant,TYPESIG_QUADRANT);
		Update( gEng.mEye.GetPosition() );
#if DEBUG
		// Eye's quadrant should be included in the Locus and at its center quadrant.
		ASSERT( std::find( mQuadrants.begin(), mQuadrants.end(), GET_PTR(gEng.mEye.GetQuadrant()) ) != mQuadrants.end() );
		ASSERT( gEng.mEye.GetQuadrant() == GetCenterQuadrant() );
#endif
	}
}
void
Locus::Update( const Position& pos )
{
ASSERT( mValid );
ASSERT( gWorld.mQuadrants.size() );

	static vector<Quadrant*> prevQuadrants;		// quadrants of previous locus
	static Array<3>          prevCenter(-1);	// tuple of center quadrant

	// The new locus shall surround the given position
	// (the given position is the center of the new locus).
	Array<3> center = gWorld.GetQuadrantTuple( pos );	// tuple of center quadrant

	// Unless viewpoint is still in the same quadrant.
	if ( center != prevCenter )
	{
		prevQuadrants = mQuadrants;		// current locus becomes the previous
		prevCenter    = center;

		// Move the locus over another set of quadrants.
		// Refill mQuadrants[].
		// As the locus moves away from quadrants, they will be shrunk.
		// Conversely, as the locus moves over quadrants, shrunk ones wiil be repopulated.
		mQuadrants.clear();
		Array<3> t;
		for ( t[XX] = center[XX]-mDimHalf[XX]; t[XX] <= center[XX]+mDimHalf[XX]; ++t[XX] )
		for ( t[YY] = center[YY]-mDimHalf[YY]; t[YY] <= center[YY]+mDimHalf[YY]; ++t[YY] )
		for ( t[ZZ] = center[ZZ]-mDimHalf[ZZ]; t[ZZ] <= center[ZZ]+mDimHalf[ZZ]; ++t[ZZ] )
		{
			Quadrant* q = GET_PTR( gWorld.GetQuadrant(t) );
			DEBUG2_CODE( if ( q != NULL ) { CHECK_TYPESIG( q, TYPESIG_QUADRANT ); } )
			mQuadrants.push_back( q );
			if ( q->GetState() != eQuadrantState_POPULATED ) q->Populate();
		}

		// To conserve memory, shrink any quadrant in the previous locus
		// but not in the current.
		for ( QuadrantItr itr = prevQuadrants.begin(); itr != prevQuadrants.end(); ++itr )
		{
			// Only shrink populated quadrants (not empty ones).
			Quadrant* qPrev = *itr;		// quadrant in previous locus
			DEBUG2_CODE( if ( qPrev != NULL ) { CHECK_TYPESIG( qPrev, TYPESIG_QUADRANT ); } )
			if ( std::find( mQuadrants.begin(), mQuadrants.end(), qPrev ) == mQuadrants.end() )
				if ( qPrev->GetState() == eQuadrantState_POPULATED ) qPrev->Shrink();
		}
	}

    // Updating Locus disrupts the Engine's heap of sorted objects.
    // Tell Engine that it must fully re-sort again.
    gEngineEvent.mLocusChange.Broadcast();
}

/*****************************************************************************
 * Return center Quadrant in the Locus.
 *****************************************************************************/
QuadrantPtrConst
Locus::GetCenterQuadrant( void ) const
{
ASSERT( mValid );

	uint idxCenter = GetQuadrantIdx( mCenterTuple );
ASSERT( idxCenter < mQuadrants.size() );
CHECK_TYPESIG( mQuadrants[idxCenter], TYPESIG_QUADRANT );
	return mQuadrants[idxCenter];
}

/*****************************************************************************
 * @return Flat index for mQuadrants[] equivalent to mQuadrants[x][y][z].
 * Unlike World's counterpart, does NOT accept an invalid tuple.
 *****************************************************************************/
uint
Locus::GetQuadrantIdx( const Array<3>& tuple ) const
{
ASSERT( mValid );

	// From the tuple [x][y][z], compute a flat index to the Quadrant vector.
	uint idx =   tuple[XX] * mDim[YY] * mDim[ZZ]	 // think per square of a cube
               + tuple[YY] * mDim[ZZ]				 // think per row of a cube
               + tuple[ZZ];
	ASSERT( idx < mQuadrants.size() );
	return idx;
}

/*****************************************************************************
 * @return Amount of Objects in locus.
 *****************************************************************************/
uint
Locus::GetObjectCnt( void ) const
{
ASSERT( mValid );

	uint cnt = 0;
	for ( ConstQuadrantItr itr = mQuadrants.begin();
          itr != mQuadrants.end();
          ++itr )
	{
		QuadrantPtr quadrant = *itr;
CHECK_TYPESIG(quadrant,TYPESIG_QUADRANT);
		cnt += quadrant->GetObjectCnt();
	}
	return cnt;
}

/*****************************************************************************
 * Return the size of an edge of the locus (in world coords).
 *****************************************************************************/
fp
Locus::GetEdge( uint dim ) const
{
ASSERT( mValid );
ASSERT( dim < 3 );

	if ( gWorld.IfMade() )
        return mDim[dim] * gWorld.GetQuadrantEdge();
    else
		return WORLD(100000.0);  // this happens when -far/-near is passed, return interim value
}

/*****************************************************************************
 * Output Locus to stream.
 *****************************************************************************/
ostream&
operator<<( ostream& strm, const Locus& o )
{
	strm << "Locus["
         << o.mDim[XX] << ','
         << o.mDim[YY] << ','
         << o.mDim[ZZ] << ']' << endl;
	for ( ConstQuadrantItr itr = o.mQuadrants.begin();
          itr != o.mQuadrants.end();
          ++itr )
	{
		strm << **itr;	// print quadrants
	}
	return strm;
}

////////////////////////////////////////////////////////////////////////////////
//////////////////////////  QuadrantObject class  //////////////////////////////
////////////////////////////////////////////////////////////////////////////////

/*****************************************************************************
 * The purpose of this object is to test the visibility of an entire Quadrant.
 * For speed, if not visible, rendering bypasses all of its Objects.
 *****************************************************************************/
QuadrantObject::QuadrantObject( QuadrantPtrConst q )
: Parent(q,q->GetCenter())
{
	SetPosition( q->GetCenter() );
	SetRadius( gWorld.GetQuadrantEdge() * 0.707 ); // sqrt(0.5 + 0.5)

	// The corners of the quadrants.
	fp y  = q->GetCube().y1;
	fp yi = (q->GetCube().y2 - q->GetCube().y1) / GetPolygonCnt();

	for ( uint i = 0; i < GetVertexCnt(); i += 4 )
	{
		mWorldVertexs[i+0].x = q->GetCube().x1;
		mWorldVertexs[i+0].y = y;
		mWorldVertexs[i+0].z = q->GetCube().z1;

		mWorldVertexs[i+1].x = q->GetCube().x2;
		mWorldVertexs[i+1].y = y;
		mWorldVertexs[i+1].z = q->GetCube().z1;

		mWorldVertexs[i+2].x = q->GetCube().x1;
		mWorldVertexs[i+2].y = y;
		mWorldVertexs[i+2].z = q->GetCube().z2;

		mWorldVertexs[i+3].x = q->GetCube().x2;
		mWorldVertexs[i+3].y = y;
		mWorldVertexs[i+3].z = q->GetCube().z2;

		y += yi;
	}

	FinalConstruction();
}
QuadrantObject::~QuadrantObject()
{
	// ~Object() does it.
}

/*****************************************************************************
 * The regular Object::Visible() isn't appropriate for extremely large objects
 * such as QuadrantObject.
 *****************************************************************************/
int
QuadrantObject::Visible( void )
{
	// Returns true unless all Z coords are behind viewpoint.
	return VisibleSimple();
}
