/*****************************************************************************
 * $Id: eng_polygon.cc,v 1.116 2006/08/27 18:48:01 devel Exp $
 * @file
 * @author	Jim E. Brooks  http://www.jimbrooks.org
 * @brief	Polygon classes.
 * @verbatim
 *
 * Creating PolygonList objects:
 * -----------------------------
 *
 * - Create a PolygonList object.
 * - To create Polygon objects one-by-one:
 *   - First, create a complete PolygonAttribs object.
 *   - Create the Polygon object by calling PolygonList::NewPolygon()
 *     and pass the completed PolygonAttribs object.
 *   - If the PolygonAttribs object is shared by SharedVal (the default),
 *     don't pass a blank PolygonAttribs object to the Polygon constructor
 *     then try modifying it afterwards -- that won't work because SharedVal
 *     has created a separate shared copy.
 *   - When the PolygonList is fully constructed, call PolygonList::Optimize().
 *
 * Sharing PolygonList objects:
 * ----------------------------
 *
 * To share a PolyonList object's resources, either make a copy of it
 * using the copy constructor, or construct one instance and have
 * static members of Object-derived classes pointer to it.
 * The former is easier, the latter requires a reference count
 * so that the destruction can avoid multiple deletions of it.
 *
 * Sharing Polygon objects:
 * ------------------------
 *
 * They're not shared since most polygons will probably contain different data.
 *
 * Sharing PolygonAttribs:
 * -----------------------
 *
 * By default, PolygonAttribs objects are automatically shared
 * when a PolygonAttribs object is passed to the Polygon constructor.
 *
 * Sharing polygon data:
 * ---------------------
 *
 * (Somewhat theoretical, somewhat practical.)
 *
 * Sharing polygon data can save lots of memory but a few 3D objects
 * may require private polygon data.  There are various ways to share objects, eg:
 * - the conventional way is to allocate an object and use multiple pointers to it
 * - sharing by copying objects but they share the resources they have pointers to
 * - use the template class SharedVal that is based on a reference count and deep copying
 *
 * Sharing using the ways based on pointers is appropriate when changes to
 * one polygon object should affect multiple polygons of an individual 3D object.
 * Eg, changing the color of a set of polygons that point to the same RGBA object.
 *
 * Sharing using SharedVal offers the most memory savings.
 * Any polygon object with the same value can be shared, and sharing spans 3D objects.
 * A disadvantage is that it requires a copy constructor that does deep copying.
 *
 * PolygonAttribs:
 * ---------------
 *
 * One scenario is where the sharing of one PolygonAttrib object is predetermined.
 * Multiple instances of the same 3D object all share the same polygon
 * attributes (eg Tree objects).  The PolygonAttribs object is constructed,
 * the Set*() methods are applied to that initial object.
 * Then, for every instance of the same class of 3D object, that PolygonAttribs
 * object is shared by new polygons.
 *
 * Another scenario is where the sharing of several PolygonAttrib objects is anticipated
 * but not exactly predetermined.  This is one reason for the template function Share().
 * Eg, a Craft object is anticipated to have sets of polygons sharing sets of the same attributes.
 * As the Craft object's polygon data is constructed, code in the Polygon classes
 * will identify polygon data with the same values and will create shared objects
 * (rather than wastefully creating copies with the same values).
 *
 * Vertex arrays:
 * --------------
 * Blender models are usually comprised of a mixture of triangles and quads.
 * This is why the PolygonList class has 2 VertexArray objects.
 *
 * @endverbatim
 *//*
 * LEGAL:	COPYRIGHT (C) JIM E. BROOKS 2005
 *          THIS SOURCE CODE IS RELEASED UNDER THE TERMS
 *          OF THE GNU GENERAL PUBLIC LICENSE (GPL).
 *****************************************************************************/

#define ENG_POLYGON_CC 1
#include "gfx.hh"
#include "gfx_shared_val.hh"
#include "eng.hh"
#include "eng_polygon.hh"

// Shared objects.
namespace gfx {
template<> SharedValFactory<PolygonAttribs>* SharedValFactory<PolygonAttribs>::mInstance = NULL;
}

// GP_TRIANGLES, GP_QUADS, etc table indexed by a polygon's vertex count.
static eGp sGpTable[MAX_POLYGON_VERTEXS+1+10];

// Temporaries.
static EyeVertex* sEyeVertexs;

/*****************************************************************************
 * Initialize static vars.
 *****************************************************************************/
void
init_eng_polygon( void )
{
	// Initialize sGpTable[].
	for ( uint i = 0; i < ELEMS(sGpTable); ++i )
	{
		if ( i == 3 )
			sGpTable[i] = GP_TRIANGLES;
		else if ( i == 4 )
			sGpTable[i] = GP_QUADS;
		else
			sGpTable[i] = GP_POLYGON;
	}
}

////////////////////////////////////////////////////////////////////////////////
/////////////////////////////  VertexArray  ////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////

/*****************************************************************************
 * Constructor.
 *****************************************************************************/
