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 OptimizeGraph.cpp
44 * @brief Implementation of the aiProcess_OptimizGraph step
45 */
46
47
48#ifndef ASSIMP_BUILD_NO_OPTIMIZEGRAPH_PROCESS
49
50#include "OptimizeGraph.h"
51#include "ProcessHelper.h"
52#include <assimp/SceneCombiner.h>
53#include "Exceptional.h"
54#include <stdio.h>
55
56using namespace Assimp;
57
58#define AI_RESERVED_NODE_NAME "$Reserved_And_Evil"
59
60/* AI_OG_USE_HASHING enables the use of hashing to speed-up std::set lookups.
61 * The unhashed variant should be faster, except for *very* large data sets
62 */
63#ifdef AI_OG_USE_HASHING
64 // Use our standard hashing function to compute the hash
65# define AI_OG_GETKEY(str) SuperFastHash(str.data,str.length)
66#else
67 // Otherwise hope that std::string will utilize a static buffer
68 // for shorter node names. This would avoid endless heap copying.
69# define AI_OG_GETKEY(str) std::string(str.data)
70#endif
71
72// ------------------------------------------------------------------------------------------------
73// Constructor to be privately used by Importer
74OptimizeGraphProcess::OptimizeGraphProcess()
75 : mScene()
76 , nodes_in()
77 , nodes_out()
78 , count_merged()
79{}
80
81// ------------------------------------------------------------------------------------------------
82// Destructor, private as well
83OptimizeGraphProcess::~OptimizeGraphProcess()
84{}
85
86// ------------------------------------------------------------------------------------------------
87// Returns whether the processing step is present in the given flag field.
88bool OptimizeGraphProcess::IsActive( unsigned int pFlags) const
89{
90 return (0 != (pFlags & aiProcess_OptimizeGraph));
91}
92
93// ------------------------------------------------------------------------------------------------
94// Setup properties for the postprocessing step
95void OptimizeGraphProcess::SetupProperties(const Importer* pImp)
96{
97 // Get value of AI_CONFIG_PP_OG_EXCLUDE_LIST
98 std::string tmp = pImp->GetPropertyString(AI_CONFIG_PP_OG_EXCLUDE_LIST,"");
99 AddLockedNodeList(tmp);
100}
101
102// ------------------------------------------------------------------------------------------------
103// Collect new children
104void OptimizeGraphProcess::CollectNewChildren(aiNode* nd, std::list<aiNode*>& nodes)
105{
106 nodes_in += nd->mNumChildren;
107
108 // Process children
109 std::list<aiNode*> child_nodes;
110 for (unsigned int i = 0; i < nd->mNumChildren; ++i) {
111
112 CollectNewChildren(nd->mChildren[i],child_nodes);
113 nd->mChildren[i] = NULL;
114 }
115
116 // Check whether we need this node; if not we can replace it by our own children (warn, danger of incest).
117 if (locked.find(AI_OG_GETKEY(nd->mName)) == locked.end() ) {
118 for (std::list<aiNode*>::iterator it = child_nodes.begin(); it != child_nodes.end();) {
119
120 if (locked.find(AI_OG_GETKEY((*it)->mName)) == locked.end()) {
121 (*it)->mTransformation = nd->mTransformation * (*it)->mTransformation;
122 nodes.push_back(*it);
123
124 it = child_nodes.erase(it);
125 continue;
126 }
127 ++it;
128 }
129
130 if (nd->mNumMeshes || !child_nodes.empty()) {
131 nodes.push_back(nd);
132 }
133 else {
134 delete nd; /* bye, node */
135 return;
136 }
137 }
138 else {
139
140 // Retain our current position in the hierarchy
141 nodes.push_back(nd);
142
143 // Now check for possible optimizations in our list of child nodes. join as many as possible
144 aiNode* join_master = NULL;
145 aiMatrix4x4 inv;
146
147 const LockedSetType::const_iterator end = locked.end();
148
149 std::list<aiNode*> join;
150 for (std::list<aiNode*>::iterator it = child_nodes.begin(); it != child_nodes.end();) {
151 aiNode* child = *it;
152 if (child->mNumChildren == 0 && locked.find(AI_OG_GETKEY(child->mName)) == end) {
153
154 // There may be no instanced meshes
155 unsigned int n = 0;
156 for (; n < child->mNumMeshes;++n) {
157 if (meshes[child->mMeshes[n]] > 1) {
158 break;
159 }
160 }
161 if (n == child->mNumMeshes) {
162
163 if (!join_master) {
164 join_master = child;
165 inv = join_master->mTransformation;
166 inv.Inverse();
167 }
168 else {
169
170 child->mTransformation = inv * child->mTransformation ;
171
172 join.push_back(child);
173 it = child_nodes.erase(it);
174 continue;
175 }
176 }
177 }
178 ++it;
179 }
180 if (join_master && !join.empty()) {
181 join_master->mName.length = ::ai_snprintf(join_master->mName.data, MAXLEN, "$MergedNode_%i",count_merged++);
182
183 unsigned int out_meshes = 0;
184 for (std::list<aiNode*>::iterator it = join.begin(); it != join.end(); ++it) {
185 out_meshes += (*it)->mNumMeshes;
186 }
187
188 // copy all mesh references in one array
189 if (out_meshes) {
190 unsigned int* meshes = new unsigned int[out_meshes+join_master->mNumMeshes], *tmp = meshes;
191 for (unsigned int n = 0; n < join_master->mNumMeshes;++n) {
192 *tmp++ = join_master->mMeshes[n];
193 }
194
195 for (std::list<aiNode*>::iterator it = join.begin(); it != join.end(); ++it) {
196 for (unsigned int n = 0; n < (*it)->mNumMeshes; ++n) {
197
198 *tmp = (*it)->mMeshes[n];
199 aiMesh* mesh = mScene->mMeshes[*tmp++];
200
201 // manually move the mesh into the right coordinate system
202 const aiMatrix3x3 IT = aiMatrix3x3( (*it)->mTransformation ).Inverse().Transpose();
203 for (unsigned int a = 0; a < mesh->mNumVertices; ++a) {
204
205 mesh->mVertices[a] *= (*it)->mTransformation;
206
207 if (mesh->HasNormals())
208 mesh->mNormals[a] *= IT;
209
210 if (mesh->HasTangentsAndBitangents()) {
211 mesh->mTangents[a] *= IT;
212 mesh->mBitangents[a] *= IT;
213 }
214 }
215 }
216 delete *it; // bye, node
217 }
218 delete[] join_master->mMeshes;
219 join_master->mMeshes = meshes;
220 join_master->mNumMeshes += out_meshes;
221 }
222 }
223 }
224 // reassign children if something changed
225 if (child_nodes.empty() || child_nodes.size() > nd->mNumChildren) {
226
227 delete[] nd->mChildren;
228
229 if (!child_nodes.empty())
230 nd->mChildren = new aiNode*[child_nodes.size()];
231 else nd->mChildren = NULL;
232 }
233
234 nd->mNumChildren = static_cast<unsigned int>(child_nodes.size());
235
236 if (nd->mChildren) {
237 aiNode** tmp = nd->mChildren;
238 for (std::list<aiNode*>::iterator it = child_nodes.begin(); it != child_nodes.end(); ++it) {
239 aiNode* node = *tmp++ = *it;
240 node->mParent = nd;
241 }
242 }
243
244 nodes_out += static_cast<unsigned int>(child_nodes.size());
245}
246
247// ------------------------------------------------------------------------------------------------
248// Execute the postprocessing step on the given scene
249void OptimizeGraphProcess::Execute( aiScene* pScene)
250{
251 DefaultLogger::get()->debug("OptimizeGraphProcess begin");
252 nodes_in = nodes_out = count_merged = 0;
253 mScene = pScene;
254
255 meshes.resize(pScene->mNumMeshes,0);
256 FindInstancedMeshes(pScene->mRootNode);
257
258 // build a blacklist of identifiers. If the name of a node matches one of these, we won't touch it
259 locked.clear();
260 for (std::list<std::string>::const_iterator it = locked_nodes.begin(); it != locked_nodes.end(); ++it) {
261#ifdef AI_OG_USE_HASHING
262 locked.insert(SuperFastHash((*it).c_str()));
263#else
264 locked.insert(*it);
265#endif
266 }
267
268 for (unsigned int i = 0; i < pScene->mNumAnimations; ++i) {
269 for (unsigned int a = 0; a < pScene->mAnimations[i]->mNumChannels; ++a) {
270
271 aiNodeAnim* anim = pScene->mAnimations[i]->mChannels[a];
272 locked.insert(AI_OG_GETKEY(anim->mNodeName));
273 }
274 }
275
276 for (unsigned int i = 0; i < pScene->mNumMeshes; ++i) {
277 for (unsigned int a = 0; a < pScene->mMeshes[i]->mNumBones; ++a) {
278
279 aiBone* bone = pScene->mMeshes[i]->mBones[a];
280 locked.insert(AI_OG_GETKEY(bone->mName));
281
282 // HACK: Meshes referencing bones may not be transformed; we need to look them.
283 // The easiest way to do this is to increase their reference counters ...
284 meshes[i] += 2;
285 }
286 }
287
288 for (unsigned int i = 0; i < pScene->mNumCameras; ++i) {
289 aiCamera* cam = pScene->mCameras[i];
290 locked.insert(AI_OG_GETKEY(cam->mName));
291 }
292
293 for (unsigned int i = 0; i < pScene->mNumLights; ++i) {
294 aiLight* lgh = pScene->mLights[i];
295 locked.insert(AI_OG_GETKEY(lgh->mName));
296 }
297
298 // Insert a dummy master node and make it read-only
299 aiNode* dummy_root = new aiNode(AI_RESERVED_NODE_NAME);
300 locked.insert(AI_OG_GETKEY(dummy_root->mName));
301
302 const aiString prev = pScene->mRootNode->mName;
303 pScene->mRootNode->mParent = dummy_root;
304
305 dummy_root->mChildren = new aiNode*[dummy_root->mNumChildren = 1];
306 dummy_root->mChildren[0] = pScene->mRootNode;
307
308 // Do our recursive processing of scenegraph nodes. For each node collect
309 // a fully new list of children and allow their children to place themselves
310 // on the same hierarchy layer as their parents.
311 std::list<aiNode*> nodes;
312 CollectNewChildren (dummy_root,nodes);
313
314 ai_assert(nodes.size() == 1);
315
316 if (dummy_root->mNumChildren == 0) {
317 pScene->mRootNode = NULL;
318 throw DeadlyImportError("After optimizing the scene graph, no data remains");
319 }
320
321 if (dummy_root->mNumChildren > 1) {
322 pScene->mRootNode = dummy_root;
323
324 // Keep the dummy node but assign the name of the old root node to it
325 pScene->mRootNode->mName = prev;
326 }
327 else {
328
329 // Remove the dummy root node again.
330 pScene->mRootNode = dummy_root->mChildren[0];
331
332 dummy_root->mChildren[0] = NULL;
333 delete dummy_root;
334 }
335
336 pScene->mRootNode->mParent = NULL;
337 if (!DefaultLogger::isNullLogger()) {
338 if ( nodes_in != nodes_out) {
339
340 char buf[512];
341 ::ai_snprintf(buf,512,"OptimizeGraphProcess finished; Input nodes: %u, Output nodes: %u",nodes_in,nodes_out);
342 DefaultLogger::get()->info(buf);
343 }
344 else DefaultLogger::get()->debug("OptimizeGraphProcess finished");
345 }
346 meshes.clear();
347 locked.clear();
348}
349
350// ------------------------------------------------------------------------------------------------
351// Buidl a LUT of all instanced meshes
352void OptimizeGraphProcess::FindInstancedMeshes (aiNode* pNode)
353{
354 for (unsigned int i = 0; i < pNode->mNumMeshes;++i) {
355 ++meshes[pNode->mMeshes[i]];
356 }
357
358 for (unsigned int i = 0; i < pNode->mNumChildren; ++i)
359 FindInstancedMeshes(pNode->mChildren[i]);
360}
361
362#endif // !! ASSIMP_BUILD_NO_OPTIMIZEGRAPH_PROCESS
363