Page MenuHome
Differential D2702 Diff 8906 intern/mikktspace/mikktspace.c

Changeset View

Standalone View

View Options

intern/mikktspace/mikktspace.c

Show First 20 Lines • Show All 422 Lines • ▼ Show 20 Lines
typedef struct { typedef struct {
float vert[3]; float vert[3];
int index; int index;
} STmpVert; } STmpVert;
static const int g_iCells = 2048; static const int g_iCells = 2048;
#ifdef _MSC_VER
# define NOINLINE __declspec(noinline)
#else
# define NOINLINE __attribute__ ((noinline))
#endif
// it is IMPORTANT that this function is called to evaluate the hash since
// inlining could potentially reorder instructions and generate different
// results for the same effective input value fVal.
static NOINLINE int FindGridCell(const float fMin, const float fMax, const float fVal)
{
const float fIndex = g_iCells * ((fVal-fMin)/(fMax-fMin));
const int iIndex = (int)fIndex;
return iIndex < g_iCells ? (iIndex >= 0 ? iIndex : 0) : (g_iCells - 1);
}
static void MergeVertsFast(int piTriList_in_and_out[], STmpVert pTmpVert[], const SMikkTSpaceContext * pContext, const int iL_in, const int iR_in);
static void MergeVertsSlow(int piTriList_in_and_out[], const SMikkTSpaceContext * pContext, const int pTable[], const int iEntries);
static void GenerateSharedVerticesIndexListSlow(int piTriList_in_and_out[], const SMikkTSpaceContext * pContext, const int iNrTrianglesIn); static void GenerateSharedVerticesIndexListSlow(int piTriList_in_and_out[], const SMikkTSpaceContext * pContext, const int iNrTrianglesIn);
static void GenerateSharedVerticesIndexList(int piTriList_in_and_out[], const SMikkTSpaceContext * pContext, const int iNrTrianglesIn) static uint float_as_uint(const float v)
{
// Generate bounding box
int * piHashTable=NULL, * piHashCount=NULL, * piHashOffsets=NULL, * piHashCount2=NULL;
STmpVert * pTmpVert = NULL;
int i=0, iChannel=0, k=0, e=0;
int iMaxCount=0;
SVec3 vMin = GetPosition(pContext, 0), vMax = vMin, vDim;
float fMin, fMax;
for (i=1; i<(iNrTrianglesIn*3); i++)
{
const int index = piTriList_in_and_out[i];
const SVec3 vP = GetPosition(pContext, index);
if (vMin.x > vP.x) vMin.x = vP.x;
else if (vMax.x < vP.x) vMax.x = vP.x;
if (vMin.y > vP.y) vMin.y = vP.y;
else if (vMax.y < vP.y) vMax.y = vP.y;
if (vMin.z > vP.z) vMin.z = vP.z;
else if (vMax.z < vP.z) vMax.z = vP.z;
}
vDim = vsub(vMax,vMin);
iChannel = 0;
fMin = vMin.x; fMax=vMax.x;
if (vDim.y>vDim.x && vDim.y>vDim.z)
{
iChannel=1;
fMin = vMin.y;
fMax = vMax.y;
}
else if (vDim.z>vDim.x)
{
iChannel=2;
fMin = vMin.z;
fMax = vMax.z;
}
// make allocations
piHashTable = (int *) malloc(sizeof(int)*iNrTrianglesIn*3);
piHashCount = (int *) malloc(sizeof(int)*g_iCells);
piHashOffsets = (int *) malloc(sizeof(int)*g_iCells);
piHashCount2 = (int *) malloc(sizeof(int)*g_iCells);
if (piHashTable==NULL || piHashCount==NULL || piHashOffsets==NULL || piHashCount2==NULL)
{
if (piHashTable!=NULL) free(piHashTable);
if (piHashCount!=NULL) free(piHashCount);
if (piHashOffsets!=NULL) free(piHashOffsets);
if (piHashCount2!=NULL) free(piHashCount2);
GenerateSharedVerticesIndexListSlow(piTriList_in_and_out, pContext, iNrTrianglesIn);
return;
}
memset(piHashCount, 0, sizeof(int)*g_iCells);
memset(piHashCount2, 0, sizeof(int)*g_iCells);
// count amount of elements in each cell unit
for (i=0; i<(iNrTrianglesIn*3); i++)
{ {
const int index = piTriList_in_and_out[i]; return *((uint*)(&v));
const SVec3 vP = GetPosition(pContext, index);
const float fVal = iChannel==0 ? vP.x : (iChannel==1 ? vP.y : vP.z);
const int iCell = FindGridCell(fMin, fMax, fVal);
++piHashCount[iCell];
}
// evaluate start index of each cell.
piHashOffsets[0]=0;
for (k=1; k<g_iCells; k++)
piHashOffsets[k]=piHashOffsets[k-1]+piHashCount[k-1];
// insert vertices
for (i=0; i<(iNrTrianglesIn*3); i++)
{
const int index = piTriList_in_and_out[i];
const SVec3 vP = GetPosition(pContext, index);
const float fVal = iChannel==0 ? vP.x : (iChannel==1 ? vP.y : vP.z);
const int iCell = FindGridCell(fMin, fMax, fVal);
int * pTable = NULL;
assert(piHashCount2[iCell]<piHashCount[iCell]);
pTable = &piHashTable[piHashOffsets[iCell]];
pTable[piHashCount2[iCell]] = i; // vertex i has been inserted.
++piHashCount2[iCell];
} }
for (k=0; k<g_iCells; k++)
assert(piHashCount2[k] == piHashCount[k]); // verify the count
free(piHashCount2);
// find maximum amount of entries in any hash entry
iMaxCount = piHashCount[0];
for (k=1; k<g_iCells; k++)
if (iMaxCount<piHashCount[k])
iMaxCount=piHashCount[k];
pTmpVert = (STmpVert *) malloc(sizeof(STmpVert)*iMaxCount);
#define HASH(x, y, z) (((x) * 73856093) ^ ((y) * 19349663) ^ ((z) * 83492791))
#define HASH_F(x, y, z) HASH(float_as_uint(x), float_as_uint(y), float_as_uint(z))
// complete the merge /* Sort comp and data based on comp.
for (k=0; k<g_iCells; k++) * comp2 and data2 are used as temporary storage. */
{ static void radixsort(uint *comp, int *data, uint *comp2, int *data2, int n)
// extract table of cell k and amount of entries in it
int * pTable = &piHashTable[piHashOffsets[k]];
const int iEntries = piHashCount[k];
if (iEntries < 2) continue;
if (pTmpVert!=NULL)
{
for (e=0; e<iEntries; e++)
{ {
int i = pTable[e]; int shift = 0;
const SVec3 vP = GetPosition(pContext, piTriList_in_and_out[i]); for(int pass = 0; pass < 4; pass++, shift+=8) {
pTmpVert[e].vert[0] = vP.x; pTmpVert[e].vert[1] = vP.y; int bins[257] = {0};
pTmpVert[e].vert[2] = vP.z; pTmpVert[e].index = i; /* Count number of elements per bin. */
for(int i = 0; i < n; i++) {
bins[((comp[i] >> shift) & 0xff) + 1]++;
} }
MergeVertsFast(piTriList_in_and_out, pTmpVert, pContext, 0, iEntries-1); /* Compute prefix sum to find position of each bin in the sorted array. */
for(int i = 2; i < 256; i++) {
bins[i] += bins[i-1];
} }
else /* Insert the elements in their correct location based on their bin. */
MergeVertsSlow(piTriList_in_and_out, pContext, pTable, iEntries); for(int i = 0; i < n; i++) {
int pos = bins[(comp[i] >> shift) & 0xff]++;
comp2[pos] = comp[i];
data2[pos] = data[i];
} }
if (pTmpVert!=NULL) { free(pTmpVert); } /* Swap arrays. */
free(piHashTable); int *tmpdata = data; data = data2; data2 = tmpdata;
free(piHashCount); uint *tmpcomp = comp; comp = comp2; comp2 = tmpcomp;
free(piHashOffsets);
} }
static void MergeVertsFast(int piTriList_in_and_out[], STmpVert pTmpVert[], const SMikkTSpaceContext * pContext, const int iL_in, const int iR_in)
{
// make bbox
int c=0, l=0, channel=0;
float fvMin[3], fvMax[3];
float dx=0, dy=0, dz=0, fSep=0;
for (c=0; c<3; c++)
{ fvMin[c]=pTmpVert[iL_in].vert[c]; fvMax[c]=fvMin[c]; }
for (l=(iL_in+1); l<=iR_in; l++) {
for (c=0; c<3; c++) {
if (fvMin[c]>pTmpVert[l].vert[c]) fvMin[c]=pTmpVert[l].vert[c];
if (fvMax[c]<pTmpVert[l].vert[c]) fvMax[c]=pTmpVert[l].vert[c];
} }
}
dx = fvMax[0]-fvMin[0];
dy = fvMax[1]-fvMin[1];
dz = fvMax[2]-fvMin[2];
channel = 0; /* Merge identical vertices.
if (dy>dx && dy>dz) channel=1; * To find vertices with identical position, normal and texcoord, we calculate a hash of the 9 values.
else if (dz>dx) channel=2; * Then, by sorting based on that hash, identical elements (having identical hashes) will be moved next to each other.
* Since there might be hash collisions, the elements of each block are then compared with each other and duplicates
fSep = 0.5f*(fvMax[channel]+fvMin[channel]); * are merged.
*/
// stop if all vertices are NaNs static void GenerateSharedVerticesIndexList(int piTriList_in_and_out[], const SMikkTSpaceContext * pContext, const int iNrTrianglesIn)
if (!isfinite(fSep)) {
int numVertices = iNrTrianglesIn*3;
uint *hashes = (uint*) malloc(sizeof(uint)*numVertices);
int *indices = (int*) malloc(sizeof(int)*numVertices);
if(hashes == NULL || indices == NULL) {
if(hashes) free(hashes);
if(indices) free(indices);
GenerateSharedVerticesIndexListSlow(piTriList_in_and_out, pContext, iNrTrianglesIn);
return; return;
}
// terminate recursion when the separation/average value for (int i = 0; i < numVertices; i++) {
// is no longer strictly between fMin and fMax values.
if (fSep>=fvMax[channel] || fSep<=fvMin[channel])
{
// complete the weld
for (l=iL_in; l<=iR_in; l++)
{
int i = pTmpVert[l].index;
const int index = piTriList_in_and_out[i]; const int index = piTriList_in_and_out[i];
const SVec3 vP = GetPosition(pContext, index); const SVec3 vP = GetPosition(pContext, index);
const uint hashP = HASH_F(vP.x, vP.y, vP.z);
const SVec3 vN = GetNormal(pContext, index); const SVec3 vN = GetNormal(pContext, index);
const SVec3 vT = GetTexCoord(pContext, index); const uint hashN = HASH_F(vN.x, vN.y, vN.z);
tbool bNotFound = TTRUE; const SVec3 vT = GetTexCoord(pContext, index);
int l2=iL_in, i2rec=-1; const uint hashT = HASH_F(vT.x, vT.y, vT.z);
while (l2<l && bNotFound)
{
const int i2 = pTmpVert[l2].index;
const int index2 = piTriList_in_and_out[i2];
const SVec3 vP2 = GetPosition(pContext, index2);
const SVec3 vN2 = GetNormal(pContext, index2);
const SVec3 vT2 = GetTexCoord(pContext, index2);
i2rec=i2;
//if (vP==vP2 && vN==vN2 && vT==vT2) hashes[i] = HASH(hashP, hashN, hashT);
if (vP.x==vP2.x && vP.y==vP2.y && vP.z==vP2.z && indices[i] = i;
vN.x==vN2.x && vN.y==vN2.y && vN.z==vN2.z &&
vT.x==vT2.x && vT.y==vT2.y && vT.z==vT2.z)
bNotFound = TFALSE;
else
++l2;
} }
// merge if previously found uint *temp_hashes = (uint*) malloc(sizeof(uint)*numVertices);
if (!bNotFound) int *temp_indices = (int*) malloc(sizeof(int)*numVertices);
piTriList_in_and_out[i] = piTriList_in_and_out[i2rec]; if(temp_hashes == NULL || temp_indices == NULL) {
} if(hashes) free(hashes);
if(indices) free(indices);
if(temp_hashes) free(temp_hashes);
if(temp_indices) free(temp_indices);
GenerateSharedVerticesIndexListSlow(piTriList_in_and_out, pContext, iNrTrianglesIn);
return;
} }
else
{
int iL=iL_in, iR=iR_in;
assert((iR_in-iL_in)>0); // at least 2 entries
// separate (by fSep) all points between iL_in and iR_in in pTmpVert[] radixsort(hashes, indices, temp_hashes, temp_indices, numVertices);
while (iL < iR) free(temp_hashes);
{ free(temp_indices);
tbool bReadyLeftSwap = TFALSE, bReadyRightSwap = TFALSE;
while ((!bReadyLeftSwap) && iL<iR)
{
assert(iL>=iL_in && iL<=iR_in);
bReadyLeftSwap = !(pTmpVert[iL].vert[channel]<fSep);
if (!bReadyLeftSwap) ++iL;
}
while ((!bReadyRightSwap) && iL<iR)
{
assert(iR>=iL_in && iR<=iR_in);
bReadyRightSwap = pTmpVert[iR].vert[channel]<fSep;
if (!bReadyRightSwap) --iR;
}
assert( (iL<iR) || !(bReadyLeftSwap && bReadyRightSwap) );
if (bReadyLeftSwap && bReadyRightSwap) int blockstart = 0;
{ while (blockstart < numVertices) {
const STmpVert sTmp = pTmpVert[iL]; /* Find end of this block (exclusive). */
assert(iL<iR); uint hash = hashes[blockstart];
pTmpVert[iL] = pTmpVert[iR]; int blockend = blockstart+1;
pTmpVert[iR] = sTmp; for(; blockend < numVertices; blockend++) {
++iL; --iR; if(hashes[blockend] != hash) break;
}
} }
assert(iL==(iR+1) || (iL==iR)); for(int i = blockstart; i < blockend; i++) {
if (iL==iR) int index1 = piTriList_in_and_out[indices[i]];
const SVec3 vP = GetPosition(pContext, index1);
const SVec3 vN = GetNormal(pContext, index1);
const SVec3 vT = GetTexCoord(pContext, index1);
for(int i2 = i+1; i2 < blockend; i2++) {
int index2 = piTriList_in_and_out[indices[i2]];
if(index1 == index2) continue;
if(veq(vP, GetPosition(pContext, index2)) &&
veq(vN, GetNormal(pContext, index2)) &&
veq(vT, GetTexCoord(pContext, index2)))
{ {
const tbool bReadyRightSwap = pTmpVert[iR].vert[channel]<fSep; piTriList_in_and_out[indices[i2]] = index1;
if (bReadyRightSwap) ++iL; /* Once i2>i has been identified as a duplicate, we can stop since any
else --iR; * i3>i2>i that is a duplicate of i (and therefore also i2) will be
* compared to i2 and therefore be identified there anyways. */
break;
} }
// only need to weld when there is more than 1 instance of the (x,y,z)
if (iL_in < iR)
MergeVertsFast(piTriList_in_and_out, pTmpVert, pContext, iL_in, iR); // weld all left of fSep
if (iL < iR_in)
MergeVertsFast(piTriList_in_and_out, pTmpVert, pContext, iL, iR_in); // weld all right of (or equal to) fSep
} }
} }
static void MergeVertsSlow(int piTriList_in_and_out[], const SMikkTSpaceContext * pContext, const int pTable[], const int iEntries) /* Advance to next block. */
{ blockstart = blockend;
// this can be optimized further using a tree structure or more hashing.
int e=0;
for (e=0; e<iEntries; e++)
{
int i = pTable[e];
const int index = piTriList_in_and_out[i];
const SVec3 vP = GetPosition(pContext, index);
const SVec3 vN = GetNormal(pContext, index);
const SVec3 vT = GetTexCoord(pContext, index);
tbool bNotFound = TTRUE;
int e2=0, i2rec=-1;
while (e2<e && bNotFound)
{
const int i2 = pTable[e2];
const int index2 = piTriList_in_and_out[i2];
const SVec3 vP2 = GetPosition(pContext, index2);
const SVec3 vN2 = GetNormal(pContext, index2);
const SVec3 vT2 = GetTexCoord(pContext, index2);
i2rec = i2;
if (veq(vP,vP2) && veq(vN,vN2) && veq(vT,vT2))
bNotFound = TFALSE;
else
++e2;
} }
// merge if previously found free(hashes);
if (!bNotFound) free(indices);
piTriList_in_and_out[i] = piTriList_in_and_out[i2rec];
}
} }
static void GenerateSharedVerticesIndexListSlow(int piTriList_in_and_out[], const SMikkTSpaceContext * pContext, const int iNrTrianglesIn) static void GenerateSharedVerticesIndexListSlow(int piTriList_in_and_out[], const SMikkTSpaceContext * pContext, const int iNrTrianglesIn)
{ {
int iNumUniqueVerts = 0, t=0, i=0; int iNumUniqueVerts = 0, t=0, i=0;
for (t=0; t<iNrTrianglesIn; t++) for (t=0; t<iNrTrianglesIn; t++)
{ {
for (i=0; i<3; i++) for (i=0; i<3; i++)
▲ Show 20 Lines • Show All 1,165 Lines • Show Last 20 Lines