VertexArray::VertexArray( const uint polygonCnt, const uint vertexPerPolygon, TexturePtrc texture )
{
	ASSERT( polygonCnt > 0 );
	ASSERT( polygonCnt < MAX_POLYGONS );
	ASSERT( vertexPerPolygon == 3 || vertexPerPolygon == 4 );

	// Order-dependent.
	mPrim			= sGpTable[vertexPerPolygon];
	ASSERT( mPrim == GP_TRIANGLES || mPrim == GP_QUADS );
	mVertexCnt		= vertexPerPolygon * polygonCnt;	// each polygon has same amount of vertexs
	mVixCnt			= mVertexCnt;
	mVixArr			= new VaVix[mVixCnt];
	mTexCoordCnt	= texture != NULL ? texture->DimCnt() * mVertexCnt : 0;  // tex coords per vertex
	mTexCoordArr	= texture != NULL ? new VaTexCoord[mTexCoordCnt] : NULL;
	mRgbaElemCnt	= 4 * mVertexCnt;					// 4 elems in RGBA (one RGBA per vertex)
	mRgbaElemArr	= new VaRgbaElem[mRgbaElemCnt];
	mTexture		= texture;
}
VertexArray::~VertexArray()
{
	DELETE_ARR_NULL( mVixArr );
	DELETE_ARR_NULL( mTexCoordArr );
	DELETE_ARR_NULL( mRgbaElemArr );
}

/*****************************************************************************
 * Builds a second array of eye vertexs in a linear order suited to an OpenGL vertex array.
 * Eg, imagine an Object comprised of 2 triangles joined at one edge.
 *
 * Input:
 * ve[0] = {..}
 * ve[1] = {..}
 * ve[2] = {..}
 * ve[3] = {..}
 * poly_vix[0] = { 0, 1, 2 }
 * poly_vix[1] = { 0, 1, 3 }
 *
 * Output (ve2):
 * ve2[0] = ve[0]
 * ve2[1] = ve[1]
 * ve2[2] = ve[2]
 * ve2[3] = ve[0]
 * ve2[4] = ve[1]
 * ve2[5] = ve[3]
 *
 * Thus, glDrawArray() can linearly "plow" thru the elements of
 * a non-indexed vertex array.
 *****************************************************************************/
const EyeVertex*
VertexArray::Linearize( const EyeVertex* const ev )
{
	// Use separate temp array as input itself is another temp array.
	static TempArray<EyeVertex> tempArrayEyeVertex;
	EyeVertex* const ev2 = tempArrayEyeVertex.Get( mVixCnt );

	// For each vertex index.
	for ( Vix i = 0; i < mVixCnt; ++i )
	{
		// The input vertex is referenced by a vertex index ([vix]).
		// The output vertex ([i]) is appended to an OpenGL vertex array.
		Vix vix = mVixArr[i];
		ASSERT( vix < MAX_VERTEXS );
		ev2[i] = ev[vix];
	}

	return ev2; // temp array will survive long enough
}

////////////////////////////////////////////////////////////////////////////////
/////////////////////////  PolygonAttribs class  ///////////////////////////////
////////////////////////////////////////////////////////////////////////////////

/*****************************************************************************
 * Default constructor.
 *****************************************************************************/
PolygonAttribs::PolygonAttribs( void )
{
	Init();
	ENGINE_STATS_CODE( ++gEng.mStats.mPolygonAttribs; )
}
void
PolygonAttribs::Init( void )
{
	SET_TYPESIG( this, TYPESIG_POLYGON_ATTRIBS );
	CLEAR( &mBits, sizeof(mBits) );
	//mRgba
	mTexture		= NULL;
	mTexCoords		= NULL;
}

/*****************************************************************************
 * Constructor.
 * @param	rgba
 * @param	texture
 *          Pass NULL if the polygon has no texture.
 * @param	texCoordCnt
 *          If the polygon has a texture, this should equal vixCnt and vertexCnt
 *          (one 2D texture coordinate for each polygon 3D vertex).
 * @param	shared (default true)
 *			This specifically tells the Polygon constructor whether to share this object.
 *****************************************************************************/
PolygonAttribs::PolygonAttribs( const RGBA rgba, TexturePtrc texture, uint texCoordCnt, bool shared )
:	mRgba(rgba)
{
ASSERT( texCoordCnt <= TEXTURE_COORDS_MAX );
DEBUG_CODE( if ( texture != NULL ) ASSERT( texCoordCnt > 0 ); else ASSERT( texCoordCnt == 0 ); )
	Init();
	mBits.mShared       = shared;
	mBits.mTexCoordCnt  = texCoordCnt;
	mTexture		    = texture;
	mTexCoords		    = mTexture != NULL ? new TexCoord2[texCoordCnt] : NULL;
	ENGINE_STATS_CODE( ++gEng.mStats.mPolygonAttribs; )
}

/*****************************************************************************
 * Copy constructor.
 *****************************************************************************/
PolygonAttribs::PolygonAttribs( const PolygonAttribs& src )
{
	Init();			// so that copy constructor won't free garbage
	*this = src;	// copy constructor will free members of this
	ENGINE_STATS_CODE( ++gEng.mStats.mPolygonAttribs; )
}

/*****************************************************************************
 * Destructor.
 *****************************************************************************/
PolygonAttribs::~PolygonAttribs()
{
	INVALIDATE_TYPESIG( this, TYPESIG_POLYGON_ATTRIBS );
	Free();
	ENGINE_STATS_CODE( --gEng.mStats.mPolygonAttribs; )
}
void
PolygonAttribs::Free( void )
{
	DELETE_ARR_NULL( mTexCoords );
	// (don't delete Texture object)
}

/*****************************************************************************
 * Assignment operator.  Effectively does a deep copy (required by SharedVal template).
 *****************************************************************************/
