Fix T52818: Tangent space calculation is really slow for high-density mesh with degen...
authorSergey Sharybin <sergey.vfx@gmail.com>
Tue, 19 Sep 2017 12:46:34 +0000 (17:46 +0500)
committerSergey Sharybin <sergey.vfx@gmail.com>
Tue, 19 Sep 2017 12:50:09 +0000 (17:50 +0500)
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.

intern/mikktspace/mikktspace.c

index 947def4002cbb9e26decf7be887ee4513fa6c461..f832b356ffeb7a4f3c3d79db324543b53de7427f 100644 (file)
@@ -1847,11 +1847,101 @@ static void DegenPrologue(STriInfo pTriInfos[], int piTriList_out[], const int i
        assert(iNrTrianglesIn == t);
 }
 
        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;
 {
        int t=0, i=0;
+       VertReverseLookupContext lookupCtx = { TFALSE };
        // deal with degenerate triangles
        // 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
        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];
                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++)
 
        // deal with degenerate quads with one good triangle
        for (t=0; t<iNrTrianglesIn; t++)