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