vrshoot

annotate libs/assimp/OptimizeGraph.cpp @ 0:b2f14e535253

find changesets by author, revision, files, or words in the commit message
initial commit
author John Tsiombikas <nuclear@member.fsf.org>
date Sat, 01 Feb 2014 19:58:19 +0200
parents
children
rev   line source
nuclear@0 1 /*
nuclear@0 2 ---------------------------------------------------------------------------
nuclear@0 3 Open Asset Import Library (assimp)
nuclear@0 4 ---------------------------------------------------------------------------
nuclear@0 5
nuclear@0 6 Copyright (c) 2006-2012, assimp team
nuclear@0 7
nuclear@0 8 All rights reserved.
nuclear@0 9
nuclear@0 10 Redistribution and use of this software in source and binary forms,
nuclear@0 11 with or without modification, are permitted provided that the following
nuclear@0 12 conditions are met:
nuclear@0 13
nuclear@0 14 * Redistributions of source code must retain the above
nuclear@0 15 copyright notice, this list of conditions and the
nuclear@0 16 following disclaimer.
nuclear@0 17
nuclear@0 18 * Redistributions in binary form must reproduce the above
nuclear@0 19 copyright notice, this list of conditions and the
nuclear@0 20 following disclaimer in the documentation and/or other
nuclear@0 21 materials provided with the distribution.
nuclear@0 22
nuclear@0 23 * Neither the name of the assimp team, nor the names of its
nuclear@0 24 contributors may be used to endorse or promote products
nuclear@0 25 derived from this software without specific prior
nuclear@0 26 written permission of the assimp team.
nuclear@0 27
nuclear@0 28 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
nuclear@0 29 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
nuclear@0 30 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
nuclear@0 31 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
nuclear@0 32 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
nuclear@0 33 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
nuclear@0 34 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
nuclear@0 35 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
nuclear@0 36 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
nuclear@0 37 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
nuclear@0 38 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
nuclear@0 39 ---------------------------------------------------------------------------
nuclear@0 40 */
nuclear@0 41
nuclear@0 42 /** @file OptimizeGraph.cpp
nuclear@0 43 * @brief Implementation of the aiProcess_OptimizGraph step
nuclear@0 44 */
nuclear@0 45
nuclear@0 46 #include "AssimpPCH.h"
nuclear@0 47 #ifndef ASSIMP_BUILD_NO_OPTIMIZEGRAPH_PROCESS
nuclear@0 48
nuclear@0 49 using namespace Assimp;
nuclear@0 50 #include "OptimizeGraph.h"
nuclear@0 51 #include "ProcessHelper.h"
nuclear@0 52 #include "SceneCombiner.h"
nuclear@0 53
nuclear@0 54 #define AI_RESERVED_NODE_NAME "$Reserved_And_Evil"
nuclear@0 55
nuclear@0 56 /* AI_OG_USE_HASHING enables the use of hashing to speed-up std::set lookups.
nuclear@0 57 * The unhashed variant should be faster, except for *very* large data sets
nuclear@0 58 */
nuclear@0 59 #ifdef AI_OG_USE_HASHING
nuclear@0 60 // Use our standard hashing function to compute the hash
nuclear@0 61 # define AI_OG_GETKEY(str) SuperFastHash(str.data,str.length)
nuclear@0 62 #else
nuclear@0 63 // Otherwise hope that std::string will utilize a static buffer
nuclear@0 64 // for shorter node names. This would avoid endless heap copying.
nuclear@0 65 # define AI_OG_GETKEY(str) std::string(str.data)
nuclear@0 66 #endif
nuclear@0 67
nuclear@0 68 // ------------------------------------------------------------------------------------------------
nuclear@0 69 // Constructor to be privately used by Importer
nuclear@0 70 OptimizeGraphProcess::OptimizeGraphProcess()
nuclear@0 71 {}
nuclear@0 72
nuclear@0 73 // ------------------------------------------------------------------------------------------------
nuclear@0 74 // Destructor, private as well
nuclear@0 75 OptimizeGraphProcess::~OptimizeGraphProcess()
nuclear@0 76 {}
nuclear@0 77
nuclear@0 78 // ------------------------------------------------------------------------------------------------
nuclear@0 79 // Returns whether the processing step is present in the given flag field.
nuclear@0 80 bool OptimizeGraphProcess::IsActive( unsigned int pFlags) const
nuclear@0 81 {
nuclear@0 82 return (0 != (pFlags & aiProcess_OptimizeGraph));
nuclear@0 83 }
nuclear@0 84
nuclear@0 85 // ------------------------------------------------------------------------------------------------
nuclear@0 86 // Setup properties for the postprocessing step
nuclear@0 87 void OptimizeGraphProcess::SetupProperties(const Importer* pImp)
nuclear@0 88 {
nuclear@0 89 // Get value of AI_CONFIG_PP_OG_EXCLUDE_LIST
nuclear@0 90 std::string tmp = pImp->GetPropertyString(AI_CONFIG_PP_OG_EXCLUDE_LIST,"");
nuclear@0 91 AddLockedNodeList(tmp);
nuclear@0 92 }
nuclear@0 93
nuclear@0 94 // ------------------------------------------------------------------------------------------------
nuclear@0 95 // Collect new children
nuclear@0 96 void OptimizeGraphProcess::CollectNewChildren(aiNode* nd, std::list<aiNode*>& nodes)
nuclear@0 97 {
nuclear@0 98 nodes_in += nd->mNumChildren;
nuclear@0 99
nuclear@0 100 // Process children
nuclear@0 101 std::list<aiNode*> child_nodes;
nuclear@0 102 for (unsigned int i = 0; i < nd->mNumChildren; ++i) {
nuclear@0 103
nuclear@0 104 CollectNewChildren(nd->mChildren[i],child_nodes);
nuclear@0 105 nd->mChildren[i] = NULL;
nuclear@0 106 }
nuclear@0 107
nuclear@0 108 // Check whether we need this node; if not we can replace it by our own children (warn, danger of incest).
nuclear@0 109 if (locked.find(AI_OG_GETKEY(nd->mName)) == locked.end() ) {
nuclear@0 110 for (std::list<aiNode*>::iterator it = child_nodes.begin(); it != child_nodes.end();) {
nuclear@0 111
nuclear@0 112 if (locked.find(AI_OG_GETKEY((*it)->mName)) == locked.end()) {
nuclear@0 113 (*it)->mTransformation = nd->mTransformation * (*it)->mTransformation;
nuclear@0 114 nodes.push_back(*it);
nuclear@0 115
nuclear@0 116 it = child_nodes.erase(it);
nuclear@0 117 continue;
nuclear@0 118 }
nuclear@0 119 ++it;
nuclear@0 120 }
nuclear@0 121
nuclear@0 122 if (nd->mNumMeshes || child_nodes.size()) {
nuclear@0 123 nodes.push_back(nd);
nuclear@0 124 }
nuclear@0 125 else {
nuclear@0 126 delete nd; /* bye, node */
nuclear@0 127 return;
nuclear@0 128 }
nuclear@0 129 }
nuclear@0 130 else {
nuclear@0 131
nuclear@0 132 // Retain our current position in the hierarchy
nuclear@0 133 nodes.push_back(nd);
nuclear@0 134
nuclear@0 135 // Now check for possible optimizations in our list of child nodes. join as many as possible
nuclear@0 136 aiNode* join_master = NULL;
nuclear@0 137 aiMatrix4x4 inv;
nuclear@0 138
nuclear@0 139 const LockedSetType::const_iterator end = locked.end();
nuclear@0 140
nuclear@0 141 std::list<aiNode*> join;
nuclear@0 142 for (std::list<aiNode*>::iterator it = child_nodes.begin(); it != child_nodes.end();) {
nuclear@0 143 aiNode* child = *it;
nuclear@0 144 if (child->mNumChildren == 0 && locked.find(AI_OG_GETKEY(child->mName)) == end) {
nuclear@0 145
nuclear@0 146 // There may be no instanced meshes
nuclear@0 147 unsigned int n = 0;
nuclear@0 148 for (; n < child->mNumMeshes;++n) {
nuclear@0 149 if (meshes[child->mMeshes[n]] > 1) {
nuclear@0 150 break;
nuclear@0 151 }
nuclear@0 152 }
nuclear@0 153 if (n == child->mNumMeshes) {
nuclear@0 154
nuclear@0 155 if (!join_master) {
nuclear@0 156 join_master = child;
nuclear@0 157 inv = join_master->mTransformation;
nuclear@0 158 inv.Inverse();
nuclear@0 159 }
nuclear@0 160 else {
nuclear@0 161
nuclear@0 162 child->mTransformation = inv * child->mTransformation ;
nuclear@0 163
nuclear@0 164 join.push_back(child);
nuclear@0 165 it = child_nodes.erase(it);
nuclear@0 166 continue;
nuclear@0 167 }
nuclear@0 168 }
nuclear@0 169 }
nuclear@0 170 ++it;
nuclear@0 171 }
nuclear@0 172 if (join_master && join.size()) {
nuclear@0 173 join_master->mName.length = sprintf(join_master->mName.data,"$MergedNode_%i",count_merged++);
nuclear@0 174
nuclear@0 175 unsigned int out_meshes = 0;
nuclear@0 176 for (std::list<aiNode*>::iterator it = join.begin(); it != join.end(); ++it) {
nuclear@0 177 out_meshes += (*it)->mNumMeshes;
nuclear@0 178 }
nuclear@0 179
nuclear@0 180 // copy all mesh references in one array
nuclear@0 181 if (out_meshes) {
nuclear@0 182 unsigned int* meshes = new unsigned int[out_meshes+join_master->mNumMeshes], *tmp = meshes;
nuclear@0 183 for (unsigned int n = 0; n < join_master->mNumMeshes;++n) {
nuclear@0 184 *tmp++ = join_master->mMeshes[n];
nuclear@0 185 }
nuclear@0 186
nuclear@0 187 for (std::list<aiNode*>::iterator it = join.begin(); it != join.end(); ++it) {
nuclear@0 188 for (unsigned int n = 0; n < (*it)->mNumMeshes; ++n) {
nuclear@0 189
nuclear@0 190 *tmp = (*it)->mMeshes[n];
nuclear@0 191 aiMesh* mesh = mScene->mMeshes[*tmp++];
nuclear@0 192
nuclear@0 193 // manually move the mesh into the right coordinate system
nuclear@0 194 const aiMatrix3x3 IT = aiMatrix3x3( (*it)->mTransformation ).Inverse().Transpose();
nuclear@0 195 for (unsigned int a = 0; a < mesh->mNumVertices; ++a) {
nuclear@0 196
nuclear@0 197 mesh->mVertices[a] *= (*it)->mTransformation;
nuclear@0 198
nuclear@0 199 if (mesh->HasNormals())
nuclear@0 200 mesh->mNormals[a] *= IT;
nuclear@0 201
nuclear@0 202 if (mesh->HasTangentsAndBitangents()) {
nuclear@0 203 mesh->mTangents[a] *= IT;
nuclear@0 204 mesh->mBitangents[a] *= IT;
nuclear@0 205 }
nuclear@0 206 }
nuclear@0 207 }
nuclear@0 208 delete *it; // bye, node
nuclear@0 209 }
nuclear@0 210 delete[] join_master->mMeshes;
nuclear@0 211 join_master->mMeshes = meshes;
nuclear@0 212 join_master->mNumMeshes += out_meshes;
nuclear@0 213 }
nuclear@0 214 }
nuclear@0 215 }
nuclear@0 216 // reassign children if something changed
nuclear@0 217 if (child_nodes.empty() || child_nodes.size() > nd->mNumChildren) {
nuclear@0 218
nuclear@0 219 delete[] nd->mChildren;
nuclear@0 220
nuclear@0 221 if (child_nodes.size())
nuclear@0 222 nd->mChildren = new aiNode*[child_nodes.size()];
nuclear@0 223 else nd->mChildren = NULL;
nuclear@0 224 }
nuclear@0 225
nuclear@0 226 nd->mNumChildren = child_nodes.size();
nuclear@0 227
nuclear@0 228 aiNode** tmp = nd->mChildren;
nuclear@0 229 for (std::list<aiNode*>::iterator it = child_nodes.begin(); it != child_nodes.end(); ++it) {
nuclear@0 230 aiNode* node = *tmp++ = *it;
nuclear@0 231 node->mParent = nd;
nuclear@0 232 }
nuclear@0 233
nuclear@0 234 nodes_out += child_nodes.size();
nuclear@0 235 }
nuclear@0 236
nuclear@0 237 // ------------------------------------------------------------------------------------------------
nuclear@0 238 // Execute the postprocessing step on the given scene
nuclear@0 239 void OptimizeGraphProcess::Execute( aiScene* pScene)
nuclear@0 240 {
nuclear@0 241 DefaultLogger::get()->debug("OptimizeGraphProcess begin");
nuclear@0 242 nodes_in = nodes_out = count_merged = 0;
nuclear@0 243 mScene = pScene;
nuclear@0 244
nuclear@0 245 meshes.resize(pScene->mNumMeshes,0);
nuclear@0 246 FindInstancedMeshes(pScene->mRootNode);
nuclear@0 247
nuclear@0 248 // build a blacklist of identifiers. If the name of a node matches one of these, we won't touch it
nuclear@0 249 locked.clear();
nuclear@0 250 for (std::list<std::string>::const_iterator it = locked_nodes.begin(); it != locked_nodes.end(); ++it) {
nuclear@0 251 #ifdef AI_OG_USE_HASHING
nuclear@0 252 locked.insert(SuperFastHash((*it).c_str()));
nuclear@0 253 #else
nuclear@0 254 locked.insert(*it);
nuclear@0 255 #endif
nuclear@0 256 }
nuclear@0 257
nuclear@0 258 for (unsigned int i = 0; i < pScene->mNumAnimations; ++i) {
nuclear@0 259 for (unsigned int a = 0; a < pScene->mAnimations[i]->mNumChannels; ++a) {
nuclear@0 260
nuclear@0 261 aiNodeAnim* anim = pScene->mAnimations[i]->mChannels[a];
nuclear@0 262 locked.insert(AI_OG_GETKEY(anim->mNodeName));
nuclear@0 263 }
nuclear@0 264 }
nuclear@0 265
nuclear@0 266 for (unsigned int i = 0; i < pScene->mNumMeshes; ++i) {
nuclear@0 267 for (unsigned int a = 0; a < pScene->mMeshes[i]->mNumBones; ++a) {
nuclear@0 268
nuclear@0 269 aiBone* bone = pScene->mMeshes[i]->mBones[a];
nuclear@0 270 locked.insert(AI_OG_GETKEY(bone->mName));
nuclear@0 271
nuclear@0 272 // HACK: Meshes referencing bones may not be transformed; we need to look them.
nuclear@0 273 // The easiest way to do this is to increase their reference counters ...
nuclear@0 274 meshes[i] += 2;
nuclear@0 275 }
nuclear@0 276 }
nuclear@0 277
nuclear@0 278 for (unsigned int i = 0; i < pScene->mNumCameras; ++i) {
nuclear@0 279 aiCamera* cam = pScene->mCameras[i];
nuclear@0 280 locked.insert(AI_OG_GETKEY(cam->mName));
nuclear@0 281 }
nuclear@0 282
nuclear@0 283 for (unsigned int i = 0; i < pScene->mNumLights; ++i) {
nuclear@0 284 aiLight* lgh = pScene->mLights[i];
nuclear@0 285 locked.insert(AI_OG_GETKEY(lgh->mName));
nuclear@0 286 }
nuclear@0 287
nuclear@0 288 // Insert a dummy master node and make it read-only
nuclear@0 289 aiNode* dummy_root = new aiNode(AI_RESERVED_NODE_NAME);
nuclear@0 290 locked.insert(AI_OG_GETKEY(dummy_root->mName));
nuclear@0 291
nuclear@0 292 const aiString prev = pScene->mRootNode->mName;
nuclear@0 293 pScene->mRootNode->mParent = dummy_root;
nuclear@0 294
nuclear@0 295 dummy_root->mChildren = new aiNode*[dummy_root->mNumChildren = 1];
nuclear@0 296 dummy_root->mChildren[0] = pScene->mRootNode;
nuclear@0 297
nuclear@0 298 // Do our recursive processing of scenegraph nodes. For each node collect
nuclear@0 299 // a fully new list of children and allow their children to place themselves
nuclear@0 300 // on the same hierarchy layer as their parents.
nuclear@0 301 std::list<aiNode*> nodes;
nuclear@0 302 CollectNewChildren (dummy_root,nodes);
nuclear@0 303
nuclear@0 304 ai_assert(nodes.size() == 1);
nuclear@0 305
nuclear@0 306 if (dummy_root->mNumChildren == 0) {
nuclear@0 307 pScene->mRootNode = NULL;
nuclear@0 308 throw DeadlyImportError("After optimizing the scene graph, no data remains");
nuclear@0 309 }
nuclear@0 310
nuclear@0 311 if (dummy_root->mNumChildren > 1) {
nuclear@0 312 pScene->mRootNode = dummy_root;
nuclear@0 313
nuclear@0 314 // Keep the dummy node but assign the name of the old root node to it
nuclear@0 315 pScene->mRootNode->mName = prev;
nuclear@0 316 }
nuclear@0 317 else {
nuclear@0 318
nuclear@0 319 // Remove the dummy root node again.
nuclear@0 320 pScene->mRootNode = dummy_root->mChildren[0];
nuclear@0 321
nuclear@0 322 dummy_root->mChildren[0] = NULL;
nuclear@0 323 delete dummy_root;
nuclear@0 324 }
nuclear@0 325
nuclear@0 326 pScene->mRootNode->mParent = NULL;
nuclear@0 327 if (!DefaultLogger::isNullLogger()) {
nuclear@0 328 if ( nodes_in != nodes_out) {
nuclear@0 329
nuclear@0 330 char buf[512];
nuclear@0 331 sprintf(buf,"OptimizeGraphProcess finished; Input nodes: %i, Output nodes: %i",nodes_in,nodes_out);
nuclear@0 332 DefaultLogger::get()->info(buf);
nuclear@0 333 }
nuclear@0 334 else DefaultLogger::get()->debug("OptimizeGraphProcess finished");
nuclear@0 335 }
nuclear@0 336 meshes.clear();
nuclear@0 337 locked.clear();
nuclear@0 338 }
nuclear@0 339
nuclear@0 340 // ------------------------------------------------------------------------------------------------
nuclear@0 341 // Buidl a LUT of all instanced meshes
nuclear@0 342 void OptimizeGraphProcess::FindInstancedMeshes (aiNode* pNode)
nuclear@0 343 {
nuclear@0 344 for (unsigned int i = 0; i < pNode->mNumMeshes;++i) {
nuclear@0 345 ++meshes[pNode->mMeshes[i]];
nuclear@0 346 }
nuclear@0 347
nuclear@0 348 for (unsigned int i = 0; i < pNode->mNumChildren; ++i)
nuclear@0 349 FindInstancedMeshes(pNode->mChildren[i]);
nuclear@0 350 }
nuclear@0 351
nuclear@0 352 #endif // !! ASSIMP_BUILD_NO_OPTIMIZEGRAPH_PROCESS