PolygonAttribs&
PolygonAttribs::operator=( const PolygonAttribs& src )
{
	CHECK_TYPESIG( this, TYPESIG_POLYGON_ATTRIBS );
	CHECK_TYPESIG( &src, TYPESIG_POLYGON_ATTRIBS );
	// Self-assignment is unexpected but not handling it would be folly.
	if ( EX( &src != this ) )
	{
		// Free resources before reassignment.
		Free();

		// Reassign.
		mBits      = src.mBits;
		mRgba      = src.mRgba;
		mTexture   = src.mTexture;
		mTexCoords = src.mBits.mTexCoordCnt > 0 ? NewArray<TexCoord2>( src.mTexCoords, src.mBits.mTexCoordCnt ) : NULL;
	}
	return *this;
}

/*****************************************************************************
 * Set RGBA attribute.
 *****************************************************************************/
void
PolygonAttribs::SetRgba( const RGBA rgba )
{
	CHECK_TYPESIG( this, TYPESIG_POLYGON_ATTRIBS );
	mRgba = rgba;
}

/*****************************************************************************
 * Set Texture attribute.
 *****************************************************************************/
void
PolygonAttribs::SetTexture( TexturePtrc texture )
{
	CHECK_TYPESIG( this, TYPESIG_POLYGON_ATTRIBS );
	mTexture = texture;
}

/*****************************************************************************
 * Add a 2D texture coordinate.
 *****************************************************************************/
void
PolygonAttribs::AddTexCoord( const TexCoord2* const texcoord )
{
	CHECK_TYPESIG( this, TYPESIG_POLYGON_ATTRIBS );
	ASSERT( mBits.mTexCoordsTail < mBits.mTexCoordCnt );
	mTexCoords[mBits.mTexCoordsTail++] = *texcoord;
}
void
PolygonAttribs::AddTexCoord( fp x, fp y )
{
	TexCoord2 t;	// TODO TexCoord is a misnomer, rather, its a texture tuple/vertex
	t.x = x;
	t.y = y;
	AddTexCoord( &t );
}

/*****************************************************************************
 * Helper method to add a set of three 2D texture coordinates for a triangle.
 *****************************************************************************/
void
PolygonAttribs::AddTexCoordsTriangle( void )
{
	CHECK_TYPESIG( this, TYPESIG_POLYGON_ATTRIBS );
	static const TexCoord2 texCoords[3] = { { 0.0, 0.0 },
                                            { 0.0, 1.0 },
                                            { 1.0, 1.0 } };
	AddTexCoord( &texCoords[0] );
	AddTexCoord( &texCoords[1] );
	AddTexCoord( &texCoords[2] );
}

/*****************************************************************************
 * Required by SharedVal's use of STL map.
 *****************************************************************************/
bool
operator<( const PolygonAttribs& a, const PolygonAttribs& b )
{
	// Be careful comparing addresses of objects.
	// Objects with different values could be allocated
	// from the same recycled heap memory.
	CHECK_TYPESIG( &a, TYPESIG_POLYGON_ATTRIBS );
	CHECK_TYPESIG( &b, TYPESIG_POLYGON_ATTRIBS );

	// sizeof(uint)==sizeof(PolygonAttribsBits) assumption verified by SelfCheck().
	RETURN_LT_TRUE_GT_FALSE( *reinterpret_cast<const uint*>( &a.mBits ),
                             *reinterpret_cast<const uint*>( &b.mBits ) )
	RETURN_LT_TRUE_GT_FALSE( a.mRgba,
                             b.mRgba )
	RETURN_LT_TRUE_GT_FALSE( long(GET_PTR(a.mTexture)),
                             long(GET_PTR(b.mTexture)) )
	for ( uint i = 0; i < MAX(a.mBits.mTexCoordCnt,b.mBits.mTexCoordCnt); ++i )
	{
		if ( i >= a.mBits.mTexCoordCnt )
			return true;
		if ( i >= b.mBits.mTexCoordCnt )
			return false;
		RETURN_LT_TRUE_GT_FALSE( a.mTexCoords[i],
                                 b.mTexCoords[i] )
	}
	return false; // equal
}

////////////////////////////////////////////////////////////////////////////////
/////////////////////////////  Polygon class  //////////////////////////////////
////////////////////////////////////////////////////////////////////////////////

/*****************************************************************************
 * Constructor.
 * @param   attribs
 *          Polygon attributes object.  If PolygonAttribs.mBits.mShare is true,
 *          it is shared using SharedVal.  Otherwise, its pointer is stored
 *          and the caller is responsible for deleting it.
 * @param	vixCnt
 *			Amount of vertex indexs in this polygon.
 * @param	num
 *			Polygon number which correlates to the index in a normal vector array.
 *          Eg, normal[num] is the normal vector on this polygon.
 *****************************************************************************/
Polygon::Polygon( PolygonAttribs* attribs, uint vixCnt, uint num )
{
CHECK_TYPESIG( attribs, TYPESIG_POLYGON_ATTRIBS );
ASSERT( vixCnt <= MAX_POLYGON_VERTEXS );
ASSERT( num < MAX_POLYGONS );

	SET_TYPESIG( this, TYPESIG_POLYGON );
	CLEAR( &mBits, sizeof(mBits) );
	mBits.mVixCnt	= vixCnt;
	mBits.mNum		= num;
	mAttribs		= attribs->IfShared() ? ShareVal<PolygonAttribs>( attribs ) : attribs;
	mVixArr			= NewArray<Vix>( vixCnt, VIX_NONE );
}
Polygon::~Polygon()
{
	INVALIDATE_TYPESIG( this, TYPESIG_POLYGON );
	if ( mAttribs->IfShared() )	UnshareVal<PolygonAttribs>( mAttribs ); // else don't delete
	DELETE_ARR_NULL( mVixArr );
}

