nuclear@0: /*
nuclear@0: ---------------------------------------------------------------------------
nuclear@0: Open Asset Import Library (assimp)
nuclear@0: ---------------------------------------------------------------------------
nuclear@0: 
nuclear@0: Copyright (c) 2006-2012, assimp team
nuclear@0: 
nuclear@0: All rights reserved.
nuclear@0: 
nuclear@0: Redistribution and use of this software in source and binary forms, 
nuclear@0: with or without modification, are permitted provided that the following 
nuclear@0: conditions are met:
nuclear@0: 
nuclear@0: * Redistributions of source code must retain the above
nuclear@0:   copyright notice, this list of conditions and the
nuclear@0:   following disclaimer.
nuclear@0: 
nuclear@0: * Redistributions in binary form must reproduce the above
nuclear@0:   copyright notice, this list of conditions and the
nuclear@0:   following disclaimer in the documentation and/or other
nuclear@0:   materials provided with the distribution.
nuclear@0: 
nuclear@0: * Neither the name of the assimp team, nor the names of its
nuclear@0:   contributors may be used to endorse or promote products
nuclear@0:   derived from this software without specific prior
nuclear@0:   written permission of the assimp team.
nuclear@0: 
nuclear@0: THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 
nuclear@0: "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 
nuclear@0: LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
nuclear@0: A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 
nuclear@0: OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
nuclear@0: SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 
nuclear@0: LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
nuclear@0: DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 
nuclear@0: THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 
nuclear@0: (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 
nuclear@0: OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
nuclear@0: ---------------------------------------------------------------------------
nuclear@0: */
nuclear@0: 
nuclear@0: /** @file  OptimizeGraph.cpp
nuclear@0:  *  @brief Implementation of the aiProcess_OptimizGraph step
nuclear@0:  */
nuclear@0: 
nuclear@0: #include "AssimpPCH.h"
nuclear@0: #ifndef ASSIMP_BUILD_NO_OPTIMIZEGRAPH_PROCESS
nuclear@0: 
nuclear@0: using namespace Assimp;
nuclear@0: #include "OptimizeGraph.h"
nuclear@0: #include "ProcessHelper.h"
nuclear@0: #include "SceneCombiner.h"
nuclear@0: 
nuclear@0: #define AI_RESERVED_NODE_NAME "$Reserved_And_Evil"
nuclear@0: 
nuclear@0: /* AI_OG_USE_HASHING enables the use of hashing to speed-up std::set lookups.
nuclear@0:  * The unhashed variant should be faster, except for *very* large data sets
nuclear@0:  */
nuclear@0: #ifdef AI_OG_USE_HASHING
nuclear@0: 	// Use our standard hashing function to compute the hash 
nuclear@0: #	define AI_OG_GETKEY(str) SuperFastHash(str.data,str.length)
nuclear@0: #else
nuclear@0: 	// Otherwise hope that std::string will utilize a static buffer 
nuclear@0: 	// for shorter node names. This would avoid endless heap copying.
nuclear@0: #	define AI_OG_GETKEY(str) std::string(str.data)
nuclear@0: #endif
nuclear@0: 
nuclear@0: // ------------------------------------------------------------------------------------------------
nuclear@0: // Constructor to be privately used by Importer
nuclear@0: OptimizeGraphProcess::OptimizeGraphProcess()
nuclear@0: {}
nuclear@0: 
nuclear@0: // ------------------------------------------------------------------------------------------------
nuclear@0: // Destructor, private as well
nuclear@0: OptimizeGraphProcess::~OptimizeGraphProcess()
nuclear@0: {}
nuclear@0: 
nuclear@0: // ------------------------------------------------------------------------------------------------
nuclear@0: // Returns whether the processing step is present in the given flag field.
nuclear@0: bool OptimizeGraphProcess::IsActive( unsigned int pFlags) const
nuclear@0: {
nuclear@0: 	return (0 != (pFlags & aiProcess_OptimizeGraph));
nuclear@0: }
nuclear@0: 
nuclear@0: // ------------------------------------------------------------------------------------------------
nuclear@0: // Setup properties for the postprocessing step
nuclear@0: void OptimizeGraphProcess::SetupProperties(const Importer* pImp)
nuclear@0: {	
nuclear@0: 	// Get value of AI_CONFIG_PP_OG_EXCLUDE_LIST
nuclear@0: 	std::string tmp = pImp->GetPropertyString(AI_CONFIG_PP_OG_EXCLUDE_LIST,"");
nuclear@0: 	AddLockedNodeList(tmp);
nuclear@0: }
nuclear@0: 
nuclear@0: // ------------------------------------------------------------------------------------------------
nuclear@0: // Collect new children
nuclear@0: void OptimizeGraphProcess::CollectNewChildren(aiNode* nd, std::list<aiNode*>& nodes)
nuclear@0: {
nuclear@0: 	nodes_in += nd->mNumChildren;
nuclear@0: 
nuclear@0: 	// Process children
nuclear@0: 	std::list<aiNode*> child_nodes;
nuclear@0: 	for (unsigned int i = 0; i < nd->mNumChildren; ++i) {
nuclear@0: 
nuclear@0: 		CollectNewChildren(nd->mChildren[i],child_nodes);
nuclear@0: 		nd->mChildren[i] = NULL;
nuclear@0: 	}
nuclear@0: 
nuclear@0: 	// Check whether we need this node; if not we can replace it by our own children (warn, danger of incest).
nuclear@0: 	if (locked.find(AI_OG_GETKEY(nd->mName)) == locked.end() ) {
nuclear@0: 		for (std::list<aiNode*>::iterator it = child_nodes.begin(); it != child_nodes.end();) {
nuclear@0: 
nuclear@0: 			if (locked.find(AI_OG_GETKEY((*it)->mName)) == locked.end()) {
nuclear@0: 				(*it)->mTransformation = nd->mTransformation * (*it)->mTransformation;
nuclear@0: 				nodes.push_back(*it);
nuclear@0: 
nuclear@0: 				it = child_nodes.erase(it);
nuclear@0: 				continue;
nuclear@0: 			}
nuclear@0: 			++it;
nuclear@0: 		}
nuclear@0: 
nuclear@0: 		if (nd->mNumMeshes || child_nodes.size()) { 
nuclear@0: 			nodes.push_back(nd);
nuclear@0: 		}
nuclear@0: 		else {
nuclear@0: 			delete nd; /* bye, node */
nuclear@0: 			return;
nuclear@0: 		}
nuclear@0: 	}
nuclear@0: 	else {
nuclear@0: 		
nuclear@0: 		// Retain our current position in the hierarchy
nuclear@0: 		nodes.push_back(nd);
nuclear@0: 
nuclear@0: 		// Now check for possible optimizations in our list of child nodes. join as many as possible
nuclear@0: 		aiNode* join_master = NULL;
nuclear@0: 		aiMatrix4x4 inv;
nuclear@0: 
nuclear@0: 		const LockedSetType::const_iterator end = locked.end();
nuclear@0: 
nuclear@0: 		std::list<aiNode*> join;
nuclear@0: 		for (std::list<aiNode*>::iterator it = child_nodes.begin(); it != child_nodes.end();)	{
nuclear@0: 			aiNode* child = *it;
nuclear@0: 			if (child->mNumChildren == 0 && locked.find(AI_OG_GETKEY(child->mName)) == end) {
nuclear@0: 			
nuclear@0: 				// There may be no instanced meshes
nuclear@0: 				unsigned int n = 0;
nuclear@0: 				for (; n < child->mNumMeshes;++n) {
nuclear@0: 					if (meshes[child->mMeshes[n]] > 1) {
nuclear@0: 						break;
nuclear@0: 					}
nuclear@0: 				}
nuclear@0: 				if (n == child->mNumMeshes) {
nuclear@0: 
nuclear@0: 					if (!join_master) {
nuclear@0: 						join_master = child;
nuclear@0: 						inv = join_master->mTransformation;
nuclear@0: 						inv.Inverse();
nuclear@0: 					}
nuclear@0: 					else {
nuclear@0: 
nuclear@0: 						child->mTransformation = inv * child->mTransformation ;
nuclear@0: 
nuclear@0: 						join.push_back(child);	
nuclear@0: 						it = child_nodes.erase(it);
nuclear@0: 						continue;
nuclear@0: 					}
nuclear@0: 				}
nuclear@0: 			}
nuclear@0: 			++it;
nuclear@0: 		}
nuclear@0: 		if (join_master && join.size()) {
nuclear@0: 			join_master->mName.length = sprintf(join_master->mName.data,"$MergedNode_%i",count_merged++);
nuclear@0: 
nuclear@0: 			unsigned int out_meshes = 0;
nuclear@0: 			for (std::list<aiNode*>::iterator it = join.begin(); it != join.end(); ++it) {
nuclear@0: 				out_meshes += (*it)->mNumMeshes;
nuclear@0: 			}
nuclear@0: 			
nuclear@0: 			// copy all mesh references in one array
nuclear@0: 			if (out_meshes) {
nuclear@0: 				unsigned int* meshes = new unsigned int[out_meshes+join_master->mNumMeshes], *tmp = meshes;
nuclear@0: 				for (unsigned int n = 0; n < join_master->mNumMeshes;++n) {
nuclear@0: 					*tmp++ = join_master->mMeshes[n];		
nuclear@0: 				}
nuclear@0: 
nuclear@0: 				for (std::list<aiNode*>::iterator it = join.begin(); it != join.end(); ++it) {
nuclear@0: 					for (unsigned int n = 0; n < (*it)->mNumMeshes; ++n) {
nuclear@0: 
nuclear@0: 						*tmp = (*it)->mMeshes[n];
nuclear@0: 						aiMesh* mesh = mScene->mMeshes[*tmp++];
nuclear@0: 
nuclear@0: 						// manually move the mesh into the right coordinate system
nuclear@0: 						const aiMatrix3x3 IT = aiMatrix3x3( (*it)->mTransformation ).Inverse().Transpose(); 
nuclear@0: 						for (unsigned int a = 0; a < mesh->mNumVertices; ++a) {
nuclear@0: 						
nuclear@0: 							mesh->mVertices[a] *= (*it)->mTransformation;
nuclear@0: 
nuclear@0: 							if (mesh->HasNormals())
nuclear@0: 								mesh->mNormals[a] *= IT;
nuclear@0: 
nuclear@0: 							if (mesh->HasTangentsAndBitangents()) {
nuclear@0: 								mesh->mTangents[a] *= IT;
nuclear@0: 								mesh->mBitangents[a] *= IT;
nuclear@0: 							}
nuclear@0: 						}
nuclear@0: 					}
nuclear@0: 					delete *it; // bye, node
nuclear@0: 				}
nuclear@0: 				delete[] join_master->mMeshes;
nuclear@0: 				join_master->mMeshes = meshes;
nuclear@0: 				join_master->mNumMeshes += out_meshes;
nuclear@0: 			}
nuclear@0: 		}
nuclear@0: 	}
nuclear@0: 	// reassign children if something changed
nuclear@0: 	if (child_nodes.empty() || child_nodes.size() > nd->mNumChildren) {
nuclear@0: 
nuclear@0: 		delete[] nd->mChildren;
nuclear@0: 
nuclear@0: 		if (child_nodes.size())
nuclear@0: 			nd->mChildren = new aiNode*[child_nodes.size()];
nuclear@0: 		else nd->mChildren = NULL;
nuclear@0: 	}
nuclear@0: 
nuclear@0: 	nd->mNumChildren = child_nodes.size();
nuclear@0: 
nuclear@0: 	aiNode** tmp = nd->mChildren;
nuclear@0: 	for (std::list<aiNode*>::iterator it = child_nodes.begin(); it != child_nodes.end(); ++it) {
nuclear@0: 		aiNode* node = *tmp++ = *it;
nuclear@0: 		node->mParent = nd;
nuclear@0: 	}
nuclear@0: 
nuclear@0: 	nodes_out += child_nodes.size();
nuclear@0: }
nuclear@0: 
nuclear@0: // ------------------------------------------------------------------------------------------------
nuclear@0: // Execute the postprocessing step on the given scene
nuclear@0: void OptimizeGraphProcess::Execute( aiScene* pScene)
nuclear@0: {
nuclear@0: 	DefaultLogger::get()->debug("OptimizeGraphProcess begin");
nuclear@0: 	nodes_in = nodes_out = count_merged = 0;
nuclear@0: 	mScene = pScene;
nuclear@0: 
nuclear@0: 	meshes.resize(pScene->mNumMeshes,0);
nuclear@0: 	FindInstancedMeshes(pScene->mRootNode);
nuclear@0: 
nuclear@0: 	// build a blacklist of identifiers. If the name of a node matches one of these, we won't touch it
nuclear@0: 	locked.clear();
nuclear@0: 	for (std::list<std::string>::const_iterator it = locked_nodes.begin(); it != locked_nodes.end(); ++it) {
nuclear@0: #ifdef AI_OG_USE_HASHING
nuclear@0: 		locked.insert(SuperFastHash((*it).c_str()));
nuclear@0: #else
nuclear@0: 		locked.insert(*it);
nuclear@0: #endif
nuclear@0: 	}
nuclear@0: 
nuclear@0: 	for (unsigned int i = 0; i < pScene->mNumAnimations; ++i) {
nuclear@0: 		for (unsigned int a = 0; a < pScene->mAnimations[i]->mNumChannels; ++a) {
nuclear@0: 		
nuclear@0: 			aiNodeAnim* anim = pScene->mAnimations[i]->mChannels[a];
nuclear@0: 			locked.insert(AI_OG_GETKEY(anim->mNodeName));
nuclear@0: 		}
nuclear@0: 	}
nuclear@0: 
nuclear@0: 	for (unsigned int i = 0; i < pScene->mNumMeshes; ++i) {
nuclear@0: 		for (unsigned int a = 0; a < pScene->mMeshes[i]->mNumBones; ++a) {
nuclear@0: 		
nuclear@0: 			aiBone* bone = pScene->mMeshes[i]->mBones[a];
nuclear@0: 			locked.insert(AI_OG_GETKEY(bone->mName));
nuclear@0: 
nuclear@0: 			// HACK: Meshes referencing bones may not be transformed; we need to look them.
nuclear@0: 			// The easiest way to do this is to increase their reference counters ...
nuclear@0: 			meshes[i] += 2;
nuclear@0: 		}
nuclear@0: 	}
nuclear@0: 
nuclear@0: 	for (unsigned int i = 0; i < pScene->mNumCameras; ++i) {
nuclear@0: 		aiCamera* cam = pScene->mCameras[i];
nuclear@0: 		locked.insert(AI_OG_GETKEY(cam->mName));
nuclear@0: 	}
nuclear@0: 
nuclear@0: 	for (unsigned int i = 0; i < pScene->mNumLights; ++i) {
nuclear@0: 		aiLight* lgh = pScene->mLights[i];
nuclear@0: 		locked.insert(AI_OG_GETKEY(lgh->mName));
nuclear@0: 	}
nuclear@0: 
nuclear@0: 	// Insert a dummy master node and make it read-only
nuclear@0: 	aiNode* dummy_root = new aiNode(AI_RESERVED_NODE_NAME);
nuclear@0: 	locked.insert(AI_OG_GETKEY(dummy_root->mName));
nuclear@0: 
nuclear@0: 	const aiString prev = pScene->mRootNode->mName;
nuclear@0: 	pScene->mRootNode->mParent = dummy_root;
nuclear@0: 
nuclear@0: 	dummy_root->mChildren = new aiNode*[dummy_root->mNumChildren = 1];
nuclear@0: 	dummy_root->mChildren[0] = pScene->mRootNode;
nuclear@0: 
nuclear@0: 	// Do our recursive processing of scenegraph nodes. For each node collect
nuclear@0: 	// a fully new list of children and allow their children to place themselves
nuclear@0: 	// on the same hierarchy layer as their parents.
nuclear@0: 	std::list<aiNode*> nodes;
nuclear@0: 	CollectNewChildren (dummy_root,nodes);
nuclear@0: 
nuclear@0: 	ai_assert(nodes.size() == 1);
nuclear@0: 
nuclear@0: 	if (dummy_root->mNumChildren == 0) {
nuclear@0: 		pScene->mRootNode = NULL;
nuclear@0: 		throw DeadlyImportError("After optimizing the scene graph, no data remains");
nuclear@0: 	}
nuclear@0: 
nuclear@0: 	if (dummy_root->mNumChildren > 1) {
nuclear@0: 		pScene->mRootNode = dummy_root;
nuclear@0: 	
nuclear@0: 		// Keep the dummy node but assign the name of the old root node to it
nuclear@0: 		pScene->mRootNode->mName = prev;
nuclear@0: 	}
nuclear@0: 	else {
nuclear@0: 		
nuclear@0: 		// Remove the dummy root node again.
nuclear@0: 		pScene->mRootNode = dummy_root->mChildren[0];
nuclear@0: 
nuclear@0: 		dummy_root->mChildren[0] = NULL;
nuclear@0: 		delete dummy_root;
nuclear@0: 	}
nuclear@0: 
nuclear@0: 	pScene->mRootNode->mParent = NULL;
nuclear@0: 	if (!DefaultLogger::isNullLogger()) {
nuclear@0: 		if ( nodes_in != nodes_out) {
nuclear@0: 
nuclear@0: 			char buf[512];
nuclear@0: 			sprintf(buf,"OptimizeGraphProcess finished; Input nodes: %i, Output nodes: %i",nodes_in,nodes_out);
nuclear@0: 			DefaultLogger::get()->info(buf);
nuclear@0: 		}
nuclear@0: 		else DefaultLogger::get()->debug("OptimizeGraphProcess finished");
nuclear@0: 	}
nuclear@0: 	meshes.clear();
nuclear@0: 	locked.clear();
nuclear@0: }
nuclear@0: 
nuclear@0: // ------------------------------------------------------------------------------------------------
nuclear@0: // Buidl a LUT of all instanced meshes
nuclear@0: void OptimizeGraphProcess::FindInstancedMeshes (aiNode* pNode)
nuclear@0: {
nuclear@0: 	for (unsigned int i = 0; i < pNode->mNumMeshes;++i) {
nuclear@0: 		++meshes[pNode->mMeshes[i]]; 
nuclear@0: 	}
nuclear@0: 
nuclear@0: 	for (unsigned int i = 0; i < pNode->mNumChildren; ++i)
nuclear@0: 		FindInstancedMeshes(pNode->mChildren[i]);
nuclear@0: }
nuclear@0: 
nuclear@0: #endif // !! ASSIMP_BUILD_NO_OPTIMIZEGRAPH_PROCESS