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