1/*
2---------------------------------------------------------------------------
3Open Asset Import Library (assimp)
4---------------------------------------------------------------------------
5
6Copyright (c) 2006-2017, assimp team
7
8
9All rights reserved.
10
11Redistribution and use of this software in source and binary forms,
12with or without modification, are permitted provided that the following
13conditions are met:
14
15* Redistributions of source code must retain the above
16 copyright notice, this list of conditions and the
17 following disclaimer.
18
19* Redistributions in binary form must reproduce the above
20 copyright notice, this list of conditions and the
21 following disclaimer in the documentation and/or other
22 materials provided with the distribution.
23
24* Neither the name of the assimp team, nor the names of its
25 contributors may be used to endorse or promote products
26 derived from this software without specific prior
27 written permission of the assimp team.
28
29THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
30"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
31LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
32A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
33OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
34SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
35LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
36DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
37THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
38(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
39OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
40---------------------------------------------------------------------------
41*/
42
43/** @file Implementation of the post processing step to join identical vertices
44 * for all imported meshes
45 */
46
47
48#ifndef ASSIMP_BUILD_NO_JOINVERTICES_PROCESS
49
50#include "JoinVerticesProcess.h"
51#include "ProcessHelper.h"
52#include "Vertex.h"
53#include "TinyFormatter.h"
54#include <stdio.h>
55
56using namespace Assimp;
57// ------------------------------------------------------------------------------------------------
58// Constructor to be privately used by Importer
59JoinVerticesProcess::JoinVerticesProcess()
60{
61 // nothing to do here
62}
63
64// ------------------------------------------------------------------------------------------------
65// Destructor, private as well
66JoinVerticesProcess::~JoinVerticesProcess()
67{
68 // nothing to do here
69}
70
71// ------------------------------------------------------------------------------------------------
72// Returns whether the processing step is present in the given flag field.
73bool JoinVerticesProcess::IsActive( unsigned int pFlags) const
74{
75 return (pFlags & aiProcess_JoinIdenticalVertices) != 0;
76}
77// ------------------------------------------------------------------------------------------------
78// Executes the post processing step on the given imported data.
79void JoinVerticesProcess::Execute( aiScene* pScene)
80{
81 DefaultLogger::get()->debug("JoinVerticesProcess begin");
82
83 // get the total number of vertices BEFORE the step is executed
84 int iNumOldVertices = 0;
85 if (!DefaultLogger::isNullLogger()) {
86 for( unsigned int a = 0; a < pScene->mNumMeshes; a++) {
87 iNumOldVertices += pScene->mMeshes[a]->mNumVertices;
88 }
89 }
90
91 // execute the step
92 int iNumVertices = 0;
93 for( unsigned int a = 0; a < pScene->mNumMeshes; a++)
94 iNumVertices += ProcessMesh( pScene->mMeshes[a],a);
95
96 // if logging is active, print detailed statistics
97 if (!DefaultLogger::isNullLogger())
98 {
99 if (iNumOldVertices == iNumVertices)
100 {
101 DefaultLogger::get()->debug("JoinVerticesProcess finished ");
102 } else
103 {
104 char szBuff[128]; // should be sufficiently large in every case
105 ::ai_snprintf(szBuff,128,"JoinVerticesProcess finished | Verts in: %i out: %i | ~%.1f%%",
106 iNumOldVertices,
107 iNumVertices,
108 ((iNumOldVertices - iNumVertices) / (float)iNumOldVertices) * 100.f);
109 DefaultLogger::get()->info(szBuff);
110 }
111 }
112
113 pScene->mFlags |= AI_SCENE_FLAGS_NON_VERBOSE_FORMAT;
114}
115
116// ------------------------------------------------------------------------------------------------
117// Unites identical vertices in the given mesh
118int JoinVerticesProcess::ProcessMesh( aiMesh* pMesh, unsigned int meshIndex)
119{
120 static_assert( AI_MAX_NUMBER_OF_COLOR_SETS == 8, "AI_MAX_NUMBER_OF_COLOR_SETS == 8");
121 static_assert( AI_MAX_NUMBER_OF_TEXTURECOORDS == 8, "AI_MAX_NUMBER_OF_TEXTURECOORDS == 8");
122
123 // Return early if we don't have any positions
124 if (!pMesh->HasPositions() || !pMesh->HasFaces()) {
125 return 0;
126 }
127
128 // We'll never have more vertices afterwards.
129 std::vector<Vertex> uniqueVertices;
130 uniqueVertices.reserve( pMesh->mNumVertices);
131
132 // For each vertex the index of the vertex it was replaced by.
133 // Since the maximal number of vertices is 2^31-1, the most significand bit can be used to mark
134 // whether a new vertex was created for the index (true) or if it was replaced by an existing
135 // unique vertex (false). This saves an additional std::vector<bool> and greatly enhances
136 // branching performance.
137 static_assert(AI_MAX_VERTICES == 0x7fffffff, "AI_MAX_VERTICES == 0x7fffffff");
138 std::vector<unsigned int> replaceIndex( pMesh->mNumVertices, 0xffffffff);
139
140 // A little helper to find locally close vertices faster.
141 // Try to reuse the lookup table from the last step.
142 const static float epsilon = 1e-5f;
143 // float posEpsilonSqr;
144 SpatialSort* vertexFinder = NULL;
145 SpatialSort _vertexFinder;
146
147 typedef std::pair<SpatialSort,float> SpatPair;
148 if (shared) {
149 std::vector<SpatPair >* avf;
150 shared->GetProperty(AI_SPP_SPATIAL_SORT,avf);
151 if (avf) {
152 SpatPair& blubb = (*avf)[meshIndex];
153 vertexFinder = &blubb.first;
154 // posEpsilonSqr = blubb.second;
155 }
156 }
157 if (!vertexFinder) {
158 // bad, need to compute it.
159 _vertexFinder.Fill(pMesh->mVertices, pMesh->mNumVertices, sizeof( aiVector3D));
160 vertexFinder = &_vertexFinder;
161 // posEpsilonSqr = ComputePositionEpsilon(pMesh);
162 }
163
164 // Squared because we check against squared length of the vector difference
165 static const float squareEpsilon = epsilon * epsilon;
166
167 // Again, better waste some bytes than a realloc ...
168 std::vector<unsigned int> verticesFound;
169 verticesFound.reserve(10);
170
171 // Run an optimized code path if we don't have multiple UVs or vertex colors.
172 // This should yield false in more than 99% of all imports ...
173 const bool complex = ( pMesh->GetNumColorChannels() > 0 || pMesh->GetNumUVChannels() > 1);
174
175 // Now check each vertex if it brings something new to the table
176 for( unsigned int a = 0; a < pMesh->mNumVertices; a++) {
177 // collect the vertex data
178 Vertex v(pMesh,a);
179
180 // collect all vertices that are close enough to the given position
181 vertexFinder->FindIdenticalPositions( v.position, verticesFound);
182 unsigned int matchIndex = 0xffffffff;
183
184 // check all unique vertices close to the position if this vertex is already present among them
185 for( unsigned int b = 0; b < verticesFound.size(); b++) {
186
187 const unsigned int vidx = verticesFound[b];
188 const unsigned int uidx = replaceIndex[ vidx];
189 if( uidx & 0x80000000)
190 continue;
191
192 const Vertex& uv = uniqueVertices[ uidx];
193 // Position mismatch is impossible - the vertex finder already discarded all non-matching positions
194
195 // We just test the other attributes even if they're not present in the mesh.
196 // In this case they're initialized to 0 so the comparison succeeds.
197 // By this method the non-present attributes are effectively ignored in the comparison.
198 if( (uv.normal - v.normal).SquareLength() > squareEpsilon)
199 continue;
200 if( (uv.texcoords[0] - v.texcoords[0]).SquareLength() > squareEpsilon)
201 continue;
202 if( (uv.tangent - v.tangent).SquareLength() > squareEpsilon)
203 continue;
204 if( (uv.bitangent - v.bitangent).SquareLength() > squareEpsilon)
205 continue;
206
207 // Usually we won't have vertex colors or multiple UVs, so we can skip from here
208 // Actually this increases runtime performance slightly, at least if branch
209 // prediction is on our side.
210 if (complex){
211 // manually unrolled because continue wouldn't work as desired in an inner loop,
212 // also because some compilers seem to fail the task. Colors and UV coords
213 // are interleaved since the higher entries are most likely to be
214 // zero and thus useless. By interleaving the arrays, vertices are,
215 // on average, rejected earlier.
216
217 if( (uv.texcoords[1] - v.texcoords[1]).SquareLength() > squareEpsilon)
218 continue;
219 if( GetColorDifference( uv.colors[0], v.colors[0]) > squareEpsilon)
220 continue;
221
222 if( (uv.texcoords[2] - v.texcoords[2]).SquareLength() > squareEpsilon)
223 continue;
224 if( GetColorDifference( uv.colors[1], v.colors[1]) > squareEpsilon)
225 continue;
226
227 if( (uv.texcoords[3] - v.texcoords[3]).SquareLength() > squareEpsilon)
228 continue;
229 if( GetColorDifference( uv.colors[2], v.colors[2]) > squareEpsilon)
230 continue;
231
232 if( (uv.texcoords[4] - v.texcoords[4]).SquareLength() > squareEpsilon)
233 continue;
234 if( GetColorDifference( uv.colors[3], v.colors[3]) > squareEpsilon)
235 continue;
236
237 if( (uv.texcoords[5] - v.texcoords[5]).SquareLength() > squareEpsilon)
238 continue;
239 if( GetColorDifference( uv.colors[4], v.colors[4]) > squareEpsilon)
240 continue;
241
242 if( (uv.texcoords[6] - v.texcoords[6]).SquareLength() > squareEpsilon)
243 continue;
244 if( GetColorDifference( uv.colors[5], v.colors[5]) > squareEpsilon)
245 continue;
246
247 if( (uv.texcoords[7] - v.texcoords[7]).SquareLength() > squareEpsilon)
248 continue;
249 if( GetColorDifference( uv.colors[6], v.colors[6]) > squareEpsilon)
250 continue;
251
252 if( GetColorDifference( uv.colors[7], v.colors[7]) > squareEpsilon)
253 continue;
254 }
255
256 // we're still here -> this vertex perfectly matches our given vertex
257 matchIndex = uidx;
258 break;
259 }
260
261 // found a replacement vertex among the uniques?
262 if( matchIndex != 0xffffffff)
263 {
264 // store where to found the matching unique vertex
265 replaceIndex[a] = matchIndex | 0x80000000;
266 }
267 else
268 {
269 // no unique vertex matches it up to now -> so add it
270 replaceIndex[a] = (unsigned int)uniqueVertices.size();
271 uniqueVertices.push_back( v);
272 }
273 }
274
275 if (!DefaultLogger::isNullLogger() && DefaultLogger::get()->getLogSeverity() == Logger::VERBOSE) {
276 DefaultLogger::get()->debug((Formatter::format(),
277 "Mesh ",meshIndex,
278 " (",
279 (pMesh->mName.length ? pMesh->mName.data : "unnamed"),
280 ") | Verts in: ",pMesh->mNumVertices,
281 " out: ",
282 uniqueVertices.size(),
283 " | ~",
284 ((pMesh->mNumVertices - uniqueVertices.size()) / (float)pMesh->mNumVertices) * 100.f,
285 "%"
286 ));
287 }
288
289 // replace vertex data with the unique data sets
290 pMesh->mNumVertices = (unsigned int)uniqueVertices.size();
291
292 // ----------------------------------------------------------------------------
293 // NOTE - we're *not* calling Vertex::SortBack() because it would check for
294 // presence of every single vertex component once PER VERTEX. And our CPU
295 // dislikes branches, even if they're easily predictable.
296 // ----------------------------------------------------------------------------
297
298 // Position
299 delete [] pMesh->mVertices;
300 pMesh->mVertices = new aiVector3D[pMesh->mNumVertices];
301 for( unsigned int a = 0; a < pMesh->mNumVertices; a++)
302 pMesh->mVertices[a] = uniqueVertices[a].position;
303
304 // Normals, if present
305 if( pMesh->mNormals)
306 {
307 delete [] pMesh->mNormals;
308 pMesh->mNormals = new aiVector3D[pMesh->mNumVertices];
309 for( unsigned int a = 0; a < pMesh->mNumVertices; a++) {
310 pMesh->mNormals[a] = uniqueVertices[a].normal;
311 }
312 }
313 // Tangents, if present
314 if( pMesh->mTangents)
315 {
316 delete [] pMesh->mTangents;
317 pMesh->mTangents = new aiVector3D[pMesh->mNumVertices];
318 for( unsigned int a = 0; a < pMesh->mNumVertices; a++) {
319 pMesh->mTangents[a] = uniqueVertices[a].tangent;
320 }
321 }
322 // Bitangents as well
323 if( pMesh->mBitangents)
324 {
325 delete [] pMesh->mBitangents;
326 pMesh->mBitangents = new aiVector3D[pMesh->mNumVertices];
327 for( unsigned int a = 0; a < pMesh->mNumVertices; a++) {
328 pMesh->mBitangents[a] = uniqueVertices[a].bitangent;
329 }
330 }
331 // Vertex colors
332 for( unsigned int a = 0; pMesh->HasVertexColors(a); a++)
333 {
334 delete [] pMesh->mColors[a];
335 pMesh->mColors[a] = new aiColor4D[pMesh->mNumVertices];
336 for( unsigned int b = 0; b < pMesh->mNumVertices; b++) {
337 pMesh->mColors[a][b] = uniqueVertices[b].colors[a];
338 }
339 }
340 // Texture coords
341 for( unsigned int a = 0; pMesh->HasTextureCoords(a); a++)
342 {
343 delete [] pMesh->mTextureCoords[a];
344 pMesh->mTextureCoords[a] = new aiVector3D[pMesh->mNumVertices];
345 for( unsigned int b = 0; b < pMesh->mNumVertices; b++) {
346 pMesh->mTextureCoords[a][b] = uniqueVertices[b].texcoords[a];
347 }
348 }
349
350 // adjust the indices in all faces
351 for( unsigned int a = 0; a < pMesh->mNumFaces; a++)
352 {
353 aiFace& face = pMesh->mFaces[a];
354 for( unsigned int b = 0; b < face.mNumIndices; b++) {
355 face.mIndices[b] = replaceIndex[face.mIndices[b]] & ~0x80000000;
356 }
357 }
358
359 // adjust bone vertex weights.
360 for( int a = 0; a < (int)pMesh->mNumBones; a++) {
361 aiBone* bone = pMesh->mBones[a];
362 std::vector<aiVertexWeight> newWeights;
363 newWeights.reserve( bone->mNumWeights);
364
365 if ( NULL != bone->mWeights ) {
366 for ( unsigned int b = 0; b < bone->mNumWeights; b++ ) {
367 const aiVertexWeight& ow = bone->mWeights[ b ];
368 // if the vertex is a unique one, translate it
369 if ( !( replaceIndex[ ow.mVertexId ] & 0x80000000 ) ) {
370 aiVertexWeight nw;
371 nw.mVertexId = replaceIndex[ ow.mVertexId ];
372 nw.mWeight = ow.mWeight;
373 newWeights.push_back( nw );
374 }
375 }
376 } else {
377 DefaultLogger::get()->error( "X-Export: aiBone shall contain weights, but pointer to them is NULL." );
378 }
379
380 if (newWeights.size() > 0) {
381 // kill the old and replace them with the translated weights
382 delete [] bone->mWeights;
383 bone->mNumWeights = (unsigned int)newWeights.size();
384
385 bone->mWeights = new aiVertexWeight[bone->mNumWeights];
386 memcpy( bone->mWeights, &newWeights[0], bone->mNumWeights * sizeof( aiVertexWeight));
387 }
388 else {
389
390 /* NOTE:
391 *
392 * In the algorithm above we're assuming that there are no vertices
393 * with a different bone weight setup at the same position. That wouldn't
394 * make sense, but it is not absolutely impossible. SkeletonMeshBuilder
395 * for example generates such input data if two skeleton points
396 * share the same position. Again this doesn't make sense but is
397 * reality for some model formats (MD5 for example uses these special
398 * nodes as attachment tags for its weapons).
399 *
400 * Then it is possible that a bone has no weights anymore .... as a quick
401 * workaround, we're just removing these bones. If they're animated,
402 * model geometry might be modified but at least there's no risk of a crash.
403 */
404 delete bone;
405 --pMesh->mNumBones;
406 for (unsigned int n = a; n < pMesh->mNumBones; ++n) {
407 pMesh->mBones[n] = pMesh->mBones[n+1];
408 }
409
410 --a;
411 DefaultLogger::get()->warn("Removing bone -> no weights remaining");
412 }
413 }
414 return pMesh->mNumVertices;
415}
416
417#endif // !! ASSIMP_BUILD_NO_JOINVERTICES_PROCESS
418