/*
===========================================================================
maya2q3 - export .md3 files from maya
Copyright (C) 2005 HermitWorks Entertainment Corporation

This program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License
as published by the Free Software Foundation; either version 2
of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
===========================================================================
*/

#include "common.h"

namespace md3
{                
   
struct VertID
{
	size_t mesh;
	unsigned int vert;
	int uv;
	int norm;

	bool operator == ( const VertID &other ) { return mesh == other.mesh && vert == other.vert && uv == other.uv && norm == other.norm; }
};

//temporary storage for all of the mesh data
struct Surface
{
	q3::qname	name;
	q3::qname	shader;
	size_t		numVertsPerFrame;

	//stores the vertex data
	//tangent, binormal invalid until after AddExtendedData
	//uvs only valid on first numVertsPerFrame entries
	std::vector< nv::MeshMender::Vertex > vertices;
	std::vector< VertID > ids;
	std::vector< size_t > reps;

	std::vector< unsigned int > indices;
};

#define Epsilon 0.0001f
#define Equal( a, b, c ) ( fabsf( a.x - b.x ) <= c && fabsf( a.y - b.y ) <= c && fabsf( a.z - b.z ) <= c )

static size_t FindVertex( Surface &surface, const VertID &id )
{
	for( size_t i = 0; i < surface.ids.size(); i++ )
		if( surface.ids[i] == id )
			return i;

	return (size_t)~0;
}

static Surface& GetSurface( std::vector< Surface > &surfaceList, const q3::qname groupName, const q3::qname matName )
{
    for( size_t i = 0; i < surfaceList.size(); i++ )
	{
		if( surfaceList[ i ].name == groupName )
			return surfaceList[ i ];
	}

	Surface newSurf;
	newSurf.name = groupName;
	newSurf.shader = matName;
	newSurf.numVertsPerFrame = 0;

	surfaceList.push_back( newSurf );
	return surfaceList[ surfaceList.size() - 1 ];
}

struct CachedMeshData
{
	MDagPath path;
	MFnMesh fn;

	MFloatPointArray points;
	MFloatVectorArray normals;

	MFloatArray tus, tvs;

#if MAYA_API_VERSION >= 700
	MFloatVectorArray tangents, binormals;
#endif

	void Update( MDGContext &ctx, bool extended )
	{
		MFnDependencyNode depNode( path.node() );

		MPlug meshPlug = depNode.findPlug( "outMesh", true );
		
		MObject meshData;
		meshPlug.getValue( meshData, ctx );
				
		//fn is object-space only
		fn.setObject( meshData );
		
		//get the transform
		MPlug matPlug = depNode.findPlug( "worldMatrix", true )
			.elementByLogicalIndex( path.isInstanced() ? path.instanceNumber() : 0 );

		MObject matData;
		matPlug.getValue( matData, ctx );
		MFnMatrixData matFn( matData );

		MFloatMatrix mat( matFn.matrix().matrix );

		fn.getPoints( points, MSpace::kObject );
		fn.getNormals( normals, MSpace::kObject );
		fn.getUVs( tus, tvs );
		
		//convert points to world space
		for( uint c = points.length(); c--; )
			points[c] *= mat;
		for( uint c = normals.length(); c--; )
			normals[c] *= mat;

#if MAYA_API_VERSION >= 700
		if( extended )
		{
			fn.getTangents( tangents, MSpace::kObject );
			fn.getBinormals( binormals, MSpace::kObject );

			//convert points to world space
			for( uint c = tangents.length(); c--; )
				tangents[c] *= mat;
			for( uint c = binormals.length(); c--; )
				binormals[c] *= mat;
		}
#else
		//shut up unreferenced param warning
		extended = extended;
#endif

		//attach back to the scene dag path to get at
		//components and materials
		fn.setObject( path );
	}

