/******************************************************************************
	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
{

/*****
	Lod
*/

std::vector< GroupPtr > Lod::SplitGroupByWeightCount( const ConstGroupPtr &group )
{
	std::vector< GroupPtr > ret( 4 );
	std::vector< std::vector< int > > vertMaps( 4 );
	
	for( uint i = 0; i < 4; i++ )
	{
		ret[i] = GroupPtr( new Group( this ) );
		
		ret[i]->surfaceName = group->surfaceName;
		ret[i]->material = group->material;
		
		ret[i]->maxInfsPerVert = i + 1;

		vertMaps[i].resize( group->verts.size(), -1 );
	}

	GroupPrimitiveIterator iter( group );
	while( iter.Next() )
	{
		int maxWt = 0;

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

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

			if( numWt > maxWt )
				maxWt = numWt;
		}
		
		GroupPtr tg = ret[maxWt - 1];
		std::vector< int > &vertMap = vertMaps[maxWt - 1];

		for( uint i = 0; i < iter.IndicesPerPrim(); i++ )
		{
			index idx = iter.Current( i );

			if( vertMap[idx] == -1 )
			{
				Vertex v = group->verts[idx];

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

					uint srcInf = group->infMap[v.idx[i]];
					uint dstInf;
					
					for( dstInf = 0; dstInf < tg->infMap.size(); dstInf++ )
					{
						if( tg->infMap[dstInf] == srcInf )
							break;
					}

					if( dstInf == tg->infMap.size() )
						tg->infMap.push_back( srcInf );

					v.idx[i] = dstInf;
				}

				tg->verts.push_back( v );
				vertMap[idx] = (int)tg->verts.size() - 1;
			}

			idx = (index)vertMap[idx];
			tg->indices.push_back( idx );
		}
	}

	return ret;
}

GroupPtr Lod::MergeGroups( const ConstGroupPtr &ga, const ConstGroupPtr &gb )
{
	GroupPtr ret( new Group( this ) );

	demand( ga->primType.ElemsPerPrim() == gb->primType.ElemsPerPrim(), "mismatched primitive sizes" );

	ret->surfaceName = ga->surfaceName;
	ret->material = ga->material;

	ret->primType = PrimType::ListTypeFromElemsPerPrim( ga->primType.ElemsPerPrim() );

	ret->verts.insert( ret->verts.begin(), ga->verts.begin(), ga->verts.end() );
	ret->infMap.insert( ret->infMap.begin(), ga->infMap.begin(), ga->infMap.end() );

	if( ga->primType.IsListType() && ga->indices.size() )
	{
		ret->indices.insert( ret->indices.begin(), ga->indices.begin(), ga->indices.end() );
	}
	else
	{
		GroupPrimitiveIterator ia( ga );
		while( ia.Next() )
		{
			for( uint i = 0; i < ia.IndicesPerPrim(); i++ )
				ret->indices.push_back( ia.Current( i ) );
		}
	}

	std::vector< int > remap( gb->verts.size() );

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

		uint idx;
		for( idx = 0; idx < ret->verts.size(); idx++ )
		{
			if( ret->verts[idx].point_rep == v.point_rep )
				break;
		}

		if( idx == ret->verts.size() )
		{
			Vertex vo = v;

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

				uint srcInf = gb->infMap[vo.idx[i]];
				uint dstInf;

				for( dstInf = 0; dstInf < ret->infMap.size(); dstInf++ )
				{
					if( ret->infMap[dstInf] == srcInf )
						break;
				}

				if( dstInf == ret->infMap.size() )
					ret->infMap.push_back( srcInf );

				vo.idx[i] = dstInf;
			}

			ret->verts.push_back( vo );
		}

		remap[i] = idx;
	}

	GroupPrimitiveIterator ib( gb );
	while( ib.Next() )
	{
		for( uint i = 0; i < ib.IndicesPerPrim(); i++ )
			ret->indices.push_back( util::checked_int_cast< index >( remap[ib.Current( i )] ) );
	}

	ret->FixupWeights();

	return ret;
}

