diff options
author | Sergey Sharybin <sergey.vfx@gmail.com> | 2017-09-19 15:46:34 +0300 |
---|---|---|
committer | Sergey Sharybin <sergey.vfx@gmail.com> | 2017-09-19 15:50:09 +0300 |
commit | 3241905f40e11ffc276bcca09033c045eaad70cd (patch) | |
tree | 97a2866dc9d159fbaf0fa542c634023fccb5412e /intern/mikktspace/mikktspace.c | |
parent | 2dab6f499c1b7337c5c2676aafa2548efd246de3 (diff) |
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.
Diffstat (limited to 'intern/mikktspace/mikktspace.c')
-rw-r--r-- | intern/mikktspace/mikktspace.c | 128 |
1 files changed, 108 insertions, 20 deletions
diff --git a/intern/mikktspace/mikktspace.c b/intern/mikktspace/mikktspace.c index 947def4002c..f832b356ffe 100644 --- a/intern/mikktspace/mikktspace.c +++ b/intern/mikktspace/mikktspace.c @@ -1847,11 +1847,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 @@ -1864,29 +1954,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++) |