	nv::MeshMender::Vertex GrabVert( const VertID &vid, float unitScale, bool extended )
	{
		const MFloatPoint &pos = points[vid.vert];
		const MVector &norm = normals[vid.norm];
		float tu = (vid.uv >= 0 && vid.uv < (int)tus.length()) ? tus[vid.uv] : 0;
		float tv = (vid.uv >= 0 && vid.uv < (int)tvs.length()) ? tvs[vid.uv] : 0;

		nv::MeshMender::Vertex ret;
		
		ret.pos = dx::D3DXVECTOR3( q3::MayaVecToQ3( pos ) * unitScale );
		ret.normal = dx::D3DXVECTOR3( q3::MayaVecToQ3( norm ) );
		ret.s = tu;
		ret.t = 1.0F - tv;

#if MAYA_API_VERSION >= 700
		if( extended )
		{
			ret.tangent = dx::D3DXVECTOR3( q3::MayaVecToQ3( tangents[vid.norm] ) );
			ret.binormal = dx::D3DXVECTOR3( q3::MayaVecToQ3( binormals[vid.norm] ) );
		}
#else
		//shut up unreferenced param warning
		extended = extended;
#endif

		return ret;
	}
};

static q3::md3Tag_t DagToTag( const MDagPath &path, MDGContext &ctx, const float scaleFactor )
{
	MFnDependencyNode depNode( path.node() );
	MPlug matPlug = depNode.findPlug( "worldMatrix", true )
		.elementByLogicalIndex( path.isInstanced() ? path.instanceNumber() : 0 );
	MObject matData;
	matPlug.getValue( matData, ctx );
	MFnMatrixData matFn( matData );
	    
	q3::affine_t mtx = q3::MayaMatrixToQ3( matFn.matrix() );

	q3::md3Tag_t ret;

	ret.origin = q3::MayaVecToQ3( mtx.origin ) * scaleFactor;

	for( uint i = 0; i < 3; i++ )
		ret.axis[i] = q3::MayaVecToQ3( normalize( mtx.axis[i] ) );
					
	ret.name = q3::GetTagName( path ).asChar();

	return ret;
}

static size_t CollectSurfacesAndTags( const MDagPathArray &mayaMeshes, const MDagPathArray &mayaTags,
							  std::vector< Surface > &surfaces, std::vector< q3::md3Tag_t > &tags, bool extended )
{
	surfaces.clear();
	tags.clear();

	MayaAnimIt animIter;
	size_t numFrames = animIter.frameCount();

	MDGContext &ctx = MDGContext::fsNormal;
                   
	const float unitScale = 1.0F;

	CachedMeshData *cachedMeshes = new CachedMeshData[ mayaMeshes.length() ];

	//this takes care of adding a frame's worth of data to the surfaces list
	//note, the first frame must look **exactly** like this, then, before frame
	//2 goes in each surface must have its vertex array resized to accomodate
	//all vertices which will follow, after this the vertex ids are used to scan
	//in each frame's vertices (without going through all the BS of UVs, triangulating, etc)
	for( size_t meshIdx = 0; meshIdx < mayaMeshes.length(); meshIdx++ )
	{
		MDagPath path = mayaMeshes[ meshIdx ];	

		int instanceNum = 0;
		if( path.isInstanced() )
			instanceNum = path.instanceNumber();

		CachedMeshData &mesh = cachedMeshes[ meshIdx ];
		mesh.path = path; //update will set up the fn object

		mesh.Update( ctx, extended );

		MObjectArray sets, components;
		mesh.fn.getConnectedSetsAndMembers( instanceNum, sets, components, true );
		
		size_t setCount = sets.length();
		for( size_t i = 0; i < setCount; i++ )
		{
			MStatus status;
			
			if( setCount > 1 )
			{
				//multi-component objects may contain a "special" set
				//that holds all of the geometry in the mesh, ignore that
				//set when exporting

				MFnComponent comp( components[ i ], &status );
				if( status != MS::kSuccess )
					continue;

				if( comp.elementCount() == 0 )
					//the offending set flagged by having an empty component
					//that corresponds to it
					continue;
			}

			MItMeshPolygon polyIter( path, components[ i ], &status );

			if( status != MS::kSuccess )
				//not a poly set
				continue;
		
			MFnSet set( sets[ i ] );

			q3::qname shaderName = q3::GetShaderSetName( set.object() );
			if( shaderName == "lambert1" )
				//leaving something in the default shader group is akin to
				//calling it a "don't export" object...
				continue;

			Surface &surf = GetSurface( surfaces, set.name().asChar(), shaderName );

			for( ; !polyIter.isDone(); polyIter.next() )
			{  
				MPointArray dummy;
				MIntArray faceVerts, faceNorms, triVerts;

				polyIter.getVertices( faceVerts );
				MIntArray md3Verts( polyIter.polygonVertexCount() );

				mesh.fn.getFaceNormalIds( polyIter.index(), faceNorms );

				for( size_t i = 0; i < md3Verts.length(); i++ )
				{
					VertID vid;

					vid.mesh = meshIdx;
					vid.vert = faceVerts[i];
					vid.norm = faceNorms[i];
					mesh.fn.getPolygonUVid( polyIter.index(), i, vid.uv );

					size_t vidx = FindVertex( surf, vid );

					if( vidx == (size_t)~0 )
					{
						surf.vertices.push_back( mesh.GrabVert( vid, unitScale, extended ) );
						surf.ids.push_back( vid );

						vidx = surf.vertices.size() - 1;
					}

					md3Verts[i] = vidx;
				}

				polyIter.getTriangles( dummy, triVerts, MSpace::kObject );
				
				//changing the coordinate system effectively flipped our triangles
				//inside out, reverse the windings to compensate and undo the flip
				size_t numTriangles = triVerts.length() / 3;
				for( size_t i = 0; i < numTriangles; i++ )
				{
					for( int j = 2; j >= 0; j-- )
					{
						size_t t = i * 3 + j;

						for( size_t k = 0; k < faceVerts.length(); k++ )
							if( triVerts[ t ] == faceVerts[ k ] )
							{
								surf.indices.push_back( md3Verts[ k ] );
								break;
							}
					}
				}
			}
		}
	}

	for( size_t i = 0; i < surfaces.size(); i++ )
	{
		Surface &s = surfaces[ i ];
		s.numVertsPerFrame = s.vertices.size();

		s.vertices.resize( s.numVertsPerFrame * numFrames );
	}	

	//read in frame 1's tags
	for( size_t i = 0; i < mayaTags.length(); i++ )
		tags.push_back( DagToTag( mayaTags[ i ], ctx, unitScale ) );

	for( size_t f = 1; f < numFrames; f++ )
	{
		//add in the rest of the frames
		animIter.next();
		MDGContext &ctx = MDGContext::fsNormal;

		for( size_t i = 0; i < mayaMeshes.length(); i++ )
			cachedMeshes[i].Update( ctx, extended );

		//go through each surface
		for( size_t i = 0; i < surfaces.size(); i++ )
		{
			Surface &s = surfaces[ i ];

			//for every vertex in the base frame, get the corresponding
			//vertex for the current frame (set up above)
			const size_t fb = s.numVertsPerFrame * f;
			for( size_t i = 0; i < s.numVertsPerFrame; i++ )
			{
				const VertID &vid = s.ids[i];

				s.vertices[ fb + i ] = cachedMeshes[vid.mesh].GrabVert( vid, unitScale, extended );
			}
		}

		//read in frame f's tags
		for( size_t i = 0; i < mayaTags.length(); i++ )
			tags.push_back( DagToTag( mayaTags[ i ], ctx, unitScale ) );
	}

	delete [] cachedMeshes;

	return numFrames;
}

#if MAYA_API_VERSION < 700
void AddExtendedData( std::vector< Surface > &surfaces, size_t numFrames )
{
	demand( numFrames == 1, "don't support anims yet" );

	//this can't do anims because NvMeshMender may reorder the geometry
	//depending on the mesh topology - we can't have this since the MD3
	//format demands that the vertex layout remain the same...

	//this isn't even used in maya 7

	for( size_t i = 0; i < surfaces.size(); i++ )
	{
		Surface &s = surfaces[ i ];
	
		std::vector< unsigned int > mapNewToOld;

		nv::MeshMender mender;
		mender.Mend( s.vertices, s.indices, mapNewToOld,
			0.0F, 0.0F, 0.0F, 1.0F, nv::MeshMender::DONT_CALCULATE_NORMALS,
			nv::MeshMender::RESPECT_SPLITS, nv::MeshMender::DONT_FIX_CYLINDRICAL );
	}
}
#endif

static void SplitLargeSurfaces( std::vector< Surface > &surfaces, size_t numFrames )
{
	const unsigned int INVALID_INDEX = (unsigned int)~0;
	const size_t maxVerts = ((q3::SHADER_MAX_VERTEXES < q3::MD3_MAX_VERTS) ?
		q3::SHADER_MAX_VERTEXES : q3::MD3_MAX_VERTS) - 3; //this value is per frame
	
	for( size_t i = 0; i < surfaces.size(); i++ )
	{
        const Surface &src = surfaces[ i ];

		if( src.numVertsPerFrame <= q3::SHADER_MAX_VERTEXES
			&& src.numVertsPerFrame <= q3::MD3_MAX_VERTS
			&& src.indices.size() <= q3::SHADER_MAX_INDEXES )
			//surface is not too big
			continue;

		//surface is too big, pull out a full surface,
		//throw the rest into a new surface on the end
		//of the list, subsequent iterations will catch
		//it if it is still too big for q3

		assert( src.indices.size() % 3 == 0, "wrong number of indices" );

		std::vector< unsigned int > vertMap;
		vertMap.resize( src.numVertsPerFrame, INVALID_INDEX );

		Surface sa, sb;

		sa.name = sb.name = src.name;
		sa.shader = sb.shader = src.shader;
		
		size_t srcIdx = 0;
        
		//move triangles into surface sa (the one that will fit) until it is full
		while( sa.indices.size() < q3::SHADER_MAX_INDEXES
			&& srcIdx < src.indices.size() && sa.vertices.size() < maxVerts )
			for( int c = 3; c--; )
			{
				unsigned int si = src.indices[ srcIdx++ ];
				unsigned int sm = vertMap[ si ];
				if( sm == INVALID_INDEX )
				{
					sa.vertices.push_back( src.vertices[ si ] );
					sm = sa.vertices.size() - 1;
					vertMap[ si ] = sm;
				}

				sa.indices.push_back( sm );
			}

		//move the vertices for the rest of the frames across as well
		sa.numVertsPerFrame = sa.vertices.size();
		sa.vertices.resize( sa.numVertsPerFrame * numFrames );

		for( size_t f = 1; f < numFrames; f++ )
		{
			//every vertex we remapped is now in group a,
			//also make copies for the other frame sets

			//get the base vertex in source and dest vertex lists
			size_t fbsrc = f * src.numVertsPerFrame;
			size_t fbsa = f * sa.numVertsPerFrame;

			for( size_t i = 0; i < vertMap.size(); i++ )
			{
				unsigned int j = vertMap[ i ];
				if( j != INVALID_INDEX )
					//vertex was remapped into the destination surface
					//move ith vertex in the frame to the jth position in the group
					sa.vertices[ fbsa + j ] = src.vertices[ fbsrc + i ];
			}
		}

		vertMap.clear();
		vertMap.resize( src.numVertsPerFrame, INVALID_INDEX );

		while( srcIdx < src.indices.size() ) 
			for( int c = 3; c--; )
			{
				unsigned int si = src.indices[ srcIdx++ ];
				unsigned int sm = vertMap[ si ];
				if( sm == INVALID_INDEX )
				{
					sb.vertices.push_back( src.vertices[ si ] );
					sm = sb.vertices.size() - 1;
					vertMap[ si ] = sm;
				}

				sb.indices.push_back( sm );
			}

		//move the vertices for the rest of the frames across as well
		sb.numVertsPerFrame = sb.vertices.size();
		sb.vertices.resize( sb.numVertsPerFrame * numFrames );

		for( size_t f = 1; f < numFrames; f++ )
		{
			//every vertex we remapped is now in group a,
			//also make copies for the other frame sets

			//get the base vertex in source and dest vertex lists
			size_t fbsrc = f * src.numVertsPerFrame;
			size_t fbsb = f * sb.numVertsPerFrame;

			for( size_t i = 0; i < vertMap.size(); i++ )
			{
				unsigned int j = vertMap[ i ];
				if( j != INVALID_INDEX )
					//vertex was remapped into the destination surface
					//move ith vertex in the frame to the jth position in the group
					sb.vertices[ fbsb + j ] = src.vertices[ fbsrc + i ];
			}
		}

		surfaces[ i ] = sa;
		surfaces.push_back( sb );
	}
}

static void OptimizeSurfaces( std::vector< Surface > &surfaces, size_t numFrames )
{
	//make strips
    for( size_t i = 0; i < surfaces.size(); i++ )
	{
		Surface &s = surfaces[ i ];
		//the mesh mender took all the indices in 32-bit format,
		//but the mender wants them in 16-bit, copy out, copy back
		//md3 wants them in 32-bit as well

		unsigned short *indices = new unsigned short[ s.indices.size() ];
		for( size_t i = 0; i < s.indices.size(); i++ )
			indices[ i ] = (unsigned short)s.indices[ i ];

		nv::PrimitiveGroup *pgStrip, *pgRemap;
		unsigned short numPrimGroups;

		nv::DisableRestart();			//nv only feature, don't want it
		nv::SetStitchStrips( true );	//minimize the number of groups
		nv::SetListsOnly( true );		//we want to get triangles out of this
																			  
		nv::GenerateStrips( indices, s.indices.size(), &pgStrip, &numPrimGroups );
		nv::RemapIndices( pgStrip, (unsigned short)numPrimGroups, (unsigned short)s.vertices.size(), &pgRemap );

		//copy the remapped indices back into our surface
		s.indices.clear();

		std::vector< nv::MeshMender::Vertex > newVerts;
		std::vector< bool > newVertSet;

        newVerts.resize( s.vertices.size() );
		newVertSet.resize( s.vertices.size(), false );

		//we should only get one PrimitiveGroup out of the stripper and mender
		//but if we don't it's no big deal, since we're using tirangle lists we
		//can just append each list to the end of the indices array (no draw restarts)

		for( nv::PrimitiveGroup *pg = pgStrip, *rpg = pgRemap; numPrimGroups--; pg++, rpg++ )
		{
			assert( pg->type == nv::PT_LIST, "nv stripper gave non-list" );
			assert( rpg->type == nv::PT_LIST, "nv remapper gave non-list" );

			for( size_t i = 0; i < pg->numIndices; i++ )
			{  
				unsigned int destIdx = rpg->indices[ i ];		//index of the vertex's optimal position

				if( !newVertSet[ destIdx ] )
				{
					unsigned int srcIdx = pg->indices[ i ];		//index in the original vertex array

					for( size_t f = 0; f < numFrames; f++ )
					{
						size_t baseVert = s.numVertsPerFrame * f;
						newVerts[ destIdx + baseVert ] = s.vertices[ srcIdx + baseVert ];
					}

					newVertSet[ destIdx ] = true;
				}

				s.indices.push_back( destIdx );
			}
		}

		delete[] pgStrip;
		delete[] pgRemap;
		delete[] indices;

		s.vertices = newVerts;
	}
}

static void MakePointReps( std::vector< Surface > &surfaces, size_t numFrames )
{            
	for( size_t i = 0; i < surfaces.size(); i++ )
	{
		Surface &s = surfaces[ i ];

		assert( s.numVertsPerFrame > 0, "empty surface?" );

		s.reps.clear();
		s.reps.resize( s.vertices.size(), 0 );

		for( size_t f = 0; f < numFrames; f++ )
		{
            size_t start = s.numVertsPerFrame * f;
			size_t end = start + s.numVertsPerFrame;

			for( size_t i = start + 1; i < end; i++ )
			{
				const dx::D3DXVECTOR3 &vi = s.vertices[ i ].pos;

				s.reps[ i ] = i - start; //point reps are relative to the start of the frame

				for( size_t j = i; j-- > start; )
					if( Equal( vi, s.vertices[ s.reps[ j ] ].pos, Epsilon ) )
					{          
						s.reps[ i ] = s.reps[ j ];
						break;
					}
			}
		}
	}
}

/*
This method computes a simple axis aligned bounding box and a bounding sphere for the model
at each frame of animation. The bounding sphere is computed using the method described in
Mathematics for 3D Game Programming & Computer Graphics, Second Edition by Eric Lengyel.
*/
static void GetFrameInfos( const std::vector< Surface > &surfaces, std::vector< q3::md3Frame_t > &frames, size_t numFrames )
{
	assert( surfaces.size() > 0, "can't get frame bounds: model has no surfaces" );

	frames.clear();
	frames.resize( numFrames );

	std::vector< bool > isVertUsed;

    for( size_t f = 0; f < numFrames; f++ )
	{
		q3::md3Frame_t &frame = frames[ f ];
		
		vec3 aaMin, aaMax;
		vec3 mean = vec3c( 0 );
		size_t numVerts = 0;

		aaMin = aaMax = vec3v( surfaces[0].vertices[surfaces[0].numVertsPerFrame * f].pos );

		for( size_t i = 0; i < surfaces.size(); i++ )
		{
			const Surface &s = surfaces[i];

			isVertUsed.clear();
			isVertUsed.resize( s.numVertsPerFrame, false );

			const size_t start = s.numVertsPerFrame * f;
			const size_t end = start + s.numVertsPerFrame;

			for( size_t i = start; i < end; i++ )
			{
				//since we're tracking a mean value as well
				//we only want each 3-space position to be
				//accounted for once, we use our point reps to
				//keep split vertices from skewing the results
				if( isVertUsed[ s.reps[i] ] )
					continue;

				isVertUsed[ s.reps[i] ] = true;

				//get the axis-aligned bounds
				//and the mean position (for the bounding sphere)
				const vec3 &v = vec3v( s.vertices[ i ].pos );
                   
				aaMin = min( aaMin, v );
				aaMax = max( aaMax, v );

				mean += v;
				numVerts++;
			}
		}

		//store the min and max vertices
		frame.bounds[0] = aaMin;
		frame.bounds[1] = aaMax;

		float invNumVerts = 1.0f / (float)numVerts;
		mean *= invNumVerts;        

		//set up for the covariance matrix
		//note, the matrix is symmetric so
		//c21 also represents c12, etc
		float c11 = 0;
		float c21 = 0, c22 = 0;
		float c31 = 0, c32 = 0, c33 = 0;

		for( size_t i = 0; i < surfaces.size(); i++ )
		{
			const Surface &s = surfaces[ i ];

			isVertUsed.clear();
			isVertUsed.resize( s.numVertsPerFrame, false );

			const size_t start = s.numVertsPerFrame * f;
			const size_t end = start + s.numVertsPerFrame;

			for( size_t i = start; i < end; i++ )
			{
				//again, we're dealing with a sum so we want
				//the same vertices with which we computed mean
				if( isVertUsed[s.reps[i]] )
					continue;

				isVertUsed[s.reps[i]] = true;

				//build the covariance matrix
				const vec3 d = vec3v( s.vertices[i].pos ) - mean;

				c11 += d[0] * d[0];
				c21 += d[0] * d[1]; c22 += d[1] * d[1];
				c31 += d[0] * d[2]; c32 += d[1] * d[2]; c33 += d[2] * d[2];
			}
		}

		c11 *= invNumVerts;
		c21 *= invNumVerts; c22 *= invNumVerts;
		c31 *= invNumVerts; c32 *= invNumVerts; c33 *= invNumVerts;

		//solve for the initial sphere center (should be close)
		vec3 r, s, t;
		float l[3];

		CalculateEigensystem3x3s( c11, c21, c22, c31, c32, c33, r, s, t, l );
		//get the real r vector (the one with the biggest eigenvalue)
		if( l[1] > l[0] )
		{
			if( l[2] > l[1] )
				r = t;
			else
				r = s;
		}
		else if( l[2] > l[0] )
			r = t;

		//normalize the principle axis (r)
		float len = length( r );
		assert( len > 0, "could not find principle axis" );
		r *= 1.0F / len;

		float mind, maxd; //reusing min and max vectors from above

		aaMin = aaMax = vec3v( surfaces[0].vertices[0].pos );
		mind = maxd = dot( r, aaMin );

		//get the sphere center
		for( size_t i = 0; i < surfaces.size(); i++ )
		{
			const Surface &s = surfaces[i];

			const size_t start = s.numVertsPerFrame * f;
			const size_t end = start + s.numVertsPerFrame;

			for( size_t i = start; i < end; i++ )
			{  
				const vec3 v = vec3v( s.vertices[i].pos );
				float d = dot( r, v );

				if( d < mind )
				{
					mind = d;
					aaMin = v;
				}
				else if( d > maxd )
				{
					maxd = d;
					aaMax = v;
				}
			}
		}

		//get the sphere center
		vec3 c = (aaMin + aaMax) * 0.5F;
		//get the radius, reuse min and max since they're dead now
		aaMin = c - aaMax;
		frame.radius = length( aaMin );

		//adjust the sphere to include outlying points
		for( size_t i = 0; i < surfaces.size(); i++ )
		{
			const Surface &s = surfaces[i];

			const size_t start = s.numVertsPerFrame * f;
			const size_t end = start + s.numVertsPerFrame;

			for( size_t i = start; i < end; i++ )
			{ 
				const vec3 v = vec3v( s.vertices[i].pos );
				r = v - c;
				float d = length( r );

				if( d <= frame.radius )
					//point already in sphere, good to go
					continue;

				//need to adjust the bounding
				//sphere to contain the old one
				//as well as the point v

				r *= 1.0F / d;

				//get a point g on the old sphere opposite the center from v
				vec3 g = c - r * frame.radius;

				//find the new center (half way between v and g)
				c = (v + g) * 0.5F;
				//and the new radius
				r = v - c;
				frame.radius = length( r );
			}
		}

		//save the center
		frame.localOrigin = c;
	}
}

static void WriteMD3( std::ostream &stm, const std::vector< Surface > &surfaces, const std::vector< q3::md3Frame_t > &frames,
			  const std::vector< q3::md3Tag_t > &tags, bool extended )
{
	BinaryWriter out( stm );

	q3::md3Header_t header;

	header.ident = q3::MD3_IDENT;
	header.version = q3::MD3_VERSION;
	//header.name is not needed for game
	header.flags = 0;
	header.numFrames = frames.size();
	header.numTags = tags.size() / frames.size();
	header.numSurfaces = surfaces.size();
	header.numSkins = 1;	
    
	std::vector<  q3::md3Surface_t > surfaceHeaders;
	surfaceHeaders.resize( surfaces.size() );

	//go through the file and come up with the file layout (offsets)
	size_t pos = sizeof( q3::md3Header_t ); //start after the header

	//write tags
	header.ofsTags = pos;
	pos += tags.size() * sizeof( q3::md3Tag_t );

	//write frames
	header.ofsFrames = pos;
	pos += frames.size() * sizeof( q3::md3Frame_t );

	//write surfaces
    header.ofsSurfaces = pos;
    for( size_t i = 0; i < surfaces.size(); i++ )
	{
		const Surface &s = surfaces[ i ];
		q3::md3Surface_t &sh = surfaceHeaders[ i ];

		sh.ident = q3::MD3_IDENT;
		sh.name = s.name;
		sh.flags = 0;
		sh.numFrames = frames.size();
		sh.numShaders = 1;
		sh.numVerts = s.vertices.size() / frames.size();
		sh.numTriangles = s.indices.size() / 3;
		
		size_t surfStart = pos;
		pos += sizeof( q3::md3Surface_t );

		//write the shader
		sh.ofsShaders = pos - surfStart;
		pos += sizeof( q3::md3Shader_t ) * sh.numShaders;

		//write the indices
		sh.ofsTriangles = pos - surfStart;
		pos += sizeof( q3::md3Triangle_t ) * sh.numTriangles;

		//write the uvs
		sh.ofsSt = pos - surfStart;
		pos += sizeof( q3::md3St_t ) * sh.numVerts;

		//write the geometry
		sh.ofsXyzNormals = pos - surfStart;
		pos += sizeof( q3::md3XyzNormal_t ) * s.vertices.size();

		if( extended )
			//write the extended geometry
			pos += sizeof( q3::md3TangentBasis_t ) * s.vertices.size();

		sh.ofsEnd = pos - surfStart;
	}

	//mark the file end
	header.ofsEnd = pos;

	out << header;

	for( size_t i = 0; i < tags.size(); i++ ) 
		out << tags[ i ];

	for( size_t i = 0; i < frames.size(); i++ )
		out << frames[ i ];

	for( size_t i = 0; i < surfaces.size(); i++ )
	{
		const Surface &s = surfaces[ i ];
		const q3::md3Surface_t &sh = surfaceHeaders[ i ];

		out << sh;
        
		//write the shader (should only be one at this point)
		assert( sh.numShaders == 1, "too many shaders in the md3" );
        out << s.shader;
		out.pad( sizeof( int ) ); //dummy value not used till run time

		for( size_t i = 0; i < s.indices.size(); i++ )
			out << (int)s.indices[ i ];

		for( size_t i = 0; i < s.numVertsPerFrame; i++ )
		{
			const nv::MeshMender::Vertex &v = s.vertices[ i ];

			out << v.s;
			out << v.t;
		}

		for( size_t i = 0; i < s.vertices.size(); i++ )
		{
			const nv::MeshMender::Vertex &v = s.vertices[ i ];

			//encode and emit each vertex

			q3::md3XyzNormal_t vert;

			vec3 n = normalize( vec3v( v.normal ) );

			/*
			the normal is stored in spherical polar coordinates, where we have:

				x = sin(a)cos(b)
				y = sin(a)sin(b)
				z = cos(a)

			r is ignored since it is 1
			*/

			float fa = acosf( n[2] );
			float fb = atan2f( -n[1], -n[0] ) + (float)M_PI;

			unsigned char a = (unsigned char)(fa * ((float)0xFF / ((float)M_PI * 2)));
			unsigned char b = (unsigned char)(fb * ((float)0xFF / ((float)M_PI * 2)));

			vert.normal = (b << 8) | a;

			vert.xyz = v.pos;

			out << vert;
		}

		if( extended )
			for( size_t i = 0; i < s.numVertsPerFrame; i++ )
			{
				const nv::MeshMender::Vertex &v = s.vertices[ i ];

				out << v.tangent;
				out << v.binormal;
			}
	}
}

static bool ExportFromMaya( std::ostream &out, const MDagPathArray &mayaMeshes, const MDagPathArray &mayaTags, bool extended )
{
	std::vector< Surface > surfaces;
	std::vector< q3::md3Tag_t > tags;
	size_t numFrames;

	//pull the secene info from maya
	numFrames = CollectSurfacesAndTags( mayaMeshes, mayaTags, surfaces, tags, extended );

	assert( numFrames != 0, "nothing to export" );
	assert( numFrames == 1 || !extended, "can't add extended data to animated objects" );

	if( surfaces.size() == 0 )
		fail( "nothing to export" );

	//we should now have all of our surfaces gathered together
	//we'll eventually need to collect the unique shader names
	//to build the shaders list

	//first we want to get things all nice and optimal

#if MAYA_API_VERSION < 700
	//maya 7 and higher provides this data for us, so we don't
	//have to use the limited NvMeshMender functionality
	if( extended )
		AddExtendedData( surfaces, numFrames );
#endif
		
	SplitLargeSurfaces( surfaces, numFrames );
	
	OptimizeSurfaces( surfaces, numFrames );
    	
	//convert the vertIDs into real (position only) point reps
	//GetFrameInfos will use the point reps to get better results
	MakePointReps( surfaces, numFrames );

	std::vector< q3::md3Frame_t > frames;
	GetFrameInfos( surfaces, frames, numFrames );

	//write the file
	WriteMD3( out, surfaces, frames, tags, extended );

	return true;
}

//=============================================================================
//
// File translator class - exposes the above to Maya!
//
//=============================================================================
class ExportMD3 : public MPxFileTranslator
{
	
public:
	ExportMD3( void ) { }
	virtual /* override */ ~ExportMD3( void ) { }
	
