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  FindInstancesProcess.cpp
nuclear@0:  *  @brief Implementation of the aiProcess_FindInstances postprocessing step
nuclear@0: */
nuclear@0: 
nuclear@0: #include "AssimpPCH.h"
nuclear@0: #include "FindInstancesProcess.h"
nuclear@0: 
nuclear@0: using namespace Assimp;
nuclear@0: 
nuclear@0: // ------------------------------------------------------------------------------------------------
nuclear@0: // Constructor to be privately used by Importer
nuclear@0: FindInstancesProcess::FindInstancesProcess()
nuclear@0: :	configSpeedFlag (false)
nuclear@0: {}
nuclear@0: 
nuclear@0: // ------------------------------------------------------------------------------------------------
nuclear@0: // Destructor, private as well
nuclear@0: FindInstancesProcess::~FindInstancesProcess()
nuclear@0: {}
nuclear@0: 
nuclear@0: // ------------------------------------------------------------------------------------------------
nuclear@0: // Returns whether the processing step is present in the given flag field.
nuclear@0: bool FindInstancesProcess::IsActive( unsigned int pFlags) const
nuclear@0: {
nuclear@0: 	// FindInstances makes absolutely no sense together with PreTransformVertices
nuclear@0: 	// fixme: spawn error message somewhere else?
nuclear@0: 	return 0 != (pFlags & aiProcess_FindInstances) && 0 == (pFlags & aiProcess_PreTransformVertices);
nuclear@0: }
nuclear@0: 
nuclear@0: // ------------------------------------------------------------------------------------------------
nuclear@0: // Setup properties for the step
nuclear@0: void FindInstancesProcess::SetupProperties(const Importer* pImp)
nuclear@0: {
nuclear@0: 	// AI_CONFIG_FAVOUR_SPEED
nuclear@0: 	configSpeedFlag = (0 != pImp->GetPropertyInteger(AI_CONFIG_FAVOUR_SPEED,0));
nuclear@0: }
nuclear@0: 
nuclear@0: // ------------------------------------------------------------------------------------------------
nuclear@0: // Compare the bones of two meshes
nuclear@0: bool CompareBones(const aiMesh* orig, const aiMesh* inst)
nuclear@0: {
nuclear@0: 	for (unsigned int i = 0; i < orig->mNumBones;++i) {
nuclear@0: 		aiBone* aha = orig->mBones[i];
nuclear@0: 		aiBone* oha = inst->mBones[i];
nuclear@0: 
nuclear@0: 		if (aha->mNumWeights   != oha->mNumWeights   ||
nuclear@0: 			aha->mOffsetMatrix != oha->mOffsetMatrix ||
nuclear@0: 			aha->mNumWeights   != oha->mNumWeights) {
nuclear@0: 			return false;
nuclear@0: 		}
nuclear@0: 
nuclear@0: 		// compare weight per weight ---
nuclear@0: 		for (unsigned int n = 0; n < aha->mNumWeights;++n) {
nuclear@0: 			if  (aha->mWeights[n].mVertexId != oha->mWeights[n].mVertexId ||
nuclear@0: 				(aha->mWeights[n].mWeight - oha->mWeights[n].mWeight) < 10e-3f) {
nuclear@0: 				return false;
nuclear@0: 			}
nuclear@0: 		}
nuclear@0: 	}
nuclear@0: 	return true;
nuclear@0: }
nuclear@0: 
nuclear@0: // ------------------------------------------------------------------------------------------------
nuclear@0: // Update mesh indices in the node graph
nuclear@0: void UpdateMeshIndices(aiNode* node, unsigned int* lookup)
nuclear@0: {
nuclear@0: 	for (unsigned int n = 0; n < node->mNumMeshes;++n)
nuclear@0: 		node->mMeshes[n] = lookup[node->mMeshes[n]];
nuclear@0: 
nuclear@0: 	for (unsigned int n = 0; n < node->mNumChildren;++n)
nuclear@0: 		UpdateMeshIndices(node->mChildren[n],lookup);
nuclear@0: }
nuclear@0: 
nuclear@0: // ------------------------------------------------------------------------------------------------
nuclear@0: // Executes the post processing step on the given imported data.
nuclear@0: void FindInstancesProcess::Execute( aiScene* pScene)
nuclear@0: {
nuclear@0: 	DefaultLogger::get()->debug("FindInstancesProcess begin");
nuclear@0: 	if (pScene->mNumMeshes) {
nuclear@0: 
nuclear@0: 		// use a pseudo hash for all meshes in the scene to quickly find 
nuclear@0: 		// the ones which are possibly equal. This step is executed early 
nuclear@0: 		// in the pipeline, so we could, depending on the file format,
nuclear@0: 		// have several thousand small meshes. That's too much for a brute
nuclear@0: 		// everyone-against-everyone check involving up to 10 comparisons
nuclear@0: 		// each.
nuclear@0: 		boost::scoped_array<uint64_t> hashes (new uint64_t[pScene->mNumMeshes]);
nuclear@0: 		boost::scoped_array<unsigned int> remapping (new unsigned int[pScene->mNumMeshes]);
nuclear@0: 
nuclear@0: 		unsigned int numMeshesOut = 0;
nuclear@0: 		for (unsigned int i = 0; i < pScene->mNumMeshes; ++i) {
nuclear@0: 
nuclear@0: 			aiMesh* inst = pScene->mMeshes[i];
nuclear@0: 			hashes[i] = GetMeshHash(inst);
nuclear@0: 
nuclear@0: 			for (int a = i-1; a >= 0; --a) {
nuclear@0: 				if (hashes[i] == hashes[a])
nuclear@0: 				{
nuclear@0: 					aiMesh* orig = pScene->mMeshes[a];
nuclear@0: 					if (!orig)
nuclear@0: 						continue;
nuclear@0: 					
nuclear@0: 					// check for hash collision .. we needn't check
nuclear@0: 					// the vertex format, it *must* match due to the
nuclear@0: 					// (brilliant) construction of the hash
nuclear@0: 					if (orig->mNumBones       != inst->mNumBones      ||
nuclear@0: 						orig->mNumFaces       != inst->mNumFaces      ||
nuclear@0: 						orig->mNumVertices    != inst->mNumVertices   ||
nuclear@0: 						orig->mMaterialIndex  != inst->mMaterialIndex ||
nuclear@0: 						orig->mPrimitiveTypes != inst->mPrimitiveTypes)
nuclear@0: 						continue;
nuclear@0: 
nuclear@0: 					// up to now the meshes are equal. find an appropriate
nuclear@0: 					// epsilon to compare position differences against
nuclear@0: 					float epsilon = ComputePositionEpsilon(inst);
nuclear@0: 					epsilon *= epsilon;
nuclear@0: 
nuclear@0: 					// now compare vertex positions, normals,
nuclear@0: 					// tangents and bitangents using this epsilon.
nuclear@0: 					if (orig->HasPositions()) {
nuclear@0: 						if(!CompareArrays(orig->mVertices,inst->mVertices,orig->mNumVertices,epsilon))
nuclear@0: 							continue;
nuclear@0: 					}
nuclear@0: 					if (orig->HasNormals()) {
nuclear@0: 						if(!CompareArrays(orig->mNormals,inst->mNormals,orig->mNumVertices,epsilon))
nuclear@0: 							continue;
nuclear@0: 					}
nuclear@0: 					if (orig->HasTangentsAndBitangents()) {
nuclear@0: 						if (!CompareArrays(orig->mTangents,inst->mTangents,orig->mNumVertices,epsilon) ||
nuclear@0: 							!CompareArrays(orig->mBitangents,inst->mBitangents,orig->mNumVertices,epsilon))
nuclear@0: 							continue;
nuclear@0: 					}
nuclear@0: 
nuclear@0: 					// use a constant epsilon for colors and UV coordinates
nuclear@0: 					static const float uvEpsilon = 10e-4f;
nuclear@0: 
nuclear@0: 					{
nuclear@0: 						unsigned int i, end = orig->GetNumUVChannels();
nuclear@0: 						for(i = 0; i < end; ++i) {
nuclear@0: 							if (!orig->mTextureCoords[i]) {
nuclear@0: 								continue;
nuclear@0: 							}
nuclear@0: 							if(!CompareArrays(orig->mTextureCoords[i],inst->mTextureCoords[i],orig->mNumVertices,uvEpsilon)) {
nuclear@0: 								break;	
nuclear@0: 							}
nuclear@0: 						}
nuclear@0: 						if (i != end) {
nuclear@0: 							continue;
nuclear@0: 						}
nuclear@0: 					}
nuclear@0: 					{
nuclear@0: 						unsigned int i, end = orig->GetNumColorChannels();
nuclear@0: 						for(i = 0; i < end; ++i) {
nuclear@0: 							if (!orig->mColors[i]) {
nuclear@0: 								continue;
nuclear@0: 							}
nuclear@0: 							if(!CompareArrays(orig->mColors[i],inst->mColors[i],orig->mNumVertices,uvEpsilon)) {
nuclear@0: 								break;	
nuclear@0: 							}
nuclear@0: 						}
nuclear@0: 						if (i != end) {
nuclear@0: 							continue;
nuclear@0: 						}
nuclear@0: 					}
nuclear@0: 
nuclear@0: 					// These two checks are actually quite expensive and almost *never* required.
nuclear@0: 					// Almost. That's why they're still here. But there's no reason to do them
nuclear@0: 					// in speed-targeted imports.
nuclear@0: 					if (!configSpeedFlag) {
nuclear@0: 
nuclear@0: 						// It seems to be strange, but we really need to check whether the
nuclear@0: 						// bones are identical too. Although it's extremely unprobable
nuclear@0: 						// that they're not if control reaches here, we need to deal
nuclear@0: 						// with unprobable cases, too. It could still be that there are
nuclear@0: 						// equal shapes which are deformed differently.
nuclear@0: 						if (!CompareBones(orig,inst))
nuclear@0: 							continue;
nuclear@0: 
nuclear@0: 						// For completeness ... compare even the index buffers for equality
nuclear@0: 						// face order & winding order doesn't care. Input data is in verbose format.
nuclear@0: 						boost::scoped_array<unsigned int> ftbl_orig(new unsigned int[orig->mNumVertices]);
nuclear@0: 						boost::scoped_array<unsigned int> ftbl_inst(new unsigned int[orig->mNumVertices]);
nuclear@0: 
nuclear@0: 						for (unsigned int tt = 0; tt < orig->mNumFaces;++tt) {
nuclear@0: 							aiFace& f = orig->mFaces[tt];
nuclear@0: 							for (unsigned int nn = 0; nn < f.mNumIndices;++nn)
nuclear@0: 								ftbl_orig[f.mIndices[nn]] = tt;
nuclear@0: 
nuclear@0: 							aiFace& f2 = inst->mFaces[tt];
nuclear@0: 							for (unsigned int nn = 0; nn < f2.mNumIndices;++nn)
nuclear@0: 								ftbl_inst[f2.mIndices[nn]] = tt;
nuclear@0: 						}
nuclear@0: 						if (0 != ::memcmp(ftbl_inst.get(),ftbl_orig.get(),orig->mNumVertices*sizeof(unsigned int)))
nuclear@0: 							continue;
nuclear@0: 					}
nuclear@0: 
nuclear@0: 					// We're still here. Or in other words: 'inst' is an instance of 'orig'.
nuclear@0: 					// Place a marker in our list that we can easily update mesh indices.
nuclear@0: 					remapping[i] = remapping[a];
nuclear@0: 
nuclear@0: 					// Delete the instanced mesh, we don't need it anymore
nuclear@0: 					delete inst;
nuclear@0: 					pScene->mMeshes[i] = NULL;
nuclear@0: 					break;
nuclear@0: 				}
nuclear@0: 			}
nuclear@0: 
nuclear@0: 			// If we didn't find a match for the current mesh: keep it
nuclear@0: 			if (pScene->mMeshes[i]) {
nuclear@0: 				remapping[i] = numMeshesOut++;
nuclear@0: 			}
nuclear@0: 		}
nuclear@0: 		ai_assert(0 != numMeshesOut);
nuclear@0: 		if (numMeshesOut != pScene->mNumMeshes) {
nuclear@0: 
nuclear@0: 			// Collapse the meshes array by removing all NULL entries
nuclear@0: 			for (unsigned int real = 0, i = 0; real < numMeshesOut; ++i) {
nuclear@0: 				if (pScene->mMeshes[i])
nuclear@0: 					pScene->mMeshes[real++] = pScene->mMeshes[i];
nuclear@0: 			}
nuclear@0: 
nuclear@0: 			// And update the nodegraph with our nice lookup table
nuclear@0: 			UpdateMeshIndices(pScene->mRootNode,remapping.get());
nuclear@0: 
nuclear@0: 			// write to log
nuclear@0: 			if (!DefaultLogger::isNullLogger()) {
nuclear@0: 			
nuclear@0: 				char buffer[512];
nuclear@0: 				::sprintf(buffer,"FindInstancesProcess finished. Found %i instances",pScene->mNumMeshes-numMeshesOut);
nuclear@0: 				DefaultLogger::get()->info(buffer); 
nuclear@0: 			}
nuclear@0: 			pScene->mNumMeshes = numMeshesOut;
nuclear@0: 		}
nuclear@0: 		else DefaultLogger::get()->debug("FindInstancesProcess finished. No instanced meshes found"); 
nuclear@0: 	}
nuclear@0: }