Coverage Report

Created: 2026-11-12 07:30

next uncovered line (L), next uncovered region (R), next uncovered branch (B)
/src/assimp/code/PostProcessing/JoinVerticesProcess.cpp
Line
Count
Source
1
/*
2
---------------------------------------------------------------------------
3
Open Asset Import Library (assimp)
4
---------------------------------------------------------------------------
5
6
Copyright (c) 2006-2026, assimp team
7
8
All rights reserved.
9
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:
13
14
* Redistributions of source code must retain the above
15
  copyright notice, this list of conditions and the
16
  following disclaimer.
17
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.
22
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.
27
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
*/
41
42
/** @file Implementation of the post processing step to join identical vertices
43
 * for all imported meshes
44
 */
45
46
#ifndef ASSIMP_BUILD_NO_JOINVERTICES_PROCESS
47
48
#include "JoinVerticesProcess.h"
49
#include "ProcessHelper.h"
50
#include <assimp/Vertex.h>
51
#include <assimp/TinyFormatter.h>
52
53
#include <stdio.h>
54
#include <unordered_set>
55
#include <unordered_map>
56
#include <memory>
57
#include <map>
58
59
using namespace Assimp;
60
61
// ------------------------------------------------------------------------------------------------
62
// Returns whether the processing step is present in the given flag field.
63
120k
bool JoinVerticesProcess::IsActive( unsigned int pFlags) const {
64
120k
    return (pFlags & aiProcess_JoinIdenticalVertices) != 0;
65
120k
}
66
// ------------------------------------------------------------------------------------------------
67
// Executes the post processing step on the given imported data.
68
52.8k
void JoinVerticesProcess::Execute( aiScene* pScene) {
69
52.8k
    ASSIMP_LOG_DEBUG("JoinVerticesProcess begin");
70
71
    // get the total number of vertices BEFORE the step is executed
72
52.8k
    int iNumOldVertices = 0;
73
52.8k
    if (!DefaultLogger::isNullLogger()) {
74
0
        for( unsigned int a = 0; a < pScene->mNumMeshes; a++)   {
75
0
            iNumOldVertices +=  pScene->mMeshes[a]->mNumVertices;
76
0
        }
77
0
    }
78
79
    // execute the step
80
52.8k
    int iNumVertices = 0;
81
738k
    for( unsigned int a = 0; a < pScene->mNumMeshes; a++) {
82
685k
        iNumVertices += ProcessMesh( pScene->mMeshes[a],a);
83
685k
    }
84
85
52.8k
    pScene->mFlags |= AI_SCENE_FLAGS_NON_VERBOSE_FORMAT;
86
87
    // if logging is active, print detailed statistics
88
52.8k
    if (!DefaultLogger::isNullLogger()) {
89
0
        if (iNumOldVertices == iNumVertices) {
90
0
            ASSIMP_LOG_DEBUG("JoinVerticesProcess finished ");
91
0
            return;
92
0
        }
93
94
        // Show statistics
95
0
        ASSIMP_LOG_INFO("JoinVerticesProcess finished | Verts in: ", iNumOldVertices,
96
0
            " out: ", iNumVertices, " | ~",
97
0
            ((iNumOldVertices - iNumVertices) / (float)iNumOldVertices) * 100.f );
98
0
    }
99
52.8k
}
100
101
namespace {
102
103
struct CompareVerticesAlmostEqual {
104
141M
    bool operator () (const Vertex & a, const Vertex & b) const {
105
141M
        static const float epsilon = 1e-5f;
106
141M
        static const float squareEpsilon = epsilon * epsilon;
107
108
141M
        if ((a.position - b.position).SquareLength() > squareEpsilon) {
109
1.61k
            return false;
110
1.61k
        }
111
112
        // We just test the other attributes even if they're not present in the mesh.
113
        // In this case they're initialized to 0 so the comparison succeeds.
114
        // By this method the non-present attributes are effectively ignored in the comparison.
115
116
141M
        if ((a.normal - b.normal).SquareLength() > squareEpsilon) {
117
70.5M
            return false;
118
70.5M
        }
119
120
70.4M
        if ((a.tangent - b.tangent).SquareLength() > squareEpsilon) {
121
3.60M
            return false;
122
3.60M
        }
123
124
66.8M
        if ((a.bitangent - b.bitangent).SquareLength() > squareEpsilon) {
125
69.9k
            return false;
126
69.9k
        }
127
128
599M
        for (uint32_t i = 0; i < AI_MAX_NUMBER_OF_TEXTURECOORDS; i ++) {
129
532M
            if ((a.texcoords[i] - b.texcoords[i]).SquareLength() > squareEpsilon) {
130
284k
                return false;
131
284k
            }
132
532M
        }
133
134
578M
        for (uint32_t i = 0; i < AI_MAX_NUMBER_OF_COLOR_SETS; i ++) {
135
514M
            if (GetColorDifference(a.colors[i], b.colors[i]) > squareEpsilon) {
136
2.59M
                return false;
137
2.59M
            }
138
514M
        }
139
140
        // If reached this point, they are ~equal
141
63.9M
        return true;
142
66.5M
    }
143
};
144
145
struct HashVertex {
146
261M
    inline void hash_combine(std::size_t& seed, const ai_real& v) const {
147
261M
        std::hash<ai_real> hasher;
148
261M
        seed ^= hasher(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
149
261M
    }
150
151
87.1M
    size_t operator () (const Vertex & v) const {
152
87.1M
        size_t hash = 0;
153
154
87.1M
        hash_combine(hash, v.position.x);
155
87.1M
        hash_combine(hash, v.position.y);
156
87.1M
        hash_combine(hash, v.position.z);
157
158
87.1M
        return hash;
159
87.1M
    }
160
};
161
162
template<class XMesh>
163
685k
void updateXMeshVertices(XMesh *pMesh, std::vector<int> &uniqueVertices) {
164
    // replace vertex data with the unique data sets
165
685k
    pMesh->mNumVertices = (unsigned int)uniqueVertices.size();
166
167
    // ----------------------------------------------------------------------------
168
    // NOTE - we're *not* calling Vertex::SortBack() because it would check for
169
    // presence of every single vertex component once PER VERTEX. And our CPU
170
    // dislikes branches, even if they're easily predictable.
171
    // ----------------------------------------------------------------------------
172
173
    // Position, if present (check made for aiAnimMesh)
174
685k
    if (pMesh->mVertices) {
175
685k
        std::unique_ptr<aiVector3D[]> oldVertices(pMesh->mVertices);
176
685k
        pMesh->mVertices = new aiVector3D[pMesh->mNumVertices];
177
12.6M
        for (unsigned int a = 0; a < pMesh->mNumVertices; a++)
178
11.9M
            pMesh->mVertices[a] = oldVertices[uniqueVertices[a]];
179
685k
    }
180
181
    // Normals, if present
182
685k
    if (pMesh->mNormals) {
183
467k
        std::unique_ptr<aiVector3D[]> oldNormals(pMesh->mNormals);
184
467k
        pMesh->mNormals = new aiVector3D[pMesh->mNumVertices];
185
11.9M
        for (unsigned int a = 0; a < pMesh->mNumVertices; a++)
186
11.4M
            pMesh->mNormals[a] = oldNormals[uniqueVertices[a]];
187
467k
    }
188
    // Tangents, if present
189
685k
    if (pMesh->mTangents) {
190
26.4k
        std::unique_ptr<aiVector3D[]> oldTangents(pMesh->mTangents);
191
26.4k
        pMesh->mTangents = new aiVector3D[pMesh->mNumVertices];
192
2.35M
        for (unsigned int a = 0; a < pMesh->mNumVertices; a++)
193
2.33M
            pMesh->mTangents[a] = oldTangents[uniqueVertices[a]];
194
26.4k
    }
195
    // Bitangents as well
196
685k
    if (pMesh->mBitangents) {
197
26.4k
        std::unique_ptr<aiVector3D[]> oldBitangents(pMesh->mBitangents);
198
26.4k
        pMesh->mBitangents = new aiVector3D[pMesh->mNumVertices];
199
2.35M
        for (unsigned int a = 0; a < pMesh->mNumVertices; a++)
200
2.33M
            pMesh->mBitangents[a] = oldBitangents[uniqueVertices[a]];
201
26.4k
    }
202
    // Vertex colors
203
835k
    for (unsigned int a = 0; pMesh->HasVertexColors(a); a++) {
204
149k
        std::unique_ptr<aiColor4D[]> oldColors(pMesh->mColors[a]);
205
149k
        pMesh->mColors[a] = new aiColor4D[pMesh->mNumVertices];
206
1.27M
        for (unsigned int b = 0; b < pMesh->mNumVertices; b++)
207
1.12M
            pMesh->mColors[a][b] = oldColors[uniqueVertices[b]];
208
149k
    }
209
    // Texture coords
210
718k
    for (unsigned int a = 0; pMesh->HasTextureCoords(a); a++) {
211
33.2k
        std::unique_ptr<aiVector3D[]> oldTextureCoords(pMesh->mTextureCoords[a]);
212
33.2k
        pMesh->mTextureCoords[a] = new aiVector3D[pMesh->mNumVertices];
213
2.46M
        for (unsigned int b = 0; b < pMesh->mNumVertices; b++)
214
2.42M
            pMesh->mTextureCoords[a][b] = oldTextureCoords[uniqueVertices[b]];
215
33.2k
    }
216
685k
}
JoinVerticesProcess.cpp:void (anonymous namespace)::updateXMeshVertices<aiMesh>(aiMesh*, std::__1::vector<int, std::__1::allocator<int> >&)
Line
Count
Source
163
685k
void updateXMeshVertices(XMesh *pMesh, std::vector<int> &uniqueVertices) {
164
    // replace vertex data with the unique data sets
165
685k
    pMesh->mNumVertices = (unsigned int)uniqueVertices.size();
166
167
    // ----------------------------------------------------------------------------
168
    // NOTE - we're *not* calling Vertex::SortBack() because it would check for
169
    // presence of every single vertex component once PER VERTEX. And our CPU
170
    // dislikes branches, even if they're easily predictable.
171
    // ----------------------------------------------------------------------------
172
173
    // Position, if present (check made for aiAnimMesh)
174
685k
    if (pMesh->mVertices) {
175
685k
        std::unique_ptr<aiVector3D[]> oldVertices(pMesh->mVertices);
176
685k
        pMesh->mVertices = new aiVector3D[pMesh->mNumVertices];
177
12.6M
        for (unsigned int a = 0; a < pMesh->mNumVertices; a++)
178
11.9M
            pMesh->mVertices[a] = oldVertices[uniqueVertices[a]];
179
685k
    }
180
181
    // Normals, if present
182
685k
    if (pMesh->mNormals) {
183
467k
        std::unique_ptr<aiVector3D[]> oldNormals(pMesh->mNormals);
184
467k
        pMesh->mNormals = new aiVector3D[pMesh->mNumVertices];
185
11.9M
        for (unsigned int a = 0; a < pMesh->mNumVertices; a++)
186
11.4M
            pMesh->mNormals[a] = oldNormals[uniqueVertices[a]];
187
467k
    }
188
    // Tangents, if present
189
685k
    if (pMesh->mTangents) {
190
26.4k
        std::unique_ptr<aiVector3D[]> oldTangents(pMesh->mTangents);
191
26.4k
        pMesh->mTangents = new aiVector3D[pMesh->mNumVertices];
192
2.35M
        for (unsigned int a = 0; a < pMesh->mNumVertices; a++)
193
2.33M
            pMesh->mTangents[a] = oldTangents[uniqueVertices[a]];
194
26.4k
    }
195
    // Bitangents as well
196
685k
    if (pMesh->mBitangents) {
197
26.4k
        std::unique_ptr<aiVector3D[]> oldBitangents(pMesh->mBitangents);
198
26.4k
        pMesh->mBitangents = new aiVector3D[pMesh->mNumVertices];
199
2.35M
        for (unsigned int a = 0; a < pMesh->mNumVertices; a++)
200
2.33M
            pMesh->mBitangents[a] = oldBitangents[uniqueVertices[a]];
201
26.4k
    }
202
    // Vertex colors
203
835k
    for (unsigned int a = 0; pMesh->HasVertexColors(a); a++) {
204
149k
        std::unique_ptr<aiColor4D[]> oldColors(pMesh->mColors[a]);
205
149k
        pMesh->mColors[a] = new aiColor4D[pMesh->mNumVertices];
206
1.27M
        for (unsigned int b = 0; b < pMesh->mNumVertices; b++)
207
1.12M
            pMesh->mColors[a][b] = oldColors[uniqueVertices[b]];
208
149k
    }
209
    // Texture coords
210
718k
    for (unsigned int a = 0; pMesh->HasTextureCoords(a); a++) {
211
33.2k
        std::unique_ptr<aiVector3D[]> oldTextureCoords(pMesh->mTextureCoords[a]);
212
33.2k
        pMesh->mTextureCoords[a] = new aiVector3D[pMesh->mNumVertices];
213
2.46M
        for (unsigned int b = 0; b < pMesh->mNumVertices; b++)
214
2.42M
            pMesh->mTextureCoords[a][b] = oldTextureCoords[uniqueVertices[b]];
215
33.2k
    }
216
685k
}
Unexecuted instantiation: JoinVerticesProcess.cpp:void (anonymous namespace)::updateXMeshVertices<aiAnimMesh>(aiAnimMesh*, std::__1::vector<int, std::__1::allocator<int> >&)
217
218
} // namespace
219
220
// ------------------------------------------------------------------------------------------------
221
222
static constexpr size_t JOINED_VERTICES_MARK = 0x80000000u;
223
224
// now start the JoinVerticesProcess
225
685k
int JoinVerticesProcess::ProcessMesh( aiMesh* pMesh, unsigned int meshIndex) {
226
685k
    static_assert( AI_MAX_NUMBER_OF_COLOR_SETS    == 8, "AI_MAX_NUMBER_OF_COLOR_SETS    == 8");
227
685k
  static_assert( AI_MAX_NUMBER_OF_TEXTURECOORDS == 8, "AI_MAX_NUMBER_OF_TEXTURECOORDS == 8");
228
229
    // Return early if we don't have any positions
230
685k
    if (!pMesh->HasPositions() || !pMesh->HasFaces()) {
231
0
        return 0;
232
0
    }
233
234
    // We should care only about used vertices, not all of them
235
    // (this can happen due to original file vertices buffer being used by
236
    // multiple meshes)
237
685k
    std::vector<bool> usedVertexIndicesMask;
238
685k
    usedVertexIndicesMask.resize(pMesh->mNumVertices, false);
239
35.9M
    for (unsigned int a = 0; a < pMesh->mNumFaces; a++) {
240
35.2M
        aiFace& face = pMesh->mFaces[a];
241
128M
        for (unsigned int b = 0; b < face.mNumIndices; b++) {
242
93.2M
            usedVertexIndicesMask[face.mIndices[b]] = true;
243
93.2M
        }
244
35.2M
    }
245
246
    // We'll never have more vertices afterwards.
247
685k
    std::vector<int> uniqueVertices;
248
249
    // For each vertex the index of the vertex it was replaced by.
250
    // Since the maximal number of vertices is 2^31-1, the most significand bit can be used to mark
251
    //  whether a new vertex was created for the index (true) or if it was replaced by an existing
252
    //  unique vertex (false). This saves an additional std::vector<bool> and greatly enhances
253
    //  branching performance.
254
685k
    static_assert(AI_MAX_VERTICES == 0x7fffffff, "AI_MAX_VERTICES == 0x7fffffff");
255
685k
    std::vector<unsigned int> replaceIndex( pMesh->mNumVertices, 0xffffffff);
256
257
    // Run an optimized code path if we don't have multiple UVs or vertex colors.
258
    // This should yield false in more than 99% of all imports ...
259
685k
    const bool hasAnimMeshes = pMesh->mNumAnimMeshes > 0;
260
261
    // We'll never have more vertices afterwards.
262
685k
    std::vector<std::vector<int>> uniqueAnimatedVertices;
263
685k
    if (hasAnimMeshes) {
264
0
        uniqueAnimatedVertices.resize(pMesh->mNumAnimMeshes);
265
0
        for (unsigned int animMeshIndex = 0; animMeshIndex < pMesh->mNumAnimMeshes; animMeshIndex++) {
266
0
            uniqueAnimatedVertices[animMeshIndex].reserve(pMesh->mNumVertices);
267
0
        }
268
0
    }
269
    // a map that maps a vertex to its new index
270
685k
    std::unordered_map<Vertex, int, HashVertex, CompareVerticesAlmostEqual> vertex2Index = {};
271
    // we can not end up with more vertices than we started with
272
    // Now check each vertex if it brings something new to the table
273
685k
    int newIndex = 0;
274
114M
    for( unsigned int a = 0; a < pMesh->mNumVertices; a++)  {
275
        // if the vertex is unused Do nothing
276
113M
        if (!usedVertexIndicesMask[a]) {
277
37.6M
            continue;
278
37.6M
        }
279
        // collect the vertex data
280
75.8M
        Vertex v(pMesh,a);
281
        // is the vertex already in the map?
282
75.8M
        auto it = vertex2Index.find(v);
283
        // if the vertex is not in the map then it is a new vertex add it.
284
75.8M
        if (it == vertex2Index.end()) {
285
            // this is a new vertex give it a new index
286
11.9M
            vertex2Index.emplace(v, newIndex);
287
            // keep track of its index and increment 1
288
11.9M
            replaceIndex[a] = newIndex++;
289
            // add the vertex to the unique vertices
290
11.9M
            uniqueVertices.push_back(a);
291
11.9M
            if (hasAnimMeshes) {
292
0
                for (unsigned int animMeshIndex = 0; animMeshIndex < pMesh->mNumAnimMeshes; animMeshIndex++) {
293
0
                    uniqueAnimatedVertices[animMeshIndex].emplace_back(a);
294
0
                }
295
0
            }
296
63.9M
        } else{
297
            // if the vertex is already there just find the replace index that is appropriate to it
298
      // mark it with JOINED_VERTICES_MARK
299
63.9M
            replaceIndex[a] = it->second | JOINED_VERTICES_MARK;
300
63.9M
        }
301
75.8M
    }
302
303
685k
    if (!DefaultLogger::isNullLogger() && DefaultLogger::get()->getLogSeverity() == Logger::VERBOSE)    {
304
0
        ASSIMP_LOG_VERBOSE_DEBUG(
305
0
            "Mesh ",meshIndex,
306
0
            " (",
307
0
            (pMesh->mName.length ? pMesh->mName.data : "unnamed"),
308
0
            ") | Verts in: ",pMesh->mNumVertices,
309
0
            " out: ",
310
0
            uniqueVertices.size(),
311
0
            " | ~",
312
0
            ((pMesh->mNumVertices - uniqueVertices.size()) / (float)pMesh->mNumVertices) * 100.f,
313
0
            "%"
314
0
        );
315
0
    }
316
317
685k
    updateXMeshVertices(pMesh, uniqueVertices);
318
685k
    if (hasAnimMeshes) {
319
0
        for (unsigned int animMeshIndex = 0; animMeshIndex < pMesh->mNumAnimMeshes; animMeshIndex++) {
320
0
            updateXMeshVertices(pMesh->mAnimMeshes[animMeshIndex], uniqueAnimatedVertices[animMeshIndex]);
321
0
        }
322
0
    }
323
324
    // adjust the indices in all faces
325
35.9M
    for( unsigned int a = 0; a < pMesh->mNumFaces; a++) {
326
35.2M
        aiFace& face = pMesh->mFaces[a];
327
128M
        for( unsigned int b = 0; b < face.mNumIndices; b++) {
328
93.2M
            face.mIndices[b] = replaceIndex[face.mIndices[b]] & ~JOINED_VERTICES_MARK;
329
93.2M
        }
330
35.2M
    }
331
332
    // adjust bone vertex weights.
333
804k
    for( int a = 0; a < (int)pMesh->mNumBones; a++) {
334
119k
        aiBone* bone = pMesh->mBones[a];
335
119k
        std::vector<aiVertexWeight> newWeights;
336
119k
        newWeights.reserve( bone->mNumWeights);
337
338
119k
        if (nullptr != bone->mWeights) {
339
3.61M
            for ( unsigned int b = 0; b < bone->mNumWeights; b++ ) {
340
3.49M
                const aiVertexWeight& ow = bone->mWeights[ b ];
341
                // if the vertex is a unique one, translate it
342
        // filter out joined vertices by JOINED_VERTICES_MARK.
343
3.49M
                if ( !( replaceIndex[ ow.mVertexId ] & JOINED_VERTICES_MARK ) ) {
344
1.25M
                    aiVertexWeight nw;
345
1.25M
                    nw.mVertexId = replaceIndex[ ow.mVertexId ];
346
1.25M
                    nw.mWeight = ow.mWeight;
347
1.25M
                    newWeights.push_back( nw );
348
1.25M
                }
349
3.49M
            }
350
119k
        } else {
351
0
            ASSIMP_LOG_ERROR( "X-Export: aiBone shall contain weights, but pointer to them is nullptr." );
352
0
        }
353
354
119k
        if (newWeights.size() > 0) {
355
            // kill the old and replace them with the translated weights
356
19.3k
            delete [] bone->mWeights;
357
19.3k
            bone->mNumWeights = (unsigned int)newWeights.size();
358
359
19.3k
            bone->mWeights = new aiVertexWeight[bone->mNumWeights];
360
19.3k
            memcpy( bone->mWeights, &newWeights[0], bone->mNumWeights * sizeof( aiVertexWeight));
361
19.3k
        }
362
119k
    }
363
685k
    return pMesh->mNumVertices;
364
685k
}
365
366
#endif // !! ASSIMP_BUILD_NO_JOINVERTICES_PROCESS