	static void* Creator() { return new ExportMD3; }

	virtual bool /* override */ haveWriteMethod () const { return true; }
	virtual bool /* override */ haveReadMethod () const { return false; }
	virtual MString /* override */ defaultExtension() const { return MString( "md3" ); }
	virtual MString /* override */ filter() const { return MString( "*.md3" ); }
	
	virtual MFileKind /* override */ identifyFile( const MFileObject &file, const char *buffer, short size ) const
	{
		const char * name = file.name().asChar();
		int nameLength = strlen( name );

		if( size >= 4 && *(int*)buffer == q3::MD3_IDENT )
			return kIsMyFileType;

		if( (nameLength > 4) && !strcasecmp( name + nameLength - 4, ".md3" ) )
			return kCouldBeMyFileType;

		return kNotMyFileType;
	}

protected:
	bool IsVisible( const MDagPath &dag )
	{
		MStatus status;

		MDagPath path = dag;
		path.extendToShape();

		while( path.pop() == MS::kSuccess )
		{
			MFnDependencyNode node( path.node() );
			MPlug p = node.findPlug( "visibility", true, &status );

			if( status != MStatus::kSuccess )
				continue;

			bool vis;
			status = p.getValue( vis );

			if( status != MStatus::kSuccess )
				return false;

			if( !vis )
				return false;
		}

		return true;
	}
		
