1 /*
2 ---------------------------------------------------------------------------
3 Open Asset Import Library (assimp)
4 ---------------------------------------------------------------------------
5
6 Copyright (c) 2006-2019, assimp team
7
8
9
10 All rights reserved.
11
12 Redistribution and use of this software in source and binary forms,
13 with or without modification, are permitted provided that the following
14 conditions are met:
15
16 * Redistributions of source code must retain the above
17 copyright notice, this list of conditions and the
18 following disclaimer.
19
20 * Redistributions in binary form must reproduce the above
21 copyright notice, this list of conditions and the
22 following disclaimer in the documentation and/or other
23 materials provided with the distribution.
24
25 * Neither the name of the assimp team, nor the names of its
26 contributors may be used to endorse or promote products
27 derived from this software without specific prior
28 written permission of the assimp team.
29
30 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
31 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
32 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
33 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
34 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
35 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
36 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
37 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
38 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
39 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
40 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
41 ---------------------------------------------------------------------------
42 */
43
44 /** @file FindInstancesProcess.cpp
45 * @brief Implementation of the aiProcess_FindInstances postprocessing step
46 */
47
48
49 #include "FindInstancesProcess.h"
50 #include <memory>
51 #include <stdio.h>
52
53 using namespace Assimp;
54
55 // ------------------------------------------------------------------------------------------------
56 // Constructor to be privately used by Importer
FindInstancesProcess()57 FindInstancesProcess::FindInstancesProcess()
58 : configSpeedFlag (false)
59 {}
60
61 // ------------------------------------------------------------------------------------------------
62 // Destructor, private as well
~FindInstancesProcess()63 FindInstancesProcess::~FindInstancesProcess()
64 {}
65
66 // ------------------------------------------------------------------------------------------------
67 // Returns whether the processing step is present in the given flag field.
IsActive(unsigned int pFlags) const68 bool FindInstancesProcess::IsActive( unsigned int pFlags) const
69 {
70 // FindInstances makes absolutely no sense together with PreTransformVertices
71 // fixme: spawn error message somewhere else?
72 return 0 != (pFlags & aiProcess_FindInstances) && 0 == (pFlags & aiProcess_PreTransformVertices);
73 }
74
75 // ------------------------------------------------------------------------------------------------
76 // Setup properties for the step
SetupProperties(const Importer * pImp)77 void FindInstancesProcess::SetupProperties(const Importer* pImp)
78 {
79 // AI_CONFIG_FAVOUR_SPEED
80 configSpeedFlag = (0 != pImp->GetPropertyInteger(AI_CONFIG_FAVOUR_SPEED,0));
81 }
82
83 // ------------------------------------------------------------------------------------------------
84 // Compare the bones of two meshes
CompareBones(const aiMesh * orig,const aiMesh * inst)85 bool CompareBones(const aiMesh* orig, const aiMesh* inst)
86 {
87 for (unsigned int i = 0; i < orig->mNumBones;++i) {
88 aiBone* aha = orig->mBones[i];
89 aiBone* oha = inst->mBones[i];
90
91 if (aha->mNumWeights != oha->mNumWeights ||
92 aha->mOffsetMatrix != oha->mOffsetMatrix) {
93 return false;
94 }
95
96 // compare weight per weight ---
97 for (unsigned int n = 0; n < aha->mNumWeights;++n) {
98 if (aha->mWeights[n].mVertexId != oha->mWeights[n].mVertexId ||
99 (aha->mWeights[n].mWeight - oha->mWeights[n].mWeight) < 10e-3f) {
100 return false;
101 }
102 }
103 }
104 return true;
105 }
106
107 // ------------------------------------------------------------------------------------------------
108 // Update mesh indices in the node graph
UpdateMeshIndices(aiNode * node,unsigned int * lookup)109 void UpdateMeshIndices(aiNode* node, unsigned int* lookup)
110 {
111 for (unsigned int n = 0; n < node->mNumMeshes;++n)
112 node->mMeshes[n] = lookup[node->mMeshes[n]];
113
114 for (unsigned int n = 0; n < node->mNumChildren;++n)
115 UpdateMeshIndices(node->mChildren[n],lookup);
116 }
117
118 // ------------------------------------------------------------------------------------------------
119 // Executes the post processing step on the given imported data.
Execute(aiScene * pScene)120 void FindInstancesProcess::Execute( aiScene* pScene)
121 {
122 ASSIMP_LOG_DEBUG("FindInstancesProcess begin");
123 if (pScene->mNumMeshes) {
124
125 // use a pseudo hash for all meshes in the scene to quickly find
126 // the ones which are possibly equal. This step is executed early
127 // in the pipeline, so we could, depending on the file format,
128 // have several thousand small meshes. That's too much for a brute
129 // everyone-against-everyone check involving up to 10 comparisons
130 // each.
131 std::unique_ptr<uint64_t[]> hashes (new uint64_t[pScene->mNumMeshes]);
132 std::unique_ptr<unsigned int[]> remapping (new unsigned int[pScene->mNumMeshes]);
133
134 unsigned int numMeshesOut = 0;
135 for (unsigned int i = 0; i < pScene->mNumMeshes; ++i) {
136
137 aiMesh* inst = pScene->mMeshes[i];
138 hashes[i] = GetMeshHash(inst);
139
140 // Find an appropriate epsilon
141 // to compare position differences against
142 float epsilon = ComputePositionEpsilon(inst);
143 epsilon *= epsilon;
144
145 for (int a = i-1; a >= 0; --a) {
146 if (hashes[i] == hashes[a])
147 {
148 aiMesh* orig = pScene->mMeshes[a];
149 if (!orig)
150 continue;
151
152 // check for hash collision .. we needn't check
153 // the vertex format, it *must* match due to the
154 // (brilliant) construction of the hash
155 if (orig->mNumBones != inst->mNumBones ||
156 orig->mNumFaces != inst->mNumFaces ||
157 orig->mNumVertices != inst->mNumVertices ||
158 orig->mMaterialIndex != inst->mMaterialIndex ||
159 orig->mPrimitiveTypes != inst->mPrimitiveTypes)
160 continue;
161
162 // up to now the meshes are equal. Now compare vertex positions, normals,
163 // tangents and bitangents using this epsilon.
164 if (orig->HasPositions()) {
165 if(!CompareArrays(orig->mVertices,inst->mVertices,orig->mNumVertices,epsilon))
166 continue;
167 }
168 if (orig->HasNormals()) {
169 if(!CompareArrays(orig->mNormals,inst->mNormals,orig->mNumVertices,epsilon))
170 continue;
171 }
172 if (orig->HasTangentsAndBitangents()) {
173 if (!CompareArrays(orig->mTangents,inst->mTangents,orig->mNumVertices,epsilon) ||
174 !CompareArrays(orig->mBitangents,inst->mBitangents,orig->mNumVertices,epsilon))
175 continue;
176 }
177
178 // use a constant epsilon for colors and UV coordinates
179 static const float uvEpsilon = 10e-4f;
180 {
181 unsigned int j, end = orig->GetNumUVChannels();
182 for(j = 0; j < end; ++j) {
183 if (!orig->mTextureCoords[j]) {
184 continue;
185 }
186 if(!CompareArrays(orig->mTextureCoords[j],inst->mTextureCoords[j],orig->mNumVertices,uvEpsilon)) {
187 break;
188 }
189 }
190 if (j != end) {
191 continue;
192 }
193 }
194 {
195 unsigned int j, end = orig->GetNumColorChannels();
196 for(j = 0; j < end; ++j) {
197 if (!orig->mColors[j]) {
198 continue;
199 }
200 if(!CompareArrays(orig->mColors[j],inst->mColors[j],orig->mNumVertices,uvEpsilon)) {
201 break;
202 }
203 }
204 if (j != end) {
205 continue;
206 }
207 }
208
209 // These two checks are actually quite expensive and almost *never* required.
210 // Almost. That's why they're still here. But there's no reason to do them
211 // in speed-targeted imports.
212 if (!configSpeedFlag) {
213
214 // It seems to be strange, but we really need to check whether the
215 // bones are identical too. Although it's extremely unprobable
216 // that they're not if control reaches here, we need to deal
217 // with unprobable cases, too. It could still be that there are
218 // equal shapes which are deformed differently.
219 if (!CompareBones(orig,inst))
220 continue;
221
222 // For completeness ... compare even the index buffers for equality
223 // face order & winding order doesn't care. Input data is in verbose format.
224 std::unique_ptr<unsigned int[]> ftbl_orig(new unsigned int[orig->mNumVertices]);
225 std::unique_ptr<unsigned int[]> ftbl_inst(new unsigned int[orig->mNumVertices]);
226
227 for (unsigned int tt = 0; tt < orig->mNumFaces;++tt) {
228 aiFace& f = orig->mFaces[tt];
229 for (unsigned int nn = 0; nn < f.mNumIndices;++nn)
230 ftbl_orig[f.mIndices[nn]] = tt;
231
232 aiFace& f2 = inst->mFaces[tt];
233 for (unsigned int nn = 0; nn < f2.mNumIndices;++nn)
234 ftbl_inst[f2.mIndices[nn]] = tt;
235 }
236 if (0 != ::memcmp(ftbl_inst.get(),ftbl_orig.get(),orig->mNumVertices*sizeof(unsigned int)))
237 continue;
238 }
239
240 // We're still here. Or in other words: 'inst' is an instance of 'orig'.
241 // Place a marker in our list that we can easily update mesh indices.
242 remapping[i] = remapping[a];
243
244 // Delete the instanced mesh, we don't need it anymore
245 delete inst;
246 pScene->mMeshes[i] = NULL;
247 break;
248 }
249 }
250
251 // If we didn't find a match for the current mesh: keep it
252 if (pScene->mMeshes[i]) {
253 remapping[i] = numMeshesOut++;
254 }
255 }
256 ai_assert(0 != numMeshesOut);
257 if (numMeshesOut != pScene->mNumMeshes) {
258
259 // Collapse the meshes array by removing all NULL entries
260 for (unsigned int real = 0, i = 0; real < numMeshesOut; ++i) {
261 if (pScene->mMeshes[i])
262 pScene->mMeshes[real++] = pScene->mMeshes[i];
263 }
264
265 // And update the node graph with our nice lookup table
266 UpdateMeshIndices(pScene->mRootNode,remapping.get());
267
268 // write to log
269 if (!DefaultLogger::isNullLogger()) {
270 ASSIMP_LOG_INFO_F( "FindInstancesProcess finished. Found ", (pScene->mNumMeshes - numMeshesOut), " instances" );
271 }
272 pScene->mNumMeshes = numMeshesOut;
273 } else {
274 ASSIMP_LOG_DEBUG("FindInstancesProcess finished. No instanced meshes found");
275 }
276 }
277 }
278