/*****************************************************************************
 * Add a vertex index.
 * Heed that the array which holds vertex indexs has a fixed-length.
 *****************************************************************************/
void
Polygon::AddVix( Vix vix )
{
ASSERT( vix != VIX_NONE && vix <= MAX_VERTEXS );

	// Scan for the first empty element.
	for ( uint i = 0; i < mBits.mVixCnt; ++i )
	{
		if ( mVixArr[i] == VIX_NONE )	// empty element?
		{
			mVixArr[i] = vix;	// occupy it
			return;
		}
	}

ASSERT(0); // oops, array full
}

////////////////////////////////////////////////////////////////////////////////
///////////////////////////  PolygonList class  ////////////////////////////////
////////////////////////////////////////////////////////////////////////////////

// A PolygonList object's resources (Dlist) are shared rather than the object itself.
// SharedVal can't be applied as Dlist doesn't have a copy constructor.
// See eng_polygon.hh and implementation.html.

ObjectMesh* PolygonList::msDrawObj;					// alive only during Draw*()

/*****************************************************************************
 * Constructor.
 *****************************************************************************/
PolygonList::PolygonList( void )
{
	SET_TYPESIG( this, TYPESIG_POLYGON_LIST );
	CLEAR( &mBits, sizeof(mBits) );
	mPolygonDlistAll         = new Dlist<Polygon>( Dlist<Polygon>::KEEP ); // keep, otherwise double-deletion
	mPolygonDlistOpaque      = new Dlist<Polygon>;
	mPolygonDlistTextured    = new Dlist<Polygon>;
	mPolygonDlistTranslucent = new Dlist<Polygon>;
	mTextureSingle           = NULL;
	mPolygonCnt              = 0;
	mVertexArray[0]          = NULL;
	mVertexArray[1]	         = NULL;
	mRefCntPtr		         = new int;  // reference count isn't tied to this object
	*mRefCntPtr		         = 1;
}

/*****************************************************************************
 * Copy constructor.
 * This can be used to effectively share a PolygonList object
 * as it shares its resources (see eng_polygon.hh and implementation.html).
 * @param	src
 *****************************************************************************/
PolygonList::PolygonList( const PolygonList& src )
{
	*this = src;
}
PolygonList& PolygonList::operator=( const PolygonList& src )
{
	// Copying pointers is safe as the destructor does nothing
	// until the reference count hits zero.
	SET_TYPESIG( this, TYPESIG_POLYGON_LIST );
	mBits					 = src.mBits;
	mDrawParm				 = src.mDrawParm;
	mPolygonDlistAll		 = src.mPolygonDlistAll;
	mPolygonDlistOpaque		 = src.mPolygonDlistOpaque;
	mPolygonDlistTextured	 = src.mPolygonDlistTextured;	
	mPolygonDlistTranslucent = src.mPolygonDlistTranslucent;
	mTextureSingle			 = src.mTextureSingle;
	mPolygonCnt				 = src.mPolygonCnt;
	mVertexArray[0]			 = src.mVertexArray[0];
	mVertexArray[1]			 = src.mVertexArray[1];
	mRefCntPtr				 = src.mRefCntPtr;  // reference count stored on heap (untied)
	++(*mRefCntPtr);
	return *this;
}

/*****************************************************************************
 * Destructor.
 *****************************************************************************/
PolygonList::~PolygonList()
{
ASSERT( *mRefCntPtr > 0 );
	// Don't delete shared resources until the reference count hits zero.
	if ( --(*mRefCntPtr) == 0 )		// ref cnt stored on heap
	{
		// ~Dlist() deletes all the linked Polygon objects and the list itself.
		// Except mPolygonDlistAll as Keep() was called to avoid double-deletion.
		DELETE_NULL( mPolygonDlistAll );
		DELETE_NULL( mPolygonDlistOpaque );
		DELETE_NULL( mPolygonDlistTextured );
		DELETE_NULL( mPolygonDlistTranslucent );
		DELETE_NULL( mVertexArray[0] );
		DELETE_NULL( mVertexArray[1] );
		DELETE_NULL( mRefCntPtr );
	}
	INVALIDATE_TYPESIG( this, TYPESIG_POLYGON_LIST );
}

/*****************************************************************************
 * External code should call this upon completion of building a PolygonList.
 * The PolygonList will optimize itself.
 * This is required -- Draw() depends of mHasTranslucent.
 * Notes: Why is the vertex count passed to Optimize() but not the constructor?
 *        Because the Blender import code calls "new PolygonList" before
 *        it yet knows the vertex count.
 *****************************************************************************/