	void CheckPath( MDagPath path, MDagPathArray &meshes, MDagPathArray &tags )
	{
		if( q3::DagIsTag( path ) )
			tags.append( path );

		if( path.apiType() == MFn::kTransform )
		{
			if( path.extendToShape() != MS::kSuccess )
				return;

			MFnDagNode nodeOp( path );
			if( nodeOp.isIntermediateObject() )
				return;

			if( !path.hasFn( MFn::kMesh ) )
				return;

			if( IsVisible( path ) )
				meshes.append( path );
		}
	}

public:
	virtual MStatus /* override */ writer( const MFileObject &filename, const MString & /* optionsString */, FileAccessMode mode )
	{   
		MDagPathArray meshes;
		MDagPathArray tags;
		
		switch( mode )
		{
		case kExportAccessMode:
			for( MItDag it( MItDag::kBreadthFirst ); !it.isDone(); it.next() )
			{
				MDagPath path;
				if( it.getPath( path ) != MS::kSuccess )
					continue;

				CheckPath( path, meshes, tags );
			}     
			break;

		case kExportActiveAccessMode:
			{
				MSelectionList sel;
				if( MGlobal::getActiveSelectionList( sel ) != MS::kSuccess )
				{
					MGlobal::displayError( MString( "Error, couldn't get selection list." ) );
					return MS::kFailure;
				}

				for( MItSelectionList it( sel ); !it.isDone(); it.next() )
				{
					MDagPath path;
					if( it.getDagPath( path ) != MS::kSuccess )
						continue;

					if( path.apiType() == MFn::kMesh )
						//CheckPath operates on the transform above the mesh
						path.pop();

					CheckPath( path, meshes, tags );
				}
			}
			break;

		default:
			MGlobal::displayError( MString( "Error: Unsupported export mode." ) );
			return MS::kInvalidParameter;
		}

		if( meshes.length() == 0 )
		{
			MGlobal::displayError( MString( "Nothing to export." ) );
			return MS::kFailure;
		}

		std::ofstream file;
		file.open( filename.fullName().asChar(), std::ios::out | std::ios::trunc | std::ios::binary );

		bool failed = false;
		try
		{
			md3::ExportFromMaya( file, meshes, tags, false );
		}
		catch( ... )
		{         
			failed = true;
		}

		file.close();

		if( failed )
		{
			warn( "failed to export, deleting file" );
			remove( filename.fullName().asChar() );
		}
		else
		{
			MGlobal::displayInfo( MString( "successfully wrote file: " ) + filename.fullName() );
		}

		return MS::kSuccess;
	}
};

void* (CDECL *g_translatorCreator)( void ) = &ExportMD3::Creator;
const char *g_translatorName = "exportMD3";

};