/******************************************************************************
	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
{
/*****
	BoneTopology
*/
BoneTopology::BoneTopology( const std::vector<BonePtr> &bones )
	: entries( bones.size() )
{
	for( uint i = 0; i < bones.size(); i++ )
		ProcessBone( bones[i] );

	ProcessEntries();
}

BoneTopology::BoneTopology( const std::vector<ConstBonePtr> &bones )
	: entries( bones.size() )
{
	for( uint i = 0; i < bones.size(); i++ )
		ProcessBone( bones[i] );

	ProcessEntries();
}

void BoneTopology::ProcessBone( ConstBonePtr bone )
{
	Entry &boneEnt = entries[bone->index];

	boneEnt.bone = bone;

	if( bone->parent )
	{
		Entry &parentEnt = entries[bone->parent->index];

		boneEnt.parent = parentEnt.bone;
		entries[bone->parent->index].children.push_back( bone );
		
		boneEnt.localRoot = parentEnt.IsRoot() ? parentEnt.bone : parentEnt.localRoot;
		boneEnt.distanceToLocalRoot = parentEnt.distanceToLocalRoot + 1;
	}
	else
	{
		boneEnt.parent = ConstBonePtr();

		boneEnt.localRoot = ConstBonePtr();
		boneEnt.distanceToLocalRoot = 0;
	}
}

void BoneTopology::ProcessEntries( void )
{
	for( uint i = 0; i < entries.size(); i++ )
	{
		if( entries[i].IsRoot() )
			roots.push_back( entries[i].bone );
	}

	for( uint i = 0; i < entries.size(); i++ )
	{
		if( entries[i].IsLeaf() )
			leaves.push_back( entries[i].bone );
	}

	for( uint i = (uint)entries.size(); i--; )
	{
		Entry &ent = entries[i];

		ent.nearestLeaf = ConstBonePtr();
		ent.pathToNearestLeaf = ConstBonePtr();

		if( ent.IsLeaf() )
		{
			ent.distanceToNearestLeaf = 0;
			
			continue;
		}

		ent.distanceToNearestLeaf = 0xFFFFFFFF;

		for( uint i = 0; i < ent.children.size(); i++ )
		{
			Entry &childEnt = entries[ent.children[i]->index];

			if( childEnt.distanceToNearestLeaf + 1 < ent.distanceToNearestLeaf )
			{
				ent.distanceToNearestLeaf = childEnt.distanceToNearestLeaf + 1;
				ent.nearestLeaf = childEnt.nearestLeaf;
				ent.pathToNearestLeaf = childEnt.bone;
			}
		}
	}
}

};
};