1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/libs/assimp/FindInstancesProcess.cpp	Sat Feb 01 19:58:19 2014 +0200
     1.3 @@ -0,0 +1,277 @@
     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  FindInstancesProcess.cpp
    1.46 + *  @brief Implementation of the aiProcess_FindInstances postprocessing step
    1.47 +*/
    1.48 +
    1.49 +#include "AssimpPCH.h"
    1.50 +#include "FindInstancesProcess.h"
    1.51 +
    1.52 +using namespace Assimp;
    1.53 +
    1.54 +// ------------------------------------------------------------------------------------------------
    1.55 +// Constructor to be privately used by Importer
    1.56 +FindInstancesProcess::FindInstancesProcess()
    1.57 +:	configSpeedFlag (false)
    1.58 +{}
    1.59 +
    1.60 +// ------------------------------------------------------------------------------------------------
    1.61 +// Destructor, private as well
    1.62 +FindInstancesProcess::~FindInstancesProcess()
    1.63 +{}
    1.64 +
    1.65 +// ------------------------------------------------------------------------------------------------
    1.66 +// Returns whether the processing step is present in the given flag field.
    1.67 +bool FindInstancesProcess::IsActive( unsigned int pFlags) const
    1.68 +{
    1.69 +	// FindInstances makes absolutely no sense together with PreTransformVertices
    1.70 +	// fixme: spawn error message somewhere else?
    1.71 +	return 0 != (pFlags & aiProcess_FindInstances) && 0 == (pFlags & aiProcess_PreTransformVertices);
    1.72 +}
    1.73 +
    1.74 +// ------------------------------------------------------------------------------------------------
    1.75 +// Setup properties for the step
    1.76 +void FindInstancesProcess::SetupProperties(const Importer* pImp)
    1.77 +{
    1.78 +	// AI_CONFIG_FAVOUR_SPEED
    1.79 +	configSpeedFlag = (0 != pImp->GetPropertyInteger(AI_CONFIG_FAVOUR_SPEED,0));
    1.80 +}
    1.81 +
    1.82 +// ------------------------------------------------------------------------------------------------
    1.83 +// Compare the bones of two meshes
    1.84 +bool CompareBones(const aiMesh* orig, const aiMesh* inst)
    1.85 +{
    1.86 +	for (unsigned int i = 0; i < orig->mNumBones;++i) {
    1.87 +		aiBone* aha = orig->mBones[i];
    1.88 +		aiBone* oha = inst->mBones[i];
    1.89 +
    1.90 +		if (aha->mNumWeights   != oha->mNumWeights   ||
    1.91 +			aha->mOffsetMatrix != oha->mOffsetMatrix ||
    1.92 +			aha->mNumWeights   != oha->mNumWeights) {
    1.93 +			return false;
    1.94 +		}
    1.95 +
    1.96 +		// compare weight per weight ---
    1.97 +		for (unsigned int n = 0; n < aha->mNumWeights;++n) {
    1.98 +			if  (aha->mWeights[n].mVertexId != oha->mWeights[n].mVertexId ||
    1.99 +				(aha->mWeights[n].mWeight - oha->mWeights[n].mWeight) < 10e-3f) {
   1.100 +				return false;
   1.101 +			}
   1.102 +		}
   1.103 +	}
   1.104 +	return true;
   1.105 +}
   1.106 +
   1.107 +// ------------------------------------------------------------------------------------------------
   1.108 +// Update mesh indices in the node graph
   1.109 +void UpdateMeshIndices(aiNode* node, unsigned int* lookup)
   1.110 +{
   1.111 +	for (unsigned int n = 0; n < node->mNumMeshes;++n)
   1.112 +		node->mMeshes[n] = lookup[node->mMeshes[n]];
   1.113 +
   1.114 +	for (unsigned int n = 0; n < node->mNumChildren;++n)
   1.115 +		UpdateMeshIndices(node->mChildren[n],lookup);
   1.116 +}
   1.117 +
   1.118 +// ------------------------------------------------------------------------------------------------
   1.119 +// Executes the post processing step on the given imported data.
   1.120 +void FindInstancesProcess::Execute( aiScene* pScene)
   1.121 +{
   1.122 +	DefaultLogger::get()->debug("FindInstancesProcess begin");
   1.123 +	if (pScene->mNumMeshes) {
   1.124 +
   1.125 +		// use a pseudo hash for all meshes in the scene to quickly find 
   1.126 +		// the ones which are possibly equal. This step is executed early 
   1.127 +		// in the pipeline, so we could, depending on the file format,
   1.128 +		// have several thousand small meshes. That's too much for a brute
   1.129 +		// everyone-against-everyone check involving up to 10 comparisons
   1.130 +		// each.
   1.131 +		boost::scoped_array<uint64_t> hashes (new uint64_t[pScene->mNumMeshes]);
   1.132 +		boost::scoped_array<unsigned int> remapping (new unsigned int[pScene->mNumMeshes]);
   1.133 +
   1.134 +		unsigned int numMeshesOut = 0;
   1.135 +		for (unsigned int i = 0; i < pScene->mNumMeshes; ++i) {
   1.136 +
   1.137 +			aiMesh* inst = pScene->mMeshes[i];
   1.138 +			hashes[i] = GetMeshHash(inst);
   1.139 +
   1.140 +			for (int a = i-1; a >= 0; --a) {
   1.141 +				if (hashes[i] == hashes[a])
   1.142 +				{
   1.143 +					aiMesh* orig = pScene->mMeshes[a];
   1.144 +					if (!orig)
   1.145 +						continue;
   1.146 +					
   1.147 +					// check for hash collision .. we needn't check
   1.148 +					// the vertex format, it *must* match due to the
   1.149 +					// (brilliant) construction of the hash
   1.150 +					if (orig->mNumBones       != inst->mNumBones      ||
   1.151 +						orig->mNumFaces       != inst->mNumFaces      ||
   1.152 +						orig->mNumVertices    != inst->mNumVertices   ||
   1.153 +						orig->mMaterialIndex  != inst->mMaterialIndex ||
   1.154 +						orig->mPrimitiveTypes != inst->mPrimitiveTypes)
   1.155 +						continue;
   1.156 +
   1.157 +					// up to now the meshes are equal. find an appropriate
   1.158 +					// epsilon to compare position differences against
   1.159 +					float epsilon = ComputePositionEpsilon(inst);
   1.160 +					epsilon *= epsilon;
   1.161 +
   1.162 +					// now compare vertex positions, normals,
   1.163 +					// tangents and bitangents using this epsilon.
   1.164 +					if (orig->HasPositions()) {
   1.165 +						if(!CompareArrays(orig->mVertices,inst->mVertices,orig->mNumVertices,epsilon))
   1.166 +							continue;
   1.167 +					}
   1.168 +					if (orig->HasNormals()) {
   1.169 +						if(!CompareArrays(orig->mNormals,inst->mNormals,orig->mNumVertices,epsilon))
   1.170 +							continue;
   1.171 +					}
   1.172 +					if (orig->HasTangentsAndBitangents()) {
   1.173 +						if (!CompareArrays(orig->mTangents,inst->mTangents,orig->mNumVertices,epsilon) ||
   1.174 +							!CompareArrays(orig->mBitangents,inst->mBitangents,orig->mNumVertices,epsilon))
   1.175 +							continue;
   1.176 +					}
   1.177 +
   1.178 +					// use a constant epsilon for colors and UV coordinates
   1.179 +					static const float uvEpsilon = 10e-4f;
   1.180 +
   1.181 +					{
   1.182 +						unsigned int i, end = orig->GetNumUVChannels();
   1.183 +						for(i = 0; i < end; ++i) {
   1.184 +							if (!orig->mTextureCoords[i]) {
   1.185 +								continue;
   1.186 +							}
   1.187 +							if(!CompareArrays(orig->mTextureCoords[i],inst->mTextureCoords[i],orig->mNumVertices,uvEpsilon)) {
   1.188 +								break;	
   1.189 +							}
   1.190 +						}
   1.191 +						if (i != end) {
   1.192 +							continue;
   1.193 +						}
   1.194 +					}
   1.195 +					{
   1.196 +						unsigned int i, end = orig->GetNumColorChannels();
   1.197 +						for(i = 0; i < end; ++i) {
   1.198 +							if (!orig->mColors[i]) {
   1.199 +								continue;
   1.200 +							}
   1.201 +							if(!CompareArrays(orig->mColors[i],inst->mColors[i],orig->mNumVertices,uvEpsilon)) {
   1.202 +								break;	
   1.203 +							}
   1.204 +						}
   1.205 +						if (i != end) {
   1.206 +							continue;
   1.207 +						}
   1.208 +					}
   1.209 +
   1.210 +					// These two checks are actually quite expensive and almost *never* required.
   1.211 +					// Almost. That's why they're still here. But there's no reason to do them
   1.212 +					// in speed-targeted imports.
   1.213 +					if (!configSpeedFlag) {
   1.214 +
   1.215 +						// It seems to be strange, but we really need to check whether the
   1.216 +						// bones are identical too. Although it's extremely unprobable
   1.217 +						// that they're not if control reaches here, we need to deal
   1.218 +						// with unprobable cases, too. It could still be that there are
   1.219 +						// equal shapes which are deformed differently.
   1.220 +						if (!CompareBones(orig,inst))
   1.221 +							continue;
   1.222 +
   1.223 +						// For completeness ... compare even the index buffers for equality
   1.224 +						// face order & winding order doesn't care. Input data is in verbose format.
   1.225 +						boost::scoped_array<unsigned int> ftbl_orig(new unsigned int[orig->mNumVertices]);
   1.226 +						boost::scoped_array<unsigned int> ftbl_inst(new unsigned int[orig->mNumVertices]);
   1.227 +
   1.228 +						for (unsigned int tt = 0; tt < orig->mNumFaces;++tt) {
   1.229 +							aiFace& f = orig->mFaces[tt];
   1.230 +							for (unsigned int nn = 0; nn < f.mNumIndices;++nn)
   1.231 +								ftbl_orig[f.mIndices[nn]] = tt;
   1.232 +
   1.233 +							aiFace& f2 = inst->mFaces[tt];
   1.234 +							for (unsigned int nn = 0; nn < f2.mNumIndices;++nn)
   1.235 +								ftbl_inst[f2.mIndices[nn]] = tt;
   1.236 +						}
   1.237 +						if (0 != ::memcmp(ftbl_inst.get(),ftbl_orig.get(),orig->mNumVertices*sizeof(unsigned int)))
   1.238 +							continue;
   1.239 +					}
   1.240 +
   1.241 +					// We're still here. Or in other words: 'inst' is an instance of 'orig'.
   1.242 +					// Place a marker in our list that we can easily update mesh indices.
   1.243 +					remapping[i] = remapping[a];
   1.244 +
   1.245 +					// Delete the instanced mesh, we don't need it anymore
   1.246 +					delete inst;
   1.247 +					pScene->mMeshes[i] = NULL;
   1.248 +					break;
   1.249 +				}
   1.250 +			}
   1.251 +
   1.252 +			// If we didn't find a match for the current mesh: keep it
   1.253 +			if (pScene->mMeshes[i]) {
   1.254 +				remapping[i] = numMeshesOut++;
   1.255 +			}
   1.256 +		}
   1.257 +		ai_assert(0 != numMeshesOut);
   1.258 +		if (numMeshesOut != pScene->mNumMeshes) {
   1.259 +
   1.260 +			// Collapse the meshes array by removing all NULL entries
   1.261 +			for (unsigned int real = 0, i = 0; real < numMeshesOut; ++i) {
   1.262 +				if (pScene->mMeshes[i])
   1.263 +					pScene->mMeshes[real++] = pScene->mMeshes[i];
   1.264 +			}
   1.265 +
   1.266 +			// And update the nodegraph with our nice lookup table
   1.267 +			UpdateMeshIndices(pScene->mRootNode,remapping.get());
   1.268 +
   1.269 +			// write to log
   1.270 +			if (!DefaultLogger::isNullLogger()) {
   1.271 +			
   1.272 +				char buffer[512];
   1.273 +				::sprintf(buffer,"FindInstancesProcess finished. Found %i instances",pScene->mNumMeshes-numMeshesOut);
   1.274 +				DefaultLogger::get()->info(buffer); 
   1.275 +			}
   1.276 +			pScene->mNumMeshes = numMeshesOut;
   1.277 +		}
   1.278 +		else DefaultLogger::get()->debug("FindInstancesProcess finished. No instanced meshes found"); 
   1.279 +	}
   1.280 +}