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

TopologicalSplitter::TopologicalSplitter( ConstGroupPtr group,
	uint maxVerts, uint maxPrims, uint maxInfluences )

	: group( group ),
	maxVerts( maxVerts ), maxPrims( maxPrims ), maxInfluences( maxInfluences ),
	
	goodGroup( boost::const_pointer_cast< Group >( group )->GetLod()->InternalCreateGroup() ),
	goodInfMap( group->infMap.size(), Group::InvalidInfluence ),
	goodVertMap( group->verts.size(), Group::InvalidIndex ),
	
	spillGroup( boost::const_pointer_cast< Group >( group )->GetLod()->InternalCreateGroup() ),
	spillInfMap( group->infMap.size(), Group::InvalidInfluence ),
	spillVertMap( group->verts.size(), Group::InvalidIndex ),

	triIndices( group->InternalGetTriangleIndices() )
{
	std::vector< index > adjIndices( triIndices );
	ResolvePointReps( adjIndices );
	adj.Init( adjIndices );

	triangles.resize( triIndices.size() / 3 );
	for( uint i = 0; i < triangles.size(); i++ )
		triangles[i].idx = i;

	goodGroup->material = group->material;
	goodGroup->surfaceName = group->surfaceName;
	goodGroup->maxInfsPerVert = group->maxInfsPerVert;
	goodGroup->primType = PrimType::TriangleList;

	spillGroup->material = group->material;
	spillGroup->surfaceName = group->surfaceName;
	spillGroup->maxInfsPerVert = group->maxInfsPerVert;
	spillGroup->primType = PrimType::TriangleList;
}

void TopologicalSplitter::ResolvePointReps( std::vector< index > &indices )
{
	std::vector< index > pointReps( group->verts.size() );
	for( uint i = 0; i < pointReps.size(); i++ )
	{
		const Vertex &vi = group->verts[i];

		pointReps[i] = (index)i;

		for( uint j = i; j--; )
		{
			const Vertex &vj = group->verts[j];

			if( !equal( vi.pos, vj.pos, 1e-5F ) )
				continue;

			bool eq = true;
			for( uint wt = 0; eq && wt < X42_WEIGHTS_PER_VERT; wt++ )
			{
				if( fabsf( vi.wt[wt] - vj.wt[wt] ) > 1e-5F )
					eq = false;
				else if( vi.wt[wt] && vi.idx[wt] != vj.idx[wt] )
					eq = false;
			}

			if( !eq )
				continue;

			pointReps[i] = pointReps[j];
			break;
		}
	}

	for( uint i = 0; i < indices.size(); i++ )
		indices[i] = pointReps[indices[i]];
}

void TopologicalSplitter::AddUnvisitedSetsInOrder( void )
{
	for( uint i = 0; i < triangles.size(); i++ )
	{
		if( !triangles[i].visited )
			AddAdjacencySet( i );
	}
}

struct LeafSortLt
{
public:
	LeafSortLt( const BoneTopology &topology ) : top( &topology ) { }

	bool operator () ( const ConstBonePtr &a, const ConstBonePtr &b )
	{
		return (*top)[a].distanceToLocalRoot < (*top)[b].distanceToLocalRoot;
	}

private:
	const BoneTopology *top;
};

void TopologicalSplitter::AddSetsStartingAtLeaves( void )
{
	const ModelData *mod = group->GetModel();
	BoneTopology topology( mod->bones );

	std::vector< ConstBonePtr > toVisit;

	toVisit.insert( toVisit.begin(), topology.leaves.begin(), topology.leaves.end() );
	std::sort( toVisit.begin(), toVisit.end(), LeafSortLt( topology ) );

	InternalAddSets( toVisit, false, topology );
}

struct LeafSortGt
{
public:
	LeafSortGt( const BoneTopology &topology ) : top( &topology ) { }

	bool operator () ( const ConstBonePtr &a, const ConstBonePtr &b )
	{
		return (*top)[a].distanceToLocalRoot > (*top)[b].distanceToLocalRoot;
	}

private:
	const BoneTopology *top;
};

