nuclear@0: /*
nuclear@0: Open Asset Import Library (assimp)
nuclear@0: ----------------------------------------------------------------------
nuclear@0: 
nuclear@0: Copyright (c) 2006-2012, assimp team
nuclear@0: All rights reserved.
nuclear@0: 
nuclear@0: Redistribution and use of this software in source and binary forms, 
nuclear@0: with or without modification, are permitted provided that the 
nuclear@0: following conditions are met:
nuclear@0: 
nuclear@0: * Redistributions of source code must retain the above
nuclear@0:   copyright notice, this list of conditions and the
nuclear@0:   following disclaimer.
nuclear@0: 
nuclear@0: * Redistributions in binary form must reproduce the above
nuclear@0:   copyright notice, this list of conditions and the
nuclear@0:   following disclaimer in the documentation and/or other
nuclear@0:   materials provided with the distribution.
nuclear@0: 
nuclear@0: * Neither the name of the assimp team, nor the names of its
nuclear@0:   contributors may be used to endorse or promote products
nuclear@0:   derived from this software without specific prior
nuclear@0:   written permission of the assimp team.
nuclear@0: 
nuclear@0: THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 
nuclear@0: "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 
nuclear@0: LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
nuclear@0: A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 
nuclear@0: OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
nuclear@0: SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 
nuclear@0: LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
nuclear@0: DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 
nuclear@0: THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 
nuclear@0: (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 
nuclear@0: OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
nuclear@0: 
nuclear@0: ----------------------------------------------------------------------
nuclear@0: */
nuclear@0: 
nuclear@0: 
nuclear@0: /// @file SplitByBoneCountProcess.cpp 
nuclear@0: /// Implementation of the SplitByBoneCount postprocessing step
nuclear@0: 
nuclear@0: #include "AssimpPCH.h"
nuclear@0: 
nuclear@0: // internal headers of the post-processing framework
nuclear@0: #include "SplitByBoneCountProcess.h"
nuclear@0: 
nuclear@0: #include <limits>
nuclear@0: 
nuclear@0: using namespace Assimp;
nuclear@0: 
nuclear@0: // ------------------------------------------------------------------------------------------------
nuclear@0: // Constructor
nuclear@0: SplitByBoneCountProcess::SplitByBoneCountProcess()
nuclear@0: {
nuclear@0: 	// set default, might be overriden by importer config
nuclear@0: 	mMaxBoneCount = AI_SBBC_DEFAULT_MAX_BONES;
nuclear@0: }
nuclear@0: 
nuclear@0: // ------------------------------------------------------------------------------------------------
nuclear@0: // Destructor
nuclear@0: SplitByBoneCountProcess::~SplitByBoneCountProcess()
nuclear@0: {
nuclear@0: 	// nothing to do here
nuclear@0: }
nuclear@0: 
nuclear@0: // ------------------------------------------------------------------------------------------------
nuclear@0: // Returns whether the processing step is present in the given flag.
nuclear@0: bool SplitByBoneCountProcess::IsActive( unsigned int pFlags) const
nuclear@0: {
nuclear@0: 	return !!(pFlags & aiProcess_SplitByBoneCount);
nuclear@0: }
nuclear@0: 
nuclear@0: // ------------------------------------------------------------------------------------------------
nuclear@0: // Updates internal properties
nuclear@0: void SplitByBoneCountProcess::SetupProperties(const Importer* pImp)
nuclear@0: {
nuclear@0: 	mMaxBoneCount = pImp->GetPropertyInteger(AI_CONFIG_PP_SBBC_MAX_BONES,AI_SBBC_DEFAULT_MAX_BONES);
nuclear@0: }
nuclear@0: 
nuclear@0: // ------------------------------------------------------------------------------------------------
nuclear@0: // Executes the post processing step on the given imported data.
nuclear@0: void SplitByBoneCountProcess::Execute( aiScene* pScene)
nuclear@0: {
nuclear@0: 	DefaultLogger::get()->debug("SplitByBoneCountProcess begin");
nuclear@0: 
nuclear@0: 	// early out 
nuclear@0: 	bool isNecessary = false;
nuclear@0: 	for( size_t a = 0; a < pScene->mNumMeshes; ++a)
nuclear@0: 		if( pScene->mMeshes[a]->mNumBones > mMaxBoneCount )
nuclear@0: 			isNecessary = true;
nuclear@0: 
nuclear@0: 	if( !isNecessary )
nuclear@0: 	{
nuclear@0: 		DefaultLogger::get()->debug( boost::str( boost::format( "SplitByBoneCountProcess early-out: no meshes with more than %d bones.") % mMaxBoneCount));
nuclear@0: 		return;
nuclear@0: 	}
nuclear@0: 
nuclear@0: 	// we need to do something. Let's go.
nuclear@0: 	mSubMeshIndices.clear();
nuclear@0: 	mSubMeshIndices.resize( pScene->mNumMeshes);
nuclear@0: 
nuclear@0: 	// build a new array of meshes for the scene
nuclear@0: 	std::vector<aiMesh*> meshes;
nuclear@0: 
nuclear@0: 	for( size_t a = 0; a < pScene->mNumMeshes; ++a)
nuclear@0: 	{
nuclear@0: 		aiMesh* srcMesh = pScene->mMeshes[a];
nuclear@0: 
nuclear@0: 		std::vector<aiMesh*> newMeshes;
nuclear@0: 		SplitMesh( pScene->mMeshes[a], newMeshes);
nuclear@0: 
nuclear@0: 		// mesh was split
nuclear@0: 		if( !newMeshes.empty() )
nuclear@0: 		{
nuclear@0: 			// store new meshes and indices of the new meshes
nuclear@0: 			for( size_t b = 0; b < newMeshes.size(); ++b)
nuclear@0: 			{
nuclear@0: 				mSubMeshIndices[a].push_back( meshes.size());
nuclear@0: 				meshes.push_back( newMeshes[b]);
nuclear@0: 			}
nuclear@0: 
nuclear@0: 			// and destroy the source mesh. It should be completely contained inside the new submeshes
nuclear@0: 			delete srcMesh;
nuclear@0: 		}
nuclear@0: 		else
nuclear@0: 		{
nuclear@0: 			// Mesh is kept unchanged - store it's new place in the mesh array
nuclear@0: 			mSubMeshIndices[a].push_back( meshes.size());
nuclear@0: 			meshes.push_back( srcMesh);
nuclear@0: 		}
nuclear@0: 	}
nuclear@0: 
nuclear@0: 	// rebuild the scene's mesh array
nuclear@0: 	pScene->mNumMeshes = meshes.size();
nuclear@0: 	delete [] pScene->mMeshes;
nuclear@0: 	pScene->mMeshes = new aiMesh*[pScene->mNumMeshes];
nuclear@0: 	std::copy( meshes.begin(), meshes.end(), pScene->mMeshes);
nuclear@0: 
nuclear@0: 	// recurse through all nodes and translate the node's mesh indices to fit the new mesh array
nuclear@0: 	UpdateNode( pScene->mRootNode);
nuclear@0: 
nuclear@0: 	DefaultLogger::get()->debug( boost::str( boost::format( "SplitByBoneCountProcess end: split %d meshes into %d submeshes.") % mSubMeshIndices.size() % meshes.size()));
nuclear@0: }
nuclear@0: 
nuclear@0: // ------------------------------------------------------------------------------------------------
nuclear@0: // Splits the given mesh by bone count.
nuclear@0: void SplitByBoneCountProcess::SplitMesh( const aiMesh* pMesh, std::vector<aiMesh*>& poNewMeshes) const
nuclear@0: {
nuclear@0: 	// skip if not necessary
nuclear@0: 	if( pMesh->mNumBones <= mMaxBoneCount )
nuclear@0: 		return;
nuclear@0: 
nuclear@0: 	// necessary optimisation: build a list of all affecting bones for each vertex
nuclear@0: 	// TODO: (thom) maybe add a custom allocator here to avoid allocating tens of thousands of small arrays
nuclear@0: 	typedef std::pair<size_t, float> BoneWeight;
nuclear@0: 	std::vector< std::vector<BoneWeight> > vertexBones( pMesh->mNumVertices);
nuclear@0: 	for( size_t a = 0; a < pMesh->mNumBones; ++a)
nuclear@0: 	{
nuclear@0: 		const aiBone* bone = pMesh->mBones[a];
nuclear@0: 		for( size_t b = 0; b < bone->mNumWeights; ++b)
nuclear@0: 			vertexBones[ bone->mWeights[b].mVertexId ].push_back( BoneWeight( a, bone->mWeights[b].mWeight));
nuclear@0: 	}
nuclear@0: 
nuclear@0: 	size_t numFacesHandled = 0;
nuclear@0: 	std::vector<bool> isFaceHandled( pMesh->mNumFaces, false);
nuclear@0: 	while( numFacesHandled < pMesh->mNumFaces )
nuclear@0: 	{
nuclear@0: 		// which bones are used in the current submesh
nuclear@0: 		size_t numBones = 0;
nuclear@0: 		std::vector<bool> isBoneUsed( pMesh->mNumBones, false);
nuclear@0: 		// indices of the faces which are going to go into this submesh
nuclear@0: 		std::vector<size_t> subMeshFaces;
nuclear@0: 		subMeshFaces.reserve( pMesh->mNumFaces);
nuclear@0: 		// accumulated vertex count of all the faces in this submesh
nuclear@0: 		size_t numSubMeshVertices = 0;
nuclear@0: 		// a small local array of new bones for the current face. State of all used bones for that face
nuclear@0: 		// can only be updated AFTER the face is completely analysed. Thanks to imre for the fix.
nuclear@0: 		std::vector<size_t> newBonesAtCurrentFace;
nuclear@0: 
nuclear@0: 		// add faces to the new submesh as long as all bones affecting the faces' vertices fit in the limit
nuclear@0: 		for( size_t a = 0; a < pMesh->mNumFaces; ++a)
nuclear@0: 		{
nuclear@0: 			// skip if the face is already stored in a submesh
nuclear@0: 			if( isFaceHandled[a] )
nuclear@0: 				continue;
nuclear@0: 
nuclear@0: 			const aiFace& face = pMesh->mFaces[a];
nuclear@0: 			// check every vertex if its bones would still fit into the current submesh
nuclear@0: 			for( size_t b = 0; b < face.mNumIndices; ++b )
nuclear@0: 			{
nuclear@0: 				const std::vector<BoneWeight>& vb = vertexBones[face.mIndices[b]];
nuclear@0: 				for( size_t c = 0; c < vb.size(); ++c)
nuclear@0: 				{
nuclear@0: 					size_t boneIndex = vb[c].first;
nuclear@0: 					// if the bone is already used in this submesh, it's ok
nuclear@0: 					if( isBoneUsed[boneIndex] )
nuclear@0: 						continue;
nuclear@0: 
nuclear@0: 					// if it's not used, yet, we would need to add it. Store its bone index
nuclear@0: 					if( std::find( newBonesAtCurrentFace.begin(), newBonesAtCurrentFace.end(), boneIndex) == newBonesAtCurrentFace.end() )
nuclear@0: 						newBonesAtCurrentFace.push_back( boneIndex);
nuclear@0: 				}
nuclear@0: 			}
nuclear@0: 
nuclear@0: 			// leave out the face if the new bones required for this face don't fit the bone count limit anymore
nuclear@0: 			if( numBones + newBonesAtCurrentFace.size() > mMaxBoneCount )
nuclear@0: 				continue;
nuclear@0: 
nuclear@0: 			// mark all new bones as necessary
nuclear@0: 			while( !newBonesAtCurrentFace.empty() )
nuclear@0: 			{
nuclear@0: 				size_t newIndex = newBonesAtCurrentFace.back();
nuclear@0: 				newBonesAtCurrentFace.pop_back(); // this also avoids the deallocation which comes with a clear()
nuclear@0: 				if( isBoneUsed[newIndex] ) 
nuclear@0: 					continue;
nuclear@0: 
nuclear@0: 				isBoneUsed[newIndex] = true;
nuclear@0: 				numBones++;
nuclear@0: 			}
nuclear@0: 
nuclear@0: 			// store the face index and the vertex count
nuclear@0: 			subMeshFaces.push_back( a);
nuclear@0: 			numSubMeshVertices += face.mNumIndices;
nuclear@0: 
nuclear@0: 			// remember that this face is handled
nuclear@0: 			isFaceHandled[a] = true;
nuclear@0: 			numFacesHandled++;
nuclear@0: 		}
nuclear@0: 
nuclear@0: 		// create a new mesh to hold this subset of the source mesh
nuclear@0: 		aiMesh* newMesh = new aiMesh;
nuclear@0: 		if( pMesh->mName.length > 0 )
nuclear@0: 			newMesh->mName.Set( boost::str( boost::format( "%s_sub%d") % pMesh->mName.data % poNewMeshes.size()));
nuclear@0: 		newMesh->mMaterialIndex = pMesh->mMaterialIndex;
nuclear@0: 		newMesh->mPrimitiveTypes = pMesh->mPrimitiveTypes;
nuclear@0: 		poNewMeshes.push_back( newMesh);
nuclear@0: 
nuclear@0: 		// create all the arrays for this mesh if the old mesh contained them
nuclear@0: 		newMesh->mNumVertices = numSubMeshVertices;
nuclear@0: 		newMesh->mNumFaces = subMeshFaces.size();
nuclear@0: 		newMesh->mVertices = new aiVector3D[newMesh->mNumVertices];
nuclear@0: 		if( pMesh->HasNormals() )
nuclear@0: 			newMesh->mNormals = new aiVector3D[newMesh->mNumVertices];
nuclear@0: 		if( pMesh->HasTangentsAndBitangents() )
nuclear@0: 		{
nuclear@0: 			newMesh->mTangents = new aiVector3D[newMesh->mNumVertices];
nuclear@0: 			newMesh->mBitangents = new aiVector3D[newMesh->mNumVertices];
nuclear@0: 		}
nuclear@0: 		for( size_t a = 0; a < AI_MAX_NUMBER_OF_TEXTURECOORDS; ++a )
nuclear@0: 		{
nuclear@0: 			if( pMesh->HasTextureCoords( a) )
nuclear@0: 				newMesh->mTextureCoords[a] = new aiVector3D[newMesh->mNumVertices];
nuclear@0: 			newMesh->mNumUVComponents[a] = pMesh->mNumUVComponents[a];
nuclear@0: 		}
nuclear@0: 		for( size_t a = 0; a < AI_MAX_NUMBER_OF_COLOR_SETS; ++a )
nuclear@0: 		{
nuclear@0: 			if( pMesh->HasVertexColors( a) )
nuclear@0: 				newMesh->mColors[a] = new aiColor4D[newMesh->mNumVertices];
nuclear@0: 		}
nuclear@0: 
nuclear@0: 		// and copy over the data, generating faces with linear indices along the way
nuclear@0: 		newMesh->mFaces = new aiFace[subMeshFaces.size()];
nuclear@0: 		size_t nvi = 0; // next vertex index
nuclear@0: 		std::vector<size_t> previousVertexIndices( numSubMeshVertices, std::numeric_limits<size_t>::max()); // per new vertex: its index in the source mesh
nuclear@0: 		for( size_t a = 0; a < subMeshFaces.size(); ++a )
nuclear@0: 		{
nuclear@0: 			const aiFace& srcFace = pMesh->mFaces[subMeshFaces[a]];
nuclear@0: 			aiFace& dstFace = newMesh->mFaces[a];
nuclear@0: 			dstFace.mNumIndices = srcFace.mNumIndices;
nuclear@0: 			dstFace.mIndices = new unsigned int[dstFace.mNumIndices];
nuclear@0: 
nuclear@0: 			// accumulate linearly all the vertices of the source face
nuclear@0: 			for( size_t b = 0; b < dstFace.mNumIndices; ++b )
nuclear@0: 			{
nuclear@0: 				size_t srcIndex = srcFace.mIndices[b];
nuclear@0: 				dstFace.mIndices[b] = nvi;
nuclear@0: 				previousVertexIndices[nvi] = srcIndex;
nuclear@0: 
nuclear@0: 				newMesh->mVertices[nvi] = pMesh->mVertices[srcIndex];
nuclear@0: 				if( pMesh->HasNormals() )
nuclear@0: 					newMesh->mNormals[nvi] = pMesh->mNormals[srcIndex];
nuclear@0: 				if( pMesh->HasTangentsAndBitangents() )
nuclear@0: 				{
nuclear@0: 					newMesh->mTangents[nvi] = pMesh->mTangents[srcIndex];
nuclear@0: 					newMesh->mBitangents[nvi] = pMesh->mBitangents[srcIndex];
nuclear@0: 				}
nuclear@0: 				for( size_t c = 0; c < AI_MAX_NUMBER_OF_TEXTURECOORDS; ++c )
nuclear@0: 				{
nuclear@0: 					if( pMesh->HasTextureCoords( c) )
nuclear@0: 						newMesh->mTextureCoords[c][nvi] = pMesh->mTextureCoords[c][srcIndex];
nuclear@0: 				}
nuclear@0: 				for( size_t c = 0; c < AI_MAX_NUMBER_OF_COLOR_SETS; ++c )
nuclear@0: 				{
nuclear@0: 					if( pMesh->HasVertexColors( c) )
nuclear@0: 						newMesh->mColors[c][nvi] = pMesh->mColors[c][srcIndex];
nuclear@0: 				}
nuclear@0: 
nuclear@0: 				nvi++;
nuclear@0: 			}
nuclear@0: 		}
nuclear@0: 
nuclear@0: 		ai_assert( nvi == numSubMeshVertices );
nuclear@0: 
nuclear@0: 		// Create the bones for the new submesh: first create the bone array
nuclear@0: 		newMesh->mNumBones = 0;
nuclear@0: 		newMesh->mBones = new aiBone*[numBones];
nuclear@0: 
nuclear@0: 		std::vector<size_t> mappedBoneIndex( pMesh->mNumBones, std::numeric_limits<size_t>::max());
nuclear@0: 		for( size_t a = 0; a < pMesh->mNumBones; ++a )
nuclear@0: 		{
nuclear@0: 			if( !isBoneUsed[a] )
nuclear@0: 				continue;
nuclear@0: 
nuclear@0: 			// create the new bone
nuclear@0: 			const aiBone* srcBone = pMesh->mBones[a];
nuclear@0: 			aiBone* dstBone = new aiBone;
nuclear@0: 			mappedBoneIndex[a] = newMesh->mNumBones;
nuclear@0: 			newMesh->mBones[newMesh->mNumBones++] = dstBone;
nuclear@0: 			dstBone->mName = srcBone->mName;
nuclear@0: 			dstBone->mOffsetMatrix = srcBone->mOffsetMatrix;
nuclear@0: 			dstBone->mNumWeights = 0;
nuclear@0: 		}
nuclear@0: 
nuclear@0: 		ai_assert( newMesh->mNumBones == numBones );
nuclear@0: 
nuclear@0: 		// iterate over all new vertices and count which bones affected its old vertex in the source mesh
nuclear@0: 		for( size_t a = 0; a < numSubMeshVertices; ++a )
nuclear@0: 		{
nuclear@0: 			size_t oldIndex = previousVertexIndices[a];
nuclear@0: 			const std::vector<BoneWeight>& bonesOnThisVertex = vertexBones[oldIndex];
nuclear@0: 
nuclear@0: 			for( size_t b = 0; b < bonesOnThisVertex.size(); ++b )
nuclear@0: 			{
nuclear@0: 				size_t newBoneIndex = mappedBoneIndex[ bonesOnThisVertex[b].first ];
nuclear@0: 				if( newBoneIndex != std::numeric_limits<size_t>::max() )
nuclear@0: 					newMesh->mBones[newBoneIndex]->mNumWeights++;
nuclear@0: 			}
nuclear@0: 		}
nuclear@0: 
nuclear@0: 		// allocate all bone weight arrays accordingly
nuclear@0: 		for( size_t a = 0; a < newMesh->mNumBones; ++a )
nuclear@0: 		{
nuclear@0: 			aiBone* bone = newMesh->mBones[a];
nuclear@0: 			ai_assert( bone->mNumWeights > 0 );
nuclear@0: 			bone->mWeights = new aiVertexWeight[bone->mNumWeights];
nuclear@0: 			bone->mNumWeights = 0; // for counting up in the next step
nuclear@0: 		}
nuclear@0: 
nuclear@0: 		// now copy all the bone vertex weights for all the vertices which made it into the new submesh
nuclear@0: 		for( size_t a = 0; a < numSubMeshVertices; ++a)
nuclear@0: 		{
nuclear@0: 			// find the source vertex for it in the source mesh
nuclear@0: 			size_t previousIndex = previousVertexIndices[a];
nuclear@0: 			// these bones were affecting it
nuclear@0: 			const std::vector<BoneWeight>& bonesOnThisVertex = vertexBones[previousIndex];
nuclear@0: 			// all of the bones affecting it should be present in the new submesh, or else
nuclear@0: 			// the face it comprises shouldn't be present
nuclear@0: 			for( size_t b = 0; b < bonesOnThisVertex.size(); ++b)
nuclear@0: 			{
nuclear@0: 				size_t newBoneIndex = mappedBoneIndex[ bonesOnThisVertex[b].first ];
nuclear@0: 				ai_assert( newBoneIndex != std::numeric_limits<size_t>::max() );
nuclear@0: 				aiVertexWeight* dstWeight = newMesh->mBones[newBoneIndex]->mWeights + newMesh->mBones[newBoneIndex]->mNumWeights;
nuclear@0: 				newMesh->mBones[newBoneIndex]->mNumWeights++;
nuclear@0: 
nuclear@0: 				dstWeight->mVertexId = a;
nuclear@0: 				dstWeight->mWeight = bonesOnThisVertex[b].second;
nuclear@0: 			}
nuclear@0: 		}
nuclear@0: 
nuclear@0: 		// I have the strange feeling that this will break apart at some point in time...
nuclear@0: 	}
nuclear@0: }
nuclear@0: 
nuclear@0: // ------------------------------------------------------------------------------------------------
nuclear@0: // Recursively updates the node's mesh list to account for the changed mesh list
nuclear@0: void SplitByBoneCountProcess::UpdateNode( aiNode* pNode) const
nuclear@0: {
nuclear@0: 	// rebuild the node's mesh index list
nuclear@0: 	if( pNode->mNumMeshes > 0 )
nuclear@0: 	{
nuclear@0: 		std::vector<size_t> newMeshList;
nuclear@0: 		for( size_t a = 0; a < pNode->mNumMeshes; ++a)
nuclear@0: 		{
nuclear@0: 			size_t srcIndex = pNode->mMeshes[a];
nuclear@0: 			const std::vector<size_t>& replaceMeshes = mSubMeshIndices[srcIndex];
nuclear@0: 			newMeshList.insert( newMeshList.end(), replaceMeshes.begin(), replaceMeshes.end());
nuclear@0: 		}
nuclear@0: 
nuclear@0: 		delete pNode->mMeshes;
nuclear@0: 		pNode->mNumMeshes = newMeshList.size();
nuclear@0: 		pNode->mMeshes = new unsigned int[pNode->mNumMeshes];
nuclear@0: 		std::copy( newMeshList.begin(), newMeshList.end(), pNode->mMeshes);
nuclear@0: 	}
nuclear@0: 
nuclear@0: 	// do that also recursively for all children
nuclear@0: 	for( size_t a = 0; a < pNode->mNumChildren; ++a )
nuclear@0: 	{
nuclear@0: 		UpdateNode( pNode->mChildren[a]);
nuclear@0: 	}
nuclear@0: }