1/*
2Open Asset Import Library (assimp)
3----------------------------------------------------------------------
4
5Copyright (c) 2006-2017, assimp team
6
7All rights reserved.
8
9Redistribution and use of this software in source and binary forms,
10with or without modification, are permitted provided that the
11following conditions are met:
12
13* Redistributions of source code must retain the above
14 copyright notice, this list of conditions and the
15 following disclaimer.
16
17* Redistributions in binary form must reproduce the above
18 copyright notice, this list of conditions and the
19 following disclaimer in the documentation and/or other
20 materials provided with the distribution.
21
22* Neither the name of the assimp team, nor the names of its
23 contributors may be used to endorse or promote products
24 derived from this software without specific prior
25 written permission of the assimp team.
26
27THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
28"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
29LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
30A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
31OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
32SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
33LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
34DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
35THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
36(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
37OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
38
39----------------------------------------------------------------------
40*/
41
42
43/// @file SplitByBoneCountProcess.cpp
44/// Implementation of the SplitByBoneCount postprocessing step
45
46// internal headers of the post-processing framework
47#include "SplitByBoneCountProcess.h"
48#include <assimp/postprocess.h>
49#include <assimp/DefaultLogger.hpp>
50
51#include <limits>
52#include "TinyFormatter.h"
53
54using namespace Assimp;
55using namespace Assimp::Formatter;
56
57// ------------------------------------------------------------------------------------------------
58// Constructor
59SplitByBoneCountProcess::SplitByBoneCountProcess()
60{
61 // set default, might be overridden by importer config
62 mMaxBoneCount = AI_SBBC_DEFAULT_MAX_BONES;
63}
64
65// ------------------------------------------------------------------------------------------------
66// Destructor
67SplitByBoneCountProcess::~SplitByBoneCountProcess()
68{
69 // nothing to do here
70}
71
72// ------------------------------------------------------------------------------------------------
73// Returns whether the processing step is present in the given flag.
74bool SplitByBoneCountProcess::IsActive( unsigned int pFlags) const
75{
76 return !!(pFlags & aiProcess_SplitByBoneCount);
77}
78
79// ------------------------------------------------------------------------------------------------
80// Updates internal properties
81void SplitByBoneCountProcess::SetupProperties(const Importer* pImp)
82{
83 mMaxBoneCount = pImp->GetPropertyInteger(AI_CONFIG_PP_SBBC_MAX_BONES,AI_SBBC_DEFAULT_MAX_BONES);
84}
85
86// ------------------------------------------------------------------------------------------------
87// Executes the post processing step on the given imported data.
88void SplitByBoneCountProcess::Execute( aiScene* pScene)
89{
90 DefaultLogger::get()->debug("SplitByBoneCountProcess begin");
91
92 // early out
93 bool isNecessary = false;
94 for( unsigned int a = 0; a < pScene->mNumMeshes; ++a)
95 if( pScene->mMeshes[a]->mNumBones > mMaxBoneCount )
96 isNecessary = true;
97
98 if( !isNecessary )
99 {
100 DefaultLogger::get()->debug( format() << "SplitByBoneCountProcess early-out: no meshes with more than " << mMaxBoneCount << " bones." );
101 return;
102 }
103
104 // we need to do something. Let's go.
105 mSubMeshIndices.clear();
106 mSubMeshIndices.resize( pScene->mNumMeshes);
107
108 // build a new array of meshes for the scene
109 std::vector<aiMesh*> meshes;
110
111 for( unsigned int a = 0; a < pScene->mNumMeshes; ++a)
112 {
113 aiMesh* srcMesh = pScene->mMeshes[a];
114
115 std::vector<aiMesh*> newMeshes;
116 SplitMesh( pScene->mMeshes[a], newMeshes);
117
118 // mesh was split
119 if( !newMeshes.empty() )
120 {
121 // store new meshes and indices of the new meshes
122 for( unsigned int b = 0; b < newMeshes.size(); ++b)
123 {
124 mSubMeshIndices[a].push_back( static_cast<unsigned int>(meshes.size()));
125 meshes.push_back( newMeshes[b]);
126 }
127
128 // and destroy the source mesh. It should be completely contained inside the new submeshes
129 delete srcMesh;
130 }
131 else
132 {
133 // Mesh is kept unchanged - store it's new place in the mesh array
134 mSubMeshIndices[a].push_back( static_cast<unsigned int>(meshes.size()));
135 meshes.push_back( srcMesh);
136 }
137 }
138
139 // rebuild the scene's mesh array
140 pScene->mNumMeshes = static_cast<unsigned int>(meshes.size());
141 delete [] pScene->mMeshes;
142 pScene->mMeshes = new aiMesh*[pScene->mNumMeshes];
143 std::copy( meshes.begin(), meshes.end(), pScene->mMeshes);
144
145 // recurse through all nodes and translate the node's mesh indices to fit the new mesh array
146 UpdateNode( pScene->mRootNode);
147
148 DefaultLogger::get()->debug( format() << "SplitByBoneCountProcess end: split " << mSubMeshIndices.size() << " meshes into " << meshes.size() << " submeshes." );
149}
150
151// ------------------------------------------------------------------------------------------------
152// Splits the given mesh by bone count.
153void SplitByBoneCountProcess::SplitMesh( const aiMesh* pMesh, std::vector<aiMesh*>& poNewMeshes) const
154{
155 // skip if not necessary
156 if( pMesh->mNumBones <= mMaxBoneCount )
157 return;
158
159 // necessary optimisation: build a list of all affecting bones for each vertex
160 // TODO: (thom) maybe add a custom allocator here to avoid allocating tens of thousands of small arrays
161 typedef std::pair<unsigned int, float> BoneWeight;
162 std::vector< std::vector<BoneWeight> > vertexBones( pMesh->mNumVertices);
163 for( unsigned int a = 0; a < pMesh->mNumBones; ++a)
164 {
165 const aiBone* bone = pMesh->mBones[a];
166 for( unsigned int b = 0; b < bone->mNumWeights; ++b)
167 vertexBones[ bone->mWeights[b].mVertexId ].push_back( BoneWeight( a, bone->mWeights[b].mWeight));
168 }
169
170 unsigned int numFacesHandled = 0;
171 std::vector<bool> isFaceHandled( pMesh->mNumFaces, false);
172 while( numFacesHandled < pMesh->mNumFaces )
173 {
174 // which bones are used in the current submesh
175 unsigned int numBones = 0;
176 std::vector<bool> isBoneUsed( pMesh->mNumBones, false);
177 // indices of the faces which are going to go into this submesh
178 std::vector<unsigned int> subMeshFaces;
179 subMeshFaces.reserve( pMesh->mNumFaces);
180 // accumulated vertex count of all the faces in this submesh
181 unsigned int numSubMeshVertices = 0;
182 // a small local array of new bones for the current face. State of all used bones for that face
183 // can only be updated AFTER the face is completely analysed. Thanks to imre for the fix.
184 std::vector<unsigned int> newBonesAtCurrentFace;
185
186 // add faces to the new submesh as long as all bones affecting the faces' vertices fit in the limit
187 for( unsigned int a = 0; a < pMesh->mNumFaces; ++a)
188 {
189 // skip if the face is already stored in a submesh
190 if( isFaceHandled[a] )
191 continue;
192
193 const aiFace& face = pMesh->mFaces[a];
194 // check every vertex if its bones would still fit into the current submesh
195 for( unsigned int b = 0; b < face.mNumIndices; ++b )
196 {
197 const std::vector<BoneWeight>& vb = vertexBones[face.mIndices[b]];
198 for( unsigned int c = 0; c < vb.size(); ++c)
199 {
200 unsigned int boneIndex = vb[c].first;
201 // if the bone is already used in this submesh, it's ok
202 if( isBoneUsed[boneIndex] )
203 continue;
204
205 // if it's not used, yet, we would need to add it. Store its bone index
206 if( std::find( newBonesAtCurrentFace.begin(), newBonesAtCurrentFace.end(), boneIndex) == newBonesAtCurrentFace.end() )
207 newBonesAtCurrentFace.push_back( boneIndex);
208 }
209 }
210
211 // leave out the face if the new bones required for this face don't fit the bone count limit anymore
212 if( numBones + newBonesAtCurrentFace.size() > mMaxBoneCount )
213 continue;
214
215 // mark all new bones as necessary
216 while( !newBonesAtCurrentFace.empty() )
217 {
218 unsigned int newIndex = newBonesAtCurrentFace.back();
219 newBonesAtCurrentFace.pop_back(); // this also avoids the deallocation which comes with a clear()
220 if( isBoneUsed[newIndex] )
221 continue;
222
223 isBoneUsed[newIndex] = true;
224 numBones++;
225 }
226
227 // store the face index and the vertex count
228 subMeshFaces.push_back( a);
229 numSubMeshVertices += face.mNumIndices;
230
231 // remember that this face is handled
232 isFaceHandled[a] = true;
233 numFacesHandled++;
234 }
235
236 // create a new mesh to hold this subset of the source mesh
237 aiMesh* newMesh = new aiMesh;
238 if( pMesh->mName.length > 0 )
239 newMesh->mName.Set( format() << pMesh->mName.data << "_sub" << poNewMeshes.size());
240 newMesh->mMaterialIndex = pMesh->mMaterialIndex;
241 newMesh->mPrimitiveTypes = pMesh->mPrimitiveTypes;
242 poNewMeshes.push_back( newMesh);
243
244 // create all the arrays for this mesh if the old mesh contained them
245 newMesh->mNumVertices = numSubMeshVertices;
246 newMesh->mNumFaces = static_cast<unsigned int>(subMeshFaces.size());
247 newMesh->mVertices = new aiVector3D[newMesh->mNumVertices];
248 if( pMesh->HasNormals() )
249 newMesh->mNormals = new aiVector3D[newMesh->mNumVertices];
250 if( pMesh->HasTangentsAndBitangents() )
251 {
252 newMesh->mTangents = new aiVector3D[newMesh->mNumVertices];
253 newMesh->mBitangents = new aiVector3D[newMesh->mNumVertices];
254 }
255 for( unsigned int a = 0; a < AI_MAX_NUMBER_OF_TEXTURECOORDS; ++a )
256 {
257 if( pMesh->HasTextureCoords( a) )
258 newMesh->mTextureCoords[a] = new aiVector3D[newMesh->mNumVertices];
259 newMesh->mNumUVComponents[a] = pMesh->mNumUVComponents[a];
260 }
261 for( unsigned int a = 0; a < AI_MAX_NUMBER_OF_COLOR_SETS; ++a )
262 {
263 if( pMesh->HasVertexColors( a) )
264 newMesh->mColors[a] = new aiColor4D[newMesh->mNumVertices];
265 }
266
267 // and copy over the data, generating faces with linear indices along the way
268 newMesh->mFaces = new aiFace[subMeshFaces.size()];
269 unsigned int nvi = 0; // next vertex index
270 std::vector<unsigned int> previousVertexIndices( numSubMeshVertices, std::numeric_limits<unsigned int>::max()); // per new vertex: its index in the source mesh
271 for( unsigned int a = 0; a < subMeshFaces.size(); ++a )
272 {
273 const aiFace& srcFace = pMesh->mFaces[subMeshFaces[a]];
274 aiFace& dstFace = newMesh->mFaces[a];
275 dstFace.mNumIndices = srcFace.mNumIndices;
276 dstFace.mIndices = new unsigned int[dstFace.mNumIndices];
277
278 // accumulate linearly all the vertices of the source face
279 for( unsigned int b = 0; b < dstFace.mNumIndices; ++b )
280 {
281 unsigned int srcIndex = srcFace.mIndices[b];
282 dstFace.mIndices[b] = nvi;
283 previousVertexIndices[nvi] = srcIndex;
284
285 newMesh->mVertices[nvi] = pMesh->mVertices[srcIndex];
286 if( pMesh->HasNormals() )
287 newMesh->mNormals[nvi] = pMesh->mNormals[srcIndex];
288 if( pMesh->HasTangentsAndBitangents() )
289 {
290 newMesh->mTangents[nvi] = pMesh->mTangents[srcIndex];
291 newMesh->mBitangents[nvi] = pMesh->mBitangents[srcIndex];
292 }
293 for( unsigned int c = 0; c < AI_MAX_NUMBER_OF_TEXTURECOORDS; ++c )
294 {
295 if( pMesh->HasTextureCoords( c) )
296 newMesh->mTextureCoords[c][nvi] = pMesh->mTextureCoords[c][srcIndex];
297 }
298 for( unsigned int c = 0; c < AI_MAX_NUMBER_OF_COLOR_SETS; ++c )
299 {
300 if( pMesh->HasVertexColors( c) )
301 newMesh->mColors[c][nvi] = pMesh->mColors[c][srcIndex];
302 }
303
304 nvi++;
305 }
306 }
307
308 ai_assert( nvi == numSubMeshVertices );
309
310 // Create the bones for the new submesh: first create the bone array
311 newMesh->mNumBones = 0;
312 newMesh->mBones = new aiBone*[numBones];
313
314 std::vector<unsigned int> mappedBoneIndex( pMesh->mNumBones, std::numeric_limits<unsigned int>::max());
315 for( unsigned int a = 0; a < pMesh->mNumBones; ++a )
316 {
317 if( !isBoneUsed[a] )
318 continue;
319
320 // create the new bone
321 const aiBone* srcBone = pMesh->mBones[a];
322 aiBone* dstBone = new aiBone;
323 mappedBoneIndex[a] = newMesh->mNumBones;
324 newMesh->mBones[newMesh->mNumBones++] = dstBone;
325 dstBone->mName = srcBone->mName;
326 dstBone->mOffsetMatrix = srcBone->mOffsetMatrix;
327 dstBone->mNumWeights = 0;
328 }
329
330 ai_assert( newMesh->mNumBones == numBones );
331
332 // iterate over all new vertices and count which bones affected its old vertex in the source mesh
333 for( unsigned int a = 0; a < numSubMeshVertices; ++a )
334 {
335 unsigned int oldIndex = previousVertexIndices[a];
336 const std::vector<BoneWeight>& bonesOnThisVertex = vertexBones[oldIndex];
337
338 for( unsigned int b = 0; b < bonesOnThisVertex.size(); ++b )
339 {
340 unsigned int newBoneIndex = mappedBoneIndex[ bonesOnThisVertex[b].first ];
341 if( newBoneIndex != std::numeric_limits<unsigned int>::max() )
342 newMesh->mBones[newBoneIndex]->mNumWeights++;
343 }
344 }
345
346 // allocate all bone weight arrays accordingly
347 for( unsigned int a = 0; a < newMesh->mNumBones; ++a )
348 {
349 aiBone* bone = newMesh->mBones[a];
350 ai_assert( bone->mNumWeights > 0 );
351 bone->mWeights = new aiVertexWeight[bone->mNumWeights];
352 bone->mNumWeights = 0; // for counting up in the next step
353 }
354
355 // now copy all the bone vertex weights for all the vertices which made it into the new submesh
356 for( unsigned int a = 0; a < numSubMeshVertices; ++a)
357 {
358 // find the source vertex for it in the source mesh
359 unsigned int previousIndex = previousVertexIndices[a];
360 // these bones were affecting it
361 const std::vector<BoneWeight>& bonesOnThisVertex = vertexBones[previousIndex];
362 // all of the bones affecting it should be present in the new submesh, or else
363 // the face it comprises shouldn't be present
364 for( unsigned int b = 0; b < bonesOnThisVertex.size(); ++b)
365 {
366 unsigned int newBoneIndex = mappedBoneIndex[ bonesOnThisVertex[b].first ];
367 ai_assert( newBoneIndex != std::numeric_limits<unsigned int>::max() );
368 aiVertexWeight* dstWeight = newMesh->mBones[newBoneIndex]->mWeights + newMesh->mBones[newBoneIndex]->mNumWeights;
369 newMesh->mBones[newBoneIndex]->mNumWeights++;
370
371 dstWeight->mVertexId = a;
372 dstWeight->mWeight = bonesOnThisVertex[b].second;
373 }
374 }
375
376 // I have the strange feeling that this will break apart at some point in time...
377 }
378}
379
380// ------------------------------------------------------------------------------------------------
381// Recursively updates the node's mesh list to account for the changed mesh list
382void SplitByBoneCountProcess::UpdateNode( aiNode* pNode) const
383{
384 // rebuild the node's mesh index list
385 if( pNode->mNumMeshes > 0 )
386 {
387 std::vector<unsigned int> newMeshList;
388 for( unsigned int a = 0; a < pNode->mNumMeshes; ++a)
389 {
390 unsigned int srcIndex = pNode->mMeshes[a];
391 const std::vector<unsigned int>& replaceMeshes = mSubMeshIndices[srcIndex];
392 newMeshList.insert( newMeshList.end(), replaceMeshes.begin(), replaceMeshes.end());
393 }
394
395 delete pNode->mMeshes;
396 pNode->mNumMeshes = static_cast<unsigned int>(newMeshList.size());
397 pNode->mMeshes = new unsigned int[pNode->mNumMeshes];
398 std::copy( newMeshList.begin(), newMeshList.end(), pNode->mMeshes);
399 }
400
401 // do that also recursively for all children
402 for( unsigned int a = 0; a < pNode->mNumChildren; ++a )
403 {
404 UpdateNode( pNode->mChildren[a]);
405 }
406}
407