diff options
Diffstat (limited to 'src/3rdparty/assimp/code/ImproveCacheLocality.cpp')
| -rw-r--r-- | src/3rdparty/assimp/code/ImproveCacheLocality.cpp | 388 |
1 files changed, 0 insertions, 388 deletions
diff --git a/src/3rdparty/assimp/code/ImproveCacheLocality.cpp b/src/3rdparty/assimp/code/ImproveCacheLocality.cpp deleted file mode 100644 index 2ac32aa84..000000000 --- a/src/3rdparty/assimp/code/ImproveCacheLocality.cpp +++ /dev/null @@ -1,388 +0,0 @@ -/* ---------------------------------------------------------------------------- -Open Asset Import Library (assimp) ---------------------------------------------------------------------------- - -Copyright (c) 2006-2017, assimp team - - -All rights reserved. - -Redistribution and use of this software in source and binary forms, -with or without modification, are permitted provided that the following -conditions are met: - -* Redistributions of source code must retain the above - copyright notice, this list of conditions and the - following disclaimer. - -* Redistributions in binary form must reproduce the above - copyright notice, this list of conditions and the - following disclaimer in the documentation and/or other - materials provided with the distribution. - -* Neither the name of the assimp team, nor the names of its - contributors may be used to endorse or promote products - derived from this software without specific prior - written permission of the assimp team. - -THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS -"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT -LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR -A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT -OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, -SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT -LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, -DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY -THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT -(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE -OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. ---------------------------------------------------------------------------- -*/ - -/** @file Implementation of the post processing step to improve the cache locality of a mesh. - * <br> - * The algorithm is roughly basing on this paper: - * http://www.cs.princeton.edu/gfx/pubs/Sander_2007_%3ETR/tipsy.pdf - * .. although overdraw rduction isn't implemented yet ... - */ - - - -// internal headers -#include "ImproveCacheLocality.h" -#include "VertexTriangleAdjacency.h" -#include "StringUtils.h" -#include <assimp/postprocess.h> -#include <assimp/scene.h> -#include <assimp/DefaultLogger.hpp> -#include <stdio.h> -#include <stack> - -using namespace Assimp; - -// ------------------------------------------------------------------------------------------------ -// Constructor to be privately used by Importer -ImproveCacheLocalityProcess::ImproveCacheLocalityProcess() { - configCacheDepth = PP_ICL_PTCACHE_SIZE; -} - -// ------------------------------------------------------------------------------------------------ -// Destructor, private as well -ImproveCacheLocalityProcess::~ImproveCacheLocalityProcess() -{ - // nothing to do here -} - -// ------------------------------------------------------------------------------------------------ -// Returns whether the processing step is present in the given flag field. -bool ImproveCacheLocalityProcess::IsActive( unsigned int pFlags) const -{ - return (pFlags & aiProcess_ImproveCacheLocality) != 0; -} - -// ------------------------------------------------------------------------------------------------ -// Setup configuration -void ImproveCacheLocalityProcess::SetupProperties(const Importer* pImp) -{ - // AI_CONFIG_PP_ICL_PTCACHE_SIZE controls the target cache size for the optimizer - configCacheDepth = pImp->GetPropertyInteger(AI_CONFIG_PP_ICL_PTCACHE_SIZE,PP_ICL_PTCACHE_SIZE); -} - -// ------------------------------------------------------------------------------------------------ -// Executes the post processing step on the given imported data. -void ImproveCacheLocalityProcess::Execute( aiScene* pScene) -{ - if (!pScene->mNumMeshes) { - DefaultLogger::get()->debug("ImproveCacheLocalityProcess skipped; there are no meshes"); - return; - } - - DefaultLogger::get()->debug("ImproveCacheLocalityProcess begin"); - - float out = 0.f; - unsigned int numf = 0, numm = 0; - for( unsigned int a = 0; a < pScene->mNumMeshes; a++){ - const float res = ProcessMesh( pScene->mMeshes[a],a); - if (res) { - numf += pScene->mMeshes[a]->mNumFaces; - out += res; - ++numm; - } - } - if (!DefaultLogger::isNullLogger()) { - char szBuff[128]; // should be sufficiently large in every case - ai_snprintf(szBuff,128,"Cache relevant are %u meshes (%u faces). Average output ACMR is %f", - numm,numf,out/numf); - - DefaultLogger::get()->info(szBuff); - DefaultLogger::get()->debug("ImproveCacheLocalityProcess finished. "); - } -} - -// ------------------------------------------------------------------------------------------------ -// Improves the cache coherency of a specific mesh -float ImproveCacheLocalityProcess::ProcessMesh( aiMesh* pMesh, unsigned int meshNum) -{ - // TODO: rewrite this to use std::vector or boost::shared_array - ai_assert(NULL != pMesh); - - // Check whether the input data is valid - // - there must be vertices and faces - // - all faces must be triangulated or we can't operate on them - if (!pMesh->HasFaces() || !pMesh->HasPositions()) - return 0.f; - - if (pMesh->mPrimitiveTypes != aiPrimitiveType_TRIANGLE) { - DefaultLogger::get()->error("This algorithm works on triangle meshes only"); - return 0.f; - } - - if(pMesh->mNumVertices <= configCacheDepth) { - return 0.f; - } - - float fACMR = 3.f; - const aiFace* const pcEnd = pMesh->mFaces+pMesh->mNumFaces; - - // Input ACMR is for logging purposes only - if (!DefaultLogger::isNullLogger()) { - - unsigned int* piFIFOStack = new unsigned int[configCacheDepth]; - memset(piFIFOStack,0xff,configCacheDepth*sizeof(unsigned int)); - unsigned int* piCur = piFIFOStack; - const unsigned int* const piCurEnd = piFIFOStack + configCacheDepth; - - // count the number of cache misses - unsigned int iCacheMisses = 0; - for (const aiFace* pcFace = pMesh->mFaces;pcFace != pcEnd;++pcFace) { - - for (unsigned int qq = 0; qq < 3;++qq) { - bool bInCache = false; - - for (unsigned int* pp = piFIFOStack;pp < piCurEnd;++pp) { - if (*pp == pcFace->mIndices[qq]) { - // the vertex is in cache - bInCache = true; - break; - } - } - if (!bInCache) { - ++iCacheMisses; - if (piCurEnd == piCur) { - piCur = piFIFOStack; - } - *piCur++ = pcFace->mIndices[qq]; - } - } - } - delete[] piFIFOStack; - fACMR = (float)iCacheMisses / pMesh->mNumFaces; - if (3.0 == fACMR) { - char szBuff[128]; // should be sufficiently large in every case - - // the JoinIdenticalVertices process has not been executed on this - // mesh, otherwise this value would normally be at least minimally - // smaller than 3.0 ... - ai_snprintf(szBuff,128,"Mesh %u: Not suitable for vcache optimization",meshNum); - DefaultLogger::get()->warn(szBuff); - return 0.f; - } - } - - // first we need to build a vertex-triangle adjacency list - VertexTriangleAdjacency adj(pMesh->mFaces,pMesh->mNumFaces, pMesh->mNumVertices,true); - - // build a list to store per-vertex caching time stamps - unsigned int* const piCachingStamps = new unsigned int[pMesh->mNumVertices]; - memset(piCachingStamps,0x0,pMesh->mNumVertices*sizeof(unsigned int)); - - // allocate an empty output index buffer. We store the output indices in one large array. - // Since the number of triangles won't change the input faces can be reused. This is how - // we save thousands of redundant mini allocations for aiFace::mIndices - const unsigned int iIdxCnt = pMesh->mNumFaces*3; - unsigned int* const piIBOutput = new unsigned int[iIdxCnt]; - unsigned int* piCSIter = piIBOutput; - - // allocate the flag array to hold the information - // whether a face has already been emitted or not - std::vector<bool> abEmitted(pMesh->mNumFaces,false); - - // dead-end vertex index stack - std::stack<unsigned int, std::vector<unsigned int> > sDeadEndVStack; - - // create a copy of the piNumTriPtr buffer - unsigned int* const piNumTriPtr = adj.mLiveTriangles; - const std::vector<unsigned int> piNumTriPtrNoModify(piNumTriPtr, piNumTriPtr + pMesh->mNumVertices); - - // get the largest number of referenced triangles and allocate the "candidate buffer" - unsigned int iMaxRefTris = 0; { - const unsigned int* piCur = adj.mLiveTriangles; - const unsigned int* const piCurEnd = adj.mLiveTriangles+pMesh->mNumVertices; - for (;piCur != piCurEnd;++piCur) { - iMaxRefTris = std::max(iMaxRefTris,*piCur); - } - } - ai_assert(iMaxRefTris > 0); - unsigned int* piCandidates = new unsigned int[iMaxRefTris*3]; - unsigned int iCacheMisses = 0; - - // ................................................................................... - /** PSEUDOCODE for the algorithm - - A = Build-Adjacency(I) Vertex-triangle adjacency - L = Get-Triangle-Counts(A) Per-vertex live triangle counts - C = Zero(Vertex-Count(I)) Per-vertex caching time stamps - D = Empty-Stack() Dead-end vertex stack - E = False(Triangle-Count(I)) Per triangle emitted flag - O = Empty-Index-Buffer() Empty output buffer - f = 0 Arbitrary starting vertex - s = k+1, i = 1 Time stamp and cursor - while f >= 0 For all valid fanning vertices - N = Empty-Set() 1-ring of next candidates - for each Triangle t in Neighbors(A, f) - if !Emitted(E,t) - for each Vertex v in t - Append(O,v) Output vertex - Push(D,v) Add to dead-end stack - Insert(N,v) Register as candidate - L[v] = L[v]-1 Decrease live triangle count - if s-C[v] > k If not in cache - C[v] = s Set time stamp - s = s+1 Increment time stamp - E[t] = true Flag triangle as emitted - Select next fanning vertex - f = Get-Next-Vertex(I,i,k,N,C,s,L,D) - return O - */ - // ................................................................................... - - int ivdx = 0; - int ics = 1; - int iStampCnt = configCacheDepth+1; - while (ivdx >= 0) { - - unsigned int icnt = piNumTriPtrNoModify[ivdx]; - unsigned int* piList = adj.GetAdjacentTriangles(ivdx); - unsigned int* piCurCandidate = piCandidates; - - // get all triangles in the neighborhood - for (unsigned int tri = 0; tri < icnt;++tri) { - - // if they have not yet been emitted, add them to the output IB - const unsigned int fidx = *piList++; - if (!abEmitted[fidx]) { - - // so iterate through all vertices of the current triangle - const aiFace* pcFace = &pMesh->mFaces[ fidx ]; - for (unsigned int* p = pcFace->mIndices, *p2 = pcFace->mIndices+3;p != p2;++p) { - const unsigned int dp = *p; - - // the current vertex won't have any free triangles after this step - if (ivdx != (int)dp) { - // append the vertex to the dead-end stack - sDeadEndVStack.push(dp); - - // register as candidate for the next step - *piCurCandidate++ = dp; - - // decrease the per-vertex triangle counts - piNumTriPtr[dp]--; - } - - // append the vertex to the output index buffer - *piCSIter++ = dp; - - // if the vertex is not yet in cache, set its cache count - if (iStampCnt-piCachingStamps[dp] > configCacheDepth) { - piCachingStamps[dp] = iStampCnt++; - ++iCacheMisses; - } - } - // flag triangle as emitted - abEmitted[fidx] = true; - } - } - - // the vertex has now no living adjacent triangles anymore - piNumTriPtr[ivdx] = 0; - - // get next fanning vertex - ivdx = -1; - int max_priority = -1; - for (unsigned int* piCur = piCandidates;piCur != piCurCandidate;++piCur) { - const unsigned int dp = *piCur; - - // must have live triangles - if (piNumTriPtr[dp] > 0) { - int priority = 0; - - // will the vertex be in cache, even after fanning occurs? - unsigned int tmp; - if ((tmp = iStampCnt-piCachingStamps[dp]) + 2*piNumTriPtr[dp] <= configCacheDepth) { - priority = tmp; - } - - // keep best candidate - if (priority > max_priority) { - max_priority = priority; - ivdx = dp; - } - } - } - // did we reach a dead end? - if (-1 == ivdx) { - // need to get a non-local vertex for which we have a good chance that it is still - // in the cache ... - while (!sDeadEndVStack.empty()) { - unsigned int iCachedIdx = sDeadEndVStack.top(); - sDeadEndVStack.pop(); - if (piNumTriPtr[ iCachedIdx ] > 0) { - ivdx = iCachedIdx; - break; - } - } - - if (-1 == ivdx) { - // well, there isn't such a vertex. Simply get the next vertex in input order and - // hope it is not too bad ... - while (ics < (int)pMesh->mNumVertices) { - ++ics; - if (piNumTriPtr[ics] > 0) { - ivdx = ics; - break; - } - } - } - } - } - float fACMR2 = 0.0f; - if (!DefaultLogger::isNullLogger()) { - fACMR2 = (float)iCacheMisses / pMesh->mNumFaces; - - // very intense verbose logging ... prepare for much text if there are many meshes - if ( DefaultLogger::get()->getLogSeverity() == Logger::VERBOSE) { - char szBuff[128]; // should be sufficiently large in every case - - ai_snprintf(szBuff,128,"Mesh %u | ACMR in: %f out: %f | ~%.1f%%",meshNum,fACMR,fACMR2, - ((fACMR - fACMR2) / fACMR) * 100.f); - DefaultLogger::get()->debug(szBuff); - } - - fACMR2 *= pMesh->mNumFaces; - } - // sort the output index buffer back to the input array - piCSIter = piIBOutput; - for (aiFace* pcFace = pMesh->mFaces; pcFace != pcEnd;++pcFace) { - pcFace->mIndices[0] = *piCSIter++; - pcFace->mIndices[1] = *piCSIter++; - pcFace->mIndices[2] = *piCSIter++; - } - - // delete temporary storage - delete[] piCachingStamps; - delete[] piIBOutput; - delete[] piCandidates; - - return fACMR2; -} |