void
PolygonList::Optimize( const uint vertexCnt )
{
	if ( mBits.mOptimized ) return;

ASSERT( vertexCnt < MAX_VERTEXS );

	CLEAR( &mBits, sizeof(mBits) );
	mBits.mTriQuad = 1;			// assume all polygons are triangles or quads
	bool foundTexture = false;
	bool testSameVertexCnt = true;
	bool testTriQuad = true;
	uint triCnt = 0, quadCnt = 0;

	// Examine each polygon to produce parameters (mBits) to optimize Draw*().
	for ( const Dlink<Polygon>* dlink = mPolygonDlistAll->ForStart();
          mPolygonDlistAll->ForTest(dlink);
          mPolygonDlistAll->ForNext(dlink) )
	{
		const Polygon* const polygon = dlink->mObj;
		CHECK_TYPESIG( polygon, TYPESIG_POLYGON );
		const PolygonAttribs* const attribs = polygon->GetAttribs();
		CHECK_TYPESIG( attribs, TYPESIG_POLYGON_ATTRIBS );

		// Is any polygon wireframe?
		// If not, Draw() can bypass changing line width.
		if ( attribs->IfWireframe() ) mBits.mAnyWireframe = true;

		// Is there exactly one Texture object?
		// If so, loading textures can be minimized.
		if ( ! mBits.mTexturesDiffer )
		{
			// Does this polygon have a texture?
			TexturePtrc texture = attribs->GetTexture();
			if ( texture != NULL )
			{
				// Yes.  Is this the first texture so far?
				if ( ! foundTexture )
				{
					// Assume it is single.  To be proved.
					foundTexture = true;
					mBits.mTexturesDiffer = false;
					mTextureSingle        = texture;
				}
				else if ( texture != mTextureSingle )
				{
					// Found a different texture.
					mBits.mTexturesDiffer = true;	// stops testing
					mTextureSingle        = NULL;
				}
			}
		}

		const uint vixCnt = polygon->GetVixCnt();

		// Do all polygons have the same amount of vertexs?
		// If so, calling GFX_BEGIN() can be minimized.
		if ( testSameVertexCnt )
		{
			if ( mBits.mSameVixCnt == 0 )
			{
				// First polygon encountered.
				// Assume vertex counts are the same (to be proved).
				mBits.mSameVixCnt = vixCnt;
			}
			else if ( mBits.mSameVixCnt != vixCnt )
			{
				// Vertex counts differ, stop testing.
				mBits.mSameVixCnt = 0;
				testSameVertexCnt = false;
			}
		}

		// Are all polygons triangles and/or quads?
		// If so, vertex arrays could be used.
		triCnt  += (vixCnt == 3);
		quadCnt += (vixCnt == 4);
		if ( testTriQuad )
		{
			if ( vixCnt != 3 && vixCnt != 4 )
			{
				// False assumption, stop testing.
				mBits.mTriQuad = 0;
				testTriQuad = false;
			}
		}
	}

	// Are any polygons translucent or textured or opaque?
	// This helps Draw() to call the appropriate Draw*() subroutines.
	mBits.mAnyOpaque      = ! mPolygonDlistOpaque->IfEmpty();
	mBits.mAnyTextured    = ! mPolygonDlistTextured->IfEmpty();
	mBits.mAnyTranslucent = ! mPolygonDlistTranslucent->IfEmpty();

	// Can faster vertex arrays be used?
	// TODO: A single bit-mask would be faster.
	if (      ( mBits.mAnyOpaque + mBits.mAnyTextured == 1 )	  // either but not a mixture of both
           && ! mBits.mAnyTranslucent
           && ( ! mBits.mAnyTextured || ! mBits.mTexturesDiffer ) // if zero or one texture
           && mBits.mTriQuad )
	{
		if ( mBits.mSameVixCnt == 3 )
		{
			// All polygons are triangles.
			mVertexArray[0] = BuildVertexArray( 3, triCnt );
			mVertexArray[1] = NULL;
		}
		else if ( mBits.mSameVixCnt == 4 )
		{
			// All polygons are quads.
			mVertexArray[0] = BuildVertexArray( 4, quadCnt );
			mVertexArray[1] = NULL;
		}
		else
		{
			// Mixture of triangles/quads.
			mVertexArray[0] = BuildVertexArray( 3, triCnt  );
			mVertexArray[1] = BuildVertexArray( 4, quadCnt );
		}

		mBits.mVertexArray = 1; // this polygon list has a vertex array(s)
	}

	mBits.mOptimized = true;
}

/*****************************************************************************
 * Build vertex array (and associated arrays) of triangles or quads.
 * @param	triQuad
 *			3 or 4.
 * @param	triQuadCnt
 *          Count of polygons that are either triangles or quads.
 * @return	VertexArray object.
 *****************************************************************************/
VertexArray*
PolygonList::BuildVertexArray( const uint triQuad, const uint triQuadCnt )
{
	ASSERT( triQuad == 3 || triQuad == 4 );
	ASSERT( triQuadCnt > 0 && triQuadCnt <= GetPolygonCnt() );

	// Create VertexArray object.
	// Use triQuadCnt (not PolygonCnt() which counts all polygons).
	VertexArray* vertexArray = new VertexArray( triQuadCnt, triQuad, mTextureSingle );

	// Fill VertexArray object.
	// For each polygon.
	uint iVa = 0;	// index to vertex array and associated arrays
	for ( const Dlink<Polygon>* dlink = mPolygonDlistAll->ForStart();
          mPolygonDlistAll->ForTest(dlink);
          mPolygonDlistAll->ForNext(dlink) )
	{
		// Skip quads if building triangles v.v.
		const Polygon* const polygon = dlink->mObj;
		if ( polygon->GetVixCnt() == triQuad )
		{
			// For each vertex/vix of this polygon.
			const PolygonAttribs* const attribs = polygon->GetAttribs();
			for ( uint i = 0;
                  i < triQuad;
                  ++i, ++iVa )
			{
				// Append to vix array (this isn't an OpenGL indexed vertex array).
				const Vix vix = polygon->GetVix( i );
				vertexArray->SetVix( iVa, vix );

				// Set texture coordinates associated with vertex array (optional).
				if ( mBits.mAnyTextured )
					vertexArray->SetTexCoord( iVa, attribs->GetTexCoord(i) );

				// Set RGBA elements associated with vertex array.
				vertexArray->SetRgba( iVa, attribs->GetRgba() );
			}
		}
	}

	ASSERT( iVa == vertexArray->GetPrimCnt() );

	return vertexArray;
}

