1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/libs/assimp/SplitByBoneCountProcess.cpp	Sat Feb 01 19:58:19 2014 +0200
     1.3 @@ -0,0 +1,403 @@
     1.4 +/*
     1.5 +Open Asset Import Library (assimp)
     1.6 +----------------------------------------------------------------------
     1.7 +
     1.8 +Copyright (c) 2006-2012, assimp team
     1.9 +All rights reserved.
    1.10 +
    1.11 +Redistribution and use of this software in source and binary forms, 
    1.12 +with or without modification, are permitted provided that the 
    1.13 +following conditions are met:
    1.14 +
    1.15 +* Redistributions of source code must retain the above
    1.16 +  copyright notice, this list of conditions and the
    1.17 +  following disclaimer.
    1.18 +
    1.19 +* Redistributions in binary form must reproduce the above
    1.20 +  copyright notice, this list of conditions and the
    1.21 +  following disclaimer in the documentation and/or other
    1.22 +  materials provided with the distribution.
    1.23 +
    1.24 +* Neither the name of the assimp team, nor the names of its
    1.25 +  contributors may be used to endorse or promote products
    1.26 +  derived from this software without specific prior
    1.27 +  written permission of the assimp team.
    1.28 +
    1.29 +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 
    1.30 +"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 
    1.31 +LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
    1.32 +A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 
    1.33 +OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
    1.34 +SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 
    1.35 +LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
    1.36 +DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 
    1.37 +THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 
    1.38 +(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 
    1.39 +OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
    1.40 +
    1.41 +----------------------------------------------------------------------
    1.42 +*/
    1.43 +
    1.44 +
    1.45 +/// @file SplitByBoneCountProcess.cpp 
    1.46 +/// Implementation of the SplitByBoneCount postprocessing step
    1.47 +
    1.48 +#include "AssimpPCH.h"
    1.49 +
    1.50 +// internal headers of the post-processing framework
    1.51 +#include "SplitByBoneCountProcess.h"
    1.52 +
    1.53 +#include <limits>
    1.54 +
    1.55 +using namespace Assimp;
    1.56 +
    1.57 +// ------------------------------------------------------------------------------------------------
    1.58 +// Constructor
    1.59 +SplitByBoneCountProcess::SplitByBoneCountProcess()
    1.60 +{
    1.61 +	// set default, might be overriden by importer config
    1.62 +	mMaxBoneCount = AI_SBBC_DEFAULT_MAX_BONES;
    1.63 +}
    1.64 +
    1.65 +// ------------------------------------------------------------------------------------------------
    1.66 +// Destructor
    1.67 +SplitByBoneCountProcess::~SplitByBoneCountProcess()
    1.68 +{
    1.69 +	// nothing to do here
    1.70 +}
    1.71 +
    1.72 +// ------------------------------------------------------------------------------------------------
    1.73 +// Returns whether the processing step is present in the given flag.
    1.74 +bool SplitByBoneCountProcess::IsActive( unsigned int pFlags) const
    1.75 +{
    1.76 +	return !!(pFlags & aiProcess_SplitByBoneCount);
    1.77 +}
    1.78 +
    1.79 +// ------------------------------------------------------------------------------------------------
    1.80 +// Updates internal properties
    1.81 +void SplitByBoneCountProcess::SetupProperties(const Importer* pImp)
    1.82 +{
    1.83 +	mMaxBoneCount = pImp->GetPropertyInteger(AI_CONFIG_PP_SBBC_MAX_BONES,AI_SBBC_DEFAULT_MAX_BONES);
    1.84 +}
    1.85 +
    1.86 +// ------------------------------------------------------------------------------------------------
    1.87 +// Executes the post processing step on the given imported data.
    1.88 +void SplitByBoneCountProcess::Execute( aiScene* pScene)
    1.89 +{
    1.90 +	DefaultLogger::get()->debug("SplitByBoneCountProcess begin");
    1.91 +
    1.92 +	// early out 
    1.93 +	bool isNecessary = false;
    1.94 +	for( size_t a = 0; a < pScene->mNumMeshes; ++a)
    1.95 +		if( pScene->mMeshes[a]->mNumBones > mMaxBoneCount )
    1.96 +			isNecessary = true;
    1.97 +
    1.98 +	if( !isNecessary )
    1.99 +	{
   1.100 +		DefaultLogger::get()->debug( boost::str( boost::format( "SplitByBoneCountProcess early-out: no meshes with more than %d bones.") % mMaxBoneCount));
   1.101 +		return;
   1.102 +	}
   1.103 +
   1.104 +	// we need to do something. Let's go.
   1.105 +	mSubMeshIndices.clear();
   1.106 +	mSubMeshIndices.resize( pScene->mNumMeshes);
   1.107 +
   1.108 +	// build a new array of meshes for the scene
   1.109 +	std::vector<aiMesh*> meshes;
   1.110 +
   1.111 +	for( size_t a = 0; a < pScene->mNumMeshes; ++a)
   1.112 +	{
   1.113 +		aiMesh* srcMesh = pScene->mMeshes[a];
   1.114 +
   1.115 +		std::vector<aiMesh*> newMeshes;
   1.116 +		SplitMesh( pScene->mMeshes[a], newMeshes);
   1.117 +
   1.118 +		// mesh was split
   1.119 +		if( !newMeshes.empty() )
   1.120 +		{
   1.121 +			// store new meshes and indices of the new meshes
   1.122 +			for( size_t b = 0; b < newMeshes.size(); ++b)
   1.123 +			{
   1.124 +				mSubMeshIndices[a].push_back( meshes.size());
   1.125 +				meshes.push_back( newMeshes[b]);
   1.126 +			}
   1.127 +
   1.128 +			// and destroy the source mesh. It should be completely contained inside the new submeshes
   1.129 +			delete srcMesh;
   1.130 +		}
   1.131 +		else
   1.132 +		{
   1.133 +			// Mesh is kept unchanged - store it's new place in the mesh array
   1.134 +			mSubMeshIndices[a].push_back( meshes.size());
   1.135 +			meshes.push_back( srcMesh);
   1.136 +		}
   1.137 +	}
   1.138 +
   1.139 +	// rebuild the scene's mesh array
   1.140 +	pScene->mNumMeshes = meshes.size();
   1.141 +	delete [] pScene->mMeshes;
   1.142 +	pScene->mMeshes = new aiMesh*[pScene->mNumMeshes];
   1.143 +	std::copy( meshes.begin(), meshes.end(), pScene->mMeshes);
   1.144 +
   1.145 +	// recurse through all nodes and translate the node's mesh indices to fit the new mesh array
   1.146 +	UpdateNode( pScene->mRootNode);
   1.147 +
   1.148 +	DefaultLogger::get()->debug( boost::str( boost::format( "SplitByBoneCountProcess end: split %d meshes into %d submeshes.") % mSubMeshIndices.size() % meshes.size()));
   1.149 +}
   1.150 +
   1.151 +// ------------------------------------------------------------------------------------------------
   1.152 +// Splits the given mesh by bone count.
   1.153 +void SplitByBoneCountProcess::SplitMesh( const aiMesh* pMesh, std::vector<aiMesh*>& poNewMeshes) const
   1.154 +{
   1.155 +	// skip if not necessary
   1.156 +	if( pMesh->mNumBones <= mMaxBoneCount )
   1.157 +		return;
   1.158 +
   1.159 +	// necessary optimisation: build a list of all affecting bones for each vertex
   1.160 +	// TODO: (thom) maybe add a custom allocator here to avoid allocating tens of thousands of small arrays
   1.161 +	typedef std::pair<size_t, float> BoneWeight;
   1.162 +	std::vector< std::vector<BoneWeight> > vertexBones( pMesh->mNumVertices);
   1.163 +	for( size_t a = 0; a < pMesh->mNumBones; ++a)
   1.164 +	{
   1.165 +		const aiBone* bone = pMesh->mBones[a];
   1.166 +		for( size_t b = 0; b < bone->mNumWeights; ++b)
   1.167 +			vertexBones[ bone->mWeights[b].mVertexId ].push_back( BoneWeight( a, bone->mWeights[b].mWeight));
   1.168 +	}
   1.169 +
   1.170 +	size_t numFacesHandled = 0;
   1.171 +	std::vector<bool> isFaceHandled( pMesh->mNumFaces, false);
   1.172 +	while( numFacesHandled < pMesh->mNumFaces )
   1.173 +	{
   1.174 +		// which bones are used in the current submesh
   1.175 +		size_t numBones = 0;
   1.176 +		std::vector<bool> isBoneUsed( pMesh->mNumBones, false);
   1.177 +		// indices of the faces which are going to go into this submesh
   1.178 +		std::vector<size_t> subMeshFaces;
   1.179 +		subMeshFaces.reserve( pMesh->mNumFaces);
   1.180 +		// accumulated vertex count of all the faces in this submesh
   1.181 +		size_t numSubMeshVertices = 0;
   1.182 +		// a small local array of new bones for the current face. State of all used bones for that face
   1.183 +		// can only be updated AFTER the face is completely analysed. Thanks to imre for the fix.
   1.184 +		std::vector<size_t> newBonesAtCurrentFace;
   1.185 +
   1.186 +		// add faces to the new submesh as long as all bones affecting the faces' vertices fit in the limit
   1.187 +		for( size_t a = 0; a < pMesh->mNumFaces; ++a)
   1.188 +		{
   1.189 +			// skip if the face is already stored in a submesh
   1.190 +			if( isFaceHandled[a] )
   1.191 +				continue;
   1.192 +
   1.193 +			const aiFace& face = pMesh->mFaces[a];
   1.194 +			// check every vertex if its bones would still fit into the current submesh
   1.195 +			for( size_t b = 0; b < face.mNumIndices; ++b )
   1.196 +			{
   1.197 +				const std::vector<BoneWeight>& vb = vertexBones[face.mIndices[b]];
   1.198 +				for( size_t c = 0; c < vb.size(); ++c)
   1.199 +				{
   1.200 +					size_t boneIndex = vb[c].first;
   1.201 +					// if the bone is already used in this submesh, it's ok
   1.202 +					if( isBoneUsed[boneIndex] )
   1.203 +						continue;
   1.204 +
   1.205 +					// if it's not used, yet, we would need to add it. Store its bone index
   1.206 +					if( std::find( newBonesAtCurrentFace.begin(), newBonesAtCurrentFace.end(), boneIndex) == newBonesAtCurrentFace.end() )
   1.207 +						newBonesAtCurrentFace.push_back( boneIndex);
   1.208 +				}
   1.209 +			}
   1.210 +
   1.211 +			// leave out the face if the new bones required for this face don't fit the bone count limit anymore
   1.212 +			if( numBones + newBonesAtCurrentFace.size() > mMaxBoneCount )
   1.213 +				continue;
   1.214 +
   1.215 +			// mark all new bones as necessary
   1.216 +			while( !newBonesAtCurrentFace.empty() )
   1.217 +			{
   1.218 +				size_t newIndex = newBonesAtCurrentFace.back();
   1.219 +				newBonesAtCurrentFace.pop_back(); // this also avoids the deallocation which comes with a clear()
   1.220 +				if( isBoneUsed[newIndex] ) 
   1.221 +					continue;
   1.222 +
   1.223 +				isBoneUsed[newIndex] = true;
   1.224 +				numBones++;
   1.225 +			}
   1.226 +
   1.227 +			// store the face index and the vertex count
   1.228 +			subMeshFaces.push_back( a);
   1.229 +			numSubMeshVertices += face.mNumIndices;
   1.230 +
   1.231 +			// remember that this face is handled
   1.232 +			isFaceHandled[a] = true;
   1.233 +			numFacesHandled++;
   1.234 +		}
   1.235 +
   1.236 +		// create a new mesh to hold this subset of the source mesh
   1.237 +		aiMesh* newMesh = new aiMesh;
   1.238 +		if( pMesh->mName.length > 0 )
   1.239 +			newMesh->mName.Set( boost::str( boost::format( "%s_sub%d") % pMesh->mName.data % poNewMeshes.size()));
   1.240 +		newMesh->mMaterialIndex = pMesh->mMaterialIndex;
   1.241 +		newMesh->mPrimitiveTypes = pMesh->mPrimitiveTypes;
   1.242 +		poNewMeshes.push_back( newMesh);
   1.243 +
   1.244 +		// create all the arrays for this mesh if the old mesh contained them
   1.245 +		newMesh->mNumVertices = numSubMeshVertices;
   1.246 +		newMesh->mNumFaces = subMeshFaces.size();
   1.247 +		newMesh->mVertices = new aiVector3D[newMesh->mNumVertices];
   1.248 +		if( pMesh->HasNormals() )
   1.249 +			newMesh->mNormals = new aiVector3D[newMesh->mNumVertices];
   1.250 +		if( pMesh->HasTangentsAndBitangents() )
   1.251 +		{
   1.252 +			newMesh->mTangents = new aiVector3D[newMesh->mNumVertices];
   1.253 +			newMesh->mBitangents = new aiVector3D[newMesh->mNumVertices];
   1.254 +		}
   1.255 +		for( size_t a = 0; a < AI_MAX_NUMBER_OF_TEXTURECOORDS; ++a )
   1.256 +		{
   1.257 +			if( pMesh->HasTextureCoords( a) )
   1.258 +				newMesh->mTextureCoords[a] = new aiVector3D[newMesh->mNumVertices];
   1.259 +			newMesh->mNumUVComponents[a] = pMesh->mNumUVComponents[a];
   1.260 +		}
   1.261 +		for( size_t a = 0; a < AI_MAX_NUMBER_OF_COLOR_SETS; ++a )
   1.262 +		{
   1.263 +			if( pMesh->HasVertexColors( a) )
   1.264 +				newMesh->mColors[a] = new aiColor4D[newMesh->mNumVertices];
   1.265 +		}
   1.266 +
   1.267 +		// and copy over the data, generating faces with linear indices along the way
   1.268 +		newMesh->mFaces = new aiFace[subMeshFaces.size()];
   1.269 +		size_t nvi = 0; // next vertex index
   1.270 +		std::vector<size_t> previousVertexIndices( numSubMeshVertices, std::numeric_limits<size_t>::max()); // per new vertex: its index in the source mesh
   1.271 +		for( size_t a = 0; a < subMeshFaces.size(); ++a )
   1.272 +		{
   1.273 +			const aiFace& srcFace = pMesh->mFaces[subMeshFaces[a]];
   1.274 +			aiFace& dstFace = newMesh->mFaces[a];
   1.275 +			dstFace.mNumIndices = srcFace.mNumIndices;
   1.276 +			dstFace.mIndices = new unsigned int[dstFace.mNumIndices];
   1.277 +
   1.278 +			// accumulate linearly all the vertices of the source face
   1.279 +			for( size_t b = 0; b < dstFace.mNumIndices; ++b )
   1.280 +			{
   1.281 +				size_t srcIndex = srcFace.mIndices[b];
   1.282 +				dstFace.mIndices[b] = nvi;
   1.283 +				previousVertexIndices[nvi] = srcIndex;
   1.284 +
   1.285 +				newMesh->mVertices[nvi] = pMesh->mVertices[srcIndex];
   1.286 +				if( pMesh->HasNormals() )
   1.287 +					newMesh->mNormals[nvi] = pMesh->mNormals[srcIndex];
   1.288 +				if( pMesh->HasTangentsAndBitangents() )
   1.289 +				{
   1.290 +					newMesh->mTangents[nvi] = pMesh->mTangents[srcIndex];
   1.291 +					newMesh->mBitangents[nvi] = pMesh->mBitangents[srcIndex];
   1.292 +				}
   1.293 +				for( size_t c = 0; c < AI_MAX_NUMBER_OF_TEXTURECOORDS; ++c )
   1.294 +				{
   1.295 +					if( pMesh->HasTextureCoords( c) )
   1.296 +						newMesh->mTextureCoords[c][nvi] = pMesh->mTextureCoords[c][srcIndex];
   1.297 +				}
   1.298 +				for( size_t c = 0; c < AI_MAX_NUMBER_OF_COLOR_SETS; ++c )
   1.299 +				{
   1.300 +					if( pMesh->HasVertexColors( c) )
   1.301 +						newMesh->mColors[c][nvi] = pMesh->mColors[c][srcIndex];
   1.302 +				}
   1.303 +
   1.304 +				nvi++;
   1.305 +			}
   1.306 +		}
   1.307 +
   1.308 +		ai_assert( nvi == numSubMeshVertices );
   1.309 +
   1.310 +		// Create the bones for the new submesh: first create the bone array
   1.311 +		newMesh->mNumBones = 0;
   1.312 +		newMesh->mBones = new aiBone*[numBones];
   1.313 +
   1.314 +		std::vector<size_t> mappedBoneIndex( pMesh->mNumBones, std::numeric_limits<size_t>::max());
   1.315 +		for( size_t a = 0; a < pMesh->mNumBones; ++a )
   1.316 +		{
   1.317 +			if( !isBoneUsed[a] )
   1.318 +				continue;
   1.319 +
   1.320 +			// create the new bone
   1.321 +			const aiBone* srcBone = pMesh->mBones[a];
   1.322 +			aiBone* dstBone = new aiBone;
   1.323 +			mappedBoneIndex[a] = newMesh->mNumBones;
   1.324 +			newMesh->mBones[newMesh->mNumBones++] = dstBone;
   1.325 +			dstBone->mName = srcBone->mName;
   1.326 +			dstBone->mOffsetMatrix = srcBone->mOffsetMatrix;
   1.327 +			dstBone->mNumWeights = 0;
   1.328 +		}
   1.329 +
   1.330 +		ai_assert( newMesh->mNumBones == numBones );
   1.331 +
   1.332 +		// iterate over all new vertices and count which bones affected its old vertex in the source mesh
   1.333 +		for( size_t a = 0; a < numSubMeshVertices; ++a )
   1.334 +		{
   1.335 +			size_t oldIndex = previousVertexIndices[a];
   1.336 +			const std::vector<BoneWeight>& bonesOnThisVertex = vertexBones[oldIndex];
   1.337 +
   1.338 +			for( size_t b = 0; b < bonesOnThisVertex.size(); ++b )
   1.339 +			{
   1.340 +				size_t newBoneIndex = mappedBoneIndex[ bonesOnThisVertex[b].first ];
   1.341 +				if( newBoneIndex != std::numeric_limits<size_t>::max() )
   1.342 +					newMesh->mBones[newBoneIndex]->mNumWeights++;
   1.343 +			}
   1.344 +		}
   1.345 +
   1.346 +		// allocate all bone weight arrays accordingly
   1.347 +		for( size_t a = 0; a < newMesh->mNumBones; ++a )
   1.348 +		{
   1.349 +			aiBone* bone = newMesh->mBones[a];
   1.350 +			ai_assert( bone->mNumWeights > 0 );
   1.351 +			bone->mWeights = new aiVertexWeight[bone->mNumWeights];
   1.352 +			bone->mNumWeights = 0; // for counting up in the next step
   1.353 +		}
   1.354 +
   1.355 +		// now copy all the bone vertex weights for all the vertices which made it into the new submesh
   1.356 +		for( size_t a = 0; a < numSubMeshVertices; ++a)
   1.357 +		{
   1.358 +			// find the source vertex for it in the source mesh
   1.359 +			size_t previousIndex = previousVertexIndices[a];
   1.360 +			// these bones were affecting it
   1.361 +			const std::vector<BoneWeight>& bonesOnThisVertex = vertexBones[previousIndex];
   1.362 +			// all of the bones affecting it should be present in the new submesh, or else
   1.363 +			// the face it comprises shouldn't be present
   1.364 +			for( size_t b = 0; b < bonesOnThisVertex.size(); ++b)
   1.365 +			{
   1.366 +				size_t newBoneIndex = mappedBoneIndex[ bonesOnThisVertex[b].first ];
   1.367 +				ai_assert( newBoneIndex != std::numeric_limits<size_t>::max() );
   1.368 +				aiVertexWeight* dstWeight = newMesh->mBones[newBoneIndex]->mWeights + newMesh->mBones[newBoneIndex]->mNumWeights;
   1.369 +				newMesh->mBones[newBoneIndex]->mNumWeights++;
   1.370 +
   1.371 +				dstWeight->mVertexId = a;
   1.372 +				dstWeight->mWeight = bonesOnThisVertex[b].second;
   1.373 +			}
   1.374 +		}
   1.375 +
   1.376 +		// I have the strange feeling that this will break apart at some point in time...
   1.377 +	}
   1.378 +}
   1.379 +
   1.380 +// ------------------------------------------------------------------------------------------------
   1.381 +// Recursively updates the node's mesh list to account for the changed mesh list
   1.382 +void SplitByBoneCountProcess::UpdateNode( aiNode* pNode) const
   1.383 +{
   1.384 +	// rebuild the node's mesh index list
   1.385 +	if( pNode->mNumMeshes > 0 )
   1.386 +	{
   1.387 +		std::vector<size_t> newMeshList;
   1.388 +		for( size_t a = 0; a < pNode->mNumMeshes; ++a)
   1.389 +		{
   1.390 +			size_t srcIndex = pNode->mMeshes[a];
   1.391 +			const std::vector<size_t>& replaceMeshes = mSubMeshIndices[srcIndex];
   1.392 +			newMeshList.insert( newMeshList.end(), replaceMeshes.begin(), replaceMeshes.end());
   1.393 +		}
   1.394 +
   1.395 +		delete pNode->mMeshes;
   1.396 +		pNode->mNumMeshes = newMeshList.size();
   1.397 +		pNode->mMeshes = new unsigned int[pNode->mNumMeshes];
   1.398 +		std::copy( newMeshList.begin(), newMeshList.end(), pNode->mMeshes);
   1.399 +	}
   1.400 +
   1.401 +	// do that also recursively for all children
   1.402 +	for( size_t a = 0; a < pNode->mNumChildren; ++a )
   1.403 +	{
   1.404 +		UpdateNode( pNode->mChildren[a]);
   1.405 +	}
   1.406 +}