/******************************************************************************
	libx42make - skinned vertex animation library (exporter utilities)
	Copyright (C) 2007 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 "local.h"

namespace x42
{
namespace make
{

/*****
	Vertex
*/
bool Vertex::IsValid( void )
{
	uint numWeights = 0;
	for( uint i = 0; i < X42_WEIGHTS_PER_VERT; i++ )
	{
		if( wt[i] < 0 )
			return false;

		if( wt[i] != 0 )
			numWeights++;
	}

	//check for NaN's as well?

	return numWeights > 0;
}

/*****
	Bone
*/

const float Bone::AutoGenExtent = -2;
const float Bone::InheritTolVal = -2;

Bone::Bone( ModelData *owner )
	: owner( owner ),
	flags( BoneFlags::None ),
	animGroup( 0 ), staticAnim( false ),

	extent( AutoGenExtent ),
	
	posTol( InheritTolVal ),
	rotTol( InheritTolVal ),
	scaleTol( InheritTolVal ),

	pinPosTol( InheritTolVal ),
	pinRotTol( InheritTolVal ),
	pinScaleTol( InheritTolVal )
{
}

/*****
	GroupPrimitiveIterator
*/
GroupPrimitiveIterator::GroupPrimitiveIterator( const Group *group )
	: PrimitiveIterator< ushort >( group->primType,
	group->indices.size() ? &group->indices[0] : NULL, group->NumPrimitives() )
{
}

GroupPrimitiveIterator::GroupPrimitiveIterator( ConstGroupPtr group )
	: PrimitiveIterator< ushort >( group->primType,
	group->indices.size() ? &group->indices[0] : NULL, group->NumPrimitives() )
{
}

/*****
	Group
*/

const uint Group::InvalidTriangle = 0xFFFFFFFF;
const uint Group::InvalidInfluence = 0xFFFFFFFF;
const index Group::InvalidIndex = index_traits::max_val;

Group::Group( Lod *owner )
	: owner( owner ),
	primType( PrimType::TriangleList ),
	maxInfsPerVert( X42_WEIGHTS_PER_VERT )
{

}

ModelData* Group::GetModel( void ) { return owner->GetModel(); }
const ModelData* Group::GetModel( void ) const { return owner->GetModel(); }

void Group::DoRemapInfluences( const std::vector< uint > &infRemap )
{
	std::vector< uint > localRemap( infMap.size(), ModelData::InvalidInfluence );

	uint oInf = 0;
	for( uint iInf = 0; iInf < infMap.size(); iInf++ )
	{
		uint oldIdx = infMap[iInf];
		uint newIdx = infRemap[oldIdx];

		if( newIdx != ModelData::InvalidInfluence )
		{
			infMap[oInf] = newIdx;
			localRemap[iInf] = oInf;

			oInf++;
		}
		else
		{
			localRemap[iInf] = ModelData::InvalidInfluence;
		}
	}

	infMap.resize( oInf );

	//duplicates may have arrisen - collapse them

	oInf = 0;
	for( uint iInf = 0; iInf < infMap.size(); iInf++ )
	{
		uint iDup;
		for( iDup = iInf + 1; iDup < infMap.size(); iDup++ )
		{
			if( infMap[iInf] == infMap[iDup] )
				break;
		}

		if( iDup < infMap.size() )
		{
			//iInf has a duplicate later in the list, skip it (use the dup)
			//patch up the localRemap to account for this
			for( uint i = 0; i < localRemap.size(); i++ )
			{
				if( localRemap[i] == ModelData::InvalidInfluence )
					continue;

				if( localRemap[i] == iInf )
					localRemap[i] = iDup;

				if( localRemap[i] > iInf )
					localRemap[i]--;
			}

			//take the duplicate out of the list
			infMap.erase( infMap.begin() + iInf );
			iInf--;
			continue;
		}
	}

	ApplyLocalInfluenceRemap( localRemap );
}

void Group::ApplyLocalInfluenceRemap( const std::vector< uint > &localRemap )
{
	for( uint i = 0; i < verts.size(); i++ )
	{
		Vertex &v = verts[i];

		for( uint i = 0; i < X42_WEIGHTS_PER_VERT; i++ )
		{
			if( v.wt[i] == 0 )
				continue;

			uint newIdx = localRemap[v.idx[i]];

			if( newIdx == ModelData::InvalidInfluence )
			{
				v.idx[i] = 0;
				v.wt[i] = 0;
			}
			else
			{
				v.idx[i] = newIdx;
			}

			//sort and normalize later
		}
	}

	FixupWeights();
}