/*****************************************************************************
 * Construct a new polygon with specified attributes and append it to list.
 * Its pointer is returned -- so that the caller can add vertex indexs to it.
 * Caller shouldn't ever delete the Polygon (PolygonList destructor does).
 * @param	(same as Polygon::Polygon)
 *****************************************************************************/
Polygon*
PolygonList::AddPolygon( PolygonAttribs* attribs, uint vixCnt )
{
	// The new Polygon here matches the destructor's deleting
	// of Dlist<Polygon> which will delete this Polygon.
	Polygon* polygon = new Polygon( attribs, vixCnt, mPolygonCnt );
	++mPolygonCnt;

	// Append to appropriate list.
	if ( attribs->IfTexture() )
		mPolygonDlistTextured->Append( polygon );
	else if ( attribs->IfTranslucent() )
		mPolygonDlistTranslucent->Append( polygon );
	else
		mPolygonDlistOpaque->Append( polygon );

	// Append all polygons to the total list.
	mPolygonDlistAll->Append( polygon );

	return polygon;
}

/*****************************************************************************
 * For speed, macro that continues a loop if a polygon isn't facing the viewpoint.
 *****************************************************************************/

//-----------------------------------------------------------------------------
// Polygons that are almost, but not quite, facing the viewpoint will still be rendered.
// The reason is that humans can create quads in Blender models that aren't exactly planar.
// Consequently, Blender will compute a normal vector that has a few degrees of error.
// So palomino allows a few degrees of error in the dot product, at the expense of overdraw.
//
// cos = u . v / |u| |v|
// cos = eyen . norm / |eyen| |norm|
// Since the normal vector is unit length (|norm| = 1.0), it can be factored out:
// cos = eyen . norm / |eyen|
// cos = (eyen . norm)^2 / |eyen|^2
//-----------------------------------------------------------------------------

//const fp DOT_PRODUCT_COS_ERROR = 0.08715;	// cos(85.0) = 0.08715
const fp DOT_PRODUCT_COS_ERROR = 0.06975;	// cos(86.0) = 0.06975
//const fp DOT_PRODUCT_COS_ERROR = 0.05233;	// cos(87.0) = 0.05233

#if SPEED
#define CONTINUE_IF_NOT_FACING_AND_NO_POLYGON_PLANAR_ERROR						\
		if ( dotProduct < 0 ) continue;
#else
#define CONTINUE_IF_NOT_FACING_AND_NO_POLYGON_PLANAR_ERROR						\
		if ( dotProduct < 0 )													\
		{																		\
			fp dotProductSquare = SQUARE( dotProduct );							\
			fp eyenSquare = SQUARE(eyen.x) + SQUARE(eyen.y) + SQUARE(eyen.z);	\
			if ( ABS(dotProductSquare / eyenSquare) > DOT_PRODUCT_COS_ERROR )	\
				continue;														\
		}
#endif

#define CONTINUE_UNLESS_POLYGON_FACING( POLYGON, NORMALS, WV )					\
{																				\
	if ( (POLYGON)->GetAttribs()->IfCull() )									\
	{																			\
		uint nix = (POLYGON)->GetNum();											\
		Vix vix = (NORMALS)[nix].mVixNormOrig;									\
		ASSERT2( vix < msDrawObj->GetVertexCnt() );                     		\
		static EyeVertex eyen;													\
		eyen.x = gEng.mEye.mCm[Ox] + (WV)[vix].x;								\
		eyen.y = gEng.mEye.mCm[Oy] + (WV)[vix].y;								\
		eyen.z = gEng.mEye.mCm[Oz] + (WV)[vix].z;								\
		fp dotProduct = DotProduct( (NORMALS)[nix].mNorm, eyen );				\
		CONTINUE_IF_NOT_FACING_AND_NO_POLYGON_PLANAR_ERROR						\
	}																			\
}

// Keep this as a reference.
#if 0
static inline bool
PolygonFacing( uint nix, const Normal* normals, const WorldVertex* worldVertexs )
{
	// The dot product is calculated in normal space.
	// The eye is translated to normal space as "eyen".
	Vix vix = normals[nix].mVixNormOrig;
	static EyeVertex eyen;
	eyen.x = gEng.mEye.mCm[Ox] + worldVertexs[vix].x;  // eye offsets are negative
	eyen.y = gEng.mEye.mCm[Oy] + worldVertexs[vix].y;
	eyen.z = gEng.mEye.mCm[Oz] + worldVertexs[vix].z;
	return DotProduct( normals[nix].mNorm, eyen ) < 0;  // yes, not >= 0, since eye offsets are negative
}
#endif