void Lod::SplitByWeightCount( float bal, uint max_merge )
{
	if( max_merge > index_traits::max_val )
		max_merge = index_traits::max_val;

	std::vector< GroupPtr > newGroups;

	for( uint i = 0; i < groups.size(); i++ )
	{
		GroupPtr g = groups[i];

		for( uint i = 0; i < g->verts.size(); i++ )
			g->verts[i].point_rep = i;

		std::vector< GroupPtr > sg = SplitGroupByWeightCount( g );

		while( sg.size() > 1 )
		{
			GroupPtr ga = sg[0];
			GroupPtr gb = sg[1];

			if( !ga->verts.size() )
			{
				sg.erase( sg.begin() );
				continue;
			}

			if( !gb->verts.size() )
			{
				sg.erase( sg.begin() + 1 );
				continue;
			}

			uint size_sum = (uint)ga->verts.size() + (uint)gb->verts.size();
			
			if( size_sum < max_merge && ga->verts.size() < (uint)(gb->verts.size() * bal) )
			{
				//merge a into b
				GroupPtr g = MergeGroups( ga, gb );
				g->maxInfsPerVert = gb->maxInfsPerVert;

				newGroups.push_back( g );

				sg.erase( sg.begin(), sg.begin() + 2 );
			}
			else
			{
				newGroups.push_back( ga );
				sg.erase( sg.begin() );
			}
		}

		if( sg.size() )
		{
			for( uint i = 0; i < sg.size(); i++ )
			{
				if( sg[i]->verts.size() && sg[i]->indices.size() )
					newGroups.push_back( sg[i] );
			}
		}
	}

	groups = newGroups;
}

void Lod::SplitLargeGroupsGreedy( uint maxVerts, uint maxPrims, uint maxInfluences )
{
	demand( maxInfluences <= X42_MAX_INFLUENCES_PER_BATCH_V5, "Too many influences per batch." );

	for( uint iGroup = 0; iGroup < groups.size(); iGroup++ )
	{
		if( DoGreedySplit( iGroup, maxVerts, maxPrims, maxInfluences ) )	
			iGroup--;
	}
}