void Group::DoMergeInfluences( const std::vector< uint > &mergeMap )
{
	DoRemapInfluences( mergeMap );
}

void Group::DoCollapseStaticInfluences( void )
{
	ModelData *owner = GetModel();

	for( uint i = 0; i < infMap.size(); i++ )
	{
		if( owner->influences[infMap[i]].bone )
			return;
	}

	std::vector< affine > mats( infMap.size() );
	for( uint i = 0; i < infMap.size(); i++ )
		mats[i] = owner->influences[infMap[i]].objToBone;

	uint identityIdx = uint_traits::max_val;
	for( uint i = 0; i < owner->influences.size(); i++ )
	{
		if( !owner->influences[i].bone &&
			owner->influences[i].objToBone == affinei() )
		{
			identityIdx = i;
			break;
		}
	}

	if( identityIdx == uint_traits::max_val )
	{
		Influence newInf;

		newInf.objToBone = affinei();
		newInf.useCount = 0;

		owner->influences.push_back( newInf );

		identityIdx = (uint)owner->influences.size() - 1;
	}

	infMap.clear();
	infMap.push_back( identityIdx );

	for( uint i = 0; i < verts.size(); i++ )
	{
		Vertex &v = verts[i];

		affine m = affinez();
		for( uint i = 0; i < X42_WEIGHTS_PER_VERT; i++ )
			m += mats[v.idx[i]] * v.wt[i];

		v.pos = m.mul_point( v.pos );
		v.tan = normalize( m.mul_vec( v.tan ) );
		v.bin = normalize( m.mul_vec( v.bin ) );
				
		v.norm = normalize( inverse( transpose( m ) ).mul_vec( v.norm ) );

		v.idx[0] = 0;
		v.wt[0] = 1.0F;

		for( uint i = 1; i < X42_WEIGHTS_PER_VERT; i++ )
		{
			v.idx[i] = 0;
			v.wt[i] = 0;
		}
	}
}

/*****
	Lod
*/

Lod::~Lod( void )
{

}

GroupPtr Lod::CreateGroup( void )
{
	GroupPtr ret = InternalCreateGroup();
	groups.push_back( ret );
	return ret;
}

GroupPtr Lod::InternalCreateGroup( void )
{
	return GroupPtr( new Group( this ) );
}

/*****
	ModelData
*/

const uint ModelData::InvalidInfluence = util::integer_traits< uint >::max_val;
const uint ModelData::InvalidBone = util::integer_traits< uint >::max_val;

ModelData::ModelData( void ) :
	numFrames( 0 ), boundingSphere( spherec( vec3c( 0 ), 0 ) ),
	boundingBox( aabbc( vec3c( 0 ), vec3c( 0 ) ) )
{
	SetDefaultTolerances();
}

ModelData::~ModelData( void )
{

}

BonePtr ModelData::CreateBone( void )
{
	BonePtr ret( new Bone( this ) );

	ret->index = (uint)bones.size();
	bones.push_back( ret );

	return ret;
}

LodPtr ModelData::GetLod( uint lod )
{
	for( std::vector< LodPtr >::iterator it = lods.begin();
		it < lods.end(); it++ )
	{
		if( (*it)->lod == lod )
			return (*it);

		if( (*it)->lod > lod )
		{
			LodPtr newLod( new Lod( this, lod ) );
			lods.insert( it, newLod );
			return newLod;
		}
	}

	LodPtr newLod( new Lod( this, lod ) );
	lods.push_back( newLod );
	return newLod;
}

/**
	Bone and Influence culling and sorting.
*/

