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.

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++)