/*****************************************************************************
 * Render the list of polygons.
 *****************************************************************************/
void
PolygonList::Draw( ObjectMesh* obj ) const
{
ASSERT( mBits.mOptimized ); // Draw() depends on results from Optimize()

	// Object to be drawn.
	msDrawObj = obj;

	// Use faster gfxsys vertex array?
	// Craft shadows don't use vertex arrays as the eye vertexs are specially computed.
	if ( mBits.mVertexArray && mDrawParm.IfVertexArray() )
	{
		const EyeVertex* ev = msDrawObj->GetEyeVertexs();
		ASSERT( mVertexArray[0] || mVertexArray[1] );
		if ( mVertexArray[0] != NULL ) DrawVertexArray( mVertexArray[0], ev );
		if ( mVertexArray[1] != NULL ) DrawVertexArray( mVertexArray[1], ev );
		return;
	}

	// Eye coordinates may or may not have been calculated.
	sEyeVertexs = const_cast<EyeVertex*>( mDrawParm.GetEyeVertexs() );
	if ( sEyeVertexs == NULL )
		sEyeVertexs = const_cast<EyeVertex*>( msDrawObj->GetEyeVertexs() );

	if ( mBits.mAnyOpaque )
		DrawOpaque( mPolygonDlistOpaque );

	if ( mBits.mAnyTranslucent )
		DrawTranslucent();

	if ( mBits.mAnyTextured )
	{
		// Actually draw textured polygons as opaque if LOD is low.
		if ( gEng.mView.IfTexturing() && mDrawParm.IfTexture() )
			DrawTextured();
		else
			DrawOpaque( mPolygonDlistTextured );
	}
}

/*****************************************************************************
 * Draw with specified parameters.
 *****************************************************************************/
void
PolygonList::Draw( ObjectMesh* obj, const DrawParm& drawParm ) const
{
	// Temporarily change draw parameters (mDrawParm).
	DrawParm saved = mDrawParm;		// save
	mDrawParm      = drawParm;		// modify
	Draw( obj );					// Draw() is parameterized by mDrawParm
	mDrawParm	   = saved;			// restore
}

/*****************************************************************************
 * Subroutine to render a gfxsys vertex array.
 * Restrictions intrinsically due to vertex array:
 * - all polygons must be opaque or share the same texture (not mixed)
 * - all polygons must be triangles or quads (not mixed)
 *****************************************************************************/
void
PolygonList::DrawVertexArray( VertexArray* const va, const EyeVertex* const ev ) const
{
	GfxDriverDrawVertexArray( va, ev, mDrawParm );
}

/*****************************************************************************
 * Subroutine to render a list of opaque polygons.
 *****************************************************************************/
void
PolygonList::DrawOpaque( Dlist<Polygon>* dlist ) const
{
	const WorldVertex* wv = msDrawObj->GetWorldVertexs();
	const Normal* normals = msDrawObj->GetWorldNormals();
	bool alphablend	      = mDrawParm.IfAlphablend();
	bool antialias		  = mDrawParm.IfAntialias();
	bool cull			  = mDrawParm.IfCull();
	const RGBA* rgbaAll   = mDrawParm.GetRgba(); // maybe NULL

	if ( UX(rgbaAll != NULL) ) GFX_RGBA( *rgbaAll );
	if ( UX(mBits.mAnyWireframe) ) GFX_LINE_WIDTH( 1 );

	if ( alphablend ) GFX_BEGIN_ALPHA_BLEND();
	GFX_BEGIN_ANTIALIAS_LOOP( antialias )
	{
		if ( mBits.mSameVixCnt ) GFX_BEGIN( sGpTable[mBits.mSameVixCnt] );

		// For each polygon.
		uint polygonNum = 0;
		for ( const Dlink<Polygon>* dlink = dlist->ForStart();
	          dlist->ForTest(dlink);
	          dlist->ForNext(dlink), ++polygonNum )
		{
			const Polygon* const polygon = dlink->mObj;
			CHECK_TYPESIG( polygon, TYPESIG_POLYGON );

			// Cull polygon (skip it if it isn't facing the viewpoint).
			if ( cull ) // cull overrides Polygon bit
			{
				CONTINUE_UNLESS_POLYGON_FACING( polygon, normals, wv );
			}
			const PolygonAttribs* const attribs = polygon->GetAttribs();
			CHECK_TYPESIG( attribs, TYPESIG_POLYGON_ATTRIBS );

			// Draw this polygon.
			const uint       vixCnt = polygon->GetVixCnt();
			const Vix* const vixArr = polygon->GetVixArr(); 
			if ( rgbaAll == NULL ) GFX_RGBA( attribs->GetRgba() );
			if ( ! mBits.mSameVixCnt ) GFX_BEGIN( attribs->IfWireframe() ? GP_LINE_LOOP : sGpTable[vixCnt] );
			{
				// For each vertex.
				ASSERT( vixCnt > 0 && vixCnt <= MAX_VERTEXS );
				for ( uint i = 0; i < vixCnt; ++i )
				{
					const uint vix = vixArr[i];
					GFX_VERTEXV( &sEyeVertexs[vix] );
				}
			}
			if ( ! mBits.mSameVixCnt ) GFX_END();
		}

		if ( mBits.mSameVixCnt ) GFX_END();
	}
	GFX_END_ANTIALIAS_LOOP
	if ( alphablend ) GFX_END_ALPHA_BLEND();
}

