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 Implementation of the post processing step to join identical vertices
nuclear@0:  * for all imported meshes
nuclear@0:  */
nuclear@0: 
nuclear@0: #include "AssimpPCH.h"
nuclear@0: #ifndef ASSIMP_BUILD_NO_JOINVERTICES_PROCESS
nuclear@0: 
nuclear@0: #include "JoinVerticesProcess.h"
nuclear@0: #include "ProcessHelper.h"
nuclear@0: #include "Vertex.h"
nuclear@0: #include "TinyFormatter.h"
nuclear@0: 
nuclear@0: using namespace Assimp;
nuclear@0: // ------------------------------------------------------------------------------------------------
nuclear@0: // Constructor to be privately used by Importer
nuclear@0: JoinVerticesProcess::JoinVerticesProcess()
nuclear@0: {
nuclear@0: 	// nothing to do here
nuclear@0: }
nuclear@0: 
nuclear@0: // ------------------------------------------------------------------------------------------------
nuclear@0: // Destructor, private as well
nuclear@0: JoinVerticesProcess::~JoinVerticesProcess()
nuclear@0: {
nuclear@0: 	// nothing to do here
nuclear@0: }
nuclear@0: 
nuclear@0: // ------------------------------------------------------------------------------------------------
nuclear@0: // Returns whether the processing step is present in the given flag field.
nuclear@0: bool JoinVerticesProcess::IsActive( unsigned int pFlags) const
nuclear@0: {
nuclear@0: 	return (pFlags & aiProcess_JoinIdenticalVertices) != 0;
nuclear@0: }
nuclear@0: // ------------------------------------------------------------------------------------------------
nuclear@0: // Executes the post processing step on the given imported data.
nuclear@0: void JoinVerticesProcess::Execute( aiScene* pScene)
nuclear@0: {
nuclear@0: 	DefaultLogger::get()->debug("JoinVerticesProcess begin");
nuclear@0: 
nuclear@0: 	// get the total number of vertices BEFORE the step is executed
nuclear@0: 	int iNumOldVertices = 0;
nuclear@0: 	if (!DefaultLogger::isNullLogger()) {
nuclear@0: 		for( unsigned int a = 0; a < pScene->mNumMeshes; a++)	{
nuclear@0: 			iNumOldVertices +=	pScene->mMeshes[a]->mNumVertices;
nuclear@0: 		}
nuclear@0: 	}
nuclear@0: 
nuclear@0: 	// execute the step
nuclear@0: 	int iNumVertices = 0;
nuclear@0: 	for( unsigned int a = 0; a < pScene->mNumMeshes; a++)
nuclear@0: 		iNumVertices +=	ProcessMesh( pScene->mMeshes[a],a);
nuclear@0: 
nuclear@0: 	// if logging is active, print detailed statistics
nuclear@0: 	if (!DefaultLogger::isNullLogger())
nuclear@0: 	{
nuclear@0: 		if (iNumOldVertices == iNumVertices)
nuclear@0: 		{
nuclear@0: 			DefaultLogger::get()->debug("JoinVerticesProcess finished ");
nuclear@0: 		} else
nuclear@0: 		{
nuclear@0: 			char szBuff[128]; // should be sufficiently large in every case
nuclear@0: 			sprintf(szBuff,"JoinVerticesProcess finished | Verts in: %i out: %i | ~%.1f%%",
nuclear@0: 				iNumOldVertices,
nuclear@0: 				iNumVertices,
nuclear@0: 				((iNumOldVertices - iNumVertices) / (float)iNumOldVertices) * 100.f);
nuclear@0: 			DefaultLogger::get()->info(szBuff);
nuclear@0: 		}
nuclear@0: 	}
nuclear@0: 
nuclear@0: 	pScene->mFlags |= AI_SCENE_FLAGS_NON_VERBOSE_FORMAT;
nuclear@0: }
nuclear@0: 
nuclear@0: // ------------------------------------------------------------------------------------------------
nuclear@0: // Unites identical vertices in the given mesh
nuclear@0: int JoinVerticesProcess::ProcessMesh( aiMesh* pMesh, unsigned int meshIndex)
nuclear@0: {
nuclear@0: 	BOOST_STATIC_ASSERT( AI_MAX_NUMBER_OF_COLOR_SETS    == 8);
nuclear@0: 	BOOST_STATIC_ASSERT( AI_MAX_NUMBER_OF_TEXTURECOORDS == 8);
nuclear@0: 
nuclear@0: 	// Return early if we don't have any positions
nuclear@0: 	if (!pMesh->HasPositions() || !pMesh->HasFaces()) {
nuclear@0: 		return 0;
nuclear@0: 	}
nuclear@0: 
nuclear@0: 	// We'll never have more vertices afterwards.
nuclear@0: 	std::vector<Vertex> uniqueVertices;
nuclear@0: 	uniqueVertices.reserve( pMesh->mNumVertices);
nuclear@0: 
nuclear@0: 	// For each vertex the index of the vertex it was replaced by.
nuclear@0: 	// Since the maximal number of vertices is 2^31-1, the most significand bit can be used to mark
nuclear@0: 	//	whether a new vertex was created for the index (true) or if it was replaced by an existing
nuclear@0: 	//	unique vertex (false). This saves an additional std::vector<bool> and greatly enhances
nuclear@0: 	//	branching performance.
nuclear@0: 	BOOST_STATIC_ASSERT(AI_MAX_VERTICES == 0x7fffffff);
nuclear@0: 	std::vector<unsigned int> replaceIndex( pMesh->mNumVertices, 0xffffffff);
nuclear@0: 
nuclear@0: 	// A little helper to find locally close vertices faster.
nuclear@0: 	// Try to reuse the lookup table from the last step.
nuclear@0: 	const static float epsilon = 1e-5f;
nuclear@0: 	// float posEpsilonSqr;
nuclear@0: 	SpatialSort* vertexFinder = NULL;
nuclear@0: 	SpatialSort _vertexFinder;
nuclear@0: 
nuclear@0: 	typedef std::pair<SpatialSort,float> SpatPair;
nuclear@0: 	if (shared)	{
nuclear@0: 		std::vector<SpatPair >* avf;
nuclear@0: 		shared->GetProperty(AI_SPP_SPATIAL_SORT,avf);
nuclear@0: 		if (avf)	{
nuclear@0: 			SpatPair& blubb = (*avf)[meshIndex];
nuclear@0: 			vertexFinder  = &blubb.first;
nuclear@0: 			// posEpsilonSqr = blubb.second;
nuclear@0: 		}
nuclear@0: 	}
nuclear@0: 	if (!vertexFinder)	{
nuclear@0: 		// bad, need to compute it.
nuclear@0: 		_vertexFinder.Fill(pMesh->mVertices, pMesh->mNumVertices, sizeof( aiVector3D));
nuclear@0: 		vertexFinder = &_vertexFinder; 
nuclear@0: 		// posEpsilonSqr = ComputePositionEpsilon(pMesh);
nuclear@0: 	}
nuclear@0: 
nuclear@0: 	// Squared because we check against squared length of the vector difference
nuclear@0: 	static const float squareEpsilon = epsilon * epsilon;
nuclear@0: 
nuclear@0: 	// Again, better waste some bytes than a realloc ...
nuclear@0: 	std::vector<unsigned int> verticesFound;
nuclear@0: 	verticesFound.reserve(10);
nuclear@0: 
nuclear@0: 	// Run an optimized code path if we don't have multiple UVs or vertex colors.
nuclear@0: 	// This should yield false in more than 99% of all imports ...
nuclear@0: 	const bool complex = ( pMesh->GetNumColorChannels() > 0 || pMesh->GetNumUVChannels() > 1);
nuclear@0: 
nuclear@0: 	// Now check each vertex if it brings something new to the table
nuclear@0: 	for( unsigned int a = 0; a < pMesh->mNumVertices; a++)	{
nuclear@0: 		// collect the vertex data
nuclear@0: 		Vertex v(pMesh,a);
nuclear@0: 
nuclear@0: 		// collect all vertices that are close enough to the given position
nuclear@0: 		vertexFinder->FindIdenticalPositions( v.position, verticesFound);
nuclear@0: 		unsigned int matchIndex = 0xffffffff;
nuclear@0: 
nuclear@0: 		// check all unique vertices close to the position if this vertex is already present among them
nuclear@0: 		for( unsigned int b = 0; b < verticesFound.size(); b++)	{
nuclear@0: 
nuclear@0: 			const unsigned int vidx = verticesFound[b];
nuclear@0: 			const unsigned int uidx = replaceIndex[ vidx];
nuclear@0: 			if( uidx & 0x80000000)
nuclear@0: 				continue;
nuclear@0: 
nuclear@0: 			const Vertex& uv = uniqueVertices[ uidx];
nuclear@0: 			// Position mismatch is impossible - the vertex finder already discarded all non-matching positions
nuclear@0: 
nuclear@0: 			// We just test the other attributes even if they're not present in the mesh.
nuclear@0: 			// In this case they're initialized to 0 so the comparision succeeds. 
nuclear@0: 			// By this method the non-present attributes are effectively ignored in the comparision.
nuclear@0: 			if( (uv.normal - v.normal).SquareLength() > squareEpsilon)
nuclear@0: 				continue;
nuclear@0: 			if( (uv.texcoords[0] - v.texcoords[0]).SquareLength() > squareEpsilon)
nuclear@0: 				continue;
nuclear@0: 			if( (uv.tangent - v.tangent).SquareLength() > squareEpsilon)
nuclear@0: 				continue;
nuclear@0: 			if( (uv.bitangent - v.bitangent).SquareLength() > squareEpsilon)
nuclear@0: 				continue;
nuclear@0: 
nuclear@0: 			// Usually we won't have vertex colors or multiple UVs, so we can skip from here
nuclear@0: 			// Actually this increases runtime performance slightly, at least if branch
nuclear@0: 			// prediction is on our side.
nuclear@0: 			if (complex){
nuclear@0: 				// manually unrolled because continue wouldn't work as desired in an inner loop, 
nuclear@0: 				// also because some compilers seem to fail the task. Colors and UV coords
nuclear@0: 				// are interleaved since the higher entries are most likely to be
nuclear@0: 				// zero and thus useless. By interleaving the arrays, vertices are,
nuclear@0: 				// on average, rejected earlier.
nuclear@0: 
nuclear@0: 				if( (uv.texcoords[1] - v.texcoords[1]).SquareLength() > squareEpsilon)
nuclear@0: 					continue;
nuclear@0: 				if( GetColorDifference( uv.colors[0], v.colors[0]) > squareEpsilon)
nuclear@0: 					continue;
nuclear@0: 
nuclear@0: 				if( (uv.texcoords[2] - v.texcoords[2]).SquareLength() > squareEpsilon)
nuclear@0: 					continue;
nuclear@0: 				if( GetColorDifference( uv.colors[1], v.colors[1]) > squareEpsilon)
nuclear@0: 					continue;
nuclear@0: 
nuclear@0: 				if( (uv.texcoords[3] - v.texcoords[3]).SquareLength() > squareEpsilon)
nuclear@0: 					continue;
nuclear@0: 				if( GetColorDifference( uv.colors[2], v.colors[2]) > squareEpsilon)
nuclear@0: 					continue;
nuclear@0: 
nuclear@0: 				if( (uv.texcoords[4] - v.texcoords[4]).SquareLength() > squareEpsilon)
nuclear@0: 					continue;
nuclear@0: 				if( GetColorDifference( uv.colors[3], v.colors[3]) > squareEpsilon)
nuclear@0: 					continue;
nuclear@0: 
nuclear@0: 				if( (uv.texcoords[5] - v.texcoords[5]).SquareLength() > squareEpsilon)
nuclear@0: 					continue;
nuclear@0: 				if( GetColorDifference( uv.colors[4], v.colors[4]) > squareEpsilon)
nuclear@0: 					continue;
nuclear@0: 
nuclear@0: 				if( (uv.texcoords[6] - v.texcoords[6]).SquareLength() > squareEpsilon)
nuclear@0: 					continue;
nuclear@0: 				if( GetColorDifference( uv.colors[5], v.colors[5]) > squareEpsilon)
nuclear@0: 					continue;
nuclear@0: 
nuclear@0: 				if( (uv.texcoords[7] - v.texcoords[7]).SquareLength() > squareEpsilon)
nuclear@0: 					continue;
nuclear@0: 				if( GetColorDifference( uv.colors[6], v.colors[6]) > squareEpsilon)
nuclear@0: 					continue;
nuclear@0: 				
nuclear@0: 				if( GetColorDifference( uv.colors[7], v.colors[7]) > squareEpsilon)
nuclear@0: 					continue;
nuclear@0: 			}
nuclear@0: 
nuclear@0: 			// we're still here -> this vertex perfectly matches our given vertex
nuclear@0: 			matchIndex = uidx;
nuclear@0: 			break;
nuclear@0: 		}
nuclear@0: 
nuclear@0: 		// found a replacement vertex among the uniques?
nuclear@0: 		if( matchIndex != 0xffffffff)
nuclear@0: 		{
nuclear@0: 			// store where to found the matching unique vertex
nuclear@0: 			replaceIndex[a] = matchIndex | 0x80000000;
nuclear@0: 		}
nuclear@0: 		else
nuclear@0: 		{
nuclear@0: 			// no unique vertex matches it upto now -> so add it
nuclear@0: 			replaceIndex[a] = (unsigned int)uniqueVertices.size();
nuclear@0: 			uniqueVertices.push_back( v);
nuclear@0: 		}
nuclear@0: 	}
nuclear@0: 
nuclear@0: 	if (!DefaultLogger::isNullLogger() && DefaultLogger::get()->getLogSeverity() == Logger::VERBOSE)	{
nuclear@0: 		DefaultLogger::get()->debug((Formatter::format(),
nuclear@0: 			"Mesh ",meshIndex,
nuclear@0: 			" (",
nuclear@0: 			(pMesh->mName.length ? pMesh->mName.data : "unnamed"),
nuclear@0: 			") | Verts in: ",pMesh->mNumVertices,
nuclear@0: 			" out: ",
nuclear@0: 			uniqueVertices.size(),
nuclear@0: 			" | ~",
nuclear@0: 			((pMesh->mNumVertices - uniqueVertices.size()) / (float)pMesh->mNumVertices) * 100.f,
nuclear@0: 			"%"
nuclear@0: 		));
nuclear@0: 	}
nuclear@0: 
nuclear@0: 	// replace vertex data with the unique data sets
nuclear@0: 	pMesh->mNumVertices = (unsigned int)uniqueVertices.size();
nuclear@0: 
nuclear@0: 	// ----------------------------------------------------------------------------
nuclear@0: 	// NOTE - we're *not* calling Vertex::SortBack() because it would check for 
nuclear@0: 	// presence of every single vertex component once PER VERTEX. And our CPU 
nuclear@0: 	// dislikes branches, even if they're easily predictable.
nuclear@0: 	// ----------------------------------------------------------------------------
nuclear@0: 
nuclear@0: 	// Position
nuclear@0: 	delete [] pMesh->mVertices;
nuclear@0: 	pMesh->mVertices = new aiVector3D[pMesh->mNumVertices];
nuclear@0: 	for( unsigned int a = 0; a < pMesh->mNumVertices; a++)
nuclear@0: 		pMesh->mVertices[a] = uniqueVertices[a].position;
nuclear@0: 
nuclear@0: 	// Normals, if present
nuclear@0: 	if( pMesh->mNormals)
nuclear@0: 	{
nuclear@0: 		delete [] pMesh->mNormals;
nuclear@0: 		pMesh->mNormals = new aiVector3D[pMesh->mNumVertices];
nuclear@0: 		for( unsigned int a = 0; a < pMesh->mNumVertices; a++) {
nuclear@0: 			pMesh->mNormals[a] = uniqueVertices[a].normal;
nuclear@0: 		}
nuclear@0: 	}
nuclear@0: 	// Tangents, if present
nuclear@0: 	if( pMesh->mTangents)
nuclear@0: 	{
nuclear@0: 		delete [] pMesh->mTangents;
nuclear@0: 		pMesh->mTangents = new aiVector3D[pMesh->mNumVertices];
nuclear@0: 		for( unsigned int a = 0; a < pMesh->mNumVertices; a++) {
nuclear@0: 			pMesh->mTangents[a] = uniqueVertices[a].tangent;
nuclear@0: 		}
nuclear@0: 	}
nuclear@0: 	// Bitangents as well
nuclear@0: 	if( pMesh->mBitangents)
nuclear@0: 	{
nuclear@0: 		delete [] pMesh->mBitangents;
nuclear@0: 		pMesh->mBitangents = new aiVector3D[pMesh->mNumVertices];
nuclear@0: 		for( unsigned int a = 0; a < pMesh->mNumVertices; a++) {
nuclear@0: 			pMesh->mBitangents[a] = uniqueVertices[a].bitangent;
nuclear@0: 		}
nuclear@0: 	}
nuclear@0: 	// Vertex colors
nuclear@0: 	for( unsigned int a = 0; pMesh->HasVertexColors(a); a++)
nuclear@0: 	{
nuclear@0: 		delete [] pMesh->mColors[a];
nuclear@0: 		pMesh->mColors[a] = new aiColor4D[pMesh->mNumVertices];
nuclear@0: 		for( unsigned int b = 0; b < pMesh->mNumVertices; b++) {
nuclear@0: 			pMesh->mColors[a][b] = uniqueVertices[b].colors[a];
nuclear@0: 		}
nuclear@0: 	}
nuclear@0: 	// Texture coords
nuclear@0: 	for( unsigned int a = 0; pMesh->HasTextureCoords(a); a++)
nuclear@0: 	{
nuclear@0: 		delete [] pMesh->mTextureCoords[a];
nuclear@0: 		pMesh->mTextureCoords[a] = new aiVector3D[pMesh->mNumVertices];
nuclear@0: 		for( unsigned int b = 0; b < pMesh->mNumVertices; b++) {
nuclear@0: 			pMesh->mTextureCoords[a][b] = uniqueVertices[b].texcoords[a];
nuclear@0: 		}
nuclear@0: 	}
nuclear@0: 
nuclear@0: 	// adjust the indices in all faces
nuclear@0: 	for( unsigned int a = 0; a < pMesh->mNumFaces; a++)
nuclear@0: 	{
nuclear@0: 		aiFace& face = pMesh->mFaces[a];
nuclear@0: 		for( unsigned int b = 0; b < face.mNumIndices; b++)	{
nuclear@0: 			face.mIndices[b] = replaceIndex[face.mIndices[b]] & ~0x80000000;
nuclear@0: 		}
nuclear@0: 	}
nuclear@0: 
nuclear@0: 	// adjust bone vertex weights.
nuclear@0: 	for( int a = 0; a < (int)pMesh->mNumBones; a++)
nuclear@0: 	{
nuclear@0: 		aiBone* bone = pMesh->mBones[a];
nuclear@0: 		std::vector<aiVertexWeight> newWeights;
nuclear@0: 		newWeights.reserve( bone->mNumWeights);
nuclear@0: 
nuclear@0: 		for( unsigned int b = 0; b < bone->mNumWeights; b++)
nuclear@0: 		{
nuclear@0: 			const aiVertexWeight& ow = bone->mWeights[b];
nuclear@0: 			// if the vertex is a unique one, translate it
nuclear@0: 			if( !(replaceIndex[ow.mVertexId] & 0x80000000))
nuclear@0: 			{
nuclear@0: 				aiVertexWeight nw;
nuclear@0: 				nw.mVertexId = replaceIndex[ow.mVertexId];
nuclear@0: 				nw.mWeight = ow.mWeight;
nuclear@0: 				newWeights.push_back( nw);
nuclear@0: 			}
nuclear@0: 		}
nuclear@0: 
nuclear@0: 		if (newWeights.size() > 0) {
nuclear@0: 			// kill the old and replace them with the translated weights
nuclear@0: 			delete [] bone->mWeights;
nuclear@0: 			bone->mNumWeights = (unsigned int)newWeights.size();
nuclear@0: 
nuclear@0: 			bone->mWeights = new aiVertexWeight[bone->mNumWeights];
nuclear@0: 			memcpy( bone->mWeights, &newWeights[0], bone->mNumWeights * sizeof( aiVertexWeight));
nuclear@0: 		}
nuclear@0: 		else {
nuclear@0: 		
nuclear@0: 			/*  NOTE:
nuclear@0: 			 *
nuclear@0: 			 *  In the algorithm above we're assuming that there are no vertices
nuclear@0: 			 *  with a different bone weight setup at the same position. That wouldn't
nuclear@0: 			 *  make sense, but it is not absolutely impossible. SkeletonMeshBuilder
nuclear@0: 			 *  for example generates such input data if two skeleton points
nuclear@0: 			 *  share the same position. Again this doesn't make sense but is
nuclear@0: 			 *  reality for some model formats (MD5 for example uses these special
nuclear@0: 			 *  nodes as attachment tags for its weapons). 
nuclear@0: 			 *
nuclear@0: 			 *  Then it is possible that a bone has no weights anymore .... as a quick
nuclear@0: 			 *  workaround, we're just removing these bones. If they're animated,
nuclear@0: 			 *  model geometry might be modified but at least there's no risk of a crash.
nuclear@0: 			 */
nuclear@0: 			delete bone;
nuclear@0: 			--pMesh->mNumBones;
nuclear@0: 			for (unsigned int n = a; n < pMesh->mNumBones; ++n)  {
nuclear@0: 				pMesh->mBones[n] = pMesh->mBones[n+1];
nuclear@0: 			}
nuclear@0: 
nuclear@0: 			--a; 
nuclear@0: 			DefaultLogger::get()->warn("Removing bone -> no weights remaining");
nuclear@0: 		}
nuclear@0: 	}
nuclear@0: 	return pMesh->mNumVertices;
nuclear@0: }
nuclear@0: 
nuclear@0: #endif // !! ASSIMP_BUILD_NO_JOINVERTICES_PROCESS