bool Lod::DoGreedySplit( uint iGroup, uint maxVerts, uint maxPrims, uint maxInfluences )
{
	GroupPtr group = groups[iGroup];

	uint numPrims = PrimType::ElemsToPrims( group->primType, (uint)group->indices.size() );

	if( group->verts.size() <= maxVerts && numPrims <= maxPrims && group->infMap.size() <= maxInfluences )
		return false;

	//set up a list of groups to split this one into
	uint splitCountGuess = (uint)max( (uint)group->infMap.size() / maxInfluences,
		max( (uint)group->verts.size() / maxVerts, numPrims / maxPrims ) );

	std::vector< GroupPtr > splitGroups;
	splitGroups.reserve( splitCountGuess );
	std::vector< std::vector< int > > vertRemap; //parallell to [splitGroups][group.verts]
	vertRemap.reserve( splitCountGuess );
	std::vector< std::vector< int > > infRemap; //parallell to [splitGroups][group.infMap]
	infRemap.reserve( splitCountGuess );

	std::vector< uint > addInfs;
	addInfs.reserve( splitCountGuess );
	std::vector< uint > addVerts;
	addVerts.reserve( splitCountGuess );

	/*
	Pull prims out of this group and put them into the group that
	will most easily absorb them. Never insert into a group that
	can't take more elements. Stop when this group is empty.

	This is really just a simple greedy algorighm. There's probably
	a more optimal way to do this...
	*/

	GroupPrimitiveIterator iter( group );
	while( iter.Next() )
	{	
		//create the cost estimate for the prim
		for( uint iG = 0; iG < splitGroups.size(); iG++ )
		{
			//reset the costs
			addInfs[iG] = 0;
			addVerts[iG] = 0;

			for( uint iPv = 0; iPv < iter.IndicesPerPrim(); iPv++ )
			{
				const index vIdx = iter.Current( iPv );
				//only count the cost if the vert's not already in the group

				if( vertRemap[iG][vIdx] == -1 )
				{
					addVerts[iG]++;

					const Vertex &vert = group->verts[vIdx];
					for( uint iW = 0; iW < X42_WEIGHTS_PER_VERT; iW++ )
						if( vert.wt[iW] != 0.0F && infRemap[iG][vert.idx[iW]] == -1 )
							addInfs[iG]++;
				}
			}
		}

		//find the best (cheapest) group to add it to
		uint iBest = (uint)splitGroups.size();
		for( uint i = 0; i < splitGroups.size(); i++ )
		{
			const Group &sGroup = *splitGroups[i];

			//make sure we can actually add into this group
			if( PrimType::ElemsToPrims( sGroup.primType, (uint)sGroup.indices.size() ) + 1 > maxPrims )
				continue;
			if( sGroup.verts.size() + addVerts[i] > maxVerts )
				continue;
			if( sGroup.infMap.size() + addInfs[i] > maxInfluences )
				continue;

			//we're OK to add to sGroup, now see if it's the best we can do

			if( iBest == splitGroups.size() )
			{
				iBest = i;
				continue;
			}

			if( addInfs[i] < addInfs[iBest] )
				iBest = i;
			else if( addInfs[i] == addInfs[iBest] && addVerts[i] < addVerts[iBest] )
				iBest = i;
		}

		if( iBest == splitGroups.size() )
		{
			//create a new group (outside of the groups vector) to split into
			GroupPtr newG( new Group( this ) );

			newG->material = group->material;
			newG->surfaceName = group->surfaceName;
			newG->maxInfsPerVert = group->maxInfsPerVert; //ToDo: take this into account when splitting rather than fudging it here
			newG->primType = group->primType;

			splitGroups.push_back( newG );

			vertRemap.push_back( std::vector< int >( group->verts.size(), -1 ) );
			infRemap.push_back( std::vector< int >( group->infMap.size(), -1 ) );

			addInfs.push_back( 0 );
			addVerts.push_back( 0 );
		}

		Group &sGroup = *splitGroups[iBest];
		std::vector< int > &infMap = infRemap[iBest];
		std::vector< int > &vertMap = vertRemap[iBest];

		for( uint iPv = 0; iPv < iter.IndicesPerPrim(); iPv++ )
		{
			uint vidx = iter.Current( iPv );

			if( vertMap[vidx] == -1 )
			{
				Vertex vert = group->verts[vidx];

				for( int i = 0; i < X42_WEIGHTS_PER_VERT; i++ )
				{
					if( vert.wt[i] == 0.0F )
						continue;

					if( infMap[vert.idx[i]] == -1 )
					{
						sGroup.infMap.push_back( group->infMap[vert.idx[i]] );
						infMap[vert.idx[i]] = (uint)sGroup.infMap.size() - 1;
					}

					vert.idx[i] = infMap[vert.idx[i]];
				}

				sGroup.verts.push_back( vert );
				vertMap[vidx] = (uint)sGroup.verts.size() - 1;
			}

			vidx = (uint)vertMap[vidx];

			sGroup.indices.push_back( (index)vidx );				
		}
	}

	for( uint i = 0; i < splitGroups.size(); i++ )
		splitGroups[i]->FixupWeights();

	/*
	Put the split groups back into the main iteration sequence.
	*/
	groups.erase( groups.begin() + iGroup );
	groups.insert( groups.begin() + iGroup, splitGroups.begin(), splitGroups.end() );
	
	return true;
}

#if 0
class BoneRanking
{
public:
	std::vector< ConstBonePtr > rankedBones;

	BoneRanking( const BoneTopology &topology,
		const std::vector< ConstBonePtr > &ignoreBones = std::vector< ConstBonePtr >() );

	uint NumRankedBones( void ) const { return (uint)rankedBones.size(); }
	ConstBonePtr operator [] ( uint index ) const { return rankedBones[index]; }

private:
	void AddBone_R( const BoneTopology &topology,
		const std::vector< bool > &ignoreFlags,
		ConstBonePtr bone, ConstBonePtr skipBone );
};

BoneRanking::BoneRanking( const BoneTopology &topology,
	const std::vector< ConstBonePtr > &ignoreBones )
{
	std::vector< bool > ignoreFlags( topology.entries.size(), false );

	for( uint i = 0; i < ignoreBones.size(); i++ )
	{
		ignoreFlags[ignoreBones[i]->index] = true;
	}

	for( ; ; )
	{
		//find the bone that's furthest from the root
		ConstBonePtr furthestBone;
		uint maxDist = 0;

		for( uint i = 0; i < topology.NumEntries(); i++ )
		{
			if( ignoreFlags[topology[i].bone->index] )
				//never start from an ignored bone
				continue;

			if( topology[i].distanceToLocalRoot > maxDist )
			{
				furthestBone = topology[i].bone;
				maxDist = topology[i].distanceToLocalRoot;
			}
		}

		if( !furthestBone )
			//done
			break;

		//add furthestBone and start working back from there
		AddBone_R( topology, ignoreFlags, furthestBone, ConstBonePtr() );
	}
}

