1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/libs/assimp/JoinVerticesProcess.cpp	Sat Feb 01 19:58:19 2014 +0200
     1.3 @@ -0,0 +1,414 @@
     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 Implementation of the post processing step to join identical vertices
    1.46 + * for all imported meshes
    1.47 + */
    1.48 +
    1.49 +#include "AssimpPCH.h"
    1.50 +#ifndef ASSIMP_BUILD_NO_JOINVERTICES_PROCESS
    1.51 +
    1.52 +#include "JoinVerticesProcess.h"
    1.53 +#include "ProcessHelper.h"
    1.54 +#include "Vertex.h"
    1.55 +#include "TinyFormatter.h"
    1.56 +
    1.57 +using namespace Assimp;
    1.58 +// ------------------------------------------------------------------------------------------------
    1.59 +// Constructor to be privately used by Importer
    1.60 +JoinVerticesProcess::JoinVerticesProcess()
    1.61 +{
    1.62 +	// nothing to do here
    1.63 +}
    1.64 +
    1.65 +// ------------------------------------------------------------------------------------------------
    1.66 +// Destructor, private as well
    1.67 +JoinVerticesProcess::~JoinVerticesProcess()
    1.68 +{
    1.69 +	// nothing to do here
    1.70 +}
    1.71 +
    1.72 +// ------------------------------------------------------------------------------------------------
    1.73 +// Returns whether the processing step is present in the given flag field.
    1.74 +bool JoinVerticesProcess::IsActive( unsigned int pFlags) const
    1.75 +{
    1.76 +	return (pFlags & aiProcess_JoinIdenticalVertices) != 0;
    1.77 +}
    1.78 +// ------------------------------------------------------------------------------------------------
    1.79 +// Executes the post processing step on the given imported data.
    1.80 +void JoinVerticesProcess::Execute( aiScene* pScene)
    1.81 +{
    1.82 +	DefaultLogger::get()->debug("JoinVerticesProcess begin");
    1.83 +
    1.84 +	// get the total number of vertices BEFORE the step is executed
    1.85 +	int iNumOldVertices = 0;
    1.86 +	if (!DefaultLogger::isNullLogger()) {
    1.87 +		for( unsigned int a = 0; a < pScene->mNumMeshes; a++)	{
    1.88 +			iNumOldVertices +=	pScene->mMeshes[a]->mNumVertices;
    1.89 +		}
    1.90 +	}
    1.91 +
    1.92 +	// execute the step
    1.93 +	int iNumVertices = 0;
    1.94 +	for( unsigned int a = 0; a < pScene->mNumMeshes; a++)
    1.95 +		iNumVertices +=	ProcessMesh( pScene->mMeshes[a],a);
    1.96 +
    1.97 +	// if logging is active, print detailed statistics
    1.98 +	if (!DefaultLogger::isNullLogger())
    1.99 +	{
   1.100 +		if (iNumOldVertices == iNumVertices)
   1.101 +		{
   1.102 +			DefaultLogger::get()->debug("JoinVerticesProcess finished ");
   1.103 +		} else
   1.104 +		{
   1.105 +			char szBuff[128]; // should be sufficiently large in every case
   1.106 +			sprintf(szBuff,"JoinVerticesProcess finished | Verts in: %i out: %i | ~%.1f%%",
   1.107 +				iNumOldVertices,
   1.108 +				iNumVertices,
   1.109 +				((iNumOldVertices - iNumVertices) / (float)iNumOldVertices) * 100.f);
   1.110 +			DefaultLogger::get()->info(szBuff);
   1.111 +		}
   1.112 +	}
   1.113 +
   1.114 +	pScene->mFlags |= AI_SCENE_FLAGS_NON_VERBOSE_FORMAT;
   1.115 +}
   1.116 +
   1.117 +// ------------------------------------------------------------------------------------------------
   1.118 +// Unites identical vertices in the given mesh
   1.119 +int JoinVerticesProcess::ProcessMesh( aiMesh* pMesh, unsigned int meshIndex)
   1.120 +{
   1.121 +	BOOST_STATIC_ASSERT( AI_MAX_NUMBER_OF_COLOR_SETS    == 8);
   1.122 +	BOOST_STATIC_ASSERT( AI_MAX_NUMBER_OF_TEXTURECOORDS == 8);
   1.123 +
   1.124 +	// Return early if we don't have any positions
   1.125 +	if (!pMesh->HasPositions() || !pMesh->HasFaces()) {
   1.126 +		return 0;
   1.127 +	}
   1.128 +
   1.129 +	// We'll never have more vertices afterwards.
   1.130 +	std::vector<Vertex> uniqueVertices;
   1.131 +	uniqueVertices.reserve( pMesh->mNumVertices);
   1.132 +
   1.133 +	// For each vertex the index of the vertex it was replaced by.
   1.134 +	// Since the maximal number of vertices is 2^31-1, the most significand bit can be used to mark
   1.135 +	//	whether a new vertex was created for the index (true) or if it was replaced by an existing
   1.136 +	//	unique vertex (false). This saves an additional std::vector<bool> and greatly enhances
   1.137 +	//	branching performance.
   1.138 +	BOOST_STATIC_ASSERT(AI_MAX_VERTICES == 0x7fffffff);
   1.139 +	std::vector<unsigned int> replaceIndex( pMesh->mNumVertices, 0xffffffff);
   1.140 +
   1.141 +	// A little helper to find locally close vertices faster.
   1.142 +	// Try to reuse the lookup table from the last step.
   1.143 +	const static float epsilon = 1e-5f;
   1.144 +	// float posEpsilonSqr;
   1.145 +	SpatialSort* vertexFinder = NULL;
   1.146 +	SpatialSort _vertexFinder;
   1.147 +
   1.148 +	typedef std::pair<SpatialSort,float> SpatPair;
   1.149 +	if (shared)	{
   1.150 +		std::vector<SpatPair >* avf;
   1.151 +		shared->GetProperty(AI_SPP_SPATIAL_SORT,avf);
   1.152 +		if (avf)	{
   1.153 +			SpatPair& blubb = (*avf)[meshIndex];
   1.154 +			vertexFinder  = &blubb.first;
   1.155 +			// posEpsilonSqr = blubb.second;
   1.156 +		}
   1.157 +	}
   1.158 +	if (!vertexFinder)	{
   1.159 +		// bad, need to compute it.
   1.160 +		_vertexFinder.Fill(pMesh->mVertices, pMesh->mNumVertices, sizeof( aiVector3D));
   1.161 +		vertexFinder = &_vertexFinder; 
   1.162 +		// posEpsilonSqr = ComputePositionEpsilon(pMesh);
   1.163 +	}
   1.164 +
   1.165 +	// Squared because we check against squared length of the vector difference
   1.166 +	static const float squareEpsilon = epsilon * epsilon;
   1.167 +
   1.168 +	// Again, better waste some bytes than a realloc ...
   1.169 +	std::vector<unsigned int> verticesFound;
   1.170 +	verticesFound.reserve(10);
   1.171 +
   1.172 +	// Run an optimized code path if we don't have multiple UVs or vertex colors.
   1.173 +	// This should yield false in more than 99% of all imports ...
   1.174 +	const bool complex = ( pMesh->GetNumColorChannels() > 0 || pMesh->GetNumUVChannels() > 1);
   1.175 +
   1.176 +	// Now check each vertex if it brings something new to the table
   1.177 +	for( unsigned int a = 0; a < pMesh->mNumVertices; a++)	{
   1.178 +		// collect the vertex data
   1.179 +		Vertex v(pMesh,a);
   1.180 +
   1.181 +		// collect all vertices that are close enough to the given position
   1.182 +		vertexFinder->FindIdenticalPositions( v.position, verticesFound);
   1.183 +		unsigned int matchIndex = 0xffffffff;
   1.184 +
   1.185 +		// check all unique vertices close to the position if this vertex is already present among them
   1.186 +		for( unsigned int b = 0; b < verticesFound.size(); b++)	{
   1.187 +
   1.188 +			const unsigned int vidx = verticesFound[b];
   1.189 +			const unsigned int uidx = replaceIndex[ vidx];
   1.190 +			if( uidx & 0x80000000)
   1.191 +				continue;
   1.192 +
   1.193 +			const Vertex& uv = uniqueVertices[ uidx];
   1.194 +			// Position mismatch is impossible - the vertex finder already discarded all non-matching positions
   1.195 +
   1.196 +			// We just test the other attributes even if they're not present in the mesh.
   1.197 +			// In this case they're initialized to 0 so the comparision succeeds. 
   1.198 +			// By this method the non-present attributes are effectively ignored in the comparision.
   1.199 +			if( (uv.normal - v.normal).SquareLength() > squareEpsilon)
   1.200 +				continue;
   1.201 +			if( (uv.texcoords[0] - v.texcoords[0]).SquareLength() > squareEpsilon)
   1.202 +				continue;
   1.203 +			if( (uv.tangent - v.tangent).SquareLength() > squareEpsilon)
   1.204 +				continue;
   1.205 +			if( (uv.bitangent - v.bitangent).SquareLength() > squareEpsilon)
   1.206 +				continue;
   1.207 +
   1.208 +			// Usually we won't have vertex colors or multiple UVs, so we can skip from here
   1.209 +			// Actually this increases runtime performance slightly, at least if branch
   1.210 +			// prediction is on our side.
   1.211 +			if (complex){
   1.212 +				// manually unrolled because continue wouldn't work as desired in an inner loop, 
   1.213 +				// also because some compilers seem to fail the task. Colors and UV coords
   1.214 +				// are interleaved since the higher entries are most likely to be
   1.215 +				// zero and thus useless. By interleaving the arrays, vertices are,
   1.216 +				// on average, rejected earlier.
   1.217 +
   1.218 +				if( (uv.texcoords[1] - v.texcoords[1]).SquareLength() > squareEpsilon)
   1.219 +					continue;
   1.220 +				if( GetColorDifference( uv.colors[0], v.colors[0]) > squareEpsilon)
   1.221 +					continue;
   1.222 +
   1.223 +				if( (uv.texcoords[2] - v.texcoords[2]).SquareLength() > squareEpsilon)
   1.224 +					continue;
   1.225 +				if( GetColorDifference( uv.colors[1], v.colors[1]) > squareEpsilon)
   1.226 +					continue;
   1.227 +
   1.228 +				if( (uv.texcoords[3] - v.texcoords[3]).SquareLength() > squareEpsilon)
   1.229 +					continue;
   1.230 +				if( GetColorDifference( uv.colors[2], v.colors[2]) > squareEpsilon)
   1.231 +					continue;
   1.232 +
   1.233 +				if( (uv.texcoords[4] - v.texcoords[4]).SquareLength() > squareEpsilon)
   1.234 +					continue;
   1.235 +				if( GetColorDifference( uv.colors[3], v.colors[3]) > squareEpsilon)
   1.236 +					continue;
   1.237 +
   1.238 +				if( (uv.texcoords[5] - v.texcoords[5]).SquareLength() > squareEpsilon)
   1.239 +					continue;
   1.240 +				if( GetColorDifference( uv.colors[4], v.colors[4]) > squareEpsilon)
   1.241 +					continue;
   1.242 +
   1.243 +				if( (uv.texcoords[6] - v.texcoords[6]).SquareLength() > squareEpsilon)
   1.244 +					continue;
   1.245 +				if( GetColorDifference( uv.colors[5], v.colors[5]) > squareEpsilon)
   1.246 +					continue;
   1.247 +
   1.248 +				if( (uv.texcoords[7] - v.texcoords[7]).SquareLength() > squareEpsilon)
   1.249 +					continue;
   1.250 +				if( GetColorDifference( uv.colors[6], v.colors[6]) > squareEpsilon)
   1.251 +					continue;
   1.252 +				
   1.253 +				if( GetColorDifference( uv.colors[7], v.colors[7]) > squareEpsilon)
   1.254 +					continue;
   1.255 +			}
   1.256 +
   1.257 +			// we're still here -> this vertex perfectly matches our given vertex
   1.258 +			matchIndex = uidx;
   1.259 +			break;
   1.260 +		}
   1.261 +
   1.262 +		// found a replacement vertex among the uniques?
   1.263 +		if( matchIndex != 0xffffffff)
   1.264 +		{
   1.265 +			// store where to found the matching unique vertex
   1.266 +			replaceIndex[a] = matchIndex | 0x80000000;
   1.267 +		}
   1.268 +		else
   1.269 +		{
   1.270 +			// no unique vertex matches it upto now -> so add it
   1.271 +			replaceIndex[a] = (unsigned int)uniqueVertices.size();
   1.272 +			uniqueVertices.push_back( v);
   1.273 +		}
   1.274 +	}
   1.275 +
   1.276 +	if (!DefaultLogger::isNullLogger() && DefaultLogger::get()->getLogSeverity() == Logger::VERBOSE)	{
   1.277 +		DefaultLogger::get()->debug((Formatter::format(),
   1.278 +			"Mesh ",meshIndex,
   1.279 +			" (",
   1.280 +			(pMesh->mName.length ? pMesh->mName.data : "unnamed"),
   1.281 +			") | Verts in: ",pMesh->mNumVertices,
   1.282 +			" out: ",
   1.283 +			uniqueVertices.size(),
   1.284 +			" | ~",
   1.285 +			((pMesh->mNumVertices - uniqueVertices.size()) / (float)pMesh->mNumVertices) * 100.f,
   1.286 +			"%"
   1.287 +		));
   1.288 +	}
   1.289 +
   1.290 +	// replace vertex data with the unique data sets
   1.291 +	pMesh->mNumVertices = (unsigned int)uniqueVertices.size();
   1.292 +
   1.293 +	// ----------------------------------------------------------------------------
   1.294 +	// NOTE - we're *not* calling Vertex::SortBack() because it would check for 
   1.295 +	// presence of every single vertex component once PER VERTEX. And our CPU 
   1.296 +	// dislikes branches, even if they're easily predictable.
   1.297 +	// ----------------------------------------------------------------------------
   1.298 +
   1.299 +	// Position
   1.300 +	delete [] pMesh->mVertices;
   1.301 +	pMesh->mVertices = new aiVector3D[pMesh->mNumVertices];
   1.302 +	for( unsigned int a = 0; a < pMesh->mNumVertices; a++)
   1.303 +		pMesh->mVertices[a] = uniqueVertices[a].position;
   1.304 +
   1.305 +	// Normals, if present
   1.306 +	if( pMesh->mNormals)
   1.307 +	{
   1.308 +		delete [] pMesh->mNormals;
   1.309 +		pMesh->mNormals = new aiVector3D[pMesh->mNumVertices];
   1.310 +		for( unsigned int a = 0; a < pMesh->mNumVertices; a++) {
   1.311 +			pMesh->mNormals[a] = uniqueVertices[a].normal;
   1.312 +		}
   1.313 +	}
   1.314 +	// Tangents, if present
   1.315 +	if( pMesh->mTangents)
   1.316 +	{
   1.317 +		delete [] pMesh->mTangents;
   1.318 +		pMesh->mTangents = new aiVector3D[pMesh->mNumVertices];
   1.319 +		for( unsigned int a = 0; a < pMesh->mNumVertices; a++) {
   1.320 +			pMesh->mTangents[a] = uniqueVertices[a].tangent;
   1.321 +		}
   1.322 +	}
   1.323 +	// Bitangents as well
   1.324 +	if( pMesh->mBitangents)
   1.325 +	{
   1.326 +		delete [] pMesh->mBitangents;
   1.327 +		pMesh->mBitangents = new aiVector3D[pMesh->mNumVertices];
   1.328 +		for( unsigned int a = 0; a < pMesh->mNumVertices; a++) {
   1.329 +			pMesh->mBitangents[a] = uniqueVertices[a].bitangent;
   1.330 +		}
   1.331 +	}
   1.332 +	// Vertex colors
   1.333 +	for( unsigned int a = 0; pMesh->HasVertexColors(a); a++)
   1.334 +	{
   1.335 +		delete [] pMesh->mColors[a];
   1.336 +		pMesh->mColors[a] = new aiColor4D[pMesh->mNumVertices];
   1.337 +		for( unsigned int b = 0; b < pMesh->mNumVertices; b++) {
   1.338 +			pMesh->mColors[a][b] = uniqueVertices[b].colors[a];
   1.339 +		}
   1.340 +	}
   1.341 +	// Texture coords
   1.342 +	for( unsigned int a = 0; pMesh->HasTextureCoords(a); a++)
   1.343 +	{
   1.344 +		delete [] pMesh->mTextureCoords[a];
   1.345 +		pMesh->mTextureCoords[a] = new aiVector3D[pMesh->mNumVertices];
   1.346 +		for( unsigned int b = 0; b < pMesh->mNumVertices; b++) {
   1.347 +			pMesh->mTextureCoords[a][b] = uniqueVertices[b].texcoords[a];
   1.348 +		}
   1.349 +	}
   1.350 +
   1.351 +	// adjust the indices in all faces
   1.352 +	for( unsigned int a = 0; a < pMesh->mNumFaces; a++)
   1.353 +	{
   1.354 +		aiFace& face = pMesh->mFaces[a];
   1.355 +		for( unsigned int b = 0; b < face.mNumIndices; b++)	{
   1.356 +			face.mIndices[b] = replaceIndex[face.mIndices[b]] & ~0x80000000;
   1.357 +		}
   1.358 +	}
   1.359 +
   1.360 +	// adjust bone vertex weights.
   1.361 +	for( int a = 0; a < (int)pMesh->mNumBones; a++)
   1.362 +	{
   1.363 +		aiBone* bone = pMesh->mBones[a];
   1.364 +		std::vector<aiVertexWeight> newWeights;
   1.365 +		newWeights.reserve( bone->mNumWeights);
   1.366 +
   1.367 +		for( unsigned int b = 0; b < bone->mNumWeights; b++)
   1.368 +		{
   1.369 +			const aiVertexWeight& ow = bone->mWeights[b];
   1.370 +			// if the vertex is a unique one, translate it
   1.371 +			if( !(replaceIndex[ow.mVertexId] & 0x80000000))
   1.372 +			{
   1.373 +				aiVertexWeight nw;
   1.374 +				nw.mVertexId = replaceIndex[ow.mVertexId];
   1.375 +				nw.mWeight = ow.mWeight;
   1.376 +				newWeights.push_back( nw);
   1.377 +			}
   1.378 +		}
   1.379 +
   1.380 +		if (newWeights.size() > 0) {
   1.381 +			// kill the old and replace them with the translated weights
   1.382 +			delete [] bone->mWeights;
   1.383 +			bone->mNumWeights = (unsigned int)newWeights.size();
   1.384 +
   1.385 +			bone->mWeights = new aiVertexWeight[bone->mNumWeights];
   1.386 +			memcpy( bone->mWeights, &newWeights[0], bone->mNumWeights * sizeof( aiVertexWeight));
   1.387 +		}
   1.388 +		else {
   1.389 +		
   1.390 +			/*  NOTE:
   1.391 +			 *
   1.392 +			 *  In the algorithm above we're assuming that there are no vertices
   1.393 +			 *  with a different bone weight setup at the same position. That wouldn't
   1.394 +			 *  make sense, but it is not absolutely impossible. SkeletonMeshBuilder
   1.395 +			 *  for example generates such input data if two skeleton points
   1.396 +			 *  share the same position. Again this doesn't make sense but is
   1.397 +			 *  reality for some model formats (MD5 for example uses these special
   1.398 +			 *  nodes as attachment tags for its weapons). 
   1.399 +			 *
   1.400 +			 *  Then it is possible that a bone has no weights anymore .... as a quick
   1.401 +			 *  workaround, we're just removing these bones. If they're animated,
   1.402 +			 *  model geometry might be modified but at least there's no risk of a crash.
   1.403 +			 */
   1.404 +			delete bone;
   1.405 +			--pMesh->mNumBones;
   1.406 +			for (unsigned int n = a; n < pMesh->mNumBones; ++n)  {
   1.407 +				pMesh->mBones[n] = pMesh->mBones[n+1];
   1.408 +			}
   1.409 +
   1.410 +			--a; 
   1.411 +			DefaultLogger::get()->warn("Removing bone -> no weights remaining");
   1.412 +		}
   1.413 +	}
   1.414 +	return pMesh->mNumVertices;
   1.415 +}
   1.416 +
   1.417 +#endif // !! ASSIMP_BUILD_NO_JOINVERTICES_PROCESS