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