void BoneRanking::AddBone_R( const BoneTopology &topology,
		const std::vector< bool > &ignoreFlags, ConstBonePtr bone, ConstBonePtr skipBone )
{
	if( !bone || bone == skipBone )
		return;

	if( !ignoreFlags[bone->index] )
		rankedBones.push_back( bone );

	struct LeafSort
	{
		LeafSort( const BoneTopology &topology ) : topology( topology ) { }
		const BoneTopology &topology;

		bool operator() ( ConstBonePtr a, ConstBonePtr b )
		{
			return topology[a].distanceToNearestLeaf < topology[b].distanceToNearestLeaf;
		}

	private:
		LeafSort& operator = ( const LeafSort & ) { return *this; }
	};

	std::vector< ConstBonePtr > children = topology[bone].children;
	std::sort( children.begin(), children.end(), LeafSort( topology ) );

	for( uint i = 0; i < children.size(); i++ )
	{
		if( children[i] != skipBone )
			AddBone_R( topology, ignoreFlags, children[i], bone );
	}

	if( topology[bone].parent != skipBone )
		AddBone_R( topology, ignoreFlags, topology[bone].parent, bone );
}

#endif
void Lod::SplitLargeGroupsSkeletal( uint maxVerts, uint maxPrims, uint maxInfluences )
{
#if 0
	demand( maxInfluences <= X42_MAX_INFLUENCES_PER_BATCH, "Too many influences per batch." );

	BoneTopology topology( GetModel()->bones );

	for( uint iGroup = 0; iGroup < groups.size(); iGroup++ )
	{
		Group &group = *groups[iGroup];

		uint numPrims = PrimType::ElemsToPrims( group.primType, (uint)group.indices.size() );

		if( group.verts.size() <= maxVerts && numPrims <= maxPrims && group.infMap.size() <= maxInfluences )
			continue;

		GroupPtr inGroup( new Group( this ) );
		GroupPtr outGroup( new Group( this ) );

		BoneRanking ranking( topology );

		if( inGroup->verts.size() )
			groups.push_back( inGroup );
		if( outGroup->verts.size() )
			groups.push_back( outGroup );

		groups.erase( groups.begin() + iGroup );
		iGroup--;
	}
#else
	SplitLargeGroupsTopological( maxVerts, maxPrims, maxInfluences );
#endif
}

void Lod::SplitLargeGroupsTopological( uint maxVerts, uint maxPrims, uint maxInfluences )
{
	demand( maxInfluences <= X42_MAX_INFLUENCES_PER_BATCH_V5, "Too many influences per batch." );

	for( uint iGroup = 0; iGroup < groups.size(); iGroup++ )
	{
		Group &group = *groups[iGroup];

		switch( group.primType )
		{
		case PrimType::TriangleFan:
		case PrimType::TriangleStrip:
		case PrimType::TriangleList:
			if( DoTopologicalSplit( iGroup, maxVerts, maxPrims, maxInfluences ) )
				iGroup--;
			break;

		default:
			if( DoGreedySplit( iGroup, maxVerts, maxPrims, maxInfluences ) )	
				iGroup--;
			break;
		}
	}
}

bool Lod::DoTopologicalSplit( uint iGroup, uint maxVerts, uint maxPrims, uint maxInfluences )
{
	GroupPtr group;

	//see what we'd get splitting from the leaves
	group = groups[iGroup];
	std::vector< GroupPtr > leafSplit;
	while( group->verts.size() > maxVerts || group->NumPrimitives() > maxPrims ||
		group->infMap.size() > maxInfluences )
	{
		TopologicalSplitter splitter( group, maxVerts, maxPrims, maxInfluences );	

		splitter.AddSetsStartingAtLeaves();
		splitter.AddUnvisitedSetsInOrder();

		splitter.FixupWeights();

		leafSplit.push_back( splitter.GoodGroup() );
		group = splitter.SpilloverGroup();
	}
	leafSplit.push_back( group );

	//see what we'd get splitting from the roots
	group = groups[iGroup];
	std::vector< GroupPtr > rootSplit;
	while( group->verts.size() > maxVerts || group->NumPrimitives() > maxPrims ||
		group->infMap.size() > maxInfluences )
	{
		TopologicalSplitter splitter( group, maxVerts, maxPrims, maxInfluences );	

		splitter.AddSetsStartingAtRoot();
		splitter.AddUnvisitedSetsInOrder();

		splitter.FixupWeights();

		rootSplit.push_back( splitter.GoodGroup() );
		group = splitter.SpilloverGroup();
	}
	rootSplit.push_back( group );

	//pick the best of the two options
	std::vector< GroupPtr > *bestGroup = 0;

	if( leafSplit.size() < rootSplit.size() )
		bestGroup = &leafSplit;
	else if( rootSplit.size() < leafSplit.size() )
		bestGroup = &rootSplit;
	
	if( !bestGroup )
	{
		size_t leafUploads = 0;
		for( uint i = 0; i < leafSplit.size(); i++ )
			leafUploads += leafSplit[i]->infMap.size();

		size_t rootUploads = 0;
		for( uint i = 0; i < rootSplit.size(); i++ )
			rootUploads += rootSplit[i]->infMap.size();

		if( leafUploads < rootUploads )
			bestGroup = &leafSplit;
		else if( rootUploads < leafUploads )
			bestGroup = &rootSplit;
	}

	if( !bestGroup )
		bestGroup = &leafSplit;

	if( bestGroup->size() == 1 )
		//didn't actually split anything
		return false;

	groups.erase( groups.begin() + iGroup );
	groups.insert( groups.begin() + iGroup, bestGroup->begin(), bestGroup->end() );

	return true;
}