void ModelData::SortBones( void )
{
	/*
		Bones must go out in order such that:
			1.	Each bone's parent index is smaller than the bone's index, with
				bone zero parented to the MODEL_BONE (identity matrix).
			2.	Each bone's animation group is the same as or greater than the
				prior bone's animation group.

		The code assumes that the incoming parenting data forms a valid forest.
	*/

	std::vector< uint > breadthFirst;

	/*
		We start by doing a breadth-first traversal of the bone parenting tree.
		This is used to enforce sort order condition 1.
	*/
	for( uint i = 0; i < bones.size(); i++ )
		if( !bones[i]->parent )
			breadthFirst.push_back( i );

	for( uint i = 0; i < breadthFirst.size(); i++ )
	{
		for( uint j = 0; j < bones.size(); j++ )
		{
			if( bones[j]->parent && bones[j]->parent->index == breadthFirst[i] )
				breadthFirst.push_back( j );
		}
	}

	demand( breadthFirst.size() == bones.size(), "Some bones have invalid parent indices." );

	std::vector< uint > boneIndices;

	/*
		Build a map (boneIndices) from target bone index to source bone index.

		Basically we pull bones out of the breadth-first traversal one animation
		group at a time to enforce sort condition 2. Since we assume the incoming
		data is valid this can't break sort condition 1.
	*/
	uint currGroup = 0;
	while( boneIndices.size() < bones.size() )
	{
		uint nextGroup = uint_traits::max_val;

		for( uint i = 0; i < breadthFirst.size(); i++ )
		{
			uint bIdx = breadthFirst[i];
			const Bone &b = *bones[bIdx];

			if( b.animGroup == currGroup )
				boneIndices.push_back( bIdx );

			if( b.animGroup > currGroup && b.animGroup < nextGroup )
				nextGroup = b.animGroup;
		}

		currGroup = nextGroup;
	}

	/*
		Invert the map to go from old index to new index.
	*/
	std::vector< uint > boneRemap( boneIndices.size() );
	for( uint i = 0; i < boneRemap.size(); i++ )
	{
		for( uint j = 0; j < boneIndices.size(); j++ )
		{
			if( i == boneIndices[j] )
			{
				boneRemap[i] = j;
				break;
			}
		}
	}

	DoRemapBones( boneRemap );
}

void ModelData::RemoveDeadInfluences( void )
{
	std::vector< uint > infRemap( influences.size() );

	CountInfluenceUses();

	uint infIdx = 0;
	for( uint i = 0; i < influences.size(); i++ )
	{
		if( influences[i].useCount > 0 )
			infRemap[i] = infIdx++;
		else
			infRemap[i] = InvalidInfluence;
	}

	DoRemapInfluences( infRemap );
}

void ModelData::RemoveInfluences( std::vector< uint > infsToKill )
{
	uint infIdx = 0;

	uint killIdx = 0;
	std::sort( infsToKill.begin(), infsToKill.end() );

	std::vector< uint > infRemap( influences.size() );

	for( uint i = 0; i < influences.size(); i++ )
	{
		if( killIdx < infsToKill.size() && i == infsToKill[killIdx] )
		{
			infRemap[i] = InvalidInfluence;
			killIdx++;
		}
		else
			infRemap[i] = infIdx++;
	}

	DoRemapInfluences( infRemap );
}

void ModelData::RemoveDeadBones( void )
{
	std::vector< bool > boneUsed( bones.size(), false );
	MarkUsedBones( boneUsed );

	uint boneIdx = 0;
	std::vector< uint > boneRemap( bones.size() );
	for( uint i = 0; i < bones.size(); i++ )
		if( boneUsed[i] )
			boneRemap[i] = boneIdx++;
		else
			boneRemap[i] = InvalidBone;

	DoRemapBones( boneRemap );
}

void ModelData::MarkUsedBones( std::vector< bool > &usedFlags )
{
	for( uint i = 0; i < influences.size(); i++ )
	{
		Influence *inf = &influences[i];

		if( inf->bone )
			usedFlags[inf->bone->index] = true;
	}

	for( uint i = 0; i < tags.size(); i++ )
	{
		Tag *tag = &tags[i];

		if( tag->bone )
			usedFlags[tag->bone->index] = true;
	}

	//don't assume bones are sorted (?)

	uint numMarked;
	do
	{
		numMarked = 0;

		for( uint i = 0; i < bones.size(); i++ )
		{
			if( !usedFlags[i] )
				continue;

			ConstBonePtr bone = bones[i];

			if( bone->parent && !usedFlags[bone->parent->index] )
			{
				usedFlags[bone->parent->index] = true;
				numMarked++;
			}
		}
	} while( numMarked );
}