/*****************************************************************************
 * Subroutine to render the list of textured polygons.
 *****************************************************************************/
void
PolygonList::DrawTextured( void ) const
{
	const WorldVertex* wv      = msDrawObj->GetWorldVertexs();
	const Normal*      normals = msDrawObj->GetWorldNormals();
	bool doTextureSingle       = ! mBits.mTexturesDiffer;
	bool doTextureMultiple     =   mBits.mTexturesDiffer;
	bool cull				   = mDrawParm.IfCull();
	const RGBA* rgbaAll        = mDrawParm.GetRgba(); // maybe NULL

	if ( UX(rgbaAll != NULL) ) GFX_RGBA( *rgbaAll );

#if DEBUG == 2
	static string prevObjName;
	if ( mBits.mSameVixCnt && prevObjName != msDrawObj->GetName() )
	{
		*gStreamDebug << "DrawTextured(): same vertex count for all polygons in class %s \n"
                      << msDrawObj->GetName().c_str();
		prevObjName = msDrawObj->GetName();
	}
#endif

	// Avoid switching textures if PolygonList has only one.
	if ( doTextureSingle ) mTextureSingle->Begin();  // yes, texture arg not passed to GFX_BEGIN()
	if ( mBits.mSameVixCnt ) GFX_BEGIN( sGpTable[mBits.mSameVixCnt] );

	// For each polygon.
	uint polygonNum = 0;
	for ( const Dlink<Polygon>* dlink = mPolygonDlistTextured->ForStart();
          mPolygonDlistTextured->ForTest(dlink);
          mPolygonDlistTextured->ForNext(dlink), ++polygonNum )
	{
		const Polygon* const polygon = dlink->mObj;
		CHECK_TYPESIG( polygon, TYPESIG_POLYGON );

		// Cull polygon (skip it if it isn't facing the viewpoint).
		if ( cull ) // cull overrides Polygon bit
		{
			CONTINUE_UNLESS_POLYGON_FACING( polygon, normals, wv );
		}

		const PolygonAttribs* const attribs = polygon->GetAttribs();
		CHECK_TYPESIG( attribs, TYPESIG_POLYGON_ATTRIBS );

		// If multiple textures (different textures for different polygons).
		TexturePtr texturePer = NULL;
		if ( doTextureMultiple )
		{
			texturePer = attribs->GetTexture();
			if ( texturePer != NULL ) texturePer->Begin();
		}

		// Draw this polygon.
		const uint       vixCnt = polygon->GetVixCnt();
		const Vix* const vixArr = polygon->GetVixArr(); 
		if ( rgbaAll == NULL ) GFX_RGBA( attribs->GetRgba() );
		if ( ! mBits.mSameVixCnt ) GFX_BEGIN( sGpTable[vixCnt] );
		{
			// For each vertex.
			ASSERT( vixCnt > 0 && vixCnt <= MAX_VERTEXS );
			for ( uint i = 0; i < vixCnt; ++i )
			{
				GFX_MAP_TEXTURE_2D( *attribs->GetTexCoord(i) );
				const uint vix = vixArr[i];
				GFX_VERTEXV( &sEyeVertexs[vix] );
			}
		}
		if ( ! mBits.mSameVixCnt ) GFX_END();

		// If multiple textures and this polygon has a texture.
		if ( texturePer != NULL ) texturePer->End();
	}

	if ( mBits.mSameVixCnt ) GFX_END();
	if ( doTextureSingle ) mTextureSingle->End();
}

/*****************************************************************************
 * Subroutine to render the list of translucent polygons.
 *****************************************************************************/
void
PolygonList::DrawTranslucent( void ) const
{
	GFX_BEGIN_ALPHA_BLEND( GP_SRC_ALPHA, GP_ONE_MINUS_SRC_ALPHA );
	static const RGBA rgbaTranslucent( 0.4, 0.4, 0.45, 0.45 );
	GFX_RGBA( rgbaTranslucent );
	if ( mBits.mSameVixCnt ) GFX_BEGIN( sGpTable[mBits.mSameVixCnt] );

	// For each polygon.
	for ( const Dlink<Polygon>* dlink = mPolygonDlistTranslucent->ForStart();
          mPolygonDlistTranslucent->ForTest(dlink);
          mPolygonDlistTranslucent->ForNext(dlink) )
	{
		// Draw only translucent polygons in this pass.
		const Polygon* const polygon = dlink->mObj;
		const uint       vixCnt = polygon->GetVixCnt();
		const Vix* const vixArr = polygon->GetVixArr(); 
		if ( ! mBits.mSameVixCnt ) GFX_BEGIN( sGpTable[vixCnt] );
		{
			// For each vertex.
			ASSERT( vixCnt > 0 && vixCnt <= MAX_VERTEXS );
			for ( uint i = 0; i < vixCnt; ++i )
			{
				uint vix = vixArr[i];
				GFX_VERTEXV( &sEyeVertexs[vix] );
			}
		}
		if ( ! mBits.mSameVixCnt ) GFX_END();
	}
	if ( mBits.mSameVixCnt ) GFX_END();
	GFX_END_ALPHA_BLEND();
}

/*****************************************************************************
 * For debug/stats.
 *****************************************************************************/
#if DEBUG || STATS
uint
DebugSharedPolygonAttribsCnt( void )
{
	return SharedValFactory<PolygonAttribs>::GetInstance()->Size();
}
#endif
