/** \file mikktspace/mikktspace.c * \ingroup mikktspace */ /** * Copyright (C) 2011 by Morten S. Mikkelsen * * This software is provided 'as-is', without any express or implied * warranty. In no event will the authors be held liable for any damages * arising from the use of this software. * * Permission is granted to anyone to use this software for any purpose, * including commercial applications, and to alter it and redistribute it * freely, subject to the following restrictions: * * 1. The origin of this software must not be misrepresented; you must not * claim that you wrote the original software. If you use this software * in a product, an acknowledgment in the product documentation would be * appreciated but is not required. * 2. Altered source versions must be plainly marked as such, and must not be * misrepresented as being the original software. * 3. This notice may not be removed or altered from any source distribution. */ #include <assert.h> #include <stdio.h> #include <math.h> #include <string.h> #include <float.h> #include <stdlib.h> #include "mikktspace.h" #define TFALSE 0 #define TTRUE 1 #ifndef M_PI #define M_PI 3.1415926535897932384626433832795 #endif #define INTERNAL_RND_SORT_SEED 39871946 // internal structure typedef struct { float x, y, z; } SVec3; static tbool veq( const SVec3 v1, const SVec3 v2 ) { return (v1.x == v2.x) && (v1.y == v2.y) && (v1.z == v2.z); } static SVec3 vadd( const SVec3 v1, const SVec3 v2 ) { SVec3 vRes; vRes.x = v1.x + v2.x; vRes.y = v1.y + v2.y; vRes.z = v1.z + v2.z; return vRes; } static SVec3 vsub( const SVec3 v1, const SVec3 v2 ) { SVec3 vRes; vRes.x = v1.x - v2.x; vRes.y = v1.y - v2.y; vRes.z = v1.z - v2.z; return vRes; } static SVec3 vscale(const float fS, const SVec3 v) { SVec3 vRes; vRes.x = fS * v.x; vRes.y = fS * v.y; vRes.z = fS * v.z; return vRes; } static float LengthSquared( const SVec3 v ) { return v.x*v.x + v.y*v.y + v.z*v.z; } static float Length( const SVec3 v ) { return sqrtf(LengthSquared(v)); } static SVec3 Normalize( const SVec3 v ) { return vscale(1 / Length(v), v); } static float vdot( const SVec3 v1, const SVec3 v2) { return v1.x*v2.x + v1.y*v2.y + v1.z*v2.z; } static tbool NotZero(const float fX) { // could possibly use FLT_EPSILON instead return fabsf(fX) > FLT_MIN; } static tbool VNotZero(const SVec3 v) { // might change this to an epsilon based test return NotZero(v.x) || NotZero(v.y) || NotZero(v.z); } typedef struct { int iNrFaces; int * pTriMembers; } SSubGroup; typedef struct { int iNrFaces; int * pFaceIndices; int iVertexRepresentitive; tbool bOrientPreservering; } SGroup; // #define MARK_DEGENERATE 1 #define QUAD_ONE_DEGEN_TRI 2 #define GROUP_WITH_ANY 4 #define ORIENT_PRESERVING 8 typedef struct { int FaceNeighbors[3]; SGroup * AssignedGroup[3]; // normalized first order face derivatives SVec3 vOs, vOt; float fMagS, fMagT; // original magnitudes // determines if the current and the next triangle are a quad. int iOrgFaceNumber; int iFlag, iTSpacesOffs; unsigned char vert_num[4]; } STriInfo; typedef struct { SVec3 vOs; float fMagS; SVec3 vOt; float fMagT; int iCounter; // this is to average back into quads. tbool bOrient; } STSpace; static int GenerateInitialVerticesIndexList(STriInfo pTriInfos[], int piTriList_out[], const SMikkTSpaceContext * pContext, const int iNrTrianglesIn); static void GenerateSharedVerticesIndexList(int piTriList_in_and_out[], const SMikkTSpaceContext * pContext, const int iNrTrianglesIn); static void InitTriInfo(STriInfo pTriInfos[], const int piTriListIn[], const SMikkTSpaceContext * pContext, const int iNrTrianglesIn); static int Build4RuleGroups(STriInfo pTriInfos[], SGroup pGroups[], int piGroupTrianglesBuffer[], const int piTriListIn[], const int iNrTrianglesIn); static tbool GenerateTSpaces(STSpace psTspace[], const STriInfo pTriInfos[], const SGroup pGroups[], const int iNrActiveGroups, const int piTriListIn[], const float fThresCos, const SMikkTSpaceContext * pContext); static int MakeIndex(const int iFace, const int iVert) { assert(iVert>=0 && iVert<4 && iFace>=0); return (iFace<<2) | (iVert&0x3); } static void IndexToData(int * piFace, int * piVert, const int iIndexIn) { piVert[0] = iIndexIn&0x3; piFace[0] = iIndexIn>>2; } static STSpace AvgTSpace(const STSpace * pTS0, const STSpace * pTS1) { STSpace ts_res; // this if is important. Due to floating point precision // averaging when ts0==ts1 will cause a slight difference // which results in tangent space splits later on if (pTS0->fMagS==pTS1->fMagS && pTS0->fMagT==pTS1->fMagT && veq(pTS0->vOs,pTS1->vOs) && veq(pTS0->vOt, pTS1->vOt)) { ts_res.fMagS = pTS0->fMagS; ts_res.fMagT = pTS0->fMagT; ts_res.vOs = pTS0->vOs; ts_res.vOt = pTS0->vOt; } else { ts_res.fMagS = 0.5f*(pTS0->fMagS+pTS1->fMagS); ts_res.fMagT = 0.5f*(pTS0->fMagT+pTS1->fMagT); ts_res.vOs = vadd(pTS0->vOs,pTS1->vOs); ts_res.vOt = vadd(pTS0->vOt,pTS1->vOt); if ( VNotZero(ts_res.vOs) ) ts_res.vOs = Normalize(ts_res.vOs); if ( VNotZero(ts_res.vOt) ) ts_res.vOt = Normalize(ts_res.vOt); } return ts_res; } static SVec3 GetPosition(const SMikkTSpaceContext * pContext, const int index); static SVec3 GetNormal(const SMikkTSpaceContext * pContext, const int index); static SVec3 GetTexCoord(const SMikkTSpaceContext * pContext, const int index); // degen triangles static void DegenPrologue(STriInfo pTriInfos[], int piTriList_out[], const int iNrTrianglesIn, const int iTotTris); static void DegenEpilogue(STSpace psTspace[], STriInfo pTriInfos[], int piTriListIn[], const SMikkTSpaceContext * pContext, const int iNrTrianglesIn, const int iTotTris); tbool genTangSpaceDefault(const SMikkTSpaceContext * pContext) { return genTangSpace(pContext, 180.0f); } tbool genTangSpace(const SMikkTSpaceContext * pContext, const float fAngularThreshold) { // count nr_triangles int * piTriListIn = NULL, * piGroupTrianglesBuffer = NULL; STriInfo * pTriInfos = NULL; SGroup * pGroups = NULL; STSpace * psTspace = NULL; int iNrTrianglesIn = 0, f=0, t=0, i=0; int iNrTSPaces = 0, iTotTris = 0, iDegenTriangles = 0, iNrMaxGroups = 0; int iNrActiveGroups = 0, index = 0; const int iNrFaces = pContext->m_pInterface->m_getNumFaces(pContext); tbool bRes = TFALSE; const float fThresCos = (float) cos((fAngularThreshold*(float)M_PI)/180.0f); // verify all call-backs have been set if ( pContext->m_pInterface->m_getNumFaces==NULL || pContext->m_pInterface->m_getNumVerticesOfFace==NULL || pContext->m_pInterface->m_getPosition==NULL || pContext->m_pInterface->m_getNormal==NULL || pContext->m_pInterface->m_getTexCoord==NULL ) return TFALSE; // count triangles on supported faces for (f=0; f<iNrFaces; f++) { const int verts = pContext->m_pInterface->m_getNumVerticesOfFace(pContext, f); if (verts==3) ++iNrTrianglesIn; else if (verts==4) iNrTrianglesIn += 2; } if (iNrTrianglesIn<=0) return TFALSE; // allocate memory for an index list piTriListIn = (int *) malloc(sizeof(int)*3*iNrTrianglesIn); pTriInfos = (STriInfo *) malloc(sizeof(STriInfo)*iNrTrianglesIn); if (piTriListIn==NULL || pTriInfos==NULL) { if (piTriListIn!=NULL) free(piTriListIn); if (pTriInfos!=NULL) free(pTriInfos); return TFALSE; } // make an initial triangle --> face index list iNrTSPaces = GenerateInitialVerticesIndexList(pTriInfos, piTriListIn, pContext, iNrTrianglesIn); // make a welded index list of identical positions and attributes (pos, norm, texc) //printf("gen welded index list begin\n"); GenerateSharedVerticesIndexList(piTriListIn, pContext, iNrTrianglesIn); //printf("gen welded index list end\n"); // Mark all degenerate triangles iTotTris = iNrTrianglesIn; iDegenTriangles = 0; for (t=0; t<iTotTris; t++) { const int i0 = piTriListIn[t*3+0]; const int i1 = piTriListIn[t*3+1]; const int i2 = piTriListIn[t*3+2]; const SVec3 p0 = GetPosition(pContext, i0); const SVec3 p1 = GetPosition(pContext, i1); const SVec3 p2 = GetPosition(pContext, i2); if (veq(p0,p1) || veq(p0,p2) || veq(p1,p2)) // degenerate { pTriInfos[t].iFlag |= MARK_DEGENERATE; ++iDegenTriangles; } } iNrTrianglesIn = iTotTris - iDegenTriangles; // mark all triangle pairs that belong to a quad with only one // good triangle. These need special treatment in DegenEpilogue(). // Additionally, move all good triangles to the start of // pTriInfos[] and piTriListIn[] without changing order and // put the degenerate triangles last. DegenPrologue(pTriInfos, piTriListIn, iNrTrianglesIn, iTotTris); // evaluate triangle level attributes and neighbor list //printf("gen neighbors list begin\n"); InitTriInfo(pTriInfos, piTriListIn, pContext, iNrTrianglesIn); //printf("gen neighbors list end\n"); // based on the 4 rules, identify groups based on connectivity iNrMaxGroups = iNrTrianglesIn*3; pGroups = (SGroup *) malloc(sizeof(SGroup)*iNrMaxGroups); piGroupTrianglesBuffer = (int *) malloc(sizeof(int)*iNrTrianglesIn*3); if (pGroups==NULL || piGroupTrianglesBuffer==NULL) { if (pGroups!=NULL) free(pGroups); if (piGroupTrianglesBuffer!=NULL) free(piGroupTrianglesBuffer); free(piTriListIn); free(pTriInfos); return TFALSE; } //printf("gen 4rule groups begin\n"); iNrActiveGroups = Build4RuleGroups(pTriInfos, pGroups, piGroupTrianglesBuffer, piTriListIn, iNrTrianglesIn); //printf("gen 4rule groups end\n"); // psTspace = (STSpace *) malloc(sizeof(STSpace)*iNrTSPaces); if (psTspace==NULL) { free(piTriListIn); free(pTriInfos); free(pGroups); free(piGroupTrianglesBuffer); return TFALSE; } memset(psTspace, 0, sizeof(STSpace)*iNrTSPaces); for (t=0; t<iNrTSPaces; t++) { psTspace[t].vOs.x=1.0f; psTspace[t].vOs.y=0.0f; psTspace[t].vOs.z=0.0f; psTspace[t].fMagS = 1.0f; psTspace[t].vOt.x=0.0f; psTspace[t].vOt.y=1.0f; psTspace[t].vOt.z=0.0f; psTspace[t].fMagT = 1.0f; } // make tspaces, each group is split up into subgroups if necessary // based on fAngularThreshold. Finally a tangent space is made for // every resulting subgroup //printf("gen tspaces begin\n"); bRes = GenerateTSpaces(psTspace, pTriInfos, pGroups, iNrActiveGroups, piTriListIn, fThresCos, pContext); //printf("gen tspaces end\n"); // clean up free(pGroups); free(piGroupTrianglesBuffer); if (!bRes) // if an allocation in GenerateTSpaces() failed { // clean up and return false free(pTriInfos); free(piTriListIn); free(psTspace); return TFALSE; } // degenerate quads with one good triangle will be fixed by copying a space from // the good triangle to the coinciding vertex. // all other degenerate triangles will just copy a space from any good triangle // with the same welded index in piTriListIn[]. DegenEpilogue(psTspace, pTriInfos, piTriListIn, pContext, iNrTrianglesIn, iTotTris); free(pTriInfos); free(piTriListIn); index = 0; for (f=0; f<iNrFaces; f++) { const int verts = pContext->m_pInterface->m_getNumVerticesOfFace(pContext, f); if (verts!=3 && verts!=4) continue; // I've decided to let degenerate triangles and group-with-anythings // vary between left/right hand coordinate systems at the vertices. // All healthy triangles on the other hand are built to always be either or. /*// force the coordinate system orientation to be uniform for every face. // (this is already the case for good triangles but not for // degenerate ones and those with bGroupWithAnything==true) bool bOrient = psTspace[index].bOrient; if (psTspace[index].iCounter == 0) // tspace was not derived from a group { // look for a space created in GenerateTSpaces() by iCounter>0 bool bNotFound = true; int i=1; while (i<verts && bNotFound) { if (psTspace[index+i].iCounter > 0) bNotFound=false; else ++i; } if (!bNotFound) bOrient = psTspace[index+i].bOrient; }*/ // set data for (i=0; i<verts; i++) { const STSpace * pTSpace = &psTspace[index]; float tang[] = {pTSpace->vOs.x, pTSpace->vOs.y, pTSpace->vOs.z}; float bitang[] = {pTSpace->vOt.x, pTSpace->vOt.y, pTSpace->vOt.z}; if (pContext->m_pInterface->m_setTSpace!=NULL) pContext->m_pInterface->m_setTSpace(pContext, tang, bitang, pTSpace->fMagS, pTSpace->fMagT, pTSpace->bOrient, f, i); if (pContext->m_pInterface->m_setTSpaceBasic!=NULL) pContext->m_pInterface->m_setTSpaceBasic(pContext, tang, pTSpace->bOrient==TTRUE ? 1.0f : (-1.0f), f, i); ++index; } } free(psTspace); return TTRUE; } /////////////////////////////////////////////////////////////////////////////////////////////////////////////////// typedef struct { float vert[3]; int index; } STmpVert; 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 GenerateSharedVerticesIndexList(int piTriList_in_and_out[], const SMikkTSpaceContext * pContext, const int iNrTrianglesIn) { // 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]; 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); // complete the merge for (k=0; k<g_iCells; k++) { // 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]; const SVec3 vP = GetPosition(pContext, piTriList_in_and_out[i]); pTmpVert[e].vert[0] = vP.x; pTmpVert[e].vert[1] = vP.y; pTmpVert[e].vert[2] = vP.z; pTmpVert[e].index = i; } MergeVertsFast(piTriList_in_and_out, pTmpVert, pContext, 0, iEntries-1); } else MergeVertsSlow(piTriList_in_and_out, pContext, pTable, iEntries); } if (pTmpVert!=NULL) { free(pTmpVert); } free(piHashTable); free(piHashCount); 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]; else 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; if (dy>dx && dy>dz) channel=1; else if (dz>dx) channel=2; fSep = 0.5f*(fvMax[channel]+fvMin[channel]); // terminate recursion when the separation/average value // 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 SVec3 vP = GetPosition(pContext, index); const SVec3 vN = GetNormal(pContext, index); const SVec3 vT = GetTexCoord(pContext, index); tbool bNotFound = TTRUE; int l2=iL_in, i2rec=-1; 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) if (vP.x==vP2.x && vP.y==vP2.y && vP.z==vP2.z && 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 if (!bNotFound) piTriList_in_and_out[i] = piTriList_in_and_out[i2rec]; } } 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[] while (iL < iR) { 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) { const STmpVert sTmp = pTmpVert[iL]; assert(iL<iR); pTmpVert[iL] = pTmpVert[iR]; pTmpVert[iR] = sTmp; ++iL; --iR; } } assert(iL==(iR+1) || (iL==iR)); if (iL==iR) { const tbool bReadyRightSwap = pTmpVert[iR].vert[channel]<fSep; if (bReadyRightSwap) ++iL; else --iR; } // 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) { // 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 if (!bNotFound) piTriList_in_and_out[i] = piTriList_in_and_out[i2rec]; } } static void GenerateSharedVerticesIndexListSlow(int piTriList_in_and_out[], const SMikkTSpaceContext * pContext, const int iNrTrianglesIn) { int iNumUniqueVerts = 0, t=0, i=0; for (t=0; t<iNrTrianglesIn; t++) { for (i=0; i<3; i++) { const int offs = t*3 + i; const int index = piTriList_in_and_out[offs]; const SVec3 vP = GetPosition(pContext, index); const SVec3 vN = GetNormal(pContext, index); const SVec3 vT = GetTexCoord(pContext, index); tbool bFound = TFALSE; int t2=0, index2rec=-1; while (!bFound && t2<=t) { int j=0; while (!bFound && j<3) { const int index2 = piTriList_in_and_out[t2*3 + j]; const SVec3 vP2 = GetPosition(pContext, index2); const SVec3 vN2 = GetNormal(pContext, index2); const SVec3 vT2 = GetTexCoord(pContext, index2); if (veq(vP,vP2) && veq(vN,vN2) && veq(vT,vT2)) bFound = TTRUE; else ++j; } if (!bFound) ++t2; } assert(bFound); // if we found our own if (index2rec == index) { ++iNumUniqueVerts; } piTriList_in_and_out[offs] = index2rec; } } } static int GenerateInitialVerticesIndexList(STriInfo pTriInfos[], int piTriList_out[], const SMikkTSpaceContext * pContext, const int iNrTrianglesIn) { int iTSpacesOffs = 0, f=0, t=0; int iDstTriIndex = 0; for (f=0; f<pContext->m_pInterface->m_getNumFaces(pContext); f++) { const int verts = pContext->m_pInterface->m_getNumVerticesOfFace(pContext, f); if (verts!=3 && verts!=4) continue; pTriInfos[iDstTriIndex].iOrgFaceNumber = f; pTriInfos[iDstTriIndex].iTSpacesOffs = iTSpacesOffs; if (verts==3) { unsigned char * pVerts = pTriInfos[iDstTriIndex].vert_num; pVerts[0]=0; pVerts[1]=1; pVerts[2]=2; piTriList_out[iDstTriIndex*3+0] = MakeIndex(f, 0); piTriList_out[iDstTriIndex*3+1] = MakeIndex(f, 1); piTriList_out[iDstTriIndex*3+2] = MakeIndex(f, 2); ++iDstTriIndex; // next } else { { pTriInfos[iDstTriIndex+1].iOrgFaceNumber = f; pTriInfos[iDstTriIndex+1].iTSpacesOffs = iTSpacesOffs; } { // need an order independent way to evaluate // tspace on quads. This is done by splitting // along the shortest diagonal. const int i0 = MakeIndex(f, 0); const int i1 = MakeIndex(f, 1); const int i2 = MakeIndex(f, 2); const int i3 = MakeIndex(f, 3); const SVec3 T0 = GetTexCoord(pContext, i0); const SVec3 T1 = GetTexCoord(pContext, i1); const SVec3 T2 = GetTexCoord(pContext, i2); const SVec3 T3 = GetTexCoord(pContext, i3); const float distSQ_02 = LengthSquared(vsub(T2,T0)); const float distSQ_13 = LengthSquared(vsub(T3,T1)); tbool bQuadDiagIs_02; if (distSQ_02<distSQ_13) bQuadDiagIs_02 = TTRUE; else if (distSQ_13<distSQ_02) bQuadDiagIs_02 = TFALSE; else { const SVec3 P0 = GetPosition(pContext, i0); const SVec3 P1 = GetPosition(pContext, i1); const SVec3 P2 = GetPosition(pContext, i2); const SVec3 P3 = GetPosition(pContext, i3); const float distSQ_02 = LengthSquared(vsub(P2,P0)); const float distSQ_13 = LengthSquared(vsub(P3,P1)); bQuadDiagIs_02 = distSQ_13<distSQ_02 ? TFALSE : TTRUE; } if (bQuadDiagIs_02) { { unsigned char * pVerts_A = pTriInfos[iDstTriIndex].vert_num; pVerts_A[0]=0; pVerts_A[1]=1; pVerts_A[2]=2; } piTriList_out[iDstTriIndex*3+0] = i0; piTriList_out[iDstTriIndex*3+1] = i1; piTriList_out[iDstTriIndex*3+2] = i2; ++iDstTriIndex; // next { unsigned char * pVerts_B = pTriInfos[iDstTriIndex].vert_num; pVerts_B[0]=0; pVerts_B[1]=2; pVerts_B[2]=3; } piTriList_out[iDstTriIndex*3+0] = i0; piTriList_out[iDstTriIndex*3+1] = i2; piTriList_out[iDstTriIndex*3+2] = i3; ++iDstTriIndex; // next } else { { unsigned char * pVerts_A = pTriInfos[iDstTriIndex].vert_num; pVerts_A[0]=0; pVerts_A[1]=1; pVerts_A[2]=3; } piTriList_out[iDstTriIndex*3+0] = i0; piTriList_out[iDstTriIndex*3+1] = i1; piTriList_out[iDstTriIndex*3+2] = i3; ++iDstTriIndex; // next { unsigned char * pVerts_B = pTriInfos[iDstTriIndex].vert_num; pVerts_B[0]=1; pVerts_B[1]=2; pVerts_B[2]=3; } piTriList_out[iDstTriIndex*3+0] = i1; piTriList_out[iDstTriIndex*3+1] = i2; piTriList_out[iDstTriIndex*3+2] = i3; ++iDstTriIndex; // next } } } iTSpacesOffs += verts; assert(iDstTriIndex<=iNrTrianglesIn); } for (t=0; t<iNrTrianglesIn; t++) pTriInfos[t].iFlag = 0; // return total amount of tspaces return iTSpacesOffs; } static SVec3 GetPosition(const SMikkTSpaceContext * pContext, const int index) { int iF, iI; SVec3 res; float pos[3]; IndexToData(&iF, &iI, index); pContext->m_pInterface->m_getPosition(pContext, pos, iF, iI); res.x=pos[0]; res.y=pos[1]; res.z=pos[2]; return res; } static SVec3 GetNormal(const SMikkTSpaceContext * pContext, const int index) { int iF, iI; SVec3 res; float norm[3]; IndexToData(&iF, &iI, index); pContext->m_pInterface->m_getNormal(pContext, norm, iF, iI); res.x=norm[0]; res.y=norm[1]; res.z=norm[2]; return res; } static SVec3 GetTexCoord(const SMikkTSpaceContext * pContext, const int index) { int iF, iI; SVec3 res; float texc[2]; IndexToData(&iF, &iI, index); pContext->m_pInterface->m_getTexCoord(pContext, texc, iF, iI); res.x=texc[0]; res.y=texc[1]; res.z=1.0f; return res; } ///////////////////////////////////////////////////////////////////////////////////////////////////// ///////////////////////////////////////////////////////////////////////////////////////////////////// typedef union { struct { int i0, i1, f; }; int array[3]; } SEdge; static void BuildNeighborsFast(STriInfo pTriInfos[], SEdge * pEdges, const int piTriListIn[], const int iNrTrianglesIn); static void BuildNeighborsSlow(STriInfo pTriInfos[], const int piTriListIn[], const int iNrTrianglesIn); // returns the texture area times 2 static float CalcTexArea(const SMikkTSpaceContext * pContext, const int indices[]) { const SVec3 t1 = GetTexCoord(pContext, indices[0]); const SVec3 t2 = GetTexCoord(pContext, indices[1]); const SVec3 t3 = GetTexCoord(pContext, indices[2]); const float t21x = t2.x-t1.x; const float t21y = t2.y-t1.y; const float t31x = t3.x-t1.x; const float t31y = t3.y-t1.y; const float fSignedAreaSTx2 = t21x*t31y - t21y*t31x; return fSignedAreaSTx2<0 ? (-fSignedAreaSTx2) : fSignedAreaSTx2; } static void InitTriInfo(STriInfo pTriInfos[], const int piTriListIn[], const SMikkTSpaceContext * pContext, const int iNrTrianglesIn) { int f=0, i=0, t=0; // pTriInfos[f].iFlag is cleared in GenerateInitialVerticesIndexList() which is called before this function. // generate neighbor info list for (f=0; f<iNrTrianglesIn; f++) for (i=0; i<3; i++) { pTriInfos[f].FaceNeighbors[i] = -1; pTriInfos[f].AssignedGroup[i] = NULL; pTriInfos[f].vOs.x=0.0f; pTriInfos[f].vOs.y=0.0f; pTriInfos[f].vOs.z=0.0f; pTriInfos[f].vOt.x=0.0f; pTriInfos[f].vOt.y=0.0f; pTriInfos[f].vOt.z=0.0f; pTriInfos[f].fMagS = 0; pTriInfos[f].fMagT = 0; // assumed bad pTriInfos[f].iFlag |= GROUP_WITH_ANY; } // evaluate first order derivatives for (f=0; f<iNrTrianglesIn; f++) { // initial values const SVec3 v1 = GetPosition(pContext, piTriListIn[f*3+0]); const SVec3 v2 = GetPosition(pContext, piTriListIn[f*3+1]); const SVec3 v3 = GetPosition(pContext, piTriListIn[f*3+2]); const SVec3 t1 = GetTexCoord(pContext, piTriListIn[f*3+0]); const SVec3 t2 = GetTexCoord(pContext, piTriListIn[f*3+1]); const SVec3 t3 = GetTexCoord(pContext, piTriListIn[f*3+2]); const float t21x = t2.x-t1.x; const float t21y = t2.y-t1.y; const float t31x = t3.x-t1.x; const float t31y = t3.y-t1.y; const SVec3 d1 = vsub(v2,v1); const SVec3 d2 = vsub(v3,v1); const float fSignedAreaSTx2 = t21x*t31y - t21y*t31x; //assert(fSignedAreaSTx2!=0); SVec3 vOs = vsub(vscale(t31y,d1), vscale(t21y,d2)); // eq 18 SVec3 vOt = vadd(vscale(-t31x,d1), vscale(t21x,d2)); // eq 19 pTriInfos[f].iFlag |= (fSignedAreaSTx2>0 ? ORIENT_PRESERVING : 0); if ( NotZero(fSignedAreaSTx2) ) { const float fAbsArea = fabsf(fSignedAreaSTx2); const float fLenOs = Length(vOs); const float fLenOt = Length(vOt); const float fS = (pTriInfos[f].iFlag&ORIENT_PRESERVING)==0 ? (-1.0f) : 1.0f; if ( NotZero(fLenOs) ) pTriInfos[f].vOs = vscale(fS/fLenOs, vOs); if ( NotZero(fLenOt) ) pTriInfos[f].vOt = vscale(fS/fLenOt, vOt); // evaluate magnitudes prior to normalization of vOs and vOt pTriInfos[f].fMagS = fLenOs / fAbsArea; pTriInfos[f].fMagT = fLenOt / fAbsArea; // if this is a good triangle if ( NotZero(pTriInfos[f].fMagS) && NotZero(pTriInfos[f].fMagT)) pTriInfos[f].iFlag &= (~GROUP_WITH_ANY); } } // force otherwise healthy quads to a fixed orientation while (t<(iNrTrianglesIn-1)) { const int iFO_a = pTriInfos[t].iOrgFaceNumber; const int iFO_b = pTriInfos[t+1].iOrgFaceNumber; if (iFO_a==iFO_b) // this is a quad { const tbool bIsDeg_a = (pTriInfos[t].iFlag&MARK_DEGENERATE)!=0 ? TTRUE : TFALSE; const tbool bIsDeg_b = (pTriInfos[t+1].iFlag&MARK_DEGENERATE)!=0 ? TTRUE : TFALSE; // bad triangles should already have been removed by // DegenPrologue(), but just in case check bIsDeg_a and bIsDeg_a are false if ((bIsDeg_a||bIsDeg_b)==TFALSE) { const tbool bOrientA = (pTriInfos[t].iFlag&ORIENT_PRESERVING)!=0 ? TTRUE : TFALSE; const tbool bOrientB = (pTriInfos[t+1].iFlag&ORIENT_PRESERVING)!=0 ? TTRUE : TFALSE; // if this happens the quad has extremely bad mapping!! if (bOrientA!=bOrientB) { //printf("found quad with bad mapping\n"); tbool bChooseOrientFirstTri = TFALSE; if ((pTriInfos[t+1].iFlag&GROUP_WITH_ANY)!=0) bChooseOrientFirstTri = TTRUE; else if ( CalcTexArea(pContext, &piTriListIn[t*3+0]) >= CalcTexArea(pContext, &piTriListIn[(t+1)*3+0]) ) bChooseOrientFirstTri = TTRUE; // force match { const int t0 = bChooseOrientFirstTri ? t : (t+1); const int t1 = bChooseOrientFirstTri ? (t+1) : t; pTriInfos[t1].iFlag &= (~ORIENT_PRESERVING); // clear first pTriInfos[t1].iFlag |= (pTriInfos[t0].iFlag&ORIENT_PRESERVING); // copy bit } } } t += 2; } else ++t; } // match up edge pairs { SEdge * pEdges = (SEdge *) malloc(sizeof(SEdge)*iNrTrianglesIn*3); if (pEdges==NULL) BuildNeighborsSlow(pTriInfos, piTriListIn, iNrTrianglesIn); else { BuildNeighborsFast(pTriInfos, pEdges, piTriListIn, iNrTrianglesIn); free(pEdges); } } } ///////////////////////////////////////////////////////////////////////////////////////////////////// ///////////////////////////////////////////////////////////////////////////////////////////////////// static tbool AssignRecur(const int piTriListIn[], STriInfo psTriInfos[], const int iMyTriIndex, SGroup * pGroup); static void AddTriToGroup(SGroup * pGroup, const int iTriIndex); static int Build4RuleGroups(STriInfo pTriInfos[], SGroup pGroups[], int piGroupTrianglesBuffer[], const int piTriListIn[], const int iNrTrianglesIn) { const int iNrMaxGroups = iNrTrianglesIn*3; int iNrActiveGroups = 0; int iOffset = 0, f=0, i=0; (void)iNrMaxGroups; /* quiet warnings in non debug mode */ for (f=0; f<iNrTrianglesIn; f++) { for (i=0; i<3; i++) { // if not assigned to a group if ((pTriInfos[f].iFlag&GROUP_WITH_ANY)==0 && pTriInfos[f].AssignedGroup[i]==NULL) { tbool bOrPre; int neigh_indexL, neigh_indexR; const int vert_index = piTriListIn[f*3+i]; assert(iNrActiveGroups<iNrMaxGroups); pTriInfos[f].AssignedGroup[i] = &pGroups[iNrActiveGroups]; pTriInfos[f].AssignedGroup[i]->iVertexRepresentitive = vert_index; pTriInfos[f].AssignedGroup[i]->bOrientPreservering = (pTriInfos[f].iFlag&ORIENT_PRESERVING)!=0; pTriInfos[f].AssignedGroup[i]->iNrFaces = 0; pTriInfos[f].AssignedGroup[i]->pFaceIndices = &piGroupTrianglesBuffer[iOffset]; ++iNrActiveGroups; AddTriToGroup(pTriInfos[f].AssignedGroup[i], f); bOrPre = (pTriInfos[f].iFlag&ORIENT_PRESERVING)!=0 ? TTRUE : TFALSE; neigh_indexL = pTriInfos[f].FaceNeighbors[i]; neigh_indexR = pTriInfos[f].FaceNeighbors[i>0?(i-1):2]; if (neigh_indexL>=0) // neighbor { const tbool bAnswer = AssignRecur(piTriListIn, pTriInfos, neigh_indexL, pTriInfos[f].AssignedGroup[i] ); const tbool bOrPre2 = (pTriInfos[neigh_indexL].iFlag&ORIENT_PRESERVING)!=0 ? TTRUE : TFALSE; const tbool bDiff = bOrPre!=bOrPre2 ? TTRUE : TFALSE; assert(bAnswer || bDiff); (void)bAnswer, (void)bDiff; /* quiet warnings in non debug mode */ } if (neigh_indexR>=0) // neighbor { const tbool bAnswer = AssignRecur(piTriListIn, pTriInfos, neigh_indexR, pTriInfos[f].AssignedGroup[i] ); const tbool bOrPre2 = (pTriInfos[neigh_indexR].iFlag&ORIENT_PRESERVING)!=0 ? TTRUE : TFALSE; const tbool bDiff = bOrPre!=bOrPre2 ? TTRUE : TFALSE; assert(bAnswer || bDiff); (void)bAnswer, (void)bDiff; /* quiet warnings in non debug mode */ } // update offset iOffset += pTriInfos[f].AssignedGroup[i]->iNrFaces; // since the groups are disjoint a triangle can never // belong to more than 3 groups. Subsequently something // is completely screwed if this assertion ever hits. assert(iOffset <= iNrMaxGroups); } } } return iNrActiveGroups; } static void AddTriToGroup(SGroup * pGroup, const int iTriIndex) { pGroup->pFaceIndices[pGroup->iNrFaces] = iTriIndex; ++pGroup->iNrFaces; } static tbool AssignRecur(const int piTriListIn[], STriInfo psTriInfos[], const int iMyTriIndex, SGroup * pGroup) { STriInfo * pMyTriInfo = &psTriInfos[iMyTriIndex]; // track down vertex const int iVertRep = pGroup->iVertexRepresentitive; const int * pVerts = &piTriListIn[3*iMyTriIndex+0]; int i=-1; if (pVerts[0]==iVertRep) i=0; else if (pVerts[1]==iVertRep) i=1; else if (pVerts[2]==iVertRep) i=2; assert(i>=0 && i<3); // early out if (pMyTriInfo->AssignedGroup[i] == pGroup) return TTRUE; else if (pMyTriInfo->AssignedGroup[i]!=NULL) return TFALSE; if ((pMyTriInfo->iFlag&GROUP_WITH_ANY)!=0) { // first to group with a group-with-anything triangle // determines it's orientation. // This is the only existing order dependency in the code!! if ( pMyTriInfo->AssignedGroup[0] == NULL && pMyTriInfo->AssignedGroup[1] == NULL && pMyTriInfo->AssignedGroup[2] == NULL ) { pMyTriInfo->iFlag &= (~ORIENT_PRESERVING); pMyTriInfo->iFlag |= (pGroup->bOrientPreservering ? ORIENT_PRESERVING : 0); } } { const tbool bOrient = (pMyTriInfo->iFlag&ORIENT_PRESERVING)!=0 ? TTRUE : TFALSE; if (bOrient != pGroup->bOrientPreservering) return TFALSE; } AddTriToGroup(pGroup, iMyTriIndex); pMyTriInfo->AssignedGroup[i] = pGroup; { const int neigh_indexL = pMyTriInfo->FaceNeighbors[i]; const int neigh_indexR = pMyTriInfo->FaceNeighbors[i>0?(i-1):2]; if (neigh_indexL>=0) AssignRecur(piTriListIn, psTriInfos, neigh_indexL, pGroup); if (neigh_indexR>=0) AssignRecur(piTriListIn, psTriInfos, neigh_indexR, pGroup); } return TTRUE; } ///////////////////////////////////////////////////////////////////////////////////////////////////// ///////////////////////////////////////////////////////////////////////////////////////////////////// static tbool CompareSubGroups(const SSubGroup * pg1, const SSubGroup * pg2); static void QuickSort(int* pSortBuffer, int iLeft, int iRight, unsigned int uSeed); static STSpace EvalTspace(int face_indices[], const int iFaces, const int piTriListIn[], const STriInfo pTriInfos[], const SMikkTSpaceContext * pContext, const int iVertexRepresentitive); static tbool GenerateTSpaces(STSpace psTspace[], const STriInfo pTriInfos[], const SGroup pGroups[], const int iNrActiveGroups, const int piTriListIn[], const float fThresCos, const SMikkTSpaceContext * pContext) { STSpace * pSubGroupTspace = NULL; SSubGroup * pUniSubGroups = NULL; int * pTmpMembers = NULL; int iMaxNrFaces=0, iUniqueTspaces=0, g=0, i=0; for (g=0; g<iNrActiveGroups; g++) if (iMaxNrFaces < pGroups[g].iNrFaces) iMaxNrFaces = pGroups[g].iNrFaces; if (iMaxNrFaces == 0) return TTRUE; // make initial allocations pSubGroupTspace = (STSpace *) malloc(sizeof(STSpace)*iMaxNrFaces); pUniSubGroups = (SSubGroup *) malloc(sizeof(SSubGroup)*iMaxNrFaces); pTmpMembers = (int *) malloc(sizeof(int)*iMaxNrFaces); if (pSubGroupTspace==NULL || pUniSubGroups==NULL || pTmpMembers==NULL) { if (pSubGroupTspace!=NULL) free(pSubGroupTspace); if (pUniSubGroups!=NULL) free(pUniSubGroups); if (pTmpMembers!=NULL) free(pTmpMembers); return TFALSE; } iUniqueTspaces = 0; for (g=0; g<iNrActiveGroups; g++) { const SGroup * pGroup = &pGroups[g]; int iUniqueSubGroups = 0, s=0; for (i=0; i<pGroup->iNrFaces; i++) // triangles { const int f = pGroup->pFaceIndices[i]; // triangle number int index=-1, iVertIndex=-1, iOF_1=-1, iMembers=0, j=0, l=0; SSubGroup tmp_group; tbool bFound; SVec3 n, vOs, vOt; if (pTriInfos[f].AssignedGroup[0]==pGroup) index=0; else if (pTriInfos[f].AssignedGroup[1]==pGroup) index=1; else if (pTriInfos[f].AssignedGroup[2]==pGroup) index=2; assert(index>=0 && index<3); iVertIndex = piTriListIn[f*3+index]; assert(iVertIndex==pGroup->iVertexRepresentitive); // is normalized already n = GetNormal(pContext, iVertIndex); // project vOs = vsub(pTriInfos[f].vOs, vscale(vdot(n,pTriInfos[f].vOs), n)); vOt = vsub(pTriInfos[f].vOt, vscale(vdot(n,pTriInfos[f].vOt), n)); if ( VNotZero(vOs) ) vOs = Normalize(vOs); if ( VNotZero(vOt) ) vOt = Normalize(vOt); // original face number iOF_1 = pTriInfos[f].iOrgFaceNumber; iMembers = 0; for (j=0; j<pGroup->iNrFaces; j++) { const int t = pGroup->pFaceIndices[j]; // triangle number const int iOF_2 = pTriInfos[t].iOrgFaceNumber; // project SVec3 vOs2 = vsub(pTriInfos[t].vOs, vscale(vdot(n,pTriInfos[t].vOs), n)); SVec3 vOt2 = vsub(pTriInfos[t].vOt, vscale(vdot(n,pTriInfos[t].vOt), n)); if ( VNotZero(vOs2) ) vOs2 = Normalize(vOs2); if ( VNotZero(vOt2) ) vOt2 = Normalize(vOt2); { const tbool bAny = ( (pTriInfos[f].iFlag | pTriInfos[t].iFlag) & GROUP_WITH_ANY )!=0 ? TTRUE : TFALSE; // make sure triangles which belong to the same quad are joined. const tbool bSameOrgFace = iOF_1==iOF_2 ? TTRUE : TFALSE; const float fCosS = vdot(vOs,vOs2); const float fCosT = vdot(vOt,vOt2); assert(f!=t || bSameOrgFace); // sanity check if (bAny || bSameOrgFace || (fCosS>fThresCos && fCosT>fThresCos)) pTmpMembers[iMembers++] = t; } } // sort pTmpMembers tmp_group.iNrFaces = iMembers; tmp_group.pTriMembers = pTmpMembers; if (iMembers>1) { unsigned int uSeed = INTERNAL_RND_SORT_SEED; // could replace with a random seed? QuickSort(pTmpMembers, 0, iMembers-1, uSeed); } // look for an existing match bFound = TFALSE; l=0; while (l<iUniqueSubGroups && !bFound) { bFound = CompareSubGroups(&tmp_group, &pUniSubGroups[l]); if (!bFound) ++l; } // assign tangent space index assert(bFound || l==iUniqueSubGroups); //piTempTangIndices[f*3+index] = iUniqueTspaces+l; // if no match was found we allocate a new subgroup if (!bFound) { // insert new subgroup int * pIndices = (int *) malloc(sizeof(int)*iMembers); if (pIndices==NULL) { // clean up and return false int s=0; for (s=0; s<iUniqueSubGroups; s++) free(pUniSubGroups[s].pTriMembers); free(pUniSubGroups); free(pTmpMembers); free(pSubGroupTspace); return TFALSE; } pUniSubGroups[iUniqueSubGroups].iNrFaces = iMembers; pUniSubGroups[iUniqueSubGroups].pTriMembers = pIndices; memcpy(pIndices, tmp_group.pTriMembers, iMembers*sizeof(int)); pSubGroupTspace[iUniqueSubGroups] = EvalTspace(tmp_group.pTriMembers, iMembers, piTriListIn, pTriInfos, pContext, pGroup->iVertexRepresentitive); ++iUniqueSubGroups; } // output tspace { const int iOffs = pTriInfos[f].iTSpacesOffs; const int iVert = pTriInfos[f].vert_num[index]; STSpace * pTS_out = &psTspace[iOffs+iVert]; assert(pTS_out->iCounter<2); assert(((pTriInfos[f].iFlag&ORIENT_PRESERVING)!=0) == pGroup->bOrientPreservering); if (pTS_out->iCounter==1) { *pTS_out = AvgTSpace(pTS_out, &pSubGroupTspace[l]); pTS_out->iCounter = 2; // update counter pTS_out->bOrient = pGroup->bOrientPreservering; } else { assert(pTS_out->iCounter==0); *pTS_out = pSubGroupTspace[l]; pTS_out->iCounter = 1; // update counter pTS_out->bOrient = pGroup->bOrientPreservering; } } } // clean up and offset iUniqueTspaces for (s=0; s<iUniqueSubGroups; s++) free(pUniSubGroups[s].pTriMembers); iUniqueTspaces += iUniqueSubGroups; } // clean up free(pUniSubGroups); free(pTmpMembers); free(pSubGroupTspace); return TTRUE; } static STSpace EvalTspace(int face_indices[], const int iFaces, const int piTriListIn[], const STriInfo pTriInfos[], const SMikkTSpaceContext * pContext, const int iVertexRepresentitive) { STSpace res; float fAngleSum = 0; int face=0; res.vOs.x=0.0f; res.vOs.y=0.0f; res.vOs.z=0.0f; res.vOt.x=0.0f; res.vOt.y=0.0f; res.vOt.z=0.0f; res.fMagS = 0; res.fMagT = 0; for (face=0; face<iFaces; face++) { const int f = face_indices[face]; // only valid triangles get to add their contribution if ( (pTriInfos[f].iFlag&GROUP_WITH_ANY)==0 ) { SVec3 n, vOs, vOt, p0, p1, p2, v1, v2; float fCos, fAngle, fMagS, fMagT; int i=-1, index=-1, i0=-1, i1=-1, i2=-1; if (piTriListIn[3*f+0]==iVertexRepresentitive) i=0; else if (piTriListIn[3*f+1]==iVertexRepresentitive) i=1; else if (piTriListIn[3*f+2]==iVertexRepresentitive) i=2; assert(i>=0 && i<3); // project index = piTriListIn[3*f+i]; n = GetNormal(pContext, index); vOs = vsub(pTriInfos[f].vOs, vscale(vdot(n,pTriInfos[f].vOs), n)); vOt = vsub(pTriInfos[f].vOt, vscale(vdot(n,pTriInfos[f].vOt), n)); if ( VNotZero(vOs) ) vOs = Normalize(vOs); if ( VNotZero(vOt) ) vOt = Normalize(vOt); i2 = piTriListIn[3*f + (i<2?(i+1):0)]; i1 = piTriListIn[3*f + i]; i0 = piTriListIn[3*f + (i>0?(i-1):2)]; p0 = GetPosition(pContext, i0); p1 = GetPosition(pContext, i1); p2 = GetPosition(pContext, i2); v1 = vsub(p0,p1); v2 = vsub(p2,p1); // project v1 = vsub(v1, vscale(vdot(n,v1),n)); if ( VNotZero(v1) ) v1 = Normalize(v1); v2 = vsub(v2, vscale(vdot(n,v2),n)); if ( VNotZero(v2) ) v2 = Normalize(v2); // weight contribution by the angle // between the two edge vectors fCos = vdot(v1,v2); fCos=fCos>1?1:(fCos<(-1) ? (-1) : fCos); fAngle = (float) acos(fCos); fMagS = pTriInfos[f].fMagS; fMagT = pTriInfos[f].fMagT; res.vOs=vadd(res.vOs, vscale(fAngle,vOs)); res.vOt=vadd(res.vOt,vscale(fAngle,vOt)); res.fMagS+=(fAngle*fMagS); res.fMagT+=(fAngle*fMagT); fAngleSum += fAngle; } } // normalize if ( VNotZero(res.vOs) ) res.vOs = Normalize(res.vOs); if ( VNotZero(res.vOt) ) res.vOt = Normalize(res.vOt); if (fAngleSum>0) { res.fMagS /= fAngleSum; res.fMagT /= fAngleSum; } return res; } static tbool CompareSubGroups(const SSubGroup * pg1, const SSubGroup * pg2) { tbool bStillSame=TTRUE; int i=0; if (pg1->iNrFaces!=pg2->iNrFaces) return TFALSE; while (i<pg1->iNrFaces && bStillSame) { bStillSame = pg1->pTriMembers[i]==pg2->pTriMembers[i] ? TTRUE : TFALSE; if (bStillSame) ++i; } return bStillSame; } static void QuickSort(int* pSortBuffer, int iLeft, int iRight, unsigned int uSeed) { int iL, iR, n, index, iMid, iTmp; // Random unsigned int t=uSeed&31; t=(uSeed<<t)|(uSeed>>(32-t)); uSeed=uSeed+t+3; // Random end iL=iLeft; iR=iRight; n = (iR-iL)+1; assert(n>=0); index = (int) (uSeed%n); iMid=pSortBuffer[index + iL]; do { while (pSortBuffer[iL] < iMid) ++iL; while (pSortBuffer[iR] > iMid) --iR; if (iL <= iR) { iTmp = pSortBuffer[iL]; pSortBuffer[iL] = pSortBuffer[iR]; pSortBuffer[iR] = iTmp; ++iL; --iR; } } while (iL <= iR); if (iLeft < iR) QuickSort(pSortBuffer, iLeft, iR, uSeed); if (iL < iRight) QuickSort(pSortBuffer, iL, iRight, uSeed); } ///////////////////////////////////////////////////////////////////////////////////////////// ///////////////////////////////////////////////////////////////////////////////////////////// static void QuickSortEdges(SEdge * pSortBuffer, int iLeft, int iRight, const int channel, unsigned int uSeed); static void GetEdge(int * i0_out, int * i1_out, int * edgenum_out, const int indices[], const int i0_in, const int i1_in); static void BuildNeighborsFast(STriInfo pTriInfos[], SEdge * pEdges, const int piTriListIn[], const int iNrTrianglesIn) { // build array of edges unsigned int uSeed = INTERNAL_RND_SORT_SEED; // could replace with a random seed? int iEntries=0, iCurStartIndex=-1, f=0, i=0; for (f=0; f<iNrTrianglesIn; f++) for (i=0; i<3; i++) { const int i0 = piTriListIn[f*3+i]; const int i1 = piTriListIn[f*3+(i<2?(i+1):0)]; pEdges[f*3+i].i0 = i0 < i1 ? i0 : i1; // put minimum index in i0 pEdges[f*3+i].i1 = !(i0 < i1) ? i0 : i1; // put maximum index in i1 pEdges[f*3+i].f = f; // record face number } // sort over all edges by i0, this is the pricy one. QuickSortEdges(pEdges, 0, iNrTrianglesIn*3-1, 0, uSeed); // sort channel 0 which is i0 // sub sort over i1, should be fast. // could replace this with a 64 bit int sort over (i0,i1) // with i0 as msb in the quicksort call above. iEntries = iNrTrianglesIn*3; iCurStartIndex = 0; for (i=1; i<iEntries; i++) { if (pEdges[iCurStartIndex].i0 != pEdges[i].i0) { const int iL = iCurStartIndex; const int iR = i-1; //const int iElems = i-iL; iCurStartIndex = i; QuickSortEdges(pEdges, iL, iR, 1, uSeed); // sort channel 1 which is i1 } } // sub sort over f, which should be fast. // this step is to remain compliant with BuildNeighborsSlow() when // more than 2 triangles use the same edge (such as a butterfly topology). iCurStartIndex = 0; for (i=1; i<iEntries; i++) { if (pEdges[iCurStartIndex].i0 != pEdges[i].i0 || pEdges[iCurStartIndex].i1 != pEdges[i].i1) { const int iL = iCurStartIndex; const int iR = i-1; //const int iElems = i-iL; iCurStartIndex = i; QuickSortEdges(pEdges, iL, iR, 2, uSeed); // sort channel 2 which is f } } // pair up, adjacent triangles for (i=0; i<iEntries; i++) { const int i0=pEdges[i].i0; const int i1=pEdges[i].i1; const int f = pEdges[i].f; tbool bUnassigned_A; int i0_A, i1_A; int edgenum_A, edgenum_B=0; // 0,1 or 2 GetEdge(&i0_A, &i1_A, &edgenum_A, &piTriListIn[f*3], i0, i1); // resolve index ordering and edge_num bUnassigned_A = pTriInfos[f].FaceNeighbors[edgenum_A] == -1 ? TTRUE : TFALSE; if (bUnassigned_A) { // get true index ordering int j=i+1, t; tbool bNotFound = TTRUE; while (j<iEntries && i0==pEdges[j].i0 && i1==pEdges[j].i1 && bNotFound) { tbool bUnassigned_B; int i0_B, i1_B; t = pEdges[j].f; // flip i0_B and i1_B GetEdge(&i1_B, &i0_B, &edgenum_B, &piTriListIn[t*3], pEdges[j].i0, pEdges[j].i1); // resolve index ordering and edge_num //assert(!(i0_A==i1_B && i1_A==i0_B)); bUnassigned_B = pTriInfos[t].FaceNeighbors[edgenum_B]==-1 ? TTRUE : TFALSE; if (i0_A==i0_B && i1_A==i1_B && bUnassigned_B) bNotFound = TFALSE; else ++j; } if (!bNotFound) { int t = pEdges[j].f; pTriInfos[f].FaceNeighbors[edgenum_A] = t; //assert(pTriInfos[t].FaceNeighbors[edgenum_B]==-1); pTriInfos[t].FaceNeighbors[edgenum_B] = f; } } } } static void BuildNeighborsSlow(STriInfo pTriInfos[], const int piTriListIn[], const int iNrTrianglesIn) { int f=0, i=0; for (f=0; f<iNrTrianglesIn; f++) { for (i=0; i<3; i++) { // if unassigned if (pTriInfos[f].FaceNeighbors[i] == -1) { const int i0_A = piTriListIn[f*3+i]; const int i1_A = piTriListIn[f*3+(i<2?(i+1):0)]; // search for a neighbor tbool bFound = TFALSE; int t=0, j=0; while (!bFound && t<iNrTrianglesIn) { if (t!=f) { j=0; while (!bFound && j<3) { // in rev order const int i1_B = piTriListIn[t*3+j]; const int i0_B = piTriListIn[t*3+(j<2?(j+1):0)]; //assert(!(i0_A==i1_B && i1_A==i0_B)); if (i0_A==i0_B && i1_A==i1_B) bFound = TTRUE; else ++j; } } if (!bFound) ++t; } // assign neighbors if (bFound) { pTriInfos[f].FaceNeighbors[i] = t; //assert(pTriInfos[t].FaceNeighbors[j]==-1); pTriInfos[t].FaceNeighbors[j] = f; } } } } } static void QuickSortEdges(SEdge * pSortBuffer, int iLeft, int iRight, const int channel, unsigned int uSeed) { unsigned int t; int iL, iR, n, index, iMid; // early out SEdge sTmp; const int iElems = iRight-iLeft+1; if (iElems<2) return; else if (iElems==2) { if (pSortBuffer[iLeft].array[channel] > pSortBuffer[iRight].array[channel]) { sTmp = pSortBuffer[iLeft]; pSortBuffer[iLeft] = pSortBuffer[iRight]; pSortBuffer[iRight] = sTmp; } return; } // Random t=uSeed&31; t=(uSeed<<t)|(uSeed>>(32-t)); uSeed=uSeed+t+3; // Random end iL=iLeft, iR=iRight; n = (iR-iL)+1; assert(n>=0); index = (int) (uSeed%n); iMid=pSortBuffer[index + iL].array[channel]; do { while (pSortBuffer[iL].array[channel] < iMid) ++iL; while (pSortBuffer[iR].array[channel] > iMid) --iR; if (iL <= iR) { sTmp = pSortBuffer[iL]; pSortBuffer[iL] = pSortBuffer[iR]; pSortBuffer[iR] = sTmp; ++iL; --iR; } } while (iL <= iR); if (iLeft < iR) QuickSortEdges(pSortBuffer, iLeft, iR, channel, uSeed); if (iL < iRight) QuickSortEdges(pSortBuffer, iL, iRight, channel, uSeed); } // resolve ordering and edge number static void GetEdge(int * i0_out, int * i1_out, int * edgenum_out, const int indices[], const int i0_in, const int i1_in) { *edgenum_out = -1; // test if first index is on the edge if (indices[0]==i0_in || indices[0]==i1_in) { // test if second index is on the edge if (indices[1]==i0_in || indices[1]==i1_in) { edgenum_out[0]=0; // first edge i0_out[0]=indices[0]; i1_out[0]=indices[1]; } else { edgenum_out[0]=2; // third edge i0_out[0]=indices[2]; i1_out[0]=indices[0]; } } else { // only second and third index is on the edge edgenum_out[0]=1; // second edge i0_out[0]=indices[1]; i1_out[0]=indices[2]; } } ///////////////////////////////////////////////////////////////////////////////////////////// /////////////////////////////////// Degenerate triangles //////////////////////////////////// static void DegenPrologue(STriInfo pTriInfos[], int piTriList_out[], const int iNrTrianglesIn, const int iTotTris) { int iNextGoodTriangleSearchIndex=-1; tbool bStillFindingGoodOnes; // locate quads with only one good triangle int t=0; while (t<(iTotTris-1)) { const int iFO_a = pTriInfos[t].iOrgFaceNumber; const int iFO_b = pTriInfos[t+1].iOrgFaceNumber; if (iFO_a==iFO_b) // this is a quad { const tbool bIsDeg_a = (pTriInfos[t].iFlag&MARK_DEGENERATE)!=0 ? TTRUE : TFALSE; const tbool bIsDeg_b = (pTriInfos[t+1].iFlag&MARK_DEGENERATE)!=0 ? TTRUE : TFALSE; if ((bIsDeg_a^bIsDeg_b)!=0) { pTriInfos[t].iFlag |= QUAD_ONE_DEGEN_TRI; pTriInfos[t+1].iFlag |= QUAD_ONE_DEGEN_TRI; } t += 2; } else ++t; } // reorder list so all degen triangles are moved to the back // without reordering the good triangles iNextGoodTriangleSearchIndex = 1; t=0; bStillFindingGoodOnes = TTRUE; while (t<iNrTrianglesIn && bStillFindingGoodOnes) { const tbool bIsGood = (pTriInfos[t].iFlag&MARK_DEGENERATE)==0 ? TTRUE : TFALSE; if (bIsGood) { if (iNextGoodTriangleSearchIndex < (t+2)) iNextGoodTriangleSearchIndex = t+2; } else { int t0, t1; // search for the first good triangle. tbool bJustADegenerate = TTRUE; while (bJustADegenerate && iNextGoodTriangleSearchIndex<iTotTris) { const tbool bIsGood = (pTriInfos[iNextGoodTriangleSearchIndex].iFlag&MARK_DEGENERATE)==0 ? TTRUE : TFALSE; if (bIsGood) bJustADegenerate=TFALSE; else ++iNextGoodTriangleSearchIndex; } t0 = t; t1 = iNextGoodTriangleSearchIndex; ++iNextGoodTriangleSearchIndex; assert(iNextGoodTriangleSearchIndex > (t+1)); // swap triangle t0 and t1 if (!bJustADegenerate) { int i=0; for (i=0; i<3; i++) { const int index = piTriList_out[t0*3+i]; piTriList_out[t0*3+i] = piTriList_out[t1*3+i]; piTriList_out[t1*3+i] = index; } { const STriInfo tri_info = pTriInfos[t0]; pTriInfos[t0] = pTriInfos[t1]; pTriInfos[t1] = tri_info; } } else bStillFindingGoodOnes = TFALSE; // this is not supposed to happen } if (bStillFindingGoodOnes) ++t; } assert(bStillFindingGoodOnes); // code will still work. assert(iNrTrianglesIn == t); } static void DegenEpilogue(STSpace psTspace[], STriInfo pTriInfos[], int piTriListIn[], const SMikkTSpaceContext * pContext, const int iNrTrianglesIn, const int iTotTris) { int t=0, i=0; // deal with degenerate triangles // punishment for degenerate triangles is O(N^2) for (t=iNrTrianglesIn; t<iTotTris; t++) { // degenerate triangles on a quad with one good triangle are skipped // here but processed in the next loop const tbool bSkip = (pTriInfos[t].iFlag&QUAD_ONE_DEGEN_TRI)!=0 ? TTRUE : TFALSE; if (!bSkip) { 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)) { const int index2 = piTriListIn[j]; if (index1==index2) bNotFound=TFALSE; else ++j; } 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]; } } } } // deal with degenerate quads with one good triangle for (t=0; t<iNrTrianglesIn; t++) { // this triangle belongs to a quad where the // other triangle is degenerate if ( (pTriInfos[t].iFlag&QUAD_ONE_DEGEN_TRI)!=0 ) { SVec3 vDstP; int iOrgF=-1, i=0; tbool bNotFound; unsigned char * pV = pTriInfos[t].vert_num; int iFlag = (1<<pV[0]) | (1<<pV[1]) | (1<<pV[2]); int iMissingIndex = 0; if ((iFlag&2)==0) iMissingIndex=1; else if ((iFlag&4)==0) iMissingIndex=2; else if ((iFlag&8)==0) iMissingIndex=3; iOrgF = pTriInfos[t].iOrgFaceNumber; vDstP = GetPosition(pContext, MakeIndex(iOrgF, iMissingIndex)); bNotFound = TTRUE; i=0; while (bNotFound && i<3) { const int iVert = pV[i]; const SVec3 vSrcP = GetPosition(pContext, MakeIndex(iOrgF, iVert)); if (veq(vSrcP, vDstP)==TTRUE) { const int iOffs = pTriInfos[t].iTSpacesOffs; psTspace[iOffs+iMissingIndex] = psTspace[iOffs+iVert]; bNotFound=TFALSE; } else ++i; } assert(!bNotFound); } } }