void Lod::MergeSmallGroups( float bal, uint maxVerts, uint maxPrims, uint maxInfluences )
{
	for( uint iA = 0; iA < groups.size(); iA++ )
	{
		GroupPtr ga = groups[iA];

		if( ga->infMap.size() >= maxInfluences ||
			ga->verts.size() >= maxVerts ||
			ga->NumPrimitives() >= maxPrims )
			continue;

		if( !ga->verts.size() )
		{
			groups.erase( groups.begin() + iA );
			iA--;
			continue;
		}

		for( uint iB = iA + 1; iB < groups.size(); iB++ )
		{
			GroupPtr gb = groups[iB];

			if( gb->infMap.size() >= maxInfluences ||
				gb->verts.size() >= maxVerts ||
				gb->NumPrimitives() >= maxPrims )
				continue;

			if( !gb->verts.size() )
			{
				groups.erase( groups.begin() + iB );
				iB--;
				continue;
			}

			if( ga->primType.ElemsPerPrim() != gb->primType.ElemsPerPrim() )
				continue;

			if( ga->material != gb->material ||
				ga->surfaceName != gb->surfaceName )
				continue;

			if( ga->maxInfsPerVert < gb->maxInfsPerVert )
			{
				float balFact = powf( bal, (float)(gb->maxInfsPerVert - ga->maxInfsPerVert) );
				if( ga->verts.size() > gb->verts.size() * balFact )
					continue;
			}
			else if( gb->maxInfsPerVert < ga->maxInfsPerVert )
			{
				float balFact = powf( bal, (float)(ga->maxInfsPerVert - gb->maxInfsPerVert) );
				if( gb->verts.size() > ga->verts.size() * balFact )
					continue;
			}

			GroupPtr gc = MergeGroups( ga, gb );

			if( gc->infMap.size() < maxInfluences &&
				gc->verts.size() < maxVerts &&
				gc->NumPrimitives() < maxPrims )
			{
				groups[iA] = gc;
				groups.erase( groups.begin() + iB );
			}
		}

		if( ga != groups[iA] )
			//merged and replaced this one
			iA--;
	}
}

/*****
	ModelData
*/
void ModelData::SplitLargeGroups( SplitMethod method, uint maxVerts, uint maxPrims, uint maxInfluences )
{
	for( uint i = 0; i < lods.size(); i++ )
	{
		switch( method )
		{
		case SplitMethod::Greedy:
			lods[i]->SplitLargeGroupsGreedy( maxVerts, maxPrims, maxInfluences );
			break;

		case SplitMethod::Topological:
			lods[i]->SplitLargeGroupsTopological( maxVerts, maxPrims, maxInfluences );
			break;
		}
	}
}

void ModelData::SplitByWeightCount( float bal, uint max_merge )
{
	for( uint i = 0; i < lods.size(); i++ )
		lods[i]->SplitByWeightCount( bal, max_merge );
}

void ModelData::MergeSmallGroups( float bal, uint maxVerts, uint maxPrims, uint maxInfluences )
{
	for( uint i = 0; i < lods.size(); i++ )
		lods[i]->MergeSmallGroups( bal, maxVerts, maxPrims, maxInfluences );
}

};
};