summaryrefslogtreecommitdiff
path: root/scene/resources/mikktspace.c
diff options
context:
space:
mode:
Diffstat (limited to 'scene/resources/mikktspace.c')
-rw-r--r--scene/resources/mikktspace.c1890
1 files changed, 1890 insertions, 0 deletions
diff --git a/scene/resources/mikktspace.c b/scene/resources/mikktspace.c
new file mode 100644
index 0000000000..62aa2da251
--- /dev/null
+++ b/scene/resources/mikktspace.c
@@ -0,0 +1,1890 @@
+/** \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);
+ }
+ }
+}
generated by cgit v1.2.3 (git 2.25.1) at 2024-12-18 04:18:54 +0000