blender
/
blender
132
398
Fork 577
Code Issues 6.2k Pull Requests 747 Projects 19 Wiki Activity

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.
This commit is contained in:
Sergey Sharybin 2017-09-19 17:46:34 +05:00
parent 85dc915413
commit 9a5320aea3
1 changed files with 108 additions and 20 deletions
Show Stats Download Patch File Download Diff File Expand all files Collapse all files

128
intern/mikktspace/mikktspace.c
View File

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