void TopologicalSplitter::AddSetsStartingAtRoot( void )
{
	const ModelData *mod = group->GetModel();
	BoneTopology topology( mod->bones );

	std::vector< ConstBonePtr > toVisit;

	toVisit.insert( toVisit.begin(), topology.leaves.begin(), topology.leaves.end() );
	std::sort( toVisit.begin(), toVisit.end(), LeafSortGt( topology ) );

	InternalAddSets( toVisit, false, topology );
}

void TopologicalSplitter::InternalAddSets( std::vector< ConstBonePtr > &toVisit,
	bool favorRoot, const BoneTopology &topology )
{
	const ModelData *mod = group->GetModel();
	std::vector< bool > visitedBones( mod->bones.size(), false );
	
	while( toVisit.size() )
	{
		ConstBonePtr bone = toVisit.back();
		toVisit.pop_back();
		
		if( visitedBones[bone->index] )
			continue;
		visitedBones[bone->index] = true;

		if( favorRoot )
		{
			toVisit.insert( toVisit.end(),
				topology[bone].children.begin(), topology[bone].children.end() );

			if( !topology[bone].IsRoot() )
				toVisit.push_back( topology[bone].parent );
		}
		else
		{
			if( !topology[bone].IsRoot() )
				toVisit.push_back( topology[bone].parent );

			toVisit.insert( toVisit.end(),
				topology[bone].children.begin(), topology[bone].children.end() );
		}

		//go through all influences attached to this bone
		for( uint iInf = 0; iInf < group->infMap.size(); iInf++ )
		{
			if( mod->influences[group->infMap[iInf]].bone != bone )
				continue;

			//find a triangle weighted to local influence i
			uint candidateTri = Group::InvalidTriangle;
			for( uint i = 0; i < triIndices.size(); i++ )
			{
				const Vertex &v = group->verts[triIndices[i]];
			
				bool isCandidate = false;
				for( uint iWt = 0; iWt < X42_WEIGHTS_PER_VERT; iWt++ )
				{
					if( v.wt[iWt] == 0 )
						continue;

					if( v.idx[iWt] == iInf )
					{
						isCandidate = true;
						break;
					}
				}

				if( isCandidate )
				{
					candidateTri = i / 3;
					break;
				}
			}

			if( candidateTri == Group::InvalidTriangle )
				continue;

			AddAdjacencySet( candidateTri );
		}
	}
}

struct TriCmp
{
	bool operator () ( uint ia, uint ib )
	{
		const TopologicalSplitter::Tri &a = owner->triangles[ia];
		const TopologicalSplitter::Tri &b = owner->triangles[ib];

		if( a.addInfs > b.addInfs )
			return true;
		if( a.addInfs < b.addInfs )
			return false;

		return a.addVerts > b.addVerts;
	}
	
	TriCmp( const TopologicalSplitter *owner )
		: owner( owner )
	{
	}

private:
	const TopologicalSplitter *owner;
};

void TopologicalSplitter::AddAdjacencySet( uint startingTri )
{
	std::vector< uint > toVisit, nextVisit;
	toVisit.push_back( startingTri );

	uint prevPrims = goodGroup->NumPrimitives() + 1;
	while( toVisit.size() && prevPrims != goodGroup->NumPrimitives() )
	{
		prevPrims = goodGroup->NumPrimitives();

		UpdateTriList();
		std::sort( toVisit.begin(), toVisit.end(), TriCmp( this ) );

		uint i;
		//add any triangles we can sneak in for near-free
		for( i = 0; i < toVisit.size(); i++ )
		{
			Tri &tri = triangles[toVisit[i]];

			if( tri.visited )
				continue;

			if( tri.addInfs != 0 )
				break;

			tri.visited = true;
			for( const uint *a = adj.AdjBegin( tri.idx );
				a < adj.AdjEnd( tri.idx ); a++ )
			{
				if( !triangles[*a].visited )
					nextVisit.push_back( *a );
			}

			AddTriangle( tri );
		}

		if( i )
		{
			//have added triangles, merge nextVisit with toVisit and continue from there
			toVisit.assign( nextVisit.begin(), nextVisit.end() );
			std::sort( toVisit.begin(), toVisit.end(), TriCmp( this ) );
			nextVisit.clear();
		}

		for( i = 0; i < toVisit.size(); i++ )
		{
			Tri &tri = triangles[toVisit[i]];

			if( tri.visited )
				continue;

			tri.visited = true;	
			for( const uint *a = adj.AdjBegin( tri.idx );
				a < adj.AdjEnd( tri.idx ); a++ )
			{
				if( !triangles[*a].visited )
					nextVisit.push_back( *a );
			}

			AddTriangle( tri );
		}

		toVisit.clear();
		std::swap( nextVisit, toVisit );
	}
}

