Commit: 9a5320aea382810764b8206212fd77841e66c378 Author: Sergey Sharybin Date: Tue Sep 19 17:46:34 2017 +0500 Branches: blender-v2.79a-release https://developer.blender.org/rB9a5320aea382810764b8206212fd77841e66c378
Fix T52818: Tangent space calculation is really slow for high-density mesh with degenerated topology Now we replace O(N^2) computational complexity with O(N) extra memory penalty. Memory is much cheaper than CPU time. Keep in mind, memory penalty is like 4 megabytes per 1M vertices. =================================================================== M intern/mikktspace/mikktspace.c =================================================================== diff --git a/intern/mikktspace/mikktspace.c b/intern/mikktspace/mikktspace.c index bbac8365d86..99e945d40ba 100644 --- a/intern/mikktspace/mikktspace.c +++ b/intern/mikktspace/mikktspace.c @@ -1817,11 +1817,101 @@ static void DegenPrologue(STriInfo pTriInfos[], int piTriList_out[], const int i assert(iNrTrianglesIn == t); } -static void DegenEpilogue(STSpace psTspace[], STriInfo pTriInfos[], int piTriListIn[], const SMikkTSpaceContext * pContext, const int iNrTrianglesIn, const int iTotTris) +typedef struct VertReverseLookupContext { + tbool bIsInitialized; + int * pLookup; + int iMaxVertIndex; +} VertReverseLookupContext; + +static void GenerateReverseLookup( + const int piTriListIn[], + const int iNrTrianglesIn, + VertReverseLookupContext *pLookupCtx) +{ + int t; + // Figure out what size of lookup array we need. + pLookupCtx->iMaxVertIndex = -1; + for (t=0; t<3*iNrTrianglesIn; t++) + { + int iVertIndex = piTriListIn[t]; + if (iVertIndex > pLookupCtx->iMaxVertIndex) { + pLookupCtx->iMaxVertIndex = iVertIndex; + } + } + // Allocate memory. + if (pLookupCtx->iMaxVertIndex < 1) + { + // Nothing to allocate, all triangles are degenerate. + return; + } + pLookupCtx->pLookup = malloc(sizeof(int) * (pLookupCtx->iMaxVertIndex + 1)); + if (pLookupCtx->pLookup == NULL) + { + // Most likely run out of memory. + return; + } + // Fill in lookup. + for (t=0; t<=pLookupCtx->iMaxVertIndex; t++) { + pLookupCtx->pLookup[t] = -1; + } + for (t=0; t<3*iNrTrianglesIn; t++) + { + int iVertIndex = piTriListIn[t]; + if (pLookupCtx->pLookup[iVertIndex] != -1) + { + continue; + } + pLookupCtx->pLookup[iVertIndex] = t; + } +} + +static int LookupVertexIndexFromGoodTriangle( + VertReverseLookupContext *pLookupCtx, + int piTriListIn[], + const int iNrTrianglesIn, + const int iVertexIndex) +{ + // Allocate lookup on demand. + if (!pLookupCtx->bIsInitialized) + { + GenerateReverseLookup(piTriListIn, + iNrTrianglesIn, + pLookupCtx); + pLookupCtx->bIsInitialized = TTRUE; + } + // Make sure vertex index is in the mapping. + if (iVertexIndex > pLookupCtx->iMaxVertIndex) + { + return -1; + } + if (pLookupCtx->pLookup == NULL) { + return -1; + } + // Perform actual lookup. + return pLookupCtx->pLookup[iVertexIndex]; +} + +static void FreeReverseLookup(VertReverseLookupContext *pLookupCtx) +{ + if (!pLookupCtx->bIsInitialized) { + return; + } + if (pLookupCtx->pLookup != NULL) { + free(pLookupCtx->pLookup); + } +} + +static void DegenEpilogue(STSpace psTspace[], + STriInfo pTriInfos[], + int piTriListIn[], + const SMikkTSpaceContext * pContext, + const int iNrTrianglesIn, + const int iTotTris) { int t=0, i=0; + VertReverseLookupContext lookupCtx = { TFALSE }; // deal with degenerate triangles - // punishment for degenerate triangles is O(N^2) + // punishment for degenerate triangles is O(iNrTrianglesIn) extra memory. for (t=iNrTrianglesIn; t<iTotTris; t++) { // degenerate triangles on a quad with one good triangle are skipped @@ -1834,29 +1924,27 @@ static void DegenEpilogue(STSpace psTspace[], STriInfo pTriInfos[], int piTriLis for (i=0; i<3; i++) { const int index1 = piTriListIn[t*3+i]; - // search through the good triangles - tbool bNotFound = TTRUE; - int j=0; - while (bNotFound && j<(3*iNrTrianglesIn)) + int j = LookupVertexIndexFromGoodTriangle(&lookupCtx, + piTriListIn, + iNrTrianglesIn, + index1); + if (j < 0) { - const int index2 = piTriListIn[j]; - if (index1==index2) bNotFound=TFALSE; - else ++j; + // Matching vertex from good triangle is not found. + continue; } - if (!bNotFound) - { - const int iTri = j/3; - const int iVert = j%3; - const int iSrcVert=pTriInfos[iTri].vert_num[iVert]; - const int iSrcOffs=pTriInfos[iTri].iTSpacesOffs; - const int iDstVert=pTriInfos[t].vert_num[i]; - const int iDstOffs=pTriInfos[t].iTSpacesOffs; - // copy tspace - psTspace[iDstOffs+iDstVert] = psTspace[iSrcOffs+iSrcVert]; - } + const int iTri = j/3; + const int iVert = j%3; + const int iSrcVert=pTriInfos[iTri].vert_num[iVert]; + const int iSrcOffs=pTriInfos[iTri].iTSpacesOffs; + const int iDstVert=pTriInfos[t].vert_num[i]; + const int iDstOffs=pTriInfos[t].iTSpacesOffs; + // copy tspace + psTspace[iDstOffs+iDstVert] = psTspace[iSrcOffs+iSrcVert]; } } + FreeReverseLookup(&lookupCtx); // deal with degenerate quads with one good triangle for (t=0; t<iNrTrianglesIn; t++) _______________________________________________ Bf-blender-cvs mailing list Bf-blender-cvs@blender.org https://lists.blender.org/mailman/listinfo/bf-blender-cvs