1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/libs/assimp/OptimizeGraph.cpp	Sat Feb 01 19:58:19 2014 +0200
     1.3 @@ -0,0 +1,352 @@
     1.4 +/*
     1.5 +---------------------------------------------------------------------------
     1.6 +Open Asset Import Library (assimp)
     1.7 +---------------------------------------------------------------------------
     1.8 +
     1.9 +Copyright (c) 2006-2012, assimp team
    1.10 +
    1.11 +All rights reserved.
    1.12 +
    1.13 +Redistribution and use of this software in source and binary forms, 
    1.14 +with or without modification, are permitted provided that the following 
    1.15 +conditions are met:
    1.16 +
    1.17 +* Redistributions of source code must retain the above
    1.18 +  copyright notice, this list of conditions and the
    1.19 +  following disclaimer.
    1.20 +
    1.21 +* Redistributions in binary form must reproduce the above
    1.22 +  copyright notice, this list of conditions and the
    1.23 +  following disclaimer in the documentation and/or other
    1.24 +  materials provided with the distribution.
    1.25 +
    1.26 +* Neither the name of the assimp team, nor the names of its
    1.27 +  contributors may be used to endorse or promote products
    1.28 +  derived from this software without specific prior
    1.29 +  written permission of the assimp team.
    1.30 +
    1.31 +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 
    1.32 +"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 
    1.33 +LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
    1.34 +A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 
    1.35 +OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
    1.36 +SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 
    1.37 +LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
    1.38 +DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 
    1.39 +THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 
    1.40 +(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 
    1.41 +OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
    1.42 +---------------------------------------------------------------------------
    1.43 +*/
    1.44 +
    1.45 +/** @file  OptimizeGraph.cpp
    1.46 + *  @brief Implementation of the aiProcess_OptimizGraph step
    1.47 + */
    1.48 +
    1.49 +#include "AssimpPCH.h"
    1.50 +#ifndef ASSIMP_BUILD_NO_OPTIMIZEGRAPH_PROCESS
    1.51 +
    1.52 +using namespace Assimp;
    1.53 +#include "OptimizeGraph.h"
    1.54 +#include "ProcessHelper.h"
    1.55 +#include "SceneCombiner.h"
    1.56 +
    1.57 +#define AI_RESERVED_NODE_NAME "$Reserved_And_Evil"
    1.58 +
    1.59 +/* AI_OG_USE_HASHING enables the use of hashing to speed-up std::set lookups.
    1.60 + * The unhashed variant should be faster, except for *very* large data sets
    1.61 + */
    1.62 +#ifdef AI_OG_USE_HASHING
    1.63 +	// Use our standard hashing function to compute the hash 
    1.64 +#	define AI_OG_GETKEY(str) SuperFastHash(str.data,str.length)
    1.65 +#else
    1.66 +	// Otherwise hope that std::string will utilize a static buffer 
    1.67 +	// for shorter node names. This would avoid endless heap copying.
    1.68 +#	define AI_OG_GETKEY(str) std::string(str.data)
    1.69 +#endif
    1.70 +
    1.71 +// ------------------------------------------------------------------------------------------------
    1.72 +// Constructor to be privately used by Importer
    1.73 +OptimizeGraphProcess::OptimizeGraphProcess()
    1.74 +{}
    1.75 +
    1.76 +// ------------------------------------------------------------------------------------------------
    1.77 +// Destructor, private as well
    1.78 +OptimizeGraphProcess::~OptimizeGraphProcess()
    1.79 +{}
    1.80 +
    1.81 +// ------------------------------------------------------------------------------------------------
    1.82 +// Returns whether the processing step is present in the given flag field.
    1.83 +bool OptimizeGraphProcess::IsActive( unsigned int pFlags) const
    1.84 +{
    1.85 +	return (0 != (pFlags & aiProcess_OptimizeGraph));
    1.86 +}
    1.87 +
    1.88 +// ------------------------------------------------------------------------------------------------
    1.89 +// Setup properties for the postprocessing step
    1.90 +void OptimizeGraphProcess::SetupProperties(const Importer* pImp)
    1.91 +{	
    1.92 +	// Get value of AI_CONFIG_PP_OG_EXCLUDE_LIST
    1.93 +	std::string tmp = pImp->GetPropertyString(AI_CONFIG_PP_OG_EXCLUDE_LIST,"");
    1.94 +	AddLockedNodeList(tmp);
    1.95 +}
    1.96 +
    1.97 +// ------------------------------------------------------------------------------------------------
    1.98 +// Collect new children
    1.99 +void OptimizeGraphProcess::CollectNewChildren(aiNode* nd, std::list<aiNode*>& nodes)
   1.100 +{
   1.101 +	nodes_in += nd->mNumChildren;
   1.102 +
   1.103 +	// Process children
   1.104 +	std::list<aiNode*> child_nodes;
   1.105 +	for (unsigned int i = 0; i < nd->mNumChildren; ++i) {
   1.106 +
   1.107 +		CollectNewChildren(nd->mChildren[i],child_nodes);
   1.108 +		nd->mChildren[i] = NULL;
   1.109 +	}
   1.110 +
   1.111 +	// Check whether we need this node; if not we can replace it by our own children (warn, danger of incest).
   1.112 +	if (locked.find(AI_OG_GETKEY(nd->mName)) == locked.end() ) {
   1.113 +		for (std::list<aiNode*>::iterator it = child_nodes.begin(); it != child_nodes.end();) {
   1.114 +
   1.115 +			if (locked.find(AI_OG_GETKEY((*it)->mName)) == locked.end()) {
   1.116 +				(*it)->mTransformation = nd->mTransformation * (*it)->mTransformation;
   1.117 +				nodes.push_back(*it);
   1.118 +
   1.119 +				it = child_nodes.erase(it);
   1.120 +				continue;
   1.121 +			}
   1.122 +			++it;
   1.123 +		}
   1.124 +
   1.125 +		if (nd->mNumMeshes || child_nodes.size()) { 
   1.126 +			nodes.push_back(nd);
   1.127 +		}
   1.128 +		else {
   1.129 +			delete nd; /* bye, node */
   1.130 +			return;
   1.131 +		}
   1.132 +	}
   1.133 +	else {
   1.134 +		
   1.135 +		// Retain our current position in the hierarchy
   1.136 +		nodes.push_back(nd);
   1.137 +
   1.138 +		// Now check for possible optimizations in our list of child nodes. join as many as possible
   1.139 +		aiNode* join_master = NULL;
   1.140 +		aiMatrix4x4 inv;
   1.141 +
   1.142 +		const LockedSetType::const_iterator end = locked.end();
   1.143 +
   1.144 +		std::list<aiNode*> join;
   1.145 +		for (std::list<aiNode*>::iterator it = child_nodes.begin(); it != child_nodes.end();)	{
   1.146 +			aiNode* child = *it;
   1.147 +			if (child->mNumChildren == 0 && locked.find(AI_OG_GETKEY(child->mName)) == end) {
   1.148 +			
   1.149 +				// There may be no instanced meshes
   1.150 +				unsigned int n = 0;
   1.151 +				for (; n < child->mNumMeshes;++n) {
   1.152 +					if (meshes[child->mMeshes[n]] > 1) {
   1.153 +						break;
   1.154 +					}
   1.155 +				}
   1.156 +				if (n == child->mNumMeshes) {
   1.157 +
   1.158 +					if (!join_master) {
   1.159 +						join_master = child;
   1.160 +						inv = join_master->mTransformation;
   1.161 +						inv.Inverse();
   1.162 +					}
   1.163 +					else {
   1.164 +
   1.165 +						child->mTransformation = inv * child->mTransformation ;
   1.166 +
   1.167 +						join.push_back(child);	
   1.168 +						it = child_nodes.erase(it);
   1.169 +						continue;
   1.170 +					}
   1.171 +				}
   1.172 +			}
   1.173 +			++it;
   1.174 +		}
   1.175 +		if (join_master && join.size()) {
   1.176 +			join_master->mName.length = sprintf(join_master->mName.data,"$MergedNode_%i",count_merged++);
   1.177 +
   1.178 +			unsigned int out_meshes = 0;
   1.179 +			for (std::list<aiNode*>::iterator it = join.begin(); it != join.end(); ++it) {
   1.180 +				out_meshes += (*it)->mNumMeshes;
   1.181 +			}
   1.182 +			
   1.183 +			// copy all mesh references in one array
   1.184 +			if (out_meshes) {
   1.185 +				unsigned int* meshes = new unsigned int[out_meshes+join_master->mNumMeshes], *tmp = meshes;
   1.186 +				for (unsigned int n = 0; n < join_master->mNumMeshes;++n) {
   1.187 +					*tmp++ = join_master->mMeshes[n];		
   1.188 +				}
   1.189 +
   1.190 +				for (std::list<aiNode*>::iterator it = join.begin(); it != join.end(); ++it) {
   1.191 +					for (unsigned int n = 0; n < (*it)->mNumMeshes; ++n) {
   1.192 +
   1.193 +						*tmp = (*it)->mMeshes[n];
   1.194 +						aiMesh* mesh = mScene->mMeshes[*tmp++];
   1.195 +
   1.196 +						// manually move the mesh into the right coordinate system
   1.197 +						const aiMatrix3x3 IT = aiMatrix3x3( (*it)->mTransformation ).Inverse().Transpose(); 
   1.198 +						for (unsigned int a = 0; a < mesh->mNumVertices; ++a) {
   1.199 +						
   1.200 +							mesh->mVertices[a] *= (*it)->mTransformation;
   1.201 +
   1.202 +							if (mesh->HasNormals())
   1.203 +								mesh->mNormals[a] *= IT;
   1.204 +
   1.205 +							if (mesh->HasTangentsAndBitangents()) {
   1.206 +								mesh->mTangents[a] *= IT;
   1.207 +								mesh->mBitangents[a] *= IT;
   1.208 +							}
   1.209 +						}
   1.210 +					}
   1.211 +					delete *it; // bye, node
   1.212 +				}
   1.213 +				delete[] join_master->mMeshes;
   1.214 +				join_master->mMeshes = meshes;
   1.215 +				join_master->mNumMeshes += out_meshes;
   1.216 +			}
   1.217 +		}
   1.218 +	}
   1.219 +	// reassign children if something changed
   1.220 +	if (child_nodes.empty() || child_nodes.size() > nd->mNumChildren) {
   1.221 +
   1.222 +		delete[] nd->mChildren;
   1.223 +
   1.224 +		if (child_nodes.size())
   1.225 +			nd->mChildren = new aiNode*[child_nodes.size()];
   1.226 +		else nd->mChildren = NULL;
   1.227 +	}
   1.228 +
   1.229 +	nd->mNumChildren = child_nodes.size();
   1.230 +
   1.231 +	aiNode** tmp = nd->mChildren;
   1.232 +	for (std::list<aiNode*>::iterator it = child_nodes.begin(); it != child_nodes.end(); ++it) {
   1.233 +		aiNode* node = *tmp++ = *it;
   1.234 +		node->mParent = nd;
   1.235 +	}
   1.236 +
   1.237 +	nodes_out += child_nodes.size();
   1.238 +}
   1.239 +
   1.240 +// ------------------------------------------------------------------------------------------------
   1.241 +// Execute the postprocessing step on the given scene
   1.242 +void OptimizeGraphProcess::Execute( aiScene* pScene)
   1.243 +{
   1.244 +	DefaultLogger::get()->debug("OptimizeGraphProcess begin");
   1.245 +	nodes_in = nodes_out = count_merged = 0;
   1.246 +	mScene = pScene;
   1.247 +
   1.248 +	meshes.resize(pScene->mNumMeshes,0);
   1.249 +	FindInstancedMeshes(pScene->mRootNode);
   1.250 +
   1.251 +	// build a blacklist of identifiers. If the name of a node matches one of these, we won't touch it
   1.252 +	locked.clear();
   1.253 +	for (std::list<std::string>::const_iterator it = locked_nodes.begin(); it != locked_nodes.end(); ++it) {
   1.254 +#ifdef AI_OG_USE_HASHING
   1.255 +		locked.insert(SuperFastHash((*it).c_str()));
   1.256 +#else
   1.257 +		locked.insert(*it);
   1.258 +#endif
   1.259 +	}
   1.260 +
   1.261 +	for (unsigned int i = 0; i < pScene->mNumAnimations; ++i) {
   1.262 +		for (unsigned int a = 0; a < pScene->mAnimations[i]->mNumChannels; ++a) {
   1.263 +		
   1.264 +			aiNodeAnim* anim = pScene->mAnimations[i]->mChannels[a];
   1.265 +			locked.insert(AI_OG_GETKEY(anim->mNodeName));
   1.266 +		}
   1.267 +	}
   1.268 +
   1.269 +	for (unsigned int i = 0; i < pScene->mNumMeshes; ++i) {
   1.270 +		for (unsigned int a = 0; a < pScene->mMeshes[i]->mNumBones; ++a) {
   1.271 +		
   1.272 +			aiBone* bone = pScene->mMeshes[i]->mBones[a];
   1.273 +			locked.insert(AI_OG_GETKEY(bone->mName));
   1.274 +
   1.275 +			// HACK: Meshes referencing bones may not be transformed; we need to look them.
   1.276 +			// The easiest way to do this is to increase their reference counters ...
   1.277 +			meshes[i] += 2;
   1.278 +		}
   1.279 +	}
   1.280 +
   1.281 +	for (unsigned int i = 0; i < pScene->mNumCameras; ++i) {
   1.282 +		aiCamera* cam = pScene->mCameras[i];
   1.283 +		locked.insert(AI_OG_GETKEY(cam->mName));
   1.284 +	}
   1.285 +
   1.286 +	for (unsigned int i = 0; i < pScene->mNumLights; ++i) {
   1.287 +		aiLight* lgh = pScene->mLights[i];
   1.288 +		locked.insert(AI_OG_GETKEY(lgh->mName));
   1.289 +	}
   1.290 +
   1.291 +	// Insert a dummy master node and make it read-only
   1.292 +	aiNode* dummy_root = new aiNode(AI_RESERVED_NODE_NAME);
   1.293 +	locked.insert(AI_OG_GETKEY(dummy_root->mName));
   1.294 +
   1.295 +	const aiString prev = pScene->mRootNode->mName;
   1.296 +	pScene->mRootNode->mParent = dummy_root;
   1.297 +
   1.298 +	dummy_root->mChildren = new aiNode*[dummy_root->mNumChildren = 1];
   1.299 +	dummy_root->mChildren[0] = pScene->mRootNode;
   1.300 +
   1.301 +	// Do our recursive processing of scenegraph nodes. For each node collect
   1.302 +	// a fully new list of children and allow their children to place themselves
   1.303 +	// on the same hierarchy layer as their parents.
   1.304 +	std::list<aiNode*> nodes;
   1.305 +	CollectNewChildren (dummy_root,nodes);
   1.306 +
   1.307 +	ai_assert(nodes.size() == 1);
   1.308 +
   1.309 +	if (dummy_root->mNumChildren == 0) {
   1.310 +		pScene->mRootNode = NULL;
   1.311 +		throw DeadlyImportError("After optimizing the scene graph, no data remains");
   1.312 +	}
   1.313 +
   1.314 +	if (dummy_root->mNumChildren > 1) {
   1.315 +		pScene->mRootNode = dummy_root;
   1.316 +	
   1.317 +		// Keep the dummy node but assign the name of the old root node to it
   1.318 +		pScene->mRootNode->mName = prev;
   1.319 +	}
   1.320 +	else {
   1.321 +		
   1.322 +		// Remove the dummy root node again.
   1.323 +		pScene->mRootNode = dummy_root->mChildren[0];
   1.324 +
   1.325 +		dummy_root->mChildren[0] = NULL;
   1.326 +		delete dummy_root;
   1.327 +	}
   1.328 +
   1.329 +	pScene->mRootNode->mParent = NULL;
   1.330 +	if (!DefaultLogger::isNullLogger()) {
   1.331 +		if ( nodes_in != nodes_out) {
   1.332 +
   1.333 +			char buf[512];
   1.334 +			sprintf(buf,"OptimizeGraphProcess finished; Input nodes: %i, Output nodes: %i",nodes_in,nodes_out);
   1.335 +			DefaultLogger::get()->info(buf);
   1.336 +		}
   1.337 +		else DefaultLogger::get()->debug("OptimizeGraphProcess finished");
   1.338 +	}
   1.339 +	meshes.clear();
   1.340 +	locked.clear();
   1.341 +}
   1.342 +
   1.343 +// ------------------------------------------------------------------------------------------------
   1.344 +// Buidl a LUT of all instanced meshes
   1.345 +void OptimizeGraphProcess::FindInstancedMeshes (aiNode* pNode)
   1.346 +{
   1.347 +	for (unsigned int i = 0; i < pNode->mNumMeshes;++i) {
   1.348 +		++meshes[pNode->mMeshes[i]]; 
   1.349 +	}
   1.350 +
   1.351 +	for (unsigned int i = 0; i < pNode->mNumChildren; ++i)
   1.352 +		FindInstancedMeshes(pNode->mChildren[i]);
   1.353 +}
   1.354 +
   1.355 +#endif // !! ASSIMP_BUILD_NO_OPTIMIZEGRAPH_PROCESS