void TopologicalSplitter::UpdateTriList( void )
{
	//compute the cost of adding each of the candidate triangles
	std::vector< uint > tmpInfs;
	for( uint i = 0; i < triangles.size(); i++ )
	{
		tmpInfs.assign( goodInfMap.begin(), goodInfMap.end() );

		Tri &tri = triangles[i];
		
		if( tri.visited )
		{
			//force it to sort to the back but otherwise ignore
			tri.addInfs = uint_traits::max_val;
			tri.addVerts = uint_traits::max_val;
			continue;
		}

		uint addInfs = 0;
		uint addVerts = 0;

		for( uint iVert = 0; iVert < 3; iVert++ )
		{
			uint vIdx = triIndices[tri.idx * 3 + iVert];
			const Vertex &v = group->verts[vIdx];

			if( goodVertMap[vIdx] == Group::InvalidIndex )
			{
				addVerts++;

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

					if( tmpInfs[v.idx[iWt]] == Group::InvalidInfluence )
					{
						tmpInfs[v.idx[iWt]] = 0; //just flag it so we don't count it again
						addInfs++;
					}
				}
			}
		}

		tri.addInfs = addInfs;
		tri.addVerts = addVerts;
	}
}

void TopologicalSplitter::AddTriangle( const Tri &tri )
{
	GroupPtr destGroup;
	std::vector< uint > *destInfMap;
	std::vector< index > *destVertMap;

	if( goodGroup->indices.size() / 3 + 1 <= maxPrims &&
		goodGroup->verts.size() + tri.addVerts <= maxVerts &&
		goodGroup->infMap.size() + tri.addInfs <= maxInfluences )
	{
		destGroup = goodGroup;
		destInfMap = &goodInfMap;
		destVertMap = &goodVertMap;
	}
	else
	{
		destGroup = spillGroup;
		destInfMap = &spillInfMap;
		destVertMap = &spillVertMap;
	}

	for( uint iVert = 0; iVert < 3; iVert++ )
	{
		uint vIdx = triIndices[tri.idx * 3 + iVert];
		if( (*destVertMap)[vIdx] == Group::InvalidIndex )
		{
			const Vertex &oldVert = group->verts[vIdx];
			Vertex newVert = oldVert;

			for( uint iWt = 0; iWt < X42_WEIGHTS_PER_VERT; iWt++ )
			{
				if( !oldVert.wt[iWt] )
					continue;

				if( (*destInfMap)[oldVert.idx[iWt]] == Group::InvalidInfluence )
				{
					(*destInfMap)[oldVert.idx[iWt]] = (uint)destGroup->infMap.size();
					destGroup->infMap.push_back( group->infMap[oldVert.idx[iWt]] );
				}

				newVert.idx[iWt] = (*destInfMap)[oldVert.idx[iWt]];
			}

			(*destVertMap)[vIdx] = (index)destGroup->verts.size();
			destGroup->verts.push_back( newVert );
		}

		destGroup->indices.push_back( (*destVertMap)[vIdx] );
	}
}

void TopologicalSplitter::FixupWeights( void )
{
	goodGroup->FixupWeights();
	spillGroup->FixupWeights();
}


};
};