void ModelData::DoRemapBones( const std::vector< uint > &boneRemap )
{
	uint numRem = 0;

	/*
		Reorder the bones.
	*/
	std::vector< BonePtr > tmp = bones;
	for( uint i = 0; i < bones.size(); i++ )
	{
		if( boneRemap[i] != InvalidBone )
			bones[boneRemap[i]] = tmp[i];
		else
			numRem++;
	}

	//delete any extra bones
	bones.resize( bones.size() - numRem );

	/*
		Fix up all bone references.
	*/
	for( uint i = 0; i < bones.size(); i++ )
		bones[i]->index = i;
}

void ModelData::DoRemapInfluences( const std::vector< uint > &infRemap )
{
	uint numRem = 0;

	std::vector< Influence > tmp = influences;
	for( uint i = 0; i < influences.size(); i++ )
	{
		if( infRemap[i] != InvalidInfluence )
			influences[infRemap[i]] = tmp[i];
		else
			numRem++;
	}

	//cut away excess influences
	influences.resize( influences.size() - numRem );

	for( uint i = 0; i < lods.size(); i++ )
	{
		std::vector< GroupPtr > &groups = lods[i]->groups;

		//remap each group's influence indices
		for( uint i = 0; i < groups.size(); i++ )
			groups[i]->DoRemapInfluences( infRemap );
	}
}

void ModelData::CountInfluenceUses( void )
{
	for( uint i = 0; i < influences.size(); i++ )
		influences[i].useCount = 0;

	for( uint i = 0; i < lods.size(); i++ )
	{
		LodPtr lod = lods[i];

		for( uint i = 0; i < lod->groups.size(); i++ )
		{
			GroupPtr group = lod->groups[i];

			for( uint i = 0; i < group->verts.size(); i++ )
			{
				const Vertex &v = group->verts[i];

				for( uint i = 0; i < X42_WEIGHTS_PER_VERT; i++ )
				{
					if( v.wt[i] )
						influences[group->infMap[v.idx[i]]].useCount++;
				}
			}
		}
	}
}

void ModelData::CollapseDuplicateInfluences( void )
{
	std::vector< uint > remap( influences.size() );

	for( uint i = 0; i < influences.size(); i++ )
		remap[i] = i;

	for( uint i = 0; i < influences.size(); i++ )
	{
		Influence &baseInf = influences[i];

		if( baseInf.useCount == 0 )
			//irrelevant (or already processed)
			continue;

		for( uint j = i + 1; j < influences.size(); j++ )
		{
			Influence &cmpInf = influences[j];

			if( cmpInf.useCount == 0 )
				//irrelevant (or already processed)
				continue;

			if( cmpInf.bone != baseInf.bone )
				continue;

			//if the matrices are close enough, throw out the one with the least uses
			if( !equal( baseInf.objToBone, cmpInf.objToBone, 1e-2F ) )
				continue;

			if( baseInf.useCount > cmpInf.useCount )
			{
				baseInf.useCount += cmpInf.useCount;
				cmpInf.useCount = 0;

				remap[j] = i;
			}
			else
			{
				cmpInf.useCount += baseInf.useCount;
				baseInf.useCount = 0;

				remap[i] = j;

				//baseInf no longer points to the right influence to compare against
				//fix up any references to baseInf

				for( uint k = 0; k < j; k++ )
					if( remap[k] == i )
						remap[k] = j;
				
				//pick it up again when i reaches j
				break;
			}
		}
	}

	for( uint i = 0; i < lods.size(); i++ )
	{
		std::vector< GroupPtr > &groups = lods[i]->groups;

		//remap each group's influence indices
		for( uint i = 0; i < groups.size(); i++ )
			groups[i]->DoMergeInfluences( remap );
	}
}

void ModelData::CollapseStaticInfluences( void )
{
	for( uint i = 0; i < lods.size(); i++ )
	{
		const std::vector< GroupPtr > &groups = lods[i]->groups;

		//remap each group's influence indices
		for( uint j = 0; j < groups.size(); j++ )
			groups[j]->DoCollapseStaticInfluences();
	}

	CountInfluenceUses();
}

};
};