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:
parent
85dc915413
commit
9a5320aea3
|
@ -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++)
|
||||
|
|
Loading…
Reference in New Issue